{'fraction_non_alphanumeric': 0.036764959475771686, 'fraction_numerical': 0.006828763579927574, 'mean_word_length': 4.724777887462981, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
DGPO: Discovering Multiple Strategies with Diversity-Guided Policy Optimization

Recent algorithms designed for reinforcement learning tasks focus on finding a single optimal solution. However, in many practical applications, it is important to develop reasonable agents with diverse strategies. In this paper, we propose Diversity-Guided Policy Optimization (DGPO), an on-policy framework for discovering multiple strategies for the same task. Our algorithm uses diversity objectives to guide a latent code conditioned policy to learn a set of diverse strategies in a single training procedure. Specifically, we formalize our algorithm as the combination of a diversity-constrained optimization problem and an extrinsic-reward constrained optimization problem. And we solve the constrained optimization as a probabilistic inference task and use policy iteration to maximize the derived lower bound. Experimental results show that our method efficiently finds diverse strategies in a wide variety of reinforcement learning tasks. We further show that DGPO achieves a higher diversity score and has similar sample complexity and performance compared to other baselines.


Introduction
Reinforcement learning (RL) has achieved human-level performance in various tasks, e.g., video games [1][2][3][4] and robotics [5,6]. However, RL algorithms are notorious for highly "overfitting" the given task, i.e., while there is a diverse set of quality solutions for the given problem, RL algorithms can only obtain a single optimal one. Finding a set of qualified diverse strategies is crucial for a robust agent. For example, agents acquired with qualitatively different strategies can quickly adapt to perturbations of environments [7]. Moreover, in the adversarial games, an agent's weakness can be easily identified if it always plays in a fixed pattern. Thus, improving the diversity of agents' strategies can enhance their final performance [8]. Moreover, practical applications like dialogue generation bots need to respond to users in various styles to improve customers' experience. As a general rule, there are two main reasons for obtaining diverse strategies: (1) Some mistakes occur in a way that matters less for the success of the tasks. Thus, a qualified agent does not need to achieve optimal strategies. A set of sub-optimal strategies that adjust to the global optimal point is acceptable [9]. (2) Some tasks themselves have multiple solutions [10,11], e.g., there may be two optimal trajectories with equal length in a maze.
However, exploring a set of qualified diverse solutions in a sample-efficient way is a non-trivial problem, and the proposed algorithm should address the following four challenges: Strategy Representation: The deep reinforcement learning model should be capable of representing different kinds of strategies. Thus, we should develop a method to encode diverse strategies with the deep model.
Diversity Evaluation: The algorithm should be able to evaluate the diversity score of a given set of policies. Thus, we define a rational diversity metric based on mutual information of states and latent variable z and introduce a discriminator to implement it.
Diversity Exploration: The algorithm should know how and when to explore so that the policies can deviate from the already known ones. It is important to carefully design the diversity objective and use it to guide the policy to explore.
Sample Efficiency: The algorithm should be sample efficient. Previous methods, such as RSPO [11] and RPG [12], need multiple training stages to obtain the diverse strategies, resulting in poor sample efficiency. However, our algorithm is more sample efficient since we train multiple strategies simultaneously, and the knowledge acquired during training is implicitly shared via using the same neural networks.
In this paper, we proposed Diversity-Guided Policy Optimization (DGPO), an on-policy framework for discovering multiple strategies for the same task. Our algorithm uses diversity objectives to guide a latent code conditioned policy to learn a set of diverse strategies in a single training procedure. Specifically, we formalize our algorithm as the combination of a diversity-constrained optimization problem and an extrinsic-reward constrained optimization problem. Then we solve the constrained optimization as a probabilistic inference task and use policy iteration to maximize the derived lower bound.
To sum up, our contributions are as follows: (1) We introduce intrinsic reward based on the diversity objective to guide the policy to explore and formalize two constrained optimization problems to efficiently discover a set of optimal strategies. (2) We carefully designed a novel on-policy algorithm, denoted as DGPO, that can find a diverse set of quality strategies simultaneously. (3) We empirically show that our method achieves competitive performance and sample efficiency with better diversity than other baselines on various benchmarks.

Reinforcement Learning as Probabilistic Graphical Model
Representing the reinforcement learning task as a probabilistic graphical model (PGM) has been studied in previous works [13][14][15]. Soft actor-critic (SAC) algorithm [16] formalizes reinforcement learning as probabilistic inference and maximizes the evidence lower bound by adding an entropy term to the training objective, which can encourage the agent to explore. The PGM also serves as a useful tool for solving partially observable Markov decision process (POMDP) problems with a unified framework [17][18][19]. [20] used PGM to construct a hierarchical reinforcement learning algorithm, and their method can solve complex sparse-reward tasks by learning higher-level policies on top of high-entropy skills. [21] learned a multi-task policy from a variational bound, and their method allows for the discovery of multiple solutions with a minimum number of distinct skills. In our paper, we inject a latent variable for the Markov decision process in the PGM to form a diverse MDP. We then derive the evidence lower bound to construct a novel reinforcement learning algorithm.

Diversity in Reinforcement Learning
Achieving diversity has long been studied in the reinforcement learning community [22][23][24]10]. [24] proposed DIYAN to maximize the mutual information between states and skills, which results in a maximum entropy policy. Moreover, [10] proposed an RL method that can learn infinitely many solutions by training a policy conditioned on a continuous or discrete low-dimensional latent variable. Their method can learn diverse solutions in continuous control tasks via variational information maximization. There is also a growing corpus of works studying the diversity of multi-agent reinforcement learning [25][26][27]. [27] investigated multi-agent algorithms for learning diverse skills using information bottlenecks with unsupervised rewards. However, their method does not train agents to solve a specific task, and it just learns various behaviors randomly. More recently, [11] proposed the RSPO algorithm to derive diversity strategies. However, their method needs multiple training stages, which results in poor sample efficiency. Instead, our method can train diverse strategies simultaneously to reduce the sample complexity. Figure 1: The probabilistic graphical model of MDPs. Grey nodes are observed, and white nodes are hidden. As introduced in [15], the O t is a binary random variable, where O t = 1 denotes that the action is optimal at time t, and O t = 0 denotes that the action is not optimal.

