{'fraction_non_alphanumeric': 0.054454770924749936, 'fraction_numerical': 0.01856040990978714, 'mean_word_length': 4.124511173184358, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 35, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 28, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Sample Complexity and Metastability of Heavy-tailed Policy Search in Continuous Control

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


Introduction
In reinforcement learning (RL), an autonomous agent sequentially interacts with its environment and observes rewards incrementally across time [87]. This framework has gained attention in recent years for its successes in continuous control [80,48], web services [104], personalized medicine [44], among other contexts. Mathematically, it may be described by a Markov Decision Process (MDP) [73], in which an agent seeks to select actions so as to maximize the long-term accumulation of rewards, known as the value. The key distinguishing point of RL from classical optimal control is its ability to discern control policies without a system dynamics model.
Algorithms for RL either operate by Monte Carlo tree search [31], approximately solve Bellman's equations [12,97], or conduct direct policy search [98]. While the first two approaches may have lower variance and converge faster [26,24], they typically require representing a tree or Q-function for every state-action pair, which is intractable in continuous space. For this reason, we focus on PG.
Policy search hinges upon the Policy Gradient Theorem [88], which expresses the gradient of the value function with respect to policy parameters as the expected value of the product of the score function of the policy and its associated Q function. Its performance has historically been understood only asymptotically [43,42,16] via tools from dynamical systems [45,18]. More recently, the non-asymptotic behavior of policy search has come to the fore. In continuous space, its finite-time performance has been linked to stochastic search over non-convex objectives [19], whose O(1/ √ k) convergence rate to stationarity is now clear [17,102]. However, it is challenging to discern the quality of a given limit point under this paradigm.
By contrast, for tabular MDPs, stronger results have appeared [15,101,5]: linear convergence to global optimality for softmax parameterizations. A critical enabler of these recent innovations in finite MDPs is a persistent exploration condition: the initial distribution over the states is uniformly lower bounded away from null, under which the current policy may be shown to assign strictly positive likelihood to the optimal action over the entire state space [56][ Lemma 9]. This concept of exploration is categorically different from notions common to bandits, i.e., optimism in the face of uncertainty [92,46,37,75], and instead echoes persistence of excitation in systems identification [60,61]. Under this condition, then, a version of gradient dominance [52] (known also as Polyak-Łojasiewicz inequality [51,72]) holds [4,56,55], which enables such global improvement bounds. Unfortunately, translating this condition to continuous space is elusive, as many common distributions in continuous space may fail to be integrable if their likelihood is lower bounded away from null over the entire (not necessarily compact) state space. Thus, the following question is our focus: 1 Can one nearly satisfy persistent exploration in MDPs over continuous spaces through appropriate policy parameterizations, and in doing so, mitigate the pathologies of non-convexity?
In this work, we step towards an answer by studying policy parameterizations defined by heavy-tailed distributions [20,27], which includes the family of Lévy Processes common to fractal geometry [34,53], finance [89,90], pattern formation in nature [7], and networked systems [22]. By employing a heavy-tailed policy, the induced transition dynamics will be heavy-tailed, and hence at increased likelihood of jumping to non-adjacent states. That policies [21,41] or stochastic policy gradient estimates [28] associated with heavy-tailed distributions exhibit improved coverage of continuous space is well-documented experimentally. Here we seek a more rigorous understanding of in what sense this affects performance may be formalized through metastability, the study of how a stochastic process transitions between its equilibria. This marks a step towards persistent exploration in continuous space, but satisfying it precisely remains beyond our grasp.
Historically, heavy-tailed distributions have been recently employed in non-convex optimization to perturb stochastic gradient updates by α-stable Lévy noise [32,85], inspired by earlier approaches where instead Gaussian noise perturbations are used [71,29]. Doing so has notably been shown to yield improved stability to perturbations in parameter space since SGD perturbed by heavy-tailed noise can converge to local extrema with more volume, which in supervised learning is experimentally associated with improved generalization [63,103,1], and has given rise to a nascent generalization theory based on the tail index of the parameter estimate's limiting distribution [84,85]. Rather than perturbing stochastic gradient updates, we directly parameterize policies as heavy-tailed distributions, which induces heavy-tailed gradient noise. Doing so invalidates several aspects of existing analyses of PG in continuous spaces [17,102]. Thus, our main results are: • We present a few heavy-tailed policy parameterizations that may be used in lieu of a Gaussian policy for continuous space, which can prioritize selecting actions far from the distribution's center (Sec. 2), and discuss how policy search manifests for this setting (Sec. 3); • We establish the attenuation rate of the expected gradient norm of the value function when the score function is Hölder continuous, and may be unbounded but whose moment is integrable with respect to the policy (Theorem 4.2). This statement generalizes previous results that break for non-compact spaces [17,102], and further requires introducing an exploration tolerance parameter (Definition 4.1) to quantify the subset of the action space where the score function is absolutely bounded; • In sec. 4.2, by rewriting the PG under a heavy-tailed policy as a discretization of a Lévy Process, we establish that the time required to exit a (possibly spurious) local extrema decreases polynomially with heavier tails (smaller α), and the width of a peak's neighborhood (Theorem 4.5). Further, the proportion of time required to transition from one local extrema to another depends polynomially on its width, which decreases for smaller tail index (Theorem 4.6). By contrast, lighter-tailed policies exhibit transition times depending exponentially on the volume of an extrema's neighborhood; • Experimentally, we observe that policies associated with heavy-tailed distributions converge more quickly in problems that are afflicted with multiple spurious stationary points, which are especially common when myopic and farsighted incentives are in conflict with one another (Sec. 5).

Markov Decision Problems
In RL, an agent evolves through states s ∈ S selecting actions a ∈ A, which causes transitions to another state s to occur according to a Markov transition density P(s |s, a) and a reward r(s, a) is revealed by the environment to inform its merit. Formally, an MDP [73] consists of the tuple (S, A, P, r, γ), where continuous state S ⊆ R q and action spaces may be unbounded, i.e., Euclidean space in the appropriate dimension. We hypothesize that actions a t ∼ π(·|s t ) are selected according to a time-invariant distribution π(a|s) := P(a t = a|s t = s) called a policy determining the probability of action a when in state s. Define the value as the average long-term accumulation of reward [13]: γ t r(s t , a t ) | s 0 = s, π . (2.1) Moreover, γ is a discount factor that trades off the future relative to the present, s 0 denotes the initial state along trajectory {s u , a u , r u } ∞ u=0 , and we abbreviate the instantaneous reward as r t = r(s t , a t ). In (2.1), the expectation is with respect to randomized policy a t ∼ π(·|s t ) and state transition dynamics s t+1 ∼ P(.|s t , a t ) over times t ≥ 0. We further define the action-value (known also as Q) function Q π (s, a) as the value conditioning on an initially selected action: γ t r t | s 0 = s, a 0 = a, π . (2.2) We focus on policy search over policies π θ (·|s t ) parameterized by a vector θ ∈ R d , which we estimate via maximizing the expected cumulative returns [87]: Example 2.2 (Moderate-tailed policy). A distribution whose tail decays at a slower rate than the Gaussian may better explore environment, which we define as π θ (a|s) = 1 σA α exp −|a − φ(s) T θ| α /σ α (2.4) with normalizing constant A α := exp (−|x| α ) dx < ∞, tail index α ∈ [1,2] determining the likelihood of tail events, and scale parameter σ > 0.
With a few policy choices of detailed, we delve into their relative merits and drawbacks. Intuitively, policies that select actions far from a learned mean parameter over actions may better explore the space, which exhibits outsize importance when near and long-term incentives of the MDP are misaligned [57]. More formally, persistent exploration has been identified in tabular MDPs as key to the ability to converge to the optimal policy using first-order methods [4,56,55] and avoid spurious behavior. Persistent exploration formally ensures that under any initial distribution over s 0 in (2.1), the current policy assigns strictly positive likelihood to the optimal action over the entire state space [56][Lemma 9], under which a version of gradient dominance (akin to strong convexity) holds (Lemma 8). Interestingly, these results echo classical persistence of excitation in systems identification [60,61]. The stumbling block in translating these conditions from finite to continuous spaces is that many common distributions over unbounded continuous space may fail to be integrable if their likelihood is lower bounded away from null. As a step towards satisfying this condition, we seek to ensure that the induced transition dynamics under a policy are heavy-tailed, which increases the likelihood of jumping to cover more of the state space. Doing so may be accomplished by specifying a heavy-tailed policy (Example 2.2 -2.3), whose likelihood approaches null slowly while still defining a valid distribution. That continuous space necessitates exploration to eventuate in suitable behavior may be illuminated through the Pathological Mountain Car (PMC) (cf. Fig. 1) introduced next, where a car is between two mountains.
Pathological Mountain Car. The environment consists of two goal posts, a less-rewarding goal at s = 2.667 with a reward of 10 and a bonanza at s = −4.0 of 500 units of reward. In Fig. 1, it is possible to get stuck at the lower peak and never reach the jackpot without sufficient exploration. Its potential pitfalls are illuminated experimentally in Sec. 5.
With the motivation clarified, we shift to illuminating that heavy-tailed policies, while encouraging actions far from the mean, may cause policy search directions to possibly be unbounded and nonsmooth. These issues are the focus of Section 3.

Policy Gradient Methods
PG is an RL algorithm in which policy parameters in R d are iteratively updated as approximate gradient ascent with respect to the value function (2.1). Its starting point is the Policy Gradient Theorem [87], which expresses search directions in parameter space: where ρ θ (s, a) = ρ π θ (s) · π θ (a | s) is a distribution called the discounted state-action occupancy measure defined as the product of the discounted state occupancy measure ρ π θ (s) = (1 − γ) ∞ t=0 γ t p(s k = s | s 0 , π θ ) and policy π θ (a | s). In [88], both ρ π θ (s) and ρ θ (s, a) are established as valid distributions. Despite this fact, the integral in (3.1) may not exist due to the heavy-tailed nature of policy π θ (a | s). Therefore, we first present some preliminaries regarding (3.1) AS1. The absolute value of the reward is uniformly bounded, Assumption 2 is weaker than the standard almost-sure boundedness of the score function assumed in prior work [102, Assumption 3.1], which is restrictive, and not valid even for Gaussians (Example 2.1). To see this, write the norm of its score function as ∇ θ log π θ (s, a) ≤ O a + a 2 , which grows unbounded when the support of the action space is infinite. The score function also is unbounded in Example 2.2. These subtleties motivate the relaxed condition in Assumption 2 which is valid regardless of a policy's tail index (Examples 2.1 -2.3).
Next, we shift towards detailing PG. Under Assumptions 1 -2, we establish that the integral in (3.1) is finite (Lemma 4 in Appendix B.1). Thus, we employ it to compute search directions, which requires unbiased estimates of (3.1). To realize this estimate, conduct a Monte Carlo rollout of length T k ∼ Geom(1 − γ 1/2 ), collect trajectory data τ k = (s 0 , a 0 , s 1 , a 1 , . . . , s T k , a T k ), and form the PG estimate (akin to [10,50], except with a randomized horizon): where the parameter update for θ k is defined according to stochastic gradient ascent with step-size η > 0. The procedure for policy search along a trajectory is summarized as Algorithm 1, where in the pseudo-code, we permit mini-batching with batch-size B k , but subsequently assume B k = 1.
Next, we establish that the stochastic gradient∇ θ J(θ) is an unbiased estimate of the true gradient ∇ θ J(θ) for a given θ. As previously mentioned, almost sure boundedness [102, Assumption 3.1] of the score function ∇ θ log π θ (a | s) does not even hold for the Gaussian (Example 2.1), which motivates the moment condition in Assumption 2. This alternate condition is employed to establish unbiasedness of (3.3) formalized next (see Appendix B.2 for proof).
Algorithm 1 Heavy-tailed Policy Gradient (HPG) 1: Initialize : policy parameters θ 0 , discount γ, step-size η, gradient g 0 = 0, starting point (s 0 , a 0 ) Repeat for k = 1, . . . 2: Starting from (s 0 , a 0 ) , generate B k trajectories τ k,i = (s 0 , a 0 , s 1 , a 1 , . . . s T k,i , a T k,i ) of length T k,i ∼ Geom(1 − γ 1/2 ) with actions a u ∼ π θ k (.|s u ) 3: Compute policy gradient estimate g k and update parameters θ k : Observe that the policy parameterization in Example 2.2 is not Lipschitz but Hölder continuous. In the next section, we formalize the convergence of (3.3), discerning the convergence rate to stationarity and metastability characteristics: the proportion of time the algorithm's limit points spent at wider versus narrower local extrema as a function of the tail index.

Convergence Analysis
We analyze the ability of PG [cf. (3.3)] to maximize the value function (2.3). As J(θ) is non-convex in the policy parameter θ, the best pathwise result one may hope for is convergence to stationarity unless additional structure is present. Thus, we first study sample complexity in terms of the rate of decrease of the expected gradient norm E[ ∇J(θ k ) ], which we pursue under Assumptions 2-3 regarding the integrability of the norm of the score function with respect to the policy and Hölder continuity. This generality is necessitated by heavy-tailed policy parameterizations as previously mentioned, and has not been considered in prior works such as [88, 102, 101, 50].
Assumptions 2-3 present unique confounders to the RL setting that do not manifest in vanilla stochastic programming under relaxed smoothness conditions [82,62]. Specifically, they cause integrability and smoothness complications with respect to the occupancy measure ρ θ (s, a) induced by the MDP, which upends conditions on the objective and policy gradient in existing analyses. These complications are overcome in Lemmas 2 -3, which first require partitioning the action space into sets where the score function is and is not almost surely bounded according to an exploration tolerance parameter (Definition 4.1), which is unique to this work. Next, we make precise this discussion, establishing the convergence rate to stationarity of (3.3). Later in this section, we formalize that iterates escape narrow extrema, and tend to jump towards wider peaks.

Attenuation Rate of the Expected Gradient Norm
We first focus on convergence rates to stationarity. To do so, we begin by establishing that Assumption 3 regarding the Hölder continuity of the score function implies approximate Hölder continuity on the overall policy gradient. First, we partition the action space according to when the score function is almost surely bounded and where it is integrable according via a constant λ > 0 defined next. Definition 4.1. (Exploration Tolerance) Define as A(λ) the set of subsets of action space such that Then, λ is the exploration tolerance parameter of a policy in an MDP with unbounded score function. Associated with λ is an upper bound for the score function for subset A(λ) of action space as See Appendix C for proof. Lemma 2 generalizes a comparable statement regarding the Lipschitz continuity of the score function typically imposed to establish a Lipschitz property of the policy gradient. Next, we provide an intermediate Lemma 3 (see Appendix D for proof) crucial to establishing the main convergence rates to stationarity of Algorithm 1. Lemma 3. Under Assumptions 1 -3, value function J(θ) satisfies the smoothness condition for all θ 1 , θ 2 ∈ R d and M J is as defined in Lemma (2) with exploration tolerance λ as in (4.1). Now, we formalize the convergence rate for Algorithm 1 as Theorem 4.2. 3)] converges to stationarity: with problem-dependent constant L J defined in (E.7), and exploration tolerance λ as in Def. 4.1.

