{'fraction_non_alphanumeric': 0.03823319876513892, 'fraction_numerical': 0.013061030634053668, 'mean_word_length': 4.188725741862614, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 19, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A homotopic approach to policy gradients for linear quadratic regulators with nonlinear controls

We study the convergence of deterministic policy gradient algorithms in continuous state and action space for the prototypical Linear Quadratic Regulator (LQR) problem when the search space is not limited to the family of linear policies. We first provide a counterexample showing that extending the policy class to piecewise linear functions results in local minima of the policy gradient algorithm. To solve this problem, we develop a new approach that involves sequentially increasing a discount factor between iterations of the original policy gradient algorithm. We finally prove that this homotopic variant of policy gradient methods converges to the global optimum of the undiscounted Linear Quadratic Regulator problem for a large class of Lipschitz, non-linear policies.


INTRODUCTION
Recent advances in machine learning have strongly depended on techniques from reinforcement learning to generate their superhuman results on tasks that were previously deemed "unachievable" by artificial intelligence models. Some of the most spectacular examples are the recent breakthroughs in the games of Go and Starcraft 2 [24,25,31] and the robotics tasks such as learning how to walk or controlling a hand [12,21].
A shared aspect of these recent advances is the use of policy gradient algorithms (and their variants) [28]. Given the simplicity of these algorithms, their success in solving non-convex optimization problems is rather surprising. In the past few years, there has been significant progress made in the development of our understanding of the convergence of these algorithms -especially in the tabular setting [13,19]. However, many of the games and control problems mentioned in the first paragraph have incredibly large (or infinite in the case of robotics) state and action spaces, so that tabular representation is computationally prohibitive. Due to this complexity, none of the above breakthroughs would have been possible without the use of nonlinear function approximation -most commonly, (deep) neural networks -in combination with policy gradient algorithms: With parametric function approximation, only the parameters of the approximator need to be stored rather than a table of all possible game-states.
Nevertheless, the current body of theoretical work still does not explain the success policy gradient methods have experienced in Go and Starcraft 2 due to an insufficient understanding of how such methods behave when neural networks are used as the function approximator of choice. One obstruction in this sense stems from the nonlinear behavior of neural networks, resulting in optimization landscapes that are highly non-convex [10], preventing us from using many of the tools developed in classical optimization theory. This large gap between empirical success and theory of nonlinear function approximation in reinforcement learning algorithms is also related to our limited theoretical understanding of their interplay. In this paper, we contribute to filling this gap by proving convergence results for nonlinear deterministic policies in a prototypical control problem with continuous state and action space: the Linear Quadratic Regulator (LQR) problem. In previous work by [4,6,8,33], global convergence results have been obtained in this context by restricting to the linear policy class. This choice of search space favorably aligns with the policy gradient update since the optimal policy of the LQR is known to be a linear function of the state. Our work extends these results to a larger class of non-linear policies. To do so, we first construct an example to demonstrate the potential for negative interplay between the expressiveness of the policy class and the local nature of the policy gradient algorithm. We then consider a new perspective in solving reinforcement learning problems that involves iteratively updating a discount factor. With this perspective, we reduce the global convergence problem to a local one, allowing us to work with a wider policy class and to avoid potential local minima. These stronger convergence results do not come without a cost, though; the process of iteratively updating a discount factor necessarily results in more training iterations.

Related Works.
In light of the advantages provided by policy-based approaches to reinforcement learning, there has been a recent wave of research seeking to provide theoretical guarantees for these algorithms that have been shown to work in practice.
Most of the recent work on the convergence of policy gradient methods focuses on the finite action space setting. In this context, [18] has shown that, in finite action spaces, algorithms like TRPO [22] and PPO [23] converge to the globally optimal policy. More results on the global convergence of policy gradient dynamics and extensions to function approximation are obtained in [1,17,19,32]. However, in the aforementioned publications, the assumption of a finite action space is essential in obtaining the results; when considering continuous action spaces, we use the LQR as a proxy for more general environments since the LQR setting is well understood and allows for more straightforward analysis.
In the continuous action-space setting, [8] show that deterministic policy gradient methods for the policy class of linear policies converge to the globally optimal policy of the LQR problem. Building off of [8], [6] provides strong positive results in an explicit characterization of the LQR when learning with linear policies showing that the cost is smooth and coercive and that the discretization of various gradient flows lead to algorithms with linear convergence rates. Similarly, [33] provides a convergence guarantee for Actor-Critic methods in the LQR setting by considering the class of linear-Gaussian policies with fixed variance. Other recent work [14] also considers the class of linear policies but works in the finite time-horizon setting. Rather than working with a more complex learning task such as the finite-horizon LQR, our work instead tackles the problem of nonlinear function approximation and thus we prove our results in the simpler setting of the infinite-horizon, noiseless LQR; however, unlike previous work in this setting, we consider a wider (deterministic) policy class that can be understood as linear combinations of nonlinear functions. Furthermore, most works only consider the evolution of the policy with respect to time/iterations; we also consider the evolution of the optimal policy with respect to the discount factor. This new perspective allows us to use some new tools in proving the convergence of policy gradient methods in the LQR.
Most relevant to our work, [9] discusses the effect of changing the dscount factor during training of reinforcement learning algorithms. This study, although strictly empirical, shows that our homotopic variant of policy gradient methods can reduce the number of training iterations needed to learn an optimal policy, i.e., that this modified reinforcement learning procedure not only improves the optimality properties of reinforcement learning algorithms but also their convergence speed. On the theoretical side, a team at DeepMind [29] has studied how the value function behaves as function of the discount factor and develop a set of interpolating objectives to go from a myopic value function V γ to the true objective V γ * ; they also show that their family of interpolating objectives yields faster convergence and better asymptotic performance on MuJoCo tasks.

Contributions.
Our work continues along a line of work using the LQR as a proxy for more general learning environments [3,5,7,8,11,[14][15][16]30]. In this paper, we present a homotopy-based approach inspired by the human learning process to iteratively update the policy until reaching the globally optimal policy, and in particular, we directly extend the result of [8] to nonlinear policy classes. We show that by continuously updating the discount factor after policy improvements, one can reach the global optimum regardless of the quality of the initial policy, subject to a few assumptions on the parametrization and expressiveness of the policy (e.g., our policy parametrization is linear in the parameters). Although this approach can be understood as a new type of policy-gradient algorithm, our focus is theoretical and we mainly consider the homotopy approach as a tool to prove convergence results.
The intuition behind the homotopy-based algorithm comes from the observation that when teaching children, one does not expect the child to consider the long term consequences of their actions. Instead, children are first taught to learn the basics (i.e., learn with a discount factor close to zero) before moving on to developing their long-term planning ability (increasing to a larger discount factor). Heuristically, one can make sense of this by reasoning that it's likely easier to learn the optimal policy having learned the basics than it is learning it from scratch. Mathematically, the homotopy approach relies on the fact that the optimal policy of the LQR is continuous with respect to the discount factor. In more challenging environments such as Chess or Go, this may not be the case.
Summarizing, the main contributions of this work are as follows: • We show that one can not always expect policy gradient methods to converge even with relatively well-behaved function approximators. We provide an example policy that is linear in the parameters, contains the globally optimal policy, but does not converge to such globally optimal policy when trained with a fixed discount factor. Furthermore, this example satisfies all assumptions needed for our convergence result. • We formulate the policy gradient learning process as a homotopy between various optimal policies along the discount factor. By leveraging this idea, we provide a convergence result for an expanded policy class consisting of linear combinations of non-linear functions (in state space) under some mild assumptions on the expressiveness and parametrization of the policy class (see Assumptions 1, 2).
As a corollary, our result also shows that the assumption of a stabilizing initial policy in [8] is not necessary. By using our homotopy algorithm, any linear policy will converge to the optimal policy of the undiscounted LQR. This is ultimately a trade-off between initial information and number of training iterations; the homotopy approach allows us to start the learning process with less background information at the cost of more training iterations. This type of trade-off has been considered before, most notably in [24] and [25] where AlphaGo was initially trained on human games via supervised learning before engaging in self-play but AlphaZero was trained entirely via self-play and no human input.

Organization.
The paper is organized as follows. In the coming section, we provide the necessary background information to understand the context of our problem (Section 2). In Section 3 we provide our result regarding the convergence of policy gradient methods with a non-linear function approximator in the LQR using the aforementioned homotopy approach inspired by the human learning process. In this section, we also provide the counterexample where policy gradient methods do not converge to the global optimum. The discussion is contained in Section 4. The full proofs of the results, as well as some numerical examples corroborating our claims, obtained are housed in Appendices A, B and C.

PRELIMINARIES AND BACKGROUND
In this paper, we study a reinforcement learning problem where an agent interacts in discrete time with the environment with the goal of minimizing some cost function that depends on the agent's states and actions. The agent does this by sequentially choosing actions over time which influence the agent's state in the environment. Throughout, for given n, m ∈ N we respectively define X = R n and U = R m as the set of possible states and actions of the agent. Correspondingly, for t ∈ Z ≥0 we denote by x t ∈ X and u t ∈ U the state and action of the agent at time t. The function that maps a state to action of the agent in that state is called the policy π : X → U , and the motivation behind this paper is to investigate the conditions under which an agent will learn the optimal policy of a specific environment: the Linear-Quadratic Regulator.

The Linear-Quadratic Regulator.
The Linear-Quadratic Regulator (LQR) is a classic optimal control problem. In this paper, we are interested in the special case where the dynamics are linear, time-invariant with no disturbance or added noise and the cost function is quadratic in the state and the control action. We consider the discounted infinite time-horizon problem, where A : X → X and B : U → X are the system (or transition) matrices, Q : X → X and R : U → U are positive definite cost matrices, x 0 ∈ X is randomly distributed according to probability distribution 0 on X, and γ ∈ [0, 1] is the discount factor. For a given policy π, the expression to be minimized in (2.1) is referred to as the cost associated to π, which we denote by C(π). In the entirety of this work, the pair (A, B) is assumed to be controllable and (A, D) is assumed to be observable (where Q = D T D).
It is known [2] that the optimal control for the LQR problem is a linear function of the state, If A, B, Q, R, γ are known, the optimal control K * can be calculated explicitly. Let P γ denote the unique positive definite solution to the discounted discrete-time algebraic Riccati equation (DARE) for which we know the solution exists and since (A, B) is assumed controllable and (A, D) is assumed observable [2]. We can then write the optimal control as Later, we will sometimes omit the subscript γ when the dependencies are clear from context. Note that, in general, the optimal policy for the discounted LQR is different from the optimal policy for the undiscounted LQR. For instance, the optimal policy with respect to the discounted LQR may not even be stabilizing [20].
Throughout the remainder of the paper, we will use γ to denote the discount rate which we choose given an initial policy. We assume that γ ∈ [0, 1] is small enough such that the cost function is still bounded from above for all initial states x 0 ∈ supp ( 0 ), where 0 is the distribution of initial states.
Why LQR?. Although the assumptions for the linear-quadratic system are rather restrictive, the LQR is still an important problem for multiple reasons. Firstly, it is one of the few problems where the closedform of the optimal control exists. This fact by itself makes the LQR a pleasant environment to work with. Secondly, the LQR has a continuous state and action space. Thirdly, despite its simplicity, there is still a lack of theoretical guarantees regarding convergence of reinforcement learning algorithms in this setting. All of these factors have certainly contributed to its re-emergence as a benchmark environment in reinforcement learning theory; it is both nice to work with mathematically and difficult enough to be applicable to the real world.

Policy Gradient Methods.
Policy gradient methods are a general class of reinforcement learning algorithms where the agent directly learns a policy -which is assumed to be in a certain parametric family of functions -rather than first learning a value function. During training, the parameters of the policy are updated via gradient descent on the cost function. As mentioned in the introduction, policy gradient methods have increasingly become the approach of choice for solving difficult reinforcement learning problems. One reason for this popularity is that policy-based methods, as opposed to value-based, can easily learn stochastic policies, whereas action-value based methods have no natural and flexible way to do so.
The fundamental result underlying the successful application of these methods is the policy gradient theorem [28] which provides an explicit formula for the gradient of the performance in terms of the gradient of the policy w.r.t its parameters -importantly, the gradient of the state distribution is not needed, greatly simplifying the application of these methods.
The analogous theorem in the deterministic setting (first proven by [26]) allows one to conveniently compute the gradient of the cost function when considering a class of deterministic policies, as is the case in this paper. Furthermore, as shown in [8], it is possible to explicitly compute the gradient of the LQR cost function for linear policies. They show that for a linear policy K, where P K denotes the "cost to-go" matrix (i.e., C(K) = E x 0 ∼ 0 x T 0 P K x 0 ) and Σ K is the state covariance matrix.
In our work, we consider the same LQR setup as in [8]. That is, we also consider a deterministic policy rather than a stochastic policy, a randomly distributed initial state, and noiseless dynamics. Note that it is known [2] that the inclusion of additive zero-mean white noise to the LQR dynamics (2.2) does not change the optimal control.

MAIN RESULTS
Notation. We use · as the operator norm of a matrix or the Euclidean norm of a vector. We will use λ min (·) to refer to the smallest eigenvalue of a matrix.
In the first subsection, we construct the aforementioned example where vanilla (fixed discount factor) policy gradients only yield convergence to a local optimum. Importantly, this policy class of the example satisfies the assumptions needed for our convergence result. In the following subsection, we provide the main theorems which show convergence of the homotopy algorithm. The lemmas and additional details for both subsections have been omitted for clarity, the full details can be found in Appendices C and B. We denote by {x t } the sequence generated by the dynamics x t+1 = Ax t + Bπ ϑ (x t ). Throughout, π ϑ denotes the parametric policy of choice evaluated with parameters ϑ ∈ R d . In this paper, we consider policies of the form where each f k : R n → R m is a non-linear, globally Lipschitz function and ϑ k ∈ R is a parameter to be learned.
To establish our results we make the following assumptions: Assumption 2. For the LQR problem defined by (A, B, Q, R), for all γ ∈ [0, 1], the γ-optimal policy K * γ can be represented by π ϑ , i.e. K * γ ∈ Span{f k }. Assumption 1 is a standard assumption when considering function approximation via linear combination. We need this assumption to guarantee the uniqueness of policy parametrization. Assumption 2 is necessary to guarantee that, for any choice of γ, the optimal policy is in the parametric policy class being considered.
We note that the assumption of linear independence is, however, not essential for our proofs; rather, it is made for technical convenience to simplify our proofs of Lemma C.4 and Theorem 3.5, guaranteeing local strict convexity of the landscape. For example, in the proof of Lemma C.4, if we were to relax Assumption 1, we would see that the eigenvectors that now correspond to the zero eigenvalue of the Hessian would be the directions where the policy is unaffected by changing the parameters. Therefore, we could relax the assumption to allow overparameterization and in turn to allow for wider networks in Remark 3.2.
Lemma 3.1. Assumptions 1 and 2 imply that the optimal parameters are continuous in the discount factor. In other words, for γ ∈ [0, 1] and for any ε > 0, where ϑ * γ denotes the parameters that correspond to K * γ for the policy class of (3.1).
Proof. Let {g k } denote the orthonormal set obtained from {f k } via Gram-Schmidt. We can then write Thus, we see that By Lemma C.1 we see that the optimal controls K * γ are continuous in γ. Thus we conclude that Now, notice that we can also write the hat-coefficients as   θ and this change-of-basis matrix is invertible by Assumption 1. Thus, denoting the above matrix by A, we conclude that where σ(x) = max(0, x) is the rectified linear unit (ReLU), x ∈ R n is the state, and w k ∼ N (0, I n ) are the first layer weights fixed at initialization. This type of modification with duplicated ReLU neurons has been considered before (see Appendix F of [34]).

Proof of Remark 3.2.
Recall that x ∈ R n . For Assumption 1, we note that {w k } is a linearly independent set with probability 1. With this architecture, for every x ∈ R n there will be exactly n terms in the sum that are non-zero. Since {w k } forms a basis of R n , Assumption 2 follows.
Remark 3.3. The policy class {f k } = {1 i,j } ∪ {F } for some globally Lipschitz function F satisfies the above assumptions. Here 1 i,j ∈ R m×n denotes the matrix with all 0's except for a 1 in the i, j'th entry. This policy can be written as where K ∈ R m×n , ϑ ∈ R are the parameters to be learned. This will be the policy class we consider in Section 3.1 to construct our counterexample.

Counterexample with a Globally Lipschitz Policy.
We now proceed to construct the aforementioned example where vanilla (fixed discount factor) policy gradients may result in convergence to a local optimum. Importantly, the policy class of this example satisfies the assumptions needed for the convergence result provided in the subsequent section. The lemmas and additional details for both subsections have been omitted for clarity, the full details can be found in Appendices B and C.
We consider a simple 1-dimensional system (X = U = R, γ ∈ (0, 1)). Fix γ, we then choose (A, B) = (0, 1) and (Q, R) = (1, R) as our system matrices (see (2.2)) for any R ∈ (0, γ). Notice that this system is controllable and observable so there is an optimal control. For a ∈ R and δ > 0, we define the spike or tent function of width 2δ centered at a: A cobweb diagram for the first step of the LQR dynamics in the counterexample. The blue line represents the dynamics of the system at initialization (ϑ 0 = 0, ϑ 1 = 1). Our initial distribution of states is heavily weighted around the two points (x 0 and y 0 ) that map to the two small tents on the right; this requires the points to lie somewhere in the domain of the spike on the left because all other states are mapped to negative numbers.
Next, we define the control as for a choice of parameters ω 0 ∈ (−1, 0) and where a 2 , a 3 < |a 1 | that are fixed during training of the model. We set 3) for a parameter δ to be chosen later. The dynamics resulting from this choice of parameters are depicted in Figure 1. We note that the optimal policy for the LQR belongs to this policy class and corresponds to the parameters (0, 0).
We choose the initial condition (ϑ 0 , ϑ 1 ) = (0, 1) and define the distribution of the initial state as the following measure with support on (−5, 5) where x 0 = min F −1 (a 2 ) and y 0 = min F −1 (a 3 ), i.e., we define x 0 and y 0 as the smaller of the two pre-images for a 2 and a 3 , respectively. To prove that the point (0, 1) is a local minimum of the cost function, and therefore a suboptimal fixed point of the policy gradient algorithm, we show that any infinitesimal change in ϑ 0 and ϑ 1 around (ϑ 0 , ϑ 1 ) = (0, 1) will increase such cost function.
To understand why this is the case, consider first the trajectory of the points x 0 and y 0 . It is easy to see that, by the design of the control, any small perturbation of the parameters that change the image of x 0 and y 0 will result in a state of larger absolute value, resulting in turn in a larger cost for those trajectories. On the other hand, it is also possible that a change in parameters actually lowers the cost for some trajectories starting in x ∈ [−5, 5] \ {x 0 , y 0 }. Still, by our choice of ε it is possible to show that the increase in cost for x 0 , y 0 outweighs the decrease. More specifically, the proof follows the following steps (the full details are presented in Appendix B): (1) For both x 0 , y 0 , we first prove that we can choose the parameter δ > 0 (see (3.3)) such that outside of a small cone in parameter space, we can bound the change in cost from below to show that it is always positive. (2) We then guarantee that we can pick the parameters of the model such that the cones described above corresponding to x 0 and y 0 only intersect at the origin. (3) Next, we show that the cost difference is still positive even if the infinitesimal change in (ϑ 0 , ϑ 1 ) belongs inside one cone and outside of the other. (4) Lastly, we bound the contribution of the uniform distribution term in µ 0 , showing that it is negligible with respect to any of the contributions to the cost function from the trajectories starting at x 0 or y 0 .
Qualitatively, we can plot the cost landscapes for our example around ϑ = (0, 1) to see that this point indeed is a local minimum (see Figure 3 in the appendix). The example we have described is only one member of a family of possible counterexamples. The proofs we provide have used some of the specifics of our example; however, they can be very easily generalized to describe a set of parameters and constraints necessary for the point ϑ = (0, 1) to correspond to a local minimum of the cost function. We only present this specific example as it is sufficient to demonstrate the failure of vanilla policy gradients in the LQR.

