\section{Introduction}

In this paper we consider the fundamental problem of computing an approximately optimal policy in a Markov decision process (MDP) given by a generative model. We consider a standard MDP model with a known set of states and actions. If an agent chooses an action at a given state, a known reward is immediately given to the agent and the agent probabilistically transitions to a new state by an (unknown) fixed distribution (as a function of the state-action pair). Given access to a \emph{generative model}~\citep{K03}, i.e. an oracle which when queried by a state-action pair returns an independent sample from the distribution over next states, our goal is to find a policy, i.e. a choice of action per state, that approximately maximizes a measure of (cumulative) reward over time, e.g.  discounted reward, average reward, etc.

Solving MDPs with a generative model is a fundamental problem in learning theory and a classic model for decision making under uncertainty and reinforcement learning~\citep{puterman2014markov,sutton2018reinforcement}. It is a prominent theoretical test-bed for learning algorithms and has been studied extensively over past 20 years~\citep{K03}. Multiple algorithms have been proposed for the problem~\citep{puterman2014markov} and there has been extensive research on improving the sample complexity for finding an approximately optimal policy~\citep{W17d, SWWYY18, W19, agarwal2019optimality}.

In certain settings, the sample complexity of the problem is settled. For example, consider discounted  MDPs (DMDPs) where the goal is to minimize the $\gamma$-discounted reward, i.e. the sum of the rewards where the reward at step $t\ge 0$ is discounted by $\gamma^t\in[0,1)$. For a DMDP with $\mathrm{A_{tot}}$ total state-action pairs, it is known that $\widetilde{\Omega}(\mathrm{A_{tot}}/(1-\gamma)^3\epsilon^2)$~\footnote{Many results in literature instead consider MDPs where at each state there are a fixed $A$ actions and use $|\calS|A$ to denote the total number of state-action pair in their result. These results typically generalize to non-uniform action set among states, and thus we replace this total number of state-action pair with $\mathrm{A_{tot}}$ throughout.} samples are necessary to find an $\epsilon$-optimal policy~\cite{azar2013minimax,feng2019does} and there are algorithms which solve the problem with near-optimal $\widetilde{O}(\mathrm{A_{tot}}/(1-\gamma)^3\epsilon^2)$ samples~\cite{SWWYY18,agarwal2019optimality,li2020breaking} for certain ranges of $\epsilon$. Similarly, in the case of finite-horizon MDPs, again optimal sample and query complexities are known~\cite{SWWYY18} for sufficiently small $\epsilon$.

Another popular class of MDPs are infinite-horizon average-reward MDPs~(AMDPs)~\cite{mahadevan1996average}. Here the reward function (also known as the \emph{gain} for AMDPs) is the infinite-horizon average reward and it is assumed that for any given policy the transition matrix it induces has a mixing time bounded by $t_{\mathrm{mix}} > 0$. AMDPs arise naturally in controlling computer systems and communication networks, where a controller makes frequent decisions, and for inventory systems with frequent restocking decisions~\cite{puterman2014markov}.  However, despite advancements in the theory of DMDPs and multiple proposed algorithms~\cite{W17m,jin2020efficiently}, the optimal sample complexity of AMDPs has resisted similar characterization.The best known sample complexity is $\widetilde{O}(\At_{\mathrm{mix}}^2/\epsilon^2)$ \cite{jin2020efficiently} and there is no known lower-bound.

In comparison to existing near-optimal DMDP methods for  generative models~\citep{K03}, recent methods for provably solving AMDPs suffer from two additional limitations.%
~First, they work with randomized policies, i.e. ones which choose a distribution over actions in every state. Correspondingly, these methods require stronger condition of mixing bound on all randomized policies.%
 Second, they use dynamic samples from the model, as opposed to the case for DMDPs where the sampling process can be completely oblivious, i.e. a fixed number of samples can be generated per state-action pair.

In this paper we make progress on these problems. First we provide a new method that finds an $\epsilon$-optimal deterministic stationary policy using $\widetilde{O}(\At_{\mathrm{mix}}/\epsilon^3)$ oblivious samples, thereby overcoming these limitations of previous methods. Further, we provide a lower bound showing that $\Omega(\At_{\mathrm{mix}}/\epsilon^2)$ oblivious samples are necessary. Consequently, we resolves the question of optimal dependence on $t_{\mathrm{mix}}$ for oblivious sampling methods. We achieve these results by establishing a connection between infinite-horizon average-reward MDPs and discounted MDPs which may be of utility for further research in this area.

\subsection{Problem Setup}\label{sec:intro-setup}

We define a Markov decision process (MDP) as a tuple $\calM\coloneqq (\calS,\calA,\PP,\rr)$ with the following interpretations:
\begin{itemize}
\item 	state space $\calS$ - a finite discrete set of states with size $|\calS|$
that the process transits on. In particular, $s\in\calS$ denotes a single state.
\item  total action space $\calA$ - the union of all actions that an agent can take at any state $s\in \calS$, i.e. $\calA = \cup_{s\in\calS} \calA_s$, where $\calA_s$ is the action space at state $s$ (and the $\calA_s$ are disjoint). We denote the total number of state-action pairs as $\mathrm{A_{tot}} = \sum_{s\in\calS}|\calA_s|$.
\item transition probability matrix  $\PP\in\R^{\calA\times \calS}$ - When choosing action $a_s \in \calA_s$ at state $s \in \calS$ the next state is chosen from the distribution $\mathbf{p}_{s,a_s} = \PP((s,a_s),\cdot)\in\Delta^{\calS}$.  We assume that $\PP$ is unknown but can be queried by a \emph{generative model} which when queried at any state action pair $(s,a_s)$ outputs an independent sample from the distribution $\mathbf{p}_{s,a_s}$.
\item reward vector $\rr\in [0,1]^{\calA}$ - the reward at any state $s$ when playing action $a_s$ is denoted as $r_{s,a_s}$. As is common practice we assume the reward doesn't depend on the state it transits to~\citep{SWWYY18}, and is bounded in $[0,1]$ (by uniform rescaling).
\end{itemize}
Given MDP $\calM$ at any state $s\in\calS$ an agent can take action $a_s\in\calA_s$ after which it receives instant reward $r_{s,a_s}$ and transits to some other state $s'$ with probability $\mathbf{p}_{s,a_s}(s')$. A \emph{(deterministic stationary) policy} of an MDP is a mapping $\pi:\calS\rightarrow \calA$, i.e. it maps  each state $s\in\calS$ to a fixed action $\pi(s) \in \calA_s$. A \emph{randomized stationary policy} of an MDP is a mapping $\pi:\calS\rightarrow  \Delta^{\calA}$, i.e. it maps a state $s \in \calS$ to a fixed distribution over actions $\pi(s) \in \Delta^{\calA_s}$. Under a given fixed policy $\pi$ and initial distribution over states $\mathbf{q} \in \Delta^\calS$,
 the MDP generates a sample path $\{(s_1,a_1)\in(\calS\times\calA),(s_2,a_2)\in(\calS\times\calA),\cdots\}$ where $a_i$ is chosen from $\pi(s_i)$ and $s_{i+1}$ is chosen from each $\mathbf{p}_{s_i,a_i}$. Following its sample path, it receives the (cumulative) reward $V_\mathbf{q}^\pi$ defined as
\begin{equation}\label{eq:reward}
\begin{aligned}
V_\mathbf{q,\gamma}^\pi =
 & \E^\pi\left[\sum_{t\ge 1}\gamma^{t-1}r_{s_t,a_t}|s_1\sim \mathbf{q}\right], & \gamma\text{-DMDPs};\\
V_\mathbf{q}^\pi = & 	\lim_{t\rightarrow \infty}\frac{1}{T}\E^\pi\left[\sum_{t\ge 1}r_{s_t,a_t}|s_1\sim \mathbf{q}\right], & \text{AMDPs},
\end{aligned}
\end{equation}
given $\mathbf{q}$ as the initial distribution over states. We consider discount factor $\gamma<1$ for DMDPs, and an average reward for AMDPs. For brevity,  under a policy $\pi$ we use $\PP^\pi\in\R^{\calS\times\calS}$ to denote the transition matrix of the underlying Markov chain where $\PP^\pi(s,s') = \sum_{a_s\in\calA_s}\pi_s(a_s)\mathbf{p}_{s,a_s}(s')$, and $\rr^\pi\in[0,1]^\calS$ is the reward vector where $\rr^\pi(s) = \sum_{a_s\in\calA_s}\pi_s(a_s)r_{s,a_s}$. We define $\nnu^\pi$ to denote the stationary distribution of a transition matrix $\PP^\pi$ under policy $\pi$, i.e. $(\nnu^\pi)^\top\PP^\pi = \nnu^\pi$.

Our goal in solving an MDP is to find an optimal policy $\pi^\star$, that maximizes the cumulative reward. We say (stationary) policy $\pi$ is $\epsilon$-optimal, if
$V^\pi_\mathbf{q}\ge V^{\pi^\star}_\mathbf{q}-\epsilon$, for any initial distribution $\mathbf{q} \in \Delta^{\calS}$.
In this paper our main goal is to characterize the number of samples that need to be collected for each state-action pair (in the worst case) to find an $\epsilon$-optimal policy for AMDPs. We further restrict our attention to mixing AMDPs, which we define as those satisfying the following assumption.

\begin{assumption}
\label{assum}
	An AMDP instance is \emph{mixing} if for any policy $\pi$, there exists a stationary distribution $\nnu^\pi$ so that for any initial distribution $\mathbf{q}\in\Delta^\calS$, the induced Markov chain has mixing time bounded by $t_{\mathrm{mix}}<\infty$ , where $t_{\mathrm{mix}}$ is defined as
	 %
	\begin{equation*}\label{def-mixingtime}
	t_{\mathrm{mix}}\coloneqq\max_{\pi}\left[\argmin_{t\ge1 }\left\{\max_{\qq\in\Delta^\calS} \lones{({\PP^{\pi}}^{\top})^t\qq-\nnu^\pi}\le \tfrac{1}{2}\right\}\right].
	\end{equation*}
\end{assumption}

This is a natural and widely used regularity assumption~\citep{W17m,jin2020efficiently} for AMDPs to ensure the existence of cumulative reward of AMDPs in~\eqref{eq:reward}. Under Assumption~\ref{assum} one can show that $V^\pi = \langle\nnu^\pi, \rr^\pi\rangle$, where $\nnu^\pi$ is the stationary distribution over states $\calS$ under the given  policy $\pi$.  Thus, $V^\pi$ exists independent of $\qq$ for arbitrary policy $\pi$, allowing us to omit the subscript $\mathbf{q}$ for brevity. We remark that the assumption we use is weaker than the ones in~\citet{W17m,jin2020efficiently}, as we only assume mixing bounds for deterministic stationary policies, not the randomized ones.

\subsection{Results}\label{sec:intro-result}

The main result of the paper is the following upper and lower bounds for finding an $\epsilon$-optimal policy for mixing AMDPs assuming a generative model access.

