On Lower Bounds for Regret in Reinforcement Learning

By Ian Osband, Benjamin Van Roy. 2016

109 citations recorded by the source corpus.

This is a brief technical note to clarify the state of lower bounds on regret for reinforcement learning. In particular, this paper: - Reproduces a lower bound on regret for reinforcement learning, similar to the result of Theorem 5 in the journal UCRL2 paper (Jaksch et al 2010). - Clarifies that the proposed proof of Theorem 6 in the REGAL paper (Bartlett and Tewari 2009) does not hold using the standard techniques without further work. We suggest that this result should instead be considered a conjecture as it has no rigorous proof. - Suggests that the conjectured lower bound given by (Bartlett and Tewari 2009) is incorrect and, in fact, it is possible to improve the scaling of the upper bound to match the weaker lower bounds presented in this paper. We hope that this note serves to clarify existing results in the field of reinforcement learning and provides interesting motivation for future work.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research

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 Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, background): “Most of the existing work focus on the tabular setting; see e.g., Strehl et al. (2006); Jaksch et al. (2010); Osband et 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…”
Near-Optimal Model-Free Reinforcement Learning in Non-Stationary Episodic MDPs (2021, methodology): “The MDP within each segment is essentially similar to the hard instances constructed in Osband & Van Roy (2016); Jin et al. (2018).”
Variance Reduction Methods for Sublinear Reinforcement Learning (2018, background): “Optimal ). e The minimax lower bound on the regret is Ω( H T ) ([JOA10, OVR16]).”
Is Q-learning Provably Efficient? (2018, background): “The natural analogous notion of the diameter in the episodic setting is H , and thus this suggests a lower bound in Ω( √ HSAT ), as presented in [5, 20].”
Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound (2019, methodology): “In the tabular setting where S and A are ﬁnite sets, there exist algorithms that achieve asymptotic regret O ( |S||A| T ) (e.g. (Jaksch et al., 2010; Osband and Van Roy, 2016; Osband et al., 2017; Agrawal and Jia, 2017; Azar et al., 2017; Dann et al., 2018; Jin et al., 2018)), where T is the number…”
On the Theory of Reinforcement Learning with Once-per-Episode Feedback (2021, background): “The minimax regret in the standard episodic reinforcement learning is O( √ H|S||A|N) (Osband and Van Roy, 2016; Azar et al., 2017).”
Provable Self-Play Algorithms for Competitive Reinforcement Learning (2020, background): “Both of them (nearly) match the minimax lower bound Ω( √ H 2 SAT ) (Jaksch et al., 2010; Osband and Van Roy, 2016; Jin et al., 2018).”
Influence-Based Multi-Agent Exploration (2019, methodology): “Provably efﬁcient methods are proposed, such as upper conﬁdence bound (UCB) (Jaksch et al., 2010; Azar et al., 2017; Jin et al., 2018) and posterior sampling for reinforcement learning (PSRL) (Strens, 2000; Osband et al., 2013; Osband & Van Roy, 2016; Agrawal & Jia, 2017).”
Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning? (2020, background): “1 In particular, the ﬁrst term matches the lower bound Ω |S||A| ε up to logarithmic factors [Dann and Brunskill, 2015, Osband and Roy, 2016].”
Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning (2018, unknown): “See (Osband and Roy, 2016) for a more thorough discussion.”
Provably Efficient Reinforcement Learning with Linear Function Approximation (2019, background): “In the episodic setting with nonstationary dynamics and no “simulators,” the best regrets achieved by existing model-based and model-free algorithms are O ( √ H 2 SAT ) [8] and O ( √ H 3 SAT ) [21], respectively, both of which (nearly) attain the minimax lower bound Ω( √ H 2 SAT ) [19, 31, 21].”