[Ch.7] Off-Policy Control

이번 포스팅에서는 off-policy control에 대해 다루겠습니다. Ch.5의 MC와 Ch.6의 TD는 모두 on-policy control에 해당합니다. on-policy control이란, 현재 움직이고 있는(action을 취하는) policy와 improve하는 policy가 같다는 뜻입니다. MC나 TD의 경우 control을할 때 action을 취하는 policy와 improve하는 policy가 같습니다. 하지만, on-policy control에서는 greedy improvement의 방법으로 policy를 improve할 때 한계가 있습니다. 이를 해결하는 방법으로 ε-greedy improvement를 소개했었는데 다른 방법도 존재합니다. 그 방법이 바로 off-policy control입니다. off-policy control은 action을 취하는 policy(behavior policy)와 improve하는 policy(target policy)를 다르게 취하는 겁니다. 

 

 

 

Silver교수님 강의자료에 따르면, Off-policy 방법은 다음과 같은 4가지의 장점이 있습니다.

 

 

ㆍLearn from observing humans or other agents

ㆍRe-use experience generated from old policies π1, π2, ..., πt-1

ㆍLearn about Optimal Policy while following exploratory policy

ㆍLearn about multiple policies while following one policy

 

 

여기서 중요한 것은 3번째인데, exploration을 계속하면서도 optimal한 policy를 학습할 수 있다는 것입니다. 앞부분에서 이것이 가능한 이유에 대해 다루고, 이어서 Off-policy control인 Q-learning에 대해 다루겠습니다.

 

 

---

Importance sampling

 Importance sampling은 off-policy control에서 Behavior policy와 target policy가 다른 데도 optimal한 policy를 학습할 수 있다는 근거가 됩니다. wikipedia에서는 Importance sampling을 아래와 같이 설명하고 있습니다.

 

In statistics, importance sampling is a general technique for estimating properties of a particular distribution, while only having samples generated from a different distribution than the distribution of interest

Importance sampling은 모집단 분포의 parameter를 추정하는 방법으로써 알고자하는 분포와 다른 분포에서 sample을 얻어서 추정하는 방법이라고 합니다. 본래, 모집단의 분포를 모를 때는 random sampling을 하여 이 값을 추정할 수 있습니다. MC approximation도 같은 방법입니다. 문제점이 생기는 경우가 발생합니다. 다음은 Stanford대학에 Art Owen 교수님의 강의자료인데 Importance sampling의 intro부분에 아래와 같은 내용이 나옵니다.

 

In many applications we want to compute µ = E(f(X)) where f(x) is nearly zero outside a region A for which P(X ∈ A) is small. The set A may have small volume, or it may be in the tail of the X distribution. A plain Monte Carlo sample from the distribution of X could fail to have even one point inside the region A. Problems of this type arise in high energy physics, Bayesian inference, rare event simulation for finance and insurance, and rendering in computer graphics among other areas.

원하는 확률분포에서 sampling이 가능하다면 상관이 없지만, 이 것이 어려운 경우가 있습니다. 우리가 관심있는 분포를 따르는 확률변수 X가 속하는 set A의 크기가 너무 작아서 P(X)가 0에 가까울 정도로 작을 수 있습니다. 이때 이를 추정하고자 다른 분포를 통해서 이를 추정하고, 원래 분포에 맞게 조정해주는 방법이 Importance sampling입니다.

 

 

우리가 μ(=E(f(X)), X~P)를 추정할 때, sample mean을 이용하는 방법을 생각해 볼 수 있습니다. 하지만, 앞에서 언급한대로 sampling이 어려운 경우에는, trick으로써 새로운 분포 Q에서 sampling하고 본래 P의 분포로 맞춰줄 수 있습니다. 만약 확률변수 X(~P)가 continuous한 경우라면, 아래와 같이 식의 변형이 가능합니다.

 

 

따라서 우리는 다른 분포를 통해서도 추정을 할 수 있습니다. 이때 p(Xi)/q(Xi)를 importance weight이라고 합니다.

Off-Policy Prediction

 Off-policy MC prediction

 RL에서도 on-policy의 local optimum문제를 해결하기 위해 MC와 TD에 off-policy 방법을 적용시킬 수 있습니다. MC에서 update의 target은 return, Gt입니다. 

 

 

실제로 행동을 선택하는 behavior policy를 μ, policy improvement의 대상이 되는 target policy를 π라고 한다면, MC의 update 식에서 Gt는 μ를 따를 때의 reward들을 시간에 따라 discounting하여 더한 것입니다. 

 

 

따라서, 우리는 update할 때 target policy에 대한 return값으로 변형해주어야 합니다. 이를 위해서 π에 대한 MC target(Gtπ/μ)은 해당 episode에서 방문한 s, a들의 and조건으로 다음과 같이 importance weight을 sequential하게 곱해서 구할 수 있습니다.

 

 

 

따라서 아래와 같은 update식이 만들어집니다.

 

 

 

만약, multi episode를 진행한다면 state s를 방문한 횟수를 T(s)라고 할 때, episode마다 발생하는 return에 importance weight을 곱하여 아래와 같이 단순 평균을 취하는 방법으로 value func.을 추정할 수 있습니다.

 

 Off-policy TD prediction

 TD에서는 MC와 다르게 target 값, Rt+1+γV(St+1)에 대해 one step만 importance weight을 곱해주면 됩니다.

 

 

Off-Policy Control

 Q-learning

 사실 Importance sampling은 MC에서 q(x)만 잘 취해준다면 on-policy MC보다는 variance가 낮아지게 됩니다. 

 

 

 

 

