Monte Carlo Methods in RL (1)

이번 포스팅에선 Monte Carlo 추정법을 이용하여 가치 함수를 추정하는 방법을 소개하고자합니다.

개요

이전 포스팅에서 DP를 이용하여 가치함수를 계산하는 방법을 살펴보았습니다. 몬테카를로 방법에 들어가기 앞서 왜 우리가 공부해야되는지 가벼운 동기부여를 하겠습니다. 바로 앞문장에 '계산'이라는 말에 하이라이트되어 있듯 엄연히 DP는 주어진 정책과 모델을 알고있는 상황에 대하여 가치함수를 계산한 것이기 때문에 '학습'을 했다고 보기 어렵습니다. 다시 바로 앞 문장에선 모델을 알고 있는 상황을 대전제로 했습니다. 즉, 모델을 알고 있어야만 DP로 가치함수를 계산할 수 있습니다. 하지만 실제로 대부분의 상황에선 모델을 알 수 없기 때문에 적용하기 힘듭니다. 진정한 의미의 학습과 모델을 모르는 상황에서도 가치함수를 추정하기 위한 첫 시도로 몬테카를로 방법이 있습니다.

Monte Carlo Method

몬테카를로 방법은 RL에 국한된 방법은 아닙니다. 몬테카를로 방법을 RL에 적용하기 앞서 몬테카를로 방법에 대해 먼저 살펴보겠습니다. 몬테카를로 방법은 난수를 발생시켜 어떤 대상을 수치적으로 계산하는 방법입니다.

원의 넓이를 몬테카를로 방법을 이용하여 계산해 보겠습니다. 해석적으로 반지름 $r=1$인 원의 넓이는  $\pi r^{2}=\pi$로 계산할 수 있습니다. 몬테카를로 방법에서는 $x\in[-1,1]$, $y\in[-1,1]$인 $(x, y)$쌍을 난수발생 시킨뒤 넓이 4인 정사각형안에서 반지름 1인 원 안에 들어간 점의 수를 이용하여 원의 넓이를 계산할 수 있습니다. 예를 들어, 10개의 점을 난수 발생했을때, 7개 점은 원안에, 3개 점은 원 밖에 있다고 하면, 면적의 70%가 원의 면적이니 $4\times 0.7=2.8$로 원의 넓이를 계산할 수 있습니다. 아래의 그림은 1,000~100,000개의 점을 난수 발생시켜 원의 면적을 구한 결과입니다.

Figure 1: 몬테카를로 예제 (원의 넓이)

난수의 개수가 많아질 수록 참 값에 가까운 면적을 얻는 것을 확인할 수 있고, 100,000개를 발생시켰을 땐 실제 값과 거의 차이가 없습니다.

General Policy Iteration in Model-free Method

DP 포스팅에서 GPI에 대해서 살펴봤습니다. 다시 같은 그림을 이용하여 model-free 방법에 GPI가 어떻게 적용되는지 자세히 살펴보겠습니다.

Figure 2: General Policy Iteration

