Temporal-Difference Learning

RL의 가장 중요한 아이디어라고 한다면, 의심할 여지도 없이 temporal-difference (TD) learning이다. TD learning은 Monte Carlo와 dynamic programing 아이디어를 조합한 것이다. TD learning은 Monte Carlo method처럼 environment dynamics에 관한 model이 없이도 순수한 경험(experience)만으로도 직접 학습이 가능하며, DP처럼 episode가 종료되기까지 기다리지 않아도 다른 예측치를 기반으로 value function의 update가 가능하다(이것을 bootstrap이라는 용어를 사용하여 설명하였다). TD, DP 그리고 Monte Carlo method에 사용하는 main concepts는 서로 혼합되어 사용 가능하므로, TD learning에 대한 개념을 이해해야 한다.

TD Prediction

언제나 같이 우선 policy \pi를 따르는 value function v_\pi를 예측하는 prediction problem으로 부터 시작해 보자. Monte Carlo methods는 state s를 거친후에 return값을 얻을 때까지 기다린 다음, 그 return 값을 V(S_t)의 target으로 사용하여 아래와 같은 식을 사용하여 value function을 update하게 된다.

RL eq6.1.png

여기서 G_t는 time step t 이후에 얻는 실제 return값이고, \alpha는 step-size parameter라고하며, 상수이다. Monte Carlo method가 return값을 얻기 위해 한 episode가 끝날때 까지 기다려야 한다면, TD method는 다음 time step가지만 기다려서 target값을 유추하는 방식을 사용한다. 즉, bootstrapping를 한다는 의미이다. 가장 간단한 TD method로서, TD(0)라고 불리는 방법은 다음과 같다.

rl-eq6-2

이 식에서 [ ]에 포함된 항을 TD error라고 하며 \delta_t로 표기한다. Monte Carlo update를 위한 target은 G_t인 반면, TD를 위한 update는 R_{t+1} + \gamma V(S_{t+1})이다. 이미 dynamic programming 포스팅글에서 밝힌 식이지만 다시 아래 update 식을 나타내었다. 아래 식의 맨위의 식은 Monte Carlo update target이라고 할 수 있고, 맨 마지막 식은 TD(0) update target이라고 할 수 있다. 이 update를 사용한 TD(0) prediction algorithm을 아래에 나타내었다.

rl-eq6-36-4rl-td0-prediction-algorithmTD(0) method의 backup diagram은 매우 단순하다. 맨 위에 있는 state node의 value function은이 state로부터 바로 다음 state로의 sample transition을 바탕으로 예측된다. 우리는 TD나 Monte Carlo method를 sample backup을 이용하여 update를 하는데, 이것은 DP의 full backup과는 달리 sample successor state만을 가지고 update를 하기 때문이다. 즉, DP는 모든 successor state를 고려하는 반면, TD는 하나의  sample successor state만을 이용한다는 의미이다.

rl-td0-backup-diagram

이 포스트가 참조하고 있는 Sutton & Barto 책에는 Monte Carlo method와 TD method를 보다 명확히 비교해 주는 예제가 있다. 사무실을 출발한 운전자가 집으로 차를 몰고 퇴근할동안 여러 상황에 따라 예상되는 주행시간에 변화가 있을 것이다. MC method는 그런 상황을 집에 도착하기 전까지는 전혀 반영하지 못하지만, TD method는 중간 중간의 상황에 따라 주행시간을 지속적으로 변경· update하는 것이다. 아래 그림을 참조하기 바란다. 왼쪽이 MC method, 오른쪽이 TD method에 해당한다.

rl-driving-home-travel-time-comparison

Advantages of TD Prediction Methods

TD methods는 다른 예측치를 참조해서 현 time step의 value function을 예측한다. 원문에 재미있는 표현이 있다. 단어의 유희이지만 이것만큼 정곡을 찌르는 말이 없는것 같다.

” They learn a guess from a guess”

