mlsanityData to 14 Oct 2026

Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation

arXiv 2210.00701 ↗First posted 3 Oct 2022cs.LG cs.AI stat.MLcited by 13

Not on the map. Why?

Abstract (arXiv)

We study the problem of deployment efficient reinforcement learning (RL) with linear function approximation under the reward-free exploration setting. This is a well-motivated problem because deploying new policies is costly in real-life RL applications. Under the linear MDP setting with feature dimension d and planning horizon H, we propose a new algorithm that collects at most widetildeO(fracd2H5ε2) trajectories within H deployments to identify ε-optimal policy for any (possibly data-dependent) choice of reward functions. To the best of our knowledge, our approach is the first to achieve optimal deployment complexity and optimal d dependence in sample complexity at the same time, even if the reward is known ahead of time. Our novel techniques include an exploration-preserving policy discretization and a generalized G-optimal experiment design, which could be of independent interest. Lastly, we analyze the related problem of regret minimization in low-adaptive RL and provide information-theoretic lower bounds for switching cost and batch complexity.

Key facts. Cited by 13 papers in the map (data through 14 Oct 2026). Builds on 41 of its 75 references that are in the map. First posted on arXiv 3 Oct 2022.

Builds on

41 of 75 references.

References · 41

  1. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2018Is Q-learning Provably Efficient?cited by 487
  4. 2019Reinforcement Learning in Healthcare: A Surveycited by 310
  5. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  6. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  7. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  8. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  9. 2018Optimization of Molecules via Deep Reinforcement Learningcited by 200
  10. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  11. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  12. 2021Reinforcement learning based recommender systems: A surveycited by 188
29 more
  1. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  2. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  3. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  4. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  5. 2020Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimizationcited by 120
  6. 2019Batched Multi-armed Bandits Problemcited by 98
  7. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  8. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  9. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  10. 2019Provably Efficient Q-Learning with Low Switching Costcited by 78
  11. 2020Adaptive Reward-Free Explorationcited by 77
  12. 2020Sequential Batch Learning in Finite-Action Linear Contextual Banditscited by 63
  13. 2013Online Learning with Switching Costs and Other Adaptive Adversariescited by 61
  14. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  15. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  16. 2019Regret Bounds for Batched Banditscited by 49
  17. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  18. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 40
  19. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  20. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  21. 2021Variance-Aware Off-Policy Evaluation with Linear Function Approximationcited by 34
  22. 2022Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Designcited by 33
  23. 2022Sample-Efficient Reinforcement Learning with loglog(T) Switching Costcited by 32
  24. 2022Nearly Minimax Optimal Reinforcement Learning with Linear Function Approximationcited by 30
  25. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 29
  26. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  27. 2020Nearly Minimax Optimal Reward-free Reinforcement Learningcited by 26
  28. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  29. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 14

Built on by

Cited by year

Citing papers per year: 2022: 1; 2023: 6; 2024: 5; 2025: 1.

13 papers.

Sort:

By area:

  1. 2022Near-Optimal Differentially Private Reinforcement Learningcited by 16
  2. 2023Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learningcited by 16
  3. 2023Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learningcited by 15
  4. 2024Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learningcited by 15
  5. 2024Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizescited by 12
  6. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  7. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 9
  8. 2024Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPscited by 6
  9. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 4
  10. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
  11. 2024Differentially Private Reinforcement Learning with Self-Playcited by 1
  12. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theorycited by 1
1 more
  1. 2023Offline Policy Evaluation for Reinforcement Learning with Adaptively Collected Datacited by 0