Function Approximation in RL

RL: Reinforcement Learning

Follow this topic Ask about this topic

Latest papers

22 papers4 papers in the last four weeks, with none the four weeks before. 0.0% of all new papers.

Oct 19, 2026

Toward Online Robust Zero-Sum Markov Games with Function Approximation

Online robust zero-sum Markov games pose a coupled operator-learning and game-solving problem: from nominal interaction data, the learner must recover a worst-case minimax Bellman operator while maintaining strategic coverage and controlling stage-game approximation error. Existing robust reinforcement-learning theory does not yet provide such an operator-learning perspective beyond specialized multi-agent settings. We develop an optimistic dual robust Bellman framework that combines dual robust Bellman fitting, optimistic minimax planning, backward-validated confidence sets, and exploiter-mix data collection. Our analysis is organized around the robust Bellman residuals induced by the candidate value class and yields a regret reduction that separates exploration complexity, robust operator-estimation error, stage-game solution error, and misspecification. Under explicit interpretable assumptions, we obtain conditional theorem interfaces for general and projected function approximation, together with closed results in several structured regimes, including tabular, epochwise cross-fit linear, self-normalized pure-online linear / finite-rank kernel, and projected RKHS truncation. Small-scale numerical experiments illustrate robustness calibration, strategic coverage, and the return-gap trade-off predicted by the framework.

Chenhao Zhou, Jiyu Wei

College of Computer Science and Technology, Zhejiang University

Robust RL Zero-Sum Games Game-Theoretic RL Operator Learning Function Approximation in RL

Oct 17, 2026

Sample-Efficient Reinforcement Learning with General Utilities via Neural Dual Critics

Reinforcement learning with general utilities optimizes nonlinear functionals of policy-induced occupancy measures. We develop a natural actor-critic method for concave RLGU objectives admitting an exact variational dual representation, with explicit constructions for a broad class of separable occupancy utilities. Rather than estimating the occupancy measure and then forming the policy-gradient pseudo-reward, our method learns this pseudo-reward directly as a function of the state-action pair using a neural critic. The critic is trained by projected stochastic updates, while multilevel Monte Carlo combines outputs across training horizons to control its bias at logarithmic expected cost. Our analysis separates conditional actor bias from estimator second moments and accounts explicitly for dual optimization, critic approximation, and neural linearization errors. Under policy-transfer, dual-stability, and local critic-regularity conditions, the method achieves

\widetilde{O}(T^{-1/2})

global convergence above policy, critic-class, and finite-width approximation errors using

\widetilde{O}(T)

expected environment transitions and reference samples. For a fixed critic representation, this yields

\widetilde{O}(ε^{-2})

sampling complexity above the approximation floor, covering infinite state-action spaces and occupancy utilities beyond fixed finite vectors of returns.

Ankur Naskar, Vaneet Aggarwal

Indian Institute of Science, India · Purdue University, USA

Reinforcement Learning Sample-Efficient RL Actor-Critic Methods Function Approximation in RL

Oct 2, 2026

Bellman Error Minimization Via Linear Programming Normalization

This paper proposes a new functional approximation approach to reduce Bellman error in high-dimensional dynamic programming and Reinforcement Learning problems. Using a classic dynamic programming problem (network capacity control in revenue management) as the motivational example, the paper illustrates that deep neural networks and linear programming approximation algorithms can be combined to derive approximate solutions to dynamic programming problems. Simulation results show the proposed approximation algorithms achieves competitive performance when compared with benchmark.

Haining Yu

Independent Consultant

Function Approximation in RL Dynamic Programming Function Approximation Reinforcement Learning Markov Decision Processes

Sep 26, 2026

Last-Iterate Guarantees for Online Reinforcement Learning in Structured Constrained MDPs

In safety-critical applications, deployment uses a single policy, whose performance and constraint satisfaction should hold directly rather than only for an average or mixture of training policies. This motivates last-iterate guarantees in constrained reinforcement learning. Recent progress has established such guarantees in exact-gradient or tabular online settings, yet scalable results for structured large-state problems remain open. We develop a general, statistically efficient framework for last-iterate convergence in structured Constrained MDPs (CMDPs). Our analysis separates contraction of the regularised primal-dual dynamics from actor approximation and statistical errors in policy evaluation under online exploration. This enables model-free on- and off-policy learning with structured function approximation: optimistic policy evaluation avoids explicit transition-model construction, while a compact parametric actor avoids maintaining mixtures or histories of past policies. We instantiate the framework for linear CMDPs and general function approximation, obtaining representation-dependent complexity and improved target-accuracy dependence over prior optimistic regularised primal-dual analyses. We further validate the stabilising effect predicted by our theory on a synthetic linear CMDP: the regularised method exhibits stable last-iterate behaviour, whereas its unregularised counterpart shows larger oscillations.