Convergence Results.
In this section we present our convergence result for policies of the form where each f k : R n → R m is a non-linear, globally Lipschitz function and ϑ k ∈ R is a parameter to be learned. We prove our results under Assumptions 1 and 2, restated here for convenience. Assumption 2. For the LQR problem defined by (A, B, Q, R), for all γ ∈ [0, 1], the γ-optimal policy K * γ can be represented by π ϑ , i.e. K * γ ∈ Span{f k }.
We prove the convergence of policy gradient methods for the policy class of (3.1) by using the homotopy idea discussed in the introduction. Informally, our idea is that if one updates γ by increasing it an infinitesimally small amount to γ , one might expect that the optimal policies for the corresponding discount factors might not be too far from each other. Then if these policies, and importantly their parameterizations, are sufficiently close, policy gradient methods will yield convergence from the γoptimal policy to the γ -optimal policy. It's important to remember that one should not expect this behavior in general; we have the simplicity of the LQR to thank for the continuity of the optimal policy in the discount factor, but in more challenging settings such as Chess or Go, this may not be the case.
Algorithm 1: Homotopy algorithm for LQR. Here PG(ϑ, γ) denotes the fixed point of the policy gradient algorithm for the given LQR problem with discount factor γ and initial condition ϑ.
Result: Optimal policy of the LQR problem In other words, given some initial parameters ϑ(0) and an increasing sequence of discount factors γ n ∈ [0, 1], we run the policy gradient algorithm until convergence to the optimal policy of the first discount factor. We then use this optimal policy as the initial policy for the system with the next discount factor, and let the policy gradient algorithm converge to the corresponding optimum. We continue iterating until we have converged to the optimal policy of the undiscounted LQR. To prove this algorithm converges, we need to prove that policy gradients yield convergence from the γ-optimal policy to the γ -optimal policy if γ and γ are sufficiently close, and that for any arbitrary initialization, the first iteration of the algorithm converges.
The proof is split into two main steps: (1) Prove convergence of arbitrary initializations to the γ = 0 optimal policy.
(2) Prove local convergence of policy gradient methods. In other words, we show that for discount factors γ and γ sufficiently close, policy gradient methods yield convergence from the γ-optimal policy to the γ -optimal policy.
The first step brings policies into the "homotopy" regime, while the second step shows that we can iterate this process to go from the γ = 0 optimal policy to the γ = 1 (undiscounted) optimal policy. We remark that it is also reasonable to ignore this first step and to initialize the policy to the zero function as is occasionally done in practice.
In the statements of the theorems and their proofs, we recall that ϑ ∈ R d denotes the parameters of the model and ϑ * γ ∈ R d denotes the optimal parameters for the given value of γ, which exist and are unique by Assumptions 1, 2.
Theorem 3.5 (Convergence at γ = 0). Let {f k } d k=1 be a set of globally Lip(f k )-Lipschitz continuous functions, and let 0 (the distribution of the initial state) have full support on R d . Under Assumptions 1, 2, any random initialization of the parameters ϑ will converge to the optimal policy for discounted LQR with γ = 0.
We first note that the discount factor of this first iteration does not need to be γ = 0; however, to make it easier to prove convergence of the first iteration, we can assume that γ = 0. With such high myopia, the learning task becomes much easier, since the optimal policy for the LQR with γ = 0 is simply the zero function.
The proof uses the fact that we can write a differential equation describing the evolution of the cost difference C γ (ϑ(s)) − C γ (ϑ * γ ) over time, where C γ (ϑ) denotes the cost for the policy π ϑ with discount factor γ. This results in an expression that is similar to gradient-domination bounds and from this the conclusion follows.
The main idea behind the proof of this result is to leverage a Taylor expansion of the cost function C γ ( · ) around its minimum ϑ * γ for any fixed value of γ ∈ (0, 1). We show that by considering the second order Taylor expansion in a small neighborhood around optimality, the landscape of the policy gradient algorithm is locally convex. This allows to show that from any point within this neighborhood, policy gradient methods experience exponential convergence to the γ-optimal policy by applying Grönwall's inequality.
Lastly, we want to show that by continuously updating the discount factor, we can ensure that we are always within a small neighborhood of the optimal policy for the next discount factor, eventually reaching the undiscounted optimal.
Theorem 3.7 (Convergence to Undiscounted Optimal). For any initial parameters ϑ 0 , Algorithm 1 will converge to the undiscounted optimal policy ϑ * .
Corollary 3.8. There exists an increasing sequence {γ n } n of discount factors such that Algorithm 1 converges to the global optimum of the undiscounted LQR.
Proof of Theorem 3.7. Theorem 3.5 shows that any initialization of the policy will converge to the optimal policy of the γ = 0 system. Theorem 3.6 together with positive-definiteness of H γ then tells us that policy gradient methods experience local exponential convergence near optimality. Corollary C.2 and Lemma 3.1 tell us that for |γ − γ| sufficiently small, ϑ * γ will be in close enough to ϑ * γ for Theorem 3.6 to apply. One can iterate this process until reaching the undiscounted optimal policy.

