\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}
