The Sample-Complexity of General Reinforcement Learning

Abstract

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 log^2 N) time-steps 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.

16 pages

References in corpus (2)

• On the Sample Complexity of Reinforcement Learning with a Generative Model
• Optimal Regret Bounds for Selecting the State Representation in Reinforcement Learning

Cited by in corpus (11)

• Noisy Networks for Exploration
• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• Generalization and Exploration via Randomized Value Functions
• Sample Complexity of Multi-task Reinforcement Learning
• Online Stochastic Optimization under Correlated Bandit Feedback
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Zooming for Efficient Model-Free Reinforcement Learning in Metric Spaces
• Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning
• Asynchronous Optimization over Weakly Coupled Renewal Systems
• Reinforcement Learning in Factored Action Spaces using Tensor Decompositions
• Efficient Reinforcement Learning in Deterministic Systems with Value Function Generalization