Deep RL Policy-based Method

Policy-based Method

- Steppest Ascent

- Adaptive Noise

- Cross Entropy Method

- Evoluation Strategies

Policy gradient Method

- REINFORCE

- PPO

Actor-Critic Variants

- A3C

- A2C

- GAE

- DDPG

On-policy vs. Off-policy

---

Policy-based Method

: value-based method는 value function을 구해 이를 기반으로 optimal policy를 구하지만, policy-based method는 neural network에서 optimal policy를 바로 estimate한다. 즉, value function을 구하는 과정이 없다. neural network의 output이 value function이 아닌 policy에 대한 probability가 나온다. 

 

Hill Climbing algorithm

: agent가 언덕 정상에 도달하는 것이 goal인 env이다. expected return J를 maximize 하려고 할 때, gradient descent에서도 과거에 동일한 결과가 나왔었듯이, gradient ascent를 사용해도 local minimum에 빠지는 문제가 발생했다. 

 

 

local minumum에 빠지는 문제를 해결하기 위해 다양한 방법들이 연구되었다. 

 

Steppest Ascent

: 여러 policies를 random sampling 해서 gradient가 가장 작은 것을 선택하는 방식이다. 

 

Simulated Annealing

: Steppest Ascent 과정에서 random sampling 하던 policies 영역을 점점 줄여가며 선택하는 방식이다. 

 

Adaptive Noise

: Simulated Annealing 방식으로 계속 찾아가다가 local minumum에 도착하게 되면 sampling 영역이 점점 커지다가 더 작은 값을 찾으면 다시 줄어드는 방식이다. 

 

Cross Entropy Method

: 하나가 아닌 여러 policies를 선택해서 cross-entropy가 높은 쪽으로 찾아가는 방식이다. 

 

Evolution Strategies

: sampling 한 policies 전체의 average 값들을 사용해 찾아가는 방식이다. 

 

Why Policy-based methods?

Simplicity

: optimal value function을 구하지 않아도 되며 network architecture가 단순하다. 

 

Stochastic Policies

: Stochastic Policies에 더 적합하다.

 

Continuous spaces

: Continuous spaces에 더 적합하다.

 

---

Policy Gradient methods

Policy-based methods

: action을 directly하게 찾는다. 

 

Poilcy Gradient methods

: gradient ascent를 사용하여 best weights를 estimate한다. 

 

1) Trajectory T(기존의 episode와 유사한 의미)를 충분히 모은다.

2) reward를 얻는 방향으로 probability를 조정한다. supervised learning과 유사하다고 볼 수 있다. 

 

* Trajectory T: state-action sequence

* R(T): reward summation

* U(theta): objective function; probability of T * R(T)

 

REINFORCE

: gradient ▽U(theta)에 learning rate만큼 U(theta)가 커지는 방향으로 gradient ascent를 시킨다. 기존의 policy gradient와의 차이점은 gradient ▽U(theta)를 calculate가 아닌 estimate하고, 모든 possible trajectory가 아닌 few trajectories만 사용한다. 결과적으로 매우 강력하다. 그러나 다음과 같은 단점들이 존재한다. 

 

1) update process가 매우 비효율적이다. 

2) gradient estimate가 매우 noisy하다. 

3) credit assignment가 없다. 

 

Noise Reducement

: reward를 normalization하는 방식이다. 

 

Credit Assignment 

: R(T) 계산시에 과거의 reward가 아닌 future reward만 계산하는 방식이다. 

 

Importance Sampling

: trajectory를 재사용하는 방식이다. 

 

PPO(Proximal Policy Optimization)

: policy gradient method인 REINFORCE의 단점을 해결하기 위해 등장했다. 

 

Surrogate Function

: REINFORCE에서 사용하던 objective function 대신 surrogate function을 사용하는 방식이다. 

 

Clipping Policy Updates

: gradient가 특정 구간을 넘어가기 전에 clipping 하여 update 양을 조절하는 방식이다. 

 

Clipped Surrogate Function

: 위 두 방식을 융합하여, 특정 구간에 들어가기 전까지 surrogate function을 사용하다가 임계점을 넘어가면 clipped 된 값을 사용하는 방식을 취한다. 

 

1) pi_theta(neural network의 policy parameter)에 기반한 trajectory T를 수집한다. 

2) objective surrogate function의 gradient를 계산한다. 

3) 계산한 (clipped)gradient로 theta'을 update한다. 

4) 2, 3번을 몇 차례 반복한다. 

5) theta'을 theta에 복사해주고, 1번으로 돌아간다. 

 

---

Actor-Critic Method

