Diagnosing Bottlenecks in Deep Q-learning Algorithms

Justin Fu; Aviral Kumar; Matthew Soh; Sergey Levine

Source-linked AI summary

Diagnosing Bottlenecks in Deep Q-learning Algorithms

Justin Fu, Aviral Kumar, Matthew Soh, Sergey Levine

arXiv:1902.10250v1Feb 26, 2019cs.LGstat.ML

TL;DR

The paper asks how function approximation, sampling, and nonstationarity affect Q-learning, whose behavior with deep function approximators is poorly understood. It uses oracle-based unit tests to isolate these effects and finds benefits from large architectures, practical overfitting compensation, and AFM sampling, which improves high-dimensional continuous-control performance.

Problem
Q-learning with function approximation is theoretically and empirically poorly understood, particularly regarding approximation, sampling error, and nonstationarity.
Method
An oracle-based unit-testing framework replaces approximate components with ground-truth solvers to disentangle Q-learning error sources and test trends in modern deep RL settings.
Results
Large architectures improve learning stability, early stopping mitigates overfitting, and AFM yields fair improvements in tabular and continuous domains with off-policy RL algorithms.
Takeaways & Limitations
Higher-capacity networks and carefully selected training effort are practical safeguards, while high-entropy sampling can outperform on-policy distributions.
Takeaways & Limitations
The study does not investigate overestimation bias or multi-step returns.

Abstract

from arXiv · show

Q-learning methods represent a commonly used class of algorithms in reinforcement learning: they are generally efficient and simple, and can be combined readily with function approximators for deep reinforcement learning (RL). However, the behavior of Q-learning methods with function approximation is poorly understood, both theoretically and empirically. In this work, we aim to experimentally investigate potential issues in Q-learning, by means of a "unit testing" framework where we can utilize oracles to disentangle sources of error. Specifically, we investigate questions related to function approximation, sampling error and nonstationarity, and where available, verify if trends found in oracle settings hold true with modern deep RL methods. We find that large neural network architectures have many benefits with regards to learning stability; offer several practical compensations for overfitting; and develop a novel sampling method based on explicitly compensating for function approximation error that yields fair improvement on high-dimensional continuous control domains.

1. Introduction

The paper uses an oracle-based unit-testing framework to isolate function approximation, sampling, and nonstationarity issues in Q-learning. It finds that high-capacity architectures, early stopping, and high-entropy sampling can improve learning behavior.

1. Introduction: High-capacity function approximators substantially reduce function-approximation problems, whereas small architectures can create bias beyond ordinary representation error.The paper compares learned solutions with both the optimal Q-function and the best projected solution within the model class.
1. Introduction: Sampling error can cause Bellman-backup errors and overfitting, but oracle early stopping can improve Q-learning performance.The paper studies overfitting through gradient-step ablations and oracle-based stopping procedures.
1. Introduction: Distribution shift and moving targets do not correlate with reduced performance in controlled experiments, and distributions with large shift can perform well.The paper develops metrics for both nonstationarity sources before testing their relationship with performance.
1. Introduction: On-policy sampling is not always best: broader, higher-entropy distributions perform better, motivating adversarial feature matching to compensate for function-approximation error.AFM is designed to retain high-entropy sampling while addressing approximation error.
1. Introduction: An oracle-based framework replaces approximate components with ground-truth solvers to disentangle function approximation, sampling, and distribution-shift errors.The experiments span tabular domains and test whether observed trends also hold in high-dimensional settings.

2. Preliminaries

Q-learning iteratively applies Bellman backups to estimate optimal state-action values, with tabular convergence relying on contraction properties. Function approximation replaces exact backups with projected updates, so the usual convergence guarantee no longer transfers cleanly.

