강화학습 학습하기 - [5] TD

5편 - Temporal Difference Methods 

"강화학습 학습하기"시리즈는 KAIST 신하용 교수님의 수업 IE540 "DP and RL"수업 내용을 제가 제 방식대로 요약 및 정리한 것입니다. 퍼가실때는 미리 물어봐주시고, 내용은 제가 변형하고 추가하되 렉쳐노트에 쓰인 그림은 사용해도 된다고 교수님께 허락 받았습니다. 

0. Previously on..

저번에 시리즈에서 MC method(Monte Carlo method)를 배웠다. MC method는 Dynamic Programming과 다르게 model에 대한 정보가 없을 때 사용할 수 있었다. 즉, state transition matrix 혹은 reward model을 모르기 때문에 sample reward를 얻는 것 같이 직접 agent가 환경과 상호작용하면서 적절한 학습을 해야했다. 그러나 MC method는 크게 두 가지 단점이 있었다. 

첫 번째 단점은 Variance가 크다는 것이었다. 이 말은 sample이 trajectory(series of 'state->action->state->action->->')를 얻고 나서 다시 새로운 trajectory를 얻게 되는 과정이 변동성이 크다는 것이다. 예를 들어 어느 때는 대전에서 값을 구하고, 어느 때는 서울에서 값을 구하면 변동성이 크지 않겠는가. 

두 번째 단점은 MC method의 agent가 환경과 상호작용하면서 만드는 trajectory는 terminal state에 도달할 때까지 계속 진행된다. 그렇게 terminal state에 도달하고 나면 다시 backward로 reward값을 저장한다(MC method의 MC target인 G_t = R_t + G_t+1). 그래서 무조건 끝나야만 한다. 물론 discount factor를 잘 조정해서 500번 정도 state를 방문하면 사실상 terminal state로 할 수도 있지만, 종결조건이 필요하다는 것이 단점이었다. 

1. Temporal Difference Methods(so called TD, TD(0))

이러한 단점을 없애는 것이 Temporal Difference Methods(시간차 방법)이다. TD방법에 대해서 설명을 하기 전에 Notation을 하나 소개한다. 화살표에 learning rate를 쓰면, 아래 그림과 같은 notation이다. 앞에서 말한 것처럼 온고지신의 정신으로 현재 estimate된 것과 surprise of new data의 적절한 linear combination이다. 

Bellman expectation equation에 따르면 어떤 policy PI를 따르는 state value function은 다음 state에서 받는 reward와 discount factor * 다음 state의 state value function의 합의 기댓값과 같다. 이러한 점을 이용해서 특정시각 t에서의 state value function은 밑에 있는 식을 사용한다. 업데이트할 때 필요한 값은 Toward estimated return라고 부르는 빨간색 식이다. 

이 빨간 부분을 TD target, learning rate에 붙은 식을 TD error라고 한다. 

이 식을 보면 알 수 있듯이 현재의 V 값으로 현재의 V 값을 update하기 때문에 어떤 기준이 되는 값이 필요하기에 V(terminal state) = 0 으로 기준으로 잡는다.(0이 아니면 실제로 불안정하다고 한다.)

매 time step마다 action을 정하고, V(S_t)을 업데이트하기 때문에, MC method와 다르다. 

2. 간단한 예제와 MC와 TD를 비교

True value 값은 차례로 1/6,2/6,3/6,4/6,5/6 이다. 

V(A) = 0.5*0 + 0.5 *V(B), ... V(E) = 0.5 *1 + 0.5 * V(D)를 계산하면 V(State(A,B,C,D,E))의 값을 쉽게 구할 수 있다. 이 예제를 TD로 구한 것은 다음과 같다. 

TD로 구한 값은 점점 True value로 가까워지고, 우린 여기서 RMSE라는 값을 구할 수 있다. RMSE는 root mean squrar error라는 뜻으로, true value와 구한 값의 차이를 평균내고 그 평균 낸 것에 square root를 취한 것이다. 그래서 이 차이가 작을 수록 true value와 비슷한 것이다. 이 지표를 가지고 MC와 TD를 비교하면, 다음 아래 그래프와 같다.

