[강화학습] Markov Decision Process

Vaughan·2023년 1월 24일
MDPbellman expectation equationbellman optimality equation
0

강화학습

목록 보기
3/6
post-thumbnail

본 포스팅은 David Silver 교수님의 강화학습 강의와 그 강의를 정리한 팡요랩 강의를 바탕으로 정리한 것입니다.


문제를 해결하기 위해서는 먼저 문제를 잘 정의하는 것에서부터 시작하여야한다.

대부분의 강화학습 문제는 Environment를 MDP로 formal하게 표현할 수 있다.(fully observable) 그렇다면 MDP는 무엇이며, MDP를 풀기 위해서는 어떻게 해야하는가?

1. Markov Processes : MP

1.1 Markov Property

✂️ “The future is independent of the past given the present”

  • Definition of Markov Property
    A state StS_t is Markov if and only if

    P[St+1∣St]=P[St+1∣S1.⋯ ,St]\mathbb P[S_{t+1}|S_t] = \mathbb P [S_{t+1} | S_1. \cdots, S_t]
    • 시작 state S1S_1에서부터 현재 state St+1S_{t+1}까지 도달할 확률이 바로 이전 state StS_{t}에서 현재 state St+1S_{t+1}까지 도달할 확률과 같은 state를 Markov state라고 한다.
    • 이전 state만 알 수 있다면, 이전까지의 모든 history는 잊어버려도 된다.
    • 강화학습의 문제는 기본적으로 MDP로 표현하기 때문에 Markov Property를 따른다고 가정한다.

  • State Transition Matrix

    • Basic Markov Process에서는 action 없이, 매번의 time-step마다 state를 확률에 기반하여 옮겨다니게 된다.

    • Markov state ss에서 s′s'로 transition할 probability은 다음과 같이 정의된다.

      Pss′=P[St+1=s′∣St=s]\mathcal P_{ss'} = \mathbb P[S_{t+1}=s' | S_t = s]

    • 가능한 모든 state ss와 s′s' pair를 원소로 갖는 matrix로 표현할 수 있다. (matrix의 각각의 row의 합은 1)

      P=[P11⋯P1n⋮⋮Pn1⋯Pnn]\mathcal P = \begin{bmatrix} \mathcal P_{11} & \cdots & \mathcal P_{1n} \\ \vdots & & \vdots \\ \mathcal P_{n1} & \cdots & \mathcal P _{nn}\end{bmatrix}

1.2 Definition of Markov Processes

  • Definition of Markov Processes
    A Markov Process is a tuple <S,P>< \mathcal S, \mathcal P >
    • S\mathcal S is a (finite) set of states
    • P\mathcal P is a state transition probability matrix,
      Pss′=P[St+1=s′∣St=s]\mathcal P _{ss'} = \mathbb P [S_{t+1}=s'|S_t = s]
    • Markov process는 memoryless random process이다.
      • memoryless는 내가 지금까지 어떤 경로를 따라 도달했는지 상관없이 state s에 도달한 순간, s′s'를 결정할 수 있다.
      • random process는 동일한 state에서 시작하더라도 어떤 state를 거치는지에 따라 여러가지 episode를 샘플링을 할 수 있다는 뜻이다.
        → 즉, random한 state들의 sequence S1,S2,⋯S_1, S_2, \cdots 는 Markov property를 따른다!

1.3 Example of Markov Processes

  • 위와 같은 model에서 S1=C1S_1=C1에서 시작하는 Sample episode는 다음과 같은 것들이 있을 수 있다.
    • C1 → C2 → C3 → Pass → Sleep
    • C1 → FB → FB → C1 → C2 → Sleep
    • C1 → C2 → C3 → Pub → C2 → C3 → Pass → Sleep
    • C1 → FB → FB → C1 → C2 → C3 → Pub → C1 → FB → FB → FB → C1 → C2 → C3 → Pub → C2 → Sleep
  • Model의 Edge에 표기된 probability를 바탕으로 다음과 같은 Transition Matrix를 정의할 수 있다.


2. Markov Reward Processes : MRP

