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

2022/10/03 by Qiao, Dan, Wang, Yu-Xiang · 1 citation
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2210.00701

Abstract

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((d²H⁵)/(ε²)) 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.

Cited by

• A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory

Related

• Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimality
• A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation
• Nearly Minimax Optimal Reward-free Reinforcement Learning
• Reward-Free Exploration for Reinforcement Learning
• On Reward-Free Reinforcement Learning with Linear Function Approximation