text:
\section{Algorithm}

\begin{algorithm}
\caption{Planning}\label{alg:planning}
\begin{algorithmic}
\Procedure{Planning}{$s, d, t$} \\
   \textbf{input}: $s$ state, $d$ depth, $t$ number of rollouts
   \State $\forall a: Q(s,a) \gets 0$
   \State $o \gets$ detectObjects($s$)
   \State $T, R \gets$ selectModels($o$)
    \For {$l$ in 1:$t$}
        \State $Q \gets $UCT$(T, R, o, d)$
    \EndFor
   \State \Return $\underset{a}{argmax}\ Q(s,a)$
\EndProcedure

\Procedure{UCT}{$T, R, o, d$} \\
   \textbf{input}: $T$ transition function, $R$ reward function, $O$ object state, $d$ current depth
   \If{$d \geq MaxDepth$} \Return 0 \EndIf
   $a \gets \underset{a}{argmax}\ Q(o,a) + c \sqrt{\frac{log N(o)}{N(o,a)}}$
   \State $o' \gets T(o, a)$
   \State $r \gets R(o, a)$
   \State $\tilde{R} \gets r + \gamma$ search($T,R,o',d+1$)
   \State $N(o,a) \gets N(o,a) + 1$
   \State $N(o) \gets N(o) + 1$
   \State $Q(o,a) \gets Q(o,a) + \frac{\tilde{R}-Q(o,a)}{N(o,a)}$
   \State \Return $\tilde{R}$
\EndProcedure

\end{algorithmic}
\end{algorithm}
\section{Approximately deterministic model to support fast learning}\label{sec:model}

In the previous section we considered how to plan and perform deep exploration given a transition and reward models. Now we ask a natural question, what types of model to learn?, and how these models will affect computational tractability of planning and sample efficient learning? In general simpler models are easier to learn and requires less data to train, in contrast to complex function approximation methods that often requires massive amount of data and suffer from compounding errors in lookahead planning~\citep{roderick2017deep, weber2017imagination}. Additionally, simple models are tractable to perform deep exploration with model uncertainty and reduce planning time.

There are reasonable evidence that humans learns a simple model, often inaccurate, to support planning and guide decision making~\citep{tsividis2017human, dubey2018investigating}. In particular, people seem to benefit from higher level object representations that allows them to factor a high dimensional state space into simple low dimensional object states, this allows human to generalize from few examples, explore and plan efficiently.
Additionally, as discussed in section \ref{sec:exp_disc}, deterministic models can significantly help in planning and deep exploration, due to smaller branching factor of the tree (each state node will have only one child per action). Inspired by humans and prior works on object oriented MDP~\citep{diuk2008object} we hypothesize that object oriented models can help us learn a simple, easy and approximately deterministic models that are sufficient for planning .

Object detection has been long studied in computer vision, and state-of-the-art algorithms can detect objects with great accuracy in real world scenes (e.g. YoLo~\citep{redmon2017yolo9000}, fast RCNN~\citep{girshick2015fast} mask RCNN~\citep{he2017mask} and \dots). We expect that these algorithms can simply detect objects and their bounding boxes, when they are trained on Atari2600. Thus, here we assume objects are given, in section \ref{sec:model_learning} we discuss how to learn a simple model and further in section \ref{sec:macro} we show how temporal abstraction can help learning an approximately deterministic mode.

\subsection{Review of Object Oriented MDP}

We use a simpler version of OOMDP~\citep{diuk2008object}. we define a set of object classes $\mathcal{C} = \{c_1, \dots, c_n\}$ where each class has a set of attributes $\{c.a_1,\dots,c.a_m\}$. Each state $s$ consists of objects $f(s) = \{o_1,\dots,o_k\}$ where each object $o_i \in \mathcal{C}$. The state of an object is defined by the value assignment to its attributes. Finally, the state  $s$ of the underlying MDP is the union of all object states $\cup_{i=1}^{k} o_i$.

We define the interaction function $I: \mathcal{O} \times \mathcal{O} \rightarrow \{0,1\}$ to be an indicator that determines if two objects are interacting with each other. For simplicity, we make three assumptions: first, that this interaction function is known; second, objects from the same class share the same transition function; and third, each object's next state is  dependent on at most pairwise object interactions and action.
An object's successor state is determined by a standalone transition function $T_c(o, a)$ or a pairwise transition function $T_{c_i,c_j}(o_i,o_j,a)$ if $I(o_i,o_j) = 1$.

\begin{figure}[tb]
    \centering
    \subfloat[mini \textit{Pitfall!}]{\includegraphics[width=.25\linewidth]{img/pitfall.pdf}}%

    \subfloat[][Total Entropy of Models]{\includegraphics[width=.37\linewidth]{img/pitfall_entropy_meta.pdf}}%

    \subfloat[][Per Action Entropy of Agent's Model]{\includegraphics[width=.37\linewidth]{img/pitfall_entropy_actions.pdf}}%
    \caption{Macro actions}%
    \label{fig:meta_action}%
\end{figure}

\subsection{Model Learning}\label{sec:model_learning}

Given that we are planning at an object level, we hypothesize that even simple models, such as linear and discrete count based models, give sufficient accuracy for planning, since often objects follow a very simple physical laws. More importantly, to ensure "sufficient accuracy in planning", we further require that these models predict transitions and rewards in a deterministic fashion.

To ensure deterministic transitions, we consider the class of functions $\mathcal{F}_t = \{f_{t}^{1},\dots,f_{t}^{n}\}$, where each $f_{t}^{i}$ is a count-based model of the dynamics for an object. Each function stores the count of every output based on a different set of input features with given history $t$. The simplest model in $\mathcal{F}_1$ is $f_{1}^{1}$, which uses one history with null input. For example, for a falling object with steady state velocity, such a model is sufficient as we can predict displacement $\delta x$ and $\delta y$ without any input. On the other hand, $f_{1}^{n}$, which uses one history and the most complex set of features, is the most complicated model in the class $\mathcal{F}_1$. In terms of objects, the most complex set of input features that we consider is the union of the object's state features, relative state features with respect to an interacting object, and action.

The goal then is to choose the simplest model that achieves deterministic transitions within $\mathcal{F}_t$. To do so, we compute the entropy of the observed data for each function $H(f_{t}^{k}) = -\sum_{x_i} p(x_i) \log(p(x_i|f_{t}^{k}))$ where the summation is over all the observed data. We choose the simplest model that has entropy less than a predefined threshold $\epsilon_{ent}$. If none of the models in $\mathcal{F}_t$ satisfy the entropy threshold, we increase $t$ through an exponential back off scheme. Concretely, we increase the history to the next exponent of 2. We use the same approach and same class of models for reward functions.

Figure \ref{fig:pitfall:metaction}(a) shows an example for the game \textit{Pitfall!}, where we used a Cartesian product of object size $(w,h)$, object location $(x,y)$ and object intersection $(x',y')$ as features. Ignoring null input, this Cartesian product results in 7 different feature sets. With sufficient history, the entropy of all the models eventually drops to zero.

\begin{figure}[tb]
    \centering

    \subfloat[Model entropy]{\includegraphics[width=.36\linewidth]{img/pitfall_entropy.pdf}}%
    \quad
    \subfloat[Example trained models]{\includegraphics[width=.595\linewidth]{img/Tree.pdf}}%
    \quad
    \caption{Model selection}%

    \label{fig:pitfall:metaction}%
\end{figure}

\subsection{Temporal Abstraction}\label{sec:macro}

As we observed in our experiments, objects transitions, especially action-dependent transitions, can show a highly nonlinear behaviour and dependency to multiple time step histories. Inspired by human's \textit{reaction time} and previous work~\citep{diuk2008object} we use the notion of macro action in the form of \textit{"act and then wait"} in order to learn a simple approximately deterministic transition models.

Algorithm \ref{alg:macro} shows the pseudo code to learn the macro actions from a predefined set of atomic actions (e.g. in the simplest form it can be the action space of the desired MDP; however, one can define them as any n-token combination of actions). In algorithm \ref{alg:macro} we augment all atomic actions with $k$ number of \textit{no-op} or wait, and then greedily decrease the number of no-ops followed by each action such that all model's can deterministically predict the next object state. The  goal is to have a model that achieves deterministic transition, to do so we measure the entropy of model's prediction with the observed data as in section \ref{sec:model_learning}.

\begin{algorithm}
\KwIn{maximum number of no-op $k$, set of atomic actions $\mathcal{A}$}
\SetAlgoLined
macro actions $\gets$ atomic action followed by maximum number of no-op\;
mark all macro action as reducible\;
\While{there exist a reducible macro action}{
    $a \gets$select a reducible macro action and decrease number of no-op by one\;
    $\tau \gets$ compute entropy of model's prediction with new set of macro actions\;
    \If{$\tau \geq thresh$}{
        mark $a$ as non reducible macro action and restore the number of no-op for $a$\;
    }
}
 \caption{\bf Macro Actions}\label{alg:macro}
\end{algorithm}

Figure \ref{fig:meta_action}(b) shows the total entropy of model's versus total number of \textit{no-op} in \textit{Pitfall!} environment. As algorithm progress entropy increases to pass the threshold. Figure \ref{fig:meta_action} (c) shows the entropy of agent's models while reducing number of \textit{no-op} for one action and keeping others constant. As it shows Jump Right requires 8, Down requires 4 and Right requires none \textit{no-op} afterward to achieves a deterministic transition for all actions. Running this algorithm in \textit{Pong Prime} environment results in two \textit{no-op} after each action, since the real dynamics uses 3 step history.

\section{Approximate Model-Based Planning to Support Exploration}\label{sec:exp}

Computing an optimal policy for a Markov decision process in a large state space can be extremely computationally expensive, if not impossible. Therefore some form of approximate planning procedure is almost always needed for large scale  domains. Especially in model-based RL algorithms when the transition and reward models are initially unknown and should be learned online
, a computationally tractable planning algorithm is more critical. Since the model estimates are changing and one should plan more frequently with the new model estimates.

One popular and powerful approach for scaling up planning for large Markov decision processes is Monte Carlo Tree Search~\citep{chaslot2008monte, browne2012survey}, which has been used to achieve better than world class performance in Go~\citep{silver2016mastering}. When a perfect transition and reward model is known, MCTS is guaranteed to converge to the optimal value function in the limit of infinite computation (i.e. infinite number of rollouts). However, when a model is estimated from the data and computational power is bounded, prior works has suggested how to adjust planning horizon to get the best computational performance~\citep{jiang2015dependence}. As of our knowledge there is no work that additionally investigate the performance of different exploration methods with approximate planning

We are interested in how to leverage models to support deep efficient exploration in large domains. Prior research has strong guarantees to find a near optimal policy with deep exploration when exact planning can be done, often in small state space~\citep{brunskill2009provably, brafman2002r}. In contrast, in this work, we investigate how to leverage models to support deep exploration when exact planning is not possible (large state space).

We propose a new optimistic MCTS to support deep exploration guided by models. Particularly, we suggest to perform a MCTS algorithm (e.g. UCT~\citep{kocsis2006bandit}), and use the learned reward $R$ and transition model $T$ that is optimistic toward unseen or less frequently seen part of the state-action space (we further discuss how to learn simple models for planning in section \ref{sec:model}).
Concretely, while performing rollouts using learned models at each step an optimistic reward bonus is given. Optimistic reward bonus can be given by any optimism in the face of uncertainty (OFU) algorithm (e.g. MBIE-EB~\citep{strehl2008analysis} or Rmax~\citep{brafman2002r}).

Optimistic MCTS may have some advantages over alternate ways to achieve deep exploration in large state spaces given limited computation.
In particular optimistic MCTS is leveraging model uncertainty to drive deep exploration, in contrast to policy search methods with simulated models~\citep{sutton2000policy} that relies on the stochasticity of the policy for exploration and it is unclear how to leverage model uncertainty.

Additionally, MCTS with posterior sampling methods, like Thompson Sampling~\citep{thompson1933likelihood} (by sampling a model from posterior distribution and performing rollouts) has strong guarantees when exact planning can be done, might not be optimistic enough for efficient exploration. With limited number of rollouts, agent might not observe the optimistic part of the model, in contrast to optimistic MCTS where optimism is built into every node of the tree

To investigate the impact of approximate planning on deep exploration, we compare optimistic MCTS, with Thomson Sampling, and BAMCP~\citep{guez2012efficient} (a tractable sample-based method for
approximate Bayes-optimal planning) in two toy domains, \textit{Pong Prime} and \textit{mini-Pitfall!}.

\begin{table}[tb]
  \begin{center}
    \begin{tabular}{r|c|c|c}
      \toprule
      \textbf{Method} & Optimism & Thompson Sampling & BAMCP\\
      \midrule
      \textbf{Number of Episdoes} & 5.0 $\pm$ 1.7 & 6.2 $\pm$ 1.95 & 11.0 $\pm$ 2.5\\
      \bottomrule
      \end{tabular}

  \end{center}
  \caption{Comparison of different exploration methods in \textit{mini-Pitfall!} to consistently achieve the reward at the right end of the first room.}
  \label{tab:mini_pitfall}
\end{table}

\begin{figure}[tb]
    \centering
    \subfloat[Pong Prime environment]{\includegraphics[width=.31\linewidth]{img/PongP.pdf}}%

    \subfloat[Different exploration methods]{\includegraphics[width=.33\linewidth]{img/pongp_comparison.pdf}}%

    \subfloat[Optimism based exploration]{\includegraphics[width=.33\linewidth]{img/pongp_optimism.pdf}}%
    \caption{Pong Prime}%
    \label{fig:pongp}%
\end{figure}

\subsection{Experiments}

In order to test our hypotheses on the impact of imperfect model-based planning on deep exploration we introduced two toy environments, \textit{PongPrime} and \textit{mini-Pitfall!} that are similar to general Atari games but in smaller scale. \textit{Pong Prime} environment is designed for a hard exploration task. Dynamics of this game is similar to Atari2600's Pong environment~\citep{bellemare2013arcade} with minor tweaks that make the game significantly harder. The enemy paddle is made 3 times larger than the player paddle.
Additionally, the top and bottom 10\% percent of the enemy paddle hit the ball back at 1.5 times the normal speed.
Similarly, the player paddle also consists of 3 regions with distinct behavior. The \emph{top region} of the paddle hits the ball back at 1.5 times speed. The \emph{middle region} hits the ball back at normal speed. Finally, the \emph{lower region} covers 5\% of the paddle and instantly wins a point for the player. This configuration is set up so that it is difficult but not impossible for the player to score using the top region (scoring on average around 5\% of the time the ball bounces off the top region). In this setting, the optimal policy is to always hit the ball with the lower region of the ball. The game is deterministic and model free methods with $\epsilon$-greedy exploration (e.g. DQN) consistently loses the game with lowest possible score across 5000 episodes. Figure\ref{fig:pongp}(a) shows this environment.

\textit{mini-Pitfall!} is a small version of Atari2600 game \textit{Pitfall!} which we use as a final test bed of our algorithm. In this version we limit the agent to two rooms of the game (the initial room, room 0, that agents starts the game in, and the room on the left side, room -1). There exist a dummy reward $R_{max}$ at the right end of the room 0, and the left end of room -1 is a terminal state (underground connection is also terminal state). Figure \ref{fig:meta_action}(a) shows this environment.

We provided the right model class for both experiments so we can separate the effect of exploration from model mismatch. Figure \ref{fig:pongp}(b) compares the performance of different exploration strategies to the baseline (which uses a MLE model with UCT algorithm) combining with UCT algorithm in \textit{Pong Prime} domain. We perform 500 total tree searches for all runs in Figure \ref{fig:pongp}(b). Additionally, Table \ref{tab:mini_pitfall} shows the performance of different exploration methods in achieving the reward on the right side of the room 0 in \textit{mini-Pitfall!} consistently.

\subsection{Discussion}\label{sec:exp_disc}

Both BAMCP and TS perform worse than the MLE model. In the limit of infinite simulations, BAMCP is guaranteed to converge to the Bayes optimal solution~\citep{guez2012efficient}. Similarly, with full horizon planning, we should be able to compute the exact value for the model sampled with TS, and there are strong guarantees that such a method will converge to the optimal policy~\citep{osband2016posterior}.
However, if it is infeasible to use a depth that mimics the game horizon, or perhaps even to reach a local reward, then TS may suffer. This is because TS samples a single model, which means that parts of the model may be overly optimistic, while other parts may be pessimistic. Hence, when performing a limited number of simulations using UCT, we may not go down branches of the tree that \textit{observe} the optimistic parts of the sampled model. Therefore, the computed estimates of the Q value at the root node may not be optimistic, which is often a key part of proofs of the effectiveness of TS methods, and very helpful empirically.

Additionally, BAMCP suffers more in these environments that are deterministic. This means that for TS, optimism, and MLE approaches, the tree constructed will only have one child node (the deterministic next state) for any chosen action. In contrast, BAMCP samples a different deterministic model at each rollout, and for the same action node, those models may each deterministically predict different next states. Hence, BAMCP with $M$ sampled models and planning horizon $H$, potentially builds a tree of size O($(|A|M)^H$), in contrast to the other methods that build a tree of at most size O($|A|^H$), where $|A|$ is the size of action space.

Optimism-based exploration significantly outperforms other approaches. Optimism is built into \textit{every} node of the three that is allowing it to distinguish even locally between actions that may need exploration, in absence of observing long delayed reward. As we demonstrate in Figure \ref{fig:pongp}(c) for the optimistic method, as planning power increases through more simulations (number of rollouts), the performance of optimism-based exploration also increases. With sufficient computational power, optimistic MCTS should learn the optimal policy for \textit{Pong Prime} domain.

\section{Conclusion and Future Work}
To conclude, we showed how we can achieve a sample efficient RL algorithm with object priors. We proposed optimistic MCTS as a way to drive deep exploration when exact planning is impossible, and showed this to be more effective than posterior sampling methods. Additionally, we investigate how approximately deterministic simple models can be learned with object representation to support fast learning and planning.

We introduced Strategic Object Oriented RL (SOORL) that uses object representation and optimistic MCTS with automatic model selection that biases towards simple deterministic models. SOORL achieves state of the art results in the game of $\textit{Pitfall!}$. While there remains works to be done to reduce the engineering burden of SOORL, lookahead planning with object representation is a very promising path towards more sample efficient RL algorithms.

A very important line of future research is \textbf{robust planning}. One important challenge in model-based RL is making planning robust to model
inaccuracy. Identifying the right model class is a nontrivial task, and a wrong model class can
easily introduce a catastrophic error in long-horizon prediction that prohibits the use of tree search
algorithms like UCT.

\section{Imperfect Planning}\label{sec:imperfect_plan}
Planning in an MDP with known transition and reward models can be efficiently done by focusing on promising branches of state-action tree using the UCT algorithm \citep{kocsis2006bandit}. However, when a perfect simulator of the environment is not known, learning models sufficient for planning can be hard, if not impossible. And the performance of model-based RL depends on the performance of the learned model, which often suffers from error in function approximation~\citep{talvitie2015agnostic, talvitie2014model}. These errors compound in planning and can cause \textit{catastrophic planning} errors (e.g. agent dying).

There are strong guarantees that model-based strategic exploration methods will converge to the optimal policy~\citep{brafman2002r, thompson1933likelihood, guez2012efficient}, while performing exact planning. However, exact planning in large MDPs is often impossible even if the perfect simulator is know. Thus, the resulting performance of model-based exploration methods is unclear when combining with UCT algorithm with limited depth and finite number of rollouts.

In this section we first introduce two toy examples \textit{Pong Prime} and \textit{mini-Pitfall!} and then investigate strategic exploration with imperfect planning. Then we study compounding errors and introduce a notion of macro actions similar to previous works~\citep{diuk2008object}, that will help us to learn a simple accurate model sufficient for planning.

\textit{Pong Prime} environment is designed for a hard exploration task. Dynamics of this game is similar to Pong with minor tweaks that make the game significantly harder. The enemy paddle is made 3 times larger than the player paddle, so it is impossible to score a point by simply hitting the ball back at the normal speed.  Additionally, the top and bottom 10\% percent of the enemy paddle hit the ball back at 1.5 times the normal speed so that the enemy paddle is even more powerful. Similarly, the player paddle also consists of 3 regions with distinct behavior. The \emph{top region} takes up the top 50\% of the paddle and hits the ball back at 1.5 times speed. The \emph{middle region} takes up the middle 45\% of the paddle and hits the ball back at normal speed. Finally, the \emph{lower region} covers remaining 5\% and instantly wins a point for the player. This configuration is set up so that it is difficult but not impossible for the player to score using the top region (scoring on average around 5\% of the time the ball bounces off the top region). In this setting, the optimal policy is to always hit the ball with the lower region of the ball. The game is deterministic and model free methods with $\epsilon$-greedy exploration (e.g. DDQN) consistently loses the game with lowest possible score across 5000 episodes.

\textit{mini-Pitfall!} is a small version of Atari2600~\citep{bellemare2013arcade} game \textit{Pitfall!} which we use as a final test bed of our algorithm. In this version we limit the agent to the first room of the game, and there exist a dummy reward $R_{max}$ at the right end of the room, and the left end is a terminal state. Figure \ref{fig:meta_action}(a) shows this environment.

\subsection{Exploration}

\begin{figure}[tb]
    \centering
    \subfloat[Pong Prime environment]{\includegraphics[width=.31\linewidth]{img/PongP.pdf}}%

    \subfloat[Different exploration methods]{\includegraphics[width=.33\linewidth]{img/pongp_comparison.pdf}}%

    \subfloat[Optimism based exploration]{\includegraphics[width=.33\linewidth]{img/pongp_optimism.pdf}}%
    \caption{Pong Prime}%
    \label{fig:pongp}%
\end{figure}

\begin{table}[tb]
  \begin{center}
    \begin{tabular}{r|c|c|c}
      \toprule
      \textbf{Method} & Optimism & Thompson Sampling & BAMCP\\
      \midrule
      \textbf{Number of Episdoes} & 5.0 $\pm$ 1.7 & 6.2 $\pm$ 1.95 & 11.0 $\pm$ 2.5\\
      \bottomrule
      \end{tabular}

  \end{center}
  \caption{Comparison of different exploration methods in \textit{mini-Pitfall!} to consistently achieve the reward at the end of the first room.}
  \label{tab:mini_pitfall}
\end{table}

We consider three different methods of exploration combined with UCT algorithm: \textbf{Optimisim}~\citep{brafman2002r}, \textbf{Thompson Sampling}~\citep{thompson1933likelihood}, and \textbf{BAMCP} (a tractable sample-based method for approximate Bayes-optimal planning with root and lazy sampling over parameters of the state mode, please refer to~\cite{guez2012efficient} for details). We evaluate their performance combined with UCT algorithm in a toy example \textit{Pong Prime}, which we designed for a hard exploration task.

Algorithm \ref{alg:stratigic} describes object-level planning with strategic exploration using UCT. At each state $s$, we select the appropriate distribution over models for the corresponding object representation $f(s)$ (section \ref{sec:model}) and use UCT to pick the best action . We perform: Thompson Sampling, by sampling a model at the beginning of planning (equivalent to setting $K = 1$ in Algorithm \ref{alg:planning}); BAMCP, by sampling a model for each rollout (equivalent to setting $L = 1$ in Algorithm \ref{alg:planning}); and optimism based exploration, by selecting an optimistic model ($R_{max}$ for the unseen transitions/ rewards) and $L$ rollouts. We compared these methods to Baseline, which uses a MLE model with UCT algorithm and no exploration.

\begin{algorithm}
\KwIn{state $s$, number of models $K$, number of rollouts $L$, planning depth $d$}
\SetAlgoLined
$o \gets$ detectObjects($s$)\;
$\mathcal{T}, \mathcal{R} \gets$ selectModels($o$)\;
  \For{$k$ in 1:$K$}{
        $T\sim\mathcal{T}$, $R\sim\mathcal{R}$\;
        \For {$l$ in 1:$L$}{
            UCT($T, R, o, d$)\;
        }
    }
  \Return $argmax\ Q(s,.)$\;
 \caption{\bf Strategic Exploration with UCT}\label{alg:stratigic}
\end{algorithm}

The correct model class for dynamics of each paddle is a linear model with 3 action history. We assume that the learned dynamics model uses this true model class (i.e. performs linear regression on the transitions we observe) so we can separate the effect of exploration from model mismatch. Figure \ref{fig:pongp}(b) compares the performance of different exploration strategies to the baseline. We perform 500 total tree searches for all runs in Figure \ref{fig:pongp}(b) (i.e. Thompson Sampling uses 500 rollouts with 1 model, BAMCP 500 models each with 1 rollout).

Both BAMCP and TS perform worse than the MLE model. We hypothesize that this result is due to approximate planning, as in the limit of infinite simulations, BAMCP is guaranteed to converge to the Bayes optimal solution. Similarly, with full horizon planning, we should be able to compute the exact value for the model sampled with TS, and there are strong guarantees that such a method will converge to the optimal policy.
However in practice, especially in large domains or domains with real-time constraints, the amount of computation, and therefore the quality of the computed plan, will be significantly limited. In particular, if it is infeasible to use a depth that mimics the game horizon, or perhaps even to reach a local reward, then TS may suffer. This is because TS samples a single model, which means that parts of the model may be overly optimistic, while other parts may be pessimistic. Hence, when performing a limited number of simulations using UCT, we may not go down branches of the tree that \textit{observe} the optimistic parts of the sampled model. Therefore, the computed estimates of the Q value at the root node may not be optimistic, which is often a key part of proofs of the effectiveness of TS methods, and very helpful empirically.

BAMCP faces similar challenges, but suffers further in this domain because the true domain is deterministic. This means that for TS, optimism, and MLE approaches, the tree constructed will only have one child node (the deterministic next state) for any chosen action. In contrast, BAMCP samples a different deterministic model at each rollout, and for the same action node, those models may each deterministically predict different next states. Hence, BAMCP with $M$ sampled models and planning horizon $H$, potentially builds a tree of size O($(|A|M)^H$), in contrast to the other methods that build a tree of at most size O($|A|^H$), where $|A|$ is the size of action space.

Optimism-based exploration significantly outperforms other approaches. We suspect it is more robust to approximate planning, since optimism is built into \textit{every} node, allowing it to distinguish even locally between actions that may need exploration, in absence of observing long delayed reward. To find the optimal policy still requires significant lookahead and careful planning.

Indeed as we demonstrate in Figure \ref{fig:pongp}(c) for the optimistic method, as planning power increases through more simulations, the performance of optimism-based exploration also increases. We expect that with sufficient computations the optimistic method should eventually learn the optimal policy for this domain.

Same results hold for \textit{mini-pitfall!} environment, table \ref{tab:mini_pitfall} shows the performance of different exploration methods in achieving the reward on the right side of the room consistently (three consecutive times). In this experiment we provided a transition model class that is sufficient for planning and doesn't suffer from compounding error, to separate the effect of exploration.

\subsection{Approximately deterministic model to support fast learning}\label{sec:model}

\begin{figure}[tb]
    \centering
    \subfloat[mini \textit{Pitfall!}]{\includegraphics[width=.25\linewidth]{img/pitfall.pdf}}%

    \subfloat[Total Model Entropy]{\includegraphics[width=.37\linewidth]{img/pitfall_entropy_meta.pdf}}%

    \subfloat[Per Action Entropy]{\includegraphics[width=.37\linewidth]{img/pitfall_entropy_actions.pdf}}%
    \caption{Macro actions}%
    \label{fig:meta_action}%
\end{figure}

paragraph1 : sample efficient model-based RL requires learning an easy model that can be learned by few data. Inspired by human, and many real work application follows simple physical law.

paragraph 2: Additionally, model need to be simple to support fast planning. Lookahead planning requires querying the model in multiple time steps, so simple model is necessary to be computationally feasible. Additionally models need to be simple enough to be compatible with deep exploration. And deterministic model can hellp fast planing by reducing the branch factor in tree.

\subsection{Model Learning}
paragraph 3: Object Oriented deterministic models is a promising way to learn simple model, sufficient for planning, and easy to learn. OOMDP used object oriented MDP to efficiently solve small domain with exact planning. Additionally previous works suggest that human (cite) might be using object level planning.

Paragraph 4: State of the art vision algorithm (cite Yolo, fast RCNN) can simply detect objects with high accuracy. Factored MDP is a promising way to model large MDP with smaller set of feature, and we hypothesize that objects attributes  are sufficient parent features to describe the full MDP.
\subsubsection{Object Representation}

\subsection{Learning Models}
Although transition and reward models can be modelled by functions as general as neural networks, using such complicated functions can make performing strategic exploration difficult. Moreover, such functions require much more data to train and often severely suffer from compounding errors. Given that we are planning at an object level, we hypothesize that even simple models, such as linear and discrete count based models, give sufficient accuracy for planning, since often objects follow a very simple physical laws. More importantly, to ensure "sufficient accuracy in planning", we further require that these models predict transitions and rewards in a deterministic fashion.

To ensure deterministic transitions, we consider the class of functions $\mathcal{F}_t = \{f_{t}^{1},\dots,f_{t}^{n}\}$, where each $f_{t}^{i}$ is a count-based model of the dynamics for an object. Each function stores the count of every output based on a different set of input features with given history $t$. The simplest model in $\mathcal{F}_1$ is $f_{1}^{1}$, which uses one history with null input. For example, for a falling object with steady state velocity, such a model is sufficient as we can predict displacement $\delta x$ and $\delta y$ without any input. On the other hand, $f_{1}^{n}$, which uses one history and the most complex set of features, is the most complicated model in the class $\mathcal{F}_1$. In terms of objects, the most complex set of input features that we consider is the union of the object's state features, relative state features with respect to an interacting object, and action.

The goal then is to choose the simplest model that achieves deterministic transitions within $\mathcal{F}_t$. To do so, we compute the entropy of the observed data for each function $H(f_{t}^{k}) = -\sum_{x_i} p(x_i) \log(p(x_i|f_{t}^{k}))$ where the summation is over all the observed data. We choose the simplest model that has entropy less than a predefined threshold $\epsilon_{ent}$. If none of the models in $\mathcal{F}_t$ satisfy the entropy threshold, we increase $t$ through an exponential back off scheme. Concretely, we increase the history to the next exponent of 2. Figure \ref{fig:pitfall:metaction}(a) shows an example (for our experiment in \textit{Pitfall!}) of the impact of this exponential back off scheme. With sufficient history, the entropy of the model eventually drops to zero. We use the same approach and same class of models for reward functions.

\begin{figure}[tb]
    \centering

    \subfloat[Model entropy]{\includegraphics[width=.36\linewidth]{img/pitfall_entropy.pdf}}%
    \quad
    \subfloat[Example trained models]{\includegraphics[width=.595\linewidth]{img/Tree.pdf}}%
    \quad
    \caption{Model selection}%

    \label{fig:pitfall:metaction}%
\end{figure}

\subsection{Temporal Abstraction}
In the previous section we proposed a method to avoid \textit{catastrophic error} in planning due to compounding errors. However compounding error can still limit our ability to plan for longer horizons. Object representation allows us to learn a simple predictive model of the dynamics for each object class and eliminates the necessity to use complicated function approximation methods. And thus enable us to plan for longer horizon.

As we observed in our experiments, objects transitions, especially action-dependent transitions, can show a highly nonlinear behaviour and dependency to multiple time step histories. Inspired by human's \textit{reaction time} and previous work~\citep{diuk2008object} we use the notion of macro action in the form of \textit{"act and then wait"} in order to learn a simple deterministic transition models.

Algorithm \ref{alg:macro} shows the pseudo code to learn the macro actions from predefined atomic actions (e.g. in the simplest form it can be the action space of the desired MDP; however, one can define them as any n-token combination of actions). In algorithm \ref{alg:macro} we augment all atomic actions with $k$ number of \textit{no-op} or wait, and then greedily decrease the number of no-ops followed by each action such that all model's can deterministically predict the next object state. The  goal is to have a model that achieves deterministic transition, to do so we measure the entropy of model's prediction with the observed data.

\begin{algorithm}
\KwIn{maximum number of no-op $k$, set of atomic actions $\mathcal{A}$}
\SetAlgoLined
macro actions $\gets$ atomic action followed by maximum number of no-op\;
mark all macro action as reducible\;
\While{there exist a reducible macro action}{
    $a \gets$select a reducible macro action and decrease number of no-op by one\;
    $\tau \gets$ compute entropy of model's prediction with new set of macro actions\;
    \If{$\tau \geq thresh$}{
        mark $a$ as non reducible macro action and restore the number of no-op for $a$\;
    }
}
 \caption{\bf Macro Actions}\label{alg:macro}
\end{algorithm}

Figure \ref{fig:meta_action}(b) shows the total entropy of model's versus total number of \textit{no-op} in \textit{mini-Pitfall!} environment. As algorithm progress entropy increases to pass the threshold. Figure \ref{fig:meta_action} (c) shows the entropy of all models while reducing number of \textit{no-op} for each action and keeping others constant. As it shows Jump Right requires 8, Down requires 4 and Right requires none \textit{no-op} afterward to achieves deterministic transition for all models. Running this algorithm in \textit{Pong Prime} environment results in two \textit{no-op} after each action, since the real dynamics uses 3 step history.

\section{Introduction}
The coupling of deep neural networks and reinforcement learning has led to exciting advances, enabling reinforcement learning agents that can reach human-level performance in many Atari2600 games \citep{mnih2015human, mnih2016asynchronous, silver2017mastering, hessel2017rainbow}.
However, such agents typically require hundreds of millions of time steps to learn to play well. This is in sharp contrast to people, who typically learn to play Atari games within a few episodes~\citep{lake2017building}. Prior work on human learning for Atari suggests that people may be systematically building models of the reward and dynamics in the domain and using those to plan efficiently \citep{tsividis2017human, dubey2018investigating}.

Given that human learners seemingly perform model-based RL very quickly, we are motivated to consider alternative approaches to current model-based RL, which often involves building complex predictive deep neural networks from scratch. Deep neural networks can require a large amount of data to accurately train, and performing perfect planning with those models is computationally expensive. Indeed, while there is a considerable amount of theoretical work done on tabular model-based reinforcement learning that suggests model-based approaches can be provably sample efficient~\citep{dann2017unifying, brafman2002r, strehl2008analysis}, there is much less success in using model-based reinforcement learning in extremely large environments, in part due to the challenges of learning simple accurate models in these domains.

Instead, in this paper, we investigate two issues in leveraging model-based RL to speed learning in large domains. First we explore how to perform approximate planning using models during model-based RL to support  exploration, assuming models are given.
Models can facilitate deep exploration, since one key benefit of using models is that it is often easier to quantify uncertainty in those models, and perform planning in a way to guide the agent towards exploring and reducing that uncertainty. Recent work has suggested the benefit of Thompson Sampling methods over optimism methods for reinforcement learning~\citep{osband2016posterior}, and, indeed, empirically Thompson Sampling methods have done very well in contextual bandits and small state space MDPs where it is possible to plan exactly. However, to our knowledge, there has not been an investigation of how these popular approaches scale to larger domains where it is computationally prohibitive to perform exact planning. We introduce optimistic MCTS, a variant of the popular planning technique Monte Carlo Tree Search,
and find that optimism here outperforms other approaches in several simulation experiments when planning can only be done approximately.

Second, while our first investigation explores how to plan to encourage exploration given a model, we further investigate how to choose the model class to support computational tractability and learning efficiency. Here we propose to learn object-oriented deterministic models of the domain. People may leverage and test models of object interactions during video game learning~\citep{tsividis2017human, dubey2018investigating}, and object-oriented learning has the nice benefit that data from all similar objects can be pooled when building a model. Prior work has shown that object-oriented model-based reinforcement learning can yield provably efficient learning and scale to larger domains~\citep{diuk2008object}. Deterministic models offer an additional benefit over object-oriented models--they require less data to train (since one does not have to model a large stochastic distribution of outcomes) and they have additional benefits for planning, reducing the branching factor of next states to 1. Indeed past work~\citep{diuk2008object} also proposed learning deterministic object-oriented models. In contrast, we investigate how to learn the transition model and temporal abstraction to make the world appear deterministic. In other words, we assume a candidate set of possible transition model classes and temporal abstractions, and perform model selection to select a level of temporal abstraction and model that deterministically predicts the outcome of an action.

We illustrate the potential benefit of these ideas by introducing an object oriented algorithm that uses prior knowledge of model classes and object representation, and show that our algorithm can learn to achieve positive reward in the notoriously difficult Atari game \textit{Pitfall!} within 50 episodes. Almost no RL methods have achieved positive reward on \textit{Pitfall!} without human demonstrations, and even with demonstrations, such approaches often take hundreds of millions of frames to learn~\citep{aytar2018playing, hester2017deep}. In contrast to demonstrations, we assume two forms of prior knowledge--a predefined object representation and a class of potential model features. Computer vision is rapidly advancing to the state that soon we will be able to easily extract objects from even artificial scenes like the Arcade Learning Environment.
The second assumption of candidate model classes is a stronger assumption, but a large set of models could be defined directly given the object classes and only incur a cost quadratic in the set of features.

While encouraging, such results should be mostly viewed as a case study. We believe the key contributions of our paper are not this particular demonstration on \textit{Pitfall!}, but rather the investigation of exploration approaches when planning can only be done approximately, and the benefit of selecting among model representations to support computationally tractable planning and fast learning. The second can be viewed as a bias/variance tradeoff and in future work we plan to consider how to identify and account for model biases that could limit asymptotic performance during the model-based planning procedure.

\section{Empirical Evaluation}\label{sec:pitfall}

In this section we will evaluate SOORL on an Atari game \textit{Pitfall!}. SOORL assumes access to an object detector, a predefined set of function classes and macro action (that can be learned using algorithm described in section \ref{sec:macro}).

Labeled data for object's in Atari game in not available, and in our experiment we extracted the objects from Atari RAM and screen information. The need for an object detector makes engineering burden of SOORL prohibitive to test the algorithm on all Atari games. Thus we focused on one of the hardest game (sparse reward and hard exploration~\citep{bellemare2016unifying}), \textit{Pitfall!}, where all the previous methods (without human demonstrations) failed to achieve any positive reward. We showed that object representation can be extremely helpful in this hard exploration game and SOORL can achieve a positive reward in \textit{Pitfall!} without human demonstration.

\textit{Pitfall!} is an Atari2600 environment where the goal is to have the agent traverse through multiple rooms (255 in total) while collecting rewards and avoiding obstacles. It is arguably one of the hardest Atari2600 game~\citep{hester2017deep} due to its large map, sparse positive and dense negative rewards that necessitate deep exploration and long-horizon planning. The $\epsilon$-greedy exploration strategy completely fails in this environment, and more recent count-based exploration \citep{bellemare2016unifying} does not show much performance boost due to the sparsity of positive reward. Pitfall is difficult even for human players without prior knowledge of the game -- \citep{hester2017deep} reports that human performance varies from 3662 to 47821 points, whereas for other hard Atari games, this variation is much smaller (e.g. from 32300 to 34900 for Montezuma's revenge).

\subsection{Details}
All objects information are extracted from RAM and screen information, and each object's attribute is location $(x,y)$ and bounding box size $(w,h)$. Objects are considered interacting with each other if bounding boxes collide. Transition and reward models for each object are based on the method described in Section \ref{sec:model_learning}. The features used are a Cartesian product of object size $(w,h)$, object location $(x,y)$ and object intersection $(x',y')$. Ignoring null input, this Cartesian product results in 7 different feature sets.

As described in section \ref{sec:exp} we used optimism based exploration method, by assigning reward $R_{max}$ to all unseen interactions and transitions. As we observe reward for each interaction we update the model, based on model based interval estimation~\citep{strehl2008analysis}. Additionally in order to further incentivize exploration we split the screen into $N \times  M$ grids and keeping a count of the number of times agent visits each grid. The agent is given a reward bonus $\beta n(s)^{-1/2}$ based on visit count $n(s)$.

For value function, we used discrete object's location with the same split used for optimism bonus, and computed the empirical transition $\hat{T}(o'|o,a)$ and empirical reward with optimism bonus $\hat{r}(o,a) + \beta n(s)^{-1/2}$, and at the beginning of each episode, we performed value iteration.

\subsection{Performance and Discussion}

Figure \ref{fig:pitfall}(a) shows an increasing number of rooms being discovered across episodes. On average, the agent discovers 21 rooms within 50 episodes, and in total across 20 runs the agent discovers 27 different rooms. This validates our hypothesis that optimistic MCTS drives deep exploration, that we also showed in a smaller domains in section \ref{sec:exp}.

 Figure \ref{fig:pitfall}(b) shows accumulative reward for each episode of SOORL and compares them to the other state of the art algorithm. Results of count-based \citep{bellemare2016unifying}, DQfD \citep{hester2017deep}, A3C \citep{mnih2016asynchronous} and DQN \citep{mnih2015human} are reported at the time of evaluation. Our average score across all episodes and all runs is $-193.5 \pm 595.8$ and SOORL score for the best episode across all runs in $606.6 \pm 1254.5$, which is higher than all scores that were reported at the time of evaluation. To the best of our knowledge, this is the first approach which manages to get positive rewards on \textit{Pitfall!} without human demonstrations.  Sample videos of the agent reaching the two closest positive rewards can be found here: \url{https://youtu.be/GvenPZMJiTg} (4000 reward)\,\,
\url{https://youtu.be/74F-ta5LyuA} (2000 reward)

Figure \ref{fig:pitfall} (c) shows the percentage of runs that got a positive reward. More than $80\%$ of runs got a positive reward in 50 episodes that shows consistency of our approach across multiple runs. Due to simple dynamics model that can be learned fast SOORL is extremely sample efficient in comparison to other deep RL method that often takes millions of frame to find a good policy. However, end-to-end deep RL methods use significantly less prior knowledge and using raw pixels as input, thus a direct comparison with them is unfair. We have also provided macro actions and object information for DQN and DDQN but those methods are not designed to take advantage of object representation and did not show a boost in performance. On the other hand, SOORL uses much less prior knowledge than methods with human demonstration~\citep{aytar2018playing, hester2017deep}, where human guidance enormously reduce the challenge of exploration.

Additionally, macro actions are provided for SOORL, but as shown in section \ref{sec:macro} these can be learned online. Integrating this temporal abstraction with SOORL can increase the sample complexity by $\mathcal{O}(|A|K)$, where $K$ is the maximum number of no-ops.

\begin{figure}[tb]
    \centering
    \subfloat[Room Discovery]{\includegraphics[width=.29\linewidth]{img/pitfall_room.pdf}}%
    \subfloat[][Reward per episode]{\includegraphics[width=.31\linewidth]{img/pitfall_reward.pdf}}%
    \subfloat[][Percentage of runs with positive reward]{\includegraphics[width=.33\linewidth]{img/pitfall_perc.pdf}}%
    \caption{performance of SOORL on Pitfall!}%
    \label{fig:pitfall}%
\end{figure}

\section{Preliminaries}

We consider a finite horizon Markov Decision Process (MDP) $\langle \mathcal{S}, \mathcal{A}, T, R, \gamma \rangle$, where $\mathcal{S}$ is the state space, $\mathcal{A}$ the action space, $T:\mathcal{S} \times \mathcal{A} \rightarrow \mathcal{S}$ the transition function, $R:\mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ the reward function, and $\gamma$ the discount factor. The goal of the RL agent is to maximize the expected discounted reward $\mathbb{E}_{\pi}[\sum_{t=0}^{T}\gamma^t R(s_t, a_t)]$ following a policy $\pi$.
\section{Related Work}

Model based RL has accomplished great success in tasks in which a perfect simulator is known~\citep{silver2016mastering, silver2017mastering}, mostly using Monte Carlo Tree Search algorithms like UCT~\citep{kocsis2006bandit, chaslot2010monte}. Recent work has focused on applying deep learning to model-based RL by learning the model online~\citep{rosin2011nested, finn2017deep, lenz2015deepmpc, weber2017imagination}. In contrast to these methods, we seek to learn a simple model based on object representation.

Exploration has been extensively studied in the tabular setting~\citep{brafman2002r,strehl2008analysis,jaksch2010near, osband2016posterior}. However, these methods do not scale well to large MDPs and often result in poor sample complexity. Additionally, these methods assume exact planning that might not be feasible in large state space. Recent approaches~\citep{bellemare2016unifying, ostrovski2017count, tang2017exploration} proposed an extension of count based exploration to large MDPs. Despite good asymptotic performance, when compared with humans \citep{tsividis2017human, lake2017building}, these methods require orders of magnitude more samples.

Bayesian RL methods also provide an effective balance between exploration and exploitation~\citep{ghavamzadeh2015bayesian}. When exact planning is possible, they provide strong guarantees. However, these methods remain computationally intractable in large state spaces. Recent works propose an extension of these methods to large MDPs~\citep{osband2016deep, azizzadenesheli2018efficient, fortunato2017noisy}. However, these methods are unable to show substantial improvement in hard exploration, sparse reward environments.

A closely related line of research, finite horizon planning~\citep{kearns2002sparse, mannor2007bias, kearns1994introduction}, has noted how planning horizon can affect planning loss~\citep{kearns2002near, strehl2009reinforcement}. Recent study has shown that shorter planning horizons might be better when there is model inaccuracy~\citep{jiang2015dependence}. In contrast, in this work, we studied how imperfect planning can affect exploration.

OOMDP \citep{diuk2008object} defines a notion borrowed from relational MDPs \citep{guestrin2003generalizing}, and uses objects to learn models and perform model based planning. Model free methods that use object representation \citep{garnelo2016towards, roderick2017deep, cobo2013object} fail to scale to large MDPs and do not leverage object representation for deep exploration. The main difference between our approach and other object oriented approaches is that we perform scalable planning with strategic exploration by leveraging objects to learn simple dynamics models.

\section{SOORL: Strategic Object Oriented Reinforcement Learning}
In this section we put together the insights from previous sections and propose a novel model-based object oriented RL algorithm, Strategic Object Oriented RL (\textbf{SOORL}). SOORL assumes access to an object detector, that returns a list of objects with their attributes (i.e. location and bounding box), an interaction function and macro actions (that can be learned with algorithm \ref{alg:macro}).

Algorithm \ref{alg:soorl} shows a pseudo code of SOORL. At each step, SOORL performs lookahead planning with UCT algorithm, learn and select appropriate transition and reward models for object representation and performs optimism based exploration.

\begin{algorithm}
\KwIn{object detector $f(s)$, lookahead planning depth $d$, number of rollouts $l$}
initialize\;
\For{each episode e}{
    train value function V on replay buffer $\mathcal{D}$\;
    \For{each step i}{
    $o_i \gets$ detect objects with object detector $f(s_i)$\;
    $Q(s_i,a) \gets$ perform lookahead planning with depth $d$ and $l$ rollouts\;
    take action $a_i ={argmax}{Q(s,.)}$ and update replay buffer $\mathcal{D} = \mathcal{D} \cup (o_i, a_i, o_{i+1}, r_i)$\;
    update transition and reward models with $(o_i, a_i, o_{i+1}, r_i)$
    }
}
\caption{{\bf SOORL} \label{alg:soorl}}
\end{algorithm}

\textbf{Model Learning:} SOORL uses the method described in section \ref{sec:model_learning} with Cartesian product of object size $(w,h)$, object location $(x,y)$ and object intersection $(x',y')$ as features. Ignoring null input, this Cartesian product results in 7 different feature sets.

\textbf{Exploration:} Count based models allow SOORL to efficiently perform the knows what it knows (KWIK)~\citep{li2008knows} scheme for exploration (optimistic MCTS). Concretely, if our algorithm queries the transition or reward model with a previously unseen input, we consider the resulting state as a state with $R_{max}$ reward. $R_{max}$ reward is also considered for any previously unseen object interactions. As we observe the reward for each interaction we update the reward model based on model-based interval estimation~\citep{strehl2008analysis}.

\textbf{Planning:} At the beginning of each episode, a value function is trained based on previously seen transitions and rewards. Value function $V: \mathcal{O} \rightarrow \mathbb{R}$ is trained over object states and can generally be any function approximation methods.

Lookahead planning is performed by UCT~\citep{kocsis2006bandit} algorithm with $l$ rollouts and depth $d$. Algorithm \ref{alg:planning} shows pseudo code of planning, at each planning step, SOORL computes object interactions, selects appropriate models based on interactions and object states then predicts rewards and next object state. At depth $d$ of planning SOORL uses value of the object state $V(o_d)$ trained at the beginning of each episode.

\begin{algorithm}[h]
\KwIn{objects $o$, depth $d$, rollouts $l$, value function $V$}
\For{number of rollouts $l$}{
    set current depth $i$ to zero\;
    \While{$i \leq d$}{
        \If{$i == d$}{
            update $Q$ values with $V(o_i)$\;
            break\;
        }
        detect interactions $I_i$ with objects $o_i$ and select models $T,R$\;
        take action $a_i = argmax Q(s_i,a) + c \sqrt{\frac{log N(s,a)}{N(s)}}$\;
        obtain next object state $o_{i+1}$ and reward $r_{i}$ with $R(o_i,I_i), T(o_i,I_i)$ and update $Q$\;
    }
}
\caption{{\bf Lookahead Planning} \label{alg:planning}}
\end{algorithm}

redpajama_set_name: RedPajamaArXiv


If you'll be in and out of the car all day with your twins, you can't get any better than the Combi Twin Savvy LX. Weighing in at a mere nineteen pounds, it's easy on your back. Whether your twins are infants or toddlers, they'll love the open view from this side-by-side model. Plus, since both seats recline fully, babies are free to stretch out and take a nap whenever the mood strikes. Although the back canopy pockets are great for stowing gear, the undercarriage basket is a bit compact.
From a practical point of view, the Maclaren Twin Triumph has it down. This is one sturdy stroller that will last from birth to toddlerhood. And at 21 pounds, it's a breeze to fold, lift, and store. But what I adore is the attention to detail and style. Who says you can't be a hip mama?
Peg Perego Tender is everything a tandem is not — lightweight (it weighs slightly more than most side-by-side models) and easy to drive thanks to all-wheel suspension. Plus this is one tandem stroller where both front and back seats fully recline; although, it's a bit hard to access undercarriage basket when they are.
The Mountain Buggy Urban Double is just as what an active mom of multiples needs. Completely versatile, it does double duty whether you're out for a high-paced power walk in the neighborhood or headed to the mall for a day of shopping. And at only 29" wide, the Mountain Buggy Urban Double can easily glide through any standard doorway. The only downside is its heft, making it a challenge to hoist in and out of your trunk.
I've never met a mom with twins who didn't rave about BOB. And with good reason — it drives like a dream whether in tight spaces or on the open road, and folds up easily in two steps although a bit heavy to lift. But what I like best about the BOB is its individual design approach — each compartment is fully independent so your babies will be like two peas in their own pods!
If I were a stroller designer, this is the model I'd dream up. Perfect for moms with twins, the Baby Trend Double Snap N' Go is a stroller frame that can accommodate most infant car seats. No need to wake your sleeping duo when you leave the car or house, just snap them into the stroller frame and you're off. Although you'll have to upgrade to another stroller once your twins outgrow their infant seats, the convenience and peace of mind it offers during the first few chaotic months with multiples is well worth the slim price.
You can't beat the narrow profile of this tandem; yet, it still maneuvers beautifully. Lots of added benefits, too, like the huge under seat storage basket for all your twin gear. Since the Graco DuoGlider accepts Graco infant car seats in the front as well as the back this is one stroller that will be around as your twins grow.
Easy to fold, easy to maneuver, and easy on the wallet. It even stands by itself when folded. For this price you can even overlook its one minor flaw: its 27"-wide profile.
I love this stroller for its versatility — it's just what every parent of twins needs. Snap in infant car seats (it accepts a variety of manufacturers) or move the seats around to different positions to accommodate the whim of your twins. But best of all, it handles beautifully for a tandem and looks sharp to boot!
Gear to make air travel with babies smooth and easy.
Transport two kids more easily with double strollers.
Fast, stable, and responsive junior slalom skis.
These toys make it more fun for kids to play outside.


text:
Q: How to create a dynamic pivot table with MySQL/MariaDB and LibreOffice Calc in Ubuntu? I found the following video which might be what I want:
https://www.youtube.com/watch?v=RUyZYV6vV1c
I have a MariaDB in localhost, with Ubuntu. I would normally use Excel, but need to use LibreOffice Calc because of Ubuntu, and it is free.
I need to create simple pivot charts of one SQL query, and to be able to update it by refreshing the pivot after the database is updated.
I found how to import the .jar in the video, but cannot find the option to connect to the database and write the query and link it to a pivot table/chart. How can I do this? Is it possible? If not, is there a free way to get a similar functionality in Ubuntu?

A: Go to Insert -> Pivot Table and specify Data source registered in LibreOffice.  This will show a dialog to set up the database connection.

Once the pivot table is created, the data may be updated by right clicking and selecting Refresh.

redpajama_set_name: RedPajamaStackExchange


George E. Kuehn is a top-rated attorney selected to Super Lawyers for 2006 - 2008, 2010 - 2017. He works at Butzel Long, located in Ann Arbor, Michigan, and provides legal services for issues involving Business / Corporate and Mergers & Acquisitions and Closely Held Business to the surrounding community.
George Kuehn completed legal studies at The University of Michigan Law School and graduated with the class of 1973.


text:
Smart Electric Drive Forum
Smart ED Forum and Electric Vehicle News
Smart Electric Drive Availability and Release Markets
Currently in its third generation, Smart started production of the ForTwo Electric Drive on June 12,2012 at the Hamback, Germany plant.
Smart Electric Drive on assembly line
Smart has been fairly quiet about when the Smart Electric Drive will be available in different markets, but here is what we know:
The Smart Electric Drive is currently available in Germany, Belgium, France, Switzerland, Italy and Portugal
US launch planned for Spring 2013, with some news sources saying the Smart ED is coming in late March / early April
Following that, Smart will launch the EV in 30 other markets
Smart ForTwo Electric Drive in Europe
In 2016, the new generation Smart ForTwo electric will roll out with LG Chem batteries, with North America and the rest of the world waiting until 2017 to get the updated version of the EV.
Smart Electric Drive US Availability
In August 2015, Smart introduced the new generation of its flagship model the Smart ForTwo. However, only the diesel powered version will be getting updated in November 2015. The Smart ForTwo Electric Drive will live on in its current generation until 2017.
In February 2014, Smart announced the 2014 ForTwo Electric Drive model year will be available nationwide, not just in the CARB states as it was with the 2013 model year. Smart also lowered the lease price from $199 per month, to $99 per month (both have an additional $80 per month battery rental cost).
Smart USA has announced the first Smart Electric Drives will be released on May 15th. Availability will be limited to CA, CT, ME, MA, MD,NJ,NY,OR,RI, and VT until a national roll-out begins September 1st.
Set to launch in later March or early April in the USA. Some confusion was caused by EV sales reports showing 2 were sold in January – those have been confirmed to be second generation sales, not the new and improved 3rd generation Smart electric vehicle.
Smart Electric Drive Canada Availability
The Smart ForTwo Electric Drive will be arriving in Canada in March 2012. Rated at 68 miles of range, it might not seem like enough range. However, expect the range to be much greater in the city since the Electric Drive is a giant square so wind resistance at highway speeds really affects the range ratings.
3 Responses to Availability
Jeff Darko says:
As of April 4, Smart is reporting 0 sales of the Electric Drive for March, so I guess it is safe to say deliveries didn't happen in late March.
I went to buy a smart 2 weeks ago ( Quebec, Canada), they had one in stock but was sold already and was told by sales that if I order right now, I will get one in 6 to 8 month!
Wow – is that Smart Canada that wouldn't have any for 6 to 8 months, or just that dealerships specifically?
Smart ED Forum Posts
Re: SERVICE MANUAL
26/Jun/19 - 7:06 pm
Re: Clicking sound when initial moving forward with the thro
Re: Error message on my dash: Malfunction Serv.Req
Re: Main battery cuts out while in motion
25/May/19 - 10:43 pm
Re: Gen 4 Smart fortwo Electric Drive
Smart Electric Drive Articles
90% of US buyers opt for the Battery Assurance Plus program
Smart ForTwo Electric Drive will be released May 15th in US
Smart ED Production
Smart ForTwo Electric Drive production ramping up to meet demand
Smart Electric Drive production photos
Smart Electric Drive Forum, ForTwo Electric Drive

redpajama_set_name: RedPajamaCommonCrawl


text:
Malmberget (lulesamisch Málmmavárre; meänkieli Malmivaara) ist ein Ort in der schwedischen Provinz Norrbottens län und der historischen Provinz Lappland, etwa 70 km nördlich des Polarkreises.

Geografie und Geschichte

Der Ort in der Gemeinde Gällivare ist hauptsächlich für seine Eisenerzgruben bekannt. 1741 wurde hier zum ersten Mal Eisenerz gebrochen. Nachdem 1888 die Erzbahn zunächst vom Ostseehafen Luleå bis zu den Gruben fertiggestellt war (1902/1903 auch zum ganzjährig eisfreien Narvik am Atlantik), setzte ein sogenannter "Erzrausch" ein, vergleichbar mit dem Goldrausch in Nordamerika. In den ersten Jahren lebten die Bergmänner in Hütten, die sie aus leeren Dynamitkisten zusammengezimmert hatten.

Durch Malmberget verläuft eine 250 Meter tiefe Grube, die den Ort in zwei Teile teilt. Kontinuierlich werden Gebäude und Wege abgerissen, da sie in das Gebiet mit Einsturzgefahr gelangen. So wurde 1974 eine Kirche vom Rand der Grube in das vom Erz befreite Innere der Grube versetzt. Auch andere historische Gebäude wurden nicht abgerissen, sondern in einer Entfernung von einigen Kilometern auf ein neues Fundament gesetzt. In den letzten Jahrzehnten hat sich die Einwohnerzahl stark verringert. Auch hierfür ist die Ausdehnung der Gefahrenzone einer der Hauptgründe. So begann man, die Menschen ins drei Kilometer südlich gelegene Gällivare umzusiedeln, das mittlerweile größer ist als der ursprüngliche Hauptort Malmberget.

Der heute unbebaute Streifen zwischen den beiden Ortsteilen ist etwa 500 Meter breit, sodass das Statistiska centralbyrån 2015 erstmals zwei separate Tätorter auswies. Der etwas bevölkerungsreichere Westteil, in dem sich auch die meisten öffentlichen Einrichtungen befinden, heißt weiterhin Malmberget, der östliche Teil mit den traditionellen Ortsteilbezeichnungen Malmsta und Kilen wird als Tätort Malmberget östra ("Malmberget Ost") genannt. Die Einwohnerzahl beider Ortsteile zusammen beträgt heute weniger als ein Drittel des Maximalwertes aus den 1970er-Jahren.

In Malmberget gibt es ein Grubenmuseum, in dem die Geschichte des örtlichen Erzbergbaus von der Entdeckung der Lagerstätten bis in die heutige Zeit dargestellt ist. Auch eine außergewöhnliche Mineralsammlung und eine Fotoausstellung sind hier zu besichtigen.

Söhne und Töchter der Stadt
 Harry Åhman (1912–1992), Fernschachmeister und ein Schachorganisator
 Kurt Andersson (* 1939), Eishockey- und Fußballnationalspieler
 Göran Forsmark (1955–2020), schwedischer Schauspieler
 Jan Boklöv (* 1966), Skispringer
 Olle Martinsson (* 1944), Skispringer
 Åsa Regnér (* 1964), Politikerin
 William Poromaa (* 2000), Skilangläufer

Varia
Malmberget ist Schauplatz des 44. Kapitels von Selma Lagerlöfs Roman Die wunderbare Reise des kleinen Nils Holgersson mit den Wildgänsen.

Weblinks

Einzelnachweise

Aktives Bergwerk
Bergwerk in Schweden

redpajama_set_name: RedPajamaWikipedia


Looking for a life changing destination experience with a program designed to nurture and nourish you on a multi-dimension level? We are taking expressions of interest for a tropical wellness retreat focusing of the body, mind and spirit. We are sourcing locations in our favourite part of the world; Bali for a 2019 retreat. Stay tuned, we will update you on our progress soon.


Standard rated : By default all supply of goods and services and imports in the UAE (and the GCC) will be considered as subject to Vat @ 5% known as standard rated supplies.
Supply of certain Healthcare services, and supply of relevant goods and services.
Exempt Supplies : Financial Services (Fee based services taxable and Margin based services Exempt), Residential properties, Bare land andLocal passenger transport.