Lecture 2 : Markov Decision Process

본 내용은 David Silver 교수님의 강의를 듣고 정리한 내용입니다.

https://youtu.be/lfHX2hHRMVQ

1. Introduction

• Markov Decision Processes formally describe an environment for reinforcement learning
• Where the environment is fully observable

2. Markov Process

1) Markov Property

The future is independent of the past given the present
(현재의 미래는 현재의 과거로부터 독립적이다)

• 시작 S1 부터 미래 St+1에 도달할 확률과, 현재 St에서 St+1에 도달할 확률이 동일하다.
• 현재는 과거의 미래이며, 현재는 과거의 정보들을 가지고있다.

2) State Transition Matrix

• State s, s' 이 Markov 일 때, State Transition Probability 는 다음을 만족한다.
  

• State Transition Matrix P 는 모든 State s 로부터 s' 으로 가는 State Transition Probability 를 정의합니다.

• State Transition Matrix에서 각각의 행을 구성하는 인자들의 총합은 1 이다.

3) Markov Process(or Markov Chain)

Markov Property를 만족하는 State들과, 이 State들 간의 State Transition Matrix 으로 구성된 Tuple

3. Markov Reward Process

1) Markov Reward Process

Markov Chain에 Reward가 추가된 Tuple

2) Return

• Return G는 어떤 Episode의 Step t 부터 매 Step마다 얻게되는 모든 Reward의 합을 의미한다.
• Discount r은 7. Discount 참고

3) Discount r

• 0 이상 1 이하의 값, [0, 1]
• 미래의 Reward에 패널티를 가함으로써 현재 시점에서의 기댓값으로 변환한다.
• 먼 미래의 Reward 일 수록 많은 패널티를 얻게 된다.
• 먼 미래에 얻게될 Reward와, 가까운 미래에 얻게될 Reward의 경중을 조정하는 용도.
• r이 0에 가까울 수록 가까운 미래를 더 중요시한다.
• r이 1에 가까울 수록 먼 미래또한 중요시한다.
• Cyclic 상태에서 무한으로 빠지는 것을 방지하여 준다.

4) State Value Function of MRP

State s에서 앞으로 얻게될 것이라 기대되는 가치

• Agent는 다음 State s' 으로 이동할때 v(s') 이 가장 큰 State로 이동한다.
• 학습을 반복하면서 Value Function은 업데이트 된다.

5) Bellman Equation for MRP

다음 State와 현재 State의 Value Function 사이의 관계를 식으로 나타낸 방정식.

Value Function은 두 개의 파트로 나누어질 �수 있다.

• 다음 State S' 의 보상 Rt+1
• 다음 State S' 에서의 Discouted Value Function rv(St+1)

Bellman Equation for MRP의 전개과정

Backup diagram을 이용한 도식화

Bellman Equation의 Matrix Form

Bellman Equation 풀이

• Bellman Equation 은 선형 방정식
• n States 일때의 Computational Complexity는 O(n^3)
• 아래의 Direct Solution으로 바로 풀이가 가능
• 그러나 아래의 Direct Solution은 small MRP 일때만 사용가능

• Large MRP의 경우는 다음 방법을 사용해 풀이 가능
  • Dynamic programming
  • Monte-Carlo evaluation
  • Temporal-Difference learning

4. Markov Decision Process

1) Markov Decision Process

MRP에 Decision(Action)이 추가된 튜플

2) Policy

State s에서 Action a를 할 확률

3) Value Function

(1)State-Value Function

State s에서 Policy를 따랐을 때, 얻게될 것이라 기대되는 가치

(2)Action-Value Function

State s에서 Policy를 따라 Action a 를 했을 때, 얻게될 것이라 기대되는 가치

4) Bellman Expectation Equation for MDP

(1) State-Value Function

(2) Action-Value Function

(3) Backup Diagram

(4) Direct Solution

5) Optimal Value Function

모든 Policy의 경우를 따졌을 때, 가장 큰 Value Function

6) Optimal Policy

Optimal Value Function의 Policy

Finding an Optimal Policy

해설 : State s에서 선택할 수 있는 Action들 중, 어떤 Action a의 Optimal Value Function q∗(s,a)가 가장 클 때, π∗(a|s)를 1로 설정한다. 그리고 그 외의 Action a'들의 π∗(a'|s)를 0으로 설정한다.

7) Bellman Optimality Equation