% outstanding issues/questions: % - we don't discuss the implicit assumption Plan must work % on``sub-worlds'' % - fix LOS figure such that x's are more visible \documentclass{article} \usepackage{graphics} \usepackage{icml2003} \usepackage{times} \usepackage{amsmath} \newtheorem{thm}{Theorem}[section] \newtheorem{lem}[thm]{Lemma} \newcommand{\qed}{\rule{5pt}{7pt}\bigskip} \title{Exploration in Metric State Spaces} \begin{document} \twocolumn[ \icmltitle{Exploration in Metric State Spaces} \icmlauthor{Sham Kakade}{sham@gatsby.ucl.ac.uk} \icmladdress{Gatsby Unit \, University College London \, London, England} \icmlauthor{Michael Kearns}{mkearns@cis.upenn.edu} \icmladdress{Department of Computer and Information Science\, University of Pennsylvania, Philadelphia, Pennsylvania} \icmlauthor{John Langford}{jcl@cs.cmu.edu} \icmladdress{Math.\ Sci.\ Dept.\, I.B.M. T.~J.~Watson Research Center, Yorktown Heights, NY 10598} \vskip 0.3in \vskip 0.3in ] \begin{abstract} We present metric-$E^3$, a provably near-optimal algorithm for reinforcement learning in Markov decision processes in which there is a natural {\em metric\/} on the state space that allows the construction of accurate local models. The algorithm is a generalization of the $E^3$ algorithm of Kearns and Singh, and assumes a black box for approximate planning. Unlike the original $E^3$, metric-$E^3$ finds a near optimal policy in an amount of time that does not directly depend on the size of the state space, but instead depends on the {\em covering\/} number of the state space. Informally, the covering number is the number of neighborhoods required for accurate local modeling. \end{abstract} \vspace{-0.15in} \section{Introduction, Motivation, and Background} \label{section:intro} Recent years have seen the introduction and study of a number of representational approaches to Markov Decision Processes (MDPs) with very large or infinite state spaces. These include the broad family known as function approximation, in which a parametric functional form is used to approximate value functions, and direct models of the underlying dynamics and rewards, such as factored or Dynamic Bayes Net (DBN) MDPs. For each of these approaches, there are now at least plausible heuristics, and sometimes formal analysis, for problems of planning \cite{Approxplan} and learning. Less studied and more elusive has been the problem of {\em global exploration\/}, or managing the exploration-exploitation trade-off. Here the goal is to learn a (globally) near-optimal $T$-step policy in an amount of time that has no direct dependence on the state space size, but only on the complexity of the chosen representation. Global exploration was first solved in the deterministic finite-state setting \cite{sven,thrun} and then progress slowed. It is only recently that provably correct and efficient algorithms for exploration in small nondeterministic state spaces became known (such as the $E^3$ algorithm\cite{E3} and its generalizations\cite{Rmax}). This approach has been generalized to factored MDPs under certain assumptions \cite{DBN}, but there remain many unresolved questions regarding efficient exploration in large MDPs, including whether model-based approaches are required~\footnote{ Recent work on gradient methods for approximate planning (\cite{grad1,grad2}) do not address exploration in the strong sense of interest here, but instead examines convergence to policies which small amounts of {\em random\/} exploration cannot improve (local optimality). In general, effective exploration may require the careful {\em planning\/} of a long sequence of steps that might never be encountered by a random walk. See \cite{CPI} for a further discussion.}. In general, it is intuitively clear that any general exploration algorithm has a polynomial dependence on the size of the state (see \cite{sham} for a more formal statement). Hence, to obtain near-optimal algorithms with sub-linear dependence on the size of the state-space further assumptions and restrictions on the MDP must be made. The factored $E^3$ algorithm \cite{DBN} considers one restriction where the MDP are represented in terms of a factored graph ({\em ie\/} a dynamic Bayes net). Here, the number of steps the agent must act in the MDP in order to obtain a $T$-step near optimal policy is polynomial in the representation size of the factored graph. In this work, we examine the problem of exploration in environments in which there is a {\em metric\/} on state-action pairs with the property that ``nearby'' state-actions can be useful in predicting state-action dynamics. Such conditions are common for navigation or control problems, but may be more broadly applicable as well. Given sufficient ``nearby'' experience to predict outcomes, we have an implicit nonparametric model of the dynamics in a neighborhood of the state-action space. These implicit models can be ``pieced together'' and used for planning on a subset of the global space. One natural approach in the large-state space setting is aggregate state methods which group states together and assume Markov dynamics on these aggregate states \cite{Dean,aggregation}. Clearly, this approach is useful only if a compatible set of aggregate states can be found which preserve the Markov dynamics on these aggregate states and where the size the aggregate state space is considerably smaller than that of the underlying state space. A benefit of this approach is that planning under this model can be done with traditional dynamic programming approaches on the aggregate states. Unfortunately, in many navigation domains, it appears that nontrivial state aggregation often destroys the Markov assumption required for planning in aggregate state methods (and we provide one such example later). The local modeling assumption is \emph{not} equivalent to an aggregate state method since we do not group any states together and do not assume a Markov property holds for aggregate states. In fact, under this assumption (as in factored $E^3$), the size of the state space is not diminished in any real way, unlike in aggregate state methods. Hence, the computational problem of planning is still with us strongly. As with factored $E^3$, we assume a ``black box'' planning algorithm to abstract away the difficulty of planning from that of exploration. This assumption is not meant to trivialize the planning problem, but is made in order to isolate and quantify the difficulty of exploration. Given the ability to plan, we prove that the local modeling assumption implies the time required for global exploration depends only on the metric resolution and {\em not\/} on the size of the state space. More precisely, we give a generalization of the $E^3$ algorithm for metric MDPs which learns a (globally) approximately optimal $T$-step policy in time depending only on the {\em covering numbers\/}, a natural and standard notion of the resolution required for local modeling under the metric. Metric MDPs are a natural complement to more direct parametric assumptions on value functions and dynamics. These results provide evidence that, as for factored environments\cite{DBN}, effective exploration mechanisms are available for metric MDPs. \vspace{-0.15in} \section{Definitions and Assumptions} \label{sections:defs} \vspace{-0.15in} We work in the standard MDP setting. Let \( P(s'|a,s) \) be the probability of a state \( s' \) given an action \( a \) and state \( s \). Let \( R(s) \) be the reward received in state $s$. For simplicity, assume that all rewards are deterministic and fall in the interval $[0,1]$. Define \( V_M (\pi ,s)\equiv E_{(s_1,s_2,\ldots s_T)\sim \pi ,s,M}\frac{1}{T}\sum _{t=1}^{T}R(s_{t}) \) to be the average reward received over \( T \) steps starting from state \( s \) while acting under $\pi$ in MDP $M$. We first formalize the assumption that there is a notion of distance that permits local modeling of dynamics. Thus, let $d((s',a'),(s,a))$ measure the ``distance'' between two state-action pairs. The results require that this metric obey $d((s,a),(s,a)) = 0$ for all $(s,a)$, and symmetry (\emph{i.e.,} $d((s,a),(s',a')) = d((s',a'),(s,a))$ for all $(s,a),(s',a')$), but they do \emph{not} require the triangle inequality. This is fortunate since demanding the triangle inequality limits the applicability of the notion in several natural scenarios. Let $t_{\mbox{metric}}$ denote the time required to evaluate the metric. We now provide a standard definition of coverings under a metric. An {\em $\alpha$-cover\/} is a set $C$ of state-action pairs with the property that for any $(s,a)$, there exists $(s',a') \in C$ such that $d((s,a),(s',a')) \leq \alpha$. Let $N(\alpha)$ be the size of the \emph{largest minimal} $\alpha$-cover --- that is, the largest $\alpha$-cover $C$ such that the removal of any $(s,a)$ would render $C$ no longer a cover. Our first assumption is that the metric permits local modeling of dynamics of an MDP $M$ with transition model $P$ and reward function $R$: \textbf{Local Modeling Assumption.} There exists an algorithm \emph{Model} for the MDP $M$ such that, for any $(s,a)$, if \emph{Model} is given $m$ transitions $(s',a')\rightarrow s''$ and rewards $R(s')$ distributed in accordance with $M$ and in which all $d((s,a),(s',a')) \leq \alpha $, then \emph{Model} outputs a state $\hat{s} \sim \hat{P}(\hat{s}|s,a)$ and a reward $\hat{R}$, where \emph{ $\sum_{\hat{s}}|\hat{P}(\hat{s}|s,a) - P(\hat{s}|s,a)|\leq \alpha$, } and $|R(\hat{s}) - \hat{R}| \leq \alpha$. Let $t_{\mbox{model}}$ be the maximum running time of \emph{Model}. Thus, with a sufficient number $m$ of local state-action experiences, \emph{Model} can form an accurate approximation of the local environment. Note that there is {\em no\/} requirement that a {\em destination\/} state $\hat{s}$ be in the neighborhood of $(s,a)$ --- we ask only that nearby state-actions permit generalization in next-state distributions, not that these distributions be on nearby states. The next subsection provides natural examples where the Local Modeling Assumption can be met, but we expect there are many rather different ones as well. In addition to an assumption about the ability to build local (generative) models, we need an assumption about the ability to use such models in planning. \textbf{Approximate Planning Assumption.} There exists an algorithm, \emph{Plan}, which given a generative model for an unknown MDP $M$ and a state $s$, returns a policy \( \pi \) whose average reward \( V _{M}(\pi ,s) \) satisfies $V _{M}(\pi ,s)>V _{M}(\pi ^{*},s)-\beta$, where \( \pi ^{*} \) is the optimal $T$-step policy from $s$. Let $t_{\mbox{plan}}$ upper bound the running time of \emph{Plan} and $c_{\mbox{gen}}$ upper bound the calls to the generative model. Note that the Local Modeling Assumption does not reduce the state space size, so for an arbitrary and large MDP, great computational resources may be required to meet the Approximate Planning Assumption. The purpose is not to falsely diminish the difficulty of this task, but to abstract it away from the problem of exploration-exploitation. The same approach was necessary in analyzing factored-$E^3$. There are at least three broad scenarios where this assumption might be met. The first is settings where specialized planning heuristics can do approximate planning due to strong parametric constraints on the state dynamics. For example, the recent work on planning heuristics for factored MDPs is of this form. The second is the {\em sparse sampling\/} \cite{Sparse} approach, in which it has been shown that the Approximate Planning Assumption can in fact be met for arbitrary finite-action MDPs by a policy that uses a generative model as a subroutine. Here the sample complexity $c_{\mbox{gen}}$ is exponential in $T$ per state visited (see \cite{Sparse}), but has {\em no\/} dependence on the state space size. The third setting requires a regression algorithm that is capable of accurately estimating the value of a given policy. This algorithm can be used iteratively to find a near-optimal policy \cite{CPI}. At a high level, then, we have introduced the notion of a metric over state-actions, an assumption that this metric permits the construction or inference of local models, and an assumption that such models permit planning. We believe these assumptions are broadly consistent with many of the current proposals on large state spaces. We now provide an example that demonstrates the role of covering numbers, and then show that these assumptions are sufficient for solving the exploration-exploitation problem in time depending not on the size of the state space, but on the (hopefully much smaller) covering numbers under the metric. \subsection{An Example} We can imagine at least two natural scenarios in which the Local Modeling Assumption might be met. One of these is where there is sufficient sensor information and advance knowledge of the expected effects of actions that the local modeling assumption can be satisfied even with $m=1$. As a simple example, people can typically predict the approximate effects of most physical actions available to them immediately upon entering a room and seeing its layout and content (e.g., if I go left I will exit through that door; if I go straight I will hit that wall). They could not make such predictions for unfamiliar distant rooms. Consider the MDP where the state space is the Euclidean maze world shown in Figure \ref{fig-maze}.(a), and where the agent is equipped with a vision sensor. In this world, it is plausible that the local dynamics can be predicted at any ``seen'' location. To apply this analysis, we must first specify a metric. The obvious choice is \( d_{\textrm{sight}}((s,a),(s',a'))=0 \) if there exists line-of-sight between \( s \) and \( s' \) and \( \infty \) otherwise. Note that this metric satisfies symmetry, but not the triangle inequality (which would be somewhat unnatural in this setting). For any $\alpha \geq 0$, the covering number $N(\alpha)$ is the maximum number of points which can be positioned in the space so that no pair have line-of-sight. One maximal set is given by the dots in Figure \ref{fig-maze}.(b). Note that even though this a continuous state space, the covering number is much smaller, and naturally determined by the geometric properties of the domain. \begin{figure} {\centering (a)\resizebox*{0.27\columnwidth}{!}{\includegraphics{maze.eps}} (b)\resizebox*{0.27\columnwidth}{!}{\includegraphics{cover.eps}} (c)\resizebox*{0.27\columnwidth}{!}{\includegraphics{metric_cover_2.eps}} } \caption{\label{fig-maze} (a) a maze world (b) a largest minimal cover for the line-of-sight metric (c) a largest minimal cover for the line of sight + Euclidean distance metric. } \end{figure} It is unrealistic to assume that local dynamics are modeled at distant locations as well as near locations which implies that modeling error grows with distance. In this case, a reasonable alternative is to define \( d((s,a),(s',a'))=d_{\textrm{sight}}((s,a),(s',a'))+cd_{\textrm{euclidean}}((s,a),(s',a'))\) where \( c \) is a constant controlling the rate of modeling error with Euclidean distance. Using this metric, the covers shown in Figure \ref{fig-maze}.(c) might naturally arise. Note that (in general) we are free to use actions as well as states in defining the metric. The above examples are applicable to the $m=1$ case of the Local Modeling Assumption. The second natural case is the more general ``learning'' setting, in which the next-state dynamics permit some parameterization that is smooth with respect to the distance metric, thus allowing a finite sample of an environment to provide enough data to fit a parametric next-state distribution for the neighborhood. For instance, if reward appeared stochastically in some region, it might be necessary to visit nearby states a number of times before this distribution is learned. Alternatively, the dynamics could be different in different parts of the state space. For instance, a skier moving down a hill has dynamics dependent on the terrain conditions, such as slope, snow type, and other factors. \begin{figure} {\centering \resizebox*{0.9\columnwidth}{!}{\includegraphics{instability.eps}} } \caption{\label{fig-noagg} An example showing how simple state space aggregation does not work because the precise location within the aggregate state $C_1$ influences the next (aggregate) state outcome of an action (to $C_2$ or $C_3$).} \end{figure} Incidentally, Figure \ref{fig-noagg} illustrates the reason why standard state space aggregation techniques \cite{Dean} do not work here. In particular, for partitioning induced by a cover on a Euclidean spaces there exist ``corners'' where 3 (or more) sets meet. When taking actions ``toward'' this corner from within one of the sets, the distribution over the next aggregate state set is inherently unstable. \vspace{-0.15in} \section{Metric-\protect\( E^{3}\protect \)} \vspace{-0.15in} The algorithm, Metric-\(E^{3}\), is a direct generalization of the $E^3$ algorithm\cite{E3}. We first outline this original algorithm. A crucial notion in $E^3$ is that of a ``known'' state --- a state visited often enough such that the dynamics and rewards are accurately modeled at this state. When the agent is not in the current set of known states, the agent wanders randomly to obtain new information. While at a known state, it must decide whether to explore or exploit --- a decision which can be made efficiently. Intuitively, the decision to explore is made by determining how much potential reward the agent can obtain by ``escaping'' the known states to get maximal reward elsewhere. If this number is sufficiently large, the agent explores. This number can be computed by \emph{planning} to ``escape'' in a fictitious MDP $M_{\textrm{explore}}$ which provides maximal reward for entering an unknown state. The crucial step in the proof of $E^3$ is showing that either the agent exploits for near optimal reward, or it can explore {\em quickly\/}, which results in increasing the size of the set of known states. Since the size of the known set is bounded, the algorithm eventually exploits and obtains near optimal reward. Metric $E^3$ has a few key differences. Here, a ``known'' state-action is a pair $(s,a)$ meeting the antecedent of the Local Modeling Assumption --- namely, any pair $(s,a)$ for which the algorithm has obtained at least $m$ $\alpha$-close experiences $(s',a',s'',R(s''))$. Unlike in $E^3$, our algorithm does not explicitly enumerate this set of known states, but rather is only able to decide if a particular state-action is known. Thus, in the most general version of our algorithm, our model of the MDP is represented simply by a list of all prior experience. As in the original $E^3$, a key step in Metric-$E^3$ is the creation of the {\em known\/} MDP --- a model for just that part of the global MDP that we can approximate well. Here the known MDP at any moment is given as a generative model that ``patches together'' in a particular way the generative models provided by the planning algorithm at known states. More precisely, the {\em approximate known MDP generative model\/} takes any state-action $(s,a)$ and a flag bit {\em exploit} and operates as follows: \begin{enumerate} \item If $(s,a)$ is not a known state-action, output ``fail'' and halt. \item Else give $(s,a)$ and the $m$ prior experiences $(s',a',s'',R(s''))$ in the $\epsilon$-neighborhood of $(s,a)$ to algorithm \emph{Model}; let the resulting outputs be $\hat{s}$ and $\hat{r}$. \item If {\em exploit} is 1, set $r \leftarrow \hat{r}$ and $q \leftarrow 0$; otherwise $r \leftarrow 0$ and $q \leftarrow 1$. \item If for some action $\hat{a}$, the pair $(\hat{s},\hat{a})$ is itself a known state-action, output $\hat{s}$ and $r$ and halt. \item Else output a special state $z$ and reward $q$ and halt. \end{enumerate} Intuitively, we have described a generative model for two MDPs with identical transition dynamics, but differing rewards according to the value of the {\em exploit\/} bit. In both models, all transitions that end in a state with no known actions are ``redirected'' to a single, special absorbing state $z$, while all other transitions of the global MDP are preserved. Thus initially the known MDP dynamics are a small subset of the global MDP, but over time may cover much or all of the global state space. For rewards, when {\em exploit} is 1, rewards from the real environment are preserved, whereas when {\em exploit} is 0, reward is obtained only at the absorbing state, thus rewarding (rapid) exploration (escape from known state-actions). We shall use $\hat{M}_{\textrm{exploit}}$ to denote the MDP corresponding to the generative model above when the {\em exploit} input bit is set to 1, and $\hat{M}_{\textrm{explore}}$ to denote the MDP generated by setting {\em exploit} to 0. Note that under our assumptions, we can always simulate the approximate known MDP generative model. We can also view it as being an approximate (hence the name) generative model for what we shall call the {\em true known MDP} --- the MDP whose generative model is exactly the same as described above, except where the local modeling algorithm \emph{Model} is perfect (that is, in the Local Modeling Assumption, $d((s,a),(s',a')) \leq \alpha$ implies $\sum _{\hat{s}}|\hat{P}(\hat{s}|s,a) - P(\hat{s}|s,a)| = 0$, and $|R(\hat{s}) - \hat{R}| = 0$). This may still be only a partial model of the global MDP, but it has the true probabilities for all known state-actions. We shall use ${M}_{\textrm{exploit}}$ to denote the MDP corresponding to the generative model above with a perfect \emph{Model} and the {\em exploit} input bit set to 1, and ${M}_{\textrm{explore}}$ to denote the MDP generated with a perfect \emph{Model} and {\em exploit} set to 0. Now we outline the full Metric-$E^3$ algorithm. It is important to emphasize that this algorithm \emph{never} needs to explicitly enumerate the set of known state-actions. \textbf{Algorithm Metric-\( E^{3} \)\\ Input: $d(\cdot,\cdot)$, \emph{Model}, \emph{Plan}\\ Output: A policy $\pi$} \begin{enumerate} \item Use random moves until encountering a state $s$ with at least one known action $a$ (that is, where there are at least \( m \) \( \alpha \)-close previous experiences to $(s,a)$). \item Execute \emph{Plan} twice, once using the generative model for \( \hat{M}_{\textrm{exploit}} \) and once using the generative model for \( \hat{M}_{\textrm{explore}} \). Let the resulting policies be \( \pi _{\textrm{exploit}} \) and \( \pi _{\textrm{explore}} \), respectively. \item If \( V _{\hat{M}_{\textrm{explore}}}(\pi _{\textrm{explore}},s)>\epsilon \), execute \( \pi _{\textrm{explore}} \) for the next $T$ steps, then go to Step 1. \item Else, HALT and output \( \pi _{\textrm{exploit}} \). \end{enumerate} The claim is that this algorithm finds a near optimal policy, in sample complexity and running time that depend only on the covering number under the metric. We now turn to the analysis. \vspace{-0.15in} \section{Metric-\protect\( E^{3}\protect \) Analysis} \vspace{-0.15in} \noindent We first state the main theorems\footnote{The form of these claims differs from the original $E^3$ statement because the results hold \emph{without} an assumption of a mixing MDP. Theorems similar to the original $E^3$ can be constructed in the metric case by making an additional assumption of mixing. The ``mixing free'' form stated here is subject to fewer assumptions, and therefore more general. See \cite{sham} for details.} of the paper. In the following theorems, we use: \begin{enumerate} \item $\pi^*$ is an optimal policy in $M$ \item $T$ is the time horizon \item $m$ and $\alpha$ are the sample complexity and precision defined in the Local Modeling Assumption \item $\beta$ is the precision defined in the Approximate Planning Assumption \item $\epsilon$ is an accuracy parameter \item $\delta$ a confidence parameter. \end{enumerate} \begin{thm} (Sample Complexity) \label{thm1} Suppose $\epsilon > \alpha(T+1)$. With probability $1-\delta$, after at most $\frac{TmN(\alpha)}{\epsilon -\alpha (T+1)}\ln({1}/{\delta})+mN(\alpha)$ actions in $M$, Metric-\( E^{3} \) halts in a state $s$, and outputs a policy $\pi$ such that $V _{M}(\pi,s)\geq V _{M}(\pi ^{*},s)-\epsilon-2\beta -2 \alpha (T+1)$. \end{thm} This shows that the sample complexity (the number of actions required) is bounded in terms of the covering number $N(\alpha)$ (and not the size of the state space). In addition to bounding the sample complexity, we bound the time complexity. \noindent \begin{thm} (Time Complexity) \label{thm2} Let \( k \) be the overall sample complexity. Metric-\( E^{3} \) runs in time at most \( \frac{k(k-1)}{2} t_{\mbox{metric}} + 2k (t_{\mbox{plan}} + c_{\mbox{gen}} t_{\mbox{model}}) + O(k) \). \end{thm} A few lemmas are useful in the proofs. First we define $\hat{M}$ to be an $\alpha$-approximation of $M$ if for all states $s$, $\sum _{s'}|\hat{P}(s'|s,a) - P(s'|s,a)|\leq \alpha$, and $|R(s) - \hat{R}(s)| \leq \alpha$. The original Simulation Lemma for $E^3$ had a dependence on the size of the state space that we cannot tolerate in our setting, so we first need an improved version: \begin{lem} \label{lem-sim}(Simulation Lemma) If \( \hat{M} \) is an $\alpha$-approximation of \( M \), then for any initial state \( s \), any horizon \( T \), and any policy \( \pi \), \[ |V _{\hat{M}}(\pi,s )-V _{M}(\pi,s )|\leq \alpha (T+1)\] \end{lem} \emph{Proof.} Let $H_t=\{(s_1,s_2,\ldots s_t)\}$ be the set of length $t$ paths. For $h\in H_t$, let $h_t$ be the $t$-th state in $h$ and let $A_t(h)$ and $\hat{A_t}(h)$ be the probability of $h$ in $M$ and $\hat{M}$, respectively. Let $Q(s'|s)$ and $\hat{Q}(s'|s)$ be the transition probabilities under $\pi$ in $M$ and $\hat{M}$, respectively. Since $\hat{M}$ is an $\alpha$-approximation, for any state $s'$, $\sum_{s}|Q(s|s')-\hat{Q}(s|s')|\leq\alpha$. Then \begin{eqnarray*} & & \sum _{h\in H_{t+1}} |A_{t+1}(h)-\hat{A}_{t+1}(h)| \\ &= & \sum _{h\in H_{t},s}|A_t(h)Q(s|h_t)-\hat{A}_t(h)\hat{Q}(s|h_t)| \\ & \leq & \sum _{h\in H_{t},s} |A_t(h)Q(s|h_t)-\hat{A}_t(h)Q(s|h_t)| \\ & &+ |\hat{A}_t(h)Q(s|h_t)-\hat{A}_t(h)\hat{Q}(s|h_t)| \\ & = & \sum _{h\in H_{t},s} Q(s|h_t)|A_t(h)-\hat{A}_t(h)| \\ & &+ \hat{A}_t(h)|Q(s|h_t)-\hat{Q}(s|h_t)| \\ & \leq & \sum _{h\in H_{t}} |A_t(h)-\hat{A}_t(h)| + \alpha \end{eqnarray*} where we have used the triangle inequality and linearity of expectation. Induction on \( t \) implies that: \[ \sum _{\textrm{paths}}\left|\Pr _{s_{i}\sim M,\pi,s_0 }(s_{1},...,s_{T}) -\Pr _{s_{i}\sim \hat{M},\pi,s_0 }(s_{1},...,s_{T})\right|\leq \alpha T. \] Since the rewards $\hat{R}$ in $\hat{M}$ are also $\alpha$-accurate, \[ \left|V _{\hat{M}}(\pi ,s)-E_{\textrm{length $T$ paths in }\hat{M}}\left[\frac{1}{T}\sum_{t=1}^{T}R(s_{t})\right]\right|\leq \alpha \, . \] The result follows using the previous two equations. \qed Now we restate the ``Explore-or-Exploit'' lemma from \cite{E3}. \noindent \begin{lem} \label{lem-exp-exp}(Explore or Exploit) Let $\pi^*$ be the optimal policy for the global MDP \( M \), and let \( \pi^*_{\textrm{exploit}} \) be the optimal policy for the true known MDP \( M_{\textrm{exploit}} \) described above. Then for any state $s$ of \( M_{\textrm{exploit}} \) and for any \( 0<\epsilon <1 \), either \[ V _{M_{\textrm{exploit}}}(\pi _{\textrm{exploit}}^{*},s)>V _{M}(\pi ^{*},s)-\epsilon \] or the optimal policy \( \pi^*_{\textrm{explore}} \) for $M_{\textrm{explore}}$ has probability of at least \( \epsilon \) of leaving the known states in \( T \) steps in $M$. \end{lem} One subtle distinction from the original $E^3$ algorithm exists. Here, although the algorithm plans to reach some unknown state, by the time this state is reached, it might actually be known due to the Local Modeling Assumption. Note that in the maze world example, the agent might plan to escape by moving around a corner. However, when actually executing this escape policy, the states around the corner could become known before they are reached in $T$ steps, if they come into line of sight beforehand. We now establish that Metric-\( E^{3} \) ceases to explore in a reasonable amount of time. In the original \( E^{3} \) this was a consequence of the Pigeonhole Principle applied to the number of states. A similar statement holds here, but now we use the size of a cover under the metric. It is important to note that this lemma holds whether or not the covering number \( N(\alpha) \) is known. \begin{lem} \label{lem-exp-limit}(Exploration Bound) Metric-$E^{3}$ encounters at most $mN(\alpha)$ unknown state-actions. \end{lem} \emph{Proof.} First, consider the $m=1$ case. We construct a set $C$ as follows: the state-action $(s,a)$ at time $t$ is added to the set $C$ if \[ \forall (s',a') \in C:\,\,\, d((s,a),(s',a')) > \alpha \, . \] Note that the state at time $t$ is unknown if and only if \[ \forall (s',a') \in \textrm{\{earlier state-actions\}}:\,\,\, d((s,a),(s',a')) > \alpha \] and so if $(s,a)$ is unknown, then it is added to $C$. Thus, the size of $C$ at time $t$ is an upper bound on the number of unknown state-action pairs encountered by the algorithm before time $t$. Since no element of $C$ covers another element in $C$, $C$ is minimal. In particular, if any element is removed from $C$ the set of states covered by $C$ is reduced. It follows that for all $t$ the size of $C$ is less than $N(\alpha)$, and hence the algorithm cannot encounter more than $N(\alpha)$ unknown state-actions. For the general $m$ case, consider constructing $m$ different sets, $C_1, \ldots,C_m$. The state action at time $t$ is added to only one of the sets $C_i$ if there is no $\alpha$-close element in $C_i$. By an analogous argument, if a state-action is unknown, it is added to some $C_i$, and so the sum of sizes of $C_i$ bounds the number of unknown state-actions encountered by the algorithm before time $t$. Again, by construction, each $C_i$ is minimal for all $t$. Hence, the size of each $C_i$ is bounded by $N(\alpha)$ and so the number of unknown state-actions encountered by the algorithm is bounded by $mN(\alpha)$. \qed We now provide the proofs of the main theorems. \emph{Proof of \ref{thm1}.} The exploration bound of Lemma \ref{lem-exp-limit} implies we encounter a known state after a number of actions that is at most $mN(\alpha)$, which bounds the number of successful exploration attempts. Each attempted exploration occurs when $V_{\hat{M}_{\textrm{explore}}}(\pi_{\textrm{explore}},s)>\epsilon $, and so $V _{M_{\textrm{explore}}}(\pi_{\textrm{explore}},s)>\epsilon-\alpha (T+1)$. By definition of $M_{\textrm{explore}}$, the chance of successful exploration is greater than $\epsilon-\alpha (T+1)$. Hence, at most, \( \frac{TmN(\alpha) }{\epsilon -\alpha (T+1)}\ln ({1}/{\delta) } \) actions successful exploration of the state spaces occurs with a $\delta$ chance of error. The total number of actions before halting is less than the sum of the exploration actions known states and the actions taken in unknown states. The decision to halt occurs when $V_{\hat{M}_{\textrm{explore}}}(\pi_{\textrm{explore}},s)\leq\epsilon $, which implies $V_{M_{\textrm{explore}}}(\pi_{\textrm{explore}}^*,s)\leq\epsilon+\alpha (T+1) +\beta$ due to planning and simulation error. By the Explore or Exploit lemma \[ V _{M_{\textrm{exploit}}}(\pi_{\textrm{exploit}} ^{*},s)>V_{M}(\pi ^{*},s)-\epsilon -\alpha (T+1) - \beta \, . \] Due to simulation and planning error in computing an optimal policy in $M_{\textrm{exploit}}$, \[ V _{M_{\textrm{exploit}}}(\pi _{\textrm{exploit}},s) >V_{M}(\pi ^{*},s)-\epsilon -2\alpha (T+1)-2\beta \, . \] The result follows since a policy in $M$ has no less reward than in $M_{\textrm{exploit}}$. \qed \emph{Proof of \ref{thm2}.} It is never necessary to evaluate the metric between two samples more than once. There are at most \( \frac{k(k-1)}{2} \) pairs of samples, so line 1 of Metric-$E^3$ take time at most $ t_{\mbox{metric}} \frac{k(k-1)}{2} $ computation. Step 2 is executed at most $k$ times since at least one transition occurs before reentering step 2. One call to $\emph{Plan}$ requires time at most $t_{\mbox{plan}} + c_{\mbox{gen}} t_{\mbox{model}}$ so the total time spent on step 2 is at most $2k (t_{\mbox{plan}} + c_{\mbox{gen}} t_{\mbox{model}})$. Step $3$ takes total time at most $O(k)$. The result follows by adding these times. \qed \section{Discussion} It is difficult to quantify the exact scaling improvements of metric-$E^3$ over $E^3$ because the improvements are inherently dependent upon the exact form of the local modeling assumption. In the extreme case where the state-action space is continuous and $N(\alpha)$ is finite, $E^3$ has an infinite sample complexity while metric-$E^3$ has a finite sample complexity. In less extreme cases, the advantage of metric-$E^3$ is (naturally) less extreme. It is worth noting that the extreme case is not too unusual. Certainly, many control problems are modeled using continuous (or virtually continuous) parameters. The metric-$E^3$ analysis implies that local modeling requires weaker assumptions about the behavior of the world than state aggregation. It is not necessary for aggregations of states to have Markovian dynamics in order to engage in successful exploration. Instead, all that we need is the ability to generalize via local modeling. Of course, when aggregations of states \emph{do} have Markovian dynamics, state aggregation may work well. \small \begin{thebibliography}{1} \bibitem{grad2} J. Baxter and P. L. Bartlett. ``Direct Gradient-Based Reinforcement Learning: I. Gradient Estimation Algorithms''. Technical report , Australian National University, 1999. \bibitem{Approxplan} Carlos Guestrin, Relu Patrascu, and Dale Schuurmans, ``Algorithm-Directed Exploration for Model-Based Reinforcement Learning in Factored MDPs'', ICML 2002, pages 235-242. \bibitem{DBN}M. Kearns and D. Koller. ``Efficient Reinforcement Learning in Factored MDPs''. Proceedings of IJCAI, 1999. \bibitem{E3}M. Kearns and S. Singh. ``Near-Optimal Reinforcement Learning in Polynomial Time''. Proceedings of ICML, 1998. \bibitem{Rmax}R. I. Brafman and M. Tennenholtz. ``R-max -- A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning''. Proceedings of IJCAI, 2001. \bibitem{Sparse}M. Kearns, Y. Mansour, and A. Ng. ``A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes''. Proceedings of IJCAI, 1999. \bibitem{sham}S. Kakade. Thesis. University College London. 2003. \bibitem{CPI}S. Kakade and J. Langford. ``Approximately Optimal Approximate Reinforcement Learning''. Proceedings of ICML, 2002. \bibitem{sven}S. Koenig and R. Simmons. ``Complexity Analysis of Real-Time Reinforcement Learning'' Proceedings of the National Conference on Artificial Intelligence, pages 99-105, 1993. \bibitem{thrun}S. Thrun ``Efficient exploration in reinforcement learning'' Technical Report CMU-CS-92-102, Carnegie Mellon University, Computer Science Department, Pittsburgh, PA, 1992. \bibitem{Parti-game}A. W. Moore. ``The Parti-game Algorithm for Variable Resolution Reinforcement Learning in Multidimensional State-spaces''. In NIPS 6, 1993. \bibitem{Dean}T. Dean and R. Given. ``Model Minimization in Markov Decision Processes''. In AAAI, 1997. \bibitem{aggregation} J. Rust, ``A Comparison of Policy Iteration Methods for Solving Continuous-State, Infinite-Horizon Markovian Decision Problems Using Random, Quasi-random, and Deterministic Discretizations'', http://econwpa.wustl.edu:8089/eps/comp/papers/9704/9704001.ps \bibitem{grad1} R. Sutton, D. McAllester, S. Singh and Y. Mansour. ``Policy Gradient Methods for Reinforcement Learning with Function Approximation''. In NIPS 13, 2000. \end{thebibliography} \end{document}