PaperlayerView exact revision on arXiv

Source-linked AI summary

A Theoretical Analysis of Deep Q-Learning

Jianqing Fan, Zhaoran Wang, Yuchen Xie, Zhuoran Yang

arXiv:1901.00137v3cs.LGmath.OCstat.ML

TL;DR

Deep reinforcement learning has strong empirical performance but limited theory for nonlinear neural-network approximation. This paper analyzes a simplified DQN through neural FQI, derives algorithmic and statistical convergence results, and extends the framework to zero-sum Markov games.

  • Problem

    Theory for deep reinforcement learning is limited beyond tabular and linear settings, where deep neural networks create a highly nonconvex analysis problem.

  • Method

    The paper studies neural FQI with ReLU networks as a theoretically tractable simplification of DQN and extends the analysis to Minimax-DQN for zero-sum Markov games.

  • Results

    The analysis establishes algorithmic and statistical convergence rates, with algorithmic error decreasing geometrically and statistical error reflecting approximation bias and finite-sample variance.

  • Takeaways & Limitations

    The results theoretically justify DQN's experience-replay and target-network techniques and quantify convergence toward optimal values or Markov-game equilibria.

  • Takeaways & Limitations

    The analysis assumes i.i.d. data and that global optima of the neural-network regression subproblems can be reached.

Abstract

from arXiv · show

Despite the great empirical success of deep reinforcement learning, its theoretical foundation is less well understood. In this work, we make the first attempt to theoretically understand the deep Q-network (DQN) algorithm (Mnih et al., 2015) from both algorithmic and statistical perspectives. In specific, we focus on a slight simplification of DQN that fully captures its key features. Under mild assumptions, we establish the algorithmic and statistical rates of convergence for the action-value functions of the iterative policy sequence obtained by DQN. In particular, the statistical error characterizes the bias and variance that arise from approximating the action-value function using deep neural network, while the algorithmic error converges to zero at a geometric rate. As a byproduct, our analysis provides justifications for the techniques of experience replay and target network, which are crucial to the empirical success of DQN. Furthermore, as a simple extension of DQN, we propose the Minimax-DQN algorithm for zero-sum Markov game with two players. Borrowing the analysis of DQN, we also quantify the difference between the policies obtained by Minimax-DQN and the Nash equilibrium of the Markov game in terms of both the algorithmic and statistical rates of convergence.

1 Introduction

The paper addresses the theory–practice gap in deep reinforcement learning by analyzing a simplified DQN and extending the analysis to two-player zero-sum Markov games.

  • Motivation: Existing reinforcement-learning theory mainly covers tabular or linear value functions, while deep neural-network approximation creates a highly nonconvex analysis problem.This leaves the algorithmic and statistical behavior of deep reinforcement learning less understood.
  • DQN mechanisms: Experience replay samples minibatches from stored trajectories to break temporal dependence and improve training stability.The target network is separately synchronized with the Q-network, creating a second source of structure in DQN.
  • Approach: The paper analyzes neural fitted Q-iteration as a simplification of DQN that retains experience replay and target-network features.The analysis uses an independence assumption, ReLU networks, and large batches; the target network becomes a value-iteration step.
  • Contributions: Minimax-DQN extends DQN to two-player zero-sum Markov games and yields algorithmic and statistical convergence rates for the returned policies.Its target values are obtained by solving the Nash equilibrium of a zero-sum matrix game via linear programming.
  • Contributions: The authors establish algorithmic and statistical convergence rates for neural FQI, with statistical error reflecting ReLU approximation bias and finite-sample effects.The algorithmic error converges geometrically up to intrinsic statistical error.

2 Background

