cdjs의 코딩 공부방

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

참고로, 8~10강까지의 내용은 비슷한 내용을 주제로 연강을 하게 됩니다.

이번 시간에는 Policy Search, Policy Gradient에 대해 배워보도록 하겠다.

저번 시간에, 우리는 파라미터 θ에 대해 (w에 대해) value값 및 action-value (Q)을 찾는 방법을 배웠다.

그래서, 그렇게 생성된 value값을 사용하여 직접 policy를 만드는 방식을 사용했다.

(ε-greedy 방식을 사용해서 최대의 value값을 가지는, 또는 랜덤한 policy를 찾는 방법을 사용했던 것을 생각해보자.)

그런데 이번 시간에는, 우리는 policy πθ를 직접 파라미터로 사용할 것이다.

즉, value 값에서 policy를 찾는 것이 아니라, θ (또는 w)의 값을 토대로 policy를 직접 얻을 것이다.

또, 지금까지와 비슷하게 model에 대한 접근 없이, model-free한 RL을 진행하게 될 것이다.

들어가기에 앞서, 사실 reinforcement learning도 policy를 기반으로 할지, value를 기반으로 할지 등에서 조금씩 나뉜다.

Value-Based라고 한다면, ε-greedy와 같은 형식으로 policy를 도출하게 되고,

Policy-Based라면 Value function 없이 직접 policy를 배우게 된다.

Actor-Critic은 그 사이에 있는 놈들인데, 나중에 다루게 될 것이니 일단 넘기도록 하자.

Policy-Based RL이 가지는 장점과 단점들에 대해 살펴보자.

우선, 장점들을 먼저 살펴보자면, Parametrization을 통해 policy를 나타내는 것이 더욱 효율적일 때가 있다. (사실 상황에 따라 다르긴 하다.)

또, high-dimensional / continuous action space의 경우 action-value pair을 사용하는 것 보다 훨씩 효율적이며,

stochastic policy, 즉 무작위적 policy를 가질 수 있게 된다.

value function을 바탕으로 policy를 짜면, 보통 최대의 value값을 갖는 policy를 선택하는데, 이는 stochastic한 policy를 얻지 못하게 막는다.

그런데 왜 stochastic policy가 필요한지는 후술하도록 하겠다.

단점들도 있는데, 우선 대부분의 policy-based RL은 global optima에 수렴하지 않고, local optima에 수렴하는 경우가 많다.

또, 일반적으로 policy를 계산하는 것은 sample inefficient 하다. (sample의 갯수가 많아야 한다는 뜻)

그런데, 아까 전에 stochastic policy를 학습할 수 있는 것이 장점이라고 했는데, 왜 stochastic policy가 필요할까?

가장 간단한 예시로, 가위바위보를 하는 Agent를 만든다고 생각해보도록 하자.

만약 모든 policy가 deterministic 하다면 어떨까?

예를 들어, 처음에는 바위를 내고, 전판에 상대가 보를 냈으면 다음판엔 가위를 내고, ... 하는 식으로 학습되었다고 해보자.

그렇게 학습을 끝낸 후 사람과 가위바위보를 시키면 잘 해낼 수 있을까?

가위바위보를 한판만 하는 거면 모르겠지만, 여러 판 하다 보면 결국 사람이 이게 어떤 메커니즘으로 흘러가는지 알게 되고, 그냥 처음에 보를 내고, 그 다음에 주먹을 내고, ... 하는 식으로 간파가 가능하다.

즉, 가장 최적의 policy는 사실, 가위바위보 셋 중 하나를 랜덤으로 내는 것이다.

아직 잘 와닿지 않는다면, 다음 예시를 통해 조금 더 와닿게 해 보겠다.

위와 같은 grid world가 있다고 하자.

당연히 저기 있는 돈꾸러미가 goal이고, 해골 무늬에 들어가면 죽게 된다.

(해골이나 돈꾸러미에서 시작하는 일은 없다고 가정한다.)

Agent는 동서남북 네 방향만을 관찰할 수 있어서, 동서남북의 칸에 벽이 있나 없나만을 알 수 있다.

또, 자신이 하얀 블럭 위에 있는지 회색 블럭 위에 있는지도 알 수 없다.

자, 이에 따라 돈꾸러미에 들어가는 policy를 짠다면 어떻게 될까?

우선, 하얀색의 블럭 세 개에서의 policy는 자명하게 구할 수 있다.

왼쪽 흰 블럭의 policy를 생각하면 : 왼쪽과 위쪽에 블럭이 있고, 아래쪽에 블럭이 없으면 오른쪽으로 간다! 가 될 것이고,

오른쪽 흰 블럭의 policy를 생각하면 : 오른쪽과 위쪽에 블럭이 있고, 아래쪽에 블럭이 없으면 왼쪽으로 간다! 가 될 것이다.

또, 가운데 흰 블럭은 : 위에만 블럭이 있으니, 아래로 간다! 가 policy가 될 것이다.

이렇게 하면 흰 블럭 위에 있을 때는 최적의 policy가 된다.

문제는 회색 블럭에 있을 때이다.

저 두 블럭에서는 사실 들어오는 feature가 동일하다. "아래, 위에 블럭이 있고, 왼쪽, 오른쪽은 비어 있다" 라는 feature이다.

하지만 저 feature에 대해 어떤 한 가지의 policy를 정할 수 있을까?

만약 "왼쪽으로 간다"라는 policy를 정한다면, 왼쪽 위 흰 블럭 또는 회색 블럭에서 시작하는 경우에는, 영원히 goal에 도달하지 못하게 될 것이다.

반대로 "오른쪽으로 간다"라는 policy를 정한다면, 오른쪽 위 흰 블럭 또는 회색 블럭에서 시작하는 경우에 goal에 영원히 도달하지 못한다.

하지만 Value-based learning같은 경우에는 거의 greedy한 방식으로, deterministic한 policy를 정하게 된다.

이렇게 deterministic한 policy를 정하는 경우, 이처럼 갇히게 되는 경우가 발생하여 좋지 못한 policy가 되고 만다.

그렇다면, 위의 회색 블럭의 policy를 "50% 확률로 왼쪽으로, 50%확률로 오른쪽으로 간다" 라고 잡으면 어떻게 될까?

어디서 시작하더라도, 충분한 시간 뒤에는 결국 goal에 도착하는 이상적인 policy가 완성되게 된다.

이것이 바로 stochastic policy가 필요한 이유이고, 이것이 바로 Value-Based RL이 아닌 Policy-Based RL이 필요한 이유이다.

Value-Based RL같은 경우 위와 같은 Stochastic Policy를 학습하지 못하지만,

Policy-Based RL은 저런 optimal stochastic policy도 할습할 수 있기 때문이다.

이제 본격적으로 policy based RL을 시작해 보도록 하자.

우리의 목표는 최고의 파라미터 θ를 찾아서 parametrized πθ를 찾는 것이다.

그런데, πθ가 얼마나 좋은지 어떻게 알 수 있을까?

우선 episodic environments (H steps 또는 terminal까지)의 경우, J(θ)를 start state의 Value값으로 둘 수 있다.

그리고 continuing environments 같은 경우, πθ의 평균값을 사용하거나, time-step당 reward의 평균을 사용한다.

오늘은 대부분 episodic 한 경우만 다루겠지만, 손쉽게 continuing / infinite horizon인 경우로 연장시킬 수 있다.

그리고 알아둘 점이 하나 있는데, 바로 policy based RL은 "optimization" 문제라는 것이다.

즉, 최대의 Vπθ를 갖는 parameter θ를 구해야 한다는 것이다.

물론 gradient-free한 방식도 사용할 수는 있다. (위 ppt에 나열된 방법)

하지만, 요즘에는 일반적으로 gradient를 사용하는 방식을 자주 사용한다. (강의명도 policy gradient다!)

Gradient-Free 방식을 사용한 예시 중 하나가 바로 위 예시이다.

사람이 걷기 편하게 보조하는 기계를 학습시키는 것인데, 자세한 내용은 다음 유튜브를 참고하기 바란다.

https://www.youtube.com/watch?v=Dkp_xjbRYCo

그리고, 사실 Gradient Free한 방식은 꽤나 잘 먹힌다. 그래서 간단한 baseline으로 자주 사용된다.

어떠한 policy parameterization을 대상으로도 잘 먹히고, 심지어는 미분 불가능한 경우에도 잘 작동하는 방식이다.

또, 병렬화 작업도 매우 쉽게 된다.

하지만, 치명적인 단점이 있는데, 바로 sample-efficient 하지 못하다는 것이다.

즉, 학습하는 데 매우 많은 데이터가 필요하다.

그러니까 Gradient-Free 방식은 이제 저기로 제쳐두고, policy gradient 방식에 대해 알아보자.

그렇다면 Policy Gradient가 그래서 어떻게 작동하는지 설명해보겠다.

우선 V(θ) = Vπθ로 둔다. 그리고 아까 말했다시피, 오늘은 episodic MDP의 경우만을 생각하자.

그러면 Policy Gradient 알고리즘을 사용하여 V(θ)의 local maximum을 찾을 수 있다. (Gradient Descent 사용)

그렇게 θ에 대한 V(θ)의 local maximum을 찾을 때 사용되는 식은 위 ppt에서 볼 수 있다.

이 떄, 언제나 그래왔듯 α는 learning rate이다.

그래서 이제 Gradient 계산을 해야 하는데...

필자는 아직 고등학생인지라 수학에 대해 아직 좀 많이 무지하다.

Finite Difference가 뭔뜻인지 (한정된 차이?는 아니지 않겠는가;;) 인터넷에 검색해 보니까, "유한 차분법" 이라는 방법이라고 한다.

그래서 이번 슬라이드는 완벽하게 이해하지 못했다.

그래도 이해한 것이라도 끄적여보자면,

우선 닫힌 공간 [1, n]의 있는 모든 k에 대하여, θ에 대한 k의 편미분을 계산한다.

그리고 그 편미분 값을 조금 바꿔서(약간 증가시키거나 감소시킨다는 얘기인가?) 실제 미분값에 근사시킨다.

그 뒤, n dimension을 따라 n번 evaluate해서 policy gradient를 계산한다.

이 방식은 간단(??)하지만, 약간 노이즈가 있고 inefficient한 방식이다. 하지만, 가끔 효율적으로 사용되는데,

미분 불가능한 policy를 포함해 어떠한 policy에도 작동할 수 있기 때문이다.

이 방식을 사용하여, 로봇 AIBO를 걷게 시킨 실험도 있다. (2004년)

어떻게 parameterization을 했는가 보니,

state를 두지 않고, 위 슬라이드에 나온 대로 parameterization을 진행하여, 각각의 파라미터에서 랜덤으로 -ε, 0, ε 셋 중 하나를 더해 policy를 얻었다고 한다.
 

 그런데 위에서 이거 2004년에 했다고 했는데, 이걸 어떻게 computational effecient 하게 진행했냐면,

우선 로봇 3개를 한번에 구동한다.

그리고 각각 iteration마다 policy 15개를 evaluate한다.

그리고, 각각의 policy도 3번씩 evaluate하고 (noise를 줄이려고) 그것의 평균을 구한다.

이렇게 했더니, 각 iteration이 7.5분 안에 끝났다고 한다.

그렇게 traning 시켰더니, 꽤 잘 하는 모습을 보여줬다고 한다.

그리고 이 AIBO의 성능은 초기 starting policy parameter, ε (더하고 빼지던 정도), α (learning rate), 그리고 policy parameterization 등이 영향을 미쳤다고 한다.

그리고, 이번에는 방금의 Finite Difference 방식이 아니라 그냥 analytical 하게 gradient를 구하는 방법을 알아보자.

당연하게도, 이 방식을 사용하려면 policy πθ가 미분 가능해야 하고, gradient를 알고있다고 가정해야 한다.

(즉, 이것 자체가 연산 가능하다는 것을 알고 있어야 한다는 것이다.)

그리고 이 방식을 사용할 때는, likelihood ratio policy라는 것을 사용한다.

우선, 이 방식은 Episodic 한 방식에서만 사용되며, 예전부터 해왔듯이 trajectory를 설정한다.

(당연히 episodic이므로 마지막에 Terminal이 있어야 한다.)

그리고, Reward function R은 그냥 trajectory의 reward값의 평균이다.

또한, 이렇게 두면 Policy value는 해당 policy를 따랐을 때의 Reward값의 평균이 되는데, 이를 다시 쓰면 해당 episode에서, 즉 trajectory를 따라갈 때 얻는 Reward R과 확률 P의 곱의 평균이다.

