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에 대한 더 많은 이야기들을 해 보도록 하겠다.

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

안녕!