\section{Introduction}

Given two subsets $A,B$ of a group $G$ we denote by $AB$ the set of products $ab$ where $a \in A$, $b \in B$. A subset $A$ of $G$ is called normal if $gAg^{-1} = A$ for all $g \in G$. Clearly, a subset of $G$ is normal if and only if it is a union of conjugacy classes. Observe that if $A$ and $B$ are normal sets, then $AB=BA$.

The covering number of a nontrivial conjugacy class $C$ of a finite nonabelian simple group $G$ is the minimum positive integer $k$ such that $C^k=G$. Brenner \cite{Brenner} showed that almost all conjugacy classes of the alternating group $\Alt(n)$ have covering number at most $4$, and observed that there are classes with covering number $4$, for example the class of fixed-point-free involutions (see the penultimate paragraph of the Introduction).

Larsen and Shalev \cite[Theorem 1.13]{LarsenShalev} proved that an element $g$ of the symmetric group $\Sym(n)$ satisfies $(g^{\Sym(n)})^2=\Alt(n)$ with probability tending to $1$ as $n \to \infty$. (Here and throughout the paper $x^G$ denotes the conjugacy class of an element $x$ in a finite group $G$.) For a related result see \cite[Theorem 1.20]{LarsenShalev}. Larsen and Shalev also proved \cite[Theorem 1.14]{LarsenShalev} that if $n$ is sufficiently large, then any element $g \in \Sym(n)$ with at most $n/5$ fixed points satisfies $(g^{\Sym(n)})^4 = \Alt(n)$.

In this paper we take a different approach, considering the product of possibly distinct normal sets. Larsen, Shalev and Tiep \cite{LST} proved that if $\varepsilon > 0$ is a constant, then for sufficiently large $n$ the following holds: whenever $A,B$ are two normal subsets of $G=\Alt(n)$ of size larger than $\varepsilon |G|$, then $AB$ contains every nontrivial element of $G$, and they proved that the same holds for simple groups of Lie type of bounded rank. In this context, a subset is large if it has size at least the size of $G$ multiplied by a universal positive constant (less than $1$). Observe that using their result it is easy to see that, if $A,B,C$ are large normal subsets of $G$, then $ABC=G$. We are interested in studying largeness related to the size of $G$ raised to a constant $\gamma$.

Let $G=\Alt(n)$ be the alternating group on $n$ letters. In \cite[Theorem 1.3]{MP} it is proved that there exists $\gamma$ with $0 < \gamma < 1$ such that whenever $8$ normal subsets of $G$ have size at least $|G|^{\gamma}$, their product is $G$. It was asked if the same holds with less than $8$ normal sets. In this paper we prove that the result holds for $4$ normal sets and that if $\gamma$ is close to $1/2$, then this is best possible.

\begin{theorem} \label{main}
For any $\varepsilon > 0$ there exists $N \in \mathbb{N}$ such that whenever $n > N$ and $A,B,C,D$ are normal subsets of $G=\Alt(n)$ such that all of the numbers $|A||B|$, $|A||C|$, $|A||D|$, $|B||C|$, $|B||D|$, $|C||D|$ are at least $|G|^{1+\varepsilon}$, then $ABCD=G$.
\end{theorem}

In particular Theorem \ref{main} applies to the case in which the four normal subsets have size not less than $|G|^{1/2+\varepsilon}$, improving \cite[Theorem 1.3]{MP} in the case of alternating groups. The question of whether there exists $\gamma$ with $\gamma < 1$ such that, whenever $A,B,C$ are normal subsets of $G=\Alt(n)$ with $|A|,|B|,|C| \geq |G|^{\gamma}$, then $ABC=G$ is still open, however Theorem \ref{main} goes in this direction, since one of the four classes is allowed to be very small. If we interpret largeness in the sense of Larsen, Shalev and Tiep, then the product of any three large normal sets equals $G$, as seen above.

Theorem \ref{main} is best possible in the following sense. Let $n$ be a multiple of $4$, let $G = \Alt(n)$ and let $x$ be a fixed-point-free involution in $G$. Let $C$ be the conjugacy class of $x$ in $G$. Then, using the fact that $(n/3)^n \leq n! \leq (n/2)^n$ whenever $n \geq 6$, which can be easily deduced from Stirling's inequalities, one may see that if $n$ is sufficiently large, then $|C| = (n-1)!! = (n-1)(n-3) \cdots 3 \cdot 1 \geq (2/3)^n |G|^{1/2}$. This implies that $|C|$ is arbitrarily close to $|G|^{1/2}$ in the sense that for every $\varepsilon > 0$ there exists $N \in \mathbb{N}$ such that $|C| \geq |G|^{1/2-\varepsilon}$ for every $n \geq N$. However, as shown by Brenner in \cite[Lemma 3.06]{Brenner}, $C^3 \neq G$ and $C^4=G$. See also \cite{V}.

The paper is organized as follows. In Section \ref{delta} we introduce a useful tool by Dvir and Rodgers used to decide whether a product of two conjugacy classes of $\Sym(n)$ contains the $n$-cycles, for $n$ odd, and the $(n-1)$-cycles, for $n$ even, based on the number of disjoint cycles of an element in each class (Theorem \ref{dr}). We then relate this to our context (Lemma \ref{deltac}). In Section \ref{chsum} we recall known facts about character sums and how to apply them to products of conjugacy classes. In Section \ref{symalt} we recall how to compute character values for the symmetric and alternating groups. In Section \ref{proofmain} we finish the proof of Theorem \ref{main}.

\section{The $\delta$ of a conjugacy class} \label{delta}

Given a conjugacy class $C$ of $\Alt(n)$ or $\Sym(n)$, let $\delta(C) := n-t$, where $t$ is the number of disjoint cycles of an element of $C$. Dvir \cite{Dvir} proved a fact reformulated by Rodgers \cite[Theorem 1.1(iii)]{R}, which we will state here a particular case of. Denote the set of all $n$-cycles in $\Sym(n)$ by $O_n$, and denote the set of all $(n-1)$-cycles in $\Sym(n)$ by $O_{n-1}$. Observe that if $C$ is a conjugacy class of $\Sym(n)$ contained in $\Alt(n)$ then $\delta(C)$ is even.

\begin{theorem} \label{dr}
Let $A$, $B$ be two conjugacy classes of $\Sym(n)$ contained in $\Alt(n)$.
\begin{enumerate}
\item If $n$ is odd and $\delta(A)+\delta(B)>n-1$, then $O_n \subseteq AB$.
\item If $n$ is even and $\delta(A)+\delta(B)>n$, then $O_{n-1} \subseteq AB$.
\end{enumerate}
\end{theorem}

Using Dvir's results, Rodgers proved the following \cite[Lemma 2.2]{R}:
\begin{lemma} \label{on2an}
$O_n^2 = O_{n-1}^2 = \Alt(n)$ for every $n$.
\end{lemma}

Let $G=\Alt(n)$. In order to apply Theorem \ref{dr} in our context, we need to translate the condition $|C| \geq |G|^{\gamma}$, for a conjugacy class $C$ of $G$ and a constant $\gamma$, into a lower bound for $\delta(C)$. This is precisely what we do in the following lemma.

\begin{lemma} \label{deltac}
For every $\gamma$ and $\varepsilon$ with $0 < \gamma < 1$ and $0 < \varepsilon < 1$ there exists $N \in \mathbb{N}$ such that for every $n \geq N$, whenever $x \in G = \Alt(n)$ satisfies $|x^G| \geq |G|^{\gamma}$, then $\delta(x^G) > (\gamma-\varepsilon) n.$
\end{lemma}

\begin{proof}
Let $\gamma$ and $\varepsilon$ be arbitrary positive real numbers less than $1$. Choose $\varepsilon_1$ with $0 < \varepsilon_1 < \varepsilon/(1-\gamma+\varepsilon)$, and observe that $\varepsilon_1 < 1$. Let $x \in G = \Alt(n)$ be such that $|x^G| \geq |G|^{\gamma}$. Let $r_i$ be the number of $i$-cycles in the cycle structure of $x$ for $i=1,\ldots,t$, where $t$ is a fixed positive integer such that $$\frac{1}{2} \varepsilon_1 (1-\gamma+\varepsilon) < \frac{1}{t+1} < \varepsilon_1 (1-\gamma+\varepsilon).$$ Set $s:=\sum_{i=1}^t r_i$. The number of disjoint cycles of $x$ is at most $n/(t+1)+s$, thus $$\delta(x^G) \geq n-\frac{n}{t+1}-s > n-\varepsilon_1(1-\gamma+\varepsilon)n-s.$$ In order to prove the lemma, it is sufficient to show that $s < n (1-\varepsilon_1) (1-\gamma+\varepsilon)$ for every sufficiently large $n$.

Observe that we may assume that $s$ is not bounded above by a fixed universal constant. In particular we assume that $s > 3t$.

By plugging $x_1=\ldots=x_t=1$ into the well-known identity of multinomial coefficients $$(x_1+\cdots+x_t)^s = \sum_{k_1+\ldots+k_t = s} \frac{s!}{k_1! \cdots k_t!} \prod_{i=1}^t x_i^{k_i},$$ we obtain $s!/t^s \leq \prod_{i=1}^t r_i!$.