\begin{restatable}{theorem}{ub}\label{thm:main-ub}
There exists an algorithm that, given a mixing AMDP	with $\mathrm{A_{tot}}$ state-action pairs and mixing time bounded by $t_{\mathrm{mix}}$ and accuracy parameter $\epsilon\in(0,1)$, finds an $\epsilon$-optimal deterministic policy with probability $1-\delta$ with $O(\mathrm{A_{tot}}\log(\mathrm{A_{tot}}/\epsilon\delta)t_{\mathrm{mix}}/\epsilon^3)$ oblivious samples.
\end{restatable}

The prior state-of-the-art sample complexity for this problem is  $\widetilde{O}(\At_{\mathrm{mix}}^2/\epsilon^2)$  due to the primal-dual method~\cite{jin2020efficiently}. Our method compares favorably in the following settings:
\begin{itemize}
\item $t_{\mathrm{mix}}\gg\omega(1/\epsilon)$: In certain large-scale settings, $t_{\mathrm{mix}}$ may be large and increase with dimension and whereas $\epsilon \in (0,1)$ need not. In such settings, the improved dependence on $t_{\mathrm{mix}}$ achieved by our method, at the expense of larger dependence on $1/\epsilon$, may be desirable.
\item one only has access to oblivious samples: Our method is the first one that uses oblivious instead of dynamic samples, which can be easier to access and cheaper to collect. Note this also implies  our method has $O(1)$ depth and is desirable for parallel computing, improving the prior parallel method for this model in~\citet{tiapkin2021parallel}.
\item one only has mixing condition on deterministic stationary policies: Our mixing condition is weaker than the standard mixing condition considered in prior work~\cite{W17m,jin2020efficiently}, which requires a $t_{\mathrm{mix}}<\infty$ mixing time bound for all randomized stationary policies.
\end{itemize}

We show that our upper bound on sample complexity for mixing AMDPs is tight up to logarithmic and poly-$\epsilon$ factors, by proving the lower bound on oblivious samples formally as follows.

\begin{restatable}{theorem}{lb}\label{thm:main-lb}
There are constants  $\epsilon_0, \delta_0\in(0,1/2)$ such that for all $\epsilon\in(0,\epsilon_0)$ and any algorithm $\mathcal{K}$, which on input mixing AMDP $(\calS,\calA,\PP,\rr)$ given by a generative model outputs a policy $\pi$ satisfying $V^{\pi}\ge V^{\pi^\star}- \epsilon$ with probability at least $1-\delta_0$,  $\mathcal{K}$ makes at least $\Omega(\At_{\mathrm{mix}}/\epsilon^2)$ deterministic oblivious queries to the generative model on some instance with $\mathrm{A_{tot}}$ total states and mixing time at most $t_{\mathrm{mix}}$.
 \end{restatable}

\subsection{Approach}\label{sec:intro-approach}

Both our algorithm design and lower bound construction leverage ideas from research on the complexity of solving  DMDPs~\citep{azar2013minimax,SWWYY18,li2020breaking}. AMDPs are the limiting case for DMDPs with $\gamma\rightarrow 1$ and this connection has been leveraged previously to prove that Bellman equations are optimality conditions for AMDPs, obtain value iteration methods for AMDPs~\cite{puterman2014markov}, and efficiently compute stationary distributions~\cite{cohen2016faster}. However, to the best of our knowledge, quantitative application of this connection has not been performed prior for a finite $\gamma$ in studying the sample complexity of AMDPs given by a  generative model. We obtain our main theorems by bridging this gap and showing how to transfer between AMDPS and DMDPs with bounded losses in the value.

To obtain our upper bound, we prove a key fact relating AMDPs and DMDPs given the same MDP tuple $\calM\coloneqq (\calS,\calA,\PP,\rr)$. In Lemma~\ref{lem-mixing-discounted-closeness} we show that for any initial distribution $\qq$, the cumulative rewards as defined in~\eqref{eq:reward} satisfy $|V^\pi-(1-\gamma)V^\pi_{\qq,\gamma}|\le O((1-\gamma)t_{\mathrm{mix}})$ . This fact follows from carefully examining the matrix expressions of $V^\pi$ for AMDP and $(1-\gamma)V^\pi_{\qq,\gamma}$ for DMDP. It also utilizes the algebraic implications of the mixing property of transition matrices $\PP^\pi$. In prior work, \citet{cohen2016faster} used such algebraic techniques on mixing properties of directed graphs; and \citet{jin2020efficiently} used it on MDP analysis. With that lemma, we show that a $\gamma=1-\Theta(\epsilon/t_{\mathrm{mix}})$-discounted MDP well approximates an AMDP in terms of their (approximately) optimal policy, without incurring an error larger than order of $\epsilon$. Also, we show that it suffices to solve the corresponding DMDP to accuracy $\varepsilon = \epsilon/(1-\gamma)$. By plugging in the sample complexity of most recent DMDP solvers~\citep{li2020breaking}, we thus obtain a sample complexity of
\arxiv{
\begin{align*}
\widetilde{O}\left(\frac{\mathrm{A_{tot}}}{(1-\gamma)^3\varepsilon^2}\right)  \stackrel{\text{choice of }\varepsilon}{=\joinrel=\joinrel=\joinrel=} \widetilde{O}\left(\frac{\mathrm{A_{tot}}}{(1-\gamma)\epsilon^2}\right) \stackrel{\text{choice of }\gamma}{=\joinrel=\joinrel=\joinrel=} \widetilde{O}\left(\frac{\At_{\mathrm{mix}}}{\epsilon^3}\right).
\end{align*}}
\notarxiv{
\begin{align*}
\widetilde{O}\left(\frac{\mathrm{A_{tot}}}{(1-\gamma)^3\varepsilon^2}\right)  & \stackrel{\text{choice of }\varepsilon}{=\joinrel=\joinrel=\joinrel=} \widetilde{O}\left(\frac{\mathrm{A_{tot}}}{(1-\gamma)\epsilon^2}\right) \\
& \stackrel{\text{choice of }\gamma}{=\joinrel=\joinrel=\joinrel=} \widetilde{O}\left(\frac{\At_{\mathrm{mix}}}{\epsilon^3}\right).
\end{align*}
}

For our lower bound, we modify the hard DMDP instances considered in~\citep{azar2013minimax}. In these instances we add to most state-action pairs a small probability of $O(1/t_{\mathrm{mix}})$ to ``restart'' the Markov chain, leading to an AMDP with $t_{\mathrm{mix}}$ mixing bound under the modified transition probabilities. In the class of hard instances, each state $i^1\in\mathcal{X}^1$ transits to a different state $i^2_{(i^1,a^{1})}$ when the agent takes a different action $a^1\in\calA_{i^1}\coloneqq[K]$, and there is one action among these that contributes to a larger cumulative reward than all the rest. We show to find an $\epsilon$-optimal policy for the constructed AMDP, one needs to identify the correct actions for at least a constant fraction of the states $i^1\in\mathcal{X}^1$, which each requires $\Omega(Kt_{\mathrm{mix}}/\epsilon^2)$ samples over all actions in $\calA_{i^1}$, giving the desired $\Omega(\At_{\mathrm{mix}}/\epsilon^2)$ sample lower bound.

\subsection{Previous Work}\label{sec:intro-review}

The study of sample complexities for finding approximately optimal policies for MDPs dates back to the proposal of generative models in 2000s~\citep{K03}.  Ever since, the area has seen vast progress in terms of understanding the hardness of solving different types of MDPs~\citep{azar2013minimax} and in designing efficient algorithms with improved sample complexities. Here we briefly survey advances in the complexity of computing approximately optimal policies for three typical types of MDPs given by a generative model  (see Table~\ref{tab:main} for a summary of these relevant prior results in each setup).\footnote{Another typical setting (outside the scope of this work) for studying these MDPs is to design efficient algorithms to minimize the \emph{regret} compared with the optimal policy~\cite{kearns2002near,ortner2007logarithmic,ortner2020regret}.}

