CS Paper Radar

Q-Learning with Stable Infinite-Dimensional Linear Function Approximation

Shengbo Wang

cs.LG math.OCstat.ML ·submitted 2026-08-23 22:40 UTC · v1

Abstract

Q-learning with linear function approximation can be unstable because an arbitrary approximation architecture need not preserve the Bellman contraction. We develop a stable infinite-dimensional linear function approximation framework for Q-learning from a single Markovian behavior-policy trajectory. The learning variable is a coefficient field $θ\in C(\mathbb L)$ on a compact latent metric space $(\mathbb L,ρ)$. The framework uses a reconstruction operator that maps $θ$ to a continuous Q-function and a compression operator that maps Bellman updates back to latent coordinates. Nonexpansiveness of both operators induces a contractive latent Bellman map on $C(\mathbb L)$, with a unique fixed point $θ^*$ whose reconstruction approximates the optimal Q-function up to representation error. We propose two stochastic approximation (SA) algorithms and establish their sup-norm convergence bounds with a leading term of order $\widetilde O(n^{-1/2})$. The infinite-dimensional formulation provides a powerful abstraction for identifying the structures that govern statistical difficulty. Smoothness of the compression map in $ρ$ is inherited by $θ^*$ and the SA iterates, allowing uniform estimation errors to be controlled through covering numbers of $(\mathbb L,ρ)$ rather than the dimension of $C(\mathbb L)$. Remarkably, the SA algorithms we propose are agnostic to the choice of $ρ$, and thus can automatically adapt to both the smoothness and the geometry. We further illustrate the framework through Q-measure-learning with linear density approximation and output-layer neural weight training under a frozen pretrained network.

Closest papers

Nearest neighbours by meaning across the whole index.

Sharp Gaussian Approximation for Q-Learning

cs.LG stat.MLmath.ST ·2026-11-15 ·Xingtu Liu
theory similarity 0.73
Abstract

Gaussian approximation provides a foundation for online statistical inference in reinforcement learning. We establish sharp non-asymptotic Gaussian approximation rates in Wasserstein distance for asynchronous Q-learning with Polyak-Ruppert averaging. We prove an upper bound of $\widetilde{O}(n^{-1/4})$, where $n$ is the number of iterations, together with a matching lower bound up to logarithmic factors. Q-learning is more challenging to analyze than linear stochastic approximation due to the nonlinearity of the Bellman operator. Asynchronous updates introduce further challenges due to Markovian noise. Our analysis separates the errors from Bellman nonlinearity, Markovian noise, and the finite-sample covariance discrepancy. In particular, we show that Markovian noise induces an unavoidable bias even when the Bellman operator is linear. The trade-off between this bias and the covariance discrepancy determines the convergence rate. We further extend our analysis to the synchronous setting and establish a sharp rate of $\widetilde{O}(n^{-1/2})$.

0.17

$Q$ Can Play That Game: Online Fitted $Q$-Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation

cs.GT cs.MA ·2026-10-02 ·Kushagra Gupta, Jingqi Li, Cade Armstrong, Lasse Peters, Ross E. Allen +2 more
code/data similarity 0.71
Abstract

Zero-sum Markov games arise in a wide variety of sequential decision-making problems such as adversarial learning and planning against modeled uncertainties. However, prior work on finite-sample guarantees on the learned state-action value function ($Q$-function) for zero-sum Markov games is largely restricted to finite-action settings, or to continuous-action games in which agents have linear dynamics and quadratic rewards (i.e. linear-quadratic, or LQ, games). A central challenge in extending such guarantees to more general continuous-action zero-sum Markov games is that the associated Bellman operator involves a minimax problem that need not admit a tractable saddle-point solution. To this end, we first introduce a class of neural network function approximators for the $Q$-function that is convex-concave in the players' actions, which guarantees that this minimax problem admits a pure-strategy saddle point. We then study an online variant of fitted $Q$-iteration employing this function class and establish, to the best of our knowledge, the first finite-sample guarantees for non-LQ zero-sum Markov games with continuous states and actions. Our code can be found at https://github.com/CLeARoboticsLab/QCanPlayThatGame.

0.33

Non-asymptotic Convergence of Average-reward Q-learning with Options

