강화학습 학습하기 - [3] DP

[3] - Dynamic Programming for MDP 

"강화학습 학습하기"시리즈는 KAIST 신하용 교수님의 수업 IE540 "DP and RL"수업 내용을 제가 제 방식대로 요약 및 정리한 것입니다. 퍼가실때는 미리 물어봐주시고, 내용은 제가 변형하고 추가하되 렉쳐노트에 쓰인 그림은 사용해도 된다고 교수님께 허락 받았습니다. 

There are no stupid Questions, only stupid Answers.
 (세상에 이상한 질문은 없다, 오직 이상한 대답만이 있을뿐이다.)
질문은 언제나 환영입니다. 

0. Previously on .. 

저번 시간에는 MDP 문제에 대해서 알아봤다. MDP 문제는 sequential decision making 문제를 표현하는 방식 중 하나이다. 주로 <S,A,P,R,gamma>로 정의된다. DP는 동적계획법으로 dynamic programming이다. 

1. DP for MDP

MDP 문제를 풀기 위해서는 두 가지 해결 방식이 있다. 첫 번째는 DP이다. DP는 작은 문제를 해결하고 그 결과를 보다 큰 문제를 푸는 데 적용하는 Recursive problem이다. DP를 MDP 문제로 풀려고 한다면, 그 방식에 따라서 Policy Iteration (PI), Value Iteration (VI)로 푼다. 이때 여기서 푼다는 의미는 model, reward에 대해서 정확히 아는 상태에서 value function을 정확히 추정한다는 것이다. Value function을 정확히 알아야 optimal policy로 수렴할 수 있기 때문이다. 우리의 목표는 "Find True value function"이다. 

Markov Decision Process.

어떻게 하면 V^PI(s) 혹은 V*(s)를 찾을 수 있을까? DP로 풀 때는 smaller problem solutoin을 저장하고 활용하는 것이 중요한데, finite horizon의 경우에는 ending stage에서부터 풀면 된다. 그러나 no know horizon의 경우에는 order가 clear하지 않기때문에 fixed point iteration을 사용한다. 

Horizon의 차이에 따른 문제 푸는 순서.

우리의 목표는 model과 reward를 아는 상태에서 V^PI값을 찾는 것이다. 

Iterative poicy evaluation. Policy iteration에 사용된다. 

gamma-contraction mapping에 의해서 V^PI는 operator를 반복할 때마다 수렴하게 된다. 

2. Policy Iteration

Policy iteration 모식도와 steps.

Policy iteration은 두 가지과정이 있다. 현재 policy가 얼마나 좋은지를 알아보는 policy evaluation, 현재 policy를 더 좋은 policy로 업데이트하는 policy improvement가 있다. 위에 있는 그럼처럼, 특정 policy의 V*(True)값까지 찾아본 후에 이걸 가지고 policy를 improvement한다. 이때 improvement는 greedy한 값을 선택하게 된다. 

Improve the policy. 왜 improve the policy( choosing greedy action)을 하면 policy가 좋아지는지에 대한 설명.

policy를 greedy하게 업데이트할 경우 무조건 다음 policy는 state value값이 더 크거나 같다. 

이러한 greedy한 policy improvement를 통해서 우린 이 시스템의 최적의 policy와 state value를 얻을 수 있다. 

3. Value iteration

Value iteration 모식도

만약 딱 한번 state value를 측정하고(policy evaluation), 바로 policy improvement를 한다면 어떻게 될까? 어차피 세세한 값을 측정하지 않아도 대강만 측정해도 어떤 경향성이 보이지 않을까?하는 생각이 바로 value iteration이다. 여기서는 한번 policy evaluation을 하고 바로 policy improvement를 한다. 그리고 이 두가지를 한번에 병합해서 하나의 step으로 계속 움직인다면 이게 바로 value iteration이다. 

Value iteratoin steps.

앞서 나온 policy iteratoin과는 state value가 따르는 공식 자체가 다르다. 아까는 Bellman expectation equation이었다면, 현재 value iteration은 Bellman optimality equation이다. 

Bellman optimality equation

Principle of optimality

Value iteration도 policy iteration과 마찬가지로 gamma- contraction mapping으로 인해 V^(PI)로 수렴한다. 

Value itreation의 수렴성.

Bellman optimality equation은 Bellman expectation equation과 다르게 linear하지 않다. Max operator는 굉장히 높은 non-linearity를 가지고 있다. 그래서 linear method은 matrix inversion으로 풀리지 않는다. 그리고 Value iteration이 policy iteration보다 information flow가 빠르다. world 정보가 policy iteration보다 빠르게 policy improvement로 반영된다. 그래서 policy iteration보다 converge faster하다. 

4. DP algorithms for MDP: Policy evaluation, PI,VI

DP algorithms for MDP

MDP를 DP로 풀때는 세가지가 쓰인다. 첫 번째로 단순히 얼마나 이 policy가 좋을지를 측정할때는 prediction problem이 되며, 이는 iterative policy evaluation을 사용한다. 그리고 측정뿐만 아니라 최적의 action을 해서 극대화하고 싶은 것이 있다면 이는 control problem이 된다. 이때 Bellman expectation equation을 이용하면 policy iteration, Bellman optimality equation을 policy evaluation에 사용하면 Value iteration이 된다.

  계속 강조했지만, model에 대해서 다 안다면, 무조건 gamma-contraction mapping thoerem에 의해서 최적의 policy로 수렴한다. 그러나 우린 model에 대해서 모를 수도 있다. 대부분의 경우에서는 environment는 action에 의해서 값을 주는 것이지 어떤 값을 주는 Model을 짜기란 쉽지 않다. 이걸 "Curse of model"이라고 한다. DP로 풀려면 model을 우리가 알고 있어야한다. 두 번째로 state space와 action space가 매우 넓으면 어떻게 될까? 하나의 iteration을 돌리는데도 오래 걸리게 될 것이다. 이는 반복적인 계산을 통해서 답을 찾아가는 DP에게 치명적이다. 이를 "Curse of dimensionality"라고 한다. 따라서 두 가지 저주를 해결하면서 혹은 대처해야하는 상황이 바로 Reinforcement learning이다. 여기서 DP와 강화학습의 연결고리가 생긴 것이다. 

다음시간에는 본격적인 강화학습을 배워볼 것이다. 이제 우린 model도 모르고, environment에 의해서 넓은 state space와 action space를 가질 수도 있다. 다음 편은 가장 간단한 강화학습인 MC (몬테카를로 방법)을 알아볼 것이다.