cdjs의 코딩 공부방

- 본 포스팅은 CS234 4강의 내용을 정리합니다.

 

이번 강의에선,

- Generalized Policy Iteration

- Importance of Exploration

- Monte Carlo Control

- Temporal Difference (TD) Methods for Control

- Maximization Bias

등에 대해 배운다.

 

On-policy learning이란 직접 경험한 내용을 바탕으로 policy를 예측하고, 개선해 나가는 과정이다.

즉, Agent가 직접 행한 내용에 대해서만 학습을 하는 것이다.

 

Off-policy learning은 그와 달리 이미 알고 있는 내용들을 바탕으로 아직 실행하지 않은 내용까지 예측해서 policy를 개선해 나가는 것이다.

가령, 다음과 같은 state와 action에 대한 policy를 생각해보자:

s1, a1, s1, a1

s1, a2, s1, a2

off-policy learning의 경우엔 위의 두 가지 policy를 조합하여

s1, a1, s1, a2

의 policy도 수행할 수 있게 된다.

 

이제 Policy Iteration이 뭔지 다시 한번 불러와 보자.

Policy Iteration이 뭐였느냐 한다면...

우선 Vπ를 계산해 준 다음,

그 값과 Reward model R, dynamics P를 바탕으로 policy를 개선해 나가는 과정이었다.

(자세한 내용은 2강에서 확인하도록 하자.)

 

그런데, Policy Iteration의 경우엔, 정확한 Reward model과 dynamics(~~가 일어날 확률)가 필요했다. 

그래서 저번 강의에서는 model-free policy evaluation에 대해 설명했었는데,

이걸 한번 Policy Iteration에 써먹어 보도록 하자.

 

그래서 나온 것이 Model Free Policy Iteration이다.

아이디어는 그냥 Reward model과 dynamics를 Q function으로 합쳐버려서

Qπ를 계산하고 이 π를 개선해 나가면 되지 않을까? 하는 생각인 것이다.

 

이번엔 Monte Carlo for On Policy Q Evaluation에 대해 알아보자.

이는 저번에 배웠던 Monte Carlo for on policy value evaluation과 매우 유사한데,

원래 value evaluation에서는 N(s), G(s)를 썼지만,

Q Evaluation에서는 N(s, a) 와 G(s, a)를 사용한다.

(사실 어느 정도 당연한 이야기인데... Q는 state뿐만 아니라 action 또한 사용하는 function이기 때문이다.)

즉, 원래는 State만을 사용하던 것에서 벗어나서, State, action 쌍을 사용하는 것이다.

 

 

이 방식으로, Policy Improvement를 더욱 간단히 만들 수 있다.

그냥 Qπ(s, a)의 argmax를 취하면 그게 다음 policy가 되는 것이다.

 

그리고 이 방식을 사용하면 Policy Iteration을 매우 간단하게, 그리고 Model-free하게 만들 수 있다.

하지만, 아직 신경써야 할 부분이 있다. 바로 Qπ를 compute하는 부분이다.

만약 policy가 Deterministic 할 때는 policy 안에 특정 action이 존재하지 않는다면, 그 action에 대한 Q function은 절대로 계산하지 못한다.

(결국엔 Deterministic 하다면 policy에 있는 action만 따라가니깐..)

 

이를 해결하고 model-free한 Qπ를 계산하기 위하여, Exploration을 해야 한다!

 

이 때 사용할 수 있는 방식이 ε-greedy policy라는 것이다.

매우 간단한 아이디어인데,

1 - ε 의 확률로는 그냥 argmax Qπ(s, a)를 따르고,

ε의 확률로는 그냥 action a (랜덤한 action)를 따르는 것이다.

즉, 그냥 대충 확률적으로 딴 길로 샌다는 것이다.

 

그럼 지금까지 배운 내용을 확인해보자. (맨 아래 답이 이미 나와있는 것은 못본 걸로 하자.)

지금 까지의 예제와 비슷하게 Mars Rover의 예제를 사용한다.

그런데, a1의 경우엔 [1 0 0 0 0 0 10]의 reward를, a2의 경우엔 [0 0 0 0 0 0 5]의 reward를 갖는다.

