[강화학습] 3. Dynamic Programming

Dynamic Programming

앞서 MDP라는 이론, 그리고 MDP를 풀기 위한 Bellman equation이라는 mathematical form을 배웠다. 

다만 Bellman equation은 non-linear + exhaustive function으로 직접적으로 계산하기가 어려워 근사화(approximation)가 필요하다. 이 때 사용되는 것이 바로 우리가 '동적계획법'이라 부르는 Dynamic Programming(DP)이다.

DP는 복잡한 문제를 작은 문제로 분할하고, 작은문제의 결과를 취합해 큰 문제를 해결하는 범용 기술로 알려져있다. 하지만 DP의 시초는 MDP를 풀기 위해 Richard Bellman이 처음 고안한 방법이다. [위키백과]

그리고 DP의 핵심 아이디어는 non-linear function인 BOE(Bellman Optimality Equation)를 직접적으로 풀이하는 것이 아니라,

Linear function인 BE(Bellman Equation)를 iterative하게 풀다보면 optimal value와 policy로 수렴한다는 특징을 활용하는 것이다.

※ 물론 환경의 모델인 Dynamics를 정확히 알고 있다는 가정하에 풀 수 있다. 그리고 현실은 Dynamics를 다 알고 있는 경우는 많지 않기 때문에 실제로 잘 사용하지 않는다고 한다. 

Policy Iteration

앞서 언급한 것과 같이 optimal policy를 iterative하게 찾는 DP를 Policy Iteration이라 하고, Policy Iteration은 아래 2개 step으로 구분된다.

• Policy evaluation(prediction)
  : 주어진 policy를 평가하기 위해 BE를 활용, state-value를 구하는 과정이다. 

• Policy improvement(control)
  : state-value를 기반으로 policy를 더 나은 방향으로 update하는 과정이다.

그리고 위 두 과정을 반복하며 optimal policy를 찾는 것이 Policy Iteration이다.

Step 1. policy evaluation (prediction)

policy를 평가하려면 policy을 따랐을 경우의 state-value function을 계산해야한다. 이를 DP에서 정책평가(policy evaluation) 혹은 예측 문제(prediction problem)이라 부른다.

전 포스팅에서 설명했듯, vπ(s)를 구하려면 vπ(s')을 알아야 하고, vπ(s')을 구하려면 vπ(s'')이 필요하듯 재귀(recursive) 적인 계산이 필요하다. 

만약 terminal state가 굉장히 멀리까지 가야한다면, 매우 여러번 (0, 1, ..., k, k+1, ...) 재귀함수를 계산(iteration)해야할 것이다. 이걸 그림으로 나타내면 아래와 같다.

즉, 충분히 iteration하다보면 결국 vπ로 수렴하게 될 것이고, vπ(s)는 곧 policy π(a|s)를 따랐을 때, state s 에서의 가치가 된다. 이렇게 반복적인 계산을 통한 방법을 Iterative policy evaluation이라고 한다.

위는 Iterative policy evaluation의 pseudo-code를 보여준다.

threshold Θ를 이용해 value의 변화가 충분히 줄었을 때, 조기에 iteration을 멈추는 것을 확인할 수 있다. (일종의 value approximation)

Step 2. policy improvement 

Step1에서 policy를 평가 했으니 이제 평가 결과를 통해서 policy를 개선(improvement) 시킬 차례이다.

앞서 policy의 평가 결과가 state-value이기 때문에, BE for action-value function이 아니라,

아래 value function간 관계식을 사용할 예정이다.

위 식의 vπ에 policy evaluation 결과를 대입하면 state s에서의 모든 action들의 가치를 구할 수 있다.

이제 남은 것은 action의 가치를 보고 가장 좋은 action을 선택하는 것이다. 그럼 좋은 action이란 것은 어떻게 정의 할 수 있을까?

Bellman이 제안한 Policy Improvement Theorem에 따르면, policy evaluation결과보다 높은  value를 갖는 action을 greedy하게 선택하는 것이 better policy라고 한다. 

이 과정을 모든 state에 대해서 실행해 주면 새로운 policy π'을 구할 수 있다.

이렇게 greedy한 방법으로 가치를 통해 기존 policy를 개선하는 방법을 policy improvement라 한다.

결국 이렇게 greedy policy π'을 다시 policy evaluation에 대입 → policy improvement를 반복하다보면 어느순간 q와 v의 값이 같아질 것이다. 그럼 부등식이 등식으로 바뀌면서 다음과 같이 된다.

