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.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

Contributor : Bruno Scherrer <>
Submitted on : Monday, June 3, 2013 - 2:47:00 PM
Last modification on : Tuesday, December 18, 2018 - 4:40:21 PM
Long-term archiving on : Tuesday, April 4, 2017 - 3:44:03 PM


Files produced by the author(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⟩



Record views


Files downloads