Title: MARGINAL POLICY GRADIENTS: A UNIFIED FAMILY OF ESTIMATORS FOR BOUNDED ACTION SPACES WITH APPLICATIONS

Abstract: Many complex domains, such as robotics control and real-time strategy (RTS) games, require an agent to learn a continuous control. In the former, an agent learns a policy over R d and in the latter, over a discrete set of actions each of which is parametrized by a continuous parameter. Such problems are naturally solved using policy based reinforcement learning (RL) methods, but unfortunately these often suffer from high variance leading to instability and slow convergence. Unnecessary variance is introduced whenever policies over bounded action spaces are modeled using distributions with unbounded support by applying a transformation T to the sampled action before execution in the environment. Recently, the variance reduced clipped action policy gradient (CAPG) was introduced for actions in bounded intervals, but to date no variance reduced methods exist when the action is a direction, something often seen in RTS games. To this end we introduce the angular policy gradient (APG), a stochastic policy gradient method for directional control. With the marginal policy gradients family of estimators we present a unified analysis of the variance reduction properties of APG and CAPG; our results provide a stronger guarantee than existing analyses for CAPG. Experimental results on a popular RTS game and a navigation task show that the APG estimator offers a substantial improvement over the standard policy gradient.

1. INTRODUCTION:

Recent work in deep reinforcement learning (RL) has achieved human level-control for complex tasks like Atari 2600 games and the ancient game of Go. Mnih et al. (2015) show that it is possible to learn to play Atari 2600 games using end to end reinforcement learning. Other authors (Silver et al., 2014) derive algorithms tailored to continuous action spaces, such as appear in problems of robotics control. Today, solving RTS games is a major open problem in RL (Foerster et al., 2016; Usunier et al., 2017; Vinyals et al., 2017) ; these are more challenging than previously solved game domains because the action and state spaces are far larger. In RTS games, actions are no longer chosen from a relatively small discrete action set as in other game types. Neither is the objective solely learning a continuous control. Instead the action space typically consists of many discrete actions each of which has a continuous parameter. For example, a discrete action in an RTS game might be moving the player controlled by the agent with a parameter specifying the movement direction. Because the agent must learn a continuous parameter for each discrete action, a policy gradient method is a natural approach to an RTS game. Unfortunately, obtaining stable, sample-efficient performance from policy gradients remains a key challenge in model-free RL.

Just as robotics control tasks often have actions restricted to a bounded interval, Multi-player Online Battle Arena (MOBA) games, an RTS sub-genre, often have actions restricted to the unit sphere which specify a direction (e.g. to move or attack). The current practice, despite most continuous control problems having bounded action spaces, is to use a Gaussian distribution to model the policy and then apply a transformation T to the action a before execution in the environment. This support mismatch between the sampling action distribution (i.e. the policy π), and the effective action distribution can both introduce bias to and increase the variance of policy gradient estimates (Chou et al., 2017; Fujita & Maeda, 2018) . For an illustration of how the distribution over actions a is transformed under T (a) = a/||a||, see Figure 1 in Section 3.

In this paper, motivated by an application to a MOBA game, we study policy gradient methods in the context of directional actions, something unexplored in the RL literature. Like CAPG for actions in an interval [α, β], our proposed algorithm, termed angular policy gradient (APG), uses a variance-reduced, unbiased estimated of the true policy gradient. Since the key step in APG is an update based on an estimate of the policy gradient, it can easily be combined with other state-of-the art methodology including value function approximation and generalized advantage estimation (Sutton et al., 2000; Schulman et al., 2016) , as well as used in policy optimization algorithms like TRPO, A3C, and PPO (Schulman et al., 2015; Mnih et al., 2016; Schulman et al., 2017) .

Beyond new methodology, we also introduce the marginal policy gradients (MPG) family of estimators; this general class of estimators contains both APG and CAPG, and we present a unified analysis of the variance reduction properties of all such methods. Because marginal policy gradient methods have already been shown to provide substantial benefits for clipped actions (Fujita & Maeda, 2018) , our experimental work focuses only on angular actions; we use a marginal policy gradient method to learn a policy for the 1 vs. 1 map of the King of Glory game and the Platform2D-v1 navigation task, demonstrating improvement over several baseline policy gradient approaches.

1.1. RELATED WORK:

Model-Free RL. Policy based methods are appealing because unlike value based methods they can support learning policies over discrete, continuous and parametrized action spaces. It has long been recognized that policy gradient methods suffer from high variance, hence the introduction of trust region methods like TRPO and PPO (Schulman et al., 2015; 2017) . Mnih et al. (2016) leverage the independence of asynchronous updating to improve stability in actor-critic methods. See Sutton & Barto (2018) for a general survey of reinforcement learning algorithms, including policy based and actor-critic methods. Recent works have applied policy gradient methods to parametrized action spaces in order to teach an agent to play RoboCup soccer (Hausknecht & Stone, 2016; Masson et al., 2016) . Formally, a parametrized action space A over K discrete, parametrized actions is defined as

A := k {(k, ω) : ω ∈ Ω k }, where k ∈ [K]

and Ω k is the parameter space for the k th action. See Appendix B.5 for rigorous discussion of the construction of a distribution over parametrized action spaces and the corresponding policy gradient algorithms.

Bounded Action Spaces. Though the action space for many problems is bounded, it is nonetheless common to model a continuous action using the multivariate Gaussian, which has unbounded support (Hausknecht & Stone, 2016; Florensa et al., 2017; Finn et al., 2017) . Until recently, the method for dealing with this type of action space was to sample according to a Gaussian policy and then either (1) allow the environment to clip the action and update according to the unclipped action or (2) clip the action and update according to the clipped action (Chou et al., 2017) . The first approach suffers from unnecessarily high variance, and the second approach is off-policy.

