PaperlayerView exact revision on arXiv

Source-linked AI summary

Implicit Under-Parameterization Inhibits Data-Efficient Deep Reinforcement Learning

Aviral Kumar, Rishabh Agarwal, Dibya Ghosh, Sergey Levine

arXiv:2010.14498v2cs.LGstat.ML

TL;DR

Deep RL methods that bootstrap value targets can lose value-network expressivity as gradient updates accumulate, but the mechanisms behind this instability remain poorly understood. This paper characterizes the loss through feature-rank collapse, analyzes its interaction with bootstrapping and gradient optimization, and finds that controlling rank collapse can improve performance across offline and online settings.

  • Problem

    Common deep RL algorithms using bootstrapping are unreliable because their optimization issues remain incompletely understood.

  • Method

    The paper studies effective feature rank empirically, analyzes bootstrapping with kernel and deep-linear models, and evaluates singular-value penalties for mitigating rank collapse.

  • Results

    Across Atari, Gym, and other evaluated settings, feature-rank collapse typically accompanies performance degradation, while mitigation improves value-based RL performance.

  • Takeaways & Limitations

    Implicit under-parameterization is a recurring failure mode of bootstrapped deep RL, and controlling rank collapse is a viable mitigation direction.

  • Takeaways & Limitations

    The proposed regularization relies on useful features emerging solely from the bootstrapped signal, so better mitigation strategies remain open.

Abstract

from arXiv · show

We identify an implicit under-parameterization phenomenon in value-based deep RL methods that use bootstrapping: when value functions, approximated using deep neural networks, are trained with gradient descent using iterated regression onto target values generated by previous instances of the value network, more gradient updates decrease the expressivity of the current value network. We characterize this loss of expressivity via a drop in the rank of the learned value network features, and show that this typically corresponds to a performance drop. We demonstrate this phenomenon on Atari and Gym benchmarks, in both offline and online RL settings. We formally analyze this phenomenon and show that it results from a pathological interaction between bootstrapping and gradient-based optimization. We further show that mitigating implicit under-parameterization by controlling rank collapse can improve performance.

1 INTRODUCTION

The paper identifies implicit under-parameterization as a bootstrapping-related loss of value-network expressivity that worsens with additional gradient updates and data reuse. It links feature-rank collapse to degraded performance across deep RL settings and analyzes the phenomenon theoretically.

  • Bootstrapped value learning with gradient descent can cause excessive feature aliasing, making an expressive value network behave as under-parameterized and often reducing performance.
  • More gradient updates and higher data reuse aggravate implicit under-parameterization, restricting sample efficiency in online and offline RL.
  • The learned feature rank drops after an initial learning period, generally reducing the ability to fit later targets and the optimal value function.
  • The phenomenon appears in Q-learning, actor-critic, and neural fitted-Q iteration, with rank decreases typically corresponding to sharp performance declines.
  • The paper theoretically attributes implicit under-parameterization to a pathological interaction between bootstrapping and gradient descent's implicit regularization.
  • Penalizing singular values to mitigate rank collapse improves offline Atari performance in value-based RL methods.

2 PRELIMINARIES

The preliminaries define value functions and Bellman operators, then formulate practical Q-learning as gradient-based regression on bootstrapped targets. Fitted Q-iteration provides the paper's abstraction for iteratively training value functions from previous estimates.

  • Reinforcement learning seeks to maximize long-term discounted reward in a Markov decision process defined by states, actions, rewards, transitions, and a discount factor.
  • The policy value Qπ is a fixed point of the Bellman operator, while the optimal value Q* is a fixed point of the Bellman optimality operator.
  • Practical Q-learning trains a neural Q-function by minimizing mean-squared temporal-difference error against targets from a delayed target network.
  • Fitted Q-iteration trains Q_k to match targets y_k generated from the previous value function Q_{k-1}, encompassing practical methods with varied target updates and optimizers.
  • The offline RL setup evaluates neural FQI, DQN, and SAC using fixed datasets while tracking feature rank and policy performance.

