Addressing Function Approximation Error in Actor-Critic Methods (TD3)

https://arxiv.org/abs/1802.09477

Addressing Function Approximation Error in Actor-Critic Methods

---

 

Concepts

"Twin Delayed Deep Deterministic policy gradient algorithm (TD3)"는 DPG와 Actor-Critic 방식을 기반으로 variance reduction에 초점을 맞추어 소개된 기법이다. 주요 특징은 다음과 같다.

• Target network 사용  (DQN 참고!)
• Delayed policy update
• Regularization strategy

 

Preliminaries

Problem setting

본 논문은  Actor-Critic 기법을 기반으로 하고있다.

• Objective :  Find optimal policy $\pi_{\phi}, \; \text{s.t.} \; \max J(\phi) = \mathbb{E}_{s_i \sim p_{\pi}, a_i \sim \pi} [R_0]$
•  Actor update (DPG) :  $\bigtriangledown_{\phi} J(\phi) = \mathbb{E}_{s \sim p_{\pi}} [ \bigtriangledown_a Q^{\pi}(s,a) |_{a=\pi_s} \bigtriangledown_{\phi} \pi_{\phi} (s)]$
• Critic update (Q-learning via Bellman eqn.) :  $Q^{\pi}(s,a) = r + \gamma \mathbb{E}_{s', a' \sim \pi(s')} [Q^\pi (s',a')]$

위와 같은 tabular case 외에도, 큰 state space를 갖는 문제의 경우 function approximation 방식을 사용한다. DQN에서는 policy와 value를 각각 $\pi_{\phi}$, $Q_{\theta}(s,a)$ 로 parameterize하고, 별도의 target network $Q_{\theta'}(s,a)$를 적용한 TD method를 사용한다.

Objective $y$는 아래와 같으며, 정해진 step 동안은 target value network를 고정한 채로 update를 진행한다. 이를 통해 누적 error를 감소시키고, variance reduction을 달성할 수 있다고 한다.

$$y = r + \gamma Q_{\theta'} (s', a') \, , \quad a' \sim \pi_{\phi'}(s')$$

이때, target network update 시 특정 proportion $\tau$를 사용할 수도 있다. 이 방식은 off-policy 기법이나 experience replay buffur에서 random mini-batch sampling하는 방식에 적용될 수 있다.

$$\theta' \leftarrow \tau \theta + (1-\tau) \theta'$$

Overestimation Bias

Q-learning 기법에서 value estimation은 greedy target을 이용하여 update된다.

$$y = r + \gamma \max_{a'} Q(s',a')$$

여기서, $\max$ operation을 쓰기 때문에 어떤 error $\epsilon$ 에 대해 이 추정값은 항상 true value보다 크거나 같을 수 밖에 없다.

$$\mathbb{E}_{\epsilon} [ \max_{a'} (Q(s',a') + \epsilon)] \geq \max_{a'} Q(s',a')$$

이처럼 Bellman equation이 propagte됨에 따라 지속적인 positive bias가 생기는 현상을 overestimation이라고 하며, 이를 해결하는 방법으로 Double Q-learning이 제안된 바 있다.

Double Q-learning

이 방법은 두 개의 actor-critic pair, i.e. $(\pi_{\phi_1}, \pi_{\phi_2}), \, (Q_{\theta_1}, Q_{\theta_2})$를 사용한다. 두 개의 독립된 value estimation을 사용하여 update 때 서로를 참조하게 함으로써 unbiased estimation을 달성하겠다는 것이다. Update target은 다음과 같다.

$$\begin{align*} & y_1 = r + \gamma Q_{\theta'_2} ( s', \pi_{\phi_1}(s') ) \\ & y_2 = r + \gamma Q_{\theta'_1} ( s', \pi_{\phi_2}(s') ) \end{align*}$$

하지만, 사실 이 방법도 완벽하게 bias를 잡아주지는 못한다고 한다. $Q_{\theta_1}$ 과 $Q_{\theta_2}$ 는 같은 replay buffer를 사용하기 때문에 완전히 독립적이지 못하고, 결국 특정 states $s$ 에 대해 $Q_{\theta_2} (s, \pi_{\phi_1}(s) ) > Q_{\theta_1} (s, \pi_{\phi_1}(s) )$ 가 되는 문제가 발생된다.

 

Methods

Clipped Double Q-learning algorithm

위에서 얘기한 double Q-learning의 한계점을 해결하기 위해 제안되었다. 아주 간단한 방법인데, 더 적은 bias를 갖는 추정치 $Q_{\theta_2}$ 의 upper-bound를 $Q_{\theta_1}$으로 제한하는 것이다.

$$y_1 = r + \gamma \min_{i=1,2} Q_{\theta'_i} ( s', \pi_{\phi_1}(s') )$$

이렇게 하면 절대 overestimation이 발생할 수 없지만, 반대로 underestimation bias가 발생될 수도 있다. 하지만 이는 policy update 과정에서 propagate되지 않기 때문에 문제가 되지 않는다.

따라서, 이러한 clipped double Q-learning 방식을 적용하면 low-variance value estimation이 이루어지고, 더 안정적인 학습이 가능해진다.

Solving Accumulated Error

개별 step에 대한 update 시 발생되는 error는 작을 수 있다. 하지만, 여러 step에 걸쳐 update가 진행되면 그 error는 계속 쌓이게 되고, 결국 큰 bias로 이어지게 될 수 있다. 이에 value estimate 시 expected return으로 근사하는 것이 아닌, expected return과 expected discounted sum of future TD-error 와의 차이를 사용하는 방식을 제안하고 있다.

$$\begin{align*} Q_{\theta} (s_t, a_t) & = r_t + \gamma \mathbb{E} [ Q_{\theta} (s_{t+1}, a_{t+1}) ] - \delta_t \\ & = r_t + \gamma \mathbb{E} [ r_{t+1} + \gamma \mathbb{E}[ Q_{\theta} (s_{t+2}, a_{t+2}) - \delta_{t+1} ] - \delta_t \\ & = \mathbb{E}_{s_i \sim p_{\pi}, a_i \sim \pi} \left [ \sum_{i=t}^{T} \gamma^{i-t} (r_i - \delta_i) \right ] \end{align*}$$

하지만, 이 방식도 큰 $\gamma$ 에 대해서는 variance가 증가될 수 있다. 그리고 mini-batch 단위의 update 적용 시, 해당 batch 외부의 다른 데이터들에 대해서 error를 감소시킨다는 보장을 할 수 없다는 한계점이 존재한다.

Target Network

앞서 설명했듯이, 별도의 target network $Q_{\theta'}$ 를 사용하면 error reduction을 달성하고 stable한 학습이 가능해진다.

Delayed Policy Updates

Critic network에 대해 어떤 고정된 횟수, $d$ 번의 update를 진행한 후에 policy와 target network를 update하는 방식이다. 특히, TD-error를 작게 유지하기 위해 target network를 update할 때 다음과 같이 특정 proportion $\tau$ 의 비율을 적용한다.

$$\theta' \leftarrow \tau \theta + (1-\tau) \theta'$$

이렇게 하면 적은 빈도의 policy update를 통해 더 낮은 variance를 갖는 value estimation이 가능해지고, 학습 성능이 좋아진다. 

Target Policy Smoothing Regularization

마지막 trick으로, 비슷한 action들을 비슷한 value를 갖도록 강제하면서 학습을 진행하는 방식을 사용한다. 이는 policy network output에 disturbance를 주고 학습시킴으로써 주변 action들도 기존 action의 true value와 유사한 value를 학습하게 함으로써 이루어진다.

$$y = r + \mathbb{E}_{\epsilon} [ Q_{\theta'} (s', \pi_{\phi'}(s') + \epsilon) ]$$

주변의 유사한 state-action value 추정값을 기반으로 bootstrapping하여 value 추정값을 smoothing하는 효과를 가져온다. 실제로 사용 시에는 아래와 같이 근사하여 적용하며, target policy에 작은 random noise를 추가하고 mini-batch 단위로 기댓값을 구한다.

$$y = r + \gamma Q_{\theta'} (s', \pi_{\phi'}(s') + \epsilon) \\ \epsilon \sim \text{clip}( \mathcal{N}(0, \sigma), -c, c)$$

추가된 noise는 target network output이 기존 action에 가깝에 유지될 수 있도록 clipping하여 적용된다. 이러한 형태는 Expected SARSA 알고리즘과 유사하며, value estimation은 off-policy로 학습되고 noise는 exploration policy와 무관하게 parameter $\sigma$에 따라 선택된다.

TD3 Algorithm

지금까지 설명한 방식들이 추가된 TD3 알고리즘은 아래와 같다.