Recent work considers variance reduction when actions are clipped to a bounded interval (Chou et al., 2017; Fujita & Maeda, 2018) . Depending upon the way in which the Q-function is modeled, clipping has also been shown to introduce bias (Chou et al., 2017) . Previous approaches are not applicable to the case when T is the projection onto the unit sphere; in the case of clipped actions, unlike previous work, we do not require that each component of the action is independent and obtain much stronger variance reduction results. Concurrent work (Fellows et al., 2018 ) also considers angular actions, but their method cannot be used as a drop in replacement in state of the art methods and the a special form of the critic q π is required.

Integrated Policy Gradients. Several recent works have considered, as we do, exploiting an integrated form of policy gradient (Ciosek & Whiteson, 2018; Asadi et al., 2017; Fujita & Maeda, 2018; Tamar et al., 2012) . Ciosek & Whiteson (2018) introduces a unified theory of policy gradients, which subsumes both deterministic (Silver et al., 2014) and stochastic policy gradients (Sutton et al., 2000) . They characterize the distinction between different policy gradient methods as a choice of quadrature for the expectation. Their Expected Policy Gradient algorithm uses a new way of estimating the expectation for stochastic policies. They prove that the estimator has lower variance than stochastic policy gradients. Asadi et al. (2017) propose a similar method, but lack theoretical guarantees. Fujita & Maeda (2018) introduce the clipped action policy gradient (CAPG) which is a partially integrated form of policy gradient and provide a variance reduction guarantee, but their result is not tight. By viewing CAPG as a marginal policy gradient we obtain tighter results.

Variance Decomposition. The law of total variance, or variance decomposition, is given by Var

[Y ] = E[Var(Y |X)] + Var[E[Y |X]],

where X and Y are two random variables on the same probability space. Our main result can be viewed as a special form of law of total variance, but it is highly non-trivial to obtain the result directly from the law of total variance. Also related to our approach is Rao-Blackwellization (Blackwell, 1947) of a statistic to obtain a lower variance estimator.

2. PRELIMINARIES:

Notation and Setup. For MDP's we use the standard notation. S is the state space, A is the action space, p denotes the transition probability kernel, p 0 the initial state distribution, r the reward function. A policy π(a|s) is a distribution over actions given a state s ∈ S. A sample trajectory under π is denoted τ π := (s 0 , a 0 , r 1 , s 1 , a 1 , . . . ) where s 0 ∼ p 0 and a t ∼ π(•|s t ). The statevalue function is defined as v π (s) := E π [ ∞ t=0 γ t r t+1 |s 0 = s] and the action-value function as

q π (s, a) := E π [ ∞ t=0 γ t r t+1 |s 0 = s, a 0 = a]. The objective is to maximize expected cumulative discounted reward, η(π) = E p0 [v π (s 0 )

]. ρ π denotes the improper discounted state occupancy distribution, defined as ρ π := t γ t E p0 [P(s t = s|s 0 , π)]. We make the standard assumption of bounded rewards.

We consider the problem of learning a policy π parametrized by θ ∈ Θ. All gradients are with respect to θ unless otherwise stated. By convention, we define 0 • ∞ = 0 and 0 0 = 0. A measurable space (A, E) is a set A with a sigma-algebra E of subsets of A. When we refer to a probability distribution of a random variable taking values in (A, E) we will work directly with the probability measure on (A, E) rather than the underlying sample space. For a measurable mapping T from measure space (A, E, λ) to measurable space (B, F), we denote by T * λ the push-forward of λ. S d-1 denotes the unit sphere in R d and for any space A, B(A) denotes the Borel σ-algebra on A. The notation µ ν signifies the measure µ is absolutely continuous with respect to ν. The function clip is defined as clip(a, α, β) = min(β, max(α, a)) for a ∈ R. If a ∈ R d , it is interpreted element-wise.

Variance of Random Vectors. We define the variance of a random vector y as Var(y) = E[(y -Ey) (y -Ey)], i.e. the trace of the covariance of y; it is easy to verify standard properties of the variance still hold. This definition is often used to analyze the variance of gradient estimates (Greensmith et al., 2004) .

Stochastic Policy Gradients.:

In Section 4 we present marginal policy gradient estimators and work in the very general setting described below. Let (A, E, µ) be a measure space, where as before A is the action space of the MDP. In practice, we often encounter (A, E) = (R d , B(R d )) with µ as the Lebesgue measure. The types of policies for which there is a meaningful notation of stochastic policy gradients are µ-compatible measures (see remarks 2.3 and 2.4).

Definition 2.1 (µ-Compatible Measures). Let (A, E, µ) be a measure space and consider a parametrized family of measures Π = {π(•, θ) : θ ∈ Θ} on the same space. Π is a µ-compatible family of measures if for all θ:

(a) π(•, θ) µ with density of the form f π (•, θ), (b) f π is differentiable in θ, and (c) π satisfies the conditions to apply the Leibniz integral rule for each θ, so that

∇ A f π (a)dµ = A ∇f π (a)dµ.

For µ-compatible policies, Theorem 2.2 gives the stochastic policy gradient, easily estimable from samples. When µ is the counting measure we recover the discrete policy gradient theorem (Sutton et al., 2000) . See Appendix A.1 for a more in depth discussion and a proof of Theorem 2.2, which we include for completeness. Theorem 2.2 (Stochastic Policy Gradient). Let (A, E, µ) be a measure space and let Π = {π(•, θ|s) : θ ∈ Θ} be a family of µ-compatible probability measures. Denoting by f π the density with respect to µ, we have that

∇η = S dρ π (s) A q π (s, a)∇ log f π (a|s)dπ(•|s).

In general we want an estimate g of ∇η such that it is unbiased (E[g] = ∇η) and that has minimal variance, so that convergence to a (locally) optimal policy is as fast as possible. In the following sections, we explore a general approach to finding a low variance, unbiased estimator. Remark 2.3. Under certain choices of T (e.g. clipping) the effective action distribution is a mixture of a continuous distribution and point masses. Thus, although it adds some technical overhead, it is necessary that we take a measure theoretic approach in this work.

