[RL 이론] - Dynamic Programming

◆ Dynamic Programming (DP) Introduction

MDP로써 환경을 잘 아는 perfect model이 주어졌을 때, optimal policy를 계산하기 위한 알고리즘의 집합.

 

DP는 RL에서 최적 policy를 찾을때 많이 쓰이고, 이를 위한 기반이 되는 algorithm을 제공하기도 함

즉, 다른곳에서 사용되는 RL 알고리즘도 결국에는 DP를 활용해 좀 더 빨리 찾는 방향이나, perfect하지 않은 model을 사용할 때 찾는 방향으로 발전하는 것이기 때문에, DP가 그런 알고리즘들의 근간이 되는 것이라 할 수 있다는 것.

 

DP의 아이디어는, “value function을 이용해서, 정말 좋은 policy를 찾아나가는 것.”

일단 Optimal value function을 찾으면, optimal policy를 찾는 것도 쉬워진다!

 

DP의 관점에서 이 식 v*(s)을 보자. 

State s에서 action a를 했을 때, (우리가 받는 Reward R + γ*(앞으로 받을 value들))의 기댓값을 max로 만드는 action을 찾아나가게 되면, 결국은 optimal policy를 찾게 되는 것임.

 

q*(s,a)도 마찬가지 ㅇㅇ

 

우리가 지금 선택한 policy가 얼마나 좋은지 평가(Evaluation)함으로써, 더 좋은 policy를 사용하는 방향으로 업데이트(improvement)해 나가면서 최종적으로 optimal policy에 도달할 수 있다는 것.

 

이를 위해서는 '어떻게 policy를 평가할 것인가'에 대한 정의가 완벽하게 내려져있어야 함.

 

---

◆ Policy Evaluation

어떤 정책 π에 대한 state-value function을 업데이트해 나감으로써, state s에서 π 정책을 평가할 수 있도록 방법.
단, MC처럼 에피소드 종결 후에야 알 수 있는 게 아님!
아직 state별 value를 잘 모르기 때문에 일단 임의의 값으로 초기화해놓고, iteration 돌면서 점차 업데이트함.

[컨셉] state의 value function을 업데이트 할거야. 근데 끝까지 도는 건 싫어! 내가 아는 정보로만 어떻게 해보자.
일단은 아직 state별 v(s)값을 잘 모르니까, 임의로 설정해놓자. 그러고나서 초기 v0(s)에서 한번, v1(s)에서 한번.. 값이 어느정도 일정할 때까지 반복해서 업데이트한다.
어느정도 값이 일정해지면, 그때의 state value function을 π를 평가하기 위한 믿을수있는 최종 vπ(s)로 사용할 수 있을 것이다! 즉, 내가 이 policy를 따라서 행동했을 때 어느정도의 값을 얻을 수 있는지 알 수 있게 되는 것(π를 평가할 수 있게 되는 것).

 

Policy evaluation이란, 임의의 정책 π에 대해서, state-value function vπ를 계산하는 방법.

vπ의 경우 이렇게 차근차근 풀어서 마지막줄처럼 나타낼 수 있다. (벨만 방정식)

 

이로부터, 다음과 같이 v(s)에 대한 update function을 쓸 수 있다.

 

※ 만약 environment dynamics가 모두 알려져있다면, 즉 어떤 state에서 가능한 action들과 reward들이 모두 확정이 되어있다면, 그냥 연립방정식을 통해서 value function을 풀 수 있게 된다. (MC 등의 방법)

그런데 사실 이런 연립방정식을 풀려면 계산 비용이 너무 비쌈. action이나 state가 많을수록 수식이 엄청 늘어날 것. 따라서 연립방정식을 푸는 대신에, iterative policy evaluation을 하자!는게 컨셉임. 이때, 지금 내가 관찰 가능한 영역에서만 evaluation을 하고, 이걸 반복적으로 수행하면서 추후 업데이트를 해나가는 과정으로 수행해나간다.

 

---

◆ Policy Improvement

q 함수를 업데이트해 나감으로써 최적의 policy를 찾는 방법.

[컨셉] policy evaluation은 다 끝냈어! 즉, π라는 정책을 따를 때 어떤 state에서 기대되는 가치를 나는 알 수 있어. 그런데.. 이 정책 그대로 하는게 정말로 최선일까? 이를 판단하기 위해, π를 따라서 행동하다가 어떤 한 state에서만 다른 정책 π`에 따라 행동을 해보자. (이때 π`는 다양한 정책이 될 수 있는데, 대표적으로 greedy한 결정을 하는 π`가 있다. 이는 이번 action을 통해 얻는 바로 다음 state에서의 reward가 큰 방향으로 선택하는 알고리즘). 예를 들어, 다른 모든 state들에서는 π(s)를 따라 행동하되, 어떤 한 state내에서 π(s) 대신에 π`(s)로 행동을 해봤는데, 결과가 기존보다 더 좋았다고 하자. 즉, 특정 state s에서 Qπ(s,π`(s)) 가 기존 π(s)보다 좋다고 하자. 그러면 π 정책의 s에서의 a를 π`(s)로 바꿔주자! 이런 식으로 점차 policy가 improve 되는 것.

 

 

이 policy가 정말 최적인가? 아니면 쪼금 바꾸면 더 좋아질 수 있냐? 의 문제.

어떤 policy π를 따라서 액션을 수행하다가, 어떤 액션 하나에 대해서만 다른 액션을 해보자! 

근데 만약에 이렇게 바꿔서 했을 때 결과가, 기존 pi로 수행했던 결과보다 더 좋다? 그러면 그 action만 쏙 바꾸는 것

 

ex) 현재 state에서 greedy하게 가장 좋은 action a`을 한번 해볼 수 있다. 그 뒤에는 다시 계속 π를 따라서 하고.

이랬는데 최종 결과가 기존

π보다 좋다면, 그 state에서는 기존 a대신 a`을 하도록 기존 π를 개선하자.

 