Preliminary
Reinforcement learning can be formalized as a Markov decision process (MDP). Formally, a MDP is represented as a tuple (S, A, P, r, γ), where S and A stand for state space and action space respectively. P (s, a) : S × A → S is the transition probability density. r(s, a) : S × A → R is the reward function. γ ∈ [0, 1] is the discount factor. Latent conditioned policy: We consider policy π θ that is conditioned on latent variable z to model the diverse strategies, where θ is the parameter of the policy π. For the sake of simplicity, we will omit the θ in the policy. And we denote the latent conditioned policy as π(a|s, z) and the latent conditioned critic network as V π (s, z). We will randomly sample a latent variable z ∼ p(z) at the beginning of every episode and use policy π to sample a trajectory τ z , with z being fixed for the entire episode. The latent variable z is sampled from a categorical distribution with the number of categories n z and p(z) is the uniform distribution over these integers.
Discounted state occupancy: The discounted state occupancy measure of policy π is defined as ρ π (s) = (1 − γ) ∞ t=0 γ t P π t (s), where P π t (s) is the probability that policy π visit state s at time t. The goal of the RL agent is to train a policy π to maximize the discounted accumulated reward J(θ) = E z∼p(z),s∼ρ π (s),a∼π(·|s,z) [ t γ t r(s t , a t )].
Reinforcement learning as probabilistic graphical model: An MDP can be represented as a probabilistic graphical model as shown in Fig. 1 and the optimal control problem can be solved as a probabilistic inference task. We introduce a binary random variable O t and an integer random variable z into the model. O t = 1 denotes that action a t is optimal at time step t and O t = 0 denotes it is not optimal. Normally, p(O t = 1|s t , a t , z) is defined as being proportional to exp(r(s t , a t )) to reflect the utility of decision at time step t. On the other hand, diversity term p(z|s t , a t ) reflects whether the newly discovered strategies are sufficiently different from existing ones. The evidence lower bound (ELBO) is given by: where the trajectory τ = {a 1:T , s 1:T , z} is sampled from a trajectory dataset D π . The proof of Eq. 1 can be found in the appendix E.
The diversity term p(z|s t , a t ) in the ELBO is a crucial element in our algorithm. It guides the policy to explore in a unique style and discover a set of diverse quality strategies. We divide our algorithm into two parts. First, we formulate the training process as a diversity-constrained optimization problem. The diversity constraint forces the policy to deviate from the already found ones. Then, we formulate the training process as an extrinsic-reward-constrained optimization problem. In this stage, the diversity term serves as an intrinsic reward that guides the policy to explore.