Theorem 4.2 (proof in Appendix E) establishes that the iteration complexity of Algorithm 1 is
where ζ is the accuracy parameter. This result contrasts the standard rate of O 1/ζ 2 for non-convex optimization [19], which restricts the policy parameterization to be Gaussian [17,102,50], i.e., α = 2. This means that heavy-tailed parameterizations result in slower convergence; however, we note that the rate of decrease of the expected gradient norm may not comprehensively encapsulate the non-convex landscape of value function. An additional subtlety is the effect of continuous action spaces, which are partitioned into sets where the score function is and is not bounded in accordance with the exploration tolerance parameter λ (Def. 4.1). In existing analyses of literature [102, 70,50], the effect of λ is assumed null (λ = 0), which overlooks the effect of action space coverage during policy search. Next, we establish that this perceived slower rate of heavy-tailed policies is overruled by their tendency towards local extrema with wider peaks, under a hypothesis that they admit a representation as a discretization of a Lévy Process.

Metastability and Convergence to Wide Peaks
We turn to characterizing (i) the time that Algorithm 1 takes to escape a (possibly spurious) local extremum, and (ii) how the proportion of time spent at a local maxima depends on its width and the policy's tail index. These results hinge upon introducing into RL for the first time of metastability of dynamical systems under the influence of weak random perturbations [95]. Similar results have been employed for SGD in the context of training neural networks in supervised learning [65,32]; however, it is unclear how one neural parameterization induces gradient noise whose distribution has a heavier from another. By contrast, here, this aspect is directly determined by the policy parameterization's tail index, which we choose in Algorithm 1. Moreover, in the aforementioned works, the analysis is only for the scalar-dimensional case, whereas here we consider dimension d > 1.
We begin then by rewriting (3.3) in terms of the true policy gradient and the stochastic error∇J(θ k )− ∇J(θ k ), with the noise process hypothesized as an α-tailed distribution, given by where, S k ∈ R d is SαS distributed random vector. Subsequently, we impose that the score function [cf. (3.1)] is dissipative (Assumption 6).
Hereafter, we rewrite discrete-time process θ k as θ k with superscript to disambiguate between continuous and discrete time.  Table 1: Summary of iteration complexity, exit time, and transition time results for vanilla PG and heavy-tailed PG, with as the jump process coefficient, and ζ as accuracy parameter for E[ ∇J(θ k ) ] ≤ ζ. Employing a policy with a faster tail probability decay rate such as a Gaussian (larger α) may take exponential time to escape a spurious local extrema, whereas a heavy-tailed policy escapes in polynomial time, as a function of the width a of the set containing a local maxima (4.8) and its escape direction (G.7).
with policy gradient steps are heavy-tailed, which is observed experimentally in [28]. In Sec. 5, we experimentally corroborate that policies induce gradient noise with a proportionate tail index (Fig. 2). The continuous-time analogue of (4.6), i.e., (θ k+1 − θ k )/η as η → 0, defines Stochastic Differential Equation (SDE) driven by an α−stable Lévy process as [95] where, := η α−1 α is a coefficient of the jump process (similar to diffusion coefficient in Brownian motion), and L α t denotes the multi-dimensional α-stable Lévy motion in R d . With these details in place, we impose some additional structure (Assumption 4) in Appendix G.1 on the non-convex landscape of the objective J(θ) in (2.1), namely, within the region of the objective's assumed finitely many local maxima, each one is separated by only a local minimum and no saddle points, as detailed in Appendix G.1. With the operating hypothesis that there are finitely many extrema of the objective, denote as G i ⊂ R d the neighborhood of the i-th local (arbitrary) maximizerθ i : where, a, ξ > 0 are scalar radius parameters, and ∂G i denotes the boundary of this neighborhood. Exit Time and Transition Time. We next define the metastability quantities of exit and transition time in both continuous and discrete-time, assuming that (4.7) and (4.6) are initialized at θ 0 ∈ G i . , respectively, to exit G i along standard basis vector r ∈ R d is defined byτ ξ,a ( ) inf{t ≥ 0 : θ t ∈ Ω + i (δ)}, andτ ξ,a ( ) inf{K ∈ N : Here, a and ξ denote scalar radius parameters [cf. (4.8)]. In the definition of exit time, Ω + i (δ) denote theδ ∈ (0, a + ξ) "tubes," i.e., escape directions, outside G i defined by Under the existence of a unit vector r along the direction connecting the domains G i and G i+1 between two distinct local maxima, we define the transition time from a neighborhood of one local maxima to another, i.e., from G i to G j , i = j in respective continuous-time [cf. (4.7)] and discrete-time (4.6), respectively, asT i ( ) = inf{t > 0 : The following theorems present the first exit time and transition time probabilities of the proposed heavy-tailed policy gradient setting, (3.3) when initialized within G i ⊂ R d such that (4.8) holds. Theorem 4.5. (Exit Time Dependence on Tail Index) Suppose Assumptions 1-7 hold, the value function J is initialized near local maximaθ i , and the policy gradient update in (3.3) is run under a heavy-tailed policy parameterization that induces tail index α in its stochastic error (4.6). Then, the likelihood of its exit time from neighborhood G i [cf. (4.8)] ofθ i larger than K is upper bounded as with initialization θ 0 , d + [cf. (G.7)] denotes distance between θ 0 and the boundary of G i , ρ ∈ (0, 1) is a positive constant and θ ∈ R d . Moreover, the Hölder continuity constant satisfies β ∈ (0, α − 1), δ > 0, ξ > 0, η is the step-size, k 1 := 1/η α−1 , and [cf. (4.7)] is the jump process coefficient.
See proof in Appendix H. Observe that as → 0 in (4.9), the right hand side of (4.9) depends on the distance of θ 0 from the boundary ∂G and tail-index α. Further, the dependence on d + (cf. (G.7)) implicitly hinges upon the width a of the neighborhood of the extrema (4.8), which noticeably decreases with heavier tails (smaller α), meaning that heavier-tailed policies increase the likelihood of escape and tend towards wider maxima. The intricacy of the expression precludes easy interpretation. Thus, consider the average exit time for the single dimensional case in Table 4.2, in which there exists only a single direction of exit, which coincides with [35,65]. In contrast to proposed heavy-tailed setting wherein exit time is a function of width of the neighborhood, exit time for PG under, e.g., a Gaussian parameterization, depends exponentially on the value at the extrema. Next, we discuss the transition time from one extrema to another. Theorem 4.6. (Transition Time Dependence on Tail Index) Suppose Assumptions 1-7 hold and the value function J is initialized near a local maximaθ i . Then in the limit → 0, the policy gradient update in (3.3) under a heavy-tailed parameterization with tail index α associated with its induced stochastic error (4.6), transitions from G i to the boundary of (i + 1)-th local maxima with probability, P θ0 (θ k ∈ Ω + i (δ) ∩ ∂G i+1 ) lower bounded as a function of tail index α: where δ > 0, escape distance from extrema are defined as Similar to exit time, the transition time probability [cf. (4.10)] (proof in Appendix I) depends on the width of boundary and the tail index, which noticeably also decreases for heavier tails (smaller α), and depends on the width of the neighborhood containing a local maxima. For ease of interpretation, the single-dimensional case for both vanilla PG and HPG are given in Table 4.2. Transition times are asymptotically exponentially distributed in the limit of small noise and scale with 1/ α for HPG, whereas transition time for Brownian is exponentially distributed with α replaced by exponential dependence e 2J(·)/ 2 for a Gaussian policy.
Thus, in the small noise limit, Brownian-motion driven PG needs exponential time to transition from one peak to another, whereas the Lévy-driven process requires polynomial time, illuminating that heavy-tailed policies quickly jump away from spurious extrema.

