Soopace

Notes

4. Dynamic Programming

데이터사이언스 대학원 강화학습 수업을 듣고 정리한 내용입니다. Policy Evaluati...

데이터사이언스 대학원 강화학습 수업을 듣고 정리한 내용입니다.

Policy Evaluation & Policy Improvement

The term dynamic programming (DP) refers to a collection of algorithms that can be used to compute optimal policies given a perfect model of the environment as a Markov decision process (MDP)

강화학습에서 우리가 완전한 dynamic을 알고 있을 때, DP로 다음 문제를 해결하기 위해 사용한다.

  • Policy Evaluation(prediction problem): 주어진 policy에서 value fuction을 반복적으로 연산하는 과정(MDP, π→vπ\pi \rightarrow v_{\pi})
  • Policy Improvement(control): value function이 주어졌을 때, 향상된 policy를 계산하는 것(MDP, vπ→π′v_{\pi} \rightarrow \pi')

Policy Evaluation

Policy Evaluation은 policy π\pi가 주어졌을 때, Value function vπv_\pi를 계산한다. Policy Evaluation Update Rule은 다음과 같으며, 여기서 kk는 kk 번째 policy다.

vk+1(s)←∑aπ(a∣s)∑s′∑rp(s′,r∣s,a)[r+γvk(s′)]v_{k+1}(s) \leftarrow \sum_a \pi(a \vert s) \sum_{s'} \sum_{r} p(s', r \vert s, a) \lbrack r + \gamma v_{k}(s') \rbrack
“Iterative Policy Evaluation”
pseduo code

HeadImg

Example: 4 x 4 Grid-World

HeadImg

이번 Grid-World 예시는 다음과 같다.

note
  • Non-terminal states S={1,2,⋯ ,14}S = \lbrace 1, 2, \cdots, 14 \rbrace, 회색 영역은 terminal state.
  • State Transition(s→s′s \rightarrow s')은 −1-1의 보상을 얻고, grid밖을 벗어나면 이전 state에 있는 것으로 간주한다. 즉, 많이 움직일 수록 안좋다.
  • Actions A={↑,↓,→,←}\mathcal{A} = \lbrace \uparrow, \downarrow, \rightarrow, \leftarrow \rbrace
  • Uniformly random policy π(a∣s)=0.25\pi(a \vert s) = 0.25 for all a∈Aa \in \mathcal{A} and for all non-terminal states s∈Ss \in \mathcal{S}
  • Deterministic state transition & reward model p(s′,r∣s,a)p(s', r \vert s, a)
    • 예시1: p(s′=6,r=−1∣s=5,a=→)=1p(s'=6, r=-1 \vert s=5, a=\rightarrow)=1, grid 5에서 우측 행동(→\rightarrow) 선택 시 grid 6으로 가고 보상도 −1-1을 얻을 확률은 1.
    • 예시2: p(s′=7,r=−1∣s=7,a=→)=1p(s'=7, r=-1 \vert s=7, a=\rightarrow)=1, grid 7에서 우측 행동(→\rightarrow) 선택 시 grid 7으로 가고 보상도 −1-1을 얻을 확률은 1.
    • 예시3: p(s′=10,r=r′∣s=5,a=→)=0 ∀r′∈Rp(s'=10, r=r' \vert s=5, a=\rightarrow)=0 \ \forall r' \in \mathcal{R}, grid 5에서 우측 행동(→\rightarrow) 선택 시 grid 10으로 갈 수 있는 확률은 0.
  • γ=1.0\gamma=1.0를 가정한다.

그렇다면 이러한 MDP 환경에서 최대의 보상은 무엇일까? 당연히 제일 적은 스텝으로 terminal state에 도달하는 것이다.

따라서 Initial State V(s)=0V(s)=0를 만들고 계속해서 policy evaluation을 진행해보자. 메모리에 상관없이 각 좌표에서 replace하지 않고 두 개의 matrix로 업데이트 한다고 가정한다.

“과정 풀어쓰기”
k=0
| (i, j) | 0 | 1 | 2 | 3 |
|:-:|:-:|:-:|:-:|:-:|
| 0 | 0.0 | 0.0 | 0.0 | 0.0 |
| 1 | 0.0 | 0.0 | 0.0 | 0.0 |
| 2 | 0.0 | 0.0 | 0.0 | 0.0 |
| 3 | 0.0 | 0.0 | 0.0 | 0.0 |

초기 상태 가치는 모두 0.0이다.
k=1
| (i, j) | 0 | 1 | 2 | 3 |
|:-:|:-:|:-:|:-:|:-:|
| 0 | 0.0 | -1.0 | -1.0 | -1.0 |
| 1 | -1.0 | -1.0 | -1.0 | -1.0 |
| 2 | -1.0 | -1.0 | -1.0 | -1.0 |
| 3 | -1.0 | -1.0 | -1.0 | 0.0 |

각 state $s \in \mathcal{S}$ 에서 Bellman equation을 사용하여 업데이트 하면 위의 표와 같다.
vk+1(s)←∑aπ(a∣s)∑s′∑rp(s′,r∣s,a)[r+γvk(s′)] v_{k+1}(s) \leftarrow \sum_a \pi(a \vert s) \sum_{s'} \sum_{r} p(s', r \vert s, a) \lbrack r + \gamma v_{k}(s') \rbrack 
예를 들어, 좌표 `(0, 2)` $s=2$에서 $s' \in \lbrace 1, 2, 3, 6 \rbrace$의 transition을 제외하고 모두 확률이 0이 되기 때문에 다음과 같이 $v_{k+1}(s)$를 계산할 수 있다.
vk+1(s=2)=0.25×1.0×(−1+1.0×0)s(2)→s(1)+0.25×1.0×(−1+1.0×0)s(2)→s(2)+0.25×1.0×(−1+1.0×0)s(2)→s(3)+0.25×1.0×(−1+1.0×0)s(2)→s(6) \begin{aligned} v_{k+1}(s=2) & = 0.25 \times 1.0 \times ( -1 + 1.0 \times 0 ) & s(2) \rightarrow s(1) \\ & + 0.25 \times 1.0 \times ( -1 + 1.0 \times 0 ) & s(2) \rightarrow s(2) \\ & + 0.25 \times 1.0 \times ( -1 + 1.0 \times 0 ) & s(2) \rightarrow s(3) \\ & + 0.25 \times 1.0 \times ( -1 + 1.0 \times 0 ) & s(2) \rightarrow s(6) \end{aligned} 
다른 예시로 terminal state 중 하나인 좌표 `(0, 0)`은 모든 transition에 대하여 확률이 0이기 때문에 계속 $0.0$ 이다.
k=2
| (i, j) | 0 | 1 | 2 | 3 |
|:-:|:-:|:-:|:-:|:-:|
| 0 | 0.0 | -1.75 | -2.0 | -2.0 |
| 1 | -1.75 | -2.0 | -2.0 | -2.0 |
| 2 | -2.0 | -2.0 | -2.0 | -1.75 |
| 3 | -2.0 | -2.0 | -1.75 | 0.0 |

각 state $s \in \mathcal{S}$ 에서 Bellman equation을 사용하여 업데이트 하면 위의 표와 같다.
vk+1(s)←∑aπ(a∣s)∑s′∑rp(s′,r∣s,a)[r+γvk(s′)] v_{k+1}(s) \leftarrow \sum_a \pi(a \vert s) \sum_{s'} \sum_{r} p(s', r \vert s, a) \lbrack r + \gamma v_{k}(s') \rbrack 
예를 들어, 좌표 `(1, 2)` $s=6$에서 $s' \in \lbrace 5, 2, 7, 10 \rbrace$를 제외하고 모두 확률이 0이 되기 때문에 다음과 같이 $v_{k+1}(s)$를 계산할 수 있다.
vk+1(s=2)=0.25×1.0×(−1+1.0×−1)s(6)→s(5)+0.25×1.0×(−1+1.0×−1)s(6)→s(2)+0.25×1.0×(−1+1.0×−1)s(6)→s(7)+0.25×1.0×(−1+1.0×−1)s(6)→s(10) \begin{aligned} v_{k+1}(s=2) & = 0.25 \times 1.0 \times ( -1 + 1.0 \times -1 ) & s(6) \rightarrow s(5) \\ & + 0.25 \times 1.0 \times ( -1 + 1.0 \times -1 ) & s(6) \rightarrow s(2) \\ & + 0.25 \times 1.0 \times ( -1 + 1.0 \times -1 ) & s(6) \rightarrow s(7) \\ & + 0.25 \times 1.0 \times ( -1 + 1.0 \times -1 ) & s(6) \rightarrow s(10) \end{aligned} 
다른 예시로, 좌표 `(0, 1)` $s=1$에서 $s' \in \lbrace \text{terminate}, 1, 2, 5 \rbrace$를 제외하고 모두 확률이 0이 되기 때문에 다음과 같이 $v_{k+1}(s)$를 계산할 수 있다.
vk+1(s=1)=0.25×1.0×(−1+1.0×0)s(1)→s(terminate)+0.25×1.0×(−1+1.0×−1)s(1)→s(1)+0.25×1.0×(−1+1.0×−1)s(1)→s(2)+0.25×1.0×(−1+1.0×−1)s(1)→s(5) \begin{aligned} v_{k+1}(s=1) & = 0.25 \times 1.0 \times ( -1 + 1.0 \times 0 ) & s(1) \rightarrow s(\text{terminate}) \\ & + 0.25 \times 1.0 \times ( -1 + 1.0 \times -1 ) & s(1) \rightarrow s(1) \\ & + 0.25 \times 1.0 \times ( -1 + 1.0 \times -1 ) & s(1) \rightarrow s(2) \\ & + 0.25 \times 1.0 \times ( -1 + 1.0 \times -1 ) & s(1) \rightarrow s(5) \end{aligned} 
## Policy Improvement

Policy Improvement는 value function vπv_\pi가 주어졌을 때, 향상된 policy π′\pi'을 구하는 것이다.

“Policy Improvement Theorem”

Let π\pi and π′\pi' be any pair of deterministic policies such that, for all s∈Ss \in \mathcal{S}, qπ(s,π′(s))≥vπ(s)q_{\pi}\big(s, \pi'(s) \big) \geq v_{\pi}(s).

Then the policy π′\pi' must be as good as, or better than π\pi.

Theorm을 풀어 쓰자면, 새로운 policy π′\pi' 에서의 action-value가 state-value 보다 같거나 높다면, π′\pi'는 π\pi보다 같거나 좋은 policy다. 따라서 improved policy π′\pi'를 얻기 위해서는 action-value function을 최대화 하는 policy를 선택하면 된다.

π′(s)←arg⁡max⁡a qπ(s,a)=arg⁡max⁡a E[Rt+1+γvπ(St+1)∣St=s,At=a]=arg⁡max⁡a ∑s′,rp(s′,r∣s,a)[r+γvπ(s′)]\begin{aligned} \pi'(s) &\leftarrow \underset{a}{\arg \max}\ q_{\pi}(s, a) \\ &= \underset{a}{\arg \max}\ \Bbb{E} \lbrack R_{t+1} + \gamma v_{\pi}(S_{t+1}) \vert S_t = s, A_t = a \rbrack \\ &= \underset{a}{\arg \max}\ \sum_{s', r} p(s', r \vert s, a) \lbrack r + \gamma v_{\pi}(s') \rbrack \end{aligned}
“Grid-World Improved Policy”

최종적으로 improved policy는 action-value가 최대가 되는 action을 선택하는 policy가 된다. 예: s=1s=1에서 improved policy는 ←\leftarrow

k=0
좌: $v_k$, 우: greedy policy with $v_k$

HeadImg

k=1
좌: $v_k$, 우: greedy policy with $v_k$

HeadImg

k=2
좌: $v_k$, 우: greedy policy with $v_k$

HeadImg

k=5
좌: $v_k$, 우: greedy policy with $v_k$

HeadImg

k=50
좌: $v_k$, 우: greedy policy with $v_k$

HeadImg

k=257($\infty)$
좌: $v_k$, 우: greedy policy with $v_k$

HeadImg

Policy Iteration

우리의 최종 목적은 결국 최적의 policy를 구하는 것이다. Policy Iteration은 policy evaluation(EE)과 improvement(II)를 반복하는 과정이다.

π0→Evπ0→Iπ1→E⋯→Iπ∗→Evπ∗\pi_0 \xrightarrow{E} v_{\pi_0} \xrightarrow{I} \pi_1 \xrightarrow{E} \cdots \xrightarrow{I} \pi_{*} \xrightarrow{E} v_{\pi_*}
“Policy Iteration”
pseduo code

HeadImg

해설
2. Policy Evaluation

    - $\Delta$: 이전의 value와 현재 value의 차이
    - $v$: 이전 value 저장
    - 모든 state $s$ 에서 벨만 업데이트를 통해 현재 $s$의 value $V(s)$를 구한다.
    - $v$와 $V(s)$의 차이 절댓값과 $\Delta$중 큰 것을 남긴다.
    - $\Delta$가 아주 작은 임의의 수 $\theta$보다 작을 때 까지 Policy Evaluation을 한다.

3. Policy Improvement

    - 모든 state $s$ 에서 value가 가장 큰 action을 선택하여 policy $\pi(s)$ 로 지정
    - `old-action` 이 현재 policy $\pi(s)$와 같이 않으면 아직 `policy-stable` 상태가 아닌 것이다.
    - `policy-stable` 상태면 멈추고 최적의 value $v_*$와 최적의 policy $\pi_*$ 반환

Value Iteration

Policy Iteration의 단점은 매 스텝마다 policy evaluation이 포함된다는 것이다. 한번에 가능하게 만들 수 없을까?

“Value Iteration”
pseduo code

HeadImg

Generalized Policy Iteration

HeadImg

the general idea of letting policy-evaluation and policyimprovement processes interact, independent of the granularity and other details of the two processes

Policy evaluation과 policy imporvement의 반복이라 볼 수 있다. 그리고 매 스텝마다 최적만 찾을 필요는 없다. approximate policy and approximate value function를 통해서 적당히 좋은 최적값을 찾으면 최종적으로 최적의 값을 찾게 된다.