3 IMPLICIT UNDER-PARAMETERIZATION IN DEEP Q-LEARNING

Deep RL value networks can undergo implicit under-parameterization: bootstrapped gradient training collapses feature rank, reducing their ability to fit later targets and often degrading performance. The effect appears across offline and data-efficient online settings and is tied to bootstrapping rather than initialization or dataset size alone.

  • Characterizing implicit under-parameterization: Effective feature rank decreases during bootstrapped Q-learning, causing networks to represent state-action pairs in fewer active singular directions.The paper defines implicit under-parameterization as an internally induced reduction in effective feature rank; rank decrease can become more aggressive than in supervised learning.
  • Offline RL: In offline RL, rank collapse appears across Atari, Gym, and gridworld, with Atari retaining only 20–100 active components out of 512-dimensional features.Even high-capacity networks can behave as low-capacity networks after extended training with bootstrapped objectives.
  • Offline RL: A 4x larger Atari dataset with broader coverage does not prevent rank collapse, indicating that the phenomenon is not explained by limited offline dataset size.The same pattern also appears for CQL, which is designed to address distribution mismatch.
  • Data-efficient online RL: In online RL, increasing gradient steps per environment step accelerates rank collapse and produces worse performance across neural FQI, DQN, and SAC settings.The figure compares gridworld, Atari, and Gym domains while varying n, the number of gradient steps per environment step.
  • Performance implications: As feature rank decreases, the network loses the ability to fit subsequent targets: Q∗ fitting error and Atari TD error rise, accompanying performance plateaus or collapse.The relationship is reported as a strong association rather than the claim that under-parameterization is the only cause of poor deep-Q-learning performance.
  • Role of bootstrapping: Controlled experiments link rank collapse to bootstrapping: it persists under reinitialization and fitted policy evaluation but disappears when training uses Monte-Carlo returns.These results isolate bootstrapped updates as central to the observed phenomenon.

4 THEORETICAL ANALYSIS OF IMPLICIT UNDER-PARAMETERIZATION

The theoretical analysis explains implicit under-parameterization as rank loss caused by the interaction between bootstrapping and gradient-based optimization. Kernel-regression and deep-linear analyses show that this loss compounds across fitting iterations and reduces value-function expressivity.

  • Kernel-regression analysis: The analysis models bootstrapped value learning as fitted Q-iteration, where each target y_k is generated from the previous value function Q_{k−1}.This abstraction supports analysis of neural fitted-Q iteration and practical Q-learning variants.
  • Kernel-regression analysis: With additional bootstrapping iterations, singular-value sparsity generally increases, so the effective rank of the matrix mapping rewards to Q-values diminishes.The resulting loss of expressivity can prevent the model from representing the actual Q^π.
  • Deep-linear analysis: The analysis predicts a trade-off in which lower-rank features can accompany larger TD error and greater distance from the projected fixed point.The paper’s controlled experiment reports that decreasing srank_δ(Φ) increases |Q − Q*| near the fixed point.
  • Deep-linear analysis: In the deep-linear analysis, larger singular values grow exponentially faster than smaller ones during gradient descent, causing effective rank to decrease with more within-iteration updates.The analysis uses a deep linear representation whose feature map is W_φ and assumes balancedness for most consecutive layers.
  • Kernel-regression analysis: Gradient-based optimization induces an implicit regularizer that favors disproportionate singular values and lower effective rank in the learned features.The regularizer is data-dependent, and the analysis assumes positive rank-regularization strength λ_k > 0.
  • Deep-linear analysis: Rank collapse compounds across bootstrapped fitting iterations, especially as targets approach the previous value estimate near the Bellman fixed point.Under the theorem’s closeness condition, the rank decreases by at least ||Q_k − y_k||/λ_k in iteration k.

5 MITIGATING UNDER-PARAMETRIZATION IMPROVES DEEP Q-LEARNING

