\section{Lower Bounds on Policy}
\label{sec:lower bound}

\begin{lemma}
Suppose $\cM=(\cS, \cA, P, \gamma, \br)$ is a DMDP with an sampling oracle. Suppose $\pi$ is a given policy.
Then there is an algorithm, halts in $\wt{O}((1-\gamma)^{-3}\epsilon^{-2}|\cS|)$ time, outputs a vector $\bv$ such that, with high probability,
$\|\bv^\pi - \bv\|_\infty \le \epsilon$.
\end{lemma}
\begin{proof}
The lemma follows from a direct application of Theorem~\ref{thm:high precision}.
\end{proof}

\begin{remark}
	Suppose $|\cA|= \wt{\Omega}(1)$. 
	Suppose there is an algorithm that obtains an $\epsilon$-optimal policy with $Z$ samples, then the above lemma implies an algorithm for obtaining an $\epsilon$-optimal value function with $Z + \wt{O}((1-\gamma)^{-3}\epsilon^{-2}|\cS|)$ samples.
	By the $\Omega((1-\gamma)^{-3}\epsilon^{-2}|\cS||\cA|)$ sample bound on obtaining approximate value functions given in \cite{azar2013minimax}, the above lemma implies a 
	\[
	Z = \Omega((1-\gamma)^{-3}\epsilon^{-2}|\cS||\cA|) - \wt{O}((1-\gamma)^{-3}\epsilon^{-2}|\cS|) = \Omega((1-\gamma)^{-3}\epsilon^{-2}|\cS||\cA|)
	\] sample lower bound for obtaining an $\epsilon$-optimal policy. 
	
	
\end{remark}
{"config": "arxiv", "file": "1806.01492/low_bounds.tex"}