Optimistic Linear Programming gives Logarithmic Regret for Irreducible MDPs

By Ambuj Tewari, Peter L. Bartlett. 2007

116 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Model-based reinforcement learning with parametrized physical models and optimism-driven exploration (2015, background): “In the case of linear dynamics or discrete systems, this optimistic exploration scheme has a number of desirable theoretical properties that make it a good choice [1], [3], [4], [7].”
Sample Complexity Bounds of Exploration (2012, background): “In particular, assuming irreducibility of the transition matrices, an asymptotically logarithmic regret is possible (Burnetas and Katehakis, 1997; Tewari and Bartlett, 2008): L A ( T ) ≤ C · ln T for some constant C .”
Optimism-driven exploration for nonlinear systems (2015, methodology): “The Bayesian optimistic local transitions algorithm [6] and the optimistic linear programming algorithm [7] apply the same principle to discrete MDPs, and recent results show regret bounds also based on this principle for”
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).”
REGAL: A Regularization based Algorithm for Reinforcement Learning in Weakly Communicating MDPs (2009, background): “Let V n(s) denote the maximum (over all policies, stationary or non-stationary) possible expected reward obtainable in n steps starting from s.”
Optimism in reinforcement learning and Kullback-Leibler divergence (2010, methodology): “A well-known approach to balance exploration and exploitation, followed for example by the well-know algorithm R-MAX [4], is the so-called optimism in the face of uncertainty principle.”
Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism (2020, background): “Starting from (Bur-netas & Katehakis, 1997; Tewari & Bartlett, 2008; Jaksch et al., 2010), a volume of works (see Section 3) have been”
Linearly Parameterized Bandits (2008, background): “le tunable heuristic, but do not provide any analysis on the regret or risk. Pandey et al. (2007) study bandit problems where the dependence of the arm rewards is represented by a hierarchical model. Tewari and Bartlett (2008) develop a policy that aims to maximize the average reward in an irreducib”
Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs (2018, unknown): “Subsequent studies by (Tewari and Bartlett, 2008), (Auer and Ortner, 2007), (Jaksch et al., 2010), and (Bartlett and Tewari, 2009) propose algorithms that maintain conﬁdence bounds on transition kernel deﬁned by L 1 or total variation norm.”
Thompson Sampling for Learning Parameterized Markov Decision Processes (2014, methodology): “The extension to problems with unknown rewards is well-known from here (Bartlett and Tewari, 2009; Tewari and Bartlett, 2008).”
Near-optimal Regret Bounds for Reinforcement Learning (2008, background): “This bound holds uniformly over time and under weaker assumptions: While [7] and [11] consider only ergodic MDPs in which any policy will reach every state after a sufficient number of steps, we make only the more natural assumption of a finite diameter.”
Optimistic posterior sampling for reinforcement learning: worst-case regret bounds (2022, unknown): “(b) (Tewari and Bartlett [2008], Theorem 4) The optimal gain λ∗ satisfies the following equations, λ∗ = min h∈RS max s,a rs,a + P T s,ah− hs = max a rs,a + P T s,ah ∗ − hs,∀s (1)”