Research map / Learning theory and algorithms / Sample complexity

Universal Approximation Theorem of Deep Q-Networks

ICML 2025 · Learning theory and algorithms › Sample complexity · approach: Neural network approximation theory · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Gives a continuous-time FBSDE/stochastic-control framework for DQNs, proving residual-network DQNs can approximate Q* on compact high-probability sets and that a continuous-time Q-learning scheme converges under stated assumptions.

Problem

Theoretical understanding of universal approximation and convergence of Deep Q-Networks in continuous-time MDPs driven by square-integrable martingales lacks rigorous treatment.

Approach

Models DQN as residual-network approximator of Q* in a continuous-time controlled SDE driven by a martingale; uses large-deviation bounds to restrict to a compact set with high probability, applies ResNet universal approximation, and adapts stochastic approximation theorems for Q-learning convergence.

Key results

• Theorem: for any epsilon>0 and delta in (0,1), there is a compact set K_R on which the state stays with probability at least 1-delta and a residual DQN with sup-error below epsilon approximating Q* on K_R.
• Convergence theorem: under listed assumptions (ergodicity, Robbins-Monro rates, bounded targets, representability, gradient conditions), Q-learning iterates converge to Q* almost surely in sup norm.
• No experiments are reported; results are purely theoretical.

Limitations

• Approximation theorem gives existence only; no explicit rates for network size under continuity alone.
• Convergence relies on strong, hard-to-verify assumptions (representability, gradient negative-correlation condition) that the author says may not hold for neural networks.
• No empirical validation of the theory.

Experimental setup

Builds on: Q-learning DQN FBSDE stochastic approximation (Borkar-Meyn / ODE method) ResNet universal approximation

Closest papers by meaning

• On the Convergence and Sample Complexity Analysis of Deep Q-Networks with $\epsilon$-Greedy Exploration (NeurIPS 2023 · similarity 0.90)
• A Surrogate Perspective on Convergence of Fixed-Target DQN (NeurIPS 2026 · similarity 0.89)
• A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation (ICML 2020 · similarity 0.88)
• Stochastic Q-learning for Large Discrete Action Spaces (ICML 2024 · similarity 0.87)
• Towards Optimal Adversarial Robust Q-learning with Bellman Infinity-error (ICML 2024 · similarity 0.86)
• Deep learning for continuous-time stochastic control with jumps (NeurIPS 2025 · similarity 0.85)