On the Sample Complexity of Reinforcement Learning with a Generative Model

By Mohammad Gheshlaghi Azar, R´emi Munos, Hilbert J. Kappen. 2012

158 citations recorded by the source corpus.

We consider the problem of learning the optimal action-value function in the discounted-reward Markov decision processes (MDPs). We prove a new PAC bound on the sample-complexity of model-based value iteration algorithm in the presence of the generative model, which indicates that for an MDP with N state-action pairs and the discount factor γ ∈ [0, 1) only O(N log(N/δ)/(1 - γ)3e2)) samples are required to find an e-optimal estimation of the action-value function with the probability 1 - δ. We also prove a matching lower bound of Θ(N log(N/δ)/((1 - γ)3e2)) on the sample complexity of estimating the optimal action-value function by every RL algorithm. To the best of our knowledge, this is the first matching result on the sample complexity of estimating the optimal (action-) value function in which the upper bound matches the lower bound of RL in terms of N, e, δ and 1/(1-γ). Also, both our lower bound and our upper bound significantly improve on the state-of-the-art in terms of 1/(1 - γ).

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): “Over the years, several works have addressed RL in terms of both 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…”
The Uncertainty Bellman Equation and Exploration (2017, neutral): “, the uncertainty due to estimating a parameter using a finite amount of data, rather than the higher moments of the reward-to-go (Lattimore & Hutter, 2012; Azar et al., 2012; Mannor & Tsitsiklis, 2011; Bellemare et al., 2017).”
Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning (2016, methodology): “Azar et al. (2012) showed that the model-based value iteration achieves the optimal rate O |S×A| log( |S×A| /δ ) (1 γ ) 3 (cid:15) 2 for discounted MDP. (cid:16) (cid:17) Dann and Brunskill (2015) developed a upper conﬁdence method for ﬁxed-horizon MDP and obtain a near-optimal rate O S 2 AH 2…”
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, background): “Our work builds on recent work [6, 8] on PAC infinite horizon discounted RL that offers much tighter upper and lower sample complexity bounds than was previously known.”
On the Optimality of Sparse Model-Based Planning for Markov Decision Processes (2019, methodology): “On a more technical note, our analysis is based on a novel absorbing MDP construction to deal with the dependence issues which arise in the analysis of Azar et al. (2012, 2013), and this argument might be more broadly useful.”
Provably Efficient Reinforcement Learning with Linear Function Approximation (2019, background): “The “simulator” signiﬁcantly alleviates the difﬁculty of exploration, since a naive exploration strategy which queries all state-action pairs uniformly at random already leads to the most efﬁcient algorithm for ﬁnding an optimal policy [7].”
Optimality and Approximation with Policy Gradient Methods in Markov Decision Processes (2019, result): “Note that this dimension-free rate does not contradict the lower bounds on sample complexity of RL [Azar et al., 2013], since we assume exact gradient evaluations.”
Combating the Compounding-Error Problem with a Multi-step Model (2019, background): “ to enable sample-efﬁcient learning [Sutton, 1990; Deisenroth and Rasmussen, 2011; Levine and Abbeel, 2014]. This advantage is well-understood in theory in settings such as value-function estimation [Azar et al., 2012], exploration in discounted and ﬁnite-horizon Markov decision processes (MDPs) [Sz”
Preference-based Reinforcement Learning with Finite-Time Guarantees (2020, background): “Although value-based RL with a simulator has been well-studied in the literature [3, 4], methods like value iteration cannot easily extend to PbRL, because the reward values are hidden.”
Is Q-learning Provably Efficient? (2018, methodology): “pairs uniformly at random already leads to the most efficient algorithm for finding optimal policy [3].”
A Review of Safe Reinforcement Learning: Methods, Theory and Applications (2022, background): “Lower bound [150] [18] Ω̃ ( |S | |A | (1 − γ)3 ε 2 )”
Provably Efficient Exploration in Policy Optimization (2019, background): “Meanwhile, theoretically, vanilla policy gradient can be shown to suﬀer from exponentially large variance in the well-known “combination lock” setting (Kakade, 2003; Leﬄer et al., 2007; Azar et al., 2012a), which only has a ﬁnite state space.”
Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited (2020, background): “A lower bound of the same order is provided by Azar et al. (2012) for the number of steps algorithms that have access to a generative model need to identify an ε-optimal policy. PAC-MDP algorithms in the episodic setting were later studied by Dann and Brunskill (2015), who also provide a lower bound”
Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds (2019, background): “(271) See for example (Azar et al., 2012) for a proof equivalent to this.”