On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control

Reinforcement learning is a framework for interactive decision-making with\nincentives sequentially revealed across time without a system dynamics model.\nDue to its scaling to continuous spaces, we focus on policy search where one\niteratively improves a parameterized policy with stochastic policy gradient\n(PG) updates. In tabular Markov Decision Problems (MDPs), under persistent\nexploration and suitable parameterization, global optimality may be obtained.\nBy contrast, in continuous space, the non-convexity poses a pathological\nchallenge as evidenced by existing convergence results being mostly limited to\nstationarity or arbitrary local extrema. To close this gap, we step towards\npersistent exploration in continuous space through policy parameterizations\ndefined by distributions of heavier tails defined by tail-index parameter\nalpha, which increases the likelihood of jumping in state space. Doing so\ninvalidates smoothness conditions of the score function common to PG. Thus, we\nestablish how the convergence rate to stationarity depends on the policy's tail\nindex alpha, a Holder continuity parameter, integrability conditions, and an\nexploration tolerance parameter introduced here for the first time. Further, we\ncharacterize the dependence of the set of local maxima on the tail index\nthrough an exit and transition time analysis of a suitably defined Markov\nchain, identifying that policies associated with Levy Processes of a heavier\ntail converge to wider peaks. This phenomenon yields improved stability to\nperturbations in supervised learning, which we corroborate also manifests in\nimproved performance of policy search, especially when myopic and farsighted\nincentives are misaligned.\n