[RL] Off-policy Learning for Prediction

(해당 포스트는 Coursera의 Sample-based Learning Methods의 강의 요약본입니다)

 이전 포스트에서는 Monte Carlo method를 Policy Iteration에 적용하기 위해서 필요한 Exploration policy 중 하나인 \(\epsilon\)-soft policy를 소개했다. 그러면서 참고로 소개한 내용 중에 On-policy와 Off-policy라는 것이 있었다. 이 중 Off-policy에 초점을 맞춰서 다뤄보고자 한다.

 잠깐 설명이 되었던 바와 같이, On-policy는 action을 선택하는 policy를 직접 evaluate하고, improve시키는 방식을 말한다. 반대로 Off-policy는 action을 선택하는 policy와는 별개로 별도의 policy를 학습시키는 방식이다. 간단한 예를 들면, 사람이 취한 action에 대한 data를 바탕으로 optimal policy를 찾는 것은 action을 취한 주체의 policy와 우리가 찾고자하는 agent의 optimal policy는 서로 다르기 때문에 Off-policy method라고 보면 된다. 

 이렇게 직접 수행하는 policy와 학습시키는 policy를 구분짓기 위해서, behavior policy (\(b(a|s)\))와 target policy (\(\pi(a|s)\))란 개념이 나온다. 

그림 1. Target Policy

 용어가 복잡해보여서 그렇지만, 단어가 가진 뜻 그대로, Target policy는 우리가 궁극적으로 학습할 policy, 혹은 학습을 끝내고 실제로 적용할 때 반영할 policy를 말한다. 이때 target policy를 통해서 각 state(or state-action pair)에 대한 value를 학습하게 되고, 우리가 궁극적으로 지향하는 optimal policy가 이 target policy에 포함된다고 보면 된다. 당연히 value를 기반으로 동작하기 때문에 policy가 deterministic에 가까울 것이다.

그림 2. Behavior Policy

 Behavior policy 역시 단어 뜻 그대로, action을 선택하는 policy를 나타낸다. 그 대신 현재 action을 취하고 있기 때문에 현재 수행하는 policy의 좋고 나쁜 여부를 확인을 할 수 없다. 일반적으로는 위 그림과 같이 exploration이 포함된 policy가 이 behavior policy의 범주에 들어있다. 이 때문에 policy 자체도 stochastic하고, continual exploration이 발생할 여지가 target policy에 비해 크다. 

 이 두 policy의 관계에 따라서 현재의 approach가 on-policy냐 off-policy냐가 갈리는데, 우선 가장 기본적인 원칙은 항상 behavior policy의 확률의 범주는 target policy의 확률의 범주보다 넓다는 것이다. 수식으로는 다음과 같다.

$$ \pi(a|s) > 0 \textbf{   where   } b(a|s) > 0 $$

 당연한 이야기이겠지만, behavior policy가 exploration을 수행하는 와중에 optimal policy을 찾을 가능성이 존재한다는 것이다. 

그리고 on-policy와 off-policy에 대한 구분은 아래와 같다.

$$ \begin{align} \textbf{On-policy :   } \pi(a|s) = b(a|s) \\ \textbf{Off-policy :   } \pi(a|s) \neq b(a|s) \end{align} $$

 이제 Off-policy를 다룰텐데, 통계에 대한 지식이 있는 사람이라면 이런 질문을 던질 수 있다. 결국 우리가 다뤄야할 문제는 behavior policy랑 target policy가 다른 상황이고, 이 상태에서 Monte Carlo method를 적용한다는 건 sampling을 통한 data를 활용한다는 건데, 과연 behavior policy에서 sampling한 data의 경향과 target policy에서 sampling한 data의 경향이 같다는 걸 보장할 수 있느냐는 것이다. 기본적으로 behavior policy가 target policy와 다르기 때문에 sampling에 대한 distribution도 같다는 보장을 못할 것이란 것이다. 결국 우리가 하고자 하는 것은 다음과 같은 것이다.

$$ \begin{align} \textbf{Sampling :   } x \sim b \\ \textbf{Estimate :   } \mathbb{E}_\pi [X] \end{align} $$

당연히 behavior policy의 distribution과 target policy의 distribution이 다른 상태에서는 위의 과정을 바로 수행하지 못한다. 다들 알겠지만 우리가 구할 수 있는 것은 \(\mathbb{E}_b[x]\) 이기 때문이다. 그래서 sutton책에서 설명하는 것이 Importance Sampling이다. Importance Sampling이란 다른 distribution에서 sampling한 데이터를 알아야할 distribution에 맞게끔 보정해서 estimate하는 기법을 말한다. 우선 우리가 구해야 하는 target policy 상에서의 Expected return은 다음과 같이 풀어볼 수 있다.

