A Measure-Theoretic Finite-Sample Theory for Adaptive-Data Fitted Q-Iteration
Manuel Haußmann, Mustafa Mert Çelikok, Melih Kandemir · 2026
Read A Measure-Theoretic Finite-Sample Theory for Adaptive-Data Fitted Q-Iteration by Manuel Haußmann, Mustafa Mert Çelikok, Melih Kandemir (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-05791.txt.
Introduction
Haussmann and two colleagues close a gap between reinforcement-learning practice and theory. Deep off-policy methods control complex robots, yet theory has stayed confined to tabular or linearizable settings. The authors trace the gap to three isolated schools of work. Measure-based foundations ignore learning errors, error-propagation analysis lacks finite-sample estimation bounds, and generalization bounds cover only simplified topologies. Their unified framework treats fitted Q-iteration on general measurable spaces, a broad setting.
Linking measure-based probability with Bellman-operator contraction yields a finite-sample performance bound for adaptive data. Sequential Rademacher complexity is shown to control how well Bellman regression generalizes when the data collected depend on the policy in use. The analysis extends to the first cumulative online regret guarantee that holds path by path for fitted Q-iteration in continuous spaces. That lays foundations for formal study of deep reinforcement-learning algorithms.
Catalog record
| CREATOR | Manuel Haußmann, Mustafa Mert Çelikok, Melih Kandemir |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 134 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.05791
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Measure-Theoretic Finite-Sample Theory for Adaptive-Data Fitted Q-Iteration Manuel Haußmann, Mustafa Mert Çelikok, Melih Kandemir Abstract While reinforcement learning (RL) promises to revolutionize the control of complex nonlinear robotic systems, a profound gap persists between the heuristic success of model-free off-policy deep RL and the underlying theory, which remains largely confined to tabular or linearizable settings. We identify the cause of this gap as an emergent isolation of three traditions: (i) measure-theoretic MDP foundations on general spaces limit their analysis to exact dynamic programming and ignore all error sources of a learning process; (ii) deterministic error propagation analysis addresses the approximation error via concentrability coefficients without a finite-sample analysis of the estimation error; and (iii) PAC generalization bounds characterize the estimation errors of simplified topologies. We bridge these traditions with a unified theoretical framework for fitted Q-iteration (FQI) on general measurable Borel spaces. Our main result provides a finite-sample, adaptive-data performance bound by chaining measure-theoretic probability with Bellman-operator contraction in Banach spaces. We prove that sequential Rademacher complexity controls Bellman-regression generalization under policy-dependent data collection. We further extend this analysis to provide the first cumulative, pathwise online regret guarantee for FQI in continuous spaces. These results lay the necessary foundations for the formal analysis of many modern deep RL algorithms. 1 Introduction Reinforcement learning (RL) currently inhabits a paradoxical state of unreasonable effectiveness. The most celebrated milestones, the Sternstunden that have elevated RL to a core pillar of artificial intelligence, involve tasks of staggering cognitive and physical complexity. Successes range from superhuman mastery in Atari 2600 games ( Mnih et al. 2015 ) and board games such as Go ( Silver et al. 2016 ) to solving the ultra-sparse reward landscapes of StarCraft II ( Vinyals et al. 2019 ) , the psychological maneuvering of no-press Diplomacy ( FAIR et al. 2022 ; Bakhtin et al. 2023 ) and the transitioning from digital sandboxes to high-stakes physical systems, such as the real-time magnetic control of nuclear fusion plasmas in Tokamak reactors ( Degrave et al. 2022 ) . Remarkably, these successes rely almost exclusively on a specific recipe: off-policy, model-free RL using nonlinear function approximators in continuous or high-dimensional state-action spaces. Yet despite these triumphs, a rigorous theoretical foundation for this recipe remains elusive. This theory-to-practice gap persists because the fundamental components of modern RL (measure-theoretic generality, distributional stability, and statistical complexity) have evolved into three isolated traditions: • Measure-theoretic MDP theory. The rigorous treatment of Markov decision processes on general (uncountable) Borel state-action spaces was developed in the classical works of Blackwell 1965 ; Bertsekas and Shreve 1978 ; Strauch 1966 ; Schäl 1975 ; Hernández-Lerma and Lasserre 1996 ; Hernández-Lerma and Lasserre 1999 and continued in more modern analyses ( Feinberg et al. 2012 ) . These treatments develop the full measure-theoretic state-space machinery ( \sigma -algebras, stochastic kernels, and analytic sets) to establish Bellman contraction in Banach spaces of bounded measurable functions. Crucially, this work did not extend beyond exact dynamic programming, addressing neither function approximation nor statistical estimation. • Propagation of approximation error through Bellman backups. A second tradition, with precursors in weighted-norm contraction analysis ( Gordon 1995 ; Tsitsiklis and Van Roy 1996 ) , was initiated by Munos 2003 ; Munos 2007 and refined by Farahmand et al. 2010 ; Scherrer et al. 2015 ; Geist et al. 2019 ; Zhan et al. 2022 , focusing on the distribution-mismatch mechanism. These works study how per-iteration approximation errors compound across Bellman backups, utilizing concentrability coefficients to bridge behavior and target distributions. This tradition typically assumes that the underlying MDP infrastructure is well defined and leaves the formal measurability of trajectory measures and operator well-posedness unaddressed. • Finite-sample analysis of discrete or linear MDPs. Recent work bridges statistical learning theory and approximate dynamic programming (ADP) by introducing a formal statistical complexity measure to bound excess risk, typically via Rademacher complexity ( Duan et al. 2021 ) or covering numbers ( Munos and Szepesvári 2008 ) , building on foundational PAC-MDP and regret analyses ( Kearns and Singh 2002 ; Brafman and Tennenholtz 2002 ; Auer et al. 2008 ) . More recent online analyses adopt combinatorial measures such as the eluder dimension ( Wang et al. 2020 ) , Bellman rank ( Jiang et al. 2017 ) , and bilinear classes ( Du et al. 2021 ) . However, these results apply only to finite state spaces or simple linear models. Furthermore, because they rely on i.i.d. sampling assumptions and fixed data distributions, they address the batch setting almost exclusively, failing to account for the online adaptivity required in practical RL applications. Table 1 : RL research traditions. Each column is a layer of the unified theoretical chain we synthesise: a measure-theoretic state space, formal Bellman contraction in Banach spaces, the distribution-mismatch mechanism, the statistical complexity measure, and whether the framework handles sequential policy-dependent data collection. n/a marks components not applicable to the assumed setting. Our work bridges these traditions: measure-theoretic Bellman well-posedness and ADP error propagation combined with sequential Rademacher complexity to deliver finite-sample Bellman-regression and policy-performance guarantees under adaptive data collection. Measure theoretic state space Bellman contraction Distribution mismatch mechanism Statistical complexity measure Adaptive data Bertsekas and Shreve 1978 proved proved n/a n/a n/a Hernández-Lerma and Lasserre 1999 proved proved n/a n/a n/a Munos 2007 assumed assumed conct. coef. n/a n/a Farahmand et al. 2010 assumed assumed conct. coef. n/a n/a Munos and Szepesvári 2008 assumed assumed conct. coef. covering number no Duan et al. 2021 assumed assumed conct. coef. Rademacher no Jin et al. 2020 finite/linear n/a linear dim. linear dim. yes Jin et al. 2021 finite n/a eluder dim. Bellman–eluder yes Foster et al. 2021 finite n/a DEC decision–estim. yes Dong et al. 2021 finite n/a oracle seq. Rademacher * yes This work proved proved conct. coef. seq. Rademacher yes * Dong et al. 2021 adopt sequential Rademacher complexity but primarily within the context of a regression oracle on simplified topologies. The current theory-to-practice gap is a direct consequence of the structural fragmentation summarized in Table 1 . Because no existing framework could accommodate all five columns, it has been customary to trade off measure-theoretic rigor against statistical complexity. Specifically, the classical traditions that establish the Borel state space and Bellman contraction properties lack the statistical complexity measures necessary for finite-sample guarantees. Conversely, modern online analyses provide sharp finite-sample bounds, but they almost universally revert to discrete topologies or assume the distribution-mismatch mechanism without proving the necessary measure-theoretic infrastructure. Consequently, no existing regret bound for online RL with function approximation is formally justified on the continuous state-action spaces where the field achieves its greatest successes in applications. We bridge these isolated traditions with a self-contained theoretical framework for Fitted Q-Iteration (FQI) on general Borel spaces. We anchor our analysis in FQI because it serves as the fundamental algorithmic template for modern off-policy deep RL, where iterative Bellman updates are approximated through supervised regression. We develop an adaptive-data FQI analysis using sequential Rademacher complexity. Our three-stage derivation (covering sequential generalization, per-iteration residuals, and final policy suboptimality) cleanly separates sequential complexity, martingale concentration, and Bellman approximation error. A residual-certificate proposition identifies the controls that upgrade these to a cumulative online regret theorem. We instantiate