\notarxiv{
\begin{table*}[t]
	\centering
	\renewcommand{\arraystretch}{1.4}
	\bgroup
	\caption{\textbf{Upper and lower bounds on sample complexity  to get $\epsilon$-optimal policy for different type of MDPs.} Here $\mathrm{A_{tot}}$ denotes the total size of all state-action pairs, $\gamma$ is discount factor for DMDP, $H$-MDP corresponds to finite-horizon MDP with length $H$, $t_{\mathrm{mix}}$ is mixing time for mixing AMDP, and $\tau$ is an ergodicity parameter showing up whenever the designed algorithm requires additional ergodic condition for MDP, i.e. there exists some distribution $\qq$ and $\tau>0$ satisfying $\sqrt{1/\tau}\qq\le \nnu^\pi\le\sqrt{\tau}\qq$, for any policy $\pi$ and its induced stationary distribution $\nnu^\pi$.
	%
	}\label{tab:main}

	\everymath{\displaystyle}
	\begin{tabular}{c c c c}
		\toprule
		Type                        &
		Method                    & Sample Complexity &
		Accuracy \\
		\midrule
				\multirow{9}{*}{\makecell{DMDP}}     & \emph{lower bound}~\citep{azar2013minimax,feng2019does}
	 &  $\widetilde{\Omega}(\mathrm{A_{tot}}(1-\gamma)^{-3}\epsilon^{-2})$      & N/A \\
    & Empirical QVI~\citep{azar2013minimax}
	 &  $\Otilb{\mathrm{A_{tot}}(1-\gamma)^{-3}\epsilon^{-2}}$      & $\epsilon\in(0, 1/\sqrt{(1-\gamma)|\calS|})$ \\
	&   Primal-Dual Method~\citep{W17d}  &   $\Otilb{\mathrm{A_{tot}}\tau^4(1-\gamma)^{-4}\epsilon^{-2}}$ & $\epsilon\in(0, 1/(1-\gamma))$ \\
				&   Variance-reduced QVI~\citep{SWWYY18}      &  $\Otilb{\mathrm{A_{tot}}(1-\gamma)^{-3}\epsilon^{-2}}$  & $\epsilon\in(0, 1)$ \\
		&   Empirical MDP Sampler~\citep{agarwal2019optimality}      &  $\Otilb{\mathrm{A_{tot}}(1-\gamma)^{-3}\epsilon^{-2}}$   & $\epsilon \in(0, \sqrt{1/(1-\gamma)})$\\
		& Primal-Dual SMD~\cite{jin2020efficiently}                &  $\Otilb{\mathrm{A_{tot}}(1-\gamma)^{-4}\epsilon^{-2}}$ & $\epsilon\in(0, 1/(1-\gamma))$   \\
		 & Preturbed Empirical MDP Sampler~\citep{li2020breaking}             &  $\Otilb{\mathrm{A_{tot}}(1-\gamma)^{-3}\epsilon^{-2}}$ & $\epsilon\in(0, 1/(1-\gamma))$  \\
			\hline
		\multirow{2}{*}{\makecell{H-MDP}}   &   \emph{lower bound}~\citep{SWWYY18}      &  $\widetilde{\Omega}\left(\mathrm{A_{tot}} H^3\epsilon^{-2}\right)$  & N/A \\
		 &   Variance-reduced QVI~\citep{SWWYY18}      &  $\Otilb{\mathrm{A_{tot}} H^3\epsilon^{-2}}$  & $\epsilon\in(0, 1)$ \\
	\hline

	\multirow{2}{*}{\makecell{AMDP}}
		& \emph{lower bound} (Theorem~\ref{thm:main-lb})  &  $\Omega\left(\At_{\mathrm{mix}}\epsilon^{-2}\right)$ &  N/A\\
		&  Primal-Dual Method~\citep{W17m}  &   $\Otilb{\tau^2\At_{\mathrm{mix}}^2\epsilon^{-2}}$ & $\epsilon\in(0, 1)$ \\
		& Primal-Dual SMD~\citep{jin2020efficiently}  &   $\Otilb{\At_{\mathrm{mix}}^2\epsilon^{-2}}$ & $\epsilon\in(0, 1)$
		  \\
		  & \textbf{Our method} (Theorem~\ref{thm:main-ub})                &    $\Otilb{\At_{\mathrm{mix}}\epsilon^{-3}}$ & $\epsilon\in(0, 1)$
		  \\

		\bottomrule
	\end{tabular}
	\egroup
\end{table*}
}
\arxiv{
\begin{table*}[t]
	\centering
	\renewcommand{\arraystretch}{1.4}
	\bgroup
	\caption{\textbf{Upper and lower bounds on sample complexity  to get $\epsilon$-optimal policy for different type of MDPs.} Here $\mathrm{A_{tot}}$ denotes the total size of all state-action pairs, $\gamma$ is discount factor for DMDP, $H$-MDP corresponds to finite-horizon MDP with length $H$, and $t_{\mathrm{mix}}$ is mixing time for mixing AMDP. Further, $\tau$ is an ergodicity parameter which arises in algorithms that require an additional ergodic condition for MDP which states that there exists some distribution $\qq$ and $\tau>0$ satisfying $\sqrt{1/\tau}\qq\le \nnu^\pi\le\sqrt{\tau}\qq$, for any policy $\pi$ and its induced stationary distribution $\nnu^\pi$.
	%
	}\label{tab:main}

	\everymath{\displaystyle}
	\begin{tabular}{c c c c}
		\toprule
		Type                        &
		Method                    & Sample Complexity &
		Accuracy \\
		\midrule
				\multirow{9}{*}{\makecell{DMDP}}     & \emph{lower bound}~\citep{azar2013minimax,feng2019does}
	 &  $\widetilde{\Omega}(\mathrm{A_{tot}}(1-\gamma)^{-3}\epsilon^{-2})$      & N/A \\
    & Empirical QVI~\citep{azar2013minimax}
	 &  $\Otilb{\mathrm{A_{tot}}(1-\gamma)^{-3}\epsilon^{-2}}$      & $\epsilon\in(0, \tfrac{1}{\sqrt{(1-\gamma)|\calS|}})$ \\
	&   Primal-Dual Method~\citep{W17d}  &   $\Otilb{\mathrm{A_{tot}}\tau^4(1-\gamma)^{-4}\epsilon^{-2}}$ & $\epsilon\in(0, \tfrac{1}{1-\gamma})$ \\
				&   Variance-reduced QVI~\citep{SWWYY18}      &  $\Otilb{\mathrm{A_{tot}}(1-\gamma)^{-3}\epsilon^{-2}}$  & $\epsilon\in(0, 1)$ \\
		&   Empirical MDP Sampler~\citep{agarwal2019optimality}      &  $\Otilb{\mathrm{A_{tot}}(1-\gamma)^{-3}\epsilon^{-2}}$   & $\epsilon \in(0, \tfrac{1}{\sqrt{1-\gamma}})$\\
		& Primal-Dual SMD~\cite{jin2020efficiently}                &  $\Otilb{\mathrm{A_{tot}}(1-\gamma)^{-4}\epsilon^{-2}}$ & $\epsilon\in(0, \tfrac{1}{1-\gamma})$   \\
		 & Preturbed Empirical MDP Sampler~\citep{li2020breaking}             &  $\Otilb{\mathrm{A_{tot}}(1-\gamma)^{-3}\epsilon^{-2}}$ & $\epsilon\in(0, \tfrac{1}{1-\gamma})$  \\
			\hline
		\multirow{2}{*}{\makecell{H-MDP}}   &   \emph{lower bound}~\citep{SWWYY18}      &  $\widetilde{\Omega}\left(\mathrm{A_{tot}} H^3\epsilon^{-2}\right)$  & N/A \\
		 &   Variance-reduced QVI~\citep{SWWYY18}      &  $\Otilb{\mathrm{A_{tot}} H^3\epsilon^{-2}}$  & $\epsilon\in(0, 1)$ \\
	\hline

	\multirow{2}{*}{\makecell{AMDP}}
		& \emph{lower bound} (Theorem~\ref{thm:main-lb})  &  $\Omega\left(\At_{\mathrm{mix}}\epsilon^{-2}\right)$ &  N/A\\
		&  Primal-Dual Method~\citep{W17m}  &   $\Otilb{\tau^2\At_{\mathrm{mix}}^2\epsilon^{-2}}$ & $\epsilon\in(0, 1)$ \\
		& Primal-Dual SMD~\citep{jin2020efficiently}  &   $\Otilb{\At_{\mathrm{mix}}^2\epsilon^{-2}}$ & $\epsilon\in(0, 1)$
		  \\
		  & \textbf{Our method} (Theorem~\ref{thm:main-ub})                &    $\Otilb{\At_{\mathrm{mix}}\epsilon^{-3}}$ & $\epsilon\in(0, 1)$
		  \\

		\bottomrule
	\end{tabular}
	\egroup
\end{table*}
}

\paragraph{DMDPs.}
~\citet{azar2013minimax} and~\citet{feng2019does} prove a lower bound of $\widetilde{\Omega}(\mathrm{A_{tot}}/(1-\gamma)^{3}\epsilon^{2})$ for $\gamma$-discounted MDPs. On the upper bound side, \citet{azar2013minimax} also obtain a $Q$-value-iteration algorithm with  a (sub-)optimal sample complexity of either $\widetilde{O}(\mathrm{A_{tot}}/(1-\gamma)^5\epsilon^2)$ or $\widetilde{O}(\mathrm{A_{tot}}/(1-\gamma)^3\epsilon^2)$ for $\epsilon\in(0, 1/\sqrt{(1-\gamma)|\calS|})$. Later, a sequence of work ~\citep{SWWY18,SWWYY18} provide a variance-reduced (Q-)value iteration that has near-optimal sample complexity and runtime of~$\widetilde{O}(\mathrm{A_{tot}}/(1-\gamma)^3\epsilon^2)$ for $\epsilon\in(0, 1)$. Their method incorporates variance reduction in estimating the value iteration step, and performs a fine-grained analysis of the error growth through the iterative process using a tight variance bound of Markov decision processes. Similarly, \citet{W19} shows that variance reduction can be applied to Q-learning and obtain a method with competing sample complexity guarantees for the same range of accuracy $\epsilon\in(0, 1)$. From a more statistical and less algorithmic perspective,  another work of ~\citet{agarwal2019optimality} shows that $\widetilde{O}(\mathrm{A_{tot}}/(1-\gamma)^3\epsilon^2)$ samples suffice to build an empirical MDP such that the optimal policy of it yields a near-optimal policy for the original MDP. Their work also utilizes the fine-grained variance bound using Berstein inequality and extends the near-optimal sample complexity dependence to all $\epsilon\in(0, 1/\sqrt{1-\gamma})$. Recent work~\citep{li2020breaking} fully settled the sample complexity for DMDPs for all $\epsilon$, i.e. $\epsilon\in(0,1/(1-\gamma))$, with a perturbed empirical MDP construction. We leverage this result crucially to obtain our results in Section~\ref{sec:ub}.

\paragraph{Finite-horizon MDPs.}
For finite-horizon MDPs, cumulative reward is measured as the sum of the rewards obtained within first $H$ steps for a given finite horizon $H>0$. To the best of our knowledge, the only near-optimal algorithm given for finite-horizon MDP is in~\citet{SWWY18}. There, the authors show how to apply the near-optimal variance-reduced value iteration method to MDPs with finite horizon of length $H$. They formally prove an upper bound of $\widetilde{O}(\mathrm{A_{tot}} H^3/\epsilon^{2})$ in sample complexity, for $\epsilon\in(0,1)$. Through reduction to DMDP lower bounds, they also obtain a lower bound of $\widetilde{\Omega}(\mathrm{A_{tot}} H^3/\epsilon^2)$.

\paragraph{AMDPs.}

Average-reward MDPs with bounded mixing time are another fundamental class of MDPs~\cite{kearns2002near,ortner2007logarithmic}, though less studied in terms of sample complexity. The first sample complexity bounds in the setting of a generative model is~\citet{W17m}, which applies a primal-dual method for the minimax problem related to the linear programming formulation, and proves an upper bound of $O(\tau^2\At_{\mathrm{mix}}^2/\epsilon^2)$ where $\tau$ denotes an upper bound on the ergodicity of all stationary distribution under arbitrary policies, i.e.\ there exists some distribution $\qq\in\Delta^\calS$ satisfying $\sqrt{1/\tau}\cdot\qq\le \nnu^\pi\le\sqrt{\tau}\cdot\qq$ for all policies $\pi$ and its induced stationary distribution $\nnu^\pi$. Recently, ~\citet{jin2020efficiently} design a similar primal-dual stochastic mirror descent and improve the bound to $O(\At_{\mathrm{mix}}^2/\epsilon^2)$, removing the ergodicity assumption through an improved analysis of the optimality conditions of the minimax problem. In contrast to value iteration, Q-learning, and sample-based methods for DMDPs, both known efficient methods for AMDPs use a linear programming formulation, dynamic sampling, a stronger mixing condition, and only compute randomized stationary policies. On the hardness side, there is no known lower bound for AMDPs with bounded mixing time.

 %
\subsection{Notation}\label{sec:prelims}

We use unbold letters, e.g. $V$, to denote scalars, and bold letters, e.g. $\vv$ and $\PP$, to denote vectors and matrices. We use $\ee_i$ to denote the basis vector that is $1$ on coordinate $i$, and $0$ elsewhere. We use $\mathbf{1}_\calS$ to denote the all-ones vector in $\R^\calS$, and omit the subscript when it is clear from context. We use $\|\cdot\|_\infty$ to denote the $\ell_\infty$-norm of vectors and $\ell_\infty$-operator norm of matrices, e.g.
\arxiv{
\[
\|\vv\|_\infty \coloneqq \max_{s\in\calS}|\vv(s)|~\text{and}~\|\PP\|_\infty \coloneqq
\max_{\norm{\xx}_\infty = 1} \norm{\PP \xx}_\infty =
\max_{s\in\calS}\sum_{s'\in\calS}|\PP(s,s')|\,.
\]
}
\notarxiv{
$\|\vv\|_\infty \coloneqq \max_{s\in\calS}|\vv(s)|$ and $\|\PP\|_\infty \coloneqq
\max_{\norm{\xx}_\infty = 1} \norm{\PP \xx}_\infty =
\max_{s\in\calS}\sum_{s'\in\calS}|\PP(s,s')|$.
}
 %
