{'fraction_non_alphanumeric': 0.05191530891642042, 'fraction_numerical': 0.01404288773822756, 'mean_word_length': 4.095027624309393, 'pattern_counts': {'":': 0, '<': 12, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Analytical Update Rule for General Policy Optimization

We present an analytical policy update rule that is independent of parametric function approximators. The policy update rule is suitable for optimizing general stochastic policies and has a monotonic improvement guarantee. It is derived from a closed-form solution to trust-region optimization using calculus of variation, following a new theoretical result that tightens existing bounds for policy improvement using trust-region methods. The update rule builds a connection between policy search methods and value function methods. Moreover, off-policy reinforcement learning algorithms can be derived from the update rule since it does not need to compute integration over on-policy states. In addition, the update rule extends immediately to cooperative multi-agent systems when policy updates are performed by one agent at a time.


Introduction
Policy search methods have gained great popularity in reinforcement learning (RL) for the last decade. As opposed to value function methods, in which the policy is represented implicitly by a greedy action-selection strategy with respect to an estimated value function, policy search methods search directly in the space of policy representations for a good policy. The advantages of policy search methods include being able to learn stochastic policies (Singh et al., 1994), better convergence, and effectiveness in high-dimensional or continuous action spaces. Generally, policy search approaches use function approximators, such as neural networks, to construct a parametric policy. The parametric policy is then optimized using policy gradient (Williams, 1992;Sutton et al., 1999) or derivative-free algorithms (Szita & Lörincz, 2006) by searching in the parameter space.
In this paper, we present an analytical policy update rule that is independent of parametric function approximators. We prove that the update rule has a monotonic improvement guarantee and is suitable for optimizing general stochastic policies with continuous or discrete actions. The update rule provides a new theoretical foundation for policy-based RL, which traditionally restricts the policy search to a family of parametric functions, such as policy gradient (Sutton et al., 1999), deterministic policy gradient (Silver et al., 2014;Lillicrap et al., 2016), actor critic (Konda & Tsitsiklis, 1999;Degris et al., 2012), soft actor-critic (SAC) (Haarnoja et al., 2018a;b), and so on.
Our update rule is derived from a closed-form solution to a trust region method using calculus of variation. Trust-region method is one of the most important tools in RL. The basic idea is to search for an improved policy iteratively in a local area around the current policy, in which the objective function is well-approximated by a manageable surrogate model. A representative trust-region method for RL is trust region policy optimization (TRPO) (Schulman et al., 2015). TRPO introduces a simple and functional surrogate model that can be evaluated using the current best policy and provides an upper bound of the approximation error of the surrogate model. This is particularly useful because by subtracting the bound from the surrogate model we obtain the worstcase performance degradation, or a lower bound, of the true objective. It follows that maximizing the lower bound leads to an improved policy with non-decreasing performance (Schulman et al., 2015).
The theory of TRPO is of significance to policy-based RL for it provides an approach that guarantees to improve the policy monotonically. However, the bound derived in TRPO depends on the maximum KL-Divergence of the current policy π and a proposed policy π on the entire state space, i.e., max s D KL [π π](s), which can be extremely large or infinity even if π and π are close at most states. To address this issue, TRPO heuristically imposes a strict constraint to bound the KL-Divergence at every state, but it is intractable to implement this constraint when the state space is large or continuous. To derive a practical algorithm, an empirical approximation using an expected KL-Divergence, e.g. E s∼d π [D KL [π π](s)], is usually adopted (Schulman et al., 2015;Achiam et al., 2017). Nevertheless, the monotonic improvement property is no longer guaranteed.
In this paper, we prove a new theoretical result on the bound of the surrogate approximation error by relating it to the expected KL-Divergence. This result leads to a more practical lower bound of the objective, which improves previous analysis on this topic in terms of KL-Divergence, such as Schulman et al. (2015); Achiam et al. (2017); Akrour et al. (2018). It also closes the gap between theory and practice in TRPO and the related approaches. Furthermore, this result enables us to derive a closed-form solution for policy optimization. The closed-form solution introduces a very simple policy update rule that guarantees to produce monotonically improving policies.
From an algorithmic viewpoint, the policy update rule enables the development of off-policy algorithms that do not rely on policy gradient (Sutton et al., 1999), which is known to have high variance and low sample efficiency. This is because the policy update rule does not require integrating on-policy distributions over the state space. Thus, we can reuse the past experience obtained from a behavioral policy and circumvent the high variance and sample efficiency issues. In addition, since the policy update rule is analytical, it applies to both parametric and non-parametric policies. However, policy gradient-based approaches are subject to parametric policies.
Furthermore, we prove that the update rule extends immediately to partially observable Markov games with cooperative agents and the monotonic improvement guarantee still holds when updates are performed by one agent at a time.
The contributions of this paper include: (1) a new theoretical result that tightens existing bounds for local policy search using trust-region methods; (2) a closed-form update rule for general stochastic policies with monotonic improvement guarantee; (3) a proof that shows that the policy update rule is extendable to partially observable multi-agent RL problems without compromising the monotonic improvement guarantee.

Related Work
The idea of restricting policy search to a local area of the current policy is common in model-free RL. For instance, instead of imposing a hard boundary on the searching area, Kakade & Langford (2002) proposed a conservative update scheme mixing the current policy and a greedy update via a weighted sum. A lower bound on the performance improvement as a function of the weighting coefficient was proven. Following this line of work, Pirotta et al. (2013) proposed two more general lower bounds connecting to the difference between two policies. Then, two conservative update algorithms were developed by maximizing the proposed bounds, respectively. Zhu & Matsubara (2020) proposed a similar bound and a practical algorithm for entropy-regularized RL.
While monotonic improvement guarantee is derived in the previous studies, the update scheme cannot apply to nonmixture policies. Schulman et al. (2015) extended this line of work to general stochastic policies and proposed a new bound that connected it to the maximum KL-Divergence between two successive policies on the state space. However, this bound is intractable when the state space is large. Although a tighter bound relating it to an average total variation distance is proposed in Achiam et al. (2017), deriving a closed-form policy update rule from the lower bound is still challenging.
In practice, many approaches use a hard constraint to bound the searching area but they generally lose the monotonic improvement guarantee. Peters et al. (2010) proposed relative entropy policy search (REPS) to restrict the relative entropy between observed data distribution of the state-action pairs and the distribution generated by the new policy. A closedform update rule in a softmax form was derived using the method of Lagrange multipliers. However, this approach is not straightforwardly extendable to general non-linear policies. To apply nonlinear policies, TRPO (Schulman et al., 2015) and constrained policy optimization (Achiam et al., 2017) approximately constrained the on-policy expected KL-Divergence by using second-order Taylor expansion, which was closely related to natural policy gradient (Kakade, 2001). Extending the work in TRPO, Akrour et al. (2018) provided a monotonic improvement guarantee for bounding the expected KL-divergence, but the result only held for linear-Gaussian policies. Nachum et al. (2017;2018) presented multi-step softmax consistencies under entropy regularization and adopted a discounted relative entropy trust-region constraint to improve exploration and stability. By relating policy search to probabilistic inference (Levine, 2018), Abdolmaleki et al. (2018) proposed the maximum a posterior policy optimization (MPO) algorithm based on Expectation-Maximization, where the policy update was decomposed into E-step and M-step. A closed-form E-step combined with a maximum-a-posteriori-estimation M-step for Gaussian policies was provided. Although a monotonic improvement guarantee is claimed, the guarantee is for the KL-Divergence regularized objective rather than the true expected return. Besides, suffering from the same issue as in (Peters et al., 2010), the policy update rule needs to determine the optimal Lagrangian multipliers of the dual problem, which requires a costly nonlinear optimization in the inner loop. Different from previous works, Otto et al. (2021) proposed projection-based solutions to impose trust-region constraints on the individual state, which enabled exact guarantees of monotonic improvement. Three closed-form projection layers based on Wasserstein L2 distance, Frobenius norm, and KL-Divergence were proposed to project the updated policy onto trust regions. However, the proposed approach only applies to Gaussian policies.

Markov Decision Process
A Markov decision process (MDP) is defined by a tuple (S, A, p, r, ρ 0 , γ), where S is the state space, A is the action space, p : S × A × S → R ≥0 is the transition probability density, r : S × A → [r min , r max ] is the reward function, ρ 0 : S → R ≥0 is the probability density of the initial state s 0 , γ ∈ [0, 1) is the discount factor.
Denote a stochastic policy π : S × A → R ≥0 (→ [0, 1] for discrete actions) by π(a|s), which represents the probability density (or probability mass function) of the action a given the state s. The goal is to find an optimal policy that maximizes the expected discounted return where τ denotes the trajectory τ := (s 0 , a 0 , s 1 , . . . ), and τ ∼ π indicates that the distribution over the trajectory depends on π : s 0 ∼ ρ 0 , a t ∼ π(·|s t ), s t+1 ∼ p(·|s t , a t ).
Letting R(τ ) = ∞ t=0 γ t r t denote the discounted return of the trajectory τ , we can compactly express the value function as V π (s) = E τ ∼π [R(τ )|s 0 = s], the state-action value function as Q π (s, a) = E τ ∼π [R(τ )|s 0 = s, a 0 = a], and the advantage function as A π (s, a) = Q π (s, a)−V π (s). We define the discounted state visitation distribution as where ρ π t : S → R ≥0 is probability density function (PDF) of the state at timestep t given the policy π.

Partially Observable Markov Game
A Markov game (Littman, 1994) is a game defined on a state space, S, and a collection of action spaces, A 1 , . . . , A N , one for each agent in the environment. The state transition s → s (s, s ∈ S) happens following the probability density P : S × A 1 × · · · × A N × S → R ≥0 when the actions a = [a 1 , . . . , a N ], a i ∈ A i , i ∈ {1, . . . , N }, are exerted on the environment at state s. Each agent is rewarded based on a local reward function r i : , which depends on the current state s and the joint action a.
In a partially observable Markov game (POMG), each agent has a local observation of the environment, o i , which contains incomplete information of the state s. At state s, o i is observed with a likelihood, P i o : S × O i → R ≥0 , where O i is the observation space of the agent. Each agent acts according to a policy π i : O i × A i → R ≥0 (or → [0, 1]), which is a probability distribution (or a probability mass function) over the action space A i given the observation o i . We will use the following definitions of the joint policy π(a|s) and the joint policy π −i (a −i |s) except i: where N = {1, 2, . . . , N } is a set of agent's IDs. The goal of the agents is to learn a set of distributed policies {π i (a i |o i )|i ∈ N } to maximize the expected return

Trust Region Method
Trust region method is one of the most important techniques for solving policy optimization in a Markov decision process. It works by restricting policy search to a local region around the current best solution, where the objective function is well-approximated by a surrogate model. Specifically, it solves the following optimization: whereJ(π ) is some surrogate model, D is a distance measure, and δ > 0 is the radius of a spherical region, in which we search for an improved policy. A simple and effective choice for the surrogate model is Schulman et al. (2015) prove that the difference between the surrogate model and the true objective is bounded by: which connects it to the maximum KL-Divergence over the state space, max s D KL [π π k ](s). By using this bound, we can get the worst-case performance degradation of the true objective: It follows that maximizing the right-hand side of the inequality, which is a lower bound of the true objective function, can lead to guaranteed improvement in the performance. This result has fostered a branch of practical trust-region algorithms (

Analytical Policy Update Rule with Monotonic Improvement Guarantee
Our principle result is an analytical solution for policy optimization based on trust-region methods, following a new bound on the difference between the surrogate model and the true objective. The analytical solution introduces a policy update rule that guarantees monotonic policy improvement and is suitable for general stochastic policies with discrete or continuous actions. Moreover, the update rule extends immediately to cooperative multi-agent systems when updates are performed by one agent at a time.
We first present the new bound on the difference between the surrogate model and the objective in the following theorem.
Theorem 4.1. For any stochastic policies π , π and discount factor γ ∈ [0.5, 1), the following bound holds: Proof. We provide the proof in Appendix A. The proof extends Schulman et al. (2015)'s result using the concept of α-coupling (Levin et al., 2006) and its relationship with total variation distance. However, different from the proof in (Schulman et al., 2015) that uses the maximum α over the state space, we instead use a state-dependent α(s) to represent the coupling between two arbitrary policies given s, which enables us to connect the bound to the expected KL-Divergence.
The new bound is tighter in terms of KL-Divergence compared with (8) derived from (Schulman et al., 2015). While the improvement in tightness is at a cost of γ/(4(1 − γ) 2 ), this result directly relates the bound to the expected KL-Divergence E s∼d π [D KL [π π](s)], which closes the gap between theory and practice in TRPO and related algorithms. In addition, the new bound improves prior analysis in the literature, such as (Akrour et al., 2018;Achiam et al., 2017), in terms of either KL-Divergence or total variation distance (from D TV [π π] to D 2 TV [π π], see Appendix A). Furthermore, using this result, we can derive a new lower bound of the true objective: (11) Then, we can improve the policy by maximizing the lower bound. Next, we present a closed-form solution to the maximization of the lower bound, which introduces a simple policy update rule with monotonic improvement guarantee.
Theorem 4.2. For any stochastic policies π new , π old that are continuously differentiable on the state space S, the inequality, J(π new ) ≥ J(π old ), holds when where α π old = A π old /C π old .
Proof. We provide the proof in Appendix B. The proof introduces calculus of variation (Calder, 2020;Kot, 2014) to the policy optimization problem. Based on the assumption of continuously differentiable policies on the state space S, we derive a closed-form solution for general stochastic policies with continuous or discrete actions. In the proof, we show that the closed-form solution is a necessary and sufficient condition for the policy optimization.
Another interesting result of Theorem 4.2 is that the update rule immediately extends to cooperative multi-agent RL problems while the monotonic improvement guarantee still holds if the agents perform local policy updates in turn. We present this result in the following corollary.
Corollary 4.3. For any stochastic policies π i new , π i old of agent i that are continuously differentiable on the local observation space O i , and the corresponding joint policies π new , π old , the inequality, J(π new ) ≥ J(π old ), holds when where π −i new , π −i old are joint policies of all agents except i.
Proof. Based on Theorem 4.2, we have Note that the joint policy can be decomposed as follows: Thus, we can rewrite Eq. (14) as follows: when π −i new = π −i old , they cancel each other on both sides. Then, simplifying the above equation, the result follows.

Connections with Prior Work
In this section, we connect the proposed policy update rule with some state-of-the-art algorithms and discuss how the update rule can help explain these algorithms from a different perspective.

TRPO and Proximal Policy Optimization
Note that the exponential factor in (12) can be written as where γ ∈ [0.5, 1). The first term on the right-hand side is a normalized advantage and the second term is a positive constant smaller than 1. Letting [α min , α max ] denote the range of α π old , then we have α min ≤ 0 ≤ α max , as shown in Figure 1. In addition, since α π old is a random variable given s, we have e αmin ≤ E a∼π old [e απ old ] ≤ e αmax . Then, based on the update rule (12), the ratio of the new policy to the old policy is bounded by where Z = E a∼π old [e απ old ] and 1 , 2 are positive numbers ( 1 < 1). Equation (18) indicates that bounding the policy ratio is an effective way to confine the searching area. This help explain the success of the proximal policy optimization (PPO) algorithm (Schulman et al., 2017), which clips the policy ratio by [1 − , 1 + ], 0 < < 1.
It is also noted that the policy ratio π new /π old will be greater than 1 if e απ old > E a∼π old [e απ old ], and vice versa (shown in Figure 1). Note that the exponential term e απ old is monotonically increasing with respect to A π old (s, a), and so is the policy ratio π new /π old . Less rigorously, consider the term E a∼π old [e απ old ] as an "average" advantage of the policy π old . Then, selecting the action a at state s is encouraged, i.e. π new (a|s) > π old (a|s), if it leads to an advantage that is above average. On the contrary, selecting the action a at state s is discouraged, i.e. π new (a|s) < π old (a|s), if it leads to an advantage that is below average. To what extent the action a is encouraged or discouraged is determined by the value of A π old (s, a). This result matches the TRPO algorithm (Schulman et al., 2015), which maximizes where π(a|s) is increased to gain weights for large advantages and decreased to lose weights for small advantages. Although our update rule suggests that the policy ratio is proportional to an exponential advantage, rather than a linear advantage as suggested in TRPO and PPO, it is easy to verify that e A old /C old ≈ A old /C old + 1 when the policy ratio is bounded around 1. Figure 1. From the policy update rule, we can derive πnew/π old ∈ [e α min /Z, e αmax /Z], where Z = Ea∼π old [e απ old ] and αmin and αmax are the minimum and maximum values of απ old , respectively. Since e α min ≤ Ea∼π old [e απ old ] ≤ e αmax , the upper and lower bounds of the policy ratio πnew/π old can be expressed as [1 − 1, 1 + 2], where 1, 2 ≥ 0 and 1 < 1. This indicates that we can bound the policy ratio to restrict the search area, which has been adopted in PPO and proven effective in practice. In addition, if e απ old > Ea∼π old [e απ old ], the policy ratio πnew/π old will be greater than 1, and vice versa. Note that e απ old is monotonically increasing with respect to Aπ old (s, a), and so is the ratio πnew/π old . Less rigorously, consider the term Ea∼π old [e απ old ] as the "average" advantage of the policy π old . Then, selecting the action a at state s is encouraged, i.e. πnew(a|s) > π old (a|s), if it leads to an "above average" advantage. On the contrary, selecting the action a at state s is discouraged, i.e. πnew(a|s) < π old (a|s), if it leads to a "below average" advantage. To what extent the action a is encouraged or discouraged is determined by the value of Aπ old (s, a).

Value-Based Methods and Dynamic Programming
In this section, we provide a different explanation of the policy update rule by considering discrete actions and then connect it to value function methods. By multiplying the numerator and denominator both by e Vπ old (s)/Cπ old , we can rewrite the update rule as As shown in (20), the new policy is a weighted probability mass function of the old policy in a softmax form. The weights are the exponential terms, exp{Q π old (s, a i )/C π old }. That indicates actions with larger Q values will get better chance to be selected in the future. In fact, the policy update rule can be deemed as a stochastic analogy of the -greedy policy used in value function methods, such as SARSA (Sutton & Barto, 2018).
In addition, we can verify the monotonic improvement guarantee of the policy update rule via dynamic programming. To see this, we will show V π old (s) ≤ V πnew (s) for all s ∈ S. Note that For brevity, we will use P s sa := P (s |s, a). Then, we have (22) Therefore, by applying the update rule (20), we can obtain a sequence of monotonically improving policies and value functions:

Relative Entropy Policy Search and Maximum a Posterior Policy Optimization
The REPS (Relative Entropy Policy Search) algorithm (Peters et al., 2010) can be obtained as a special case of the update rule by replacing π old with the observed data distribution and the coefficient C π old with the Lagrange multiplier η. However, the REPS algorithm is based on finite MDPs with discrete actions and not extendable to general continuous policies. A similar closed-form update rule has also been derived in the MPO (Maximum a posterior Policy Optimization) algorithm (Abdolmaleki et al., 2018) in its E-step for evaluating a variational policy, which is then used to optimize policy parameters.
Our policy update rule is different from the previous work because it directly expresses the new policy as a closed-form function of the current policy. That means the policy update can be accurately calculated using the current policy without involving policy gradient or policy optimization. Especially, the proposed update rule provides an explicit formula for determining the coefficient C π old and guarantees monotonic improvement on performance. However, the update rules in (Peters et al., 2010;Abdolmaleki et al., 2018) need to numerically determine the optimal Lagrangian multiplier η, which requires a costly nonlinear optimization in the inner loop and no monotonic improvement is guaranteed.

Soft Actor-Critic
The SAC (Soft Actor-Critic) algorithm (Haarnoja et al., 2018a;b) can also be derived as a special case of the policy update rule. Note that the update rule (12) can be expressed as a Gibbs measure (Boltzmann distribution in case of discrete actions): π new (a|s) = π old (a|s) e Aπ old (s,a)/Cπ old E a∼π old e Aπ old (s,a) /C π old = π old (a|s) e Qπ old (s,a)/Cπ old E a∼π old e Qπ old (s,a)/Cπ old where Z = E a∼π old e Qπ old (s,a)/Cπ old is the partition function.
To optimize a policy π, we can minimize the KL-Divergence between π and π new : where Q π old is the soft Q-function: Q π old (s, a) = Q π old (s, a) + C π old log π old (a|s). (25) Replacing C π old with a temperature parameter α, we immediately get the SAC algorithm (Haarnoja et al., 2018b).
A slight difference of the algorithm (24) than SAC is that it minimizes the policy entropy instead of maximizing it. Note that the soft state value function derived from our update rule is given by where H(π(·|s)) is the policy entropy. Since C π is always positive, the policy entropy is penalized in the soft state value function. Thus, applying (24) will minimize the policy entropy. This is reasonable because the policy distribution should be concentrating more and more on the optimal action as the policy improves monotonically.
The derivation of SAC also verifies that the update rule is essentially off-policy.

Tightness of the Bound in Terms of γ
The bound in Theorem 4.1 improves prior analysis in terms of KL-Divergence, but not in terms of γ, which could be a limitation of the policy update rule. Compared to the bound in TRPO, the improvement is at a cost of γ/(4(1 − γ) 2 ). When γ is close to 1, the penalty coefficient C π old for the KL-Divergence can be large, resulting in small step sizes for policy updates. While C π old can be tuned to allow larger step-sizes in practice, a proven bound that is tighter in terms of γ will be an interesting direction for future work.

Monotonic Guarantee and Function Approximation
The policy update rule is a closed-form solution, so it assumes an exact advantage function and an exact maximum of its absolute value. In large MDPs, these quantities generally need to be estimated by function approximators. The use of function approximatiors will inevitably introduce errors and can undermine the monotonic improvement guarantee. While our goal is to provide the theory, we would like to clarify this to encourage the development of efficient algorithms using function approximation. We also look forward to new RL theories building upon the update rule given its simplicity and wide connections with prior RL approaches.

Simultaneous Update for Multi-Agent RL
The extension of the update rule to multi-agent RL requires agents to take turns updating their policies. Thus, the learning process could be slow if there are many agents. From Equation (16) we see that the main reason for this requirement is that we need to make sure π −i new = π −i old . We believe that relaxing this requirement so as for the agents to update policies simultaneously without jeopardizing the monotonic improvement guarantee is worth studying in the future.

Conclusion
We have presented a closed-form update rule for general stochastic policy optimization with monotonic improvement guarantee. A new theoretical result has been provided by relating the lower bound of the performance to an expected KL-Divergence, which closes the gap between theory and practice in the literature. Based on the theoretical result, calculus of variation has been introduced to derive the policy update rule. Furthermore, we have proved that the policy update rule is extendable to cooperative multi-agent RL when agents take turns performing policy updates. Since the proposed update rule is analytical, we hope that it serves as a stepping stone for future work on novel RL theories and principled RL algorithms using parametric or non-parametric policies.

A. Proof of Policy Performance Bound
This proof uses techniques from the proof of Lemma 3. in (Schulman et al., 2015), exploiting them to derive a new bound that relates to an average divergence between policies, π , π. An informal overview is as follows. First, using Lemma 1. in (Schulman et al., 2015), the gap between the surrogate and the objective is decomposed into the difference of two expected advantages over the policies π , π. Then, we use the coupling technique to measure the coincidence of two trajectories resulted from π , π before an arbitrary timestep t. Finally, we constrain the gap to an average KL-Divergence using Pinsker's inequality.
Definition A.1 (Notations). We consider a Markov decision process with a continuous state space. The following definitions and notations will be used.
1. Probability density function (PDF) of the state at timestep t given the policy π: ρ π t (s) = P DF (s t = s|π).
Note that ρ π 0 (s) = ρ 0 (s) is the PDF of the initial state s 0 , which is independent of π. 2. Discounted state visitation PDF: 3. One-step state transition density given the policy π: ν π (s |s) = A p(s |s, a)π(a|s)da.
where 0 ≤ m ≤ t, and ν 0 π (s |s) is a Dirac delta distribution: Note that ν 0 π (s |s) is independent of the policy π, and thus ν 0 π (s |s) = ν 0 π (s |s). 5. Discounted state transition PDF given the policy π: Then, the discounted visitation PDF can be written as 6. Surrogate model: We start by introducing the definition of α-coupled policies from the Definition 1 in (Schulman et al., 2015) with some changes.
Definition A.2 (α-coupled policies). A coupling of two probability distributions µ and ν is a pair of random variables (X, Y ) defined on a single probability space such that the marginal distribution of X is µ and the marginal distribution of Y is ν (Levin et al., 2006).
The policies π (a |s) and π(a|s) are called α-coupled if they define a coupling of (π , π) such that P (a = a|s) ≤ α(s).
Numerically, α-coupling means that the actions a and a given state s match with probability of at least 1 − α(s) when their samples are drawn using the same seed.
The technique of coupling is useful because it relates two policies to their total variation distance. According to the lemma 4.7 in (Levin et al., 2006), for policies π and π, there exists a coupling that satisfies D TV [π ||π](s) = inf{P (a = a|s), a and a is a coupling of π and π}.
where D TV [π ||π](s) represents the total variation distance between policies π and π given the state s. This means that D TV [π ||π](s) is the infimum of the probability P (a = a|s), and therefore we can select α(s) to be D TV [π ||π](s).
Note that our definition of α(s), depending on the state s, is different from the definition in (Schulman et al., 2015), which is the maximum over the state space, i.e. max s∈S α(s).
Next, we present a lemma from (Kakade & Langford, 2002) and (Schulman et al., 2015) that shows that the performance difference between two arbitrary policies can be expressed as an expected advantage of one policy over a trajectory resulted from the other.
Lemma A.5. Let α t and γ be any real numbers within α t ∈ [0, 1], ∀t ∈ N and γ ∈ [0.5, 1) , the following inequality holds: Proof. First note that α 0t can be expressed as or in a recursive form: where α 00 = α 0 . Then, we have For the inequality (44) to hold, we only need to prove that the subtrahend on the rightest-hand side of (47) is greater than 0. Note that In the expanded form, the rightest-hand side of (48) can be expressed as Equation (49) can be rewritten as where and Next, we prove H t ≥ 0 for all t ∈ N + by using convex optimization. Decompose H t into: Taking the partial derivative of H t with respect to α t and setting it to be zero, H t attains its minimum value, i.e., Denoting b 1 = 1/4a 0 and decomposing h t−1 , we get Again, taking the partial derivative with respect to α t−1 and setting it to be zero, we get Recursively, as long as b i ≥ 0 and a i − b i ≥ 0 hold for all i ≤ t ∈ N + , we can repeatedly apply the previous procedure and get b 0 = 0 and a i is defined in Equation (52). Next, we prove b i ≥ 0 and First, it is easy to manually verify that b i ≥ 0 and a i − b i ≥ 0 when i < 15. In addition, for i = 15, we can verify that the following inequalities holds since a 15 = 121 and b 15 ≈ 3.6945.
Next, we prove the inequalities in (60) holds for i > 15. Note that Therefore, we have and Based on Equations (60), (62) and (63), we can prove that b i ≥ 0 and a i − b i ≥ 0 hold for i ≥ 15 using mathematical induction. Combining the fact that they also hold for i < 15, we have b i ≥ 0 and a i − b i ≥ 0 for all i ≤ t ∈ N + . As a result, the inequality (58) holds, i.e., H t ≥ 0, which concludes the proof.
Proof. Define A(s) to be the expected advantage of π over π at state s: Then, Lemma A.3 can be rewritten as follows: Note that the surrogate model can be written as Then, the difference between the surrogate L π (π ) and the true objective J(π ) can be written as Next, we split the proof into three parts.
(1) By using the coupling technique, we decompose the difference terms in (68) A(s t ) , to derive an equivalent expression.
(2) Based on the result from the first part, we use Lemma A.4 to derive an upper bound of |J(π ) − L π (π )|, which depends on a bunch of state-dependent total variation distances of π , π. (3) We relate the bound derived from the second part to the expected KL-Divergence between π , π.
i) The first part of the proof is given as follows.
We will use techniques from the proof of Lemma 3. in (Schulman et al., 2015) to measure the coincidence of two trajectories resulted from π , π before an arbitrary timestep t. Let n t denote the number of times that a i = a i |s i at state s i for i < t. For instance, n t = 0 means the trajectories τ, τ completely match before timestep t, i.e., a i = a i |s i for all i < t.
In a recursive form, it can be expressed as: Note that Substituting (76) into (75), we get For notational simplicity, we denote Then, Equation (77) can be expressed as ii) The second part of the proof is given as follows.
Recall that n t denote the number of times that a i = a i |s i at state s i for i < t, and n t = 0 means that a i = a i |s i for all i < t. Based on Definition A.2 (α-coupled policy), we have P (a i = a i |s i ) ≥ 1 − α(s i ) for every s i . Thus, An Analytical Update Rule for General Policy Optimization Substituting (90) and (84) into (89), we have Using Lemma A.5, the inequality (91) can be further simplified as Replacing Last, applying Pinsker's inequality, 2D 2 TV [π ||π](s) ≤ D KL [π ||π](s), the result follows.

B. Proof of Analytical Policy Update Rule with Monotonic Improvement Guarantee
This proof uses calculus of variations to derive an analytical solution for trust region policy update.
Theorem B.1. For any stochastic policies π new , π old that are continuously differentiable on the state space S, the inequality, J(π new ) ≥ J(π old ), holds when Proof. With Theorem 4.1, we can get a lower bound of the objective function J(π ) when approximating around π old : J(π ) ≥ L π old (π ) − 1 1 − γ C π old E s∼d π old [D KL [π π old ](s)] .
It follows that maximizing the lower bound will give us a new policy that is not worse than π old . To see this, let I(π ) denote the lower bound and π new denote its maximum solution: I(π ) = L π old (π ) − 1 1 − γ C π old E s∼d π old [D KL [π π old ](s)] π new = arg max π I(π ) where L π old (π ) is the surrogate model. Then, we have J(π new ) ≥ I(π new ) ≥ I(π old ) = J(π old ).
Next, we prove that the expression of π new in (94) is a necessary and sufficient condition for the optimal solution of the problem in (97).

B.1. Continuous action space
We will use calculus of variation to derive the analytical expression for π new . Let π ∈ C 1 (U ) be functions defined on U . = S × A. Note that the lower bound I(π ) can be rewritten as follows: I(π ) = J(π old ) + 1 1 − γ S×A d π old (s) π (a|s)A π old (s, a) − C π old π (a|s) log π (a|s) π old (a|s) dsda.
Note that the policy π should be a probability distribution, which means that it integrates to 1. To ensure that, we add the following constraint: H(π ) = 1 1 − γ S d π old (s) A π (a|s)da − 1 ds = 0.
Taking logarithm on both sides and rearranging it, we get λ = C π old log A π old (a|s) exp A π old (s, a) C π old da − C π old .
Denote α π old = Aπ old (s,a) Cπ old . Then, the optimal policy can be simplified as .
Until now, we have proved the sufficient condition. Next, we prove that the policy π new in Eq. (109) is also the necessary condition for the optimal solution to the maximization of I(π ).

B.2. Discrete action space
For discrete actions, the functionals I(π ) and H(π ) can be rewritten as follows: π (a i |s)A π old (s, a i ) − C π old π (a i |s) log π (a i |s) π old (a i |s) ds, π (a i |s) − 1 ds.
Now, consider the policy as a vector of functions, π = [π 1 , π 2 , . . . , π k ], where π i = π (a i |s) ∈ C 1 (S) is a function defined on S given the action a i . Then, we can define the Lagrange functions by F (s, a, π ) = d π old k i=1 π i A π old − C π old π i log π i + C π old π i log π i,old .
Use the same method as in Equation (110), we can prove that the second-variation condition is satisfied.