\section{Introduction}\label{sec:1}}
Reinforcement Learning (RL) provides a mathematical formalism for an agent to learn a policy maximizing the expected cumulative rewards in a given environment. 
RL has achieved great success in learning an efficient policy for a given task, including board games\cite{silver2017mastering, silver2018general}, poker games\cite{zha2021douzero, zhao2022alphaholdem}, video games\cite{mnih2015human, berner2019dota, vinyals2019grandmaster, lillicrap2015continuous, haarnoja2018soft}, autonomous control\cite{schulman2015trust,bellemare2020autonomous, schulman2017proximal, fujimoto2018addressing}, and robotic manipulation\cite{kober2008policy, kober2013reinforcement, kalashnikov2018scalable, andrychowicz2020learning}. 
A reinforcement learning environment is typically formulated as a Markov decision process (MDP).
And an MDP is limited by the Markovian assumption that a reward only depends on the immediate state and action.
The policy is constantly updated during the learning process, and a policy updating trajectory will be generated in the policy space.

To maximize the expected cumulative reward under MDP, there are many qualitatively different optimal or near-optimal policies for the agent's decision. 
Considering the insufficiency of prior knowledge from the environment, learning diverse policies can avoid converging to only one local solution and handle more irregular situations.
A series of existing Quality-Diversity (QD)~\cite{pugh2016quality} related evolutionary algorithms have achieved good performance in exploring diverse behaviors and diverse policies~\cite{cully2017quality,gangwani2020harnessing,hong2018diversity,masood2019diversity,peng2020non,zhang2019learning,conti2017improving}. 
The MAP-Elites algorithms \cite{cully2015robots,mouret2015illuminating} solve this problem by discretizing the behavior description space into a grid of cells. 
Some theoretical conclusions are also developed to ensure that diverse policies are not obtained by sacrificing their effectiveness. 
The DvD \cite{parker2020effective} algorithm proves that under tabular MDP, multiple distinct optimal solutions can be obtained by maximizing the proposed loss function.
The ridge rider algorithm \cite{parker2020ridge} proposes to use the eigenvectors of the Hessian matrix to discover diverse local optima with theoretical guarantees.
\cite{nieves2021modelling} theoretically shows that maximizing the diversity metric based on the decision point process can guarantee to enlarge the convex polytopes spanned by the policies of agents. 
However, the above methods neglect to capture reward-relevant historical information, which is essential to non-Markovian environments.




In most real-world problems, the rewards do not depend on the immediate state and the chosen action but rather on the agent's visited states and performed actions. 
In such environments, the Markovian assumption (MA) does not hold, and the reward function has a temporal nature \cite{neider2021advice}, that the agent receives its rewards for complex, temporally-extended behaviors sparsely. 
For example, a robot should be rewarded for delivering coffee only if a user previously requested it. 
The example describes a non-Markovian reward recently studied in \cite{camacho2017decision,gaon2020reinforcement,brafman2018ltlf}. 
The non-Markovian rewards typically offer sparse supervision signals for the training process, which means the agent will not get rewards or get zero rewards in most timesteps. 
This leads the agent to acquire similar policies. 
When the agent achieves the goal and gets a non-Markovian reward, the agent generally tends to memorize the action trajectory and overfit the given task, and this leads the agent can not quickly adapt to perturbations of environments. 









\textbf{Proposal/Motivation} To resolve this problem, the key is to learn diverse policies from the history of the state-action pairs under a non-Markovian environment.
An inherent motivation is that maintaining a set of diverse policies leads to better exploration and quick adaptation to perturbations of environments \cite{kumar2020one}.
In an RL task, the candidate policies of the agent usually have consistent initialization states, that is, their embeddings are aggregated in a unified region in the policy embedding space. 
In this setting, learning diverse policies requires the policy embeddings to be sufficiently dispersed.
During this potential dispersion process, the embeddings are repeatedly constructed as the policy update progresses, forming different dispersion trajectories (Fig. \ref{policy dispersion}). 
To obtain diverse dispersion trajectories, maximizing the dispersion disagreements of dynamic policy updating trajectories could be a feasible and effective strategy. 








\textbf{Technical statement} Motivate by the above dispersion  perspective, this paper presents a policy-efficient method  \textbf{D}iscovering \textbf{D}iverse \textbf{P}olicy via \textbf{E}mbedding \textbf{D}ispersion (D2PED), which can efficiently learn high-quality policies with diverse behaviors in non-Markovian environments.
Specifically, we design a policy dispersion scheme to disperse policy embeddings along different trajectories as the policy update progresses. 
Then the policy embeddings are employed to construct a \emph{ dispersion matrix}, which is used to measure the diversity of the candidate policies and guides the update of the policies.
Learning effective embeddings for the policies that capture the features of the non-Markovian environment is key to solving this problem.
We use a Transformer-based architecture~\cite{vaswani2017attention} to capture long-horizon dependencies for histories of state-action pairs, which include all reward-relevant historical information. 
Moreover, in non-Markovian environments, the agent receives its reward sparsely for complex actions over a long period of time \cite{neider2021advice}, which is not conducive to training the Transformer-based policy representation model.
We construct a sample categorical distribution to sample higher cumulative reward trajectories with a higher probability. 
We also give the theoretical conditions such that the policy diversity will not reduce their effectiveness. 

\begin{figure} 
\centering
\includegraphics[scale=0.4]{policy_dispersion.pdf}
\caption
{Policy embeddings dispersion.  There are three  dispersion trajectories   over  different policy embeddings, where their initial positions  are marked by a red circle.  
In the dispersion process, 
the embeddings are repeatedly constructed as the policy update progresses, forming three different dispersion  trajectories  with direction guidelines.
}
\label{policy dispersion}
\end{figure}

\textbf{Contributions} Our contributions are summarized as follows: 
\begin{itemize}
\item [$\bullet$]
\textbf{New Inisght} We present a novel RL perspective that models the policy update as embedding dispersion, deriving different trajectories to explore  policy diversity.

\item [$\bullet$] \textbf{New Scheme}
Motivated by our new insight, we design a policy-efficient method \textbf{D}iscovering \textbf{D}iverse \textbf{P}olicy via \textbf{E}mbedding \textbf{D}ispersion (D2PED), which can efficiently learn high-quality policies with diverse behaviors in non-Markovian environments.




\item [$\bullet$]\textbf{New Technique}
Under the new framework, we propose a policy dispersion scheme to disperse policy embeddings along different trajectories as the policy update progresses and use the embeddings to construct a dispersion matrix that guides the learning of diverse policies.




\item [$\bullet$] \textbf{Effective Analysis}
To guarantee the diversity of candidate policies can be achieved without sacrificing their effectiveness, we also prove that if the dispersion matrix is positive definite,  the optimal candidate policies could correspond to effective disagreements across policies dispersed embeddings.

\item [$\bullet$]
\textbf{Efficient Performance} With our effective module design  and theoretical analysis, our policy diversity learning scheme can be combined with any off-policy reinforcement learning algorithm, and the experimental results of various environments show that it outperforms multiple recently proposed baselines with both non-Markovian and Markovian environments.

\end{itemize}

The rest of this paper is organized as follows. In Section \ref{related work},
we introduce the related work. 
In Section \ref{Preliminaries},
we introduce the preliminary knowledge about Non-Markovian decision process and policy diversity learning.
The methodology of policy dispersion is presented in Section \ref{Methodology}, where \ref{sec:4.2} presents the policy representation module which is employed to generate
effective and diverse embeddings for different policies,
and \ref{sec:4.3} describes the process of dispersing the dynamically updating trajectories over
embedding reconstruction to learn diverse policies. 
In Section \ref{exp}, we conduct various experiments to demonstrate the effectiveness and robustness of D2PRD.
We conclude this paper in Section \ref{conclusion}.