결론을 말하면 model-free 방법에서는 행동가치함수에 대하여 GPI를 적용합니다. (Model-based의 경우 상태가치함수 적용) 행동가치함수의 벨만 방정식은 $$\begin{align*}q_{\pi}(s,a)&=\mathbb{E}_{\pi}\left[\left.R_{t+1}+\gamma v_{\pi}(S_{t+1})\right|S_{t}=s, A_{t}=a\right]\\&=\sum_{s',r}\mathbb{P}(s',r|s,a)\left[r+\gamma v_{\pi}(s')\right]\end{align*}$$입니다. 즉 모델인 $\mathbb{P}(s',r|s,a)$를 알고 있어야 계산 가능합니다. 따라서 동일한 방법은 model-free 방법에 적용할 수 없습니다. 그래서 model-free 방법은 행동가치함수 기반 GPI를 적용합니다. 상태가치함수대신 행동가치함수를 적용하는 것 말고는 모두 동일합니다.

행동가치함수를 적용해도 GPI가 그대로 유지되는지 살펴보겠습니다. 정책 $\pi_{k}$의 평가가 됐고, $q_{\pi_{k}}$를 이용하여 정책 개선을 위 그림과 같이 greedy하게 진행하면, $$\pi_{k+1}=\underset{a}{\operatorname{argmax}}q_{\pi_{k}}(s, a)$$로 정책을 개선 시킬 수 있습니다. 그러면 모든 상태 $s\in\mathcal{S}$에 대하여, $$\begin{align*}q_{\pi_{k}}\left(s, \pi_{k+1}(s)\right)&=q_{\pi_{k}}\left(s, \underset{a}{\operatorname{argmax}}q_{\pi_{k}}(s,a)\right)\\&=\underset{a}{max}q_{\pi_{k}}(s, a)\\&\ge q_{\pi_{k}}\left(s,\pi_{k}(s)\right)\\&\ge v_{\pi_{k}}(s)\end{align*}$$ 상태가치함수기반 GPI와 동일하게 정책이 개선됨을 확인 할 수 있습니다.

Monte Carlo Method

On-policy v.s. Off-policy

정책을 학습하는데 있어, 행동 정책 (Behavior policy)과 목표 정책 (Target Policy)의 같음과 다름에 따라 on-policy, off-policy 방법으로 구분합니다. 여기에서 행동 정책은 에이전트를 실제 행동의 기준이 되는 정책을 의미하고, 목표 정책은 최적 정책을 구하기 위한 학습의 대상이 되는 정책을 의미합니다. On-policy의 경우 목표 정책 과 행동 정책이 동일하며, Off-policy의 경우 행동 정책과 목표 정책을 다르게 합니다. 왜 그럴까요? GPI를 다시 살펴보면 정책 개선을 할때 $\operatorname{argmax}$로 개선합니다. 그렇기 때문에 각 상태에서 deterministic한 행동 결정을 하고, 에이전트는 항상 동일한 방식으로 행동하게 됩니다. 

Figure 3: Grid World 예시

위와 같은 정책으로 계속 샘플링을 진행하더라고 $S_{1}, S_{5}, S_{9}, S_{10}, S_{14}, S_{16}$의 에피소드만 얻게될 것입니다. 학습은 많은 경험이 필요한 데 위와 같은 상황이면 충분한 경험을 쌓기 어렵습니다. 따라서 목표 정책과는 별도로 행동 정책을 고려하여 최대한 많은 상태에서 많은 행동을 하도록하는 것이 Off-policy 방법입니다.

Monte Carlo Iteration (On-policy)

행동가치함수의 정의는 아래와 같습니다 $$q_{\pi}(s, a)=\mathbb{E}_{\pi}\left[\left.R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\cdots\right|S_{t}=s, A_{t}=a\right]$$ 즉 몬테카를로 방법으로 행동가치함수를 학습하기 위해선 순차적으로 방문한 상태와 주어진 상태에서 행동한 기록(history)이 필요합니다. Continuing Task의 경우 끝이 없기 때문에 몬테카를로 방법으로 강화학습하기 어렵고(불가능한 건 아닙니다), Episodic Task에 대하여 적용가능합니다. 몬테카를로 방법은 여러 episode를 발생하고 얻어진 기록을 이용하여 평균내어 행동가치함수를 학습 할 수 있습니다. 예를 들어 아래와 같은 trajectory를 생각하면 쉽습니다. $$\begin{align*}S_{0}&, A_{0}, R_{1}, S_{1}, A_{1}, R_{2}\\S_{0}&, A_{0}, R_{1}, S_{1}, A_{1}, R_{2}, S_{2}, A_{2}, R_{3}, S_{3}, A_{3}, R_{4}\\S_{0}&, A_{0}, R_{1}, S_{1}, A_{1}, R_{2}\end{align*}$$ 이런 식으로 많은 trajectory를 얻고 아래와 같이 행동가치함수를 학습하는 방식입니다. $$q_{\pi}(s, a)=\frac{1}{N(s)}\sum_{i=1}^{N(s)}G_{i}(s)$$ 여기에서 $N(s)$는 상태 $s$에서 시작하여 종료상태까지간 횟수, $G_{i}$는 상태 $s$에서 시작한 $i$ 번째의 누적보상입니다. 이런 저런 상태에서 여러 행동을 하다가 보면 한 번 방문 했던 상태에 또 방문할 수 있습니다. 이런 경우엔 어떻게 해야할까요? 두 가지 선택 법이 있습니다. 어떤 상태에 제일 처음 방문한 것만 고려하는 first-visit 방법과 방문할 때 마다 새로운 시작시점으로 생각하는 every-visit 방식이 있습니다.

Figure 4: first-visit v.s. every-visit

DP는 모델을 알고있는 상태에서 모든 가능한 행동에 대하여 가치함수를 계산하지만,  몬테카를로는 에피소드를 샘플링하는 방식입니다. 따라서 deterministic한 정책을 이용할 경우 매번 같은 episode가 얻어질 수 밖에 없습니다.  두 가지 해결책이 있는데, 첫 번째는 exploring starts 방법이고, 두 번째는 off-policy 방법입니다. off-policy 방법은 다음 포스팅에서 자세히 다루기로하고 exploring starts 방법을 살펴보겠습니다.

Exploring starts 방법은 매 episode 시작 상태는 상태공간에서 랜덤하게 선택하고, 시작할 때만 가능한 주어진 상태에서 가능한 모든 행동을 랜덤하게 하는 것입니다. 이렇게 하면 상대적으로 모든 상태를 방문할 수 있게되어 학습의 취지에 부합하게됩니다. Exploring starts 기반 first-visit 몬테카를로 방법의 pseudocode는 아래와 같습니다.

FIgure 5: On-policy Monte Carlo Iteration (Exploring Starts)

앞서 exploring starts와 off-policy 방법이 있다고 했습니다. Off-policy는 왜 필요할까요? 눈치채셨겠지만 exploring starts는 불필요할 정도로 random하게 선택하기 때문에 계산된 가치함수의 분산이 커지는 문제점이 있습니다. 이를 보완하고자 off-policy 방법을 적용하게 됩니다.

마치며

DP 방법은 모델을 꼭 알고 있어야하는 단점과 학습이 아닌 계산이라는 점에서 한계점을 갖고 있습니다. 몬테카를로 방법은 이런 단점을 보완한 방법으로 무작위로 에피소드를 발생시키고 누적보상을 평균내는 방법으로 행동가치함수를 학습할 수 있었습니다. 그런데 determinitic하게 행동을 결정하면, 항상 동일한 에피소드가 얻어질 수 있어 제대로 학습할 수 없기 때문에 exploring starts 방법을 적용하는 것까지 확인했습니다. 이번 포스팅은 여기서 마치고, 빠른시일내 off-policy 몬테카를로 방법으로 찾아 뵙겠습니다. 감사합니다:)

References

• Sutton, Richard S., and Andrew G. Barto. Introduction to reinforcement learning. Vol. 2. No. 4. Cambridge: MIT press, 1998.