An easy application of Stirling's inequality gives $s! \geq (s/3)^s$. Since $\gamma > 0$ and $|x^G| \geq |G|^{\gamma}$, $x$ is not the identity and so $\prod_{i=1}^t r_i! \leq |C_G(x)| \leq |G|^{1-\gamma}$. We obtain $$(s/3t)^s \leq s!/t^s \leq \prod_{i=1}^t r_i! \leq |C_G(x)| \leq (n!/2)^{1-\gamma} < n^{n(1-\gamma)}.$$ Taking natural logarithms we obtain $s \log(s/3t) < n \left( 1-\gamma \right) \log(n)$. Since $s > 3t$, we obtain $$s < n(1-\gamma) \frac{\log(n)}{\log(s/3t)}.$$ Let $$\mathcal{A} := \{(n,s) \in \mathbb{N} \times \mathbb{N}\ :\ \exists x \in G\ :\ |x^G| \geq |G|^{\gamma}\ \mbox{and}\ s \geq n(1-\varepsilon_1)(1-\gamma+\varepsilon)\}.$$In order to prove the result, it is enough to show that $\mathcal{A}$ is finite. Assume by contradiction that $\mathcal{A}$ is infinite. Observe that, if $(n,s) \in \mathcal{A}$, then
\begin{align*}
\frac{\log(n)}{\log(s/3t)} & = \frac{\log(n)}{\log(s)-\log(3t)} \leq \frac{\log(n)}{\log(n)+\log((1-\varepsilon_1)(1-\gamma+\varepsilon))-\log(3t)}.
\end{align*}
It follows that $\log(n)/\log(s/3t)$ tends to $1$ as $(n,s) \in \mathcal{A}$ and $n$ goes to infinity, since $\varepsilon_1$, $\gamma$, $\varepsilon$ and $t$ are fixed.

Since $\frac{\varepsilon(1-\varepsilon_1)}{1-\gamma} > \frac{\varepsilon}{1-\gamma+\varepsilon} > \varepsilon_1$, there exists $\varepsilon_2$ such that $0 < \varepsilon_2 < \frac{\varepsilon(1-\varepsilon_1)}{1-\gamma}-\varepsilon_1$. If $(n,s) \in \mathcal{A}$ and $n$ is sufficiently large, we have $\log(n)/\log(s/3t) \leq 1+\varepsilon_2$, therefore
\begin{align*}
s & < n(1-\gamma)(1+\varepsilon_2) < n(1-\gamma) \left( 1+\frac{\varepsilon(1-\varepsilon_1)}{1-\gamma}-\varepsilon_1 \right) = n (1-\varepsilon_1)(1-\gamma+\varepsilon).
\end{align*}
This contradicts the fact that $(n,s) \in \mathcal{A}$.
\end{proof}

\section{Background on character sums} \label{chsum}

Let $\Irr(G)$ denote the set of irreducible complex characters of a finite group $G$.

If $A,B$ are conjugacy classes of $G$ we are interested to know which conjugacy classes the normal set $AB$ contains. Fix $a \in A$, $b \in B$, $g \in G$. Then \cite[page 43]{ASH} gives $$|\{(x,y) \in A \times B\ :\ xy=g\}| = \frac{|A||B|}{|G|} \left( \sum_{\chi \in \Irr(G)} \frac{\chi(a)\chi(b)\overline{\chi(g)}}{\chi(1)} \right).$$It follows that the conjugacy class of $g$ in $G$ is contained in the normal set $AB$ if and only if
\begin{equation} \label{cs}
\sum_{\chi \in \Irr(G)} \frac{\chi(a)\chi(b) \overline{\chi(g)}}{\chi(1)} \neq 0.
\end{equation}
Assume $G$ is the alternating group $\Alt(n)$. The strategy to show that condition (\ref{cs}) holds will often be the following: first, we separate the contribution of the trivial character in the sum, which is $1$, then we show that the remaining part tends to $0$ when $n$ tends to infinity. This implies that in this case condition (\ref{cs}) holds when $n$ is sufficiently large.

\section{Background on characters of $\Alt(n)$} \label{symalt}

In this section we review some basic facts about the characters of the alternating and symmetric groups. Everything here may be found in \cite[Chapter 2]{JamesKerber}.

A partition $\lambda = (\lambda_1,\ldots,\lambda_t)$ of $n$ is a sequence of positive integers $\lambda_1 \geq \ldots \geq \lambda_t$ such that $\lambda_1+\cdots+\lambda_t=n$. The partitions of $n$ correspond bijectively to the cycle structures of the elements of $\Sym(n)$ and to the Young diagrams of size $n$. Each partition $\lambda$ of $n$ determines uniquely a complex irreducible character $\chi_{\lambda}$ of $\Sym(n)$, and these are precisely the complex irreducible characters of $\Sym(n)$. We will use the well-known Murnaghan-Nakayama rule to compute character values, and the well-known hook length formula to compute character degrees.

We define $l$ to be $n$ if $n$ is odd and $n-1$ if $n$ is even. An $l$-hook will be a hook of length $l$. An immediate consequence of the Murnaghan-Nakayama rule is the following. Assume that $\lambda$ is a partition of $n$ and $g \in \Sym(n)$ is an $l$-cycle. If $\lambda$ contains an $l$-hook then $\chi_{\lambda}(g)=(-1)^k$ where $k$ is the leg length of the unique $l$-hook of $\lambda$. If $\lambda$ does not contain an $l$-hook, then $\chi_{\lambda}(g)=0$.

Before describing the irreducible complex characters of $\Alt(n)$ we introduce a notation. The conjugacy class of an element $g$ of $\Alt(n)$ may or may not be equal to its conjugacy class in $\Sym(n)$. If it is (resp. if it is not), we call $g$ a non-exceptional (resp. exceptional) element, the conjugacy class of $g$ a non-exceptional (resp. exceptional) class and the cycle type of $g$ a non-exceptional (resp. exceptional) cycle type. Since partitions of $n$ correspond bijectively to cycle types, we may also talk about exceptional and non-exceptional partitions. Recall that an element of $\Alt(n)$ is exceptional if and only if the lengths of the cycles in its disjoint cycle decomposition are odd and pairwise distinct (including $1$-cycles), and that the conjugacy class in $\Sym(n)$ of an exceptional element is the union of precisely two conjugacy classes of $\Alt(n)$ of equal size. An important example of an exceptional element is given by any $l$-cycle, where $l$ is defined in the previous paragraph.

The irreducible complex characters of $\Alt(n)$ are described as follows. Let $\lambda$ be a partition of $n$. Denote by $\lambda'$ the partition adjoint to $\lambda$, obtained by reflecting its Young diagram through the main diagonal. The partition $\lambda$ is said to be self-adjoint if $\lambda = \lambda'$. If $\lambda \neq \lambda'$, then the restriction of the character $\chi_{\lambda}$ to $\Alt(n)$ is an irreducible character of $\Alt(n)$, which we denote by $\psi_{\lambda}$. Clearly, $\psi_{\lambda} = \psi_{\lambda'}$ in this case. If $\lambda = \lambda'$, then the restriction of the character $\chi_{\lambda}$ to $\Alt(n)$ is the sum of two irreducible characters $\psi_{\lambda}^+$, $\psi_{\lambda}^-$ of $\Alt(n)$. Every irreducible complex character of $\Alt(n)$ is of the form $\psi_{\lambda}$ where $\lambda$ is a non-self-adjoint partition or $\psi_{\lambda}^{\pm}$ where $\lambda$ is a self-adjoint partition.

Given a self-adjoint partition $\lambda$ of $n$, denote by $h(\lambda)$ the partition whose parts are the lengths of those hooks of $\lambda$ whose heads are in the main diagonal. Observe that $h(\lambda)$ is an exceptional partition. For example, if $\lambda$ is a self-adjoint hook, then $h(\lambda)$ is the partition $(n)$.

Let $\lambda$ be a partition of $n$ and let $x \in \Alt(n)$. If $\lambda \neq \lambda'$, then $\psi_{\lambda}(x) = \chi_{\lambda}(x)$. If $\lambda = \lambda'$ and the cycle type of $x$ is not $h(\lambda)$, then $\psi_{\lambda}^{\pm}(x) = \chi_{\lambda}(x)/2$. If $\lambda = \lambda'$ and the cycle type of $x$ is $h(\lambda)$, then $x$ is an exceptional element, hence there exists $y \in \Sym(n)$ which is conjugate to $x$ in $\Sym(n)$ but not in $\Alt(n)$. Let $h^{\lambda}_{ii}$ be the length of the hook in $\lambda$ with head in position $(i,i)$. We have $$\psi_{\lambda}^{\pm}(x) = \frac{1}{2} \left( \chi_{\lambda}(x) \pm \sqrt{\chi_{\lambda}(x) \prod_{i}h^{\lambda}_{ii}} \right), \hspace{.3cm} \psi_{\lambda}^{\pm}(y) = \frac{1}{2} \left( \chi_{\lambda}(y) \mp \sqrt{\chi_{\lambda}(y) \prod_{i}h^{\lambda}_{ii}} \right).$$

