On-policy와 Off-policy, Policy Gradient, Importance Sampling

# On-policy : 학습하는 policy와 행동하는 policy가 반드시 같아야만 학습이 가능한 강화학습 알고리즘.

ex) Sarsa

on-policy의 경우 이론상 1번이라도 학습을 해서 policy improvement를 시킨 순간, 그 policy가 했던 과거의 experience들은 모두 사용이 불가능하다. 즉 매우 데이터 효율성이 떨어진다. 한 번 exploration해서 얻은 experience를 학습하고나면 그냥은 재사용이 불가능하다.(Importance sampling등을 해야만 재사용가능 함.)

 

 

# Off-policy : 학습하는 policy와 행동하는 policy가 반드시 같지 않아도 학습이 가능한 알고리즘.

ex) Q-learning

off-policy는 현재 학습하는 policy가 과거에 했던 experience도 학습에 사용이 가능하고, 심지어는 해당 policy가 아니라 예를 들어 사람이 한 데이터로부터도 학습을 시킬 수가 있다. 과거 데이터로만 학습하는 경우는 offline RL이라고도 부른다.

 

 

# Sarsa는 on-policy인데 Q-learning은 off-policy인 이유

Sarsa는 과거에 했던 데이터에 대해서는 Q(St, At) = Rt + discount_factor * Q(St+1, At+1) 이 성립하지 않는다. 왜냐하면 Q-function이 한 번이라도 업데이트 되는 순간, 과거의 At+1의 선택지로부터 오는 q-value값은 더이상 Q(St, At)의 value를 estimation하는 데 의미를 줄 수가 없다. 왜냐하면 과거의 At+1 선택지가 아주 안 좋은 q-value를 가져와버리면, 그 행동을 안하면 되는데, 그렇지 않고 Q(St, At)에 대해 그 나쁜 value를 그대로 전파하기 때문이다.

 

* 이를 정확하게 다시 설명하자면, 과거의 policy가 내놓은 At+1에 대한 확률과 현재의 policy가 내놓은 At+1의 확률이 다르기 때문에, importance sampling을 해서 이 확률을 조절해주는 과정이 필요하다. 즉 과거의 안좋은 policy는 At+1이 90% 확률로 나온다고 생각했었는데, 현재의 좋은 policy At+1이 0.001%의 확률로 나온다고 생각했을 때 생기는 문제를 해결하기 위해 importance sampling을 하게 된다.

 

반면에 Q-learning에서는 상황이 다르다. Q(St, At) = Rt + discount_factor * max_a Q(St+1, a ) 이 수식에서는 St+1에서 선택하는 action을 max로 매번 새롭게 가져온다. 따라서 Q함수가 업데이트 되더라도, St+1에서의 최적의 선택지를 max_a로 다시 고를 수 있다. 따라서 의미 있는 Q(St, At)에 대한 estimation이 가능하다. 사실 max_a가 저 등식을 성립시키는건 아니다. 엄밀하게는 아마도 a에 대한 expectation을 취한 Expected Sarsa만이 저 등식을 성립시킬 수 있을 것이다. 그럼에도 불구하고 유의미한 것은, Q(St, At)의 값이 미래에 가능한 최고 좋은 value로부터 업데이트 될수가 있기 때문이다.

 

 

# Sarsa에서도 epsilon greedy를 쓸 수 있는 이유

epsilon만큼 random으로 action을 고르는 확률 자체를 포함해서 target policy과 behavior policy로 사용하기 때문이다. 즉 일정 확률 랜덤으로 action을 뽑는 분포가 epsilon greedy가 target에도 있고, behavior에도 똑같이 있으면 두 policy의 확률 분포는 동일해진다.

 

 

* Importance sampling은 과거 policy의 확률 분포로 현재 policy의 확률 분포를 나눠주어, 같은 분포가 되도록 맞춰주는 것.

생각을 해보면, on-policy가 학습 policy와 탐험 policy가 같은 분포여야한다는 조건인데, 이걸 맞춰 주려면 학습 policy가 내놓은 확률을 탐험 policy의 확률 분포와 같아주게 하면됨. 그걸 하기 위해서 Importance sampling을 이용해서 파이(a|s)의 확률 분포를 교정해주자.

 

 

https://dnddnjs.gitbooks.io/rl/content/importance_sampling.html

 

 

근데 이걸 100step만 지나서해도, 미묘한 분포이 차이가 100제곱이되어서 쓰기가 힘들어진다고 함. 

# Policy gradient

policy 분포로 pmf를 쓰면 discrete action space, pdf를 쓰면 continuous action space가 된다.
Loss는 그냥 두 케이스 모두에서 log likelihood에 score값을 곱한 다음 gradient ascent하는 개념이다. softmax같은 pmf이면 cross-entropy가 되고, gaussian 같은 pdf 이면 MLE가 된다.

 

Policy gradient의 시작인 REINFORCE 알고리즘도 Bellman equation에 기반한 알고리즘과 동일하게, expected sum of future reward(expected return)을 최대화하는 방향으로 학습을 한다.

https://talkingaboutme.tistory.com/entry/RL-Policy-Gradient-Algorithms

 

그리고 REINFORCE 알고리즘의 loss를 보면, 결국 일반적인 MLE에서의 loss에 return이 곱해진 형태로 이해할 수 있다. 자세한 내용은 아래 블로그 참조

https://talkingaboutme.tistory.com/entry/RL-CS285-Understanding-Policy-Gradients

 

# Actor-Critic

Critic: Q function을 의미하고, TD(0) 혹은 SARSA를 이용해 학습한다.
Actor: policy를 의미하고, Critic을 value로 받는 REINFORCE알고리즘을 이용해 학습을 한다.

https://dnddnjs.gitbooks.io/rl/content/actor-critic_policy_gradient.html

 

# Advantage Function

Advantage function: Q(s,a) - V(s)

it can be considered as another version of Q-value with lower variance by taking the state-value off as the baseline.

https://lilianweng.github.io/posts/2018-04-08-policy-gradient/

 

# TRPO(Trust Region Policy Optimization)
업데이트될 policy와 그전 policy의 KL_D 값이 너무 커지게되면 penalty를 줘서 step을 조금만 가도록 제한함. 즉 신뢰할만한 거리까지만 업데이트해라.

 

# PPO(Proximal Policy Optimization)

TRPO의 복잡도를 매우 단순화 시킨 버전. 그러나 학습도 더 잘됨.

 

PPO와 TRPO의 실제 구현 코드를 보면, 1번 gradient update하고난 experience도 몇차례 재사용하는 것을 볼 수 있다. 이는 엄밀히 말하면 off-policy에 해당하나, 이 두 논문의 철학 자체가 policy의 차이가 크지 않은 안전한 수준에서만 업데이트를 하길 바라기 때문에 근사적으로 몇번의 gradient update된 policy도 현재 policy와 같다고 보는 것 같다.

https://github.com/openai/baselines/issues/316

 

 

# Macro-action

Action들의 고정된 set. 사람이 직접 정의한 primitive action들의 시퀀스를 의미한다.

 

# Option

Macro-action 과 유사하지만, 함수형태로 되어있어 intra-option policy라고도 불린다. 즉 가장 상위의 policy는 option을 선택하며, 다른 이름으로 policy over options이라고 부르고, 이 때 선택되는 option이 일종의 작은 skill 혹은 작은 policy로, intra-option policy라고 한다.