Policy Search: Any Local Optimum Enjoys a Global Performance Guarantee
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: \emph{any} (approximate) \emph{local optimum} enjoys a \emph{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.
Code (0)
등록된 구현이 없습니다.
Tasks
Reinforcement LearningSimilar Papers 제목 키워드 기반
Variance-Reduced Conservative Policy Iteration
We study the sample complexity of reducing reinforcement learning to a sequence of empirical risk minimization problems over the policy space. Such reductions-based algorithms exhibit local convergence in the function sp…
reinforcement-learningReinforcement Learning (RL)Global optimization of expensive black-box models based on asynchronous hybrid-criterion with interval reduction
In this paper, a new sequential surrogate-based optimization (SSBO) algorithm is developed, which aims to improve the global search ability and local search efficiency for the global optimization of expensive black-box m…
global-optimizationCan We Find Nash Equilibria at a Linear Rate in Markov Games?
We study decentralized learning in two-player zero-sum discounted Markov games where the goal is to design a policy optimization algorithm for either agent satisfying two properties. First, the player does not need to kn…
Probabilistic Saliency Estimation
In this paper, we model the salient object detection problem under a probabilistic framework encoding the boundary connectivity saliency cue and smoothness constraints in an optimization problem. We show that this proble…
Objectobject-detectionObject DetectionOne-Class Classification+3High-dimensional Bayesian Optimization via Covariance Matrix Adaptation Strategy
Bayesian Optimization (BO) is an effective method for finding the global optimum of expensive black-box functions. However, it is well known that applying BO to high-dimensional optimization problems is challenging. To a…
Bayesian Optimization