Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds

By Andrea Zanette, Emma Brunskill. 2019

310 citations recorded by the source corpus.

Strong worst-case performance bounds for episodic reinforcement learning exist but fortunately in practice RL algorithms perform much better than such bounds would predict. Algorithms and theory that provide strong problem-dependent bounds could help illuminate the key features of what makes a RL problem hard and reduce the barrier to using RL algorithms in practice. As a step towards this we derive an algorithm for finite horizon discrete MDPs and associated analysis that both yields state-of-the art worst-case regret bounds in the dominant terms and yields substantially tighter bounds if the RL environment has small environmental norm, which is a function of the variance of the next-state value functions. An important benefit of our algorithmic is that it does not require apriori knowledge of a bound on the environmental norm. As a result of our analysis, we also help address an open learning theory question~\cite{jiang2018open} about episodic MDPs with a constant upper-bound on the sum of rewards, providing a regret bound with no $H$-dependence in the leading term that scales a polynomial function of the number of episodes.

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

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

In Statistical Learning Theory

Citations in the corpus

MOPO: Model-based Offline Policy Optimization (2020, background): “Uncertainty quantiﬁcation, a key ingredient to our approach, is critical to good performance in model-based RL both theoretically [62, 73, 43] and empirically [11, 6, 49, 38, 7], in optimal control [61, 2, 33].”
Learning When-to-Treat Policies (2019, background): “Intriguingly, related quantities (the expected temporal-difference error, and the variance of the value of next state) have been observed to play important roles in online reinforcement learning regret bounds (see, e.g., Zanette and Brunskill 2019) as well.”
A Kernel-Based Approach to Non-Stationary Reinforcement Learning in Metric Spaces (2020, background): “As a sanity-check, we note that in stationary MDPs, for which ∆ = 0 , we recover the regret bound of Kernel-UCBVI 7 (Domingues et al., 2020) , which is optimal for d = 1 in the (stationary) bandit case (Bubeck et al., 2011).”
Near-Optimal Offline Reinforcement Learning via Double Variance Reduction (2021, background): “Previous sample complexity bounds for RL has primarily focused on the online setting [Azar et al., 2017, Jin et al., 2018, Zanette and Brunskill, 2019, Simchowitz and Jamieson, 2019, Efroni et al., 2019, Cai et al., 2019] or the generative model (simulator) setting [Azar et al., 2013, Sidford et…”
On the Optimality of Sparse Model-Based Planning for Markov Decision Processes (2019, background): “For instance, the Bellman structure of variances in an MDP, observed in Azar et al. (2013) has subsequently formed a crucial component of minimax optimal exploration algorithms (Azar et al., 2017; Jin et al., 2018; Zanette and Brunskill, 2019; Wainwright, 2019).”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, background): “…al. (2014); Osband and Van Roy (2016); Azar et al. (2017); Dann et al. (2017); Agrawal and Jia (2017); Jin et al. (2018); Russo (2019); Rosenberg and Mansour (2019a,b); Jin and Luo (2019); Zanette and Brunskill (2019); Simchowitz and Jamieson (2019); Dong et al. (2019b) and the references therein.”
Regret Bounds for Kernel-Based Reinforcement Learning (2020, methodology): “Indeed, while modelbased algorithms (e.g., UCBVI by Azar et al., 2017 or EULER by Zanette & Brunskill, 2019) enjoy regret bounds that are first-order optimal, model-free algorithms (e.g., optimistic Q-Learning (OptQL) by (Jin et al., 2018)) are suboptimal by a factor √ H .”
Preference-based Reinforcement Learning with Finite-Time Guarantees (2020, methodology): “Using Hoeﬀding’s inequality and property of EULER we have that with probability 1 − δ/ 2 , for every state s we have”
Reward-Free Exploration for Reinforcement Learning (2020, methodology): “Therefore, we have replace the upper bound G 2 in (156) of Zanette and Brunskill [2019] by 4V ⋆ 1 (s1). This allows us also replace the G2 in Theorem 1 of Zanette and Brunskill [2019] by 4V ⋆ 1 (s1), which gives the regret of algorithm (note Zanette and Brunskill [2019] is for stationary MDP, while ”
Reinforcement Learning with Trajectory Feedback (2020, background): “…can be roughly divided into optimistic algorithms (Jaksch, Ortner, and Auer 2010; Azar, Osband, and Munos 2017; Jin et al. 2018; Dann et al. 2019; Zanette and Brunskill 2019; Simchowitz and Jamieson 2019; Efroni et al. 2019) and Thompson-Sampling (or Posterior-Sampling) based algorithms (Osband,…”
Provably Efficient Q-learning with Function Approximation via Distribution Shift Error Checking Oracle (2019, methodology): “In the tabular setting, previous work showed that under this assumption, one can obtain log T regret bound [28, 38].”
Ranking Policy Gradient (2019, background): “end if 18: end while and Brunskill, 2019).”
Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function (2019, background): “Recently, Kakade et al. [2018] and Zanette and Brunskill [2019] achieved the same regret bound of ˜ O ( √ SAHT ) by learning a precise value function to predict the best future reward of current state.”
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? (2020, background): “Jiang and Agarwal [2018] conjectured a linear dependence on the horizon, which is consistent with all existing upper bounds, which scale at least linearly with the planning horizon [Dann and Brunskill, 2015, Azar et al., 2017, Zanette and Brunskill, 2019] (see Section 3 for further discussion).”
Provable Self-Play Algorithms for Competitive Reinforcement Learning (2020, methodology): “We note Algorithm 4 use subroutine EULER, which is the algorithm presented in Zanette and Brunskill (2019).”
On the Theory of Reinforcement Learning with Once-per-Episode Feedback (2021, methodology): “As a subroutine Algorithm 2 uses the EULER algorithm (Zanette and Brunskill, 2019).”