The paper introduces a feature-rank regularizer to prevent rank collapse and evaluates whether this mitigation improves deep Q-learning. It generally preserves or increases effective rank and improves offline Atari performance, though online results are mixed.

  • Regularizer design: The penalty Lp(Φ) encourages higher effective rank by controlling the singular values of the learned feature matrix.It minimizes the largest singular value while balancing singular-value magnitudes, and is added to the TD-error objective.
  • Rank-collapse mitigation: On gridworld, Lp(Φ) reduces rank collapse and yields higher performance than unregularized FQI.With 200 gradient updates per fitting iteration, effective rank gradually decreases and plateaus rather than collapsing.
  • Rank-collapse mitigation: In offline Atari experiments, Lp(Φ) generally increases effective rank for DQN and CQL.Figure 6 reports this pattern across the evaluated Atari games.
  • Offline performance: DQN with Lp(Φ) improved performance on 16/16 Atari games, while CQL improved on 11/16 games.Median improvements were 74.5% for DQN and 14.1% for CQL in the 5% offline setting.
  • Online performance: Online results were mixed: Rainbow improved by 20.6% median performance, whereas DQN declined by 11.5%.The authors conclude that the penalty mitigates but does not fully solve implicit under-parameterization.

6 RELATED WORK

The related-work discussion distinguishes this study from prior analyses of tabular and linear Q-learning by focusing on learning dynamics in deep Q-learning.

  • Scope relative to prior work: Prior work studied error propagation and divergence prevention mainly for tabular or linear function approximation, whereas this work analyzes deep Q-learning.The distinction concerns the function-approximation regime and the associated learning dynamics.

7 DISCUSSION

The discussion characterizes implicit under-parameterization as a bootstrapping-related reduction in value-network expressivity and reports that regularization can improve performance. It also identifies better mitigation strategies as an open problem.

  • Discussion: Bootstrapped gradient optimization can collapse value-network feature rank, alias states, reduce expressive power, and often harm performance.The paper attributes the effect to implicit regularization from gradient descent on bootstrapped objectives.
  • Discussion: The proposed regularizer improves performance in some settings but does not address the root cause, leaving better mitigation strategies for future work.The authors suggest auxiliary losses and further study of initialization and optimizer effects as possible directions.

Appendices

The appendices provide additional evidence that rank collapse tracks degraded performance across offline and data-efficient online settings, is tied to bootstrapping, and can be mitigated by controlling feature rank.

  • A.1 Offline RL: Offline DQN on Atari generally shows lower effective rank alongside worse policy performance, with collapse often beginning near peak return in the 5% dataset setting.The 20% dataset setting also shows the association between low rank and worse performance.
  • A.2 Offline control: Offline CQL on Atari and SAC or CQL on MuJoCo show that rank reduction generally corresponds to degraded policy performance.The MuJoCo experiments use 20% uniformly sampled data from an online SAC replay experience.
  • Online RL: In online DQN and Rainbow, increasing gradient steps per environment step causes earlier or larger rank collapse and generally poorer performance.The results indicate that greater data reuse aggravates implicit under-parameterization.
  • Online RL: Online SAC shows environment-dependent behavior: effective rank and performance can improve with larger update counts in simpler tasks, but rank decreases in Ant-v2.The appendix contrasts HalfCheetah-v2, Hopper-v2, and Walker2d-v2 with the more complex Ant-v2 environment.
  • Bootstrapping ablations: Fitted policy evaluation still exhibits under-parameterization, whereas Monte Carlo targets avoid rank collapse and can increase effective rank over time.This indicates that the phenomenon is not specific to the Bellman optimality operator and depends essentially on bootstrapping.
  • Bootstrapping ablations: Using true value-function targets in a control setting avoids the substantial rank decrease seen with bootstrap TD targets.The corresponding effective rank increases with more iterations, supporting bootstrapping rather than policy non-stationarity as the primary cause.

A.4 HOW DOES IMPLICIT REGULARIZATION INHIBIT DATA-EFFICIENT RL?