---

◆ Policy Iteration

이제 앞에서 배운 Policy Evaluation, Policy Improvement 를 반복해가면서, 최적을 정책을 찾아나가자!

각각 E, I로 표현하도록 하겠다.

 

우리가 policy를 더 좋은 방향으로 업데이트를 할건데, 이때 E와 I를 번갈아가면서 해줄거야. 

우선 어떤 polciy π0을 한번 Evaluation 완료하면 vπ0가 측정될 것임. 

이를 기반으로 Improvement해서, π 자체를 업데이트함.

업데이트된 π1를 기반으로 다시 한번 vπ1 측정하고, 또 다시 Improvement..

 

어느 순간 E와 I를 했을 때의 변화가 별로 없어짐(수렴). 그러면 종료하면 됨!

 

이런 방식으로 최적의 π*를 찾아나갈 수 있다!

 

< 예시 >

agent가 모든 방향으로 움직일 확률이 같은 π0가 있다.

그리드의 임의의 위치에 공이 하나 생성되고, 공이 1이나 16으로 가면 episode가 종료된다 하자.

reward는 다음과 같다.

• 한 step 이동할 때마다 reward = -1
• 1이나 16에 도달하면 reward = 0

이때 π0를 평가하고, 개선해보자!

 

[Evaluation]

처음에는 모든 action space가 25프로로 동일하다.

π0를 한번 evaluation 완료했을 때, 각 state가 가지는 value가 두번째 그림처럼 보일 것임. 

(아직까지 π0는 그대로 네 방향 동일한 확률로 움직이는 policy임)

 

[Improvement]

기존 정책보다 좀 더 괜찮은 게 있을거 같은데?

vπ를 보아하니, state 2에서는 모든 방향 동일한 확률로 가기보다는 왼쪽으로 가는 게 더 좋은데? 하고 슬쩍 바꿔봄.

근데 만약 그게 더 좋다? 그럼 정책 π 자체를 업데이트함.

 

[결과]

세번째 그림을 보면, 확실히 π0보다 좋아진 π1을 볼 수 있음!

 

이 예제는 간단한 예제라 한번만에 π*를 찾았지만, 보통의 경우 여러번의 E와 I를 반복해가면서 

각 state에서 가장 괜찮은 action을 선택할 수 있는 optimal policy π*를 얻을 수 있게 됨!

이 과정을 Policy Iteration 이라고 함.

 

---

◆ Value Iteration

Policy를 업데이트하는 또 하나의 방법 : Value iteration

Value iteration은, 앞서 했던 Policy Iteration 과정의 E, I를 그냥 합쳐버림.

저기 안에다가 그냥 바로 argmax a를 넣어버리는거임

 

즉 내가 현재 상태에서 평가를 함에 있어서 원래는 a가 정해진 대로 평가하는건데

그냥 저 식 자체를 극대화하는 a를 바로 고려해버리는 것

이를 통해 앞에서 열심히 반복하는 저 과정을 1번 step으로 간단화했다!

 

얘도 수렴할 때까지 반복함.

 

---

◆ Policy Iteration vs Value Iteration

일반적으로 policy iteration은 iteration 자체가 짧음. 빨리 수렴됨. 근데 각 iteration의 계산비용이 비쌈.(evaluation과 update가 나눠져있기 때문). evaluation 전부 끝낸 다음에, 그걸 기반으로 action을 바꿔가며 하는 것이니까.

 

근데 value iteration은, update와 iteration을 섞어버린 것이기 때문에 iteration이 좀 더 많이 필요함. 그대신, 원래 나눠져있던 update와 evaluation을 한번에 묶어버림 => 따로 하는거보단 계산비용이 작음

 

---

◆ Generalized Policy Iteration (GPI)

Evaluation과 Improvement가 interaction하면서 더 좋은 policy를 찾아나가는 과정을 총칭함.
(E-I interact 개념이 들어간 policy 개선 알고리즘들)

앞에서 우리가 policy evaluation, policy improvement를 이용해, 서로 interaction 하면서 최종적으로 policy 자체를 개선했었다. 이렇게 만드는 것 자체를 Generalized Policy Iteration이라 부름.

우리가 앞에서 배운 건 대표적인 예시를 배운 것 ㅇㅇ

 

즉, GPI란 evaluation과 improvement가 interaction하면서 더 좋은 policy를 찾아나가는 과정을 총칭하는구나! 라고 말할 수 있음.

 

이를 기반으로 하는 알고리즘들 역시 결국엔 어느 정도의 복잡성을 가지고 evaluation, improvement를 하느냐? 에 관한 이야기. 니가 하려는 일에 있어서 뭘 얼마나 중요하게 생각할거냐?의 느낌.이런것들은 convergence rate와 연관이 있음.

 

예를들어 fine-grained(디테일한, 자잘한) policy evaluation process인 경우, value function들을 측정함에 있어서 엄청 정확하게 하려고 함. 그래서 iteration도 많이 필요하고 convergence도 오래 걸릴 것임.

반면, coarse-grained (대충 하려는, 맥락만 보는 느낌) policy evaluation process는 정확도는 좀 떨어지지만, iteration을 조금만 돌게되고 convergence도 빠르다.

 

 

거의 대부분의 RL 알고리즘 자체가 GPI 개념으로 설명가능함.

이렇듯 E-I 과정들은 GPU내부에서 경쟁하기도, 협력하기도 하면서 Optimal Value Function과 Optimal Policy를 찾아나간다~ 라는 재밌는 이론.