\section{Related Work} \label{related work}
In non-Markovian environments, the reward function has a temporal nature, which means the agent receives its reward for temporally-extended behaviors
sparsely. This leads the agent to acquire similar policies and overfit the given task. 
To mitigate this problem, the agent needs to learn diverse policies.
In such a scenario, the policy representation learning was proposed and attracted the eyes of the learning community. Related works thus focus on the below  three aspects as the rising of our curtain.

\textbf{Non-Markovian Environment.} In a standard Reinforcement Learning (RL) problem setting of a Markov decision process (MDP), rewards depend only on the most recent state-action pair. 
In a non-Markovian reward decision process
(NMRDP) \cite{bacchus1996rewarding}, rewards depend on the
history of state-action pairs \cite{bacchus1996rewarding}. 
Building in temporal logics over finite traces, \cite{brafman2018ltlf} adopt linear dynamic logic on finite traces for specifying non-markovian rewards and provide an automaton construction algorithm for building a Markovian model.
In another paper \cite{camacho2017non}, the authors are concerned with both the specification and effective exploitation of non-Markovian rewards in the context of MDPs. They specify non-Markovian reward-worthy behavior in LTL. Similarly, \cite{li2017reinforcement} use truncated LTL as a reward specification language, and \cite{toro2018teaching} use ${\rm LTL}_f$ to specify desired complex behavior. 
Because temporal formulas are evaluated over an entire trace, it is difficult to guide the RL agent locally towards desirable behaviors.
Data-driven approaches to learning NMRDP problems \cite{icarte2018using} often make use of domain-specific propositions and temporal logic operators \cite{bacchus1997structured, thiebaux2006decision, toro2019learning}.

\textbf{Learning diverse policies via Reinforcement Learning.} Our method can be grouped into this category. Some Reinforcement Learning (RL) based methods have been developed to explore diverse behaviors \cite{eysenbach2018diversity,hartikainen2019dynamical}. 
The GEP-PG algorithm \cite{colas2018gep} uses Goal Exploration Processes \cite{forestier2017intrinsically} to generate diverse policies and combines them with the Deep RL algorithm DDPG \cite{lillicrap2015continuous}, which performs well in continuous control tasks. 
The RSPO \cite{zhou2022continuously} explores diverse policies by solving a filtering-based objective, which restricts RL policies from converging to a solution that differs from a set of local optimal policies.
P3S-TD3 \cite{jung2019population} method periodically determines the best policy among all learners and assigns the best policy parameters to all learners so that the learner can search for a better policy under the guidance of the best policy.


\textbf{Policy representation learning.} A generative method is proposed in \cite{grover2018learning}, which proposed an encoder-decoder method for modeling the agent’s policy. 
The encoder learns a point-based representation of different agent trajectories, and the decoder learns to reconstruct the modeled agent’s policy.
Two meta-learning methods are proposed in \cite{rusu2018meta, ghosh2020representations}, and they both regard the latent generative representation of learning model parameters as the policy representation, and the method in \cite{ghosh2020representations} shows more stable performance.
\cite{tacchetti2018relational} proposed relational forward models to model agents using
graph neural networks. 
\cite{zintgraf2021deep} uses a VAE for agent modeling for fully-observable
tasks.
\cite{rabinowitz2018machine} proposed the Theory of mind Network (TomNet), which learns embedding-based representations of modeled agents for meta-learning.


Learning diverse policies and effective policy representations is difficult with non-Markovian rewards since the rewards depend on the history of states and actions, and the supervision signals are usually sparse. Moreover, diverse policies should be obtained without sacrificing their effectiveness. To the best of our knowledge,  our method is the first method that discusses policy diversity learning in non-Markovian environments.




\section{Preliminaries} \label{Preliminaries}
In this section, we present the necessary background relevant to the problem setting of this work. 

Markov Decision Process (MDP) is a mathematical framework to describe an environment in reinforcement learning.
An MDP is a tuple $ \mathcal{M} = \left\langle S, A, P, R, \gamma \right\rangle $, where $S$ and $A$ represent state space and action space, respectively. 
The state transition dynamic function is given by $P:S \times A \rightarrow S$, which is a mapping from the current state $s \in S $ to the next state $s'\in S$. The reward function is given by $R:S \times A \rightarrow \mathbb{R}$, mapping from state $s \in S$ and action $a\in A$ to reward $r \in \mathbb{R}$. $\gamma \in [0,1)$ denotes the discount factor. 

A Policy $\pi: S \rightarrow A$ is a mapping from $S$ to $A$. 
A trajectory $\tau \in \Tau$ is a sequence of state-action pairs, $\tau = ((s_0,a_0),...,(s_{T-1}, a_{T-1}))$.
In deep reinforcement learning, policy $\pi$ is typically a neural network, encoded by parameter vectors $\theta$, and the goal is to optimize parameters $\theta$ of $\pi$ such that an agent equipped with policy $\pi_\theta$ in the environment described by a fixed MDP maximizes $R(\tau)=\sum_{t=1}^{T}\gamma^{t-1} r_t$, the expected cumulative reward of a trajectory $\tau$ over an episode time-step horizon $T$ (assumed to finite). 
The typical objective function of policy $\pi_\theta$ is as follows:
\begin{equation}
J(\pi_\theta)=\mathbb{E}_{\tau\sim\pi_\theta}[R(\tau)].
\end{equation}


Non-Markovian Decision Process\cite{bacchus1996rewarding, bacchus1997structured, brafman2019regular, gaon2020reinforcement} (NMDP) extends MDP and assumes transition and reward functions depend on the history of state-action pairs.
Formally, an NMDP is a tuple $ M = \left\langle S, A, tr, R^{+}, \gamma \right\rangle $, where $S, A$ are as in an MDP, $tr: S^* \times A \times S \rightarrow \Pi(S)$ is the transition function, i.e., $tr((s_0, \ldots, s_k), a, s^{\prime})$ is the probability of reaching state $s^{\prime}$ when executing action $a$ given history $s_0, ..., s_k$.
Here $S^*$ is the set of finite, non-empty, state sequences.
A non-Markovian Reward (NMR) function is a mapping from the finite history of states and actions to reward $\mathbb{R}$, denoted as $ R^{+}: (S \times A)^* \rightarrow \mathbb{R}$. 

To make better exploration and have more robustness, novelty search methods \cite{conti2017improving, lehman2011abandoning} and QD \cite{pugh2016quality, cully2017quality} algorithms seek to find a set of policies with both high rewards and diverse behaviors, and explicitly augment the loss function with an additional term, as follows:
\begin{equation}
J(\pi_\theta) = (1- \lambda)\mathbb{E}_{\tau\sim\pi_\theta}[R(\tau)] + \lambda \rm Div(\pi_\theta)
\end{equation}
where $\lambda \in (0,1)$ controls the trade-off between the effective (i.e., expected cumulative rewards) and diversity, and $\rm Div(\pi_{\theta^{i}}) = \frac{1}{M} \sum_{i,j \in M, i\neq j}{||b(\pi_{\theta^{i}})-b(\pi_{\theta^{j}})||}_{2} $ is the diversity of a particular policy $\pi_{\theta^{i}}$ computed as the average Euclidean distance between $b(\pi_{\theta^{i}})$ and $\{b(\pi_{\theta^{j}})\}_{j \in M, j\neq i}$, $b(\pi_{\theta^{i}})$ denotes the behavior characterization of policy $\pi_{\theta^{i}}$.
In the following, for the convenience of representation, we will simplify $\pi_{\theta^{i}}$ into $\pi_{i}$.