Remark 2.4. Definition 2.1 is required to ensure the policy gradient is well defined, as it stipulates the existence of an appropriate reference measure; it also serves to clarify notation and to draw a distinction between π and its density f π . Though these details are often minimized they are important in analyzing the interaction between T and π.

3. ANGULAR POLICY GRADIENTS:

Consider the task of learning a policy over directions in A = R 2 , or equivalently learning a policy over angles [0, 2π) . A naive approach is to fit the mean m θ (s), model the angle as normally distributed about m θ , and then clip the sampled angle before execution in the environment. However, this approach is asymmetric in that does not place similar probability on m θ (s)and m θ (s) + for m θ (s) near to 0 and 2π.

An alternative is to model m θ (s) ∈ R 2 , sample a ∼ N (m θ (s), Σ), and then execute T (a) := a/||a|| in the environment. This method also works for directional control in R d . The drawback of this approach is the following: informally speaking, we are sampling from a distribution with d degrees of freedom, but the environment is affected by an action with only d -1 degrees of freedom. This suggests, and indeed we later prove, that the variance of the stochastic policy gradient for this distribution is unnecessarily high. In this section we introduce the angular policy gradient which can be used as a drop-in replacement for the policy update step in existing algorithms. 

ANGULAR GAUSSIAN DISTRIBUTION:

Instead, we can directly model

T (a) ∈ S d-1 instead of a ∈ R d . If a ∼ N (m θ (s), Σ θ (s)), then T (a)

is distributed according to what is known as the angular Gaussian distribution (Definition 3.1). It can be derived by a change of variables to spherical coordinates, followed by integration with respect to the magnitude of the random vector (Paine et al., 2018) . Figure 1 illustrates the transformation of a Gaussian sampling policy π under T . Definition 3.1 (Angular Gaussian Distribution). Let a ∼ N (m, Σ). Then, with respect to the spherical measure σ on (S d-1 , B(S d-1 )), x = a/||a|| has density

EQUATION

where

α = x Σ -1 m (x Σ -1 x) 1/2 and M d-1 (x) = (2π) -1 2 ∞ 0 u d-1 exp(-(u -x) 2 /2)du.

POLICY GRADIENT METHOD:

Although the density in Definition 3.1 does not have a closed form, we can still obtain a stochastic policy gradient for this type of policy. Define the action space as A := S d-1 and consider angular Gaussian policies parametrized by θ := (θ m , θ Σ ), where θ m parametrizes m and θ Σ parametrizes Σ.

As before, denote the corresponding parametrized family of measures as Π := {π(•, θ|s) : θ ∈ Θ}.

Directly from Definition 3.1, we obtain

log f π = 1 2 α 2 -m Σ -1 m + log M d-1 (α) - 1 2 (d -1) log 2π + log |Σ| + d log x Σx .

Though this log-likelihood does not have a closed form, it turns out it is easy to compute the gradient in practice. It is only necessary that we can evaluate M d-1 (α) and M d (α) easily. Assuming for now that we can do so, denote by θ i the parameters after i gradient updates and define

l i (θ) := 1 2 α 2 -m Σ -1 m + M d-1 (α(θ i )) M d-1 (α(θ i )) (i) α - 1 2 (d -1) log 2π + log |Σ| + d log x Σx . By design, ∇ log f π (θ)| θ=θi = ∇l i (θ)| θ=θi ,

thus at update i it suffices to compute the gradient of l i , which can be done using standard autodifferentiation software (Paszke et al., 2017) since term (i) is a constant. From Paine et al. (2018) , we have that

M d (α) = dM d-1 (α), M d+1 (α) = αM d (α) + dM d-1 (α), M 1 (α) = αΦ(α) + φ(α)

and M 0 (α) = Φ(α), where Φ, φ denote the PDF and CDF of N (0, 1), respectively. Leveraging these properties, the integral M d (α) can be computed recursively; Algorithm 1 in Appendix B.1 gives psuedo-code for the computation. Importantly it runs in O(d) time and therefore does not effect the computational cost of the policy update since it is dominated by the cost of computing ∇l i . In addition, stochastic gradients of policy loss functions for TRPO or PPO Schulman et al. (2015; 2017) can be computed in a similar way since we can easily get the derivative of f π (θ) when M d-1 (α) and M d-1 (α) are known.

4. MARGINAL POLICY GRADIENT ESTIMATORS:

In Section 2, we described a general setting in which a stochastic policy gradient theorem holds on a measure space (A, E, λ) for a family of λ-compatible probability measures, Π = {π(•, θ|s) : θ ∈ Θ}.

As before, we are interested in the case when the dynamics of the environment only depend on a ∈ A via a function T . That is to say r(s, a) := r(s, T (a)) and p(s, a, s ) := p(s, T (a), s ).

The key idea in Marginal Policy Gradient is to replace the policy gradient estimate based on the log-likelihood of π with a lower variance estimate, which is based on the log-likelihood of T * π. T * π can be thought of as (and in some cases is) a marginal distribution, hence the name Marginal Policy Gradient. For this reason it can easily be used with value function approximation and GAE, as well as incorporated into algorithms like TRPO, A3C and PPO.

4.1. SETUP AND REGULARITY CONDITIONS:

For our main results we need regularity Condition 4.1 on the measure space (A, E, λ). Next, let (B, F) be another measurable space and T : A → B be a measurable mapping. T induces a family of probability measures on (B, F), denoted T * Π := {T * π(•, θ|s) : θ ∈ Θ}. We also require regularity Conditions 4.2 and 4.3 regarding the structure of F and the existence of a suitable reference measure µ on (B, F). These conditions are all quite mild and are satisfied in all practical settings, to the best of our knowledge. Condition 4.1 . A is a metric space and λ is a Radon measure. 1Condition 4.2 . F is countably generated and contains the singleton sets {b}, for all b ∈ B. Condition 4.3 . There exists a σ-finite measure µ on (B, F) such that T * λ µ and T * Π is µcompatible.

