[4] DP, MC, TD(0)

Reinforcement Learning : An Introduction - [4] DP, MC, TD(0)

Chapter 4. DP, MC, TD(0)

Planning & Learning

• planning

  앞서 배운 environment에 대한 model 을 가지고 있는 경우, 
  Markov Decision Process 에 대한 full knowlege 를 가지고 있게 된다. 
  이를 planning 이라고 하며 MDP 의 정보를 기반한다.

• learning

  Learning이란 environment의 model을 모르지만 상호작용을 통해서 문제를 푸는 것을  
  말합니다.

이중 planning 의 process 는 prediction 과 control 로 이루어진다. Prediction 에서는 value function 을 estimate 하게 되며, control 에서는 optimal policy 를 estimate 한다.

다른 말로 planning 은 model based , learning 은 model free 라고 볼 수 있다.

• planning process

  

Dynamic Programming

DP 는 planning 의 일종이다. 즉 MDP 에 대한 정보를 알고 있다고 가정한다.
이에는 policy iteration 방식과 value iteration 방식이 있다.
각각은 prediction 과 control process 로 구성된다.

Policy Iteration

Prediction

value function 을 구하기 위한 과정을 prediction 이라고 한다.

prediction 을 위해서 DP 의 policy iteration 방식 에서는 policy evaluation 을 수행합니다.

• policy evaluation

policy evaluation 에서는 현재의 policy 에 기반한 value function 을 찾기 위해서

아래의 bellman expectation equation 을 사용한다.

앞서 방식과 비교해보면, k 첨자가 생긴것을 알 수 있는데, 이것이 iteration number 로 t(state transition number)와 구분된다. ($s -> s' = s_t -> s_t+1$)

cf. k 첨자가 없는 MDP 에서 배운 value function

위 equation 에서 MDP 를 모두 알고 있기 때문에 P를 알고 있고, 모르는 v 에 대한 linear equation 을 푸는 것이다.

처음엔 arbitary approximation value function 부터 시작해서 $V_0, V_1, V_2 .. $ 이런식으로 업데이트 해나간다.

이런식으로 무한대로 반복하게 되면 upper bound 가 존재한다는 가정하에
해당 policy 에 대한 true value function 을 수렴하여 찾을 수 있다.

Control

• policy improvement

해당 policy 에대한 true value function을 얻은 후 policy 를 업데이트 해주게 되는데 다음 식에서 보듯이 간단히 다음
state중에서 가장 높은 value function을 가진 state로 가는 것이다. 즉, max를 취하는 것입니다.

policy evaluation, improvement 이 두과정을 지속적으로 반복하게 되면서, optimal policy 를 찾아 가게 된다.

Value Iteration

value iteration 이 policy iteration과 다른 점은 Bellman Expectation Equation이 아니고

Bellman Optimality Equation을 사용한다는 것이다.

이는 첫번째 action 이 optimal 하다면 이후 다른 action들도 optimal 할 것이라는 기대에 기반한다.

Policy Iteration의 경우에는 evaluation 할 때 수많은 계산을 해줘야하는 단점이 있었는데 그 evaluation을 단 한 번만 하는 것이 value iteration이다. 따라서 현재 value function을 계산하고 update할때 max를 취함으로서 greedy하게 improve하는 효과를 준다. 따라서 한 번의 evaluation + improvement = value iteration이 된다.

argmax 대신 max 가 사용된 부분이 특징이다. 즉 policy 를 고려해 모든 action 에 대해서 value function 을 구하는 것이 아니라 바로 maximum value function 으로 업데이트 하게 된다.

DP Summary

우리는 DP 의 방법으로 Policy Iteration 과 Value Iteration 에 대해서 배웠고, 정리하면 위의 표와 같다.

즉, DP 는 prediction만 하는 경우 iterative policy evaluation 을 bellman eq. 을 통해서 수렴하는 value function 을 구하는 것이고,

prediction + control 중 policy iteration 의 경우 bellman expectation

cf. extension of dp 부분 참고 - synchronize/asynchronize , full-backups/sample-backups

Monte Carlo

앞서 DP 의 경우는 model based, planning 방식이었으나 Monte Carlo 방식은
MDP = environment 에 대한 정보를 모르므로 model free 방식에 해당한다.
또한, DP 는 full-backup 에 기반하여 전체 state 를 업데이트 해줬지만, 여기서는 sampling 방식을 사용하게 된다.
sampling 방식을 사용하는 방법으로 MC 와 TD 가 있다.
앞서와 마찬가지로 prediction 과 control 의 process 를 거치게 된다.

prediction

True value function 을 찾기 위한 prediction 과정에서 MC 는 에피소드 단위의 sampling 정보를 이용한다.

First - visit / Every - visit

• First -visit method

  

처음 방문했을 때만 N(s)를 증가시키고 해당 state 의 reward 를 return 에 넣는다. (S(s) 표기가 이상한거 같다.? -> return 을 s 로 표기한 것 같다.)

• every - visit method

  

이는 방문할때마다 counter 를 증가시키고 평균을 내는 방식이다.

• incremental method

  평균을 구할때 모든 state 에 대한 rewards 를 저장해 두었다가 계산시 computation load 가 크므로, 이에 incremental 하게 mean 을 구하기 위해서는 아래와 같은 방식으로 계산한다.

  

  ​

즉 이전까지의 mean 이던 value function 을 이용하여 새로 구한 $G_t$ 와 계산하여 업데이트 한다.

• non - stationary environment

  

  Non stationary 에서는 이전까지의 counting number 로 나누어주는 것이 아니라 특정 parameter $\alpha$ 로 control 하는 것이 특징이다.

control

(from 이웅원님 글 참고)

위에서 구한 valuation function 이 monte-carlo policy evaluation 에 속하며

다음으로 마찬가지로 policy iteration 을 수행해주며 control 을 수행한다.

하지만 여기에 몇가지 문제 점이 있다.

1) Value function
2) Exploration
3) Policy Iteration

