Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation
This work addresses the challenge of costly policy deployments in real-life RL applications, offering a near-optimal solution for deployment efficiency with linear function approximation, though it is incremental in improving specific bounds.
The paper tackles the problem of deployment-efficient reinforcement learning with linear function approximation in a reward-free setting, proposing an algorithm that collects at most $\widetilde{O}( rac{d^2H^5}{ε^2})$ trajectories within $H$ deployments to identify an $ε$-optimal policy for any reward function. It achieves optimal deployment complexity and optimal $d$ dependence in sample complexity simultaneously, a first in this context.
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}{ε^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.