text:
\section{Introduction}
\label{sec:intro}
Long horizons, along with the state dependent transitions, is the differentiator between reinforcement learning (RL) problems and simpler contextual bandit problems.
In the former (RL), actions taken at early stages could substantially impact the future; with regards to planning, the agent must not only consider the immediate reward but also the possible future transitions into differing states.
In contrast, for the latter (contextual bandit problems), the action taken at each time step is independent of the future, though it does depend on the current state (the ``context''); we can consider a contextual bandit problem as a Markov decision process (MDP) with a horizon equal to one.
For a known contextual bandit problem, it is sufficient for the agent to act myopically by choosing the action which maximizes the current reward as a function of the current state.

~\citep{jiang2018open}  proposed to study this distinction by examining how the sample complexity depends on the horizon length (of each episode) in a finite horizon, episodic MDP, where the MDP is unknown to the agent.
Clearly, as the horizon $H$ grows, we will observe more samples in each episode.
To appropriately measure the sample complexity (see~\cite{jiang2018open}), we consider a normalized notion: we
are interested in the \emph{number of episodes} it takes to provably discover a policy whose value is
$\varepsilon$ near to that of the optimal value, where the value is measured
by the \emph{normalized} cumulative reward in each episode (i.e. values are normalized to be bounded between $0$ and $1$).
Here, all existing upper bounds depend polynomially on the horizon, while
lower bounds do not provide \emph{any} dependence on the horizon $H$.
Motivated by these observations, \citet{jiang2018open} posed the following open problem in COLT 2018:
\begin{center}
\emph{Can we prove a lower bound that depends polynomially on the planning horizon, $H$?}
\end{center}
\cite{jiang2018open} conjectured a linear dependence on the horizon, which is consistent with all existing upper bounds, which scale at least linearly with the planning horizon~\citep{dann2015sample,azar2017minimax,zanette2019tighter} (see
Section~\ref{sec:rel} for further discussion).
In other words, the conjecture is that, even when the values are
appropriately normalized, long
horizon RL is polynomially more difficult than short horizon RL.

This work resolves this question, with,  perhaps surprisingly, a \emph{negative} answer.
Here we give an informal version of our main result.
\begin{theorem}[Informal version of Theorem~\ref{thm:main}]\label{thm:informal}
	Suppose the reward at each time step is non-negative and the total reward of each episode is upper bounded by $1$.
	Given any target accuracy $0 < \varepsilon < 1$ and a failure probability $0 \le \delta \le 1$,
	the \emph{Online Trajectory Synthesis} algorithm returns an $\varepsilon$-optimal policy with probability at least $1 - \delta$ by sampling at most $\mathrm{poly}\left(\abs{\mathcal{S}},\abs{\mathcal{A}},\log H, \frac{1}{\varepsilon},\log\frac{1}{\delta}\right)$
	episodes, where $\abs{\mathcal{S}}$ is the number of states and $\abs{\mathcal{A}}$ is the number actions.
\end{theorem}
Importantly, this sample complexity scales only \emph{logarithmically} with $H$.
Thus, there does not exist a lower bound that depends polynomially on the planning horizon.
This result is an exponential improvement on the dependency on $H$ over existing upper bounds.

In the context of the discussion in \cite{jiang2018open}, these results suggest that perceived differences between long horizon RL and contextual bandit problems (or short horizon RL) are not attributable to the horizon dependence, at least in a minimax sense. It is worthwhile to note that while our upper bound is logarithmic in $H$, it does have polynomial dependence (beyond just being linear) on the number of states (or ``contexts'') and the number actions. We return to the question of obtaining an optimal rate in Section~\ref{sec:dis}.

\section{Preliminaries}
\label{sec:pre}
Throughout this paper, for a given integer $H$, we use $[H]$ to denote the set $\{1, 2, \ldots, H\}$.
For a condition $\mathcal{E}$, we use $\mathbb{I}[\mathcal{E}]$ to denote the indicator function, i.e., $\mathbb{I}[\mathcal{E}] = 1$ if $\mathcal{E}$ holds and $\mathbb{I}[\mathcal{E}] = 0$ otherwise.

Let $M =\left(\mathcal{S}, \mathcal{A}, P ,R, H, \mu\right)$ be a \emph{Markov Decision Process} (MDP)
where $\mathcal{S}$ is the finite state space,
$\mathcal{A}$ is the finite action space,
$P: \mathcal{S} \times \mathcal{A} \rightarrow \Delta\left(\mathcal{S}\right)$ is the transition operator which takes a state-action pair and returns a distribution over states,
$R : \mathcal{S} \times \mathcal{A} \rightarrow \Delta\left( \mathbb{R} \right)$ is the reward distribution,
$H \in \mathbb{Z}_+$ is the planning horizon  (episode length),
and $\mu \in \Delta\left(\mathcal{S}\right)$ is the initial state distribution.
We refer to a \emph{contextual bandit problem} as an MDP with $H=1$.

A (non-stationary) policy $\pi$ chooses an action $a$ based on the current state $s \in \mathcal{S}$ and the time step $h \in [H]$.
Formally, $\pi = \{\pi_h\}_{h = 1}^H$ where for each $h \in [H]$, $\pi_h : \mathcal{S} \to \mathcal{A}$ maps a given state to an action.
The policy $\pi$ induces a (random) trajectory $s_1,a_1,r_1,s_2,a_2,r_2,\ldots,s_{H},a_{H},r_{H}, s_{H + 1}$,
where $s_1 \sim \mu$, $a_1 = \pi_1(s_1)$, $r_1 \sim R(s_1,a_1)$, $s_2 \sim P(s_1,a_1)$, $a_2 = \pi_2(s_2)$, $r_2 \sim R(s_2, a_2)$, $\ldots$, $a_H = \pi_H(s_H)$, $r_H \sim R(s_H, a_H)$, $s_{H + 1} \sim P(s_H, a_H)$.\footnote{In this paper, for simplicity, we assume the agent receives samples from both $R(s_H, a_H)$ and $P(s_H, a_H)$ in the last time step.}

We assume, almost surely,  that $r_h \ge 0$ for all $h \in [H]$ and
\[
\sum_{h = 1}^{H}r_h \in [0, 1] .
\]
In other words, we work with normalized cumulative reward.
It is worth emphasizing that this assumption is weaker than the
standard one in that we do not assume the
immediate rewards $r_h$ are bounded (see Assumptions~\ref{asmp:uniform}
and~\ref{asmp:total_bounded} in Section~\ref{sec:rel} for comparison).
Our goal is to find a policy $\pi$ that maximizes the expected total
reward, i.e.
\[
\max_\pi \mathbb{E} \left[\sum_{h=1}^{H} r_h \mid \pi\right] .
\]
We say a policy $\pi$ is $\varepsilon$-optimal if $\mathbb{E}
\left[\sum_{h=1}^{H} r_h\mid \pi\right] \ge \mathbb{E}
\left[\sum_{h=1}^{H} r_h\mid \pi^*\right] - \varepsilon$, where
$\pi^*$ denotes an optimal policy.

An important concept in RL is the $Q$-function.
Given a policy $\pi$, a level $h \in [H]$ and a state-action pair
$(s,a) \in \mathcal{S} \times \mathcal{A}$, the $Q$-function is defined as:
\[
Q_h^\pi(s,a) = \mathbb{E}\left[\sum_{h' = h}^{H}r_{h'}\mid s_h =s, a_h = a, \pi\right].
\]
Similarly, the value function of a given state
$s \in \mathcal{S}$ is defined as:
\[
V_h^\pi(s)=\mathbb{E}\left[\sum_{h' = h}^{H}r_{h'}\mid s_h =s,
  \pi\right].
\]
For notational convenience, we denote $Q_h^*(s,a) = Q_h^{\pi^*}(s,a)$
and $V_h^*(s) = V_h^{\pi^*}(s)$.

\section{Related Work}
\label{sec:rel}
We now discuss related theoretical work on tabular RL,
largely focussing on the episodic, finite horizon settings due to
these being most relevant in our setting (also see
\cite{jiang2018open}).   Here, most results focus either on the regret
minimization problem, which aims to collect maximum reward for
a limit number of interactions with the environment, or on the
sample complexity of PAC learning for finding a near-optimal policy.

In episodic tabular RL,  sample complexities will depend on
$\abs{\mathcal{S}}$, $\abs{\mathcal{A}}$ and $H$, all of which are assumed to
be finite. In many works, the standard assumption on the rewards are
that: $r_h \in [0,1]$ and hence $\sum_{h=1}^H r_h \in [0, H]$.
However, as pointed out in \cite{jiang2018open}, to have a fair
comparison with contextual bandits (and short horizon RL) and illustrate the hardness due to
the planning horizon, one should scale down by an $H$ factor in order to
normalize the total reward, so that it is bounded in $[0,1]$.

Following \cite{jiang2018open} (also
see \cite{kakade2003sample}), we can rescale the total reward
(the value functions) to be bounded in $[0,1]$ as follows:
\begin{asmp}[Reward Uniformity, the standard assumption]
\label{asmp:uniform}
The reward received at the $h$-th time step $r_h$ satisfies
$r_h \in [0,1/H]$ for $h=1,\ldots,H$, and hence $\sum_{h=1}^{H}r_h \le 1$.
\end{asmp}
Furthermore, following \cite{jiang2018open}, we can further relax this assumption to
a weaker version where we only bound the total reward as follow.
\begin{asmp}[Bounded Total Reward (see e.g.~\cite{krishnamurthy2016pac})]
	\label{asmp:total_bounded}
	The reward received at the $h$-th time step $r_h$ satisfies
        $r_h \ge 0$ for $h=1,\ldots,H$, and we assume that total
        reward is bounded as $\sum_{h=1}^{H}r_h \le 1$.
\end{asmp}
Assumption~\ref{asmp:total_bounded} is more natural in environments
with sparse rewards, as argued in \cite{jiang2018open}.
As pointed out in
\cite{jiang2018open}, this scaling permits more fair comparisons with
contextual bandit problems.  Furthermore, Assumption~\ref{asmp:total_bounded} is clearly more
general than Assumption~\ref{asmp:uniform}, so any bound under
Assumption~\ref{asmp:total_bounded}, also implies a bound under Assumption~\ref{asmp:uniform}.

Under Assumption~\ref{asmp:uniform}, a line of work has attempted to provide tight sample complexity bounds~\citep{azar2017minimax,dann2015sample,dann2017unifying,dann2019policy,jin2018q,osband2017posterior}.
To obtain an $\varepsilon$-optimal policy, state-of-the-art results show
that $\widetilde{O}\left(\frac{\abs{\mathcal{S}}\abs{\mathcal{A}}}{\varepsilon^2} +
  \frac{\mathrm{poly}\left(\abs{\mathcal{S}},\abs{\mathcal{A}},H\right)}{\varepsilon}\right)$
episodes suffice~\citep{dann2019policy,azar2017minimax}.\footnote{$\widetilde{O}\left(\cdot\right)$ omits logarithmic factors.}
In particular, the first term matches the lower bound $\Omega\left(\frac{\abs{\mathcal{S}}\abs{\mathcal{A}}}{\varepsilon^2}\right)$ up to logarithmic factors~\citep{dann2015sample,osband2016on}.

There are two concerns with these work.
First, these bound are optimal only in the regime $\varepsilon \in [0,1/H]$.\footnote{In \cite{dann2015sample}, it appears that $\mathrm{poly}(\abs{\mathcal{S}}^2\abs{\mathcal{A}}/\varepsilon^2)$ episodes are sufficient for $\varepsilon\in[0, 1/H]$. However, it is not clear whether the requirement of $\varepsilon\in[0,1/H]$ can be relaxed to $\varepsilon\in[0, 1]$.
}
However, as explained in \cite{jiang2018open}, in many scenarios with
a long planning horizon such as control, this regime is not
interesting.\footnote{See the motor control problem described in
  Section 2.1 of \cite{jiang2018open}.} In particular, the more
interesting regime is when $\varepsilon \gg 1/H$.
Secondly, Assumption~\ref{asmp:uniform} is a strong assumption as it cannot model environments with sparse rewards.
\cite{jiang2018open} thus argued that one should study tabular RL with
a more general assumption, i.e. under Assumption~\ref{asmp:total_bounded}.

Note that environments under Assumption~\ref{asmp:total_bounded} can have one-step reward as high as a constant.
These are the sparse reward environments which are often considered to be hard.
\citet{jiang2018open} conjectured that under Assumption~\ref{asmp:total_bounded}, there is a lower bound of the sample complexity that scales \emph{polynomially} in $H$.
Under Assumption~\ref{asmp:total_bounded}, upper bounds in \cite{azar2017minimax,dann2019policy} will become $\widetilde{O}\left(\frac{\abs{\mathcal{S}}\abs{\mathcal{A}}H^2}{\varepsilon^2}\right)$ whose dependency on $H$ is not tight even in the $\varepsilon \ll 1/H$ regime (recall the lower bound is still $\Omega\left(\frac{\abs{\mathcal{S}}\abs{\mathcal{A}}}{\varepsilon^2}\right)$).

