We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Markov Decision Processes with Arbitrary Reward Processes.
- Authors
Jia Yuan Yu; Mannor, Shie; Shimkin, Nahum
- Abstract
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.
- Subjects
MARKOV processes; GAME theory; MATHEMATICAL functions; ALGORITHMS; APPROXIMATION theory
- Publication
Mathematics of Operations Research, 2009, Vol 34, Issue 3, p737
- ISSN
0364-765X
- Publication type
Article
- DOI
10.1287/moor.1090.0397