$$ \begin{align} \mathbb{E}_\pi[X] &\doteq \sum_{x \in X} x \pi(x) \\ 
 &= \sum_{x \in X} x \pi(x) \frac{b(x)}{b(x)} \\
 &= \sum_{x \in X} x \frac{\pi(x)}{b(x)}b(x) \end{align}$$

첫번째 줄은 sampling data에 각 sampling data가 target policy내에서 발생할 확률(\(\pi(x)\))을 다 더한 것인데, 여기다 해당 sampling data가 behavior policy에서 발생할 확률(\(b(x)\))를 분모 분자에 모두 곱해준다. 분모 분자에 모두 같은 값을 곱했기 때문에 전체 결과에는 영향이 없는 상태에서 target policy와 behavior policy간의 비율(\(\frac{\pi(x)}{b(x)}\))을 하나의 인자(\(\rho(x)\))로 만들어서 표현한다. 이 인자를 Importance Sampling Ratio라고 부른다. 그러면 최종적으로 target policy상에서의 expectation은 다음과 같은 식을 도출할 수 있다.

$$ \begin{align} \mathbb{E}_{\pi}[x] &= \sum_{x \in X} \color{red}{x \rho(x)} b(x) \\
&= \mathbb{E}_{b}[X_{\rho}(X) ]\end{align}$$

그러면 위 식을 통해서 \(x \rho(x)\)라는 새로운 random variable을 가지면서 behavior policy의 distribution 활용하는 식으로 유도 되고, 결국 이 식은 behavior policy의 expected return을 구하는 식이 된다. 문제는 최종식을 어떻게 구하냐인데, 이미 Monte Carlo Method에서도 Expectation을 구할 때는 다음과 같은 관계를 사용했었다.

$$ \mathbb{E}[X] \approx \frac{1}{n} \sum_{i=1}^{n} x_i $$

이 관계를 그대로 가져오면 behavior policy상의 expectation도 Importance Sampling Ratio를 일종의 weight로 가지는 것에 대한 expectation으로 근사를 시킬 수 있다. 물론 이 값이 target policy의 expectation으로 근사된다.

$$ \begin{align} \mathbb{E}_{b}[X_{\rho}(X) ] &\approx \frac{1}{n} \sum_{i=1}^{n} x_i \rho(x_i) \\ & x_i \sim b \end{align} $$

이런 특성을 활용하면 이제 Off-policy Monte Carlo를 구할 수 있다. 결국 별게 아니라 기존의 On-policy Monte Carlo에서 Importance Sampling만 추가가 된 것이다. 기존의 방식대로라면 On-policy Monte Carlo는 다음과 같이 target policy \(\pi\)에 대한 State Value function을 구하는 것(\( V_{\pi}(s) \doteq \mathbb{E}_{\pi}[G_t | S_t = s] \))이었다. 이를 위해서 각 Return들을뽑아, 이에 대한 average를 하는 것이 Monte Carlo method였는데, 이제 Off-policy에서는 각 Return에 앞에서 언급한 Importance Sampling Ratio를 각각 곱해줘야 한다. 

$$ \begin{align} \text{Returns[0]} &\rightarrow \rho_0 \text{Returns[0]} \\ 
\text{Returns[1]} &\rightarrow \rho_1 \text{Returns[1]} \\
\text{Returns[2]} &\rightarrow \rho_2 \text{Returns[2]} \\ &\ldots \end{align} $$

이제 \(\rho\)를 구해야 되는데, 위의 식대로 따라가면 target policy \(\pi\)를 따라갔을 때의 trajectory가 나올 확률을 behavior policy \(b\)를 따라갔을 때의 trajectory가 나올 확률로 나눈 값이 될 것이다.

$$ \rho = \frac{\mathbb{P}(\textbf{trajectory under }\pi)}{\mathbb{P}(\textbf{trajectory under }b)} $$

 이를 이용해서 target policy \(\pi\)에 대한 State Value function을 구할 수 있다.

$$ V_\pi(s) = \mathbb{E}_b[\rho G_t | S_t = s] $$

 Trajectory는 말그대로 Termination될 때까지 수행한 state와 action을 나열한 것을 말하고, 우리가 관심있는 것은 현재 시점에서 Termination 시점 \(T\)까지의 trajectory이다. 가령 behavior policy \(b\)에 대한 trajectory의 확률은 다음과 같다.

