Dynamic Programming, Policy Iteration부터 Value Iteration까지

지난 MDP 포스팅에 이어서, 이번 포스팅은 MDP를 iterative하게 푸는 방법 중 하나인 Dynamic Programming(DP)에 대해서 다룹니다. CS234 2강, Deep Mind의 David Silver 강화학습 강의 3강, Richard S. Sutton 교재 Reinforcement Learning: An Introduction의 Chapter 4 기반으로 작성하였습니다. 또한, 대부분 수식 표기법은 Sutton 교재를 따랐습니다.

일반적으로 Dynamic Programming란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말합니다. 지난 시간에서 벨만 방정식(벨만 기대 방정식, 벨만 최적 방정식)은 recursive한 관계를 가지고 있기 때문에, 벨만 방정식을 풀기 위한 솔루션으로 DP 사용이 적합하다고 할 수 있습니다.

따라서, 상태 $s \in S$, 행동 $a \in A$, 보상 $r \in R$ 인 환경 모델 $p(s’,s|r,a)$ 을 아는 상황에서, 벨만 기대 방정식과 벨만 최적 방정식의 recursive한 성질을 이용하여 최적 가치 함수 $v_\ast, q_\ast$ 를 구하는 것이 Dynamic Programming을 이용한 MDP 를 푸는 것입니다.

MDP문제는 환경모델을 완벽하게 아는 상황이기 때문에, dynamic programming은 'reinforcement learning'이 아니라 'planning' 방법입니다.

DP설명은 finite MDP에 유한하여 설명하도록 하겠습니다. 일반적으로 continuous MDP문제는 DP방법이 아닌 다른 방법을 이용하여 풀기 때문입니다.

지난 강화학습 소개[2] 포스팅에서, sequential decision making 문제 종류로 evaluation(prediction)과 control을 소개하였습니다. evaluation은 일정 정책 아래, 기대보상을 추정하여 현재 따르는 정책의 좋고/나쁨을 평가하는 것입니다. 즉, 현재 정책의 평가가 되는 것입니다. control은 정책들의 평가를 기반으로 최적의 정책을 찾는 것입니다. evaluation과 control은 독립적인 과정이 아니라 서로 연계되어 있는 과정이라 하였습니다. 마찬가지로 Dynamic Programing도 evaluation에 해당하는 Policy Evaluation과 control에 해당하는 Policy Improvement로 구성됩니다. 각각에 대해 알아봅시다.

DP설명은 finite MDP에 유한하여 설명하도록 하겠습니다. 일반적으로 continuous MDP문제는 DP방법이 아닌 다른 방법을 이용하여 풀기 때문입니다.

Policy Evaluation

Policy evaluation은 벨만 기대 방정식을 이용하여 iterative한 방법으로 현 정책 아래의 가치함수를 구하는 과정입니다. 아래 벨만 기대 방정식을

update rule의 관계를 가진 방정식으로 취급한 뒤,

k=0부터 수렴할 때까지 반복적으로 계산하는 것입니다. 즉 가치 함수를 초기화한 후, $v_0 \to v_1 \to v_2 \to \cdots \to v_\pi$ 으로 수렴할 때까지 모든 상태에 대해서 동시에 업데이트하는 것입니다.

이를 back-up diagram으로 다시 표현해 봅시다.

그림 4.를 보시면, k 스텝에서 다음 상태를 이용하여 k+1 스텝의 현재 상태를 업데이트합니다. 또한 업데이트되는 방식은 다음 상태에서 나올 수 있는 누적보상의 가중 평균으로 계산됩니다(벨만 기대 방정식이기 때문입니다).

To produce each successive approximation, $v_{k+1}$ from $v_{k}$, iterative policy evaluation applies the same operation to each state s: it replaces the old value of s with a new value obtained form the old values of the successor states of s and the expected immediate rewards, along all the one-step transitions possible under the policy being evaluated. - Sutton and Barto, Reinforcement Learning : An Introduction

아래 그리드월드 예제로, policy evaluation을 살펴봅시다.

처음 시작 상태에서 여러 경로를 다니다가 회색색깔에 도착하면 끝나는 게임이 있다고 합시다. 각 상태마다 받는 보상은 -1이고, 행동 좌,우,위,아래 방향에 대해 갈 확률은 0.25라 한다면, k=0, k=1, k= $\infty$ 을 수렴할 때까지 반복하면 각 $v_k$ 에 대해 각 상태의 가치함수 값은 아래 그림과 같습니다.

왼쪽 행은 가치함수 결과이고, 오른쪽 행은 각 가치함수에서 greedy한 전략을 보여줍니다. 그러나 위 예제같은 경우는 간단한 케이스이어서 빨리 수렴에 도달합니다. 일반적으로 상태 집합의 크기 $|S|$ 가 큰 경우, 수렴할 때까지의 속도가 매우 느릴 수도 있기 때문에, 아래 알고리즘과 같이 어느 정도 수렴조건을 만족하면 다음 스텝으로 넘어가는 방법을 주로 택합니다.

Policy Improvement

결국 현재 정책을 평가하는 이유는 더 나은 정책을 찾기 위한 것입니다. 그렇다면 현재 정책 평가한 것을 기반으로 어떻게 더 나은 정책을 찾는지 알아보도록 하겠습니다.

임의의 정책 $\pi$ 아래 policy evaluation을 통해 $v_\pi$ 를 구했다고 하겠습니다. 그림 6.에서 처럼 수렴된 $v_\pi$ 에 대한 greedy policy가 있을 것입니다. 하지만 그 greedy policy 이외의 다른 행동 $a$ 을 선택하고, 즉, $a \neg \pi(s)$ 하고, 기존 정책 $\pi$ 를 따른다고 했을 때,

