On the Performance Bounds of some Policy Search Dynamic Programming Algorithms

Bruno Scherrer 1
1 MAIA - Autonomous intelligent machine
Inria Nancy - Grand Est, LORIA - AIS - Department of Complex Systems, Artificial Intelligence & Robotics
Abstract : We consider the infinite-horizon discounted optimal control problem formalized by Markov Decision Processes. We focus on Policy Search algorithms, that compute an approximately optimal policy by following the standard Policy Iteration (PI) scheme via an -approximate greedy operator (Kakade and Langford, 2002; Lazaric et al., 2010). We describe existing and a few new performance bounds for Direct Policy Iteration (DPI) (Lagoudakis and Parr, 2003; Fern et al., 2006; Lazaric et al., 2010) and Conservative Policy Iteration (CPI) (Kakade and Langford, 2002). By paying a particular attention to the concentrability constants involved in such guarantees, we notably argue that the guarantee of CPI is much better than that of DPI, but this comes at the cost of a relative--exponential in $\frac{1}{\epsilon}$-- increase of time complexity. We then describe an algorithm, Non-Stationary Direct Policy Iteration (NSDPI), that can either be seen as 1) a variation of Policy Search by Dynamic Programming by Bagnell et al. (2003) to the infinite horizon situation or 2) a simplified version of the Non-Stationary PI with growing period of Scherrer and Lesner (2012). We provide an analysis of this algorithm, that shows in particular that it enjoys the best of both worlds: its performance guarantee is similar to that of CPI, but within a time complexity similar to that of DPI.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

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

Contributeur : Bruno Scherrer <>
Soumis le : lundi 3 juin 2013 - 14:47:00
Dernière modification le : mardi 18 décembre 2018 - 16:40:21
Document(s) archivé(s) le : mardi 4 avril 2017 - 15:44:03


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


  • HAL Id : hal-00829559, version 1
  • ARXIV : 1306.0539



Bruno Scherrer. On the Performance Bounds of some Policy Search Dynamic Programming Algorithms. 2013. 〈hal-00829559〉



Consultations de la notice


Téléchargements de fichiers