끄적끄적

요약

 MDP를 통해서 확률적으로 변화하는 과정을 어떻게 모델링하는지를 배웠지만, 현실의 많은 문제에서는 action $a$를 취했을 때 Transition probability $T(s,a,s')$와 $Reward(s,a,s')$을 알 수 없다. Reinforcement Learning이란 이러한 상황에서 policy $\pi$에 따른 path(episode)가 주어졌을 때, $T(s,a,s')$와 $Reward(s,a,s')$, 또는 각 상황$(s,a)$에서 주어지는 찬스라고 할 수 있는 $Q(s,a)$를 계산하는 방법이라고 할 수 있다.  

Model-based Monte Carlo

 Data(episode)가 $s_0;a_1 r_1 s_1;a_2 r_2 s_2; \dots$ 로 주어졌을 때, $T$와 $Reward$를 추측하는 가장 간단한 방법은 데이터로부터 $(s,a,s')$이 몇 번 나타나는지 세는 것이다. ($\hat{}$은 추정량을 의미)

 $\hat{T}(s,a,s')=\frac{\mbox{# of (s,a,s') occurs}}{\mbox{# of (s,a) occurs}}$

 $\hat{Reward}(s,a,s') = r \mbox{ in }(s,a,r,s')$

 수많은 데이터로부터 위의 과정을 통해 $T$와 $Reward$를 추정하는 것이 Model-based Monte Carlo 방법인데, 이 문제의 가장 큰 문제는, data에서 나타나지 않는 $(s,a)$에 대하여는 위의 값들을 알 수가 없다는 것이다. 즉, $s$에서 policy $\pi(s)$가 고정되어 있을때, $\pi(s)$에 의하여 선택되어 지지 않는 $a$가 있을 경우, 그 $a$에 대한 값들을 추정할 수가 없다.

 따라서 reinforcement learning을 하기 위해서는 다양한 $(s,a)$에 대하여 탐사해야 하는데, 이러한 문제를 exploration이라 하며 아주 중요한 문제이다.

Model-free Monte Carlo

 사실 $T$와 $Reward$로 우리가 하려는 것은 $V_\pi(s)$와 $Q_\pi(s,a)$를 구하려는 것이므로, $T$와 $Reward$가 아닌 $\hat{Q}_\pi(s,a)$를 직접 구할 수도 있는데 이것이 Model-free Monte Carlo에서 하고자 하는 것이다. utility $u_t = r_t + \gamma r_{t+1} + \gamma^2 r_{t+2} + \dots$ 로 주어질 때, Q value의 추정값은 다음과 같이 쓸 수 있다

 $\hat{Q}_\pi(s,a) = \mathbb{E}[u_t]$ where $s_{t-1} = s, a_t = a$

 하지만, 위에서 구한 추정값은 $\hat{Q}_\pi$ 이지 $\hat{Q}_{opt}$가 아니다. 즉, 이 방법은 데이터가 생성되는데에 사용된 $\pi$에 굉장히 의존적이다. 

 알고리즘은 아래와 같이 쓸 수 있다.

For each (s,a,u):

    $\hat{Q}_\pi(s,a) \leftarrow (1-\eta)\hat{Q}_\pi(s,a) + \eta u$, where $\eta = \frac{1}{\# of (s,a,u)}$

즉, 기존의 값 $\hat{Q}_\pi(s,a)$ 와 새로운 데이터 $u$ 가 서로 맞도록 조절해 가는 것이다. 또한, 위의 식을 아래와 같이 고쳐씀으로써, Model-free Monte Carlo의 target이 $u$임을 알 수 있다.

    $\hat{Q}_\pi(s,a) \leftarrow \hat{Q}_\pi(s,a) - \eta(\hat{Q}_\pi(s,a) - u)$

SARSA

 위에 언급했듯, Model-based MC의 target은 $u$인데, 문제는 $u$의 variance가 매우 크다는 것이다. 전 강의의 동전던지기 문제를 예로 들면 $u = 4, 8, 12, 16, \dots$ 의 값들이 나타날 것이다. 데이터가 아주 많다면 위처럼 평균을 취함으로써 맞출 수 있겠지만, 더 효율적인 방법으로서 제시되는 것이 SARSA이다.

    $\hat{Q}_\pi(s,a) \leftarrow (1-\eta)\hat{Q}_\pi(s,a) + \eta(r + \gamma\hat{Q}_\pi(s',a'))$

위의 업데이트 과정에서 알 수 있듯, model-free MC에서는 모든 r값의 함으로 u를 계산했다면, SARSA에서는 첫번째 Reward r값만을 취하고 뒤의 Reward들은 추정값인 $\hat{Q}_\pi(s',a')$으로 대체한다. 이렇게 함으로써 데이터 간의 $u$ 값의 편차를 줄일 수 있다. 다시 동전던지기 문제를 예로 들면, 첫번째에 실패한 데이터의 경우 $u=4+0$이 되고, 1번 이상 성공한 경우는 $u=4+\hat{Q}_\pi(s',a')$으로 모두 같게 된다. 또한, 실제 $u$값이 아닌 추정값이기에 편향(biased)되었다고 할 수 있다.

Q-Learning

 위의 SARSA가 $(s,a,r,s',a')$에 대한 모델링이었다면, Q-Learning은 $(s,a,r,s')$에 대한 모델링이다. 따라서 여기서는 $\hat{Q}_\pi(s',a')$ 대신 $V_{opt}(s')$을 사용하게 된다.

    $\hat{Q}_{opt}(s,a) \leftarrow (1-\eta)\hat{Q}_{opt}(s,a) + \eta(r + \gamma V_{opt}(s'))$

 여기서는 $\hat{V}_\pi(s)$가 아닌 $\hat{V}_{opt}(s,a)$ 이므로, 특정 policy에 대한 예측값이 아닌 $s$에서 가능한 모든 $a$에 대하여 최적의 값이 된다. 또한, Q-Learning 역시 다음과 같이 Stochastic하게 구현할 수도 있다.

    $\hat{Q}_{opt}(s,a) \leftarrow \hat{Q}_{opt}(s,a) - \eta(\hat{Q}_{opt}(s,a) - (r + \gamma V_{opt}(s')))$

Exploration

 위에서 언급했듯, reinforcement learning을 성공적으로 학습시키기 위해서는 모든 $(s,a)$를 돌아다닐 필요가 있다. 따라서 데이터를 생성할 policy를 정하는 것은 굉장히 중요한 일이다. 만약 $\pi(s)$가 $\hat{Q}_{opt}(s,a)$를 최대화 시키도록 하면, 여러 $(s,a)$를 돌아다니지 않고, 처음 발견한 가장 좋은 $a$만을 계속해서 선택할 것이다. 즉, Greedy하게 되어버린다. 그렇다고 random하게만 $a$를 선택하면 생성된 데이터들의 $u$값이 너무 낮게 된다. 따라서, 좋은 곳을 적절한 비율로 선택하며 가끔 색다른 선택도 하는 방식이 좋을 것이고, 이것이 Epsilon Greedy 방법이다. 즉, $1-\epsilon$의 확률로 전자를 택하고 $\epsilon$의 확률로 후자를 택하는 방법이다.