또한, ε = 0.5이고, Trajectory = (s3, a1, 0, s2, a2, 0, s3, a1, 0, s2, a2, 0, s1, a1, 1, terminal) 이다.

이 때, First visit MC on policy Q의 값은 무엇일까?

 

 

간단하게 생각하자.

우선 a1을 취한 경우를 생각하면,

(s3, a1, 0, s2), (s1, a1, 1, terminal)의 두 가지 경우밖에 존재하지 않는다.

그리고, 𝛾=1이므로 지나온 모든 states에 final reward 1을 넣어 Q(-, a1) = [1 0 1 0 0 0 0]이 나오게 된다.

이 때 s2의 경우엔 a1의 action을 취하지 않았기 때문에 0이 들어가게 된다.

 

그럼 a2를 취한 경우도 생각하면,

(s2, a2, 0, s1)밖에 존재하지 않는다. (First-visit이므로 두 번 지나간건 생각하지 않는다. 사실 그거나 그거나 𝛾=1이라..)

그렇다면 위와 비슷하게, Q(-, a2) = [0 1 0 0 0 0 0]이 나오게 된다.

간단하지 않은가?

 

 

위는 ε-greedy Policy Improvement방식을 사용하면, policy는 제자리에 머무르거나 무조건 더 좋은 방향으로 갈 수 밖에 없다는 것을 증명한다.

그냥 공식으로 되어 있으니 딱히 쓸 말이 더 없을 것 같다...

 

여기서 GLIE (Greedy in the Limit of Infinite Exploration)에 대하여 나온다.

GLIE는 Exploration을 효율적으로 만드는 것을 목적으로 한 일종의 전략인데,

간단히 말하면 모든 (s, a)를 무한히 지나고 나면 policy를 greedy하게 만드는 것이다.

 

이에 대한 간단한 예로, ε의 값이 조금씩 줄어드는 ε-greedy를 생각할 수 있다.

가령, ε = 1/i로 두는 것이다.

 

이러면 i가 무한대로 발산하면 ε=0으로 수렴하게 되고, 결국 1-ε가 1로 수렴하게 되어 언제나 greedy한 선택을 하게 된다.

이런 방식을 바로 GLIE하다고 하는 것이다.

(좀 더 간단히 말하자면, 그냥 무한히 exploration을 지나면 greedy해지는 알고리즘을 의미한다.)

 

그리고 다음은 ε-greedy policy를 적용한 Monte Carlo Control 알고리즘의 의사 코드이다.

그냥 쭉쭉 읽어나가면서 이해하면 될 것 같고...

조금 신경쓸 부분만 짚어보자면,

 

2번째 줄. policy 를 ε-greedy(Q)로 initialize하고 있다.

 

6번째 줄. 위에선 First visit이라고만 적혀 있지만, Every-visit을 해도 된다.

 

7번째 줄. 원래 Monte Carlo면 N(s, a)가 아니라 N(s)였겠지만, On Policy Q Improvement 이므로 N(s, a)가 된다.

 

11번째 줄. GLIE하게 만들어 주기 위해서 ε = 1/k로 만들어준다.

 

이제 예제로 한번 알아보도록 하자.

언제나와 같이 Mars Rover의 예시인데,

Q(-, a1) = [1 0 1 0 0 0 0], Q(-, a2) = [0 1 0 0 0 0 0] 일때

optimal policy π(s)는 무엇이고,

k = 3, ε = 1/k 일 때 ε-greedy policy는 무엇일까?

 

 

optimal policy는 argmax Q(s, a)이므로, [a1, a2, a1, tie, tie, tie, tie] 가 된다.

참고 : state s4 이후에는 모두 Q(-, a1), Q(-, a2)의 값이 0으로 같으므로 tie가 된다.
만약 tie가 나온다면 무조건 a1을 고르거나 a2를 고르는 등의 방식도 있고 랜덤으로 하나를 고르는 방식도 있는데, 일반적으로는 랜덤으로 하나를 고르는 방식이 더 효율이 좋다.

 

또한, k=3, ε=1/k라면 ε-greedy policy의 경우