\section{Upper Bound}\label{sec:ub}

In this section, we prove the sample complexity upper bound for obtaining an $\epsilon$-optimal deterministic policy for mixing AMDPs. We first provide Lemma~\ref{lem-mixing-discounted-closeness} that relates the value of AMDPs and DMDPs under the same policy. Then we reduce solving AMDPs to DMDPs with the proper discount factor (Lemma~\ref{lem:redx-ub}) and use the state-of-the-art DMDP solver (restated in Lemma~\ref{lem:solver}) to obtain our result.

Throughout the section, we consider some mixing AMDP, and its corresponding DMDP with the same tuple $(\calS,\calA,\PP,\rr)$ and some discount factor $\gamma\in(0,1)$ to be specified.

\paragraph{Characterization of value vectors.}

We introduce the  value vector $\vv^\pi\in\R^\calS$ under a given policy $\pi$ for all states $s\in\calS$.  To distinguish between the value vectors of a DMDP and AMDP, we use $\vv^\pi_{\gamma}$ for DMDPs and $\vv^\pi$ for AMDPs respectively. For the discounted case, we let $\vv_{\gamma}^\pi(s) = V^\pi_{\qq = \ee_s,\gamma}$, i.e. the cumulative reward of the MDP with initial distribution only on state $s$.  We first give the following equations for computing value vectors $\vv^\pi$. These are known results widely used in literature~(see also \citet{puterman2014markov, W17m,jin2020efficiently}).

Given a tuple $(\calS,\calA,\PP,\rr)$, for DMDP with discount factor $\gamma$ and a policy $\pi$, we have
\begin{equation}
\vv^\pi_\gamma = \sum_{t\ge 0}\gamma^{t}(\PP^\pi)^t\rr^\pi
\enspace\text{ and }\enspace
\linf{\vv^\pi_\gamma}\in\left[0,\frac{1}{1-\gamma}\right].\label{eq:DMDP-value}
\end{equation}
Similarly, for AMDP and a policy $\pi$ that induces stationary distribution $\nnu^\pi$, since the reward doesn't depend on initial distribution, we have
\begin{equation}
\vv^\pi = \langle \rr^\pi,\nnu^\pi\rangle\mathbf{1}
\enspace\text{ and }\enspace
\linf{\vv^\pi}\in\left[0,1\right].\label{eq:DMDP-value}
\end{equation}

To put the two value vectors on the same $[0,1]$ scale, we introduce the following rescaled value vectors denoted by $\bar{\vv}^\pi$, one has
\begin{equation}\label{def:value-vector-rescaled}
\begin{aligned}
\bar{\vv}^\pi & = \vv^\pi = \lim_{T\rightarrow \infty}\frac{1}{T}\sum_{t=0}^T (\PP^\pi)^t \rr^\pi = V^\pi\cdot\mathbf{1}\\
 \text{ and }~~   \bar{\vv}_{\gamma}^\pi & =  (1-\gamma)\vv_{\gamma}^\pi = (1-\gamma)\left[\sum_{t=0}^\infty \gamma^t(\PP^\pi)^t\rr^\pi \right].
\end{aligned}
\end{equation}

We first state a helper lemma for $\PP^\pi$ following from the fact that it has mixing time bound $t_{\mathrm{mix}}$, quoted from Lemma 23 of~\citet{cohen2016faster}.

\begin{lemma}[see Lemma 14 of~\citet{jin2020efficiently}, Lemma 23 of~\citet{cohen2016faster}]\label{lem:inf-bound}
For any policy $\pi$ with induced probabilistic transition matrix $\PP^\pi$ of mixing time $t_{\mathrm{mix}}$ and stationary distribution $\nnu^\pi$ and any non-negative integer $k\ge t_{\mathrm{mix}}$,
\begin{align*}
\linf{(\PP^\pi)^{k}-\mathbf{1}(\nu^\pi)^\top}  \le \left(\frac{1}{2}\right)^{\left\lfloor \frac{k}{t_{\mathrm{mix}}}\right\rfloor}.
\end{align*}
\end{lemma}

Now we provide a lemma that bounds the $\ell_\infty$-difference of the two rescaled value vectors $\bar{\vv}^\pi$ and $\bar{\vv}_{\gamma}^\pi$ under the given policy $\pi$ and discount factor $\gamma$.

\begin{lemma}\label{lem-mixing-discounted-closeness}
Given a same MDP tuple $(\calS,\calA,\PP,\rr)$, a policy $\pi$ and some discount factor $\gamma$, rescaled value vectors $\bar{\vv}^\pi$ for AMDP and $\bar{\vv}^\pi_{\gamma}$ for DMDP as defined in~\eqref{def:value-vector-rescaled} satisfy
\[
\linf{\bar{\vv}^\pi-\bar{\vv}^\pi_{\gamma}}\le 3(1-\gamma)
t_{\mathrm{mix}}.
\]
\end{lemma}
\begin{proof}
Note that
\arxiv{
\begin{align*}
\linf{\bar{\vv}^\pi-\bar{\vv}^\pi_{\gamma}}
	&= \linfbigg{(1-\gamma)\sum_{t\ge 0}\gamma^t\langle\rr^\pi,\nnu^\pi\rangle\mathbf{1}-(1-\gamma)\sum_{t\ge 0}\gamma^t(\PP^\pi)^t\rr^\pi}\\
	&= (1-\gamma)\linfbigg{\sum_{t=0}^\infty \gamma^t\left[(\PP^\pi)^t-\mathbf{1}(\nnu^\pi)^\top\right]\rr^\pi} \\
	&\leq  (1-\gamma) \sum_{t=0}^\infty \gamma^t \linf{(\PP^\pi)^t-\mathbf{1}(\nnu^\pi)^\top} \cdot \linf{\rr^\pi} ~.
\end{align*}}
\notarxiv{
\begin{align*}
& \linf{\bar{\vv}^\pi-\bar{\vv}^\pi_{\gamma}} \\
	= & \linfbigg{(1-\gamma)\sum_{t\ge 0}\gamma^t\langle\rr^\pi,\nnu^\pi\rangle\mathbf{1}-(1-\gamma)\sum_{t\ge 0}\gamma^t(\PP^\pi)^t\rr^\pi}\\
	= & (1-\gamma)\linfbigg{\sum_{t=0}^\infty \gamma^t\left[(\PP^\pi)^t-\mathbf{1}(\nnu^\pi)^\top\right]\rr^\pi} \\
	\leq & (1-\gamma) \sum_{t=0}^\infty \gamma^t \linf{(\PP^\pi)^t-\mathbf{1}(\nnu^\pi)^\top} \cdot \linf{\rr^\pi} ~.
\end{align*}
}
Now, $\linf{\rr^\pi} \leq 1$ by assumption and for all $t \geq 0$ we have
\[
\linf{(\PP^\pi)^t-\mathbf{1}(\nnu^\pi)^\top}
\leq \linf{(\PP^\pi)^t} + \linf{\mathbf{1}(\nnu^\pi)^\top}
= 2 ~.
\]
Further for all $t \geq t_{\mathrm{mix}}$ we have $\linf{(\PP^\pi)^t-\mathbf{1}(\nnu^\pi)^\top} \leq 2^{- \lfloor k/t_{\mathrm{mix}} \rfloor}$ by  Lemma~\ref{lem:inf-bound}. Combining yields the desired bound of
\arxiv{
\begin{align*}
\linf{\bar{\vv}^\pi-\bar{\vv}^\pi_{\gamma}}
&\leq
(1-\gamma) \sum_{t=0}^{t_{\mathrm{mix}} - 1} \gamma^t \linf{(\PP^\pi)^t-\mathbf{1}(\nnu^\pi)^\top}
+ (1-\gamma) \sum_{t \geq  t_{\mathrm{mix}}} \gamma^t \linf{(\PP^\pi)^t-\mathbf{1}(\nnu^\pi)^\top}  \\
&\leq (1-\gamma) \sum_{t=0}^{ t_{\mathrm{mix}} - 1} 2 \gamma^t
+ (1-\gamma) \sum_{t \geq  t_{\mathrm{mix}}} \frac{1}{2^{\lfloor k/t_{\mathrm{mix}}\rfloor}}
\leq 3(1 - \gamma)t_{\mathrm{mix}}\,.
\end{align*}}
\notarxiv{
\begin{align*}
& \linf{\bar{\vv}^\pi-\bar{\vv}^\pi_{\gamma}} \\
\leq &
(1-\gamma) \sum_{t=0}^{t_{\mathrm{mix}} - 1} \gamma^t \linf{(\PP^\pi)^t-\mathbf{1}(\nnu^\pi)^\top} \\
& + (1-\gamma) \sum_{t \geq  t_{\mathrm{mix}}} \gamma^t \linf{(\PP^\pi)^t-\mathbf{1}(\nnu^\pi)^\top}  \\
\leq & (1-\gamma) \sum_{t=0}^{ t_{\mathrm{mix}} - 1} 2 \gamma^t
+ (1-\gamma) \sum_{t \geq  t_{\mathrm{mix}}} \frac{1}{2^{\lfloor k/t_{\mathrm{mix}}\rfloor}}\\
\leq & 3(1 - \gamma)t_{\mathrm{mix}}\,.
\end{align*}}
\end{proof}

This lemma shows under the same policy, the values of AMDP and its corresponding DMDP are close up to $\epsilon$ when choosing the discount factor $\gamma = 1-\Theta(\epsilon/t_{\mathrm{mix}})$. This  allows us to formally reduce solving AMDPs to solving DMDPs with large enough discount factors in Lemma~\ref{lem:redx-ub}.

\begin{lemma}\label{lem:redx-ub}
Given an AMDP with mixing time bounded by $t_{\mathrm{mix}}$, accuracy parameter $\epsilon\in(0,1)$, and an $\tfrac{\epsilon}{3(1-\gamma)}$-optimal policy $\pi$ for the corresponding DMDP with $\gamma = 1-\tfrac{\epsilon}{9t_{\mathrm{mix}}}$, $\pi$ is also a $\epsilon$-optimal policy for the original AMDP.
\end{lemma}

\begin{proof}
Consider a DMDP with the same transition matrix and discount factor $\gamma  = 1-\frac{\epsilon}{9t_{\mathrm{mix}}}$, 	we have $\linf{\bar{\vv}^\pi-\bar{\vv}^\pi_{\gamma}}\le \epsilon/3$ by Lemma~\ref{lem-mixing-discounted-closeness}.

