Addressing Function Approximation Error in Actor-Critic Methods

Scott Fujimoto; Herke van Hoof; David Meger

Source-linked AI summary

Addressing Function Approximation Error in Actor-Critic Methods

Scott Fujimoto, Herke van Hoof, David Meger

arXiv:1802.09477v3Feb 26, 2018cs.AIcs.LGstat.ML

TL;DR

Overestimation bias and error accumulation remain insufficiently addressed in actor-critic methods for continuous control. TD3 limits overestimation through clipped Double Q-learning and related updates, improving learning speed and performance while exceeding numerous state-of-the-art algorithms.

Problem
Overestimation bias and its effects are less established in actor-critic methods for continuous control than in discrete-action value-based methods.
Method
TD3 adapts Double Q-learning with paired critics, examines target networks, delays policy updates, and adds SARSA-style target-policy smoothing.
Results
TD3 greatly improves DDPG’s learning speed and performance in challenging continuous-control tasks and exceeds numerous state-of-the-art algorithms.
Takeaways & Limitations
The simple modifications can be added to other actor-critic algorithms to limit overestimation and improve performance.
Takeaways & Limitations
The theoretical overestimation result assumes normalized gradients.

Abstract

from arXiv · show

In value-based reinforcement learning methods such as deep Q-learning, function approximation errors are known to lead to overestimated value estimates and suboptimal policies. We show that this problem persists in an actor-critic setting and propose novel mechanisms to minimize its effects on both the actor and the critic. Our algorithm builds on Double Q-learning, by taking the minimum value between a pair of critics to limit overestimation. We draw the connection between target networks and overestimation bias, and suggest delaying policy updates to reduce per-update error and further improve performance. We evaluate our method on the suite of OpenAI gym tasks, outperforming the state of the art in every environment tested.

1. Introduction

The introduction shows that function-approximation overestimation and error accumulation affect actor-critic methods in continuous control, producing poor or divergent policy updates. It presents TD3, which combines variance reduction, delayed policy updates, and other modifications to address these issues and outperforms the state of the art across seven OpenAI Gym domains.

Problem: Overestimation bias and temporal-difference error accumulation persist in actor-critic methods for continuous control, potentially causing suboptimal policies and divergent behavior.Imprecise estimates are repeatedly incorporated into updates, allowing arbitrarily bad states to receive high estimated values.
Problem: Deterministic policy gradients exhibit overestimation, while Double DQN is ineffective for addressing the problem in actor-critic settings.The paper establishes the continuous-control analogue of the discrete-action overestimation problem and questions direct transfer of Double DQN.
Method: The proposed method reduces variance using target networks, delays policy updates until value estimates converge, and introduces a novel regularization strategy.These components target error accumulation and the coupling between value and policy updates.
Method: TD3 applies these modifications to DDPG and explicitly addresses function-approximation error in both policy and value updates.The resulting algorithm is named Twin Delayed Deep Deterministic policy gradient (TD3).
Evaluation: Across seven continuous-control domains from OpenAI Gym, TD3 outperforms the state of the art by a wide margin.The evaluation covers seven environments and compares the proposed actor-critic algorithm with the state of the art.

2. Related Work

Prior work has examined function approximation error in reinforcement learning, especially overestimation bias and variance accumulation. Existing remedies include Double Q-learning, variance reduction, target networks, discount-factor reduction, and extensions to deterministic actor-critic methods.

Function approximation error has been studied for its effects on reinforcement learning bias and variance, with this work focusing on overestimation bias and high variance build-up.
Double Q-learning uses two independent estimators for unbiased value estimates, while other approaches reduce variance, limit overfitting to early high-variance estimates, or add corrective terms.
Target networks are identified as important for reducing per-update error, while longer horizons and reduced discount factors address error accumulation indirectly.
The method builds on DPG and DDPG, an actor-critic extension that achieved state-of-the-art results with efficient iterations; related DDPG improvements include distributed and multi-step methods.

3. Background

Reinforcement learning trains an agent to maximize discounted rewards by learning an optimal policy. Actor-critic methods update an actor policy using expected-return gradients while estimating action values with a critic, often using Bellman-based temporal-difference learning and target networks.

3. Background: Reinforcement learning models an agent selecting actions from states and receiving rewards and successor states to learn reward-maximizing behavior.The return is the discounted sum of rewards, with γ controlling the priority of short-term rewards.
3. Background: The objective is to learn a parameterized policy πφ that maximizes expected return J(φ), with continuous-control actors updated using ∇φJ(φ).In actor-critic methods, the policy is the actor and can be updated with the deterministic policy gradient algorithm.
3. Background: The critic or value function Qπ(s, a) estimates expected return after taking action a in state s and subsequently following policy π.Q-learning learns the value function through temporal-difference updates based on the Bellman equation relating current and successor state-action values.
3. Background: For large state spaces, deep Q-learning uses differentiable value approximators and a frozen target network to maintain a fixed objective across multiple updates.Target networks can be synchronized periodically or updated by θ′ ← τθ + (1 −τ)θ′, with off-policy updates using replay-buffer mini-batches.

