현실에 있는 큰 문제를 풀기 위해 table lookup 방식이 아닌 Lecture 6에서 FA를 통해 value fn를 학습하였고, 이번 단원에서는 동일한 조건인 big scale model-free 상황에서의 policy를 찾는 방법을 배울 것이다.
Policy Gradient의 개요 + 장단점과 세가지 심화되는 접근 방법
- 지난 시간엔 state value fn인 V(s)와 action value fn인 Q(s,a)를 파라미터들을 Gradient discent로 update하는 방식으로 학습했다.
- value fn를 이용해서 e-greedy 방식으로 만들어진 policy였다. == value fn만 존재하고 policy는 없었다.
- 이번 시간에는 직접적으로 policy를 parametrise한다. == policy를 파라미터 방식으로 표현
- 우리는 model-free RL에 초점을 둘 것이다.
- value-based
value fn를 직접적으로 함수로 표현했고 파라미터들을 update해서 그 함수가 정확한 value fn를 return하도록 학습(e-greedy와 같은 value fn를 이용한 policy making)
- policy-based
아예 value fn를 학습하지 않고, 바로 policy를 수정하는 방법을 학습
- Actor-Critic
위 두 value fn, policy를 같이 수정 시키면서 agent가 움직이며 학습, actor는 움직이는 policy, Critic은 평가하는 value fn
Policy-Based Advantages
- 수렴하는 성질이 훨씬 좋다.
- high-dimensional or continuous action spaces(무한한 action 수로 인해 deterministic한 대입이 불가능한) 상황에서 효과적이다.
- value based 방법은 deterministic policy만 학습 가능했지만 policy based에서는 stochastic policies를 학습 가능하다.
Policy-Based Disadvantages
- Global보다는 local optimum에 빠지기 쉽다.
- policy를 학습하는데 variances가 크고, 비효율적인 것이 있을 수 있다.
"value based는 max를 취해버리기 때문에 aggressive한 방법론"
"policy based는 gradient만큼 파라미터를 미세하게 update하기 때문에 stable한 방법론"
Stochastic policy가 좋은 상황 예시들
반복해서 계속하는 가위바위보
ex) deterministic policy로 항상 내는 모양이 정해져있는 고정된 패턴 => policy를 쉽게 찾을 수 있음
ex) uniform random policy로 내는 모양이 1/4인 패턴 => 간파가 불가능 Nash Equilibrium(평형) 상태로 나와 상대가 그 전략을 썼을 때 서로 바꿀 요인이 없어서 평형에 이루는 관계에 도달하여 최적화됨
uniform random에서 policy를 찾기 위해서 policy based가 필요하다.
해골에 빠지면 죽고 금에 도달하면 성공하는 env를 보면 현재 MDP를 fully observable한 상태
partially observable한 상태로 가정: state를 구분하는 feature를 생성해도 state의 완전한 표현이 불가능한 상황
ex) 내 (N, E, S, W)에 벽이 있으면 1, 없으면 0 feature
- 회색칸은 feature로 서로 구분이 불가능하다. feature가 아직 완전하지 않기 때문에 fully known MDP가 깨지는 상황
- deterministic policy: 두 회색칸을 같은 state 이라고 생각하고 같은 output을 도출하므로 금에 도달하지 못하는 케이스 발생
- value based RL은 deterministic policy(greedy or e-greedy)를 학습하기 때문에 불필요한 무한 Loop가 발생한다.
- stochastic policy: 양쪽으로 가는 policy가 있다면 몇 step만 밞으면 금에 도달 가능
Q: 3장에서 항상 언제나 deterministic policy가 존재한다는 정리는? Markov property + fully observable 한 상황에서는 정리가 성립
- Goal: 어떤 파라미터 θ에 대해서 action a를 할 확률을 뱉어주는 함수 policy Piθ를 어떻게 update 하는게 좋은 Pi인가?
J(θ)(Maximise하고자 하는 목적함수)를 구하는 것 : policy를 따랐을 때, 총 reward인 value fn를 더 많이 받는 policy
- episode env(한 에피소드로 종료되는 환경)에서는 start value를 사용 가능하다.
start value: 처음 state는 정해져있다고 생각하고 이 state에서 시작했을 때, policy로 끝까지 episode를 진행하면 얼마의 reward를 받을지 == pi를 따랐을 때의 value fn 기댓값
첫 state는 하나여도 되고, 고정된 분포(start state의 여러개의 분포)도 가능함
- continuing env에서는 average value를 사용 가능하다.
d^piθ(s) stationary distribution: markov chain에서 policy를 따라서 무한히 움직이다보면 각 state 별로 머무는 확률분포 d^pi(s)가 일정 확률로 수렴
average value: 각 state에 있을 확률 * state에서의 value 의 총합 == 평균 value 기댓값
average reward per time-step: d^pi(s)에 대해서 각 state에서 policy로 action을 하고 그때 얻는 reward들을 pi의 확률 가중치를 곱해서 더하고 state distrbution 가중치를 곱해서 더함 == 그 state에서의 one step에서 기댓값
결국 3개다 value를 최대화하기 위해 하는 동작이고 목적함수인 J(θ)를 정의한 표현
- optimisation: 임의의 함수에서 주어진 정의역 안에서 최대화 하는 input x를 찾는 최적화 문제
- Policy based RL의 목적은 목적함수인 J(θ)에서의 input θ를 찾는 과정
policy가 θ로 parameterize 되어 있(pi가 θ로 표현된 함수)이므로, θ가 policy를 정해주고 θ가 바뀌면 policy가 바뀌고 policy가 바뀌면 얻는 reward가 바뀌며 결국 J(θ)가 바뀌게 된다.
- Gradient를 안쓰는 방식: hill climbing, simplex / amoeba/ nelder mead, genetic alghrithms
- Gradient를 쓰며 훨씬 효과적인 방식: gradient descent, conjugate gradient, Quasi-newton
- 우리는 gradient descent를 사용하며 많은 sequential structure를 이용하는 방식들에 대한 확장과 같은 것들이 가능하다.
- 어떤 목적함수 J(θ)가 있어서, J에 대한 gradient를 구할 수 있는 상황으로 만든다. policy pi는 우리가 정한 함수이므로 우리가 gradient를 적용 가능한 함수로 정하면 됨
- J에 대한 gradient를 구해서 θ를 바꿨을 때 J가 가장 급격하게 변하는 방향으로 a만큼 update 해주는 방식
저번 시간에는 error를 minimize하는 문제, 이번 시간에는 J를 maximize하는 문제
- J에 대한 gradient를 구하면 다음과 같은 vector(각 칸에 대해서의 편미분)이 나온다. policy gradient: ▽θJ(θ)
policy gradient는 pi에 대한 gradient가 그 과정에서 쓰일 수는 있지만, pi에 대한 gradient가 아닌 J에 대한 gradient를 구해서 J를 최대화 하는 것이 목적 == J에 대한 gradient를 구해야 한다
Finite Differences θ1~θn
- policy gradient를 계산하기 위해서
예를 들어 θ1이 1이었는데 1.01을 넣으면, θ1에 대한 편미분(기울기값)을 계산 가능(0.01만큼 바뀌었을 때 J가 얼마나 바뀌나) => θ2 값도 미세하게 바꾸고, 바꾸기 전 J을 알기 때문에 그 차이로 분모 분자를 나누면 θ2 편미분(기울기 값) 계산 가능 => 이 과정을 n번 반복하면, 길이 n인 vector인 gradient가 계산
- n dimension의 policy gradient의 값을 구하기 위해서는 n번 evaluation이 필요하다. policy를 가지고여러번 해서 평균내는 값이므로 비용이 상당히 비쌈
- 단순하지만, evaluation을 많이 가져갈 수 없기 때문에 noisy하고, 비효율적 - 그러나 때때로 효과적이다.
- policy가 differentiable하지 않아도 사용 가능, poilcy에 대해서 바꾼 값만 넣으면 미분 가능하지 않아도 update의 방향성을 유추가능
weight가 1백만개 있다고 가정하면, 1번 update하기위해 1백만개 evaluation이 필요함, 매우 비효율적
매우 바보같은 1번 방법론이므로 현재는 거의 쓰이지 않음
- 12개의 파라미터(dimensions)로 AIBO walk에 finite difference policy gradient 적용을 통한 학습이 가능했다.
~게 있다고 함
- policy를 수학적으로 접근을 할 것이다.
- policy pi가 항상 differentiable하고, pi에 대한 gradient를 안다고 가정한다.
- Likelihood ratios trick를 사용한 수식 뒤에서 좀 더 쉬운 꼴로 사용하기 위해 변환
pi에 대한 gradient에 분모 분자에 pi를 곱하고
gradient pi/pi = gradient log pi(dx/x = d log x과 같은 원리로 log x를 미분하면 1/x인 것을 이용, x자리에 pi가 들어감)
d log x/dx = 1/x 이므로 dx를 양쪽에 곱해주면, d log x = dx/x
- score function: gradient log pi
- one-step MDP: 어떤 분포를 따르는 initial state s에서 시작해서 one-step가서 reward 받고 끝남
ex) 카지노의 10개의 vending machine 중 어느 머신에서 돌릴지 확률이 존재하는 MDP에서의 policy gradient 계산 목적
J(θ)[3번째 정의] 각각의 initial state 분포의 확률 * 그 state에서 어떤 action를 할지 확률* 그때의 reward
- s에서 a를 했을 때, 어느 state에 가고 어느 reward를 받을 지 모르는데 R은 실제 action(sample)을 했을 때 받는 값, s에서 같은 a를 해도 다른 output이 나올 수 있다는 것이 중요
θ를 update하기 위해서는 J를 미분해야하기 때문에 미분 =>
d는 θ와 관련 없는 함수이므로 pi에 gradient pi가 들어가는데, gradient pi == pi * gradient log pi(Likelihood ratio trick) 따라 J에 대한 gradient는 다음과 같이 써진다 =>
pi가 앞으로 삐져 나오면서 앞부분이 expectation로 묶이고 결과적으로 gradient J가 expectation으로 표현
∴ policy pi를 따라 나온 행동 (s,a)에서 ▽θlogPiθ(s,a)를 구하고 그 값에 r를 곱해준 것이 gradient J가 된다!
각 sample들을 통해서 θ를 update가 가능해진다.
통계적 표현: gradient J에 대한 unbiased sample들을 얻고, 여러번 update하면 대수 법칙에 의해 J가 수렴하게 된다.
- Neural net에서 많이 쓰이는 형태인 sofmax policy를 example로 사용한다.
- weight는 feature(pi(s,a)Tθ)의 linear combination를 사용하며 동작한다.
- action의 확률 ∝ feature의 expotential weight에 비례한다. feature * feature weight
확률 형태로 각 action들이 표현되는 softmax policy가 있다고 가정하면 위 gradient 처럼 수식 전환이 가능
- score function: softmax에 log를 취하면 pi가 앞으로 나오면서, 분모와 분자가 계산되면서 쉽게 구해진다.
- continuous action spaces에서 Gaussian policy를 쓰는 것이 자연스럽다. score function이 구해진다.
어떤 평균이 있고, 어떤 state에서 대체로 이 action을 할 건데, variance를 줘서 다른 확률의 가능성이 있는 상태
- 이전까지 one-step MDP, likelihood ratio를 이용한 방법론을 multi-step MDP까지 일반화 시켜주는 Theorem
- one-step MDP에서의 r자리를 Q로 대체하면 J gradient로 같다.
one-step: r이 곧 cumulative reward == episode가 끝날 때까지 받은 reward의 총합
multi-step: Q가 cumulative reward == 그 step에서 a를 했을 때 얼마 받을지에 대한 총합
- J에 대한 목적함수 표현 3가지를 어느 것을 사용하더라도 가능하다.
gradient log pi * Q == score * Q
지금까지의 Q는 Oracle이 알려주었는데 우리는 Q가 없으므로 return이 Q의 unbiased sample이기 때문에 return를 사용한다.
- r이 sample이기 때문에 계속 sampling하다보면 unbiased estimate가 보장되어서 결국 평균이 Q로 간다.
gradient log pi에다가 Q자리에 return(cumulative discount reward)를 쓰게 되면 MC와 같은 방식의 pi update를 진행
- gradient J에 step-size a를 곱하여 그 방향으로 θ를 update 시킨다.
<sudo code>
θ를 임의로 초기화 => θ를 이용한 poilcy pi가 존재 => Pi로 episode 실행 뒤 첫 step부터 마지막까지 θ를 update =>
초기화 되었던 θ에 a * gradient log pi만큼 θ를 곱해주면 pi가 좀더 좋은 policy로 바뀐다 == REINFORCE Algorithms == MC policy gradient(alphaGo에 사용됨)
- 아이스 하키의 puck를 움직이는 continuous action space가 존재한다.
- target이 존재하고 가까워 질수록 reward를 받고 30초마다 target location이 바뀐다.
- Policy는 MC policy gradient를 통해 학습되었다.
1. value-based와는 다르게 learning curve가 지그재그 하지 않게 올라감 == policy-based는 θ를 조금씩 바꾸기 때문에 stable하다.
2. Iteration이 10^7 == MC와 같은 관점으로 variance가 매우 크기 때문에 느림
- MC policy gradient는 variance가 너무 높다.
- 우리는 action-value fn를 예측하기 위해 Critic 방식을 사용한다.
Qpi가 Oracle이 준 ture Q, Qw로 estimate해서 function approximate를 Q에 사용하는 것
Actor-Critic algorithms는 2 parameter set를 유지한다 == 학습 대상이 2개 Q, pi
- Critic: action-value fn parameter w를 update한다. Q는 w라는 파라미터로 표현
- Actor: Critic에 의해 제안된 policy parameters θ를 update한다. Pi는 θ라는 파라미터로 표현
- Actor-Critic algorithms는 approximate policy gradient에 기반한다.
score(gradient log pi) * Q의 기댓값 = gradient policy gradient theorem
Actor-Critic: Q자리에 return을 넣는 대신 Q를 따로 estimate해서 학습한 값을 넣는 것
Q는 어떤 pi를 따라서 진행했을 때의 기댓값이고, 따라서 Q는 pi에 종속적인데 pi가 계속 바뀜
Q 학습 pi update => pi 학습 그에 대한 Q 학습 => ... 반복
Q를 학습하는 Prediction 문제
- critic는 policy evaluation이라는 이전 단원에서 배웠던 익숙한 문제를 풀어야 한다.
- 이 문제들은 MC, TD(0), TD(lamda)를 써서 true Q를 학습해라
<Actor-Critic sudo code>
- Critic: TD(0), w로 update / Actor: policy gradient, θ로 update/ 목적: w, θ 둘다 학습하는 것
state, θ를 초기화 => θ에서 policy pi를 이용해서 action을 sample => 매 step마다, reward와 다음 state가 뭔지, 다음 state에서의 action a'을 알기 때문에, TD error(one-step 더 가서의 추측치 - 현재의 추측치)가 계산이 된다
delta: TD error이며 w를 update하는데 쓰인다. w가 Q니까 TD error에다가 beta: learning mate
결국 learning mate * TD error * (linear combination of feature의 FA를 사용해서 나온 feature)를 통해 Q로 update 함과 동시에 θ는 gradient log pi * Q로 θ를 update하고 반복
결국 내가 action a를 어떻게 θ update하는 거냐가 목적
∴ action a를 하는 확률인 gradient log pi(a를 하는 확률을 바꾸는 방향)로 만약 Q가 좋았으면 더 좋은 방향으로 바꾸고, 안좋았으면 더 안좋은 방향으로 바꾸는 것, 좋았나 안좋았냐의 지표는 Q가 제공
- policy gradient 수식에서 a를 바꾸는 방향으로 바꾸었을 때 Q가 너무 클 경우 비효율이기 때문에 baseline를 빼준다.
action 사이의 상대적인 우열을 가리는 것이 목적인데 variance가 너무 크면 계산이 너무 많다.
- 여전히 variance가 존재하기 때문에 expectation 변화 없이 더 감소시킬 수 있다.
B(s): state에 대한 함수, 상수값임
gradient log pi에 B(s)를 곱한 값 => expectation를 풀고 pi가 붙음 => likelihood ratio trick를 써서 log가 gradient pi로 바뀜 => B(s)는 a와 관련이 없기 때문에 밖으로 빼주고, Piθ(s,a)의 합이 1이기 때문에 그걸 θ로미분하면 0
원래 policy gradient에서 B(s)의 자리는 Q가 있었기 때문에, Q - B(s)(에 대한 기댓값은 0)를 해도 된다.
B(s)는 θ에 대한 일반적인 함수이기 때문에 value fn으로 선택하면 Q자리에 Q-Value fn를 넣어도 식이 성립한다.
- advantage function: Qpiθ(s,a)-Vpiθ(s) = Apiθ(s,a)를 수식에 대입해준다.
- advantage fn는 policy gradient의 variance를 눈에 띄게 줄일 수 있다.
- Critic은 advantage fn를 추정할 수 있어야 한다.
- policy 학습하기 위한 weight, Q학습하기 위한 weight, V학습하기 위한 함수까지 필요하므로 3쌍의 parameter 필요
- policy: θ, Q: w, V: v를 모두 학습하여 Q-V를 한 다음에 TD를 써서 θ, Q와 더불어 V까지 동시에 update한다.
V에 대한 parameter들 가지고 Q를 계산할 수 있기 때문에 더이상 Q가 필요가 없다.
- true Value fn Vpiθ, TD error delta^piθ
- TD error가 advantage fn의 unbiased estimate sample이다.
delta의 기댓값 => Vpiθ는 a와 관련이 없으므로 -Vpiθ로 expectation에서 나와짐 =>action a를 했을 때 받는 reward와
one-step 더 가서의 value의 기댓값: Q => Q - V: advantage fn
delta의 기댓값이 A이기 때문에 delta라는 sample들은 a의 unbiased sample이다 == delta를 계속 취하다 보면 평균은 A와 같게 된다.
결국 A자리에 delta를 넣을 수 있다 = advantage 자리에 sample인 TD error를 넣을 수 있다.
- 실제에서는 true value fn를 모방한 A가 있기 때문에 그걸 그냥 쓰면 된다.
TD error가 A의 sample이기 때문에 A자리에 학습해서 배운 TD error를 쓰면 된다.
- Q를 학습할 필요 없이 parameter v만 사용하면 된다.
- Critic과 Actor 따로 학습해야되기 때문에 Critic학습할 때 여러 방식을 쓸 수 있다.
- Critic을 different time-scales 마다 쓸 수 있다.
- 위 방식으로 학습하고 나면 Actor를 학습 할때도 different time-scales에서 가능하다.
- Actor도 여러 time-scale에서 볼 수 있으므로 TD(lamda)와 같은 개념도 가능하다.
backward-view TD(lamda)는 eligibility traces가 score에 대해 traces가 계산된다.
- policy gradient는 여러 형태가 존재한다. 각 형태별로 이름이 붙는다.
gradient를 학습하는 방법
REINFORCE: gradient log pi * return, policy-based method로 critic이 필요 없는 actor 방식
Q Actor-Critic: policy gradient theorem으로 return(MC)이 variance가 너무 커서 Q를 학습시켜서 교체
Advantage Actor-Critic: Q 또한 상대적인 차이가 중요하므로 variance를 더 줄이기 위해 Q-V=A를 사용
TD Actor-Critic: A를 쓰기 위해서 Q와 V를 모두 학습해야하므로 parameter가 너무 많이 필요해 TD error가 A의 sample이므로 A자리에 TD error를 사용, one-step만 확인가능
TD(lamda) Actor-Critic: 여러 time-scale를 고려하는 score함수에 축적되는 eligibility traces 값을 써서 TD(lamda) 사용
- stochastic gradient ascent algorithms에 위 학습방법을 이용해 gradient를 구하면 gradient ascent가 가능해진다.
- Critic 학습은 policy-evaluation방식이므로 MC던 TD던 사용하면 된다.
아래는 교재 및 참고 블로그, 유튜브 강좌입니다.
deepmind.com/learning-resources/-introduction-reinforcement-learning-david-silver
Interested in learning more about reinforcement learning? Follow along in this video series as DeepMind Principal Scientist, cre
We research and build safe AI systems that learn how to solve problems and advance scientific discovery for all. Explore our work: deepmind.com/research
deepmind.com
www.youtube.com/watch?v=2YFBordM1fA&list=LL&index=3&t=4s
'논문 리뷰 > RL' 카테고리의 다른 글
| 03. Finite Markov Decision Process (0) | 2021.03.20 |
|---|---|
| Vanila Actor-Critic (0) | 2021.03.09 |
| REINFORCE(MC-PG) + vanila Policy Gradient (0) | 2021.03.04 |
| Lecture 6: Value Function Approximation (0) | 2021.01.19 |
| Lecture 5: Model-Free Control (0) | 2021.01.18 |
| Lecture 4: Model-Free Prediction (0) | 2021.01.15 |
댓글