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

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

## 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 (most cited first, 30 of 41)

- [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)
- [Reinforcement Learning in Healthcare: A Survey](https://mlsanity.com/paper/1908.08796/) (2019)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Optimization of Molecules via Deep Reinforcement Learning](https://mlsanity.com/paper/1810.08678/) (2018)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Reinforcement learning based recommender systems: A survey](https://mlsanity.com/paper/2101.06286/) (2021)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints](https://mlsanity.com/paper/2101.02195/) (2021)
- [Deployment-Efficient Reinforcement Learning via Model-Based Offline Optimization](https://mlsanity.com/paper/2006.03647/) (2020)
- [Batched Multi-armed Bandits Problem](https://mlsanity.com/paper/1904.01763/) (2019)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)
- [Policy Certificates: Towards Accountable Reinforcement Learning](https://mlsanity.com/paper/1811.03056/) (2018)
- [Provably Efficient Q-Learning with Low Switching Cost](https://mlsanity.com/paper/1905.12849/) (2019)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [Online Learning with Switching Costs and Other Adaptive Adversaries](https://mlsanity.com/paper/1302.4387/) (2013)
- [Provably Efficient Reward-Agnostic Navigation with Linear Value Iteration](https://mlsanity.com/paper/2008.07737/) (2020)
- [Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design](https://mlsanity.com/paper/2007.01980/) (2020)
- [Regret Bounds for Batched Bandits](https://mlsanity.com/paper/1910.04959/) (2019)
- [Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processes](https://mlsanity.com/paper/2201.11206/) (2022)
- [A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Cost](https://mlsanity.com/paper/2101.00494/) (2021)

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

- [Near-Optimal Differentially Private Reinforcement Learning](https://mlsanity.com/paper/2212.04680/) (2022)
- [Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning](https://mlsanity.com/paper/2305.10282/) (2023)
- [Minimax-Optimal Reward-Agnostic Exploration in Reinforcement Learning](https://mlsanity.com/paper/2304.07278/) (2023)
- [Traversing Pareto Optimal Policies: Provably Efficient Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2407.17466/) (2024)
- [Stable Minima Cannot Overfit in Univariate ReLU Networks: Generalization by Large Step Sizes](https://mlsanity.com/paper/2406.06838/) (2024)
- [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)
- [Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs](https://mlsanity.com/paper/2408.04526/) (2024)
- [Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints](https://mlsanity.com/paper/2402.01111/) (2024)
- [Sample-Efficiency in Multi-Batch Reinforcement Learning: The Need for Dimension-Dependent Adaptivity](https://mlsanity.com/paper/2310.01616/) (2023)
- [Differentially Private Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2404.07559/) (2024)
- [A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory](https://mlsanity.com/paper/2508.07746/) (2025)
- [Offline Policy Evaluation for Reinforcement Learning with Adaptively Collected Data](https://mlsanity.com/paper/2306.14063/) (2023)

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