mlsanityData to 7 Oct 2026

Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes

arXiv 2012.08507 ↗First posted 15 Dec 2020cs.LG math.OC stat.MLcited by 199

Not on the map. Why?

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

Abstract (arXiv)

We study reinforcement learning (RL) with linear function approximation where the underlying transition probability kernel of the Markov decision process (MDP) is a linear mixture model (Jia et al., 2020; Ayoub et al., 2020; Zhou et al., 2020) and the learning agent has access to either an integration or a sampling oracle of the individual basis kernels. We propose a new Bernstein-type concentration inequality for self-normalized martingales for linear bandit problems with bounded noise. Based on the new inequality, we propose a new, computationally efficient algorithm with linear function approximation named UCRL-VTR+ for the aforementioned linear mixture MDPs in the episodic undiscounted setting. We show that UCRL-VTR+ attains an tilde O(dH√T) regret where d is the dimension of feature mapping, H is the length of the episode and T is the number of interactions with the MDP. We also prove a matching lower bound Omega(dH√T) for this setting, which shows that UCRL-VTR+ is minimax optimal up to logarithmic factors. In addition, we propose the UCLK+ algorithm for the same family of MDPs under discounting and show that it attains an tilde O(d√T/(1-γ)1.5) regret, where γ∈ [0,1) is the discount factor. Our upper bound matches the lower bound Omega(d√T/(1-γ)1.5) proved by Zhou et al. (2020) up to logarithmic factors, suggesting that UCLK+ is nearly minimax optimal. To the best of our knowledge, these are the first computationally efficient, nearly minimax optimal algorithms for RL with linear function approximation.

Key facts. Cited by 199 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Dec 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 38; 2022: 42; 2023: 49; 2024: 35; 2025: 22; 2026: 13.

199 papers.

Sort:

By area:

  1. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  2. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  3. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  4. 2025Outcome-based Exploration for LLM Reasoningcited by 79
  5. 2021Understanding Domain Randomization for Sim-to-real Transfercited by 69
  6. 2022Near-optimal Offline Reinforcement Learning with Linear Representation: Leveraging Variance Information with Pessimismcited by 63
  7. 2022Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processescited by 57
  8. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  9. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  10. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Gamecited by 53
  11. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  12. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
38 more
  1. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  2. 2023Reason for Future, Act for Now: A Principled Framework for Autonomous LLM Agents with Provable Sample Efficiencycited by 46
  3. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  4. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  5. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
  6. 2021Simple Agent, Complex Environment: Efficient Reinforcement Learning with Agent Statescited by 42
  7. 2022Leveraging Offline Data in Online Reinforcement Learningcited by 42
  8. 2021An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gapcited by 40
  9. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  10. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 39
  11. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  12. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  13. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  14. 2022On the Complexity of Adversarial Decision Makingcited by 32
  15. 2023Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaRcited by 32
  16. 2022Model-based RL with Optimistic Posterior Sampling: Structural Conditions and Sample Complexitycited by 31
  17. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  18. 2021Weighted Gaussian Process Bandits for Non-stationary Environmentscited by 30
  19. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  20. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  21. 2023Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficientcited by 29
  22. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 29
  23. 2023Provable and Practical: Efficient Exploration in Reinforcement Learning via Langevin Monte Carlocited by 29
  24. 2021Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPscited by 28
  25. 2023A Theoretical Analysis of Optimistic Proximal Policy Optimization in Linear Markov Decision Processescited by 28
  26. 2021Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisitingcited by 27
  27. 2022Contrastive UCB: Provably Efficient Contrastive Self-Supervised Learning in Online Reinforcement Learningcited by 26
  28. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  29. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  30. 2022Regret Bounds for Information-Directed Reinforcement Learningcited by 24
  31. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithmscited by 24
  32. 2021Learning Stochastic Shortest Path with Linear Function Approximationcited by 23
  33. 2022Differentially Private Reinforcement Learning with Linear Function Approximationcited by 22
  34. 2022On Instance-Dependent Bounds for Offline Reinforcement Learning with Linear Function Approximationcited by 22
  35. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  36. 2021Linear Contextual Bandits with Adversarial Corruptionscited by 21
  37. 2023Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Explorationcited by 20
  38. 2022Offline Reinforcement Learning with Differential Privacycited by 19

50 most cited of 199 All 199 (JSON)