Implicit regularization creates a trade-off in which rank collapse reduces the value network’s ability to fit targets, while rank-control penalties generally improve effective rank and performance. Across offline and data-efficient online settings, these penalties improve several value-based RL methods.

  • Performance effects: In gridworld, small rank drops preserve the ability to fit oracle Q∗ values and learn good-performing policies.The observed regression error decreases when rank drop is small, unlike the stronger-collapse case.
  • Performance effects: As effective rank decreases, TD error increases and the value function eventually cannot fit target estimates, producing a performance plateau.This links feature-rank collapse to reduced target-fitting ability in Atari.
  • Rank-control penalty: The Lp(Φ) penalty generally increases effective rank and improves DQN and CQL performance in offline Atari experiments.The reported comparisons include both the standard dataset and a 4x larger dataset.
  • Rank-control penalty: In PONG, the penalty fails to increase rank and performance remains suboptimal, linking effective-rank control with the observed benefit.This pattern is reported for both the 4x larger offline dataset and online Rainbow analyses.
  • Rank-control penalty: For online Rainbow with n = 4, the Lp(Φ) penalty improves performance over the base method in 12/16 games.The corresponding learning curves compare Rainbow against the penalized variant across 16 games.

A.7 RELAXING THE NORMALITY ASSUMPTION IN THEOREM 4.1

The analysis extends effective-rank results beyond normal transition-related matrices by using eigenvalue-based rank measures for non-normal matrices. These measures closely track singular-value-based rank empirically, supporting the practical relevance of the theoretical result.

  • Theoretical extension: The eigenvalue-based measure uses eigenvalue norms instead of singular values and orders complex eigenvalues by decreasing magnitude.This relaxes the normality assumption used for the singular-value formulation.
  • Theoretical extension: For diagonalizable matrices, the eigenvalue-based effective rank srankδ,λ(Mk) decreases, covering almost all matrices of the relevant size.When matrices are approximately normal, the theorem also holds approximately through the relation between singular values and eigenvalue magnitudes.
  • Empirical validation: Empirically, singular-value and normalized-eigenvalue effective ranks show almost identical trends on offline DQN and gridworld experiments.The comparison uses a batch of d state-action pairs because eigenvalues require a square feature matrix.
  • Empirical validation: The practical feature-rank trends support applying the theorem to neural Q-learning, even though the theoretical matrix S is not directly computable.The feature matrix Φ serves as the practical counterpart of S in the analysis.
  • Rank collapse with data reuse: After rescaling for total gradient updates, larger data-reuse values still produce more aggressive rank drops in all but one game.This indicates that the trend is not explained only by the number of plotted updates.

B.1 ATARI EXPERIMENTS

The Atari experiments follow established evaluation and dataset protocols while varying offline data coverage and using specified agent, environment, and replay configurations. The setup includes 5-game and 16-game subsets for analysis and empirical evaluation.

  • Experimental protocol: The experiments follow Agarwal et al. (2020) protocols, including Dopamine agent architectures and reported hyperparameters.The study tunes only the regularization parameter αp using five Atari games.
  • Experimental protocol: Atari evaluation uses sticky actions with a 25% repeat probability and compares agents by their best score averaged over five runs.Evaluations are performed online during training with an ϵ-greedy policy.
  • Datasets: Offline datasets are subsampled from a 50-million-transition DQN Replay dataset, with 5% used most often and a 20% dataset providing 4x larger coverage.The larger dataset tests whether the claims persist with greater state-space coverage.
  • Benchmarks: The analysis uses five Atari games, while the broader empirical evaluation uses a 16-game subset that adds eleven games.The five-game subset is ASTERIX, QBERT, PONG, SEAQUEST, and BREAKOUT.
  • Benchmarks: The gridworld experiments use a 16 × 16 environment with 256 cells, five actions per state, and a two-hidden-layer network of sizes (64, 64).The setup follows the gridworld suite and soft Q-learning configuration described in the cited passages.

C PROOFS FOR SECTION 4.1