\begin{figure*} 
\centering
\includegraphics[width=\linewidth]{policy_diversity.pdf}
\caption{\textbf{A schematic illustration of D2PED:} \textbf{(a)} The overall structure of D2PED. D2PED comprises the policy representation module and the policy dispersion module. 
$M$ learners execute parallelly and store trajectories into a shared replay buffer $D$. 
\textbf{(b)} The policy representation module samples a batch of trajectories from replay buffer $D$ and then constructs a sample distribution via Eq. (\ref{eq:cat}) to select high-quality trajectories for training the module. 
The Transformer encoder inputs the trajectories and output policy embeddings, then the embeddings are classified into policy indexes (classification labels) by the classification layer. 
\textbf{(c)} The policy dispersion module utilizes the policy embeddings to construct a dispersion matrix. 
The determinant of the diversity matrix is regarded as a policy diversity measure, which is further as a term of the policy diversity objective $\tilde{J}(\pi_m)$ (Eq. (\ref{10})). }
\label{Figure1}
\end{figure*}

\section{Methodology} \label{Methodology}

In this paper, we model the policy update as embedding dispersion, deriving different trajectories to explore policy diversity. 
In non-Markovian environments, it is difficult to learn effective policy embeddings since the rewards depend on the history of state-action pairs, namely, the embeddings need to capture reward-relevant historical information, and the supervision signals are usually sparse.
We present a Transformer-based policy representation
module, which is capable of learning effective policy embeddings in non-Markovian environments.
Meanwhile, to avoid the lack of supervision signal problem caused by non-Markovian rewards, we design
a sample categorical distribution to sample trajectories
for training the policy representation model.
Further, we propose a policy dispersion
scheme to disperse policy embeddings along different
trajectories as the policy update progresses and use
the embeddings to construct a dispersion matrix that
guides the learning of diverse policies.


Our proposed method, D2PED (Discovering Diverse Policies via Embedding Dispersion), comprises two primary submodules: the policy representation module and the policy dispersion module. 
The schematic illustration of our method is shown in Fig. \ref{Figure1}.
In our method, $M$ parallel learners learn $M$ distinct policies and share a common replay buffer $D$. 
The $M$ learners execute parallelly in different copies of the same environment and employ a common base algorithm which can be any off-policy RL algorithm. 







\subsection{Policy Representation Module} \label{sec:4.2}
The policy representation module is employed to generate effective and diverse embeddings for different policies. 
Inspired by \cite{grover2018learning}, trajectories consisting of state-action pairs can directly reflect the characteristics of the policy, and using trajectories to learn the policy embeddings is an effective method. 
In non-Markovian environments, rewards have a temporal nature in that each reward depends not only on the current state and action but also on the history of state-action pairs.
For this, the policy embeddings should aggregate all the reward-relevant historical information that accumulates over an episode time-step horizon.
So that we use a Transformer-based method, which is the current tool of choice for capturing long-horizon dependencies to learn the policy embeddings. 
Due to the temporal nature, non-Markovian rewards are usually sparse. 
To train the policy representation module with sparse supervision signals, we design a sample categorical distribution by the cumulative rewards of the trajectories to select samples for policy representation module training.

The representation module is shown in Fig. \ref{Figure1}(b), which is utilized to obtain effective policy embeddings. 
Specifically, for the $m$-th ($m\in\{1,...,M\}$) policy $\pi_m$, the representation module inputs a trajectory collected by $\pi_m$ and outputs a policy embedding $v_m$ for $\pi_m$.








\subsubsection{Sample Trajectories with Categorical Distribution}\label{sec:4.2.1}


In most non-Markovian environments, supervision signals of policy training are usually sparse. 
In order to learn effective policy embeddings, it is necessary to capture all the reward-relevant historical information that accumulates over an episode time-step horizon. 
So if the rewards are sparse, it means that there are very few rewards that can be used to capture the information, which is not conducive to learning policy embedding.
Thus, We build a sample categorical distribution by the cumulative rewards of trajectories to select high-quality (relatively high reward) trajectories to learn policy embeddings.


Let $\tau_{i,m}$ be the $i$-th trajectory collected by policy $\pi_m$, and $r_{i,m}$ denotes the accumulated reward of $\tau_{i,m}$.
We regard $r_{i,m}$ as a parameter of the categorical distribution and use this distribution to sample the trajectories for training policy $\pi_m$. 
Specifically, we construct the sample categorical distribution as follows: 
\begin{equation}\label{eq:cat}
i_m\sim\Cat{(\sigma(r_{i,m})^{\frac{1}{T}}/ \sum_{j=1}^N \sigma(r_{j,m})^{\frac{1}{T}})_{i=1}^{N}},
\end{equation}
where $\sigma$ is the sigmoid function, $N$ is the batch size that sample trajectories from replay buffer $D$ for policy $m$, and $N$ is equal for each policy. 
A hyperparameter $T$ is used to adjust the “temperature” of the sampling distribution. 
The trajectory index $i_m$ is sampled by the categorical distribution for policy $\pi_m$.

With the sample categorical distribution, trajectories with higher cumulative rewards will be sampled to train the model at a higher frequency, and $M$ policies are sampled multiple times using the distribution to obtain samples for learning $M$ policy embeddings.
We regard the trajectory indexes sampled by Eq. (\ref{eq:cat}) as the classification labels, which will be used to train the representation model by minimizing the loss Eq. (\ref{8}) in  Section \ref{sec:4.2.2}.


\subsubsection{Generative Policy Representations via Capturing Reward-Relevant Historical Information}\label{sec:4.2.2}
The non-Markovian rewards depend on the history of states and actions rather than solely on the immediate state and action. 
Thus, it is essential to understand and mine the complex characteristics in the trajectories and capture all reward-relevant historical information. 
So that we use a Transformer-based architecture to capture long-horizon dependencies between states and actions via self-attention mechanisms.

To train the Transformer-based policy representation module, we model the problem as a trajectory classification task. 
First, We sample $N$ trajectories for each of the $M$ policies and shuffle all the trajectories. 
Then the trajectories are used to train the policy representation module and output policy embeddings.
Finally, we regard the policy indexes of trajectories (the trajectories collected by which policy) as class labels, and 
we assign the class labels to the policy embeddings.

Specifically, we design the policy representation module as a mapping function $\Tau \rightarrow \mathcal{V} \rightarrow Y$ parameterized by $\phi$, which is the combination of Eq. (\ref{fun5}) and Eq. (\ref{6}), where $\Tau={\{\tau_{i,m}\}_{i=1, m=1}^{N, M}}$ denotes the set of trajectories collected by policies $\{\pi_m\}_{m=1}^M$, $\mathcal{V} ={\{v_m\}_{m=1}^M}$ is the policy embeddings, and $Y={\{y_m\}_{m=1}^M}$ is the set of the policy indexes. 
The module inputs trajectories and outputs policy embeddings which are the essential ingredients to learning diverse policies.
Then, the embeddings are classified into policy indexes to train this module.






The transformer architecture can efficiently model sequential data. 
This model consists of stacked self-attention layers with residual connections. 
Each self-attention layer receives embeddings generated by tokens and outputs embeddings that preserve the input dimensions.
For $i$-th $T$ time-step horizon trajectory collected by policy $\pi_m$, $\tau_{i,m} = (s_{i,m}^1, a_{i,m}^1, ... , s_{i,m}^T, a_{i,m}^T)$, we let $\omega_{i,m}^t=(s_{i,m}^t,a_{i,m}^t)$ for each time step $t\in\{1,...,T\}$ as a token. 
Subsequently, we regard $(\omega_{i,m}^t)_{t=1}^{T}$ as a sequence, and input to the Transformer encoder (i.e., a Layernorm (LN), a multiheaded self-attention (MSA) layer, and residual connections \cite{wang2019learning,baevski2018adaptive}), to obtain the policy embedding:
\begin{equation} \label{fun5}
v_{i,m} = {\rm MSA}(\rm LN(\omega_{i,m}^t)_{t=1}^{T} + E_{pos})+(\omega_{i,m}^t)_{t=1}^{T},
\end{equation}
where $v_{i,m} \in \mathbb{R}^{K}$ is the $i$-th embedding for policy $\pi_m$ and $E_{pos}$ is the positional encoding. 