In statistics, Fisher information is used to capture the variance of a score function. In reinforcement learning, typically one encounters a score function that has been rescaled by a measurable function q(a). Definition 4.4 provides a variant of Fisher information for λ-compatible distributions and rescaled score functions; we defer a discussion of the definition until Section 4.4 after we present our results in their entirety. If q(a) = 1, Definition 4.4 is the trace of the classical Fisher Information. Definition 4.4 (Total Scaled Fisher Information). Let (A, E, λ) be a measure space, Π = {π(•, θ) : θ ∈ Θ} be a family of λ-compatible probability measures, and q a measurable function on E. The total scaled fisher information is defined as I π,λ (q, θ)

:= E[q(a) 2 ∇ log f π (a) ∇ log f π (a)]. 4.2 VARIANCE REDUCTION GUARANTEE From Theorem 2.2 it is immediate that ∇η(θ) = S dρ(s) A q(T (a), s)∇ log f π (a|s)dπ(a|s) = S dρ(s) B q(b, s)∇ log f T * π (b|s)d(T * π)(b|s),

where we dropped the subscripts on ρ and q because the two polices affect the environment in the same way, and thus have the same value function and discounted state occupancy measure. Denote the two alternative gradient estimators as g 1 = q(T (a), s)∇ log f π (a|s) and g 2 = q(b, s)∇ log f T * π (b|s). Just by definition, we have that E ρ,π [g 1 ] = E ρ,π [g 2 ]. Lemma 4.5 says something slightly differentit says that they are also equivalent in expectation conditional on the state s, a fact we use later. Lemma 4.5. Let (A, E, λ) and (B, F, µ) be measure spaces, and T : A → B be measurable mapping. If Π, parametrized by θ, is λ-compatible and T * Π is µ-compatible, then

E π|s [g 1 ] = E π|s [g 2 ] = E T * π|s [g 2 ] .

(4.1)

Proof. The result follows immediately from the proof of Theorem 2.2 in Appendix A.1.

Because the two estimates g 1 and g 2 are both unbiased, it is always preferable to use whichever has lower variance. Theorem 4.6 shows that g 2 is the lower variance policy gradient estimate. See Appendix B.3 for the proof. The implication of Theorem 4.6 is that if there is some information loss via a function T before the action interacts with the dynamics of the environment, then one obtains a lower variance estimator of the gradient by replacing the density of π with the density of T * π in the expression for the policy gradient. Theorem 4.6. Let g 1 and g 2 be as defined above. Then if Conditions 4.1-4.3 are satisfied,

Var ρ,π (g 1 ) -Var ρ,T * π (g 2 ) = E ρ,T * π I π|s|b,λ b (q • T, θ) ≥ 0,

for some family of measures {λ b } on A. 

ψ(s, b, θ) =      ∇ log (-∞,α] f π (a, θ|s)dλ b = α ∇ log f π (b, θ|s) b ∈ (α, β) ∇ log [β,∞) f π (a, θ|s)dλ b = β.

We can apply Theorem 4.6 in this setting to obtain Corollary 4.7. It is a strict generalization of the results in Fujita & Maeda (2018) in that it applies to a larger class of measures and provides a much stronger variance reduction guarantee. It is possible to obtain this more powerful result precisely because we require minimal assumptions for Theorem 4.6. Note that the result can be extended to R 1. E π|s [q π (s, a)ψ(s, a, θ)] = E π|s q π (s, a) ψ(s, T (a), θ) , and 2. Var ρ,π (q π (s, a)ψ(s, a, θ)) -Var ρ,π (q π (s, a) ψ(s, T (a), θ)) = E ρ,T * π Var π|b (q π (s, a)ψ r (s, r, θ)) , where r = ||a||, f r is the conditional density of r, ψ(s, a, θ) := ∇ log f M V (a, θ|s), ψ(s, b, θ) = ∇ log f AG (b, θ|s), and ψ r (s, r, θ) = ∇ log f r (r, θ|s).

PARAMETRIZED ACTION SPACES:

As one might expect, our variance reduction result applies to parametrized action spaces when a lossy transformation T i is applied to the parameter for discrete action i. See Appendix B.5 for an in depth discussion of policy gradient methods for parametrized action spaces.

4.4. DISCUSSION:

Denoting by g 1 the standard policy gradient estimator for a λ-compatible family Π, observe that Var ρ,π (g 1 ) = I π,λ (q, θ). We introduce the quantity I π,λ because unless T is a coordinate projection it is not straightforward to write Theorem 4.6 in terms of the density of a conditional distribution. Corollary 4.8 can be written this way because under a re-parametrization to polar coordinates, T (a) = a/||a|| can be written as a coordinate projection. In general, by using I π,λ we can phrase the result in terms of a quantity with an intuitive interpretation: a (q-weighted) measure of information contained in a that does not influence the environment.

Recalling the law of total variance (LOTV), we can observe that Theorem 4.6 is indeed specific version of that general result. We can not directly apply the LOTV because in the general setting, it is highly non-trivial to conclude that g 2 is a version of the conditional expectation of g 1 , and for arbitrary policies, one must be extremely careful when making the conditioning argument (Chang & Pollard, 1997) . However for certain special cases, like CAPG, we can check fairly easily that

g 2 = E[g 1 |b].

5. APPLICATIONS AND DISCUSSION:



5.1. 2D NAVIGATION TASK:

Because relatively few existing reinforcement learning environments support angular actions, we implement a navigation task to benchmark our methods2 . In this navigation task, the agent is located on a platform and must navigate from one location to another without falling off. The state space is S = R 2 , the action space is A = R 2 and the transformation T (a) = a/||a|| is applied to actions before execution in the environment. Let s G = (1, 1) be the goal (terminal) state. Using the reward shaping approach (Ng et al., 1999) , we define a potential function φ(s) = ||ss G || 2 and a reward function as r(s t , a t ) = φ(s t )φ(s t + a t ). The start state is fixed at s 0 = (-1, -1). One corner of the platform is located at (-1.5, -1.5) and the other at (1.5, 1.5).

