2008 · 174 citations · 22 references
BusinessMathematicsAlgorithmsMarkov Decision ProcessesStochastic ProcessesReinforcement LearningStochastic ControlReinforcement Learning Theory
For undiscounted reinforcement learning we consider the total regret of a learning algorithm in respect to an optimal policy. We present a reinforcement learning algorithm with total regret Õ DS √) AT after T steps for any unknown Markov decision process (MDP) with S states, A actions per state, and diameter D. The diameter of an MDP is at most D if for any pair of states s1, s2 there is a policy which moves from s1 to s2 in at most D steps (on average). Our upper bound holds with high probability and it can be converted into a logarithmic regret bound, if a xed di erence between the average reward of the optimal policy and the second optimal policy is assumed. We also present a corresponding lower bound Ω any learning algorithm. ( √DSAT) on the worst case total regret of
22
Reinforcement Learning: An Introduction
IEEE Transactions on Neural Networks · 2005 · 25.8K citations
The Nonstochastic Multiarmed Bandit Problem
Peter Auer, Nicolò Cesa‐Bianchi, Yoav Freund et al. · SIAM Journal on Computing · 2002 · 2.3K citations
Kybernetes · 1998 · 1.6K citations