Tight Performance Bounds for Approximate Modified Policy Iteration with Non-Stationary Policies

Boris Lesner 1 Bruno Scherrer 1
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : We consider approximate dynamic programming for the infinite-horizon stationary $\gamma$-discounted optimal control problem formalized by Markov Decision Processes. While in the exact case it is known that there always exists an optimal policy that is stationary, we show that when using value function approximation, looking for a non-stationary policy may lead to a better performance guarantee. We define a non-stationary variant of MPI that unifies a broad family of approximate DP algorithms of the literature. For this algorithm we provide an error propagation analysis in the form of a performance bound of the resulting policies that can improve the usual performance bound by a factor $O\left(1-\gamma\right)$, which is significant when the discount factor $\gamma$ is close to 1. Doing so, our approach unifies recent results for Value and Policy Iteration. Furthermore, we show, by constructing a specific deterministic MDP, that our performance guarantee is tight.
Type de document :
Pré-publication, Document de travail
2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00815996
Contributeur : Bruno Scherrer <>
Soumis le : vendredi 19 avril 2013 - 15:54:01
Dernière modification le : jeudi 11 janvier 2018 - 06:25:23
Document(s) archivé(s) le : lundi 3 avril 2017 - 07:56:17

Fichiers

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

Identifiants

  • HAL Id : hal-00815996, version 1
  • ARXIV : 1304.5610

Collections

Citation

Boris Lesner, Bruno Scherrer. Tight Performance Bounds for Approximate Modified Policy Iteration with Non-Stationary Policies. 2013. 〈hal-00815996〉

Partager

Métriques

Consultations de la notice

292

Téléchargements de fichiers

252