CS234 3강 Summary
CS234 강의 중 Lecture 3(Model-Free Policy Evaluation)을 듣고 정리해보자
본 포스팅은 Stanford Univ의 CS234:Reinforcement Learning 강의를 듣고 정리한 글입니다.
지난 포스팅 요약(Dynamic Programming)
저번 포스팅에서 Dynamic Programming으로 Policy $\pi$에 대한 Evaluation에 대해 배웠었다.
이는 k번째의 horizon에서 정확한 value값을 뽑아낸다고 할 때, 이 k의 값을 Value 값이 $ \| V_{k} ^{\pi}(s) - V_{k-1} ^{\pi}(s) \| < \epsilon $ ($\epsilon$은 매우 작은 값) 로 수렴할 때 까지 증가시켜 infinite horizon의 value값을 찾아내는 방법이다.
Dynamic Programming 방식은 이전에 계산해 뒀던 $V_{k-1} ^{\pi}(s)$ 의 값을 통해 $V_{k} ^{\pi}(s)$ 의 값을 구한다. 이 때, Dynamic Programming 방식은 World의 Model인 $P(s^{\prime} \vert s,a)$를 알고 있기 때문에 어떤 Action을 했을 때 어떤 reward가 들어오는지 정확히 알 수 있다. 따라서 정확한 $V_{k} ^{\pi}(s)$ 의 값을 구할 수 있다.
여기서 알 수 있는 점은 Dynamic Programming (DP) 방식은 MDP 의 모델인 $M$ 을 필요로 한다는 것이다.
그런데, 만약 dynamics model P 나 reward model R을 모른다면 어떻게 해야 할까 ?
이번 포스팅에서는, model없이 Policy evaluation을 하는 방법을 알아보도록 하자.
혹시 앞으로 배울 MC와 TD(0)의 식이 유도되는 방법을 간결하게 확인하고 싶다면 Stochastic approximation으로 유도하는 MC 와 TD에 잘 설명이 되어 있으니 참고해보도록 하자.
Monte Carlo Policy Evaluation
Monte Carlo Policy Evaluation 방식은 모든 Action에 대한 Value를 평균을 내면 해당 state의 value를 알 수 있다는 아이디어로 시작되었다.
이는 만약 한 State에서 도달할 수 있는 길이 유한하다면, 그 길들을 sampling해서 return의 평균을 내는 방법이다. 따라서 이 방법은 가능한 경우의 수를 평균낸 것이므로 MDP dynamics model P가 필요하지 않다.
또한, Dynamic Programming 처럼 bootstrapping(예측값을 이용해 또다른 값을 에측하는것)하지 않으며, state가 Markov하다는 가정을 하지 않는다.
결국 Monte Carlo 방식은 경험에 의존한 방법이므로, 과거에 Agent가 받았던 reward와 action등에 의해 Value가 결정된다.
하지만 이는 episodic MDPs (반복 가능하고 언젠간 끝나는 MDP 예를 들어 게임 Pong)의 경우에만 사용 가능하다. 여기서 episode란, 한 번의 순환을 의미한다. 가령 게임 Pong의 경우, 한번의 게임이 끝나는 것이 하나의 episode이다.
First-Visit Monte Carlo
하나의 episode를 마치면 episode 동안 진행해왔던 state들 마다 return값이 존재하게 되는데, 이때, 중복 방문에 대한 return값을 처리하는 방식에 따라 First-visit MC와 Every-visit MC로 나누어진다.
First-Visit Monte Carlo란, 처음 방문한 state의 경우에만 V를 update하는 방식이다.
N(s) (state의 방문 횟수)와 G(s)를 모든 s에 대하여 0으로 초기화해 준 다음 episode i를 위의 슬라이드와 같이 정의한다(state $s_{1}$ 에서 action $a_{1}$을 하고 reward $r_{1}$을 받고, state $s_{2}$로 가서 다시 $a_{2}$를 하고 $r_{2}$를 받으며 언젠가는 Terminate(종료) 되는 형식)
$G_{i,t}$를 각각의 reward의 total discounted value라고 할 때, 처음 state를 방문하는 t의 경우에만 $V^{\pi}(s)$를 update해준다.
예를 들어, 내가 방문한 state가 $s_{1} \; s_{1} \;s_{2}\; s_{2}\; s_{2}\; s_{3} \;s_{3}$ Terminate state 순서라고 하면, 각 state의 첫 번째 $s_{1},s_{2},s_{3}$(1,3,6번째 state) 의 경우에만 $V^{\pi}(s)$를 update 하고 , 그 외의 경우에는 그냥 값을 무시하고 지나가게 된다.
또한, $V^{\pi}(s)$ 의 estimator $ (\hat\theta)$ 은, unbiased(bias가 없는) 실제 $[G_{t} \vert s_{t} = s]$ 의 기댓값이다. 그리고 큰 수의 법칙에 의해서, N(s)가 무한대로 발산하면, 그에 따라 $V^{\pi}(s)$ 는 실제 값에 수렴하게 된다.
하지만 First-Visit Monte Carlo는 데이터 대비 비효율적이라는 단점이 존재한다.
Every-Visit Monte Carlo
First-Visit Monte Carlo와 달리 Every-Visit Monte Carlo 방식은 State를 방문할 때 마다 $V^{\pi}(s)$ 를 update해준다.
이러한 Every-Visit Monte Carlo 방식은 biased한 방식이다.
예를 들어, 한 episode에서 state 하나를 딱 한번만 뽑는다면 (First-Visit Monte Carlo의 경우엔) $ G(s) = 0 + G_{i,t}$ 가 되므로, 어떤 경우에서든 G(s)는 독립적인 변수가 될 것이다.
반면에 한 episode에서 state가 여러번 나온다면, (Every-Visit Monte Carlo의 경우엔) G(s)는 다른 time t에서의 G(s)와 상관관계가 생기게 된다.
결국, Every-Visit Monte Carlo의 방법은 그 상관관계가 어느 정도 존재하는 것들을 평균을 내게 되는 것이므로, 상관관계가 높은 쪽으로 어느정도 치우쳐지게 될 것이다. (그래서 biased 해진다.)
그러나 이 Every-Visit Monte Carlo로 얻는 추정량은 일치 추정량이어서, 데이터를 많이 얻으면 얻을수록 실제 추정치에 수렴하게 된다. 따라서 그래서, Every-Visit Monte Carlo 방식은 First-Visit Monte Carlo 방식에 비해 훨씬 더 낮은 Variance를 갖게 된다.
Incremental Monte Carlo
$V^{\pi}(s)$ 는 위 슬라이드에서의 방식으로 계산하며, $\alpha$ 가 1/N(s)라면 every visit Monte Carlo와 아예 동일한 방식이 되고, $\alpha$ 가1/N(s)보다 크다면 오래된 data를 잊게 되는, discount factor와 약간 비슷한 느낌이 된다.
Example
위 예제는 First-Visit MC 방식과 Every-Visit MC방식을 사용했을 때 V의 예측치를 찾는 문제이다.
First-Visit의 경우 실제로 방문한 state만 update하고, 각각 첫 번째 $ s_{3}, s_{2}, s_{1}$ 에서만 Value를 예측하고, $\gamma = 1$ 이므로 $V(s_{1}) = 1$,$V(s_{2}) = 1$,$V(s_{3}) = 1$ 이 되고, 그 외에 나머지 즉, $V(s_{4}) = 0$,$V(s_{5}) = 0$,$V(s_{6}) = 0$,$V(s_{7}) = 0$ 이 될 것이다.
Every-Visit 의 경우 $s_{2}$는 2번 나오지만 $V^{\pi}(s) = G(s)/N(s) $ 에서 2/2 = 1 이므로 $V(s_{2}) = 1$이 된다.
Monte Carlo 방식의 한계점
Monte Carlo방식의 한계점들은 다음과 같다.
-
일반적으로 variance가 높은 편이다. 이를 줄이기 위해선 많은 데이터가 필요하다.
-
episodic setting이 필요하다. episode가 끝나야지만 $V^{\pi}(s)$가 update되기 때문이다.
Temporal Difference Learning
다음으로 배울 내용은 TD(Temporal Difference) Learning이다.
이 방식은 위의 Monte-Carlo 방식과 비슷하게 Model이 필요없다.
또한 TD(Temporal Difference) Learning 방식은 Dynamic Programming 방식과 같이 Bootstrap 하면서도 Monte Carlo 방식과 같이 sample을 내기도 하며, episodic하건 infinite-horizon / non-episodic 하건 사용 가능하며, 각각의 $(s,a,r,s^{\prime})$ (state, action, reward, next state) 튜플이 지나갈 때 마다 $V$의 예측값을 업데이트 해 준다. 다시 말해서 각각의 time step마다 $V$의 예측값을 update한다.
저번 시간에 잠깐 했던 벨만 방정식 (Bellman operator)을 다시 가져오자면, $V^{\pi}(s)$는 현재 immediate reward r(s, π(s)) 와 discounted sum의 합이었다.
그리고 every-visit MC에서, $V^{\pi}(s) = V^{\pi}(s) + \alpha(G_{i,t} - V^{\pi}(s))$ 라고 정의했었다. 이 때, $G_{i,t}$를 계산하기 위해선 episode 하나가 끝날 때 까지 기다려야 했다.
TD Learning은 Dynamic Progamming 방식과 같이 다음 reward를 계산할 때, 이미 갖고 있는 데이터를 바탕으로 계산하기 위해 every-visit MC 에서의 $G_{i,t}$ 를 Bellman operator로 바꾸어서, $r_{t} + \gamma V^{\pi}(s_{t+1})$라고 두었다.
이는 만약 state가 Markov 하다면, 실제 측정 reward 값인 $G_{i,t}$가 Bellman Operator와 동일하게 성립할 것이라는 생각으로부터 나온 것이다.
Example
Mars rover예제로, R = [1 0 0 0 0 0 10]이라고 가정하고 $s_{1}$이나 $s_{7}$ 에 도달하면 그 뒤에 무조건 episode가 terminate 된다고 생각해보자.
이 때, 위 그림과 같은 튜플(Trajectory)이 주어질 때, $\alpha = 1$ 에서의 TD 예측치는 무엇일까 ?
우선, $\alpha$ 와 $\gamma$는 모두 1이므로 $V^{\pi}(s) = r_{t} + V^{\pi}(s_{t+1})$ 가 된다. 또한 모든 state s에 대해 $V^{\pi}(s) = 0$ 으로 초기화 했으므로,
$V(s_{3})$ = 0($s_{3}$에서 보상이 0이므로) + 0(첫 $V^{\pi}(s_{2})$의 경우, 모든 state s에대해 0으로 초기화 했으므로) = 0, $V(s_{2})$ = 0($s_{2}$에서 보상이 0이므로) + 0(첫 $V^{\pi}(s_{1})$의 경우, 모든 state s에대해 0으로 초기화 했으므로) = 0, $V(s_{1})$ = 1($s_{1}$에서 보상이 1이므로) + 0(Terminate 됨) = 1 이다.
이것이 TD Learning과 MC의 차이점이다.
MC의 경우 $V^{\pi}(s_{3})$ 를 계산할 때 모든 경로를 끝까지 계산하여 $s_{1}$ 에 도달했을 때의 값 또한 $V^{\pi}(s_{3})$ 의 값에 넣는다.
반면 TD Learning은 $s_{3}$에서 $s_{2}$로 가면(다음 state로 이동하면) Agent가 $s_{3}$ 있었다는 정보를 바로 버리게 된다. 따라서 TD learning은 추후에 $s_{1}$에 도달하더라도 $s_{3}$의 값에는 변화를 주지 않는다.
즉, TD learning은 Monte Carlo와는 다르게 끝까지 가지도 않고 바로 앞에서 무슨 일이 벌어지는지만 bootstrapping하여 알아내기 때문에 episodic 하지 않아도 되는 것이다. (time step 별로 update한다는 소리다.)
참고로, 바로 앞선 step 만을 보고 Value Function을 업데이트 하는 TD update는 TD(0)라고 한다. (n개의 step을 보면, TD(n)이며, Episode가 Terminate 해질 때 까지의 state까지 가져간다면 MC와 동일해진다.)
DP, MC, TD의 차이
그럼, 이제부터 DP, MC, TD의 속성들을 비교해보자.
- model 없이 사용 가능한가?
우선, DP는 무조건 MDP가 필요한 방법이므로 X이고, MC, TD는 경우의 수를 샘플링 하는 방식으로 진행되므로, model-free하다. O
- non-episodic한 경우 사용 가능한가?
MC의 경우 episode 한번이 끝날때 마다 update하는 방식이므로, 무조건 episodic한 경우여야 한다. X
DP, TD의 경우 bootstrapping하여 $V^{\pi}(s)$를 얻어내는 방식이므로, non-episodic / infinite episodic의 경우도 가능하다. O
- Non-Markovian할 때 사용 가능한가?
MC의 경우 그저 가능한 경우의 수를 나열하는 것이므로, Markovian하건 안하건 그냥 평균만 내면 되는 방식이다. O
DP, TD의 경우 state가 Markov하다는 전제 하에 bootstrapping을 하는 것이므로, state는 Markovian 해야 한다. X
- 극한값에서 실제 값에 수렴하는가?
DP, TD는 bootstrapping을 하면 할수록 수렴하고, MC의 경우도 episode를 무수히 반복하다 보면 큰 수의 법칙에 의해 수렴한다. O
- unbiased한가?
MC의 경우, First-Visit MC는 unbiased 하지만, Every-Visit MC는 biased하다. O
TD의 경우, bias가 있다고 할 수 있다.
DP의 경우, $V^{\pi}(s_{t+1})$의 값은 Model을 통해 얻는 정확한 값이므로 Bias가 있다고 하기엔 애매한 감이 있다.
간단한 차이는 위 그림을 통해 확인하자.
Batch MC and TD
MC, TD 방식 모두 에피소드를 무한하게 반복하게 되면 결국 실제 value 에 수렴하게 된다.
그런데 Batch 방식으로 에피소드를 일부만 가지고 계속적으로 학습을 시킨다고 하면 어떻게 될까 ? 다시 말해서, K개의 finite한 episode가 있을 때, K에서 반복적으로 샘플링을 해서 MC 또는 TD(0)의 방식을 적용할 때, MC와 TD(0)은 어떻게 수렴할까?
$\gamma = 1$이라고 가정했을 때, 위와 같이 8개의 에피소드가 존재한다.
A, 0, B, 0
B, 1 (6번 반복)
B, 0
(이 때, A,B는 state, 0,1은 reward를 의미한다.)
이 때, MC와 TD(0)방식의 V(A), V(B)는 어떻게 수렴할까 ?
우선 V(B)부터 보도록 하자.
MC를 사용하면, 결국 B는 8번의 episode가 존재하고 그중 6개의 episode에서 1의 reward를 받았으므로, V(B) = 6/8 = 3/4가 될 것이다. (무한히 많이 반복하면 이렇게 수렴하게 된다는 뜻이다.)
TD(0)를 사용하더라도 결국 sampling 후 무한정 bootstrapping하다 보면, 6/8 = 3/4로 수렴하게 될 것이다.
하지만, V(A)의 경우는 조금 다르다.
MC를 사용하게 되면, A는 언제나 A, 0, B, 0으로 갔으므로, V(A) = 0이다. (이 episode 들 중 A에서 출발하는 경로는 단 하나이고, 언제나 0의 reward를 뽑아냈기 때문이다.)
하지만 TD(0)를 사용하면 이야기가 다르다. TD(0)에서 사용했던 공식 $V^{\pi}(s_{t}) = r_{t} + \gamma V^{\pi}(s_{t+1})$ 을 이용하면 $\gamma = 1$이므로
\[V^{\pi}(A) = r_{t} + V^{\pi}(B)\]에서 $V^{\pi}(B)$ = 3/4이므로 $ V^{\pi}(A)$ = 3/4 가 되게 된다. 따라서 MC를 사용했을 때의 V(A)의 값과 다른 값이 도출되는 것을 알 수 있다.
이것을 통해 MC와 TD가 Batch setting에서 수렴하는 방식의 차이를 알 수 있다.
MC의 경우는 MSE (Mean Squared Error)를 최소화하는 방식 즉, 예측값이 얼마나 치우쳤는지(Bias)와 예측값이 실제값과 얼마나 떨어져 있는지(Variance)가 최소화 하는 방식으로 수렴하게 되어, 이미 관찰된 return에 대한 오차를 최소화하는 방식이다.
TD(0)같은 경우, MDP에 최대한 가깝게 수렴한다. 예를 들어, $P(B \vert A)$ =1이고, $r(B)$= 3/4, $r(A)$ =0이므로 $V(A) = 3/4$라고 예측하는 것이다.
각 방식(DP,MC,TD)의 backup 도식화
Dynamic Programming(DP)
Dynamic Programming 방식의 backup을 도식화하면 위와 같다.
DP 방식에서는 모델을 통해서 이미 모든 MDP를 알고 있고, 이에 대한 value와 reward를 통해서 학습을 하기 때문에 위와 같이 모든 것을 고려해서 학습한다.
Monte Carlo(MC)
Monte Carlo 방식의 backup을 도식화하면 위와 같다.
MC 방식에서는 경험한 에피소드에 대한 업데이트가 일어난다. 즉, 한 에피소드 전체를 고려해서 reward값을 계산하기에 전체 Trajectory가 중요하다.
Temporal Difference(TD)
Temporal Difference 방식의 backup을 도식화하면 위와 같다.
TD 방식에서는 각 time step 별로 업데이트가 일어나게 된다.
이번 포스팅은 조금 길었지만 RL에서 꽤나 중요한 내용인 것 같으니 잘 숙지하도록 하자.
댓글남기기