Experiments
In this section, we evaluate the proposed HPG (Algorithm 1) as compared to some common approaches for policy search. Before doing so, we demonstrate experimentally evidence that the heavy-tailed policies results in heavy tailed policy gradients. Then, we provides experiments for the Pathological Mountain Car (PMC) (Sec. 2) and 1D Mario environment [54]. Details of parameter selections are given in Appendix J.1, and additional experiments with continuous control environments are provided in Appendix J.2. In Fig. 2, we depict the estimation of tail index α (using method in [59]) for gradient estimates [cf. (3.3)] with a Cauchy and Gaussian policy. The lower the value of α the heavier the tail is of the policy gradient. In Fig. 2(a), we observe that the average estimate for the Gaussian policy settles to a value of one, while the corresponding value for Cauchy values settles around 0.2 for 1D Mario environment. A similar plot for PMC is in Fig. 2 Fig. 3, again for the 1D Mario environment and PMC is in Fig. 3. Fig. 3(a) presents the cumulative return for a test trajectory over the previous 100 episodes as a function of the number of training episodes processed for the fixed variance-parameter case in PMC. Observe that HPG outperforms approaches based on Gaussian policies. This trend continues for the variable-variance setting in PMC ( Fig. 3(b)), although the gap is less pronounced. This suggests that Gaussians with a variable variance can eventually escape a spurious policy, but more slowly than a Cauchy, providing experimental evidence of metastability  (Sec. 4.2). We also see this phenomenon in the 1D Mario environment ( Fig. 3(c)). We remark that the optimally turned TRPO is able to perform equally well as HPG in some instances but exhibit higher per iteration complexity due to challenge of solving trust region sub problem.