Nam Phuong Tran, Trinh Ha Mai Huynh, Tuyen Pham Le +3

Inria centre at the University of Lille Lille, France · Vin Motion Vietnam · Department of Computer Science University of Warwick Coventry, United Kingdom

Function Approximation in RL Reinforcement Learning Constrained RL

Sep 25, 2026

Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation

Model misspecification poses a fundamental challenge in multi-agent reinforcement learning, where transition uncertainty can be amplified by strategic interactions among agents. Distributionally robust Markov games (DRMGs) provide a principled framework for addressing such uncertainty, yet existing methods often rely on restrictive assumptions or scale poorly to large state and joint action spaces. We study online learning in general-sum DRMGs with general function approximation and

φ

-divergence uncertainty sets. We propose RoMEX-

φ

, a model-free framework that integrates equilibrium-based exploration with dual fitted learning. Through a functional dual representation of the robust multi-agent Bellman operator, RoMEX-

φ

enables tractable worst-case value estimation from nominal interaction data using a centered empirical robust discrepancy. We introduce the robust Multi-Agent Decoupling Coefficient (robust MADC) to characterize the intrinsic exploration complexity arising from strategic interactions and adversarial transition uncertainty. We establish sublinear robust regret guarantees governed by the robust MADC rather than explicitly by the state and joint action space sizes, replacing tabular dependence with intrinsic function-class complexity. Numerical experiments on a scalable general-sum DRMG under total variation uncertainty show that RoMEX-

φ

is substantially more resilient to transition shifts than its non-robust counterpart while remaining competitive with an exact tabular robust baseline. Our results provide a scalable framework for distributionally robust multi-agent reinforcement learning with general function approximation.

Debamita Ghosh, George K. Atia, Yue Wang

Department of Electrical and Computer Engineering, University of Central Florida, Orlando, FL 32816, USA · Department of Computer Science, University of Central Florida, Orlando, FL 32816, USA

Function Approximation in RL Reinforcement Learning Distributionally Robust RL Multi-Agent Reinforcement Learning Robust RL

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

θ\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.

Shengbo Wang

Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California

Q-Learning Function Approximation in RL Linear Function Approximation Stochastic Approximation

Jul 8, 2026

Mathematical methods of reinforcement learning

Reinforcement learning (RL) is increasingly grounded in tools from probability, optimization, and operator theory. This survey organizes the mathematical structures that underpin the design and analysis of modern algorithms in RL. We begin from Markov decision processes (MDPs) and the Bellman operators, emphasizing contraction mappings, monotonicity, and fixed-point theory that yield convergence guarantees and rates for value and policy iteration, and temporal-difference schemes. We then develop the optimization perspective: stochastic approximation and martingale methods, convex duality and the role of regularization linking mirror/proximal methods. Function approximation is treated through linear and non-linear settings, covering stabilization, error decomposition, and sample-complexity via concentration inequalities for dependent data and mixing processes. We further cover off-policy evaluation/learning, constrained RL and constrained MDPs (CMDPs). Throughout we unify algorithmic templates under common operator and variational lenses, highlighting both finite-sample bounds and asymptotic results. Our presentation is intended to provide a unified mathematical entry point for researchers in probability, optimization, and statistics interested in reinforcement learning.

Denis Belomestny, Alexander Gasnikov, Egor Gladin +5

Duisburg-Essen University, HSE University · Innopolis University, MIPT, HSE University · HSE University +1

Markov Decision Processes Reinforcement Learning Function Approximation in RL

Jun 16, 2026

A Diffusion Approximation for Temporal-Difference Learning with Linear Features under Markovian Noise