TD가 더 빠르게 수렴하고, 더 큰 learning rate도 적용한다. MC의 경우 learning rate가 너무 크면 variance가 커져서 불안정해진다. 

전편에서도 나온 그림을 통해서 DP와 TD 그리고 MC method를 직관적으로 이해해보자. 

모델에 대한 정보를 이미 다 파악하고 있는 Dynamic Programming의 경우는 Full back up을 사용해서 모든 경우를 고려한 후 업데이트를 해줄 수 있지만 Reinforcement Learning의 경우는 model에 대한 정보가 없기 때문에 sample을 통해서 환경과 상호작용한 후에 정보(true value function, policy, state transition matrix,...)를 얻게 된다. 이러한 경우 업데이트할 때 target에서 현재값을 뺀 것을 learning rate로 곱하게 되는데 이때 시각 t에서 끝날때까지의 sum of discounted reward를 target으로 한다면 MC method이고 이때 그 다음 상태에서의 reward와 value function을 target으로 한다면 TD method이다. TD method처럼 현재 값을 이용해서 현재 값을 업데이트하는 방식을 bootstrapping이라고 한다. Bootstrapping은 TD 뿐만 아니라 DP에서도 사용한다. 

3. Epsilon- Greedy Policy Improvement

Policy evaluation을 통해서 true value값들을 계산한 후에는 그 값들을 통해서 policy를 더 좋게 향상시켜야하는데 이를 policy improvement라고 한다. PI를 진행할 때는 두 가지 선택지가 있다. greedy improvement와 epsilon-greedy improvement이다. 

강화학습에는 두 가지 요소에 대한 적절한 조화가 필요하다. Exploitation은 현재 주어진 상황에서의 best action을 선택하는 것이고, Exploration은 어디에 더 좋은 것이 있을까 생각하여 best action을 선택하지 않는 것이다. Exploitation만 사용한다면 local 값에 머물게 되고 exploration만 사용한다면 수렴하지 못하고 제대로 update가 안 된다. 그래서 조화가 필요하다. epsilon값은 얼마나 탐험할 지를 나타내는 수로 epsilon이 커지면 더 많이 탐험하게 된다. 

4. SARSA, Q-Learning ( On-policy TD control, off-policy TD control)

4-1. SARSA (on-policy TD control)

SARSA는 on-policy MC control using GLIE policy와 비슷하다. 알고리즘은 밑에 있는 그림과 같다. 

SARSA 알고리즘

여기서는 action value function을 사용했고, choose action을 할 때(policy가) epsilon-greedy를 사용하는 것이 특징이다. 그리고 그 값을 다시 action value 값에 넣어서 update한다. 즉 TD target에서 action value function의 액션을 epsilon greedy로 선택하는 것이 특징이다. behavior policy가 epsilon greedy이고 target policy가 똑같이 epsilon greedy이니 on-policy 알고리즘이다. 

4-2. Q-Learning (off-policy TD control)

