The Sample-Complexity of General Reinforcement Learning

By Tor Lattimore, Marcus Hutter, Peter Sunehag. 2013

73 citations recorded by the source corpus.

We present a new algorithm for general reinforcement learning where the true environment is known to belong to a finite class of N arbitrary models. The algorithm is shown to be near-optimal for all but O(N log2 N) timesteps with high probability. Infinite classes are also considered where we show that compactness is a key criterion for determining the existence of uniform sample-complexity bounds. A matching lower bound is given for the finite case.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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 Computational Theory and Mathematics

Citations in the corpus

Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning (2016, methodology): “Theorem 5 (Exact Recovery of The Optimal Policy) For any (cid:15) > 0 , δ ∈ (0 , 1) , let the SPD-dMDP Algorithm 1 iterate with the following sample size Let ˆ π be obtained by rounding the randomized policy ˆ π to the nearest deterministic policy, given by ˆ π ( i ) = argmax a ˆ λ a,i , i ∈ S .”
Noisy Networks for Exploration (2017, background): “Various forms of this heuristic often come with theoretical guarantees on agent performance [2, 17, 15, 1, 16].”
Generalization and Exploration via Randomized Value Functions (2014, background): “A recent paper [Lattimore et al., 2013] proposes a novel algorithm for the case where the true environment is known to belong to a finite or compact class of models, and shows that its sample complexity is polynomial in the cardinality of the model class if the model class is finite, or the…”
Deep Exploration via Randomized Value Functions (2017, background): “There is work on model learning algorithms [20, 21, 22, 8, 23, 24, 25, 26], which apply to specific model classes and become statistically or computationally intractable for problems of practical scale.”
Efficient Exploration and Value Function Generalization in Deterministic Systems (2013, background): “A recent paper [14] proposes a novel algorithm for the case where the true environment is known to belong to a finite or compact class of models, and shows that its sample complexity is polynomial in the cardinality of the model class if the model class is finite, or the ✏-covering-number if the”
Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements over Model-free Approaches (2018, background): “On the model-based side, Lattimore et al. (2013) and Osband and Van Roy (2014a) obtain sample complexity guarantees; the former makes no assumptions but the guarantee scales linearly with the model class size, and the latter makes continuity assumptions, so both results have more limited scope than…”
FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs (2020, background): “…as bounded Eluder dimension (Russo and Van Roy, 2013; Osband and Van Roy, 2014), (c) have sample complexity scaling linearly with the function class size (Lattimore et al., 2013; Ortner et al., 2014) or (d) are computationally intractable (Jiang et al., 2017; Sun et al., 2019; Dong et al., 2019).”
Regret Bounds for Kernel-Based Reinforcement Learning (2020, background): “[9] Tor Lattimore, Marcus Hutter, Peter Sunehag, et al.”
Extreme State Aggregation beyond MDPs (2014, methodology): “This would have to be done ﬁrst: either a PAC version of BLB by combining MERL [LHS13] with UCRL γ [LH12], or average reward versions of the bounds derived in this paper.”