\begin{table}[htpb]
\centering
 \begin{tabular}{|c|c|}
 \hline
 {\bf exploration method} & {\bf expected episodes to learn} \\
 \hline
 optimal & $\Theta(N)$ \\
 pure exploitation & $\infty$ \\
 myopic & $\infty$ \\
 dithering & $\Theta(2^N)$ \\
% curiosity-driven & $\Theta(N^2)$ \\
 optimistic & $\Theta(N)$ \\
 randomized & $\Theta(N)$ \\
 \hline
 \end{tabular}
 \caption{Expected number of episodes required to learn an optimal policy for Example \ref{ex:grid}.}
\label{tab:grid}
\end{table}
exploration method expected episodes to learn
optimal
pure exploitation
myopic
dithering
optimistic
randomized Θ N
( )
∞
∞
Θ 2N
( )
Θ N
( )
Θ N
( )