Conclusion
We focused on PG method in infinite-horizon RL problems. Inspired by persistent exploration that mitigates the tendency of policies to become mired at spurious behavior, we sought to nearly satisfy it in continuous settings through heavy-tailed policies. Doing so invalidated several aspects of existing analyses, which motivated studying the sample complexity of policy search when the score function is Hölder continuous and its norm is integrable with respect to the policy, and introducing an exploration tolerance parameter to quantify the degree to which the score function may be unbounded.
Moreover, we established that heavy-tailed policies induce heavy-tailed transition dynamics, which jump away from local extrema as formally quantified by the metastability characteristics of its Lévy process representation. We discerned that policies a heavier tail induce transitions away from a local extrema more quickly than one with a lighter tail, and tend towards extrema with more volume, which we empirically associated with more stable policies for a few RL problems in practice. The characterization of jumps defined by metastability provides a lens through which approximate persistent exploration may be satisfied in continuous space. [50] Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variancereduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33, 2020.
[ Alternatively, in continuous space, one may hypothesize the policy parameterization is a neural network whose size grows unbounded with the number of samples processed [96,49]. Doing so belies the fact that typically a parameterization has fixed dimension during training. Alternatively, one may impose a "transferred compatible function approximation error" condition that mandates the ability to sample from the occupancy measure of the optimal policy to ensure sufficient state space coverage [4,50], which is difficult to perform in practice.
Two additional lines of effort are pertinent to the objective of this work. Such representations can be used in, e.g., policy search [2,74] or value iteration [6] to obtain refined convergence behavior that depends only on the properties of the representation rather than the underlying state or action spaces. Finding this representation is itself not necessarily easier than solving the original MDP, however. See, for instance, [3,58], where a variety of structural assumptions and representations are discussed. In this work, we assume such a feature map is fixed at the outset of training as part of one's specification of a policy parameterization.
The other research thrust broadly related to this work is information-theoretic exploration that seeks comprehensive state-space coverage. The simplest way to achieve this goal is to simply replace the cumulative return with an objective that prioritizes state-space coverage, such as the entropy of the occupancy measure induced by a policy [77, 33,100]. This goal does not necessarily result in good performance with respect to the cumulative return, however. Alternatively, exploration bonuses in the form of upper-confidence bound [46,37], Thompson sampling [92], information-directed sampling [75], among other strategies (see [76] for a thorough review), have percolated into RL in various forms.
For instance, incorporating randomized perturbations/exploration bonuses into value iteration [66], Q-learning [39], or augmenting a policy's variance hyper-parameters in policy search in a manner reminiscent of line-search for step-size selection [68]. Alternative approaches based on Thompson sampling [30,67] and various Bayesian models of the value function [11,8] have been considered, as well as approaches which subsume exploration goals into the choice of the aforementioned state aggregator [2,58]. Our approach contrasts with approaches that inject suitably scaled randomness into an RL update, by searching over a policy class that is itself more inherently random. Proof. Consider the integral for the policy gradient from (3.1), we obtain From Assumption (1) and the definition of Q function, we note that Q π θ (s, a) ≤ U R 1−γ for any θ, s and a. Therefore we could upper bound the above integral as follows where we obtain (B.1) from Assumption 2 after applying the Jensen's inequality which implies that is the occupancy measure distribution for states s, we can obtain the following upper bound for the integral as

B.2 Proof of Lemma 1
Proof. Let us start by considering the stochastic gradient∇J(θ) as defined in (3.3) In order to relate the above expression to the true gradient, we introduce the infinite sum via the identity function notation 1 T ≥t and modify (B.2) as To interchange the limit and expectation in the above expression via Dominated Convergence Theorem in (B.3), we need first to ensure that the individual terms are dominated by an integrable function. To do so, we consider the term inside the expectation in (B.3) as which follows from the bound R(s t , a t ) ≤ U R . The sum on the right-hand side of (B.4) is integrable with respect to the occupancy measure via Assumption 2. Therefore, we may apply Dominated Convergence Theorem in (B.3) in order to exchange expectation and limit as follows Next, we note that since T ∼ Geom(1 − γ 1/2 ) which implies that P[T ≥ t] = γ t/2 , hence we can write After rearranging the order of summation in the above expression, we could write which is as stated in Lemma 1.

C Proof of Lemma 2
Before providing the proof for the statement of Lemma 2, we discuss an intermediate Lemma 5 provided next. Lemma 5. For any given (θ, θ ) ∈ R d , it holds that 1) the occupancy measure is Lipschitz continuous, which implies that 2) and the Q π θ is also Lipschitz continuous which satisfies Proof. Proof of statement (1). In order to bound the term ||ρ θ (s, a) − ρ θ (s, a)|| 1 , let us define a function d(θ, θ ) as follows Next, we evaluate the gradient of d(θ, θ ) with respect to θ and tale norm as We recall the definition of the occupancy measure and write where p(s t = s, a t = a | π θ , ξ(s 0 )) is the probability of visiting state s and a at the t th instant and ξ(s 0 ) denotes the initial state distribution. We write the explicit form of p(s t = s, a t = a | π θ , ξ(s 0 )) as p(s t = s, a t = a | π θ , ξ(s 0 )) = S×A ξ(s 0 ) · π θ (a 0 |s 0 )p(s 1 |s 0 , a 0 )× × π θ (a 1 |s 1 )p(s 2 |s 1 , a 1 )× . . .
We write (C.5) as After rearranging the above expression and adjusting the limits of integration, we can write where we first use the triangle inequality and then perform the standard log trick. Next, from the definition in (C.8), we evaluate ∇ θ log p θ (T t ) and obtain ∇ θ log π θ (a u |s u ) · p θ (s u , a u ) · ds u da u . (C.14) By Jensen's inequality, from Assumption 2, it holds that A ∇ θ log π θ (a | s) · π θ (a | s)da ≤ √ B. Hence, we can write (C.14) as where we have used the fact that arithmetic-geometric sequence ∞ t=0 (t + 1)γ t = γ (1−γ) 2 . Since the gradient of function d(θ, θ ) with respect to θ is bounded, it implies that d(θ, θ ) is Lipschitz with respect to θ, which further implies that 16) for all θ, θ ∈ R d . Next, substituting the definition from (C.3) into (C. 16) and noting that d(θ , θ ) = 0 , we get which is as stated in Lemma 5(1).
Proof of statement (2). Let us define the occupancy measure, γ t · p(s t = s , a t = a | π θ , s 0 ∼ p(·|s, a)) (C. 18) where the initial state s 0 ∼ p(·|s, a). With the help of occupancy measure µ sa θ (s , a ), we could write the Q π θ function for state action pair (s, a) as Using the definition in (C.19), we can write Utilizing the upper bound in (C.17), we can write Using the definition in (C.19), we can write as stated in Lemma 5(2). Now we shift focus to prove the statement of Lemma 2 as follows.
Proof of Lemma 2. To obtain a bound on the gradient norm difference for J, we start by considering the term ∇ θ J(θ 1 ) − ∇ θ J(θ 2 ) and expanding it using the definition in (3.1), we get − S×A Q π θ 2 (s, a)∇ log π θ2 (a|s)ρ π θ 2 (s, a)ds da .
(C.36) From (4.2) and the definition of · 1 , we can write
(C. 38) Let us focus on the second term Z of the right-hand side of (C.38). We expand its expression using (4.1) as Z = S A\C ∇ log π θ2 (a|s) · ρ π θ 1 (s, a)ds da + S A\C ∇ log π θ2 (a|s) · ρ π θ 2 (s, a)ds da. (C.39) Next, from the Hölder continuity of the score function, by adding and subtracting ∇ log π θ1 (a|s) inside the norm for the first term, we may write (C.40) Substituting (C.40) into the right hand side of (C.38), we get (C.41) Next, substituting the upper bounds for I 1 , I 2 , and I 3 into the right hand side of (C.24), we get where M J is defined as (C.42) which concludes the proof of Lemma 2.