We compare angular Gaussian policies with (1) bivariate Gaussian policies and (2) a 1-dimensional Gaussian policy where we model the mean of the angle directly, treating angles that differ by 2π as identical. For all candidate policies, we use A2C (the synchronous version of A3C (Mnih et al., 2016) ) to learn the conditional mean m(s; θ) of the sampling distribution by fitting a feed-forward neural network with tanh activations. The variance of the sampling distribution, σ 2 I, is fixed. For the critic we estimate the state value function v π (s), again using a feed-forward neural network. Appendix C.1 for details on the hyper-parameter settings, network architecture and training procedure.

5.2. APPLICATION -KING OF GLORY:

We implement a marginal policy gradient method for King of Glory (the North American release is titled Arena of Valor) by Tencent Games. King of Glory has several game types and we focus on the 1v1 version. Our work here is one of the first attempts to solve King of Glory, and MOBA games in general, using reinforcement learning. Similar MOBA games include Dota 2 and League of Legends.

Game Description. In King of Glory, players are divided into two "camps" located in opposite corners of the game map. Each player chooses a "hero", a character with unique abilities, and the objective is to destroy the opposing team's "crystal", located at their game camp. The path to each camp and crystal is guarded by towers which attack enemies when in range. Each team has a number of allied "minions", less powerful characters, to help them destroy the enemy crystal. Only the "hero" is controlled by the player. During game play, heroes increase in level and obtain gold by killing enemies. This allows the player to upgrade the level of their hero's unique skills and buy improved equipment, resulting in more powerful attacks, increased HP, and other benefits. Figure 2 shows King of Glory game play; in the game pictured, both players use the hero "Di Ren Jie".

Formulation as an MDP. A is a parametrized action space with 7 discrete actions, 4 of which are parametrized by ω ∈ R 2 . These actions include move, attack, and use skills; a detailed description of all actions and parameters is given in Table 3 , Appendix C.2. In our setup, we use rules crafted by domain experts to manage purchasing equipment and learning skills. The transformation T (a) = a/||a|| is applied to the action parameter before execution in the environment, so the effective action parameter spaces are S 1 .

Using information obtained directly from the game engine, we construct a 2701-dimensional state representation. Features extracted from the game engine include hero locations, hero health, tower health, skill availability and relative locations to towers and crystals -see Appendix C.2 for details on the feature extraction process. As in Section 5.1, we define rewards using a potential function. In particular we define a reward feature mapping ρ and a weighting vector w, and then a linear potential function as φ r (s) = w T ρ(s). Information extracted by ρ includes hero health, crystal health, and game outcome; see Table 5 , Appendix C.2 for a complete description of w and ρ. Using φ r , we can define the reward as r t = φ r (s t )φ r (s t-1 ).

Implementation. We implement the A3C algorithm, and model both the policy π and the value function v π using feed-forward neural networks. See Appendix C.2 for more details on how we model and learn the value function and policy. Using the setup described above, we compare: 1. a standard policy gradient approach for parametrized action spaces, and 2. a marginal (angular) policy gradient approach, adapted to the parametrized action space where T i (a) = a/||a|| is applied to parameter i. Additional details on both approaches can be found in Appendix B.5. For the navigation task, the top row of Figure 2 contains, from left to right, cumulative, discounted reward trajectories, and two plots showing the variances of the competing estimators. We see that the agent using the angular policy gradient converges faster compared to the multivariate Gaussian due to the variance reduced gradient estimates. The second baseline also performs worse than APG, likely due in part to the fact that the critic must approximate a periodic function. Only APG achieves the maximum possible cumulative, discounted reward. On the King of Glory 1 vs. 1 task, the agent is trained to play as the hero Di Ren Jie and training occurs by competing with the game's internal AI, also playing as Di Ren Jie. The bottom row of Figure 2 shows the results, and as before, the angular policy gradient outperforms the standard policy gradient by a significant margin both in terms of win percentage and cumulative discounted reward.

5.3. RESULTS:

In addition, Figure 2 highlights the effects of Theorem 4.6 in practice. The plot in the center shows the variance at the start of training, for a fixed random initialization, and the plot on the right shows the variance for a trained model that converged to the optimal policy. The main difference between the two settings is that the value function estimate v π is highly accurate for the trained model (since both actor and critic have converged) and highly inaccurate for the untrained model. In both cases, we see that the variance of the marginal policy gradient estimator is roughly 1 2 that of the estimator using the sampling distribution.

Motivated by challenges found in complex control problems, we introduced a general family of variance reduced policy gradients estimators. This view provides the first unified approach to problems where the environment only depends on the action through some transformation T , and we demonstrate that CAPG and APG are members of this family corresponding to different choices of T . We also show that it can be applied to parametrized action spaces. Because thorough experimental work has already been done for the CAPG member of the family (Fujita & Maeda, 2018) , confirming the benefits of MPG estimators, we do not reproduce those results here. Instead we focus on the case when T (a) = a/||a|| and demonstrate the effectiveness of the angular policy gradient approach on King of Glory and our own Platform2D-v1 environment. Although at this time few RL environments use directional actions, we anticipate the number will grow as RL is applied to newer and increasingly complex tasks like MOBA games where such action spaces are common. We also envision that our methods can be applied to autonomous vehicle, in particular quadcopter, control.

Proposition A.3 (Existence, Chang & Pollard (1997) ). Let A be a metric space, λ be a σ-finite Radon measure, and µ be a σ-finite measure such that T * λ µ. If F is countably generated and contains the singleton sets {b}, then λ has a (T, µ)-disintegration. The measures {λ b } are unique up to an almost-sure equivalence in that if {λ * b } is another (T, µ)-disintegration, µ({b :

λ b = λ * b }) = 0.

Lastly, we have Proposition A.4 which characterizes the properties of disintegrations and how they relate to densities and push-forward measures. 

B THEORY AND METHODOLOGY:

This section contains additional theoretical and methodology results, including our crucial scaled Fisher information decomposition theorem.

B.1 ANGULAR POLICY GRADIENT:

Algorithm 1 shows how to compute M d (α), allowing us to easily find the angular policy gradient.

Algorithm 1 Computing M d (α) for Angular Policy Gradient Input: d, α Output: M d (α) 1: M 0 ← Φ(α) 2: M 1 ← αΦ(α) + φ(α) 3: if d > 1 then 4:

for i = 2, . . . , d do 5:

M i ← αM i-1 + dM i-2 6:

end for 7: end if 8: return M d

B.2 FISHER INFORMATION DECOMPOSITION:

Using the disintegration results stated in Appendix A.2, we now can state and prove our key decomposition result, Theorem B.1, used in the proof of our main result.

Theorem B.1 (Fisher Information Decomposition). Let (A, E, λ) be a measure space, (B, F) be a measurable space, T : A → B be a measurable, surjective mapping, and q a measurable function on 3. for any measurable function q : B → R,

I π,λ (q • T, θ) = E T * π I π|b,λ b (q • T, θ) + I T * π,µ (q, θ).

Proof of Theorem B.1. To simplify matters, we assume without loss of generality that all densities are strictly positive. This is allowed because if some density is zero on part of its domain, we can just replace the associated measure with its restriction to sets where the density is non-zero.

The conditions to apply Proposition A. 

+ 2 B q(b) 2 ∇ log f T (b) E π|b [∇ log f a|b (a)]dT * π(b) (i) + B q(b) 2 E π|b [∇ log f T (b) ∇ log f T (b)]dT * π(b). In the equation above, term (i) is 0 because E π|b [∇ log f a|b (a)] = 0. Thus we get that (B.1) = B q(b) 2 E π|b [∇ log f a|b (a) ∇ log f a|b (a)]dT * π(b) + B q(b) 2 ∇ log f T (b) ∇ log f T (b)dT * π(b) = A q(T (a)) 2 ∇ log f a|b (a) ∇ log f a|b (a)dπ(a) + B q(b) 2 ∇ log f T (b) ∇ log f T (b)dT * π(b). (B.2)

Because a density is unique almost-everywhere, we can replace f T with f T * π in (B.2), giving claim 3: 

E π q(T (a)) 2 g(a) g(a) = E T * π q(b) 2 E π|b ∇ log f a|b (a) ∇ log f a|b (a) + E T * π q(b) 2 h(b) h(b) I π,λ (q • T, θ) = E T * π I π|b,λ b (q • T, θ) + I T * π,µ (q, θ). B.

E π|s g 1 g 1 -g 2 g 2 = E T * π I π|b,λ b (q • T, θ) . (B.5)

The result follows from combining (B.4) and (B.5), concluding the proof.

To finish the policy construction, we need an appropriate σ-algebra E and reference measure µ such that f π is a measurable and A f π dµ = 1. In fact it is not difficult to construct E and µ in terms of (E i ) i and (µ i ) i , respectively, but we do not go into detail here. Assuming such a construction exists, we can define Π a µ-compatible family of policies, parametrized by θ = (θ i ) i .

STOCHASTIC POLICY GRADIENT:

Let (A, E, µ) and Π be as constructed above. By applying Theorem 2.2, ∇η(θ) can be estimated from samples by g(s, a, θ) 