4. Overestimation Bias

Overestimation bias persists in actor-critic methods: deterministic policy-gradient updates can overestimate values and reinforce suboptimal actions through critic-policy feedback. The proposed Clipped Double Q-learning reduces this bias by using two critics and taking their minimum, while accepting possible underestimation as preferable.

4.1 Overestimation in Actor-Critic: Deterministic policy-gradient updates induce overestimation when the critic estimate is at least as large as the true value and the update step is sufficiently small.The condition is E[Qθ(s, πtrue(s))] ≥ E[Qπ(s, πtrue(s))] with α < min(ϵ1, ϵ2).
4.1 Overestimation in Actor-Critic: Small per-update errors can accumulate into substantial bias and create a feedback loop in which a suboptimal critic reinforces poorly rated actions through subsequent policy updates.The resulting policy updates may further favor actions that the inaccurate critic already values highly.
4.1 Overestimation in Actor-Critic: DDPG exhibits clear overestimation in Hopper-v1 and Walker2d-v1, whereas Clipped Double Q-learning greatly reduces critic overestimation.The comparison averages value estimates over 10000 states and estimates true value from discounted returns over 1000 episodes.
4.2 Clipped Double Q-learning: Clipped Double Q-learning replaces the critic with a clipped Double Q-learning variant that uses two critics and takes the minimum target to prevent additional overestimation.The method can replace the critic in any actor-critic method and may induce underestimation, which the paper considers preferable because underestimated actions are not explicitly propagated through policy updates.
4.2 Clipped Double Q-learning: Actor-critic Double DQN retains overestimation similar to DDPG, while standard Double Q-learning reduces but does not eliminate it.The paper reports that this remaining reduction is insufficient experimentally.

5. Addressing Variance

The section argues that variance in value estimates should be directly reduced because accumulated function-approximation error can destabilize policy updates. It connects stable target networks, delayed policy updates, and target policy smoothing to controlling this variance and improving learning behavior.

Accumulated Error: Temporal-difference errors can accumulate under function approximation, producing large overestimation bias and suboptimal policy updates.Each update leaves residual error because the Bellman equation is not exactly satisfied.
Variance Growth: High variance grows rapidly with large discount factors and is not controlled outside the mini-batch used for each gradient update.The estimate’s variance reflects future reward and estimation error, while mini-batch optimization gives no guarantees for other value estimates.
Target Networks: Stable target networks reduce error growth, whereas fast-updating targets combined with policy learning can produce highly divergent behavior.With a fixed policy, update rates show similar convergence; divergence appears when the policy is trained from the current value estimate.
Delayed Policy Updates: Delaying policy and target-network updates lets the critic first reduce error, yielding less frequent policy updates based on lower-variance value estimates.This forms a two-timescale algorithm and limits repeated updates against an unchanged critic.
Target Policy Smoothing: Target policy smoothing reduces variance caused by deterministic policies overfitting narrow value peaks by adding clipped noise and averaging over actions.The resulting update resembles Expected SARSA and learns values for a noisy policy defined by σ.

6. Experiments

Experiments evaluate TD3 on reproducible MuJoCo continuous-control tasks through OpenAI Gym, finding that it matches or outperforms competing methods in final performance and learning speed across all tasks. Ablations show that component combinations, especially the full algorithm and delayed policy updates, generally improve performance, while Clipped Double Q-learning outperforms alternative actor-critic Double Q-learning variants.

TD3 algorithm: TD3 maintains two critics and one actor, updating critics toward the minimum target value and delaying policy updates every d iterations.The policy is updated with respect to Qθ1 following the deterministic policy gradient algorithm.
Main comparison: TD3 matches or outperforms all other algorithms in final performance and learning speed across all MuJoCo continuous-control tasks.Tasks use the original OpenAI Gym environments without modifications and are evaluated over 10 random seeds.
Ablation studies: The full algorithm outperforms every other component combination in most tasks, while delayed policy updates generally improve performance and reduce training time.Single components usually produce insignificant improvements, whereas combinations perform at a much higher level.
Ablation studies: Clipped Double Q-learning outperforms both DQ-AC and DDQN-AC, suggesting that subduing overestimations from the unbiased estimator improves performance.The comparison methods also used delayed policy updates, target policy smoothing, and the same architecture and hyper-parameters.

7. Conclusion

The paper establishes overestimation bias as a problem in actor-critic methods and introduces TD3 to limit approximation errors. TD3 combines several improvements that substantially enhance DDPG’s learning speed and performance in continuous control.

