Direct policy gradient methods for reinforcement learning and continuous control problems are a popular
approach for a variety of reasons: 
1) they are easy to implement without explicit knowledge of the underlying model;
2) they are an "end-to-end" approach, directly optimizing the performance metric of interest;
3) they inherently allow for richly parameterized policies.
 A notable drawback is that even in the most basic continuous control problem (that of linear quadratic regulators), these methods must solve a non-convex optimization problem, where little is understood about their efficiency from both computational and statistical perspectives. In contrast, system identification and model based planning in optimal control theory have a much more solid theoretical footing, where much is known with regards to their computational and statistical properties.   This work bridges this gap showing that (model free) policy gradient methods globally converge to the optimal solution and are efficient (polynomially so in relevant problem dependent quantities) with regards to their sample and computational complexities. Recent years have seen major advances in the control of uncertain dynamical systems using reinforcement learning and data-driven approaches; examples range from allowing robots to perform more sophisticated controls tasks such as robotic hand manipulation (Tassa et al., 2012; BID1 Kumar et al., 2016; Levine et al., 2016; Tobin et al., 2017; Rajeswaran et al., 2017a) , to sequential decision making in game domains, e.g. AlphaGo (Silver et al., 2016) and Atari game playing (Mnih et al., 2015) . Deep reinforcement learning (DeepRL) are becoming increasingly popular for tackling such challenging sequential decision making problems.Many of these successes have relied on sampling based reinforcement learning algorithms such as policy gradient methods, including the DeepRL approaches; here, there is little theoretical understanding of their efficiency, either from a statistical or a computational perspective. In contrast, control theory (optimal and adaptive control) has a rich body of tools, with provable guarantees, for related sequential decision making problems, particularly those that involve continuous control. These latter techniques are often model-based -they estimate an explicit dynamical model first (e.g. system identification) and then design optimal controllers. This work builds bridges between these two lines of work, namely, between optimal control theory and sample based reinforcement learning methods, using ideas from mathematical optimization. This work has provided provable guarantees that model-based gradient methods and model-free (sample based) policy gradient methods convergence to the globally optimal solution, with finite polynomial computational and sample complexities. Taken together, the results herein place these popular and practical policy gradient approaches on a firm theoretical footing, making them comparable to other principled approaches (e.g. subspace ID methods and algebraic iterative approaches).Finite C(K 0 ) assumption, noisy case, and finite horizon case. These methods allow for extensions to the noisy case and the finite horizon case. This work also made the assumption that C(K 0 ) is finite, which may not be easy to achieve in some infinite horizon problems. The simplest way to address this is to model the infinite horizon problem with a finite horizon one; the techniques developed in Section D.1 shows this is possible. This is an important direction for future work.Open Problems.• Variance reduction: This work only proved efficiency from a polynomial sample size perspective. An interesting future direction would be in how to rigorously combine variance reduction methods and model-based methods to further decrease the sample size.• A sample based Gauss-Newton approach: This work showed how the Gauss-Newton algorithm improves over even the natural policy gradient method, in the exact case. A practically relevant question for the Gauss-Newton method would be how to both: a) construct a sample based estimator b) extend this scheme to deal with (non-linear) parametric policies.• Robust control: In model based approaches, optimal control theory provides efficient procedures to deal with (bounded) model mis-specification. An important question is how to provably understand robustness in a model free setting.
This paper shows that model-free policy gradient methods can converge to the global optimal solution for non-convex linearized control problems.
{"src": "scitldr-AIC_train", "paper_id": "BJDEbngCZ"}