VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation

2022/12/12 by Agarwal, Alekh, Jin, Yujia, Zhang, Tong · 2 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2212.06069

Abstract

We study time-inhomogeneous episodic reinforcement learning (RL) under general function approximation and sparse rewards. We design a new algorithm, Variance-weighted Optimistic Q-Learning (VOQL), based on Q-learning and bound its regret assuming completeness and bounded Eluder dimension for the regression function class. As a special case, VOQL achieves O(d√(HT)+d⁶H⁵) regret over T episodes for a horizon H MDP under (d-dimensional) linear function approximation, which is asymptotically optimal. Our algorithm incorporates weighted regression-based upper and lower bounds on the optimal value function to obtain this improved regret. The algorithm is computationally efficient given a regression oracle over the function class, making this the first computationally tractable and statistically optimal approach for linear MDPs.

Cited by

• Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits
• Near-Optimal Second-Order Guarantees for Model-Based Adversarial Imitation Learning

Related

• Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning
• Value Function Approximations via Kernel Embeddings for No-Regret Reinforcement Learning
• Optimism in Reinforcement Learning with Generalized Linear Function Approximation
• Optimistic Q-learning for average reward and episodic reinforcement learning
• Horizon-Free and Instance-Dependent Regret Bounds for Reinforcement Learning with General Function Approximation