hal-00758809, version 1

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

Bruno Scherrer (, ) 1, Boris Lesner () 1

NIPS 2012 - Neural Information Processing Systems (2012)

Résumé : 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''.

• Domaine : Informatique/Intelligence artificielle

• hal-00758809, version 1
• oai:hal.inria.fr:hal-00758809
• Contributeur :
• Soumis le : Jeudi 29 Novembre 2012, 13:31:31
• Dernière modification le : Mardi 4 Décembre 2012, 10:51:28