[기계학습] Key Algorithms in Reinforcement Learning

Welcome to Reinforcement Learning

이번에는 kernel $p$ 나 MDP를 모른다는 가정하에 어떻게 optimal policy를 추정할 수 있을지에 대해서 알아볼 것이다. Policy iteration, value iteration algorithm은 MDP와 모든 kernel 등에 대해서 완전히 알고 있다는 가정이 있어서 planning problem에 속한다. 이는 이러한 방법은 learning task가 아니라는 것을 의미한다. 그래서 지금부터는 우리가 MDP와 기존의 완벽한 상황에 대해 모른다는 상황에서 배워야 하는 경우에 대해서 집중해서 볼 것이다. 지금까지 봐왔던 것들은 agent와 environment 사이의 sequential interaction으로부터 배울 수 있었다. 그러나 모든 algorithm은 다음의 일반적인 policy iteraction framework를 기반으로 하고있다.
여기서는 각 policy의 evaluation을 수정하고 improvement 하는 것 대신에 $Q$ function을 근사하거나 추정하는 것이 필요할지도 모른다. 이렇게 $Q$ function을 추정하고나서 개선을 하는 것이 reinforcement learning의 기본적인 구조이다. 이러한 성능이 보장 된 algorithm이 정말로 많이 존재하며, 이 중에서 이번에는 2개의 algorithm MC와 TD에 초점을 두고 알아보고자 한다.

Monte-Carlo Methods

Monte Carlo(MC) method는 expectation을 구하는 것 대신에 random variable에 대한 확률을 weight라 했을 때 weighted summation을 기반으로 오로지 sample mean을 사용하는 것이다. $n$개의 i.i.d.를 만족하는 random observation이 존재할 때 random variable의 추정된 expecation은 다음과 같이 empirical mean 혹은 sample mean이 된다.

$\text{Basic Idea: }$

Sample mean estimation에 대해서 convergence와 correctness는 보장되어 있다. Law of large number에 의해서 무한히 많은 sample이 존재할 때 sample mean이 true expecation에 수렴한다는 사실이 보장된다. 그리고 각 sample은 서로 독립적으로 분포하게 되고, 이렇게 되면 우리는 convergence를 완전히 보장할 수 있게 된다. 이러한 insight는 RL에서도 사용될 수 있다.

MC method는 대략적으로 먼저 state에 대한 action을 계속 선택하고 수행해 나간다. 이렇게 끝날 때까지 반복해서 수행하다가 해당 episode가 종료되면 그때 reward를 사용해서 value function을 update한다. 이렇게 매 step이 아닌 episode가 끝날 때 value function을 update하므로 이 MC method를 episode-by-episode라고 할 수 있다.

MC for RL

여러 방법 중 하나로 sequential interaction을 기반으로 바로 kernel을 추정할 수 있다. 우리는 $s$에서 $s'$으로의 transition의 빈도를 알고 있어서 $\tilde{p}(s'|s,a)$를 $(s,a)$의 개수와 transition 개수의 비율로 계산할 수 있다.

이와 유사하게 동일한 작업을 reward에 대해서도 할 수 있다. 우리는 reward의 distribution을 추정할 필요가 없다. 대신에 policy iteration과 value iteration으로부터 expected reward $\tilde{r}(s,a)$를 추정할 수 있다. 이는 $(s,a)$의 개수와 $(s,a)$로부터의 $r$의 summation의 비율로 계산할 수 있다. 그러면 이제 추정된 transition probability와 expected reward를 policy iteration, value iteration algorithm에 넣어서 optimal policy를 추정할 수 있게 된다.

이렇게 하나의 옵션이 존재하고 다른 옵션으로는 $Q$ function으로부터 optimal policy를 구할 수 있다. Model을 바로 추정하기 보다는 $Q$ function을 근사하거나 추정하는 것을 생각할 수 있다. $Q$ function을 추정해서 얻게되면, argmax를 취함으로써 greedy improvement를 하거나 optimal policy를 찾을 수 있다.

편의성을 위해서 어떻게 sequential interaction으로부터 $Q$ function을 추정하는지를 설명하기 위해서 episodic MDP에 초점을 맞추고자 한다. 여기서 모든 episode는 유한한 시간 안에 결국 종결하게 된다. 이는 $p(T<\infty)=1$임을 의미한다. 이러한 조건을 가지면 우리는 어떤 한정된 시간에 interaction이 차단될 것이라고 예상할 것이다. 그래서 우리는 차례대로 추정할 수 있다.

Straightforward Algorithm: Evaluation

Policy evaluation에 있어서 직관적으로 생각할 수 있는 방법으로 다음과 같은 algorithm이 존재한다.