$$ \mathbb{P}(A_t, S_{t+1}, A_{t+1}, \ldots, S_T | S_t, A_{t:T} = \\ \color{red}{b(A_t|S_t) p(S_{t+1}|S_t, A_t)} b(A_{t+1}|S_{t+1}) (S_{t+2} | S_{t+1}, A_{t+1}) \ldots p(S_T | S_{T-1}, A_{T-1}) \\ = \prod_{k=t}^{T-1} b(A_k|S_k) p(S_{k+1}|S_k, A_k) $$

 여기서 빨간색으로 표기된 \( b(A_t|S_t) p(S_{t+1}|S_t, A_t) \) 는 behavior policy가 State \(S_t\)에서 Action \(A_t\)를 취할 확률에 enviornment 내에서 현재 state와 현재 action이 각각 \(S_t, A_t\)인 상태에서 \(S_{t+1}\)로 바뀔 확률을 곱한 것이다. 우리는 현재 Markov Property를 따르고 있는 상황이므로 각 State들끼리는 독립적인 event가 될 것이고, 독립된 event가 연속해서 발생할 확률은 확률의 곱셈으로 구할 수 있다는 사실을 알고 있다. 그래서 위와 같이 product의 형식으로 표현할 수 있다. 결국 target policy에서의 trajectory도 거의 동일한 형태를 띌텐데, environment에서 State transition에 대한 확률은 같은 environment상에서 진행된 것이므로 동일할 것이고, 결국 각 policy가 trajectory내에서 state에 대한 action을 취할 확률만 최종적으로 남는다.

$$ \begin{align} \rho_{t:T-1} &\doteq \frac{\mathbb{P}(\textbf{trajectory under }\pi)}{\mathbb{P}(\textbf{trajectory under }b)} \\ &\doteq \prod_{k=t}^{T-1} \frac{\pi(A_k|S_k) p(S_{k+1} | S_k, A_k) }{b(A_k|S_k) p(S_{k+1} | S_k, A_k) } \\ &\doteq \prod_{k=t}^{T-1} \frac{\pi(A_k|S_k)}{b(A_k|S_k)} \end{align} $$

 결론적으로 Off-policy에서의 state value function은 위에서 구한 Importance Sample Ratio를 이용해서 도출된다.

$$ \mathbb{E}_b[\rho_{t:T-1}G_t|S_t=s] = v_{\pi}(s) $$

그래서 Every Visit Monte Carlo 에서 On-policy냐 Off-policy냐의 차이는 다음 알고리즘을 비교해보면 이해할때 도움이 된다.

그림 3. (On-policy) Every Visit Monte Carlo Prediction

그림 4. Off-policy Every Visit Monte Carlo Prediction

 위의 그림에서도 차이가 보이는 것처럼 Off-policy에선 behavior policy \(b\)에서 trajectory를 뽑았고, 해당 policy와 target policy간의 distribution 차이를 완화시켜주기 위한 Importance Sampling Ratio를 따로 구하는 부분도 추가되어 있다.

마지막으로 다룰 것은 ratio가 epsiode가 지나가면서 어떻게 계산되고, 이를 관리할 것인가에 대한 내용인데, 사실 monte carlo method의 특성상 모든 trajectory에 대해서 termination 되기 직전의 state부터 backtracking하면서 계산된다. weight으로 계산되는 ratio 역시 recursive하게 곱해지기 때문에 이를 하나의 변수처럼 두어 계속 \(\rho\)값을 곱해주는 형태로 가면 된다.

$$ \begin{align} W_1 &\leftarrow \rho_{T-1} \\ W_2 &\leftarrow \rho_{T-1}\rho_{T-2} \\
 W_3 &\leftarrow \rho_{T-1}\rho_{T-2}\rho_{T-3} \\ &\ldots \\ W_{t+1} &\leftarrow W_t \rho_t     \end{align} $$

 위의 알고리즘이나 설명에 대한 전개는 모두 State Value function을 기반으로 되어 있다. 혹시 이를 State-Action Value function (\(Q(s, a)\))으로 풀고자 하는 사람은 Sutton 책에서 그렇게 전개했으니 참고하면 좋을거 같다. (참고로 책에서는 Importance Sampling Ratio에 대한 cummlative sum도 유지하면서 이를 Q-value update할 때 사용했다. 그 차이를 제외하고는 핵심 개념은 동일하다.) 

그림 5. Off-policy MC prediction for estimating \(Q_{\pi}\)

 지금까지 다룬 내용을 요약하면, Monte Carlo method로 policy evaluation을 하되, 이를 Off-policy approach로 어떻게 적용이 가능한지를 살펴보았다. 무엇보다도 우리가 action을 취하는 policy (behavior policy; \(b\))와 실제 학습시키려는 policy (target policy; \(\pi\))가 다르기 때문에 이에 대한 간극을 줄이기 위해서 Importance Sampling을 적용하는게 필요했었다. 그래서 각 policy 별 trajectory에 대한 확률을 활용해서 Importance Sampling Ratio (\(\rho\))을 구했고, 이를 실제 state value function을 update하는데 사용하는 것까지 확인했다.