Chapter 03) Model-based Planning

 

 

Chapter 03) Model-based Planning 

 

 

이 중, 오른편에 속하는 Model Based RL를 공부한다 

 

 

 

목차 

• Dynamic Programming
  1. Prediction (evaluation)
     • Iterative Policy Evaluation
  2. Control
     • Policy Iteration
     • Value Iteration

 

 

 

 

 

내용 

 

• Model-based : Model을 알고 있음 (= 즉 transition function을 알고 있다)
• Planning : 환경에 대한 model를 알고 있고, agent는 외부적인 상호작용을 하지 않은 채 그 model에 대해 계산한다

⇒ Dynamic Programming!

 

 

⇒ state value function을 적용하였을 때보다 action value function을 적용하였을 때 시간 복잡도가 높다

⇒ Policy iteration과 Value iteration는 time complexity에서 큰 차이를 보이지 않는다

 

 

 

Dynamic Programming

• DP란?
  • 재귀적인 방법으로 더 간단한 부분 문제로 나누어 해결하고, 해결 뒤 합쳐서 최종 해결책을 도출한다
  • Dynamic Programming은 Planning으로서 Environment의 model(reward, state transition matrix)에 대해서 안다는 전제로 문제를 푸는 방법(Bellman equation을 사용해서)을 말한다.
• ⇒ DP는 MDP 문제에도 적용할 수 있다.
• ⇒ DP는 Planning 방식으로, MDP<S,A,P,R,r>에 대해 모든 것을 알고 있다는 전제 하에, 두 단계로 나누어 1) Prediction과 2) Control 단계를 거쳐 수행된다!
  1. Prediction : 현재 optimal하지 않는 어떤 policy에 대해서 value function을 구하기
  2. Control : 그 현재의 Value Function을 토대로 더 나은 policy를 구하고 이와 같은 과정을 반복하여 optimal policy를 구하는 것
  ⇒ 즉 현재 optimal하지 않는 어떤 policy에 대해서 value function을 구하고(prediction) 현재의 value function을 토대로 더 나은 policy를 구하고 이와 같은 과정을 반복하여 optimal policy를 구하는 것!
• Bellam equation은 재귀적으로 분해될 수 있으며, Value Function은 Solution들을 저장하고 재사용하기 때문이다!

 

 

 

step 1) Prediction (evaluation)

⇒ " Prediction : 현재 optimal하지 않는 어떤 policy에 대해서 value function을 구하기 "

 

Iterative Policy Evaluation

⇒ "현재 주어진 Policy에 대한 true Value Function 구하기"

 

• 현재 상태의 value function을 update하는데 reward와 next state들의 value function을 사용하는 것!

 

 

 

step 2) Control

⇒ " Control : 그 현재의 Value Function을 토대로 더 나은 policy를 구하고 이와 같은 과정을 반복하여 optimal policy를 구하는 것"

(1) Policy Iteration

⇒ "Bellman Expectation Equation + Iterative Policy Improvement"

• Policy iteration은 항상 최적의 Policy에 수렴한다

 

 

 

• greedy improvement : 다음 state 중에서 가장 높은 value function을 가진 state로 가는 것, 즉 max를 취하는 것

⇒ 이를 반복하는 것 : Policy Iteration

 

 

• 기존의 경우 Policy Evaluation를 최선의 경우에 달할 때까지, 즉 Bellman Optimality Equation에 만족할 때까지 진행

⇒ BUT, 이럴 필요 없이 iteration에 제한을 줘도 된다! 한번도 가능함

⇒ evaluation을 한 번만 하면 다음에 나올 Value Iteration

 

 

 

(2) Value Iteration

⇒ " Bellman Optimality Equation + 한 번의 evaluation & improvement만 진행"

※ Principle of Optimality

 

 

• 모든 최적의 Policy는 최적의 첫 번째 행동 A와 그 다음 상태 S 두 가지의 요소로 나눌 수 있다.

• Value Iteration은 Deterministic한 경우 뿐만 아니라 loopy하고 Stochastic(정확히 예측 불가능)한 MDP에도 적용 가능 하다