먼저 임의의 policy $\pi$에 대해서 sample들을 수집하고 누적된 reward의 empirical mean으로서 expected reward를 구하게 된다. 예를 들어 $s_1, a_1, r_2, s_2, a_2, r_3, s_3, \dots$라는 seqence가 존재할 떄 우리가 할 수 있는 것은 $Q(s_1,a_1)$이 $r_2 + \gamma r_3 + \gamma^2 r_4 + \dots$와 같이 sampling 될 수 있다. 이러한 sequence로부터 또 다른 $Q$ function의 sample을 $Q(s_2,a_2) = r_3+\gamma r_4 + \gamma^2 r_5+...$와 같이 얻을 수 있다. 이러한 계산 과정은 위에서 빨간색 네모에 해당하게 된다. 중요한 것은 각 $Q$의 sample이 수렴성을 보장하기 위해서 독립적이어야 한다는 것이다. 그러므로 반복되는 것은 피해야 한다. $s_2$가 $s_1$과 같고 $a_2$가 $a_1$과 같은 일이 발생할 수 있다. 그러나 $s_1$과 $s_2$의 중복된 관측치가 있다고 하더라도 sample들 간의 독립성을 보장하기 위해서 2번째 sample인 $Q(s_2,a_2)$를 포함하지 않아야 한다.

$Q$ function을 기반으로 greedy improvement를 수행할 수 있다. 여기서 모든 $s,a$는 $Q$ function을 추정하기 위해서 sampling 되어야 한다. 이것이 의미하는 바는 단지 action $a$를 선택하고 $Q$ function을 최대로 만든다고 하더라도, 비록 최선의 선택이라고 할지라도 우리는 각 state $s$에서 새로운 action을 탐색해야 한다. 이러한 탐색 과정를 강제하기 위해 $\varepsilon$ noise를 포함시켜 $\varepsilon$ 확률로 optimal action이 아닌 새로운 action을 탐색할 수 있다. 그리고 $1-\varepsilon$ 확률로 greedy action을 선택하게 된다.

이렇게 작은 $\varepsilon$으로부터 모든 action들을 관찰할 수 있고, 따라서 각각의 $(s,a)$ 쌍에 대해서 0이 아닌 sample들을 결국 얻을 수가 있다. 이로부터 수렴성도 보장할 수 있다. 이렇게 살펴본 내용이 첫번째 RL의 방법 중 하나인 MC이다.

Drawback of Monte-Carlo Methods

MC method를 사용하는데 있어 단점도 분명 존재한다. 우리는 episode가 끝날 때까지 기다려야 하고, 만약 그렇지 못하면 $Q$ function의 sample들을 모르게 된다. 이는 다시 말하면 long delay가 존재한다는 것이고, long delay라는 것은 high variance estimation을 말한다. $Q$ function의 sample 하나는 분명 종결 시간에 얻게 된 것이다. 그러면 variance가 모든 시간 동안 누적되었다는 것을 알 수 있다. 그래서 하나의 sample의 variance는 episode의 길이에 비례하게 될 것이다. 그러면 high variance를 가지게 되어 수렴성을 가지는데 좋지 못한 상황이 된다.

Temporal-Different Learning

이러한 문제를 해결하기 위해서 대안으로서 temperal-difference(TD) learning을 사용할 수 있다. MC method는 episode-by-episode로 마지막 step이 끝나야 value function이 update되지만, TD method는 step-by-step으로 매 step 마다 value function이 update된다는 차이점이 존재한다.

Rewriting Monte Carlo Prediction

TD learning은 다음의 MC method로부터 식을 변형하는 것부터 시작한다.

MC method는 그저 sample mean을 취하는 것이었다. 그래서 $n$개의 random sample로부터 구한 sample mean을 $S_n$이라고 할 것이다. 결과적으로 이 $S_n$이 $S_{n-1}$과 새로운 observation $x$를 포함하는 식으로 변형시킬 수 있다. 이러한 간단한 수학적 트릭은 먼저 summation을 2개의 term으로 나누는 것부터 시작한다. 그리고 $1/n$을 위와 같이 새로 적어서 전개하다보면 $S_{n-1}$과 $x_n$의 조합으로 식을 새롭게 나타낼 수 있다.

이로부터 expectation을 근사시키는 일반적은 approach에 대해서 생각해볼 수 있다. 우리가 원하는 것은 $S$를 expecation $E[X]$에 근사시키고자 한다. 여기서 우리는 $E[X-S]$가 0이 되기를 기대한다. 다시 또 여기서 $S_n=S_{n-1}+\alpha[X-S_n]$를 만족하는 반복되는 algorithm을 생각할 수 있다. 여기서 $\alpha$는 $1/n$으로 정확하게 sample mean에 해당하게 된다. 그러나 시간에 따라 변하는 아주 작은 constant도 생각할 수 있어서 $\alpha$를 충분히 작다고 여기면 수렴성을 보장할 수 있게 된다. 이러한 insight를 기반으로 MC prediction algorithm을 다시 적어서 expecation을 사용한 식으로 algorithm을 만들 수 있다.