cs.LG cs.AI ·2026-10-14 ·Kintan Saha, Ahana Deb, Anders Jonsson, Debabrota Basu
theory similarity 0.69
Abstract

We study the finite-sample convergence of Q-learning algorithms for the average-reward formulation of Reinforcement Learning (RL) with options. While options allow temporarily extended and hierarchical actions, the average-reward formulation incorporates continual tasks beyond discounted and episodic RL. We establish the first $\tilde{O}(1/\text{iterations})$ convergence guarantees, in the mean-square sense, for average-reward option Q-learning algorithms in both the inter- and intra-option settings. First, we prove that both inter- and intra-option Bellman operators satisfy multi-step span contractions under unichain assumptions. Then, we propose synchronous estimators of these multi-step option Bellman operators leading to two variants of option Q-learning. Finally, we extend the stochastic approximation framework to prove convergence rates of these two algorithms under the minimal assumptions used in the literature.

0.10

Offline Deep Q* Estimation with Diffusion Models

cs.LG stat.ML ·2026-08-14 ·Xiaohong Chen, Yuling Jiao, Lican Kang, Jerry Zhijian Yang, Chen Zhong
theory similarity 0.69
Abstract

In offline RL, estimating the optimal action-value function $Q^*$ can be formulated as solving the optimal Bellman equation based solely on offline observations. A fundamental challenge is that the reward function and transition kernel are unknown, so the optimal Bellman operator is not directly observable from data. To address this issue, we propose a novel framework that decouples operator estimation from value function learning. In this approach, we first formulate conditional diffusion models to estimate the reward law and transition kernel, which induces a data-driven approximation of the optimal Bellman operator. We then plug these estimators into the Bellman equation and obtain a deep estimator of $Q^*$ by minimizing the empirical Bellman residual over a neural network function class. Theoretically, we first establish sharp nonasymptotic convergence rates for learning the optimal Bellman operator. We establish the smoothness of $Q^*$ through the Bellman equation using the the Hölder assumptions on the conditional reward and transition densities. With suitable sample sizes, we obtain the oracle value-stage rate $\widetilde{\mathcal O}\bigl(n^{-\frac{2α}{d_x+d_a+2α}}\bigr)$ for the excess Bellman residual risk. We then translate this risk bound into an expected $L^2$ estimation error of order $\widetilde{\mathcal O}\bigl(n^{-\fracα{d_x+d_a+2α}}\bigr)$ under a concentrability condition. For the total offline budget $\widetilde n=n+n_r+n_x$, we obtain a value estimation rate of $\widetilde{\mathcal O}\bigl(\widetilde n^{-\fracα{2d_x+d_a+2α}}\bigr)$ and establish an information-theoretic lower bound of order $\widetilde n^{-\fracα{d_x+d_a+2α}}$. Importantly, our theoretical analysis does not rely on Bellman completeness assumptions commonly used in deep RL theory.

0.04

Provably Efficient Q-learning for Robust Reinforcement Learning

cs.AI stat.MLcs.LGmath.ST ·2026-10-26 ·Yuchen Jiao, Gen Li
similarity 0.68
Abstract

Standard reinforcement learning (RL) algorithms based on Markov Decision Processes (MDPs) are vulnerable to sim-to-real gaps. To address this issue, distributionally robust RL algorithms based on robust MDPs (RMDPs) have been proposed, for ensuring that agents can perform reliably to unpredictable conditions in real-world environments. Despite of the rich literature, \revision{an efficient model-free method is still lacking} for robust RL, particularly for Markovian data, which is more relevant in practical applications. In this work, we take a step towards settling this problem by proposing a sample efficient (asynchronous Q-learning) algorithm for robust RL. In particular, consider a $γ$-discounted infinite-horizon RMDP with state space $\mathcal{S}$ and action space $\mathcal{A}$, where the uncertainty set is specified by the total variation (TV) distance with uncertainty level $σ$. Assuming access to a single trajectory of Markovian samples induced by a behavior policy and the nominal transition kernel, the sample complexity of the proposed Q-learning algorithm --- to achieve an entrywise $\varepsilon$-approximation of the optimal Q-function --- is bounded by $$ \frac{1}{μ_{\mathsf{min}}\varepsilon^2(1-γ)^3\max\{1-γ,σ\}} + \frac{t_{\mathsf{mix}}}{μ_{\mathsf{min}}(1-γ)} $$ up to logarithmic factors. Here, $t_{\mathsf{mix}}$ and $μ_{\mathsf{min}}$ denote the mixing time and the minimum state-action occupancy probability of the sample trajectory, respectively. This result is nearly minimax optimal, with an additional factor of $\frac{1}{1-γ}$. Moreover, it achieves a significant improvement over existing bounds.