D Proof of Lemma 3
Proof. The proof technique is motivated from the analysis in [64]. Consider a curve g(t) J(θ 2 + t(θ 1 − θ 2 )). Then g (t) = ∇J(θ 2 + t(θ 1 − θ 2 )), θ 1 − θ 2 . The integral of g (t) from t = 0 to t = 1 can be expressed as by the Mean Value Theorem. Now subtracting ∇J(θ 2 ), θ 1 − θ 2 on the both sides of the above expression, we get Using the expression for g (t) above expression takes the form Using Cauchy-Schwartz inequality for inner product on the right-hand side of the previous expression 3) Apply Lemma 2 to the first factor of the integrand on the right-hand side, which simplifies the preceding expression to ) which is as stated in (4.4).

E Proof of Theorem 4.2
Proof. We begin by unraveling the statement of Lemma (3) to write an approximate ascent relationship on the objective J(θ) as: For c = 1, 1 + β, 2, using Assumption 1 along with the Jensen's inequality indicates that Applying the Jensen's inequality again, we can write Taking the expectation on both sides in (E.4), we have Taking expectation on the both sides of (E.2) conditioning on θ k , denoted as E k and utilizing the bound in (E.5), gives After rearranging the term and defining, we can write (E.6) as Let J * be the optimal function value, then it holds that J(θ k+1 ) ≤ J * . Calculating the total expectation in (E.6) and taking sum from k = 0, . . . , K − 1, we get Divide both sides by K, we get Now we specify the step-size as a constant η = c . Doing so permits us to rewrite (E.11) as follows where we define the constant a β = (2L J ) 1/(β+1) (J * − J(θ 0 )) β/(β+1) , as stated in (4.2). Observe that in existing analyses in the literature[102], the O(λ) term is assumed to be null. Thus, standard rates are recovered as a special case.

F Instantiations of λ in Example 2.1-2.3
In this section, we discuss about the parameter λ in detail. Note that the specific value of delta would depend upon the policy class being considered. Therefore, we derive the values of λ for Example 2.2-2.3 (Example 2.1 is special case of Example 2.2 for α = 2).
(1) We start with the Example 2.3, for which we note that the score function is absolutely bounded over the full action space A. For this case, then, λ = 0 and B(λ) exists and is finite.
(2) For the moderate tail case (Example 2.2), note that the policy distribution is given by Therefore the score function could be written as as long as the feature map is bounded as φ(s) ≤ D φ . Suppose θ belongs to some compact set Θ. Let us construct the set C as where R is a finite positive constant. Now, let us look at the following integral A\C ∇ log π θ (a|s) · π θ (a|s) · da which follows from the upper bound in (F.2). From the definition in (F.1), we can write A\C ∇ log π θ (a|s) · π θ (a|s) · da where B α := |a| α−1 exp{− |a| α 2 } < ∞. The above equation will be less than λ if we have The above expression provides the bound for B(λ) as where D Θ := max θ,θ ∈Θ θ − θ is the diameter of Θ. Note that the bound in (F.7) is small even for a very small value of λ. This permits us to relax the standard assumption of absolutely bounded score function for continuous action spaces.

G Exit Time Analysis
We first present the technical preliminaries required for the analysis in this section as follows.

G.1 Technical Preliminaries
We begin by stating a few technical assumptions which are required for the theorems presented in Section 4.2. The first is regarding the non-convex landscape of J and the later is regarding the Lévy jump process in (4.7). AS4. Following statements holds for function, J: 2. The function J possesses the strict-saddle property, i.e., all its local maxima satisfy ∇ 2 J(θ) ≺ 0 and all its other stationary points satisfy λ min (∇ 2 J(θ)) > 0.
3. The difference (L α t − L α s ) and L α t−s have the same distribution: SαS(t − s) 1/α for s < t. 4. L α t is continuous in probability: for all δ > 0 and s ≥ 0, P(|L α t − L α s | > δ) → 0 as t → s. We also first present an additional condition we require on the score function. AS6. For some m > 0 and b ≥ 0, ∇ θ log π θ (·) is (m, b, c)-dissipative, which implies that  .7)]. We denote the first exit time for continuous SDE usingτ (·). Under the Assumption 4 (3.), we invoke results from [35] for the first exit times of continuous SDEs (4.7) in the univariate case d = 1.
Further, we impose that the multi-dimensional Lévy motion L α t in (4.7) admits a representation as a L α t = rL t with r ∈ R d as a standard basis vector in d-dimensions, which determines the direction of the jump process, and L t is a scalar α-stable Lévy motion. This restriction is needed in order to tractably study the transient behavior of (4.7) in terms of its exit time from regions of attraction [36], specifically, in applying Lemma 10, as well as characterizing the proportion of time jumping between its limit points, to be discussed next. We note that such analyses for general d-dimensional Lévy motion is an open problem in stochastic processes. Theorem G.1. [35] Consider the SDE (4.7), in the univariate case d = 1 (θ ← θ) and assume that it has a unique strong solution. Assume further that the there exists an objective J with a global maximum at zero, satisfying the conditions J (θ)θ < 0 for every θ ∈ R, J(0) = 0, J (θ) = 0 if and only if θ = 0 and J (0) < 0. Then, there exist positive constants 0 , γ, δ, and C > 0 such that for 0 < ≤ 0 , the following holds in the limit of small : uniformly for all θ ≤ a − γ and u ≥ 0. Consequently uniformly for all θ ≤ a − γ . Theorem G.2.