2/3의 확률로는 [a1, a2, a1, tie, tie, tie, tie] 를 따르고,

1/3의 확률로는 그냥 아무데나 갈 것이다.

이번에는 MC 방식이 아닌 TD 방식을 생각해보자.

어떻게 하면 model-free하게 TD방식을 만들 수 있을까?

 

아이디어는 또 단순하다.

TD방식과 ε-greedy 방식을 같이 사용하여 Qπ를 계산한 후에, (Policy evaluation)

π = ε-greedy (Qπ)로 두어 policy를 개선한다. (Policy Improvement)

 

이렇듯 TD methods에 ε-greedy policy를 적용한 것을 SARSA (states action reward states action 라는 뜻ㅎ;;)라고 한다.

간단히 SARSA가 뭔지 설명하자면 현재 state에서 action을 취한 뒤에, 다음 state에서 action을 취하고 나서 policy improvement가 이루어지는 것이다.

다르게 말하자면, 현재 (st, at) 쌍에서의 상태를 관찰한 뒤에, 다음 state st+1 에서의 action at+1을 취하고 나서,

그 뒤에 관찰한 값을 바탕으로 현재 policy π를 update 하는 것이다.

 

 

그 외의 나머지 부분은 MC 방식과 비슷하게 위의 알고리즘을 그냥 읽으면 될 것 같다.

참고로, 7번째 줄에 적혀있는 α는 learning rate이다.

 

이 방법의 장점으로는, 모든 episode를 다 돌지 않아도 금방금방 policy improvement를 진행할 수 있다는 것이다.

그렇기 때문에, 만약 episode 하나하나가 매우 길다면, 이 방식이 매우 효율적이게 될 것이다.

그때 그때 (s, a)쌍만 주어진다면 바로바로 policy improvement가 가능하기 때문이다.

 

이 부분은 조금 이론적인 부분인데,

위의 두 가지를 만족하는 α를 선택하면 SARSA는 무조건 수렴한다는 것인데,

실제 상황에서는 저런 값은 잘 선택하지 않고, 그냥 하나하나 경험적으로 집어넣어 본다고 한다.

(그러니까 그냥 이론적으로 알고만 넘어가라는 뜻 ㅎ)

 

Q-learning은 지금까지 배웠던 SARSA에서 아주 약간만 바꾼 방식이다.

원래 SARSA에서는 다음 state와 action 의 (st+1, at+1)의 쌍을 취해서 