To train the policy representation module with the policy indexes $Y={\{y_m\}_{m=1}^M}$, $v_{i,m}$ are processed with a classification layer (CL), which is formulated by:
\begin{equation} \label{6}
\xi_{i,m} = {\rm CL}(v_{i,m}),
\end{equation}
where $\xi_{i,m}$ is a vector in which the $j$-th element ($j \in \{1,2,...,M\}$) represents the probability that the policy embedding $v_{i,m}$ is assigned to the $j$-th policy.
Then we train the policy representation module and learn the policy embeddings by minimizing the loss function:
\begin{equation}\label{8}
\mathcal{L_{\phi}} = -\frac{1}{N}\frac{1}{M}\sum_{i=1}^{N}\sum_{m=1}^{M}({y_m}^T\log(\xi_{i,m})),
\end{equation}
where $y_m$ is the policy index (classification label) of $\tau_{i,m}$ obtained in Section \ref{sec:4.2.1}. 

We use the policy representation module to obtain $N$ policy embeddings for each of the $M$ policies. 
We then construct the diversity matrix by the policy embeddings, which are used to measure the diversity of the policy set and guide the policy dispersion in the space.


\subsection{Policy Dispersion Module}\label{sec:4.3} 

The candidate  policies  of the agent  usually  have consistent initialization  states, and their embeddings are concentrated in a unified region. 
Subsequently, the embeddings are repeatedly constructed as the policy update progresses, forming different dispersion  trajectories. 
To obtain diverse dispersion trajectories,  maximizing the dispersion disagreements of dynamically updating trajectories is effective. 
In this setting, those diverse policies  over varying dispersion  trajectories could provide  various decisions for the agent.





The policy dispersion module is shown in Fig. \ref{Figure1}(c), 
which aims to disperse the dynamically updating trajectories over embedding reconstruction, that is,   learning diverse policies for agent decisions. 
The key to learning diverse policies is to measure the diversity of the candidate policies, 
for which we construct a dispersion matrix using the policy embeddings. 

On this setting, the dispersion matrix stacks the embeddings of the candidate policies, modeling the process trajectory dispersion with direction guidelines.
Following the Determinantal Point Processes (DPPs) \cite{kulesza2012determinantal}, the determinant of the dispersion matrix  that proportionally draws the dimensional span over the associated geometric region of the  matrix, could be specified as a quantification of the disagreement of dispersion trajectories, that is, characterizing the diversity  of the candidate policies.


To construct the dispersion matrix, we randomly select an embedding for each of the $M$ policies from $\{v_{i,m}\}_{i=1,m=1}^{N, M}$, constituting $\{v_m\}_{m=1}^M$.
And stack the $M$ selected embeddings as the dispersion matrix. 
Further, we propose the following definitions to construct the dispersion matrix and compute the policy diversity measure as follows:




\newtheorem{definition}{Definition}[section]
\begin{definition}\label{diversity_matrix}
\textbf{(Dispersion Matrix)} Consider $M$ policies $\{\pi_m\}_{m=1}^M$, and their embeddings are denoted as $\{v_m\}_{m=1}^M$, where $v_m \in \mathbb{R}^{K}$. Let $V\triangleq[v_1,...,v_M]$, where $[ \cdot ]$ is the operator that stacks vectors into a Matrix. We define the Dispersion Matrix of policies as $\mathbf{S}\triangleq F(V)$, where $F(\cdot)$ is a function that transforms the $M\times K$ matrix $V$ to a $K\times K$ positive-definite matrix.
\end{definition}

\begin{definition}\label{diversity}
\textbf{(Policy Diversity)} We define the diversity of policies as the determinant of their dispersion matrix, denoted as $\rm Div(\{v_m\}_{m=1}^M) = \det(\mathbf{S})$. 
\end{definition}    



The matrix $V$ constructed by Definition~\ref{diversity_matrix} is an $M \times K$ matrix.
Suppose the number of candidate policies $M$ equals the dimension $K$ of the policy embeddings, i.e., $M=K$, the determinant of the square matrix $V$ that represents the dispersion disagreement of dynamically updating trajectories over embedding reconstruction, could be a feasible measurement for the diversity of the $M$ policies.
However, for the scenarios of  $M\neq K$, the function $F(\cdot)$ could be adopted to transform the polyhedron spanned by $M$ $K$-dimensional embeddings to a parallelepiped spanned by a $K$-by-$K$ positive-definite matrix in another embedding space. 
Then the determinant of the square matrix still  could measure the diversity of the $M$ candidate policies.


Now consider the total objective function ${J}(\Pi)$ of the candidate policies $\Pi=(\pi_1,...,\pi_m)$, which is the summation of two terms: the first term is the same objective function $J(\pi_m)$ as the base algorithm, and the second term is the policy diversity $\rm Div(\{v_m\}_{m=1}^M)$. Specifically, the D2PED objective function is as follows:
\begin{equation}\label{10}
{J}(\Pi) = \left\{\sum_{m=1}^{M} \left[(1 - \beta)J(\pi_m)+ \beta \rm Div(\{v_m\}_{m=1}^M) \right] \right\}
\end{equation}
where $\beta \in (0,1)$ controls the trade-off between $J(\pi_m)$ and $\rm Div(\{\pi_m\}_{m=1}^M)$.

Next, we will give a theory to justify that our method can ensure diversity and high-quality policies.







\newtheorem{theorem}{Theorem}[section]
\begin{theorem}\label{th4.1}
Consider $M$ policies for an environment characterized by finite NMDP. Suppose optimal policy $\pi_m$ achieves a cumulative reward of $R$ and suboptimal policy $\Tilde{\pi}$ achieves a cumulative reward of $R(\Tilde{\pi})$ with $R(\Tilde{\pi})+\Delta <R$ for some $\Delta>0$.  If dispersion matrix $\mathbf{S}$ is positive definite, and $\Lambda \triangleq \prod_{i=1}^{K}s_{ii} < \frac{(1-\beta)}{\beta}\Delta$, then the objective in Eq. (\ref{10}) can only be maximized when all policies are optimal.
\end{theorem}
The proof of Theorem \ref{th4.1} is in Appendix \ref{Theoretical Proof}. 
\begin{algorithm}[t] 
\caption{D2PED}
\label{alg:algorithm1}
\textbf{Require}: number of learners $M$, batch size $N$ for each policy, max iteration $Q$, period to train policy representation module $U$. \\ 
\textbf{Initialize}: $M$ policies $\{v_m\}_{m=1}^M$, parameters of policy representation module: $\phi$, environments ${\{E_1,\cdots,E_m\}}$, local experience replay buffer ${\{D_1,\cdots,D_m\}}$, shared replay buffer $D_s$. \\
\begin{algorithmic}[1]

	\WHILE{$q < Q$}
	\FOR{$m=1,2,\cdots,M$ learners in parallel}
	\STATE Reset the environment and get state $s_t$.
	\FOR{each running time step t}
	\STATE Sample action $a_m^t$ from policy $ \pi_m(a_m^t | s_m^t)$. 
	\STATE Apply the action $a_m^t$ to the environment.
	\STATE Get next state $s_m^{t+1}$ and the reward $r_m^t$. 
	\STATE Store the transition ($s_m^t,a_m^t,r_m^t,s_m^{t+1}$) into the local replay buffer $D_m$.
	\IF {environment $E_m$ done}
	\STATE Store trajectory $\tau_m=\{s_{m}^t,a_m^t,r_m^t\}_{t=1}^{T}$ into the shared replay buffer $D_s$.
	\ENDIF
	\ENDFOR
	\IF {$q\enspace \rm mod \enspace U == 0$}
	\FOR{each training step}
	\STATE Randomly sample $N$ trajectories for each of the $M$ policies from shared replay buffer $D_s$, denoted as ${\{\tau_m^i\}_{{i=1},{m=1}}^{{N},{M}}}$.
	\STATE Construct sample categorical distribution via Eq. (\ref{eq:cat}) to select training trajectories.
	\STATE Compute the policy embeddings ${\{v_{i,m}\}_{{i=1},{m=1}}^{{N},{M}}}$ via Eq. (\ref{fun5}).
	\STATE Predict classification labels ${\{\xi_{i,m}\}}_{{i=1},{m=1}}^{{N},{M}}$ via Eq. (\ref{6}).
	\STATE Compute $\mathcal{L_{\phi}}$ via Eq. (\ref{8}).
	\STATE Update $\phi$ for policy representation module.
	\ENDFOR
	\ENDIF
	\STATE Randomly samples $N$ trajectories for each of the $M$ policies and shuffles all the trajectories ${\{\tau_m^i\}_{{i=1},{m=1}}^{{N},{M}}}$.
	\STATE Compute policy embeddings $\{v_m\}_{m=1}^M$ via Eq. (\ref{fun5}).
	\STATE Stack policy embeddings $\{v_m\}_{m=1}^M$ to construct a matrix $V$.
	\STATE Compute a Dispersion Matrix $\mathbf{S} = F(V)$ based on the Definition \ref{diversity_matrix}.
	\STATE Compute Policy Diversity $\rm Div(\{v_m\}_{m=1}^M) = \rm det(\mathbf{S})$ based on the Definition \ref{diversity}.
	\STATE Compute ${J}(\Pi)$ and update candidate policies $\Pi$ with objective function: \ref{10}.
	\ENDFOR
	\ENDWHILE
