모델기반 학습 - Model Based Learning - Value, Policy Iteration by Dynamic Programming

Model based MDP에서 어떻게 DP를 활용하여 Value 와 Policy 를 Iteration 하고 optimality 를 찾을 수 있을까?

 

---

 

이전 글 : 벨만 방정식

[Artificial Intelligence/Reinforcement Learning] - 벨만 방정식 - Bellman Equation and Optimality

벨만 방정식 - Bellman Equation and Optimality

 

일단 용어 부터 정리해보자

Model Based MDP & Model Free MDP

Model based MDP는 Model 과 environment 가 action 에 따라 어떻게 동작할지 훤히 모델을 알 고 있는 MDP를 말한다. 처음 부터 끝까지 상황 별로 어떻게 전이 할지 모든 뷰를 가지고 있으므로 최적의 수를 Planning (계산) 할 수 있다. Model based 는 Model을 ‘갖고 있다’ 라는 의미로도 해석된다. 즉, 자신의 action에 따라서 environment가 어떻게 바뀔지 알고 있다면 실제로 행동하기 전에 미리 변화를 예상 해보고 최적의 행동을 계획하여 실행 할 수 있을 것이다. 이와 같은 Planning 이 가능 하다면 agent는 훨씬 효율적으로 행동 할 수 있다.

반면에, Model Free MDP 는 Model 을 알 수 없으므로 수 많은 시행과정을 거쳐서 learning (학습) 을 통해 최적의 수를 향해 찾아 간다.

종합하면, Model Based MDP 는 최적의 수를 위해 dynamic programming 이나 tree search 를 통해 최적의 수를 계산 하는 방식으로 Bellman Equation 을 풀어 나가고, Model Free MDP는 Monte carlo 나 Time Difference Learning 방식을 통해 optimality 를 찾아 가는 방법론이라 고 할 수 있다.

Prediction

MDP를 planning 하는 과정에서, Input으로 MDP와 Policy $\pi$ 를 받고 output으로 value function $V_{\pi}$ 를 도출 한다. 이 output은 optimal 한 policy 를 찾는 것이 아니라 MDP와 $\pi$가 주어졌을때 이 $\pi$를 따른 다면 어떤 value function 을 가지는지 예측하는 것이라 해석 할 수 있다. 즉, 이 policy 가 과연 얼마나 좋은지를 평가하기 위한 기준 값을 구하는 과정이다. 이는 Policy Evaluation 이라는 용어로 설명 된다.

Control

MDP를 planning 하는 과정에서, Input으로 MDP를 받고, output으로 optimal value function 인 $V^*$ 와 optimal policy 인 $\pi^*$를 얻는다. 즉, MDP만 주어졌을때 이 MDP에 따라서 가장 optimal 한 value function이 무엇이고 특히 어떤 policy 를 선택 했을때 optimal 한지를 도출한다. policy iteration, value iteration 라는 반복 연산을 통해 최적값을 찾아가는 Conrol 을 할 수 있다.

Dynamic Programming

DP는 강화학습 도메인에서만 사용되는 알고리즘은 아니고, 컴퓨터 알고리즘 전 영역에서 반복 연산을 풀어가는 하나의 큰 방법론이라 할 수 있다. 하나의 큰 문제를 작은 sub 문제로 분할 하여 각각의 sub 문제의 답을 구한후 해답을 합친다는 사상에서 출발하며, Bellman Equation 관점에서 DP를 고려해본다면, 아래의 이유로 DP를 적용하기 굉장히 적합한 구조라는 것을 알 수 있다.

• Bellmab equation 은 state 들의 반복적인 분할과 결합으로 정의 될 수 있다.
• 각 state 에서의 value function 들은 이전 히스토리 state 에서 전이된 value function 들의 합이다.
• 각 sub 문제가 되는 state 별 value funtion 들 중에 최적값이 존재하고, sub 문제들끼리는 오버래핑 된다.