0.10

An Analysis of Reinforcement Learning with Function Approximation

cs.LG ·2026-11-07 ·Francisco S. Melo, Sean P. Meyn, M. Isabel Ribeiro
top venuehighly cited similarity 0.68
Abstract · This version of the paper corrects the one that was presented at the 25th International Conference on Machine Learning. We corrected conditi…

We address the problem of computing the optimal Q-function in Markov decision problems with infinite state-space. We analyze the convergence properties of several variations of Q-learning when combined with function approximation, extending the analysis of TD-learning in Tsitsiklis and Van Roy (1996) to stochastic control settings. We identify conditions under which such approximate methods converge with probability 1. We conclude with a brief discussion on the general applicability of our results and compare them with several related works.

0.63

Finite Time Analysis of Risk-Sensitive RL via Noisy Power Iteration

cs.LG ·2026-11-07 ·Waqar Mirza, Yashaswini Murthy, Laixi Shi, Eric Mazumdar, Adam Wierman
theory similarity 0.67
Abstract

Estimating the principal eigenpair of a positive operator from stochastic evaluations gives rise to a noisy form of normalized power iteration: each step applies a sampled operator estimate and then renormalizes. We establish finite-time stochastic-approximation guarantees for this procedure, working in Hilbert's projective metric, which is well-suited to the multiplicative geometry of Perron--Frobenius eigenproblems. Our main application is risk-sensitive average-cost reinforcement learning (RL) with exponential utility. In this setting the Bellman equations are multiplicative, and value functions are characterized by nonlinear eigenvalue problems rather than additive fixed points. We cast both policy evaluation and control in this framework, obtaining risk-sensitive TD- and Q-learning algorithms that learn from a single Markovian trajectory. Under explicit positivity, mixing, and linear function approximation assumptions, we prove finite-time bounds on the recovered eigenvector and eigenvalue with $\tilde{O}(ε^{-2})$ sample complexity up to problem-dependent constants. The results cover both tabular and linear function approximation regimes, and through the duality between exponential utility and KL-robust control yield finite-time guarantees for KL-robust average-cost RL as well.

0.17

Mixing Regularization for Average-Reward $Q$-Learning and $Q$-Planning

cs.LG cs.AImath.OCstat.ML ·2026-10-10 ·Julien Roger, Sam Bodmer, Jian Qian, Benjamin Riviere
similarity 0.67
Abstract · 10 pages main body, 56 pages references and appendix, 8 figures. Under review

The average-reward setting for reinforcement learning is challenging because its Bellman operator is known to contract in span only when the underlying Markov chain is mixing. Whereas existing work typically assumes a contraction property, e.g., through environment mixing, we consider the setting where we are given a reward-agnostic $m$-step mixing policy, and we control the contraction and exploration properties of the learned policy by regularizing toward the mixing policy. We provide finite-time analysis of $Q$-learning algorithms that can be instantiated with multiple choices of regularization, with guarantees measured with respect to the regularized fixed point. Our framework exposes novel regularizer-dependent objects that control contraction, exploration, and operator bias. In the one-step setting, our rates match the best known rates for $Q$-iteration and synchronous $Q$-learning, and for $m$-step mixing we derive new rates. We also study $Q$-planning variants, and show that planning acts as time-localized learning, where the planning horizon $H$ trades off the bias from the boundary value against the sample complexity. Finally, we present numerical studies validating the analysis: (i) knowledge of a strong mixing policy improves convergence and exploration, and its advantage increases with bottleneck severity and, (ii) our theory predicts the convergence and bias rankings of regularizers from the $α$-divergence family.

0.23