Temporal difference (TD) learning with linear function approximation is a core method for policy evaluation. Its classical continuous-time description is an ordinary differential equation (ODE), which captures the asymptotic mean dynamics but neglects stochastic fluctuations determining the error floor. We introduce a stochastic differential equation (SDE) approximation for linear TD(0) under Markovian noise. The resulting model distinguishes the contraction dynamics governed by the projected Bellman operator from the influence of Markovian sampling. As a consequence, the model explains the constant-stepsize error floor through the interaction between Markovian long-run covariance and the contraction geometry of the projected Bellman operator.

M. Forzo, E. Monzio Compagnoni, A. Russo +1

Technical University of Munich (TUM), Munich, Germany · University of Basel, Basel, Switzerland · Boston University, Boston, USA.

Stochastic Differential Equations Temporal-Difference Learning Linear Function Approximation Function Approximation in RL Function Approximation

May 27, 2026

Variance-Adaptive Optimal Algorithm for Reinforcement Learning with Multinomial Logit Function Approximation

Reinforcement learning with multinomial logistic (MNL) function approximation has become an important framework due to its flexibility and broad applicability. While existing studies have established regret guarantees under worst-case analysis, they do not capture how performance depends on the variability of the interaction between the learner and the environment. In this paper, we develop a new theoretical analysis for MNL-based Markov decision processes that yields explicit variance-adaptive regret bounds. Our algorithm is computationally efficient and achieves the instance-wise optimal rate of regret, narrowing the gap between upper and lower bounds. Our numerical experiments validate that our method learns optimal policies more efficiently than conventional approaches.

Wonyoung Kim, Min-Hwan Oh, Garud Iyengar +1

Chung-Ang University · Seoul National University · Columbia University

Regret Minimization in RL Reinforcement Learning Policy Learning Function Approximation in RL

May 24, 2026

Global linear convergence of entropy-regularized softmax policy gradient beyond tabular MDPs

We study the global convergence of policy gradient for infinite-horizon entropy-regularized Markov decision processes (MDPs) with continuous state and action spaces. We consider log-linear softmax policies with linear function approximation, which extend the tabular softmax parameterization while retaining a tractable policy class. Under

Q^π_τ

-realizability for the regularized state-action value function, we first establish a non-uniform Polyak--Łojasiewicz (PŁ) inequality. The non-uniformity arises through degeneracy of constants associated with the policy geometry, namely the Fisher information matrix or an uncentered feature covariance matrix. We then identify two feature regimes under which this non-uniform constant can be bounded along the gradient flow. For full-affine-span features, we prove radial unboundedness of the KL regularizer and show that the smallest eigenvalue of the Fisher information matrix remains bounded below by an initialization-dependent positive constant. For simplex-valued features, we prove an analogous radial unboundedness result in the subspace orthogonal to the all-ones vector and obtain a uniform lower bound for the smallest eigenvalue of the uncentered covariance matrix. These results imply global linear convergence of the regularized objective along the gradient flow, i.e. suboptimality decaying as

\mathcal{O}(e^{-Ct})

for some

C>0

. Our analysis extends the global convergence theory of entropy-regularized softmax policy gradient beyond the tabular setting of Agarwal et al. (2020); Bhandari and Russo (2024); Mei et al. (2020).

Ziyue Chen, David Šiška, Lukasz Szpruch

Policy Gradient Reinforcement Learning Maximum Entropy RL Continuous-Time RL Function Approximation in RL

May 17, 2026

On Gaussian approximation for entropy-regularized Q-learning with function approximation

In this paper, we derive rates of convergence in the high-dimensional central limit theorem for Polyak--Ruppert averaged iterates generated by entropy-regularized asynchronous Q-learning with linear function approximation and a polynomial stepsize

k^{-ω}

,

ω\in (1/2,1)

. Assuming that the sequence of observed triples

(s_k,a_k,s_{k+1})_{k \geq 0}

forms a uniformly geometrically ergodic Markov chain, and under suitable regularity conditions for the projected soft Bellman equation, we establish a Gaussian approximation bound in the convex distance with rate of order

n^{-1/4}

, up to polylogarithmic factors in

n

, where

n

is the number of samples used by the algorithm. To obtain this result, we combine a linearization of the soft Bellman recursion with a Gaussian approximation for the leading martingale term. Finally, we derive high-order moment bounds for the algorithm's last iterate, which might be of independent interest.

Artemy Rubtsov, Rahul Singh, Eric Moulines +2

HSE University, Moscow, Russia · Mohamed Bin Zayed University of AI, UAE · EPITA, France +1