\end{algorithmic}
\end{algorithm}

\textbf{A method to construct a dispersion matrix.} The theory holds if the dispersion matrix is positive definite, and we give a method to construct a positive definite dispersion matrix. 
In general, we compute the covariance matrix of the policy embeddings and then regard the determinant of the covariance matrix as the diversity of policies in Definition \ref{diversity}.
Specifically, we construct the covariance matrix $\mathbf{S}$ of $(v_m)_{m=1}^M$, where $v_m \triangleq (v_{m,k})_{k=1}^K$. The $(i,k)$-th element of $\mathbf{S}$ is ${s_{ik}=\frac{1}{M-1}\sum_{m=1}^{M}(v_{mi}-\Bar{v}_i)(v_{mk}-\Bar{v}_k)},$ 
where $M$ is the number of policies, 
and $\Bar{v}_i\triangleq \frac{1}{M}\sum_{j=1}^{M}v_{ji}$. 
However, the covariance matrix is semi-positive definite, in this section, we use the following method to make it positive definite.
If $\det(\textbf{S})=0$, we replace $\textbf{S}$ with $\tilde{\textbf{S}}$, where $(i,i)$-th element is $\tilde{s}_{ii}=s_{ii} + \sum_{j \neq i}|s_{ij}|.$
According to Gershgorin circle theorem \cite{gerschgorin1931uber}, the modified matrix $\tilde{\textbf{S}}$ is positive definite. 
In statistical analysis, the determinant of the covariance matrix is termed the generalized variance \cite{wilks1932certain}, which is proportional to the sum of squares of the volumes of all the different parallelotopes formed by the policy embeddings using as principal edges \cite{andersonintroduction,johnson2014applied}. 
Note that the volume of the enclosed geometric region of those policy embeddings also can reflect the policy diversity, where the detailed explanation is presented in Appendix \ref{Explanation for Generalized Variance}.
Therefore, $\det(\textbf{S})$ could be specified as the quantification of the disagreement of dispersion trajectories, that is, the diversity measure to the candidate policies.



The D2PED algorithm is summarized in Alg. \ref{alg:algorithm1}. 
D2PED employs a dispersion matrix to measure the diversity of the candidate policies and adds the determinant of the dispersion matrix to the policy objective function. 
To improve the efficiency of the algorithm, $M$ learners (i.e., $M$ diverse policies) execute parallelly in different copies of the same environment and share a shared replay buffer.







\section{Experiments}\label{exp}


In this section, we present our experimental results and discuss their implications. 
First, we provide an overview of the experimental setup and the environments we used to evaluate our models in
Section \ref{exp}. 
Second, in Sections \ref{exp_non} $\sim$ \ref{exp_mar}, we report results in several different environments respectively. 
Then, we
further provide an ablative analysis \ref{ablation study paragraph} of the proposed methodology.
Finally, we summarize hyperparameters \ref{hyperparameters paragraph} used in experiments.

\subsection{Experimental Setup}

We conduct experiments to evaluate the performance of our method from three settings of continuous action space, discrete action space, and robustness. 
In non-Markovian environments, rewards have a temporal nature in that each reward depends not only on the current state and action but also on the history of state-action pairs.
In Markovian environments, reward only depends on the immediate state and action.
Therefore, in a sense, the Markovian environment is a special case of the non-Markovian environment, that is, the history of state-action pairs that the reward depends on is only the current state-action pair.
To evaluate the robustness of our method, we also conduct experiments in Markovian environments.
\begin{figure} 
\centering
\includegraphics[scale=0.13]{point-v1.png}
\caption
{The Point-v1 environment.}
\label{point environment}
\end{figure}

\subsubsection{Environments}

\textbf{Point.} To explicitly examine whether our method can efficiently find high-quality
policies with diverse behaviors in the non-Markovian environment, we create the Point-v1 environment with non-Markovian rewards and multi-solution, which is modified from the Point-v0 \cite{parker2020effective} and has continuous state and action space. 
An agent and a target (i.e., green cuboid) are separated by three U-shape walls (see: Fig. \ref{point environment}). 
When an episode starts, the target randomly sends a signal to the agent. 
When the agent receives the signal and reaches the target, it will get an event reward of 100. 
If there is no signal at the target, the agent starts to move, or if the agent hits a wall while moving, it will get an event reward of -100. 
The current episode ends immediately if the agent hits the wall or reaches the target.
The agent only obtains a total reward at the end of each episode. 
The total reward is the sum of the event reward and the distance reward, which is the negative distance between the agent and the target at the end of the episode.



\textbf{FrozenLake.} For discrete control tasks, we perform experiments in the FrozenLake-v1 environments with non-Markovian rewards, which is a grid world game, some grids are walkable, and some grids are holes that will make the agent fall into the water (see: Fig. \ref{frozenlake environment}).
At the beginning of an episode, the agent will stand by in the upper left corner of the map, with the target grid in the lower left corner.
The task randomly sends a start signal to the agent. 
If the agent receives the signal and reaches the goal grid, a reward of 1 is obtained. 
If the agent starts moving without receiving the signal, a reward of 0 is obtained. 
If the target is not reached within a finite time step after receiving the signal or the agent falls into the hole, the obtained reward is still 0.
As the size of grids and the density of holes increase, it becomes increasingly difficult for agents to reach the target grid.

\begin{figure} 
\centering
\includegraphics[scale=0.25]{frozenlake_environment.pdf}
\caption
{The Frozenlake $8 \times 8$ environment.}
\label{frozenlake environment}
\end{figure}

\begin{figure} 
\subfloat[Hopper]{
	\begin{minipage}[t]{0.15\textwidth}
		\centering
		\includegraphics[width=1.1in]{hopper.png}
	\end{minipage}
}
\subfloat[Halfcheetah]{
	\begin{minipage}[t]{0.15\textwidth}
		\centering
		\includegraphics[width=1.1in]{halfcheetah.png}
	\end{minipage}
} 
\subfloat[Humanoid]{
	\begin{minipage}[t]{0.15\textwidth}
		\centering
		\includegraphics[width=1.1in]{humanoid.png}
	\end{minipage}
} 
\caption{The three standard MuJoCo environments.}
\label{mujoco environments}
\end{figure}

\textbf{MuJoCo.} To examine the robustness of our method in environments with Markovian reward, we conduct experiments in various tasks (Hopper (Fig. \ref{mujoco environments}(a)), Halfcheetah (Fig. \ref{mujoco environments}(b)), Humanoid (Fig. \ref{mujoco environments}(c))) from the \textit{OpenAI Gym} library \cite{brockman2016openai}.
In each task, the agent takes as input a vector
of physical states and generates a vector of action values to manipulate the robots in the environment.
We also create two multi-modal environments based on
the HalfCheetah and Ant, where we assign rewards for both Forward and Backward tasks to examine our method's effectiveness in finding high-quality
and diverse policies in Markovian reward environments.