The background defines discounted Markov decision processes, optimal action values, Bellman operators, and the sparse ReLU network classes used to analyze DQN.

  • Markov decision processes: A discounted Markov decision process consists of states, actions, transition and reward distributions, and discount factor γ ∈ (0, 1).The transition kernel and reward distribution are unknown to decision makers, who learn through interaction.
  • Markov decision processes: A policy maps each state to an action distribution, and its value function is the cumulative discounted reward obtained under that policy.The action-value function evaluates a state–action pair under a policy.
  • Optimality: The optimal action-value function is the supremum over policies, and the optimal policy is greedy with respect to it.The optimal value satisfies the Bellman optimality equation TQ* = Q*.
  • Optimality: The Bellman operator is γ-contractive in the supremum norm, producing value iteration with geometric convergence toward Q*.Value iteration repeatedly applies the Bellman operator from an arbitrary initialization.
  • ReLU networks: The analysis uses bounded sparse ReLU networks, whose layers compose affine transformations with σ(u) = max(u, 0).The network class restricts weights and sparsity while matching the boundedness of reinforcement-learning value functions.
  • Function regularity: Compositions of Hölder-smooth functions model mappings whose components depend on only subsets of their inputs, enabling dimension-adaptive analysis.The relevant smoothness and input-dependence parameters determine the refined statistical behavior.

3 Understanding Deep Q-Network

The paper interprets DQN through neural fitted Q-iteration, explaining experience replay and target networks while isolating assumptions needed for statistical analysis.

  • Experience replay: Experience replay stores transitions and samples independent minibatches to reduce temporal correlation and stabilize stochastic-gradient training.The simplified analysis replaces replay sampling with i.i.d. transitions from a fixed distribution.
  • Target network: The target network makes the regression target independent of the updated network parameters, separating Bellman-error estimation from parameter-dependent bias.Without it, minimizing the empirical loss can differ substantially from minimizing the mean-squared Bellman error.
  • Target network: Holding the target network fixed and then synchronizing it corresponds, in the ideal realizable case, to one step of value iteration on neural-network functions.The target network is held fixed for T_target steps before being updated from the Q-network.
  • Neural FQI: Neural FQI repeatedly fits a function to Bellman targets, producing approximate operator updates eQ_k+1 ≈ T eQ_k.Its final estimator composes the learned approximate Bellman operators across iterations.
  • Analytical simplification: The analysis assumes global optima for the nonconvex neural-network regression subproblems and i.i.d. data to focus on statistical properties.The authors note that fixed data from a single trajectory could be handled using mixing-time analysis.

4 Theoretical Results

The theoretical analysis models DQN with sparse ReLU networks and compositional Hölder-smooth targets under Bellman-completeness and distribution assumptions. It decomposes convergence into statistical and algorithmic errors, yielding rates that exploit compositional structure and recover minimax-optimal rates in smooth examples.

  • Function classes and assumptions: The analysis uses sparse ReLU networks F0 to approximate compositional Hölder-smooth target functions G0, assuming Bellman closure through Tf ∈ G0.This makes the target functions in each fitted-Q iteration compatible with the approximation class while preserving a broad family of smooth functions.
  • Function classes and assumptions: The assumptions hold for MDPs with sufficiently smooth rewards and transition densities, and can also hold with deterministic transitions when the reward and transition functions have suitable compositional smoothness.The analysis also uses concentration and distribution-shift assumptions relating sampling distributions to future-state distributions.
  • Convergence rates: Theorem 4.4 bounds the policy-value error as the sum of statistical and algorithmic errors.The statistical component reflects estimation and approximation difficulty, while the algorithmic component decays geometrically with the number of iterations.
  • Convergence rates: After sufficiently many iterations, the algorithmic error is dominated by the statistical error, which decreases as the per-iteration sample size grows.The resulting rate scales linearly with the action-space capacity and vanishes as n increases, up to logarithmic factors under the stated constant-parameter view.
  • Examples and approximation effects: The compositional structure yields refined rates that adapt to the intrinsic difficulty of solving each fitted-Q iteration.The analysis identifies approximation bias and estimation variance from representing action-value functions with deep ReLU networks.
  • Examples and approximation effects: For Hölder-smooth rewards and transition kernels, the rate is |A|·n^-β/(2β+r), achieving the minimax-optimal rate for the specified Hölder class.For additive structure, the rate becomes |A|·n^-β/(2β+1), avoiding explicit dependence on input dimension r.

5 Extension to Two-Player Zero-Sum Markov Games