2. Preliminaries: Q-learning seeks the optimal state-action value function by iterating Bellman backups over an MDP's states, actions, transitions, rewards, and discount factor.The resulting policy selects actions using the learned Q-values.
2. Preliminaries: Tabular Q-iteration converges because the Bellman backup is a γ-contraction in the L-∞ norm with Q* as its fixed point.A deterministic optimal policy can then be obtained by choosing the action with the largest Q-value.
2. Preliminaries: Fitted Q-iteration projects Bellman-backup values onto a function-approximator family and underlies modern methods such as DQN.The projection is implemented through supervised learning under a weighting distribution.
2. Preliminaries: With neural networks, previous Q-functions provide target values, while Bellman errors may be computed exactly or estimated through Monte Carlo sampling.The sampled and exact variants separate sampling effects from other sources of error.
2. Preliminaries: FQI lacks the tabular convergence guarantee because an L2 projection is composed with a Bellman operator that contracts in L∞.The norm mismatch means the composed operator is not guaranteed to be a contraction under any norm.

3. Experimental Setup

The experiments progressively replace oracle components with sampled and replay-based procedures, enabling separate tests of approximation, sampling, and distributional effects. Tabular environments provide oracle comparisons, while continuous-control tasks test whether the diagnosed trends generalize.

3. Experimental Setup: The unit-testing setup begins with exact approximate dynamic programming and progressively removes oracle knowledge until it resembles modern deep Q-learning.Oracle-computable tabular environments support direct comparison with true Q-functions, followed by high-dimensional validation.
3. Experimental Setup: Exact-FQI removes sampling error by computing backups and projections over all state-action tuples with known dynamics and rewards.It is used to study convergence, distribution shift, and function approximation in isolation.
3. Experimental Setup: Sampled-FQI estimates Bellman errors and backups from Monte Carlo samples, incorporating function-approximation, sampling, and distribution-shift errors.It is used specifically to study overfitting.
3. Experimental Setup: Replay-FQI stores past transitions in a replay buffer and closely resembles DQN when the buffer is large.Its sampling distribution changes more slowly than that of online updates.
3. Experimental Setup: The study evaluates uniform, on-policy, optimal-policy, random, prioritized, and replay-based weighting distributions for Bellman-error training.Uniform weighting is the standard dynamic-programming choice, while prioritized weighting tracks Bellman-error magnitude.
3. Experimental Setup: Eight tabular domains with varied qualitative properties and four continuous-control benchmarks test oracle diagnostics and high-dimensional generalization.The continuous tasks are HalfCheetah-v2, Hopper-v2, Ant-v2, and Walker2d-v2.

4. Function Approximation and Convergence

Function approximation affects both solution quality and convergence behavior, especially for small architectures. Larger networks reduce bootstrapping bias and generally provide more stable performance, while divergence remains rare in the tested settings.

4. Function Approximation and Convergence: Figure 1 compares normalized returns and normalized Q-function errors across domains and seeds, highlighting the small-architecture gap between FQI Error and Project Error.The visual separates the learned solution's error from the best solution attainable within the model class.
4. Function Approximation and Convergence: The FQI-versus-projection gap measures bias introduced by bootstrapping while controlling for bias caused by function approximation alone.The projected optimum represents the best solution available within the model class without bootstrapping error.
4. Function Approximation and Convergence: Small architectures produce lower returns and more suboptimal solutions, with a significant gap between Exact-FQI's solution and the best solution in the model class.The gap indicates bootstrapping bias beyond the approximation error of the final representable solution.
4. Function Approximation and Convergence: Large architectures are easier to train through bootstrapping because they can represent intermediate Q-functions along the path to the solution.The study observed divergence in only 0.9% of function-approximation experiments, defined by the largest Q-value exceeding 10 times Q*.
4. Function Approximation and Convergence: Large architectures perform best in high-dimensional continuous control, while divergence remains rare even outside tabular domains.The SAC experiments in Appendix Figure 13 reproduce the preference for larger networks.

5. Sampling Error and Overfitting

Sampling error produces overfitting in Q-learning, harming returns, while replay buffers and early stopping mitigate it without sacrificing the benefits of large architectures.

Replay buffers reduce on-policy validation loss despite distribution-shift bias, making them effective against sampling error.
Higher sample counts improve learning speed and final returns, confirming that overfitting significantly affects Q-learning performance.
Too few gradient steps slow learning, whereas too many initially accelerate learning but eventually cause overfitting.
Oracle early stopping can modestly improve performance and provides an upper bound for practical stopping methods.
Large architectures remain preferable because smaller models’ function-approximation bias outweighs the additional overfitting harm of larger models.