Diversity-guide Exploration
In this section, we introduce a diversity metric that can evaluate the diversity score of the given set of policies and derive a diversity objective from it to aid exploration. The relationship between the diversity term log p(z|a 1:T , s 1:T ) in Eq. 1 and the mutual information of states and latent variables z can be written as: where I(·, ·) stands for mutual information. As we can not directly calculate p(z|s), we approximate it with a learned discriminator q φ (z|s) and derive the ELBO as where φ is the parameters of the discriminator network.
Eq. 2 shows that mutual information reflects the diversity score. However, using it as the diversity metric may cause problems. As shown in the previous work [28], mutual information is equal to the KL distance between the state marginal distribution of one policy and the average state marginal distribution, i.e., I(s; z) = E z∼p(z) [D KL (ρ π (s|z)||ρ π (s))]. It means that this metric only reflects the overall diversity score of a set of policies. To ensure that strategies will be pairwisely different when the diversity score is high, the diversity metric can be defined as below: Instead of comparing policy with the average state marginal distribution, we compare it with the nearest policy in the ρ π (s) space. In this way, DIV(π θ ) ≥ δ means that each pair of policies have at least δ distance in terms of expectation. To implement DIV(π θ ) in Eq. 3, we first derive a lower bound of DIV(π θ ) as below: .
The proof of Eq. 4 can be found in appendix F. To maximize the lower bound objective in Eq. 4 with policy optimization, we introduce the intrinsic reward based on learned discriminator q φ (z|s) as below: We introduce a diversity objective J Div (θ), which has a similar definition to J(θ) but considers intrinsic rewards: A naive method to incorporate the intrinsic rewards into PGM is defining elements in Eq. 1 as: However, the simple combination of extrinsic and intrinsic rewards may lead to poor performance. In the following paragraph, we formulate the algorithm as constrained optimization problems and mask elements in Eq. 7 based on constraints to guide the policy to explore.

Diversity-Constrained Optimization
In the practical environment, the optimal solutions to the given problem may be significantly distinct.
In other words, these optimal strategies are a set of discrete points that lie in the ρ π (s) space. To find all of these optimal strategies, perturbing around one optimal strategy is not enough. Thus, we formulate the policy optimization process as a diversity-constrained optimization problem: In this way, policies will systematically explore their own regions, gradually deviate from each other, and are more likely to converge to different optimal points. We can use a Lagrange multiplier λ to solve this constrained optimization problem: The proof of Eq. 9 can be found in the appendix G. Eq. 9 shows that we can maximize a lower bound of the Lagrange multiplier objective instead of solving the original constrained-optimization problem directly. As shown in Eq. 9, for each incoming data s ∼ ρ π (s) we optimize the extrinsic-rewards objective J(θ) when the data's diversity metric is greater than a threshold. Otherwise, we optimize the intrinsic rewards r in t . From another perspective, it is equal to adding diversity masks to the elements in Eq. 1. The updated objective can be written as below: where

Extrinsic-Reward-Constrained Optimization
In previous sections, we have found a set of discrete optimal points. However, sometimes two strategies will converge to the same sub-optimal region even if we train the policies with a diversity constraint. And the training process will become unstable since both of the strategies are attracted to the same optimal point but repelled by their counterparts simultaneously. To stabilize the training process and improve the diversity, we relax the definition of "optimal" and assume that a policy with accumulated extrinsic rewards greater than the target value is an optimal policy. Thus, the policy optimization process can be formulated as an extrinsic-reward-constrained optimization problem: This equation shows that if two strategies end up converging to the same sub-optimal region. They are allowed to find their destiny in the neighborhood of the optimal point to further maximize the level of diversity. On the other hand, for those policies that have been sufficiently different from others. The diversity objective serves as an intrinsic reward to explore. Similar to how we deal with diversity-constrained optimization. We implement Eq. 11 by injecting an extrinsic-rewards constraint into the framework. The updated elements in Eq. 1 can be defined as: where J const (π θ ) = 1 when J(θ) ≥ R target , J const (π θ ) = 0 otherwise and α ≥ 0 is a constant hyper-parameter.

