Minimax Regret Bounds for Reinforcement Learning

By Mohammad Gheshlaghi Azar, Ian Osband, R´emi Munos. 2017

882 citations recorded by the source corpus.

We consider the problem of provably optimal exploration in reinforcement learning for finite horizon MDPs. We show that an optimistic modification to value iteration achieves a regret bound of $\tilde{O}( \sqrt{HSAT} + H^2S^2A+H\sqrt{T})$ where $H$ is the time horizon, $S$ the number of states, $A$ the number of actions and $T$ the number of time-steps. This result improves over the best previous known bound $\tilde{O}(HS \sqrt{AT})$ achieved by the UCRL2 algorithm of Jaksch et al., 2010. The key significance of our new results is that when $T\geq H^3S^3A$ and $SA\geq H$, it leads to a regret of $\tilde{O}(\sqrt{HSAT})$ that matches the established lower bound of $\Omega(\sqrt{HSAT})$ up to a logarithmic factor. Our analysis contains two key insights. We use careful application of concentration inequalities to the optimal value function as a whole, rather than to the transitions probabilities (to improve scaling in $S$), and we define Bernstein-based "exploration bonuses" that use the empirical variance of the estimated values at the next states (to improve scaling in $H$).

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “, 2020a; Lattimore and Hutter, 2012) and minimizing regret via balancing exploration and exploitation (Zhang and Ji, 2019; Azar et al., 2017; Ortner, 2020; Talebi and Maillard, 2018; Efroni et al., 2020; Domingues et al., 2020b).”
Towards Continual Reinforcement Learning: A Review and Perspectives (2020, background): “This is because generic MDPs with no assumed structure have a minimax T -step regret bound of Ω( √ |S||A|T ) and sample complexity bound of Ω(|S||A|) (Jaksch et al., 2010; Azar et al., 2017), which implies that no proveable generalization to novel state and action pairs is possible in this setting.”
Dual Policy Iteration (2018, background): “We emphasize that at least, from a theoretical perspective, finding the optimal policy of the MDP with known cost function is as difficult as finding the optimal solution with unknown cost function, in terms of sample and computational complexity (Jaksch et al., 2010; Azar et al., 2017).”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, methodology): “05), against principled exploration strategies RLSVI [39], UCBVI [7], optimistic Q-learning (OQL) [23], BEB [24], Thompson sampling [38] and two variants of K-learning, one using the τt schedule (9) and the other using the optimal choice τ t from solving (10).”
Noisy Networks for Exploration (2017, background): “Various forms of this heuristic often come with theoretical guarantees on agent performance [2, 17, 15, 1, 16].”
Behaviour Suite for Reinforcement Learning (2019, background): “This literature has focused, for the most part, on bounding the scaling properties of particular algorithms in tabular MDPs through analysis [23, 48, 2].”
A Study on Overfitting in Deep Reinforcement Learning (2018, background): “…Cesa-Bianchi, 2012), for contextual bandits (Agarwal et al., 2014), contextual decision processes (Jiang et al., 2017) and RL (Jaksch et al., 2010; Azar et al., 2017), as well as Probably Approximately Correct (PAC) (Strehl et al., 2009; Lattimore & Hutter, 2014; Dann et al., 2017) guarantees are…”
Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learning (2017, background): “[16] in the S, A and T terms but not in H .”
Deep Exploration via Randomized Value Functions (2017, background): “Subsequent papers proposed and analyzed alternative tabular algorithms that carry out deep exploration with varying degrees of efficacy (Brafman and Tennenholtz, 2002; Auer and Ortner, 2006; Strehl et al., 2006; Jaksch et al., 2010; Osband et al., 2013; Dann and Brunskill, 2015; Azar et al., 2017).”
On Oracle-Efficient PAC RL with Rich Observations (2018, background): “[9] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos.”
Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition (2020, methodology): “In contrast, both UCBVI and vUCQ uses ÕpTS2Aq time and OpS2AHq space.”
On the Theory of Reinforcement Learning with Once-per-Episode Feedback (2021, methodology): “The minimax regret in the standard episodic reinforcement learning is O( √ H|S||A|N) [27, 4].”
On the Optimality of Sparse Model-Based Planning for Markov Decision Processes (2019, background): “…reinforcement learning, and understanding it is essential to tackling even more complex challenges such as sample-efﬁcient exploration (see e.g. Kakade et al. (2003); Strehl et al. (2006); Strehl (2007); Jaksch et al. (2010); Osband and Van Roy (2014); Azar et al. (2017); Sidford et al. (2018b,a)).”
Reward-Free Exploration for Reinforcement Learning (2020, methodology): “Thus, any RL algorithms with PAC or regret guarantees (Azar et al., 2017; Jin et al., 2018) can be used here to approximately find this optimal policy.”
Provably Efficient Maximum Entropy Exploration (2018, methodology): “PAC-RL Learning: For the case of tabular Markov decision processes, the balance of exploration and exploitation has been addressed in that there are a number of methods which utilize confidence based reward bonuses to encourage exploration in order to ultimately behave near optimally (Kearns & Singh”
Reinforcement Learning: Theory and Algorithms (2019, background): “This chapter follows the proof in [Azar et al., 2017], with a number of simplifications, albeit with a worse sample complexity.”
Is Q-learning Provably Efficient? (2018, methodology): “, [5]) an optimal policy π which gives the optimal value V ? h (x) = supπ V π h (x) for all x ∈ S and h ∈ [H].”
Regret Bounds for Kernel-Based Reinforcement Learning (2020, methodology): “By providing new high-probability confidence intervals for weighted sums and non-parametric kernel estimators, we generalize the techniques introduced by Azar et al. (2017) in tabular MDPs to the continuous setting.”
A Review of Safe Reinforcement Learning: Methods, Theories, and Applications (2024, neutral): “Forexample,[127]proposeamodel-basedsafeRLbylever-aginglagrangianoptimizationandCBFs;theyfurtherdeploy theirmethodinsimulationandreal-worldautonomousdriving experiments,theexperimentresultsindicatethattheirmethod can improve sample efﬁciency and ensure safety.”
Provably Efficient Exploration in Policy Optimization (2019, background): “Broadly speaking, our work is related to a vast body of work on value-based reinforcement learning in tabular (Jaksch et al., 2010; Osband et al., 2014; Osband & Van Roy, 2016; Azar et al., 2017; Dann et al., 2017; Strehl et al., 2006; Jin et al., 2018) and linear settings (Yang & Wang, 2019b;a; Jin”