Data to 14 Oct 2026

Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes

arXiv 2212.06132 ↗First posted 12 Dec 2022cs.LG math.OC stat.MLcited by 57

Not on the map. Why?

Cited by 31 in Deep reinforcement learning methods, but placed by its own abstract, which didn’t fit.

Abstract (arXiv)

We study reinforcement learning (RL) with linear function approximation. For episodic time-inhomogeneous linear Markov decision processes (linear MDPs) whose transition probability can be parameterized as a linear function of a given feature mapping, we propose the first computationally efficient algorithm that achieves the nearly minimax optimal regret tilde O(d√H3K), where d is the dimension of the feature mapping, H is the planning horizon, and K is the number of episodes. Our algorithm is based on a weighted linear regression scheme with a carefully designed weight, which depends on a new variance estimator that (1) directly estimates the variance of the optimal value function, (2) monotonically decreases with respect to the number of episodes to ensure a better estimation accuracy, and (3) uses a rare-switching policy to update the value function estimator to control the complexity of the estimated value function class. Our work provides a complete answer to optimal RL with linear MDPs, and the developed algorithm and theoretical tools may be of independent interest.

Key facts. Cited by 57 papers in the map (data through 14 Oct 2026). Builds on 27 of its 39 references that are in the map. First posted on arXiv 12 Dec 2022.

Builds on

27 of 39 references.

References · 27

2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
2017Minimax Regret Bounds for Reinforcement Learningcited by 503
2018Is Q-learning Provably Efficient?cited by 487
2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
2019Is a Good Representation Sufficient for Sample Efficient Reinforcement Learning?cited by 140
2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124

15 more

2019Optimism in Reinforcement Learning with Generalized Linear Function Approximationcited by 111
2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
2019Sample Complexity of Reinforcement Learning using Linearly Combined Model Ensemblescited by 100
2020Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal Algorithm Escaping the Curse of Horizoncited by 99
2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
2018Information Directed Sampling and Bandits with Heteroscedastic Noisecited by 76
2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
2020Nearly Minimax Optimal Reinforcement Learning for Discounted MDPscited by 42
2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 18; 2024: 26; 2025: 8; 2026: 5.

57 papers.

Sort:

By area:

38 more

2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processescited by 14
2023Optimistic Natural Policy Gradient: a Simple Efficient Policy Optimization Framework for Online RLcited by 13
2024Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximationcited by 10
2023Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximationcited by 9
2023Pessimistic Nonlinear Least-Squares Value Iteration for Offline Reinforcement Learningcited by 9
2023Variance-aware robust reinforcement learning with linear function approximation under heavy-tailed rewardscited by 8
2023Minimax Optimal Q Learning with Nearest Neighborscited by 8
2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
2023On the Model-Misspecification in Reinforcement Learningcited by 7
2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPscited by 7
2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximationcited by 7
2025Replicable Reinforcement Learning with Linear Function Approximationcited by 7
2024A Policy Gradient Primal-Dual Algorithm for Constrained MDPs with Uniform PAC Guaranteescited by 6
2024Horizon-Free Regret for Linear Markov Decision Processescited by 6
2024Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximationcited by 6
2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
2024Sample Complexity Characterization for Linear Contextual MDPscited by 5
2024Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamicscited by 5
2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
2023Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPscited by 4
2023Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practicecited by 4
2023Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedbackcited by 4
2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 4
2024Linear Bellman Completeness Suffices for Efficient Online Reinforcement Learning with Few Actionscited by 4
2025Vector-valued self-normalized concentration inequalities beyond sub-Gaussianitycited by 4
2023Posterior Sampling with Delayed Feedback for Reinforcement Learning with Linear Function Approximationcited by 3
2024Achieving Constant Regret in Linear Markov Decision Processescited by 3
2024Multiple Greedy Quasi-Newton Methods for Saddle Point Problemscited by 3
2025Catoni Contextual Bandits are Robust to Heavy-tailed Rewardscited by 3
2025Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximationcited by 3
2024Infinite-Horizon Reinforcement Learning with Multinomial Logistic Function Approximationcited by 2
2024Robust Thompson Sampling Algorithms Against Reward Poisoning Attackscited by 2
2025Minimax Optimal Reinforcement Learning with Quasi-Optimismcited by 2
2025Multi-Agent Reinforcement Learning in Intelligent Transportation Systems: A Comprehensive Surveycited by 2
2025Online Robust Reinforcement Learning with General Function Approximationcited by 2
2024Learning Infinite-Horizon Average-Reward Linear Mixture MDPs of Bounded Spancited by 1
2024The Limits of Transfer Reinforcement Learning with Latent Low-rank Structurecited by 1
2026Provably Efficient Federated Reinforcement Learning with Linear Function Approximation and Logarithmic Communication Costcited by 1

50 most cited of 57 All 57 (JSON)