mlsanityData to 7 Oct 2026

Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimality

arXiv 2202.06450 ↗First posted 14 Feb 2022cs.LG cs.AI stat.MLcited by 24

Not on the map. Why?

Abstract (arXiv)

Deployment efficiency is an important criterion for many real-world applications of reinforcement learning (RL). Despite the community's increasing interest, there lacks a formal theoretical formulation for the problem. In this paper, we propose such a formulation for deployment-efficient RL (DE-RL) from an "optimization with constraints" perspective: we are interested in exploring an MDP and obtaining a near-optimal policy within minimal deployment complexity, whereas in each deployment the policy can sample a large batch of data. Using finite-horizon linear MDPs as a concrete structural model, we reveal the fundamental limit in achieving deployment efficiency by establishing information-theoretic lower bounds, and provide algorithms that achieve the optimal deployment efficiency. Moreover, our formulation for DE-RL is flexible and can serve as a building block for other practically relevant settings; we give "Safe DE-RL" and "Sample-Efficient DE-RL" as two examples, which may be worth future investigation.

Key facts. Cited by 24 papers in the map (data through 7 Oct 2026). Builds on 52 of its 72 references that are in the map. First posted on arXiv 14 Feb 2022.

Builds on

52 of 72 references.

References · 52

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,211
  2. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,777
  3. 2018Exploration by Random Network Distillationcited by 966
  4. 2021A Minimalist Approach to Offline Reinforcement Learningcited by 882
  5. 2016Unifying Count-Based Exploration and Intrinsic Motivationcited by 632
  6. 2020MOPO: Model-based Offline Policy Optimizationcited by 630
  7. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  8. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  9. 2018Is Q-learning Provably Efficient?cited by 485
  10. 2015An Introduction to Matrix Concentration Inequalitiescited by 391
  11. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  12. 2015Doubly Robust Off-policy Value Evaluation for Reinforcement Learningcited by 337
38 more
  1. 2019Reinforcement Learning in Healthcare: A Surveycited by 308
  2. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 290
  3. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  4. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  5. 2018Provably Efficient Maximum Entropy Explorationcited by 240
  6. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  7. 2018Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimationcited by 226
  8. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  9. 2020Accelerating Reinforcement Learning with Learned Skill Priorscited by 220
  10. 2019Go-Explore: a New Approach for Hard-Exploration Problemscited by 207
  11. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  12. 2019AlgaeDICE: Policy Gradient from Arbitrary Experiencecited by 187
  13. 2021Reinforcement learning based recommender systems: A surveycited by 187
  14. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  15. 2019Provably efficient RL with Rich Observations via Latent State Decodingcited by 169
  16. 2021Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learningcited by 157
  17. 2019Minimax Weight and Q-Function Learning for Off-Policy Evaluationcited by 150
  18. 2017Safe Policy Improvement with Baseline Bootstrappingcited by 141
  19. 2021OptiDICE: Offline Policy Optimization via Stationary Distribution Correction Estimationcited by 121
  20. 2020Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimizationcited by 120
  21. 2019Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learningcited by 114
  22. 2020PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learningcited by 91
  23. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  24. 2020Learning with AMIGo: Adversarially Motivated Intrinsic Goalscited by 86
  25. 2020Off-Policy Evaluation via the Regularized Lagrangiancited by 86
  26. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  27. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  28. 2018On Oracle-Efficient PAC RL with Rich Observationscited by 71
  29. 2020Sequential Batch Learning in Finite-Action Linear Contextual Banditscited by 63
  30. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  31. 2021Tactical Optimism and Pessimism for Deep Reinforcement Learningcited by 55
  32. 2020Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Designcited by 51
  33. 2019Regret Bounds for Batched Banditscited by 49
  34. 2021MADE: Exploration via Maximizing Deviation from Explored Regionscited by 40
  35. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  36. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  37. 2017Posterior sampling for reinforcement learning: worst-case regret boundscited by 28
  38. 2020The Elliptical Potential Lemma Revisitedcited by 23

50 most cited of 52 All 52 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 3; 2023: 11; 2024: 3; 2025: 2; 2026: 5.

24 papers.

Sort:

By area:

  1. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  2. 2026Demystifying Group Relative Policy Optimization: Its Policy Gradient is a U-Statisticcited by 19
  3. 2023Reinforcement Learning in Low-Rank MDPs with Density Featurescited by 17
  4. 2023Provably Feedback-Efficient Reinforcement Learning via Active Reward Learningcited by 15
  5. 2023A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximationcited by 14
  6. 2022Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximationcited by 13
  7. 2023On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximationcited by 13
  8. 2023Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Datacited by 11
  9. 2024Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RLcited by 9
  10. 2023Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPscited by 8
  11. 2023Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPscited by 7
  12. 2023MA2CL:Masked Attentive Contrastive Learning for Multi-Agent Reinforcement Learningcited by 6
12 more
  1. 2023Finite-sample Guarantees for Nash Q-learning with Linear Function Approximationcited by 4
  2. 2024Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraintscited by 3
  3. 2022One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learningcited by 2
  4. 2023Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivitycited by 2
  5. 2025Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximationcited by 2
  6. 2023Robust Knowledge Transfer in Tiered Reinforcement Learningcited by 1
  7. 2026Adaptive Policy Selection and Fine-Tuning under Interaction Budgets for Offline-to-Online Reinforcement Learningcited by 1
  8. 2024Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPscited by 0
  9. 2025Safely Exploring Novel Actions in Recommender Systems via Deployment-Efficient Policy Learningcited by 0
  10. 2026The Horizon Threshold in Cooperative Multi-Agent Reward-Free Explorationcited by 0
  11. 2026A Queueing-Theoretic Framework for Dynamic Attack Surfaces: Data-Integrated Risk Analysis and Adaptive Defensecited by 0
  12. 2026Active Offline-to-Online Reinforcement Learningcited by 0