\begin{figure} 
\centering
\includegraphics[scale=0.24]{point-v2-reward.pdf}
\caption
{The performance of different algorithms in the Point-v1 environment.}
\label{point figure}
\end{figure}
\begin{table*} 
\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}} 
\caption{The average number of times the five candidate policies for each method reach the target in the three versions of FrozenLake-v1 environments.}
\label{table1}
\setlength\tabcolsep{24pt}
\centering
\begin{tabular}{ccccc}
	\toprule

	\cmidrule(r){1-5}
	Environment  & D2PED-DQN & P3S-DQN & DvD-DQN & QD-DQN \\
	\midrule
	FrozenLake-v1 $4\times4$ (4holes)   & \textbf{2175}  & 2034  & 1874  & 1582  \\
	FrozenLake-v1 $5\times5$ (10holes)   & \textbf{1895}  & 1798  & 1603  & 1489   \\
	FrozenLake-v1 $8\times8$ (28holes)   & \textbf{1040}  & 770  & 689  & 634  \\
	\bottomrule
\end{tabular}
\end{table*}
\begin{figure*}
\subfloat[  POINT(D2PED-PPO)]{
	\begin{minipage}[t]{0.24\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.25in]{route_visualization_D2PED_.pdf}
	\end{minipage}
}
\subfloat[ POINT(DvD-PPO)]{
	\begin{minipage}[t]{0.24\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.25in]{route_visualization_DVD_.pdf}
	\end{minipage}
} 
\subfloat[ POINT(QD-PPO) ]{
	\begin{minipage}[t]{0.24\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.25in]{route_visualization_QD_.pdf}
	\end{minipage}
} 
\subfloat[ POINT(P3S-PPO) ]{
	\begin{minipage}[t]{0.24\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.25in]{route_visualization_P3S_.pdf}
	\end{minipage}
} 
\caption{Paths of five candidate policies visualization of our proposed D2PED and baselines after 500 training iterations in the Point-v1 environment.}
\label{visualization figure}
\end{figure*}

\subsubsection{Baseline Methods}
The baseline methods (or simply “baselines") adopted for comparison are the same within different environments.
We select DvD \cite{parker2020effective}, QD-RL \cite{cideron2020qd}, and P3S \cite{jung2019population} as the baselines. 
For a fair comparison, we combine our method and baselines with the same base algorithm (i.e., DQN, PPO, TD3) and use the same hyperparameters for each environment. 
The number of candidate policies $M$ of these algorithms is always set to 5. 
We report the mean and standard deviations across five identical seeds for all algorithms and all tasks. The experiments are performed using the ray \cite{moritz2018ray} library for multi-process parallel computation on a computer with 16 cores.







\subsection{Learning Diversity Policies in Non-Markovian Reward Environments}\label{exp_non}
In this experiment, we consider two environments, Point-v1 and FrozenLake-v1, with non-Markovian rewards and multi-solutions to explicitly examine whether D2PED can efficiently find high-quality policies with diverse behaviors.



\textbf{Continuous Control.} 
In the Point-v1 environment, we combine our method and baselines with PPO \cite{schulman2017proximal}.
The results are shown in Fig. \ref{point figure}.
It can be observed that DvD-PPO achieves the second-best performance but is still 20\% worse than our method. 
DvD-PPO neglects the long-horizon dependencies from the history of states and actions in non-Markovian rewards environments, leading to imperfect policy embeddings and dispersion trajectories that cannot provide effective diversity guidance in non-Markovian environments.
QD-PPO shows unstable performance and unsatisfied policy diversity, which is due to its instability in handling sparse rewards.
P3S-PPO finally gets trapped into a less-attractive local optimal. 
P3S-PPO searches policies only according to the previous best policy, which causes a rapid improvement of a particular policy but may also lead to a search in a small-range policy space.
The result implies that the D2PED-PPO can achieve better performance with much fewer training iterations, which shows the advantage of the policy dispersion scheme of the D2PED method in non-Markovian reward environments.




	
	
	


	
	
	
















To intuitively measure the diversity of different methods, we visualize the paths of five candidate policies of each method which are learned after 500 training iterations in the Point-v1 environment in Fig. \ref{visualization figure} for our method and baselines.
The lines represent the paths of five candidate policies, the orange point and the green square represent the start position and target position, respectively, and the black polylines represent the walls that separate the agent and the target. 



Overall, all policies of our method reach the target successfully in the Point-v1 environment. 
Moreover, our method manages to bypass the three walls over the upper wall, beneath the bottom wall, and through two gaps between walls, i.e., the gap between the middle wall and the upper wall and the gap between the middle wall and the bottom wall, which demonstrates the excellence of our method in learning diverse policies. 
Besides, the paths of our method from the same side are also different from each other. 

In comparison, the paths of P3S-PPO overlapped over a long period, and most policies got stuck in front of the walls, which demonstrates that P3S-PPO can not work well in the non-Markovian environment. 
For QD-PPO, only two policies can bypass the wall from the gap between the middle wall and the upper wall, and the others are stuck in front of the walls. One of the policies hit the edge of the upper wall and stumble to the target. 
DvD-PPO shows similar results.

A fraction of the candidate policies of DvD-PPO, QD-PPO, and P3S-PPO can reach the target, and these policies can only move through two gaps. 
In comparison, all of the policies of our method can reach the target from different paths, including gaps between walls and spaces over or beneath the walls, 
demonstrating that the policy dispersion scheme of our D2PED is capable of achieving better performance in learning diverse policies.








\textbf{Discrete Control.} 
We conduct experiments in $4\times4$ grids, $5\times5$ grids, and $8\times8$ grids three versions of FrozenLake-v1 environments, and we combine our method D2PED and baselines with DQN \cite{2013Playing}.
For each policy of each method, we first train 4000 episodes, then we show in Table \ref{table1} the average number of times the five candidate policies for each method reach the target in the three versions of FrozenLake-v1 environments. 
D2PED-DQN reaches the target more times than DvD-DQN, P3S-DQN, and QD-DQN in all three environments. The 
experimental results show that the policy dispersion scheme of D2PED in non-Markovian reward environments provides better exploration performance and enables agents to learn effective diversity policies. 



\begin{figure*}
\subfloat[ FROZENLAKE(D2PED-DQN)]{
	\begin{minipage}[t]{0.235\textwidth}
		\centering
		\includegraphics[width=1.75in,height=1.75in]{frozenlake_visualization_D2PED_.pdf}
	\end{minipage}
}
\subfloat[ FROZENLAKE(DvD-DQN)]{
	\begin{minipage}[t]{0.235\textwidth}
		\centering
		\includegraphics[width=1.75in,height=1.75in]{frozenlake_visualization_DvD_.pdf}
	\end{minipage}
} 
\subfloat[ FROZENLAKE(QD-DQN) ]{
	\begin{minipage}[t]{0.235\textwidth}
		\centering
		\includegraphics[width=1.75in,height=1.75in]{frozenlake_visualization_QD_.pdf}
	\end{minipage}
} 
\subfloat[ FROZENLAKE(P3S-DQN) ]{
	\begin{minipage}[t]{0.235\textwidth}
		\centering
		\includegraphics[width=1.75in,height=1.75in]{frozenlake_visualization_P3S_.pdf}
	\end{minipage}
} 
\caption{Paths of five candidate policies visualization of our proposed D2PED and baselines after 4000 training episodes in the FrozenLake-v1 environment with a $8 \times 8$ grid and $28$ holes.}
\label{visualization frozenlake}
\end{figure*}

We visualize the paths of the candidate policies of each method which are learned after 4000 training episodes in one of the FrozenLake-v1 environments (see Fig. \ref{visualization frozenlake}). 
The environment is an $8 \times 8$ grid with $28$ holes, where square S in the upper left corner and square G in the lower right corner represent the start position and target position, respectively. 
Squares marked with H represent holes, and blank squares represent ice. We use different colors of polylines to represent paths of different policies.

As shown in Fig. \ref{visualization frozenlake}, all policies of our method reach the target. 
Besides, our D2PED method learned three types of routes to reach the target, including the most tortuous route in the middle. 
P3S-DQN only learns one type of route to the target, and one of the policies falls into a hole. 
This demonstrates the P3S-DQN can only learn similar policies and can not properly handle non-Markovian rewards. 
QD-DQN also only learns one type of route to the target. 
Although QD-DQN explores the other two kinds of paths, all these policies fail to reach the target and fall into holes. 
DvD-DQN learns two types of routes to the target, and a policy still drives the agent to a hole.
Only a part of the candidate policies of DvD-PPO, QD-PPO, and P3S-PPO can reach the target, and these policies can only generate one or two types of routes, while D2PED-DQN can explore three types of routes, which demonstrates the effectiveness of the policy dispersion scheme of D2PED in learning diverse policies.




\subsection{Performance Comparison in Markovian Reward Environments}\label{exp_mar}
\textbf{Single modal.} 
To examine the robustness of D2PED in environments with Markovian reward, we conduct experiments in three standard MuJoCo environments. 
We combine our method D2PED and baselines with TD3 \cite{fujimoto2018addressing}.
The accumulated rewards versus the number of training iterations are shown in Fig. \ref{mujoco figure}.

\begin{figure*}[htbp]
\subfloat{
	\begin{minipage}[t]{0.33\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.52in]{hopper-reward.pdf}
	\end{minipage}
}
\subfloat{
	\begin{minipage}[t]{0.33\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.52in]{halfcheetah-reward.pdf}
	\end{minipage}
} 
\subfloat{
	\begin{minipage}[t]{0.33\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.52in]{humanoid-reward.pdf}
	\end{minipage}
} 
\quad
\subfloat{
	\begin{minipage}[t]{1\textwidth}
		\centering
		\includegraphics[width=3.7in]{hopper_halfcheetah_humanoid_legend.pdf}
	\end{minipage}
}
\caption{Performance of different algorithms in the three standard MuJoCo environments.}
\label{mujoco figure}
\end{figure*}
In the three environments, the convergence speed of D2PED-TD3 is faster than DvD-TD3, QD-TD3, and P3S-TD3. We can observe that D2PED-TD3 can always achieve the best final performance. 
Although P3S-TD3 can sometimes learn faster at the early stage of optimization, e.g., in the Humanoid-v2 environment, its final performance is worse than the other methods. 
The results show our method can achieve better performance than baselines in environments with Markovian rewards. 
Moreover, the results also reflect that during the training process, policy diversity learning by the policy dispersion scheme of D2PED is not achieved by sacrificing effectiveness. 








\textbf{Multi modal.} 
To examine the effectiveness of D2PED in learning diverse and high-quality policies in Markovian environments.
We change the original single-mode environments HalfCheetah and Ant into two-mode environments by assigning rewards for both Forward and Backward tasks. 
All the methods are trained in two-mode environments and tested in single-mode environments.

\begin{table*}[htbp]
\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}} 
\caption{The average reward of five candidate policies for each method in two mutli-mode environments.}
\label{multi-modal}
\setlength\tabcolsep{25pt}
\centering
\begin{tabular}{cccccc}
	\toprule

	\cmidrule(r){1-6}
	Envrionment       & Mode & D2PED-TD3       & P3S-TD3 & DvD-TD3 & QD-TD3 \\
	\midrule
	\multirow{2}{*}{HalfCheetah} &  Forward    & \textbf{5325} & 5014    & -3591   & 4897   \\
	&  Backward    & \textbf{6716} & -4452   & 6380    & 6045   \\
	\midrule
	
	\multirow{2}{*}{Ant} &  Forward    & \textbf{4740} & 4454    & 4437    & 4033   \\
	&   Backward   & \textbf{4734} & -3273   & 4090    & 4108  \\
	\bottomrule
