Lecture 3: Planning by Dynamic Programming

Overview

• slide
• youtube

Contents

DP는 모든 evironment의 동작방식을 알고 있다는것이 전제이기때문에 RL 문제가 아니다. planning 문제이다.

DP는 복잡한 문제를 subproblem으로 나누고 각각의 문제들을 해결한 뒤 하나로 합쳐서 해결한다. 이때 각각의 문제들을 해결한 결과들을 backup 해뒀다가 써먹는데, 여기서는 이 전략을 MDP문제를 푸는데 사용한다.

• For prediction:
  • Input: MDP $<S, A, P, R, γ>$ and policy π
  • or: MRP $< S, P^π, R^π, γ>$
  • Output: value function $v_π$
• Or for control:
  • Input: MDP $<S, A, P, R, γ>$
  • Output: optimal value function $v_∗$
  • and: optimal policy $π_∗$

크게 3가지 개념에대한 설명이 나온다.

Problem	Bellman Equation	Algorithm
Prediction	Bellman Expectation Equation	Iterative Policy Evaluation
Control	Bellman Expectation Equation Policy Iteration + Greedy Policy Improvement	Policy Iteration
Control	Bellman Optimality Equation	Value Iteration

Iterative Policy Evaluation

특정 policy의 value function을 구한다. 헷갈리지 말아야할것은 value function이라는 것은 특정 state의 value를 구해주는 함수라는 것. value가 아니다. 이 $v_{\pi}$ 값은 $\gamma$ < 1 거나 터미널 스테이트가 있을때 해당 policy에서 유일하게 존재한다.

전장에서 배운바와 같이 특정 policy $\pi$의 value function은 다음과 같다.