Now let $\pi_d$ and $\pi_a$ denote optimal policies for the DMDP and AMDP respectively. By definition of $\pi$ one has
\arxiv{
\begin{equation}\label{def:pi-d-pi}
\linf{\vv^\pi_{\gamma}-\vv^{\pi_d}_{\gamma}}\le \frac{\epsilon}{3(1-\gamma)}
\enspace\text{ or equivalently, }\enspace
\linf{\bar{\vv}^\pi_{\gamma}-\bar{\vv}^{\pi_d}_{\gamma}}\le \epsilon/3.
\end{equation}}
\notarxiv{
\begin{equation}\label{def:pi-d-pi}
\linf{\vv^\pi_{\gamma}-\vv^{\pi_d}_{\gamma}}\le \frac{\epsilon}{3(1-\gamma)}
\enspace\Longleftrightarrow\enspace
\linf{\bar{\vv}^\pi_{\gamma}-\bar{\vv}^{\pi_d}_{\gamma}}\le \epsilon/3.
\end{equation}
}
Consequently, one has that entrywise,
\arxiv{
\begin{align*}
\bar{\vv}^\pi+\tfrac{\epsilon}{3}\mathbf{1} & \stackrel{(i)}{\ge} \bar{\vv}^\pi_{\gamma}\stackrel{(ii)}{\ge} \bar{\vv}^{\pi_d}_{\gamma}-\tfrac{\epsilon}{3}\mathbf{1}\stackrel{(iii)}{\ge} \bar{\vv}^{\pi_a}_{\gamma}-\tfrac{\epsilon}{3}\mathbf{1} \stackrel{(i)}{\ge} \left(\bar{\vv}^{\pi_a}-\tfrac{\epsilon}{3}\mathbf{1}\right)-\tfrac{\epsilon}{3}\mathbf{1},
\end{align*}}
\notarxiv{
\begin{align*}
\bar{\vv}^\pi+\tfrac{\epsilon}{3}\mathbf{1} & \stackrel{(i)}{\ge} \bar{\vv}^\pi_{\gamma}\stackrel{(ii)}{\ge} \bar{\vv}^{\pi_d}_{\gamma}-\tfrac{\epsilon}{3}\mathbf{1}\stackrel{(iii)}{\ge} \bar{\vv}^{\pi_a}_{\gamma}-\tfrac{\epsilon}{3}\mathbf{1} \\
& \stackrel{(i)}{\ge} \left(\bar{\vv}^{\pi_a}-\tfrac{\epsilon}{3}\mathbf{1}\right)-\tfrac{\epsilon}{3}\mathbf{1},
\end{align*}
}
where we use $(i)$ Lemma~\ref{lem-mixing-discounted-closeness} together with the choice of $\gamma = 1-\frac{\epsilon}{9t_{\mathrm{mix}}}$, $(ii)$ equation~\eqref{def:pi-d-pi}, and $(iii)$ the optimality of $\pi_d$ for DMDP by definition.

Altogether we conclude that $\bar{\vv}^\pi\ge \bar{\vv}^{\pi_a}-\epsilon\mathbf{1}$ and therefore $V^\pi\ge V^{\pi^\star}-\epsilon$,
i.e. $\pi$ is a $\epsilon$-optimal policy for the given AMDP.
\end{proof}

With the reduction, we can apply recent DMDP solvers to obtain an AMDP solver with the desired sample complexity. In order to solve the corresponding $\gamma$-discounted MDP to a desired accuracy, we use the following recent efficient DMDP solver~\cite{li2020breaking}.

\begin{lemma}[Corollary of Theorem 1 of~\citet{li2020breaking}]\label{lem:solver}
There is an algorithm that, given a $\gamma$-discounted MDP, desired accuracy $\varepsilon\le 1/(1-\gamma)$, failure probability $0<\delta\ll 1$, outputs an $\varepsilon$-optimal policy with probability $1-\delta$ with a number of oblivious samples bounded by
\[
\widetilde{O}\left(\frac{\mathrm{A_{tot}}}{(1-\gamma)^3\varepsilon^2}\log\frac{\mathrm{A_{tot}}}{(1-\gamma)\varepsilon\delta}\right)\,.
\]
\end{lemma}

We remark that what we state is an immediate corollary of Theorem 1 in~\citet{li2020breaking} which works for non-uniform action space per state as well by expanding the space. Now we can apply this solver to find an $\epsilon/(1-\gamma)$-optimal policy for $\gamma$-discounted MDP to   obtain our main result.

\ub*

\begin{proof}[Proof of Theorem~\ref{thm:main-ub}]

By Lemma~\ref{lem:redx-ub}, it suffices to solve the corresponding DMDP to $\epsilon/3(1-\gamma)$ accuracy with $\gamma =1-\epsilon/9t_{\mathrm{mix}}$. Using the solver in Lemma~\ref{lem:solver} with $\varepsilon = \epsilon/3(1-\gamma)$, it has sample complexity bounded by the following as stated.
\begin{align*}
& \O{\frac{\mathrm{A_{tot}}}{(1-\gamma)^3(\epsilon/3(1-\gamma))^2}\log \frac{\mathrm{A_{tot}}}{(1-\gamma)\frac{\epsilon}{3(1-\gamma)}\delta}} \\
= & \O{\frac{\mathrm{A_{tot}}}{(1-\gamma)\epsilon^2}\log \frac{\mathrm{A_{tot}}}{\epsilon\delta}} = \O{\frac{\At_{\mathrm{mix}}}{\epsilon^3}\log\frac{\mathrm{A_{tot}}}{\epsilon\delta} },
\end{align*}
where we use the choice of $\gamma$ for the last equality. This proves the correctness of the method and yields the sample complexity bound as claimed.

\end{proof}

\notarxiv{
\begin{figure*}[ht]
\vskip 0.2in
\centering
\begin{center}
\centerline{\includegraphics[width=2\columnwidth]{lb-v2.pdf}}
\caption{\textbf{AMDP lower bound hard instance illustration.} $N$ states in $\mathcal{X}^1$ (corresponding to first level), $K$ action per state $i^1\in\mathcal{X}^1$, $\mathrm{A_{tot}} = O(NK)$ total state-action pairs. $\gamma\in(0,1)$, $p_{i^1,a^1}\in[0,1]$ for all $i^1\in\mathcal{X}^1$, $a^1\in [K]$ are tunable parameters.}\label{fig:lb}
\end{center}
\vskip -0.2in
\end{figure*}
}

\begin{remark}[Nearly-tight $\epsilon$ regime.]
That \citet{li2020breaking} achieves near-optimal sample complexity for solving DMDPs for all $\varepsilon\in(0,1/(1-\gamma))$, as opposed to the more restricted range of $\varepsilon \in (0, 1)$ in~\citet{SWWYY18} and $\varepsilon \in (0, 1/\sqrt{1-\gamma})$ in~\citet{agarwal2019optimality}, is key for Theorem~\ref{thm:main-ub}. This is due to the fact that we need to solve the corresponding DMDP to an accuracy of $\varepsilon = \epsilon/(1-\gamma)$, which is on the order of $1/(1-\gamma)$ for constant accuracy parameter $\epsilon\in(0,1)$. The $\epsilon$ regime where we can apply prior results, i.e.  $\varepsilon\le 1/\sqrt{1-\gamma}$, corresponds in AMDPs in the regime where our method's sample complexity is no better than that of $\widetilde{O}(\At_{\mathrm{mix}}^2/\epsilon^2)$ achieved by prior work~\cite{jin2020efficiently}.
\end{remark}

 %

\section{Lower Bound}

In this section, we show a lower bound of $\Omega(\At_{\mathrm{mix}}/\epsilon^2)$ oblivious samples for finding an $\epsilon$-optimal policy for an AMDP with mixing time $t_{\mathrm{mix}}$. This closes the gap (up to logarithmic and poly-$\epsilon$ terms) for finding an approximately-optimal policy for an AMDP given oblivious samples
and shows that the method we propose in Theorem~\ref{thm:main-ub} with  sample complexity $\widetilde{O}(\At_{\mathrm{mix}}/\epsilon^{3})$ is near optimal for constant $\epsilon$. We defer some proofs in this section to Appendix~\ref{app:lb}.

To obtain this result, we provide a family of AMDP instances that we prove are difficult to solve. Our construction is similar to that given in \citet{azar2013minimax, feng2019does} for lower bounding the sample complexity of DMDPs. Formally, we consider the state space to be $\calS = \mathcal{X}^1\cup\mathcal{X}^2\cup\mathcal{X}^3$, denoting three disjoint subsets of states on different levels (see Figure~\ref{fig:lb}). We denote the action space as $\calA_s = [K]$, for all $s = i^1\in\mathcal{X}^1$, and $\calA_s = \{\text{single fixed action}\}$, for all $s\in\mathcal{X}^2\cup\mathcal{X}^3$.

Let  $\mathcal{X}^1$ have $N$ independent states, each with $K$ independent actions. We assume for state $i^1\in\mathcal{X}_1$, when taking action $a^{1}$, an agent gets to some state at second level, denoted as $i^2_{(i^1,a^1)}\in\mathcal{X}^2$. At state $i^2_{(i^1,a^1)}\in\mathcal{X}^2$ the agent can only take one single action after which with probability $1-\gamma$ it goes uniformly random to a state at the first level in $\mathcal{X}^1$, with probability $p_{(i^1,a^1)}\gamma$ it goes back to its own state, and with probability $(1-p_{(i^1,a^1)})\gamma$ it gets to some state on the third level denoted as $i^3_{(i^1,a^1)}\in\mathcal{X}^3$. At $i^3_{(i^1,a^1)}\in\mathcal{X}^3$, the agent can take a single action after which with probability $1-\gamma$ it goes uniformly randomly to a state at first level in $\mathcal{X}^1$ while with probability $\gamma$ it stays at the original state $i^3_{(i^1,a^1)}\in\mathcal{X}^3$. A reward $1$ is generated when the agent transfers from a state in $\mathcal{X}^2$ to itself, and all other transmissions generate $0$ reward. See Figure~\ref{fig:lb} for an illustration.

\arxiv{
\begin{figure*}[ht]
\vskip 0.2in
\centering
\begin{center}
\centerline{\includegraphics[width=\columnwidth]{lb-v2.pdf}}
\caption{\textbf{AMDP lower bound hard instance illustration.} $N$ states in $\mathcal{X}^1$ (corresponding to first level), $K$ action per state $i^1\in\mathcal{X}^1$, $\mathrm{A_{tot}} = O(NK)$ total state-action pairs. $\gamma\in(0,1)$, $p_{i^1,a^1}\in[0,1]$ for all $i^1\in\mathcal{X}^1$, $a^1\in [K]$ are tunable parameters.}\label{fig:lb}
\end{center}
\vskip -0.2in
\end{figure*}
}

We construct the instances such that for each state-action pair $(i^1,a^1)$, a chain of length-$2$ composed of states $i^2_{(i^1,a^1)}$, $i^3_{(i^1,a^1)}$ follows. The probability $(1-\gamma)$ to go back uniformly to a state $i^1\in\mathcal{X}^1$ from each chain allows the entire Markov chain to ``restart'' from $i^1$ uniformly, and ensures a $O(1/(1-\gamma))$ mixing time bound, as we show in Section~\ref{sec:lb-mix}. When in a single chain, only the transition probability $p_{(i^1,a^1)}$ of transiting from $i^2_{(i^1,a^1)}$ to itself effects the average-reward.

To create our family of hard AMDP intances, we consider all instances such that for each $i^1\in\hat{\mathcal{X}}^1$, one of the following two cases occurs: \begin{itemize}
 \item 	Case $(i)$: there is one action $k\in[K]$ that leads to transition probability $\gamma p'$, and all other actions with probability $\gamma p$; in this case the optimal action is $k$.
 \item Case $(ii)$: there is one action $a^1_\star$ that leads to transition probability $\gamma p^\star$, one action  $k\in[K]$ leading to probability $\gamma p'$, and all others leading to probability $p$; in this case the optimal action is $a^1_\star$.
 \end{itemize}