이러한 관점에서 bellman equation 은 결국 현재와 다음 state 상황만 고려하여 문제를 풀고 이를 캐시에 저장해두는 식으로 전개 된 문제를 계속 반복적으로 풀어나간다는 방법으로 해결 가능하며, 이에 적합한 알고리즘이 바로 Dynammic programming 이 된다.

---

 

Iterative Policy Evaluation

value 와 policy 의 optimality 를 찾아 내려면, 일단 MDP에서 policy 가 정의 되었을 때 각 state에서 value function 을 찾아내는 것 부터가 필요하다. 이 문제를 해결 하기 위해서 Bellman expectation 과정을 반복적으로 수행하는 Iterative 한 접근 방식을 사용한다.

$$ V_1 \to V_2 \to ... \to V_k \to ... \to V_{\pi} $$

위 흐름은 value function 이 policy 에 따라서 계속 업데이트 되는 과정을 표현 한 것이며, 이 value function 은 아래 Bellman Equation 수식을 통해 업데이트 된다. 이는 앞선 정리에서 소개한 MDP의 value funtion 수식을 iteration k 와 k+1 회차의 연관성을 묶어서 표현한 것이다.

state value funtion 의 evaluation 수식

k+1 은 각 iteration 을 의미하는 것이고, $\pi(a|s)$ 는 action을 수행할 확률을 의미 하며, 뒤에 나오는 수식 역시 앞서 소개한 바 있는 action value function 을 의미한다. 이 action value function 은 Q function 이라고 한다

저명한 인공지능 학자인 David silver 교수님의 예제를 발췌 해보았다.

가장 첫번째 스텝인 MDP의 정의 단계이다. reward r 에 -1을 준 이유는, 빨리 최종 목적지로 도달하는 것이 목표이니 한번 이동할때마다 reward를 -1로 준다는 의미 이며, agent 는 random policy 를 따르므로 4가지 action 의 확률인 0.25를 각 동서남북으로 action 할 확률 값으로 사용 하였다.

interation 을 k 회 늘려나감에 따라 value function 들이 업데이트 되는 과정을 수식에 대입한 결과이고 k가 1일때의 연산 결과이다.

k=2 일때의 연산결과 이다.

state value function 과 action value funciotn 을 Bellman equation 으로 표현하는 수식을 이해하고 있다면 어렵지 않으니 차근차근 대입해서 풀어보자.

k를 무한대까지로 늘려 본다면, value function 들이 특정 값으로 수렴하게 되고 이때를 optimal 한 policy 로서 선택 할 수 있게 된다. 이는 Greedy 한 해법을 사용하며, value function 이 큰 곳으로 따라 가다보면 결국 최적값이 나오게 된다는 간단한 아이디어에서 해결 되는 셈이다. greedy 를 적용 한다는 것은, 결국 이 모델이 어떻게 동작할지 모든 behavior가 관측 가능한 model based MDP 이기 때문에 가능한 접근이다.

 

 

Policy Iteration

Control 관점을 생각해보자. 앞서 수행한 Iterative Value Evaluation 의 흐름을 보면, greedy 한 방식으로 value 를 evaluation 하고 반복을 통해 policy 를 업데이트 시켜 왔다. 이것을 Policy Iteration 관점으로 풀어보면 아래와 같은 두가지 스텝으로 분할 된다.

• Evaluate Policy $\pi$
  • $V_\pi(s)= \mathbb E[ r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3}...|S_t = s]$
• Improve Policy with acting greedily
  • $\pi' = greedy (V_\pi)$

설명하고자 하는 바는 기대값을 통해 value function 을 evaluate 한 후, 두 과정을 무한 반복하면 결국 optimal policy 인 $\pi'$ 로 수렴하게 되는 것이다. policy 와 value가 둘다 더 좋아지니 결국 수렴한다는 의미를 도식화 하면 아래와 같다.