DISCUSSION AND CONCLUSION
This paper provides a convergence guarantee for model-based policy gradient methods in the setting of the LQR with the policy class { d k=1 ϑ k f k (x) | ϑ k ∈ R} contingent on a few assumptions on the expressiveness and parametrization of the policy class. Unlike previous works, we adopt a new approach for proving convergence, namely, the homotopy-based approach which, to the best of our knowledge, has not been used before in theoretical reinforcement learning. Using a discount factor to guarantee finite costs and well-defined updates can also be applied to solving issues involving a chaotic policy, such as the one arising naturally from piece-wise linear policies such as the tent map.
Furthermore, we provide an example illustrating a situation where expanding the policy class in the LQR case leads to local minima of vanilla policy gradient algorithms. This issue is resolved by applying the homotopic variant of policy gradients developed in this paper.
Limitations. It is important to note that our work considers an idealized, model-based and infinitesimalstepsize approach. To generalize our results to the model-free perspective, one could proceed in a similar fashion to [8] by showing that when the roll-out is sufficiently long, the cost function and covariance of the state trajectory can be accurately approximated and that with enough samples, the true gradient can be approximated within a desired accuracy. Some other interesting avenues include relaxing the assumption of continuous updating, i.e., to consider the stochastic approximation problem resulting from the real-life setting of finite samples and finite step-size and establishing quantitative bounds for the homotopy method.
Furthermore, the approach proposed in this work results in a significant increase in the computational cost of training when compared to the vanilla policy gradient algorithm. This results in a trade-off between computational cost and convergence guarantees for solving the control problem at hand. While this trade-off may not be of immediate interest in practice, what we propose is a new paradigm for studying the convergence of reinforcement learning algorithms.
Future Work. The problem of extending our proofs to establish convergence for the policy class of neural networks remains open. We expect that it should be possible to extend our result to linearized neural networks (such as the Neural Tangent Kernel regime) but we leave this result for future research.
Societal Impact. In the much bigger picture, our work is related to the issue of bias in machine learning. The common practice of seeding reinforcement learning agents with human training data can be problematic when the human-generated data contains implicit biases that we do not want in the agent -almost all data associated with humans will contain such biases. Our work specifically shows that we can do away with some assumptions on the initial knowledge of reinforcement learning agents (e.g., assuming the initial policy of the LQR is stabilizing), and thus, in applicable settings, do away with any dependence on human-generated data. We choose to include this reminder because it is imperative to keep this question in mind when designing machine learning models with the goal of bettering human lives. A simple example is the autonomous vehicle trolley problem. In some cultures, it may be preferable to crash into one individual over the other, and thus a model trained in one country may have disastrous consequences when deployed in another.

