arXiv:2605.10909v1 [cs.LG] 11 May 2026
Revisiting Policy Gradients for Restricted Policy Classes: Escaping Myopic Local Optima with k-step Policy Gradients
Alex DeWeese Guannan Qu Department of Electrical and Computer Engineering Carnegie Mellon University Pittsburgh, PA 15213-3890, USA {mdeweese, gqu}@andrew.cmu.edu
Abstract This work revisits standard policy gradient methods used on restricted policy classes, which are known to get stuck in suboptimal critical points. We identify an important cause for this phenomenon to be that the policy gradient is itself fundamentally myopic, i.e. it only improves the policy based on the one-step Q-function. In this work, we propose a generalized k-step policy gradient method that couples the randomness within a k-step time window and can escape the myopic local optima in MDPs with restricted policy classes. We show this new method is theoretically guaranteed to converge to a solution that is exponentially close in performance to the optimal deterministic policy with respect to k. Further, we show projected gradient descent and mirror descent with this k-step policy gradient can achieve this exponential guarantee in O( T1 ) iterations, despite only assuming smoothness and differentiability of the value function. This will provide near optimal solutions to previously elusive applications like state aggregation and partially observable cooperative multi-agent settings. Moreover, our bounds avoid ∗ ∗ the ubiquitous distribution mismatch factors ||dπµ /dπµ ||∞ and ||dπµ /µ||∞ enabling the k-step policy gradient method to escape suboptimal critical points that emerge from poor exploration in fully observable settings.
1
Introduction
Policy gradient methods are one of the most widely used methods to solve complex MDP problems [51, 32, 41, 42, 23]. When it comes to the convergence of policy gradient methods, it has been shown that without restrictions on the policy class, policy gradient methods will converge to the optimal policy when the initial state distribution is sufficiently exploratory [5, 3, 52]. However, policy gradient methods on restricted policy classes in general can face poor local optima. These restricted policy classes are ubiquitous and arise in many important applications including state aggregation, cooperative multi-agent settings with independence requirements, decentralized multi-agents, group decentralized multi-agents etc. [8, 45, 57, 25, 39, 11]. While there have been works that show optimality guarantees of policy gradient methods for restricted policy classes, they usually work under strong assumptions, e.g. variants of Bellman completeness, closure of the restricted policy class, etc. [3, 5]. Typically, these assumptions eliminate poor suboptimal critical points and are stronger versions of “approximate realizability”, which requires a near optimal policy (among all unrestricted policies) to be in the restricted class. However, these conditions do not hold in general for our applications of interest, which may have poor critical points and may not be approximately realizable. Preprint.
1.1
Contribution
Myopicness of the Policy Gradient: In this work, we identify a source of suboptimal local optima that arise from the myopicness of the policy gradient theorem (Section 4). Specifically, the policy gradient theorem finds an improvement direction based on the one-step Q-function, i.e. only the policy at the first step is being optimized, whereas the policy for all subsequent steps are fixed. While this can be adequate for finding the optimal policy for the unrestricted policy class (when the initial state distribution is exploratory), we show that for restricted policy classes, no improvement direction may exist even if there are better policies in the class because of the “short sightedness” of the one-step Q-function (see Section 4.2). k-step Policy Gradients: To counter this myopicness, we propose a k-step policy gradient method (Section 5) that can escape these poor local optima using a k-step Q-function. This method will descend on an adjacent k-step landscape where the critical points are guaranteed to be exponentially close to the optimal deterministic solution with respect to k (see Theorem 6.1). Convergence of Projected GD and Mirror Descent: Further, we show descent (projected GD or mirror) will be guaranteed to achieve this exponentially close to optimal guarantee in O( T1 ) iterations (see Theorem 6.2 and Theorem 6.3). This is despite only assuming smoothness and without the usual gradient dominance condition which does √ not hold in general for restricted policy classes (compared to the typical ∥∇f (x)∥2 ≤ O(1/ T ) convergence guarantee for gradient descent on smooth functions). Our results provide unusually strong theoretical convergence and near optimality guarantees rarely seen for these partial observable applications like state aggregation and cooperative multi-agent settings with independent agents, decentralized agents, or group decentralized agents (see Section 3). Extension to the Fully Observable Setting: We observe that our bounds avoid the distribution ∗ ∗ mismatch factors ||dπµ /dπµ ||∞ and ||dπµ /µ||∞ so it achieves near optimal convergence even when the initial state distribution is poor. We show in Section A that poor exploration can cause suboptimal critical points to emerge even in fully observable settings and our k-step methods can escape.
2
Preliminaries
2.1
Markov Decision Process
The infinite horizon Markov Decision Process (MDP) includes a set of states S and actions A. The dynamics begin with a sample from some fixed initial state distribution µ ∈ ∆(S). At each state, actions will be sampled from our policy π : S → ∆(A) and will be transitioned according to a transition function P : S × A → ∆(S) at each step. The notation τ ∼ π|µ will represent the trajectory of states and actions τ = (s(0), a(0), s(1), a(1), . . .) generated from a policy π starting with initial state distribution µ. Considering some restricted set of policies ΠP res , we would like to ∞ find a policy π ∈ Πres that minimizes the value function J π (µ) = Eτ ∼π|µ [ t=0 γ t g(s(t), a(t))] according to some cost function g : S × A → R with g ∈ [−gmax , gmax ] and discount factor γ ∈ (0, 1). In general, solutions to the restricted policy class Πres setting are difficult to find because our standard techniques for solving MDPs may no longer apply. Performing the Bellman optimality equations may produce a solution outside of Πres and policy iteration may leave the set Πres when computing the greedy policy. Policy gradient methods appear to be a good candidate when Πres is a parameterized set of policies but the problem in general contains poor suboptimal critical points (see Section 4.2). Later, we will propose a generalized k-step policy gradient and show theoretical bounds that ensures various descent algorithms escape poor suboptimal local optima.
3
Related Works
To the best of our knowledge, prior works with theoretical near optimality results for policy gradients in MDPs either assume an unrestricted policy class or make strong assumptions about the policy class that heavily restrict its applications. Unrestricted Policy Class: In the case of an unrestricted policy class, there have been a line of works analyzing the convergence of policy gradient methods [3, 52, 55, 15, 56, 16, 26, 20, 48, 54, 9, 31, 29]. These works analyze projected gradient descent and mirror descent with its variants showing theoretical bounds for convergence. However, in our work 2
we consider restricted policy classes which may have poor suboptimal local minima even for simple examples (see Section 4.2). Restricted Policy Class: Compared to the unrestricted case, strong theoretical results for policy gradient methods in restricted policy classes have been minimal. This literature uses assumptions that rule out all suboptimal local minima ensuring global optimality or have bounds that are meaningful only when similar assumptions hold [3, 5, 30, 46]. These guarantees have “strong results under strong assumptions” in the sense that strong convergence rates and optimality guarantees are achieved, under strong assumptions like gradient dominance or policy-class closure. Unfortunately, these assumptions rule out many applications, including the ones considered in this work (Section 5.3). Function Approximation in RL: There is a long line of work in reinforcement learning theory that studies imposing a function class on either the Q-function or the policy class and seeks to find the optimal Q-function or policy with sample complexity polynomial in the dimension of the class as opposed to the state space size [47, 34, 53, 13, 19, 33, 2, 14, 18, 43, 50]. However, most of these works require certain assumptions on the function class (e.g. linear MDP, linear Bellman completeness, bilinear class) all of which require the “realizability” or “approximate realizability” assumption, meaning a (near) optimal policy or Q-function is in the class. As mentioned in Section 1, many applications do not satisfy this, and our work does not require approximate realizability. Action Chunking: Our solution has some resemblances to the recent proposal of action chunking for reinforcement learning [22, 21]. However, our sampling scheme differs from action chunking in that we will be executing a sampled deterministic policy for k-steps rather than k actions determined all at once. POMDP / Dec-POMDP: Many of the applications considered in this work (such as state aggregation and decentralized multi-agents) are partially observable. Previously, the primary theoretical model for these applications have been the POMDP [37, 8] and Dec-POMDP [35, 4] which are generally seen as intractable to solve, proven to be PSPACE-complete and NEXP-complete respectively. Our work will provide an encouraging positive result for this literature by proving strong theoretical near optimality guarantees for gradient descent methods on a restricted policy class that models the partial observability.
4
Myopic Traits of Policy Gradients
4.1
Revisiting the Policy Gradient Theorem
The k-step policy gradient we introduce in this work will counteract the myopic behavior of traditional policy gradient methods allowing it to better escape poor local optima. To illustrate the issue, assume a restricted parameterized policy class Πres with policies of the form πα : S → ∆(A) for some learning parameters α ∈ I. Consider the standard policy gradient theorem: Theorem 4.1 (Policy Gradient Theorem). Let Πres be a restricted policy class parametrized by α ∈ I where J πα (µ) is differentiable with respect to α. Then, 1 ∇α J πα (µ) = 1−γ Es∼dπµα [Ea∼πα (·|s) [Qπα (s, a)∇α log πα (a|s)]] P∞ where dπµα (s) = (1 − γ) t=0 γ t P (st = s|µ, πα ) is the discounted state occupancy measure.
Notice the expression for the gradient contains the standard 1-step Q-function. This Q-function is myopic in that only one step of a chosen action is taken before reverting to the policy πα . This myopicness is more apparent when compared to the policy gradient theorem for bandits ∇α J πα = Ea∼πα (·) [g(a)∇α log πα (a)]. The representation takes a familiar form with g replacing Qπ and minor adjustments for the lack of a state or discount factor. This similarity begs the question of whether the policy gradient theorem for MDPs is effectively using information past the first timestep to create a satisfactory descent direction. Indeed the myopicness presents some challenges when considering restricted policy classes. We show this using our running example below. 4.2
Running Example
To illustrate many of the points introduced in this work, we will refer frequently to a two state MDP example borrowed from [5] seen in Figure 1a. Despite its minimal construction, it will contain a suboptimal critical point as seen in Figure 1b. In Figure 1a, the system can be in state sL or sR and transitioned between each other using a “left action” L or “right action” R. Changing the state will incur cost 2 and staying at sL will incur a cost of 1. The policy class is restricted to Πres = {πθ : θ ∈ [0, 1]} where πθ takes action R with probability θ regardless of the state and action 3
(b) The value function J πθ (µ) versus θ for the example in Section 4.2. There are two local minima at θ = 0, 1 and a local maxima at θ ≈ 0.32.
(a) Example from Section 4.2. Transitions are deterministic and incur costs shown above.
L otherwise. With γ = 0.8 and µ = [0.6, 0.4] this creates a suboptimal local minima at θ = 0 as seen in Figure 1b. To show why this is the case, when θ ≈ 0, the policy gradient theorem simplifies to: ∇θ J πθ (µ) ≈ 4.6(Qπ0 (sL , R) − J π0 (sL )) + 0.4(Qπ0 (sR , R) − J π0 (sR )). Following Figure 1a to evaluate Qπ0 (sL , R), the trajectory starts at sL and initially takes action R, moving the state to sR and incurring a large cost. This is followed by the action L which will move back to sL incurring another large cost then remaining at sL . This performs worse than J π0 (sL ) which simply remains at state sL . Therefore Qπ0 (sL , R) − J π0 (sL ) > 0 and the dominant first term turns positive indicating a positive slope and a suboptimal critical point at θ = 0. We later introduce a new gradient update utilizing a k-step Q-function that will allow for k-steps of evaluation of action R prior to returning to sL . When action R is taken k times, it gives the opportunity to reduce the cost by remaining at the no-cost state sR for longer periods of time before returning to sL . This allows the Q-function to “adequately test” a policy as part of the gradient computation and achieve near optimal performance for various descent algorithms. 4.3
Origin of Myopicness
At first, the myopicness of the gradient may seem mysterious because the gradient straightforwardly presents the direction of steepest ascent and seems like it could always be used to create a good update direction. However, it is specifically how the gradient interacts with the independent sampling of the policy in the traditional 1-step evaluation scheme that causes myopicness. Intuitively, trajectories that use “multi-step reasoning” will be lost in higher order terms. Concretely, in the two state MDP example from Figure 1a, suppose we begin at π0 (i.e. θ = 0, policy always takes action L) and increment the parameter by a small dθ. The policy πdθ then takes action R with this infinitesimal γH dθ. Further, we restrict the horizon to be a large H such that 1−γ gmax is small. Notice that for PH−1 t Eτ ∼πdθ |µ [ t=0 γ g(s(t), a(t))] any trajectory that takes action R m-times will have a probability of (dθ)m (1 − dθ)H−m ≤ (dθ)m due to independence. Therefore, trajectories with m ≥ 2 are lost in the higher order terms and will not appear as part of the (right hand side) derivative at 0 because m lim∆θ→0 (∆θ) = 0. In other words, only trajectories which take action R at most one time are ∆θ considered as part of the computation. This then provides an intuition for the reason the 1-step Q-function appears in the gradient expression. The primary issue that causes this myopicness is this independent evaluation of the policy at each step, that does not allow the gradient to “see the effect” of the change dθ across multiple steps.
5
Breaking Myopicness with k-step PG
5.1
Correlated Policies
In this work, we introduce a new interpretation for the policy. In the standard definition of the MDP, stochastic policies are of the form π : S → ∆(A) which takes an independent action at each state. However, another way of viewing a stochastic policy is as a distribution of deterministic policies. Definition 5.1 (Correlated Policy). Let Πdet be a set of deterministic policies of the form πdet : S → A. A correlated policy π̃ is a distribution over Πdet or in other words, π̃ ∈ ∆(Πdet ). An action can be taken at state s by sampling πdet ∼ π̃ and taking πdet (s). 4
Going forward, the restricted set of these correlated policies will be denoted Π̃res . The restricted policy class from the two state example in Section 4.2, can be viewed from a correlated policy perspective. Recall πL is the deterministic policy that takes action L at both states and πR the corresponding policy for action R. The restricted policy class can then be described as Πdet = {πL , πR } and Π̃res = {π̃θ |π̃θ = Iθ πR + (1 − Iθ )πL , θ ∈ [0, 1]} where Iθ is an indicator function that is 1 with probability θ and 0 otherwise. In a standard policy rollout, our proposed formulation would independently at each step, sample πdet ∼ π̃ and take πdet (s) for current state s. This is equivalent to taking the traditional policy π : S → ∆(A) defined implicitly by πdet (s) where iid
πdet ∼ π̃. Therefore in the “1-step evaluation” in standard rollout (independent evaluations at each step), the correlated policy and its corresponding traditional policy are equivalent. Later, we will introduce a “k-step evaluation” where this new representation will be required. 5.2
Restriction Assumption
For this work, we consider an arbitrarily restricted set of deterministic policies Πdet determined by our application. The main assumption made is that the correlated policy class Π̃res is all possible distributions ∆(Πdet ). This ensures sufficient expressibility during the “training phase.” Assumption 5.2. Πdet is an arbitrary set of deterministic policies and Π̃res is all policies ∆(Πdet ). The general outline of our solution framework is to obtain a restricted set of deterministic policies Πdet from our problem description which are of the form πdet : S → A. Then a k-step optimization procedure is performed over the correlated policies Π̃res to obtain a solution π̃ ∈ Π̃res . This may have undesired correlations (e.g. among states) so the sample πdet ∼ π̃ will be presented as a solution which again has the form of a traditional uncorrelated policy πdet : S → A. The following is a minimal list of applications that our work will encompass. 5.3
Applications
Policy with State Aggregation: Consider an MDP environment with a set of observations O and an observation function Of unc : S → O. We may define the set of deterministic policies that only depend on this observation. Πdet will therefore be all possible deterministic policies of the form + + πdet (s) = πdet (Of unc (s)) where πdet : O → A. The two state example from Section 4.2 is a state aggregation problem. Real life scenarios involving policies with state-aggregation may appear by a necessity to reduce computation need (e.g. by grouping similar states into the same aggregated state). Other times, state aggregation may be a result of partial observability. For example, the state is a tuple (x, y), but the agent only observes x. These types of partially observable systems appear in applications in the medical field, computer vision, military applications and many more (see [8]). This is typically modeled as a POMDP which is generally intractable to solve. With the methods developed in this work, we will be able to produce unusually strong theoretical near optimality results for this setting. Independent Multi-Agents: Frequently in multi-agent settings, every agent has its own state Si which produces a global state S = S1 × . . . × Sn for agents N = {1, . . . , n}. Each agent then decides on an action ai ∈ Ai with a global action space of A = A1 × . . . × An . Further, in cooperative independent agent environments, agents are only allowed to observe their own state but have rewards and transitions that may depend on other agents. Examples include traffic control [45] and power systems [57]. Unfortunately, the general multi-agent extension of the POMDP called the Dec-POMDP is NEXP-Complete and generally intractable to solve [4]. In these environments, Πdet i will be all deterministic policies that map to πdet (s) = (πdet (si ) : i ∈ N ) for all possible individual i policies πdet : Si → Ai for i ∈ N (see Section A.1 for an example). Decentralized Multi-Agents: Another common multi-agent setting is when cooperative decentralized agents act according to an observation of the state. Assume the same factored state and action space as in the independent multi-agents setting. Then at a state s ∈ S = S1 × . . . Sn , agent i acts according to some observation Oi,f unc (s) where Oi,f unc : S → Oi for some set of observations i,+ Oi . The restricted set of deterministic policies Πdet is then πdet (s) = (πdet (Oi,f unc (s)) : i ∈ N ) i,+ for all possible individual policies πdet : Oi → Ai for i ∈ N (see Section A.2 for an example). Similarly, these applications in general are also modeled using a Dec-POMDP which is generally seen as intractable to solve. Examples include robotics applications where agents can only view other 5
agents within their vicinity [36, 25]. This also encompasses the networked RL literature where agents are connected in some graph with a fixed distribution and agents can observe their κ-hop neighbors [39, 38, 24]. Group Decentralized Agents: In the group decentralized setting, agents are grouped together based on some criteria, and the agents in that group all share a joint observation of each others state. For s ∈ S = S1 × . . . × Sn , a grouping function exists G : S → P art(N ) where P art(N ) is the set of partitions over the agents. Then at each state s, each agent in the same partiton g ∈ G(s) will observe the states of the agents in the group sg = (si : i ∈ g). Πdet will be all deterministic policies g g of the form πdet (s) = (πdet (sg ) : g ∈ G(s)) with πdet : Sg → Ag and g ⊂ N . The concept of group decentralized agents is expanded upon in the Locally Interdependent Multi-Agent MDP works [11, 12] that can model various autonomous vehicle and robotics applications. The outcome of policy gradient methods directly on the group decentralized policy class is still not well understood and the methods in this work can offer a solution. 5.4
The k-step Evaluation
Leveraging our new formulation of the policy, we will now introduce the k-step evaluation of a policy. In the traditional 1-step evaluation described in more detail in Section 5.1 we sample πdet ∼ π̃ from π̃ ∈ Π̃res and take the policy πdet (s) independently at each step. For the k-step evaluation, once πdet ∼ π̃ is sampled, we will execute πdet for k iterations before sampling again. This will allow for a better “measure of the quality” of the deterministic policies sampled by π̃. Definition 5.3 (k-step value P∞ function). For a correlated policy π̃ ∈ Π̃res , the k-step value function is J π̃,k (s) = Eτ ∼π̃|s,k [ t=0 γ t g(s(t), a(t))] where τ ∼ π̃|s,k represents the trajectory starting at state s generated by repeatedly sampling πdet ∼ π̃ and taking πdet for k steps (we sample from π̃ at timesteps 0, k, 2k, . . . and the sampled deterministic policy is used in the intermediate timesteps). Notice that this k-step value function is still a function on S but it uses correlated policies and is rolled out in a different way, altering the probabilities of the sampled trajectories. We now define the analogous k-step Q-function. Definition 5.4 (k-step Q-function). P∞ For a correlated policy π̃ ∈ Π̃res , the k-step Q-function is ′ ′ Qπ̃,k (s, πdet ) = Eτ ∼π̃|s,π′ ,k [ t=0 γ t g(s(t), a(t))] where τ ∼ π̃|s,πdet ,k represents the trajectory det
′ starting at state s and takes πdet for the initial k steps before repeatedly using π̃ to sample and execute ′ for k iterations (πdet is used for the first k timesteps followed by taking samples of π̃ at timesteps k, 2k, . . . and using the sampled deterministic policy for the intermediate timesteps).
Computing the k-step Q-function. This Q-function should not be computed in whole as the second argument is dependent on a potentially large number of deterministic policies in Πdet (much more than the number of actions as in the traditional Q-function). In practice, we suggest building an ′ estimator for J π̃ (s) and choosing a reasonable k for the problem so Qπ̃,k (s, πdet ) can quickly be π̃,k ′ reconstructed. Notice in the case of deterministic dynamics Q (s, πdet ) can be constructed from ′ ′ ′ J π̃ (s) quite quickly as Qπ̃,k (s, πdet ) = g(s, πdet (s)) + γg(s1 , πdet (s1 )) + . . . + γ k J π̃ (sk ) would only require a single k-step roll out. In non-deterministic cases, Monte-Carlo estimation can be used along with various variance reduction methods. This k-step Q-function has a tradeoff between the ′ computation time and myopicness. When k = 1, the standard Q-function Qπ̃ (s, πdet (s)) can be used but is mostly an evaluation of the performance of π̃. When k → ∞, the k-step Q-function becomes ′ ′ ′ Qπ̃,k (s, πdet ) → J πdet (s) which is excellent in determining if πdet is a “good policy” but requires a ′ πdet ′ full computation of J (s) for every πdet and state s which is not feasible. 5.5
The k-step Policy Gradient
The gradient in this k-step regime can be expressed with the following variant of the Policy Gradient Theorem. Theorem 5.5 (k-step Policy Gradient Theorem). Let Π̃res be a restricted policy class parametrized by α ∈ I and J π̃α ,k (µ) is differentiable with respect to α. Then the following equality holds: 1 π̃α ,k ∇α J π̃α ,k (µ) = 1−γ (s, πdet )∇α log π̃α (πdet )]. k Es∼dπ̃α ,k Eπdet ∼π̃α [Q µ
6
P∞ Here, dπ̃s0α ,k = (1 − γ k ) m=0 γ mk P (smk = s|s0 , π̃α , k) is the k-step discounted state occupancy measure. The proof is shown in Section B.1. Compared to the standard policy gradient theorem in Theorem 4.1, this k-step policy gradient theorem incorporates descent over the correlated policies as well as including a k-step Q-function in its expression, which tests πdet for k steps to compute the gradient. This will overcome the myopic traits of standard policy gradient (see Section 6). Consider using this gradient in the two state example from Section 4.2 expressed with correlated policies in Section 5.1. For π̃θ with θ ≈ 0, the k-step Q-function in the gradient expression will include the value of taking action R (or the deterministic policy πR ) for k times before reverting to πθ ≈ πL . This will allow the k-step policy gradient method to overcome the myopicness of traditional policy gradients (see Section 7).
6
Theoretical Guarantees
We show that when policies are improved with the k-step policy gradient introduced in Section 5.5, strong theoretical bounds can be proved. Recall that we are assuming an arbitrarily restricted class of deterministic policies Πdet and learning a policy in Π̃res which is all correlated policies of the form π̃ ∈ ∆(Πdet ) (see Section 5.2). The optimality guarantees in this section are relative to the optimal ∗ deterministic policy in the policy class πdet ∈ Πdet . For deterministic policies, the k-step evaluation ∗ ∗ and the traditional 1-step evaluations are equivalent (J πdet ,k (µ) = J πdet (µ)) and therefore, this optimal deterministic policy can act as a fixed point of comparison for both settings and for all k. 6.1
Near Optimal Critical Points
To begin, we show that all zero gradient critical points and local minima on the boundary are theoretically guaranteed to be exponentially close in performance to the optimal deterministic policy with respect to k. This demonstrates a strong and general near optimality bound that is rarely seen for these restricted policy classes. Theorem 6.1. Consider the policy class Π̃res with the assumptions from Section 5.2 with the trivial parametrization (elements of Π̃res are directly represented as elements of the simplex ∆(Πdet )). Assume J π̃,k (µ) is differentiable with respect to π̃. Let π̃crit ∈ Π̃res be a zero-gradient critical point or a local minima on the boundary. Then, the following performance bound is satisfied: ∗
k
γ Eπdet ∼π̃crit [J πdet (µ)] − J πdet (µ) ≤ 8 1−γ gmax
Notice that as k increases, the performance of ALL specified critical points in the system are pushed towards the optimal deterministic policy exponentially fast in k. Further, as will be shown in the next subsections, descent using k-step evaluations will converge to a theoretically near optimal solution despite considering a broad class of restricted policies that may have poor 1-step local minima as in Figure 1a. Lastly, we note Lemma B.1 is used to prove this result and acts as an approximate gradient dominance condition that will take the place of the usual gradient dominance condition as in [3] for the following descent proofs. 6.2
Projected Gradient Descent
Next, despite only assuming smoothness, performing projected gradient descent and mirror descent will satisfy this exponential performance bound (Theorem 6.1) in O( T1 ) iterations. Specifically, projected gradient descent on the trivially parametrized policy Π̃res (in other words ∆(Πdet )) with updates π̃t+1 ← P rojΠ̃res (π̃t − η∇J π̃t ,k (µ)) achieves the following (proved in Section B.2.2). Theorem 6.2. Suppose J π̃,k (µ) is differentiable and β-smooth in π̃. Then, projected gradient descent on the trivially parametrized Π̃res with learning rate η = β1 converges. Further, if π̃T is the T-th timestep in projected gradient descent with the trivial parametrization, then the following performance guarantee is satisfied: ∗ γk β 1 πdet πdet ∗ 2 Eπdet ∼π̃T [J (µ)] − J (µ) ≤ 8 1−γ gmax + T 2 ∥π̃ − π̃0 ∥2 Prior works like [3, 5] have achieved this rate for unrestricted policy classes where a gradient dominance condition is satisfied, whereas we may have suboptimal critical points as in Section 4.2. In 7
Figure 2: Critical points being removed as predicted by our theoretical bound discussed in Section 6. general, smoothness alone for projected gradient descent and mirror descent on general functions only provides convergence bounds of the form ∥∇J π (µ)∥2 ≤ O( √1T ). In fact, in [6, 7] an information theoretic lower bound is shown guaranteeing this rate is tight for any algorithm on the class of all problems with bounded initial value and first-order smoothness. Our O( T1 ) rate holds because the k-step evaluation induces an approximate gradient dominance condition (Lemma B.1). Therefore, this k-step policy gradient brings about a “good landscape” for the descent algorithms ensuring a faster descent to “high performing” solutions. Crucially, our results are not dependent on the distribution mismatch coefficients of the form ∗ ∗ ||dπµ /dπµ ||∞ nor ||dπµ /µ||∞ that is common in the literature [3, 52, 55]. This is a term that can easily ∗ be infinite when the supports of µ or dπµ does not subsume the supports of dπµ that depends on the unknown policy π ∗ . See Section A for examples of how suboptimal critical points can emerge in fully observable examples with poor exploration and how the k-step methods can escape. 6.3
Mirror Descent
Non-trivial parameterizations on Π̃res can be handled through the generalized mirror descent algorithm. For π̃α ∈ Π̃res which is parametrized by α ∈ I, mirror descent with mirror map Φ updates the policy π̃αt+1 ← argminπ̃α ∈Π̃res ⟨∇J π̃αt ,k (µ), π̃α ⟩ + η1 DΦ (π̃α , π̃αt ) where DΦ is the Bregman divergence. We present the following result for mirror descent with these correlated policies (proved in Section B.2.3): Theorem 6.3. Assume J π̃,k (µ) is differentiable and β-smooth in π̃ with respect to some norm ∥ · ∥. Let Φ be a differentiable mirror map that is λ-strongly convex with respect to the same norm. Then mirror descent on the constraint set Π̃res with learning rate η = βλ converges. Further if π̃T is the T-th timestep in mirror descent. Then the following performance guarantee is satisfied: k
∗
γ Eπdet ∼π̃T [J πdet (µ)] − J πdet (µ) ≤ 8 1−γ gmax + T1
β ∗ λ DΦ (π̃ , π̃0 )
For various parameterizations and choices of a mirror maps, the mirror descent updates often simplify. In the standard MDP setting with an unrestricted policy class, when the expected negative Shannon entropy mirror map is used, the mirror descent update becomes the ubiquitous natural policy gradient. The natural policy gradient handles the learning parameters through the fisher information matrix. When a softmax parametrization is used with the natural policy gradient, this results in a multiplicativeweights style update [3]. The natural policy gradient is also the basis for empirical algorithms such as trust region policy optimization (TRPO) and proximal policy optimization (PPO) [41, 42]. However, for both the traditional setting and our correlated setting, the natural policy gradient update may require modifications to adhere to the policy class restriction and may have a different form dependent on the restriction Π̃res [17, 10, 44]. Thus, for our purposes, we will focus on mirror descent in its most general form.
7
Simulation of Two-State Example
We confirm our results in the two state example from Section 4.2 shown in Figure 2 (as well as additional examples in Section A). In the k = 1 diagram, we see the 1-step evaluation from Figure 1a in Section 4.2. The three critical points are a local minima at θ = 0, θ = 1 and a local maximum at θ ≈ 0.32. As k is increased, the curve straightens and the local minima at θ = 0 ceases to be a local minima by kesc = 3. Likewise the local maxima at θ ≈ 0.3 by kesc = 3 becomes sloped 8
and is no longer a local maxima. Increasing k successfully removes the suboptimal critical points as predicted by our theoretical bound. When k is large as seen in the k = 100 diagram, the k-step evaluation turns affine. This is because when k is large, the initial deterministic policy πdet (s) ∼ π̃ from π̃ ∈ Π̃res will determine the trajectory for longer periods. In other words, as k → ∞, the value function simplifies to J π̃θ ,k (µ) → θJ πR (µ) + (1 − θ)J πL (µ). In general, when k is large, an affine structure will emerge (because of our assumptions in Section 5.2) creating a very easy space to optimize but the gradient will become progressively more expensive to compute as described in Section 5.4.
8
Proof Sketch
The proofs in this work primarily focus on directional derivatives in MDPs. When a directional derivative is negative at a point, this guarantees that the gradient is non-zero and provides a direction for the descent algorithms to improve. Intuitively, the directional derivative provides an “escape direction” for the descent process. The proofs are split into two parts. Firstly, we provide an approximate gradient dominance result. Theorem 6.1 proved in Section B.2.1 will follow directly. Secondly, we will show that descent (projected GD or mirror) on smooth functions will provide an average iterate bound on the negative directional derivative towards the optimal deterministic policy with a O( T1 ) rate. This is again in contrast to the standard convergence rate on smooth functions that guarantees ∥∇J π (µ)∥2 ≤ O( √1T ). Combining part 1) and part 2) will give Theorem 6.2 and Theorem 6.3 proved in Section B.2.2 and Section B.2.3 respectively. Part 1) Let π̃ ∗ be the correlated policy with the Dirac delta of the optimal deterministic policy ∗ δ(πdet ) ∈ Π̃res . The directional derivative at the point π̃ towards π̃ ∗ is denoted as ∇π̃∗ −π̃ J π̃,k (µ) = 1 π̃ ∗ ,k ∗ (π̃ − π̃) · ∇π̃ J π̃,k (µ). We show in Lemma B.1: ∇π̃∗ −π̃ J π̃,k (µ) ≤ 1−γ (µ) − J π̃,k (µ)) + k (J 6γ k . This acts as an approximate gradient dominance condition and ensures that if g (1−γ k )(1−γ) max the directional derivative ∇π̃∗ −π̃crit J π̃crit ,k (µ) ≥ 0 at a local minimum or 0 at gradient critical ∗ ∗ γk gmax and therefore Eπdet ∼π̃crit [J πdet (µ)] − J πdet (µ) ≤ point, then J π̃crit ,k (µ) − J πdet (µ) ≤ 6 1−γ k
γ gmax as desired (see Section B.2.1). 8 1−γ
Part 2) For general smooth functions, when performing projected gradient descent on a convex set or mirror descent with a λ-strongly convex mirror map, the negative directional derivative can be bounded by a O( T1 ) term. Intuitively, this is done through a modification of the traditional smooth + convex O( T1 ) performance bound. The traditional smooth + convex proof uses the first order condition for convexity which lower bounds the negative directional derivative f (x) − f (y) ≤ ∇f (x) · (x − y) = −∇y−x f (x). Since we will use Lemma B.1 in the place of convexity, we will instead keep the negative directional derivative term and simplify. In the case of mirror descent with PT −1 1 π̃t ,k ∗ a learning rate 1/β, (µ) ≤ this yields the following average iterate bound: T t=0 −∇π̃ −π̃t J P T −1 β 1 1 ∗ π̃t+1 ,k (µ) − J π̃t ,k (µ)) proved in Lemma B.2. The result from Part t=0 (J T λ DΦ (π̃ , π̃0 ) − T 1) then provides a lower bound on −∇π̃∗ −π̃t J π̃t (µ). Noting that mirror descent on a smooth function reduces the value at each step (proved in Lemma B.6), yields the last-iterate bound in Theorem 6.3.
9
Future Works / Discussion
Our results (Section 6) show a promising new angle of attack for solving MDPs with restricted policy classes in applications such as state aggregation, independent multi-agents, decentralized multi-agents, and group decentralized agents (Section 5.3). This work presents a theoretical treatment, but the future empirical works seem just as promising. Diffusion models have been used to represent the policy in various RL settings [49, 27, 28] and may model the potentially high dimensional correlated policies. Learning could be performed using reweighted score matching [27] using the k-step Q-function. This motivates applications of this theory to larger scale simulations and baselines. We may also extend the MDP results in this work to the RL setting where transitions and reward functions are unknown and further investigate the consequences of the k-step methods in the fully observable settings (see Section A) where optimization is still challenging such as in robotics applications [40]. 9
Acknowledgments This research was supported by NSF Grants 2339112, 2512805, CMU CyLab Seed Funding, and Pennsylvania Infrastructure Technology Alliance. In addition, Alex DeWeese is supported by Leo Finzi Memorial Fellowship in Electrical & Computer Engineering, the David H. Barakat and LaVerne Owen-Barakat CIT Dean’s Fellowship, and the Fritsch Family Fellowship.
References [1] Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 32:96, 2019. [2] Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank mdps. Advances in neural information processing systems, 33:20095–20107, 2020. [3] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1–76, 2021. [4] Daniel S Bernstein, Robert Givan, Neil Immerman, and Shlomo Zilberstein. The complexity of decentralized control of markov decision processes. Mathematics of operations research, 27(4):819–840, 2002. [5] Jalaj Bhandari and Daniel Russo. Global optimality guarantees for policy gradient methods. Operations Research, 72(5):1906–1927, 2024. [6] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points i. Mathematical Programming, 184(1):71–120, 2020. [7] Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. Lower bounds for finding stationary points ii: first-order methods. Mathematical Programming, 185(1):315–355, 2021. [8] Anthony R Cassandra. A survey of pomdp applications. In Working notes of AAAI 1998 fall symposium on planning with partially observable Markov decision processes, volume 1724, 1998. [9] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4):2563– 2578, 2022. [10] Jinchi Chen, Jie Feng, Weiguo Gao, and Ke Wei. Decentralized natural policy gradient with variance reduction for collaborative multi-agent reinforcement learning. Journal of Machine Learning Research, 25(172):1–49, 2024. [11] Alex DeWeese and Guannan Qu. Locally Interdependent Multi-Agent MDP: Theoretical Framework for Decentralized Agents with Dynamic Dependencies. In Forty-first International Conference on Machine Learning, 2024. [12] Alex DeWeese and Guannan Qu. Thinking beyond visibility: A near-optimal policy framework for locally interdependent multi-agent mdps. arXiv preprint arXiv:2506.04215, 2025. [13] Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826–2836. PMLR, 2021. [14] Simon Du, Akshay Krishnamurthy, Nan Jiang, Alekh Agarwal, Miroslav Dudik, and John Langford. Provably efficient rl with rich observations via latent state decoding. In International Conference on Machine Learning, pages 1665–1674. PMLR, 2019. [15] Ilyas Fatkhullin, Anas Barakat, Anastasia Kireeva, and Niao He. Stochastic policy gradient methods: Improved sample complexity for fisher-non-degenerate policies. In International Conference on Machine Learning, pages 9827–9869. PMLR, 2023. 10
[16] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In International conference on machine learning, pages 1467–1476. PMLR, 2018. [17] Roy Fox, Stephen M Mcaleer, Will Overman, and Ioannis Panageas. Independent natural policy gradient always converges in markov potential games. In International Conference on Artificial Intelligence and Statistics, pages 4414–4425. PMLR, 2022. [18] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire. Contextual decision processes with low bellman rank are pac-learnable. In International Conference on Machine Learning, pages 1704–1713. PMLR, 2017. [19] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan. Provably efficient reinforcement learning with linear function approximation. Mathematics of Operations Research, 48(3):1496– 1521, 2023. [20] Guanghui Lan. Policy mirror descent for reinforcement learning: Linear convergence, new sampling complexity, and generalized problem classes. Mathematical programming, 198(1):1059– 1106, 2023. [21] Qiyang Li, Seohong Park, and Sergey Levine. Decoupled q-chunking. arXiv preprint arXiv:2512.10926, 2025. [22] Qiyang Li, Zhiyuan Zhou, and Sergey Levine. Reinforcement learning with action chunking. arXiv preprint arXiv:2507.07969, 2025. [23] Timothy P Lillicrap, Jonathan J Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.02971, 2015. [24] Yiheng Lin, Guannan Qu, Longbo Huang, and Adam Wierman. Multi-agent reinforcement learning in stochastic networked systems. Advances in neural information processing systems, 34:7825–7837, 2021. [25] Miao Liu, Kavinayan Sivakumar, Shayegan Omidshafiei, Christopher Amato, and Jonathan P How. Learning for multi-robot cooperation in partially observable stochastic environments with macro-actions. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 1853–1860. IEEE, 2017. [26] 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:7624–7636, 2020. [27] Haitong Ma, Tianyi Chen, Kai Wang, Na Li, and Bo Dai. Efficient online reinforcement learning for diffusion policy. arXiv preprint arXiv:2502.00361, 2025. [28] Haitong Ma, Ofir Nabati, Aviv Rosenberg, Bo Dai, Oran Lang, Idan Szpektor, Craig Boutilier, Na Li, Shie Mannor, Lior Shani, et al. Reinforcement learning with discrete diffusion policies for combinatorial action spaces. arXiv preprint arXiv:2509.22963, 2025. [29] Jincheng Mei, Wesley Chung, Valentin Thomas, Bo Dai, Csaba Szepesvari, and Dale Schuurmans. The role of baselines in policy gradient optimization. Advances in Neural Information Processing Systems, 35:17818–17830, 2022. [30] Jincheng Mei, Bo Dai, Alekh Agarwal, Mohammad Ghavamzadeh, Csaba Szepesvári, and Dale Schuurmans. Ordering-based conditions for global convergence of policy gradient methods. Advances in Neural Information Processing Systems, 36:30738–30749, 2023. [31] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In International conference on machine learning, pages 6820–6829. PMLR, 2020. 11
[32] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In International conference on machine learning, pages 1928–1937. PmLR, 2016. [33] Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh. Sample complexity of reinforcement learning using linearly combined model ensembles. In International Conference on Artificial Intelligence and Statistics, pages 2010–2020. PMLR, 2020. [34] Rémi Munos. Error bounds for approximate value iteration. In Proceedings of the National Conference on Artificial Intelligence, volume 20, page 1006. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2005. [35] Frans A Oliehoek, Christopher Amato, et al. A Concise Introduction to Decentralized POMDPs, volume 1. Springer, 2016. [36] Shayegan Omidshafiei, Ali-Akbar Agha-Mohammadi, Christopher Amato, and Jonathan P How. Decentralized control of partially observable markov decision processes using belief space macro-actions. In 2015 IEEE international conference on robotics and automation (ICRA), pages 5962–5969. IEEE, 2015. [37] Christos H Papadimitriou and John N Tsitsiklis. The complexity of markov decision processes. Mathematics of operations research, 12(3):441–450, 1987. [38] Guannan Qu, Yiheng Lin, Adam Wierman, and Na Li. Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward. Advances in Neural Information Processing Systems, 33, 2020. [39] Guannan Qu, Adam Wierman, and Na Li. Scalable reinforcement learning for multiagent networked systems. Operations Research, 70(6):3601–3628, 2022. [40] Tom Schaul, Diana Borsa, Joseph Modayil, and Razvan Pascanu. Ray interference: a source of plateaus in deep reinforcement learning. arXiv preprint arXiv:1904.11455, 2019. [41] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889–1897. PMLR, 2015. [42] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347, 2017. [43] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898–2933. PMLR, 2019. [44] Philip S Thomas, William C Dabney, Stephen Giguere, and Sridhar Mahadevan. Projected natural actor-critic. Advances in neural information processing systems, 26, 2013. [45] Pravin Varaiya. Max pressure control of a network of signalized intersections. Transportation Research Part C: Emerging Technologies, 36:177–195, 2013. [46] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. arXiv preprint arXiv:1909.01150, 2019. [47] Yining Wang, Ruosong Wang, Simon S Du, and Akshay Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv:1912.04136, 2019. [48] Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In International conference on machine learning, pages 23484–23526. PMLR, 2022. [49] Zhendong Wang, Jonathan J Hunt, and Mingyuan Zhou. Diffusion policies as an expressive policy class for offline reinforcement learning. arXiv preprint arXiv:2208.06193, 2022. 12
[50] Zheng Wen and Benjamin Van Roy. Efficient exploration and value function generalization in deterministic systems. Advances in Neural Information Processing Systems, 26, 2013. [51] Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229–256, 1992. [52] Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282):1–36, 2022. [53] Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International conference on machine learning, pages 6995–7004. PMLR, 2019. [54] Rui Yuan, Simon S Du, Robert M Gower, Alessandro Lazaric, and Lin Xiao. Linear convergence of natural policy gradient methods with log-linear policies. arXiv preprint arXiv:2210.01400, 2022. [55] Rui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pages 3332–3380. PMLR, 2022. [56] Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvari, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. Advances in Neural Information Processing Systems, 33:4572–4583, 2020. [57] Changhong Zhao, Ufuk Topcu, Na Li, and Steven Low. Design and stability of load-side primary frequency control in power systems. IEEE Transactions on Automatic Control, 59(5):1177–1189, 2014.
13
A
Simulations
In this section, we provide additional simulations on examples with suboptimal critical points. The two state example from Section 4.2 is an example of state-aggregation and here we will give examples of the other applications from Section 5.3. Our first two simulations “Number Matching with Independent Agents” and “Button Press with Decentralized Agents” are examples of independent multi-agents and decentralized multi-agents respectively (in the two agent case, decentralized and group decentralized agents are identical). Then, we will show the surprising effectiveness of these methods in the fully observable setting. Naively, it seems that by the gradient dominance bound shown in [1], that there should not be any suboptimal critical points when the setting is fully observable. However, this bound depends on the ∗ ∗ factor ||dπµ /dπµ ||∞ or ||dπµ /µ||∞ which can easily be infinite when the support of µ or dπµ is off even ∗ by a single state from dπµ such as in the examples we will provide. This invalidates the bound and easily creates suboptimal critical points as we will demonstrate. These critical points can then be escaped using our k-step methods as predicted by Theorem 6.1. A.1
Number Matching with Independent Agents
Figure 3: Each agent independently transitions between states 0 and 1 and are rewarded with cost reductions when the numbers match. Switching their numbers incur penalties. The optimal policy in ∗ red πdet is to match the number 1. The suboptimal critical point πcrit indicated in blue matches the number zero. In this simulation, two agents N = {0, 1} will either be in a state of 0 or 1 with a joint state space of S = {(s1 , s2 )} = {(0, 0), (0, 1), (1, 0), (1, 1)}. Each agent can take an action of either 0 or 1 which will determine which state they will transition to next deterministically with a joint action space of A = {(a1 , a2 )} = {(0, 0), (0, 1), (1, 0), (1, 1)} (e.g. taking action (1, 1) will transition the agents to state (1, 1)). When the agents take the joint action (0, 0) they obtain a cost reduction of −3 and for joint action (1, 1) will obtain a higher cost reduction of −10. However, there will be a penalty of +5 for each agent that has si ̸= ai (the agent chooses to switch its state). We will use a discount factor of γ = 0.9 and initial state distribution µ = [µ(0, 0), µ(0, 1), µ(1, 0), µ(1, 1)] = [0.05, 0.37, 0.37, 0.21]. Notice that in the fully observable case, since the support of the initial state distribution µ is over all states, we would be theoretically guaranteed to not have suboptimal critical points with trivial 14
parametrization due to the gradient dominance condition in [1]. However, as we will see, a suboptimal critical point will be created by considering a partial observability structure. In terms of the policy restriction, agents will be independent so they must take an action that only 1 2 i depends on their own state. In otherwords, Πdet = {(πdet , πdet )} where πdet : si → ai . Π̃res will then contain a distribution over Πdet and we will assume a trivial parameterization which holds a weight for each element of Πdet . We define the four individual deterministic policies available to each agent: πa0 always takes action 0, πa1 always takes action 1, πst (si ) = si stays in the current state, and πfl (si ) = 1 − si flips to the opposite state. There are 4 × 4 = 16 joint deterministic policies in Πdet . ∗ The optimal policy πdet = (πa1 , πa1 ) has both agents deterministically move to state 1, yielding ∗ πdet ,1 J (µ) = µ · [−90, −95, −95, −100]T = −95.8. We claim that πcrit = (πa0 , πa0 ), which has both agents always move to state 0, is a suboptimal 1-step critical point with J πcrit ,1 (µ) = µT [−30, −25, −25, −20] = −24.2.
To show πcrit is a 1-step critical point we compute the 1-step advantages Aπcrit ,1 (s, π ′ ) = Qπcrit ,1 (s, π ′ ) − J πcrit (s) for all π ′ ∈ Πdet at each joint state s, using the discounted occupancy dπµcrit = [dπµcrit (0, 0), dπµcrit (0, 1), dπµcrit (1, 0), dπµcrit (1, 1)] = [0.905, 0.037, 0.037, 0.021]. For the purposes of the table, we abbreviate Aπcrit ,1 ((s1 , s2 ), π ′ ) as A1 (s1 , s2 ) and write Ā1 = dπµcrit · [A1 (0, 0), A1 (0, 1), A1 (1, 0), A1 (1, 1)]T for the weighted average. Policy π ′
A1 (0, 0)
A1 (0, 1)
A1 (1, 0)
A1 (1, 1)
Ā1
(πa0 , πa0 ) [πcrit ] (πa0 , πa1 ) (πa0 , πfl ) (πa0 , πst ) (πa1 , πa0 ) ∗ ] (πa1 , πa1 ) [πdet (πa1 , πfl ) (πa1 , πst ) (πfl , πa0 ) (πfl , πa1 ) (πfl , πfl ) (πfl , πst ) (πst , πa0 ) (πst , πa1 ) (πst , πfl ) (πst , πst )
0.000 +12.500 +12.500 0.000 +12.500 +12.000 +12.000 +12.500 +12.500 +12.000 +12.000 +12.500 0.000 +12.500 +12.500 0.000
0.000 +2.500 0.000 +2.500 +12.500 +2.000 +12.500 +2.000 +12.500 +2.000 +12.500 +2.000 0.000 +2.500 0.000 +2.500
0.000 +12.500 +12.500 0.000 +2.500 +2.000 +2.000 +2.500 0.000 +12.500 +12.500 0.000 +2.500 +2.000 +2.000 +2.500
0.000 +2.500 0.000 +2.500 +2.500 −8.000 +2.500 −8.000 0.000 +2.500 0.000 +2.500 +2.500 −8.000 +2.500 −8.000
+0.0000 +11.9200 +11.7750 +0.1450 +11.9200 +10.8400 +11.4490 +11.3110 +11.7750 +11.4490 +11.7850 +11.4390 +0.1450 +11.3110 +11.4390 +0.0170
All weighted 1-step advantages Ā1 are non-negative and indicating the one step costs are worse. By Theorem 5.5, with the trivial parameterization the 1-step policy gradient with respect to each π ′ ∈ Πdet is proportional to Ā1 , so every gradient direction is non-improving. Thus πcrit is a suboptimal 1-step critical point. ∗ Computing the k-step advantages of πdet = (πa1 , πa1 ):
k
Ak (0, 0)
Ak (0, 1)
Ak (1, 0)
Ak (1, 1)
Āk
1 2 3 4 5 10 25
+12.0000 +4.8000 −1.6800 −7.5120 −12.7608 −32.1057 −54.2568
+2.0000 −5.2000 −11.6800 −17.5120 −22.7608 −42.1057 −64.2568
+2.0000 −5.2000 −11.6800 −17.5120 −22.7608 −42.1057 −64.2568
−8.0000 −15.2000 −21.6800 −27.5120 −32.7608 −52.1057 −74.2568
+10.8400 +3.6400 −2.8400 −8.6720 −13.9208 −33.2657 −55.4168
At k = 3 the weighted average Āk first becomes negative, so kesc = 3. A k-step policy gradient ∗ with k ≥ 3 will descend toward πdet , whereas k ∈ {1, 2} remains stuck at πcrit . The penalty for switching state dominates the 1-step and 2-step horizons; by k = 3 the repeated lower cost at state (1, 1) outweighs the switching cost. 15
A.2
Button Press with Decentralized Agents
Figure 4: A left agent in {1, 2, 3} and a right agent in {5, 6, 7} are separated by a wall at position 4. When at positions (3, 5) staying at that position interpreted as jointly “pushing a button” will reduce the cost of agents (−5) with a penalty if either decide to leave (+30). Similarly there are a set of “buttons” at (1, 7) but with a better cost reduction −18. Indicated in red is the optimal deterministic ∗ policy πdet to bring the agents towards the higher reward button states (1, 7). There is a suboptimal deterministic policy πcrit which brings both agents to the center button state (3, 5) and is a critical point. Crosses mark the support of the initial state distribution. This experiment illustrates that a decentralized policy restriction alone can create suboptimal critical points even when the initial distribution µ has full support. In the fully observable setting, full-support µ together with the gradient dominance bound of Theorem 6.1 would guarantee that there are no suboptimal critical points. Here, the decentralized constraint is the source of the critical point. A left agent occupies sL ∈ {1, 2, 3} and a right agent occupies sR ∈ {5, 6, 7}, separated by a wall at position 4 so the agents cannot cross. Each agent can move to an adjacent position or stay and the boundary positions are clamped. The immediate cost depends only on the joint state with g(3, 5) = −5 (center button, if staying), g(1, 7) = −18 (high-reward button, if staying), leaving either button incurs a positive cost (−5 + 30 = +25 or −18 + 30 = +12 respectively), and all other states have cost 0. We use γ = 0.9 and µ uniform over all 9 joint states. Agents are decentralized with visibility V = 2: at every joint state except (3, 5), neither agent can observe the other, so each agent’s action may only depend on its own position. At the sole mutually visible state (3, 5) (|3 − 5| = 2 = V), both agents observe the full joint state and may independently choose their action there. The left agent’s policy therefore has four independent components: π L (1) ∈ {1, 2} and π L (2) ∈ {1, 2, 3} applied at all out-of-view states with those positions, π L (3) ∈ {2, 3} applied only at the out-of-view states (3, 6) and (3, 7), and a separate L visible-state action πvis ∈ {2, 3} applied at (3, 5) independently. This gives 2 × 3 × 2 × 2 = 24 left-agent policies and by symmetry the right agent also has 24. There are 24 × 24 = 576 joint deterministic policies in Πdet . ∗ The optimal policy πdet sends each agent toward its end of the grid and stays at the high-reward button: ∗ πdet J (µ) = −152.22. We claim that πcrit , which sends the left agent toward 3 and the right agent toward 5 and stays at the center button, is a suboptimal 1-step critical point with J πcrit (µ) = −41.72.
Under πcrit , occupancy concentrates at (3, 5). The full discounted occupancy is dπµcrit (3, 5) = 0.861, dπµcrit (2, 5) = dπµcrit (3, 6) = 0.031, dπµcrit (2, 6) = 0.021, and dπµcrit (s) = 0.011 for s ∈ {(1, 5), (1, 6), (1, 7), (2, 7), (3, 7)}. All 576 joint deterministic policies π ′ ∈ Πdet satisfy dπµcrit ·Āπcrit ,1 (·, π ′ )T ≥ 0 (verified numerically, omitted for brevity). ∗ Below, we provide the k-step advantages of πdet :
k
Ak (1, 5)
Ak (1, 6)
Ak (1, 7)
Ak (2, 5)
Ak (2, 6)
Ak (2, 7)
Ak (3, 5)
Ak (3, 6)
Ak (3, 7)
Āk
1 2 3 4 5 6 7 8
+4.050 +17.415 +5.143 −5.901 −15.841 −24.787 −32.838 −40.084
+14.850 +1.215 −11.057 −22.101 −32.041 −40.987 −49.038 −56.284
−15.150 −28.785 −41.057 −52.101 −62.041 −70.987 −79.038 −86.284
+8.550 +21.915 +9.643 −1.401 −11.341 −20.287 −28.338 −35.584
+19.350 +5.715 −6.557 −17.601 −27.541 −36.487 −44.538 −51.784
+14.850 +1.215 −11.057 −22.101 −32.041 −40.987 −49.038 −56.284
+34.500 +51.915 +39.643 +28.599 +18.659 +9.713 +1.662 −5.584
+8.550 +21.915 +9.643 −1.401 −11.341 −20.287 −28.338 −35.584
+4.050 +17.415 +5.143 −5.901 −15.841 −24.787 −32.838 −40.084
+30.9005 +46.2830 +34.0115 +22.9672 +13.0272 +4.0813 −3.9700 −11.2162
16
At k = 7 the weighted average Āk first becomes negative, so kesc = 7. The center button (3, 5) maintains a positive advantage (Ak (3, 5) > 0) through k = 6, pushing the weighted average in the wrong direction until the high-reward button advantage at (1, 7) and intermediate states accumulates sufficiently. A.3
Fully Observable Moat Cross
Figure 5: A 7-long grid world where the agent starts at state 4 (µ = δ4 ). The costs in the diagram are ∗ g(1) = −1, g(5) = g(6) = +3 (moat), g(7) = −20. The optimal policy in red πdet will overcome the penalty from the moat and move to the higher reward square at state 7. A suboptimal critical point will be present at πcrit which goes directly to state 1. With this experiment, we demonstrate the benefits of our theory in a fully observable setting. Recall that in the unrestricted policy class setting there exists a gradient dominance bound in [1]. However, ∗ ∗ this bound depends on the factor ||dπµ /dπµ ||∞ or ||dπµ /µ||∞ which will be infinite in this example ∗ (since the support of µ and dπµ does not subsume the support of dπµ ). Therefore, suboptimal critical points may emerge even when the policy class is unrestricted. In this single-agent experiment, the state space is a grid world that has 7 states in a row S = {1, . . . , 7} with the agent starting at state 4 (µ = δ4 ). At each step the agent chooses to move left (a = −1), stay (a = 0), or move right (a = +1), and transitions to the adjacent state deterministically (clamped at boundaries). The per-step costs are g(1) = −1, g(5) = g(6) = +3 (moat), g(7) = −20 and all other states have g = 0. We use γ = 0.9. The suboptimal policy πcrit always moves left and remains at state 1 with J πcrit (δ4 ) = −7.29. ∗ The optimal policy πdet always moves right, crossing the moat (states 5, 6) to stay at state 7 with ∗ πdet J (δ4 ) = −140.67. The discounted occupancy under πcrit is dπδ4crit (1) = 0.729, dπδ4crit (2) = 0.081, dπδ4crit (3) = 0.090, dπδ4crit (4) = 0.100, dπδ4crit (s) = 0 for s ∈ {5, 6, 7}, making the ∗ gradient dominance bound in [1] vacuous since πdet visits states unreachable under πcrit . At every support state s ∈ {1, 2, 3, 4}, every action a ∈ {−1, 0, +1} has Aπcrit ,1 (s, a) ≥ 0, confirming that πcrit is a 1-step critical point: State s
J πcrit (s)
Action a
Qπcrit (s, a)
Aπcrit (s, a)
s=1
−10.00
a=−1 [πcrit ] a=0 a=+1
−10.000 −10.000 −9.100
0.000 0.000 +0.900
s=2
−9.00
a=−1 [πcrit ] a=0 a=+1
−9.000 −8.100 −7.290
0.000 +0.900 +1.710
s=3
−8.10
a=−1 [πcrit ] a=0 a=+1
−8.100 −7.290 −6.561
0.000 +0.810 +1.539
s=4
−7.29
a=−1 [πcrit ] a=0 a=+1
−7.290 −6.561 −3.205
0.000 +0.729 +4.085
The positive Aπcrit for rightward actions reflects the fact that the moat states 5, 6 have low value under πcrit : transitioning into the moat is immediately costly and the future value J πcrit (5) = −3.56 ∗ is poor. Computing the k-step advantages of πdet : 17
k
Ak (1)
Ak (2)
Ak (3)
Ak (4)
Āk
1 2 3 4 5 6 7 10
+0.900 +2.439 +3.686 +6.664 +10.847 +2.013 −7.543 −30.851
+1.710 +3.095 +6.404 +11.053 +1.237 −9.381 −18.937 −42.245
+1.539 +5.216 +10.381 −0.526 −12.324 −22.942 −32.498 −55.805
+4.085 +9.824 −2.294 −15.403 −27.201 −37.819 −47.375 −70.682
+1.342 +3.481 +3.910 +4.165 +4.179 −5.139 −14.695 −38.003
At k = 6 the weighted average Āk first becomes negative, so kesc = 6. Note that state 4 escapes as early as k = 3 (its per-state advantage turns negative), but the high occupancy mass at state 1 (dπδ4crit (1) = 0.729) keeps Āk positive through k = 5. A.4
Fully Observable Two Path Navigation
Figure 6: A 3 × 5 grid where the agent starts at (2, 1) (µ = δ(2,1) ) and is forced upward each step. ∗ The optimal policy indicated in red πdet moves right incurring a minor penalty of +1 at (3, 2) and then passes through a high cost reduction intermediate state (3, 3) of −15 and is absorbing at (3, 5) which gives −20. The suboptimal policy πsub moves left passing through the minor cost reduction of −2 at (1, 3) and absorbs at a (1, 5) which gives a minor cost reduction of −5. Similar to the previous experiment, we will consider another fully observable example where a suboptimal critical point emerges. In this single-agent, fully observable experiment the state space is S = {1, 2, 3} × {1, . . . , 5} with the agent starting at (2, 1) (µ = δ(2,1) ). The row coordinate increases by 1 deterministically each step regardless of the action; the agent’s action a ∈ {−1, 0, +1} controls horizontal movement (clipped to columns {1, 2, 3}). The per-step cost is g(2, y) = +10 for y ≥ 2 (the crater column), g(1, 3) = −2, g(1, 5) = −5, g(3, 3) = −15, g(3, 5) = −20 g(3, 2) = +1, and g = 0 elsewhere. Both (1, 5) and (3, 5) are absorbing. We use γ = 0.9. The suboptimal policy πcrit always moves left, following (2, 1) → (1, 2) → · · · → (1, 5), ∗ with J πcrit (δ(2,1) ) = −34.43. The optimal policy πdet always moves right, following ∗ crit (2, 1) → (3, 2) → · · · → (3, 5), with J πdet (δ(2,1) ) = −142.47. The support of dπδ(2,1) is {(2, 1), (1, 2), (1, 3), (1, 4), (1, 5)}. Most states on the right path lie entirely outside this support, making the gradient dominance bound vacuous. crit crit crit The discounted occupancy under πcrit is dπδ(2,1) (2, 1) = 0.100, dπδ(2,1) (1, 2) = 0.090, dπδ(2,1) (1, 3) = πcrit πcrit πcrit 0.081, dδ(2,1) (1, 4) = 0.073, dδ(2,1) (1, 5) = 0.656 with dδ(2,1) (s) = 0 elsewhere.
18
At every support state, all three actions have Aπcrit ,1 (s, a) ≥ 0. The right-moving actions enter the crater (or hit the +1 penalty before moving into the crater), and the left-moving or stay actions either are already following πcrit or enters the crater. The full table of advantages across the support of crit dπδ(2,1) is shown below. State s
J πcrit (s)
Action a
Qπcrit (s, a)
Aπcrit (s, a)
(2, 1)
−34.425
a=−1 [πcrit ] a=0 ∗ a=+1 [πdet ]
−34.425 −25.425 −23.805
0.000 +9.000 +10.620
(1, 2)
−38.250
a=−1 [πcrit ] a=0 a=+1
−38.250 −38.250 −27.450
0.000 0.000 +10.800
(1, 3)
−42.500
a=−1 [πcrit ] a=0 a=+1
−42.500 −42.500 −33.500
0.000 0.000 +9.000
(1, 4)
−45.000
a=−1 [πcrit ] a=0 a=+1
−45.000 −45.000 −31.500
0.000 0.000 +13.500
(1, 5)
−50.000
a=−1 [πcrit ] a=0 a=+1
−50.000 −50.000 −36.500
0.000 0.000 +13.500
∗ Computing the k-step advantages of πdet (all actions set to right, a = +1):
k
Ak (1, 2)
Ak (1, 3)
Ak (1, 4)
Ak (1, 5)
Ak (2, 1)
Āk
1 2 3 4 5 10
+10.800 +21.735 +9.706 −1.119 −10.862 −46.771
+9.000 +7.785 −4.244 −15.069 −24.812 −60.721
+13.500 +12.285 +0.256 −10.569 −20.312 −56.221
+13.500 +12.285 +0.256 −10.569 −20.312 −56.221
+10.620 −2.340 +0.212 −10.614 −20.357 −56.266
+12.605 +11.309 +0.738 −10.088 −19.831 −55.740
At k = 4 the weighted average Āk first becomes negative, so kesc = 4. Four steps of lookahead are required to see past the crater penalty and notice that (3, 5) offers substantially lower long-run cost than (1, 5).
19
B
Proofs
B.1
k-step Policy Gradient Theorem
Below we prove the k-step Policy Gradient theorem in Theorem 5.5. The proof mirrors the standard policy gradient theorem proof from [1]. Proof for Theorem 5.5
Proof. ∇α J π̃α ,k (s0 )
(1) π̃α ,k
= ∇α Eπdet ∼π̃α [Q (s0 , πdet )] X π̃α ,k = ∇α π̃α (πdet )Q (s0 , πdet )
(2) (3)
πdet
=
X
(∇α π̃α (πdet ))Qπ̃α ,k (s0 , πdet ) +
X
π̃α (πdet )∇α Qπ̃α ,k (s0 , πdet )
(4)
πdet
πdet
=
X
(π̃α (πdet )∇α log π̃α (πdet ))Qπ̃α ,k (s0 , πdet ) + γ k
X
π̃α (πdet )Eτ k ∼πdet |s0 [∇α J π̃α ,k (sk )]
πdet
πdet
(5) π̃α ,k
X
π̃α ,k
(sk )] (6)
= ... ∞ X X X = γ mk P (smk = s|s0 , π̃α , k) π̃α (πdet )Qπ̃α ,k (smk , πdet )∇α log π̃α (πdet )
(7)
= Eπdet ∼π̃α [Q
(s0 , πdet )∇α log π̃α (πdet )] + γ
k
π̃α (πdet )Eτ k ∼πdet |s0 [∇α J
πdet
m=0
=
s∈S
(8)
πdet
1 E π̃α ,k Eπdet ∼π̃α [Qπ̃α ,k (s, πdet )∇α log π̃α (πdet )] 1 − γ k s∼ds0
(9)
Chain rule is used in Equation (4). For Equation (5), ∇α Qπ̃α ,k (s0 , πdet ) = k π̃α ,k γ Eτ k ∼πdet |s0 [∇α J (sk )] because the first k timesteps are not dependent on α. In Equation (6), τ k ∼ πdet |s0 refers to the trajectory generated by πdet starting at s0 up to timestep k. Equation (8) is obtained through recursive substitution of Equation (6). Lastly, Equation P∞ (9) is by the definition our k-step discounted state occupancy measure dπ̃s0α ,k (s) = (1 − γ k ) m=0 γ mk P (smk = s|s0 , π̃α , k). Taking expectation with respect to s0 ∼ µ gives Theorem 5.5 as desired. B.2
Main Results
Recall from Section 8 that the proofs of the main results will be split into two parts. In part 1), we will show an upper bound for the directional derivative which will prove Theorem 6.1 and will be used in part 2). We will then prove in Part 2), Theorem 6.2 and Theorem 6.3. B.2.1
Part 1) Approximate Gradient Dominance
Before proving Theorem 6.1, we will show the following bound on the directional derivative Lemma B.1 (Approximate Gradient Dominance). ∇π̃′ −π̃ J π̃,k (µ) ≤
1 6γ k π̃ ′ ,k π̃,k (J (µ) − J (µ)) + gmax 1 − γk (1 − γ k )(1 − γ)
20
Proof. Using the definition of the directional derivative, and a k-step variant of the performance difference lemma proved in Lemma B.3 we obtain: ′
J π̃+θ(π̃ −π̃),k (µ) − J π̃,k (µ) θ→0 θ ′ J (1−θ)π̃+θπ̃ ,k (µ) − J π̃,k (µ) = lim θ→0 θ π̃,k E (s, θπ̃ ′ + (1 − θ)π̃) − J π̃,k (s)] (1−θ)π̃+θ π̃ ′ ,k [Q 1 s∼dµ = lim θ→0 1 − γ k θ π̃,k (s, π̃ ′ ) + (1 − θ)Qπ̃,k (s, π̃) − J π̃,k (s)] π̃ ′ ,k [θQ 1 Es∼d(1−θ)π̃+θ µ = lim θ→0 1 − γ k θ π̃,k ′ ′ (s, π̃ ) − θJ π̃,k (s)] π̃ ,k [θQ 1 Es∼d(1−θ)π̃+θ µ = lim θ→0 1 − γ k θ 1 E (1−θ)π̃+θπ̃′ ,k [Qπ̃,k (s, π̃ ′ ) − J π̃,k (s)] = lim θ→0 1 − γ k s∼dµ 1 E π̃,k [Qπ̃,k (s, π̃ ′ ) − J π̃,k (s)] = 1 − γ k s∼dµ
∇π̃′ −π̃ J π̃,k (µ) = lim
(10) (11) (12) (13) (14) (15) (16)
In Equation (13), we use an affine property of the k-step Q-function in the correlated policy argument. This can be shown by viewing θπ̃ ′ + (1 − θ)π̃ as a policy where π̃ ′ or π̃ is chosen according to an independent indicator Iθ . Conditioning on whether π or π ′ is chosen as follows Eπdet ∼θπ̃′ +(1−θ)π̃ [Qπ̃,k (s, πdet )] = EIθ [Iθ Eπdet ∼π̃′ [Qπ̃,k (s, πdet )] + (1 − Iθ )Eπdet ∼π̃ [Qπ̃,k (s, πdet )]] = θEπdet ∼π̃′ [Qπ̃,k (s, πdet )] + (1 − θ)Eπdet ∼π̃ [Qπ̃,k (s, πdet )]. This hints at a major theoretical reason why we use correlated policies in this work. The direction θπ̃ ′ + (1 − θ)π̃ is still a correlated policy but stochastically interpolating state independent policies of the form π : S → ∆(A) may result in correlations that cannot be expressed with these state independent policies. P k Next, we will use s∈S |dπ̃,k µ (s) − µ(s)| ≤ 2γ proved in Lemma B.4 to change the expectation to π̃,k be over µ instead of dµ as follows: 1 E π̃,k [Qπ̃,k (s, π̃ ′ ) − J π̃,k (s)] (17) 1 − γ k s∼dµ 1 X 1 π̃,k Es∼µ [Qπ̃,k (s, π̃ ′ ) − J π̃,k (s)] + |µ(s) − dπ̃,k (s, π̃ ′ ) − J π̃,k (s)| ≤ µ (s)||Q k 1−γ 1 − γk s∈S
(18) k
1 4γ Es∼µ [Qπ̃,k (s, π̃ ′ ) − J π̃,k (s)] + gmax (19) 1 − γk (1 − γ k )(1 − γ) ′ ′ 1 4γ k = Es∼µ [J π̃ ,k (s) − J π̃,k (s) − (J π̃ ,k (s) − Qπ̃,k (s, π̃ ′ ))] + gmax k 1−γ (1 − γ k )(1 − γ) (20)
≤
=
≤
≤
1 4γ k π̃ ′ ,k π̃,k k π̃ ′ ,k π̃,k E [J (s) − J (s) − γ E (s ) − J (s )]] + gmax k ∼π̃ ′ | [J k k s∼µ τ s 1 − γk (1 − γ k )(1 − γ) (21) 1 −2 4γ k π̃ ′ ,k π̃,k k E [J (s) − J (s)] − γ E g ] + gmax k ∼π̃ ′ | [ s∼µ max τ s 1 − γk (1 − γ) (1 − γ k )(1 − γ) (22) 1 6γ k π̃ ′ ,k π̃,k (J (µ) − J (µ)) + gmax 1 − γk (1 − γ k )(1 − γ)
which gives the lemma statement as desired.
21
(23)
Now to prove Theorem 6.1, notice for any critical point π̃crit , the directional derivative ∇π̃′ −π̃crit J π̃crit ,k (µ) exists for any π̃ ′ ∈ Π̃res by differentiability. Further, the assumption in Section 5.2 implies the domain Π̃res is convex and therefore (1 − θ)π̃ + θπ̃ ′ ∈ Π̃res . Therefore, a small change of π̃crit along the direction of π̃ ′ − π̃crit will keep it in Π̃res . So, all zero gradient critical points will have ∇π̃′ −π̃crit J π̃crit ,k (µ) = 0 and local minima on the boundary will have ∇π̃′ −π̃crit J π̃crit ,k (µ) ≥ 0 for any π̃ ′ ∈ Πres because otherwise, it would contradict πcrit having a zero gradient (all directional derivatives zero) or being a local minima (all directional derivatives in a direction staying in Π̃res are ≥ 0). Proof for Theorem 6.1: ∗ Proof. Using Lemma B.1 and the argument above with π̃ ∗ = δ(πdet ) ∈ Πres in place of π̃ ′ and π̃crit in place of π̃, this yields: k
∗
1 πdet 0 ≤ ∇π̃∗ −π̃crit J π̃crit ,k (µ) ≤ 1−γ (µ) − J π̃crit ,k (µ)) + (1−γ6γ k (J k )(1−γ) gmax
simplifying to k
∗
6γ gmax J π̃crit ,k (µ) − J πdet (µ) ≤ 1−γ
This gives Theorem 6.1 when the the difference between Eπdet ∼π̃crit [J πdet (µ)] and J π̃crit ,k (µ) is bounded as follows: ∗
∗
Eπdet ∼π̃crit [J πdet (µ)] − J πdet (µ) = J π̃crit ,k (µ) − J πdet (µ) + (Eπdet ∼π̃crit [J πdet (µ)] − J π̃crit ,k (µ)) (24) ∗
k
≤ J π̃crit ,k (µ) − J πdet (µ) + ≤
2γ gmax 1−γ
(25)
8γ k gmax . 1−γ
(26)
Here, Equation (25) uses that both terms Eπdet ∼π̃crit [J πdet (µ)] and J π̃crit ,k (µ) have the same distribution of states and actions in the first k iterations.
B.2.2
Part 2.1) Projected Gradient Descent
Proof for Theorem 6.2: Proof. Projected gradient descent is a special case of mirror descent with mirror map Φ(x) = 12 ∥x∥22 which is 1-strongly convex. The Bregman divergence takes the form DΦ (x, y) = 12 ∥x∥22 − 12 ∥y∥22 − y T (x − y) = 12 ∥x − y∥22 . Using Theorem 6.3, we obtain Eπdet ∼π̃T [J
πdet
(µ)] − J
∗ πdet
8γ k 1 ∗ (µ) ≤ gmax + βDΦ (π̃ , π̃0 ) 1−γ T 8γ k 1 β ∗ ≤ gmax + ∥π̃ − π̃0 ∥22 1−γ T 2
(27) (28)
as desired. B.2.3
Part 2.2) Mirror Descent
Lemma B.2. Mirror descent with the same conditions as Theorem 6.3 converges and satisfies the following bound: T −1
1 X 1 −∇π̃∗ −π̃t J π̃t ,k (µ) ≤ T t=0 T
T −1 β 1 X π̃t+1 ,k ∗ DΦ (π̃ , π̃0 ) − (J (µ) − J π̃t ,k (µ)) λ T t=0 22
∗ where π ∗ = δ(πdet ) ∈ Πres is the Dirac delta of the optimal deterministic policy.
Proof. Mirror descent will converge due to the descent lemma shown in Lemma B.6. ′
To prove the bound, we will evoke the smoothness of the objective J π̃ ,k (µ) ≤ J π̃,k (µ) + ⟨∇J π̃,k (µ), π̃ ′ − π̃⟩ + β2 ∥π̃ ′ − π̃∥2 . Next by the definition of the Bregman Divergence, µ-strong convexity of Φ implies DΦ (π̃ ′ , π̃) ≥ λ2 ∥π̃ ′ − π̃∥2 . Lastly, we will use a consequence of the threepoint equality ⟨∇J π̃t ,k (µ), π̃t+1 − π̃ ∗ ⟩ ≤ η1 (DΦ (π̃ ∗ , π̃t ) − DΦ (π̃ ∗ , π̃t+1 ) − DΦ (π̃t+1 , π̃t )) proved in Lemma B.5. We will create a bound on −∇π̃∗ −π̃t J π̃t ,k as follows: −∇π̃∗ −π̃t J π̃t ,k = ⟨∇J π̃t ,k (µ), π̃t − π̃ ∗ ⟩ = ⟨∇J
π̃t ,k
∗
(µ), π̃t − π̃ ⟩ + ⟨∇J
(29) π̃t ,k
(µ), π̃t+1 − π̃t ⟩ − ⟨∇J
π̃t ,k
(µ), π̃t+1 − π̃t ⟩ (30)
= ⟨∇J π̃t ,k (µ), π̃t+1 − π̃ ∗ ⟩ − ⟨∇J π̃t ,k (µ), π̃t+1 − π̃t ⟩ (31) β ≤ ⟨∇J π̃t ,k (µ), π̃t+1 − π̃ ∗ ⟩ + ∥π̃t+1 − π̃t ∥2 − (J π̃t+1 ,k (µ) − J π̃t ,k (µ)) (32) 2 β (33) ≤ ⟨∇J π̃t ,k (µ), π̃t+1 − π̃ ∗ ⟩ + DΦ (π̃t+1 , π̃t ) − (J π̃t+1 ,k (µ) − J π̃t ,k (µ)) λ β 1 ≤ (DΦ (π̃ ∗ , π̃t ) − DΦ (π̃ ∗ , π̃t+1 ) − DΦ (π̃t+1 , π̃t )) + DΦ (π̃t+1 , π̃t ) − (J π̃t+1 ,k (µ) − J π̃t ,k (µ)) η λ (34) β 1 1 = (DΦ (π̃ ∗ , π̃t ) − DΦ (π̃ ∗ , π̃t+1 )) + ( − )DΦ (π̃t+1 , π̃t ) − (J π̃t+1 ,k (µ) − J π̃t ,k (µ)) η λ η (35) 1 ≤ (DΦ (π̃ ∗ , π̃t ) − DΦ (π̃ ∗ , π̃t+1 )) − (J π̃t+1 ,k (µ) − J π̃t ,k (µ)) (36) η Equation (32), Equation (33), Equation (34) are the applications of the smoothness condition, lower bound on Bregman divergence, and Lemma B.5 respectively. In Equation (35), our chosen learning rate η = βλ is used. Averaging both sides across the iterations yields: T −1 T −1 T −1 1 X 1 X π̃t+1 ,k 1 X −∇π̃∗ −π̃t J π̃t ,k (µ) ≤ (DΦ (π̃ ∗ , π̃t ) − DΦ (π̃ ∗ , π̃t+1 )) − (J (µ) − J π̃t ,k (µ)) T t=0 T η t=0 T t=0 (37) T −1 1 1 X π̃t+1 ,k (DΦ (π̃ ∗ , π̃0 ) − DΦ (π̃ ∗ , π̃T )) − (J (µ) − J π̃t ,k (µ)) Tη T t=0 (38) T −1 1 X π̃t+1 ,k 1 β ≤ (µ) − J π̃t ,k (µ)) (39) DΦ (π̃ ∗ , π̃0 ) − (J T λ T t=0
=
where the learning rate η = βλ is use once again.
This result is then combined with Lemma B.1 to prove Theorem 6.3. Proof for Theorem 6.3: 1 π̃t ,k Proof. Lemma B.1 is evoked with π̃t and π̃ ∗ which gives −∇π̃∗ −π̃t J π̃t ,k (µ) ≥ 1−γ (µ) − k (J ∗
k
J πdet (µ)) − (1−γ6γ k )(1−γ) gmax 23
Substituting into Lemma B.2, T −1
T −1
∗ 6γ k 1 X π̃t ,k 1 β 1 − γ k X π̃t+1 ,k J (µ) − J πdet (µ) ≤ (J (µ) − J π̃t ,k (µ)) gmax + (1 − γ k ) DΦ (π̃ ∗ , π̃0 ) − T t=0 1−γ T λ T t=0 (40)
T −1 6γ k 1β 1 X π̃t+1 ,k ∗ ≤ (J gmax + DΦ (π̃ , π̃0 ) − (µ) − J π̃t ,k (µ)) 1−γ Tλ T t=0 (41) PT −1 π̃t+1 ,k Here Equation (41) uses that t=0 (J (µ) − J π̃t ,k (µ)) is negative by the descent lemma in Lemma B.6.
Combining the sums together with the descent lemma shown in Lemma B.6 gives the last iterate performance bound T −1
π̃T ,k
J
(µ) − J
∗ πdet
∗ 1 X π̃t+1 ,k (µ) ≤ J (µ) − J πdet (µ) T t=0 6γ k 1 β ≤ gmax + DΦ (π̃ ∗ , π̃0 ) 1−γ T λ
Following similar steps to Section B.2.1, results in ∗
Eπdet ∼π̃T [J πdet (µ)] − J πdet (µ)
(42)
k
∗ 2γ ≤ J π̃T ,k (µ) − J πdet (µ) + gmax 1−γ 8γ k 1 β ≤ gmax + DΦ (π̃ ∗ , π̃0 ) . 1−γ T λ
B.3
(43) (44)
Intermediate Lemmas
Lemma B.3 (k-step Performance Difference Lemma). J π̃1 ,k (µ) = J π̃2 ,k (µ) −
1 E π̃2 ,k [Aπ̃1 ,k (s, π̃2 )] 1 − γ k s∼dµ
where Aπ̃1 ,k (s, π̃2 ) = Qπ̃1 ,k (s, π̃2 ) − J π̃1 ,k (s) is the k-step advantage function. Proof. Following similar steps to the traditional performance difference lemma proof, J π̃1 ,k (s0 ) = Qπ̃1 ,k (s0 , π̃2 ) − Qπ̃1 ,k (s0 , π̃2 ) + J π̃1 ,k (s0 ) π̃1 ,k
=Q
(s0 , π̃2 ) − A k−1 X
= Eτ k ∼π̃2 |s0 [
π̃1 ,k
(s0 , π̃2 )
(45) (46)
γ t g(st , at ) + γ k J π̃1 ,k (sk )] − Aπ̃1 ,k (s, π̃2 )
(47)
t=0
= ... = J π̃2 ,k (s0 ) −
(48) ∞ X m=0
= J π̃2 ,k (s0 ) −
γ mk
X
P (smk = s|s0 , π̃2 , k)Aπ̃1 ,k (smk , π̃2 )
(49)
s∈S
1 E π̃2 ,k [Aπ̃1 ,k (s, π̃2 )] 1 − γ k s∼ds0
(50)
In Equation (49), we recursively substitute our expression for J π̃1 ,k (s0 ). 1 π̃1 ,k Taking expectations on both sides, J π̃1 ,k (µ) = J π̃2 ,k (µ) − 1−γ (s, π̃2 )] k Es∼dπ̃2 ,k [A µ
24
Lemma B.4.
π̃,k k s∈S |µ(s) − dµ (s)| ≤ 2γ
P
Proof. The following bounds the difference between µ and dπ̃,k µ : X
|µ(s) − dπ̃,k µ (s)| =
s∈S
X
µ(s) − (1 − γ k )
X
γ mk P (sk = s|µ, π̃, k)
µ(s) − (1 − γ k )µ(s) − (1 − γ k )
X
∞ X
γ mk P (sk = s|µ, π̃, k)
(52)
m=1
s∈S
=
(51)
m=0
s∈S
=
∞ X
γ k µ(s) − γ k (1 − γ k )
γ (m−1)k P (sk = s|µ, π̃, k)
m=1 ∞ X k
s∈S
= (2γ k )
∞ X
1X µ(s) − (1 − γ ) 2 s∈S
′
γ m k P (sk = s|µ, π̃, k)
(53)
(54)
m′ =0
≤ 2γ k .
(55)
The last step uses that the total variation distance of any two distributions is bounded by 1. Lemma B.5. Mirror descent under the same assumptions of Theorem 6.3 will satisfy ⟨∇J π̃t ,k (µ), π̃t+1 − π̃⟩ ≤
1 (DΦ (π̃, π̃t ) − DΦ (π̃, π̃t+1 ) − DΦ (π̃t+1 , π̃t )) η
for any π̃ ∈ Π̃res . Proof. Let Ft (π̃) = η⟨∇J π̃t ,k (µ), π̃⟩ + DΦ (π̃, π̃t ). Note that π̃t+1 is a minimizer of this function by definition. Further, Ft is convex in π̃ and therefore π̃t+1 is globally optimal for Ft . Therefore, ⟨∇Ft (π̃t+1 ), π̃ − π̃t+1 ⟩ ≥ 0 or equivalently ⟨∇Ft (π̃t+1 ), π̃t+1 − π̃⟩ ≤ 0. ∇Ft (π̃) can be simplified using the definition of the Bregman Divergence DΦ (x, y) = Φ(x)−Φ(y)− ∇Φ(y)T (x − y) as follows: ∇Ft (π̃) = η∇J π̃t ,k (µ) + ∇DΦ (π̃, π̃t ) = η∇J π̃t ,k (µ) + ∇Φ(π̃) − ∇Φ(π̃t ). Plugging this expression into ⟨∇Ft (π̃t+1 ), π̃t+1 − π̃⟩ ≤ 0, we get η⟨∇J π̃t ,k (µ), π̃t+1 − π̃⟩ ≤ ⟨∇Φ(π̃t ) − ∇Φ(π̃t+1 ), π̃t+1 − π̃⟩ = DΦ (π̃, π̃t ) − DΦ (π̃, π̃t+1 ) − DΦ (π̃t+1 , π̃t ) using the three point property of Bregman Divergences (∇Φ(x) − ∇Φ(y))T (x − z) = DΦ (x, y) + DΦ (z, x) − DΦ (z, y) as desired. Lemma B.6. Mirror descent under the same assumptions of Theorem 6.3 will satisfy J π̃t+1 ,k (µ) − J π̃t ,k (µ) ≤ −
λ ∥π̃t+1 − π̃t ∥2 2η
Proof. By the β-smoothness of J π̃,k (µ), we have β ∥π̃t+1 − π̃t ∥2 2 1 β ≤ J π̃t ,k (µ) − (DΦ (π̃t+1 , π̃t ) + DΦ (π̃t , π̃t+1 )) + ∥π̃t+1 − π̃t ∥2 η 2 λ β ≤ J π̃t ,k (µ) − ∥π̃t+1 − π̃t ∥2 + ∥π̃t+1 − π̃t ∥2 η 2 λ β = J π̃t ,k (µ) − ( − )∥π̃t+1 − π̃t ∥2 η 2 λ = J π̃t ,k (µ) − ∥π̃t+1 − π̃t ∥2 . 2η
J π̃t+1 ,k (µ) ≤ J π̃t ,k (µ) + ⟨∇J π̃t ,k (µ), π̃t+1 − π̃t ⟩ +
25
(56) (57) (58) (59) (60)
In Equation (57), we evoke Lemma B.5 with π̃t as π̃. In Equation (58), we evoke the λ-strong convexity of Φ, the Bregman Divergence satisfies DΦ (π̃ ′ , π̃) ≥ λ2 ∥π̃ ′ − π̃∥2 . In Equation (60), we use η = βλ .
C
Potential Pitfall - Alternative k-step Definition:
The following is a tempting but unsuccessful alternative k-step construction that at first glance may appear promising. Suppose we return to the original policy definition π : S → ∆(A) and simply maintain k independent policies {π j : π j ∈ Πres , 0 ≤ j < k} that would cycled through and executed one after the other independently. This seems as though it may allow extra “directions of movement” that would allow a descent on these chain of policies to escape poor suboptimal local minima. Unfortunately, it can be verified by simulation that the suboptimal local minima in the two state example from Section 4.2 is not removed with this scheme even for large k. Intuitively, the reason is because the argument from Section 4.3 still causes myopicness in this alternative scheme. The two state example under this scheme will have policies of the form πθ1 , πθ1 , . . . , πθk that can have different θ-parameters at each step. But the policy with θi = 0 for 0 ≤ i < k will remain a critical point because when perturbed by dθi for parameter θi , the probability of sampling trajectories taking action R more than one time will include products of these dθi . Similar to Section 4.3, these will be treated as higher order terms.
26