Tightening Exploration in Upper Confidence Reinforcement Learning

2020/04/20 by Hippolyte Bourel, Odalric-Ambrym Maillard, Bourel, Hippolyte +3 · 6 citations
Computer Science · Decision Sciences · #Adaptive Dynamic Programming Control #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Electrical engineering #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics #Systems and Control (eess.SY) #electronic engineering #information engineering

paper · pdf · doi:10.48550/arxiv.2004.09656

openalex publication_date 2020/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The upper confidence reinforcement learning (UCRL2) algorithm introduced in (Jaksch et al., 2010) is a popular method to perform regret minimization in unknown discrete Markov Decision Processes under the average-reward criterion. Despite its nice and generic theoretical regret guarantees, this algorithm and its variants have remained until now mostly theoretical as numerical experiments in simple environments exhibit long burn-in phases before the learning takes place. In pursuit of practical efficiency, we present UCRL3, following the lines of UCRL2, but with two key modifications: First, it uses state-of-the-art time-uniform concentration inequalities to compute confidence sets on the reward and (component-wise) transition distributions for each state-action pair. Furthermore, to tighten exploration, it uses an adaptive computation of the support of each transition distribution, which in turn enables us to revisit the extended value iteration procedure of UCRL2 to optimize over distributions with reduced support by disregarding low probability transitions, while still ensuring near-optimism. We demonstrate, through numerical experiments in standard environments, that reducing exploration this way yields a substantial numerical improvement compared to UCRL2 and its variants. On the theoretical side, these key modifications enable us to derive a regret bound for UCRL3 improving on UCRL2, that for the first time makes appear notions of local diameter and local effective support, thanks to variance-aware concentration bounds.

Citations

• REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs
• Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function

Cited by

• Tail Distribution of Regret in Optimistic Reinforcement Learning
• The Confusing Instance Principle for Online Linear Quadratic Control
• Towards Blackwell Optimality: Bellman Optimality Is All You Can Get
• Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learning
• CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption
• Statistical and Algorithmic Foundations of Reinforcement Learning

Related

• Constrained Upper Confidence Reinforcement Learning
• Near-optimal Optimistic Reinforcement Learning using Empirical Bernstein Inequalities
• Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits
• Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism
• Randomized Exploration for Reinforcement Learning with General Value Function Approximation