TD method는 DP method에 비해 environment의 모델이나, reward 및 다음 state의 probability distribution을 필요로하지 않는다는 점에서 이점이 뚜렸하다. Monte Carlo method에 비해서는 on-line으로 incremental 방식으로 구현가능하다는 점이 이점이다. 즉, episode가 실행되는 도중에라도 다음 step 결과를 이용하여 update가 가능하다. 만약 한 episode가 꽤 오랜시간 동안 지속된다고 한다면 이 잇점은 더욱 크게 작용할 것이다.

그렇다면 한가지 의문점이 들 수 밖에 없다. 이렇게 예측치로만 update를 하게되면, 수렴을 보장할 수 있을까? 다행이도 그 질문에 대한 답은 “yes” 이다. TD method와 Monte Carlo method가 모두 수렴이 보장된다면, 다음질문은 어떤 method가 더 빨리 수렴하는가 일것이다. 그것에 대한 대답은 그다지 간단하지 않다. 수학적 증명뿐만 아니라 누구도 명쾌한 답을 내리지 못했기 때문이다. 그러나 stochastic tasks에 대해 constant-\alpha MC method에 비해 일반적으로 더 빨리 수렴한다고 한다.

Optimality of TD(0)

먼저 TD(0) method의 합리성에 대해 이야기 하기 전에 용어 정의부터 시작하도록 하겠다. 예를들어, 우리가 경험한 episode가 10개 또는 100정도 밖에 없다고 가정해 보자. 이경우에, value function의 update는 training data를 한 batch 단위로 정리했다가 한꺼번에 update를 시키는 형태로 이루어 진다. 새로 얻어진 value function을 기반으로 다음 batch의 training data를 이용하여 value function을 다시 update시키는 것이다. 이러한 방식의 update를 batch updating이라고 한다.

이처럼 batch updating하는 상황에서 sample이 작은 경우에는 Monte Carlo method와 TD(0) method가 서로 다른 결과를 내는 경우가 발생할 수 있다. 예를 들어 Markov reward process가 아래와 같이 8개의 episode를 데이터로 얻었다고 가정해 보자(episode가 state-reward순서로 나열되어 있다). V(A)와 V(B) 값을 예측해 보라. V(B)의 경우에는 상대적으로 쉽다. 3/4가 예상 답변이다. 그러나, V(A)는 어떠한가? 두가지 답을 예상해 본다. V(A)=0 또는 V(B)=3/4. 첫번째 답은 MC 방법에 의한 추론이고, 두번째 답은 TD(0)에 의한 추론이다. 어느것이 더 합리적인 답이라고 생각되는가? TD(0)가 더 합리적인 결과를 낸다고 판단할 수 있다.

Sarsa (On-Policy TD Control)

TD method를 control에 적용시켜 보자. TD도 역시 앞선 방법과 다르지 않게, GPI 패턴을 따르면서 exploration과 exploitation 개념의 관계를 접하게 되고, on-policy 방법과 off-policy방법으로 구분하게 될것이다.

첫번째 스텝은 state-value function보다는 action-value function을 다룰것이다. 먼저 state와 state-action pair가 번갈아 나타나는 다음과 같은 하나의 episode를 생각해 보자

rl-sarsa-sequence-diagram

여기서는 state에서 state로의 상태 변화에 따른 state-value에 관심을 기울이기 보다는 state-action pair에서 다음 state-action pair로의 전이를 고려해 보자. 이것은 동일한 Markov chain에 대한 다른 시각으로 관찰하는 것이다. 앞서 보인 state value에 대한 update와 마찬가지로 action value에 대한 update는 아래와 같이 나타낼 수 있다. 아래 backup diagram도 참조 바란다.

rl-eq6-7rl-sarsa-backup-diagram

이 update rule을 보게되면 (S_t , A_t , R_{t+1} , S_{t+1} , A_{t+1} )로 이루어진 5개의 항목이 사용되는 것을 알 수 있다. 이 5개의 항목을 고려하여 Sarsa algorithm이라 명명된 것이다.