이렇게 되면, optimal한 q(x)를 찾는 문제에 다시 봉착합니다. 또한 TD에서도 기존의 on-policy보다 variance가 높습니다.

 

 이를 해결하고자 하는 것이 바로 Q-Learning입니다. Q-learning은 importance sampling을 필요로 하지 않기 때문에, 간단히 off-policy 방법을 추구할 수 있습니다. Q-learning의 방법은 다음과 같습니다.

 

1) 현재 state S 에서 behavior policy, μ에 따라 action A을 선택. A = μ (S )

2) q-func.을 이용하여 update하는데 이때, 다음 state S'에서의 action A'는 π에 따라 선택. A' = π (St+1 )  c.f. At+1 = μ (St+1 )

 

 Off-policy control with Q-learning

 Q-learning에서는 behavior policy, μ을 ε-greedy로, target policy π를 greedy로 택하는 것이 가장 유명합니다. 본래 on-policy control에서는 ε-greedy 방법을 택하여 improve하면 ε의 확률로 선택하는 random action(exploration)때문에 수렴하는 속도가 느려집니다. 반대로 greedy 방법을 택했을 때는 수렴은 빠르게 되나 local optima에 빠지기 쉽습니다. 따라서, 이 둘의 한계에 대한 절충안으로 ε-greedy의 ε를 decay시키는 방법을 Part 0에서 다루었습니다. 아래는 Part_0 code에서 ε를 decay하는 방법을 적용한 부분입니다. 여기서 1/(i+1)을 곱한 것이 random요소를 decay하는 부분에 해당합니다. 

 

<Fig 1. decayed ε in Part_0>

 

ε-greedy의 ε를 decay하는 방법 외에 Q-learning을 통해서도 이를 해결할 수 있습니다. 

 

1) 현재 state S 에서 behavior policy, μ(e.g. ε-greedy)에 따라 action A을 선택.

2) q-func.을 이용하여 다음 state S'에서의 action A'는 π(e.g. greedy)에 따라 선택. 

 

3) Q-learning의 target은 아래 식으로 도출.

 

4) 아래 식에 따라 q-func.을 update.

 

 

위 update 식은 Ch.4에서 다룬 DP의 value iteration을 이용한 것입니다. value iteration과 같이 Q-learning control은 optimal action-value func.으로 수렴하게 됩니다. value iteration에서도 q-func.을 이용하여 policy evaluation을 진행하고 greedy하게 max값을 취하는 형태로 policy를 improve했습니다(엄밀히 말하자면 policy improvement는 evaluation과정에서 max값을 취하면서 함께 이루어집니다).

 아래는 Q-learning control의 algorithm입니다.

 

<Fig 2. The algorithm of Q-learning for off-policy control>

 

 아래는 앞서 언급했던 Part_0의 Q-learning 실습에서 구현한 code와 위 algorithm에 해당하는 부분입니다. 아래 code를 보시면 Repeat부분 이후에 진행하는 로직이 같습니다.

 

<Fig 3. The code of Q-learning in Part_0>

 SARSA vs Q-learning

 이제는 on-policy TD control인 SARSA와 off-policy TD control인 Q-learning을 비교하여 어떤 점이 개선되었는지 느끼기 위해서 예제를 하나 살펴보겠습니다. 아래 예제는 "Cliff Walking"이란 예제입니다. 

 

<Fig 4. Cliff Walking Example>

 

이 예제에서 agent는 Start state, S로부터 Cliff에 빠지지 않고 Goal state, G까지 최단거리로 이동하는 것을 목표로 학습합니다. Cliff에 빠지면 -100의 reward를 받고, time-step마다는 -1의 reward를 받습니다. 우리가 이 문제를 풀 때, optimal path를 한 눈에 찾을 수 있습니다. SARSA와 Q-learning 모두 ε-greedy policy를 취한다고할 때, agent 입장에서 SARSA를 택하면 곤란해집니다. 여기 저기를 exploration하다가 cliff에 빠지면, cliff 주위의 state는 모두 낮은 value func.을 갖습니다. 따라서 SARSA를 택하면 절대로 cliff 근처의 state는 갈 수 없게되고, optimal path를 찾지 못합니다. 이에 반해, Q-learning은 비록 cliff에 빠졌다고 한들 해당 하는 action-value func.만 낮아지므로 cliff 근처 state에는 도달할 수 있습니다. 단지, cliff쪽으로 가는 "action"만 하지 않으면 된다고 학습합니다. 따라서, SARSA보다 효율적으로 optimal path를 찾을 수 있습니다.

마치며

이제까지의 learning은 state와 action pair 경우의 수가 작기 때문에 모든 실측값을 얻어 계산할 수 있었습니다. 하지만, 현실 문제는 모든 경우의 수를 고려할 수 없기 때문에, 이를 함수화로 modeling하여 실측값과 근사하여 사용하자는 idea가 생겨났습니다. 이 방법을 사용하면, 아무리 많은 경우의 수가 있더라도 모든 data를 저장하지 않고 학습이 가능합니다. 다음 포스팅은 value function approximation에 대해 다루겠습니다. 

 

오탈자나 잘못 언급된 부분이 있으면 댓글로 지적해 주세요 :)

 

Reference

[1] https://dnddnjs.gitbooks.io/rl/content/q_learning.html

[2] 이웅원, 양혁렬, 김건우, 이영무, 이의령. "파이썬과 케라스로 배우는 강화학습". 위키북스. p.50-59

[3] http://www.phrgcm.com/blog/2017/11/16/importance-sampling/

[4] https://en.wikipedia.org/wiki/Importance_sampling

[5] https://statweb.stanford.edu/~owen/mc/Ch-var-is.pdf

[6] https://www.youtube.com/watch?v=S3LAOZxGcnk

[7] https://jay.tech.blog/2016/12/27/monte-carlo-methods/