2.1 Definition of Markov Reward Processes

  • Definition of Markov Reward Processes

    A Markov Reward Process is a tuple <S,P,R,γ>< \mathcal S, \mathcal P , \color{red} \mathcal R, \mathcal \gamma \color{b}>

    • S\mathcal S is a finite set of states
    • P\mathcal P is a state transition probability matrix, Pss′=P[St+1=s′∣St=s]\mathcal P_{ss'} = \mathbb P [S_{t+1}=s'|S_t = s]
    • R\mathcal R is a reward function, Rs=E[Rt+1∣St=s]\mathcal R_s = \mathbb E[R_{t+1} | S_t = s]
    • γ\gamma is a discount factor, γ∈[0,1]\gamma \in [0, 1]
  • Reward
    • state의 변화에 따른 reward를 “environment”가 Agent에게 알려준다.
    • MRP에서는 현재 state St=sS_t=s에 도달하면 Reward Rt+1R_{t+1}을 제공한다.
    • Agent는 immediate reward 뿐만 아니라, 이후로 얻게되는 미래의 reward까지 고려한다. (with discount)

2.2 Value function

  • Definition of Return

    The return GtG_t is the total discounted reward from time-step tt

    Gt=Rt+1+γRt+2+⋯=∑k=0∞γkRt+k+1G_t = R_{t+1} + \gamma R_{t+2} + \cdots = \sum^\infin_{k=0} \gamma^k R_{t+k+1}

    • discount γ∈[0,1]\gamma \in [0,1]

      • k+1k+1 time-step이후의 reward는 γkR\gamma^k R의 reward로 표현된다.
      • immediate reward가 delayed reward보다 더 큰 영향을 줄 수 있게 한다.

    • ∗γ*\gamma 값에 따른 효과*

      • 00에 가까울수록 “myopic” evaluation (근시안적)
      • 11에 가까울수록 “far-sighted” evaluation (미래지향적)

    • why discount?

      discount가 없을 때 발생할 수 있는 문제점

      • infinite한 time-step을 가질 때, 매 time step마다 0.1의 reward를 받는 episode와 1의 reward를 받는 episode를 구분할 수 없다. (∞\infin 크기비교 불가)
      • Agent가 시작할 떄 1을 받은 경우와 종료할 때 1을 받은 경우 둘 중에 어떤 episode가 더 나은지를 판단할 수 없다.

  • Definition of Value Function

    The state value function v(s)v(s) of an MRP is the expected return starting from state ss

    v(s)=E[Gt∣St=s]v(s) = \mathbb E[G_t|S_t=s]
    • 현재 state ss에서 Return에 대한 기댓값으로 value function을 정의할 수 있다.