Sarsa prediction method를 이요해서 on-policy control algorithm을 구축하는 것은 어렵지 않은 일이다. 모든 on-policy method와 마찬가지로, behavior policy \pi에 대한 q_\pi를 계속해서 예측하면서, 동시에 policy \pi를  greedy한 방향으로 변모시키는 방법이다. 일반적인 형태의 Sarsa algorithm을 아래에 나타내었다.

rl-sarsa-algorithm

Q-learning (Off-Policy TD Control)

RL에서 초기에 이루어낸 혁신중 하나는 Q-learning(Watkins, 1989)이라 알려진 off-policy TD control algorithm를 개발해낸 것이다.

rl-eq6-8

이식을 살펴보면, Q-learning은 action-value Q를 update하는 과정에서 곧바로 optimal action-value function인 q_*를 예측하려하는것을 볼 수 있다. 그러므로 획기적으로 알고리즘 분석을 간소화 시키면서 빠른 속도로 수렴에 이르도록 한다. 이 알고리즘을 아래 나타내었다.

rl-q-learning-algorithm

Q-Learning에 대한 backup diagram을 아래 나타내었다(왼쪽 diagram). Q-learning은 state-action pair로 부터 시작하고 다음 state에서 action value중 최대값을 선택하도록 arc를 표시해야 한다.

rl-q-learning-expected-sarsa-backup-diagram

Q-Learning과 유사하지만, next state-action pair에서 maximum을 선택하는 대신 각각의 action이 어떤 확률로 일어날 수 있는가를 감안하는 방법을 사용하는 다른 learning algorithm을 생각해 볼 수 있다. 이 알고리즘의 update rule은 아래와 같이 표현될수 있을 것이고, policy가 점차 개선됨에 따라 (deterministically moves to) Sarsa update로 변모하게 될것이다. 이것을 expected Sarsa라고 하며 backup diagram은 앞서 제시된 그림을 참조하기 바란다.

Double Q-Learning

새로운 Q-learning algorithm을 알아보기 전에 이 알고리즘이 탄생하게 된 배경부터 살펴보는 것이 이해가 쉬울것이다. 우리가 지금까지 살펴본 control algorithm은 maximization operation이 포함되어 있다. 그렇게 되면, 학습 초기에는 value function이 실제보다 높은 값을 가지는 경향이 생길 수 밖에 없다. 이것을 maximizaton bias라고 한다. 아무래도 이 편차가 있으면 실제 action-value값에 수렴하는 속도가 느릴 수 밖에 없다.

