Linear Function Approximation

Follow this topic Ask about this topic

Linear function approximation represents value functions, action values, or policies as weighted combinations of features, allowing reinforcement learning methods to scale beyond tabular problems. Work studies temporal-difference learning, Q-learning, policy gradients, and policy iteration, with guarantees for settings such as Markovian single-trajectory data, robust control, and multi-agent games. Common tools include projected Bellman equations, stochastic approximation, feature-level coverage conditions, and stability analysis; evaluations range from theoretical bandit cases to game benchmarks such as Tic-Tac-Toe and Connect4. A central tension is that compact features can improve data efficiency, but convergence and error still depend on feature quality, sampling conditions, and stability—especially in off-policy and robust settings.

Latest papers

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

Q-Learning with Stable Infinite-Dimensional Linear Function Approximation
Aug 23, 2026Shengbo WangQ-Learning Function Approximation in RL
Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California
A Diffusion Approximation for Temporal-Difference Learning with Linear Features under Markovian Noise
Jun 16, 2026M. Forzo, E. Monzio Compagnoni, A. Russo +1Stochastic Differential Equations Temporal-Difference Learning
Technical University of Munich (TUM), Munich, Germany · University of Basel, Basel, Switzerland · Boston University, Boston, USA.
Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples
Jun 4, 2026Ziad Kobeissi, Éloïse BerthierStochastic Approximation Temporal-Difference Learning
L2S · L2S, INRIA Université Paris-Saclay, CentraleSupelec, Gif-sur-Yvette, France · U2IS +1
Optimal Data Acquisition for Reinforcement Learning: A Large Deviations Perspective
May 27, 2026Mingjie Hu, Jian-Qiang Hu, Enlu ZhouReinforcement Learning Large Deviation Principles
School of Management, Fudan University · H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology
Behavior-Aware Auxiliary Corrections for Off-Policy Temporal-Difference Prediction
May 17, 2026Xingguo Chen, Zhiang He, Yuchen Shen +4Temporal-Difference Learning Linear Function Approximation
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
A Switching System Theory of Q-Learning with Linear Function Approximation
May 10, 2026Donghwan Lee, Han-Dong LimQ-Learning Linear Function Approximation
Department of Electrical Engineering · Korea Advanced Institute of Science and Technology (KAIST) · Daejeon 34141, South Korea
Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation
May 4, 2026Jingchu Gai, Laixi ShiMulti-Agent System Optimization Markov Models
Machine Learning Department, Carnegie Mellon University. · Department of Electrical and Computer Engineering, Johns Hopkins University, MD 21286, USA.
Bridging the Gap Between Average and Discounted TD Learning
May 3, 2026Haoxing Tian, Zaiwei Chen, Ioannis Ch. Paschalidis +1Reinforcement Learning Average-Reward RL
Department of Electrical and Computer Engineering Boston University · Edwardson School of Industrial Engineering Purdue University
Personalized Multi-Agent Average Reward TD-Learning via Joint Linear Approximation
Mar 2, 2026Leo Muxing Wang, Pengkun Yang, Lili SuTemporal-Difference Learning Multi-Agent Reinforcement Learning
Northeastern University · Tsinghua University
Frozen Policy Iteration: Computationally Efficient RL under Linear $Q^π$ Realizability for Deterministic Dynamics
Feb 28, 2026Yijing Ke, Zihan Zhang, Ruosong WangRegret Minimization in RL Policy Iteration
School of EECS, Peking University · Department of Computer Science and Engineering, HKUST · CFCS and School of Computer Science, Peking University
Multi-agent imitation learning with function approximation: Linear Markov games and beyond
Feb 26, 2026Luca Viano, Till Freihaut, Emanuele Nevali +3Game Theory Imitation Learning
1EPFL · University of Zurich · 3Earth Species Project
Finite-Time Convergence of Single-Trajectory Chi-Square Robust Q-Learning With Linear Function Approximation
Oct 2, 2025Saptarshi Mandal, Yashaswini Murthy, R. SrikantQ-Learning Distributionally Robust RL
ECE, UIUC · ORIE, UT Austin · ECE, CSL, and the director of NCSA at UIUC
Rethinking the Global Convergence of Softmax Policy Gradient with Linear Function Approximation: The Case of Multi-Armed Bandits
May 6, 2025Max Qiushi Lin, Jincheng Mei, Matin Aghaei +6Multi-Armed Bandits Policy Gradient
Simon Fraser University · Google DeepMind · Google Research +1

Aug 23, 2026J/K move · Enter open · S save

Q-Learning with Stable Infinite-Dimensional Linear Function Approximation

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

Open paper AskPDF arXiv

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.