기존 정책에 따른 $v_\pi(s)$ 보다 크다면 새로 선택된 행동 a가 발전된 전략일 것입니다(policy improvement).

처음에, 이 부분을 혼자 공부할 때, 이해하기 어려웠던 부분이 ‘greedy policy 이외의 다른 행동 $a$ 를 선택하고 기존 정책을 따른다는 부분’이었습니다. 저는 이 부분은 아래와 같이 이해하였습니다.

그러나, 지난 MDP 포스팅에서 더 나은 정책이 되려면 $q_\pi(s, \pi’(s)) \geq v_\pi(s)$ 가 아닌 $v_{\pi}(s) \geq v_{\pi’}(s)$ 를 만족해야 합니다. 이를 유도하는 수학적 증명은 아래와 같습니다.

따라서, greedy하게 policy improvement하는 방식을 수식으로 깔끔하게 정리하면

입니다. 즉 기존 정책에서 발전된 새로운 정책 $\pi’$ 가 되었습니다.

만약에, 새로운 정책 $\pi’$ 가 기존 정책 $\pi$ 에서 더이상의 발전이 없다면, $v_\pi=v_\pi’$ 이를 만족하기 때문에, 아래 식이 성립됩니다.

위의 식을 가만보면, 어디서 많이 봤습니다. 바로 벨만 최적 방정식입니다. 즉, 더이상 발전이 없을 때, $v_\pi’$ 는 최적정책임을 의미합니다.

Policy Iteration

최적 정책을 찾기 위해서 결국 evaluation과 imporvement과정을 번갈아 가면서 정책이 더 이상 발전이 없을 때까지 진행해야 합니다. 이를 policy iteration이라 합니다.

E는 evalution이고, I는 improvement를 뜻합니다. Finite MDP인 경우 정책 후보의 갯수도 유한하기 때문에 반드시 언젠간 수렴합니다. Policy iteration 알고리즘은 아래 그림과 같습니다.

그림 9.를 보면, policy improvement를 한 후, 다시 policy evalutation을 할 때, 이전 정책 $/pi$ 에 관한 $v_\pi$ 로 초기값으로 하여 진행합니다.

Value Iteration

최적 정책을 찾는 방법엔 policy iteration 말고 value iteration도 있습니다. Value iteration에 대해 설명하기 전에 먼저 벨만 최적 방정식에서의 optimality의 개념을 다시 한번 생각해 봅시다.

Principle of Optimality

벨만 최적 방정식을 다시 한번 살펴보면,

상태 s에서 optimal value를 가지려면, 다음 상태 s’까지 진행해봐야 상태 s의 가치가 최적인지 아닌지 판단할 수 있습니다. 아래와 같이 $s_t$ 가 terminal state인 시퀀스가 있다고 한다면,

상태 $s_0$ 의 가치는 $s_1$ 에 도착해야 알고, $s_1$ 의 가치는 $s_2$ 에 도착해야 알고, …, $s_{t-1}$ 의 가치는 $s_t$ 에 도착해야 압니다. 즉 $s_t$ 의 최적가치를 알고 있어야 처음 상태 $s_0$ 의 최적가치값을 알 수 있단 얘기입니다. 아래 예를 살펴보겠습니다.

회색인 부분이 도달해야 하는 골이라 하면, 골까지 가는 가장 짧은 경로를 찾는 문제입니다. 흰색 칸을 밟을 때마다 받는 보상은 -1, 회색 칸을 밟으면 보상 0을 받는다고 할 때, 처음 상태가 정해진 것이 아니라면 당연히 회색 부분 근처 칸에서 시작하는게 최적일 것입니다. 그리고 회색 칸은 종결지점이기 때문에 회색 칸 이후로 더이상의 시퀀스가 존재하지 않아, 회색 칸의 최적가치는 즉각적인 보상인 0일 것입니다. 그렇다면 골에서 가장 멀리 있는 맨 오른쪽 칸의 최적 가치는 어떻게 구할까요? 골의 최적가치가 골에서 가까운 위치부터 퍼져나가 맨 오른쪽 칸의 최적 가치를 계산할 수 있도록 도달해야 합니다.

그러나, DP에서 모든 상태에 대한 업데이트를 동시에 진행하기 때문에, 골의 최적가치가 퍼져나가 다른 상태의 최적가치를 구할 수 있을 때까지 여러 번 반복 진행해야 합니다. 이것이 바로 “Value Iteration”입니다.

Value iteration을 수식으로 표현하면 아래와 같습니다.

위 수식을 보시면, 벨만 최적 방정식과 유사합니다. 즉, value iteration은 벨만 최적 방정식을 업데이트 형식으로 바뀐 것입니다.

policy evalutation은 벨만 기대 방정식을 업데이트 형식으로 바꾼 것이고, value iteration은 벨만 최적 방정식을 업데이트 형식으로 바뀐 것입니다.

value iteration은 policy iteration 처럼 명시적인 정책 발전 과정을 중간에 생략하고, 최적 가치 함수를 바로 계산하여 마지막에 정책 발전을 한번만 수행하여 최적 정책을 얻는 과정이라 생각할 수 있습니다.

이상으로 이번 포스팅을 마치겠습니다. 읽어주셔서 감사합니다.

1. CS234 Winter 2019 course Lecture 2
2. Richard S. Sutton and Andre G. Barto : Reinforcement Learning : An Introduction
3. David Silver Lecture 3
4. 위키백과, 동적계획법