The paper extends DQN to two-player zero-sum Markov games through Minimax-DQN and analyzes a fitted-Q-iteration variant. The analysis bounds the distance between returned policies and the Nash equilibrium using statistical and geometrically decaying algorithmic errors.

  • Extension and algorithm: Minimax-DQN combines DQN with Minimax-Q learning for two-player zero-sum Markov games.Its target values are computed by solving a zero-sum matrix game rather than maximizing over one action space.
  • Equilibrium target: The equilibrium policy associated with the minimax function Q∗ achieves the Markov game's Nash equilibrium.Learning the Nash equilibrium therefore reduces to estimating Q∗, the unique fixed point of the Bellman operator.
  • Extension and algorithm: The Minimax-DQN target network is updated periodically, while training uses replayed transition samples and neural-network action-value approximation.The fitted analysis replaces replay-memory sampling with i.i.d. state-action tuples from a fixed distribution.
  • Theoretical guarantees: The Minimax-FQI bound separates statistical error from algorithmic error when measuring distance to the Nash-equilibrium policy.Statistical error reflects neural-network approximation bias and variance, while algorithmic error decays geometrically with the iteration count K.
  • Theoretical guarantees: The statistical rate scales linearly with the capacity of the joint action space and recovers the single-agent rate when |B| = 1.The rate n^(α∗−1)/2 is described as optimal for nonparametric regression with compositional structure.

6 Proof of the Main Theorem

The proof decomposes fitted-Q-iteration error into one-step approximation error and its propagation across iterations. It characterizes approximation bias from ReLU networks and variance from finite-sample estimation, then uses these bounds to establish convergence.

  • Proof strategy: The proof first quantifies how action-value approximation error propagates through each fitted-Q-iteration step, then bounds the one-step error for ReLU networks.These are identified as the two key ingredients of the main analysis.
  • Error propagation: Theorem 6.1 bounds the final action-value and policy error using the one-step approximation errors of the fitted-Q-iteration iterates.The theorem concerns the one-step greedy policy with respect to the final estimator.
  • One-step approximation: Theorem 6.2 decomposes one-step estimation error into approximation bias and finite-sample variance over a function class.The bias term measures how well ReLU networks approximate the Bellman target, while covering numbers control uniform estimation variance.
  • ReLU approximation: The ReLU approximation construction represents compositional Hölder-smooth functions as compositions of approximating subnetworks.The proof builds approximations for component functions, stacks them, and embeds the resulting network into the target function class.
  • ReLU approximation: The resulting approximation error combines a term decreasing with network size and a term decreasing with the smoothness-dependent exponent β_j/t_j.The displayed bounds retain both the depth/width construction and the smoothness-dependent approximation contribution.

7 Conclusion

The paper theoretically analyzes a ReLU-network fitted-Q-iteration simplification of DQN and establishes statistical and algorithmic convergence guarantees. It also extends the framework to Minimax-DQN for two-player zero-sum Markov games and identifies continuous-action analysis as future work.

  • Conclusion: The paper studies DQN statistically through fitted Q-iteration with ReLU networks, a modification intended to capture DQN's key features.The analysis neglects computational issues and considers both sample size and iteration count increasing.
  • Conclusion: Under mild assumptions, the resulting policy sequence converges in value to the optimal value function with characterized statistical and algorithmic rates.The conclusion also identifies theoretical justification for DQN's target-network technique.
  • Conclusion: The paper proposes Minimax-DQN and provides theoretical guarantees for its extension to two-player zero-sum Markov games.The guarantees use the DQN analysis to study convergence toward the game's Nash equilibrium.
  • Future work: Analyzing methods for continuous-action MDPs is identified as a future research direction.The examples include soft Q-learning and deep deterministic policy gradient.

A Deep Q-Network