FIGURE 2. Evolution of the cost during Algorithm 1 as a function of training iterations.
The blue line is the cost during training of the homotopy algorithm in a similar setting to the one described in Section 3.1. The orange dots represent a point at which γ was updated. The red lines are the optimal costs for the various values of γ. The graph on the left is a close-up of the cost between iterations 0 and 10 5 , the one on the right represents the full training process. The dashed red line on the plot on the right is the optimal cost for γ = 1. We run Algorithm 1 to solve the LQR problem (2.1), (2.2) in dimension n = m = 1 with (A, B) = (0.1, 1) and (Q, R) = (1, 0.1) with the parametric policy class described in Section 3.1 and setting δ = 5e-4. We do so by writing a policy using PyTorch and updating the parameters via gradient descent with a stepsize of 1e-3. We increased γ by 0.02 whenever the absolute values of both partial derivatives with respect to the parameters ϑ 0 , ϑ 1 were less than a tolerance hyperparameter, in our case set to 1e-4. Note that the initial states x 0 and y 0 described in Section 3.1 can be explicitly calculated to be −117/59 and −588/295, respectively. We trained the model for a total of 500000 episodes. During each episode, we interacted with the LQR system for a fixed number of steps, in our case, 5. Since the value for ε determined by our model is negligibly small (i.e., ε < 1e-12), we simultaneously simulate the roll-outs from x 0 and y 0 during training and update using the total sum of discounted costs experienced in both roll-outs. We update the parameters after every episode. To highlight the homotopy algorithm, we initialize our policy with the parameters ϑ = (0, 0) which correspond to the γ = 0 optimal policy.