Recently, under Assumption~\ref{asmp:total_bounded}, \citet{zanette2019tighter} gave a new algorithm which enjoys
a sample complexity of $\widetilde{O}\left(\frac{\abs{\mathcal{S}}\abs{\mathcal{A}}}{\varepsilon^2} + \frac{\mathrm{poly}\left(\abs{\mathcal{S}},\abs{\mathcal{A}},H\right)}{\varepsilon}\right)$.\footnote{In fact, \citet{zanette2019tighter} proved a even stronger result that the first term can be a problem-dependent quantity which is upper bounded by $\frac{\abs{\mathcal{S}}\abs{\mathcal{A}}}{\varepsilon^2} $.}
In particular, the first term matches the lower bound in the regime $\varepsilon \ll 1/H$.
Unfortunately, the second term still scales \emph{polynomially} with $H$.

In another related ``generative model'' setting, where the agent can query samples freely from any state-action pair of the environment, the question of sample complexity is also posed as the total number of batches of queries  (a batch corresponds to $H$ queries) to the environment to obtain an $\varepsilon$-optimal policy.
Results in this setting include \cite{kearns1999finite, kakade2003sample, singh1994upper, azar2013minimax, sidford2018variance, sidford2018near,agarwal2019optimality}. However, even with this much stronger query model, we are not aware of any algorithm whose sample complexity scales sublinearly in $H$.

The main barrier of achieving logarithmic dependency on $H$ is that almost all the above mentioned works rely on a dynamic programming step (i.e., the Bellman update) in learning the optimal value functions.
In this paper, we bypass this long-standing barrier using a completely different approach.
We provide a new technique to simulate the Monte Carlo methods to evaluate a set of given policies using existing samples and to do exploration.
Interestingly, this technique is related to the method  proposed in
\cite{fonteneau2013batch} for policy evaluation, though there is no
exploration component in their paper.
Our algorithm has some similarities to the ``Trajectory Tree''  method in \cite{kearns2000approximate} in that both attempt to simultaneously evaluate many policies on a ``tree'' of collected data (using a generative model); a key difference in our approach is that (due to the adaptive nature of data collection) we are not able to explicitly build a tree or reuse data on trajectories.

\section{Main Result and Technical Overview}
\label{sec:main}
\newcommand{\delta_{\mathsf{overall}}}{\delta_{\mathsf{overall}}}
The main result of this work follows:
\begin{thm} \label{thm:main}
	Suppose the reward at each level satisfies $r_h \ge 0$ and $\sum_{h=1}^H r_h \le 1$ almost surely.
	Given a target accuracy $0 < \varepsilon < 1$,
	then with probability at least $1 - \delta$, Algorithm~\ref{alg:main} returns an $\varepsilon$-optimal policy by sampling at most
	\[
	O\left(\frac{|\mathcal{S}|^3|\mathcal{A}|^3\log^2 H}{\varepsilon^3} \log\left(\frac{|\mathcal{S}||\mathcal{A}|}{\varepsilon}\right) \cdot \left(|\mathcal{S}|^2|\mathcal{A}|\log\left(\frac{H|\mathcal{S}|}{\varepsilon}\right) + \log\left(\frac{1}{\delta}\right)\right)
	\right)
	\]
	episodes.
\end{thm}
This result shows that only \emph{logarithmic} dependence on the horizon is possible.
Algorithm~\ref{alg:main} is provided in Section~\ref{sec:proof}.
We remark that, while our bound improves the dependency on $H$, the dependency on $\abs{\mathcal{S}}$, $\abs{\mathcal{A}}$ and $1 / \varepsilon$ are worse than existing state-of-the-art bounds (cf. Section~\ref{sec:rel}). It is an open problem to further tighten the dependencies on $\abs{\mathcal{S}}$, $\abs{\mathcal{A}}$ and $\frac{1}{\varepsilon}$.

We now provide an overview of our analysis.
\subsection{Technical Overview}
\label{sec:techover}
\paragraph{An $\varepsilon$-net For Non-stationary Policies.}
We first construct a set of polices $\Pi$ which contains an $\varepsilon$-optimal policy for any MDP.
Importantly, the size of $\Pi$ satisfies $|\Pi| = (H / \varepsilon)^{\mathrm{\mathrm{poly}(|\mathcal{S}||\mathcal{A}|)}}$, which is acceptable since the overall sample complexity of our algorithm depends only logarithmically on $|\Pi|$.
To define such a set of policies, we consider all discretized MDPs whose transition probabilities and reward values are integer multiples of $\mathrm{poly}(\varepsilon/(|\mathcal{S}||\mathcal{A}|H))$.
Clearly, there are most $(H / \varepsilon)^{\mathrm{\mathrm{poly}(|\mathcal{S}||\mathcal{A}|)}}$ such discretized MDPs, and for each discretized MDP $M$, we add an optimal policy of $M$ into $\Pi$.
It remains to show that for any $M$, there exists a policy $\pi \in \Pi$ which is an $\varepsilon$-optimal policy of $M$.
This can be seen since there exists a discretized MDP $\hat{M}$ whose transition probabilities and reward values are close enough to those of $M$, and by standard perturbation analysis, it can be easily shown that an optimal policy of $\hat{M}$ is an $\varepsilon$-optimal policy of $M$.
The formal analysis is given in Section~\ref{sec:policy}.

\paragraph{The Trajectory Synthesis Method.}
Now we show how to evaluate values of all policies in the policy set $\Pi$ constructed above by sampling at most $\mathrm{poly}(|\mathcal{S}|, |\mathcal{A}|, 1 / \varepsilon, \log |\Pi|, \log H)$ episodes.
To achieve this goal, we design a trajectory simulator, which, for every policy in the set, either interacts with the environment to collect trajectories, or simulates trajectories using collected samples.
In either case, the simulator obtains trajectories of the policy with distribution close enough to those sampled by interacting with the environment.
The most natural idea is to collect trajectories for each policy $\pi$ separately by interacting with the environment.
This method, although is guaranteed to output ``true'' trajectories for every policy, has sample complexity at least linear in the size of the policy set $|\Pi|$ and is thus insufficient for our goal.
Another possible way to evaluate policies is to build an empirical model (an estimation of transition probability and reward function) and evaluate policies on the empirical model (or to build a trajectory tree as in~\cite{kearns2000approximate}).
However, we do not know how to deal with the dependency issue in building the empirical model and to prove a sample complexity bound that scales logarithmically with the  planning horizon.
The analysis based on performance difference lemma can lead to polynomial dependency on the planning horizon~\citep{kakade2003sample}.

\paragraph{Reuse Samples.} A key observation is that once we obtain a trajectory for a policy by interacting with the environment, samples collected during this process can be used to simulate trajectories for other policies.
To better illustrate this idea, we use $\Pi_\mathcal{D}$ to denote the set of policies for which we have obtained trajectories by interacting with the environment, and denote
\[
\mathcal{D}_{s,a}=\left[\left(s_{(s,a)}^{(1)}, r_{(s,a)}^{(1)}\right), \left(s_{(s,a)}^{(2)}, r_{(s,a)}^{(2)}\right), \ldots\right]
\]
to be the sequence of samples obtained from $P(s, a)$ and $R(s, a)$.
These samples are sorted in chronological order.
Suppose that now we are given a new policy $\pi$ and for all $(s, a) \in \mathcal{S} \times \mathcal{A}$, $|\mathcal{D}_{s,a}^{(t)}|\ge H$.
Then it is easy to simulate a trajectory for $\pi$ using the set of samples $\left\{ \mathcal{D}_{s,a}\right\}_{s \in \mathcal{S}, a \in \mathcal{A}}$.
Indeed, we start from state $s_1$ and set $(s_2, r_2)$ to be the first pair in $\mathcal{D}_{s_1,\pi_1(s_1)}$, and then set $(s_3, r_3)$ to be the first pair in $\mathcal{D}_{s_2,\pi_2(s_2)}$ that has not been used, etc.
In general, suppose we are at state $s_{h}$ for some $h < H$, we set $(s_{h + 1}, r_{h + 1})$ to be the first pair in $\mathcal{D}_{s_h, \pi_h(s_h)}$ that has not been used.
Note that such a procedure generates a trajectory for $\pi$ with exactly the same distribution as that generated by interacting with the environment.

\paragraph{Avoid Unnecessary Sampling.}
We have described the approach to reuse samples in the above paragraph.
Nevertheless, there is a problem intrinsic to the above approach: if the process of simulating a policy $\pi$ fails (i.e., some $(s_h,\pi_h(s))$ has been visited $j\le H$ times but $|\mathcal{D}_{s_h,\pi_h(s)}|<j$), should we interact with the environment to generate a trajectory or simply claim failure?
Note that claiming failure is acceptable as long as the overall failure probability is small.

In order to decide when to interact with the environment, we design a procedure to estimate the probability of simulation failure.
If the failure probability is already small enough, there is no need to interact with the environment.
Otherwise, we interact with the environment to obtain a trajectory.
To bound the overall sample complexity, one key observation is that if the failure probability is large, then the policy will visit some state-action pair more frequently than all existing policies.
In Section~\ref{sec:analysis}, we make this intuition rigorous by designing a potential function to measure the overall progress made by our algorithm.

\section{The Proof}
\label{sec:proof}
In this section, for the sake of presentation, we assume a fixed initial state $s_1$.
When the initial	state is sampled from a distribution $\mu$, we may create a new state $s_0$ and set $s_0$ to be the initial state.
We set $P(s_0, a) = \mu$ and $r(s_0, a) = 0$ for all $a \in \mathcal{A}$, and increase the planning horizon $H$ by $1$.
By doing so, now $s_1$ is sampled from the initial state distribution $\mu$.

\subsection{An $\varepsilon$-net For Non-stationary Policies}
\label{sec:policy}
In this section, we construct a set of polices which contains a near-optimal policy for any MDP.
To define these policies, we first define a set of MDPs.

Throughout this section, without loss of genearlity, we assume $1 / \varepsilon$ is a positive integer.
In general, we may decrease $\varepsilon$ by a factor of at most two so that $1 / \varepsilon$ is a positive integer.

The following definition is helpful in our analysis.
\begin{definition}
For an MDP $M =\left(\mathcal{S}, \mathcal{A}, P ,R, H, \mu \right)$, we say a pair $(s, h) \in \mathcal{S} \times [H]$ is {\em admissible} with respect to $M$ if there exists a policy $\pi$ such that
$\Pr[s_h = s \mid \pi] > 0$.
\end{definition}

Before presenting our analysis, we prove the following property regarding admissible pairs.

\begin{lemma}\label{lem:admissible}
For any admissible $(s, h) \in \mathcal{S} \times [H]$, for any $a \in \mathcal{A}$, the following hold:
\begin{itemize}
\item $0 \le R(s, a) \le 1$ almost surely;
\item $0 \le Q^{\pi}_h(s, a) \le 1$ for any policy $\pi$;
\item $0 \le V^{\pi}_h(s) \le 1$ for any policy $\pi$.
\end{itemize}
\end{lemma}
\begin{proof}
Here we only prove $0 \le R(s, a) \le 1$. It can be similarly proved that $0 \le Q^{\pi}_h(s, a) \le 1$ and $0 \le V^{\pi}_h(s) \le 1$.
Suppose $R(s, a) > 1$ or $R(s, a) < 0$ with non-zero probability.
Since  $(s, h)$ is admissible, there exists a policy $\pi$ such that $\Pr[s_h = s \mid \pi] > 0$.
Consider the policy $\pi'$ defined to be:
\[
\pi'_{h'}(s) = \begin{cases}
\pi_{h'}(s) & h' < h\\
a& h' \ge  h
\end{cases}.
\]
Clearly, $r_h > 1$ or $r_h < 0$ with non-zero probability, which violates the assumption that $\sum_{h = 1}^{H}r_h \in [0, 1]$ and $r_h \ge 0$ for all $h \in [H]$ almost surely.
\end{proof}

\begin{definition}[Discretized MDPs]
For given $\mathcal{S}$, $\mathcal{A}$, $H$, $s_1$ and $\varepsilon > 0$, define $\mathcal{M}_{\varepsilon}$ to be the set of MDPs $M =\left(\mathcal{S}, \mathcal{A}, P ,R, H, s_1\right)$ such that
\begin{itemize}
\item Rewards are deterministic and for any $(s, a) \in \mathcal{S} \times \mathcal{A}$, $R(s, a) \in \{0, \varepsilon, 2 \varepsilon, 3\varepsilon, \ldots, 1\}$;
\item For each $(s, a, s') \in \mathcal{S} \times \mathcal{A} \times \mathcal{S}$, $P(s' \mid s, a)  \in \{0, \varepsilon, 2 \varepsilon, 3\varepsilon, \ldots, 1\}$;
\end{itemize}
\end{definition}

The following lemma gives an upper bound on the size of $\mathcal{M}_{\varepsilon}$.
\begin{lemma}\label{lem:policy_count}
$\left|\mathcal{M}_{\varepsilon}\right| \le (1 / \varepsilon + 1)^{|\mathcal{S}|^2 |\mathcal{A}| + |\mathcal{S}| |\mathcal{A}|}$.
\end{lemma}
\begin{proof}
Since each $M \in \mathcal{M}_{\varepsilon}$ is uniquely defined by its $R$ and $P$, below we count the number of possible $R$ and $P$ respectively.

Since rewards are deterministic and for any $(s, a) \in \mathcal{S} \times \mathcal{A}$, $R(s, a) \in \{0, \varepsilon, 2 \varepsilon, \ldots, 1\}$, there are $(1 / \varepsilon + 1)^{|\mathcal{S}||\mathcal{A}|}$ different rewards in total.