The proofs formalize rank decrease through kernel-regression dynamics and matrix properties. They establish that bootstrapping-related fitting iterations can reduce effective rank, with the result extended through subsequences and bounds on singular-value ratios.

  • Kernel-regression proof: The Green’s function acts as a kernel inverse to the identity on the universal-kernel operator and is evaluated on the training data to form G.The construction also permits evaluation on state-action tuples outside the training dataset.
  • Kernel-regression proof: The proof derives the kernel-regression solution by solving the bootstrapping optimization problem with functional derivatives.The solution uses the Green’s function and a universal positive-definite kernel before obtaining the closed form.
  • Rank-decrease theorem: For normal S, the theorem constructs fitting-iteration subsequences where effective rank decreases as singular-value ratios become more concentrated.The proof controls iterations outside the subsequence through an upper bound on those ratios.
  • Rank-decrease theorem: When S is positive semi-definite, effective rank decreases with every increase in fitting iterations.The result follows from the monotonic decrease of singular-value ratios between fitting iterations.
  • Rank-decrease theorem: The singular-value ratio bound is monotone decreasing, which prevents effective rank from increasing toward later fitting iterations.The argument uses the eigen- and singular-value structure of powers of the normal matrix S.
  • Rank-decrease theorem: The proof’s optimization argument connects longer gradient descent within a fitting iteration to a prescribed lower effective rank through a rank-penalized formulation.Running T0 = T(εk) steps yields srankδ(Wφ(k, T0)) = εk.

D.2 PROOF OF PROPOSITION 4.2: COMPOUNDING RANK DROP IN SECTION 4.2

Proposition 4.2 formalizes how rank changes from reward and dynamics transformations propagate across bootstrapped fitting iterations. The resulting rank drop depends on the balance between accumulated TD-error effects and the iteration-specific change c_k, whose behavior is constrained only in special cases.

  • Assumptions: The analysis assumes function-class closure under Bellman evaluation and bounds each iteration’s effective-rank change from reward and dynamics transformations by c_k.These assumptions relate the target-feature rank to the previous Q-function’s feature rank through a recursive inequality.
  • Compounding rank drop: A rank decrease occurs when accumulated TD-error reduction exceeds the possible cumulative increase represented by c_k.The same recurrence shows that rank changes in one iteration are compounded by bootstrapping in later iterations.
  • Compounding rank drop: The sign of c_k is not fixed generally: it can be positive, but both terms contribute to rank reduction when c_k is negative.Under Assumption D.1 near a fixed point, Theorem 4.2 gives the special-case bound c_k ≤ 0.
  • Empirical verification: In Seaquest, the target-feature effective rank decreases across runs, suggesting that c_k is bounded in practice.The experiment approximates the target-feature rank by expressing the dynamics-transformed previous Q-function in the Q-function class and omits the reward function.

D.3 PROOF FOR THEOREM 4.2: RANK COLLAPSE NEAR A FIXED POINT

Theorem 4.2 analyzes rank collapse near a Bellman fixed point by constructing small target perturbations whose effective rank does not increase meaningfully. In this near-fixed-point regime, self-training behavior lets gradient descent reduce feature rank even when TD error remains non-zero.

  • Fixed-point regime: Near a fixed point, the proof studies iterates whose Bellman residual is small and evaluates how perturbations change the singular values of the feature matrix.The analysis uses infinitesimal singular-value changes to characterize effective-rank behavior.
  • Proof construction: The proof constructs a perturbation ε so the target y_k = Q_{k−1} + ε has a feature representation whose rank exceeds the previous rank by only a bounded amount α.The construction keeps the last-layer weights unchanged while controlling the target feature matrix’s effective-rank increase.
  • Rank-change mechanism: The analysis separates rank changes caused by target transformation from rank decreases caused by gradient descent’s implicit behavior.This decomposition identifies the competing increase and decrease terms in the effective rank.
  • Rank-collapse result: Choosing ε sufficiently small makes α = 0, after which self-training implies that the next gradient-descent iteration reduces rank.This reduction can occur while the TD error remains non-zero, including near the optimal fixed point.
Loading 2010.14498v2…