CS Paper Radar

An Analysis of Reinforcement Learning with Function Approximation

Francisco S. Melo, Sean P. Meyn, M. Isabel Ribeiro

cs.LG ·submitted 2026-11-07 21:43 UTC · v1
top venuehighly cited

Abstract

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.

Comment
This version of the paper corrects the one that was presented at the 25th International Conference on Machine Learning. We corrected condition (7) of Theorem 1 and its proof, as well as the importance-sampling update (11). We also made the assumptions of Theorems 1 and 2 more precise and revised the proof of Theorem 2, adding an appendix with the auxiliary results it uses
Journal ref
Francisco S. Melo, Sean P. Meyn, M. Isabel Ribeiro. "An analysis of reinforcement learning with function approximation." Proc. 25th Int. Conf. Machine Learning, pp. 664-671, 2008
DOI
10.1145/1390156.1390240

Closest papers

Nearest neighbours by meaning across the whole index.

Discrete-Time Stochastic Control Beyond i.i.d. Noise

eess.SY math.OC ·2026-11-10 ·Reyajul Hasan Leon, Ali Devran Kara
similarity 0.69
Abstract

We study discrete-time stochastic control problems where the noise driving the state dynamics is a stationary infinite-order chain rather than an i.i.d. sequence. We formulate the problem as a controlled Markov process by enlarging the state space to include the posterior distribution of the noise given the state-action history. Assuming that the sensitivity of the noise transition kernel to past noise values decays exponentially, we show that the expected total variation distance between the full-history and finite-memory noise filters decays at rate $\sqrt{N}ρ^{\sqrt{N}}$. We use this result to construct finite-memory control models and establish explicit near-optimality bounds for their policies. Finally, under suitable ergodicity conditions, we show that Q-learning converges to the optimal solution of the approximate model, so the same performance bounds apply to the learned policies.

0.20

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

Sharp Gaussian Approximation for Q-Learning

cs.LG stat.MLmath.ST ·2026-11-15 ·Xingtu Liu
theory similarity 0.68
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

On the Convergence of Success Conditioning for Policy Optimization

cs.LG math.OC ·2026-10-02 ·Matthew Brun, Xu Andy Sun
theory similarity 0.68
Abstract

Success conditioning is a strategy for improving decision-making policies in stochastic environments; it updates a policy by increasing the probability of taking actions that yield successful outcomes. Success conditioning is common to many reinforcement learning applications, yet its limiting behavior and convergence rates are not well understood. In this work, we demonstrate that success conditioning converges to an optimal policy on a broad class of Markov decision processes (MDPs). We also derive convergence rates in some common settings. For discounted MDPs, we prove convergence within $\mathcal{O}(1/\varepsilon^p)$ iterations to an $\varepsilon$-optimal policy, where the exponent $p$ depends on problem data. For single-period MDPs, such a policy is obtained within $\mathcal{O}(\log(1/\varepsilon))$ iterations.

0.17

Q-Learning with Stable Infinite-Dimensional Linear Function Approximation

cs.LG math.OCstat.ML ·2026-08-23 ·Shengbo Wang
similarity 0.68
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.

0.08

Understanding the Asymptotic Transience of Q-Learning via Distributional Expansion

cs.LG math.OCstat.ML ·2026-11-11 ·Shengbo Wang
similarity 0.67
Abstract

Q-learning has been empirically observed to exhibit substantial transient error. This transient remains uncaptured by the leading Gaussian limit because the central-limit normalization removes the smaller-scale displacement generated by the initial nonlinear evolution. On the other hand, worst-case finite-sample guarantees, while accounting for transient effects, can obscure the mechanisms responsible for the error on a particular problem instance. We develop a finer asymptotic analysis that gives an asymptotically exact characterization of this transient for a fixed instance. Specifically, for synchronous Q-learning in finite discounted Markov decision processes, we separate the last-iterate error into an optimal-policy temporal-difference (TD) component and a nonnegative displacement caused by maximization. The centered TD component has Gaussian fluctuations at scale $n^{-1/2}$, whereas the maximization transient is of order $n^{-1}$ and converges almost surely, after rescaling by $n$, to a random limit. This limit represents the propagated effect of maximization errors generated before the greedy policy stabilizes. We combine this characterization with an Edgeworth expansion of the TD component to identify the corrections to its Gaussian approximation, separating the effects of initialization, non-Gaussian TD fluctuations, and maximization. The results reveal how transient errors arise for individual Q-learning instances and how their effects persist below the central-limit scale.

0.12

$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.67
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

Limiting-Kernel Q($λ$): Bridging Short and Long Horizons

cs.LG math.OC ·2026-09-23 ·Tolga Ok, Arman Sharifi Kolarijani, Peyman Mohajerin Esfahani, Mohamad Amin Sharifi Kolarijani
benchmarktheory similarity 0.66
Abstract

In reinforcement learning, more accurate policy evaluation has been frequently shown to improve downstream policy optimization performance. For tractability, most value estimators rely on $n$-step truncation and thereby omit the long-horizon behavior of the transition dynamics. Methods that instead capture this behavior through the global structure of the dynamics can converge faster, but their computational and memory requirements limit their scalability to large or continuous state spaces. To reconcile these limitations, we introduce Limiting-Kernel Q($λ$) (LKQL), an off-policy value estimator that uses the limiting kernel to approximate the long-horizon terms omitted by truncation. LKQL has the same order of complexity as $n$-step estimators and integrates directly into both on- and off-policy actor-critic algorithms. We prove that, under aperiodicity and in the near-on-policy regime, the operator underlying LKQL improves the policy evaluation convergence rate over its truncated counterpart for sufficiently large $n$, and that LKQL itself converges almost surely to the optimal values in finite Markov decision processes (MDPs) under a fixed behavior policy. On the MuJoCo continuous-control benchmark, we show that LKQL improves over $n$-step baselines in most settings, particularly on long-horizon tasks.

0.17