In Section~\ref{sec:lb-proof} we argue one needs to find the best action for at least a constant fraction of the states $i^1\in\mathcal{X}^1$ to obtain an $O(\epsilon)$-optimal policy and we show this requires at least $\Omega(NKt_{\mathrm{mix}}\epsilon^{-2})$ oblivious samples for properly chosen $p$, $p'$, and $p^\star$.

\subsection{Stationary Distribution and Mixing Time}\label{sec:lb-mix}

First, we characterize the stationary distribution under a policy $\pi$; this is useful for bounding suboptimality for policies in Section~\ref{sec:lb-proof}.

\begin{lemma}[Stationary Distribution Characterization]~\label{lem:lb-stationary}
	Consider a policy that chooses always a fixed $a^1$ for each state in $\mathcal{X}^1$. The stationary distribution $\nnu$ is in the following form:
\begin{align*}
\nnu\left(i^1\right) & = \frac{1}{N}\cdot\frac{1-\gamma}{2-\gamma}, \forall i^1\in\mathcal{X}^1;\\
\nnu\left(i^2_{(i^1,a^1)}\right) & = \frac{1}{N}\cdot\frac{1-\gamma}{(1-\gamma p_{(i^1,a^1)})(2-\gamma)},\text{ if }\pi_{i^1}(a^1) = 1,\\
\nnu\left(i^2_{(i^1,a^1)}\right) & = 0, \quad \forall a^1\in \calA,\pi_{i^1}(a^1) = 0;	\\
\nnu\left(i^3_{(i^1,a^1)}\right) & = \frac{1}{N}\cdot\frac{\gamma(1-p_{(i^1,a^1)})}{(1-\gamma p_{(i^1,a^1)})(2-\gamma)}, \text{ if }\pi_{i^1}(a^1) = 1,\\
\nnu\left(i^3_{(i^1,a^1)}\right) & = 0, \quad \forall a^1\in \calA,\pi_{i^1}(a^1) = 0.
\end{align*}

\end{lemma}

The proof of Lemma~\ref{lem:lb-stationary} follows by checking the definition of stationary distribution given the transition probabilities of the model; we defer it to Appendix~\ref{app:lb}.

Next, we show that the mixing time of such a Markov chain under any policy $\pi$ is $O(1/(1-\gamma))$ formally; we defer the complete proof to Appendix~\ref{app:lb}.

\begin{lemma}\label{lem:lb-mixing-time}
The AMDP constructed in this section has mixing time $t_{\mathrm{mix}}\le O(1/(1-\gamma))$.
\end{lemma}

\begin{proof-sketch}
We first consider a regularized probability transition matrix in form
\begin{equation}
\label{eq:reg_structure}
\hat{\PP} = \gamma\PP + (1-\gamma)\mathbf{1}\mathbf{p}^\top,
\end{equation}
for some probability transition matrix $\PP$ and some density vector $\mathbf{p}$.

Such a probability transition matrix induces a Markov chain where each step moves according to $\PP$ with probability $\gamma$, and restart from a random state following a fixed distribution $\mathbf{p}$  with probability $1-\gamma$. After $\tilde{O}(1/(1-\gamma))$ steps the initial distribution doesn't affect where one is at because with high probability it has restarted following a fixed distribution for at least once. That the distribution isn't affected by the initial distribution ensures that the Markov chain is mixing.

Unfortunately, we cannot immediately apply this result as in our Markov chain one will only restart with certain probability when at a state in $\mathcal{X}^2\cup\mathcal{X}^3$ (as opposed to all states). Instead we show the $2$-step probability transition matrix admits the structure of a regularized probability transition, i.e. \eqref{eq:reg_structure}. Thus we apply the result to the $2$-step transition matrix to argue that it mixes within $O(1/(1-\gamma))$ steps, which we show implies that  the original Markov chain mixes within time steps $O(1/(1-\gamma))$, proving the statement as claimed.
\end{proof-sketch}

\subsection{Lower Bound Proofs}\label{sec:lb-proof}

Here we show a lower bound on the sample complexity for obtaining an $\epsilon$-optimal policy. Without loss of generality in this section we assume $N,K$ are at least some sufficiently large constants, $\epsilon\le 1/32$, and $\gamma\ge 1/2$.

We consider the family of AMDPs $\M$ where for each MDP instance and any fixed $i^1\in\hat{\mathcal{X}}^1$ either case $(i)$ or case $(ii)$ will happen, i.e.
\begin{equation}\label{def:p}
\begin{aligned}
\text{let}~p = \gamma,&\ p' = \gamma+\epsilon(1-\gamma),\ p^\star = \gamma+2\epsilon(1-\gamma),\\
	\text{case}~(i):& ~p_{(i^1,a^1)}= \begin{cases}
 	p'~&\text{for some}~k\in[K],\\
 	p~&\text{for any}~a^1\neq k;
 \end{cases}\\
	\text{case}~(ii):& ~p_{(i^1,a^1)}= \begin{cases}
 	p^\star~&\text{for some}~a^1_\star\in[K],\\
 	p'~&\text{for some}~k\neq a^1_\star,\\
 	p~&\text{for any}~a^1 \notin \{a^1_\star, k\}.
 \end{cases}\\
\end{aligned}
\end{equation}
Following the characterization of stationary policy in Lemma~\ref{lem:lb-stationary}, for one state $i^1\in\mathcal{X}^1$ the difference of rewards when choosing a suboptimal  action that leads to the transition $\gamma p_2$ of staying at its own state in $i^2_{(i^1,a^1)}$ instead of an optimal action  that leads to the transition $\gamma p_1$,  with the policy for all other states keeping the same will be
\begin{equation}\label{eq:stationary-cals}
\begin{aligned}
& \frac{1}{N}\cdot \frac{(1-\gamma)p_1\gamma}{(1-\gamma p_1)(2-\gamma)}-\frac{1}{N}\cdot \frac{(1-\gamma)p_2\gamma}{(1-\gamma p_2)(2-\gamma)}\\
 &=  \frac{1}{N}\cdot\frac{1-\gamma}{2-\gamma}\frac{p_1(1-\gamma p_2)-p_2(1-\gamma p_1)}{(1-\gamma p_1)(1-\gamma p_2)}\\
 &= \frac{1}{N}\cdot\frac{1-\gamma}{2-\gamma}\frac{p_1-p_2}{(1-\gamma p_1)(1-\gamma p_2)} \ge \frac{2}{N}\epsilon,