이러한 메카니즘을 optimality 관점에서 해석하면, 현재 state에서 다음 state으로 갈 때, optimal한 action 을 취하고 다음 state 에서 optimal 한 policy 를 따른다면, 전체적으로 optimal 한 학습을 할 수 있다는 것을 의미 한다. 이는 바꿔 생각해보면 S → S’ 인 상황의 S’ 라는 state에서 $V^*(S')$라는 optimal 한 value function 을 가진다면, 현재 state 인 S에서도 optimal 한 value function 을 가진 다는 것 또한 의미 한다.

 

 

Value Iteration

역시 Control 관점에서 value 를 생각해보자. 목적은 역시 optimal policy $\pi*$ 를 찾는 것이고, 이때는 Bellman optimality 과정을 반복적으로 수행하는 Iterative 한 접근 방식을 사용한다.

$$ V_1 \to V_2 \to ... \to V_k \to ... \to V_{\pi} $$

이 흐름은 위에 정의한 policy iteration 과 같지만 각 state 에서의 value를 iteration 시킨 다는 의미로도 해석 할 수 있다. 특이한점은 poilicy 를 evaluation 하여 iteration 시킬 때는 bellman expectation 을 활용 했지만 value를 iteration 시킬 때는 Bellman optimality 를 사용 한다는 점이다.

따라서 policy iteration 에서 사용한 수식과 달리 여기서는 아래와 같은 Bellman optimality Equation 을 사용하며 이 역시 지난 정리때 소개 한 바 있다.

즉, policy 가 무엇인지 모르는 상황에서 value를 열심히 max로 만들어 주는 action을 따라가다보면 Max 에 수렴 할 수 있다는 것이며, policy 가 무엇인지 모르기 때문에 수식에 policy 가 사용 되지 않았다. 이것이 value iteration 의 핵심이다.

value iteration 역시 David silver 교수님의 예제를 발췌 해보았다. 간단한 shortest path 문제이다.

전이 확률을 모르기 때문에 동서남북 이동 behavior를 뜻하는 policy 가 수식에 없다. 따라서 상하좌우 이동 모두 해보고 그에 따라 얻는 reward 값들 중 max를 취한다. 모든 과정은 Bellman optimality equation 을 가지고 v3까지의 value function 이 업데이트 되었다.

과정을 반복 할수록, terminal state 에서 멀어질 수록 점수가 낮아짐을 확인 할 수 있다.

마지막 state 까지 이동해본 결과다. 주변의 value값이 가장 큰 쪽으로 움직인다면 가장 짧은 path 라 할 수 있다.

핵심을 뽑아보자.

 

지금까지 알아본 접근방식들은 모두 dynamic programming으로 해결 될 수 있고, 사용된 기법을 prediction 과 control 관점에서 나눠보면 다음과 같이 정리 된다.

굳이 control 문제를 policy iteration 과 value iteration 으로 나누어 정의 하였지만, 사실은 이 두가지의 메카니즘은 알아본 바와 같이 매우 비슷하다. 단지 value iteration 은 policy 를 모르는 경우 value를 통해 최적을 찾아 간다는 적용 수식만 다르고 이때 사용 되는 Bellman Optimality Equation 이 이미 greedy policy improvement 를 포함하고 있기 때문이다.

 

 

---

지금까지 Bellman Equation 을 기초로 하여 Model based MDP에서 최적을 찾아가는 policy iteration 과 value iteration 과정을 자세히 알아 보았다.

하지만 여기에는 큰 제약사항이 걸려있는데, 사실 현실에서의 우리는 모든 enviroment 를 모를 수 밖에 없다. 이런 경우를 Model Free 라고 하며 이때는 이러한 dynamic programming 방식 기반의 value/policy iteration을 사용 할 수 없다.

다음 정리에서는 Model Free 환경에서의 prediction 과 control 문제에 어떻게 접근 할지에 대해서 알아본다.