DQN combines experience replay and a target network with neural-network action-value approximation. Its Minimax-DQN extension replaces maximization-based targets with targets obtained from zero-sum matrix-game equilibria.

  • Deep Q-Network: DQN uses experience replay and a target network as two key techniques associated with its empirical success.Experience replay samples minibatches from stored MDP transitions, while the target network is updated periodically.
  • Deep Q-Network: Experience replay stores transitions and samples random minibatches to train the Q-network.Each sampled transition supplies a reward and next state for computing a target using the target network.
  • Deep Q-Network: The target network computes Yi = ri + γ · maxa∈A Qθ⋆(s′i, a), and its parameters are synchronized with the Q-network every Ttarget steps.The resulting Q-network and its greedy policy are returned as the algorithm output.
  • Minimax-DQN: Minimax-DQN extends DQN to two-player zero-sum Markov games by computing targets through a zero-sum matrix game rather than action maximization.The algorithm uses equilibrium policies and retains experience replay and target networks.

B Computational Aspect of DQN

The computational analysis simplifies DQN into neural fitted Q-iteration with overparametrized two-layer ReLU networks and projected SGD. The framework connects neural-network training to linearized random-feature and RKHS analyses.

  • Computational setup: The analysis assumes global optimization of each nonlinear least-squares subproblem because it focuses on statistical analysis.The paper notes that overparametrized networks can support convergence of stochastic gradient descent to empirical global minima.
  • Neural-network representation: The Q-network is a two-layer ReLU network with 2m neurons, with weights W optimized while the output coefficients b remain fixed during training.The construction uses symmetric initialization and packs states and one-hot actions into a Euclidean input vector.
  • Fitted Q-iteration: Each fitted-Q iteration forms a least-squares regression target from the previous Q-network and solves the subproblem with projected SGD.Fresh observations are sampled during SGD, and the resulting estimator becomes the next Q-network.
  • Neural tangent-kernel analysis: For sufficiently wide networks, the analysis uses neural tangent-kernel linearization and connects the resulting random-feature class to an RKHS.The linearized class approaches an RKHS norm ball as the width m increases.
  • Performance characterization: The performance error decomposes into statistical and algorithmic components, with the algorithmic component converging linearly as the number of FQI iterations K increases.With T ≍ m projected SGD steps and constant B, the estimator has error O(m−1/8).

B.1 Proof of Theorem B.3

The proof bounds each fitted-Q update through approximation and projected-SGD analyses, then combines these one-step errors to obtain the final policy guarantee. The resulting bound separates statistical error from an algorithmic term that decreases linearly with the iteration count.

  • Proof strategy: The proof defines the maximum one-step approximation error as εmax = maxk∈[K] Einit[∥T eQk−1 −eQk∥σ].This quantity measures the largest expected error across fitted-Q iterations.
  • Function-class approximation: The proof connects the target function T eQk−1 and the learned network eQk through the function classes GB and FB,m.GB contains the Bellman target under the stated assumption, while FB,m provides approximations for both the target and learned network.
  • Function-class approximation: For sufficiently large width m, the neural network is close to its linearization around initialization, controlling the difference between eQk and a function in FB,m.This step uses the linearization-error lemma.
  • Function-class approximation: The proof separately approximates functions in GB by random-feature functions in FB,m as m increases.This establishes the second approximation link needed before analyzing projected SGD.
  • Projected-SGD analysis: Projected SGD contributes an update error bounded by O(B2 · T −1/2 + B3 · m−1/2 + B5/2 · m−1/4).The bound is obtained under Assumption B.2 with η = O(1/T).

C Proofs of Auxiliary Results

This section presents proofs for the auxiliary results used to establish the paper’s main theorem.

  • Auxiliary results: The auxiliary-results proofs support Theorems 6.1 and 6.2, which are used to establish the main result.The passage introduces the proof section without specifying the individual auxiliary arguments.

C.1 Proof of Theorem 6.1