자세히 살펴보니 어디서 많이 본 식이다.

바로 BOE for state-value function과 완벽하게 같은 형태다.

즉, 비록 initial policy π0가 엉망이었더라도, v0 → π1 → v1 → π2... 를 반복하다 보면 언젠가 v*, π*로 수렴한다는 것을 확인할 수 있다.

이러한 방법으로 optimal policy를 찾는 것을 policy iteration이라 하며, pseudo code는 아래와 같다.

Value Iteration

앞서 살펴본 Policy Iteration은 2개의 iteration을 가지고 있다. 

• Policy evaluation을 위한 iteration

• optimal policy를 찾기 위한 evaluation-improvement iteration

그런데 특히 evaluation을 위한 iteration의 시간이 너무 많이 걸린다. (state가 많다면 특히)

그리고 policy는 value보다 일찍 수렴한다는 것을 확인했다. 

즉, optimal policy를 찾는게 목적이라면 그렇게 많이 반복할 필요가 없다. 

위 식은 Policy evaluation function 인데, 여기서 policy 에는 관심을 주지 않고 

그냥 바로 최대 가치를 가지고 value를 update하는 것이 바로 Value Iteration이다.

즉, v를 구하고 π를 update하는 과정을 가졌던 Policy Iteration이 파란색이라면,

Value Iteration은 π를 update하지 않고, v*를 Iterative하게 찾아 나가는 빨간색 과정이라 할 수 있다.

그리고 state-value보다 policy가 먼저 수렴한다는 것을 알고 있기 때문에,

state-value function의 변화가 적을 때 조기에 멈추고 policy를 찾는 원리를 아래 pseudo code에서 확인할 수 있다.

Generalized policy iteration

앞서 배운 내용을 정리하면,

• Policy Iteration은 평가(evaluation)과 개선(improvement)를 번갈아가며 하지만,

• Value Iteration은 평가와 개선을 동시에 한다.
  (평가와 개선을 한다는 의미에서 이 또한 Policy Iteration의 한 종류)

이렇게 Policy 평가와 개선이 서로 상호작용하는 이 개념은 거의 대부분의 RL 학습 알고리즘의 원리이며, Generalized Policy Iteration(GPI)라고 부른다.

Efficiency of dynamic programming

이렇게 풀기 어려운 문제를 작게 나눠서 푸는 방법이 DP의 핵심이다.

이런 원리는 Dimension이 클때는 계산량이 너무 많아 실용적이진 않지만, 다른 방법들 (linear programming)에 비해서는 꽤 효율적인 편이다. 다항식을 통해 직접 optimal policy를 구하는 것보다 훨씬 빠르기 때문이다.

그리고 계산량이 많다곤 하지만 그래도 millions of states 정도는 거뜬히 cover 가능하며,

상태가 많은 문제에 대해 병렬처리 할 수 있는 asynchronous DP방법또한 존재한다.

Summary

• finite MDP 푸는 문제로 Dynamic programming에 대한 기본 개념과 알고리즘을 배웠다.

• 정책 평가(Policy evaluation)은 주어진 정책에 대한 가치함수의 반복적인 계산(iterative computation)이다

• 정책 개선(Policy improvement)은 정책에 대한 가치함수를 가지고 정책을 개선하는 계산이다.

• 위 두 개(policy평가 & 개선)을 통해 DP에서 가장 대표적인 policy iteration과 value iteration을 할 수 있다. 그리고 확실히 최적의 policy과 value function을 구할 수 있다.

• 고전 DP는 상태들에 대해 sweep에서 연산을 다음의 상태와 그렇게 될 확률을 모두 고려한 가치를 업데이트 하는 expected update operation을 한다.

• Expected update는 Bellman equation과 관계있다. (등식이 할당으로 바뀐 것 뿐)

• 업데이트의 변화가 일정 이하면 수렴해서 Bellman Equation을 만족한 것이다.

• 거의 모든 강화학습이 Generalized Policy Iteration(GPI)라고 볼 수 있다.

• GPI는 두 프로세스가 정책과 가치함수를 주변으로 상호작용하는 개념이다.

• 둘은 서로를 기반으로 변해가고 있는 거지만 결국 하나의 해결점을 향해 나아가는 것이다.

마지막으로 DP의 아주 특별한 특징이 있는데, next state-value function에 대한 추측(estimate)을 가지고 current state-value function를 업데이트한다. 즉, 추측(estiamte)한 값으로 또다른 추측(estimate)를 하는데, 이를 bootstrapping이라 한다.