Since for each $(s, a, s') \in \mathcal{S} \times \mathcal{A} \times \mathcal{S}$, $P(s' \mid s, a)  \in \{0, \varepsilon, 2 \varepsilon, \ldots, 1\}$, there are at most $(1 / \varepsilon + 1)^{|\mathcal{S}|^2|\mathcal{A}|}$ different transitions in total.

Therefore, $\left|\mathcal{M}_{\varepsilon}\right| \le (1 / \varepsilon + 1)^{|\mathcal{S}|^2 |\mathcal{A}| + |\mathcal{S}| |\mathcal{A}|}$.

\begin{definition}[$\varepsilon$-net for Non-stationary Policies]
	\label{defn:discrete_policies}
For given $\mathcal{S}$, $\mathcal{A}$, $H$ and $\varepsilon > 0$, define $\Pi_{\varepsilon}$ to be the set of polices such that
\[
\Pi_{\varepsilon} = \{\pi_{M} \mid \text{$\pi_{M}$ is an optimal policy for $M \in \mathcal{M}_{\varepsilon}$}\}.
\]
For each $M \in \mathcal{M}_{\varepsilon}$, when $M$ has multiple optimal policies, we add an arbitrary one to $\Pi_{\varepsilon}$.
\end{definition}
By construction of $\Pi_{\varepsilon}$ and Lemma~\ref{lem:policy_count}, it is clear that $\left|\Pi_{\varepsilon} \right|  \le (1 / \varepsilon + 1)^{|\mathcal{S}|^2 |\mathcal{A}| + |\mathcal{S}| |\mathcal{A}|}$
\end{proof}

Now we prove that for any MDP $M$, there is a near-optimal policy $\pi \in \Pi_{\varepsilon}$.

