On the Use of Non-Stationary Policies for Stationary Infinite-Horizon Markov Decision Processes

preprint2012arXivOpen access

Abstract

We consider infinite-horizon stationary γγ-discounted Markov Decision Processes, for which it is known that there exists a stationary optimal policy. Using Value and Policy Iteration with some error εε at each iteration, it is well-known that one can compute stationary policies that are 2γ(1−γ)2ε\frac{2γ}{(1-γ)^2}ε-optimal. After arguing that this guarantee is tight, we develop variations of Value and Policy Iteration for computing non-stationary policies that can be up to 2γ1−γε\frac{2γ}{1-γ}ε-optimal, which constitutes a significant improvement in the usual situation when γγ is close to 1. Surprisingly, this shows that the problem of "computing near-optimal non-stationary policies" is much simpler than that of "computing near-optimal stationary policies".

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.