mlsanityData to 14 Oct 2026

Best Policy Identification in Linear MDPs

arXiv 2208.05633 ↗First posted 11 Aug 2022cs.LG stat.MLcited by 4

Not on the map. Why?

Abstract (arXiv)

We investigate the problem of best policy identification in discounted linear Markov Decision Processes in the fixed confidence setting under a generative model. We first derive an instance-specific lower bound on the expected number of samples required to identify an varepsilon-optimal policy with probability 1-δ. The lower bound characterizes the optimal sampling rule as the solution of an intricate non-convex optimization program, but can be used as the starting point to devise simple and near-optimal sampling rules and algorithms. We devise such algorithms. One of these exhibits a sample complexity upper bounded by cal O(fracd(varepsilon+Delta)2 (log(frac1δ)+d)) where Delta denotes the minimum reward gap of sub-optimal actions and d is the dimension of the feature space. This upper bound holds in the moderate-confidence regime (i.e., for all δ), and matches existing minimax and gap-dependent lower bounds. We extend our algorithm to episodic linear MDPs.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 16 of its 31 references that are in the map. First posted on arXiv 11 Aug 2022.

Builds on

16 of 31 references.

References · 16

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2015An Introduction to Matrix Concentration Inequalitiescited by 397
  3. 2014On the Complexity of Best Arm Identification in Multi-Armed Bandit Modelscited by 286
  4. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  5. 2019Learning with Good Feature Representations in Bandits and in RL with a Generative Modelcited by 127
  6. 2020Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Modelcited by 109
  7. 2015Sample Complexity of Episodic Fixed-Horizon Reinforcement Learningcited by 106
  8. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  9. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  10. 2014Best-Arm Identification in Linear Banditscited by 100
  11. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  12. 2020Optimal Best-arm Identification in Linear Banditscited by 71
4 more
  1. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  2. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  3. 2021Navigating to the Best Policy in Markov Decision Processescited by 29
  4. 2020Adaptive Sampling for Best Policy Identification in Markov Decision Processescited by 20

Built on by

Cited by year

Citing papers per year: 2023: 2; 2024: 0; 2025: 2.

4 papers.

  1. 2023Regularization and Variance-Weighted Regression Achieves Minimax Optimality in Linear MDPs: Theory and Practicecited by 4
  2. 2025Optimal Transfer Learning for Missing Not-at-Random Matrix Completioncited by 2
  3. 2025Policy Testing in Markov Decision Processescited by 2
  4. 2023Model-Free, Regret-Optimal Best Policy Identification in Online CMDPscited by 0