:= q π (s, a)∇ log f π (a, θ|s) = q π (s, a)∇ log f 0 (k, θ 0 |s) + q π (s, a)∇ log f k (ω,

:= q π (s, a)∇ log f π (a, θ|s) = q π (s, a)∇ log f 0 (k, θ 0 |s)+q π (s, a)∇ log f k, * (T k (ω), θ k |s). (B.7)

training the cumulative discounted reward of each episode and game outcome are tracked. The hyper-parameters we used for the neural network structure and the A3C algorithm are shown in Table 2 . To construct the plots in Figure 2 , we apply a low pass filter to each trajectory and then plot the average curve with a 95% confidence band.

Like Mnih et al. (2015) and others do for the Atari Learning Environment, we employ frame-skipping; two out of every three frames are skipped. Because our reward is defined in terms of a state potential function, rewards from the skipped states are still captured. For training, we use the Adam algorithm (Kingma & Ba, 2015) . No parameters are shared between different networks and all networks use SElu activation functions (Klambauer et al., 2017) . 

:

On a metric space A, a Radon measure is a measure defined on the Borel σ-algebra for which each compact K ⊂ A, λ(K) < ∞ and for all B ∈ B(A), λ(B) = sup K⊆B λ(K) where K is compact.

We have made this environment and the implementation used for the experiments available on-line. We temporarily removed the link from this paper to preserve anonymity.

Figures and Tables:

Figure 1: Transformation of a Gaussian policy -(left to right) π(•|s), T = a/||a||, and T * π(•|s).

EXAMPLES OF MARGINAL POLICY GRADIENT ESTIMATORS CLIPPED ACTION POLICY GRADIENT Consider a control problem where actions in R are clipped to an interval [α, β]. Let λ be an arbitrary measure on (A, E) := (R, B(R)), and consider any λ-compatible family Π. Following Fujita & Maeda (2018), define the clipped score function

d , but we stick to R for clarity of presentation. See Appendix B.4 for a discussion of which distributions are λ-compatible and a proof of Corollary 4.7. Corollary 4.7. Let λ be an arbitrary measure on (A, E) := (R, B(R)), T (a) := clip(a, α, β), and ψ(s, a, θ) := ∇ log f π (a, θ|s). If Π is a λ-compatible family parametrized by θ and the dynamics of the environment depend only on T (a), then 1. E π|s [q π (s, a)ψ(s, a, θ)] = E π|s q π (s, a) ψ(s, T (a), θ) , and 2. Var ρ,π (q π (s, a)ψ(s, a, θ)) -Var ρ,π (q π (s, a) ψ(s, T (a), θ)) = E ρ E T * π|s I π|s|b,λ b (q • T, θ) ,for some family of measures {λ b } on A.ANGULAR POLICY GRADIENTNow consider the case where we sample an action a ∈ R d and applyT (a) = a/||a|| to map into S d-1 . Let (A, E) = (R d , B(R d ))and let λ be the Lebesgue measure. When Π is a multivariate Gaussian family parametrized by θ, T * Π is an angular Gaussian family also parametrized by θ (Section 3). If Π is λ-compatible -here it reduces to ensuring the parametrization is such thatf π is differentiable in θ -then T * Π is σ-compatible,where σ denotes the spherical measure. Denoting by f M V (a, θ|s) and f AG (b, θ|s) the corresponding multivariate and angular Gaussian densities, respectively, we state the results for this setting as Corollary 4.8. See Appendix B.4 for a proof. Corollary 4.8. Let λ be the Lebesgue measure on (A, E) = (R d , B(R d )), T (a) := a/||a|| and Π be a multivariate Gaussian family on A parametrized by θ. If the dynamics of the environment only depend on T (a) and f M V (•, θ|s), the density corresponding to Π, is differentiable in θ, then

Figure 2: On top are results for Platform2D-v1; on bottom, results for King of Glory 1v1 and a screenshot of game play.

Proposition A.4 (Chang & Pollard (1997)). Let λ have a (T, µ)-disintegration {λ b }, and let ρ be absolutely continuous with respect to λ with a finite density r(a), where each of λ, µ and ρ is σ-finite. Then • ρ has a (T, µ)-disintegration {ρ b } where ρ b λ b with density r(a), • T * ρ µ with density r T (b) := T -1 (b) r(a)dλ b , • the measures {ρ b } are finite for µ almost all b if and only if T * ρ is σ-finite, • the measures {ρ b } are probabilities for µ almost all b if and only if µ = T * ρ, and • if T * ρ is σ-finite, then T * ρ({b : r T (b) = 0}) = 0 and T * ρ({b : r T (b) = ∞}) = 0. For T * ρ-almost all b, the measures { ρ b } defined by T -1 (b) f (a)d ρ b = T -1 (b) f (a)r a|b (a)dλ b and r a|b (a) := I[0 < r T (b) < ∞] r(a) r T (b) , are probability measures that give a T -disintegration of ρ.

Consider a λ-compatible family of probability measures Π = {π(•, θ) : θ ∈ Θ} on E and denote T * Π := {T * π(•, θ) : θ ∈ Θ}, a family of measures on F. If (a) A is a metric space, λ is a Radon measure, and T * λ µ for a σ-finite measure µ on F; (b) F is countably generated and contains the singleton sets {b}; (c) T * Π is a µ-compatible family for a measure µ on F; then 1. λ has a (T, µ)-disintegration {λ b }; 2. Π|b is a λ b -compatible family of probability measures that give a T -disintegration of π;

3 are satisfied, so λ has a (T, µ)-disintegration {λ b }, which proves claim 1. Next, denote by g(a) = ∇ log f π (a) and h(b) = ∇ log f T * π (b). Because the conditions to apply Proposition A.4 are satisfied, we obtain that A q(T (a)) 2 g(a) g(a)dπ(a) = B T -1 (b) q(T (a)) 2 g(a) g(a)f a|b (a)dλ b (a)dT * π(b) g(a)f a|b (a)dλ b (a)dT * π(b) log f π (a) ∇ log f π (a) f a|b (a)dλ b (a)dT * π(b).(B.1) Denoting by π|b the probability measure with density f a|b , we see that Π|b := {π|b(•, θ) : θ ∈ Θ} is a λ b -compatible family of probability measures, proving claim 2. If we denote E π|b [g] = T -1 (b) g(a)f a|b (a)dλ b (a), we further obtain that (B.1) = B q(b) 2 E π|b [∇ log f a|b (a) ∇ log f a|b (a)]dT * π(b)

3 PROOF OF THEOREM 4.6 First, we decompose the variance of g 1 asVar ρ,π (g 1 ) = Var ρ E π|s [g 1 ] + E ρ Var π|s [g 1 ] . Var ρ,π (g 1 ) -Var ρ,T * π (g 2 ) = E ρ Var π|s [g 1 ] -Var T * π|s [g 2 ] .

Table content: <table><tr><td>(B.3)</td></tr><tr><td>A similar decomposition holds for g 2 . By combining Lemma 4.5 with (B.3) and its equivalent for g 2 ,</td></tr><tr><td>we get that</td></tr><tr><td>For any fixed s, applying the definition of variance given in Section 2 and Lemma 4.5 gives</td></tr><tr><td>Var</td></tr></table>

θ k |s).The second term in (B.6) is simply the policy gradient for a µ k -compatible family on (Ω k , E k , µ k ). Let (B k , F k ) be a measurable space and consider the setting in which we apply a measurable function T k : A k → B k to the action parameters before execution in the environment. Assume the conditions are satisfied to apply Theorem 4.6, and denote by f k, * the density of T * π k with respect to an appropriate reference measure. Then we can replace q π (s, a)∇ log f k (ω, θ k |s) with q

Table content: <table><tr><td>(B.6)</td></tr><tr><td>RESTRICTED ACTION PARAMETERS</td></tr></table>



Table content: <table><tr><td>contains various hyper-parameter settings</td></tr></table>

Parametrized action space for King of Glory

Table content: <table><tr><td>Action</td><td colspan="2">Parameter Dimension Description</td></tr><tr><td>no action</td><td>0</td><td>agent does nothing</td></tr><tr><td>move</td><td>2</td><td>move in direction ω</td></tr><tr><td>attack</td><td>0</td><td>hero uses its normal attack</td></tr><tr><td>skill 1</td><td>2</td><td>hero uses skill 1 towards direction ω</td></tr><tr><td>skill 2</td><td>2</td><td>hero uses skill 2 towards direction ω</td></tr><tr><td>skill 3</td><td>2</td><td>hero uses skill 3 towards direction ω</td></tr><tr><td colspan="2">recovery skill 0</td><td>hero uses the recovery skill to heal itself</td></tr></table>

