3장 Dynamic Programming

MostlyFor·2023년 1월 9일

강화학습

목록 보기

1/12

해당 글은 아래 강의를 보고 정리한 내용입니다.
https://www.youtube.com/watch?v=o85AaCB5Nck&list=PLKs7xpqpX1beJ5-EOFDXTVckBQFFyTxUH

DP 란?

: 시간에 따라 순차적으로 policy를 찾아나가는 방법

Key idea : divide and conquer

우선 perfect model을 가정함. 따라서 엄밀하게 말하면 모든 정보를 다 알아서 환경으로부터 배울 필요가 없음. 근데 왜 배우는가? DP와 RL은 비슷해서 이 다음 챕터에서 RL과 연결시킴.

Two key properties

Optimal substructure → 전체의 Optimal은 부분의 Optimal이 된다. MDP에서의 특징.
Ovelapping subproblems → 지금의 함수를 다음 시간의 함수로도 표현할 수 있음.

Planning

이 장에서 배우는 Planning은 2가지임.

Prediction : value function을 구하는 것을 prediction이라 함.
Control : optimal policy를 구하는 것을 Control이라 함.

Bellman Expactation equation

v_\pi(s) = E_\pi[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s] \\=\sum\limits_a\pi(a|s)\sum\limits_{s',r}p(s',r|s,a)[r+\gamma v_\pi(s')]

*첫번째 식에서 $E_\pi$ 의 의미가 헷갈릴수도 있는데 이건 s상태에서 a를 고르고 상태 s’이 될 경우까지 포함한 평균이다. 좀 포괄적인 개념인듯.

dp에선 sequential한 개념을 도입하기 위해 다음과 같이 응용한다.

Update rule for iterative policy evaluation (단어가 헷갈리는데 이건 policy가 주어졌을 때 value function을 구하는 것을 말함)

v_{k+1}(s) = E_\pi[R_{t+1}+\gamma v_k(S_{t+1})|S_t=s] \\= \sum\limits_a \pi(a|s)\sum\limits_{s',r}p(s',r|s,a)[r+\gamma v_k(s')]

*근데 여기서 k+1이랑 k 위치 바뀌어야 하는거 아닌가?

→ k는 시간이 아니라 버전느낌임. 예를 들어 새로운 k+1 버전을 만들기 위해서는 이전의 k 버전의 가치를 기반으로 계산한다는 느낌인듯. 예전에 이거 때문에 행렬 계산할 때 헷갈렸었는데, 그때는 v_k+1과 v_k가 같은 버전이고 지금은 서로 다른 버전임.

gridworld 예제에 policy가 주어졌을 때 value function을 어떻게 계산하는 지 나옴.

https://www.youtube.com/watch?v=3vuw23_l_oA&list=PLKs7xpqpX1beJ5-EOFDXTVckBQFFyTxUH&index=6

Policy Improvement

만약 value function이 주어지면 현재의 policy보다 좋은 policy를 항상 만들 수 있다.

greedy policy : $\pi'(s)=\argmax\limits_aq_\pi(s,a)$

현재시간 상태 s 에서 q function이 가장 큰 action a를 하는 정책을 쓰고 나머지 시간에는 기존 정책을 쓰는 정책 이렇게 해야 잘 했는지 비교 가능. 딱 한번만 바꿔보는 것. (편미분과 같은 느낌)

Policy Improvement Thorem

참고 자료 : https://jay.tech.blog/2016/12/26/dynamic-programing/

if\;q_\pi(s,\pi'(s))\geq v_\pi(s),\forall s \\v_{\pi'}(s)\geq v_\pi(s)

s에서 a라는 행동을 했을때 얻는 보상의 평균이 그 위치에서의 평균 이득보다 높다면 그건 더 좋은 정책을 한것이다.

결론 : 주어진 value function에 greedy한 policy만 취해도 항상 더 좋은 policy가 된다.

Convergence of Policy Improvement

q_\pi(s,\pi(s))=v_\pi(s)

강의에서 이 내용이 나오는데, 좌변은 policy에 대한 평균값인듯하다.

greedy한 policy를 계속 적용하다가 더 이상 바뀌지 않을 떄 optimal한 value function에 도달했다고 할 수 있음. 이건 bellman optimal value function임.

Policy iteration

기존 정책을 바탕으로 policy evaluation으로 최적의 가치함수를 찾음

→ policy improvement로 가치함수를 기반으로 정책을 greedy하게 적용시켜 정책을 변경

→ 다시 policy evaluation ...

Generalized Policy Iteration (GPI)

Policy iteration을 할 때 evaluation과정에서 value function을 수렴 시키지 않고 처음 몇번만 돌려도 policy는 정해져서 greedy policy를 구할 수 있다.

Value Iteration

evaluation을 1번만 수행하고 반복문을 돌리는 것. (one sweep)

MostlyFor

다음 포스트