A.2. Counterexample.
(A) Notice, in the top-right figure, the two "good" directions in parameter space.
(B) Close-up of the above plots. FIGURE 3. Landscape of the cost function from the example of Section 3.1 in a neighborhood around ϑ = (0, 1). The local minimum at (0, 1) can be clearly seen in these plots. We compute the landscape of the cost function to verify numerically the result of Proposition 3.4 and represent the lanscape in Figure 3. These results were generated by evaluating the cost experienced by the policy with parameters (ϑ 0 , ϑ 1 ) in a neighborhood of (0, 1) for the choice of parameters in Section 3.1 and setting ε = 0 and δ = 5e-4. The cost of a policy was evaluated by rolling out the policy from both x 0 and y 0 for 5 steps and computing the discounted sum of the instantaneous costs. Plots were made using the contour plot method from matplotlib.pyplot.

APPENDIX B. PROOFS FOR THE COUNTEREXAMPLE
Before stating and proving our results, we give a roadmap for the structure of the proof. In Lemma B.1 we show that the cost associated to trajectories starting at x 0 or y 0 is lower-bounded locally by the 1 norm of the perturbation of the parameters dϑ 1 outside of 2 cone in parameter space (one for each initial condition). Then, in Lemma B.2 we show that a similar lower bound -with a reduced constantholds when the perturbation dϑ lies in one such cone (e.g. the one associated to x 0 ) but outside of the other (e.g. the one associated to y 0 ), i.e., in such regions the positive contribution to the cost of one of the trajectories outweights the one of the other. Combining this with Lemma B.3 showing that for a choice of parameters the cones do not overlap, we obtain in Corollary B.4 that the joint contribution to the cost function associated to trajectories starting at x 0 , y 0 is lower-bounded locally by (a constant times) the 1 norm of the perturbation of the parameters dϑ 1 . We conclude by further combining this with Lemma B.5, showing that the contribution to the calculation of the uniform measure is negligible, so that the lower bound stated above holds for µ 0 .
Throughout, we define where x t (dϑ) ∈ R n denotes the trajectory of the LQR with control π ϑ+dϑ for ϑ = (0, 1) and initial condition x 0 .
Notation. We will use z t to denote the t'th state of the unperturbed trajectory and we will use z t (dϑ) for the corresponding state of the perturbed trajectory (i.e., generated by policy π ϑ+dϑ ).
Lemma B.1. Let ϑ = (0, 1) and let z 0 ∈ (x 0 , y 0 ) defined in Section 3.1. For any α > 0, there exists δ > 0, K > 0 such that for any i ∈ {2, 3} and dϑ = (dϑ 0 , dϑ 1 ) satisfying the cost difference between the contribution to the cost function using the perturbed and unperturbed policies for trajectories starting from z 0 is strictly positive and bounded from below: Proof of Lemma B.1. Throughout, let z, a, ω be generic variables that can be replaced by either (x, a 2 , ω 2 ) or (y, a 3 , ω 3 ). We first consider how the cost of a trajectory changes for any infinitesimal variation of the parameters dϑ = (dϑ 0 , dϑ 1 ). To do so we calculate the first order corrections (in dϑ) to the first two timesteps of the trajectory z t (dϑ) starting at z 0 . For the first timestep, since along the unperturbed trajectory we have z 1 = F (z 0 ) = a, we have where here and throughout this section z t = z t (0) denotes the unperturbed trajectory. For the second timestep, where dz 2 := z 2 dϑ 1 + adϑ 0 + ω 0 (adϑ 1 + z 0 dϑ 0 ) − ω δ |adϑ 1 + z 0 dϑ 0 | is the first order correction to the second timestep of the trajectory. We then note that since z 2 ∈ (−1, 0) due to our choice of parameters, the future cost from z 2 is given by Since z 2 (dϑ) ∈ (−1, 0) by construction as well, the above expression also holds for z 2 (dϑ). Therefore, since Q = 1 and 1 + Rω 2 0 > 0, the cost of trajectory from z 2 onward will vary (to first order in dϑ) by Inserting the expression of dz 2 , since z 2 is negative. The inequality comes from the fact that whenever |z 0 dϑ 0 + adϑ 1 | ≥ α dϑ 1 we can choose δ > 0 sufficiently small such that (γ + R)a|adϑ 1 + z 0 dϑ 0 | z 2 γ 2 1 + Rω 2 0 /(1 − γω 2 0 ) Bounding the right-hand-side by triangle inequality, the above is satisfied when .
Based on the above, the only variation of the parameters that does not increase the cost of the policy is when dϑ is inside the cone |z 0 dϑ 0 + F (z 0 )dϑ 1 | ≤ α dϑ 1 , for z 0 ∈ {x 0 , y 0 }. For the statement of the next lemma, for a choice of z 0 ∈ {x 0 , y 0 } we definē z 0 ∈ {x 0 , y 0 } \ z 0 as the other initial condition and byz t (dϑ) the corresponding perturbed trajectory.
For the same δ, K > 0 as determined by Lemma B.1, the cost difference is strictly positive and can be bounded by Here µ 0,pp = 1−ε 2 (δ x 0 + δ y 0 ) denotes the pure-point, or discrete, part of µ 0 . Proof of Lemma B.2. The proof proceeds similarly to the proof of Lemma B.1. We start by bounding from below the variation of the cost due to the trajectory z t starting at z 0 with |z 0 dϑ 0 + F (z 0 )dϑ 1 | ≤ α dϑ 1 . Recalling the expression for the first-order variation of the cost (B.2) from the proof of Lemma B.1 and that z 2 < 0 by our choice of parameters, we bound the negative part of the contribution to the cost function for t ≥ 2 as: denote the positive and negative part of b ∈ R respectively. We can assume that the quantity on the LHS above is negative; if it were positive, then the proof is done since we are aiming to lower bound the total difference, so we could ignore this term if it were positive. Since we are using the same δ as chosen in Lemma B.1, recalling the definition of K > 0 and that z 2 < 0 we obtain Then, recalling that z 1 = F (z 0 ) = a and 0 < R < γ, the total cost difference from the initial point z 0 (to first order) can then be bounded as follows for dϑ sufficiently small: where in the second inequality we have used that where µ 0,pp denotes the discrete part of the measure µ 0 .

