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

preprint2012arXivOpen access

Abstract

We consider infinite-horizon γγ-discounted Markov Decision Processes, for which it is known that there exists a stationary optimal policy. We consider the algorithm Value Iteration and the sequence of policies π1,...,πkπ_1,...,π_k it implicitely generates until some iteration kk. We provide performance bounds for non-stationary policies involving the last mm generated policies that reduce the state-of-the-art bound for the last stationary policy πkπ_k by a factor 1−γ1−γm\frac{1-γ}{1-γ^m}. In particular, the use of non-stationary policies allows to reduce the usual asymptotic performance bounds of Value Iteration with errors bounded by εε at each iteration from γ(1−γ)2ε\fracγ{(1-γ)^2}ε to γ1−γε\fracγ{1-γ}ε, which is significant in the usual situation when γγ is close to 1. Given Bellman operators that can only be computed with some error εε, a surprising consequence of this result is that the problem of "computing an approximately optimal non-stationary policy" is much simpler than that of "computing an approximately optimal stationary policy", and even slightly simpler than that of "approximately computing the value of some fixed policy", since this last problem only has a guarantee of 11−γε\frac{1}{1-γ}ε.

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.