강화학습팀 : 조민성 이상민 임정환 차원범 백윤성
발표자 : 백윤성
강화학습팀은 David Silver의 Reinforcement Learning Course를 리뷰한 팡요랩 유튜브를 보며 스터디를 진행하였다.
Lecture 1~6의 강의를 들었고 해당 리뷰에서는 Lecture 2~5의 내용에 대한 대략적인 리뷰를 진행한다.
리뷰에 앞서서 RL문제에 대한 분류를 보자면
1. environment에 대한 model을 아느냐, 즉 MDP를 모두 아는 상황의 문제를 model-based, MDP를 모두 알지는 못하는 문제를 model-free문제로 볼 수 있다. model-based 문제는 model을 통해 바로 다음 state를 planning이 가능하지만 model-free 문제는 알지 못하기 때문에 시뮬레이션의 방법을 사용한다.
2. 현재 state에서 value function을 추정하는 문제를 prediction문제, value function을 최적화하여 최적의 policy를 찾는 문제를 control문제로 볼 수 있다.
그렇다면 MDP, value function, policy가 무엇일까?
MDP는 RL문제를 정형화 하는 방법이다.
S는 agent가 가질 수 있는 state set, A는 취할 수 있는 action set, P는 state s에서 action a를 할 경우 그 다음 state s'으로 될 확률 matrix, R은 s에서 a를 할 경우 받는 reward, gamma는 return에서 다시 설명할 것이다.
model-based는 위의 정보를 모두 알고 있는 경우의 문제이고 model-free는 모두 알고 있지는 않은 경우인 것이다.
value function에 대해 알기 전에 return과 policy에 대한 내용을 보겠다.
return은 현재 시간 t에서 앞으로 받을 discount reward들의 총합이다. discount의 가장 큰 이유는 값이 수렴하여 수학적으로 편리하다고 한다. discount factor의 값이 큰 경우 미래의 reward의 영향을 더 크게, 작은 경우 영향을 더 작게 설정해 줄 수 있다.
policy는 현재 state s에서 action a를 할 확률분포를 나타낸다. policy는 agent가 갖는 것으로 MDP에서 표현하지 않는다.
state value function은 state s에서 policy 𝝅를 따랐을 때 얻을 return G의 기대값으로 현재 state에서 sampling을 통해 나온 G값들의 평균을 사용한다. action value function은 state s에서 action a를 한 후 policy 𝝅를 따랐을 때 얻을 return의 기대값이다. 우리는 앞으로 value function v와 q를 학습하는 것이 목적이고, 즉 return을 maximize하는 것이 목적이다.
마지막으로 Bellman equation이다. model-based에서 value function을 학습하는 방법으로 오른쪽 식의 유도에 따라 왼쪽 식들로 표현할 수 있다. value function의 의미는 한 step을 진행한 후 reward를 받고 다음 state에서 policy를 따르는 것과 같다. 아래의 두 그림은 v를 q로, q를 v로 표현한 것이며 앞으로 planning을 할 때 사용할 식이다.
Planning은 dynamic programming 방법으로 해결한다. DP는 복잡한 문제를 푸는 방법론으로 큰 문제를 작은 문제들로 나눠 작은 문제들의 solution을 종합하여 큰 문제를 해결하는 방식이다. planning의 방법으로 policy evalution, policy iteration, value iteration이 있다. policy evalution은 prediction 문제를 해결하는 방법, policy iteration과 valut iteration은 control 문제를 해결하는 방법이다.
policy evaluation은 policy 𝝅가 주어졌을 때 value function을 평가하는 문제이다. 앞서 보았던 bellman expectation equation을 사용하여 synchronous backup을 진행한다. 초기 value function은 무작위로 초기화 한 후 각 iteration마다 모든 state들의 value function값들을 update한다. 해당 방식을 지속적으로 반복하면 최종적으로 value function들은 하나의 값으로 수렴하게 된다.
다음은 random policy를 적용한 small gridworld에서 각 state들의 value function을 평가하는 과정을 보여준다. 각 iteration마다 bellman expectation backup을 사용하여 update하였다. 눈여겨볼 점은 greedy policy는 각 iteration마다 v가 더 높은 방향으로 policy를 정하는데 우리는 value function이 최종적으로 수렴하는 동안 optimal policy를 찾은 것을 볼 수 있다.
즉 우리는 policy evaluation하는 과정에서 optimal policy를 찾을 수 있다는 것이고 이를 policy iteration이라고 한다. evaluation과 improvement를 반복하는 것이다.
value iteration은 policy iteration과 다르게 policy가 주어지지 않은 상황에서 value function으로만 update를 진행하여 optimal policy 𝝅를 찾는 문제이다. bellman optimality backup을 사용하는데 이는 현재 state에서의 action들 중 action value function이 가장 큰 값을 선택하는 방법이다.
해당 문제는 초기 v값을 모두 0으로 초기화 후 bellman optimality backup을 이용하여 각 iteration마다 update를 진행한 결과이다. 각 state의 v값은 7번째 iteration 이후 모두 같은 값으로 수렴하며 이 value function을 이용하여 optimal policy를 찾을 수 있다.
다음은 model-free문제에 대해 볼 것이다. model-free prediction문제는 environment에 대해 모를 때 value function을 찾는 문제로 Monte-Carlo와 Temporal-Difference 방법이 있다.
monte-carlo는 경험으로부터 배운다는 개념으로 episode들의 return값의 평균으로 value를 평가하는 방식이다. 단점으로는 모든 episode가 끝나야 학습이 가능하기 때문에 terminal state가 있는 MDP에서만 사용이 가능하다.
monte-carlo는 first-visit과 every-visit 방법으로 나뉘는데 두 방법의 차이는 한 episode에서 state s를 처음 방문했을 때만 counter와 return을 증가시키느냐 매 방문 때마다 증가시키느냐의 차이이다. 모든 episode가 끝나고 나온 return 값들의 평균을 이용하여 value function을 측정한다. 최종적으로 해당 state에 무수히 많이 방문을 한다면 v𝝅(s)는 policy 𝝅에 수렴한 value function이 된다.
v(s)를 incremental mean을 사용하여 state에 방문 때마다 return값들을 모두 저장할 필요 없이 이전까지의 평균 값에 현재의 값을 바로 계산할 수 있다. 따라서 v(s) = s(s)/n(s)를 위와 같은 식으로 변형 가능하다.
temporal-difference 또한 경험으로부터 배운다는 개념이다. MC와의 차이점은 episode가 끝나지 않아도 update가 가능하다는 점인데 TD는 한 step을 더 가서의 추측으로 현재 step을 update하는 방식이다. 즉 MC는 episode 전체가 끝나고의 return값으로 update를 진행했다면 TD는 무작위로 한 step 앞으로 진행을 해보고 해당 step에서의 value function으로 현재 value 값을 계산하는 것이다.
위 슬라이드는 MC와 TD의 차이를 식으로 표현한 것이다. TD도 무수히 많은 경험을 통해 policy 𝝅에 대해 수렴하는 v𝝅를 찾을 수 있다.
이제까지는 한 step 혹은 episode가 끝날 때까지의 경우만을 보았다면 여러 step을 진행하여 value 값을 추정하는 방법도 있다. TD(n)으로 표현하며 적절한 n에 따라 더 좋은 성능을 내기도 한다. TD(λ)의 경우 모든 step에 대한 평균을 이용하는 방식이다. 평균을 낼 때 각 step에 해당하는 return에 가중치를 곱하여 더해주는데 λ는 0~1사이의 값으로 MC로 갈수록 더 작은 가중치가 곱해지는 것을 볼 수 있다. forward-view와 backward-view의 방법이 있다. 실제로 많은 논문에서도 TD(λ)를 사용한다고 한다.
다음으로는 model-free에서 control 문제를 본다. On-policy, Off-policy로 나눌 수 있는데 on-policy는 내가 최적화하고자 하는 policy와 실제 환경에서 경험을 쌓는 policy가 같은 경우, off-policy는 그렇지 않은 경우이다. 쉽게 말해 off-policy는 다른 이가 쌓아놓은 경험을 토대로 배우는 방법으로 볼 수 있다.
왼쪽은 이전에 보았던 policy iteration이다. 이를 model-free에 맞게 바꾸어 볼 것이다.
1. prediction에서 본 monte-carlo를 policy evaluation을 할 때 사용하면 되지 않을까? 사용가능하지만 model-free는 MDP를 모르기 때문에 improvement가 불가능하다. 따라서 state value function v대신 action value function q를 evaluation하는 방식을 사용하는데 MDP를 몰라도 현 state에서 할 수 있는 action이 무엇인지는 알기 때문에 q가 가장 높은 action을 취하는 방식으로 improvement가 가능해진다.
2. 1의 방식을 취해도 문제가 있다. greedy policy는 현 시점에서 가장 좋은 방향으로만 움직이기 때문에 충분한 exploration이 불가능하다. 따라서 ε의 확률로 랜덤한 action을 취하고 1-ε의 확률로 greedy하게 action하는 방식을 사용할 수 있다.
3. 추가로 MC는 모든 episode가 끝나야 policy evaluation이 끝나지만 한 episode가 끝날 때마다 improvement를 진행하여 더 효율적으로 진행한다.
policy evaluation에서 MC 대신 TD를 적용하는 방법은 sarsa라고 한다. 앞서 보았던 n-step, λ sarsa 방법 또한 있다.
off-policy는 내가 최적화하려는 target policy 𝝅는 behavior policy μ를 통해 action을 sampling한다. importance sampling과 Q-learning의 방법이 있다.
importance sampling은 왼쪽의 방법을 사용하여 다른 확률 분포로부터 나의 기대값을 추출한다. 즉 두 분포의 확률의 비율을 곱하면 다른 분포에서의 기대값을 얻을 수 있다. MC는 최종 return값을 얻을 때까지의 각 policy에 따른 확률의 비율들의 곱을 통해 얻고, TD는 한 step만 진행했을 때 해당 확률의 비율을 곱해준다.
q-learning은 off-policy에서 q에 대해 학습한다. 이 때는 importance sampling 없이 가능하다. 현재 state에서 취할 action At는 behavior policy에서 고르고 TD target의 q에는 target policy의 action A'을 취해주는 방식을 사용한다. 한 step이후의 q는 다음 state에서의 추측치이므로 target policy의 값을 사용해도 무방하다고 한다.
더해서 우리는 target policy에서 action을 선택할 때에는 greedy하게, behavior policy에서 action을 선택할 때에는 ε-greedy를 사용하여 policy를 improve하면서 exploration을 보장할 수 있다. 최종적으로 오른쪽의 식이 나오며 sarsa와 다르게 내가 할 수 있는 action들 중 max값을 선택하는 방식을 사용한다.