[RL]Lecture #2 - Markov Decision Processes

영상: https://youtu.be/NMesGSXr8H4

강의 자료: Markov Decision Process

 

 

Table Of Content

​

Introduction to MDPs

• RL에서의 Environment를 표현
• Fully Observable Environment이다.
  • Agent State == Environment State = Information State
• 현재 State가 Process를 표현한다.
• 강화학습 문제를 정의하는 것

 

Markov Property

[Definition]
A state S_t Markov if and only if
P[S_t+1 | S_t] = P[S_t+1 | S_t1, ..., S_t]

• The state captures all relevant information from the history
  • State만 보고 History는 사용하지 않는다

 

State Transition Matrix

State Transition Probability

[Definition]
Pss' = P[St+1 = s' | St = s]

• 시간이 t일 때 State s에 있었다면, 시간 t+1일 때 State s'로 전이할 확률

State Transition Matrix

• 시간이 t일 때 State s에 있었다면, 시간 t+1일 때 가능한 모든 State들로 전이할 각각의 확률들

 

Markov Process

• A Markov process is a memoryless random process, i.e. a sequence of random states S₁, S₂, ... with the Markov property.
  • 어떤 경로를 통해 여기 왔는지 상관하지 않고 샘플링을 수행한다
• 예)
  •  
  • State 개수: 7, State 전이 확률: 화살표
  • Terminal State: Sleep 노드, 모든 프로세스가 종료되는 것
  • Episode: 어떤 State에서 시작해서 Final State까지 가는 것
  • 예시에서 C1 C2 C3 Pass Sleep
    • 이게 하나의 Episode이고, Episode를 Sampling한다고 표현

 

Markov Reward Process

• Markov Process의 S, P에 R, γ가 추가됨
• 확률분포에 따라 시스템이 자동으로 State를 변화시켜줌
• 예)
  • 

 

MRP > Return

• Reward와 Return은 서로 다른 개념
  • Return: 경로들도 Reward들의 총합인데, 그냥 더하지 않고 기준에 따라 가중치를 곱해서 더함
• The discount γ ∈ [0, 1] is the present value of future rewards
• The value of receiving reward R after k + 1 time-steps is γ^kR
• This values immediate reward above delayed reward.
  • γ close to 0 leads to myopic evaluation
    • 0에 가까울수록 순간적인 reward만 중요
  • γ close to 1 leads to far-sighted evaluation
    • 1에 가까울수록 장기적인 reward 중요
    • 미래의 가치를 현재 가치로 표현한 것

 

MRP > Why discount

• 수학적으로 편해서. 즉 discount로 인해서 수렴성이 증명되었기 때문에
• 모든 Sequence가 Terminate되는게 보장된다면, γ=1로 해도 된다

 

MRP > Value Function

• The value function v(s) gives the long-term value of state s
  • 현재 시점에서 미래의 기대하는 모든 Return들을 표현
• 미래의 Return이 가장 큰 의사결정을 하고 행동하는 것이 최종 목표
• 동일한 State에서 시작해도 경로에 따라서 Reward들의 총합이 다름

 

MRP > Bellman Equation for MRPs

• Value Function은 Bellman Equation에 의해 학습된다
• Value Function은 2개의 부분으로 분해 가능하다
  • immediate reward R_t+1
  • discounted value of successor state γv(S_t+1)
• Bellman Equation을 통해서 현재 시점의 Value는 현재의 Return과 다음 시점의 Value로 표현할 수 있다
• 한 Step 더 가서 보는 게 Bellman Equation
• 예)
  •  
  • Class 3이 현재 상태일 때
  • Value Function 값은 4.3
  • 현재 시점에서의 Return - 2 + 확률적으로 선택될 다음 State들의 Value의 Return * 확률

MRP > Bellman Equation in Matrix Form

• The Bellman Equation can be expressed concisely using matrices,
  • v = R + γPv
• where v is a column vector with one entry per state

  • 

• The Bellman Equation is a linear equation
• It can be solved directly

  • 