An important consequence for us is the following. Let $l$ be $n$ if $n$ is odd and $n-1$ if $n$ is even and let $x$ be an $l$-cycle. Let $\lambda$ be a partition of $n$. If $\lambda$ does not contain an $l$-hook, then $\psi_{\lambda}(x) = 0$. Assume $\lambda$ contains an $l$-hook. Observe that in this case $\lambda$ contains a unique $l$-hook. If $\lambda \neq \lambda'$, then $\psi_{\lambda}(x) = \chi_{\lambda}(x) = (-1)^k$ where $k$ is the leg length of the $l$-hook contained in $\lambda$. If $\lambda = \lambda'$, then $|\psi_{\lambda}^{\pm}(x)| \leq \sqrt{n}$.

\section{Proof of Theorem \ref{main}} \label{proofmain}

In this section we prove Theorem \ref{main}. First we need a list of technical lemmas.

The following is a special case of \cite[Theorem 1.2]{LarsenShalev}.

\begin{theorem}[Larsen, Shalev] \label{ls}
If $\sigma \in \mathrm{Sym}(n)$ has at most $n^{o(1)}$ cycles of length at most $5$, then $|\chi(\sigma)| \leq \chi(1)^{1/5 + o(1)}$ for every complex irreducible character $\chi$ of $\mathrm{Sym}(n)$.
\end{theorem}

This theorem will be applied in the special case when $\sigma$ is an exceptional element in $\Sym(n)$, and $\chi=\chi_{\lambda}$, where $\lambda$ is a partition containing an $n$-hook for $n$ odd and an $(n-1)$-hook for $n$ even.

Let $l$ be $n$ if $n$ is odd and $n-1$ if $n$ is even.

\begin{lemma} \label{degalt}
Let $n \geq 9$ and let $G=\Alt(n)$. Let $\psi \in \Irr(G)$ be a nontrivial character associated to a partition $\lambda$ of $n$ containing an $l$-hook. Either $\psi(1) \geq n(n-3)/2$ or $n$ is odd, $\psi$ is equal to the restriction of $\chi_{\lambda}$ to $G$ where $\lambda=(n-1,1)$ and $\psi(1)=n-1$. Moreover if $\lambda=\lambda'$, then $\psi(1) \geq 2^{n-2}/n^2$.
\end{lemma}