State features for King of Glory 13 our hero's level, experience, current money, kill count, death count, assist count, total money, attack range, physical attack, magical attack, move speed, health points, energy points hero state: enemy hero 13 [0, 1] 13 enemy hero's level, experience, current money, kill count, death count, assist count, total money, attack range, physical attack, magical attack, move speed, health points, energy points

Table content: <table><tr><td>Feature</td><td>Dimension</td><td>Range</td><td>Description</td></tr><tr><td>position: our hero</td><td>2</td><td>[-1, 1] 2</td><td>x,y coordinates of our hero's position</td></tr><tr><td>position: enemy hero</td><td>2</td><td>[-1, 1] 2</td><td>x,y coordinates of enemy hero's position</td></tr><tr><td>position: enemy hero, relative</td><td>3</td><td>R 3</td><td>distance, direction to enemy hero</td></tr><tr><td>position: enemy tower, relative</td><td>4</td><td>R 4</td><td>distance, distance relative to attack range, relative direction to the near-</td></tr><tr><td/><td/><td/><td>est enemy tower</td></tr><tr><td>position: enemy minion, relative</td><td>3</td><td>R 3</td><td>distance, relative direction to the nearest enemy minion</td></tr><tr><td>position: our spring, relative</td><td>3</td><td>R 3</td><td>distance, relative direction to our life spring</td></tr><tr><td>in tower range: our hero</td><td>3</td><td>{0, 1} 3</td><td>is our hero in the range of the enemy's towers</td></tr><tr><td>in tower range: enemy hero</td><td>3</td><td>{0, 1} 3</td><td>is enemy hero in the range of our tower</td></tr><tr><td>attacked by tower</td><td>3</td><td>{0, 1} 3</td><td>are the enemy towers are attacking our hero</td></tr><tr><td>skill cool down: our hero</td><td>5</td><td>[-1, 1] 5</td><td>normalized cool down time for our hero's skills</td></tr><tr><td>skill cool down: enemy hero</td><td>5</td><td>[-1, 1] 5</td><td>normalized cool down time for enemy hero's skills</td></tr><tr><td>HP: our hero</td><td>1</td><td>[-1, 1]</td><td>our hero's health points</td></tr><tr><td>HP: enemy hero</td><td>1</td><td>[-1, 1]</td><td>enemy hero's health points</td></tr><tr><td>HP: nearest minion</td><td>1</td><td>[-1, 1]</td><td>health points of the nearest enemy minion</td></tr><tr><td>HP: nearest tower</td><td>1</td><td>[-1, 1]</td><td>health points of the nearest enemy tower</td></tr><tr><td>HP: minions in range</td><td>1</td><td>R +</td><td>sum of HP of all the minions in the attack range of our hero</td></tr><tr><td>alive: our hero</td><td>1</td><td>{0, 1}</td><td>whether our hero is alive</td></tr><tr><td>alive: enemy hero</td><td>1</td><td>{0, 1}</td><td>whether enemy hero is alive</td></tr><tr><td>gold: our hero</td><td>1</td><td>[0, 1]</td><td>our hero's gold</td></tr><tr><td>gold: enemy hero</td><td>1</td><td>[0, 1]</td><td>enemy hero's gold</td></tr><tr><td>gold: ∆</td><td>1</td><td>[-1, 1]</td><td>difference between our hero's gold and enemy hero's gold</td></tr><tr><td>EP: our hero</td><td>1</td><td>[-1, 1]</td><td>normalized energy points of our hero</td></tr><tr><td>EP: enemy hero</td><td>1</td><td>[-1, 1]</td><td>normalized energy points of enemy hero</td></tr><tr><td>hero state: our hero</td><td>13</td><td>[0, 1]</td><td/></tr></table>

State features and weights used in reward design

Table content: <table><tr><td>Feature</td><td>Weight</td><td>Description</td><td>Notes</td></tr><tr><td>gold difference</td><td>0.5</td><td>difference between the amount of our hero and enemy hero</td><td/></tr><tr><td>HP (our hero)</td><td>0.5</td><td>health points of our hero</td><td/></tr><tr><td>hurt to enemy hero</td><td>0.5</td><td>total amount of hurt from our hero to enemy hero</td><td/></tr><tr><td>hurt to enemy</td><td>1.0</td><td>total amount of hurt from our hero to all the enemies</td><td/></tr><tr><td>kill dead difference</td><td>1.0</td><td>difference between kill count and dead count</td><td/></tr><tr><td>distance to our life spring</td><td>0.25×(1.0 -HP)</td><td>distance from our hero to spring</td><td>HP ∈ [0, 1]</td></tr><tr><td>distance to enemy</td><td>0.125×HP</td><td>distance from our hero nearest enemy</td><td>HP ∈ [0, 1]</td></tr><tr><td>tower HP difference</td><td>1.0</td><td>difference between HP of our tower and enemy tower</td><td/></tr><tr><td>crystal HP difference</td><td>2.0</td><td>difference between HP of our crystal and enemy crystal</td><td/></tr><tr><td>skill hit rate</td><td>0.15</td><td>percent of emitted skills that hit enemy hero</td><td/></tr><tr><td>win/loss</td><td>2.0</td><td>game result</td><td/></tr></table>

Peer review (iclr2019):
 This paper introduces policy gradient methods for RL where the policy must choose a direction (a.k.a., the navigation problem). Mapping techniques from "non-directional" problems (where the action space is not a direction) and then projeting on the sphere is sub-optimal (the variance is too big). The authors propose to sample directly on the sphere, using the fact that the likelyhood of an angular Gaussian r.v. has *almost* a closed form and its gradient can almost be computed, up to some normalization term (the integral which is constant in the standard Gaussian case). This can be seen as a variance reduction techniques. The proofs are not too intricate, for someone used to variance reduction (yet computations must be made quite carefully). The result is coherent, interesting from a theoretical point of view and the experiment are somehow convincing. The main drawback would be the rather incrementality of that paper (basically sample before projecting is a bit better than projecting after sampling) and that this directional setting is quite limited...