Logarithmic Online Regret Bounds for Undiscounted Reinforcement Learning

By Peter Auer, Ronald Ortner. 2006

272 citations recorded by the source corpus.

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

Safe Policy Improvement with Baseline Bootstrapping (2017, methodology): “In an online learning setting, algorithms based on OFU, such as R-MAX or UCRL, are provably efficient, because a good outcome brings a policy improvement, and even an error leads to learning not to do it again at a lesser cost [5, 2].”
Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning (2016, neutral): “…learning, many methods have been developed and some of them are proved to achieve near-optimal performance guarantees in certain senses; recent examples including (Ortner and Auer, 2007; Dann and Brunskill, 2015; Lattimore et al., 2013; Lattimore and Hutter, 2012; Chen and Wang, 2016).”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, background): “uality such as Hoeffding’s lemma, and then searching over the space of transition functions within some conﬁdence set for the one that gives the largest value function. The algorithms UCRL and UCRL2 (Auer and Ortner, 2006; Jaksch et al., 2010) fall into this category for the MDP case, and UCB1 for t”
Noisy Networks for Exploration (2017, background): “References [1] Peter Auer and Ronald Ortner.”
PAC Bounds for Discounted MDPs (2012, methodology): “We modify ucrl2 of Auer and Ortner (2010) to a new algorithm, ucrlγ, given below.”
Generalization and Exploration via Randomized Value Functions (2014, background): “To make efficient use of data and computational resources, the agent must generalize from observations and select actions that strike a balance between exploitation of current knowledge to maximize near-term rewards and exploration to acquire new information that can improve long-term prospects.”
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).”
Optimism in reinforcement learning and Kullback-Leibler divergence (2010, background): “The subsequent works [2, 9, 3] introduced algorithms that guarantee non-asymptotic logarithmic regret in a large class of MDPs.”
Transfer Reinforcement Learning with Shared Dynamics (2017, methodology): “In order to guide the exploration, we adopt the well-known heuristic, which can be found in Prioritized Sweeping (Moore and Atkeson 1993), R-MAX (Brafman and Tennenholtz 2002), UCRL (Auer and Ortner 2007), and VIME (Houthooft et al. 2016).”
REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs (2009, methodology): “, 2006, Auer and Ortner, 2007, Tewari and Bartlett, 2008, Auer et al., 2009a]. These efforts improved the S and A dependence of their bounds, investigated lower bounds and explored other ways to study the exploration vs. exploitation trade-off. The results of Auer and Ortner [2007] and Tewari and Ba”
Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds (2019, background): “• Bounds that depend on MDP mixing: (Auer & Ortner, 2006; Talebi & Maillard, 2018) have bounds on the mix- ing time but hold for MDPs that are unichain or ergodic.”
Regret Bounds for Reinforcement Learning via Markov Chain Concentration (2018, methodology): “The mixing time parameter in our bounds is different from the transition parameters in the regret bounds of [2, 13] or the bias span used in [7, 11].”
Reinforcement Learning of POMDPs using Spectral Methods (2016, methodology): “, 2011), linear quadratic control (Abbasi-Yadkori and Szepesvári, 2011), and reinforcement learning (Ortner and Auer, 2007; Jaksch et al., 2010).”
Near-Bayesian exploration in polynomial time (2009, unknown): “An alternative means of analyzing the e.ciency of reinforcement learning algorithms is the notion of regret in in.nite-horizon settings (Auer & Ortner, 2007), and it remains an open question whether the ideas we present here can be extended to this in.nite-horizon case.”
A Bayesian Approach for Learning and Planning in Partially Observable Markov Decision Processes (2011, background): “…performance with high probability using only a polynomial number of steps (Kearns and Singh, 1998; Brafman and Tennenholtz, 2003; Strehl and Littman, 2005), or alternately to have small regret with respect to the optimal policy (Auer and Ortner, 2006; Tewari and Bartlett, 2008; Auer et al., 2009).”
Optimistic Linear Programming gives Logarithmic Regret for Irreducible MDPs (2007, background): “The following constant is defined just for comparison with results in [2].”
Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs (2018, methodology): “To analyze the under-sampled regime, where some state-action pair is not sufficiently sampled, we borrow some techniques from (Auer and Ortner, 2007).”