7. Conclusion: Overestimation bias affects actor-critic methods, while common deep Q-learning remedies for discrete actions are ineffective in actor-critic settings.The paper develops a Double Q-learning variant that limits possible overestimation.
7. Conclusion: Target networks help limit errors from imprecise function approximation and stochastic optimization by addressing temporal-difference error accumulation.The paper also examines the connection between noise and overestimation.
7. Conclusion: A SARSA-style regularization technique modifies the temporal-difference target to bootstrap from similar state-action pairs.This technique is introduced alongside the analysis of target networks and error accumulation.
7. Conclusion: TD3 combines these improvements and greatly improves DDPG’s learning speed and performance across challenging continuous-control tasks.The algorithm exceeds numerous state-of-the-art algorithms and can be added to other actor-critic methods because its modifications are simple to implement.

Supplementary Material … C. DDPG Network and Hyper-parameter Comparison

The supplementary material establishes convergence of Clipped Double Q-learning under finite-MDP conditions, explains overestimation in deterministic policy gradients, and records the compared DDPG network configurations.

A. Proof of Convergence of Clipped Double Q-Learning: In function approximation, both value estimates can be updated at each iteration because approximation error is the primary concern.The passage contrasts this with finite-MDP Double Q-learning, where either estimate is updated randomly to address noise from rewards or transitions.
B. Overestimation Bias in Deterministic Policy Gradients: With unnormalized deterministic policy-gradient updates, overestimation is guaranteed under a stronger expectation condition on the approximate value function.The condition concerns agreement with the true value function in expectation over the steady-state distribution along policy parameters between the original policy and the true update direction.
B. Overestimation Bias in Deterministic Policy Gradients: The actor’s approximate-policy value is at least the true-policy value, while the true-policy value is at least the approximate-policy value, demonstrating value-function overestimation.The ordering is Qθ(s, πapprox(s)) ≥Qπ(s, πtrue(s)) ≥Qπ(s, πapprox(s)).
C. DDPG Network and Hyper-parameter Comparison: The compared DDPG network uses a state input followed by a 400-unit ReLU layer and a 300-unit layer receiving action dim + 400 inputs.The supplied implementation passages provide two network expressions: one beginning with state dim and one with state dim + action dim.

D. Additional Implementation Details

The implementation uses a terminal-transition target rule that sets Q(s, ·) to zero for failure-state terminations but bootstraps otherwise. It also clips target-policy-smoothing noise to feasible actions to avoid errors from impossible-action values.

Terminal transitions: For failure-state terminations before the maximum horizon, the target sets Q(s, ·) to 0; otherwise, it uses the bootstrapped target.This rule is applied in both DDPG and TD3 implementations.
Terminal transitions: The target uses r when s′ is terminal before the maximum horizon, and r + γQθ′(s′, πφ′(s′)) otherwise.The distinction is between failure-state termination and episodes reaching the maximum horizon.
Target policy smoothing: Target-policy-smoothing noise is clipped to the range of possible actions to avoid errors from impossible-action values.This mechanism is described for target policy smoothing in Section 5.3.

E. Soft Actor-Critic Implementation Details · F. Additional Learning Curves

The Soft Actor-Critic implementation follows the authors’ code and hyperparameters, with task-specific policy and reward-scaling adjustments and a reduced training budget for fair comparison. Additional curves ablate TD3/AHE modifications and compare TD3 with actor-critic variants using delayed updates and target policy smoothing.

E. Soft Actor-Critic Implementation Details: The implementation uses the authors’ Soft Actor-Critic code and hyperparameters, with a Gaussian mixture policy containing 4 Gaussian distributions.The Reacher-v1 exception and reward scaling are specified separately.
E. Soft Actor-Critic Implementation Details: Reacher-v1 uses a single Gaussian distribution because of numerical instability in the provided implementation.This is the only task-specific policy exception described.
E. Soft Actor-Critic Implementation Details: Rewards are multiplied by 3 for Walker2d-v1 and Ant-v1, and by 1 for all remaining environments.This follows the environment-dependent reward scaling described by the Soft Actor-Critic authors.
E. Soft Actor-Critic Implementation Details: For fair comparison, training uses 1 iteration per time step instead of the authors’ reported 4 iterations, along with fewer total time steps.The comparison also uses a prior Soft Actor-Critic version; its most recent variant includes Clipped Double Q-learning in the value update.
F. Additional Learning Curves: Figure 6 ablates TD3 by comparing delayed policy updates, target policy smoothing, and Clipped Double Q-learning.The compared variants are TD3 - DP, TD3 - TPS, and TD3 - CDQ.
F. Additional Learning Curves: Figure 7 ablates AHE by comparing the addition of delayed policy updates, target policy smoothing, and Clipped Double Q-learning.The compared variants are AHE + DP, AHE + TPS, and AHE + CDQ.
F. Additional Learning Curves: Figure 8 compares TD3 with the Double Q-learning and Double DQN actor-critic variants, which leverage delayed policy updates and target policy smoothing.The variants are labeled DQ-AC and DDQN-AC.