Q-learning은 1989년에 나온 알고리즘으로 이전까지 Bellman expectataion을 이용한 TD control과 다르게 Bellman optimality equation을 사용했다. Q 값을 업데이트할 때 max Q(s',a)를 사용한다. 

Q-learning

업데이트된 Q-value는 traget policy를 통해서 업데이트되지만, 실제로 take action하는 Policy는 다르다. 알고리즘을 보면 쉽게 알 수 있는데, 처음에 behavior policy(epsiolon-greedy)를 통해서 action을 택하고 그 액션에 해당되는 reward와 next state를 관찰한다. 그리고 관찰한 결과 best action을 택해서 그 값을 Q(S,A)를 update하는데 사용한다. take action이 behavior policy, update할 때 best action을 택하는 것이 target policy로 각각 e-greedy, greedy policy로 다르다. 그래서 Q-learning이 off-policy인 것이다. 

Q-learning 알고리즘

4-3. SARSA, Q-learning 비교

SARSA의 경우는 epsilon값이 점점 작아져야지 optimal policy로 수렴한다. 그리고 Q-learning에서는  behavior policy가 target policy에 연관되지 않는다. behavior policy는 GL(greedy in the limit)과 IE(infinite exploration) 중 IE는 지켜야한다. 무한히 탐험하여 globally best action을 찾아야한다. 흔히들 SARSA는 겁쟁이라고 한다. 이유는 다음 예제인 cliff walking을 보면 알 수 있다. 

Cliff walking Example. Safet path의 G는 -17, Optimal path의 G는 -13이다. 

SARSA는 행동하는 policy와 target policy가 epsilon greedy이기 때문에 만약 optimal path로 SARSA agent가 간다고 하면 epsilon에 의해서 절벽으로 떨어질 수 있다. 그래서 가장 최대한 안전한 곳으로 멀리 돌아서 간다. 반면에 Q-learning은 다르다. Behavior policy를 통해서 절벽으로 수 없이 떨어졌어도 상관없다. 결국 최적의 값을 찾으면 그 값만 이용하기 때문에 가장 최적의 길로 간다. Q-learning은 off-line performance는 더 좋지만 on-line performance(수 없이 절벽으로 떨어지기 때문에)는 SARSA보다 안 좋을 것이다. 

Safer path : SARSA, Optimal path: Q-learning

그리고 만약 epsilon이 점점 줄어든다면, SARSA도 최적의 길로 수렴할 것이다. 

Back up diagram for SARSA(up), Q-learning(down)

5. Expected SARSA 

Different Target Values.

지금까지 Q-learning은 여러가지 action들 중 best를 하나 골랐다면, expected SARSA는 여러가지 action들의 expectation을 구하는 것이다. 이렇게 계산하면, much more stable than SARSA라고 한다. 

x축은 learning rate, y축은 sum of rewards per episode

또한 넓은 learning rate range를 가져서 practical하다. SARSA에서 learning rate가 커질수록 epsilon greedy에서의 탐험의 영향을 더 많이 받아서 var가 커지게 되면서 rewards가 나쁘게 된다. Expected SARSA와 Q-learning의 converge한 값들은 learning rate에 영향을 받지 않는다.

알고리즘 정리(출처:https://data-newbie.tistory.com/547)

6. Maximazation Bias and Double Q-Learning

6-1. Maximazation Bias

최대값을 구하는 과정은 control에 자주 사용된다. SARSA에서는 epsilon greedy action을 통해서 greedy한 action을 구할 때, Q-learning에서는 behavior policy 뿐만 아니라 target policy를 만들기 위해 true function을 업데이트할 때 사용한다. 그러나 maximazation bias라는 것이 있다. Jensen's inequality를 통해서 우린 최대화의 기댓값은 기대값의 최대화보다 항상 큰 것을 알 수 있다(positively biased). 그리고 max함수는 convex function임을 알 수 있다. 

Jensen's inequality, max function is a convex function 

Q_hat은 unbiased estimator of Q(s,a).E(Q_hat)은 Q이다.

positively bias이기 때문에 만약 larger variance of Q_hat이면 larger bias이다. 만약 Q_hat의 많은 샘플이 생긴다면, bias는 줄어들 것이다.

6-2. 예제

최대화 편차를 알 수 있는 예제가 있다. 

State A는 오른쪽으로 가면 reward로 0을 받고 terminal state에 도달하여 끝이고, 왼쪽으로 가면 state B가 된다. State B는 오른쪽으로 가면 state A가 나오고 왼쪽으로 가면 reward를 받고 terminal state에 도달하여 끝이다. 이때의 reward는 -0.1을 평균으로 가진 분산이 1인 분포이다. 그리고 이러한 reward는 총 n개이다. State A는 왼쪽으로 가면 평균 값이 -0.1인 reward를 받게 되니 최적의 선택은 오른쪽으로 가서 terminal state로 들어가는 것이다. 하지만, 

만약 B에서 왼쪽으로 가서 set1 같은 보상을 받았다면, 일반적인 Q-learning을 하게 되면 V(B)는 +0.3이 나온다. 분명 평균이 0인데도 최대화로 인한 편차가 나타난 것이다. 그래서 A 입장에서는 오히려 오른쪽이 아닌 왼쪽을 택하게 된다. 이러한 문제를 막기 위한 방법이 바로 Double Q-learning이다. Q값을 두 개로 만들어서 action을 select하는 Q값들이랑 update하는 Q값을 다르게 하는 것이다. 알고리즘을 보면 이해가 더 빠를 것이다. 

액션을 가져오는 Q값과 그 가져온 action값을 이용해서 TD target으로 쓰이는 Q값. Q는 두 종류.

Q=(Q_A + Q_B)/2

이를 이용해서 앞 부분 문제를 다시 풀면, 

즉 Q'(B,i*)가 큰데 i*이 좋은 값이 그런 것이라면, 이 값은 Q값에 반영될 것이다. 그리고 Q'(B,i*)가 큰데 random하게 좋은 것이었다면, 이 값은 Q값에 작게 반영될 것이다. 왜냐면 Q와 Q'은 다르기 때문이다. 

7. Summary

7-1. MC와 TD 비교

MC는 learns from complete episode이기 때문에 episodic task(task with finitie or indefinite horizon)만 적용가능하다. 혹은 discounted factor에 의해서 state 수가 많아지면 사실상 0이 되기때문에 continuing task의 경우도 제한적으로 적용가능하다. 그리고 MC target은 시각 t에서 끝날때까지의 return값이 G_t이며 이는 G_t의 expectation값이 true state value function이기 때문에 unbiased estimator이다. 어차피 끝까지 진행한 후에 업데이트를 시작하기 때문에 상대적으로 initial state에 대해서 예민하지 않다. 현재 값을 이용해서 현재 값을 업데이트하는 bootstrapping은 없고 끝까지 진행할 때 거치는 모든 action에 대해서 G_t 값이 영향을 받기 때문에 variance는 상당히 크다. Variance가 상당히 크기에 slow converge하다. 또한, MC method는 전체 trajectory를 고려하기 때문에 여러 개를 같이 고려하다보면 대부분의 값과 coincide한 패턴을 찾기 쉽다. 하지만 이 패턴은 미래의 episode와 값이 일치하지 않을 수도 있다. 그래서 이런 경우 보통 MC method는 overfit이 잘 일어난다. 

이에 반면 TD method는 learns from incomplete sequence이다. 그래서 episodic and continuing task에 모두 적용가능하다. 다음 상태의 값이 바로 TD target이 되고, immediate reward인 R_t+1만 영향을 받기 때문에 variance는 작고, V(s_t+1)과 V(s_t)는 expectation이 대부분 다르기 때문에(업데이트 중이기 때문에) some bias가 있다. 현재 값을 이용해서 현재 값을 업데이트하는 bootstrapping을 사용하고 바로 다음 스텝만 고려해서 업데이트 하기 때문에 초기값에 예민하다. 그리고 어떤 기준점이 필요하기에 V(terminal)은 0으로 지정해야할 필요가 있다. 만약 bias가 episode가 진행될 수록 작아진다면, 이는 consistent estimator가 되고 작은 변동성과 점점 작아지는 bias를 가지기 때문에 빠르게 true값으로 수렴한다. agent가 다음 스텝만을 고려하기 때문에 어떠한 패턴이나 일반화를 찾기 어렵다. 그래서 TD는 underfit이 일어나기 쉽다. 

7-2. TD(0) 학습 

TD(0)는

- model Free

- Sample backup

- Using Belmman equation: Markove state-> 수렴성 보장

- bootstrap을 사용하기 때문에 biased가 생긴다. consistent estimator라면 bias가 점점 줄어드는 경우이기 때문에 바람직하다.

- smaller variance of target이다. 

Maximization bias는 over-estimation of maximum이고 이는 Double Q-learning으로 줄일 수 있다.

8. 몇 가지 알면 좋은 것들(Think Ahead Questions)

만약 V(s)가 V(s+1)보다 더 정확하다면, V(s)를 이용해서 V(s+1)을 업데이트해도 괜찮다. 보통의 경우, V(s+1)이 terminal state에 가깝기 때문에 더 정확하다.