Reinforcement Learning Stochastic Approximation Q-Learning Entropy Regularization Function Approximation in RL

May 17, 2026

Behavior-Aware Auxiliary Corrections for Off-Policy Temporal-Difference Prediction

Temporal-difference learning with function approximation can be unstable under off-policy sampling. TDC stabilizes off-policy TD through an auxiliary covariance correction, and TDRC further regularizes this correction in a single-timescale recursion. This paper studies a behavior-aware replacement of the auxiliary covariance geometry in the linear prediction setting, which is the standard local model for understanding the feature-space dynamics of value-function approximation. We first replace the TDC auxiliary matrix (C) by the behavior Bellman matrix (A_μ), yielding BA-TDC, and then regularize the same behavior-aware equation to obtain BA-TDRC. This two-step construction separates the contribution of behavior-aware geometry from the contribution of regularization. The linear analysis also provides a tractable model for an auxiliary-geometry design question that arises in neural-network value approximation, where feature covariances and temporal transition matrices jointly shape the last-layer correction dynamics. We give a finite-state mean-system formulation, prove fixed-point preservation and almost-sure convergence under a Hurwitz stability condition on the instantiated mean system, and compare deterministic mean rates through the spectral radius of the exact linear error recursion. Experiments on the two-state counterexample, Baird's counterexample, Random Walk, and Boyan Chain show that the behavior-aware replacement can be highly beneficial by itself on some tasks, but that regularization is necessary for robust performance across harder settings.

Xingguo Chen, Zhiang He, Yuchen Shen +4

Nanjing University of Posts and Telecommunications, Nanjing, China · Department of Computer Science and Technology, Nanjing University, Nanjing, China · College of Electronic Countermeasure, National University of Defense Technology, Hefei, China

Temporal-Difference Learning Linear Function Approximation Off-Policy RL Function Approximation in RL

May 7, 2026

Towards Differentially Private Reinforcement Learning with General Function Approximation

We present the first theoretical guarantees for differentially private online reinforcement learning (RL) with general function approximation, extending beyond prior work restricted to tabular and linear settings. Our approach combines a batched policy update scheme with the exponential mechanism, together with a novel regret analysis. We show that, even under general function approximation, the regret in the model-free setting under differential privacy matches the state of the art for the linear case, scaling as

\widetilde{O}(K^{3/5})

, where

K

denotes the number of episodes. As an important by-product, we also establish the first regret bound for online RL with batch update that depends on the standard complexity measure of coverability, complementing existing results based on a newly introduced Eluder-Condition class. In addition, we uncover fundamental gaps in recent results for private RL with linear function approximation, thereby clarifying its landscape.

Yi He, Xingyu Zhou

Wayne State University, Detroit, USA

Regret Minimization in RL Reinforcement Learning Privacy-Preserving ML Differential Privacy Model-Free RL Policy Learning+1

May 1, 2026

Reinforcement Learning with Markov Risk Measures and Multipattern Risk Approximation

For a risk-averse finite-horizon Markov Decision Problem, we introduce a special class of Markov coherent risk measures, called mini-batch measures. We also define the class of multipattern risk-averse problems that generalizes the class of linear systems. We use both concepts in a feature-based

Q

-learning method with multipattern

Q

-factor approximation and we prove a high-probability regret bound of

\mathcal{O}\big(H^2 N^H \sqrt{ K}\big)

, where

H

is the horizon,

N

is the mini-batch size, and

K

is the number of episodes. We also propose an economical version of the

Q

-learning method that streamlines the policy evaluation (backward) step. The theoretical results are illustrated on a stochastic assignment problem and a short-horizon multi-armed bandit problem.

Andrzej Ruszczynski, Tiangang Zhang

Department of Management Science and Information Systems, Rutgers University

Markov Decision Processes Reinforcement Learning Markov Models Q-Learning Risk-Sensitive RL Function Approximation in RL

Apr 15, 2026

Provably Efficient Offline-to-Online Value Adaptation with General Function Approximation

We study value adaptation in offline-to-online reinforcement learning under general function approximation. Starting from an imperfect offline pretrained

Q

-function, the learner aims to adapt it to the target environment using only a limited amount of online interaction. We first characterize the difficulty of this setting by establishing a minimax lower bound, showing that even when the pretrained

Q

-function is close to optimal

Q^\star

