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