# Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimality

arXiv: https://arxiv.org/abs/2202.06450 · HTML: https://mlsanity.com/paper/2202.06450/

## Key facts

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

## Builds on (most cited first, 30 of 52)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Conservative Q-Learning for Offline Reinforcement Learning](https://mlsanity.com/paper/2006.04779/) (2020)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [A Minimalist Approach to Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06860/) (2021)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [MOPO: Model-based Offline Policy Optimization](https://mlsanity.com/paper/2005.13239/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Doubly Robust Off-policy Value Evaluation for Reinforcement Learning](https://mlsanity.com/paper/1511.03722/) (2015)
- [Reinforcement Learning in Healthcare: A Survey](https://mlsanity.com/paper/1908.08796/) (2019)
- [Contextual Decision Processes with Low Bellman Rank are PAC-Learnable](https://mlsanity.com/paper/1610.09512/) (2016)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation](https://mlsanity.com/paper/1810.12429/) (2018)
- [Accelerating Reinforcement Learning with Learned Skill Priors](https://mlsanity.com/paper/2010.11944/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Go-Explore: a New Approach for Hard-Exploration Problems](https://mlsanity.com/paper/1901.10995/) (2019)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [AlgaeDICE: Policy Gradient from Arbitrary Experience](https://mlsanity.com/paper/1912.02074/) (2019)
- [Reinforcement learning based recommender systems: A survey](https://mlsanity.com/paper/2101.06286/) (2021)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Provably efficient RL with Rich Observations via Latent State Decoding](https://mlsanity.com/paper/1901.09018/) (2019)
- [Policy Finetuning: Bridging Sample-Efficient Offline and Online Reinforcement Learning](https://mlsanity.com/paper/2106.04895/) (2021)
- [Minimax Weight and Q-Function Learning for Off-Policy Evaluation](https://mlsanity.com/paper/1910.12809/) (2019)
- [Safe Policy Improvement with Baseline Bootstrapping](https://mlsanity.com/paper/1712.06924/) (2017)

## Built on by (most cited first, 24 of 24)

- [On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RL](https://mlsanity.com/paper/2206.10770/) (2022)
- [Demystifying Group Relative Policy Optimization: Its Policy Gradient is a U-Statistic](https://mlsanity.com/paper/2603.01162/) (2026)
- [Reinforcement Learning in Low-Rank MDPs with Density Features](https://mlsanity.com/paper/2302.02252/) (2023)
- [Provably Feedback-Efficient Reinforcement Learning via Active Reward Learning](https://mlsanity.com/paper/2304.08944/) (2023)
- [On the Statistical Efficiency of Mean-Field Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2305.11283/) (2023)
- [A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2311.15238/) (2023)
- [Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2210.00701/) (2022)
- [Policy Finetuning in Reinforcement Learning via Design of Experiments using Offline Data](https://mlsanity.com/paper/2307.04354/) (2023)
- [Logarithmic Switching Cost in Reinforcement Learning beyond Linear MDPs](https://mlsanity.com/paper/2302.12456/) (2023)
- [Model-Based RL for Mean-Field Games is not Statistically Harder than Single-Agent RL](https://mlsanity.com/paper/2402.05724/) (2024)
- [Optimal Horizon-Free Reward-Free Exploration for Linear Mixture MDPs](https://mlsanity.com/paper/2303.10165/) (2023)
- [MA2CL:Masked Attentive Contrastive Learning for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.02006/) (2023)
- [Finite-sample Guarantees for Nash Q-learning with Linear Function Approximation](https://mlsanity.com/paper/2303.00177/) (2023)
- [Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints](https://mlsanity.com/paper/2402.01111/) (2024)
- [Sample and Computationally Efficient Continuous-Time Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2505.14821/) (2025)
- [One Policy is Enough: Parallel Exploration with a Single Policy is Near-Optimal for Reward-Free Reinforcement Learning](https://mlsanity.com/paper/2205.15891/) (2022)
- [Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity](https://mlsanity.com/paper/2310.01616/) (2023)
- [Robust Knowledge Transfer in Tiered Reinforcement Learning](https://mlsanity.com/paper/2302.05534/) (2023)
- [Adaptive Policy Selection and Fine-Tuning under Interaction Budgets for Offline-to-Online Reinforcement Learning](https://mlsanity.com/paper/2605.05123/) (2026)
- [Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs](https://mlsanity.com/paper/2411.10906/) (2024)
- [Safely Exploring Novel Actions in Recommender Systems via Deployment-Efficient Policy Learning](https://mlsanity.com/paper/2510.07635/) (2025)
- [The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration](https://mlsanity.com/paper/2602.01453/) (2026)
- [A Queueing-Theoretic Framework for Dynamic Attack Surfaces: Data-Integrated Risk Analysis and Adaptive Defense](https://mlsanity.com/paper/2604.10427/) (2026)
- [Active Offline-to-Online Reinforcement Learning](https://mlsanity.com/paper/2607.11720/) (2026)

## 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.