2.3 Bellman Equation for MRPs

  • Bellman Equation

    • value function은 다음의 2가지 part로 분리할 수 있다.

      • immediate reward Rt+1R_{t+1}
      • discounted value of successor state γv(St+1)\gamma v(S_{t+1})

    • 유도과정

      1. v(s)=E[Gt∣St=s]v(s) = \mathbb E [G_t | S_t = s]
      2. =E[Rt+1+γRt+2+γ2Rt+3+⋯∣St=s]= \mathbb E [R_{t+1}+\gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots | S_t=s]
      3. =E[Rt+1+γ(Rt+2+γRt+3+⋯ )∣St=s]= \mathbb E [R_{t+1}+\gamma (R_{t+2} + \gamma R_{t+3} + \cdots) | S_t=s]
      4. =E[Rt+1+γGt+1∣St=s]= \mathbb E [R_{t+1}+\gamma G_{t+1} | S_t=s]
      5. =E[Rt+1+γv(St+1)∣St=s]= \mathbb E [R_{t+1}+\gamma v(S_{t+1}) | S_t=s]

  • Bellman Equation의 직관적인 이해

    • Bellman Equation

      v(s)=E[Rt+1+γv(St+1)∣St=s]v(s) = \mathbb E [R_{t+1} + \gamma v(S_{t+1})|S_t = s]

      현재 state ss가 transition할 수 있는 다음 state s′s'들의 후보는 여러가지가 있을 수 있다. 여러가지 후보 중에서 “확률”에 따라 next state를 결정하게 된다. 따라서 가능한 여러가지 episode들에 대한 기댓값으로서 리턴을 계산하며, 이 때 같은 value-function을 사용하여 재귀 형태로 표현할 수 있게된다.

    • Expectation을 제거한 형태

      • MRP에서 1-step Reward는 현재의 state ss에 따라 고정된 상수이기 때문에 그대로 빠져나온다.
      • v(s′)v(s')는 next state s’가 무엇인지에 따라 달라지는 값이기 때문에 Expectation을 적용한다.
        *Definition of Expectation : probability ×\times value
      v(s)=Rs+γ∑s′∈SPss′v(s′)v(s) = \mathcal R_s + \gamma\sum_{s'\in \mathcal S} \mathcal P_{ss'}v(s')

  • for Matrix Form

    v=R+γPvv = \mathcal R + \gamma \mathcal Pv

    ∗v*v is a column vector with one entry per state*

    [v(1)⋮v(n)]=[R1⋮Rn]+γ[P11⋯P1n⋮⋮Pn1⋯Pnn][v(1)⋮v(n)]\begin{bmatrix} v(1) \\ \vdots \\ v(n) \end{bmatrix} = \begin{bmatrix} \mathcal R_1 \\ \vdots \\ \mathcal R_n \end{bmatrix} + \gamma \begin{bmatrix} \mathcal P_{11} & \cdots & \mathcal P_{1n} \\ \vdots & & \vdots \\ \mathcal P_{n1} & \cdots & \mathcal P_{nn} \end{bmatrix} \begin{bmatrix} v(1) \\ \vdots \\ v(n) \end{bmatrix}

    • solving Bellman Equation

      v=R+γPvv = \mathcal R + \gamma \mathcal Pv
      (I−γP)v=R(I-\gamma\mathcal P) v = \mathcal R
      v=(I−γP)−1Rv = (I - \gamma \mathcal P)^{-1} \mathcal R

      ⇒ Bellman Equation을 linear equation으로 표현하여 directly solve할 수 있다!

    • 단점

      • 단, computational complexity가 O(n3)O(n^3)이다.
      • state가 커질수록 계산량이 매우 커지기 때문에 direct solution은 small MRPs에만 적용한다.

    • 대부분의 경우 MRPs는 iterative method를 이용하여 해결한다.

      • Dynamic Programming
      • Monte-Carlo evaluation
      • Temporal-Difference learning

      여기서 소개된 iterative method는 MDP를 solve하기 위해서 사용되는 방법이기도 하다. MRP와 달리 MDP는 directly solve를 위한 방법이 존재하지 않기 때문에, iterative method를 채택한다.


2.4 Example of MRPs

  • Sample returns for Student MRP

    starting from S1=C1S_1 = C1 with γ=0.5\gamma = 0.5 일 때, 각각의 sample episode들에 대한 Return은 다음과 같이 계산될 수 있다.

    G1=R2+γR3+⋯+γT−2RTG_1 = R_2 + \gamma R_3 + \cdots + \gamma^{T-2}R_T

  • discount value에 따른 state value의 변화

  • Bellman Equation

    Q. 빨간색 state의 value가 4.34.3이라고 알려져 있을 떄, Bellman Equation을 만족하는가?


3. Markov Decision Processes : MDP

3.1 Definition of Markov Decision Processes

MP, MRP에서는 state의 변화가 오로지 Environment의 transition probability P\mathcal P에 의해 결정되었다.

그러나 MDP에서는 state의 변화가 Agent의 Action A\mathcal A에 의해 결정되게 된다! (다만, 여전히 환경의 불안정함은 존재)

  • Definition of Markov Reward Processes

    A Markov Reward Process is a tuple <S,A,P,R,γ>< \mathcal S, \color{red} \mathcal A, \color{b}\mathcal P , \mathcal R, \mathcal \gamma>

    • S\mathcal S is a finite set of states
    • A\mathcal A is a finite set of actions
    • P\mathcal P is a state transition probability matrix, Pss′a=P[St+1=s′∣St=s,At=a]\mathcal P^{a}_{ss'} = \mathbb P [S_{t+1}=s'|S_t = s, A_t = \color {red} a \color{b} ] → state ss에서 action aa를 취할 때, state s′s'에 도달할 확률 (환경의 불안정함)
    • R\mathcal R is a reward function, Rsa=E[Rt+1∣St=s,At=a]\mathcal R^a_s = \mathbb E[R_{t+1} | S_t = s, A_t = \color{red} a \color{b} ]
    • γ\gamma is a discount factor, γ∈[0,1]\gamma \in [0, 1]
  • state transition probability
    • Agent가 어떠한 Action을 취했을 때, Agent가 인식하는 state가 deterministic하게 결정되지 않고 “확률”적으로 정해지게 된다.
    • 또한 해당 state에서 그 Action을 할 확률도 정해진다.
    • Example) 무인이동체가 우회전이라는 action을 결정했지만, 그 순간 빨간불로 신호가 바뀌어 우회전을 하지 못하고 정지하는 경우

3.2 Policy & Value function

  • Definition of Policy

    A policy π\pi is a distribution over actions given states,

    π(a∣s)=P[At=a∣St=s]\pi(a|s) = \mathbb P[A_t=a|S_t=s]
    • state ss에서 action aa를 수행할 확률 분포
    • Agent는 policy를 따라서 어떤 action을 선택할지를 결정하게 된다.
    • MDP의 policy는 agent가 지금까지 겪어온 history가 아닌, 오직 current state에 의해서만 의존한다.[1]^{[1]}
    • Policies are stationary (time-independent)
      At∼π(⋅∣St),  ∀t>0A_t ∼ \pi (\cdot|S_t),\ \ \forall t>0

  • (번외) policy와 MDP를 이용하여 MRP로 표현하기

    MDP에서 Agent의 policy가 고정이라면 Agent가 없는 Markov Process로 표현할 수 있다.

    Given an MDP M=<S,A,P,R,γ>\mathcal M = < \mathcal S, \mathcal A, \mathcal P, \mathcal R, \gamma> and a policy π\pi

    • State sequence S1,S2,⋯S_1, S_2, \cdots → Markov process <S,Pπ><\mathcal S, \mathcal P^\pi> 로 표현할 수 있다.
    • State and Reward sequence S1,R2,S2,⋯S_1, R_2, S_2, \cdots → Markov reward process <S,Pπ,Rπ,γ><\mathcal S, \mathcal P^\pi, \mathcal R^\pi, \gamma> 로 표현할 수 있다.
      *where : policy가 고정되어있다면, 어떤 action 선택하고-transition probability에 따라 최종적으로 어떤 state가 next state가 되는지를 확률로서 계산할 수 있다.
      • transition probability : s′s'으로 갈 확률은 각 action의 확률 ×\times action aa를 했을 때 s′s'로 갈 확률의 합(기댓값)
      • reward : ss의 return은 각 action의 확률 ×\times action aa를 했을 때 ss의 reward의 합(기댓값)
        Ps,s′π=∑a∈Aπ(a∣s)Pss′a\mathcal P^\pi_{s,s'} = \sum_{a\in\mathcal A} \pi(a|s) \mathcal P^a_{ss'}
        Rsπ=∑a∈Aπ(a∣s)Rsa\mathcal R^\pi_{s} = \sum_{a\in\mathcal A} \pi(a|s) \mathcal R^a_{s}

  • Value Function

    • 어떤 “policy” 를 따라 episode를 진행하는지에 따라 value가 달라질 수 있기 때문에, Agent가 어떻게 행동하는지를 나타내는 policy π\pi를 함께 기술해야한다.

    • Definition of state-value function

      The state value function vπ(s)v_\pi(s) of an MDP is the expected return starting from state ss, and then following policy π\pi

      vπ(s)=Eπ[Gt∣St=s]v_\pi(s) = \mathbb E_\pi[G_t|S_t=s]

    • Definition of action-value function

      The action value function qπ(s,a)q_\pi(s, a) is the expected return starting from state ss, taking action aa, and then following policy π\pi

      qπ(s,a)=Eπ[Gt∣St=s,At=a]q_\pi(s,a) = \mathbb E_\pi[G_t|S_t=s, A_t = a]
      • 현재 state ss에서 선택하는 action aa는 policy를 따라 선택한 것이 아닐수도 있다! 단, 이후 episode를 진행할 때는 policy π\pi를 따라 진행하게 된다.
      • action-value function이 정의된다면, Agent가 어떤 action을 선택할 지 결정할 때 Action value function의 값을 보고 선택하기만 하면된다.
        ⇒ 즉, 문제를 간단하게 표현할 수 있다.
        (state value function을 사용하면 다른 state들의 value function을 알아야하며, 그때 어떤 action을 했을 때 s′s'로 가게될 확률도 알고 있어야한다.)
      • Q-learning이나 DQN같은 곳에서 사용하는 Q가 바로 action-value function을 의미한다.

3.3 Bellman Expectation Equation

MRP에서 value function을 2가지 part(immediate reward, discounted value)로 분리했던 과정을 동일하게 적용하면 MDP에서도 초기 Bellman Equation을 쉽게 얻을 수 있다.

  • Bellman Expectation Equation (초기)

    • Bellman Expectation Equation for vπv_\pi

      ss에서의 state-value는 ∗∗π**\pi를 따라** 1-step 수행하여 받은 reward와 next-state St+1S_{t+1}에서의 value의 합의 기댓값과 동일하다.

    vπ(s)=Eπ[Rt+1+γvπ(St+1)∣St=s] v_\pi(s) = \mathbb E_\pi[R_{t+1} + \gamma v_\pi(S_{t+1})|S_t=s] \\ \ \\

    • state와 action의 관계 - (1)

      • state의 value는 그 state에서 가능한 모든 action(a∈Aa\in \mathcal A)에 대한 action-value의 기댓값과 동일하다.
      • action의 선택은 오로지 policy에 의존하기 때문에 확률분포에 따라 episode별로 선택된 action이 달라지고 따라서 reward가 변화하여 정확한 값을 모르기 때문에 기댓값 형태로 표현해야한다.
      • state-value function의 definition이 policy에 의해 선택된 action에 대한 가능한 모든 episode의 리턴의 기댓값이기 때문에 Q-function으로 표현할 수 있다.

      → GtG_t에 대한 기댓값의 다른 표현

vπ(s)=∑a∈Aπ(a∣s)qπ(s,a)v_\pi(s) =\sum_{a\in\mathcal A} \pi(a|s) q_\pi(s,a)

  • Bellman Expectation Equation for qπq_\pi

    ss에서 action aa를 선택하여 받은 action-value는 aa를 선택해 1-step 수행하여 받은 reward와 next-state St+1S_{t+1}에서의 action-value의 합의 기댓값과 동일하다.

    qπ(s,a)=Eπ[Rt+1+γqπ(St+1,At+1)∣St=s,At=a] q_\pi(s,a) = \mathbb E_\pi[R_{t+1} + \gamma q_\pi(S_{t+1}, A_{t+1})|S_t=s, A_t = a]\\\ \\

    • action과 state의 관계 - (2)

      • action의 value는 action을 수행함으로써 전달받는 1-step reward Rsa\mathcal R^a_s과 가능한 모든 next-state(s′∈Ss'\in \mathcal S)에 대한 state-value의 (감쇄)기댓값의 합과 동일하다.

      • 특정 action aa를 수행하면 그 때 받게되는 reward의 값을 확실하게 알 수 있기 때문에 immediate rewrd를 이용하여 표현한다.

      • Bellman Expectation Equation에서 Expectation E\mathbb E를 제거한 형태

        qπ(s,a)=Rsa+γ∑s′∈SPss′avπ(s′)q_\pi(s, a) =\mathcal R_s^a+\gamma \sum_{s'\in\mathcal S}\mathcal P^a_{ss'}v_\pi(s')

  • Bellman Expectation Equation [재귀]

    MRP에서의 Bellman Equation과 달리, MDP에서는 action의 존재로 인하여 가장 초기의 Bellman Equation을 바로 재귀적으로 표현하기 힘들다. 따라서 action-value와 state-value간의 관계를 이용하여 재귀적 표현으로 Bellman Expectation Equation을 표현한다.

    → 그대로 관계식을 대입한다!

    • Bellman Expectation Equation for vπv_\pi

      vπ(s)=∑a∈Aπ(a∣s)(Rsa+γ∑s′∈SPss′avπ(s′))v_\pi(s) =\sum_{a\in\mathcal A} \pi(a|s) \left( \mathcal R^a_s + \gamma \sum_{s'\in\mathcal S}\mathcal P^a_{ss'}v_\pi(s')\right)

    • Bellman Expectation Equation for qπq_\pi

      qπ(s,a)=Rsa+γ∑s′∈SPss′a∑a′∈Aπ(a′∣s′)qπ(s′,a′)q_\pi(s, a) =\mathcal R_s^a+\gamma \sum_{s'\in\mathcal S}\mathcal P^a_{ss'} \sum_{a'\in\mathcal A}\pi(a'|s') q_\pi(s',a')
  • for Matrix Form
    *MDP에서 Agent의 policy가 고정이라면 Agent가 없는 MRP로 표현할 수 있기 때문에, 그대로 matrix form을 적용해서 direct solution을 얻을 수 있다.
    vπ=Rπ+γPπvπv_\pi = \mathcal R^\pi + \gamma \mathcal P^\pi v_\pi
    with direct solution
    vπ=(I−γPπ)−1Rπv_\pi = (I - \gamma \mathcal P^\pi)^{-1} \mathcal R^\pi

3.4 Example of MDPs

  • MDP의 예시 : Action에 대하여 reward가 제공된다

  • MDP에서 state-value function의 계산

  • Bellman Expectation Equation Q. 빨간색 state의 value가 7.47.4라고 알려져 있을 떄, Bellman Expectation Equation을 만족하는가?

4. Optimal Solution

4.1 Optimal Value Function

  • Definition of Optimal Value Function

    가능한 모든 policy에 대하여 계산했을 때, 그 중에서 가장 maximum 값을 갖는 value function

    • Definition of optimal state-value function

      The optimal state value function v∗(s)v_*(s) is the maximum value function over all policies

      v∗(s)=max⁡πvπ(s)v_*(s) = \max_\pi v_\pi(s)
    • Definition of optimal action-value function

      The optimal action value function q∗(s,a)q_*(s, a) is the maximum action-value function over all policies

      q∗(s,a)=max⁡πqπ(s,a)q_*(s,a) = \max_\pi q_\pi(s,a)

  • Optimal Value Function

    • optimal value function은 MDP에서 가능한 최고의 성능을 나타낸다.
    • 해당 MDP의 optimal value function을 찾았다면, 그 MDP는 “solved”되었다고 한다.
    • 일반 value function과 달리 bellman optimality eqation은 matrix form으로 표현되지 않기 때문에 directly solve가 불가능하다.

  • Example

    optimal policy를 따랐을 때, state-value function과 action-value function



4.2 Optimal Policy

  • policy간의 partial ordering

    모든 state에 대하여 vπ(s)v_\pi(s)가 vπ′(s)v_\pi'(s)보다 같거나 크다면, π\pi가 π′\pi'보다 더 나은 policy 라고 말할 수 있다.

    π≥π′ if vπ(s)≥vπ′(s),∀s \pi \ge \pi' \text{ if } v_\pi(s) \ge v_{\pi'}(s), \forall s\\\ \\

  • Theorem of policy

    For any Markov Decision Process

    • 다른 모든 policy보다 더 같거나 좋은 π∗≥π,∀π\pi_* \ge \pi, \forall \pi optimal policy π∗\pi_*가 존재한다.
    • optimal policy를 따르는 value function은 optimal value function과 동일하다
      • 모든 optimal policy는 그 optimal policy를 따르는 optimal value function을 가진다.
        vπ∗(s)=v∗(s)v_{\pi_*}(s) = v_*(s)
      • 모든 optimal policy는 그 optimal policy를 따르는 optimal action-value function을 가진다. qπ∗(s,a)=q∗(s,a)q_{\pi_*}(s,a) = q_*(s,a)

  • Optimal Policy를 찾는 방법

    • optimal action-value function에 대하여 max가 되게하는 action만을 계속해서 취하는 policy

    • 즉, optimal action-value function q∗(s,a)q_*(s,a)을 알고있다면 그 즉시 deterministic optimal policy를 구할 수 있다. ⇒ MDP를 solve!

      deterministic

      • 원래 policy는 각각의 action을 수행할 확률로 정의되기 때문에 stochastic하다.
      • 그러나 optimal action-value function을 사용하여 구한 optimal policy는 하나의 action만을 하도록 결정된 deterministic한 policy이다.
      π∗(a∣s)={1if a=arg max⁡a∈Aq∗(s,a)0 otherwise\pi_*(a|s) = \begin{cases} 1 & \text{if } a= \argmax_{a\in \mathcal A}q_*(s,a)\\ 0 & \text{ otherwise}\end{cases}

  • Example : Optimal Policy


4.3 Bellman Optimality Equation

기본적으로 Bellman Expectation Equation과 동일한 구조를 이룬다. 다만, optimal policy를 알지 못하여 모든 수식을 Expectation으로부터 표현하기 시작했던 것과 달리 여기서는 optimal policy ∗*를 알고있기 때문에 이를 이용하여 equation을 표현한다.

  • Optimal state-value function과 Optimal action-value function의 관계

    • state과 action의 관계 - (1)

      • state ss의 optimal value는 그 state에서 optimal action-value가 최대가 되게하는 action aa을 취했을 때의 optimal action value와 동일하다.

      • action-value를 maximize하는 action을 선택하는것이 optimal하기 때문에 자명하다.

        v∗(s)=max⁡aq∗(s,a)v_*(s) =\max_aq_*(s,a)

    • action과 state의 관계 - (2)

      • (state ss에서) action aa의 optimal value는 action을 수행함으로써 전달받는 1-step reward Rsa\mathcal R^a_s과 가능한 모든 next-state(s′∈Ss'\in \mathcal S)에 대한 optimal state-value의 (감쇄)기댓값의 합과 동일하다.

      • action을 하더라도 그 다음 state가 무엇으로 결정되는지는 환경의 불안정성(=state probability)를 따르기 때문에 기댓값의 형태로 표현한다.

        q∗(s,a)=Rsa+γ∑s′∈SPss′av∗(s′)q_*(s, a) =\mathcal R_s^a+\gamma \sum_{s'\in\mathcal S}\mathcal P^a_{ss'}v_*(s')

  • Bellman Optimality Equation [재귀]

    • Bellman Optimality Equation for vπv_\pi

      v∗(s)=max⁡aRsa+γ∑s′∈SPss′av∗(s′)v_*(s) =\max_a \mathcal R^a_s + \gamma \sum_{s'\in\mathcal S}\mathcal P^a_{ss'}v_*(s')

    • Bellman Optimality Equation qπq_\pi

      q∗(s,a)=Rsa+γ∑s′∈SPss′amax⁡a′q∗(s′,a′)q_*(s, a) =\mathcal R_s^a+\gamma \sum_{s'\in\mathcal S}\mathcal P^a_{ss'} \max_{a'} q_*(s',a')

  • Example

    Q. 빨간색 state의 value가 66이라고 알려져 있을 떄, Bellman Optimality Equation을 만족하는가?

  • Bellman Optimaliy Equation을 푸는 방법

    • Bellman Optimally Equation은 non-linear equation이다. (max⁡\max 때문) ⇒ 따라서 closed form solution을 가지지 았는다. (in general)
    • Many iterative solution methods
      • Value Iteration (DP)
      • Policy Iteration (DP)
      • Q-learning
      • SARSA

Reference

profile
Vaughan
우주의 아름다움도 다양한 지식을 접하며 스스로의 생각이 짜여나갈 때 불현듯 나를 덮쳐오리라.
이전 포스트

[강화학습] Deep Reinforcement Learning

다음 포스트

[강화학습] Planning by Dynamic Programming

0개의 댓글