6. Non-Stationarity

The study separates moving targets from distribution shift using controlled Q-learning experiments. Isolated nonstationarities generally do not create major stability problems, while function approximation and sampling error matter more.

6.2. Does a moving target cause instability in the absence of a moving distribution?: An α-smoothed Bellman backup controls target-change speed by averaging previous targets, trading weaker contraction for potentially greater stability.
6.2. Does a moving target cause instability in the absence of a moving distribution?: Hard target updates usually converge fastest and reach the highest asymptotic performance, while slower targets slightly help only the two smallest architectures.
6.3. Does distribution shift impact performance?: Replay buffers greatly reduce distribution shift, whereas prioritized and on-policy sampling induce the greatest shift.
6.3. Does distribution shift impact performance?: Distribution shift shows little correlation with returns, as prioritized weighting can perform well despite producing high distribution shift.
When isolated, target and distribution nonstationarities do not cause significant stability issues; sampling error and function approximation have larger performance effects.

7. Sampling Distributions

The study isolates how weighting distributions affect Q-learning and proposes AFM, which combines high-entropy coverage with function-approximation-aware weighting. AFM matches or improves on strong baselines in tabular and continuous-control settings.

7.1. Technical Background: Exact-FQI results favor high-entropy, broadly supported weighting distributions, while AFM is comparable to Replay(s, a) and better for small networks.The experiments isolate weighting from sampling because all states are observed with different weights.
7.3. Designing a Better Off-Policy Distribution: Adversarial Feature Matching: AFM models the weighting distribution as an adversary maximizing Bellman error while the Q-function minimizes it, with constraints limiting adversarial concentration.Feature matching keeps the adversary near uniform while allowing emphasis on selected state-action pairs.
7.3. Designing a Better Off-Policy Distribution: Adversarial Feature Matching: The authors argue that AFM outperforms PER by rebalancing replay-buffer coverage rather than explicitly correcting distribution shift.This contrasts AFM’s objective with PER’s importance-sampling correction.
7.3. Designing a Better Off-Policy Distribution: Adversarial Feature Matching: AFM+Sampling performs strictly better than AFM and PER in the replay-buffer setting.AFM reweights uniformly sampled buffer data, whereas AFM+Sampling changes which samples are drawn.
7.3. Designing a Better Off-Policy Distribution: Adversarial Feature Matching: AFM yields substantial improvement with TD3 across Half-Cheetah, Hopper, and Ant, and performs slightly better than entropy-constrained SAC.PER performed poorly in these continuous-control domains.

8. Conclusions and Discussion

The conclusions identify function approximation, sampling error, and weighting-distribution choice as major practical determinants of Q-learning performance. Large architectures, replay and early stopping, and AFM provide the main reported remedies, while several Q-learning topics remain outside the study.

8. Conclusions and Discussion: Expressive architectures largely mitigate approximation problems, suffer less bootstrapping error, converge faster, and are more stable with moving targets.Potential convergence issues were not empirically endemic, but function approximation still strongly affected the converged solution.
8. Conclusions and Discussion: Sampling error can cause substantial overfitting, while replay buffers and early stopping can mitigate it.The authors recommend large architectures with the number of gradient steps selected carefully.
8. Conclusions and Discussion: Oracle early stopping can provide huge performance benefits, motivating methods that dynamically control gradient steps rather than fixing them as a hyperparameter.The authors link fixed gradient-step choices to large performance differences.
8. Conclusions and Discussion: AFM balances high entropy and state aliasing and improves performance in both tabular and continuous domains with state-of-the-art off-policy RL algorithms.The conclusion presents sampling-distribution design as a major determinant of solution quality.
8. Conclusions and Discussion: The study does not investigate overestimation bias or multi-step returns, leaving them for future work using the oracle-based framework.This is the stated scope boundary of the conclusions.

A. Benchmark Tabular Domains

The benchmark covers eight tabular domains spanning gridworlds, sequence-like navigation, discretized control, and random graphs. These tasks vary state size and representation, including settings designed to expose function-approximation and state-aliasing difficulty.

