Dynamic Programming

Prediction은 Evaluation과 같다고 생각하시면 됩니다. 강화학습에서 Prediction은 Policy가 주어져 있을 때 각각의 state가 몇 점인지 평가를 해 주는 것입니다. Control은 결국에는 가장 좋은 것을 찾는 것입니다. 그리고 강화학습에서 가장 좋은 것은 즉, 최적의 Policy입니다. 그리고 최적의 Policy를 찾는 데에는 두 가지 방법이 있는데, 이 두 개는 사실상 같은 것이라고 할 수 있습니다. Value iteration은 Policy iteration의 특수한 경우입니다. 

오늘은 1) 평가하는 것, 2) 가장 좋은 것을 찾는 것 이라는 두 가지를 다룰 텐데 이는 모두 MDP라는 특수한 환경에서 이루어집니다. 그리고 MDP를 풀 때는 여러가지 방식이 있지만 '모델을 알 때' (state transition을 알 때) 에는 Dynamic programming으로 문제를 풀 수 있습니다. 그리고 이렇게 문제를 푸는 방식을 Planning이라고 합니다. 

다만 99%의 문제들은 모델을 모르는 경우이기 때문에, 이럴 때는 Learning을 사용해서 문제를 풉니다. 그때 사용하는 것이 MC, TD 등입니다. 

그렇지만 어떤 방식을 쓰든지 우리가 결국 하고자 하는 것은 MDP를 푸는 것이고, 이는 Optimal Policy π를 찾는 것을 의미합니다. 

• 모델을 알 때 (state transition matrix가 있을 때) -> Dynamic Programming(DP)
• 모델을 모를 때 -> Monte Carlo(MC), Temporal Difference(TD)

 

Dynamic Programming

벨만 방정식의 벨만 씨가 만든 디자인 테크닉입니다. 어떤 문제가 있을 때, 이 최적화 문제가 어떤 Sub-problem으로 자를 수 있을 때 각각 잘라낸 문제들의 최적값을 구하면 그게 전체 문제의 최적값이라는 것입니다. (Devide-and-conquer)

• Dynamic programming is a design technique for solving optimization problems having a recursive structure
• Dynamic programming is related partially to Divide and Conquer(top-down) and to Greedy Algorithms(bottom-up)
• Problem at hand is subdivided to partial problems(subproblems) whose results are combined to solve the overall problem

이런 DP는 다음과 같을 때 유용하게 사용할 수 있습니다. 

• 최적의 원리(Principle of optimality)를 따를 때
• Subproblem이 중복 될 때

MDP는 두 가지 요소를 모두 충족하고 있습니다. 벨만 방정식을 사용하면 문제가 Recursive하게 풀리고, Value function이 solution을 중복적으로 사용하기 때문입니다. 이런 DP를 사용하여 풀리는 문제의 대표적인 예시로는 피보나치, 팩토리얼 등이 있습니다. 

Planning by Dynamic Programming

DP는 MDP에 대한 Full knowledge를 알고 있다고 가정합니다. 

• For prediction : policy에 대한 평가
  • Input : MDP <S,A,P,R,γ> and policy π
  • Output : value function v_π (policy에 대한 value)
• For control : 좋은 policy를 찾아내는 게 목표
  • Input : MDP <S,A,P,R,γ>
  • Output
    • The Optimal value function v*
    • The Optimal policy π*

 

Iterative Policy Evaluation = Prediction

말 그대로 Policy가 주어지면 이 policy에 대한 value를 찾아내는 것인데, 이걸 한 번에 하는 게 아니라 iterative하게 수행합니다. 이 과정은 Bellman expectation을 거꾸로 가면서 하게 됩니다. 

 

 

Policy Iteration = Control

 

Value Iteration = Control

 

 

---

위 내용은 경희대학교 소프트웨어융합학과 황효석 교수님의 2023년 <강화학습> 수업 내용을 요약한 것입니다.