cs.LGNov 7, 2026

An Analysis of Reinforcement Learning with Function Approximation

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

Organizations: Carnegie Mellon University, Pittsburgh, PA 15213, USA · Coordinated Science Lab, Urbana, IL 61801, USA · Institute for Systems and Robotics, 1049-001 Lisboa, Portugal

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.

Explore similar work

Aug 23, 2026

Q-Learning with Stable Infinite-Dimensional Linear Function Approximation

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 θ∈C(L)θ\in C(\mathbb L) on a compact latent metric space (L,ρ)(\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(L)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 O~(n−1/2)\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 (L,ρ)(\mathbb L,ρ) rather than the dimension of C(L)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.
Mar 3, 2026

Q-Measure-Learning for Continuous State RL: Efficient Implementation and Convergence

We study reinforcement learning in infinite-horizon discounted Markov decision processes with continuous state spaces, where data are generated online from a single trajectory under a Markovian behavior policy. To avoid maintaining an infinite-dimensional, function-valued estimate, we propose the novel Q-Measure-Learning, which learns a signed empirical measure supported on visited state-action pairs and reconstructs an action-value estimate via kernel integration. The method jointly estimates the stationary distribution of the behavior chain and the Q-measure through coupled stochastic approximation, leading to an efficient weight-based implementation with O(n)O(n) memory and O(n)O(n) computation cost per iteration. Under uniform ergodicity of the behavior chain, we prove almost sure sup-norm convergence of the induced Q-function to the fixed point of a kernel-smoothed Bellman operator. We also bound the approximation error between this limit and the optimal Q∗Q^* as a function of the kernel bandwidth. To assess the performance of our proposed algorithm, we conduct RL experiments in a two-item inventory control setting.
May 27, 2026

Commit to the Bit: Reactive Reinforcement Learning Done Right

Reinforcement learning algorithms are commonly analyzed (and designed) under the Markov assumption. This is unrealistic, as most environments encountered in practice are either partially observable, or require function approximation that restricts the agent to access non-Markovian state features. We consider the problem of learning an optimal reactive policy in a finite environment with deterministic observations (or equivalently, hard state aggregation). We introduce a new algorithm, Committed Q-learning, and prove almost-sure convergence to the optimal reactive policy under an intuitive assumption we call rewire-robustness. This assumption is strictly weaker than the q⋆q_\star-realizability condition used in prior work. Our algorithm is a variant of classical Q-learning in which the behavior policy commits to a single action upon entering a feature, and only resamples actions when the observed feature changes. A crucial part of our analysis is the introduction of quasi-Markov environments.