Data to 7 Oct 2026

Provably Efficient Reinforcement Learning with Linear Function Approximation

arXiv 1907.05388 ↗First posted 11 Jul 2019cs.LG math.OC stat.MLcited by 514

Not on the map. Why?

Cited by 83 in Offline RL and imitation learning from data, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

Modern Reinforcement Learning (RL) is commonly applied to practical problems with an enormous number of states, where function approximation must be deployed to approximate either the value function or the policy. The introduction of function approximation raises a fundamental set of challenges involving computational and statistical efficiency, especially given the need to manage the exploration/exploitation tradeoff. As a result, a core RL question remains open: how can we design provably efficient RL algorithms that incorporate function approximation? This question persists even in a basic setting with linear dynamics and linear rewards, for which only linear function approximation is needed. This paper presents the first provable RL algorithm with both polynomial runtime and polynomial sample complexity in this linear setting, without requiring a "simulator" or additional assumptions. Concretely, we prove that an optimistic modification of Least-Squares Value Iteration (LSVI)---a classical algorithm frequently studied in the linear setting---achieves tildeO(√d3H3T) regret, where d is the ambient dimension of feature space, H is the length of each episode, and T is the total number of steps. Importantly, such regret is independent of the number of states and actions.

Key facts. Cited by 514 papers in the map (data through 7 Oct 2026). First posted on arXiv 11 Jul 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2020: 1; 2021: 83; 2022: 86; 2023: 113; 2024: 107; 2025: 63; 2026: 61.

514 papers.

Sort:

By area:

2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
2023Foundation Models for Decision Making: Problems, Methods, and Opportunitiescited by 160
2022Hybrid RL: Using Both Offline and Online Data Can Make RL Efficientcited by 158
2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
2021Representation Learning for Online and Offline RL in Low-rank MDPscited by 128
2022Pessimistic Bootstrapping for Uncertainty-Driven Offline Reinforcement Learningcited by 125
2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
2024Exploratory Preference Optimization: Harnessing Implicit Q*-Approximation for Sample-Efficient RLHFcited by 106

38 more

2022Jump-Start Reinforcement Learningcited by 102
2021Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approachcited by 98
2023Is RLHF More Difficult than Standard RL?cited by 96
2022RORL: Robust Offline Reinforcement Learning via Conservative Smoothingcited by 83
2022The Role of Coverage in Online Reinforcement Learningcited by 82
2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
2025Outcome-based Exploration for LLM Reasoningcited by 79
2021Understanding Domain Randomization for Sim-to-real Transfercited by 69
2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimismcited by 69
2021Feel-Good Thompson Sampling for Contextual Bandits and Reinforcement Learningcited by 65
2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
2024Self-Exploring Language Models: Active Preference Elicitation for Online Alignmentcited by 63
2022Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexitycited by 59
2021Exploration in Deep Reinforcement Learning: From Single-Agent to Multiagent Domaincited by 57
2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
2021Tactical Optimism and Pessimism for Deep Reinforcement Learningcited by 55
2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
2021Misspecified Gaussian Process Bandit Optimizationcited by 52
2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
2021Corruption-Robust Offline Reinforcement Learningcited by 51
2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 51
2022Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approachcited by 51
2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
2022Making Linear MDPs Practical via Contrastive Representation Learningcited by 49
2021Breaking the Deadly Triad with a Target Networkcited by 47
2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 42
2021Towards General Function Approximation in Zero-Sum Markov Gamescited by 42
2021Exponential Bellman Equation and Improved Regret Bounds for Risk-Sensitive Reinforcement Learningcited by 42
2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
2024Dataset Reset Policy Optimization for RLHFcited by 41
2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
2025Towards General-Purpose Model-Free Reinforcement Learningcited by 40
2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39

50 most cited of 514 All 514 (JSON)