A. Benchmark Tabular Domains: The benchmark contains eight tabular domains selected for qualitative differences.The suite includes four Gridworlds alongside Cliffwalk, InvertedPendulum, MountainCar, and SparseGraph.
A. Benchmark Tabular Domains: Gridworld varies size between 16×16 and 64×64 and compares one-hot, coordinate, and random state representations.Random observations increase function-approximation difficulty through significant state aliasing.
A. Benchmark Tabular Domains: Cliffwalk uses sequential states with two actions and random 16-dimensional observations, rewarding only arrival at the final state.The alternative action returns the agent to the initial state.
A. Benchmark Tabular Domains: InvertedPendulum and MountainCar are discretized continuous-control tasks, while SparseGraph is a 256-state graph with randomly drawn edges.SparseGraph assigns two action-linked edges to each state and designates one goal state with reward one.
A. Benchmark Tabular Domains: Function approximation removes guarantees that fitted Q-iteration converges to the optimal solution, although this does not imply divergence in typical cases.The supplied theoretical discussion instead characterizes solution degradation through projection or Bellman error.

B.1. Unbounded divergence in FQI

The analysis identifies conditions under which fitted Q-iteration avoids or exhibits unbounded divergence, and shows that α-smoothed Bellman backups remain convergent. Divergence depends on sampling support, while smoothing preserves contraction toward Q∗.

B.1. Unbounded divergence in FQI: Unbounded divergence is impossible when the weighting distribution has positive support everywhere and the projection is non-expansive in ℓ2.The resulting bound can still be loose because it scales with the state-action space size.
B.1. Unbounded divergence in FQI: Nearly uniform weighting distributions can perform well because they maximize the denominator in the divergence bound.The analysis also notes that tighter L2-based bounds depend on the transition distribution.
B.1. Unbounded divergence in FQI: When the weighting distribution lacks support over some state-action pairs, a two-state linear example diverges with γ > 0.5.Adding sampled transitions from the second state can avoid divergence.
C. α-smoothed Q-iteration: The α-smoothed Bellman backup remains a valid Q-iteration method because it is a contraction for 1 ≥ α > 0 and converges to Q∗.Its contraction factor is 1 − α + γα.

D. Adversarial Feature Matching (AFM): Detailed Explanation and Practical Implementation

AFM constructs an adversarial weighting distribution for Bellman-error minimization, constrained by Q-network features and implemented with alternating optimization and replay-buffer importance weighting. The supplied experiments connect this approach to larger-architecture stability, overfitting diagnostics, and sampling evaluation across continuous-control settings.

D. Adversarial Feature Matching (AFM): Detailed Explanation and Practical Implementation: AFM constrains an adversary with Q-network features so it can exploit state aliasing while promoting more separable feature learning.For continuous control, the features depend on actions as well as states.
D. Adversarial Feature Matching (AFM): Detailed Explanation and Practical Implementation: The optimization alternates between an inner adversarial maximization and an outer Q-function minimization using dual gradient descent.The implementation avoids backpropagating through the Q-network feature representation during the outer minimization.
D. Adversarial Feature Matching (AFM): Detailed Explanation and Practical Implementation: The α-smoothed backup favors higher α for large architectures but slightly favors lower α for smaller architectures.The results average normalized errors and returns across domains and five seeds.
D. Adversarial Feature Matching (AFM): Detailed Explanation and Practical Implementation: AFM estimates Bellman-error expectations under its adversarial distribution by importance weighting replay-buffer samples and regularizing the second-order Rényi divergence.Self-normalized importance sampling and parameter clipping are used for practical stability.
D. Adversarial Feature Matching (AFM): Detailed Explanation and Practical Implementation: Bigger SAC networks learn faster and achieve higher returns on three MuJoCo tasks.The figure averages results over three seeds, with each epoch representing 1000 environment steps.
D. Adversarial Feature Matching (AFM): Detailed Explanation and Practical Implementation: Increasing critic and actor gradient steps per environment step causes clear performance decay in TD3 on Half Cheetah and Hopper.The experiment uses a replay buffer of size 2e4 and interprets the decay as evidence of Q-function overfitting.