원래 Q(s+1, at+1)였던 것을 max Q(st+1, a')으로 바꾸어 준 것이다.

그러니까, 다음 action을 고를 때 그냥 아무거나 고르는 것이 아니라, Q의 값이 최대가 되는 action을 고른다는 얘기이다.

그리고 Q-learning에도 ε-greedy Exploration을 적용할 수 있다.

사실 SARSA랑 너무 똑같아서 딱히 할 말이 없다.

그냥 중간에 Q(st+1, at+1) 이었던 것이 max Q(st+1, a)가 된 것 뿐이다.

 

그리고 ε-greedy policy를 Q-learning에 적용할 때도, 위의 MC의 경우와 마찬가지로

GLIE함을 만족하여야 optimal Q*와 optimal π*를 구할 수 있다.

 

 

그런데, 원래는 unbias한 Q function을 사용하더라도, max연산을 하면 π의 예측값의 value V는 bias해질 수도 있다.

왜 그러는지는 위에 annotation으로 적혀있는 수식을 확인하면 될 것 같다.

(참고 : 1번째 줄에서 2번째줄로 넘어가는 수식에서 부등식이 생기는 이유 : 옌센 부등식 https://ko.wikipedia.org/wiki/%EC%98%8C%EC%84%BC_%EB%B6%80%EB%93%B1%EC%8B%9D)

 

이를 보완하기 위해서 고안된 방법이 바로 Double Learning이다.

예측치의 최댓값가 실제 값의 최댓값의 예측치로 사용되는 것을 피하기 위해서 고안되었다.

(예측치의 최댓값 <= 실제 값의 최대값의 예측치 이므로)

그래서 Q를 하나를 쓰는게 아니라 두 개 (Q1, Q2)로 나누어 사용한다.

그 중 Q1은 max action a*를 선택하는데 사용하고,

Q2는 a*의 값을 예측하는데 사용한다.

 

이렇게 하면, estimator가 bias해지는 것을 방지할 수 있다.

 

위는 Double Q-Learning의 작동 과정을 간단히 나타낸 것이다.

물론 Double Q-Learning은 Q-Learning보다 메모리 및 연산이 더 많이 필요하게 될 것이다.

 

하지만 특정 상황에서 Double Q-learning은 Q-learning보다 훨씬 더 빠르게 optimal한 값에 수렴할 수 있게 된다.

 

 

후반부는 강의 내에서도 교수님이 그냥 후딱후딱 넘어가는 바람에 나도 설명 후딱후딱 해버렸다.

어째 지금까지 모든 강의가 다 시간이 부족해서 후반부는 빠르게 넘어가는 느낌이다.

아무튼, 다음 CS234 5강에서 보도록 하자.

- 본 포스팅은 CS234 3강의 내용을 정리합니다.

CS234 3강에선, MDP 모델 없이 Policy Evaluation하는 법에 대해 다룬다.

주로 다루는 내용은,

- Dynamic Programming

- Monte Carlo policy evaluation

- Temporal Difference(TD)

등이 있다.

 

저번 시간에 Dynamic Programming으로 Policy π에 대한 Evaluation에 대해 배운 바 있다.

k번째의 horizon에서 정확한 value값을 뽑아낸다고 할 때,

이 k의 값을 Value 값이 ||Vₖπ - Vₖ₋₁π|| < ε 로 수렴할 때 까지 증가시켜

infinite horizon의 value값을 찾아내는 방법이다.

 

이것을 그림으로 조금 더 자세히 알아보도록 하자.

위 그림은 State s에서 특정한 action들을 취하는 것을 트리형 구조로 나타낸 것이다.

State s에서 특정 Action을 취했을 때, 어떠한 state로 가게 되고

그 후에 또 Action을 취한 후 특정한 State로 가게 되고 ... 을 반복하게 된다.

Policy Evaluation에서 원하는 것은, 저 Action을 취했을 때 받는 Reward의 총 합을 얻는 것이다.

(바로 앞의 Action에서뿐만 아니라, 그 뒤에 일어날 것들을 포함한, discounted value를 의미함.)

DP 방식은 이전에 계산해 뒀던 Vₖ₋₁π의 값을 통해 Vₖπ의 값을 구한다.

이 때, DP 방식은 World의 Model인 P(s' | s, a)를 알고 있기 때문에

정확한 Vₖπ의 값을 구할 수 있다. (어떤 Action을 했을 때 어떤 reward가 들어오는지 정확히 알고 있으므로.)

 

 

즉, 여기서 알 수 있는 점은 Dynamic Programming (DP) 방식은 MDP 의 모델인 M을 필요로 한다는 것이다.

이 모델 없이는, DP는 돌아갈 수 없다.

그런데, 만약 dynamics model P 나 reward model R을 모른다면 어떻게 해야 할까?

이제부터, model없이 Policy evaluation을 하는 방법을 알아보도록 하자.

 

Gt와 Vπ(s)는 위의 슬라이드를 참고해서 보도록 하자.

Monte Carlo 방식은 모든 Action에 대한 Value를 평균을 내면 그 state의 value를 알 수 있다는 아이디어로 시작되었다.

만약 한 State에서 도달할 수 있는 길이 유한하다면, 그 길들을 sample을 내서 그 return의 평균을 내는 방법이다.

MDP dynamics / model이 필요하지 않다. (그냥 가능한 경우의 수를 평균낸 것이므로)

또한, DP처럼 bootstrapping (한 구간에서 계속해서 반복하는 것?) 하지 않는다.

그리고 state가 Markov하다는 가정을 하지 않는다.

결국 Monte Carlo 방식은 경험에 의존한 방법이므로, 과거에 Agent가 받았던 reward와 action등에 의해 Value가 결정되기 때문이다.

하지만, episodic MDPs (반복 가능하고 언젠간 끝나는 MDP. 예시 : 게임 Pong)의 경우에만 사용 가능하다.

여기서 episode란, 한 번의 순환을 의미한다. 가령 게임 Pong의 경우, 한번의 게임이 끝나는 것이 하나의 episode이다.

 

First-Visit Monte Carlo란, 처음 방문한 state의 경우에만 V를 update하는 방식이다.

N(s) (state의 방문 횟수)와 G(s)를 모든 s에 대하여 0으로 초기화해 준 다음

episode i를 위처럼 정의하고, (state s1에서 action a1을 하고 reward r1을 받고 s2로 가서 a2를 하고 r2를 받고 ... 언젠가 Terminate되고 끝)

Gi,t를 각각의 reward의 total discounted value라고 할 때,

처음 state를 방문하는 t의 경우에만 Vπ(s)를 update해준다.

가령, 내가 방문한 state가 s1, s1, s2, s2, s2, s3, s3, Terminate 순서라면,

각각 첫번째 s1,s2,s3 (1, 3, 6번째)의 경우에만 작동을 하고, 그 외의 경우에는 그냥 값을 무시하고 지나가게 된다.

(아래 예시가 나온다. 곧...)

 

 

더 자세히 들어가기 전에, Bias, Variance, MSE가 무엇인지 빠르게 알아보도록 하자.

참고로 위 용어들은 통계학 용어들이므로, 이번 포스팅에서는 그 자세한 내용은 생략하겠다.

(참고자료 - 추정량 위키백과 https://ko.wikipedia.org/wiki/%EC%B6%94%EC%A0%95%EB%9F%89)

 

간단하게 이야기하자면,

Bias(편향)는 예측한 값이 얼마나 한쪽으로 치우쳐져 있는가를 의미하고,

Variance(분산)는 예측한 값이 실제 측정치와 얼마나 떨어져 있는가를 의미하고,

MSE(Mean Squared Error)는 그 둘을 조합해놓은 것이다.

 

위 내용들을 갖고 다시 Fist-Visit Monte Carlo로 돌아오자.

Vπ의 estimator θ^은, unbiased(bias가 없는) 실제 [Gt|st = s]의 기댓값이다.

그리고 큰 수의 법칙에 의해서, N(s)가 무한대로 발산하면, 그에 따라 Vπ(s)는 실제 값에 수렴하게 된다.

(참고 : 큰 수의 법칙 https://ko.wikipedia.org/wiki/%ED%81%B0_%EC%88%98%EC%9D%98_%EB%B2%95%EC%B9%99)

 

하지만, 데이터 대비 비효율적이라는 단점이 존재한다.

가령, time step이 10000이 지나가도 똑같은 state만 지났었다면 그 episode에서 얻을 수 있는 정보가 1개밖에 없고

그 값으로만 Vπ를 개선하는 방식인 것이므로, 

각각의 time step에 대한 데이터가 10000개가 들어와도 거기서 쓸만한 정보를 하나밖에 구해오지 못하는 것이다.

 

 

Every-Visit Monte Carlo 는 First-Visit Monte Carlo에서 약간의 변화를 준 방식이다.

이름만 봐도 알겠지만...

First-Visit Monte Carlo 방식은 State를 처음 방문했을 때에만 Vπ를 update해주었지만,

Every-Visit Monte Carlo 방식은 State를 방문할 때 마다 Vπ를 update해준다.

 

이 방식은 biased한 방식인데...

직관적으로 보았을 때, 한 episode에서 state 하나를 딱 한번만 뽑는다면 (First-Visit Monte Carlo의 경우엔)

G(s) = 0 + Gi,t가 되므로, 어떤 경우에서든 G(s)는 독립적인 변수가 될 것이다.

하지만, 만약 한 episode에서 state가 여러번 나온다면, (Every-Visit Monte Carlo의 경우엔)

G(s)는 다른 time t에서의 G(s)와 상관관계가 생기게 된다.

결국, Every-Visit Monte Carlo의 방법은 그 상관관계가 어느 정도 존재하는 것들을 평균을 내게 되는 것이므로,

상관관계가 높은 쪽으로 어느정도 치우쳐지게 될 것이다. (그래서 biased 해진다.)

 

그러나 이 Every-Visit Monte Carlo로 얻는 추정량은 일치 추정량이어서, 데이터를 많이 얻으면 얻을수록

실제 추정치에 수렴하게 된다.

그래서, 이 방식은 First-Visit Monte Carlo에 비해 훨씬 더 낮은 Variance를 갖게 된다.

그리고 경험적으로, 이렇게 나온 값이 거의 확실히 First-Visit Monte Carlo보다 MSE가 낮다. (더 좋다는 뜻이다.)

 

 

또, Incremental Monte Carlo에 대해 생각해 볼수도 있다.

Vπ(s)는 위 ppt의 방식으로 계산하여, 그 다음 ppt의 방식으로 바꿔줄 수 있다.

이 때, α가 1/N(s)라면 every visit Monte Carlo와 아예 동일한 방식이 되고, (Vπ(s) = Gi,t와 같아지므로)

α가 1/N(s)보다 크다면 오래된 data를 잊게 되는, discount factor와 약간 비슷한 느낌이 된다.

 

First-Visit MC 방식과 Every-Visit MC방식을 사용했을 때 V의 예측치를 찾는 문제이다.

저번 시간부터 사용해왔던 Mars rover의 예제를 다시 들고 와서

𝛾=1, R=[1,0,0,0,0,0,10]이라고 하고,

(s3, a1, 0, s2, a1, 0, s2, a1, 0, s1, a1, 1, terminal)의 방식으로 움직인다고 가정할 때,

각각의 state에서 First Visit MC의 V의 예측값은 무엇인가?

또, state s2에서 Every-Visit MC의 V의 예측값은 무엇인가?

 

First-Visit의 경우 각각 첫 번째 s3, s2, s1에서만 Value를 예측하고,

𝛾=1이므로 V(s1) = 1, V(s2) = 1, V(s3) = 1, 그 외 나머지 state에서는 V(s)는 0이 될 것이다.

 

Every-Visit의 경우도 이와 마찬가지이다.

V(s1)=1이고, s2는 두번 나오지만 V(s) = G(s) / N(s) 이므로 2/2 = 1, 즉 V(s2) = 1이 된다.

 

이를 아까 DP처럼 트리형 구조로 나타낸다면,

DP는 맨 위에서만 Bootstrapping을 하던 반면,

MC는 가능한 경우의 수를 샘플을 내어 평균을 내서

그 값을 reward의 예측값으로 사용하게 된다.

Monte Carlo방식의 한계점들은 다음과 같다.

- 일반적으로 variance가 높은 편이다. 이를 줄이기 위해선 많은 데이터가 필요하다.

- episodic setting이 필요하다. episode가 끝나야지만 Vπ(s)가 update되기 때문이다.

 

다음은 MC의 요약본이다.

위의 내용을 잘 숙지하고 넘어갈 수 있도록 하자.

 

 

다음으로 배울 내용은 TD learning이다.

이 방식은 위의 Monte-Carlo 방식과 비슷하게 Model이 필요없다.

또, DP와 같이 Bootstrap 하면서도 MC와 같이 sample을 내기도 하며,

episodic하건 infinite-horizon / non-episodic 하건 사용가능하며,

각각의 (s, a, r, s') (state, action, reward, next_state) 튜플이 지나갈 때 마다 V의 예측값을 업데이트 해 준다.

(각각의 time step마다 update한다는 뜻)

 

저번 시간에 잠깐 했던 벨만 방정식 (Bellman operator)을 다시 가져오자면,

Vπ(s) 는 현재 immediate reward r(s, π(s)) 와 discounted sum의 합이었다.

그리고 every-visit MC에서, Vπ(s) = Vπ(s) + α(Gi,t - Vπ(s)) 라고 정의했었다.

이 때, Gi,t를 계산하기 위해선 episode 하나를 통째로 끝날 때 까지 기다려야 했다.

그런데, 그냥 이 Gi,t를 Bellman operator로 바꾸어서, rt + 𝛾Vπ(st+1)라고 두면 어떨까?

즉, DP와 같이 다음 reward를 계산할 때, 이미 갖고 있는 데이터를 바탕으로 계산하자는 것이다.

 

어렵게 생각할 것 없이, 그냥 저번에 했던 DP의 방식을 조금만 차용했을 뿐이라고 생각하면 된다.

실측값인 Gi,t는 state가 Markov 하다면 Bellman Operator와 동일하게 성립하지 않겠는가?

 

이것을 알고리즘으로 나타내면 다음과 같다.

α값을 input으로 준 뒤에, (내가 선택하면 된다.)

모든 state에 대해 Vπ(s) = 0으로 초기화 한 뒤,

(st, at, rt, st+1) 튜플을 샘플링 하여

이 튜플을 바탕으로, 아까 제안했던 TD 공식을 사용하여

Vπ(st) = Vπ(st) + α(rt + 𝛾Vπ(st+1) - Vπ(st)) 를 그대로 반복하는 것이다.

빠른 이해를 위해, 바로 예제로 들어가보자. 

아까 전과 같이 Mars rover예제로, R = [1 0 0 0 0 0 10]이라고 가정하고

s1이나 s7에 도달하면 그 뒤에 무조건 episode가 terminate 된다고 하자.

이 때, (s3, a1, 0, s2, a1, -, s2, a1, 0, s1, a1, 1, terminal) 의 튜플이 주어질 때, (ppt 오른쪽 위에 쓰여진 대로 수행된다.)

α=1에서의 TD 예측치는 무엇인가?

 

이를 식으로 잠시 나타내어 

Vπ(st) = Vπ(st) + α(rt + 𝛾Vπ(st+1) - Vπ(st))를 위 상황에 대입하면,

α, 𝛾 모두 1이므로

Vπ(st) = Vπ(st) + rt + Vπ(st+1) - Vπ(st)

         = rt + Vπ(st+1)가 된다.

모든 state s에 대해 Vπ(st) = 0으로 초기화 했으므로,

 

Vπ(s3) = rt + Vπ(s2)

-> Vπ(s3) = 0 + 0 = 0

 

Vπ(s2) = rt + Vπ(s1)

-> Vπ(s2) = 0 + 0 = 0

 

Vπ(s1) = rt + Vπ(terminated)

-> Vπ(s1) = 1 + 0 = 1

 

즉, Vπ(s1)=1, 그 외 나머지 state 에서 Vπ(s) = 0이 된다.

 

이것이 TD Learning과 MC의 차이점인데,

MC의 경우 Vπ(s3)를 계산할 때 모든 경로를 끝까지 계산하여, s1에 도달했을 때의 그 값 또한 Vπ(s3)의 값에 넣어두지만,

TD Learning은 그냥 s3에서 s2로 한번 간 순간 이미 Agent가 s3에 있었다는 정보를 바로 버리게 된다.

그렇기 때문에 TD learning은 추후에 s1에 도달하더라도 s3의 값에는 변화를 주지 않는다.

그리고 그렇기 때문에 TD learning은 Monte Carlo와는 다르게 episodic 하지 않아도 되는 것이다.

어차피 끝까지 가지도 않고 바로 앞에서 무슨 일이 벌어지는지만 bootstrapping하여 알아내기 때문이다.

 

+ 위 경우엔, α=1이었기에 아무리 반복해도 딱히 변하지를 않았지만,

α=1이 아닌 경우엔, 지속적으로 반복하면 Vπ(s2), Vπ(s3)의 값들도 조금씩 변화하며

계속 반복하게 되면 일정 값에 수렴하게 될 것이다.

가령, α=2의 경우엔,

Vπ(st) = Vπ(st) + 2 * (rt + Vπ(st+1) - Vπ(st))

         = 2 * (rt + Vπ(st+1)) - Vπ(st) 가 된다.

이 때는 Vπ(st)의 값들이 어떻게 바뀌는지는, 직접 해보며 익히길 바란다.

 

++ 참고로, α=1인 경우의 TD update Vπ(st) = rt + Vπ(st+1)는 TD(0)이라고도 한다!

이를 트리형 구조로 나타내면 다음과 나타낼 수 있다.

TD는 value를 예측하기 위해 st+1을 샘플링 하여 기댓값의 근사값을 찾아내고,

V(st+1)의 예측치를 활용하여 DP와 비슷하게 bootstrapping하여 value를 update한다.

일종의 MC와 DP의 짬뽕 느낌이 확 들지 않는가?

 

그럼, 이제부터 DP, MC, TD의 속성들을 비교해보자.

- model 없이 사용 가능한가?

우선, DP는 무조건 MDP가 필요한 방법이므로 X

MC, TD는 경우의 수를 샘플링 하는 방식으로 진행되므로, model-free하다. O

 

- non-episodic한 경우 사용 가능한가?

MC의 경우 episode 한번이 끝날때 마다 update하는 방식이므로, 무조건 episodic한 경우여야 한다. X

DP, TD의 경우 bootstrapping하여 Vπ(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가 있다고 할 수 있다.

가령 아까 위의 Check your understanding에서, α=2의 경우에 첫 번째 반복에선 Vπ(s1)만 reward가 1이라고 되는 편향이 생긴다.

(다르게 이야기하자면, s3, s2일 경우에 reward가 0이라는 편향값이 생긴다고 보면 될 것 같다. 즉, 정확하지 못하다는 것이다.)

DP의 경우가 제일 특이한데, Vπ(s+1)의 값은 Model을 통해 얻는 정확한 값이므로 Bias가 있다고 하기엔 애매한 감이 있다. NA

 

그리고, MC, TD 등의 알고리즘을 선택할 때 Bias/variance, Data efficiency, Computational efficiency와 같은 점들을 고려해야 한다.

(이 근방 부분은 나중에 더 자세히 다루겠다고 하신다.)

 

이번에 생각할 내용은 Batch (Offline이라고도 한다?) solution에 대한 내용이다.

K개의 finite한 episode가 있을 때, K에서 반복적으로 샘플링을 해서 MC 또는 TD(0)의 방식을 적용할 때,

MC와 TD(0)은 어떻게 수렴할까?

* TD(0)은 α=1일 때의 TD를 의미함.

다음 예시를 보도록 하자.

𝛾=1이라고 가정하자.

오른쪽 위의 노드 그림과 같은 State가 있다.

다음과 같은 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π(st) = rt + 𝛾Vπ(st+1) 였고,

𝛾=1이라고 했으므로 Vπ(st) = rt + Vπ(st+1)이 된다.

즉 Vπ(A) = rt + Vπ(st+1)

            = 0 + Vπ(B)

            = 0 + 3/4

            = 3/4

그러므로 MC를 사용했을 때의 V(A) = 0, TD(0)을 사용했을 때의 V(A) = 3/4라는, 다른 값이 나오게 된다.

 

이것을 통해 MC와 TD가 Batch setting에서 수렴하는 방식의 차이를 알 수 있다.

MC의 경우는 MSE (Mean Squared Error)를 최소화하는 방식으로 수렴하게 되어,

이미 관찰된 return에 대한 오차를 최소화하는 방식이다.

 

TD(0)같은 경우, MDP에 최대한 가깝게 수렴하는데,

가령 P(B|A) = 1이고, r(B) = 3/4, r(A) = 0이므로 V(A) = 3/4라고 예측하는 것이다.

(이는 TD가 Markov structure을 사용하기 때문이다. MC는 Markov structure가 아니기에, MSE만을 최소화한다.)

 

 

 

여기까지 CS234 3강의 내용이었다.

쓰다보니 엄청나게 길게 쓴 것 같다.

여기까지 읽는 사람은 없을 것 같아서 쓰는 말이지만,

통계학 공부를 조금 더 하고 나서 인공지능을 다시 배워야될 것 같은 걱정이 들기 시작한다.

게다가 죄다 영어로 써져 있어서 직역해야 하는건지 수학 용어인지도 모르는 것들이 쑥쑥 나와서

다른 강의보다 더 쓰기 힘들었던 것 같다.

 

아무튼 다음 CS234 4강에서 보도록 하자.

수고링 ㅎ