Chapter 02) Markov Decision Process

 

 

Chapter 02) Markov Decision Process

 

 

 

목차

 

1. Markov Property <S>
   • State Transition Matrix
2. Markov Process(=Chain) <S, P>
3. Markov Reward Process <S, P, R, r>
   1. (Discounted) Return
   2. Value Function - State Value Function
   3. Bellman Equation for MRPs
4.  Markov Decision Process <S, A, P, R, r, >
   1.  Bellman Expectation Equation <V.F>
      1. Policies
      2. Value Function 
   2. Bellman Optimality Equation <Optimal V.F>
      1. Optimal Policies
      2. Optimal Value Function

 

 

 

내용 

 

 

1. Markov Property <S>

⇒ " 어떤 상태 S는 Markov 상태이다 "

 

 

첫 상태로부터 현 상태에 올 확률 == 직전 상태로부터 현 상태에 올 확률

→ 현 state는 그 이전, 즉 history로부터 모든 관련 있는 정보를 담고 있다!

 

 

 

State Transition Matrix

 

 

• 현재 상태 s가 given일 때, 다음 상태 s'로 갈 확률을 담은 행렬
• 각 확률P_ss'가 합쳐진 행렬 P는 각 row의 합이 1이 된다

 

 

2. Markov Process(=Chain) <S, P>

⇒ "Markov Process는 <S, P>이며, S는 상태들의 집합, P는 상태 변이 확률 행렬이다"

• Markov Process는 Memoryless random process.
• 단, 이 때의 Random은 어떤 확률(Markvov 속성)에 기반한 Random이란 뜻!

 

 

 

 

 

 

3. Markov Reward Process <S, P, R, r>

⇒ "Markov reward process는 values(가치)와 discount 값이 포함된 Markov Chain이다!"

 

 

 

 

 

(Discounted) Return

 

 

→ 늦은 보상에 대해 할인율 적용하여 계산한다! 그 이유 ?

1. 반복되는 Markov Process 내에서 무한한 return을 막고 어느 정도 수렴시키기 위해
2. 미래에 대한 **불확실성(Uncertainty)**를 적용하기 위해서
3. 특정 경우, 먼 미래의 보상보다는 가까운 미래의 보상에 더 관심 있기 때문에

• 할인율 r 값이 클수록 먼 미래의 reward을 크게 반영하므로 원시안적이며, 할인율 r 값이 작을 수록 먼 미래의 reward의 가치를 낮게 평가하므로 근시안적이다
• → 할인율 r=1이라면, 해당 process가 모두 끝날 것이라는 것 가정해야 함

 

 

 

 

Value Function - State Value Function

⇒ "현재 상태 S로부터 끝날 때까지의 보상의 기댓값"

 

 

 

 

 

 

 

 

 

 

Bellman Equation for MRPs

⇒ "Bellman equation은 다음 state와 현재 state의 value function 사이의 관계를 식으로 나타낸 것!"

⇒ "MRP을 풀기 위한 방법으로 Bellman Equation 적용!"

 

 

 

• 아래의 노드들은 각각 다음 단계의 가능한 state를 의미하고 V(s)는 그 state의 value를 의미한다⇒ 계산하면 다음과 같이 !
  • → 다음 단계의 모든 state들의 value들을 기댓값으로 표현(갈 확률 곱하여)하여 discount factor를 곱한다
   

 

 

 

4. Markov Decision Process <S, A, P, R, r, >

⇒ "Markov Decision Process는 decisions(actions)가 포함된 Markov Reward Process"

 

 

• MDP는 fully observable한 Env.에서 적용되지만, Partially Observable하거나 Optimal Control한 경우에도 적용할 수 있다!
• MDP의 다음 state와 현재 state의 value Function들 간의 사이를 Bellman Expectation과 Bellman Optimality Equation으로 표현할 수 있다!

 

 

 

 

1) Bellman Expectation Equation <V.F>

⇒ "Policies + Value Function"

⇒ " 현재 state와 다음 state의 Value Function 사이의 관계를 나타내주기 위한 식 "

 

 

(1) Policies

• 정책은 agent의 행동을 결정한다
• MDP 정책은 history가 아니라 현재 state에 의존한다

→ Policy는 시간 독립적이다 (= time independent, stationary )

 

 

 

(2) Value Function

• state value function은 현재 상태 s가 주어졌을 때, 기대되는 보상값(expected return)들의 기댓값이다
• action value function은 현재 상태 s와 행동 a가 주어졌을 때, 기대되는 보상값(expected return)들의 기댓값이다

 

 

 

 

⇒ value function은 또다시 G(t)를 즉각적인 보상과 할인된 다음 상태의 가치로 나누어 재귀적으로 표현할 수 있다

 

 

 

1. State Value Function V(x)

 

 

• 아래의 노드들은 현재 상태 s에서 선택할 수 있는 action들을 의미한다
  • → 그 Q(x)에 Policy까지 고려하면 현재 state에 대한 value, 즉 V(x)를 구할 수 있다
  • → 현재 State에 대해 각 action에 대해 고르니 Q(x)로 value를 도출할 수 있다

 

• Q(x)를 치환해서 V(x)만으로 표현할 수 있다

 

2. Action Value Function Q(x)

 

 

 

• 아래의 노드들은 각각 한 action a를 취했을 때 나올 수 있는 다음 단계의 state들을 의미한다
  • → 같은 action을 해도 어떤 환경에 의해 다른 state로 갈 수 있기 때문에 이를 고려하기 위해 상태 변이 확률 행렬을 곱한다

 

• 위의 V(x)를 다시 Q(x)으로 표현된 식으로 치환한다

 

 

2) Bellman Optimality Equation <Optimal V.F>

⇒ "Optimal Policies + Optimal Value Function"

⇒ " 현재 state와 다음 state의 Optimal Value Function 사이의 관계를 나타내주기 위한 식 "

(1) Optimal Policies

 

 

 

(2) Optimal Value Function

 

 

• optimal state-value function이란 현재 state에서 policy에 따라서 앞으로 받을 reward들이 달라질 때, 그 중에서 앞으로 가장 많은 reward를 받을 policy를 따랐을 때의 value function이다

 

 

1. State Value Function V(x)

 

 

 

 

2. Action Value Function Q(x)