Mathematics of Operations Research · 2009 · 146 citations · 16 references
ComputingComputer ScienceAlgorithmsMarkov Decision ProcessesStochastic ProcessesMarkov ProcessesOnline AlgorithmsPolicy LearningReinforcement LearningReinforcement Learning FoundationsStochastic ControlFinite-horizon Decision MakingMarkov Decision ModelsState-space Structure
We consider a Markov decision process (MDP) setting in which the reward function is allowed to change after each time step (possibly in an adversarial manner), yet the dynamics remain fixed. Similar to the experts setting, we address the question of how well an agent can do when compared to the reward achieved under the best stationary policy over time. We provide efficient algorithms, which have regret bounds with no dependence on the size of state space. Instead, these bounds depend only on a certain horizon time of the process and logarithmically on the number of actions.
16
Reinforcement Learning: An Introduction
Richard S. Sutton, Andy Barto · IEEE Transactions on Neural Networks · 1998 · 27.1K citations
Reinforcement Learning: An Introduction
IEEE Transactions on Neural Networks · 2005 · 25.8K citations
The Weighted Majority Algorithm
N. Littlestone, Manfred K. Warmuth · Information and Computation · 1994 · 2K citations
Near-Optimal Reinforcement Learning in Polynomial Time
Michael Kearns, Satinder Singh · Machine Learning · 2002 · 858 citations · Full text