Randomized Exploration for Reinforcement Learning with General Value Function Approximation

2021/06/15 by Ishfaq, Haque, Cui, Qiwen, Nguyen, Viet +5 · 4 citations
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2106.07841

Abstract

We propose a model-free reinforcement learning algorithm inspired by the popular randomized least squares value iteration (RLSVI) algorithm as well as the optimism principle. Unlike existing upper-confidence-bound (UCB) based approaches, which are often computationally intractable, our algorithm drives exploration by simply perturbing the training data with judiciously chosen i.i.d. scalar noises. To attain optimistic value function estimation without resorting to a UCB-style bonus, we introduce an optimistic reward sampling procedure. When the value functions can be represented by a function class F, our algorithm achieves a worst-case regret bound of \widetildeO(poly(d_EH)√(T)) where T is the time elapsed, H is the planning horizon and d_E is the eluder dimension of F. In the linear setting, our algorithm reduces to LSVI-PHE, a variant of RLSVI, that enjoys an \widetildeO(√(d³H³T)) regret. We complement the theory with an empirical evaluation across known difficult exploration tasks.

Cited by

• Rediscovering Entropy Regularization: Adaptive Coefficient Unlocks Its Potential for LLM Reinforcement Learning
• Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits
• Homomorphic Mappings for Value-Preserving State Aggregation in Markov Decision Processes
• An Arbitration Control for an Ensemble of Diversified DQN variants in Continual Reinforcement Learning

Related

• Generalization and Exploration via Randomized Value Functions
• Deep Exploration via Randomized Value Functions
• On Optimistic versus Randomized Exploration in Reinforcement Learning
• Worst-Case Regret Bounds for Exploration via Randomized Value Functions
• Frequentist Regret Bounds for Randomized Least-Squares Value Iteration