(policy에서 확률이 왜 나오냐 할 수도 있겠지만, 이제는 이것이 deterministic하지 않는다는 것을 알아야 한다!)

그리고, 이제부터 나오는 대부분의 수식들에는 Reward Function이 그대로 쓰이기 보단, 위의 형태와 같이 Probability P와 R의 곱 형태로 나오게 될 것이다.

그리고 이 상태에서, 위 V(θ)의 Policy Gradient를 구하면 (θ에 대해 Gradient한다), 위와 같게 된다.

딱히 설명할 필요는 없겠지만 대충이라도 설명을 해 보자면,

첫 번째 줄에는 그냥 양변에 gradient를 씌워 준 것이고, (이 표현이 맞는지는 모르겠지만... 뭔뜻인지 알겠지??)

어차피 θ를 인수로 갖는 것은 P(𝛾;θ) 뿐이니 저 시그마 안으로 들어가 준 다음에,

P(𝛾;θ)/P(𝛾;θ) 를 곱해준다. (1을 곱한 것과 같다.)

그리고, P(𝛾;θ)를 분수 아래로, ∇θP(𝛾;θ)를 분수 위로 올리면, P(𝛾;θ)R(𝛾) * ∇θP(𝛾;θ)/P(𝛾;θ)가 된다.

그런데, ∇θlog(P(𝛾;θ)) 는 1/P(𝛾;θ) * ∇θP(𝛾;θ)라고 한다.(왠지는 필자도 잘 모르겠다 ㅠㅠㅠ)

그래서 이를 정리하면, 맨 아래 식이 나온다.

이 식을 사용하는 이유는, policy를 사용하여 trajectory 몇 개를 sampling 한 뒤에, reward를 조금 구하면서 Gradient를 구할 수 있기 때문이다.

즉, 어떻게 Gradient를 구해야 할지에 대한 방법을 얻게 된 것이다.

어떻게 Gradient를 구하는지 조금만 더 자세히 보자면,

우리의 목적은 policy parameters θ를 찾는 것이므로,

θ에 대해 Gradient를 아까 위에서 한 것처럼 구한 뒤에,

그 값을 그냥 policy 몇 번 돌려서 구한 값과 유사한 값으로 맞춰주면 되는 것이다.

...그런데 우리가 지금 뭘 하고 있는걸까?

그냥 일반적으로 Gradient Descent를 사용하는 다른 알고리즘을 생각하면 편하다.

우리는 지금, Gradient를 구하는 방법을 알게 되었다.

그런데 우리의 trajectory는 Policy Parameter θ에 따라 달라지지 않겠는가!

그러므로, 현재 parameter가 가지는 reward값이 가장 커지도록 parameter값을 바꿔준다고 생각하면 된다.

조금 더 자세히 하자면, 그 sample이 얼마나 좋은지에 비례해서 그 sample이 나오게 만드는 확률을 높여주는 방향으로 진행된다.

현재 trajectory의 state에서 앞으로 가는 것이 가장 reward가 높은 행동이라면, 앞으로 가는 확률(로그가 씌워져 있긴 하지만)을 높이는 방향으로 parameter를 움직인다.

조금 더 직관적으로, 위 그래프를 보자.

f(x)는 Reward Function이고, P(x)는 trajectory이다.

그래서, 좋은 reward를 갖는 trajectory를 갖게 parameter를 조정하게 된다. (위 예시에서는, 아마 가장 오른쪽의 값이 가장 reward가 높은이다.)

그냥 이게 다다. 매우 직관적이지 않은가?

이제 우리가 할 것은, 위 Trajectory를 State와 Action에 대한 식으로 풀어 쓰는 것이다.

일단 위 식에서 Trajectory를 갖는 ∇θlogP(𝛾⁽i⁾;θ) 를 보면, parameter θ를 가질 때, i번째 trajectory의 Log Probaility의 미분값이다.

그런 일단, P(𝛾⁽i⁾;θ) 이 부분만 위의 식 μ(s₀)𝚷πθ(at|st)P(st+1|st, at) 라고 나타낼 수 있다.

왠지 대충만 설명하자면, 결국 P(𝛾⁽i⁾;θ)의 의미는 i번째 trajectory의 Prob을 의미하는데,

현재 policy에서 state가 주어졌을 때 action이 나올 확률에 dynamics model P를 곱해준 뒤에, initial state distribution까지 곱해주면, 결국 같은 것을 의미하는 식이 되는 것이다.

그리고 로그를 다시 안쪽으로 넣어주면, product pi 는 sigma가 되어 이와 같이 쓰일 수 있고,

그런데 이를 또다시 θ에 대해 미분해 주면, 신비로운 일이 잇어난다.

우선 왼쪽의 logμ(s₀)는 θ와 독립적이므로, θ에 대한 편미분을 하면 0이 된다.

오른쪽의 P(st+1|st, at) 또한 θ와 독립적이므로, θ에 대한 편미분값은 0이다.

그러면 결국엔 θ를 갖는 식 하나, 가운데 log(πθ(at|st))만 θ에 대해 편미분해주면 되는, 간단한 현상이 일어난다.

그래서 결국 마지막 식이 도출되게 된다.

근데 우리가 왜 이 짓을 했을까?

첫 번째 식과 마지막 결과식을 비교해 보자.

첫 번째 식에는 trajectory가 포함되어 있으므로, dynamics model이 무조건 필요하게 된다.

그런데, 이렇게 trajectory를 state와 action에 대한 식으로 바꿔 주니, dynamics model이 더 이상 필요하지 않다.

그냥 단순한 policy의 logprob값의 편미분값으로만 위 식이 표현이 되는 것이다!

그리고 우리는 위 식을, Score Function이라고 부르게 된다.

이제 지금까지 나온 내용을 다시 뭉쳐보자면 위와 같다.

우리는 좋은 parameter θ를 찾고자 한 것이다.

그리고, V(θ)의 편미분값은 사실 위 (1/m)Σ(i=1 ~ m)R(𝛾(i))∇θlog(P(𝛾(i); θ))이다.

또, 아까 전에 저 P(𝛾(i); θ)을 풀어 쓴 대로 써보면, (1/m)Σ(i=1 ~ m)R(𝛾(i))∇θlog(πθ(at|st))가 된다! 

위 식을 조금만 풀어서 쓰자면, trajectory를 m번씩 돌 때, 각각의 trajectory에서 나온 Reward값의 평균에다가,

∇θlog(πθ(at|st))를 곱한 식이 된다.

즉, ∇θlog(πθ(at|st))를 score function으로 갖는 함수가 완성된다. (reward에다가 저 값들만 곱하면 Value값이므로)

또한, 이것도 마찬가지로 dynamics model이 필요없는, 매우 간결한 식이 된다.

그리고, 이 Policy Gradient Theorm은 뒤 식을 약간 일반화 시킨 식이다.

policy objective function J를 J1(episodic reward), JavR(time step당 평균 reward), 1/1-𝛾 * JavV(평균 value)라고 한다면

다음과 같은 식이 써진다. (위 ppt 참조 ㅎㅎ)

그런데, 위와 같은 식은 unbiased하긴 하지만 매우 noisy하다.

대충 딱 보면 monte Carlo 방식이 떠오르지 않는가?

사실상 trajectory의 episodic reward라던지, trajectory의 평균 reward를 갖고 계산한다는 점이 말이다.

그래서, 이러한, 매우 noisy하다는 문제점을 해결하기 위해 여러 가지 방법을 사용한다.

오늘은, Temporal structure과 Baseline에 대해 알아보고, 다음 시간에 추가적인 테크닉들을 설명하겠다.

우선, Temporal Structure는, 말 그대로 우리 model에게 "지금 우리가 하고 있는 것은 temporal 한, 즉 시간적 구조가 나타나는 일이란다" 하고 알려주는 것이다.

이것을 하기 위해서, 위와 같은 공식들이 유도된다.

한번 쭉 읽어보면 딱히 필자가 유도하지 않더라도 어느 정도는 다 이해할 것이라 믿고 넘기겠다.

...사실 필자가 이해하지를 못하겠다 ㅠㅠㅠ

혹시라도 필자를 이해시켜줄 수 있는 용자가 있다면, 댓글로 조언 부탁바란다 ㅠ

(사실 이 강의 설명이 이렇게까지 늦은 이유도, 수식들 하나하나 다 이해하면서 넘어가느라 그랬는데, 여기서부턴 도저시 모르겠다 ㅠㅠ)

다만, 마지막 줄에서 logπθ(at, st)는 logπθ(at|st)의 오타인 것 같다.

위 내용들은 나--중에, 필자가 저 수식들을 이해할 정도의 실력이 되면 그때 다시한번 도전해 보도록 하고,

다음 시간엔 Policy search에 대한 더 많은 이야기들을 해 보도록 하겠다.

그럼... 좀 씁쓸하긴 하지만...

안녕!

