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 Citing Articles Citing Articles via HighWire Google Scholar Articles by Yu, J. Y. Articles by Shimkin, N.

Markov Decision Processes with Arbitrary Reward Processes

Department of Electrical and Computer Engineering, McGill University, Montréal, Québec H3A 2A7, Canada
Department of Electrical and Computer Engineering, McGill University, Montréal, Québec H3A 2A7, Canada, and Technion, Technion City, 32000 Haifa, Israel
Department of Electrical Engineering, Technion, Technion City, 32000 Haifa, Israel
jia.yu{at}mcgill.ca
shie.mannor{at}mcgill.ca
shimkin{at}ee.technion.ac.il

We consider a learning problem where the decision maker interacts with a standard Markov decision process, with the exception that the reward functions vary arbitrarily over time. We show that, against every possible realization of the reward process, the agent can perform as well—in hindsight—as every stationary policy. This generalizes the classical no-regret result for repeated games. Specifically, we present an efficient online algorithm—in the spirit of reinforcement learning—that ensures that the agent's average performance loss vanishes over time, provided that the environment is oblivious to the agent's actions. Moreover, it is possible to modify the basic algorithm to cope with instances where reward observations are limited to the agent's trajectory. We present further modifications that reduce the computational cost by using function approximation and that track the optimal policy through infrequent changes.

Key Words: Markov decision processes; online learning; no-regret algorithms
History: Received: August 22, 2007; revision received: December 2, 2008;

This article has been cited by other articles:

				E. Even-Dar, Sham. M. Kakade, and Y. Mansour Online Markov Decision Processes Mathematics of Operations Research, August 1, 2009; 34(3): 726 - 736. [Abstract] [PDF]