arXiv (Cornell University) · 2012 · 27 citations · 15 references
ComputingComputer ScienceAlgorithmsArtificial IntelligenceMarkov Decision ProcessesExploration-exploitation TradeoffHeuristic SearchPolicy LearningReinforcement LearningReinforcement Learning FoundationsBayesian Reinforcement LearningComplexityExploration - Exploitation Trade-offExploration-exploitation Trade-offHeuristic AlgorithmsHeuristic ApproachSample ComplexitySample Complexity Analysis
Model-based Bayesian Reinforcement Learning (BRL) allows a found formalization of the problem of acting optimally while facing an unknown environment, i.e., avoiding the exploration-exploitation dilemma. However, algorithms explicitly addressing BRL suffer from such a combinatorial explosion that a large body of work relies on heuristic algorithms. This paper introduces BOLT, a simple and (almost) deterministic heuristic algorithm for BRL which is optimistic about the transition function. We analyze BOLT's sample complexity, and show that under certain parameters, the algorithm is near-optimal in the Bayesian sense with high probability. Then, experimental results highlight the key differences of this method compared to previous work.
15
Reinforcement Learning: An Introduction
IEEE Transactions on Neural Networks · 2005 · 25.8K citations
Leslie G. Valiant · 1984 · 4.2K citations
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