# Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximation

arXiv: https://arxiv.org/abs/2206.11489 · HTML: https://mlsanity.com/paper/2206.11489/

## Key facts

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

## Builds on (most cited first, 19 of 19)

- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Improved Optimistic Algorithms for Logistic Bandits](https://mlsanity.com/paper/2002.07530/) (2020)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensembles](https://mlsanity.com/paper/1910.10597/) (2019)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [On Oracle-Efficient PAC RL with Rich Observations](https://mlsanity.com/paper/1803.00606/) (2018)
- [Randomized Exploration for Reinforcement Learning with General Value Function Approximation](https://mlsanity.com/paper/2106.07841/) (2021)
- [Tight Regret Bounds for Infinite-armed Linear Contextual Bandits](https://mlsanity.com/paper/1905.01435/) (2019)
- [Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities](https://mlsanity.com/paper/1905.12425/) (2019)

## Built on by (most cited first, 30 of 30)

- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processes](https://mlsanity.com/paper/2305.08841/) (2023)
- [Near-Optimal Differentially Private Reinforcement Learning](https://mlsanity.com/paper/2212.04680/) (2022)
- [Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning](https://mlsanity.com/paper/2409.20521/) (2024)
- [Improved Regret Bounds for Linear Adversarial MDPs via Linear Optimization](https://mlsanity.com/paper/2302.06834/) (2023)
- [Tackling Heavy-Tailed Rewards in Reinforcement Learning with Function Approximation: Minimax Optimal and Instance-Dependent Regret Bounds](https://mlsanity.com/paper/2306.06836/) (2023)
- [A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2311.15238/) (2023)
- [Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2210.00701/) (2022)
- [Understanding Deep Neural Function Approximation in Reinforcement Learning via ε-Greedy Exploration](https://mlsanity.com/paper/2209.07376/) (2022)
- [Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation](https://mlsanity.com/paper/2305.06446/) (2023)
- [Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learning](https://mlsanity.com/paper/2310.01380/) (2023)
- [Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewards](https://mlsanity.com/paper/2303.05606/) (2023)
- [Near-optimal Policy Identification in Active Reinforcement Learning](https://mlsanity.com/paper/2212.09510/) (2022)
- [A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guarantees](https://mlsanity.com/paper/2401.17780/) (2024)
- [Pessimism Meets Risk: Risk-Sensitive Offline Reinforcement Learning](https://mlsanity.com/paper/2407.07631/) (2024)
- [Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs](https://mlsanity.com/paper/2408.04526/) (2024)
- [Sample Complexity Characterization for Linear Contextual MDPs](https://mlsanity.com/paper/2402.02700/) (2024)
- [Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processes](https://mlsanity.com/paper/2407.03065/) (2024)
- [Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practice](https://mlsanity.com/paper/2305.13185/) (2023)
- [Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback](https://mlsanity.com/paper/2311.07876/) (2023)
- [Demystifying Linear MDPs and Novel Dynamics Aggregation Framework](https://mlsanity.com/paper/2410.24089/) (2024)
- [A Doubly Robust Approach to Sparse Reinforcement Learning](https://mlsanity.com/paper/2310.15286/) (2023)
- [Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximation](https://mlsanity.com/paper/2406.13633/) (2024)
- [When Do Multi-Agent Systems Outperform? Analysing the Learning Efficiency of Agentic Systems](https://mlsanity.com/paper/2602.08272/) (2026)
- [Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Span](https://mlsanity.com/paper/2410.14992/) (2024)
- [Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Cost](https://mlsanity.com/paper/2609.00193/) (2026)
- [Influential Bandits: Pulling an Arm May Change the Environment](https://mlsanity.com/paper/2504.08200/) (2025)
- [DARLING: Detection Augmented Reinforcement Learning with Non-Stationary Guarantees](https://mlsanity.com/paper/2604.16684/) (2026)

## 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.