Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation
Preprint
Abstract
We study the problem of deployment efficient reinforcement learning (RL) with linear function approximation under the \emph{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 $\widetilde{O}(\frac{d^2H^5}{\epsilon^2})$ trajectories within $H$ deployments to identify $\epsilon$-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.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Reinforcement Learning in Healthcare: A SurveyACM Computing Surveys, 2021
- Optimization of Molecules via Deep Reinforcement LearningScientific Reports, 2019
- Batched bandit problemsThe Annals of Statistics, 2016
- Near-Optimal Reinforcement Learning in Polynomial TimeMachine Learning, 2002
- Finite-time Analysis of the Multiarmed Bandit ProblemMachine Learning, 2002
- The Equivalence of Two Extremum ProblemsCanadian Journal of Mathematics, 1960