Temporal-Difference Learning -2
4.2 Advantages of TD prediction Methods
TD방법은 다른 estimates에 기초하여 estimate를 update합니다. 즉 추측으로부터 추측을 배웁니다.
Monte Carlo와 Dynamic programming의 방법을 둘다 사용한 TD 방법은 어떤 강점이 있을까요??
첫번째, Monte carlo의 강점인 환경의 모델을 몰라도 사용 가능합니다. (reward와 다음 스테이트의 확률분포)
두번째, Dynamic programming에서 처럼 On-line 입니다.
세번째, 끝까지 기다리지 않아도, 중간중간 update가 가능하기에 episode가 많이 길거나 혹은 continue한 model에서 사용하기 좋습니다.
이 Temporal-Diffrenece Learning이 Sarsa와 Q-learning의 바탕 아이디어가 되었습니다.
지금부터 On-policy TD control 방법인 Sarsa, Off-policy TD control 방법인 Q-learning에 대하여 알아보겠습니다.
4.3 Sarsa : On-policy TD control
TD prediction의 control을 하는데 on-policy 방법을 사용하는 Sarsa에대해 배우도록 하겠습니다.
첫번째 해야할 것은 state-value function 대신 action-value function을 학습하는 것입니다.
On-policy method에서는 현재 behavior policy 를 따라를 estimate했던것과 마찬가지로
TD method를 사용하여 를 을 배울수 있습니다.
전에는 state에서 state로 변할때의 value of state를 배웠는데, 이제는 state- action pair에서 state-action pair로의 변할때의 state-action value를 학습하게 하겠습니다.
time step 에서 state action pair을 구하는데 다음 time step 의 pair을 estimate하여 action value를 estimate합니다.
여기서는 $$(S_t , A_t,R_{t+1}, S_{t+1},A_{t+1})를 이용하여 action value를 estimate하는데 이것을 Sarsa라고 부릅니다.
위의 back up diagram과 같이 sarsa는 다음 time step 에서 state와 action를 둘다 사용하여 action value를 estimate합니다.
on-policy TD Control인 Sarsa를 이용하여 를 estimate하는 pseudo code는 아래와 같습니다.
4.4 Q-learning: Off-policy TD Control
Q-lerning이라고 불리는 off-policy TD control인해 강화학습이 발전하는 계기가 되었습니다.
Q-lerning 의 정의는 다음과 같습니다.
Q-learning은 Sarsa와 같이 policy는 사용하며, 동시에 를 Target value로 두어 exploration과 exploitation을 같이 합니다.
Q-learning 의 pseudo code는 다음과 같습니다.
Q-learning의 Backup diagram은 어떻게 생겼을까요??
위의 Q-learning의 Back diagram을 보면,
action value인 (검은색 노드) 에서 action을 선택한 뒤, State 에서 선택할 수 있는 모든 action 중 action value를 가장 maximaize를 시킬수 있는 값으로 update합니다.
4.5Maximazation Bias and Double Learning
지금까지 배운 Control problem들은 전부 target policy를 maximize시키는 것이었습니다. 예를들어 Q-learning은 현재의 주어진 action value를 maximize하며 (greedy-policy)
Sarsa는 를 사용하여 maximize operation이 포함된 policy를 사용합니다.
이 알고리즘은 estimate value를 최대화 하는 것은 bias를 발생시킬 수 있습니다.
예를들면, state에 선택할 수 있는 여러 action이 있고, 그 action들의 진짜 value 는 0 이라고 한다면,
estimate value인 는 불확실하기 때문에 어떠한 estimate value는 양수가 될수 있고 또 어떠한 estimate value는 negative가 될 수 있습니다.
진짜 value는 이지만 estimate value는 estimate value를 maximze하기에 0이 아닌 양수의 값이 나올 것입니다.
이러한 positive bias를 maximization bias라고 합니다.
Maximization bias는 estimate value를 maximize할때 발생한다고 하였습니다.
이는 maximize한 action과 value를 estimate하는 것을 같이 하려고 할때 발생합니다!
그렇다면 true value인 )를 estimate하는 두개의 독립적인 함수 두개를 만들고, 하나는 action을 maximizing하는 를 estimate하고, 다른 하나는 그 argmax를 action을 사용하여 value를 estimate 한다.
예)
즉, estimate한 Q값을 계산할때 Q값의 최대값을 구하지 않고, 다른 네트워크를 이용해 action을 선택하고, 그 action에 대한 Q-value를 target값으로 주어 update합니다.
action을 선택하는 것과 Q value를 분리하며 overestimate를 많이 줄일 수 있습니다.
그리고 이 방법을 사용하였을때 $E[Q_2(A)]= q(A)$$이 성립하기에 unbiased 합니다.
이렇게 action을 선택하는 함수와 q value 함수를 분리하며 overestimate를 줄이는 방법을 Double learning이라고 합니다.
이 Double learning을 Q-learningg에 적용한것을, Double Q-learning이라고 부릅니다.
Q를 update할때 50%의 확률로 두 개의 function중 하나를 선택하여 update합니다.
Double q-learning pseudo code는 다음과 같습니다.
강화학습의 주요 아이디어라고 불리는 TD에 대하여 알아보았습니다.
몬테카를로와 DP의 방법을 사용해, 모델이 없어도 DP와 같이 time step마다 action value를 업데이트 할 수 있게되었습니다.
이 TD방법을 적용하여 on-policy TD control 방법인 sarsa,off-policy TD control 방법으로 Q-learning도 배웠고요.
value를 estimate할때 overestimate하는 Q-learning의 단점을 보안하기 위해, target value function을 두 개를 만들어
업데이트 하는 Double q-learning에 대하여 알아보았습니다.
강화학습에 딥러닝을 적용한 DQN과 DDQN으로 발전하는 이 q-learning, double q-learning에 대해 필수로 알아야 겠네요!!
내일 또 봐용
Reference
- Reinforcement Learning: An Introduction Richard S. Sutton and Andrew G. Barto Second Edition, in progress MIT Press, Cambridge, MA, 2017