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

1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : We consider infinite-horizon stationary $\gamma$-discounted Markov Decision Processes, for which it is known that there exists a stationary optimal policy. Using Value and Policy Iteration with some error $\epsilon$ at each iteration, it is well-known that one can compute stationary policies that are $\frac{2\gamma}{(1-\gamma)^2}\epsilon$-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 $\frac{2\gamma}{1-\gamma}\epsilon$-optimal, which constitutes a significant improvement in the usual situation when $\gamma$ 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''.
Type de document :
Communication dans un congrès
NIPS 2012 - Neural Information Processing Systems, Dec 2012, South Lake Tahoe, United States. 2012

https://hal.inria.fr/hal-00758809
Contributeur : Bruno Scherrer <>
Soumis le : jeudi 29 novembre 2012 - 13:31:31
Dernière modification le : mercredi 28 septembre 2016 - 11:00:57
Document(s) archivé(s) le : samedi 17 décembre 2016 - 17:48:15

### Fichiers

nips2012.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : hal-00758809, version 1
• ARXIV : 1211.6898

### Citation

Bruno Scherrer, Boris Lesner. On the Use of Non-Stationary Policies for Stationary Infinite-Horizon Markov Decision Processes. NIPS 2012 - Neural Information Processing Systems, Dec 2012, South Lake Tahoe, United States. 2012. <hal-00758809>

Consultations de
la notice

## 213

Téléchargements du document