PAC Bounds for Discounted MDPs

By Tor Lattimore, Marcus Hutter. 2012

198 citations recorded by the source corpus.

We study upper and lower bounds on the sample-complexity of learning near-optimal behaviour in finite-state discounted Markov Decision Processes (mdps). We prove a new bound for a modified version of Upper Confidence Reinforcement Learning (ucrl) with only cubic dependence on the horizon. The bound is unimprovable in all parameters except the size of the state/action space, where it depends linearly on the number of non-zero transition probabilities. The lower bound strengthens previous work by being both more general (it applies to all policies) and tighter. The upper and lower bounds match up to logarithmic factors provided the transition matrix is not too dense.

Subfields: Artificial Intelligence, 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 Management Science and Operations Research

In Reinforcement Learning

Citations in the corpus

Dueling RL: Reinforcement Learning with Trajectory Preferences (2021, background): “…the optimal sample complexity for finding the best policy (Azar et al., 2013; Dann and Brunskill, 2015; Dann et al., 2017; Domingues et al., 2020a; Lattimore and Hutter, 2012) and minimizing regret via balancing exploration and exploitation (Zhang and Ji, 2019; Azar et al., 2017; Ortner, 2020;…”
Unifying Count-Based Exploration and Intrinsic Motivation (2016, background): “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).”
The Uncertainty Bellman Equation and Exploration (2017, background): “Unlike most prior work, we focus upon the epistemic uncertainty over the mean of the value function, rather than the higher moments of the reward-to-go [16, 1, 18].”
Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning (2016, methodology): “• Upper conﬁdence methods maintain and update a value or interval for each state-action-state triplet; see the works by Lattimore and Hutter (2012), Dann and Brunskill (2015).”
Why is Posterior Sampling Better than Optimism for Reinforcement Learning? (2016, methodology): “A very similar observation is used by recent analyses in the sample complexity setting [18] and also ﬁnite horizon MDPs [8].”
Variational Bayesian Reinforcement Learning with Regret Bounds (2018, background): “orithms UCRL and UCRL2 [8, 36] fall into this category for the MDP case, and UCB1 for the bandit case [6]. Various extensions that obtain better regret bounds exist and are an active area of research [10, 45]. In the Bayesian case the optimal policy can be formulated using belief states , but this i”
Implicit Quantile Networks for Distributional Reinforcement Learning (2018, methodology): “This change in perspective has yielded new insights into the dynamics of RL (Azar et al., 2012), and been a useful tool for analysis (Lattimore & Hutter, 2012).”
A Distributional Perspective on Reinforcement Learning (2017, background): “…1982; White, 1988), in reinforcement learning it has thus far been subordinated to speciﬁc purposes: to model parametric uncertainty (Dearden et al., 1998), to design risk-sensitive algorithms (Morimura et al., 2010b;a), or for theoretical analysis (Azar et al., 2012; Lattimore & Hutter, 2012).”
Sample Complexity of Episodic Fixed-Horizon Reinforcement Learning (2015, methodology): “We therefore follow existing sample complexity analyses [6, 7] and assume known rewards for simplicity.”
Minimax Regret Bounds for Reinforcement Learning (2017, background): “Previous works have argue for the potential benefits of such PSRL methods over existing optimistic approaches (Osband et al., 2013; Osband & Van Roy, 2016b) but they come with guarantees on the Bayesian regret only. However a very recent work Agrawal & Jia (2017) have shown that an optimistic versio”
Safe Reinforcement Learning (2015, methodology): “For example, a recent PAC RL algorithm requires approximately 1017 time steps to guarantee that the policy for a gridworld similar to the one we described in Section 2.5 is probably approximately correct (Lattimore and Hutter, 2012).”
Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism (2021, methodology): “We adopt the following construction of the hard MDP instance from the work [85].”
Invariant Causal Prediction for Block MDPs (2020, methodology): “Lattimore and Hutter (2012) offers lower and upper bounds on the sample complexity of learning near-optimal behavior in MDPs by modifying the Upper Conﬁ-dence RL (UCRL) algorithm (Jaksch et al., 2010).”
PAC-inspired Option Discovery in Lifelong Reinforcement Learning (2014, background): “For instance, an interesting observation in Lattimore & Hutter (2012) is that one can use variance information in empirical Bernstein inequalities to get a sharper bound on the speed of model parameter concentration.”
Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function (2019, methodology): “UCB algorithm with Bernstein bound [Lattimore and Hutter, 2012] provides a near optimal regret bound.”
Provably efficient RL with Rich Observations via Latent State Decoding (2019, unknown): “…methods are difﬁcult to adapt to rich observation spaces, because they all require a number of interactions polynomial in the number of observed states , and, without additional structural assumptions, such a dependency is unavoidable (see, e.g., Jaksch et al., 2010; Lattimore & Hutter, 2012).”