Lemma B.3.
For any x 0 = y 0 such that x 0 , y 0 < 0 and F (x 0 ), F (y 0 ) > 0, there exists an α > 0 such that The above directly implies that Corollary B.4. For the same δ, K > 0 as determined by Lemma B.1, and for every dϑ ∈ R d with dϑ < δ we have that Here µ 0,pp denotes the pure-point, or discrete, part of µ 0 .
Proof of Corollary B.4. For our choice of parameters (3.3), Lemma B.3 gives us an α > 0 such that the cones determined by x 0 and y 0 in parameter space do not overlap except at dϑ = (0, 0). By Lemma B.1, for any such α there exists a δ > 0 such that the claim holds.
Proof of Lemma B.3. By assumption, the lines only intersect at the origin. Then, the bisector of the central angle between these two lines can be written as We can assume without loss of generality that the line corresponding to x 0 lies above the bisector (i.e., −x 0 /F (x 0 ) > M ). Then, it suffices to choose α such that neither of the sets intersects the line M = {(dϑ 0 , dϑ 1 ) ∈ R 2 : dϑ 0 = M dϑ 1 } outside of (0, 0). Notice that the boundaries of the sets in (B.6) that are closest to M can be explicitly written as the lines .
Then, noting that we can replace −x 0 with |x 0 | and −y 0 with |y 0 | since x 0 , y 0 < 0, we have that the only intersection of the sets in (B.6) with M is (0, 0) if which is equivalent to the conditions Since we have assumed that and that F (x 0 ), F (y 0 ) > 0, we know that the bounds in both constraints are strictly positive. Thus, we can choose any Lemma B.5. There exists K > 0 such that for any initial point u 0 ∼ U (−5, 5), the average cost difference can be bounded from above by Proof of Lemma B.5. For any u 0 ∈ [−5, 5], we can write the cost difference as since we assume, in the construction of the example, that 0 < R < γ. Iterating the bound established above we obtain We now proceed to estimate the numerator of the above expression. To do so, let L = |ω 0 |+|ω 1 | δ 1 denote the Lipschitz constant of F on (−5, 5). Notice that in the interval (−1, 1), the Lipschitz constant of F restricted to this interval is |ω 0 | and that on (−5, 5) F is non-expansive (|F (x)| ≤ |x|) and F 2 is contractive (∃k ∈ [0, 1) s.t. |F 2 (x)| ≤ k|x|) by construction. Since 5|ω 0 | 2 > 1 but 5|ω 0 | 3 < 1, any initial point will take at most three steps before it is mapped into the region with Lipschitz constant |ω 0 |.
for dϑ small enough, taking only the first order term. Combining the above with (B.7) and defining L = γL + 25R finally gives as claimed. and for dϑ = 0 sufficiently small, since µ 0 = µ 0,pp + ε 10 for µ 0,pp = 1−ε 2 δ x 0 + 1−ε 2 δ y 0 we have that where in the second line we have combined Corollary B.4 and Lemma B.5. Thus, we see that the point in parameter space corresponding to ϑ = (0, 1) is a local minimum of the cost function.

