2013/06/06 by Bruno Scherrer, Matthieu Geist, Scherrer, Bruno +1 · 1 citation
Computer Science · #Artificial Intelligence (cs.AI) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Reinforcement Learning in Robotics #Robotics (cs.RO)
paper · pdf · doi:10.48550/arxiv.1306.1520
openalex publication_date 2013/06/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Local Policy Search is a popular reinforcement learning approach for handling large state spaces. Formally, it searches locally in a paramet erized policy space in order to maximize the associated value function averaged over some predefined distribution. It is probably commonly b elieved that the best one can hope in general from such an approach is to get a local optimum of this criterion. In this article, we show th e following surprising result: any (approximate) local optimum enjoys a global performance guarantee. We compare this g uarantee with the one that is satisfied by Direct Policy Iteration, an approximate dynamic programming algorithm that does some form of Poli cy Search: if the approximation error of Local Policy Search may generally be bigger (because local search requires to consider a space of s tochastic policies), we argue that the concentrability coefficient that appears in the performance bound is much nicer. Finally, we discuss several practical and theoretical consequences of our analysis.