A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation

2023/11/26 by Heyang Zhao, Zhao, Heyang, Jiafan He +3 · 2 citations
Computer Science · Decision Sciences · #Reinforcement Learning in Robotics #Advanced Bandit Algorithms Research #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2311.15238

Abstract

The exploration-exploitation dilemma has been a central challenge in reinforcement learning (RL) with complex model classes. In this paper, we propose a new algorithm, Monotonic Q-Learning with Upper Confidence Bound (MQL-UCB) for RL with general function approximation. Our key algorithmic design includes (1) a general deterministic policy-switching strategy that achieves low switching cost, (2) a monotonic value function structure with carefully controlled function class complexity, and (3) a variance-weighted regression scheme that exploits historical trajectories with high data efficiency. MQL-UCB achieves minimax optimal regret of O(d√(HK)) when K is sufficiently large and near-optimal policy switching cost of O(dH), with d being the eluder dimension of the function class, H being the planning horizon, and K being the number of episodes. Our work sheds light on designing provably sample-efficient and deployment-efficient Q-learning with nonlinear function approximation.

Cited by

• Breaking the Total Variance Barrier: Sharp Sample Complexity for Linear Heteroscedastic Bandits with Fixed Action Set
• A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory

Related

• Near-Optimal Deployment Efficiency in Reward-Free Reinforcement Learning with Linear Function Approximation
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning
• Sample Complexity of Kernel-Based Q-Learning
• Constrained Policy Improvement for Safe and Efficient Reinforcement\n Learning
• Reinforcement Learning with General Value Function Approximation: Provably Efficient Approach via Bounded Eluder Dimension