$Q$ function의 업데이트를 위와 같은 식으로 다시 적어서 이해할 수 있다. 특히, $\alpha=1/n_{S_t,A_t}$로 설정하면 이는 MC method를 정확하게 구현하게 되는 것이다. 누군가는 다음의 algorithm을 expecation으로 equation을 해결하는 알고리즘로 이해할 수 있다.

이는 iterative method를 통해서 expecation을 근사하려고 시도한다. 여기서 업데이트는 현재의 estimation과 random sample 간 차이를 통해서 진행된다. 그래서 이는 MC prediction을 일반화 한 것이고, 더 나아가 동일한 것을 Bellman eqaution을 통해서도 할 수 있다.

Bellman Eqaution for Q-function

$Q$ function에 대한 Bellman equation은 위와 같이 주어지게 된다. 대부분의 deriviation은 Bellman value equation과 비슷하지만, 현재의 action $A_t=a$가 추가되었다는 점과 value function 대신에 $q_\pi(S_{t+1},A_{t+1})$이 사용되었다는 점이 다르다.

Temporal Difference Learning for Control

그리고 이는 expecation을 가지는 equation으로 간단해지게 된다.
그리고 이를 기반으로 일반적인 MC method를 만들었고, 다음의 algorithm을 적을 수가 있다. 이러한 방식으로 expecation을 추정하는 algorithm을 만드는 것을 stochastic approximation algorithm이라 한다.
이는 MC prediction과 거의 비슷한 구조를 가지고 있다. 여기서 파란 부분은 temporal difference error라고 부르며, 이는 time $t$와 $t+1$에서의 $Q$ function의 estimation 차이를 말한다. $Q(S_t,A_t)$는 time $t$에서의 $Q$ function의 estimation이지만, $R_{t+1}+\gamma Q(S_{t+1},A_{t+1})$의 경우는 다음 reward와 transition을 관찰할 때의 업데이트 된 prediction이다. 그래서 $Q(S_t,A_t)$는 estimatation of previous step, $R_{t+1}+\gamma Q(S_{t+1},A_{t+1})$는 estimation of next step이 된다.

그리고 이러한 algorithm은 또한 bootstrapping method라고도 부르는데, 이는 estimation이 또 다른 estimation을 기반으로 하기 때문이다. $Q(S_t,A_t)$를 업데이트 하는데 다른 $Q(S_{t+1},A_{t+1})$을 사용한다는 것이다. 이러한 algorithm으로부터 일단 true $Q$ function에 도달하기만 하면 차이는 매우 작아지게 되어서 true $Q$ function에만 집중할 수 있게 된다.

SARSA Algorithm

형식적으로 이 algorithm은 SARSA algorithm이라고 알려져있다.
각각의 업데이트는 $S_t,A_t,R_{t+1},S_{t+1},A_{t+1}$을 기반으로 하고 있다. MC method에서 우리는 episode가 끝나기를 기다려야만 했다. 각 $Q$ function의 업데이트에 있어서 이는 $S_1,A_1,R_1$부터 $S_t,A_t,R_t$까지 모두 의존해야 했다. 이는 long delay를 의미했다.

반면, SARSA algorithm은 한번의 업데이트에 있어서 하나의 transition만을 필요로 한다. 그래서 이 algorithm은 매우 빠른 속도로 진행이 된다. SARSA algorithm을 기반으로 $Q$ function을 추정할 수 있고, 수렴한 이후에는 새로운 sequence를 만들기 위해서 greedy improvement를 수행하고 $\varepsilon$을 더하게 된다. 그러면 우리는 다시 $Q$ function과 업데이트 된 policy을 추정할 수 있다.

MC vs. TD

TD method는 bootstrapping method라서 업데이트 할 때 또 다른 estimation을 기반으로 진행된다. 이는 TD method가 심하게 intialization에 의존한다는 것을 의미한다. 만약 초기값 설정을 잘못하면 업데이트 할 때 큰 error가 생기게 되어 크게 변동하게 된다. 그러나 MC method는 이러한 문제는 발생하지 않는다. Initialization에 robust하다고 볼 수 있다. 실제로는 trivial initialization 때문에 TD method가 MC method보다 성능이 좋다.

그리고 TD는 high bias라서 예측값을 사용하므로 실제 값과 어느정도 차이가 날 수 있지만 trade-off로 variance가 낮아지게 된다. 반면, MC는 high variance라서 최종적으로 episode의 결과값을 사용하므로 실제 값과 매우 가깝지만 trade-off로 variance가 높아지게 된다.

A Variant of SARSA: Expected SARSA