, online adaptation can be no more efficient than pure online RL on certain hard instances. On the positive side, under a novel structural condition on the offline-pretrained value functions, we propose O2O-LSVI, an adaptation algorithm with problem-dependent sample complexity that provably improves over pure online RL. Finally, we complement our theory with neural-network experiments that demonstrate the practical effectiveness of the proposed method.

Shangzhe Li, Weitong Zhang

UNC Chapel Hill

Offline-To-Online RL Sample-Efficient RL Value Function Estimation Function Approximation in RL

Apr 8, 2026

Contraction-Aligned Analysis of Soft Bellman Residual Minimization with Weighted Lp-Norm for Markov Decision Problem

The problem of solving Markov decision processes under function approximation remains a fundamental challenge, even under linear function approximation settings. A key difficulty arises from a geometric mismatch: while the Bellman optimality operator is contractive in the Linfty-norm, commonly used objectives such as projected value iteration and Bellman residual minimization rely on L2-based formulations. To enable gradient-based optimization, we consider a soft formulation of Bellman residual minimization and extend it to a generalized weighted Lp -norm. We show that this formulation aligns the optimization objective with the contraction geometry of the Bellman operator as p increases, and derive corresponding performance error bounds. Our analysis provides a principled connection between residual minimization and Bellman contraction, leading to improved control of error propagation while remaining compatible with gradient-based optimization.

Hyukjun Yang, Han-Dong Lim, Donghwan Lee

the Department of Electrical Engineering, Korea Advanced Institute of Science and Technology (KAIST), Daejeon, 34141, South Korea

Function Approximation in RL Markov Decision Processes Reinforcement Learning

Mar 24, 2026

End-to-End Efficient RL for Linear Bellman Complete MDPs with Deterministic Transitions

We study reinforcement learning (RL) with linear function approximation in Markov Decision Processes (MDPs) satisfying linear Bellman completeness -- a fundamental setting where the Bellman backup of any linear value function remains linear. While statistically tractable, prior computationally efficient algorithms are either limited to small action spaces or require strong oracle assumptions over the feature space. We provide a computationally efficient algorithm for linear Bellman complete MDPs with deterministic transitions, stochastic initial states, and stochastic rewards. For finite action spaces, our algorithm is end-to-end efficient; for large or infinite action spaces, we require only a standard argmax oracle over actions. Our algorithm learns an

\varepsilon

-optimal policy with sample and computational complexity polynomial in the horizon, feature dimension, and

1/\varepsilon

.

Zakaria Mhammedi, Alexander Rakhlin, Nneka Okolo

Google Research, NYC · MIT

Reinforcement Learning Linear Markov Decision Processes Policy Learning Sample-Efficient RL Function Approximation in RL

Mar 9, 2026

Impact of Connectivity on Laplacian Representations in Reinforcement Learning

Learning compact state representations in Markov Decision Processes (MDPs) has proven crucial for addressing the curse of dimensionality in large-scale reinforcement learning (RL) problems. Existing principled approaches leverage structural priors on the MDP by constructing state representations as linear combinations of the state-graph Laplacian eigenvectors. When the transition graph is unknown or the state space is prohibitively large, the graph spectral features can be estimated directly via sample trajectories. In this work, we prove an upper bound on the approximation error of linear value function approximation under the learned spectral features. We show how this error scales with the algebraic connectivity of the state-graph, grounding the approximation quality in the topological structure of the MDP. We further bound the error introduced by the eigenvector estimation itself, leading to an end-to-end error decomposition across the representation learning pipeline. Additionally, our expression of the Laplacian operator for the RL setting, although equivalent to existing ones, prevents some common misunderstandings, of which we show some examples from the literature. Our results hold for general (non-uniform) policies without any assumptions on the symmetry of the induced transition kernel. We validate our theoretical findings with numerical simulations on gridworld environments.

Tommaso Giorgi, Pierriccardo Olivieri, Keyue Jiang +2

Baker Hughes, Florence, Italy · Politecnico di Milano · University College London, AI Center (UCL) +1

Reinforcement Learning Representation Learning for RL State Representation Learning Function Approximation in RL Value Function Estimation

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)

memory and

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^*

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.

Shengbo Wang

Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California

Reinforcement Learning Q-Learning Function Approximation in RL

Mar 1, 2026

PAC Guarantees for Reinforcement Learning: Sample Complexity, Coverage, and Structure