• 연산량: O(n³) for n states
• Direct solution only possible for small MRPs
• There are many iterative methods for large MRPs, e.g.,
  • Dynamic Programming
  • Monte-Carlo evaluation
  • Temporal-Difference learning

 

Markov Decision Process

• MRP with Decisions
  • 즉 MRP에서 Action이 더해진 것이 MDP
• It is an environment in which all states are Markov
• 예)

 

MDP > Policies

• Action에 따라 다음 State가 달라지기 때문에 어떤 Policy를 갖고 하느냐가 중요
• Action은 확률분포
• MDP policies depend on the current state (not the history)
  • MDP에서의 Policy는 현재 State에 의존한다
• i.e. Policies are stationary (time-independent),
  • A_t ∼ π(·|S_t), ∀t > 0
• Reward를 최대화해주는 어떤 Policy를 찾는 과정을 MDP를 푼다고 한다
• Given an MDP M = <S, A,P, R, γ> and a policy π
• The state sequence S₁, S₂ is Markov Process <S, P_𝝿>
  • Agent에서 Policy가 고정되면, 다음 State가 무엇이 될지 확률을 계산할 수 있음
• The state and reward sequence S₁, R₁, S₂, ... is a Markov Reward Process <S, P_𝝿, R_𝝿, γ>
  • 

 

MDP > Value Function

• 어떤 State에서 어떤 Policy 𝝿를 따라서 Episode가 끝날 때까지 수행하면 Episode 1개가 생성됨
• 이걸 여러 번 수행 → Episode N개
• Episode N개의 결과를 평균낸 것이 MDP에서의 Value Function
• State Value Function
  • State s인 조건에서 Policy를 따르는 기대되는 미래 보상들의 모든 합
  • 현재 State에서 특정 Policy를 따랐을 때 얼마나 좋은지, 얼마나 가치있는지 나타내는 값
• Action Value Function
  • State s에서 Action a를 수행했을 때, 이후는 Policy 𝝿를 따라서 게임을 수행했을 때 그 판의 기대값
  • State s이고 Action a인 조건에서 Policy를 따르는 기대되는 미래 보상들의 모든 합
  • 현재 State에서 특정 Policy를 따랐을 때 특정 행동을 하였을 때 얼마나 좋은지, 얼마나 가치있는지 나타내는 값
  • Q-Learning이 이에 해당
• 예)
  • 

 

MDP > Bellman Expectation Equation

State Value Function

• Step을 한번 움직인 이후, 그 다음 Step부터 𝝿를 따라 가는 것과 동일하다
  • 

Action Value Function

• S에서 A를 해서 R을 하나 받고, 다음 S에서 다음 Action을 하는 것의 기대값과 동일하다
  • 

예)

 

MDP > Bellman Expectation Equation - Matrix Form

• The Bellman expectation equation can be expressed concisely using the induced MRP,
• v_𝝿 = R^𝝿 + γP^𝝿v_𝝿
• Direct Solution: v_𝝿 = (1 - R^𝝿)^-1 * R^𝝿

 

MDP > Optimal Value Function

• 가능한 모든 Policy에서 가능한 Value 중에 최대값
• The optimal value function specifies the best possible performance in the MDP
  • Optimal Value Function은 MDP에서 가능한 최적의 성능을 나타냄
• 이걸 아는 순간 MDP가 solved됨

 

MDP > Optimal Policy

• 2개의 Policy가 있을 때 둘중 어떤게 나은 Policy인지 비교하려면 Partial Ordering을 정의해야함
  • π ≥ π' if v_π(s) ≥ v_π'(s), ∀s
• An optimal policy can be found by maximising over q_*(s, a)

  • 

• There is always a deterministic optimal policy for any MDP
• If we know q_*(s, a), we immediately have the optimal policy
• 예)
  • 

 

MDP > Bellman Optimality Equation for v_*

• max로 인해서 non-linear

 

 

MDP > Bellman Optimality Equation for Q_*

• 예)

  • 

 

Solving the Bellman Optimality Equation

• Bellman Optimality Equation is non-linear
• No closed form solution (in general)
• Many iterative solution methods
  • Value Iteration
  • Policy Iteration
  • Q-Learning
  • Sarsa