mlsanityData to 7 Oct 2026

Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation

arXiv 2206.11489 ↗First posted 23 Jun 2022cs.LGcited by 30

Not on the map. Why?

Abstract (arXiv)

We study reinforcement learning with linear function approximation where the transition probability and reward functions are linear with respect to a feature mapping boldsymbolφ(s,a). Specifically, we consider the episodic inhomogeneous linear Markov Decision Process (MDP), and propose a novel computation-efficient algorithm, LSVI-UCB^+, which achieves an widetildeO(Hd√T) regret bound where H is the episode length, d is the feature dimension, and T is the number of steps. LSVI-UCB^+ builds on weighted ridge regression and upper confidence value iteration with a Bernstein-type exploration bonus. Our statistical results are obtained with novel analytical tools, including a new Bernstein self-normalized bound with conservatism on elliptical potentials, and refined analysis of the correction term. This is a minimax optimal algorithm for linear MDPs up to logarithmic factors, which closes the √Hd gap between the upper bound of widetildeO(√H3d3T) in (Jin et al., 2020) and lower bound of Omega(Hd√T) for linear MDPs.

Key facts. Cited by 30 papers in the map (data through 7 Oct 2026). Builds on 19 of its 36 references that are in the map. First posted on arXiv 23 Jun 2022.

Builds on

19 of 36 references.

References · 19

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  3. 2018Is Q-learning Provably Efficient?cited by 485
  4. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  6. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  7. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  8. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  9. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  10. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  11. 2020Improved Optimistic Algorithms for Logistic Banditscited by 117
  12. 2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
7 more
  1. 2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
  2. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  3. 2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 75
  4. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  5. 2021Randomized Exploration for Reinforcement Learning with General Value Function Approximationcited by 49
  6. 2019Tight Regret Bounds for Infinite-armed Linear Contextual Banditscited by 17
  7. 2019Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalitiescited by 15

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 5; 2023: 12; 2024: 9; 2025: 1; 2026: 3.

30 papers.

Sort:

By area:

  1. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  2. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  3. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  4. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  5. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
  6. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learningcited by 15
  7. 2023Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimizationcited by 14
  8. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  9. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  10. 2023Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Boundscited by 13
  11. 2022Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Explorationcited by 11
  12. 2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
18 more
  1. 2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
  2. 2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
  3. 2022Near-optimal Policy Identification in Active Reinforcement Learningcited by 7
  4. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
  5. 2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 5
  6. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  7. 2024Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learningcited by 5
  8. 2023Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practicecited by 4
  9. 2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
  10. 2024Sample Complexity Characterization for Linear Contextual MDPscited by 4
  11. 2024Demystifying Linear MDPs and Novel Dynamics Aggregation Frameworkcited by 4
  12. 2023A Doubly Robust Approach to Sparse Reinforcement Learningcited by 3
  13. 2024Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximationcited by 2
  14. 2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
  15. 2026When Do Multi-Agent Systems Outperform? Analysing the Learning Efficiency of Agentic Systemscited by 1
  16. 2025Influential Bandits: Pulling an Arm May Change the Environmentcited by 0
  17. 2026DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guaranteescited by 0
  18. 2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 0