그렇다면, 이 maximization bias를 피하는 알고리즘은 있을까? 이 문제를 바라보는 관점중 하나는 이 문제가 같은 sample로 maximizing action을 선택하기도 하고 더불어 그것의 action value값도 동시에 예측하기 때문이라는 관점이다. 그렇다면, 역할을 분할해야 하는데, action-value를 예측하는 서로 독립적인 함수를 두는 방법을 생각해 볼 수 있다. 예를 들어 하나의 estimates Q_1 (a)은 maximizing action A^* =argmax_a {Q_1 (a)}를 결정하는데 사용하고, 다른 Q_2 (a)는 이것의 값인 Q_2 (A^*) = Q_2 (argmax_a {Q_1 (a)}를 예측하는데 사용하게된다. 이렇게되면, \mathcal{E} [Q_2 (A^*)] =q (A^*)라는 관점에서 bias를 가지지 않은(unbiased) action-value 값을 가질 수 있다. 이 아이디어를 double learning이라고 하며, 이 아이디어를 Q-learning에 적용하여 Double Q-learning이라고 한다. 아래에 update rule을 예시하였고, Double Q-learning의 알고리즘을 나타내었다.

rl-eq6-10

rl-double-q-learning-algorithm

알고리즘을 보면 action-value update가 반반의 확률로 다른 Q에 근거하여 이루어지는 것을 알 수 있다. 이 두 value function 근사치는 완전히 대칭적으로 이루어지므로 behavior policy는  이 둘을 다 사용할 수 있다. 예를 들어, Double Q-learning의 \epsilon - greedy  policy는 이 두 Q값의 평균을 기반으로 결정할 수 있다.

Afterstate value function

지금까지 state-value function과 action-value function을 사용하여 learning algorithm을 구현하였다. 이접근 방법이 대부분의 경우에 이용가능하나, 항상 예외는 있기 마련이다. 일반적으로, state로부터 agent는 action을 선택하게 되는데, tic-tac-toe game을 예를 들어 설명하면 agent가 action을 선택한 후의 상태에서 state-value function을 평가해야 하는 경우가 생긴다. Afterstates는 environment dynamics의 전체를 알지 못하더라도 초기상황을 아는 경우에 유용하다. 체스게임의 경우 우리가 말을 움직인 후의 상황은 곧바로 알지만 상대편이 어떻게 대응할지는 모르는 상태이다. 이 개념이 알고리즘을 설계할때 더 효울적인 이유는 tic-tac-toe 게임을 들어 설명할 수 있다. 일반적인 action-value function은 positions과 moves를 연결지어 value를 예측하게 될것이다. 그러나, 많은 position-move pairs는 아래 그림에서보인바와 같이 같은 position을 야기하게 될것이다.

rl-tic-tac-toe-afterstates

이런 경우에는 비록 position-move pair가 서로 다르지만 결론적으로 같은 “afterposition”을 내게되고 결국 같은 state-value를 가져야만 한다. 일반적인 action-value function은 서로 다르게 두 pairs를 펴가하겠지만, afterstate value fuction은 즉시 이 두경우는 같은것으로 평가한다. 즉, 왼편의 position-move pair에 대해 학습이 되었다면 그 결과를 즉시 오른편 pair에 전달하게 된다.

Sarsa & Q-learning for Cliff-walking

앞서 언급한 두 TD learning algorithm을 이용하여 cliff-walking task에 적용한 결과를 살펴보려 한다. 먼저 cliff-walking task는 RL algorithm test에 grid world task와 함께 자주 사용되는 task이다. 아래 그림을 먼저 살펴보기 바란다. Task 자체는 매우 간단하다. 출발지점(S)에서 목표지점(G)로 최대한 빠른 path로 도달하는것이 목표이나, 절벽(cliff)에 떨어지면 안된다. 이 task를이용하여 Sarsa와 Q-learning을 수행한 결과를 함께 나타내었다. 5000번의 episode를 수행하는 동안 agent가 받은 total reward의 trend를 살펴본 그림이다. 결과를 살펴보면, Q-learning은 target의  variance가 Sarsa보다 큰관계로 reward면에서 노이즈가 큰것을 알 수 있으며, Sarsa가 알고리즘면에서 훨씬 안정적으로 최적 path를찾아가는 것을 알 수 있다. 그러나, 이 결과가 두 알고리즘을 평가하는 기준으로 삼아서는 안된다고 강조하고 싶다. Task에 따라 결과가 달라질뿐만 아니라, \epsilon값이 점차 작아지도록 유도하면 마찬가지로 Q-learning도 안정적인 학습을 하기 때문이다.

rl-cliff-walking-diagram

Sarsa (\epsilon = 0.02 and \alpha =0.01)
rl-cliff-walking-sarsa-reward

Q-learning (\epsilon = 0.02 and \alpha =0.01)rl-cliff-walking-q-learning-reward

여기까지 temporal-difference learning에 대한 기본 이론을 살펴보았다. 특히 Sarsa algorithm과 Q-learning algorithm은 RL에서 매우 중요한 역할을 차지하므로 유념해 두기 바란다.

Note) 본 포스팅은 Sutton과 Barto가 공저한 Reinforcement Learning : An Introduction을 기초로 작성된것이다.

Advertisements

Temporal-Difference Learning”에 대한 답글 1개

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중