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

Bruno Scherrer 1
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : We consider infinite-horizon $\gamma$-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 $\pi_1,\dots,\pi_k$ it implicitely generates until some iteration $k$. We provide performance bounds for non-stationary policies involving the last $m$ generated policies that reduce the state-of-the-art bound for the last stationary policy $\pi_k$ by a factor $\frac{1-\gamma}{1-\gamma^m}$. In particular, the use of non-stationary policies allows to reduce the usual asymptotic performance bounds of Value Iteration with errors bounded by $\epsilon$ at each iteration from $\frac{\gamma}{(1-\gamma)^2}\epsilon$ to $\frac{\gamma}{1-\gamma}\epsilon$, which is significant in the usual situation when $\gamma$ is close to $1$. Given Bellman operators that can only be computed with some error $\epsilon$, 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 $\frac{1}{1-\gamma}\epsilon$.
Type de document :
[Research Report] 2012
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

Contributeur : Bruno Scherrer <>
Soumis le : vendredi 30 mars 2012 - 16:39:29
Dernière modification le : mardi 18 décembre 2018 - 16:40:21
Document(s) archivé(s) le : mercredi 14 décembre 2016 - 19:11:48


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-00682172, version 2
  • ARXIV : 1203.5532



Bruno Scherrer. On the Use of Non-Stationary Policies for Infinite-Horizon Discounted Markov Decision Processes. [Research Report] 2012. 〈hal-00682172v2〉



Consultations de la notice


Téléchargements de fichiers