Diversity-Guided Policy Optimization
In this section, we summarize our algorithm and introduce how to implement it with on-policy RL algorithm. We develop a new variation of PPO [29] by considering policy network and critic network that are conditioned on latent variable z, i.e., π(a t |s t , z). The critic network is divided into two parts, i.e., V π ψex (o 1:t , z) for approximating accumulated extrinsic rewards and V π ψin (o 1:t , z) for approximating the diversity objective, where ψ ex and ψ in are their parameters. The parameters of critic networks can be trained by a temporal difference (TD) loss [30]. We maintain a running average of V π ψex (s t , z) to approximate E s∼ρ π (s),a∼π(·|s) [ t γ t r(s t , a t )]. We also construct a discriminator q φ (z|s t ) that takes the state as input and predict the probability of latent variable z, where φ is the parameter of the discriminator network. And the discriminator can be trained in a supervised manner: where CE(·, ·) stands for cross entropy loss. We implement DGPO by incorporating diversityconstrained optimization and extrinsic-reward-constrained optimization into the same framework, i.e., the total rewards can be defined as below: Theoretically, we can not conduct diversity-constrained optimization and extrinsic-reward-constrained optimization simultaneously. Thus, the implementation above is an approximation to the original objective. We assume that the approximation is reasonable since the empirical results show that the two training stages do not overlap. Fig. 2 and Algorithm 1 show the overall framework of the DGPO algorithm.

Experiment Setup
In this section, we evaluate our algorithm on multiple RL benchmarks, i.e., Multi-agent Particle-world Environment (MPE) [31], StarCraft II Micromanagement Challenge (SMAC) [32], and Atari [33]. We compare our algorithm with 4 baseline algorithms, including MAPPO [34], DIAYN [24], SMEPL [7], and RSPO [11]. We summarize these algorithms as belows: MAPPO [34]: MAPPO adapts the single-agent PPO [29] algorithm to the multi-agent setting by using a centralized value function without individual utilities. DIAYN [24]: DIAYN introduces an intrinsic reward based on mutual information and trains the policy with this reward to discover a set of skills. We design two versions of DIAYN. DIAYN-v1 simply adds the intrinsic reward and task-specific reward together. DIAYN-v2 first unsupervised trains the model by intrinsic rewards and then fine-tune on the task-specific rewards. SMEPL [7]: SMEPL maximizes a weighted combination of intrinsic rewards and extrinsic rewards when the return of extrinsic reward is greater than the given threshold. RSPO [11]: RSPO finds a diverse set of quality strategies iteratively. It switches between extrinsic and intrinsic rewards via a trajectory-based novelty measurement to discover undiscovered local optimums.
For a fair comparison, we ensure that all the methods except RSPO use the same network structure and adopt the same hyper-parameters.   In both scenarios, Agents(purple dots) aim to reach one of the destinies (black dots). We highlight the optimal solutions in different colors.