The mean of first exit time is given by
3. Normalized first exit time is exponentially distributed: for u ≥ 0 uniformly in θ on compact subsets of (−b, a).
Note that the above results hold for continuous SDEs in one dimensional space. Next we present extend the exit time results from a domain G i ⊂ R d around i-th local maxima of J(·),θ i [36] with an assumption that the system is perturbed by a single one-dimensional Lévy process with α-stable component.
Before moving to multi dimentional case, we redefine the exit time and transition time here for the quick reference.
Exit Time and Transition Time. Let us now formally define the meta-stability characteristics, namely exit time and transition time in continuous time and then extend it to the the proposed heavy-tailed setting with the assumption that (4.7) and (4.6) are initialized at θ 0 inside G i . Definition G.3. (Exit time from G i ) The time required for the continuous-time process (4.7) and discrete-time process (4.6), respectively, to exit G i along standard basis vector r ∈ R d is defined bŷ Here, a and ξ denote scalar radius parameters (cf. (4.8)). For all (θ −θ i ) at a distanceδ from ∂G i , we define its distance to ∂G i along standard basis vector r ∈ R d , where r is as in (4.7) with L α t = rL t in terms of the lines in R d as g i θ (t) = θ −θ i +t·r for t ∈ R. Then, for all θ −θ i <δ,δ ∈ (0, a+ξ), the distance function to the boundary along r is defined as where (G.7) define distance between any point of interest and the boundary of domain along the unit vector, r, we have g i θ (t) / ∈ G i for t / ∈ (d − (θ), d + (θ)) for all i. We say the point exits the domain G i in the direction r when it enters theδ-tubes outside G i defined by We underscore thatτ (·) represents the exit time of discrete-time process θ k , whereasτ (·) denotes that of continuous-time stochastic process θ t . Definition G.4. (Transition time from G i to G j ) Under the existence of a unit vector r along the direction connecting the domains G i and G i+1 between two distinct local maxima, we define the transition time from a neighborhood of one local maxima to another, i.e., from G i to G j , i = j in respective continuous-time [cf. (4.7)] and discrete-time (4.6) Multi-Dimensional Case d > 1. Before proceeding to the the statement of results and proofs, we define assumptions and terminologies associated with the multi-dimensional space, i.e., subsequently θ ∈ R d . The reason for separately stating the scalar case and the multi-dimensional case, is that results and conditions for the scalar-dimensional case are invoked in generalizing to the multi-dimensional case, specifically, in Lemmas 8 and 9. For simplicity, we assume the tail-index (α) of perturbations are identical in all the directions. The dynamical system of (4.7) when perturbed by single dimensional Lévy process is given by where, r ∈ R d is the unit vector.
We impose the following structural assumption on G i [cf. (4.8)] such that desired properties for a domain perturbed by a Lévy noise in multi-dimensional space holds [36].
AS7. The following assumptions hold for G i : 1. We denote by Ω i := {θ ∈ R d : θ = t · r∀t ∈ R} the straight line in the direction of r. Let ∇J(·) :Ḡ → R d and the setḠ ∩ Ω is connected.
2. The boundary of G i defined by ∂G i is a C 1 -manifold so that the vector field n of the outer normals on the boundary exists. We assume for all θ ∈ G i . This means that ∇J(·) points into G i .
3. Local extrema,θ i is an attractor of the domain, i.e. for every starting value θ ∈ G i , the deterministic solution vanishes asymptotically.
4. There exists atleast one set of domains, We assume existence of a local minima at the intersection of ∂G i and ∂G j .
We define the inner parts of G i by G iδ := {z ∈ G i : dist(z, ∂G i ) ≥δ}. Therefore, the following holds: Sets Gδ are positively invariant for allδ ∈ (0, a + ξ) (cf. (4.8)), in the sense that the deterministic solutions starting in Gδ do not leave this set for all times t ≥ 0. We have The preceding statements follows from [36]. Next we state exit time results from the domain, G i for a system defined by (G.10).
Furthermore, for everyδ ∈ (0,δ 0 ) the probabilities to exit in direction ±r are given by for all θ t ∈ G and d + and d − define distance from boundary of interest ∂G i along ±r.
The above expression is obtained by using a single r in (3.4) of [36]. It is to be noted that for a general process perturbed by finitely many single dimensional Lévy processes with different tail indices, the exit time depends on the smallest tail-index, and the system exits from the domain in the direction of the process with smallest α i .
In this section we derive the first exit time behavior for the proposed heavy tailed setting of Algorithm 1. We proceed by defining some key quantities of interest and lemmas used in the proof of Theorem 4.5. The first is the Itô formula for stochastic differential equations, and then we present the Bellman-Gronwall inequality.
Definition G.6. (Itô formula) [99] Let N be a Poisson random measure with intensity measure dtν(dz), where ν is a Lévy measure on R d , ie., R d (|z| 2 ∧ 1)ν(dz) < +∞, ν({0}) = 0. The compensated Poisson random measure N is defined as N (dt, dz) := N (dt, dz) − dtν(dz). Consider the following SDE in R d with jumps: where R > 0 is a fixed constant. Suppose g(x) ∈ C 2 (R) is a twice continuously differentiable function (in particular all second-partial-derivatives are continuous functions). Suppose Y t = g(X t ) is again an Itô process, then we have where M t is local martingale, L bt 1 is the first order differential operator associated with drift (b t ), and L g ν h is the non-local operator associated with jump coefficient g() such that: Next we provide a lemma regarding the difference between a Lévy process with two different tail indices α and kη. Lemma 6.
[91] For any u > 0, η > 0 and K ∈ N, there exist a constant C α such that: and Next we state a stochastic variant of Gronwall's inequality which is also used in the proof. Lemma 7. Stochastic Gronwall's inequality [78] Let Z and H be nonnegative, adapted processes with continuous path and assume that ψ is nonnegative and progressively measurable. Let M be a continuous local martingale starting at 0. If holds for all t ≥ 0, then for p ∈ (0, 1) and µ and ν > 1 such that 1 µ + 1 ν = 1 and pν < 1, we have where, a real valued process Y * (t) := sup 0≤s≤t Y (s).
Next we provide a bound on the second moment of parameter vector θ when integrated with respect to Lévy measure ν. Lemma 8.
[91] Let ν be the Lévy measure of a d-dimensional Lévy process L α whose components are independent scalar symmetric α-stable Lévy processes L 1 , . . . , L d . Then there exists a constant C > 0 such that the following inequality holds with k 1 ≥ 1 and 2 > α > 1: 1 Given the Assumptions 1-5 and the proposed Heavy tailed setting of (4.6), for λ ∈ (0, 1), θ ∈ R d , there exists constants C 1 and C 2 depending on λ, dissipativity constants (m, b), and θ 0 , the following holds on the expected value of θ for all t > 0 such that where (m, b) are the dissipativity constants from Assumption 6 and k 1 is a function of stepsize η, Proof. Here we derive an upper bound on E sup s∈[0,t] ( θ s ) λ for the heavy-tailed policy gradient setting of (4.6) perturbed by a single dimensional Lévy process in the direction of unit vector r. We build up on the existing results from [91, 99] for Lévy process and SDE. Using Itô formula, the whole expression is divided into two terms. We simplify the second term using properties of a Lévy process from [91, 99]. Further we build upon the heavy-tailed setting and its properties such as dissipativity of score function and Hólder continuity to simplify the first term. Further the combined expression is simplified using direct application of stochastic Gronwall's inequality. We start with the continuous equivalent of (4.6) defined by dθ t = b(θ t− )dt + k −1/α 1 dL α t (t − denote left limit of the process) and k 1 := 1/η α−1 (k 1 is always greater than 1 as η α−1 < 1), we use F = −J for simplicity, b(·) := −∇F (·) using (4.7). Note that this representation is equivalent to (4.7) and helps to invoke some of the existing results in the analysis. Here the direction of perturbation r is absorbed into L α t without the loss of generality (cf. (G.10)). In order to upper bound E sup s∈[0,t] ( θ s ) λ , we start by defining a function, g 1 (θ) (1 + θ 2 ) 1/2 . Using direct application of Itô's formula from Definition G.6 with jump coefficient g being k −1/α 1 , we can write Itô formula for (4.6) as follows (G.23) here, M (t) is defined as local martingale and ν be the Lévy measure of a d-dimensional Lévy process L α . We have ∂ i g 1 (θ) = θ i (1 + θ 2 ) −1/2 /2.
Next we unfold the expressions for T 1 and T 2 using the expression for the policy gradient in (3.3).
Expression for T 1 : Expression for T 1 along with the policy gradient of (3.3) takes the form Now using Assumption 1 to upper bound Q π θ (s, a) , expression reduces to The expression, T 3 is simplified using (m, b, β)-dissipative assumption of Assumption 6 (T 3 = − ∇ log π θ (s, a), θ ≤ −m θ 1+β + b). Unfolding the expectation operator defined with respect to the occupancy measure of the MDP under policy π θ allows us to write The integral S×A (1 − γ)ρ π θ (s) · π θ (a|s) ds da from the preceding expression is a valid probability measure and hence integrates to unit. Therefore, we can simplify the right-hand side as Adding and subtracting m inside T 4 gives 29) In order to simplify the term T 5 , we evaluate (1 + θ 2 ) β1 .
Expression for T 2 : Similarly, we analyze the second term, T 2 . Note that T 2 does not depend on the heavy-tailed gradients and simplification is based on the standard results on properties of Lévy process from [99]. We get Note that the above expression is a standard result for Lévy process ([99], Expression 7.6). Using Lemma 8 on the right-hand-side inequality, we get Using (G.38) and (G.41) in (G.23) and integrating the expression from 0 to t gives The above expression can be simplified using Gronwall's inequality for stochastic equations ( where, ν > 0, c pν := (4 ∧ 1 pν ) sin πν πpν (Proposition 1, [78]). Now for λν < 1, p ∈ (0, 1) from Lemma 7, we get where, c λ := (c pν + 1) λ . As we have g 1 (θ) ≥ θ , the above inequality is lower bounded by E sup s∈[0,t] θ ) λ and we get (G.46) where C 1 and C 2 are positive constants depending on c λ and Eg 1 (θ 0 ).
The following lemma upper bounds the error between (4.6) and its continuous time equivalent SDE (4.7) for t ∈ [kη, (k + 1)η] and derives its probabilistic interpretation. Note that this result is useful in translating exit time results for the proposed setting as defined in Theorem 4.5. Lemma 10. Given the proposed heavy-tailed setting of (3.3) is initialized at θ 0 with step-size η : (exp (M J η)η(B + M J ) ≤ ξ/3) , ξ > 0, there exist a set of positive constants C α , C 1 , and C 2 such that the following holds Proof. In order to upper bound the error between the discrete and continuous equivalents, we start by analyzing the difference in dynamics for t ∈ [kη, (k + 1)η] and t = kη. Using the continuous equivalent (G.10) and integrating the expression over 0 to t gives For t = kη, ie., the beginning of the interval considered, we have Using the above two expressions, θ t − θ kη takes the form Here θ u denotes θ t (u), r is the unit vector defining the direction of perturbation. We are interested in the dynamics when t ∈ [kη, (k + 1)η). Adding and subtracting ∇J(θ kη ) inside the integral of the above expression yields Next, Apply Lemma 2 and the Hölder continuity of the policy gradients inside the integral to write: By employing Hölder continuity and Cauchy Schwartz inequality for the second term, we obtain Using ∇J(0) ≤ B in the above expression, we get Substituting (G.54) for the second term of (G.52) results in For β < 1, θ u − θ kη β < θ u − θ kη + 1. This fact allows us to rewrite the above expression as (G.56) Evaluating the maximum of the above expression in the interval k ∈ [0, As we are interested in evaluating the probability of θ t − θ kη ∈ B C (cf. (H.8)), consider the cases where error between continuous and discrete process exceeds ξ , ie., Now with the assumption that each term on the right hand side of (G.57) contributes equally, we have Next we evaluate the probability that the above expression holds given the process is initialized at θ 0 From Markov's inequality, we can write Using Markov's inequality for first term on the right hand side of (G.60) gives Using the choice of η such that (exp (M J η)η(B + M J )) is always less than ξ/3, second term of the right hand side inequality equals to zero. Using properties of Lévy process from Lemma 6 (Lemma 3, [91]), the last term of the above inequality simplifies to Using the above expression in (G.62) Now the expression for E max 0≤k≤K−1 θ kη ) β can be obtained by the direct substitution of inequality from Lemma 9. Therefore, we get where β ∈ (0, 1), U R is the upper bound on the reward function from Assumption 1, constants C 1 and C 2 depends on β, dissipativity constants (m, b), and tail index α, k 1 := 1/η α−1 .