: 주로 value-based는 bias가 크고, policy-based는 variance가 크기 때문에 bias-variance trade-off를 해결하기 위해 두 방식을 혼합해서 사용하는 방식이다. 

 

value-based method

: value-based method에서 episode를 통해 state-value function, action-value function, advatage function을 알 수 있다. 

 

Two ways for estimating expected returns

Monte Carlo - High variance, Low bias

: single episode 내 많은 random events를 포함하기 때문에 variance가 높고, 자신이 얻은 true rewards를 사용하기 때문에 estimate가 정확하므로 bias가 낮다. 

 

Temporal Difference - Low variance High bias

: randomness를 가진 single time-step만을 포함하므로 variance가 낮고, next_state에 대해 bootstrapping하여 true value가 아니므로 calculation에 bias가 포함되어 bias가 높다. 따라서 agent는 빠르게 학습할 수 있지만 convergence가 힘들다. 

 

Actor-Critic Architecture

Actor(policy-based method)와 Critic(value-based method)의 두 가지의 network를 사용한다. 

 

1) state가 들어오면 Actor에서 학습 한 뒤, (s, a, r, s')을 출력하여 모아준다.  

 

2) 모은 (s, a, r, s')로 Critic에서 학습 한 뒤, state-value function과 action-value function 구한다.  

 

3) 2번에서 얻은 value-function들로 advantage function을 구해 Actor를 다시 학습시킨다. 

 

---

Actor-Critic Variants

A3C(Asynchronous Advantage Actor-Critic)

 

N-step Bootstrapping

: TD estimate(ex. sarsa, Q-learning) 과정에서는 action을 취한 후에 state transition이 진행되고 한 번의 action을 더 진행한다. 그러나 A3C에서는 n번의 action을 끝까지 진행하여 확인한다. N-step bootstrapping은 TD와 MC estiamte의 abstration 및 generalization이라고 볼 수 있다. TD는 1-step bootstrapping이라고 볼 수 있고, MC는 infinite-step bootstrapping이라 정확히는 bootstrap 하지않는다. 

 

Parallel Agents

: experience buffer를 대체해서, 여러 agent를 사용하여 experience를 병렬적으로 수집하는 방식이다. 각 agent는 correlated experience의 많은 batch를 받게 된다. 그러나 agent는 주어진 시간에 다른 state에서 경험할 가능성이 높기 때문에 sample은 decorrelated하다. 이러한 학습 방식을 통해 보다 안정적인 학습과 관련된 On-policy 학습이 가능하다.

 

A2C(Advantage Actor-Critic)

: A3C와 동일한 구조지만 weight를 synchronization하는 point가 추가되었다. 추가로, agent를 각각의 gpu에 할당하여 좀 더 병렬적인 구조로 속도면에서 큰 이점을 보이는 방식이다. 

 

GAE(Generalized Advantage Estimation)

: A3C에서의 N-step Bootstrapping을 lamda라는 hyperparameter를 사용하여 얼마나 많은 step까지 진행할지 조절할 수 있게 조정한 방식이다. A3C이 generalization 버전이다. 

 

DDPG(Deep Deterministic Policy Gradient)

: 보통은 Actor-Critic이라고 보지만 DQN이라고 보는 시각도 모두 존재한다. DQN이 continuous action space에서 학습이 잘 되지 않는다는 단점을 해결하기 위해 등장했다. 기존 Actor-Critic 방식에서 서로 주고 받는 input, output이 다르다. Regular Actor network, Regular Critic network, Target Actor network, Target Critic network의 총 4가지 network를 사용한다. 

 

Replay buffer

: DQN과 동일한 experience 저장 방식을 따른다.

 

Soft Update

: regular network에서 target network로 weight를 매 step마다 최소 0.01%만큼 주기적으로 복사한다. 

 

---

On-policy vs. Off-policy

Off-policy learning

:  env와 interaction하기 위해 사용되는 policy가 learning policy가 다른 경우이다. 불안정하고 neural network에 따라 다양하다고 알려져있다. (ex. Q-learning, DQN, ...)

 

On-policy learning

:  env와 interaction하기 위해 사용되는 policy가 learning policy가 같은 경우이다. 현재 learning policy에 의해 생성된 데이터만 사용하며 policy를 개선할 때마다 모든 데이터를 버리고 더 많은 데이터를 수집한다. experience를 사용하는데 조금 비효율적이지만, 보통 더 안정적이고 지속적인 수렴성을 보여준다. (ex. SARSA, A3C, ...)

 

---

Reference

https://www.youtube.com/watch?v=srgNJWVgs9w&list=PLMhvUUCFLfI4K_d9lCXtY0e3iAEV_HbnK&index=1&t=67s