# A Convergence Framework for Deep V-Learning: Error Propagation and Sharp Action-Gap Bounds

arXiv: https://arxiv.org/abs/2609.18782 · HTML: https://mlsanity.com/paper/2609.18782/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 48 references that are in the map.
- First posted on arXiv 16 Sep 2026.

## Builds on (most cited first, 19 of 19)

- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Crowd-Robot Interaction: Crowd-aware Robot Navigation with Attention-based Deep Reinforcement Learning](https://mlsanity.com/paper/1809.08835/) (2018)
- [Socially Aware Motion Planning with Deep Reinforcement Learning](https://mlsanity.com/paper/1703.08862/) (2017)
- [What are the Statistical Limits of Offline RL with Linear Function Approximation?](https://mlsanity.com/paper/2010.11895/) (2020)
- [Decentralized Non-communicating Multiagent Collision Avoidance with Deep Reinforcement Learning](https://mlsanity.com/paper/1609.07845/) (2016)
- [Batch Value-function Approximation with Only Realizability](https://mlsanity.com/paper/2008.04990/) (2020)
- [Finite-Sample Analysis for SARSA with Linear Function Approximation](https://mlsanity.com/paper/1902.02234/) (2019)
- [Exponential Lower Bounds for Batch Reinforcement Learning: Batch RL can be Exponentially Harder than Online RL](https://mlsanity.com/paper/2012.08005/) (2020)
- [Increasing the Action Gap: New Operators for Reinforcement Learning](https://mlsanity.com/paper/1512.04860/) (2015)
- [A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation](https://mlsanity.com/paper/1912.04511/) (2019)
- [On the Convergence and Sample Complexity Analysis of Deep Q-Networks with ε-Greedy Exploration](https://mlsanity.com/paper/2310.16173/) (2023)
- [Analysis of Stochastic Processes through Replay Buffers](https://mlsanity.com/paper/2206.12848/) (2022)
- [Convergence Results For Q-Learning With Experience Replay](https://mlsanity.com/paper/2112.04213/) (2021)
- [Robot Navigation with Entity-Based Collision Avoidance using Deep Reinforcement Learning](https://mlsanity.com/paper/2408.14183/) (2024)
- [Finite-Time Analysis of Temporal Difference Learning with Experience Replay](https://mlsanity.com/paper/2306.09746/) (2023)
- [Hybrid Motion Planning with Deep Reinforcement Learning for Mobile Robot Navigation](https://mlsanity.com/paper/2512.24651/) (2025)

## Abstract (arXiv)

We establish convergence bounds for deep V-learning with horizon H. The algorithm fits a scalar value function to targets from executed transitions and selects actions using a predictive model and the value function. For current observed-successor targets with fresh true-kernel outcomes, the conditional mean is Tβ V, which averages over behavior-policy actions. The Bellman optimality update is T V. We decompose the update error into six residuals: fitting, transition reuse, target construction, replay, action selection, and exploration. Under Ls concentrability, their Lp norms (p=s/(s-1)) control expected L1 policy loss. The bound explicitly weights residuals from only the last H-1 update blocks, plus an initialization term for shorter runs. We quantify the cost of a shared sampling distribution across horizon levels. For statistical error bounds of order n-nu, we derive optimal continuous allocations and an integer allocation whose objective is within a factor 2^nu of the constrained optimum. A margin condition with exponent α gives action error of order Lambda1+α/p, where Lambda combines network drift and score error; a one-step construction proves the exponent sharp. Bounds on the distance between frozen and optimal scores transfer an optimal-gap condition to frozen-iterate gap bounds while retaining the mass of optimal ties. Survival probabilities and coverage conditions at deployment yield bounds for policies selected with approximate scores. Separate spatial ReLU networks per horizon level give a conditional neural regression rate, and the finite-state case gives a log-free expected fit rate. These results give expected policy-loss consistency for the fixed-horizon generative-reset approximate-ERM procedure with exact action scores and provide an explicit residual-decay criterion for FIFO/interleaved SGD.