- 훈련 environment : CarRacing-v1 (https://github.com/NotAnyMike/gym)

https://notanymike.github.io/Solving-CarRacing/

위 링크를 참고하여 제작했습니다.

Proximal Policy Optimization (줄여서 PPO) 알고리즘을 사용하여 훈련하였습니다.

timestep 100만회 colab에서 훈련시켰고, 어느 정도 쓸만한 결과가 나왔습니다!

이렇게 좋은 모습들을 보이기도 하는 반면,

어디서 막혔는지;;; 가끔 보면 이상한 장면들도 나오곤 합니다.

너무 굴곡이 깊거나 하면 그냥 그대로 탈선해서 돌아오려고 하지도 않는 모습을 보이기도 하고,

????????

이해할수도 없이 그냥 멈춰있기도 하고;;;

갑자기 Agent가 술마셨는지 시작하자마자 어기적대면서 그대로 풀로 들어가서 주차하기도 하고;;;

한 천만번 정도는 돌린 다음에 하면 거의 완벽하게 되지 않을까 싶습니다.

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

* 강의 앞부분에 DQN을 정리하는 부분이 있는데, 그 부분은 그냥 빼고 설명하겠습니다.

오늘 배울 것들로는,

Behavioral Cloning, Inverse Reinforcement Learning, Apprenticeship Learning 등이 있습니다.

지금까지 우리는 Optimization과 Generalization에 대해서 배웠었다.

어떻게 최적의 policy를 찾아가는지, 그리고 어떻게 그것을 일반화 시킬지에 대한 이야기를 많이 했었는데,

이번에 볼 것은 바로 Efficiency, 즉 효율성이다.

컴퓨팅 파워를 많이 사용하지 않고 최적의 policy를 찾는 방법에 대해서 알아볼 것이다.

일반적인 MDP에서는, 좋은 policy를 찾기 위해서는 굉장히 많은 양의 sample들이 필요했다.

가령 DQN같은 경우, 굉장히 오랫동안 훈련시켜야, 즉 최대한 많은 양의 sample들이 있어야 좋은 성적을 낼 수 있었다.

그런데, 실제 강화 학습의 경우 이런 sample들을 얻기란 쉽지 않다.

만약 우리가 우주선을 발사하는 강화학습 Agent를 만들어야 한다면 어떨까?

수없이 많은 우주선 발사를 실패해야만 진짜 제대로 된 우주선 발사를 볼 수 있을 것이다.

그렇게 되면 천문학적인 비용이 깨지게 될 것이므로, 사실상 이런 방식의 RL로는 우주선 발사는 택도 없다는 것을 알 수 있다.

자율주행 자동차도 비슷하다. 스스로 운전하는 자동차를 만들어야 하는데, 수없이 많은 사고 이후에야 운전을 제대로 할 수 있다면, 아무도 그 비용을 감수하지 않으려고 할 것이다.

그렇다면, sample의 갯수를 줄일 수 있지 않을까?

그냥 아무것도 알려주지 않은 상태로 Optimal policy를 얻기를 기대하기 보다는,

이 강화 학습 과정을 도와줄 추가적인 정보나 구조들을 알려준 뒤에 훈련시키면 되지 않을까?

오늘은 이 아이디어를 Imitation Learning을 통해 살펴보자.

지금까지 우리들은 Reward를 통해서 Agent를 학습시켰었다.

DQN, Q-learning, MC 등등 모두 다 reward function을 사용하여 최대의 reward를 얻을 수 있도록 하는 것이 주요 포인트였다.

이 방식은 매우 간단한 방식으로 훈련이 가능하다는 점에서 좋지만, 아까 위에서 언급했듯 너무 많은 sample을 요구한다는 단점이 있다.

이는 데이터를 얻기 쉬운 가상의 환경 (시뮬레이터 등)이라면 큰 문제가 안되겠지만, 아까 위에서 말했던 우주선이나 자율주행 자동차같은 예시의 경우에는 이런 방식은 올바르지 못할 수 있다.

그리고, reward를 산정하는 방식도 조금 생각을 해 보자.

가령 자율 주행 자동차의 reward를 산정하려면 어떻게 해야할까?

만약 이 reward를 사고날 때 -10, 안나면 +0.1 이런 식으로 두면 어떨까?

그러면 아마 이 Agent는 어떻게 해야 사고가 나고 어떻게 해야 사고가 나지 않을지 알아내느라 한참을 고생할 것이다.

그러면 모든 상황에 대해서 적절한 reward를 대입해주면 어떨까?

우선 이 방식은 너무 오랜 시간이 걸리기도 하고 (초마다 reward를 넣어준다고 해도 1시간동안 운전한다면...),

이렇게 reward를 정해준다고 해도 reward의 상태가 매우 불안정해질 수 있다.

이를 보완하기 위한 대안책으로는, 바로 reward를 demonstration, 즉 실제로 어떻게 하는지 보여주면서 reward를 implicit하게 주는 것이다.

이렇게 demonstration으로 reward를 산정하려면 어떻게 해야할까?

바로 학습시킬 일의 전문가를 데려와서 demonstration trajectory를 만들어 학습시키는 것이다.

가령 자율 주행 자동차를 만든다고 한다면, 운전을 매우 잘하는 어떤 사람을 데려와서 실제로 한번 운전시켜 보는 것이다.

그렇게 얻은 State/action sequence들을 강화 학습 Agent에게 줌으로써 그것을 바탕으로 학습시키면 된다.

이 Imitation learning 방식은 reward를 일일히 부여하거나 특정 policy를 따르도록 하게 하려는 것이 아닐 경우에 효율적이다.

이제 Imitation learning의 기본적인 setting에 대해 설명해 보겠다.

우선, Input은 지금까지와 비슷하게 State space와 action space로 이루어져 있고, Transition model P가 주어진다.

다른 점은, reward function R은 주어지지 않는다. 그 대신, (s0, a0, s1, a1, ....) 과 같은 demonstration을 주어준다.

(위에서 설명했던 것과 비슷하다.)

이제부터 Behavioral Cloning, Inverse RL, Apprenticeship learning에 대해 배울 것인데, 각 종류에 대한 목표 과제는 다음과 같다.

Behavioral Cloning : supervised learning을 통해 스승(전문가)의 policy를 직접 배울 수 있게 하자!

Inverse RL : reward function R을 demonstration을 통해 얻을 수 있을까?

Apprenticeship learning : R값을 좋은 policy를 생성하는데 사용할 수 있나?

이제부터 Behavioral Cloning부터 차근차근 알아가 보자.

Behavioral Cloning 방식은 이 강화 학습 문제를 기존의 머신 러닝 문제를 푸는 방식대로 생각하는 것이다.

즉, 원래 자주 사용하던 Supervised learning 방식을 사용하자는 것이다.

우선 policy class를 설정해 두고, (인공 신경망, decision tree 등등을 사용할 수 있다.)

expert의 state와 action의 sequence를 supervised learning model의 input/output으로 두고 Agent를 학습시킨다.

자율 주행 자동차를 예시로 들자면, 만약 왼쪽으로 코너를 돌 때의 action이 대부분 핸들을 왼쪽으로 꺾는 것이라면,

supervised learning model은 다음부터 왼쪽으로 돌아야 한다는 state를 받을 때 action은 핸들을 왼쪽으로 꺾어야 한다고 학습할 것이다.

하지만, 이 Behavioral Cloning 방식에는 큰 문제가 하나 있다.

Compounding Error (직역하면 합성되는 에러..?)라는 문제점이 바로 그것이다.

이는 Supervised learning은 모든 데이터가 iid라는 것을 전제로 한다는 것 때문에 발생한다.

여기서 iid란 각각의 데이터들이 독립적이고 동일한 확률분포를 가진다는 것을 의미하는데, 조금 더 쉽게 하자면 그냥 모든 데이터 아무거나 하나를 뽑아도 다른 데이터와 연관이 없다는 것을 전제한다는 것이다.

(그래서 Supervised learning에서는 데이터가 어떻게 주어지든 그 데이터의 순서를 마구 섞어서 input으로 집어넣어도 된다.)

그런데, 분명 우리가 주는 데이터 state, action pair은 시간의 흐름에 따라 이어지는 데이터이다.

즉, (s0, a0, s1, a1, s2, a2, ...)라는 데이터에서 분명 s0이 s1보다 먼저, s1이 s2보다 먼저 있는 state라는 것이다.

하지만 Supervised learning에서는 이러한 데이터의 시간적 구조를 싸그리 무시하고, 모든 데이터를 iid라고 가정하기 때문에,

언제 어떤 state였는지는 중요하지 않고, 그냥 특정 state에서 특정 action이 취해지길 바라고 있는 것이다.

자율 주행 자동차의 예를 다시 한번 들어보자.

사람의 경우, 고속도로를 달리는 중 휴게소가 가고 싶다면 휴게소 쪽으로 차선을 옮기게 될 것이다.

어떤 특정 state와는 관계 없이 (휴게소가 아주 가까이 있지 않더라도) 휴게소 쪽으로 차선을 옮기는 것이다.

하지만 Supervised learning 기법으로 학습한다면, 어떤 상황에 왜 차선을 변경하는지는 알지 못하고, "아, 저 state에서는 차선을 바꿔야겠구나!" 생각하고 action을 선택하게 된다.

이런 것들이 하나 둘씩 쌓이다 보면, error가 굉장히 커지게 된다.

또 다른 예를 들어보자.

위 사진에서 보면, Expert가 운전한 대로 Agent가 운전을 하고 있다가, 특정 구간에서의 Error로 인해 코너링 초반에 실수를 조금 했다. (조금 더 바깥쪽으로 코너링을 시도했다.)

하지만, expert는 그런 실수를 하지 않았기에, (그리고 하지도 않을 것이기에,) 저런 상황에서 어떻게 복구해야 하는지 알 길이 없다.

그러면 time step t에서의 실수 하나로 인해 그 이후의 time step t+1, t+2에서도 계속 error가 생길 수 밖에 없고,

그러다 보면 결국 학습에 실패하게 되는 것이다.

이 문제를 해결하기 위해 DAGGER : Dataset Aggregation이라는 방식을 사용한다.

아이디어는 놀라우리만큼 간단하다.

그냥 잘못된 길을 가는 경우 expert에게 어떤 action을 취해야 할지 알려달라고 하는 것이다.

그러니까 코너링을 잘못 돌았을 때, expert에게 "이런 경우엔 어떻게 해야되요?" 라고 물어보고,

expert는 "이렇게 코너링을 돌아야 한단다 ㅎㅎ" 라고 알려주는 것이다.

아이디어만 들어도 알겠지만, 이 방식은 모든 상황에서 효율적으로 쓰일 수 있는 방식은 아니다.

우선, 정말 짧은 time step 간의 state에 대한 action이 필요한 경우에는 사실상 이러한 방식이 불가능하다.

자율 주행 자동차 같은 경우, 정말 짧은 시간동안 어떻게 운전할지가 중요한데, 이런 경우에는 모든 잘못된 경우마다 어떻게 해야 하는지 알려주는 것은 힘들 것이다.

그러나, 만약 그렇게 디테일한 정보까지는 필요 없고 간단한 정보만 필요한 경우에는 사용할 만한 가치가 있을 것이다.

가령, 예시가 간단한 Frozen lake같은 게임을 플레이 하는 것이라면, 굉장히 사용할 만 할 것이다.

오목같은 경우에도, 조금 힘들긴 하겠지만 어떻게든 사용해 먹을 수는 있을 것이다.

그런데 사실 일반적인 경우에는 쓰기 힘들다는 것을 알 수 있다. GPU로 훈련하는 중에 action을 어떻게 효율적으로 집어 넣어줄 것인가?

수시간, 길게는 수십시간 동안의 훈련 시간동안 expert가 컴퓨터 앞에 쭉 앉아 있을 수도 없고 말이다.

그런 단점들 때문에, 후술할 다른 방식들 보다는 이 쪽 업계에 미친 영향이 조금 적다고 한다.

다음으로 알아볼 방식은 Inverse RL이라는 방식이다.

이 방식은 (위에서 짤막하게 설명했듯이) expert의 (위 슬라이드에서는 teacher라고 명명한다.) policy를 보고, reward function을 찾아나가는 방식이다.

아까 전에 설명한 것이지만 다시 세팅을 알려주자면,

state space, action space, transition model P가 주어지지만, reward function R은 주어지지 않는다.

그 대신, teacher의 demonstration (s0, a0, s1, a1 ...)을 받게 된다.

이제 이 Inverse RL은 reward function R을 teacher의 demonstration을 통해 알아가게 된다.

여기서 간단하게 질문 하나를 해보자.

만약 teacher의 policy가 optimal하다는 전제가 없다면, 위 demonstration은 R에 대한 어떤 정보를 줄 수 있을까?

정답은, 간단하게 "줄 수 없다" 이다.

그냥 간단하게, teacher의 policy가 말짱 꽝이라고 해보자. 자율주행 자동차의 경우, 그냥 직진만 한다고 해보자.

그러면, 이 teacher가 운전하는 모습을 보고 운전을 처음 하는 사람이 뭔가를 배울 수 있을까?

뭐가 좋은 것이고 뭐가 나쁜 것인지 알 수 있을까?

당연하게도 알 수 없다.

즉, 우리가 이 Inverse RL 방식을 사용하려면 teacher의 policy는 optimal하다는 전제가 있어야 한다.

(아니, 그래도 teacher의 policy가 어느 정도 이성적으로 판단한 거 아닌가? 라고 생각할 수도 있겠지만, 그런거 베재하고 생각하는 것이다.)

그렇다면, teacher의 policy가 optimal하다고 가정했을 때 reward function은 unique할까, 아니면 여러 개가 있을 수 있을까?

(단, 데이터는 충분히 존재한다고 가정한다.)

정답은, 여러 개가 존재할 수 있다 이다.

이유는 간단하다. 그냥 모든 reward에다가 0을 던져버리면, 어떤 optimal policy가 있더라도 모두 다 동일한 reward를 가지게 될 것이다.

비단 0이 아니더라도 모든 action에 따른 reward를 1, 2, 3과 같은 동일한 상수값을 던져주게 되면, 어떤 policy라도 optimal하게 된다.

조금 더 쉽게 설명해 보겠다.

만약, 선생님이 당신에게 C언어에서 출력을 어떻게 하는지 알려주고 있다고 해보자.

printf("%d",a+b); 라는 코드를 짜 줄수도 있고,

printf("%c",a); 라는 코드를 짜 줄수도 있을 것이다.

그러면 일반적인 상식적으로, 우리는 저 앞의 printf("% 부분의 reward는 높을 것이고, 또 맨 뒤에 );의 reward도 높을 것이라고 예측할 수 있다.

그런데 만약 위 두 case의 각각의 철자마다 그냥 reward가 0이라고 해버린다면 어떨까?

그러니까, 선생님이 어떤 코드를 짜던지간에, "아몰라 저거 다 reward 0이라고 하면 되는거잖아? 그러면 내가 뭔 코드를 짜던지 간에 내 코드도 optimal policy로 짜지는 코드인데??" 라고 할 수 있다는 것이다.

즉, printf에 가중치가 부여되는 것이 아니라, 그냥 drqctz나 printf나 똑같은 reward를 갖게 되는 것이다.

그런데 당연히 이것을 의도하고 코딩하는 법을 가르쳐 준 것이 아니지 않겠는가!

이런 점에서, 이 Inverse RL은 큰 문제에 봉착하게 되었다.

그렇다면 이 Inverse RL의 문제를 어떻게 해결할까?

우선 저번에 배웠던 Linear value function approximation을 다시 가져와 보자.

R값은 여러 개가 존재할 수도 있다고 했지만, 그냥 일단 R값을 wT x(s)라고 둬보자.

(이 때, w는 weight vector이고 x(s)는 state의 feature이다.)

그래서, 이 weight vector w를 주어진 demonstration을 통해 찾아내는 것이 목표이다.

우선, policy π에 대한 Vπ값을 E[Σt=0-->∞ 𝛾^t*R(sₜ)|π] 라고 할 수 있다.

(즉, Reward의 discounted sum이다. 수식을 예쁘게 쓰고 싶은데 수식 편집기가 없어서 ㅠㅠ 위 슬라이드를 보며 이해하면 좋겠다.)

이것에 위에서 정의한 R(s) = wTx(s)를 대입하면,

E[Σt=0-->∞ 𝛾^t*wT*x(sₜ)|π]라고 할 수 있다.

또, 모든 π에 대하여 wT의 값은 동일하므로, wT값을 앞으로 넘겨서 

wT*E[Σt=0-->∞ 𝛾^t*x(sₜ)|π] 라고 할 수도 있다.

그러면 이제 거의 다 끝났다.

E[Σt=0-->∞ 𝛾^t*x(sₜ)|π]의 값을 그냥 μ(π)라는 값으로 두면,

최종적인 Vπ의 값을 wT*μ(π) 라고 할 수 있다.

그런데, 여기서 μ(π)(s)가 의미하는 바가 무엇인가?

(참고로, 뒤에다가 (s)붙인거 오타 아니다. μ(π)는 벡터이므로...)

각각의 time step t에서 나타나는 state feature x(s)에다가 discount factor 𝛾^t를 곱한 것이다.

그리고 거기에다가 w의 transpose를 곱하므로, 이는 각 state feature의 weighted discounted frequency를 나타내는 값과 동일해 진다.

즉, 우리가 학습시킨 weight vector w값에다가 자주 등장하는 state feature의 값을 곱해주는 것이다.

자, 그럼 이 값이 잘 만들어진 값인지 보자!

Inverse RL에서 우리의 목표는 무엇이었는가?

바로 (optimality가 전제된) teacher의 policy를 보고, 그 policy를 토대로 reward function이 어떻게 되어 있을지 찾아가는 것이었다!

그러면, teacher의 policy를 봤을 때 자주 보이는 state feature의 실제 reward 값은 어떨까?

당연하게도, optimality가 전제되어 있으므로, 자주 보이는 state feature를 갖는 state의 reward는 높을 것이다.

비슷하게, 거의 보이지 않았던 state feature를 갖는 state의 reward값은 일반적으로 낮게 될 것이다.

이것도 자율주행 자동차를 생각하면 편할 듯 하다.

왼쪽으로 코너를 돌 때, 차선을 잘 맞춰서 도는 일이 빈번할 것이므로 (optimal한 policy였으므로...) 그러한 state에서는 당연히 높은 reward값을 가질 것이다.

또, 왼쪽으로 코너를 돌 때 웬만하면 왼쪽으로 막 틀어지거나 하는 일은 없을 것이므로, 그 state의 경우는 reward가 낮게 측정되는 것이 일반적이다.

이렇게, 비교적 간단한 수식으로 Inverse RL을 수행할 수 있다.

그리고 이런 방식을 사용하면, 모든 경우에 reward를 0을 던질 일은 없어지므로, 제기되었던 문제를 어느 정도 해결할 수 있게 되었다!

다음 방식은 Apprenticeship Learning이다.

사실 Apprenticeship Learning도 Inverse RL과 굉장히 비슷하다.

방금 전까지 한거 그대로 이어서, 조금 더 잘 만든 버전이라고 생각하면 될 듯 하다.

Vπ = wTμ(π)부분까지는 그냥 동일하다고 보면 된다.

위 ppt 참고해서 보면, V*는 언제나 Vπ보다 크거나 같다. (기억안날까봐 - *는 optimal함을 의미함.)

그러므로, expert의 demonstration이 optimal policy에서 온 것이라면, w를 찾기 위해서는

w*Tμ(π*) >= w*Tμ(π) 를 만족하는 w*를 찾을 필요가 있다.

수식을 해체해서 설명하자면,

μ(π*)는 expert가 주는 optimal한 policy이므로 우리가 이미 알고 있는 값이고,

μ(π)는 expert가 주는 policy를 제외한 다른 어떤 policy를 의미한다.

즉, optimal policy의 값을 정말 optimal하게 만들어주는 w*의 값을 찾아야 한다는 것이다.

(만약 위의 수식을 만족하지 않는다면 reward function R에서 V값이 optimal policy보다 높은 policy가 존재한다는 것인데, 이건 말이 안되지 않는가!)

**설명이 약간 부실한 것 같아서 부연설명하자면... (이미 이해했으면 걸러도 됨)

지금 문제 상황은 우리가 모르는 reward function R값이 있다는 것이다.

분명 expert는 (무의식적으로라도) reward function 값들을 알겠지만, 우리 (Agent)는 그 값을 모르니, 그 값을 찾아가겠다는 것이다.

그런데 expert가 optimal하게 움직인다는 것은, 당연히 그 reward function을 통해 얻을 수 있는 최적의 움직임을 하고 있다는 뜻이다.

그러니 저 위의 수식을 만족하는 w값을 찾을 수 있어야 한다는 것이다.

(이래도 이해 안되면 댓글로 ㅎㅎ..)

그래서 저 수식을 만족하는, 즉 expert policy가 다른 어떤 policy보다 잘 작동하는 reward function을 찾고 싶다는 것이다.

그리고 만약 우리의 policy π와 π*에서의 Value 값이 충분히 비슷하다면, 우리는 π*, 즉 optimal policy 수준의 policy를 찾아냈다고 할 수 있을 것이다.

조금 더 정확히 말하자면, 어떤 ε에 대하여 ||μ(π)-μ(π*)||₁<=ε를 만족하는 π를,

그리고 ||w||∞ <=1을 만족하는 모든 w에서 |wTμ(π) - wTμ(π*)|<=ε을 만족하는 w를 구해야 한다는 것이다.

*참고 : ||X||₁은 L1 norm을, ||X||∞는 L infinity norm을 의미한다. 자세한건 구글링으로 알아보시길...

수식을 또 간단히 하자면 (약간 의역하자면), 모든 state에 대해서 μ(π)의 값과 μ(π*)의 값의 차이가 ε이하이고,

모든 값의 절대값이 1보다 작은 w값에 대해서 wTμ(π)와 wTμ(π)의 차이가 ε이하인 π와 w를 구해야 한다.

(당연히, 여기서 ε은 충분히 작은 값이다.)

(+ w값의 절대값이 1보다 작아야 하는 이유는 훈련 도중에 값이 explode하지 않게 하기 위함인듯 하다.)

이렇게 하면, 원래 reward function이 뭐였느냐에 관계 없이, 학습으로 도출된 reward function을 사용하더라도 충분히 optimal policy에 가까운 policy를 얻어낼 수 있다!

이 부분은 지금까지 위에서 말한 것을 알고리즘으로 나타낸 것이다.

그런데 교수님 말씀으로는 이거 이제 거의 안쓰인다고 설명을 안해주셨다.

사실 이쯤되면 위 ppt 보는것 만으로도 이해가 될 경지에 이르렀다고 생각하겠다 ㅎㅎ

지금까지에서 가장 중요한 것은, optimal policy와 충분히 비슷한 policy를 얻어내는 것만으로도 학습이 충분하다는 것이다.

(실제 optimal policy가 가지던 reward function과 관계없이 어떠한 reward function으로라도 저런 policy만 찾을 수 있으면 된다는 뜻이다.)

하지만 아직 문제점들이 남아 있다.

아까 전에 같은 optimal policy에도 수없이 많은 reward function들이 있을 수 있다고 했는데, 사실 위의 알고리즘이 이 문제를 완벽히 해결하지는 못한다.

또한, reward function을 구했더라도 그 reward function에 최적으로 부합하는 policy도 사실 여러 개가 있을 것이다.

그 중 어떤 것을 골라야 하는가? 가 바로 그 문제점이다.

이런 문제들 같은 경우, 아직도 활발히 연구되고 있다.

주요 논문으로는, Maximum Entropy Inverse RL과 Generative adversarial imitation learning이 있다.

Maximum Entropy Inverse RL의 경우, 말 그대로 Entropy의 값을 최대화시키자는 것인데...

필자도 설명을 들어도 잘 모르겠어서, 구글링을 이리저리 하다가 설명을 매우 잘 해놓은 다른 블로그를 보게 되었다.

https://reinforcement-learning-kr.github.io/2019/02/10/4_maxent/

필자가 아무리 잘 설명해 봤자 이것보단 더 잘 설명할 수 없을 것 같으므로, 그냥 여기 들어가서 보는 것을 추천한다.

간단하게 설명하자면, Imitation learning의 uncertanty를 최소화 하기 위해, (즉, 최악의 선택을 피하기 위해) entropy를 최대화 시켜줘야 한다는 것이다. 최대한 일반적인 움직임만을 선택하자는 느낌이다.

Generative adversarial imitation learning, 줄여서 GAIL의 경우의 아이디어는 GAN과 매우 흡사하다. (이름부터가...)

주요 아이디어는, discriminator (판별자?)를 만들어서, expert policy와 우리가 찾아낸 policy를 구별하게 만드는 것이다.

그렇게 해서 최적의 이 discriminator가 expert policy와 그냥 policy를 구별할 수 없을 정도의 policy를 찾아낸다면, 그것이 바로 충분히 좋은 policy라고 하는 것이다.

이 방식을 사용함으로써, 우리는 통계적 계산의 산물인 μ(π)에서 조금 더 멀어져서, 실제 좋은 움직임을 찾을 수 있을 것이다.

자, 이제 거의 다 왔다! 이제 지금까지 배운 내용을 마무리해보자.

Imitation learning을 사용하면, 다른 방법들을 사용하는 것 보다 좋은 policy를 얻기 위해 필요한 데이터의 양이 매우 적어진다.

그렇기 때문에, 실제 산업 현장에서도 굉장히 practical하게 사용되고 있는 기법 중 하나이다.

특히 로봇쪽에서 굉장히 많이 보이지만, 그것 외에도 굉장히 다양한 분야에서 시도되고 있는 기법이다.

가장 큰 도전 중 하나는, 사실 대부분의 문제에서 우리는 optimal policy가 뭔지 모른다는 것이다.

사실 오늘 강의는 expert의 policy가 언제나 optimal하다는 것을 전제로 해 왔지만, 솔직히 누가 운전하는 optimal한 방법을 알고 있겠는가?

학생을 가장 효율적으로 교육하는 교육 시스템을 만든다고 하면, 대체 누가 가장 효율적인 학습 방법을 알고 있다는 것인가?

그리고, 아직 optimal policy를 모르는 문제들의 경우 어떻게 exploration을 진행하며 좋은 policy를 얻어가야 할까?

이러한 문제들은 Imitation learning, 그리고 강화 학습이 발전하면서 차차 해결해 나가야 할 문제이다.

오랫만에 글을 써서 그런지 힘을 빡 주고 쓴 느낌이다.

원래는 그냥 막 넘길 부분도 조금 자세히 설명하기도 하고, 최대한 이해가 쉽게 노력했다.

(그래서 그런지 글 쓰는데 강의 시청시간 제외 총합 5시간정도 쓴것 같다;;)

(지금 보니까 지금까지 글 쓴것 중에서 가장 길게 쓴 글이다. 호달달;;)

모쪼록 이 정리 포스팅을 보고 강화 학습을 쉽게 배울 수 있었으면 좋겠다.

혹시라도 이해가 잘 되지 않거나, 오타나 잘못된 점들이 있으면 댓글로 남겨주면 좋겠다.

아무튼, 다음 시간에는 Policy Search라는 방식을 알아보도록 하겠다.

- 본 포스팅은 CS234 6강의 내용을 정리합니다....만 CNN 부분은 따로 설명하지 않겠습니다.

그 대신, 제 블로그의 CS231n 강의 (https://cding.tistory.com/5) 를 보시거나 간단한 CNN 오버뷰 정도는 보고 오시면 좋겠습니다.

오늘 배울 것들로는 원래는 CNN과 Deep Q Learning이겠지만, 위에서 언급했듯 DNN 및 CNN은 설명하지 않고 바로 DQN으로 뛰어넘도록 하겠다. 

그래서, DQN이 뭔지, 어떻게 이루어지는지 알아보자.

저번에 짤막하게 설명했듯이, function approximation, off policy control, boostrapping 셋을 모두 사용하는 것은 굉장히 unstable하다. Converge하지 않을 가능성이 농후하기 때문이다.

짤막하게 DQN의 역사에 대해 설명하자면,

1994년즘에 backgammon을 DQN으로 구현해낸 이후로 1995년 ~ 1998즘엔 위에서 말한 unstability를 개선하기 위한 연구를 진행하다가 DNN 자체가 망하는 바람에 연구가 더 진행되지 못했다.

그러다 2000년대 중반즈음부터 computational power의 증가 및 data의 증가 등의 이유로 DNN이 각광받기 시작하며,

DQN 또한 같이 주목받게 되었다.

그리고 2014년 (정말 얼마 안되었다) 경 Deepmind에서 위처럼 breakout (벽돌깨기) AI를 DQN을 사용해서 만들기에 이른다.

최근에는 도타 2 AI인 Openai five가 5대5로 프로게이머를 이기고, 전세계 사람들과 대전했을 때 99.5%의 승률을 자랑하기까지 하는 등 Deep Reinforcement Learning이 각광받고 있다.

아무튼, 우리는 DNN을 사용해서 Reinforcement Learning을 시킬 것이다.

(당연히 VFA를 사용한다.)

DQN은 그냥 Q (state action)을 DNN에 적용시킨 것 뿐이다. 그렇게 Value와 Q function을 구하는 것이 목적이다.

(대충 저번 시간에 했던 내용이므로 대충 생략하겠다는 말)

그래서 이러한 Q-Learning 방식을 Atari 게임에 적용시키면 된다.

게임 화면의 이미지를 state로, agent가 취하는 컨트롤을 action으로, 그리고 게임에서 주는 점수를 reward로 한다.

그렇게 해서 agent를 학습시켜 보자는 것이 기초적인 아이디어이다.

Atari Breakout (벽돌깨기) 을 예시로 들 것인데, Atari breakout같은 경우 action의 종류가 약 4개에서 18개정도밖에 되지 않는다.

하지만, state같은 경우 이미지의 픽셀값들을 받아오므로 굉장히 큰 data가 된다. 이것들을 어떻게 다뤄야 하는지 알아보자.

참고로 말해두자면, 지금부터 배울 대부분의 내용들은 2015년도 Deepmind의 Atari DQN 논문에 있는 내용들이다.

우선, input으로는 이전 4프레임의 이미지를 받는다.

1프레임의 이미지만을 input으로 두지 않고 이렇게 4프레임의 이미지를 받는 이유는 공의 방향이나 속도들을 알기 위해서이다.

CNN과 relu, fully-connected layer 등을 걸쳐 나오는 output은 Q(s,a)로, 18개의 조이스틱 및 버튼의 움직임을 표현한다.

그리고 Deepmind의 논문에서는, 이 아키텍쳐와 hyperparameter 들을 모든 게임에 동일하게 적용하였다.

그것만으로도 충분히 학습된다는 것을 보이기 위해서였고, 실제로 많은 게임들에 잘 적용되는 것을 볼 수 있다.

물론, 몇 개의 게임들은 확실히 tuning해야 할 것이다.

가령 delayed reward가 매우 중요한 게임들은 (감마) 값을 높게 두어야 할 것이다.

이제 진짜 본론으로 들어가보자.

Q-learning을 VFA를 사용해서, SGD를 사용해 MSE loss를 최소화시키고, 최적의 Q*(s, a)를 찾아가는 과정이다.

그러나, 저번에도 말했듯이 Q-learning을 VFA와 함께 사용하면 diverge할 수 있다. (수렴하지 않고 막 나간다)

그 이유는 첫번째로는, sample간의 연관성이 너무 크기 때문이다.

아까 전, 분명 DQN은 게임의 화면을 5프레임 간격으로 받는다고 했었는데, 분명히 게임의 연속된 다섯 프레임은 굉장히 연관되어 있을것이다.

그런데 이렇게 sample 간의 연관성이 너무 커져 버리면, SGD 방식으로 수렴하기 위해 필요한 IID 상태가 아니게 된다.

(IID란 간단히 말해서 모든 데이터들이 다 독립적이어야 한다는 뜻이다.)

또한, target이 non-stationary하다. 즉, target이 계속 변화한다.

VFA를 적용시키려면, 최소한 어디에 Converge시켜야 하는지는 알아야 한다.

그런데 Q-learning의 경우 이 optimal policy가 계속 바뀌므로, 어디다 Converge하기가 쉽지 않다.

이 두 가지 문제점을 해결하기 위해서, deepmind에서는 Experience Replay와 Fixed Q-target이라는 방법을 사용한다.

Experience Replay는, 말 그대로 지금까지의 경험을 축적해서 다시 사용하는 것이다.

원래였다면 그냥 한번 w와 policy를 update하고 말 경험들 (지나친 step들)을 저장하고 있다가, 나중에 다시 이 값들을 사용해서 w값을 update해 주는 것이다. 

이렇게 하면 원래 굉장히 높은 연관성을 띄던 데이터들로부터 벗어나서, 조금 더 독립적인 (연관성이 적은) 데이터들로 다시 w를 update해줄 수 있는 것이다.

또, 원래 update하던 도중에도 Q-learning방식을 사용했기에 target value가 이미 바뀌어 있을 것이고, 그러면 그 바뀐 값에 대해 다시 독립적인 데이터를 사용해 w를 update해줄 수 있는 것이다.

Fixed Q-Targets는 말 그대로, target weight를 고정시켜주는 것이다.

Q-learning 방식에서는 계속 target이 바뀌어서 문제였지만, 이것을 그냥 고정시켜줌으로써 대처하는 것이다.

target update를 할 때 사용할 weight w⁻와 실제 update를 해 줄 weight w를 나누어서 사용하는 것이다.

아래쪽의 식을 보면 이해가 빠를 것 같다.

원래 max를 시켜주는 저 target에는 w⁻를 집어넣고, 그 외 나머지 부분에는 원래 weight w를 집어넣어 준다.

그리고, n번째 마다 (hyper parameter이다.) w⁻값을 다시 원래 w값으로 맞춰 준다.

이렇게 해 주면, 원래 Q-learning에서 계속 w가 바뀌다가 결국 w가 막 infinity로 터지는, 그런 상황을 방지할 수 있다.

즉, stability가 꽤 많이 향상된다는 것이다.

-정리-

DQN은 experience replay와 fixed Q-target를 사용한다.

replay memory D에 experience (s, a, r, s')을 채워주고, 거기서 mini-batch를 sampling해서 update한다.

또 fixed parameter w⁻를 사용하여 Q-learning target을 연산하고, MSE loss를 최소화 시켜준다.

SGD를 사용하고, (위에서 나오진 않았지만) ε-greedy exploration도 사용한다.

그러면, 이렇게 학습하면 잘 될까?

https://www.youtube.com/watch?v=V1eYniJ0Rnk

ㅇㅇ.. 잘 된다!

그럼 DQN에선 어떤 부분이 가장 중요할까?

위 표를 보면 알겠지만, experience replay를 적용시키는 경우 효율이 가장 좋은 것을 알 수 있다.

이제부턴, Deepmind의 논문 이후에 발표된, Deep RL의 주요 improvemets들을 설명하겠다.

그 중 첫번째는, 바로 Double DQN이다.

저번에 설명했던, maximization bias 문제를 해결하기 위해 나온 Double Q-learning의 Deep RL 적용판이다.

Double Q-learning이 뭐였는가?

Q를 하나만 쓰는 대신, 두 개를 사용하여 50% 확률로 Q1, 나머지 50% 확률로 Q2를 사용하여 Q-learning을 하는 방식이었다.

이 아이디어를 DQN에도 적용시킨 것이 바로 Double DQN이다.

현재 사용하는 Q-network w를 action을 고르는 데 사용하고,

w⁻는 action을 evaluate 하는 데 사용하는 것이다. (위 식 참고)

그래서, Double DQN을 사용하면, 위와 같이 좋은 결과를 낼 수 있다.

두 번째 방식은, 바로 Prioritized Replay이다.

말 그대로, Experience Replay를 그냥 막 골라서 하지 말고, 우선순위를 정해서 하자는 것이다.

이쯤, Mars Rover 예시를 다시 들어보자.

(지금까지 엄청 자주 설명했고, 위에도 잘 나오니 자세한 설명은 생락하겠다.)

그래서 위 예제에서 (s3, a1, 0, s2, a1, , s2, a1, 0, s1, a1, 1, terminal) 에피소드를 지난 뒤에, TD estimate는 어떻게 되는가?

한 번 update를 해 주면, 결국 reward가 s1, a1, 1, terminal 에서 나왔으므로 결국 [1 0 0 0 0 0 0]이 된다. (bootstrapping)

이제 여기서 replay를 두 번 진행할 수 있다고 할 때, 어떤 step을 replay하는 것이 가장 좋을까?

(오른쪽 위가 replay buffer가 저장되어 있는 모습이다.)

만약 (s3, a1, 0, s2) 버퍼를 사용해서 replay 한다면, 아무런 의미도 없을 것이다.

결국 지금 상태는 [1 0 0 0 0 0 0]이고, s3, s2는 reward가 0이므로, 아무런 영향도 미치지 않는다.

(s2, a1, 0, s2)를 선택하는 경우에도 마찬가지로, s2는 reward가 0이므로 아무런 영향도 미치지 않는다.

(s2, a1, 0, s1)을 선택하는 경우만 다르게 적용된다. 현재 s1이 1이므로, 이 reward 1은 그대로 s2에 전달되게 된다. (α=1)

그러면, 결국 TD estimate는 [1 1 0 0 0 0 0]이 된다.

그 다음엔?

만약 (s3, a1, 0, s2) 버퍼를 사용하면, s2의 reward가 1이므로, s3에도 그 reward가 그대로 전달되므로,

TD estimate는 [1 1 1 0 0 0 0]이 된다.

이렇게, 한 episode에서 최소의 replay buffer만을 사용하여 최적의 TD estimate를 얻어냈다.

만약 위처럼 우리가 replay buffer를 선택하지 않고 그냥 아무런 replay buffer나 사용하였다면, 이렇게 결과가 잘 나오진 못했 을 것이다.

위에서 아무런 영향을 주지 못한 replay는 결국 연산 횟수만 증가시키는 꼴이 되기 때문이다.

즉, 이렇게  replay buffer를 선택하는 과정은 update 효율을 굉장히 증가시켜 준다는 사실을 알 수 있다.

위에서 봤듯이, TD-learning에서는 replay의 순서가 학습의 속도를 늘리는 데 도움을 줄 수 있다.

아무런 쓸데 없는 정보가 담긴 버퍼를 사용하는 것 보다, 쓸데 있는 버퍼를 사용하는 것이 더 좋다는 것인데...

그런데, 어떻게 replay buffer의 우선순위를 정해야 할까?

위처럼 하나하나 넣어봐서 가장 좋은 버퍼를 고르는 것은 매우 비효율적일 것이니 말이다.

(대충 Episodic Replay Update의 순서를 정하는 것이 convergence를 빠르게 한다는 내용)

그래서 우리가 사용할 방법은 DQN error을 사용하는 방법이다.

어떤 tuple (replay buffer)를 골랐을 경우의 TD error와 현재 error의 차이가 가장 큰 것의 우선순위를 크게 잡아두는 것이다.

왜 이렇게 하냐고? 직관적으로 바라보자면...

만약 TD error가 현재의 error와 같다면 어떨까?

지금 선택한 replay buffer가 error에 아무런 영향을 끼치지 않는다는 이야기가 되므로, 정말 아무런 쓸데 없는 연산이 된다고 할 수 있다.

아까 위에 예시에서 아무런 영향을 끼치지 못하는 버퍼가 바로 이런 것들이다.

반면, TD error가 현재의 error와 크게 차이가 난다면?

그 버퍼가 바로 우리가 미처 제대로 습득하지 못한 데이터일 가능성이 커지게 되는 것이다.

그래서 이런 방식으로 replay buffer의 우선순위를 결정할 수 있다.

그럼 한 가지 질문만 던져보자. 만약 α=0이라면 어떻게 replay buffer가 선택이 될까?

α=0이라면, 저번 step에서 일어난 일이 현재 step까지 어떤 영향을 끼치지 못하게 되는 꼴이므로,

모든 TD-error과 현재 error의 차이가 동일하게 정해지게 된다.

그렇기에, replay buffer는 그냥 랜덤하게 결정되게 된다.

위는 Prioritized replay 방식과 double dqn 방식을 사용했을 때의 효과를 나타낸 그래프이다.

그냥.. 그렇다구...

다음으로, Dueling DQN이라는 방식이 있다.

이 방식의 요점은, optimal Q를 선택할 때 현재 state의 value와 action을 따로따로 생각한다는 점이다.

여기서 Advantage Function이 나오는데, 이는 Q(s, a)에서 V(s)를 뺀 값으로, 현재 action을 선택했을 경우 다른 action을 선택했을 때 보다 얼마나 더 좋은 결과를 내보내는지를 의미한다.

즉, 현재 Vπ(s)값에 비례한, action에 따른 상대적인 Value값을 의미한다.

개인적으로 이 부분 이해가 힘들었으므로 더 적어두자면, (사실 나중에 까먹었을때 볼라구 ㅎㅎ)

Vπ(s)는 policy를 따를 때, 그 state에서의 Value의 평균이다.

그리고 Qπ(s, a)는 각각의 action a를 따를 때 나오는 Value이므로,

결국 모든 action에 대한 Qπ(s, a) - Vπ(s) = 0이다.

여기서, 만약 Qπ(s, a)의 값이 Vπ(s)보다 크다면, 현재의 state에서 일반적으로 나올 수 있는 Value보다 더 좋은 Value를 얻은 action을 선택했다는 의미가 된다.

게임을 예시로 들어보자면,

현재 점수가 Vπ(s)인 것이고, Qπ(s, a)는 다음 action a를 취했을 때의 점수인 것이다.

만약 Advantage Function을 사용하지 않고 그냥 Qπ(s, a)만 본다면,

게임 후반의 점수가 게임 초반의 점수보다 당연히 더 높을 것이므로 게임 후반의 Q(s, a)값만 바라보고, 그 action을 취하는 데에 치중하게 될 것이다.

하지만 만약 Advantage Function을 사용하면, 게임 초반이나 후반이나 상관없이 내가 이 action을 취했을 때 얼마나 잘 플레이 한 것인지 알 수 있게 된다.

다음은 Dueling DQN의 아키텍쳐이다.

원래 DQN에서 마지막에 Q(s, a1), Q(s, a2) ...의 값이 나왔다면,

Dueling DQN에서는 마지막에 V(s), A(s,a1), A(s,a2)의 값들이 따로 나오고,

이 값들을 합쳐서 Q(s, a1), Q(s, a2)의 값을 얻어내는 것이다.

위 두 슬라이드는 영상에서 교수님이 설명을 안하셨다.

그러니 이해하고 싶으면 ppt를 보고 이해해야 된다.

난 못했으니 그냥 넘어간다.

Dueling DQN은 굉장히 효율이 좋은 학습 방식이고, 이는 위 그래프로 설명이 가능하다.

지금부터는 이 DQN을 실제 적용할 때의 팁들이다.

- DQN은 다른 방식들보다는 더 믿을만한 방법이다. Pong은 그중에서도 좀 믿음직 스러운 게임인데, 만약 DQN을 Pong에 적용시켰는데 뭔가 잘 안된다면, 너가 뭔가 잘못 한 것이다.

- DQN에서 replay buffer는 크면 좋으므로, 메모리 효율이 매우 중요하다. 데이터를 막 중복해서 쌓지 말고, uint8 이미지를 사용하라.

- DQN은 굉장히 천천히 Converge 하므로, 참을성 있게 기다려라.

아타리의 경우 천만~4천만 프레임 동안 기다려야지 random policy보다 훨씬 더 좋은 결과를 얻을 수 있는데,이는 GPU에서 훈련시킬 때 두시간 정도에서 하루 종일이 걸릴 정도의 양이다.

- 그리고 나중에 Atari를 실제로 학습시키려고 할 때, 작은 test environment에서 디버깅 꼭 해봐라.

이거 안하고 그냥 Atari에 때려 박았다가 잘 안되면 시간 날려먹는거니깐.

(이 ppt는 그냥 영상에서도 거의 거르다시피 함 - 알고 있거나 이해한 부분만 써놓음)

- Bellman error에서 Huber loss를 시도해 보아라. (위 식 참고)

- Double DQN을 써 보자 - 코드는 별로 안 바꿔도 되는데 성능 차이는 크게 난다.

- Learning rate scheduling은 꽤 좋다. 처음 exploration period에는 learning rate를 크게 잡아 놓아라.

이렇게 DQN에 대한 설명은 끝!

다른 강의들과는 조금 다르게 수학적으로 파고드는 것 보다 아이디어를 설명하는 강의였던 것 같다.

- 본 포스팅은 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 2강의 내용을 정리합니다.

매우 간단하게 용어 정리 및 공식만 적으므로, 자세한 내용은 강의 정리 포스팅을 보시기 바랍니다.

Markov Process : Markov한 상태를 띄는 Action / Control이 없는 random한 state들의 집합.

이를 행렬으로 나타낸 것을 Markov Chain 이라고 부른다.

Markov Reward Process (MRP) : Markov Process + Reward.

Markov Process에다가 Reward를 추가함. 

Horizon : 각각의 에피소드에 대한 time step의 개수.

Return function (Gₜ) - time step t부터 horizon까지의 reward의 discounted sum.

State Value Function (V(s)) - state s에서 얻을 수 있는 reward의 기댓값.

Discount Factor (𝛾) - immediate reward (즉각적 보상)과 future reward (미래에 얻을 보상)과의 연관관계.

0이면 연관 없음, 1이면 immediate = future

일반적으로 MRP value를 계산하는데 Dynamic Programming 방식이 사용됨. (Iterative Algorithm이라고도 함.)

Vₖ(s) = R(s) + 　∑s'∈S 𝛾P(s'|s) Vₖ₋₁(s')

(위 ppt에 더 정확하게 나와있음.)

Markov Decision Process (MDP) - MRP + Action.

이젠 Action까지 포함되어 있음.

(S, A, P, R, 𝛾)의 튜플로 표현함.

지금까지의 기호들을 설명하자면,

S는 Markov State s의 집합.

A는 actions 의 집합.

P는 각 action에 따른 dymanics/transition model. (위의 MRP / MP와 다르게 action이 포함되어 있음!)

R은 Reward function으로, 각 state와 action에 따른 reward의 기댓값.

𝛾는 Discount Factor.

Policy : 각각의 state에서 어떤 action을 취할지를 선택하는 것. (그냥 말 그대로 정책이다.)

Deterministic : 결정론적임. 취하고자 하는 행동은 무조건 일어남.

Stochastic : 무작위적임. 취하고자 하는 행동이 확률적으로 일어나거나 일어나지 않을 수도 있음.

MDP + Policy = MRP이다.

이를 활용하여, MDP의 Policy Evaluation에서도 MRP와 비슷한 공식을 응용할 수 있다.

MDP Control : optimal policy를 계산함.

이때 optimal policy는 π*(s)로 표현함.

optimal policy는 유니크한 optimal value function을 가짐.

Policy Iteration : optimal policy를 구하기 위한 Iterative Algorithm.

현재 policy가 특정 값에 수렴할 때까지 지속적으로 policy를 바꿔준다.

State-Action Value Qπ(s, a)

Qπ(s, a) = R(s, a) + 𝛾∑s'∈S P(s'|s, a)Vπ(s')

로 정의되는 함수.

Policy Improvement : Policy를 강화함.

모든 state와 action 중에서 Qπ(s,a) 값이 가장 큰 state s,action a를 구해서 그 값들을 policy로 적용시킴.

즉, Policy Iteration (PI) 는 다음과 같은 행동을 반복한다.

πᵢ의 값 V을 구한다.

그 값을 사용하여 Q(s,a)도 구한 뒤,

Policy Improvement를 사용하여 πᵢ₊₁을 구함.

이를 ||πᵢ - πᵢ₋₁||₁ > 0 일 때까지 (즉, 새로운 policy와 저번 policy의 차이가 없을 때까지) 반복함.

이러면 optimal policy를 찾아낼 수 있다!

(위 세 슬라이드는 수학적 내용임으로 설명하진 않으나, ppt를 보면 이해가 갈 것임.)

Value Iteration (VI) : Value를 활용하여 optimal policy를 구하는 방법.

V의 값이 수렴할 때 까지,

최대의 Reward가 나오는 R(s, a)와 𝛾∑s'∈S P(s'|s,a)Vπ(s') 를 더한 값을 V에 집어넣어줌.

PI와는 다르게 Policy Improvement 과정 없이 진행됨.

해석본은 아래 글에 있습니다. 여기서는 풀이만 하도록 하겠습니다.

(a) optimal action은 (최적의 action은) 어떤 state si에서든 G에 도달할 때 까지 오른쪽으로 가는 것이다 (action a0을 취하는 것이다). 이 때, 모든 state si와 goal state G에서의 optimal value function을 구하여라. [5점]

optimal value function V(s) = R(s) + 𝛾Σ s'∈S P(s'|s)V(s') 이다.

이 때, action은 무조건 오른쪽으로 가는 것이고, deterministic한 상황이기 때문에 P(s'|s) = 1이 된다. (s'의 경우의 수는 1개이다.)

이를 정리하면,

V(s) = R(s) + 𝛾Σ s'∈S V(s')

이 때, s'은 s의 바로 오른쪽 (s=G일 때는 G)가 될 것이다.

이를 사용해 goal state G에서의 optimal value function을 구해 보면,

V(G) = R(G) + 𝛾Σ s'∈S V(G)

V(G) = 1 + 𝛾 + 𝛾^2 + 𝛾^3 + ....

       = 1/(1-𝛾)             (등비급수)

V(sₙ₋₁) = R(G) + 𝛾Σ s'∈S V(s')

         = 0 + 𝛾 + 𝛾^2 + 𝛾^3 + ....

         = 𝛾/(1-𝛾)

......

V(s₁) = 0 + 0 + 0 + ... + 𝛾ⁿ + 𝛾ⁿ⁺¹ + ....

       = 𝛾ⁿ / 1-𝛾

(b) optimal policy가 discount factor 𝛾의 영향을 받는지에 대해 서술하시오. [5점]

optimal policy의 경우, 0<𝛾인 모든 상황에서는 위의 '무조건 오른쪽으로 가는' action을 취할 것이다.

하지만 𝛾=0인 경우엔 0<𝛾인 경우와 비슷하게 무조건 오른쪽으로 가는 action만을 취하겠지만, 그 policy 말고 다른 policy 또한 optimal policy가 될 수 있다.

(오른쪽 왼쪽 오른쪽 오른쪽 오른쪽 .... 도 optimal policy라 할 수 있다.)

(c) 모든 reward 에 상수 c를 더한다고 생각해보자. (즉, G에서는 reward 1+c를, 나머지 state에서는 reward c를 받는다.)

이 때, 모든 si와 G에 대한 새로운 optimal value function을 구하시오. 상수 c를 더한 것이 optimal policy를 바꾸는가? 답을 설명하시오. [5점]

영향을 끼치지 않는다.

직관적으로 보자면, 어떤 상수 c를 더한다고 해도 결국 reward가 가장 큰 것을 G일 것이므로,

optimal policy는 언제나 오른쪽으로 가는 action을 취하는 policy이라는 점은 변하지 않는다.

optimal value function을 구하면,

c를 더한 V(s)를 new_V(s), 원래 V(s)를 old_V(s)라 할때,

new_V(s) = old_V(s) + c + 𝛾c + 𝛾^2c + .... 

            = old_V(s) + c/(1-𝛾)

(d) 모든 reward에 상수 c를 더하고 상수 a를 곱한다고 해보자. (new_r = a * (c + old_r))  이 때 모든 si와 G에 대한 새로운 optimal value function을 구하여라. 이것이 optimal policy에 변화를 주었는가? 답을 설명하고, 만약 '그렇다'고 답했다면 optimal policy를 바꾸는 a와 c의 예시를 드시오. [5점]

우선 위의 방식으로 optimal value function을 구하면,

new_V(s) = a * (old_V(s) + c + 𝛾c + 𝛾^2c + .... )

            = a * old_V(s) + ac/(1-𝛾)

가 된다.

이 때 a>0이라면 optimal policy는 원래와 같이 goal state G로 곧장 가는, 무조건 오른쪽으로만 가는 policy가 될 것이다.

a=0이라면, 모든 reward가 0이 되므로 모든 value function과 policy가 optimal 해 진다. (바람직하진 못하겠지만)

a<0이라면, goal state G가 가장 낮은 reward를 갖게 되므로, goal state G를 거치지 않는 모든 policy는 모두 optimal policy가 될 것이다. (즉, G를 지나는 policy는 optimal 하지 못하다.)

또한, c의 값은 어떻게 변해도 아무런 영향을 끼치지 않는다.

Assignment 1 중에서 가장 쉬운 난이도 문제였습니다.

Value function의 공식을 알고 있는지,

Optimal policy와 Optimal value function의 개념을 알고 있는지,

그리고 value function의 공식을 응용할 수 있는지에 대해 묻는 문제들이었습니다.

사실상 공식에 대입하는 문제였네요 ㅎㅎ

- 본 포스팅은 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강에서 보도록 하자.

수고링 ㅎ

CS234의 Assignment1의 해석입니다.

사실 풀이까지 쓰려고 했는데, 학교에다가 노트를 두고오는 바람에... 풀이는 나중에 사진으로 대체하겠읍니다..

한번 풀어보시기 바랍니다. 재밌음 ㅎㅎ

아래 Assignment의 pdf와 코딩 문제의 파일은 CS234 assignment 페이지 (http://web.stanford.edu/class/cs234/assignment1/index.html) 에서 다운로드 받을 수 있습니다.

1. Figure 1에 있는 간단한 n-state MDP를 보자. State s1에서 시작하는 Agent는 어떤 state si에서도 오른쪽 (a0) 또는 왼쪽 (a1)으로 가는 action을 취할 수 있다. 모든 Action은 deterministic(결정론적)이고, 언제나 성공한다. (가령 s2에서 왼쪽으로 가면 s1으로 가고, s1에서 왼쪽으로 또 가면 s1 자신으로 돌아온다.) State에서 Action을 취함으로써 Reward를 취할 수 있다.  goal state G에서 취한 모든 Action은 r(reward) += 1 을 얻고, G에 머무른다. 그 외의 나머지 행위는 reward 0을 얻는다. discount factor ᵞ < 1 이라고 가정한다.

(a) optimal action은 (최적의 action은) 어떤 state si에서든 G에 도달할 때 까지 오른쪽으로 가는 것이다 (action a0을 취하는 것이다). 이 때, 모든 state si와 goal state G에서의 optimal value function을 구하여라. [5점]

(b) optimal policy가 discount factor ᵞ의 영향을 받는지에 대해 서술하시오. [5점]

(c) 모든 reward 에 상수 c를 더한다고 생각해보자. (즉, G에서는 reward 1+c를, 나머지 state에서는 reward c를 받는다.)

이 때, 모든 si와 G에 대한 새로운 optimal value function을 구하시오. 상수 c를 더한 것이 optimal policy를 바꾸는가? 답을 설명하시오. [5점]

(d) 모든 reward에 상수 c를 더하고 상수 a를 곱한다고 해보자. (new_r = a * (c + old_r))  이 때 모든 si와 G에 대한 새로운 optimal value function을 구하여라. 이것이 optimal policy에 변화를 주었는가? 답을 설명하고, 만약 '그렇다'고 답했다면 optimal policy를 바꾸는 a와 c의 예시를 드시오. [5점]

이번 문제에서는 value iteration을 사용하여 optimal policy를 찾을 때 사용할 steps의 갯수를 제한하는 예시를 들 것이다. Figure 2에 나오는 discount factor ᵞ < 1 인 infinite MDP를 보자. 이 MDP는 state 3개로 구성되어 있고, state에서 action을 취할 때 reward를 얻는다. state s0에서 a1의 Action을 취하면 0의 reward를 얻은 뒤 s1으로 이동하고, 그 이후의 모든 action에 대해 r = +1을 얻는다. state s0에서 a2의 Action을 취하면 s2로 이동하고 즉시 ᵞ^2 / (1-ᵞ) 의 reward를 얻지만, s2는 그 이후의 모든 action에 대해 r = +0을 얻는다.

(a) time step t=0인 state s0에서 action a1을 취할 때, 최종 discounted return (위 수식 참고)은 무엇인가? [5점]

(b) time step t=0인 state s0에서 action a2를 취할 때, 최종 discounted return (위 수식 참고)은 무엇인가? optimal action은 무엇인가? [5점]

(c) 모든 state의 value를 0으로 초기화 했다고 가정하자. value iteration은 위의 수식 (n* ≥ log(1-ᵞ)/logᵞ ≥ 1/2 * log(1/1-ᵞ) * 1/(1-ᵞ)이 성립할 때 까지 sub-optimal action을 선택하는데, 이를 증명하여라.

따라서, value iteration은 1/(1-ᵞ)보다 빠르게 증가한다. (첫 번째 부등식이 옳다는 것만 보이면 된다.) [10점]

finite MDP M = <S, A, T, R, ᵞ> 가 있다고 생각해보자. (S = state space, A = action space, T = transition probability, R = reward function, ᵞ = discount factor이다.)

Q* 을 optimal state-action function인 Q*(s, a) = Qπ*(s, a) (이 때, π*는 optimal policy이다.) 라고 정의하자.

또, ||x||∞ = max(|x(s, a)| 일 때 Q* 의 예측값인 Q˜을 가지고 있다고 가정하자. (이 때 Q˜는 l∞ norm ||Q˜ - Q*||∞ ≤ ε으로 제한되어 있다.)

만약 Q˜에 대한 greedy policy, π(s) = argmaxₐ∈AQ˜(s, a)를 따른다고 가정하자. 이 때, 우리는 다음을 보이고 싶다: Vπ(s) ≥ V*(s) − 2ε / (1 − γ)

(이 때 Vπ(s)는 π에 대한 greedy policy를 따르는 value function이고,  V*(s) = maxₐ∈AQ*(s, a)는 optimal value function이다.)

이것은 만약 우리가 거의 optimal한 state-action value function을 계산하여 그 대략의(approximate한) state-action value function에서 greedy policy를 뽑아낸다면, 그 policy는 실제 MDP에서도 잘 작동한다는 것을 보여준다.

(a) π*가 optimal policy이고 V*이 oprimal value function이라고 하고, 위에서 정의했듯 π(s) = argmaxₐ∈AQ˜(s, a)라고 하자. 모든 state s∈S에서 다음의 부등식, V*(s) − Q*(s, π(s)) ≤ 2ε을 만족함을 보여라. [10점]

(b) part 1의 결과를 사용하여, Vπ(s) ≥ V*(s) − 2ε/(1−γ)임을 증명하라. [10점]

이렇게, 위의 범위가 성립함을 보였다. figure 3에 나온 2-state MDP를 고려하자. 이 MDP의 state1은 두 가지 action이 가능하다. 첫 번째 action은 reward 0을 얻고 다시 자기 자신의 state s1으로 돌아로는 action이고, 두 번째 action은 reward 2ε를 얻고 state s2로 가는 action이다. state s2는 추후의 모든 time step에 대하여 reward 2ε를 얻으며 자기 자신으로만 갈 수 있다. (어떤 action을 취해도 reward 2ε를 얻고 state s2로 돌아온다.)

(c) 모든 state에 대하여, optimal value function V*(s)를 구하고, state s1와 각각의 action에 대한 optimal state-action value function Q*(s, a)를 구하여라. [5점]

(d) π(s) = argmaxₐ∈AQ˜(s, a)일 때, Vπ(s1) − V*(s1) = −2ε/(1−γ)를 만족시키는, (l∞ norm으로 측정된) ε error를 갖는 대략적의 state-action value function Q˜이 존재함을 보여라. (일관적인 tie break rule을 정의해야 할 수도 있다.) [10점]

이제 OoenAI Gym을 사용하여 Frozen Lake environment에 대한 value iteration과 policy iteration을 구현할 것이다.

starter code 에 이 environment의 custom version을 제공하였다. (최상단의 링크에서 다운로드 가능)

(a) (코딩 문제) vi_and_pi.py를 읽고, policy_evaluation, policy_improvement, policy_iteration을 구현하라.

maxₛ |old_V(s) - new_V(s)|로 정의되는 stopping tolerance는 10⁻³이고, γ=0.9이다. optimal value function과 optimal policy를 return하여라. [10점]

(b) (코딩 문제) vi_and_pi.py에서 value_iteration을 구현하여라. stopping tolerance는 10⁻³이고, γ=0.9이다. optimal value function과 optimal policy를 return하여라. [10점]

(c) 각각의 방법 (vi와 pi)를 Deterministic-4x4-FrozenLake-v0과 Stochastic-4x4-FrozenLake-v0의 environment에서 실행시켜 보아라. 두 번째 environment에서, world의 dynamics는 무작위적이다. (world가 어떻게 움직이는지 랜덤이라는 뜻이다.) 이 무작위성은 반복의 횟수와 policy의 결과에 어떤 영향을 미치는가? [5점]

이해가 잘 되지 않는 부분이 있거나, 혹시라도 제가 잘못 해석한 부분이 있다면 댓글로 시정 요청 부탁드립니다.

(풀이는 나중에 올리도록 하겠습니다!)

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

CS234 2강의 주요 내용은

- Markov Process (+ Markov Chain)

- Markov Reward Process (MRP)

- Markov Decision Process (MDP)

- Policy Iteration (PI)

- Value Iteraion (VI)

등이 있습니다.

Markov Process

Markov 한 상태를 띄는 랜덤한 State들.

Action도 없고, Reward도 없는 상태이다.

S는 states의 유한집합이고,

P는 현재 state s에 대해 다음 state s'를 나타내는 dynamics/transition model이다.

+ P는 그냥 모델이라는 뜻으로 받아들이면 된다. 단, 원래 모델에서의 정의와는 달리 다음 state인 st+1이 action에 영향을 받지 않고 이전의 state만의 영향을 받는다.

그리고, 이것을 Matrix로 하여 나타낸 것이 Markov Chain이다.

(아래쪽에 있는 Matrix)

Markov Reward Process (MRP) - Markov Process에 reward를 추가함.

S,P의 정의는 같고,

R는 reward function인데,

reward function은 현재 state에 대한 reward의 기댓값을 표현하는 함수이다.

ᵞ(감마)는 [0,1]의 범위를 갖는 discount factor이다.

discount factor는 현재 얻을 수 있는 immediate reward와 나중에 얻을 수 있는 reward간의 차이를 의미한다.

(나중에 더 자세히 나옴)

여기서도 Markov Process와 같이 Action은 없다.

Horizon : 각각의 에피소드에 대한 time step의 개수.

Agent나 Process의 time step의 개수.

horizon이 무한하지 않으면 finite Markov reward process라고 불리지만,

많은 경우 무한하다.(infinite)

가령, 주식 시장은 오늘도 열리고 내일도 열리고 모레도 열리고 .... 하는 식이다.

(그러니까 여기서 말하는 infinite는 엄밀한 정의의 infinite가 아니라, 그만큼 엄청 많아서 무한하다고 불러도 될 정도를 의미한다. 주식 시장은 사실상 우리가 살아있는 동안은 열려 있지 않겠는가? 그런 식이다.)

Return function (Gt) - time step t부터 horizon까지의 reward의 discounted sum.

즉, 지금부터 이 process가 끝날 때까지 (horizon이 무한하다면 그냥 앞으로 쭉)의 reward에 discount factor ᵞ를 곱한 값의 합.

State Value Function (V(s)) - state s에서 얻을 수 있는 reward의 기댓값.

참고로, 위 수식은 앞으로 계속 나오므로 잘 숙지해 둬야 한다!

Return function은 실제로 얻는 reward를 의미하고, Value Function은 그 reward의 기댓값이므로, 서로 다를 수 있다.

(물론, Deterministic한 경우엔 같을 수도 있다.)

위의 수식을 보면 알겠지만, V(s)는 state s일 때의 Gt의 기댓값으로 나타낼 수 있다.

Discount factor은 immediate reward (즉각적 보상)과 future reward (미래에 얻을 보상)과의 연관관계를 나타낸다.

[0, 1]의 범위 안에서, ᵞ = 0이면 future reward 무시, ᵞ=1이면 immediate reward = future reward란 의미를 가진다.

이때 ᵞ를 사용하는 것은 infinite 한 value를 피할 수 있으므로 수학적으로 용이하지만,

horizon이 finite한 경우에는 ᵞ=1을 사용해도 어차피 infinite한 value는 나오지 않으므로 ᵞ=1을 사용할 수 있다.

s1일때 reward 1, s7일때 reward 10, ᵞ=0.5라고 하자.

s4에서 시작해서 s5,s6,s7으로 가면

V(s)의 수식대로 갔을 때,

V(s) = 0 + 0.5 * 0 + 0.25 * 0 + 0.125 * 10 = 1.25

가 된다.

(이해가 안되면 저 위에 있는 V(s)의 공식을 보고 오라.)

그 외의 경우는 위의 ppt를 보며 직접 확인하면 될 것 같다.

V = [1.53 0.37 0.13 0.22 0.85 3.59 15.31] 은 각각의 s값에 대한 V(s)의 값이다.

MRP를 계산하는 방법은 크게 세 가지가 있다.

그 중 첫번째가 simulation인데,

그냥 하나하나의 경우의 수를 다 해보는 것이다.

(s4, s5, s6, s7의 경우, s4,s4,s5,s4의 경우 등등 그냥 죄다 해보면서 확률적으로 값을 도출한다는 뜻.)

두 번째 방법은 수학적인 방법이다.

finite state MRP의 경우, V(s)를 Matrix 연산으로 표현 가능한데,

V(s1, s2, ..., sn)은 각각의 state의 Reward (immediate reward)에 가능한 모든 경우의 수 (Markov Chain)에 Discount factor ᵞ를 곱하고, 거기에서 각각의 V(s1, s2, ..., sn)의 값을 또 곱한 것으로 표현이 된다.

(여기서 다시 곱하는 V(s1, s2, ..., sn)은 action을 취한 이후의 지점의 s값을 따른다. 밑의 예시를 참고하자.)

가령, 위의 Mars Rover MRP의 예시를 가져온다면

ᵞ가 0.5일때, 

V(4)는 ᵞ(0.5)에다가 s4가 취할 수 있는 모든 경우의 수인 가만히 있기 (0.2), 왼쪽으로 가기 (0.4), 오른쪽으로 가기 (0.4)를 곱하고, 그 각각의 state의 V(s)를 곱해준다. (V(3), V(4), V(5))

더 자세한 예시는 밑에 나온다.

세 번째 방법은 Dynamic Programming이다.

k=1부터 시작해서, 모든 s에 대하여

Vk(s) = R(s) + 　∑ᵞP(s'|s)Vk-1(s')를 계산해준다.

(이를 |Vk - Vk-1| < ε(엡실론, 그냥 아주 작은 특정 값) 일때 까지 반복한다.)

(그냥 저 V(s)의 공식을 다이나믹 프로그래밍으로 계산한다는 뜻이다.)

Markov Decision Process (MDP) : Markov Reward Process (MRP) + action

즉, MDP란 MRP에 action이 추가된 최종 진화형이다.

이게 어차피 Markov 변화의 마지막 형태이니까 기호를 하나씩 다시 써보면...

S는 Markov State s의 집합.

A는 actions 의 집합.

P는 각 action에 따른 dymanics/transition model. (위의 MRP / MP와 다르게 action이 포함되었다.)

R은 Reward function으로, 각 state와 action에 따른 reward의 기댓값이다.

그래서, MDP는 이 S,A,P,R과 discount factor ᵞ를 포함한 튜플 (S, A, P, R, ᵞ) 로 표현 가능하다.

위의 사진은 MDP에서의 P의 예시이다.

a1은 왼쪽으로 갈 확률이 1인 (즉, 무조건 왼쪽으로만 가는) action의 집합이고

a2는 오른쪽으로 갈 확률이 1인 (즉, 무조건 오른쪽으로만 가는) action의 집합이다.

Policy : 각각의 state에서 어떤 action을 취할지를 선택하는 것. (그냥 말 그대로 정책이다.)

결정론적(deterministic)일 수도, 확률적(stochastic)일 수도 있다.

Policy는 π(a|s) 이고, 이는 P(at = a | st = s) 와 같다.

그리고, MDP + π(a|s)는 Markov Reward Process 로 유도할 수 있다.

(정확히는, MRP(S, Rπ, Pπ, ᵞ) 로 유도할 수 있다.)

왜냐하면, π(a|s) 그 자체로 어떤 action을 취할지 알려주는 것이므로,

결국 π(a|s)만 알면 그 policy에 대한 reward의 기댓값 Rπ도 도출되고,

취할 행동의 distribution인 Pπ도 도출되는 것이다.

MDP는 MRP에서 R과 P를 Action에 관한 것으로 변경한 것이고,

policy는 각각의 state에 따른 action을 mapping 한 것이므로 (action을 대체 가능하다.)

MRP에서 R, P를 각각 Rπ와 Pπ로만 바꿔주면 되는 것이다.

이 성질은 추후 evaluation을 할 때 MDP가 아닌 MRP만 사용하면 되게 해주는 장점을 갖는다.

즉 위의 MDP + π(a|s) = MRP라는 성질을 사용하면

아까 저기 위에 있던 MRP의 Dynamic programming 수식을 조금만 바꾸어서,

Policy에 대한 V(s)를 구할 수 있게 된다.

(수식 참고)

위의 경우를 보자.

Mars Rover (로봇) 은 왼쪽 또는 오른쪽으로만 갈 수 있다.

s1에 Mars Rover가 위치하면 reward +1, s7에 Mars Rover가 위치하면 reward +10을 주고,

그 외의 나머지 경우에는 reward는 0이 주어진다.

π(s)는 모든 state에 대하여 a1이고 ᵞ=0이라고 했을 때,

Dynamic Programming 방식을 기용한다면 policy의 value는 무엇일까?

답은, s1과 s7에 있을 때를 제외하면 죄다 0이고,

s1에 있을 때는 1, s7에 있을 때는 10이다.

어차피 ᵞ = 0이므로 위의 v(s) 의 식의 ᵞ의 뒤에 있는 식들은 죄다 날라가고,

π(s) 당시의 reward, 즉 immediate reward만 합해주면 되므로

s1에 있을 땐 1, s7에 있을 땐 10이다.

두 번째 문제이다.

P(s6 | s6 , a1) = 0.5, P(s7 | s6,a1) = 0.5 이고,

reward는 위와 같을 때,

π(s) 가 언제나 a1을 취하고 k=1, ᵞ=0.5일때 π(s6)의 reward는?

아까 전의 MRP로의 식을 사용하면 된다.

우선 immediate reward는 0이다. (s6의 reward는 0이므로...)

그리고, P(s6 | s6 , a1) = 0.5, P(s7 | s6,a1) = 0.5이고 ᵞ=0.5이므로 최종 계산식은

0 + ᵞ * 0.5 * v(s6) + ᵞ * 0.5 * v(s7)

= 0 + 0.5 * 0.5 * 0 + 0.5 * 0.5 * 10

= 2.5

가 된다.

MDP Control은 optimal한 policy를 compute한다.

즉, Vπ(s)가 최대가 되는 π의 값을 구하는 것이다.

그리고, optimal한 value function은 언제나 unique 하다. (교수님이 이 부분은 설명을 안하고 넘어가셨다.. 중요하다고만 하심)

아까 전의 Mars Rover의 예시를 다시 가져오자.

states는 s1부터 s7까지 7개의 state가 있고, action은 왼쪽 또는 오른쪽 두 가지만 있다.

이 때, deterministic한 policy는 몇개인가?

ppt에 적혀있듯, 2^7개이다.

(각각의 action 2개가 각각의 state에서 실행 가능하므로)

그리고 이 이후의 예제에서도,

action의 개수 A와 state의 개수 S에 대하여 가능한 policy의 개수는 A^S개이다.

그리고, MDP의 optimal policy는 언제나 unique 한가?

위의 ppt에서 적혀있듯, No 이다. 만약 다른 Policy 두개의 Value가 모두 optimal value function의 값이 된다면,

이 Policy들 모두 optimal policy가 된다.

Policy Search : Optimal한 policy를 찾는 과정.

Policy Iteration은 이의 한 종류이다.

i=0으로 설정하고, π0(s)를 랜덤한 값으로 설정한 뒤 시작하는데,

i==0 or |πi - πi-1| >0일 때 반복한다.

(시작할때와 policy가 바뀌고 있을 때 반복한다.)

그런데, 이것을 제대로 하려면 일단 Policy Improvement가 뭔지 알아야 한다.

일단, PI에 들어가기 전에 먼저 Qπ에 대해 알아보자면,

Qπ(s, a) = R(s, a) + ᵞΣP(s'|s, a)Vπ(s') 이다.

이는 Vπ(s , π(s|a)) 에서 R(s, π(s))를 R(s, a)로 바꿔준 식으로,

일단은 Policy를 따르지 않고 action a를 취한 후에

그 뒤에 policy를 따르겠다는 뜻이다.

그리고, Qπi(s, a)를 모든 State의 s, 모든 Action의 a에 대하여 compute한 뒤에, 

모든 State에 대하여 Qπi(s, a)가 최대가 되는 π를 찾는다.

자, Qπi(s, a)는 π(s|a)를 그대로 따르는 것이 아니라 각각의 State에서 가능한 모든 Action을 취하는 것이므로...

Qπi(s, a)의 값들 중 최소한 하나는 π(s|a)보다 크거나 같을 것이다.

(각각의 State에서 가능한 모든 Action은 π(s|a)에서 취한 행동도 포함하므로, 무조건 같은 것 하나는 나오게 된다.)

그리고, 이것을 πi+1에 넣어준다.

이것을, Policy Improvement라고 한다.

그러면, 이제 위에서 무슨 말을 하는지 이해가 될 것이다.

| πi - πi-1 | == 0이라는 것은 결국 πi가 optimal 하다는 뜻이므로 |πi - πi-1| > 0 일때 동안 반복하는 것이고,

그렇게 나온 πi+1로 policy improvement를 해주고, i++을 해준다.

(이렇게 해도 이해 안되면 강의 보쉬던지... 깔깔!)

조금 더 깊게 파고들자면,

Qπi(s, a)의 Max값은 R(s, Vi(s)) .... (이하 Vπ(s))보다 언제나 크거나 같다.

그리고, πi+1(s) 는 Qπi(s, a)의 최댓값을 보장하는 a를 의미한다. (즉, 더 나은 policy가 된다.)

그리고는, 이 이후에는 πi+1을 가져가고, πi는 버린다.

πi+1은 언제나 πi보다 낫거나 같기 때문이다.

즉, 모든 State s에 대해 Vπi >= Vπ2 : Vπ2(s) >= Vπ2(s)라는 이야기이다.

이를 증명 하자면...

위의 수식처럼 된다.

약간 참고만 하라고 첨언하자면,

πi+1 = argmax(a)Qπi(s,a) 이다.

그리고 주목해야할 부분은 두번째줄에서 세번째 줄로 넘어가는 부분인데,

Vπi(s) <= max(a) Qπi(s, a)이므로, 

Vπi(s') <= max(a) Qπi(s', a) 이라는 점에서 두 번째 줄에서 세 번째 줄로 넘어갈 수 있다.

이를 계속 반복하다 보면, 결국 Vπi(s) <= Vπi+1(s) 라는 식이 나오게 된다.

(증명은 알아서 이해할 수 있도록 하자 ㅎ)

위 ppt의 조건대로라고 했을 때, (Policy Iteration을 사용할 때)

만약 Policy가 한번 바뀌지 않으면 앞으로도 바뀌지 않는가?

PI에서 최대 반복 횟수가 있는가?

답은 위에서 확인하도록 하자. (설명도 잘되어 있다.)

첫 번째 질문에 대한 comment만 달자면, 한번 Policy가 바뀌지 않으면

| πi - πi+1 | == 0이 되므로

더이상 Policy Iteration이 진행되지 않는다.

그러므로, Policy도 더이상 변하지 않는다.

다음은 Value Iteration이다.

위의 Policy Iteration과 비슷하다고 느껴질 수 있지만, 조금 다른 방식이다.

V0(s)를 0으로 초기화 한 뒤에,

V가 어떤 값으로 Converge 될때 까지 (수렴할때 까지), 또는 horizon이 끝날때 까지

Vk+1(s) = max(a) R(s, a) + ᵞΣP(s'|s, a)Vk(s')

을 반복한다.

풀어 말하자면, 각각의 time step에 대해서 최선의 선택만을 가지고 가는 것이다.

이는 원래 Policy를 랜덤으로 취한 뒤 policy를 가장 좋은 것으로 바꾸어 가는 Policy Iteration과는 다른 방식으로,

처음의 time step 0으로 시작해서, 모든 state에서 가능한 최선의 action만을 취해서 Policy를 만들어 가는 것이다.

그리고, Value Iteration은 수렴하는가? 에 대한 답은 YES이다.

결국 V(s)의 값에는 지속적으로 ᵞ가 씌워지므로,

Horizon이 무한하더라도 1보다 작은 ᵞ값을 무한정 제곱하여 더하는 꼴이 되므로

일정한 값에 수렴하게 된다.

Value Iteration과 Policy Iteration간의 차이점을 설명하자면,

Value Iteration은 time step (horizon) = k일 때의 optimal value를 찾아가며 k를 증가시키는 형식이고,

Policy Iteration은 infinite한 horizon에서 더 나은 policy를 찾아가는 형식이다.

이 Policy Iteration은 RL에서 매우 유명한 Policy Gradient라는 방식과 매우 유사하다.

여기까지 CS234 2강을 정리하도록 하겠다.

사실 그냥 간단한 정리노트만 쓰려고 했는데, 어찌어찌하다 보니 뭔가 강의 형식이 되어 버렸다.

그냥 정리 노트와 강의를 합쳐버리는 게 나을지도 모르겠다.