Near-optimal Regret Bounds for Reinforcement Learning

By Thomas Jaksch, Ronald Ortner, Peter Auer. 2008

1,579 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Electrical and Electronic Engineering, 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 Electrical and Electronic Engineering

In Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “Classical reinforcement learning (RL) with absolute reward feedback is a well-studied framework which is a sequential experience-driven learning process to optimize an accumulated long-term reward (Sutton and Barto, 2018; Auer et al., 2009; Singh et al., 2002).”
Surprising Negative Results for Generative Adversarial Tree Search (2018, methodology): “The regret analysis of MDPs (Jaksch et al., 2010; Bartlett & Tewari, 2009) is investigated, where the Optimism in the Face of Uncertainty ( OFU ) principle is applied to guarantee a high probability regret upper bound.”
Neural Approaches to Conversational AI (2018, neutral): “verse with a user, in the hope to discover a better policy in the long run; see, e.g., Daubigney et al. (2011). While exploration in ﬁnite-state RL is relatively well-understood (Strehl et al., 2009; Jaksch et al., 2010; Osband and Roy, 2017; Dann et al., 2017), exploration when parametric models li”
Unifying Count-Based Exploration and Intrinsic Motivation (2016, methodology): “There are near-optimal algorithms for multi-armed bandits (Bubeck and Cesa-Bianchi, 2012); the hardness of exploration in Markov Decision Processes (MDPs) is well-understood (Jaksch et al., 2010; Lattimore and Hutter, 2012).”
Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, methodology): “This can utilize explicit modeling of confidence sets, such as by maintaining upper and lower confidence bounds (Jaksch et al., 2010), or directly representing samples from the distribution over Q-functions, for example via bootstrap ensembles (Osband et al.”
Conservative Q-Learning for Offline Reinforcement Learning (2020, methodology): “Following [47, 26, 45], we use concentration properties of B̂π to control this error.”
Beyond Individual and Group Fairness (2020, background): “Furthermore, we know that (Jaksch et al. [2010]) for any sequence z1, z2, .”
Off-Policy Deep Reinforcement Learning without Exploration (2018, background): “In an on-policy setting, extrapolation error may be a source of beneficial exploration through an implicit “optimism in the face of uncertainty” strategy (Lai & Robbins, 1985; Jaksch et al., 2010).”
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.”
Algorithmic Framework for Model-based Deep Reinforcement Learning with Theoretical Guarantees (2018, methodology): “Another line of work of model-based reinforcement learning is to learn a dynamic model in a hidden representation space, which is especially necessary for pixel state spaces (Kakade et al., 2018; Dann et al., 2017; Szita & Szepesvári, 2010; Kearns & Singh, 2002; Jaksch et al., 2010).”
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).”
The Uncertainty Bellman Equation and Exploration (2017, background): “The exploration-bonus agent takes the action that maximizes (Q̂i +β log(t)ExplorationBonusi) (the log(t) term is required to achieve a regret bound (Jaksch et al., 2010), but doesn’t materially affect the previous argument) where β > 0 is a hyper-parameter chosen by a sweep and where Q̂i is the esti”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, methodology): “We can bound the contribution from unknown rewards w k (xkh) with a standard argument from earlier work (Buldygin & Kozachenko, 1980; Jaksch et al., 2010).”
Deep Exploration via Bootstrapped DQN (2016, methodology): “proposed for finite-armed bandits (Lai & Robbins, 1985), but the principle has been extended successfully across bandits with generalization (Rusmevichientong & Tsitsiklis, 2010) and tabular RL (Jaksch et al., 2010).”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, background): “and UCRL2 [21] but they did not perform much better than the dithering approaches and contributed to the clutter in the figure so we do not show them.”
COMBO: Conservative Offline Model-Based Policy Optimization (2021, methodology): “Following prior work [42, 19, 29], we assume: Assumption A1.”
Count-Based Exploration with Neural Density Models (2017, background): “From a theoretical perspective, exploration is now well-understood (e.g. Strehl & Littman, 2008; Jaksch et al., 2010; Osband et al., 2016), and Bayesian methods have been successfully demonstrated in a number of settings (Deisenroth & Rasmussen, 2011; Guez et al., 2012).”
Noisy Networks for Exploration (2017, background): “Various forms of this heuristic often come with theoretical guarantees on agent performance [2, 17, 15, 1, 16].”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “Reinforcement learning results with a flavor similar to those described in the previous sections can be found in [48, 105, 141, 172].”