\end{tabular}
\end{table*}

\begin{table*}
	\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}} 
	\caption{The average number of times to reach the target of D2PED equipped with different policy embedding algorithms in the three version of FrozenLake-v1 environments.}
	\label{ablation table}
	\setlength\tabcolsep{22pt}
	\centering
	\begin{tabular}{cccc}
		\toprule
	
		\cmidrule(r){1-4}
		Environment  & Policy Representation Module & Auto-Encoder & Behavior Embedding \\
		\midrule
		FrozenLake-v1 $4\times4$ (4holes)   & \textbf{2175}  & 1257  & 848   \\
		FrozenLake-v1 $5\times5$ (10holes)   & \textbf{1895}  & 808  & 653   \\
		FrozenLake-v1 $8\times8$ (28holes)   & \textbf{1040}  & 688  & 301   \\
		\bottomrule
	\end{tabular}
\end{table*}

To compare different algorithms more clearly, we organize the experimental results into Table \ref{multi-modal}. 
We observe PS3-TD3 can learn to handle Forward tasks but fails in Backward tasks of both environments. DvD-TD3 can learn to handle both tasks of the Ant environment and the Backward task of the HalfCheetah Environment. Only QD-TD3 and our method can handle both tasks in both environments, but our method can obtain larger cumulative rewards than QD-TD3, demonstrating its good performance in learning high-quality and diverse policies. This demonstrates D2PED can learn high-quality and diverse policies in Markovian reward environments.  

The experimental results of single-modal and multi-modal reflect that the performance of our method outperforms the baselines, so our method still has good performance in the Markov environment, demonstrating the strong robustness of our method.

\begin{figure*}
\subfloat{
	\begin{minipage}[t]{0.24\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.52in]{Point_ablation_study_.pdf}
	\end{minipage}
}
\subfloat{
	\begin{minipage}[t]{0.24\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.52in]{Hopper_ablation_study_.pdf}
	\end{minipage}
} 
\subfloat{
	\begin{minipage}[t]{0.24\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.52in]{Halfcheetah_ablation_study_.pdf}
	\end{minipage}
} 
\subfloat{
	\begin{minipage}[t]{0.24\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.52in]{Humanoid_ablation_study_.pdf}
	\end{minipage}
} 
\quad
\subfloat{
	\begin{minipage}[t]{1\textwidth}
		\centering
		\includegraphics[width=4.5in]{ablation_point_hopper_halfcheetah_humanoid_legend.pdf}
	\end{minipage}
} 
\caption{Performance of D2PED equipped with different policy embedding algorithms.}
\label{ablation study}
\end{figure*}

\subsection{Ablation Studies}\label{ablation study paragraph}
In this section, we conduct ablation studies to analyze the relative contribution of our policy representation module and the sensitivity of the number of candidate policies $M$.




\begin{figure*}
\subfloat{
	\begin{minipage}[t]{0.24\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.52in]{Point_change_size_.pdf}
	\end{minipage}
}
\subfloat{
	\begin{minipage}[t]{0.24\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.52in]{Hopper_change_size_.pdf}
	\end{minipage}
} 
\subfloat{
	\begin{minipage}[t]{0.24\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.52in]{Halfcheetah_change_size_.pdf}
	\end{minipage}
} 
\subfloat{
	\begin{minipage}[t]{0.24\textwidth}
		\centering
		\includegraphics[width=1.8in,height=1.52in]{Humanoid_change_size_.pdf}
	\end{minipage}
}
\quad
\subfloat{
	\begin{minipage}[t]{1\textwidth}
		\centering
		\includegraphics[width=2.8in]{change_point_hopper_halfcheetah_humanoid_legend.pdf}
	\end{minipage}
}
\caption{Performance of D2PED with different number of candidate policies $M$.}
\label{change size}
\end{figure*}

