This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Even-Dar, E. Articles by Mansour, Y.

Online Markov Decision Processes

Google Research, New York, New York 10011
Toyota Technological Institute, Chicago, Illinois 60637
School of Computer Science, Tel Aviv University, 69978 Tel Aviv, Israel
evendar{at}google.com
sham{at}tti-c.org
mansour{at}post.tau.ac.il

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.

Key Words: Markov decision process; no-regret algorithms
History: Received: August 16, 2006; revision received: September 29, 2008;