\begin{lemma}\label{lem:discrete_near_optimal}
For any MDP $M =\left(\mathcal{S}, \mathcal{A}, P ,R, H, s_1\right)$, there exists $\pi \in \Pi_{\varepsilon}$ such that $\pi$ is $8H|\mathcal{S}|\varepsilon$-optimal.
\end{lemma}
\begin{proof}
We first show that there exists $\hat{M} =\left(\mathcal{S}, \mathcal{A}, \hat{P} ,\hat{R}, H, s_1\right) \in \mathcal{M}_{\varepsilon}$ such that the following hold:
\begin{itemize}
\item For any $(s, h) \in \mathcal{S} \times [H]$ admissible with respect to $M$, for any $a \in \mathcal{A}$, $|\hat{R}(s, a) - \mathbb{E}[R(s, a)]| \le \varepsilon$;
\item For each $(s, a, s') \in \mathcal{S} \times \mathcal{A} \times \mathcal{S}$, $\left|P(s' \mid s, a) - \hat{P}(s' \mid s, a)\right| \le \varepsilon$;
\item For each $(s, a, s') \in \mathcal{S} \times \mathcal{A} \times \mathcal{S}$, if $P(s' \mid s, a)= 0$ then $\hat{P}(s' \mid s, a) = 0$;
\end{itemize}

Below we construct such $\hat{P}$ and $\hat{R}$.
By Lemma~\ref{lem:admissible} we have $\mathbb{E}[R(s, a)] \in [0, 1]$.
Therefore, by setting $\hat{R}(s, a)$ to be closest real number in $\{0, \varepsilon, 2\varepsilon, \ldots, 1\}$, we have $|\hat{R}(s, a) - \mathbb{E}[R(s, a)]| \le \varepsilon$.
Furthermore, for each $(s, a, s') \in \mathcal{S} \times \mathcal{A} \times \mathcal{S}$, we set
\[
P'(s' \mid s, a) = \min \{p \in \{0, \varepsilon, 2\varepsilon, \ldots, 1\} \mid p \geP(s' \mid s, a) \}.
\]
Notice that $P'(s, a)$ may not always be a probability distribution.
Clearly $P'(s' \mid s, a) \ge P(s' \mid s, a)$ for each $(s, a, s') \in \mathcal{S} \times \mathcal{A} \times \mathcal{S}$ and $\sum_{s' \in \mathcal{S}} P'(s' \mid s, a)  = 1 + k\varepsilon$ for some positive integer $0 \le k \le |\mathcal{S}|$.
Now for each $(s, a)$, we set $\hat{P}(s' \mid s, a)= P'(s' \mid s, a) - \varepsilon$ for an arbitrary $k$ states $s' \in \mathcal{S}$ with $P(s' \mid s, a) > 0$, and set  $\hat{P}(s' \mid s, a)= P'(s' \mid s, a)$ for all other states $s'$.
Clearly, $P'(s, a)$ is a probability distrbution for any $(s, a)$ and satisfies the desired property.

Now for any policy $\pi$, we use $V^{\pi}$ to denote the $V$-value of $\pi$ on MDP $M$, and use $\hat{V}^{\pi}$ to denote the $V$-value of $\pi$ on $\hat{M}$. $Q^{\pi}$ and $\hat{Q}^{\pi}$ are defined analogously. We prove that $|V^{\pi} - \hat{V}^{\pi}| \le 4|\mathcal{S}|H\varepsilon$ for any policy $\pi$ inductively by the following induction hypothesis:
\begin{itemize}
\item $|V_h^{\pi}(s) - \hat{V}_h^{\pi}(s)| \le (1 + (H - h)(|\mathcal{S}| + 1))\varepsilon$ for any admissible $(s, h)$;
\item $|Q_h^{\pi}(s, a) - \hat{Q}_h^{\pi}(s, a)| \le  (1 + (H - h)(|\mathcal{S}| + 1))\varepsilon$ for any admissible $(s, h)$ and any $a \in \mathcal{A}$.
\end{itemize}

When $h = H$, $V_H^{\pi}(s) = Q_H(s, \pi_H(s)) = \mathbb{E}[R(s, \pi_H(s))]$ and $\hat{V}_H^{\pi}(s) = \hat{Q}_H(s, \pi_H(s)) = \hat{R}(s, \pi_H(s))$.
Therefore, the induction hypothesis holds when $h = H$ since $|\hat{R}(s, a) - \mathbb{E}[R(s, a)]| \le \varepsilon$.

Now we show the induction hypothesis holds for any $h < H$.
For any $h < H$, consider any state $s$ such that $(s, h)$ is admissible.
Notice that $V_h^{\pi}(s) = Q_h(s, \pi_h(s))$ and  $\hat{V}_h^{\pi}(s) = \hat{Q}_h(s, \pi_h(s))$, and therefore $|V_h^{\pi}(s) - \hat{V}_h^{\pi}(s)|  = |Q_h^{\pi}(s, \pi_h(s)) - \hat{Q}_h^{\pi}(s, \pi_h(s))|$.
Furthermore,
\[
Q_h^{\pi}(s, a) = \mathbb{E}[R(s, a)] + \sum_{s' \in \mathcal{S}} P(s' \mid s, a) V_{h + 1}^{\pi}(s')
\]
and
\[\hat{Q}_h^{\pi}(s, a) = \hat{R}(s, a) + \sum_{s' \in \mathcal{S}} \hat{P}(s' \mid s, a)V_{h + 1}^{\pi}(s').\]
Therefore,
\begin{align*}
&\left|Q_h^{\pi}(s, a) - \hat{Q}_h^{\pi}(s, a)\right| \\
\le &  \left| \mathbb{E}[R(s, a)]  - \hat{R}(s, a)\right| + \sum_{s' : P(s' \mid s, a) > 0} \left|P(s' \mid s, a) V_{h + 1}^{\pi}(s') - \hat{P}(s' \mid s, a)\hat{V}_{h + 1}^{\pi}(s')\right|\\
\le &  \varepsilon + \sum_{s' : P(s' \mid s, a) > 0} \left( \left|P(s' \mid s, a) - \hat{P}(s' \mid s, a)\right| \cdot V_{h + 1}^{\pi}(s') + \hat{P}(s' \mid s, a) \cdot \left| V_{h + 1}^{\pi}(s' ) - \hat{V}_{h + 1}^{\pi}(s')\right| \right)\\
\le &  (|\mathcal{S}| + 1)\varepsilon + \sum_{s' : P(s' \mid s, a) > 0}  \hat{P}(s' \mid s, a) \cdot \left| V_{h + 1}^{\pi}(s' ) - \hat{V}_{h + 1}^{\pi}(s')\right| \tag{$V_{h + 1}^{\pi}(s') \le 1$ by Lemma~\ref{lem:admissible}} \\
\le &  (|\mathcal{S}| + 1)\varepsilon + (1 + (H - (h + 1))(|\mathcal{S}| + 1))\varepsilon \tag{$\sum_{s' \in \mathcal{S}}  \hat{P}(s' \mid s, a)= 1$ and induction hypothesis} \\
= &  (1 + (H - h)(|\mathcal{S}| + 1))\varepsilon.
\end{align*}
Thus, we have
\[
\left|V^{\pi}_1(s_1) - \hat{V}^{\pi}_1(s_1)\right| \le 4|\mathcal{S}|H \varepsilon.
\]

Finally, consider any optimal policy $\hat{\pi}$ of $\hat{M}$ and any optimal policy $\pi$ of $M$, we have
\[
V^{\hat{\pi}}_1(s_1) \ge \hat{V}^{\hat{\pi}}_1(s_1) -  4|\mathcal{S}|H \varepsilon \ge \hat{V}^{\pi}_1(s_1) -  4|\mathcal{S}|H \varepsilon \ge V^{\pi}_1(s_1) - 8|\mathcal{S}|H\varepsilon.
\]
Since $\hat{\pi} \in \Pi_{\varepsilon}$, the lemma holds.
\end{proof}
\subsection{Evaluating Policies}
\label{sec:evaluate}
\newcommand{\delta_{\mathsf{sim}}}{\delta_{\mathsf{sim}}}

As shown in Section~\ref{sec:policy}, there exists a set of policies $\Pi$ such that for any MDP $M$, there exists a near-optimal policy $\pi \in \Pi$.
In this section, we show how to approximately evaluate the values of all policies in $\Pi$ using at most $\mathrm{poly}(|\mathcal{S}|, |\mathcal{A}|, 1 / \varepsilon, \log |\Pi|, \log H)$ episodes.
We formally describe our simulator in Section~\ref{sec:simulator} and present its analysis in Section~\ref{sec:analysis}.

\subsubsection{The Trajectory Simulator}\label{sec:simulator}
In this section, we describe our algorithm for simulating trajectories.
The algorithm is formally presented in Algorithm~\ref{alg:tsimall} and Algorithm~\ref{alg:tsim}.
Algorithm~\ref{alg:tsim} receives a parameter $\tau$ and uses a replay buffer $\mathcal{D}$ to store samples.
Formally, $\mathcal{D}=\{\mathcal{D}_{s,a}\}_{s \in \mathcal{S}, a \in \mathcal{A}}$, where each $\mathcal{D}_{s,a}$ contains samples associated with state-action pair $(s,a)$, i.e., \[\mathcal{D}_{s,a}=\left[(s^{(1)}_{s,a}, r_{s,a}^{(1)}), (s^{(2)}_{s,a}, r_{s,a}^{(2)}), \ldots \right]\] and samples are sorted in chronological order.
  We also maintain $\Pi_{\mathcal{D}}$ in Algorithm~\ref{alg:tsim} which is the set of policies used to generate $\mathcal{D}$.
There are two subroutines in Algorithm~\ref{alg:tsim}.
Subrountine \textsc{Simulate} takes an input policy $\pi$ and outputs either \texttt{Fail} or a trajectory for policy $\pi$.
Subroutine \textsc{Rollout} takes an input policy $\pi$, samples $\tau$ episodes for $\pi$ by interacting with the environment and stores all collected samples in the replay buffer $\mathcal{D}$.
It also returns one of the $\tau$ trajectories sampled for for $\pi$.
Moreover, whenever Subroutine \textsc{Rollout} is invoked, samples in $\mathcal{D}$ are recollected so that independence among samples in the replay buffer $\mathcal{D}$ is ensured.

Algorithm~\ref{alg:tsimall} receives a failure probability $\delta_{\mathsf{sim}}$ and a policy set $\Pi$ as inputs.
In Algorithm~\ref{alg:tsimall}, we run $F$ independent copies of  Algorithm~\ref{alg:tsim} in parallel.
For each policy $\pi$, for the $F$ independent copies of  Algorithm~\ref{alg:tsim}, Algorithm~\ref{alg:tsimall} checks whether Subroutine \textsc{Simulate} returns \texttt{Fail} for too many times.
If so, it calls Subroutine \textsc{Rollout} for each copy of Algorithm~\ref{alg:tsim} to collect samples and produce trajectories for $\pi$.
Otherwise, it directly returns trajectories returned by Subroutine \textsc{Simulate}.
The formal analysis of our algorithms will presented in Section~\ref{sec:analysis}.

\begin{algorithm}[t]
  \caption{\texttt{SimAll}\label{alg:tsimall}}
  \begin{algorithmic}[1]
  \State \textbf{Input:} failure probability $\delta_{\mathsf{sim}}$, policy set $\Pi$, number of trajectories $F$
  \State $\tau \gets 16|\mathcal{S}|\abs{\mathcal{A}} / \delta_{\mathsf{sim}} \cdot \log(4 |\mathcal{S}|\abs{\mathcal{A}} / \delta_{\mathsf{sim}})$
  \For{$i \in [F]$} \Comment{Run $F$ copies of Algorithm~\ref{alg:tsim} in parallel}
  \State Set $\mathsf{SO}_i$ to be the $i$-th independent copy of \texttt{SimOne}$(\tau)$ (Algorithm~\ref{alg:tsim})
  \EndFor
  \For{$\pi \in \Pi$}
  \For{$i \in [F]$}
  \State $z_i^{\pi} \gets \mathsf{SO}_i$.\textsc{Simulate}$(\pi)$
  \EndFor
  \If{$\sum_{i = 1}^F \mathbb{I}[z_i^{\pi} \text{ is \texttt{Fail}}]> 3\delta_{\mathsf{sim}}/2 \cdot F$}\label{algline:simfail}
  \For{$i \in [F]$}
  \State $z_i^{\pi} \gets \mathsf{SO}_i$.\textsc{Rollout}$(\pi)$
  \EndFor
  \EndIf
\EndFor
  \State \Return{$\{z_i^{\pi}\}_{(i, \pi) \in [F] \times \Pi}$}
  \end{algorithmic}
\end{algorithm}

\begin{algorithm}[t]
  \caption{\texttt{SimOne}\label{alg:tsim}}
  \begin{algorithmic}[1]
  \State \textbf{Input:} number of repetitions $\tau$
  \Function{Simulate}{$\pi$}:
     \For{$(s, a) \in \mathcal{S} \times \mathcal{A}$}
     \State Mark all elements in $\mathcal{D}_{s, a}$ as \texttt{unused}
     \EndFor
      \For{$h \in \{1, 2, \ldots, H\}$}
      \If{all elements in $\mathcal{D}_{s_h, \pi_h(s_h)}$ are marked as \texttt{used}}
      \State \Return \texttt{Fail}
      \Else
      \State Set $(s_{h + 1}, r_{h})$ to be the first element in $\mathcal{D}_{s_h, \pi_h(s_h)}$ that is marked as \texttt{unused}
      \State Mark $(s_{h + 1}, r_{h})$ (the first unused element in $\mathcal{D}_{s_h, \pi_h(s_h)}$) as \texttt{used}
      \EndIf
     \EndFor
     \State \Return $(s_1, \pi_1(s_1), r_1), (s_2, \pi_2(s_2), r_2), \ldots, (s_H, \pi_H(s_H), r_H)$
  \EndFunction
  \Function{Rollout}{$\pi$}
    \State Set $\mathcal{D}_{s,a}$ to be an empty sequence for all $(s, a) \in \mathcal{S} \times \mathcal{A}$
    \State $\Pi_{\mathcal{D}}\gets \Pi_{\mathcal{D}}\cup \{\pi\}$ \label{line:add_policy}
    \For{$\pi'\in \Pi_{\mathcal{D}}$}
    	\State Sample $\tau$ trajectories for $\pi'$ by interacting with the environment \label{line:rollout}
	\State Add all collected samples to $\mathcal{D}$
    \EndFor
    \State \Return one of the $\tau$ trajectories sampled for $\pi$
  \EndFunction
\end{algorithmic}
\end{algorithm}

\subsubsection{Analysis}\label{sec:analysis}
In this section, we present the formal analysis of Algorithm~\ref{alg:tsimall} and Algorithm~\ref{alg:tsim}.
Before we present our analysis, we first introduce some necessary notations.
\begin{defn}
For any policy $\pi$, for any state-action pair $(s, a) \in \mathcal{S} \times \mathcal{A}$, define $f^{\pi}(s,a) \in [H]$ to be a random variable defined as
\[
f^{\pi}(s,a) = \sum_{h = 1}^H \mathbb{I}[(s, a) = (s_h, a_h) \mid \pi].
\]
I.e., $f^{\pi}(s,a)$ is the random variable which is the total number of times a trajectory induced by $\pi$ visits $(s,a)$.
\end{defn}

We additionally define the following quantity to characterize the number times a state-action pair is visited by a set of policies.
Intuitively, given a success probability $\delta$, this quantity measures the maximum number of times a policy within a given policy set can visit a particular $(s,a)$ pair.
\begin{defn}
	\label{defn:policy-freq}
For a set of policies $\Pi$, for any $(s,a)\in \mathcal{S} \times \mathcal{A}$, define
\[
 \mu^{\Pi}_{\delta}(s,a) = \max\big\{\lambda \mid \lambda\in [0,H], \max_{\pi\in \Pi}\Pr[f^{\pi}(s,a) \ge \lambda]\ge \delta\big\}.
\]
\end{defn}
Note that $\mu^{\Pi}_{\delta}(s,a)$ is always a non-negative integer since for any state-action pair $(s, a) \in \mathcal{S} \times \mathcal{A}$, policy $\pi$ and real number $\lambda$,
\[
\Pr\left[f^{\pi}(s,a) \ge \lambda\right] = \Pr\left[f^{\pi}(s,a) \ge \lceil{\lambda\rceil}\right].
\]

Our next lemma states that for some policy $\pi$, if \texttt{SimOne} fails with high probability, then there exists a state-action pair that $\pi$ visits more frequently than all previous policies.
\begin{lemma}
\label{lem:prob-increase}
For a policy $\pi\in \Pi$, suppose Subroutine \textsc{Simulate} in Algorithm~\ref{alg:tsim} returns \texttt{Fail} with probability at least $\delta_{\mathsf{sim}}$ over the randomness of the generating process of the replay buffer $\mathcal{D}$.
There exists $(s, a) \in \mathcal{S} \times \mathcal{A}$ such that
\[
\Pr\Big[f^{\pi}(s,a) > \tau\cdot\frac{\delta_{\mathsf{sim}}}{4|\mathcal{S}|\abs{\mathcal{A}}}\cdot  \mu_{\delta_{\mathsf{sim}}/(2|\mathcal{S}|\abs{\mathcal{A}})}^{\Pi_{\mathcal{D}}}(s,a)\Big]\ge \frac{\delta_{\mathsf{sim}}}{2|\mathcal{S}|\abs{\mathcal{A}}}
\]
where $\Pi_{\mathcal{D}}$ is the set of policies used to generate $\mathcal{D}$.
\end{lemma}
\begin{proof}
Suppose for the sake of contradiction that for each $(s, a) \in \mathcal{S} \times \mathcal{A}$,
\[
\Pr\Big[f^{\pi}(s,a) > \tau\cdot\frac{\delta_{\mathsf{sim}}}{4|\mathcal{S}|\abs{\mathcal{A}}}\cdot  \mu_{\delta_{\mathsf{sim}}/(2|\mathcal{S}|\abs{\mathcal{A}})}^{\Pi_{\mathcal{D}}}(s,a)\Big]< \frac{\delta_{\mathsf{sim}}}{2|\mathcal{S}|\abs{\mathcal{A}}}.
\]
Let us denote
\[
\Gamma(s,a) = \tau\cdot\frac{\delta_{\mathsf{sim}}}{4|\mathcal{S}|\abs{\mathcal{A}}}\cdot  \mu_{\delta_{\mathsf{sim}}/ (2|\mathcal{S}|\abs{\mathcal{A}})}^{\Pi_\mathcal{D}}(s,a).
\]
For each $(s,a) \in \mathcal{S} \times \mathcal{A}$, we have
\[
\Pr\Big[f^{\pi}(s,a) >\Gamma(s,a) \Big]< \frac{\delta_{\mathsf{sim}}}{2|\mathcal{S}|\abs{\mathcal{A}}}.
\]
Therefore, by a union bound over all state-action pairs $(s, a) \in \mathcal{S} \times \mathcal{A}$, with probability at least $1 - \delta_{\mathsf{sim}}/2$, for all $(s,a) \in \mathcal{S} \times \mathcal{A}$,
\begin{align}
 f^{\pi}(s,a) \le \Gamma(s,a). \label{eqn:smaller_than_thres}
\end{align}

For each $(s,a)\in \mathcal{S} \times \mathcal{A}$, define $\mathcal{E}_{s,a}$ to be the event that
\[
\mathcal{E}_{s,a} = \left\{\left| \mathcal{D}_{s, a}\right| \ge  \Gamma(s, a)\right\}.
\]
By Definition~\ref{defn:policy-freq}, there exists a policy $\pi_{s,a}^* \in \Pi_{\mathcal{D}}$ such that
\[\Pr\left[f^{\pi_{s,a}^*}(s,a) \ge  \mu^{\Pi_\mathcal{D}}_{\delta_{\mathsf{sim}} / (2|\mathcal{S}|\abs{\mathcal{A}})}(s,a)\right]\ge \delta_{\mathsf{sim}} / (2 |\mathcal{S}|\abs{\mathcal{A}}).\]
Now consider Line~\ref{line:rollout} in Subroutine~\textsc{Rollout} in Algortihm~\ref{alg:tsim}.
Define
\[
X_i = \begin{cases}
1 & \text{if $\sum_{h = 1}^H \mathbb{I}[(s_h, a_h) = (s, a)] \ge  \mu^{\Pi_\mathcal{D}}_{\delta_{\mathsf{sim}} / (2|\mathcal{S}|\abs{\mathcal{A}})}(s,a)$ for the $i$-th trajectory of $\pi^*_{s, a}$}\\
0 & \text{otherwise}
\end{cases}.
\]
Note $X_1,\ldots,X_\tau$ are i.i.d. random variables.
By definition, $\mathbb{E}[X_i] \ge \delta_{\mathsf{sim}} / (2 |\mathcal{S}|\abs{\mathcal{A}})$.
Therefore, since $\tau = 16|\mathcal{S}|\abs{\mathcal{A}} / \delta_{\mathsf{sim}} \cdot \log(4 |\mathcal{S}|\abs{\mathcal{A}} / \delta_{\mathsf{sim}})$, by Chernoff bound,
\[
\Pr\left[\sum_{i=1}^{\tau} X_i \le \tau \cdot \frac{\delta_{\mathsf{sim}}}{4|\mathcal{S}|\abs{\mathcal{A}}}\right]
\le \exp\left(-\frac{\tau \delta_{\mathsf{sim}}/(2|\mathcal{S}|\abs{\mathcal{A}})}{8}\right)
\le \frac{\delta_{\mathsf{sim}}}{4|\mathcal{S}|\abs{\mathcal{A}}}.
\]

Therefore,
\[
\Pr[\mathcal{E}_{s,a}] \ge\Pr\left[\sum_{i=1}^{\tau} X_i \ge \tau \cdot \frac{\delta_{\mathsf{sim}}}{4|\mathcal{S}|\abs{\mathcal{A}}}\right] \ge 1 - \frac{\delta_{\mathsf{sim}}}{4 |\mathcal{S}|\abs{\mathcal{A}}}.
\]
It follows that with probability at least $1 - \delta_{\mathsf{sim}} / 4$, for all $(s, a) \in \mathcal{S}\times\mathcal{A}$,
\begin{align}
\left| \mathcal{D}_{s, a}\right| \ge  \Gamma(s, a). \label{eqn:thres_upper}
\end{align}

By a union bound over~\eqref{eqn:smaller_than_thres} and~\eqref{eqn:thres_upper}, with probability at least $1 - \frac{3\delta_{\mathsf{sim}}}{4}$, for all $(s,a) \in \mathcal{S} \times \mathcal{A}$,
\[
\left|\mathcal{D}_{s, a}\right| \ge  \Gamma(s, a) \ge  f^{\pi}(s,a),
\]
in which case Subroutine \textsc{Rollout} does not return \texttt{Fail}.
This contradicts the assumption that Subroutine \textsc{Rollout} returns \texttt{Fail} with probability at least $\delta_{\mathsf{sim}}$.

\end{proof}
Now we discuss the implication of Lemma~\ref{lem:prob-increase}.
Note that Algorithm~\ref{alg:tsim} interacts with the environment to sample trajectories only when Subroutine~\textsc{Simulate} fails with probability at least $\delta_{\mathsf{sim}}$.
By Lemma~\ref{lem:prob-increase}, when Algorithm~\ref{alg:tsim} interacts with the environment to sample trajectories, $\mu_{\delta_{\mathsf{sim}}/(2|\mathcal{S}|\abs{\mathcal{A}})}^{\Pi_\mathcal{D}}(s,a)$ doubles or changes from $0$ to $1$ for some $(s, a) \in \mathcal{S} \times \mathcal{A}$ since $\tau \delta_{\mathsf{sim}} / (4|\mathcal{S}|\abs{\mathcal{A}}) > 2$.
However, $\mu_{\delta_{\mathsf{sim}}/(2|\mathcal{S}|\abs{\mathcal{A}})}^{\Pi_\mathcal{D}}(s,a)$ is always upper bounded by $H$.
Therefore, the total number of calls to Subrountine \textsc{Rollout} in Algorithm~\ref{alg:tsimall} is upper bounded by $O(|\mathcal{S}||\mathcal{A}|\log H)$.
Our next lemma guarantees that whenever Algorithm~\ref{alg:tsimall} invokes Subroutine \textsc{Rollout}, the probability that Subroutine \textsc{Simulate} returns \texttt{Fail} is at least $\delta_{\mathsf{sim}}$, and when Subroutine~\textsc{Rollout} is not invoked, the probability that Subroutine \textsc{Simulate} returns \texttt{Fail} is at most $2\delta_{\mathsf{sim}}$.
\begin{lemma}
\label{lem:chern}
Suppose $F \ge 24 / \delta_{\mathsf{sim}} \cdot \log (2 |\Pi| / \delta_{\mathsf{overall}})$.
With probability at least $1-\delta_{\mathsf{overall}} / (2|\Pi|)$,
each time Line~\ref{algline:simfail} in Algorithm~\ref{alg:tsimall} is executed,
the following hold:
\begin{itemize}
    \item when $\sum_{i = 1}^F \mathbb{I}[z_i^{\pi} \text{ is \texttt{Fail}}] > 3\delta_{\mathsf{sim}}/2 \cdot F$, the probability that Subroutine \textsc{Simulate} returns \texttt{Fail} is at least $\delta_{\mathsf{sim}}$ over the randomness of the generating process of the replay buffer $\mathcal{D}$;
    \item when $\sum_{i = 1}^F \mathbb{I}[z_i^{\pi} \text{ is \texttt{Fail}}] \le 3\delta_{\mathsf{sim}}/2 \cdot F$, the probability that Subroutine \textsc{Simulate} returns \texttt{Fail} is at most $2\delta_{\mathsf{sim}}$ over the randomness of the generating process of the replay buffer $\mathcal{D}$.
    \end{itemize}
\end{lemma}
\begin{proof}
Let $Y_i = \mathbb{I}[\text{$z_i^{\pi}$ is \texttt{Fail}}]$.
Note that each time Subroutine \textsc{Rollout} is invoked, all samples in $\mathcal{D}$ are recollected.
Therefore, for any given time step of the algorithm, $\{Y_i\}_{i = 1}^{F}$ are independent random variables.

If $\Pr[Y_i = 1]<\delta_{\mathsf{sim}}$, by Chernoff bound,
\[
\Pr\left[\sum_{i=1}^{F}Y_i \ge 3\delta_{\mathsf{sim}}/2 \cdot F\right] \le \exp(-\delta_{\mathsf{sim}} F / 24) \le \frac{\delta_{\mathsf{overall}}}{2|\Pi|}.
\]

On the other hand, if $\Pr[Y_i = 1]\ge 2\delta_{\mathsf{sim}}$, by Chernoff bound,
\[
\Pr\left[\sum_{i=1}^{F}Y_i \le 3\delta_{\mathsf{sim}}/2 \cdot F\right] \le \exp(-\delta_{\mathsf{sim}} F / 16)\le \frac{\delta_{\mathsf{overall}}}{2|\Pi|}.
\]
Thus the lemma holds.
\end{proof}
Now we bound the overall sample complexity of the algorithm.
\begin{lemma}
\label{lem:double}
Suppose $F \ge 24 / \delta_{\mathsf{sim}} \cdot \log (2 |\Pi| / \delta_{\mathsf{overall}})$.
Let $\Pi_{\mathcal{D}}$ be the set of policies maintained by Algorithm~\ref{alg:tsim} before executing Line~\ref{line:add_policy}, and let $\hat{\Pi}_{\mathcal{D}}$ be the set of policies maintained after executing Line~\ref{line:add_policy}, i.e., $\hat{\Pi}_{\mathcal{D}} = \Pi_{\mathcal{D}} \cup \{\pi\}$.
With probability at least $1-\delta_{\mathsf{overall}}/(2|\Pi|)$, there exists $(s,a) \in \mathcal{S} \times \mathcal{A}$, such that
\[
\mu_{\delta_{\mathsf{sim}}/{(2|\mathcal{S}||\mathcal{A}|)}}^{\hat{\Pi}_{\mathcal{D}}}(s,a) \ge \max \left(
2\cdot\mu_{\delta_{\mathsf{sim}}/{(2|\mathcal{S}|\abs{\mathcal{A}})}}^{\Pi_{\mathcal{D}}}(s,a),  1
\right).
\]
\end{lemma}
\begin{proof}
By Lemma~\ref{lem:chern}, with probability at least $1-\delta_{\mathsf{overall}}/(2|\Pi|)$,
for the added policy $\pi$,
the probability that Subroutine \textsc{Simulate} returns \texttt{Fail} is at least $\delta_{\mathsf{sim}}$.
By Lemma~\ref{lem:prob-increase},
there exists $(s, a) \in \mathcal{S} \times \mathcal{A}$ such that
\[
\Pr\Big[f^{\pi}(s,a) > \tau\cdot\frac{\delta_{\mathsf{sim}}}{4|\mathcal{S}|\abs{\mathcal{A}}}\cdot  \mu_{\delta_{\mathsf{sim}}/(2|\mathcal{S}|\abs{\mathcal{A}})}^{\Pi_{\mathcal{D}}}(s,a)\Big]\ge \frac{\delta_{\mathsf{sim}}}{2|\mathcal{S}|\abs{\mathcal{A}}}.
\]

If $\mu_{\delta_{\mathsf{sim}}/(2|\mathcal{S}|\abs{\mathcal{A}})}^{\Pi_\mathcal{D}}(s,a) = 0$, we have
\[
\Pr[f^{\pi}(s,a) >0] =
\Pr[f^{\pi}(s,a) \ge 1]\ge \frac{\delta_{\mathsf{sim}}}{2|\mathcal{S}|\abs{\mathcal{A}}}.
\]
Otherwise, we have
\[
\Pr\left[f^{\pi}(s,a) \ge 2 \cdot \mu_{\delta_{\mathsf{sim}}/(2|\mathcal{S}|\abs{\mathcal{A}})}^{\Pi_\mathcal{D}}(s,a)\right]\ge \frac{\delta_{\mathsf{sim}}}{2|\mathcal{S}|\abs{\mathcal{A}}}.
\]
\end{proof}
\begin{lemma}\label{lem:sample_complexity}
Suppose $F \ge 24 / \delta_{\mathsf{sim}} \log (2 |\Pi| / \delta_{\mathsf{overall}})$.
With probability at least $1-\delta_{\mathsf{overall}}/2$, Algorithm~\ref{alg:tsimall} at most interacts
\[
O\left(\frac{|\mathcal{S}||\mathcal{A}|}{\delta_{\mathsf{sim}}}\cdot\log(|\mathcal{S}||\mathcal{A}|/\delta_{\mathsf{sim}})\cdot |\mathcal{S}|^2|\mathcal{A}|^2\log^2 H \cdot F\right)
\]
episodes  with the environment.
\end{lemma}
\begin{proof}
Notice that our algorithm interacts with the environment only when Subroutine~\textsc{Rollout} in Algorithm~\ref{alg:tsim} is invoked.
By Lemma~\ref{lem:double} and union bound, with probability at least $1 - \delta_{\mathsf{overall}} / 2$, whenever Subroutine \textsc{Rollout} is invoked, there exists $(s, a) \in \mathcal{S} \times \mathcal{A}$ such that $\mu_{\delta_{\mathsf{sim}}/(2|\mathcal{S}|\abs{\mathcal{A}})}^{\Pi_{\mathcal{D}}}(s,a)$ is increased from $0$ to $1$, or $\mu_{\delta_{\mathsf{sim}}/(2|\mathcal{S}|\abs{\mathcal{A}})}^{\Pi_{\mathcal{D}}}(s,a)$ is increased by a factor of $2$.
Since $\mu_{\delta_{\mathsf{sim}}/(2|\mathcal{S}|\abs{\mathcal{A}})}^{\Pi_{\mathcal{D}}}(s,a)\le H$, with probability at least $1 - \delta_{\mathsf{sim}} / 2$, Subroutine~\textsc{Rollout} is invoked for at most $O(|\mathcal{S}||\mathcal{A}|\log H)$ times.
Hence $|\Pi_\mathcal{D}|= O(|\mathcal{S}||\mathcal{A}|\log H)$.
Finally, whenever Subroutine~\textsc{Rollout} is invoked, the algorithm samples at most $F|\Pi_\mathcal{D}|\tau$ trajectories by interacting with the environment.
Therefore, with probability at least $1 - \delta_{\mathsf{sim}} / 2$, the total number of trajectories sampled by the algorithm is upper bounded by $O(F\tau\cdot(|\mathcal{S}||\mathcal{A}|\log H)^2)$.
\end{proof}

\subsection{The Algorithm}
\label{sec:final}
\begin{algorithm}[t]
  \caption{\texttt{Main}\label{alg:main}}
  \begin{algorithmic}[1]
  \State \textbf{Input:} failure probability $\delta_{\mathsf{overall}}$, accuracy $\varepsilon$
  \State Let $\Pi_{\varepsilon / (32 H |\mathcal{S}|)}$ be the set of policies as defined in Definition~\ref{defn:discrete_policies}
  \State Invoke \texttt{SimAll} (Algorithm~\ref{alg:tsim}) with $\delta_{\mathsf{sim}} = \varepsilon / 8$ and \[F = \max\{64\log(4|\Pi_{\varepsilon / (32 H |\mathcal{S}|)}| / \delta_{\mathsf{overall}}) / \varepsilon^2, 192 \log (2 |\Pi_{\varepsilon / (32 H |\mathcal{S}|)}| / \delta_{\mathsf{overall}}) / \varepsilon\}\]
  \For{each trajectory $z = (s_1, a_1, r_1), (s_2, a_2, r_2), \ldots, (s_H, a_H,r_H)$ returned by \texttt{SimAll}}
  \State Calculate
  $
  r(z) = \begin{cases}
  0 & \text{$z$ is \texttt{Fail}}\\
  \sum_{h = 1}^H r_h & \text{otherwise}
  \end{cases}
  $
  \EndFor
  \For{$\pi \in \Pi_{\varepsilon / (32 H |\mathcal{S}|)}$}
  \State Calculate $\hat{r}(\pi) = \frac{1}{F} \sum_{i \in [F]} r(z_i^{\pi})$ \label{line:empirical_value}
  \EndFor
  \State \Return $\mathrm{argmax}_{\pi \in \Pi_{\varepsilon / (32 H |\mathcal{S}|)}} \hat{r}(\pi)$
  \end{algorithmic}
\end{algorithm}

In this section we present our final algorithm.
The algorithm description is given in Algorithm~\ref{alg:main}.
Our algorithm invokes Algorithm~\ref{alg:tsimall} on the set of policies defined in in Definition~\ref{defn:discrete_policies} to obtain trajectories for each policy, and simply returns the policy with largest empirical cumulative reward. Now we give the formal analysis of our algorithm.

\begin{lemma}\label{lem:approx_single}
For each policy $\pi \in \Pi_{\varepsilon / (32 H |\mathcal{S}|)}$, for the value $\hat{r}(\pi)$ calculated in Line~\ref{line:empirical_value} of Algorithm~\ref{alg:main}, with probability at least $1 - \delta_{\mathsf{overall}} / (2 |\Pi_{\varepsilon / (32 H |\mathcal{S}|)}|)$,
\[
\left| \hat{r}(\pi) - \mathbb{E} \left[\sum_{h=1}^{H} r_h \mid \pi\right] \right| \le 5\varepsilon / 16.
\]
\end{lemma}
\begin{proof}
For those policies $\pi \in \Pi_{\mathcal{D}}$, notice that $\{z_i^{\pi}\}_{i \in [F]}$ are sampled by interacting with the environment.
Since all reward values are positive and cumulative reward is upper bounded by $1$ almost surely, by Chernoff bound,
\[
\Pr \left[ \left| \hat{r}(\pi) - \mathbb{E} \left[\sum_{h=1}^{H} r_h \mid \pi\right] \right| \le \varepsilon / 8 \right] \ge 1- 2\exp(-F \varepsilon^2 / 64) \ge 1 - \delta_{\mathsf{overall}} / (2 |\Pi_{\varepsilon / (32 H |\mathcal{S}|)}|).
\]

For those policies $\pi \notin \Pi_{\mathcal{D}}$, notice that $\{z_i^{\pi}\}_{i \in [F]}$ have the same distribution as $F$ independent trajectories sampled by interacting with the environment, except that at most $3\delta_{\mathsf{sim}} /2 \cdot F = 3\varepsilon/16 \cdot F$ trajectories are replaced with \texttt{Fail}.
If all trajectories are independently sampled by interacting with the environment, by Chernoff bound, with probability at least $1 - \delta_{\mathsf{overall}} / (2 |\Pi_{\varepsilon / (32 H |\mathcal{S}|)}|)$,
\[
\left| \hat{r}(\pi) - \mathbb{E} \left[\sum_{h=1}^{H} r_h \mid \pi\right] \right| \le \varepsilon / 8.
\]
Since cumulative reward is in $[0, 1]$ almost surely, by replacing at most $ 3\varepsilon/16 \cdot F$ trajectories with \texttt{Fail}, $\hat{r}(\pi)$ is changed by at most $3\varepsilon/16$.
Therefore, with probability at least $1 - \delta_{\mathsf{overall}} / (2 |\Pi_{\varepsilon / (32 H |\mathcal{S}|)}|)$,
\[
\left| \hat{r}(\pi) - \mathbb{E} \left[\sum_{h=1}^{H} r_h \mid \pi\right] \right| \le 5\varepsilon / 16.
\]

\end{proof}

\begin{lemma}\label{lem:correct}
With probability at least $1 - \delta_{\mathsf{overall}} / 2$, Algorithm~\ref{alg:main} returns an $\varepsilon$-optimal policy.
\end{lemma}
\begin{proof}
By Lemma~\ref{lem:discrete_near_optimal}, there exists a $\varepsilon/4$-optimal policy $\pi' \in \Pi_{\varepsilon / (32 H |\mathcal{S}|)}$.
By Lemma~\ref{lem:approx_single} and a union bound over $\Pi$, with probability at least $1 - \delta_{\mathsf{overall}} / 2$,
for all policy $\pi \in \Pi_{\varepsilon / (32 H |\mathcal{S}|)}$,
\[
\left| \hat{r}(\pi) - \mathbb{E} \left[\sum_{h=1}^{H} r_h \mid \pi\right] \right| \le 5\varepsilon / 16.
\]
Let $\pi$ be the policy returned by algorithm.
Conditioned on the event mentioned above, we have
\[
\mathbb{E} \left[\sum_{h=1}^{H} r_h \mid \pi\right] \ge \hat{r}(\pi) - 5\varepsilon / 16 \ge \hat{r}(\pi') - 5\varepsilon / 16 \ge \mathbb{E} \left[\sum_{h=1}^{H} r_h \mid \pi'\right] - 5\varepsilon / 8 \ge \mathbb{E} \left[\sum_{h=1}^{H} r_h \mid \pi^*\right] - \varepsilon .
\]
\end{proof}

Our main result, Theorem~\ref{thm:main} is a direct implication of Lemma~\ref{lem:sample_complexity} and Lemma~\ref{lem:correct}.

\section{Discussion and Further Open Problems}
\label{sec:dis}
This work provides an episodic, tabular reinforcement learning
algorithm whose sample complexity only depends logarithmically with
the planning horizon, thus resolving the open problem proposed in
\cite{jiang2018open}.  This result is an exponential improvement on the dependency on $H$ over existing upper bounds.
Furthermore, this works applies to
a more general setting, where we only assume the
total  reward is bounded by one, without requiring any boundedness on
instantaneous rewards (see Section~\ref{sec:rel}).

\paragraph{Conjectured Minimax Optimal Sample Complexity for Tabular RL.}
Our upper bounds have a worse dependency on $\abs{\mathcal{S}},
\abs{\mathcal{A}}$ and $1 / \varepsilon$ compared to existing
results. One may conjecture that this suggests there is a tradeoff
between obtaining a sublinear rate (in the model size) and obtaining a
logarithmic dependence on $H$. However,
our conjecture is that this is not the case, and that the  PAC minimax-optimal sample complexity
for episodic, tabular RL (to obtain an
$\varepsilon$-optimal policy) is of the form:
\[
\widetilde{O}\left(\frac{\abs{\mathcal{S}}\abs{\mathcal{A}}\mathrm{poly}(\log  H)}{\varepsilon^2} \right).
\]
This conjecture, if true, would show that when sample complexity is measured by
the number of episodes, then the difficulty of RL is a not a function
of the horizon, and there is a sense in which RL is no more
challenging than a contextual bandit problem.

We also conjecture a minimax optimal regret bound (rather than PAC) is
of the same form.

\paragraph{Computational Efficiency.}
The computation complexity of our simulator scales  as $\abs{\Pi}$ due
to that we need to simulate all policies in the set.
The policy set we study in this paper has cardinality exponential in $\abs{\mathcal{S}}$ and $\abs{\mathcal{A}}$.
We leave it as an open problem is to develop a polynomial time algorithm for the setting where $r_h \ge 0 $  for $h \in [H]$ and $\sum_{h=1}^H r_h \le 1$ whose sample complexity scales only logarithmically with $H$.
One possible way is to exclude sub-optimal policies in $\abs{\Pi}$ in our simulator without explicitly evaluating them.

It is also an important open question whether or not
an upper confidence bound approach achieves the same polylogarithmic
dependence in $H$. Such an algorithm would be promising for resolving
the aforementioned conjectured minimax optimal rate.

\paragraph{Generalization and Large State Space.}
While our paper shows, from sample complexity point of view, that long planning horizon is not an issue, in practice, the state space $\mathcal{S}$ can be huge.
Recently, many works have established that with additional assumptions, e.g. low-rankness of the transition, functions approximations for $Q$-functions, etc, the sample complexity does not depend on $\abs{\mathcal{S}}$~\citep{li2011knows,wen2017efficient,krishnamurthy2016pac,jiang2017contextual,dann2018oracle,du2019provably,feng2020provably,du2019q,zhong2019pac,yang2019reinforcement,jin2019provably,du2019good,roy2019Comments,lattimore2019learning,du2020agnostic,zanette2020learning}.\footnote{Here we only focus on works where agent needs to explore the environment.
There is another line of works that require a sufficiently good exploration policy, e.g., \cite{fan2019theoretical}.
	}
However, to our knowledge, the sample complexity of all these work scales polynomially with $H$ with the only exceptions to require the transition being deterministic~\citep{wen2017efficient,du2020agnostic}.
We believe a fruitful direction is to develop algorithms for these settings with sample complexity that scales only logarithmically with $H$.

\section*{Acknowledgments}
\label{sec:ack}
We thank Alekh Agarwal, Lijie Chen, Nan Jiang, Chi Jin, Yash Nair, Zihan Zhang for useful discussions.
Ruosong Wang is supported is part by NSF IIS1763562, AFRL CogDeCON
FA875018C0014, and DARPA SAGAMORE.
Simon S. Du is supported by NSF grant DMS-1638352 and the Infosys
Membership.
Sham Kakade gratefully acknowledges funding from the Washington Research
Foundation for Innovation in Data-intensive Discover, the ONR award
N00014-18-1-2247, and NSF Award's CCF-1703574 and CCF-1740551.

\bibliographystyle{plainnat}

redpajama_set_name: RedPajamaArXiv


text:
Attractions from all over the world...
Explore our Attractions area on szeneputzen.de, your portal for more success.
Register, Log In and publish your articles, ideas about More success and more money for all our readers!
Beautiful Attractions and details about them...
Planning to see a Beautiful attractions, we have a directory of beautiful attractions in just few clicks...
Elbphilharmonie Hamburg
The Elbphilharmonie is a concert hall in the HafenCity quarter of Hamburg, Germany, on the Grasbrook peninsula of the Elbe River. It is one of the largest and acoustically most...
Romantic Road
The Romantic Road (German: Romantische Straße) is a "theme route" devised by promotion-minded travel agents in the 1950s. It describes the 350 kilometres of surface roads between Würzburg and Füssen...
Europa-Park
Europa-Park is the largest theme park in Germany, and the second most popular theme park resort in Europe, following Disneyland Paris. If you come to Europa-Park looking for fun, excitement...
Heidelberg Palace
The English landscape garden, also called English landscape park or simply the English garden, is a style of "landscape" garden which emerged in England in the early 18th century, and...
Marienplatz
Marienplatz was named after the Mariensäule, a Marian column erected in its centre in 1638 to celebrate the end of Swedish occupation. Marienplatz is a central square in the city...
Cologne Cathedral
The Reichstag is a historic edifice in Berlin, Germany, constructed to house the Imperial Diet (German: Reichstag) of the German Empire. The Reichstag bears silent witness to the turbulent history...
The Brandenburg Gate is an 18th-century neoclassical monument in Berlin, built on the orders of Prussian king Frederick William II after the temporary restoration of order during the Batavian Revolution....
Neuschwanstein Castle is a 19th-century Romanesque Revival palace on a rugged hill above the village of Hohenschwangau near Füssen in southwest Bavaria, Germany. The palace was commissioned by Ludwig II...
Spiti Valley
Spiti Valley is a cold desert mountain valley located high in the Himalayas in the north-eastern part of the northern Indian state of Himachal Pradesh. The name "Spiti" means "The...
Dudhsagar Falls
Dudhsagar Falls (literally Sea of Milk) is a four-tiered waterfall located on the Mandovi River in the Indian state of Goa. It is 60 km from Panaji by road and...
Nahargarh Fort
Nahargarh Fort stands on the edge of the Aravalli Hills, overlooking the city of Jaipur in the Indian state of Rajasthan. Along with Amer Fort and Jaigarh Fort, Nahargarh once...
Kaziranga national park
One of the most sought after wildlife holiday destinations in India, Kaziranga National park's 430 square kilometer area sprinkled with elephant-grass meadows, swampy lagoons, and dense forests is home to...
Ranthambore National Park
Ranthambore National Park is one of the biggest and most renowned national park in Northern India. In 1992, the Tiger Reserve was expanded to include the adjoining Keladevi Sanctuary in...
Informieren Sie sich über neue Listing
Abonniere jetzt

redpajama_set_name: RedPajamaCommonCrawl


text:
Q: jQuery trigger inside ES6 class is not working I´m struggling with a jQuery trigger inside an ES6 class. I can't figure out why this trigger is not working.
This is my class. The trigger should be executed when the triggerFilter method is called.

// vendor import
import $ from 'jquery';

export default class SortingBar {
    constructor() {
        this.element = '[data-sortingBar]';
        this.sortOption = $(this.element).find('.sorting-bar__item');
        this.sortType = '';
        this.sortTypeInput = $(this.element).find('[name="sortType"]');
        this.init();
    }

    init() {
        // early exit
        if ($(this.element).length === 0) {
            return false;
        }

        // trigger filter on sort option click
        this.sortOption.on('click', (e) => {
            this.triggerFilter(e.currentTarget);
        });
    }

    triggerFilter(element) {
        // avoid filter trigger for active sort option
        if ($(element).hasClass('active')) {
            return false;
        }

        // set sort option value for hidden input
        this._setSortTypeInputValue(element);

        // trigger filter change
        this.sortTypeInput.trigger('change');
    }

    _getSortType(element) {
        this.sortType = $(element).data('sort-type');
        return this.sortType;
    }

    _setSortTypeInputValue(element) {
        this.sortTypeInput.val(this._getSortType(element));
    }
}

This module is imported in the main file like this

// modules import
import Overlay from './modules/overlay';
import SortingBar from './modules/sorting-bar';

// modules init
const overlay = new Overlay();
const sortingBar = new SortingBar();

// modules object
const modules = {
    overlay,
    sortingBar
};

// modules object default export
export default {
    modules
};

There is also an old filter.js file in which the change event is binded to the hidden input which should be triggered. This file will be loaded before the main.js file.

$('[name=selectWrapper], [name=sortType], [data-filters=reset]').on('change', refreshByChange);

I'm using webpack and babel-loader to compile the files to ES5. This is my Webpack config.

// require
const path = require('path');
const webpack = require('webpack');

// check node enviroment
const nodeEnv = process.env.NODE_ENV || 'development';
const isProd = (nodeEnv.trim() === 'production');

// default config settings
const config = {
    entry: {
        desktop: './src/main/js/thymeleaf_desktop/main_desktop.js'
        // mobile: './src/main/js/thymeleaf_phone/main_mobile.js'
    },
    output: {
        filename: 'main_[name].js',
        path: path.resolve(__dirname, 'target/classes/js/thymeleaf_desktop')
    },
    module: {
        rules: [
            {
                test: /\.js$/,
                exclude: /node_modules/,
                use: {
                    loader: 'babel-loader?cacheDirectory=true',
                    options: {
                        presets: ['es2015']
                    }
                }
            }
        ]
    },
    plugins: [],
    devtool: 'inline-source-map'
};

// production config settings
if (isProd) {
    // eslint config settings
    const eslintConfig = {
        enforce: 'pre',
        test: /\.js$/,
        exclude: /(node_modules|_externals|standalone)/,
        loader: 'eslint-loader',
        options: {
            configFile: path.resolve(__dirname, './src/build/eslint/webpack/.eslintrc')
        }
    };

    config.devtool = false;
    config.module.rules.push(eslintConfig);
    config.output.filename = 'main_[name].min.js';
    config.plugins.push(
        new webpack.optimize.UglifyJsPlugin()
    );
}

module.exports = config;

The strange thing is, when I put the trigger in the main.js file everything is working just fine.
Is there a known issue for jQuery trigger inside an ES6 class?

A: Base on the comment the problem is that two instances of jQuery are used.
The jQuery2130225834388266846541 tells you that the jQuery version 2.3.1 (the first three digits of the whole number, the other digits are the unique id of the instance)  was used to register the event listener.
import $ from 'jquery'; includes the most likely the node module version (3.2.1)
The event triggering in jQuery does not use native events but an own event handling. You can only listen to events that are triggered by the same instance of jQuery that was used to register the even listeners (even if it is the same jQuery version), so you have to make sure that you only use one jQuery instance.
This is not only the case for event handling but also for .data(), because each instance of jQuery creates an own and isolated storage for data and even listeners. This can not only result in problems like the given one but also into memory leaks.

A: I solved the problem by changing the jQuery trigger to native Javascript.
from:
this.sortTypeInput.trigger('change');
to:
const event = new Event('change');
 document.getElementById('sortType').dispatchEvent(event);
I don´t know why jQuery trigger is not working thow.

A: I had this problem and it came from the webpack context. Webpack create a copy of jquery so the event was triggered but in the wrong scope.
I deal with it by adding this line at the beggining of my code: $ = window.$;

redpajama_set_name: RedPajamaStackExchange


Gül Hürgel's top is made from an airy linen that's patterned with royal blue floral blooms. It has a rounded collar, fluttering cape sleeves and a buckle-fastening waist belt. Layer it over the label's matching pants.


text:
Alanis Martinez, Photographer
With a very open minded and determined personality, Alanis Martinez, 10, joins the Downey Legend as a photographer. Since 7th grade, Martinez has shown her interest in photojournalism, photography, and writing which made her grow and improve her skills, guiding her to join this year's newspaper staff as a photographer. Whether it be a big or small project, Martinez is very optimistic about her first year and can't wait to be involved to showcase her creative ideas. With qualities of being a natural leader, Martinez hopes to enter a profession in the educational field working with kids. Martinez was a camp counselor for kindergarteners and hopes to one day influence and shape kids into amazing leaders as well.
"Being a part of journalism made me feel like I have an important role in the school" Martinez stated. "Spreading the word and involving everyone, whether it be with a small interview, can go a long way, I feel like I've grown, not just educational wise but also as a person"
All content by Alanis Martinez
Favorite Holiday Films
Halloween Horror Nights at Universal Studios Hollywood
Taylor Swift's Newest Album: Midnights
Our Los Angeles Dodgers: NL West Champions!
Love is in the Air with Love Club
Alanis Martinez


Alicia Lopez-Harrison de Larde supported her mathematician husband John Nash and was a mental health care advocate.
"I'm not out there to find a cure for AIDS, I'm out there to help the kids who are orphaned by it"
Louis Zamperini was a WW2 prisoner of war survivor who forgave his tormentor and inspires others to forgive.
Terry Fox a nation through his courage and tenacity.
Audrey Hepburn was an actress, dancer and notable Ambassador for UNICEF.
St. Katharine Drexel supported petitions to Congress to improve governmental aid for Native American schools.
Suzan Mathebule and Joanna Jordan- two mothers, two lives, two continents.
Adi Roche founded an organization that helps orphans of nuclear disaster.
Lisa Ford was a courageous cancer victim who inspired her friend, Claire.
Alicia O'Brien was the inspiration for Cherie Bennett's novel Zink.
Saur Marlina Manurung provides educational opportunities in a remote Indonesian village.
Jeni Stepanek is an ambassador for Muscular Dystrophy who continues to spread her son Mattie's message of peace.
Leo A Strutner believed that if you love the people around you, the love will return to you as happiness.
Ann Armstrong-Dailey and Children's Hospice International meet the special needs of children with life-threatening conditions.
Ryuichi Hirokawa photographer who illuminates the needs of children in crisis.
Susan G. Komen was the inspiration for her sister to reach out to other women with cancer.
Dr. Andrew Wade saved a child's life and she thanks him here.
Abdul Sattar Edhi founded Edhi International Foundation, and has been called the greatest living humanitarian in the world.
Kelly Perkins climbs mountains to raise support for organ donation.
Connie O'Connell was a hero and inspiration to her family.
Florence Kelley was an outspoken leader against child labor.
William J. Meyers taught the importance of taking time to enjoy LIFE, with music, art, laughter and friends.
Mother Teresa devoted her life to the homeless and dying in India.
Daphna Ziman founded Children Uniting Nations.
Papa Lloyd did not let his blindness keep him from serving his community.


text:
```bash
# starting after machine or VBox crash or restart
eval "$(docker-machine env springmusic)"
docker-machine start springmusic
docker-machine regenerate-certs springmusic

# orchestrate start-up of containers, tailing the logs...
docker-compose -p music up -d elk && docker logs elk --follow # ^C to break
docker-compose -p music up -d mongodb && docker logs mongodb --follow
docker-compose -p music up -d app && docker logs music_app_1 --follow
docker-compose scale app=3 && sleep 15
docker-compose -p music up -d proxy && docker logs proxy --follow

# orchestrate start-up of containers
docker start elk && sleep 15 \
  && docker start mongodb && sleep 15 \
  && docker start music_app_1 music_app_2 music_app_3 && sleep 15 \
  && docker start proxy

# update images
docker pull mongo:latest \
  && docker pull nginx:latest \
  && docker pull sebp/elk:latest \
  && docker pull tomcat:8.5.4-jre8

# stopping containers
docker-compose stop
# removing containers
docker-compose rm

# inspect VM
docker-machine inspect springmusic
docker-machine ssh springmusic
```

## Application Startup Issues

```bash
# stop / start Tomcat
docker exec -it music_app_1 sh /usr/local/tomcat/bin/startup.sh
docker exec -it music_app_1 sh /usr/local/tomcat/bin/shutdown.sh

# check logs for start-up issues...
docker exec -it music_app_1 cat /var/log/spring-music.log
docker exec -it music_app_1 ls -al /usr/local/tomcat/logs
docker exec -it music_app_1 cat /usr/local/tomcat/logs/catalina.out
docker logs music_app_1

# remove application containers and images
docker rm -f music_app_1 music_app_2 music_app_3
docker rmi music_app

# remove dangling (unused) volumes
docker volume rm $(docker volume ls -qf dangling=true)

# remove <none> images
docker rmi $(docker images -a | grep "^<none>" | awk "{print $3}")
```

## Useful Links

- <http://elk-docker.readthedocs.io/>
- <http://pugnusferreus.github.io/blog/2016/01/03/integrating-logstash-with-your-java-application/>
- <http://techfree.com.br/2016/07/dockerizando-aplicacoes-concorrencia/>

redpajama_set_name: RedPajamaGithub


Section 85. Contributory negligence shall not bar recovery in any action by any person or legal representative to recover damages for negligence resulting in death or in injury to person or property, if such negligence was not greater than the total amount of negligence attributable to the person or persons against whom recovery is sought, but any damages allowed shall be diminished in proportion to the amount of negligence attributable to the person for whose injury, damage or death recovery is made. In determining by what amount the plaintiff's damages shall be diminished in such a case, the negligence of each plaintiff shall be compared to the total negligence of all persons against whom recovery is sought. The combined total of the plaintiff's negligence taken together with all of the negligence of all defendants shall equal one hundred per cent.
The violation of a criminal statute, ordinance or regulation by a plaintiff which contributed to said injury, death or damage, shall be considered as evidence of negligence of that plaintiff, but the violation of said statute, ordinance or regulation shall not as a matter of law and for that reason alone, serve to bar a plaintiff from recovery.
The defense of assumption of risk is hereby abolished in all actions hereunder.
The burden of alleging and proving negligence which serves to diminish a plaintiff's damages or bar recovery under this section shall be upon the person who seeks to establish such negligence, and the plaintiff shall be presumed to have been in the exercise of due care.


text:
Élie Marie Gabriel Dor de Lastours (12 August 1874 – 18 November 1932), also known as Élie, Count de Lastours, was a French fencer and tennis player. He competed in the individual épée and men's doubles events at the 1900 Summer Olympics.

References

External links

1874 births
1932 deaths
Fencers at the 1900 Summer Olympics
French male épée fencers
French male tennis players
Olympic fencers of France
Olympic tennis players of France
Tennis players at the 1900 Summer Olympics
Sportspeople from Yvelines

redpajama_set_name: RedPajamaWikipedia


The $7.6 billion overall impact of UIC on the state is larger than the entire Arts, Entertainment & Recreation industry in Illinois and supports 73,559 jobs. With 7.8 million jobs in the state, this means that one out of every 106 jobs is supported by the activities of UIC and its students.
The impact of UIC's $424.6 million in research spending on the state economy is equal to supporting 4,370 jobs. In the last four years, UIC has received 624 invention disclosures, filed 199 new U.S. patent applications and produced 212 licenses.
UIC's 16.5% annual rate of return for students shows that there are life-long benefits of attending UIC and for every $1 invested, students receive $5.30 in higher future income.


text:
Q: How to set Bottom Navigation Bar in Android Can anyone help me, my bottom navigation bar looks like this:

I want to make it to look like this:
Offcourse, with blue color.
My code is below: Thanks everyone!!
layout.xml
 <android.support.design.widget.BottomNavigationView

            android:id="@+id/bottom_navigation"
            android:layout_width="match_parent"
            android:layout_height="wrap_content"
            android:layout_alignParentBottom="true"
            app:menu="@menu/main_manu"
            app:itemBackground="@color/blue"
            app:itemIconTint="@android:color/white"
            app:itemTextColor="@android:color/white"
            app:layout_behavior="com.google.android.material.behavior.HideBottomViewOnScrollBehavior"

            />

Application.java
final BottomNavigationView bottomNavigationView = (BottomNavigationView) findViewById(R.id.bottom_navigation);
        Menu menu = bottomNavigationView.getMenu();
        MenuItem menuItem = menu.getItem(2);
        menuItem.setChecked(true);
        bottomNavigationView.setOnNavigationItemSelectedListener(new BottomNavigationView.OnNavigationItemSelectedListener() {
            @Override
            public boolean onNavigationItemSelected(@NonNull MenuItem item) {
                switch (item.getItemId()) {
                    case  R.id.action_pocetna:
                        new ListaVoznji.Home().execute();
                        break;
                    case R.id.action_unos:
                        new ListaVoznji.Login().execute();
                        break;
                    case R.id.action_pregled:
                        Intent intent2 = new Intent(ListaVoznji.this,ListaSvihVoznji.class);
                        intent2.putExtra("voznja",voznja);
                        startActivity(intent2);
                        break;
                    case R.id.action_shutdown:
                        Intent homescreen=new Intent(ListaVoznji.this,LoginActivity.class);
                        log = 1;
                        homescreen.addFlags(Intent.FLAG_ACTIVITY_CLEAR_TOP);
                        startActivity(homescreen);
                        finish();
                        break;

                }
                return true;
            }
        });

A: Add app:labelVisibilityMode="labeled" in your layout in botton navigation

A: Just use the background attribute to change the whole background , and if you want to customize the item's text and icon color , you can do this by :
First create a drawable file name item_background , add to it the following lines :
<selector>
<item android:state_checked="true" android:color="@color/colorPrimary" />

 <item android:state_checked="false" android:color="@color/colorAccent"/>

</selector>

Then in your bottom navigation view add attributes itemTextColor & itemIconTint with the value @drawable/item_background


text:
I'm just a lady who likes to read, write and drink!
The Book Blog Around the Corner
YA Reviews
Mystery Reviews
Adult Fiction Reviews
Owlcrate Unboxings
Review- City of Ghosts
⭐⭐⭐⭐⭐/ 5 stars
Synopsis from GoodReads:
They're here.
They're watching.
Cass can pull back the Veil that separates the living from the dead.
When Cass's parents start hosting a TV show about the world's most haunted places, the family heads off to Edinburgh. Here, graveyards, castles and secret passageways teem with restless phantoms.
But when Cass meets a girl who shares her "gift", she realizes how much she still has to learn about the Veil—and herself. And she'll have to learn fast. The city of ghosts is more dangerous than she ever imagined.
My Thoughts-Spoiler Free
Cassidy Blake can see the dead even her best friend Jacob is a ghost. She can also cross into the veil where the spirits reside after death but only temporary.
Her parents are writers and write ghost stories of all things. In fact they land a documentary TV show where they visit haunted cities and the ghost legends in that land, except Cass is pretty sure neither of them have actually seen or met a ghost.
Unfortunately, for Cass she can't tell anyone her secret. Even her parents. As they start filming their TV show, their first stop is Edinburgh, a city teeming with ghosts. There Cass and Jacob meet Lara, a teen girl who has the same gift as Cass, except she knows far more about their ability and helps Cass understand her purpose.
While in the veil, Cass encounters a mysterious spirit who legend says takes the lives of children and she has her eyes set on Cassidy. What is it about Cass that the spirit wants? That's what we find out. It's a good one, I promise.
I love Jacob and the relationship between him and Cass. Jacob may be a ghost but we get a 3D version of him full of voice and personality. I loved every bit of him. I hope we get to find out his story in book 2. Cassidy is such a great flawed character. I wasn't annoyed by her mistakes but more like, oh yeah, I can see how that happened. I think we've all been there.
This book was a fast read and if you're looking for a spooky story this season, pick up City of Ghosts and you can even read it with your kiddos!
Review-The Dark Descent of Elizabeth Frankenstein
Review-The Shadows Between Us
Review-Tunnel of Bones
© 2020 by AB_ReedBooks


text:
Tagetes erecta
Common Name: African Marigold
Flowering plant (yellow form)
Photograph by: Not known
Creative Commons Attribution-Share Alike 3.0
Flowers and leaves of an orange form
Photograph by: Forest and Kim Starr
Tagetes erecta is an annual plant that can grow up to 1.00 metres tall.
It is harvested from the wild for local use as a food, medicine and source of materials.
Southern N. America - Mexico.
Grows in the pine-oak forest zone[
Meet Flora Mexicana.
Pesman. M. W.
Dale S. King. Arizona.
Very readable flora but rather lacking botanically. A few notes on useful plants.
]. A garden escape in the USA where it grows along the sides of roads[
Habit Annual
Requires a well-drained moderately fertile soil in a sunny position[
]. Grows well in heavy clay soils and in sandy soils[
Although not very frost resistant, it can be grown as a tender annual in Britain, sowing the seed in a greenhouse in the spring and planting out after the last expected frosts.
The flowers are often sold in local markets in Nepal and used as an offering to the Gods[
Plants and People of Nepal
Manandhar. N. P.
Excellent book, covering over 1,500 species of useful plants from Nepal together with information on the geography and peoples of Nepal. Good descriptions of the plants with terse notes on their uses.
A number of named forms have been developed for their ornamental value[
Cornucopia - A Source Book of Edible Plants.
Facciola. S.
Kampong Publications
0-9628087-0-9
Excellent. Contains a very wide range of conventional and unconventional food plants (including tropical) and where they can be obtained (mainly N. American nurseries but also research institutes and a lot of other nurseries from around the world.
]. The cultivar 'Yellow Climax' has mild flavoured edible flowers that can be used as colourful garnishes[
All parts of the plant emit an unpleasant smell similar to that of stale urine when they are bruised[
Removing dead flowers before the seed is formed will extend the flowering season[
Plants are prone to attacks by slugs, snails and botrytis[
The petals of the flowers of some varieties can be eaten[
]. The fresh receptacle is eaten by children[
A yellow dye obtained from the flowers can be used as a saffron substitute for colouring and flavouring foods[
The plant is used as a condiment[
]. (This probably refers to the use of the flowers as an edible dye)
The whole herb is anthelmintic, aromatic, digestive, diuretic, emmenagogue, sedative and stomachic[
]. It is used internally in the treatment of indigestion, colic, severe constipation[
], coughs and dysentery[
]. Externally, it is used to treat sores, ulcers, eczema. sore eyes and rheumatism[
]. The leaves are harvested as required for immediate use during the growing season, whilst the flowering plant can be dried and stored for later use[
A paste of the leavs is applied externally to treat boils, carbuncles and earaches[
The flowers are carminitive, diuretic and vermifuge[
]. A decoction is used to treat colds, and mumps[
]. It is applied externally to trea skin diseases, conjunctivitis and sore eyes[
The root is laxative[
Secretions from the roots of growing plants have an insecticidal effect on the soil, effective against nematodes and to some extent against keeled slugs. These secretions are produced about 3 - 4 months after sowing[
]. The flower petals also have nematacidal properties[
]. The growing plant is also said to repel insects and can be grown amongst crops such as potatoes and tomatoes.
A yellow dye is obtained from the flowers[
A Weavers Garden
Buchanan. R.
McGraw-Hill Contemporary
Covers all aspects of growing your own clothes, from fibre plants to dyes.
Seed - sow early spring in a greenhouse. Only just cover the seed. Germination usually takes place within 2 weeks. When they are large enough to handle, prick the seedlings out into individual pots and plant them out after the last expected frosts.
Cite as: Temperate Plants Database, Ken Fern. temperate.theferns.info. 2023-02-02. <temperate.theferns.info/plant/Tagetes+erecta>
Captcha: if i have 3 bananas, and i eat them all, how many bananas did i just eat?


Call 765.285.5531 or visit MuncieSymphony.org for more information.
Witness the talents of young musicians who live right here in the state of Indiana! These amazing, accomplished musicians compete for monetary awards and performance opportunities.


MUMBAI: Vedanta Board has 12.5% representation of women and has set a target to reach a level of 33% by 2020, Vedanta Group's Sustainable Development Report for the year 2015-16, revealed. Vedanta Limited, India's leading diversified natural resources company. Group has also established gender diversity target for Business Level.
Vedanta has released recently its 8th Sustainable Development Report for its group companies, which is prepared based on Global Reporting Initiative (GRI) G4 – 'in accordance'- Core guidelines and is mapped to the United Nations Global Compact (UNGC) and Sustainable Development Goals (SDGs).
Women representation in total employee strength is 9.4% in the year 2015-16 as compare to 8.6% for the year 2014-15.
The progress in gender equality in the corporate sector is moving forward. Women hold up half the sky, if empowered, they have the ability to not just lead the society, but also contribute to economic activities of the country.
"We represent one of the highest numbers of women in senior management in the industry.", Vedanta said.
"Our board has 12.5% representation of women and has set a target to reach over 33% by 2020. This diversity focus is visible across hierarchies and functions." Report said.
As a new target, Continue to focus on the same diversity objective of 15% women hiring, more than 15% of female professionals join the group and has target to focus on the same diversity objective of hiring 15% for the year 2016-17.
"To enable women to work with dignity and without fear, a sexual harassment prohibition policy and sexual harassment committee is in place in each business.", it added.
In the year 2014-15, 184 female employees have taken parental leaves.
Vedanta has recently announced an enhanced parental leave policy for its employees. Building upon its employee friendly policies, the company's maternity leave has been enhanced to 26 weeks. The company has also introduced an adoption leave for 12 weeks and a paternity leave for 1 week. It is said that the new parental leave policy is best-in-class in the industry.
"In a male dominated sector like mining, five women in Vedanta Resources' Aluminium Manufacturing plant in Lanjigarh (Odisha) are in-charge of the two most important departments – central control room laboratory and distribution control system. This is not just a one-off case, but part of a well thought out group-wide strategy to appoint women in key revenue generating roles at the leadership level.", report said.
"Across the Group, both men and women are recruited on the premise of 'equal remuneration, equal opportunities", report said.
In recent years, Vedanta has witnessed the appointment of women to a number of key positions including Non-Executive Director-CEO-Zinc International, Group President-Sustainability, CSR and Community, Group Head of Treasury, Head CSR-HZL and Group Head –Taxation.
"Our recruitment drives focus on identifying women candidates of key roles and offering them career advancement. We have witnessed an upward inclination in percentage of women in total workforce ratio, i.e. from 8.1% in FY 2012-13 to 9.4% in FY 2015-16." Report also said.
Vedanta is also signatory to the 'CEO Statement of Support' for the United Nations' Women's Empowerment Principles.
The 67 pages report highlighted the wide range of business responsibility and sustainability issues that impact stakeholders and community. They report on how Vedanta is managing these constantly evolving issues and provided a deep insight into future aspects of interventions.
The report is an approach and disclosure towards triple bottom line principles – people, planet and profit over the financial year 2015-16.
Vedanta group companies: Vedanta Limited, Bharat Aluminium Company Ltd. (BALCO), Konkola Copper Mines, Copper Mines of Tasmania, Hindustan Zinc Ltd, Talwani Sabo Power, Cairn India, Zinc International, Sterlite Copper, Sesa Iron Ore.
Vedanta Resources is a London Stock Exchange listed, globally diversified natural resources Company with interests in Zinc, Lead, Silver, Copper, Iron Ore, Aluminium, Power, and Oil & Gas. Our operational footprint spans four continents encompassing India, Zambia, Namibia, South Africa, Liberia, Ireland, Sri Lanka and Australia.


text:
Q: How do I have a view controller run updating code when it is brought to the top of the stack of views? I have a viewController (Planner) that loads two view controllers (InfoEditor and MonthlyPlan) when the application starts. MonthlyPlan is hidden behind InfoEditor (on load).
So my question is when I exchange InfoEditor for MonthlyPlan (MonthlyPlan gets brought to the top) how can I have data on the MonthlyPlan view be updated. An NSLog in viewDidLoad is being called when the application starts (which makes sense.) NSLogs in viewDidAppear and viewWillAppear aren't doing anything.
Any ideas?
Thanks!
-- Adding more details --
I'm creating the view hierarchy myself. A simple viewController that is just loading two other viewControllers. The two child viewControllers are loaded at the same time (on launch of application.) To exchange the two views I'm using this code:
[self.view exchangeSubviewAtIndex:1 withSubviewAtIndex:0];

The exchanging of the views is fine. The part that is missing is just some way of telling the subview, you're in front, update some properties.

A: There's a lack of details here. How are you "exchanging" the two views?
If you were using a UINavigationController as the container then viewWillAppear/viewDidAppear would be called whenever you push/pop a new viewController. These calls are made by the UINavigationController itself. If you ARE using a UINavigationController then make sure you have the prototypes correct for these functions.
- (void)viewWillAppear:(BOOL)animated

If you are trying to implement a view hierarchy yourself then you may need to make these calls yourself as part of activating/deactivating the views. From the SDK page of viewWillAppear;

If the view belonging to a view
  controller is added to a view
  hierarchy directly, the view
  controller will not receive this
  message. If you insert or add a view
  to the view hierarchy, and it has a
  view controller, you should send the
  associated view controller this
  message directly.

Update:
With the new details the problem is clear: This is a situation where you must send the disappear/appear messages yourself as suggested by the SDK. These functions are not called automagically when views are directly inserted/removed/changed, they are used by higher-level code (such as UINavigationController) that provides hierarchy support.
If you think about your example of using exchangeSubView then nothing is disappearing, one view just happens to cover the other wholly or partially depending on their regions and opacity.
I would suggest that if you wish to swap views then you really do remove/add as needed, and manually send the viewWillAppear / viewWillDisappear notifications to their controllers.
E.g.
// your top level view controller
-(void) switchActiveView:(UIViewController*)controller animated:(BOOL)animated
{
    UIController* removedController = nil;

    // tell the current controller it'll disappear and remove it
    if (currentController)
    {
        [currentController viewWillDisapear:animated];
        [currentController.view removeFromSuperView];
        removedController = currentController;
    }

    // tell the new controller it'll appear and add its view
    if (controller)
    {
        [controller viewWillAppear:animated];
        [self.view addSubView:controller.view];
        currentController = [controller retain];
    }

    // now tell them they did disappear/appear
    [removedController viewDidDisappear: animated];
    [currentController viewDidAppear: animated];
    [removedController release];
}

A: I would just add an updataData method to each subview and call it at the same time you bring it to the front. You would need to add a variable to your root view controller to track the active subView:
[self.view exchangeSubviewAtIndex:1 withSubviewAtIndex:0];
if (subView1IsActive) [subView1Controller updateData];
else [subView2Controller updateData];


Our program for two-year-olds provides an opportunity for young children to experience a social setting away from home and parents, as well as to function in a group of children their own age, and to relate to adults other than their parents. This Montessori experience is a comfortable first step away from home and into the larger community. A home visit by the teacher for each family encourages a smooth and positive separation for the child on the road to becoming more independent.
Guided by an experienced and certified Montessori trained teacher along with an assistant, the environment is prepared especially for the young child with materials for language development, practical life and sensory skills predominating. These exercises encourage concentration, independence, sensitivity to one's surroundings and awareness to order. These experiences form the base upon which the sequence of advanced Montessori materials builds. Our cozy, home-like environment with plenty of natural light helps to ensure that this first school experience be one that creates joy of living and learning as the young child is gently guided toward independent self-directed learning. Parents, staff and children also work together on learning to use the toilet as readiness occurs.


IBM is simply too late: Microsoft has the business email market sewn up with Exchange and Office 365 and is advancing on all fronts in the context of social, content management and cloud.
IBM is making a big push into email at a time when email is passé and we're all moving on to newer and better ways of communicating.
IBM is smart enough to know that email use is actually growing, but email users need a new paradigm, such as melding email with social and analytics that will make the email experience more effective and efficient.
I'm in the last camp. Our research shows that email use is growing and that it's actually a more important communication medium for information workers today than it was just a year ago. Our research shows that email is the primary tool that individuals use to do their work, accounting for about 160 minutes of time spent during a typical workday. Email has become the de facto file transport system for most users, their contact manager, their task manager, and – in many cases – their personal archive. Finally, our research shows that email is still the most important single application in the new paradigm of mobility.
First, Verse represents a new design for email that, at first and second glance, looks as though it contains some elements borrowed from the iOS design team. That may or may not be a coincidence given IBM and Apple recent cozying up to one another.
Second, Verse carries with it the promise of a significant focus on enterprise social networking and analytics in an email context that can make the email experience more efficient and that can make users more productive. The new paradigm will be particularly important for mobile workers and those that work on distributed teams – one of the raisons d'etre for enterprise social networking.
Microsoft is continuing to push hard with Office 365 (albeit not with on-premises Exchange). The company has a very solid lead in the business-grade email and cloud markets, they're the "comfortable" choice for decision makers, and they have solid offerings in social, content management, file sync and share, server and other key markets that fill out the Microsoft ecosystem quite nicely.
Outlook is the dominant email client in every business market (small business, mid-market and enterprise). That's important, since lots of business decision makers still think their corporate email system is "Outlook" even though it's really Exchange.
Microsoft's marketing engine has more horsepower. That's not a ding against IBM's marketing prowess, but Microsoft marketing gets in front of people more effectively.
Email is deeply entrenched in virtually every organization. Convincing decision makers to implement a new email system that will benefit primarily users will not be easy.
Personally, I'm looking forward to using Verse as soon as possible. I'd prefer that IBM offer a thick client for Verse (yes, I'm one of those old school dinosaurs that prefers thick clients to the browser experience), but I don't believe that's in the offing, at least in the near term.
The bottom line: I think Verse has a decent chance of being quite successful if IBM can appropriately educate a large part of the market that email must be – and can be – more efficient and effective.
Previous Previous post: How Have Email and Instant Messaging Use Changed Since 2001?


Don't get confused. The summer is coming. For real! To be prepared for all sorts of seasonal situations (occupy beach chairs, take a sun bath, take a real bath, swing something through the air while a hiphop jam is playing etc.), we just launched the Keinemusik beach towel. In all purpose size of 90 x 160 cm, you can also build a comfy beach bed out of it. The colorful artwork comes from Monja Gentschow, obviously. Now available in our shop.


"Another thing we can do for jobs is make toys of me, especially for the holidays. Little dolls. Me. Like maybe little action dolls. Me in an army uniform, air force uniform, and me in my suit. They can make toys of me and my vehicle, especially for the holidays and Christmas for the kids. That's something that would create jobs. So you see I think out of the box like that. It's not something a typical person would bring up. That's something that could happen, that makes sense. It's not a joke," - Alvin Greene, joke Democratic nominee for US Senate in South Carolina.