$$v_{\pi}(s) = \sum_{a \in A}\pi(a|s)(R_s^a + \gamma \sum_{s' \in S}P_{ss'}^a v_{=pi}(s'))$$

이를 한번에 구하기는 매우 골치아프고 복잡하기때문에, iterative policy evaluation를 사용한다. Bellman expectation Equation을 계속해서 적용해서 approximate value functions을 발전시키다보면 이것이 $v_{\pi}$ 값으로 수렴하게 된다. 수렴하게 되는 이유는 iterative하게 적용되는 Bellman expectation Equation 이 Contraction mapping하기 때문이다. 한글로 바꾸면 축소 사상이라고 하는데, 아주간단하게 이야기하면 계속해서 특정 operation을 적용할 수록 차이가 계속 작아져서 특정값으로 수렴하게 된다. 자세한 설명은 모두의 연구소, cmu lecture slide 참조하자. 여튼 이 iteration을 무한히 적용하면 $v_{\pi}$ 로 수렴한다.

공식을 보자

$$v_{k+1}(s) = \sum_{a \in A}\pi(a|s)(R_s^a + \gamma \sum_{s' \in S}P_{ss'}^a v_k(s'))$$ $$v^{k+1} = R^{\pi} + \gamma P^{\pi}v^k$$

이전에 구한 value function(vk)은 다음 value function(vk+1)을 구하는데 사용된다. s는 현재 계산하려고 하는 state이고, s’은 현재 s에서 도달 가능한 next state이다. 업데이트 루틴을 돌때 두가지 array를 사용하는데 old values를위한 vk, vk를 통해 새로 생성되는 vk+1 이 2가지를 사용한다. 다음 iteration때는 vk+1이 vk된다. DP에서의 value function 업데이트(vk+1)는 이전(vk)의 모든 state value에서 현재 policy하에서 one-step transitions한 possible next states 보고 하기때문에 expected update라 한다.

위공식을 이용해서 approximate value function을 계속 발전시켜나가면 다음과 같은 시퀀스가 나오게 된다.

$$v_1 -> v_2 -> ... -> v_{\pi}$$

approximate value functions을 통해서 모든 state들의 value를 구할 수 있고, 여기서 구해진 모든value들이 다음 approximate value functions을 구하는데 사용된다. 최초의 v1은 임의로 설정된 value값들을 이용한다. 보통 0으로 모든 state들의 value를 설정한다.

이제 실제 예제를 보면서 이해해보자.

• γ = 1
• terminal state: 음영 부분
• grid 바깥으로의 이동은 현재 state를 유지(그 자리 그대로)하는 것으로 처리
• 매 이동마다 reward -1(terminal state 제외)
• action은 4방으로 움직이고 random policy를 따름(동서남북 이동확률 25%로 같다)

$$\pi(n|\cdot) = \pi(e|\cdot) = \pi(s|\cdot) = \pi(w|\cdot) = 0.25$$

초기에 설정한 random policy를 따라서 Iterative Policy Evaluation을 돌며 approximate value functions 구하면 위의 그림과 같은 값이 나온다. 각각의 표 하나하나가 approximate value functions이 되는 것이다.

k=2, k+1=3일때 어떻게 approximate value functions값들이 구해지는지 아래그림을 보자.

Policy Iteration

최적의 policy를 찾아내는 과정. 다음 과정을 계속해서 반복한다. policy iteration은 언제나 π*로 수렴. 각 policy는 이전 것보다 향상된것이 보장된다. finite MDP는 유한개의 정책들을 갖기때문, 떄문에 이 process는 finite 횟수의 iteration안에 optimal policy 와 optimal value function으로 수렴됨. 이를 policy iteration라고 한다.

• Given a policy π
  • Evaluate the policy π:
  $$v_π(s) = \mathbb{E}[R_{t+1} + γR_{t+2} + ...|St = s]$$
  • Improve the policy by acting greedily with respect to $v_π$:
  $$π' = \text{greedy}(v_π)$$

위 과정을 그림으로 나타내면 다음과 같다 좌측 그림에서 위를 향하는 화살표가 evaluation, 아래로 향하는 화살표가 Improvement를 나타낸다. 조금 더 자세히보자. 우선 현재 policy의 value를 구하고, 가장 최대 값을 얻을 수 있는 action을 취한다. 그 뒤 value를 다시구하게 되면 이전과 변화된 조금 더 큰값의 value를 얻게되고, 이때 다시 최대 값을 취하는 action을 취한다. 이를 계속해서 반복하는것이 위의 그림. 결국 V* 와 π*를 향해 수렴하게 된다.

improvement 되는 과정을 조금더 자세히 보자. greedy를 수식으로 풀면 다음과 같이 된다

$$\DeclareMathOperator*{\argmax}{arg\,max} \pi'(s) = \argmax_{a \in A}q_{\pi}(s, a)$$

식에서 보듯이 가장 value를 최대로 하는 action을 취한다(argmax). 이런식으로 한 스텝마다 모든 state들의 policy 들을 update한다. 이렇게 업데이트를 하게되면 이전 value보다 업데이트된 policy를 통해 얻어진 value값은 반드시 크거나 같다. 왜 무조건 클까? 단순한 내용이다. argmax값이니까 특정 state에서 현재 value값보다 더 큰 이득을 취할 수 있는 action이 없다면 현재 action 값이 argmax가 된다, 따라서 action은 바뀌지 않고 value값은 유지가 되므로 무조건 같거나 크게 될 수 밖에 없다.

$$q_{\pi}(s, \pi'(s)) = \max_{a \in A} q_{\pi}(s, a) \geq q_{\pi}(s, \pi(s)) = v_{\pi}(s)$$

REINFORCEjs을 이용한 예제를 한번 보자. 최초 state에서 iteration을 몇회 반복했다. 예제의 초기 상태는 아래 그림과 같다. 이 Gridworld에 관해 대략적인 설명을 하자면

• γ = 0.9
• state: 각 cell
• terminal state: reward가 +1.00 인 cell
• reward/penalty: cell 하단숫자. 비어있는 cell은 0
• policy: 각 cell에 화살표로 표시
• action: 동서남북 4방. policy를 따름
• state value: 각 cell 상단숫자

파란색 박스가 새로 바뀐 policy 이다. 해당 state에서 최대값인 0.81 얻을 수 있는 방향으로 action이 바뀌었다.

바뀐 policy를 이용해서 value를 새로 구한다. update후에 action이 최대값을 얻을 수 있는 한 방향으로 정해졌기때문에 나머지 방향에대한 action 확률은 0이 되므로, 1방향에대한 결과만 합산된다

가장 최초의 state부터 연속해서 policy iteration 과정을 살펴보면 다음과 같다.

Value Iteration

위의 policy iteration과 같이 최적의 policy를 찾아내는 과정이다. 같은 결과를 도출하지만, 과정은 차이가 있다. value iteration은 우선 value function을 최적으로 수렴을 시킨뒤에 그것을 바탕으로 policy update를 마지막에 한번만 한다.

value function을 찾는 과정과 거의 유사하나 그림에서 표시된 max에서 차이가 발생한다. 항상 greedy하게 value값을 받아오기 때문에 일종의 upate 된 policy를 통해 값을 얻어오는 것과 유사한 효과가 나타난다. 간단하게 생각하면 policy iteration에서 evaluation, update 2step으로 진행됐던 것이 여기서는 1step으로 합쳐졌다고 생각하면된다. 물론 실제 policy update는 마지막에 발생하지만 value를 구하는 과정에서는 차이가 없다.

과정을 나타낸 그림도 거의 차이가 없고, 공식 또한 마찬가지이다. max 값이 차이이다. 그림에서 형광색으로 표시된 부분

$$v_{k+1}(s) = \max_{a \in A}(R_s^a + \gamma \sum_{s' \in S}P_{ss'}^a v_k(s'))$$ $$v^{k+1} = \max_{a \in A}R^a + \gamma P^av_k$$

보다 자세한 설명은 stackoverflow를 참고하도록 하자.(교석형님 좋은자료 감사합니다)