\textbf{The contribution of our policy representation module.} 
One of the crucial parts of this work is the policy representation module. 
To demonstrate the importance of our policy representation module, we replace it with two policy embedding methods: auto-encoder and behavioral embedding, respectively. 
The auto-encoder method takes the trajectories generated by $\pi_m$ as input and outputs the embedding for $\pi_m$. The behavioral embedding method is an action-based behavior characterization method. Following the implementation in \cite{parker2020effective}, we randomly select 20 states and concatenate the actions of the selected states as the policy embedding.








The experimental results of $7$ environments are shown in Fig. \ref{ablation study} and Table \ref{ablation table}. 
Using the policy embeddings generated by the auto-encoder method and the behavioral embedding method will significantly reduce the performance of D2PED. 
The behavior embedding method can not extract the mutual dependencies between states and actions, and the auto-encoder can not properly characterize the long-horizon dependencies of states and actions. 




\begin{table*}
\setlength\tabcolsep{32pt}
\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}} 
\caption{The number of times to reach the target of D2PED with different number of candidate policies $M$ in three FrozenLake-v1 environments.}
\label{change size table}
\centering
\begin{tabular}{ccccc}
	\toprule

	\cmidrule(r){1-5}
	Environment  & M = 3 & M = 5 & M = 7 & M = 9 \\
	\midrule
	FrozenLake-v1 $4\times4$ (4holes)   & \textbf{2243}  & 2175  & 2120  & 2092  \\
	FrozenLake-v1 $5\times5$ (10holes)   & 1812  & \textbf{1895}  & 1862  & 1809   \\
	FrozenLake-v1 $8\times8$ (28holes)   & 1021  & \textbf{1040}  & 1012  & 995  \\
	\bottomrule
\end{tabular}
\end{table*}

\begin{table*}
\setlength\tabcolsep{19pt}
\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}} 
\caption{Policy embedding parameter configurations for every environment.}
\label{table3}
\centering
\begin{tabular}{lccccc}
	\toprule

	\cmidrule(r){1-6}
	Hyperparameters  & \tabincell{c}{Point-v1} & \tabincell{c}{FrozenLake-v1} & \tabincell{c}{Humanoid-v2} & \tabincell{c}{HalfCheetah-v3} & \tabincell{c}{Hopper-v3} \\
	\midrule
	embedding dim     & 30  & 125   &120  &85  &40  \\
	attention heads   & 4   & 8   &8  &8  &4  \\
	learning rate     & 3e-4  & 3e-4   &3e-4  &3e-4  &3e-4  \\
	attention depth   & 4  & 6   &6  &6  &4  \\
	dropout           & 0.1  & 0.1   &0.1  &0.1  &0.1  \\
	\bottomrule
\end{tabular}
\end{table*}
\textbf{The sensitivity of the number of candidate policies.}
The number $M$ of candidate policies directly affects the number of policy embeddings used to construct the \emph{Diversity Matrix}. 
If the number of candidate policies is too small, it is less likely to find most of the optimal policies with diverse behaviors. If the number of candidate policies is too large, some policies with similar behavior will be selected
and updated, harming the efficiency of D2PED. 






Fig. \ref{change size} and Table \ref{change size table} show the performance of D2PED with different number of candidate policies. 
We report the results under the same number of iterations. It can be observed that the D2PED can achieve better performance than the baseline methods when $M$ takes $3$, $5$, and $7$, which shows our method is not quite sensitive to the policy set size.





\subsection{Hyperparameters} \label{hyperparameters paragraph}

Our method combines with different reinforcement learning methods (PPO, DQN, TD3) in the experiments. 
For all methods, Adam is used as the gradient optimizer. 
In every experiment, our method trains policy embeddings. 
The hyperparameters and details are reported below.

\textbf{Policy embedding} In Table \ref{table3} we show the hyperparameters of the policy representation module of D2PED. Three versions of FrozenLake-v1 environments use the same settings. 
Since the state dimensions of the Point-v1 environment and the Hopper environment are smaller than other environments, the embedding dimensions and attention depths of these two environments are also set to be smaller.



\textbf{D2PED-PPO}
In Table \ref{table4}, we show the hyperparameters used in PPO when combined with D2PED.
The networks for policy and critic have two hidden layers of dimension $64$. The non-linearity function of the hidden layers is tangent.   
\begin{table} 
\setlength\tabcolsep{34pt}
\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}} 
\caption{Parameter configurations for the Point-v1 environment.}
\label{table4}
\centering
\begin{tabular}{lc}
	\toprule

	\cmidrule(r){1-2}
	Hyperparameters    &  \tabincell{c}{Point-v1}     \\
	\midrule
	batch size         & 2048    \\
	minibatch size     & 256    \\
	$\lambda$          & 0.97         \\
	$\gamma$           & 0.995         \\
	learning rate      & 3e-4         \\
	\bottomrule
\end{tabular}
\end{table}

\textbf{D2PED-DQN}
In Table \ref{table5}, we show the hyperparameters used in DQN when combined with D2PED.
Three FrozenLake-v1 environments used the same settings. The network has a hidden layer of dimension 10, and the non-linearity function of the hidden layers is ReLU.
\begin{table} 
\setlength\tabcolsep{32pt}
\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}} 
\caption{Parameter configurations for three FrozenLake-v1 environments.}
\label{table5}
\centering
\begin{tabular}{lc}
	\toprule

	\cmidrule(r){1-2}
	Hyperparameters    &  \tabincell{c}{FrozenLake-v1}     \\
	\midrule
	learning rate     & 0.001    \\
	$\gamma$     & 0.9           \\
	epsilon greedy     & 0.9            \\
	batch size          & 32            \\
	\bottomrule
\end{tabular}
\end{table}
\begin{table}[!t] 
\newcommand{\tabincell}[2]{\begin{tabular}{@{}#1@{}}#2\end{tabular}} 
\caption{Parameter configurations for the three MuJoCo environments.}
\label{table6}
\centering
\begin{tabular}{lccc}
	\toprule

	\cmidrule(r){1-4}
	Hyperparameters    &  \tabincell{c}{Humanoid-v2} &  \tabincell{c}{HalfCheetah-v3} & \tabincell{c}{Hopper-v3}  \\
	\midrule
	learning rate     & 3e-4   & 3e-4  & 3e-4   \\
	$\gamma$     & 0.99   & 0.99  & 0.99    \\
	batch size     & 256  & 256   & 128     \\
	target noise   & 0.2  & 0.2   & 0.2      \\
	buffer size    & 1e6  & 1e6   & 1e6     \\
	\bottomrule
\end{tabular}
\end{table}
\textbf{D2PED-TD3}
In Table \ref{table6}, we show the hyperparameters used in TD3 when combined with D2PED.
The networks for two Q-functions and the policy have 2 hidden layers. Both the first and second layers have a dimension of 256. The non-linearity function of the hidden layers is ReLU. The last layer of the actor network has a tangent activation function, whereas the last layer of the critic networks has a linear activation function.






\section{Conclusion} \label{conclusion}
In this paper, we introduced D2PED, a method for learning effective diverse policies for control tasks in non-Markovian environments. 
D2PED designs a policy dispersion scheme that repeatedly constructs policy embeddings as the policy update progresses, forming different dispersion trajectories and maximizing the dispersion disagreements of dynamically updating trajectories.
To guarantee our idea and the proposed method, we analyze that the diversity of candidate policies could be achieved without sacrificing their effectiveness, and the subsequent experimental results of non-Markovian environments also present evidence to support this analysis. 
Moreover, the experimental results also show that D2PED  could provide more effective policy exploration and diverse behaviors than the selected baselines. 
With such achievements, we further examine the performance of D2PED in Markov environments which verifies its robustness.











\ifCLASSOPTIONcompsoc
\section*{Acknowledgments}
\else
\section*{Acknowledgment}
\fi


The authors would like to thank...


\ifCLASSOPTIONcaptionsoff
\newpage
\fi