Multi-Agent Particle-World Environment
We empirically study our method on two scenarios, Spread(easy) and Spread(hard). In the Spread(easy), there are four landmarks and one agent. The agent starts from the center and aims to reach one of the landmarks. In the Spread(hard) scenario, there are three agents and three landmarks. Agents cooperate to cover all the landmarks and avoid colliding with others. The optimal solutions to these problems can be found in Fig. 3. We consider the task that always starts with the same initial state.
Similar to [35], we introduce a metric to quantitively evaluate the diversity score of the given set of policies Π: is the behavior embedding of the policy π. In the MPE tasks, Φ(π) stands for an episode of agents' position collected by policy π.
We compare our algorithm with baseline algorithms in both scenarios. We set n z = 4 in Spread(easy) to test whether an algorithm can find out all of the possible optimal solutions. It is hard to determine the number of solutions in practice. Thus, we set n z = 3 in Spread(hard) to test the performance when n z is greater than the number of optimal solutions. All results are averaged over 5 seeds. The performance of each algorithm at convergence is shown in Fig. 4.
Steps(×10 6 ) RSPO DGPO(ours) Spread(easy) 0.449 0.324 Spread(hard) 4.685 0.290 Table 1: Steps to convergence in Spread(easy) and Spread(hard). Results show that DGPO uses significantly fewer steps to converge than the iterative method RSPO. Fig. 4 and Table 1 show that DGPO achieves reasonable performance and has the highest diversity score among all of the algorithms. MAPPO always finds identical trajectories in both scenarios even with the use of the latent conditioned policy. The performance of DIAYN-v1 is unstable since the intrinsic rewards may sharply influence the rewards space and make exploration difficult. DIAYN-v2 is unstable and highly depends on the pre-training model obtained by the unsupervised learning stage. The phenomenon is more significant in Spread(hard), which needs a long-term exploration to obtain the solutions. SMEPL discovers multiple strategies by perturbing around the global optimal point. Thus, it finds a set of similar strategies and has a relatively low diversity score. Although RSPO has a similar level of diversity to DGPO, it is sample inefficient and has a significant decadence on the performance when n z becomes larger. In this game, our agent (in white) has a boxing match with the opponent (in black). When z = 0, the agent attacks the opponent from the left-hand side. When z = 1, the agent attacks the opponent from the right-hand side. The heatmaps show the overall trajectories of our agents.  We apply DGPO to two Atari scenarios: Pong and Boxing to test the performance of our algorithm for image input tasks. We set the behavior embedding Φ(π) as the average image in an episode collected by policy π. In each scenario, we set n z = 2 and measure the average diversity score over 5 seeds for all the algorithms. Results are summarized in Table 2, where DGPO significantly outperforms all the baselines. Fig. 5(a) visualizes the results of the two strategies obtained by DGPO on Pong. In this game, we control the paddle (green block) to hit the ball (white dot). When z = 0, the agent waits at the bottom of the screen and moves upward to hit the ball when the ball comes. When z = 1, the agent waits at the top of the screen. Fig. 5(b) visualizes two different strategies obtained by the DGPO algorithm on the Boxing game. In this scenario, we control the agent (in white) to duke it out in the ring. In each step, the agent can move or punch and will be rewarded when successfully punching the opponent (in black). Fig. 5(b) shows that DGPO can learn to attack the opponent from different sides while other baseline algorithms always stay in one corner. Due to the space limit, more experimental results on Atari are placed in the appendix.

StarCraft II
We conduct experiments on two StarCraft II maps(i.e. 2s_vs._1sc and 3m) from the SMAC benchmark.
In each map, we set n z = 3 and measure the average winning rates over 5 seeds for all the algorithms. Fig. 6(a) compares the training curve of DGPO to baseline algorithms. To test the efficiency, we compare our algorithm with the original MAPPO algorithm that does not take latent variable z as input and another version of MAPPO that considers latent conditioned policy, which we denoted as MAPPO and MAPPO(with z) respectively. Empirical results show that DGPO takes 1.5 to 2 times as long to converge as MAPPO(with z) and DGPO finds three different strategies simultaneously. Fig. 6(b) visualizes three strategies obtained by DGPO on 3m map. In this map, we control three agents (in green) to combat build-in agents (in red). We visualize the moving trajectories of our agents in green arrows. When z = 0, the policy produces an aggressive strategy, i.e., our agents move forward to attack the enemies directly. When z = 1, the policy produces a kiting strategy, i.e., our agents keep switching between attacking and moving. Through this, they can attack the enemies and avoid damage from them. When z = 2, the policy produces another kiting strategy but the agents move downward.

