Beyond the Independence Assumption: Finite-Sample Guarantees for Deep Q-Learning under τ \tau -Mixing
Leon Halgryn, Sophie Langer, Janusz M. Meylahn, E. Moritz Hahn · 2026
Read Beyond the Independence Assumption: Finite-Sample Guarantees for Deep Q-Learning under τ \tau -Mixing by Leon Halgryn, Sophie Langer, Janusz M. Meylahn, E. Moritz Hahn (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-06373.txt.
Introduction
Leon Halgryn, Sophie Langer, Janusz M. Meylahn, and E. Moritz Hahn give finite-sample bounds for deep Q-learning when replay data are not independent. Analyses usually pretend sampled minibatches are independent, yet they come from time-linked trajectories. The authors model the minibatches as tau-mixing, a formal way of saying dependence fades over time.
They show that assumption holds under stated conditions on trajectories and sampling, then treat each network update as a regression problem with dependent data. The resulting risk bounds show dependence slows the statistical rate, reflecting a smaller effective sample size. Tests on standard Gymnasium tasks confirm that this assumption often fails.
Catalog record
| CREATOR | Leon Halgryn, Sophie Langer, Janusz M. Meylahn, E. Moritz Hahn |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 137 KB |
| LICENSE | http://creativecommons.org/licenses/by-sa/4.0/ |
| RIGHTS | CC BY SA |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.06373
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Beyond the Independence Assumption: Finite-Sample Guarantees for Deep Q-Learning under τ \tau -Mixing Leon Halgryn, Sophie Langer, Janusz M. Meylahn, E. Moritz Hahn Abstract Finite-sample analyses of deep Q-learning typically treat replayed data as independent, even though it is sampled from temporally dependent state-action trajectories. We study the Deep Q-networks (DQN) algorithm under explicit dependence by modelling the minibatches used for updating the network as τ \tau -mixing. We show that this assumption holds under certain dependence conditions on the underlying trajectories and the mechanism used to sample minibatches. Building on this observation, we extend statistical analyses of DQN with fully connected ReLU architectures to dependent data. We formulate each update as a nonparametric regression problem with τ \tau -mixing observations and derive finite-sample risk bounds under this dependence structure. Our results show that temporal dependence leads to a degradation in the statistical rate by inducing an additional dimensionality penalty in the rate exponent, reflecting the reduced effective sample size of τ \tau -mixing data. Moreover, we derive the sample complexity of DQN under τ \tau -mixing from these risk bounds. Finally, we empirically demonstrate on standard Gymnasium environments that the independence assumption is systematically violated and that replay sampling yields approximately exponentially decaying correlations, supporting our theoretical framework. 1 Introduction Reinforcement learning (RL) addresses sequential decision-making problems in which data are generated through interaction with an environment. In value-based methods such as deep Q-learning, this amounts to learning the action-value (Q-)function from data using function approximation. Modern approaches rely on deep neural networks, enabling applications in high-dimensional settings. This paradigm has achieved remarkable empirical success, from Atari games with Deep Q-Networks (DQN) ( 27 ) to large-scale game-playing systems such as AlphaZero ( 33 ) , AlphaStar ( 39 ) , and MuZero ( 32 ) . From the theoretical perspective, RL is well understood in the tabular setting, where sharp finite-sample guarantees are available ( ( 2 ; 15 ; 37 ; 13 ) ), and extends to structured function approximation such as linear models ( ( 16 ) ). However, analyzing nonlinear function approximation, especially deep neural networks, remains challenging. A common approach in recent analyses of deep Q-learning (e.g., 10 ) is to view each update as a supervised learning problem, where the Q-function is estimated from sample transitions. This reduction enables the use of classical empirical process techniques, but typically relies on the assumption that the training data are independent and identically distributed (i.i.d.). In practice, however, data are generated sequentially through agent-environment interaction and stored in a replay buffer, inducing temporal dependence. As a result, the i.i.d. assumption abstracts away the sequential nature of data collection in RL and creates a mismatch between theoretical guarantees and practical implications. This raises the question: Do the same theoretical guarantees hold under temporal dependence? To address this, we model the state-action trajectory in the replay buffer as weakly dependent (either \beta - or \tau -mixing) and show that, under appropriate sampling schemes, the induced minibatches are \tau -mixing. We establish statistical convergence rates for fitted Q-iteration with deep neural networks under temporally dependent data, showing that \tau -mixing dependence degrades the rate through a reduced effective sample size. Building on 10 , we extend their supervised learning framework to this dependent setting and quantify the resulting loss in statistical efficiency. We focus on fully connected feedforward neural networks, which include sparse architectures as a special case. We consider Bellman operators for which, for the relevant class of Q-functions, the backup \mathcal{T}Q admits a compositional or low-intrinsic-dimensional representation, or a combination of both. The low-dimensional structure may occur either at the input level, through dependence on a small subset of state-action coordinates, or internally, through low-dimensional intermediate representations in the composition. This is motivated by the structure of many RL problems: rewards often depend on a small number of task-relevant variables, transition dynamics frequently factor into local or modular mechanisms, and the reachable state-action space may concentrate near a low-dimensional latent manifold. Since the Bellman backup combines the reward, transition kernel, and continuation value, such environmental structure can be inherited by \mathcal{T}Q . Empirically, we observe across several standard Gymnasium environments ( 36 ) that RL trajectories and replay buffer data violate the independence assumption, while sampled minibatches exhibit approximately exponential decay of correlations, supporting our theoretical framework. To summarize, our contributions are as follows: • We extend finite-sample guarantees for DQN to dependent data and fully connected ReLU networks under structured Bellman operators that are compositional, low-dimensional, or both. We show that temporal dependence degrades statistical rates via an additional dimensionality penalty in the rate exponent, and derive the corresponding sample complexity under \tau -mixing. • We show that if the underlying state-action process is exponentially \beta - or \tau -mixing, then the sampled minibatches are exponentially \tau -mixing provided an order-preserving, duplicate-free sampler is used. Moreover, we show why the standard DQN sampling scheme (uniform with replacement) is problematic and introduce a contiguous block sampler that provides some control over the rate of decay of correlations in the minibatches. • We design an estimator for analyzing weak dependence and use this in experiments to (i) show that the i.i.d. assumption is violated for standard Gymnasium environments ( 36 ) , and (ii) empirically assess our assumption on the minibatch dependence. Related Work. A growing line of work establishes finite-sample guarantees for deep value-based RL. 10 analyze neural fitted Q -iteration as an idealized form of DQN and obtain convergence rates to the optimal Q -function for sparse ReLU networks. Subsequent work studies convergence and sample complexity of neural temporal-difference (TD) and Q -learning, including overparameterized regimes and mean-field limits ( 5 ; 34 ; 44 ; 40 ; 35 ; 17 ) . More directly related to DQN, 43 provide convergence and sample-complexity guarantees under \epsilon -greedy exploration, while 22 establish regret bounds under smoothness assumptions. Most existing analyses assume i.i.d. replay samples or independence across updates. Some works account for dependence at the trajectory level using Markovian or mixing assumptions ( 40 ; 17 ; 1 ) . Relatedly, 9 analyze replay buffers as stochastic processes and show that specific replay sampling schemes can decorrelate trajectories. Instead, our work studies how the remaining temporal dependence affects the statistical convergence rates of replay-based DQN. Our analysis builds on viewing DQN updates as supervised regression problems under dependent data. While neural network estimators are well understood in the i.i.d. setting ( 31 ; 19 ; 14 ; 29 ) , only limited results exist under dependence, including \alpha -mixing ( 24 ) , \psi -mixing ( 18 ) and \tau -mixing ( 23 ) . The latter is most closely related to our work, but focuses on sparse networks, more restrictive function classes, and is not embedded in RL. Our work combines these learning-theoretic tools with mixing-process techniques ( 41 ; 8 ; 7 ; 26 ) to analyze the dependent regression problems arising in DQN. Notation. For n\in\mathbb{N} and a,b\in\mathbb{R} , write [n]:=\{1,\dots,n\} , a\lor b:=\max\{a,b\} , and a\land b:=\min\{a,b\} . For x\in\mathbb{R} , let \lfloor x\rfloor and \lceil x\rceil denote the floor and ceiling of x , respectively. For positive sequences \{f(n),g(n)\}_{n\geq 1} , we