The proof bounds DQN’s value-function error through recursive error propagation, then relates the greedy policy’s suboptimality to approximation error and derives an expected-norm bound.

  • Proof strategy: The proof decomposes the analysis into three steps: value-error recursion, greedy-policy suboptimality, and an expected-norm bound.The final step uses a fixed distribution over state-action pairs.
  • Step (i): Error propagation: The one-step value error is sandwiched between transition-operator terms involving the current error and the approximation error.The corresponding upper and lower bounds are expressed using the optimal and greedy policies’ transition operators.
  • Step (i): Error propagation: Lemma C.2 extends the one-step recursion to multiple iterations, bounding propagated initial error together with accumulated approximation errors.The bounds are obtained by repeatedly applying the one-step inequalities and composing linear transition operators.
  • Step (ii): Policy suboptimality: The greedy policy’s suboptimality is bounded by applying the inverse contraction operator to the difference between optimal and approximate value errors.Invertibility follows because each policy Bellman operator is γ-contractive.
  • Step (iii): Expected error: The resulting bound for Q*−QπK combines weighted propagated approximation errors with a geometrically decaying initial-error term.The proof then takes expectations under μ and controls the propagated terms using concentration coefficients.

C.2 Proof of Theorem 6.2

The proof establishes a one-step statistical error bound for nonlinear least-squares Bellman regression by separating approximation, estimation, and distribution-transfer terms.

  • Regression formulation: The Bellman target TQ is the conditional expectation in the nonlinear least-squares problem, but it need not belong to the function class F.The analysis therefore introduces the best approximation of TQ in F.
  • Final bound: The final one-step bound contains a variance term scaling with Vmax and log Nδ/n, plus approximation terms involving δ and the population error.The displayed intermediate bound includes constants and an adjustable parameter ǫ.
  • Statistical control: The estimation analysis uses a δ-cover of F, centered sub-Gaussian variables, and concentration inequalities to control empirical deviations.The covering number Nδ enters through a union bound over cover elements.
  • Distribution transfer: The population-risk analysis transfers bounds from the sampling distribution to an independent reference distribution using Bernstein’s inequality.The proof bounds the relevant bounded random variables and integrates their tail probabilities.

D Proof of Theorem 5.4

The proof of Theorem 5.4 combines error propagation with a one-step statistical bound for Minimax-FQI and specializes the result to ReLU Q-networks.

  • Proof strategy: The proof requires two ingredients: error propagation and the statistical error incurred by one Minimax-FQI step.The propagation analysis is related to prior approximate modified policy-iteration results.
  • Minimax-FQI regression: The Minimax-FQI regression target is the Bellman operator applied to the current action-value function, and the iterate is obtained by least-squares fitting.The response variable incorporates the first player’s reward and the next state.
  • One-step bound: The one-step statistical bound depends on the covering number of the function class and includes approximation error controlled by δ.The theorem states the result for bounded measurable function classes under the specified sampling distribution.
  • ReLU specialization: Specializing to ReLU Q-networks with ǫ=1 and δ=1/n reduces the bound to a term involving the 1/n-covering number of the network class.The proof separately bounds ReLU approximation error and the covering number.

D.1 Proof of Theorem D.1

The proof of Theorem D.1 analyzes Minimax-DQN by recursively propagating value-function errors, bounding equilibrium-policy suboptimality, and controlling the resulting expected error.

  • Step (ii): Policy suboptimality: Unlike the MDP proof, the Markov-game analysis requires refined treatment because the opponent induces a nonlinear Bellman operator.The nonlinearity arises from minimization in the operator.
  • Step (i): Error propagation: Minimax-DQN’s recursion sandwiches the next value error between transition-operator terms for equilibrium and best-response policies plus one-step approximation error.The opponent’s response policies are explicitly included in the transition operators.
  • Step (i): Error propagation: Lemma D.4 iterates this recursion to produce upper and lower bounds for error propagation across multiple Minimax-DQN iterations.The proof relies on linearity of the joint-policy transition operator.
  • Step (ii): Policy suboptimality: The policy analysis bounds the suboptimality of the equilibrium policies produced by the algorithm through the approximate and optimal action-value functions.The relevant value function uses the first player’s policy against the second player’s best response.
  • Step (iii): Expected error: The final expected-error bound combines weighted one-step approximation errors, discount factors, and concentration parameters under Assumption 5.3.The maximum one-step approximation error is εmax=maxk∈[K] ∥̺k∥σ, and the concentration-weighted sum is bounded by φµ,ν.
Loading 1901.00137v3…