\begin{proof}
Since $\psi$ is nontrivial, both $\lambda$ and $\lambda'$ are different from $(n)$. Let $\lambda=\lambda'$. The hook length formula implies $$\psi(1) = \left\{ \begin{array}{ll} \frac{1}{2} \binom{n}{n/2} \frac{(n/2-1)^2}{n-1} & \mbox{if}\ n\ \mbox{is even}, \\ & \\ \frac{1}{2} \binom{n-1}{(n-1)/2} & \mbox{if}\ n\ \mbox{is odd}. \end{array} \right.$$It follows that $\psi(1) \geq n(n-3)/2$ for $n \geq 9$. In any case $\psi(1) \geq 2^{n-2}/n^2$. Now let $\lambda \neq \lambda'$. Let $k \geq 1$ be the leg length of the unique $l$-hook contained in $\lambda$. We will use the hook length formula to compute $\psi(1)$. If $n$ is odd, then $\psi(1) = \binom{n-1}{k}$. This is either $n-1$ or at least $\binom{n-1}{2}$. Let $n$ be even. Without loss of generality, $k$ satisfies $1 \leq k \leq n/2-1$ and $$\psi(1) = d(n,k) := \binom{n}{k+1} \frac{k(n-k-2)}{n-1}.$$ We claim that $d(n,k) \geq \binom{n-1}{2}$. Observe that if $k \geq 3$ we have $k(n-k-2) \geq n-3$ whenever $n \geq 6$, hence $d(n,k) \geq d(n,1)$, and if $n \geq 8$ then $$d(n,1) \leq d(n,2) \leq d(n,3).$$ This implies that if $n \geq 8$ then, for any $k$ between $1$ and $n/2-1$, we have $d(n,k) \geq d(n,1) = n(n-3)/2$.
\end{proof}

Denote the set of all $l$-cycles in $\Sym(n)$ by $O_l$.

\begin{lemma} \label{excon}
Let $A$ and $B$ be conjugacy classes of $G=\Alt(n)$, and let $n$ be sufficiently large.
\begin{enumerate}
\item If $A$ and $B$ are exceptional classes, then $AB$ contains $O_l$.
\item If $A$ and $B$ are classes of $l$-cycles, then $AB$ contains every exceptional class.
\item If $A$ is a class of $l$-cycles, then $O_lA=G$.
\item The product of any three classes of $l$-cycles equals $G$.
\end{enumerate}
\end{lemma}

\begin{proof}
We prove part (1). Assume $A$ and $B$ are exceptional classes of $G$ and let $D$ be the conjugacy class in $G$ of an $l$-cycle. Let $x \in A$, $y \in B$, and $g \in D$. Let $\psi \in \Irr(G)$ be arbitrary, and let $\lambda$ be the partition of $n$ associated to $\psi$. Then $\psi(g) = 0$, unless the Young diagram of $\lambda$ contains an $l$-hook, by Section \ref{symalt}. Therefore, it is enough to show that (cf. Section \ref{chsum}) the rational number $$\Sigma := \sum_{\psi} \frac{\psi(x)\psi(y) \overline{\psi(g)}}{\psi(1)}$$ tends to $0$ as $n$ tends to infinity, where the sum is over the nontrivial irreducible characters of $G$ corresponding to partitions containing an $l$-hook. Let $z$ be any of $x$, $y$, or $g$. For such characters $\psi$ we have $|\psi(z)| \leq |\chi_{\lambda}(z)|$, unless $\lambda$ is self-adjoint and $z$ is an $l$-cycle. Let $\lambda$ be self-adjoint, and assume $z$ is an $l$-cycle. We have $|\psi(z)| \leq \sqrt{n}$, which is at most ${\psi(1)}^{o(1)}$ as $n \to \infty$ by Lemma \ref{degalt}. Since $x,y,g$ are exceptional elements, we obtain the following by Theorem \ref{ls} and Lemma \ref{degalt} for $n$ sufficiently large.
\begin{align*}
|\Sigma| & \leq \sum_{\psi} \Big| \frac{\psi(x) \psi(y) \overline{\psi(g)}}{\psi(1)} \Big| = \sum_{\psi} \frac{|\psi(x)| |\psi(y)| |\psi(g)|}{\psi(1)} \leq \sum_{\psi} \psi(1)^{-3/5+o(1)} \\ & \leq (n-1)^{-3/5+o(1)}+n \left( \frac{n(n-3)}{2} \right)^{-3/5+o(1)},
\end{align*}
where the sums are over the nontrivial irreducible characters $\psi$ of $G$ associated to partitions containing an $l$-hook. Therefore $|\Sigma|$ tends to $0$ as $n \to \infty$.

We prove part (2). Assume $A$, $B$ are classes of $l$-cycles and $C$ is any exceptional class. We need to show that $C \subseteq AB$. Since the conjugacy class $B^{-1}$ of the inverse of an element of $B$ is an exceptional class, $A \subseteq CB^{-1}$ by part (1). Fix $a \in A$. There exist $b \in B$, $c \in C$ such that $a = cb^{-1}$, so that $c=ab \in AB$. Since $C$ is the conjugacy class of $c$ and $AB$ is a normal set, $C \subseteq AB$ follows.

We prove part (3). Let $A$ be a class of $l$-cycles. Then, since $O_lO_l=G$ (by Lemma \ref{on2an}), $O_lA$ contains a representative of every conjugacy class of $\Sym(n)$, therefore $O_lA$ contains every non-exceptional class. On the other hand, $O_l$ contains a class of $G$ consisting of $l$-cycles, hence $O_lA$ also contains every exceptional class by part (2). It follows that $O_lA=G$.

We prove part (4). Let $A,B,C$ be classes of $l$-cycles. Then $AB$ contains $O_l$ by part (1), so $ABC=G$ by part (3).
\end{proof}

\begin{lemma} \label{onsa}
Let $A,B$ be conjugacy classes of $G=\Alt(n)$. If neither $A$ nor $B$ is contained in $O_l$ and $AB$ contains an $l$-cycle, then $AB$ contains $O_l$.
\end{lemma}

\begin{proof}
Let $x \in A$, $y \in B$. Choose two nonconjugate $l$-cycles $d_1$, $d_2$ of $G$ such that $d_1 \in AB$. We need to show that $d_2$ belongs to $AB$. Let $$a_i := \sum_{\psi \in \Irr(G)} \frac{\psi(x) \psi(y) \overline{\psi(d_i)}}{\psi(1)}.$$As explained in Section \ref{chsum}, the fact that $d_1 \in AB$ is equivalent to saying that $a_1 \neq 0$. We need to show that $a_2 \neq 0$. We will show that $a_1=a_2$.

Section \ref{symalt} implies that in the formula that defines $a_i$ the summation can be done only over those $\psi$ which are labelled by partitions containing an $l$-hook. If $\lambda$ is not a self-adjoint partition containing an $l$-hook, then there is precisely one irreducible character $\psi$ of $G$ associated to $\lambda$ and the corresponding summand is the same in $a_1$ and in $a_2$. Assume now that $\lambda=\lambda_0$ is the unique self-adjoint partition of $n$ containing an $l$-hook, so that the restriction of $\chi_{\lambda_0}$ to $G$ is a sum of two irreducible characters $\psi_{\lambda_0}^+$ and $\psi_{\lambda_0}^-$. Since $x,y,1$ are not of cycle type $h(\lambda_0)$, we have $\psi_{\lambda_0}^+(x) = \psi_{\lambda_0}^-(x)$, $\psi_{\lambda_0}^+(y) = \psi_{\lambda_0}^-(y)$ and $\psi_{\lambda_0}^+(1) = \psi_{\lambda_0}^-(1)$. It follows that $$a_1-a_2 = \frac{\psi_{\lambda_0}^+(x) \psi_{\lambda_0}^+(y)}{\psi_{\lambda_0}^+(1)} \cdot \left( \overline{\psi_{\lambda_0}^+(d_1)}+\overline{\psi_{\lambda_0}^-(d_1)}-\overline{\psi_{\lambda_0}^+(d_2)}-\overline{\psi_{\lambda_0}^-(d_2)} \right).$$The second factor equals $\overline{\chi_{\lambda_0}(d_1)-\chi_{\lambda_0}(d_2)}$, which is equal to $0$ since $d_1$ and $d_2$ are conjugate in $\Sym(n)$.
\end{proof}

\begin{lemma} \label{abon}
Let $\varepsilon > 0$. There exists $N \in \mathbb{N}$ such that the following holds for every $n \geq N$: whenever $A$ and $B$ are conjugacy classes of $G = \Alt(n)$ not contained in $O_l$ and $|A||B| \geq |G|^{1+\varepsilon}$, then $AB \supseteq O_l$.
\end{lemma}

\begin{proof}
If both $A$ and $B$ are exceptional, then the result follows from Lemma \ref{excon}(1). Assume without loss of generality that $A$ is non-exceptional. Let $B'$ be the conjugacy class of $\Sym(n)$ containing $B$. We claim that $AB' \supseteq O_l$. Write $|A|=|G|^{\gamma_1}$, $|B|=|G|^{\gamma_2}$, so that $0 < \gamma_i < 1$ for $i=1,2$ and $\gamma_1+\gamma_2 \geq 1+\varepsilon$. Lemma \ref{deltac} implies that if $n$ is large enough, then $\delta(A) > n (\gamma_1-\varepsilon/2)$ and $\delta(B) > n (\gamma_2-\varepsilon/2)$, therefore $$\delta(A)+\delta(B') = \delta(A)+\delta(B) > n(\gamma_1+\gamma_2-\varepsilon/2-\varepsilon/2) \geq n(1+\varepsilon-\varepsilon) = n,$$which implies that $AB'$ contains $O_l$ by Theorem \ref{dr}. We may assume that $B'$ properly contains $B$, that is, $B$ is an exceptional class. Since $AB'$ contains $O_l$, the normal set $AB$ contains an $l$-cycle, hence $AB$ contains $O_l$ by Lemma \ref{onsa}.
\end{proof}

\begin{lemma} \label{thcl}
Theorem \ref{main} holds in the case when $A$, $B$, $C$, $D$ are conjugacy classes.
\end{lemma}

\begin{proof}
Let $l$ be $n$ if $n$ is odd and $n-1$ if $n$ is even. If at least three of the classes $A$, $B$, $C$, $D$ consist of $l$-cycles, then the result follows from Lemma \ref{excon}(4). Therefore we may assume that $A$ and $B$ are not classes of $l$-cycles, so that $O_l \subseteq AB$ by Lemma \ref{abon}. If any of $C,D$ is a class of $l$-cycles, then the result follows from Lemma \ref{excon}(3) and if $C$ and $D$ are not classes of $l$-cycles, then the result follows from Lemma \ref{abon} and Lemma \ref{on2an}.
\end{proof}

\begin{proof}[Proof of Theorem \ref{main}]
Let $|A|=|G|^a$, $|B|=|G|^b$, $|C|=|G|^c$, $|D|=|G|^d$. For any $\gamma > 0$ there exists $N=N(\gamma) \in \mathbb{N}$ such that whenever $n > N$, any normal subset $S$ of $G$ of size at least $|G|^{\gamma}$ contains a conjugacy class of $G$ of size at least $|G|^{\gamma-\varepsilon/3}$ by \cite[Lemma 4.2]{MP}. Applying this for $n > \max \{N(a),N(b),N(c),N(d)\}$ and for $(S,\gamma) = (A,a)$, $(B,b)$, $(C,c)$, $(D,d)$ we obtain that there exist conjugacy classes $A_0$, $B_0$, $C_0$, $D_0$ of $G$ contained in $A$, $B$, $C$, $D$ respectively, such that $|A_0| \geq |G|^{a-\varepsilon/3}$, $|B_0| \geq |G|^{b-\varepsilon/3}$, $|C_0| \geq |G|^{c-\varepsilon/3}$ and $|D_0| \geq |G|^{d-\varepsilon/3}$. The hypotheses of Theorem \ref{main} hold for $A_0$, $B_0$, $C_0$, $D_0$ with the constant $\varepsilon/3$. Hence $ABCD \supseteq A_0B_0C_0D_0=G$ by Lemma \ref{thcl}.
\end{proof}


\section{Introduction}
Model-free reinforcement learning (RL) has been extensively studied and successfully implemented in different domains, notably in video games \cite{mnih2013_dqn, mnih2015_dqn}, board games \cite{silver2016_go_game, heinrich2016_poker}, robotics \cite{guholly2017_robotics, grudic2003_pg_robotics, peters2006_pg_robotics}, and continuous control tasks \cite{duan2016_continuous, lillicrap2015_ddpg, schulmanl2016_gae_continuous}.  One prominent policy based RL approach is Policy Gradient (PG) \cite{grudic2003_pg_robotics, peters2006_pg_robotics, lillicrap2015_ddpg, sutton1999_pg, williams1992_reinforce, mnih2016_a3c, silver2014_dpg}, and its basic idea is to represent the policy with a parametric probability distribution $\pi_\theta (a|s) = P [a|s; \theta]$, such that the action $a$ in state $s$ is chosen stochastically following the policy $\pi_\theta$ controlled by parameter $\theta$. However, the determination of the step size for the policy update remains challenging in order to balance the tradeoff between learning stability and learning speed.

Trust Region Policy Optimization (TRPO) \cite{schulman2015_trpo} addresses this issue by imposing a Kullback-Leibler (KL) divergence based constraint (trust region constraint) to restrict the size of the policy update. To approximately solve the trust region constrained optimization problem iteratively, a second order optimizer Conjugate Gradient \cite{hestenes1952_conjugategradient} is used to update policy parameters. This procedure is theoretically justified to guarantee a monotonic improvement of the expected reward. Another way to prevent an excessive shift between the update of the policy is to penalize the update. For example, Proximal Policy Optimization (PPO) \cite{schulman2017_ppo} penalizes on the KL divergence between the old and the new policies, and it can be efficiently solved by a first-order method like Gradient Descent. Similarly, the Behavior Guided Policy Gradient (BGPG) \cite{pacchiano2019_bgpg} considers the entrophy-regularized Wasserstein distance between the old and the new policies, and penalizes the Wasserstein distance to prevent large policy updates.

One limitation for TRPO and its variants such as PPO and BGPG is that they limit the policy representation to a particular parametric distribution class, such that
the Gaussian \cite{schulman2015_trpo, schulman2017_ppo}, Beta \cite{chou2017_beta} and Delta \cite{lillicrap2015_ddpg, silver2014_dpg} distribution functions. As indicated in \cite{tessler2019_dpo}, since parametric distributions are not convex in the distribution space, optimizing over such distributions will result in local movements in the action space and thus converge to a sub-optimal solution. To address this issue, we propose an Optimistic Distributionally Robust Optimization approach to solve the trust-region constrained optimization problem in TRPO.

Distributionally Robust Optimization (DRO) is a modeling paradigm, where the objective is to find a decision $x$ that minimizes the expected cost under the most adversarial probability
distribution, i.e., $\min_{x \in \mathcal{X}} \max_{\mathbb{P} \in \mathcal{D}} \mathbb{E}_{\mathbb{P}}[Q(x,\xi)]$, where the distribution $\mathbb{P}$ of the random parameter $\xi$ is not precisely known but assumed to belong to an ambiguity set $\mathcal{D}$. Multiple types of ambiguity set $\mathcal{D}$ have been studied recently, such as moment based confidence set \cite{delage2010_dro_moment, zymler2011_dro_moment, goh2010_dro_moment}, $\phi$ divergences based confidence set \cite{hu2012_dro_kl, bental2013_dro_phi} and Wasserstein metric based confidence set \cite{kuhn2015_dro_wasserstein, zhao2018_dro_wasserstein}. Unlike the traditional gradient-based optimization methods, DRO approach releases the assumption that the distribution $\mathbb{P}$ must fall into a particular parametric probability distribution class. Instead, it considers all distributions  that are admissible.

In this paper, we utilize Optimistic DRO approach to tackle the trust region constrained optimization problem. That is, instead of considering the most adversarial probability distribution, we aim to find the most optimistic (i.e., optimal) one to maximize the total reward function. To explore the impact of different metrics on the system performance, we consider both KL divergence and Wasserstein metric to construct the trust region. We highlight our contributions as follows:
\begin{enumerate}
    \item We develop an innovative Optimistic Distributionally Robust Policy Optimization (\texttt{ODRPO}) framework that effectively utilizes Optimistic DRO approach to address the trust region constrained optimization problem. The reformulations of  the trust region constrained optimization problem are derived and the closed-form optimal policies are obtained for both KL-divergence and Wasserstein metric cases.

    \item We show that the iterative policy updates performed by \texttt{ODRPO} are globally optimal. Also overall, it can guarantee a monotonic performance improvement through the iterations. Compared with the traditional TRPO and PPO, our proposed approach has a better sample efficiency while maintaining the learning stability.

    \item Since the policy learnt by \texttt{ODRPO} is not confined to the scope of parametric functions, this certainly opens up the possibility of converging to a better final policy. In fact, we observed significant improvements in nearly all our test cases.

    \item A comprehensive evaluation on several types of environment including tabular domains and robotic locomotion tasks shows the effectiveness of our approach. The implementation of the proposed \texttt{ODRPO} algorithm can be found at \url{https://github.com/kadysongbb/dr-trpo}.
\end{enumerate}

\section{Background}
We consider an infinite-horizon discounted Markov Decision Process (MDP), defined by the tuple $(\mathcal{S},\mathcal{A},P,r,\rho_0,\gamma)$, where $\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, $P: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \xrightarrow{} \mathbb{R}$ is the transition probability, $r: \mathcal{S} \times \mathcal{A} \xrightarrow{} \mathbb{R}$ is the reward function, $\rho_0: \mathcal{S} \xrightarrow{} \mathbb{R}$ is the distribution of the initial state $s_0$, and $\gamma$ is the discount factor. We define the return of timestep $t$ as the accumulated discounted reward from $t$, $R_t = \sum_{k=0}^{\infty} \gamma^k r(s_{t+k},a_{t+k})$, and the performance of a stochastic policy $\pi$ as $\eta(\pi) = \mathbb{E}_{s_0,a_0,s_1 \dots} [\sum_{t=0}^{\infty} \gamma^t r(s_t,a_t)]$ where $a_t \sim \pi(a_t|s_t)$, $s_{t+1} \sim P(s_{t+1}|s_t,a_t)$.

As shown in \cite{kakade2002_approximatelyoptimal}, the expected return of a new policy $\pi'$ can be expressed in terms of the advantage over the old policy $\pi$: $\eta(\pi') = \eta(\pi) + \mathbb{E}_{s\sim \rho^{\pi'}, a \sim \pi'} [A^{\pi}(s,a)]$, where $A^{\pi}(s,a) = \mathbb{E}[R_t|s_t = s, a_t = a; \pi] - \mathbb{E}[R_t|s_t = s; \pi]$ represents the advantage function and $\rho^{\pi}$ represents the unnormalized discounted visitation frequencies, i.e., $\rho^{\pi}(s) = \sum_{t=0}^{\infty}\gamma^t P(s_t = s)$.

Trust Region Policy Optimization (TRPO) \cite{schulman2015_trpo} introduces the following function $L_{\pi}(\pi')$ to approximate $\eta(\pi')$, by sampling the states with $\pi$ instead of $\pi'$:

\begin{equation}
L_{\pi}(\pi') = \eta(\pi) + \mathbb{E}_{s\sim \rho^{\pi}, a \sim \pi'} [A^{\pi}(s,a)].
\label{local_approximation}
\end{equation}

To obtain the performance bound of $\eta(\pi')$, two particular probability metrics are discussed in \cite{schulman2015_trpo}: total variation metric $d_{TV}$ and KL divergence $d_{KL}$. Let $d_{TV}^{\max}(\pi',\pi) = \max_{s} d_{TV} (\pi'(\cdot|s), \pi(\cdot|s))$ and $d_{KL}^{\max}(\pi',\pi) = \max_{s} d_{KL} (\pi'(\cdot|s), \pi(\cdot|s))$, the following performance bounds can be derived \cite{schulman2015_trpo}:
\begin{restatable}{thm}{} Let $\epsilon = \max_{s,a}|A^{\pi}(s,a)|$ and $c = \frac{4\epsilon\gamma}{(1-\gamma)^2}$, then the following bounds hold:
\begin{equation*}
\begin{split}
&\eta(\pi') \ge L_{\pi}(\pi') - c(d_{\tiny{\mbox{TV}}}^{\max}(\pi',\pi))^2, \\
&\eta(\pi') \ge L_{\pi}(\pi') - c d_{\tiny{\mbox{KL}}}^{\max}(\pi',\pi).
\end{split}
\end{equation*}
\label{trpo_theorem}
\end{restatable}
Let $M_{KL}(\pi') = L_{\pi}(\pi') - cd_{KL}^{\max}(\pi',\pi)$, which can be considered as a surrogate function to approximate $\eta(\pi')$. Maximizing $M_{KL}(\pi')$ at each iteration can guarantee a non-decreasing improvement in the expected return $\eta(\pi')$. Similarly, we can claim that $M_{TV}(\pi') = L_{\pi}(\pi') - c(d_{TV}^{\max}(\pi',\pi))^2$ is a surrogate function to approximate $\eta(\pi')$ and maximizing $M_{TV}(\pi')$ can also guarantee a monotonic performance improvement of $\eta(\pi')$.

Instead of using a penalty coefficient $c$ to control the update of the policy, TRPO uses a trust region constraint to restrict that the new policy cannot deviate from the old policy too much. In addition, in TRPO, the policy $\pi$ is parameterized as $\pi_{\theta}$ with the parameter vector $\theta$. For notation brevity, we use $\theta$ to represent the policy $\pi_{\theta}$. Then, the new policy $\theta'$ is found in each iteration to maximize \eqref{local_approximation}, or equivalently, the expected value of the advantage function:
\begin{equation}
\begin{split}
& \max_{\theta'}\ \  \mathbb{E}_{s\sim \rho^{\theta}, a \sim \theta'} [ A^{\theta} (s,a)]  \\
& \text{s.t.} \ \ \mathbb{E}_{s\sim \rho^{\theta}} [d_{M} (\theta', \theta)] \le \delta,
\end{split}
\label{trpo_problem}
\end{equation}
where $d_M$ represents a general probability metric and $\delta$ is the threshold of the distance between the new and the old policies.

\section{ODRPO: A framework to learn distributional policies}
\label{ODRPO_section_has_proofs}
In this section, we first develop the framework of the Optimistic Distributionally Robust Policy Optimization (\texttt{ODRPO}) under a general probability metric. Then we discuss the solution methodology for \texttt{ODRPO} with KL divergence and Wasserstein metric based trust regions respectively.

\subsection{Problem formulation and ODRPO framework}
\label{ODRPO_framework}
In our \texttt{ODRPO} model, we release the restrictive assumption that a policy has to follow a parametric distribution class by allowing all admissible policies, that is, the expected distance between the new and the old policies should be within a threshold $\delta$, i.e.,
\begin{equation}
\mathbb{E}_{s\sim \rho^{\pi}} [d_{M} (\pi'(\cdot|s), \pi(\cdot|s))] \le \delta.
\label{metricset}
\end{equation}
Since the optimization goal in each policy update is to obtain the maximal expected value of the advantage function, \texttt{ODRPO} focuses on identifying the optimistic policy that falls in the set depicted in \eqref{metricset}. It is completely opposite to the traditional DRO framework, which aims to find the most adversarial distribution among all admissible distributions. Therefore, the \texttt{ODRPO} framework is shown as follows:
\begin{equation}
\begin{split}
& \max_{\pi' \in \mathcal{D}} \hspace{3mm} \mathbb{E}_{s\sim \rho^{\pi}, a \sim \pi'(\cdot|s)} [ A^{\pi} (s,a)] \\
& \text{where} \hspace{3mm} \mathcal{D} = \{\pi' | \mathbb{E}_{s\sim \rho^{\pi}} [d_{M} (\pi'(\cdot|s), \pi(\cdot|s))] \le \delta \}.
\end{split}
\label{odrpo_problem}
\end{equation}
This framework is closely related to the literature on practicing optimism when facing an uncertain environment \cite{bi2005support,srinivas2009gaussian, hanasusanto2017ambiguous, nguyen2019optimistic}. To study the impact of the choice of metrics on the system performance, we explore two metrics in particular: KL divergence and Wasserstein metric. We will investigate the policy update approach for each case and compare the performance of two cases with several benchmark approaches such as TRPO, PPO, and Advantage Actor Critic (A2C) \cite{mnih2016_a2c}. Before describing our main result, we adopt a mild and conventional assumption that generally holds true in most practical cases:

\begin{assumption}
Assume $A^{\pi} (s,a)$ is bounded, i.e., $\sup_{a \in \mathcal{A}}{|A^{\pi} (s,a)|} < \infty$, $\forall s \in \mathcal{S}$.
\label{bounded_A}
\end{assumption}

\subsection{ODRPO with KL divergence based trust region}
\label{opt_policy_section1}
We first present the optimal policy for the \texttt{ODRPO} where the trust region is constructed using the KL divergence. In this formation, both the state space and the action space can be discrete or continuous. Theorems \ref{prop_dual_problem_kl} and \ref{thm_optimal_policy_kl} show the dual formulation and the optimal policy distribution of the \texttt{ODRPO} for the KL divergence case. The detailed proofs of the two theorems can be found in Appendix A.

\begin{restatable}{thm}{thmdualkl}
If Assumption \ref{bounded_A} holds, then the KL trust-region constrained optimization problem in \eqref{odrpo_problem} is equivalent to the following problem:
\begin{equation}
 \min_{\beta \ge 0} \{\beta\delta  + \mathbb{E}_{s\sim \rho^{\pi}} \beta \log \mathbb{E}_{a \sim \pi(\cdot|s)} [e^{A^\pi (s,a)/\beta}]\}.
\label{kl_trco_dual}
\end{equation}
\label{prop_dual_problem_kl}
\end{restatable}

\begin{restatable}{thm}{thmoptpolicykl}
If Assumption \ref{bounded_A} holds and $\beta^*$ is the global optimal solution to \eqref{kl_trco_dual}, then the optimal policy solution to the KL trust-region constrained optimization problem in \eqref{odrpo_problem} is:
\begin{equation}
    \pi'^*(a|s) = \frac{e^{ A^\pi (s,a)/\beta^*} \pi(a|s) }{\mathbb{E}_{a \sim \pi(\cdot|s)} [e^{ A^\pi (s,a)/\beta^*}]},  \hspace{5mm} \forall s \in \mathcal{S}, a \in \mathcal{A}.
\label{continuous_KL_optimal}
\end{equation}
\label{thm_optimal_policy_kl}
\end{restatable}
We use gradient-based global optimization algorithms \cite{wales1998_basin_hopping, zhan2006_monte_carlo_basin, leary2000_global_optimization} to find the global optimal $\beta^*$ in \eqref{kl_trco_dual}.
The gradient of the objective in \eqref{kl_trco_dual} is derived as below:
\begin{equation*}
\begin{split}
    \frac{\partial l_0}{\partial \beta} = \delta + \mathbb{E}_{s \sim \rho^\pi}\{ \log \mathbb{E}_{a \sim \pi(\cdot|s)} [e^{A^\pi (s,a)/\beta}] - \frac{ \mathbb{E}_{a \sim \pi(\cdot|s)} [e^{A^\pi (s,a)/\beta} \times A^\pi (s,a)]}{\beta \mathbb{E}_{a \sim \pi(\cdot|s)} [e^{A^\pi (s,a)/\beta}]}   \}.
\end{split}
\end{equation*}
In implementation, we obtain the global optimal $\beta^*$ using the Basin Hopping algorithm \cite{wales1998_basin_hopping}, which is a two-phase global optimization method that utilizes the gradient information to speed up the search in the local phase.

\subsection{ODRPO with Wasserstein metric based trust region}
\label{opt_policy_section2}

In this subsection, we show that the Wasserstein metric based trust region can also guarantee a monotonic improvement given that the action space is finitely discrete, and derive the optimal policy for the \texttt{ODRPO} where the trust region is constructed using the Wasserstein metric.

Given two probability distributions $\mu$ and $v$ on the supporting space, the Wasserstein metric is defined as:
\begin{equation*}
d_W(\mu,v) = \inf_\Pi \mathbb{E}_\Pi{[d(X,Y)]},
\end{equation*}
where $d(X,Y)$ is a distance between random variables $X$ and $Y$, $X \sim \mu$, $Y \sim v$, and the infimum is taken over all joint distributions $\Pi$ with marginals $\mu$ and $v$.

When the action space is finitely discrete, we have the following relationship between the total variation metric and the Wasserstein metric:  $d_{\min} d_{TV} (\pi'(\cdot|s),\pi(\cdot,s)) \le d_{W}(\pi'(\cdot|s),\pi(\cdot,s))$ where $d_{\min} = \min_{a \ne a' \in \mathcal{A}}d(a, a')$ \cite{gibbs2002choosing}. Based on this relationship and Theorem \ref{trpo_theorem}, we obtain the following corollary.

\begin{corollary}
When the action space is finite discrete, let $c_1 =  \frac{c}{d^2{\min}}$ and $d_{W}^{\max}(\pi',\pi) = \max_{s} d_{W} (\pi'(\cdot|s), \pi(\cdot|s))$, then we have:
\begin{equation*}
    \eta(\pi') \ge L_{\pi}(\pi') - c_1 (d_{W}^{\max}(\pi',\pi))^2.
\end{equation*}
\label{cor_wass_can_be_used}
\end{corollary}
Let $M_{W}(\pi') = L_{\pi}(\pi') - c_1 (d_{W}^{\max}(\pi',\pi))^2$. From Corollary \ref{cor_wass_can_be_used} we can see that $M_{W}(\pi')$ is a surrogate function that approximates $\eta(\pi')$. Since $M_{W}(\pi) = \eta(\pi)$ and $M_{W}(\pi') \le \eta(\pi')$, $\forall \pi' \neq \pi$, maximizing this surrogate function at each iteration can guarantee a non-decreasing improvement in the true objective function.

We consider a general state space, and a finite action space with $N$ actions $a_1, a_2 \dots a_N$. The distribution function of policy $\pi$ is represented as $P^{s}_{i} = \pi(a_i|s)$, $\forall s \in \mathcal{S}, i = 1\dots N$. The following two theorems show the dual formulation and the optimal policy distribution of the \texttt{ODRPO} for the Wasserstein metric case (see Appendix A for detailed proofs).

\begin{restatable}{thm}{thmdualwass}
If Assumption \ref{bounded_A} holds, then the Wasserstein trust-region constrained optimization problem in \eqref{odrpo_problem} is equivalent to the following problem:
\begin{equation}
\min_{\beta \ge 0} \{\beta\delta + \mathbb{E}_{s \sim \rho^{\pi}} \sum_{i=1}^N P^s_{i}(A^{\pi} (s,a_{j^*_{s,i,\beta}}) -  \beta d(a_{j^*_{s,i,\beta}}, a_i)) \},
\label{wass_trco_dual}
\end{equation}
where $j^*_{s,i, \beta} = \text{argmax}_{j = 1\dots N} ( A^{\pi} (s,a_j) -  \beta d(a_j, a_i) )$.
\label{prop_dual_problem_wass}
\end{restatable}

\begin{restatable}{thm}{thmoptpolicywass}
If Assumption \ref{bounded_A} holds and $\beta^*$ is the global optimal solution to \eqref{wass_trco_dual}, then the optimal policy solution to the Wasserstein trust-region constrained optimization problem in \eqref{odrpo_problem} is:
\begin{equation}
\pi'^*(a_j|s) = \sum_{i=1}^N P^s_{i} Q^{s*}_{ij},
\label{discrete_wass_optimal}
\end{equation}
where $Q^{s*}_{ij} = 1$ if $j = j^*_{s,i,\beta^*}$ and $Q^{s*}_{ij} = 0$ otherwise.
\label{thm_optimal_policy_wass}
\end{restatable}

For the Wasserstein metric case, we are not able to obtain the closed-form gradient of the objective in \eqref{wass_trco_dual}, in search of the global optimal $\beta^*$. However, if an initial point $\beta_0$ is given, the closed-form expression of the local optimal solution can still be obtained. We define the distance $d(x,y) = 0$ if $x = y$ and $1$ otherwise, and $k_s = \text{argmax}_{i = 1 \dots N} A^{\pi} (s, a_i)$. Then, we have the following proposition to show the optimal value of $\beta$ regarding different initial points:

\begin{restatable}{prop}{propoptimalbeta}
\label{prop_optimal_beta_wass}

(1). If the initial point $\beta_0$ is in $[\max_{s, i} \{A^{\pi}(s,a_{k_s}) - A^{\pi} (s,a_i) \}, +\infty)$, the optimal $\beta$ solution is $\max_{s, i} \{A^{\pi}(s,a_{k_s}) - A^{\pi} (s,a_i) \}$.
\\
(2). If the initial point $\beta_0$ is in $[0, \min_{s, i \ne k_s} \{A^{\pi}(s,a_{k_s}) - A^{\pi} (s,a_i) \}]$: if $\delta - \int_{s\in \mathcal{S}} \rho^{\pi} (s)  (1 -  P^{s}_{k_s}) ds < 0$, the optimal $\beta$ is $\min_{s, i \ne k_s} \{A^{\pi}(s,a_{k_s}) - A^{\pi} (s,a_i) \}$; otherwise, the optimal $\beta$ solution is $0$.

(3). If the initial point $\beta_0$ is in $(\min_{s, i \ne k_s} \{A^{\pi}(s,a_{k_s}) - A^{\pi} (s,a_i) \}, \max_{s, i} \{A^{\pi}(s,a_{k_s}) - A^{\pi} (s,a_i) \})$, we construct sets $I_s^1$ and $I_s^2$ as:
$\textbf{\textup{for}} \hspace{1mm} s \in \mathcal{S}, i \in \{1,2\dots N\} \hspace{1mm}: \hspace{1mm} \textbf{\textup{if}} \hspace{1mm} \beta_0 \ge A^{\pi}(s,a_{k_s}) - A^{\pi} (s,a_i) \hspace{1mm} \textbf{\textup{then}} \hspace{1mm} \textup{\text{Add}}\hspace{1mm} i \hspace{1mm} \textup{\text{to}} \hspace{1mm} I_s^1 \hspace{1mm} \textbf{\textup{else}} \hspace{1mm} \textup{\text{Add}} \hspace{1mm} i \hspace{1mm} \textup{\text{to}} \hspace{1mm} I_s^2$. Then, if $\delta - \mathbb{E}_{s \sim \rho^{\pi}}\sum_{i \in I_s^2} P^s_{i} < 0$, the optimal $\beta$ is $\min_{s \in \mathcal{S}, i \in I_s^2} \{ A^{\pi}(s,a_{k_s}) - A^{\pi} (s,a_i) \}$; otherwise, the optimal $\beta$ is $\max_{s \in \mathcal{S}, i \in I_s^1} \{A^{\pi}(s,a_{k_s}) - A^{\pi} (s,a_i)\}$. \end{restatable}

Based on Proposition \ref{prop_optimal_beta_wass}, we can use a two-phase global optimization method \cite{schoen2002_twophase} to find the global optimal solution $\beta^*$.

\section{ODRPO algorithm and discussion}
\label{drtrpo_alg_sec}

In this section, we first propose our \texttt{ODRPO} algorithm based on the previous results. Then we highlight the major advantages of the proposed \texttt{ODRPO} algorithm as compared to the original TRPO algorithm.

\subsection{ODRPO algorithm}
Let $\pi_{k+1} = \mathbb{F} (\pi_k)$ denotes the policy update in \eqref{continuous_KL_optimal} if the KL divergence is used to construct the trust region, and let $\pi_{k+1} = \mathbb{G} (\pi_k)$ denotes the policy update in \eqref{discrete_wass_optimal} if the Wasserstein metric is used. Based on Theorems \ref{thm_optimal_policy_kl} and \ref{thm_optimal_policy_wass}, we develop the following \texttt{ODRPO} algorithm:

\begin{algorithm}[H]
\SetAlgoLined
Input: number of iterations $K$, learning rate $\alpha$ \\
Initialize policy $\pi_0$ and value network $V_{\psi_0}$ with random parameter $\psi_0$\\
 \For{$k = 0,1,2 \dots K$}{
  Collect a set of trajectories $\mathcal{D}_k$ on policy $\pi_k$
  \\
  For each timestep $t$ in each trajectory, compute total returns $G_t$ \\
  \hspace{3mm} and estimate advantages $\hat{A}_t^{\pi_k}$
  \\
  Update value: \\
  \hspace{2cm} $\begin{aligned} \psi_{k+1} \xleftarrow[]{} \psi_{k} - \alpha \nabla_{\psi_{k}} \sum (G_t - V_{\psi_k}(s_t))^2 \end{aligned}$
  \\
  Update policy: \\
  \hspace{2cm} $\pi_{k+1} \xleftarrow[]{} \mathbb{F} (\pi_k)$ \\
  \hspace{1.5cm} \text{or} \hspace{0.5mm} $\pi_{k+1} \xleftarrow[]{} \mathbb{G} (\pi_k)$
 }
 \caption{\texttt{ODRPO} Algorithm}
 \label{odrpo_algorithm}
\end{algorithm}

The trajectories sampled in the algorithm can either be complete or partial. If the trajectory is complete, we obtain the total return by using the accumulated discounted rewards $G_t  = \sum_{k=0}^{T-t-1} \gamma^k r_{t+k}$. If the trajectory is partial, we estimate the total return by using the multi-step temporal difference (TD) methods \cite{asis2017_multistep}: $\hat{G}_{t:t+n} = \sum_{k=0}^{n-1} \gamma^k r_{t+k} + \gamma^n V(s_{t+n})$. In the advantage estimation step, we can use the Monte Carlo advantage estimation, i.e., $\hat{A}_t^{\pi_k}=G_t - V_{\psi_k}(s_t)$ or alternative advantage estimation methods such as Generalized Advantage Estimation (GAE) \cite{schulmanl2016_gae_continuous}, which provides an explicit control over the bias-variance trade-off.

\subsection{Same stability, better sample efficiency and better performance}

The original TRPO approximately solves the trust-region constraint optimization problem in \eqref{trpo_problem} by using the conjugate gradient algorithm, after making a linear approximation to the objective and a quadratic approximation to the constraint. These approximations will not prevent the method from performing large steps of policy update that violate the KL constraint, and therefore cause the degradation of the system performance. To overcome it, TRPO adds a line search which can reject the update that either violates the KL constraint or decreases the objective of the surrogate function. However, due to the approximations, the new policy accepted by the line search may not be the optimal policy within the trust region. Another factor that may lead TRPO to perform sub-optimal policy updates and converge to a sub-optimal final policy is that in TRPO, the policy is assumed to belong to a particular parametric distribution class (i.e., $\pi(a|s) = P [a|s; \theta]$) \cite{tessler2019_dpo}. Since the optimal policy does not necessarily belong to this particular distribution class, it may be excluded when TRPO performs policy updates.

The proposed \texttt{ODRPO} algorithm overcomes the above limitations by utilizing DRO. At each iteration of the \texttt{ODRPO} policy update, we use DRO to exactly solve the trust-region constraint optimization problem in \eqref{odrpo_problem}, without making any approximation. Also, in DRO, we consider all admissible policies (i.e., distributional policies within the trust region). Therefore the new policy is always the one that maximizes the surrogate objective within the trust region centered on the old policy. Thus, the trust-region constraint is satisfied in each update and the globally optimal policy update can be obtained in each iteration.

To conclude, \texttt{ODRPO} has the following advantages as compared with TRPO:
\begin{itemize}
    \item \texttt{ODRPO} maintains the stability of TRPO since the trust region constraint is always satisfied.
    \item \texttt{ODRPO} has a better sample efficiency since it performs updates more often (accepts all updates), and in each update, the policy obtained by \texttt{ODRPO} is globally optimal within the trust region.
    \item \texttt{ODRPO} converges to a better final policy since \texttt{ODRPO} learns distributional policies while TRPO limits policies to a particular parametric distribution class.
\end{itemize}

\section{Experiments}
\label{experiment_section}
In this section, we conduct an experimental evaluation of \texttt{ODRPO} on tabular domains and robotic locomotion tasks. We use \texttt{ODRPO-KL} to denote the \texttt{ODRPO} algorithm with KL divergence and \texttt{ODRPO-Wass} to denote the \texttt{ODRPO} algorithm with Wasserstein metric. We compare the performance of our proposed method with several benchmarks, including TRPO \cite{schulman2015_trpo}, PPO \cite{schulman2017_ppo} and A2C \cite{mnih2016_a2c} \footnote{We use the implementations of TRPO, PPO and A2C from OpenAI Baselines \cite{openaibaseline} for MuJuCo tasks and Stable Baselines \cite{stable-baselines} for other tasks. }
. We consider comparing with A2C because it is similar to our \texttt{ODRPO} algorithm in the sense that both of them are simple on-policy actor-critic methods that utilize the advantage information to perform policy updates.
\subsection{Tabular domains}
We evaluate \texttt{ODRPO} on a set of tasks including Taxi \cite{dietterich1998_taxi}, Chain \cite{richard1998_chain} and Cliff Walking \cite{sutton2018_cliff_walking}, which are intentionally designed to test the exploration ability of the algorithms. The tabular domain has a special environment structure with a discrete state space and a discrete action space. Thus, we use an array of size $|\mathcal{S}| \times |\mathcal{A}|$ to represent the policy $\pi(a|s)$. For the value function, we use a neural net to smoothly update the values. The performance of \texttt{ODRPO} is compared to the performance of TRPO, PPO and A2C with the same neural net structure. Each algorithm is evaluated $5$ times with a random initialization.

As shown in Figure \ref{fig:tabular}, the performance of \texttt{ODRPO} and TRPO is manifestly better than the first-order optimization methods A2C and PPO. Between the trust region based methods, \texttt{ODRPO} outperforms TRPO in most tasks, except in Chain, where the performance of these two methods are not significantly different. In Cliff Walking, \texttt{ODRPO} converges to the optimum much faster than TRPO. In Taxi, \texttt{ODRPO} converges to a better optimum compared to TRPO. We further analyze the performance of the trained agent for each algorithm on the Taxi environment. As shown in Table \ref{taxi_table}, \texttt{ODRPO} has a higher successful drop-off rate and a lower task completion time while the original TRPO reaches the time limit with a drop-off rate $0$. Therefore, the results in Taxi show that \texttt{ODRPO} finds a better policy than the original TRPO. Among the variants of \texttt{ODRPO}, the relative strength of \texttt{ODRPO-KL} and \texttt{ODRPO-Wass} on convergence rate and solution quality is highly task dependent. However, a general pattern across tasks shows that \texttt{ODRPO-KL} converges faster and attains a slightly better optimum than \texttt{ODRPO-Wass} in the tabular domains.

\begin{table}[H]
\renewcommand{\arraystretch}{1.2}
\centering
\caption{Trained agents performance on Taxi (averaged over $1000$ episodes)}
\begin{adjustbox}{width=0.9\columnwidth,center}
\begin{tabular}{lllll}
 \hline
 & Successful Dropoff (+20) & Illegal Pickup/ Dropoff (-10) &  Timesteps (-1) & Average Return \\
 \hline
 \texttt{ODRPO-KL} & 0.995 & 0.732 & 18.556 & -5.976 \\
 \hline
 \texttt{ODRPO-Wass} & 0.753  & 0.232 & 70.891 & -58.151  \\
 \hline
 TRPO & 0 & 0 & 200 & -200   \\
 \hline
\end{tabular}
\label{taxi_table}
\end{adjustbox}
\end{table}

\begin{figure}[H]
\centering
\begin{minipage}{.3\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{taxi.png}
\end{minipage}
\begin{minipage}{.3\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{cliff.png}
\end{minipage}
\begin{minipage}{.3\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{chain.png}
\end{minipage}
\caption{Episode rewards during the training process for the tabular domain tasks, averaged across $5$ runs with a random initialization. The shaded area depicts the mean $\pm$ the standard deviation.}
\label{fig:tabular}
\end{figure}

\subsection{Robotic locomotion tasks}
We then integrate deep neural network architecture into the \texttt{ODRPO} framework and evaluate its performance on several locomotion tasks, including CartPole \cite{barto1983_carpole}, Acrobot \cite{geramifard2015_acrobot}, Lunar Lander \cite{brockman2016_openai_gym} and MuJuCo control suite \cite{todorov2012_mujuco}. For the experiments with a discrete action space, we use two separate neural nets to represent the policy and the value. The policy neural net receives state $s$ as an input and outputs the categorical distribution of $\pi(a|s)$. For the experiments with a continuous action space, we use the generative actor critic network in \cite{tessler2019_dpo} with the target distribution defined by $\pi_{k+1} = \mathbb{F} (\pi_k)$. The performance of \texttt{ODRPO} is compared to the performance of TRPO, PPO and A2C with the same neural net structure. Each algorithm is run $5$ times with a random initialization.

\begin{wraptable}{r}{0.45\textwidth}
\caption{Timesteps to hit threshold ($\times 10^4$)}
\renewcommand{\arraystretch}{1.1}
\centering
\begin{adjustbox}{width=\linewidth,center}
\begin{tabular}{lllll}
 \hline
 & Threshold & \texttt{ODRPO}  & TRPO & PPO \\
 \hline
CartPole & 200 & 0.8 & 0.7 & 2.3  \\
Acrobot & -150 & 5.1 & 15.0 & 2.0  \\
LunarLander & 50 & 10 & 18 &  8 \\
Walker & 3000 & 45 & 112 & 52  \\
Hopper & 3000 & 64 & 115 & 127  \\
Reacher & -10 & 2 & 13 & 20  \\
 \hline
\end{tabular}
\label{locomotion_efficiency_table}
\end{adjustbox}
\end{wraptable}

\textbf{Sample efficiency: }
Table \ref{locomotion_efficiency_table} lists the timesteps required by \texttt{ODRPO}, TRPO and PPO to hit a predefined threshold. As seen in Table \ref{locomotion_efficiency_table}, in most cases, \texttt{ODRPO} reduces the number of timesteps by at least half as compared with TRPO. Also \texttt{ODRPO} requires less timesteps than PPO in most tasks.

\textbf{Final performance/quality: }
Figure \ref{fig:locomotion_control} shows the episode rewards during the training process and Table \ref{locomotion_performance_table} shows the performance improvement of the best among two \texttt{ODRPO} methods compared to the best among the baseline algorithms: TRPO, PPO, and A2C. As seen in Figure \ref{fig:locomotion_control}, \texttt{ODRPO} outperforms TRPO, PPO and A2C in most tasks in terms of the final performance. As shown in Table \ref{locomotion_performance_table}, \texttt{ODRPO} achieves $+75\%$ better performance in average compared to the best of TRPO, PPO and A2C.

\begin{table}[H]
\footnotesize
\renewcommand{\arraystretch}{1.25}
\caption{\texttt{ODRPO} best performance compared to the baseline best performance}
\begin{adjustbox}{width=\columnwidth,center}
\centering
\begin{tabular}{lllllllll}
 \hline
  CartPole  & Acrobot  & LularLander & Walker & Hopper & Reacher & Ant & HalfCheetah & InvertedPendulum \\
 \hline
  $+94$  & $-12$ & $+77$ &  $+507$ & $+68$  & $+1$ & $+3647$ & $+6330$ & $+11$\\
  $(+30\%)$ & $(-14\%)$ &  $(+82\%)$ & $(+16\%)$ & $(+3\%)$ & $(+13\%)$ & $(+208\%)$ & $(+343\%)$ & $(+1\%)$\\
 \hline
\end{tabular}
\label{locomotion_performance_table}
\end{adjustbox}
\end{table}

\textbf{Training time: }
To train $10^5$ timesteps in the discrete locomotion tasks, the training wall-clock time is around 63s for \texttt{ODRPO}, 59s for TRPO and 70s for PPO. Therefore, \texttt{ODRPO} has a similar computational efficiency as TRPO and PPO.

Among variants of \texttt{ODRPO}, \texttt{ODRPO-KL} converges faster than \texttt{ODRPO-Wass}. This is coherent with the convergence property discussed in \cite{hu2012_dro_kl} and \cite{kuhn2015_dro_wasserstein} that the radii of Wasserstein uncertainty set decays polynomially with a larger number of samples while the radii of KL uncertainty set decays exponentially. As a result, \texttt{ODRPO-KL} has a smaller uncertainty set than \texttt{ODRPO-Wass}, and thus converges faster.

\begin{figure}[H]
\centering
\begin{minipage}{.245\textwidth}
  \centering
  \includegraphics[width=\linewidth]{cartpole_eps.png}
\end{minipage}
\begin{minipage}{.245\textwidth}
  \centering
  \includegraphics[width=\linewidth]{acrobot_eps.png}
\end{minipage}
\begin{minipage}{.245\textwidth}
  \centering
  \includegraphics[width=\linewidth]{cartpole_time.png}
\end{minipage}
\begin{minipage}{.245\textwidth}
  \centering
  \includegraphics[width=\linewidth]{acrobot_time.png}
\end{minipage}
\begin{minipage}{.245\textwidth}
  \centering
  \includegraphics[width=\linewidth]{lunar.png}
\end{minipage}
\begin{minipage}{.245\textwidth}
  \centering
  \includegraphics[width= \linewidth]{walker.png}
\end{minipage}
\begin{minipage}{.245\textwidth}
  \centering
  \includegraphics[width= \linewidth]{hopper.png}
\end{minipage}
\begin{minipage}{.245\textwidth}
  \centering
  \includegraphics[width= \linewidth]{reacher.png}
\end{minipage}
\caption{Episode rewards during the training process for the locomotion tasks, averaged across $5$ runs with a random initialization. The shaded area depicts the mean $\pm$ the standard deviation.}
\label{fig:locomotion_control}
\end{figure}

\section{Discussion and future work}
In this paper, we present a novel RL algorithm, Optimistic Distributionally Robust Policy Optimization (\texttt{ODRPO}), which addresses the sub-optimality issue of trust region based methods such like TRPO and PPO. Our \texttt{ODRPO} method improves TRPO and PPO with better sample efficiency and better final performance, while maintaining the stable learning property.

To our knowledge, our \texttt{ODRPO} method is the first trust region based policy optimization method that learns distributional policies. We believe that this work can be a principal alternative to the trust region based PG methods. \texttt{ODRPO} is a theoretically grounded method, but at the same time, it is a simple on-policy actor-critic algorithm. Therefore, we will focus on integrating \texttt{ODRPO} with other well-known off-policy frameworks, such as Soft Actor Critic \cite{haarnoja2018_sac} and Twin Delayed DDPG \cite{fujimoto2018_td3} as our future work.

\newpage
\section{Broader impact}
By employing the probabilistic model-free conception into the reinforcement learning domain, we open the opportunities for researchers and practitioners to achieve better learning outcomes. The reason is three-fold.
First of all, by replacing untrustworthy probabilistic assumptions with a confidence set that covers all permissible distributions, a potentially better result is theoretically guaranteed. Second, by avoiding having to resort to heuristics, each step can be solved to its optimality using a rigorous optimization approach. Third, it greatly reduces the effort of tackling nonconvexity constraints introduced by parametric policy assumptions, which is oftentimes the major computational obstacles in solving the subroutine of the model-free reinforcement learning framework.

\small
\bibliographystyle{unsrt}