APPENDIX C. PROOFS OF CONVERGENCE OF THE HOMOTOPY ALGORITHM
For notational convenience, we define We use ∆ϑ = (∆ϑ 1 , . . . ∆ϑ d ) to denote a perturbation of the parameters. We study the behavior of the parameters in the setting where ϑ = ϑ * + ∆ϑ.
Lemma C.1. For a fixed quadruple (A, B, Q, R) that is controllable and observable, let P γ denote the unique positive semi-definite solution to the discounted discrete algebraic Riccati equation (discounted DARE) with discount factor γ ∈ [0, 1] Since the optimal policy is a continuous function of P γ , Lemma C.1 immediately gives us Corollary C.2. The optimal policy K * γ is continuous in γ. We preface the next two lemmas by reminding the reader that the expansion of the cost function that we consider is around the optimal policy K * γ . However, since this notation is a bit tedious, we simply use K to refer to this optimal policy in our coming computations. Here, we are using Assumption 2 when we stipulate that π ϑ * = K * γ . Lemma C.3. The first-order term in the Taylor expansion of the cost (with respect to the parameters) evaluates to zero at optimality.
Let π denote the policy and letπ denote the perturbation of π (i.e., π ϑ * +∆ϑ = π ϑ * +π). Furthermore, recall that our policy representation is linear in the parameters. We first compute the zero'th, first, and second order terms of the expansion of the trajectory.
where we ignore all non-second-order terms to reach the last equality. We note that, by the Lipschitz continuity of policy π, all remaining terms in the first order term of the Volterra expansion for the given system are of order higher than 1.
We can bound the Euclidean norm of the second order term in the expansion using the assumed Lipschitz continuity of π: Proof of Lemma C.3. We consider a perturbation of the parameters of the policy. For any x 0 ∈ supp ( 0 ), the first order term of the Taylor approximation is Let s = t − l, changing the order of summation, we get which evaluates to zero at K * since K * = −γ R + γB T P γ B −1 B T P γ A. This is consistent with the fact that the first order term is the gradient multiplied by ∆ϑ. This calculation gives us an explicit form of the term that will simplify the proof of the next lemma.
Lemma C.4. Let 0 have full support, then the Hessian is symmetric and strictly positive definite at optimality.
Proof of Lemma C.4. For any x 0 ∈ supp ( 0 ), the second order term in the approximation of the cost is as follows.
Notice we can ignore the underlined sum since it is already symmetric. In the remainder of this calculation, we will use a red underline to highlight the symmetric terms that we will omit for clarity. The remaining terms of interest are Like the proof of Lemma C.3, we define s = t − l and change the order of summation to get We have dealt with the term containing two copies of x (1) t by splitting it into two pieces: the sum of all terms where both indices of the inner sums are 0 and everything else. The former is symmetric, so we can omit it. Noticing that P γ = ∞ t=0 γ t (A t ) Q A t we continue from above To finish the proof, notice that the bracketed terms are almost identical the first-order term from Lemma C.3. We also note that the terms multiplied to the bracketed terms are guaranteed to be finite due to the assumed Lipschitz continuity of F .
Thus, the second-order term of the expansion of the cost function around optimality for the trajectory with initial condition x 0 reads Since the policy is linear in the parameters, we can formally write this as an inner product where we define multiplication between an m × m matrix and a vector of m × 1 vectors to be carried out component-wise.
To avoid writing this large expression again, we denote the matrix in the parentheses by H γ . We use this matrix to define the quadratic form used as the Lyapunov function in the proof of Theorem 3.6. Given this expression for C (2) , we notice that it is always non-negative and is zero if and only if the policy is optimal for the given initial condition, x (i.e., ∆u t = 0 ∀t). Consequently, integrating this term against the initial distribution 0 will result in a nonzero outcome if and only if the trajectory of almost all initial condition is optimal. Since 0 has full support, and by Assumption 1 (2) [x] = 0 [ 0 ]-a.e. ⇐⇒π(x (0) t ) = 0 ∀t ⇐⇒ ∆ϑ = 0 Theorem 3.5 (Convergence at γ = 0). Let {f k } d k=1 be a set of globally Lip(f k )-Lipschitz continuous functions, and let 0 (the distribution of the initial state) have full support on R d . Under Assumptions 1, 2, any random initialization of the parameters ϑ will converge to the optimal policy for discounted LQR with γ = 0.
Proof of Theorem 3.5. Let ϑ be the randomly initialized parameters. When γ = 0, the cost can be written as For convenience, we will omit the subscripts. Notice that the optimal parameters are ϑ * = 0 which correspond to the optimal action of u = 0. We can calculate where ·, · denotes the scalar product in R d . To prove convergence, what remains is to show that the only extremum is the global minimum. In other words, we want to show ∇ ϑ C 0 (ϑ) = 0 ⇐⇒ ϑ = ϑ * 0 (⇐) This direction is straightforward. At ϑ = ϑ * γ , we see that u = 0 for any x, thus, ∇ C = 0.
For the next theorem, we recall the definition of the positive definite Hessian H γ appearing in the proof of Lemma C.4: