Fitted Q-Iteration with Continuous Actions and Adaptive Data: Smoothed Coverage and Minimax Rates

The gist: This work provides a unified theoretical framework for Fitted Q-Iteration (FQI) on general measurable Borel spaces, establishing a finite-sample, adaptive-data performance bound by chaining measure-theoretic probability with Bellman-operator contraction in Banach spaces.

Measure theoretic MDP Foundations

The paper addresses the gap between measure-theoretic MDP foundations and modern deep RL by bridging three isolated traditions: (i) exact dynamic programming on general spaces, (ii) deterministic error propagation analysis, and (iii) PAC generalization bounds for simplified topologies The framework is built upon establishing the necessary measure-theoretic infrastructure, including joint measurability of transition kernels and the existence of measurable optimal selectors It defines an infinite-horizon discounted Markov Decision Process (MDP) as a tuple (S, ΣS, A, ΣA, P, r, γ), where P is a transition kernel and r is a bounded measurable reward function Action values are viewed as elements of the Banach space Q = B(S × A, ΣS ⊗ ΣA) because completeness ensures iterative updates have well-defined limits Bellman operators Tπ and T∗Q are defined as functional mappings on Q, and under Assumption 1 (Action-space regularity), the policy-conditioned transition operator Pπ is a nonexpansive linear operator, meaning∥Pπ∥∞ ≤ 1

Bellman Contraction and Fixed Points

The core theoretical result relies on the contraction property of the Bellman operators in Banach spaces Theorem 1 proves that for every measurable policy π, the Bellman expectation operator Tπ is a γ-contraction on (Q,∥ ·∥∞), and similarly for the Bellman optimality operator T∗Q on Q0 This contraction ensures the existence of unique fixed points Qπ ∈ Q and Q∗ ∈ Q0 satisfying TπQπ = Qπ and T∗Q∗ = Q These fixed points admit a direct trajectory-measure characterization on general Borel spaces via the Ionescu–Tulcea theorem The standard policy-iteration analysis on this Banach space yields the dominance chain Qk ≤ Qπk ≤ Q and uniform convergence∥Q − Qπk∥∞ → 0 as k → ∞

Approximate Dynamic Programming and Error Propagation

The paper formalizes Fitted Q-Iteration (FQI) as an algorithm where Bellman updates are approximated through supervised regression, starting from an initial Q0 ∈ F The fundamental tension is the norm mismatch between the L2(µ) geometry of empirical regression and the L∞ geometry of Bellman updates Lemma 4 quantifies how per-step Bellman residuals εk = Qk+1 − T∗Qk propagate across iterations, recovering the classical 2γ/(1 − γ) rate in the sup-norm specialisation∥εk∥∞ ≤ ε Furthermore, it quantifies distribution mismatch via the all-policy uniform-marginal concentrability coefficient C which uniformly dominates every state–action marginal generated by an arbitrary non-stationary Markov policy

Adaptive Data and Sequential Rademacher Complexity

To handle modern off-policy deep RL with history-dependent, non-i.i.d sampling, the analysis extends to sequential Rademacher complexity The analysis proceeds in three stages: a sequential generalization theorem for adaptive Bellman regression (Theorem 2), a per-iteration FQI update-residual bound (Theorem 3), and a final greedy-policy performance guarantee under adaptive concentrability (Theorem 4) Theorem 3 decomposes the realized Bellman residual εk into its structural, statistical, and optimization-driven components: εk ≤ εapp,k + q2 α′k(δ/K) + εopt,k The final performance bound (Theorem 4) shows that the greedy policy πbK satisfies∥V∗ − VπbK∥1,ρ ≤ 4√C(1 − γ)2(1 − γK)εapp,k + q2α′k(δ/K)+8BγK/(1 − γ)

Global Complexity and Performance Rates

The analysis connects the sequential Rademacher complexity to function class properties through Proposition 2, which shows that for Sobolev classes F†, the global sequential Rademacher complexity satisfies c1√n ≤ Rseq n(F†) ≤ c2√n This leads to a standard slow rate residual scaling in Theorem 4, up to logarithmic factors, rather than a Sobolev-optimal fast rate Proposition 3 demonstrates that linear classes yield an n−1/4 rate and norm-controlled neural networks contribute only width-independent factors when norm constraints do not grow with width

Extension to Online Regret

The paper identifies a structural gap between final-policy guarantees and cumulative online regret, noting that sequential Rademacher complexity controls estimation error under a fixed data distribution, but online regret requires controlling how the data distribution evolves with the learner’s policy It proposes two routes to bridge this gap: (i) stronger uniform coverage assumptions over policy-induced occupancies, and (ii) algorithmic stability or exploration mechanisms that control distribution drift The analysis shows that under strong uniform coverage assumption (41), one can obtain a cumulative bound Xn k=1 Eρk V∗ − Vπbk ≲ 1/(1 − γ)3∥Q∗ − Qb0∥∞ + pCad nX−1 j=0 bj

Total Error Decomposition

Theorem 8 provides a decomposition of the Bellman residual of Qbk+1 - T∗Qbk into three terms: transition–target noise εest,P,k (statistical), sampling/design error εest,µ,k (statistical), and inherent Bellman approximation error εapprox,k (structural) This decomposition shows that the first two terms vanish as n → ∞ while the third is independent of n

Open Questions

The paper concludes by highlighting three critical directions for future investigation: first, extending the analysis to cumulative online regret governing the entire policy sequence requires additional control of the diagonal residual Qbt − T∗Qbt via either iterate stability, direct diagonal-residual minimisation, or optimism-based exploration Second, integrating cutting-edge stochastic optimisation theory would bridge theoretical global optima and the empirical landscapes of neural networks Third, the adaptive concentrability hypothesis requires that the predictable design measures cover the residual-evaluation measures of the final policy

Conclusion

The framework successfully grounds modern off-policy deep RL on Borel transition systems by providing a complete chain from Borel well-posedness to sequential Rademacher generalization This provides a rigorous metric-aware foundation for adaptive-data FQI on continuous spaces

How it works

The analysis proceeds via a three-stage derivation in Section 3: first, covering sequential generalization, second, per-iteration update-residual bound, and third, final greedy-policy performance guarantee The key mechanism is the residual certificate proposition which identifies the controls that upgrade these to a cumulative online regret theorem The framework uses sequential Rademacher complexity to control empirical-process deviations along arbitrary predictable trees

Distribution Mismatch and Coverage

The distribution mismatch mechanism is quantified by the all-policy uniform-marginal concentrability coefficient C, which uniformly dominates every state–action marginal generated by an arbitrary non-stationary Markov policy This assumption quantifies the degree of distribution shift between the data-generating process and the policies induced during learning Assumption 5 requires coverage of the residual-evaluation measures of the final greedy policy πbK by the predictable design measures µk

1. The improved system can perform finite-sample, adaptive-data performance bound by chaining measure-theoretic probability with Bellman-operator contraction in Banach spaces, providing a rigorous theoretical foundation for off-policy deep RL on continuous state and action spaces.

2. The system can achieve a cumulative, pathwise online regret guarantee for FQI in continuous spaces by leveraging sequential Rademacher complexity to control the empirical process deviations along arbitrary predictable trees.

3. The system can utilize a generalized performance bound, as stated in Theorem 4: ∥V∗ − VπbK∥1,ρ ≤ 4√C(1 − γ)2(1−γK)εapp + q2α′k(δ/K)+εopt,k + 8BγK/1−γ, to guarantee the suboptimality of the final greedy policy.

4. The system can operate effectively under adaptive data collection protocols where the conditional law of each transition may depend arbitrarily on the past data and on the current iterate, by using a predictable average design measure and controlling distribution shift via an all-policy uniform-marginal concentrability coefficient C.

5. The system can be deployed with robustness against estimation noise, as shown in Theorem 8, where the Bellman residual decomposes into three terms: transition–target noise term, sampling/design error, and inherent Bellman approximation error.

Fitted Q-iteration (FQI) is well understood when the data come from a fixed distribution and the action set is finite, whereas value-based continuous control collects its data adaptively and maximizes over continuous actions. Both features break the standard analysis: the regression data are dependent, and every density-ratio concentrability coefficient of a deterministic greedy policy is infinite when the exploration has no atoms. Conditioning on the history freezes the regression target, so each round of FQI is a regression with martingale noise, and we obtain localized rates that are fast for classes of polylogarithmic metric entropy. We transfer the regression error to the loss of the greedy policy by smoothing the measures on which this loss is evaluated, at a price that depends on the action dimension and the smoothness of the residuals in the action. Under deterministic dynamics the state is smoothed as well, and the state dimension enters the price. Minimax lower bounds with the same exponents in the sample size show that no learner avoids these prices, for restart data in the case of the state dimension. The coverage conditions do not involve the unknown greedy policies; they hold under exploration floors with restarts and, for action smoothing, bounded transition densities.