Ablation Study
To conduct an ablation study, we conduct experiments on the MPE tasks and iteratively remove each of the elements in our algorithm to see how these changes damage the performance. No-Diversity-Constrained can only find one optimal solution in both scenarios. However, the trajectories obtain from different latent-conditioned policies have subtle diversity thanks to the extrinsic-reward constrained optimization stage. No-Diversity-Guided rejects data that do not fulfill the diversity constrained. It fails to find an optimal solution in both scenarios due to sample inefficiency. Change-Diversity-Objective uses mutual information as shown in Eq. 2 as diversity metric. It has a lower diversity score in Spread(hard). In this scenario, two out of three solutions it found lying in the same sub-optimal region. We have shown that Eq. 2 only reflects the overall diversity, i.e., the influence of further policy will dominate the closer one. And our diversity metric can relieve this problem. No-Extrinsic-Reward-Constrained has higher performance but lower diversity scores. By adjusting the hyper-parameter R target , we can strict a balance between performance and diversity.
We find that our algorithm can be noticeably divided into two stages, which we highlight in different background colors in Fig. 7. The policies will move randomly at the beginning stage of the training, so the diversity score is relatively high. However, the random policies do not behave in a unique style, which makes the trajectories indistinguishable. Thus, we mainly conduct diversity-constrained optimization in this stage. The diversity score may decline as the performance increase since there is a similar pattern for every optimal strategy. Our algorithm will switch into extrinsic-reward-constrained optimization once the expected accumulated reward becomes greater than R target . In this stage, we fix the performance to be equal to R target and maximize the diversity score. Fig. 7(a) shows the diversity score of each method, and DGPO can further improve the diversity score in this stage, but Non-Extrinsic-Reward-Constrained can not. We also report the performance of each method in Fig. 7(b), and No-Diversity-Guided fails to find an optimal solution in both scenarios due to the sample inefficiency.

Conclusions
In this paper, we proposed Diversity-Guided Policy Optimization (DGPO), an on-policy algorithm that can efficiently discover diverse quality strategies. DGPO formulates the training process as two constrained optimization problems and solves them as a probabilistic inference task. Empirical results indicate that DGPO has competitive performance and sample efficiency with state-of-the-art on-policy RL algorithms and achieves the highest diversity score in comparison with baseline algorithms in various domains. Currently, our method is implemented with latent variables which are sampled from a categorical distribution. In the future, we will try to incorporate the DGPO algorithm with continuous latent variables, and we also try to apply DGPO to a more complex scenario and study how it contributes to exploration, self-play, and robustness. Lastly, we do not believe our work has broader negative societal impacts, as we focus on developing new reinforcement learning algorithms to obtain diverse solutions.

B Network structure for Atari Games
The overall framework of the DGPO algorithm for Atari games is summarized in Figure 8. We introduce two Convolutional Neural Networks(CNN) to deal with image inputs. One for extracting features for diversity and another for extracting features for calculating extrinsic rewards.

D Hyperparametric sensitivity
In this section, we test whether our algorithm is sensitive to the choice of hyper-parameters. We study our method in Spread(hard) scenario and test two hyper-parameter, including R target and δ. The results can be found in Figure 9.   Figure 9 shows that both R target and δ have influence on diversity points and rewards. In general, the higher rewards our algorithm gets, the lower the diversity points it obtains. We can strike a balance between rewards and diversity points by choosing the appropriate R target and δ. Empirical results show that our algorithm is not sensitive to the choice of hyper-parameters. Except for δ = − log 1.99, all hyper-parameter achieve competitive rewards and high diversity points.
We can use a Lagrange multiplier λ to solve the constrained optimization problem above: where the inequality on the last line is hold because of Jensen inequality and the fact that min λ is a convex function.

H Training curve
In this section, we show the training curves that do not report in the main paper due to the space limit. (c) ratio of data that satisfy Div(θ) ≥ δ curve of different algorithms in Spread(easy) scenario (d) ratio of data that satisfy R ex exp ≥ Rtarget of different algorithms in Spread(easy) scenario (e) rewards of different algorithms in Spread(hard) scenario (f) diversity points of different algorithms in Spread(hard) scenario (g) ratio of data that satisfy Div(θ) ≥ δ of different algorithms in Spread(hard) scenario (h) ratio of data that satisfy R ex exp ≥ Rtarget of different algorithms in Spread(hard) scenario