When data is scarce or mistakes are costly, average-case metrics fall short. What a practitioner needs is a guarantee: with probability at least

1-δ

, the learned policy is

\varepsilon

-close to optimal after

N

episodes. This is the PAC promise, and between 2018 and 2025 the RL theory community made striking progress on when such promises can be kept. We survey that progress. Our organizing tool is the Coverage-Structure-Objective (CSO) framework, proposed here, which decomposes nearly every PAC sample complexity result into three factors: coverage (how data were obtained), structure (intrinsic MDP or function-class complexity), and objective (what the learner must deliver). CSO is not a theorem but an interpretive template that identifies bottlenecks and makes cross-setting comparison immediate. The technical core covers tight tabular baselines and the uniform-PAC bridge to regret; structural complexity measures (Bellman rank, witness rank, Bellman-Eluder dimension) governing learnability with function approximation; results for linear, kernel/NTK, and low-rank models; reward-free exploration as upfront coverage investment; and pessimistic offline RL where inherited coverage is the binding constraint. We provide practitioner tools: rate lookup tables indexed by CSO coordinates, Bellman residual diagnostics, coverage estimation with deployment gates, and per-episode policy certificates. A final section catalogs open problems, separating near-term targets from frontier questions where coverage, structure, and computation tangle in ways current theory cannot resolve.

Joshua Steier

Function Approximation in RL Reinforcement Learning Sample-Efficient RL

May 17, 2025

Adaptive Resolving Methods for Markov Decision Processes with Function Approximations

Learning the optimal policy for Markov decision process problems (MDPs) from samples is a fundamental problem in online and data-driven decision-making. Function approximations are usually deployed to handle large or infinite state-action space. In our work, we consider the MDP problems with function approximation and we develop a new algorithm to solve it efficiently. Our algorithm is based on a linear programming (LP) reformulation and repeatedly resolves the identified reduced linear system as new transition samples arrive. After the optimal basis is identified, we show that, after

N

resolving rounds, the expected averaged iterate achieves an instance-dependent

\widetilde O(C_{\mathrm{inst}}/N)

objective shortfall and signed constraint residual. We separately account for the historical samples used for basis identification and the

d_2

transition queries used in each resolving round, which yields the corresponding total transition-query complexity. We further complement our result with a robust

O(1/\sqrt{N})

bound that is independent of

Δ

. In comparison to the guarantees established in the previous literature, our instance dependent guarantee is tighter when the underlying instance is favorable, and the numerical experiments also reveal the wide applications and efficient empirical performances of our algorithms.

Jiashuo Jiang, Yinyu Ye, Yiming Zong

Department of Industrial Engineering & Decision Analytics, The Hong Kong University of Science and Technology · Department of Management Science & Engineering, Stanford University

Markov Decision Processes Reinforcement Learning Markov Models Policy Learning Sample-Efficient RL Function Approximation in RL

Oct 21, 2024

Statistical Inference for Policy Evaluation with Temporal Difference Learning

We investigate the statistical properties of Temporal Difference (TD) learning with Polyak-Ruppert averaging, arguably one of the most widely used algorithms in reinforcement learning, for the task of estimating the parameters of the optimal linear approximation to the value function. Assuming independent samples, we make three theoretical contributions that improve upon the current state-of-the-art results: (i) we establish refined high-dimensional Berry-Esseen bounds over the class of convex sets, achieving faster rates than the best known results, and (ii) we propose and analyze a novel, computationally efficient online plug-in estimator of the asymptotic covariance matrix; (iii) we derive sharper high probability convergence guarantees that depend explicitly on the asymptotic variance and hold under weaker conditions than those adopted in the literature. These results enable the construction of confidence regions and simultaneous confidence intervals for the linear parameters of the value function approximation, with guaranteed finite-sample coverage. We demonstrate the applicability of our theoretical findings through numerical experiments.

Weichen Wu, Gen Li, Yuting Wei +1

The Voleon Group, New York, NY, USA · Department of Statistics, The Chinese University of Hong Kong, Hong Kong SAR. · Department of Statistics and Data Science, The Wharton School, University of Pennsylvania, Philadelphia, PA, USA. +1

Parameter Estimation Confidence Region Estimation Value Function Estimation Stochastic Approximation Policy Evaluation Temporal-Difference Learning+3