(1) Value function
현재 MC로서 Policy를 evaluation하는데 Value function을 사용하고 있습니다. 하지만 value function을 사용하면 policy를 improve(greedy)할 때 문제가 발생합니다. 원래 MC를 했던 이유는 Model-free를 하기 위해서 였는데 value function으로 policy를 improve하려면 MDP의 model을 알아야합니다. 아래와 같이 다음 policy를 계산하려면 reward와 transition probability를 알아야 할 수 있습니다. 따라서 value function 대신에 action value function을 사용합니다. 그러면 이러한 문제없이 model-free가 될 수 있습니다.

(2) exploration - $\epsilon-greedy$ method

현재는 policy improve는 greedy policy improvement를 사용하고 있습니다. 하지만 계속 현재 상
황에서 최고의 것만 보고 판단을 할 경우에는 optimal로 가는 것이 아니고 local obtimum에 빠져버
릴 수가 있습니다.

따라서 그에 따른 대안으로서 일정 확률로 현재 상태에서 가장 높은 가치를 가지지 않은 다른 action을 하도록 합니다. 그 일정 확률을 epsilon이라하며 그러한 improve방법을 epsilon greedy policy improvement라고 합니다. 아래와
같이 선택할 수 있는 action이 m개 있을 경우에 greedy action(가장 action value function이 높은
action)과 다른 action들을 아래와 같은 확률로 나눠서 선택합니다. 이로서 부족했던 exploration을
할 수 있게 된 것 입니다.

m개의 action 에 대해서 $\epsilon$ 의 확률로 optimum. 이 아닌 선택을 한다.

** value iteration 에 대한 내용은 찾아볼 것

이와 같은 과정을 통해 control 을 수행하게 되고 iteration 을 통해 optimal 에 수렴하게 된다.

** GLIE 에 대한 부분 추가할 것.

TD - Learning

Temporal difference(TD)는 MC와 DP를 섞은 것으로서 MC처럼 raw experience로부터 학습할
수 있지만 DP처럼 time step마다 학습할 수 있는 방법입니다.

마지막에 "bootstrap"이라고 하는데
이 말은 무엇을 뜻할까요? 대학생활을 예로 들어보겠습니다. MC는 대학교에 들어와서 졸업을 한 다음에 그 동안을 돌아보며 "이건 더 했어야했고 술은 덜 마셔야했다"라고 생각하며 다시 대학교를 들어가서 대학생활을 하면서 졸업할 때까지 똑같이 살다가 다시 졸업하고 자신을 돌아보는 반면에 TD같은 경우는 같은 대학교를 다니고 있는 2학년 선배가 1학년선배를 이끌어주는 것을 말합니다.
사실은 둘 다 대학교를 졸업을 해보지 않은 상태에서 (잘 모르는 상황에서)이끌어 주는 것이지만 대
학교를 다니면서 바로 바로 자신을 고쳐나가기 때문에 어쩌면 더 옳은 방법일지도 모릅니다. TD는
따라서 현재의 value function을 계산하는데 앞선(앞선이라고 표현하기에는 좀 애매한 부분이 있지만)주변의 state들의 value function을 사용합니다. 이 것은 이전에 배웠던 Bellman Equantion이며 따라서 Bellman equation자체가 Bootstrap하는 것이라고 볼 수 있습니다.

Prediction

every-visit MC에서는 실제 에피소드가 끝나고 받게되는 보상을 사용해서 value function을 업데이트 하였습니다.

하지만 TD에서는 현재 스탭의 보상과 다음 step에 대한 미래추정가치함수를 사용해서 학습을 하게 됩니다.

이때 사용하는 보상과 value function의 합을 TD target이라고합니다.
그리고 이 TD target과 실제 V(S)와의 차이를 TD error 라고 하고 델타라고 표현을 합니다.

즉 실제 다 reward 를 다 받고나서 return 으로 계산하느냐 아니면 현재받은 reward 를 가지고 앞으로의 rewards 는 estimate 하느냐의 차이입니다.

실제 $G_t$에 대해서 $v_\pi$ 는 unbias 되어 있습니다.

하지만 TD target에 $v_\pi$를 추정하는 $V(S_{t+1})$을 사용하기에 실제값이 아니라 실제값을 추정하는 값임으로 bias가 발생합니다. 그리고 TD target은 단지 하나의 step에서만 계산을 하기에 noise가 작게 되므로 상대적으로 variance가 낮게 나타납니다.

• MC = unbiased, high variance
• TD = biased, small variance

Control

model-free control이 되기 위해서는 action-value function을 사용해야한다고 말했었습니다. 따라서 위 TD(0)의 식에서 value function을 action value function으로 바꾸어주면 Sarsa가 됩니다. Sarsa는 아래 backup diagram에서 따온 이름으로 아래 update식을 보면 현재 state action pair에서 다음 state와 다음 action까지를 보고 update하기 때문에 붙은 이름입니다.

Sarsa는 따라서 TD(0)를 가지고 action-value function으로 바꾸고 $$\epsilon$$-greedy policy improvement를 한 것 입니다.

• on policy control with Sarsa

  

현재의 Q value를 imediate reward와 다음 action의 Q value를 가지고 update합니다.
policy는 따로 정의되지는 않고 이 Q value를 보고 $$\epsilon$$-greedy하게 움직이는 것 자체가 policy입니다.