H Proof of Theorem 4.5: Exit time Analysis for Heavy-tailed Policy Search
Next, we present results on the first exit time for the proposed heavy-tailed policy gradient setting.
Proof. We start along the lines of [83, 91, 95] and relate the proposed setting of (4.6) to the continuous SDE of (4.7). We define the set of K points, k = 1 . . . , K obtained from (4.6) which are at a maximum distance of a from the local maxima of interest,θ i is defined as Next we define a set N a as the neighborhood in Euclidean distance centered atθ i : As we initialized both discrete and continuous process at θ 0 , processes defined by (4.6) and (4.7) are considered close enough if both of their exit times from N a are close. For the moment, we assume step-size η k = η is constant, and consider the linearly interpolated version of (4.6) given by Note that the unit vector direction of perturbation is absorbed into dL t α (cf. (G.10)). Here,θ = {θ t } t≥0 denotes the whole process with drift term, b defined as (H. 4) where I denotes the indicator function such that I = 1 if t ∈ [kη, (k + 1)η). The above expression for the drift (deterministic) component of the continuous-time process can also be expressed as First exit time of a continuous SDE (4.7) is summarized in Theorem G.5 [36]. To invoke this result, we first more rigorously establish the connection between the exit times of the discrete [cf. (4.6)] and continuous-time [cf. (4.7)] processes. Then, we may invoke this result to obtain the desired statement associated with the heavy-tailed policy search scheme in discrete time given in (4.6).
For the time being, we assume the distance (divergence) between the underlying distributions of processes (4.6) and (4.7) sampled at discrete instants, η, kη, . . . .., Kη is bounded by δ. Since (H.3) is the interpolated version of (4.6), this sampling specification also implies that there exists an optimal transport plan or optimal coupling between {θ s } s∈[0,. Next we relate the expressions for the exit time of continuous and discrete-time processes, (4.6) and (4.7), respectively. Let {θ s ∈ A, for k = 1, . . . , K}. Asθ s is the linearly interpolated version of the discrete process defined by (4.7) we get θ 1 , . . . , θ K ∈ A. The statement θ 1 , . . . , θ K ∈ A implies exit timeτ of the discrete process from a domain characterized by a is greater than K, P(τ 0,a ( ) > K). Therefore, using (H.6), the following events can happen with a probability dependent on δ if we havē τ 0,a ( ) > K θ t ∈ A for t = η, . . . , Kη / ∈ A : with probability < δ This fact allows us to write the probability ofτ 0,a ( ) > K for some constant K as follows: Note that ((θ η , . . . , θ Kη ) ∈ A) implies maximum distance from local minimum is a.
Now we have an expression connecting the probability for continuous time processes, θ t at t = kη, k = 1, . . . , K being inside A to the exit time of discrete equivalents given both of them are initialized with same value. However, the identity of continuous random variables θ t between [kη, (k + 1)η] are still unknown. To understand their behavior within this range, we study their behavior to sets N a [cf. (H.2)]. Once we augment that into (H.7), we are in the position to derive for exit time results for discrete process in terms of its continuous equivalent. These steps are formalized next.
We define a set B such that For a clear understanding of the process, we illustrate the previously defined sets in Fig. 4 Let A defines a hyper sphere with K points θ k ∈ R d from discrete process (4.6). The radius of A is defined by a andθ i be its center. Now we have another hyper sphere (shown in gray), B of Figure 4: Sketch of intuition for the analysis of the exit time behavior of the discrete time process. We study the behavior of discrete and continuous process initialized at same point. On the left we depict N a , the neighborhood of the local extrema for a generic element θ ∈ R d with respect to which we study the exit time behavior. In order to do that we first analyze the behavior of the continuous-time process at discrete time indices which is piecewise constant within intervals t = η, · · · , Kη within a neighborhood of local maximumθ i defined in Assumption 7 (3.). This interpolation process bridges the gap between the continuous-time process and the discrete time process. On the right we depict an equivalent neighborhood for the discrete-time process. We show that the probabilistic behavior of the continuous and discrete neighborhoods are comparable up to constant factors that depend on algorithm step-size and interpolation parameters (cf. (H.7)). Characterizing this probabilistic behavior does not bound the behavior of the continuous process between the instants t ∈ [kη, (k + 1)η]. To do so, we introduce event B and study the behavior of continuous process between [kη, (k + 1)η] (Lemma 10). Now relating events A ∩ B and B c , we obtain an upper bound on the exit time of discrete process.
Therefore, the first term of the inequality (H.12) corresponds to the time at which θ exits G i , i.e., the time at which θ ∈ Ω + i (δ). Note that the probability defined in the above expression is in terms of the time at which the process exits a given domain, i.e. the probability that the exit time is greater than Kη. Using Assumption 7, there exists a K such thatτ ξ,a greater than Kη, K > 0 and θ τ ∈ Ω + i forτ ξ,a ( ) ≥ Kη (meaning, probability that the exit time is greater than Kη is proportional to the probability of the process entering the desired delta tube), specifically, that P(τ ξ,a ( ) ≥ Kη) ∝ P θ0 θ τ ∈ Ω + i (δ) . Therefore, substituting P(τ ξ,a ( ) ≥ Kη) with P θ0 θ τ ∈ Ω + i (δ) in (H.12) allows us to write P θ0 (τ 0,a ( ) > K) ≤P θ0 θ τ ∈ Ω + i (δ) where, P θ0 θ τ ∈ Ω + i indicates the first exit time for a continuous SDE from G i . Note that Ω + i (·) indicates delta-tube outside the boundary of G i with perturbations along the positive basis vector. Now direct application of Theorem G.5 for the first term on the right-hand-side of the inequality, we get where, d + denotes distance function to the boundary along the positive r unit vector (cf. (G.7)), ρ is a positive constant such that ρ ∈ (0, 1), a + ξ > 1−ρ , d is the dimension of θ, Hölder continuity constant, β ∈ (0, 1), δ > 0, C α > 0, ξ > 0, η is the step-size, U R , γ are the parameters of proposed RL setting, positive constants, C, C 1 C 2 , are functions of dissipativity constants of score function. Note that first term of the above inequality denotes the probability that the stochastic process exits from a given domain G i when perturbed by a jump process along unit vector r with tail index α.
Observe that the exit time is only a function of distance between the point at which the process is initialized and the boundary of the domain around local minima (extrema), but does not depend on the function values (height of the local minima (extrema)).
I Proof for Theorem 4.6: Transition time for the Proposed Heavy-tailed setting In this section, we derive transition time results for the proposed heavy-tailed setting from one local maxima to another as defined in Theorem 4.5. Suppose the domain G i satisfies the Assumption 7 defined in Section 4.2. Further there exists a unit vector, +r in the direction connecting the domains G i and G i+1 and we define the distance function to the the intersection of boundaries G i and G i+1 by: Let θ 0 ∈ G i . As is a coefficient that multiplies the noise process in (4.7), it is clear that the error between both the processes are lower bounded by , ie. θ k − θ kη > . Using Markov's inequality, the above statement can be expressed in the language of probability as Let us say the probability of above event given θ 0 = θ 0 is δ/2. Given the continuous time instant t = kη, there exists a unit vector, r in the direction connecting the domains G i and G i+1 . and let θ kη ∈ Ω + i (δ) ∩ ∂G i+1 , ∀δ ∈ (0,δ 0 ), the following events can happen with probabilities dependent on δ: The above case-by-case study illuminates that either θ k ∈ Ω + i (δ) ∩ ∂G i+1 or θ k / ∈ Ω + i (δ) ∩ ∂G i+1 (for which the probability adds up to δ). Note that Ω + i (δ) denotesδ-tubes outside of G i (cf. (G.8)). This fact allows us to write the probability that θ kη ∈ Ω + i (δ) ∩ ∂G i+1 as follows: Evaluating the above inequality in the limit of → 0 yields Observe that the probability that θ k / ∈ Ω + i (δ) ∩ ∂G i+1 is δ. Note that the value of δ can be obtained analyzing KL-divergence between underlying distirbutions of (4.6) and (H.3), the interpolated version of (4.6). The consequence of the aforementioned analysis is an upper bound on the step-size, η (See Assumption 6, [83]). Now the expression on the left-hand side of the above inequality is the probability that the process reaches to the intersection ofδ tube and G i+1 in the limit → 0.
Using Theorem G.5, for everyδ ∈ (0, a + ξ) the probabilities to exit in direction ±r are given by for all θ t ∈ G i and where d + ij and d − ij define distance from θ 0 to Ω + i (δ) ∩ ∂G i+1 along r. Now using the above expression in (I.5) yields lower bound on the transition probability from G i to G i+1 , P θ0 (θ k ∈ Ω + i (δ) ∩ ∂G i+1 ) in the limit → 0 (I.10)

J Supplemental Experiments J.1 Additional Details of Experiments
For the experiments presented in Sec. 5, we have considered two environments namely namely Pathological Mountain Car (PMC) of Fig. 1 and 1D Mario [54]. For PMC, we consider an incentive structure in which the amount of energy expenditure, i.e., the action squared, at each time-step is negatively penalized and the reward structure is given by  Each episodes are initialized at s 0 = 0. Before moving to the additional set of experiments, we first summarize the tail-index estimation part here which is shown in Fig. 2.
Tail index estimation. In Fig. 2, we established the fact that the heavy tailed policy parameterization results in heavy tailed policy gradients via plotting the estimation of α for the policy gradients. We utilized the logic presented in [59] for the α estimation reiterated here in the form of Theorem J.1 for quick reference. Theorem J.1. [59] Let {X i } K i=1 be the collection of random variables with X i ∼ SαS(σ) and . Then the estimator 1 α converges to 1 α almost surely as K 2 → ∞.
Note that {X i } corresponds to the samples from policy gradient estimates. The aforementioned approach has been employed recently for estimating the tail-index of stochastic gradients [28,83]. Next, we present the additional experiments results corroborating the findings in the main paper.  Fig. 6(a), we evaluate the performance on PMC environment when the scale of the HPG is a constant σ = 3.0 and the variance of Gaussian policy is also fixed σ = 3.0. Secondly, we present the results with variable scale σ for PMC and 1D Mario environments in Fig. 6(b)-6(c). All the experiments use a discounted factor of γ = 0.97 and we use a diminishing step-size ranging from 0.005 to 5 × 10 −9 . All the simulations are performed for 1000 episodes using a batch size of B k = 5 and with cumulative returns averaged over 100 episodes. For the comparison with PPO, the policy ratio for PPO is allowed to vary in the interval [1 − 1 , 1 + 1 ] with 1 = 0.2. Note that a fined tuned value of 1 can result in a better performance as shown in Fig. 6(b). However, note that the best performance feasible for PPO is same as that of PG. The trust region parameters for TRPO, aka. maximum KLdivergence allowed is set to 0.001. In addition, here we also evaluate performance of the HPG against Stochastic Variance-Reduced Policy Gradient (SVRPG) ( [69]). The number of epochs for SVRPG is fixed to 1000 and epoch size,  Single episode occupancy measure for for PMC with PG. Overall, we may observe that a Gaussian policy results in an occupancy measure which exhibits diffuse probability across the state space, failing to concentrate around actions associated with higher reward, whereas the heavy-tailed distribution results in an occupancy measure that assigns high likelihood to a small number of extreme actions in a manner reminiscent of the "black swan" phenomenon [89]. σ = 5, 3, respectively. For the experiments in Fig 6, we use a simple network without hidden layers. From meta stability results of Section 4.2, it is the nature of jumps initiated by heavy tailed policies which results in better meta stable characteristics and results in faster escape from spurious local extrema. In order to establish this fact, we plot the single test episode state visitation frequency (aka single episode occupancy measures) of HPG and PG once the training is done. The test episode is initialized at s = 2.26 (neighborhood of local extrema) and states of the environment s ∈ [−4, 3.709] are discretized into 100 states and the heatmap of of the state visitation frequency is shown in Fig. 7.

J.2 Additional Experimental Instantiations
Next, we evaluate the performance of the proposed algorithm on more complex environments from OpenAI gym and Roboschool, namely Inverted Pendulum from Roboschool and sparse versions of Roboschool REACHER-V2 & HALFCHEETAH-V2.

J.2.1 Inverted Pendulum
Next, we evaluate the performance of HPG on Inverted Pendulum-v1 from Roboschool in Fig. 8(c). The objective is to keep the pendulum balanced while keeping the cart upon which it is mounted away from the borders. Environment consists of a observation space of dimension 5 and an action space of dimension 1. Here we use a neural network with single hidden layer consisting of 64 neurons. All the other parameters are same as given in the previous experiments.

J.2.2 Sparse Variant of HalfCheetah
The environment consists of planar biped robot in a continuous environment with S ∈ R 26 and A ∈ R 6 . The task runs on the Roboschool simulator. In the task, the agent is a two-dimensional cheetah controlled by seven actuators. The state representation corresponds to the position and velocity of the cheetah, current angle and angular velocity of its joints as well as the torque on the actuators. The reward function in this environment is a mixture between the amount of contact the limbs have on the floor and the displacement of the agent from the starting position. The reward structure is made sparse by removing the control penalty to each actions. In addition, a step reward of 2 is provided when the x-component of speed of the Cheetah is greater than 2 as in [54]. We plot the initial average cumulative returns for sparse Chettah over latest 25 episodes in Fig. 8(d). Observe that HPG, by virtue of its extreme action selection according to a heavy-tailed distribution, causes more jumps in the state space, which results in better exploration of the environment. The result is faster policy improvement than vanilla PG.

J.2.3 Sparse Variant of Roboschool Reacher
The environment consists of an robot arm in a 2D space which tries to reach a target. Reacher is a continuous environment with S ∈ R 9 and A ∈ R 2 . A sparse variant of REACHER-V2 is created by imposing a step reward of 1 when the distance between the arm and the target is less than 0.06, and 0 otherwise [54]. The target is fixed to a position of [0.19, 0] and removed distance to the target from the observations. In addition, the reward structure is sparsified by removing the control penalty. We implement the proposed algorithm using policies with α = 1, 2. Here we choose the mode of the policy: S → A to be a neural network that has two hidden layers. Each hidden layer consists of 10 neurons with tanh being the activation function. Other parameters of the Algorithm are same as the previous experiments. Fig. 8(e) shows that HPG, by virtue of its extreme action selection according to a heavy-tailed distribution, causes more jumps in the state space, which results in better exploration of the environment. The result is faster policy improvement than vanilla PG. We plot the initial average cumulative returns for sparse Chettah over latest 25 episodes. Observe that HPG better explores the environment and shows improved performance over PG. (c) We plot the initial average cumulative returns for sparse Reacher over latest 25 episodes for HPG which shows better ability to explore over PG. For clarity of only distinguishing the performance differences associated with policy parameterization, we omit the additional comparators of Figure 6.