\end{aligned}
\end{equation}
where in the last inequality we use the choice of $p_1,p_2\in\{p,p',p^\star\}$, $p_1>p_2$, and the fact that $\epsilon\le 1/32\le \tfrac{1}{4(1+\gamma)^2(2-\gamma)}$. Consequently, in order to obtain an $\tfrac{1}{12}\epsilon$-approximate deterministic policy, one must choose the optimal action, i.e. $\pi(i) = k$ for case $(i)$ and $\pi(i) = a^1_\star$  for case $(ii)$ for a subset of $i\in\mathcal{I}\in[N]$ satisfying $|\mathcal{I}|\ge \tfrac{23}{24}N$.

Now the key argument follows from an information-theoretical lower bound for distinguishing between two binary variables with mean $\gamma p$ and $\gamma p^\star$, formally given as follows.

\newcommand{\mathrm{bin}}{\mathrm{bin}}

\begin{restatable}{lemma}{leminfo}\label{lem:information}
Given a random variable $X$ drawn uniformly randomly from the family $\{\mathrm{bin}(\gamma p),\mathrm{bin}(\gamma p^\star)\}$ where $p,p^\star$ are as defined in~\eqref{def:p}. When taking fewer than $T = \Omega(1/(1-\gamma)\epsilon^2)$ samples of $X$, any procedure with probability $1/4$ will make a wrong prediction on which binary random variable $X$ is.
\end{restatable}

 As an immediate corollary, one can show that for any algorithm $\mathcal{K}$ taking fewer than $T$ samples on $a^1_\star$ on any randomly permuted set of actions of a state $i^1$, it must fail to distinguish between case $(i)$ and case $(ii)$ in~\eqref{def:p} with probability $1/4$.

Now given any algorithm that takes fewer than $\Theta(NTK)$ deterministic~\footnote{Here deterministic means the algorithm takes fixed number of samples per state-action pair, regardless of the instance.} oblivious samples, we show the algorithm will not collect enough samples for a constant fraction of actions $a^1\in\calA_{i^1}$ of a constant fraction of states $i^1\in\mathcal{X}^1$. Thus, one can consider an adversarial instance in the family $\mathbf{M}$ that hides the best action uniformly randomly among the actions with insufficient samples. With constant probability the algorithm will output a suboptimal action for such $\Theta(N)$ states and output a suboptimal policy $\pi$ satisfying
 $V^\pi\le V^{\star}-\Theta(\epsilon)$ for some instance as we pick adversarially.
 By adjusting constants and combing with Lemma~\ref{lem:lb-mixing-time}, this implies any algorithm will need at least $\Omega(NKT) = \Omega(\At_{\mathrm{mix}}\epsilon^{-2})$ deterministic oblivious samples to find an $\epsilon$-optimal policy for all instances in the family.

 Finally, we note that our lower bound statement is applicable to any algorithms yielding deterministic policy and using deterministic oblivious sampling, which already matches our upper bound results in Section~\ref{sec:ub} nearly tightly. We present our lower bound under this setting in our main paper for clarity and simplicity. However, we believe one can extend the result to algorithms with randomized policies and using dynamic samples; we think these are interesting future directions to further strengthen the lower bound and discuss them in more detail in Appendix~\ref{app:lb-gen}.

 %
\section{Discussion}
\label{sec:disc}

In this paper, we have shown an $\Omega(\At_{\mathrm{mix}}\epsilon^{-2})$ sample complexity lower bound for AMDPs with mixing time  bound $t_{\mathrm{mix}}$, and a matching  upper bound (up to logarithmic and $\mathrm{poly}(1/\epsilon)$ factors) obtained through reduction to DMDPs . Our work suggest a few open directions which we believe would help clarify the structure of AMDPs and its connection with DMDPs:

\paragraph{Obtaining tight upper bound of sample complexity and runtime.} While the authors suspect that an $\widetilde{O}(\At_{\mathrm{mix}}\epsilon^{-2})$ upper bound on the required sample complexity may be attainable, it seems to require new ideas in leveraging the mixing structure of AMDP more directly, instead of reducing it to DMDPs. Further, it would be interesting to obtain algorithms with efficient running times as has been shown for DMDPs~\citep{SWWYY18} in certain $\epsilon$-regimes.
 \paragraph{Relaxing the mixing bound assumption.} In certain cases, assuming global mixing time bound for all policies, even for all deterministic stationary policies (as we do in the paper), can be restrictive. We ask if it is possible to obtain sample complexity dependence in terms of the mixing time of the optimal policy, or in terms of some alternative parameters like diameter~\citep{jaksch2010near}, or bias span~\citep{bartlett2012regal,fruit2018efficient} that can be smaller than $t_{\mathrm{mix}}$ for certain types of AMDPs.

\section*{Acknowledgment}
The authors thank Ron Amit and Lin F. Yang for helpful conversations. YJ was supported by Stanford Graduate Fellowship. AS was supported in part by a Microsoft Research Faculty Fellowship, NSF CAREER Award
 CCF-1844855, NSF Grant CCF-1955039, a PayPal research award, and a Sloan Research Fellowship.

\newpage

\arxiv{
\bibliographystyle{abbrvnat}


\section{Introduction}
Federated Learning (FL) \cite{mcmahan2017communication, kairouz2019advances, yang2019federated} is a relatively new and promising machine learning approach, emerging as a new paradigm of privacy-preserving machine learning.
It trains an algorithm across multiple clients (e.g., decentralized edge devices or servers holding local data samples) without exchanging their data samples.
In an FL system, data owners (participants) do not need to share raw data with the server.
Instead, participants jointly train an ML model by executing local training algorithms on their own private local data and only sharing model parameters with the parameter server.
This parameter server serves as a central aggregator to appropriately aggregate the local parameter updates and then share the aggregated updates with every participant.

While FL allows participants to keep their raw data local, recent works highlight and address the \textit{privacy} and \textit{robustness} concerns in FL.
To prevent potential privacy leakage from local parameter updates \cite{papernot2016semi}, local differential privacy (LDP) \cite{evfimievski2003limiting} has been adopted as a strong privacy guarantee in FL \cite{sun2020ldp,liuFedSelFederatedSGD2020, seifWirelessFederatedLearning2020a, truexLDPFedFederatedLearning2020} by locally adding perturbation to the updates.
Local differential privacy is a state-of-art paradigm facilitating secure analysis over sensitive data because of its strong assumption on adversary's background knowledge and smart setting of the privacy budget.
On the other hand, to avoid the adversarial examples \cite{yuanAdversarialExamplesAttacks2019, goodfellow2014explaining} and improve the adversarial robustness \cite{ dalvi2004adversarial}, researchers induce well-studied methods used in conventional ML such as bounding the norm of gradient updates or adding Gaussian noises \cite{sun2019can} for robust FL.

However, it is still not clear how LDP affects adversarial robustness in FL.
A few studies \cite{lecuyer2019certified, naseri2020toward} show that differential privacy may have positive effects on preventing adversarial examples in different settings.
Lecuyer et al. \cite{lecuyer2019certified} investigate a certified defense to adversarial examples in deep learning via a variant of differential privacy called PixelDP.
Naseri et al. \cite{naseri2020toward} present an empirical evaluation for the effect of (local) differential privacy on adversarial robustness in FL.
However, they do not have a theoretical basis to explain the effects of LDP on robustness in FL.
More importantly, all existing studies only indicate that the higher level of perturbation on training samples could lead to higher adversarial robustness, which we call \textit{positive effect} in this work;
it is intriguing to study whether there is also a \textit{negative effect} of LDP on adversarial robustness, i.e., the robustness may decrease along with the higher level of privacy.

To fill this gap, we attempt to develop a comprehensive understanding of the effects of local differential privacy on adversarial robustness in federated learning.
Specifically, we will show that a higher level of LDP (lower $\epsilon$) may not always lead to a higher level of adversarial robustness.
Given the increasing attention of LDP-based FL \cite{sun2020ldp,liuFedSelFederatedSGD2020, seifWirelessFederatedLearning2020a, truexLDPFedFederatedLearning2020},
clarifying the interplay between LDP and adversarial robustness in FL is significant since this is the first step towards a principled design of private and robust FL systems.

Our contributions in this work are three-fold.
\begin{itemize} [leftmargin=*, topsep=0pt]
\item To fill in the theoretical gap that whether local differential privacy benefits adversarial robustness, we show the theoretical evidence about the connection between local differential privacy and our proposed adversarial robustness called {$E_{e^\epsilon}$ - adversarial robustness} (Section 3).
\item We then study the mixed effects of local differential privacy on preventing adversarial examples by clarifying the connection between our proposed robustness definition and the ones defined in the literature.
We qualitatively show that LDP may also bring a negative effect on robustness, i.e., a higher level of privacy (lower $\epsilon$) can lead to lower adversarial robustness (Section 4).
\item We conduct experiments to verify how different privacy parameters of LDP affect the adversarial robustness in FL, which is in line with our theoretical analysis (Section 5).
\end{itemize}

\section{PROBLEM SETTING} \label{sec:problem_setting}

This work wants to learn about the effect of local differential privacy on adversarial robustness in federated learning.
Fig.\ref{fig:problem} shows the federated learning scenario we focus on.
The participants and the server want to train a model collaboratively.
In the training phase, due to some privacy concerns, the participants will download the global model, compute the local model, update local updates.
We suppose that each participant obeys the rule that adding local differential privacy using the same $\epsilon$ to its local data.
In the inference phase, the adversary tries to use adversarial examples to attack the model. We constrain the adversarial examples to be norm-bounded.

Overall, our work aims to

\begin{enumerate}
    \item Theoretically dig the theoretical evidence about why LDP brings the positive effect.
    \item Theoretically find the overall effect of local differential privacy on adversarial robustness.
    \item Empirically see the change of adversarial robustness on different settings of $\epsilon$.
\end{enumerate}

Here we consider a classification task in federated learning with data $(x, y) \in \mathcal{X} \times \mathcal{Y}(\mathcal{Y} = \{1,...,C\}$) from a distribution D.
We assume the existence
of a \textit{labeling oracle} $\mathcal{O} : \mathcal{X} \rightarrow \mathcal{Y} \cup \{\bot\}$ that maps any input in $\mathcal{X}$ to its true label, or to the “un-labelable”. Take a digit classification task for example, the oracle $\mathcal{O}$ corresponds to human labeling of any image as a digit.
Note that for $(x, y) \sim D$, we always have $y = \mathcal{O}(x)$.
The goal is to learn a classifier $f$: $\mathcal{X} \rightarrow \mathcal{Y}$ that agrees with the oracle’s labels.

\begin{figure}[tb]
  \centering
  \includegraphics[width=0.45\textwidth]{fig_problem.png}
  \caption{Problem setting.}
  \label{fig:problem}
\end{figure}

\section{Theoretical Evidence of Positive Effect of LDP} \label{sec:evi}

To find the theoretical evidence of why LDP brings a positive effect to adversarial robustness, we first find the connection between local differential privacy definition and adversarial robustness.
We notice that randomization is the common keyword of both local differential privacy and adversarial robustness.
While the core technology of local differential privacy is to inject noises based on the definition, randomization has also proven effective in adversarial defense strategies \cite{liu2018towards}.
The technologies used are to inject random noise (both during training and inference phases) inside the machine learning network architecture,i.e.at a given layer of the network.
Thus, the intuition is that there would be a connection between noises we add in local differential privacy and randomization we apply for generating the adversarial examples.

We find that \cite{pinot2019unified} highlights some links between Renyi differential privacy \cite{mironov2017renyi} and generalized adversarial robustness \cite{pinot2019unified}.
This presents a unified view towards both but doesn't further discuss the practical meaning. It only cares about the generalized differential privacy and generalized adversarial robustness which cannot be used when we discuss the effect of LDP.
We then want to find a type of adversarial robustness definition, which we can see as a unified view of local differential privacy.
We first give the definition of local differential privacy.

\begin{definition}
Local differential privacy \cite{evfimievski2003limiting}: A randomized algorithm (mechanism) $\mathcal{M}: \mathcal{X} \rightarrow \mathcal{Y}$ is $\epsilon$-locally differentially private if for any $x, x' \in \mathcal{X}$ and $v \in \mathcal{Y}$, we have
\begin{equation}
Pr[\mathcal{M}(x) = v] \leq e^\epsilon Pr[\mathcal{M}(x') = v]
\end{equation}
where lower $\epsilon$ means higher privacy degree.
\end{definition}

According to the definition of local differential privacy, we propose a self-defined adversarial robustness named $E_{e^\epsilon}$ - adversarial robustness.

\begin{definition}
$E_{e^\epsilon}$ - adversarial robustness. A randomized classifier M is said to be $E_{e^\epsilon}$ - robust if $P_{x\sim D_\mathcal{X}}[\exists x' \in B(x, \alpha)$ $s.t$ $E_\lambda(\mathcal{M}(x'),$ $\mathcal{M}(x))$ $> 0] = 0$ where $\lambda = e^\epsilon$ and $B(x, \alpha) = \{x' \in \mathcal{X}$ $s.t$ $d_\mathcal{X}(x, x') \leq \alpha$, $\alpha = \infty\}$.
\end{definition}

Then we can see the connection between local differential privacy and $E_{e^\epsilon}$ - adversarial robustness.

\begin{theorem}
An algorithm $\mathcal{M}$ is $E_{e^\epsilon}$ - robust if and only if $\mathcal{M}$ is $\epsilon$ - local differential private.
\end{theorem}

\begin{proof}
We can rewrite the definition of local differential privacy as follows.

Let $\epsilon > 0$, $(\mathcal{X}, d_\mathcal{X})$ an arbitrary (input) metric space, and $\mathcal{Y}$ the output space. A probabilistic mapping $\mathcal{M}$ from $\mathcal{X}$ to $\mathcal{Y}$ is called $\epsilon$ - local differential private if for any $x, x'$, one has
\begin{equation}
E_\lambda(\mathcal{M}(x), \mathcal{M}(x'))  = 0
\end{equation}
where $\lambda = e^\epsilon$. $E_\lambda$ here is $E_\lambda$-divergence (hockey-stick divergence) which is a special type of $f$- divergence with $f_\lambda(t)=(t-\lambda)^+$.

We can prove the definition is a equipment of the original definition by:
\begin{equation}
\begin{split}
E_{e^\epsilon}(\mathcal{M}(x), \mathcal{M}(x')) &= 0 \\
(\frac{Pr[\mathcal{M}(x) = v]}{Pr[\mathcal{M}(x') = v]} - e^\epsilon)^+ &= 0 (v \in \mathcal{Y})\\
\frac{Pr[\mathcal{M}(x) = v]}{Pr[\mathcal{M}(x') = v]} &\leq e^\epsilon
\end{split}
\end{equation}

Comparing the definition of above local differential privacy and $E_{e^\epsilon}$ - adversarial robustness, we can get the conclusion that an algorithm $\mathcal{M}$ is $E_{e^\epsilon}$ - robust if and only if $\mathcal{M}$ is $\epsilon$ - local differential private.
\end{proof}

This conclusion indicates that applying local differential privacy improves adversarial robustness to some extent.

\section{THE EFFECT OF LOCAL DIFFERENTIAL PRIVACY ON ADVERSARIAL ROBUSTNESS} \label{sec:effect}

Section \ref{sec:evi} already shows that local differential privacy and $E_{e^\epsilon}$ - adversarial robustness are equivalent.
However, there is a gap between $E_{e^\epsilon}$ - adversarial robustness and adversarial robustness in the literature.
This section will firstly clarify the comprehensive definition of norm-bounded adversarial robustness we focus on and then qualitatively study how local differential privacy affects the norm-bounded adversarial robustness.
We then find that besides positive effects, local differential privacy can also bring negative effects on norm-bounded adversarial robustness.

\subsection{Definition of Adversarial Robustness}

The definition of adversarial robustness depends on the method of generating adversarial examples.
At its broadest, the definition of an adversarial example consists in any adversarial failure induced in a classifier \cite{goodfellow2014explaining}.
Tramèr et al. \cite{tramer2020fundamental} summary two types of adversarial examples: sensitivity adversarial examples and invariance adversarial examples.

Our work focuses on adversarial robustness defined with norm-bounded adversarial examples, which are generally used for evaluating adversarial robustness.
Norm-bounded adversarial examples are to constrain the amount of change an attacker is allowed to make to the input. The change of input is measured by the $p$-norm of the change denoted by $\lVert x^* - x \rVert_p$. Thus, we get the definition of both norm-bounded sensitivity adversarial examples and norm-bounded invariance adversarial examples.

\textbf{Definition 1} (Norm-bounded Sensitivity Adversarial Examples).
Given a classifier $f$ and a correctly classified input $(x, y) \sim D$ (i.e.,
$\mathcal{O}(x) = f(x) = y$), an "$\alpha$-bounded sensitivity adversarial
example is an input $x^* \in \mathcal{X}$ such that:
\begin{enumerate}
    \item $f(x^*) \neq f(x)$.
    \item $\lVert x^* - x \rVert_p \leq \alpha$.
\end{enumerate}

\textbf{Definition 2} (Norm-bounded Invariance Adversarial Examples).
Given a classifier $f$ and a correctly classified input $(x, y) \sim D$ (i.e.,
$\mathcal{O}(x) = f(x) = y$), an "$\alpha$-bounded invariance adversarial
example is an input $x^* \in \mathcal{X}$ such that:
\begin{enumerate}
    \item $f(x^*) = f(x)$.
    \item $\mathcal{O}(x^*) \neq \mathcal{O}(x)$, and $\mathcal{O}(x^*) != \bot$
    \item $\lVert x^* - x \rVert_p \leq \alpha$.
\end{enumerate}

Thus, we say that a model $f$ is robust to $p$-norm attacks on a given input $x$ if for all $x^* s.t. \lVert x^* - x \rVert_p \leq \alpha$, we have
\begin{enumerate}
    \item $f(x) = \mathcal{O}(x) = y$.
    \item $f(x^*) = \mathcal{O}(x^*) = y$.
\end{enumerate}

\subsection{The Effect of Local Differential Privacy on Adversarial Robustness} \label{sec:eff}

In this section, we tend to qualitatively and overall study how local differential privacy affects the norm-bounded adversarial robustness we focus on.

Combining with the result of the section \ref{sec:evi}, we can see that local differential privacy is equivalent to $E_{e^\epsilon}$ - adversarial robustness using a unified view. We then consider the exact effect of local differential privacy on norm-bounded adversarial robustness. That is, we will discuss the connection and difference between $E_{e^\epsilon}$ - adversarial robustness and norm-bounded adversarial robustness towards sensitivity adversarial examples and invariance adversarial examples.

Observing the definition of $E_{e^\epsilon}$ - adversarial robustness, we can see the biggest difference with norm-bounded adversarial robustness is the value of $\alpha$. Norm-bounded adversarial robustness uses $\alpha$ to constrain the change of input. $E_{e^\epsilon}$ - adversarial robustness here instead uses the parameter $\epsilon$ to do the similar work. We can see that $\epsilon$ is also to bound the difference of $\mathcal{M}(x)$ and $\mathcal{M}(x')$.
That is, the smaller the $\epsilon$ is, the smaller the distribution divergence of inputs is.
We then seek how the $\epsilon$ here in the $E_{e^\epsilon}$ - adversarial robustness affects the norm-bounded adversarial robustness.
Note that $\epsilon$ is actually induced from the definition from LDP, we return to the mechanism of local differential privacy. We usually add some noises to make our mechanism satisfy the definition. The extent of noising (roughly the same with the $\alpha$ we use in adversarial examples) is in inverse proportion to the value of $\epsilon$. In conclusion, we have:

\begin{quote}
    The effect of $\epsilon$ in $E_{e^\epsilon}$ - adversarial robustness is inverse proportion to the effect of $\alpha$ in norm-bounded adversarial robustness.
\end{quote}

\begin{figure}[tb]
  \centering
  \includegraphics[width=0.5\textwidth]{fig_adversarial.png}
  \caption{Generate adversarial examples with different settings of p-norm ball radius.}
  \label{fig:adversarial}
\end{figure}

For knowing the effect of $\alpha$ in norm-bounded adversarial robustness, we can mock the generation of adversarial examples.
Fig.\ref{fig:adversarial} shows three possibilities. The input space is (ground-truth) classified into the solid brown region and the blue region. The brown dotted line is the decision boundary. Given a data point (the central black point) $x$, we know its true classification and want to use it to generate some adversarial examples. Due to the norm used to define “small” adversarial perturbations is misaligned with the labeling oracle $\mathcal{O}$, we have (as show in Fig.\ref{fig:adversarial} - a, b):
\begin{equation*}
    \alpha_1 := \min{\lVert \Delta \rVert : \mathcal{O}(x + \Delta) \notin \{y, \bot\} }
\end{equation*}
\begin{equation*}
    \alpha_2 := \max{\lVert \Delta \rVert : \mathcal{O}(x + \Delta) \in \{y, \bot\} }
\end{equation*}
Then the adversarial examples with $x^*$ $s.t. \lVert x^* - x \rVert \leq \alpha_1$ we generate broaden the oracle area and can be used to strengthen the adversarial robustness. Thus, with $\alpha$ $s.t.$ $0 \leq \alpha \leq \alpha_1$ increases, the bigger oracle area we broaden, the higher adversarial robustness. In extreme cases with $\alpha = 0$, the solid brown area except $x$ can be a potential successful attack. Similarly, the adversarial examples with $x^*$ $s.t. \lVert x^* - x \rVert \geq \alpha_2$ we generate induces overly - robustness due to the presence of invariance adversarial examples \cite{tramer2020fundamental}. Thus, with $\alpha$ $s.t.$ $\alpha \geq \alpha_2$ increases, the lower adversarial robustness. In extreme cases with $\alpha = \infty$ which is definitely impractical, the whole dataset will be corrupted.
Intuitively, there should be a balance area that can benefit the adversarial robustness the best when we choose radiuses like $\alpha_3$ $s.t.$ $\alpha_1 \leq \alpha_3 \leq \alpha_2$.
To be concluded, as the radius of $p$-norm ball $\alpha$ increases, the adversarial robustness will first increase, access the balance area, and then decrease.

Based on the above relationship between $\alpha$ and $\epsilon$ we can have the conclusion which is:

\begin{quote}
    While privacy degree increases with $\epsilon$ decreasing, adversarial robustness firstly increases, access the balance area, then decreases.
\end{quote}

\section{EXPERIMENTS AND EVALUATION} \label{sec:exp}

Section \ref{sec:effect} gives the intuition about the relationship between local differential privacy and adversarial robustness.
To verify this intuition, we implement an experimental test to see the adversarial robustness in different privacy budget settings.

\subsection{Experimental Setup}

We experiment with different settings of $\epsilon$ in FL and observe the change of norm-bounded adversarial robustness on different $\epsilon$.

We use two datasets for our experiments:
1) MNIST \cite{lecun1998gradient}, to ease comparisons, and 2) CIFAR10 \cite{hope2017learning}, to extend the representativeness of our evaluation.
We use the lightweight CNN model \cite{he2016deep} for training.
All experiments use PyTorch \cite{paszke2017automatic}.
Our source code is available in Github \footnote{https://github.com/iris0305/privacy\_robust}.

\subsection{Adversarial Robustness Measurements to Adversarial Example}

Goodfellow et al. \cite{goodfellow2014explaining} proposed an efficient single iteration method, using backpropagation, to compute an $l_{\infty}$ bounded adversarial perturbation for a given input $x$ called Fast Gradient Sign Method (FGSM):

\begin{equation}
    x_{adv} = x + \alpha sign({\nabla}_x\mathcal{L}(\theta, x, y))
\end{equation}

where $y$ is the true class of input $x$, $\theta$ is the model parameters, ${\nabla}_x\mathcal{L}(\theta, x, y)$ computes the gradient of a cost function with respect
to $x$. FGSM serves as a simple yet effective way of testing the robustness of a neural network.

From \cite{yu2019interpreting}, we know that models are not always robust -- the predictions of a model on clean and noisy inputs are not always the same and can diverge to a large extent with small adversarial noises. As such, given a feasible perturbation set, the average of Kullback–Leibler divergences between the original predictions and the adversarial predictions could be used to denote the model’s vulnerability degree (i.e., the inverses of model robustness). Thus, we can calculate the average Kullback–Leibler divergence between two predictions on original inputs and adversarial inputs with perturbations in a defined range. The formal robustness could be estimated by:

\begin{equation}
    \psi(x) = \frac{1}{{\rm avg} \,  D_{KL}(f(x), f(x_{adv}))}
\end{equation}

\subsection{Experiment Results} \label{sec:expe1}

We apply several settings of $\alpha$ for measuring the norm-bounded adversarial robustness. We use the average Kullback–Leibler divergence between two predictions on original inputs and adversarial inputs with perturbations to measure the norm-bounded adversarial robustness. For each setting of $\alpha$, we run experiments five times and calculate the average for the reason that local differential privacy is based on randomization.
Fig.\ref{fig:expe1} and Fig.\ref{fig:expe2} show the results when the dataset are MNIST and CIFAR10, respectively.

From Fig.\ref{fig:expe1} and Fig.\ref{fig:expe2}, we can see that both results for MNIST and CIFAR10 agree with the expectation in section \ref{sec:eff}. While privacy degree decreases with epsilon $\epsilon$ (x-axis) increasing, adversarial robustness evaluated based on KL divergence (y-axis) firstly increases, access the balance area, then decreases. Note that in the middle range, we have a balance area since there induces mixed "good" and "bad" adversarial examples as showed in Fig.\ref{fig:adversarial} - c.

\begin{figure}[tb]
  \centering
  \includegraphics[width=0.5\textwidth]{fig_expe2.png}
  \caption{Experiment results for MNIST.}
  \label{fig:expe1}
\end{figure}

\begin{figure}[tb]
  \centering
  \includegraphics[width=0.5\textwidth]{fig_expe1.png}
  \caption{Experiment results for CIFAR10.}
  \label{fig:expe2}
\end{figure}

\section{CONCLUSION} \label{sec:Future Work}

This work uses theoretical analysis and empirical proof to study the exact effects of local differential privacy on adversarial robustness in federated learning.
We find that local differential privacy has the potential for both positive and negative effects, which means that a higher level of local differential privacy (lower $\epsilon$) can bring higher or lower adversarial robustness.
For future work, we will further put forward more theoretical proof. We will also make a more comprehensive empirical plan.

\bibliographystyle{ACM-Reference-Format}