2009 · 239 citations · 18 references
ComputingComputer ScienceAlgorithmsArtificial IntelligenceMachine LearningExploration-exploitation TradeoffPolicy LearningReinforcement LearningReinforcement Learning FoundationsBayesian Reinforcement LearningExplorationExploration - Exploitation Trade-offExploration In Reinforcement LearningExploration-exploitation Trade-offReinforcement Learning TheorySample ComplexitySample Complexity Analysis
Reinforcement learning must balance exploration and exploitation, and while a Bayesian model‑based approach can theoretically solve this, it is computationally infeasible except in very limited cases. The paper introduces a simple algorithm that, with high probability, achieves ε‑close performance to the optimal Bayesian policy within a polynomial number of steps. The algorithm and its analysis build on the PAC‑MDP framework, extending its results to the Bayesian reinforcement learning setting. The method attains lower sample‑complexity bounds than prior algorithms while employing a much greedier exploration strategy than the cautious PAC‑MDP approach.
We consider the exploration/exploitation problem in reinforcement learning (RL). The Bayesian approach to model-based RL offers an elegant solution to this problem, by considering a distribution over possible models and acting to maximize expected reward; unfortunately, the Bayesian solution is intractable for all but very restricted cases. In this paper we present a simple algorithm, and prove that with high probability it is able to perform ε-close to the true (intractable) optimal Bayesian policy after some small (polynomial in quantities describing the system) number of time steps. The algorithm and analysis are motivated by the so-called PAC-MDP approach, and extend such results into the setting of Bayesian RL. In this setting, we show that we can achieve lower sample complexity bounds than existing algorithms, while using an exploration strategy that is much greedier than the (extremely cautious) exploration of PAC-MDP algorithms.
18
Near-Optimal Reinforcement Learning in Polynomial Time
Michael Kearns, Satinder Singh · Machine Learning · 2002 · 858 citations · Full text
Applied Physics Letters · 2000 · 528 citations · Full text