that they are unbiased estimates of $V^{\pi}$. Observe that one way of
defining $V^{\pi}$ is the expected value of the following process:

  1. $(1)$

For every $(s,a)\in\mathcal{S}\times\mathcal{A}$, independently sample a next
state $s^{\prime}\sim P(\cdot|s,a)$ and a reward $r\sim R(s,a)$ to define a
deterministic MDP $\widehat{M}$

  2. $(2)$

Return the value $\widehat{v}^{\pi}$ to be the value of $\pi$ run on
$\widehat{M}$.

Define the law of this process as $\overline{\mathcal{Q}}$. The sampling
process of $\mathsf{TrajectoryTree}$ (call the law of this process
$\mathcal{Q}$) can be viewed as sampling the subset of
$\widehat{M}^{\mathrm{det}}$ which is reachable by some $\pi\in\Pi$. Thus, we
have

$\displaystyle
V^{\pi}=\mathbb{E}_{\widehat{M}\sim\overline{\mathcal{Q}}}\left[\widehat{v}^{\pi}\right]=\mathbb{E}_{\widehat{T}_{\sim}\mathcal{Q}}\left[\mathbb{E}\left[\widehat{v}^{\pi}\mid{}\widehat{T}\right]\right]=\mathbb{E}_{\widehat{T}_{\sim}\mathcal{Q}}\left[\widehat{v}^{\pi}\right],$

where the second equality is due to the law of total probability, and the
third equality is due to the fact that $\widehat{v}^{\pi}$ is measurable with
respect to the trajectory tree $\widehat{T}$. Thus,
$\\{\widehat{v}_{i}^{\pi}\\}_{i\in[n]}$ are unbiased estimates of $V^{\pi}$.

Therefore, by Hoeffding’s inequality (Lemma 17) we see that $\lvert
V^{\pi}-\widehat{V}^{\pi}\rvert\leq\sqrt{\tfrac{\log(2/\delta)}{2n}}$.
Applying union bound we see that when the number of trajectory trees exceeds
$n\gtrsim\tfrac{\log(\lvert\Pi\rvert/\delta)}{\varepsilon^{2}}$, with
probability at least $1-\delta$, for all $\pi\in\Pi$, the estimates satisfy
$\lvert V^{\pi}-\widehat{V}^{\pi}\rvert\leq\varepsilon/2$. Thus the
$\mathsf{TrajectoryTree}$ algorithm returns an $\varepsilon$-optimal policy.
Since each trajectory tree uses at most $H\cdot\mathfrak{C}(\Pi)$ queries to
the generative model, we have the claimed sample complexity bound. ∎

###  D.2 Proof of Theorem 2

Fix any worst-case deterministic MDP $M^{\star}$ which witnesses
$\mathfrak{C}(\Pi)$ at layer $h^{\star}$. Since $\mathfrak{C}(\Pi)$ is a
property depending on the dynamics of $M^{\star}$, we can assume that
$M^{\star}$ has zero rewards. We can also assume that the algorithm knows
$M^{\star}$ and $h^{\star}$ (this only makes the lower bound stronger). We
construct a family of instances $\mathcal{M}^{\star}$ where all the MDPs in
$\mathcal{M}^{\star}$ have the same dynamics as $M^{\star}$ but different
nonzero rewards at the reachable $(s,a)$ pairs at layer $h^{\star}$.

Observe that we can embed a multi-armed bandit instance with
$\mathfrak{C}(\Pi)$ arms using the class $\mathcal{M}^{\star}$. The value of
any policy $\pi\in\Pi$ is exactly the reward that it receives at the _unique_
$(s,a)$ pair in layer $h^{\star}$ that it reaches. Any
$(\varepsilon,\delta)$-PAC algorithm that works over the family of instances
$\mathcal{M}^{\star}$ must return a policy $\hat{\pi}$ that reaches an $(s,a)$
pair in layer $h^{\star}$ with near-optimal reward. Furthermore, in the
generative model setting, the algorithm can only receive information about a
single $(s,a)$ pair. Thus, such a PAC algorithm must also be able to PAC learn
the best arm for multi-armed bandits with $\mathfrak{C}(\Pi)$ arms. Therefore,
we can directly apply existing PAC lower bounds which show that the sample
complexity of $(\varepsilon,\delta)$-PAC learning the best arm for $K$-armed
multi-armed bandits is at least
$\Omega(\tfrac{K}{\varepsilon^{2}}\cdot\log\tfrac{1}{\delta})$ (see, e.g.,
Mannor and Tsitsiklis, 2004).∎

###  D.3 Proof of Corollary 1

The upper bound is obtained by a simple modification of the argument in the
proof of Theorem 1. In terms of data collection, the trajectory tree collected
every time is the same fixed deterministic MDP (with different rewards);
furthermore, one can always execute line 7 and line 10 for a deterministic MDP
since the algorithm can execute a sequence of actions to get to any new
$(s,a)$ pair required by line 10. Thus in every episode of online interaction
we are guaranteed to add the new $(s,a)$ pair to the trajectory tree.

The lower bound trivially extends because the proof of Appendix D.2 uses a
family of MDPs with deterministic transitions (that are even known to the
algorithm beforehand).

##  Appendix E Proofs for Section 5

In this section, we prove Theorem 3, which shows a superpolynomial lower bound
on the sample complexity required to learn bounded spanning capacity classes,
ruling out $\mathrm{poly}(\mathfrak{C}(\Pi),H,\log\lvert\Pi\rvert)$ sample
complexity for online RL. We restate the theorem below with the precise
constants:

######  Theorem 5 (Lower bound for online RL).

Let $h_{0}\in\mathbb{N}$ and $c\in(0,1)$ be universal constants. Fix any
$H\geq h_{0}$. Let $\varepsilon\in(1/2^{cH},1/(100H))$ and
$\ell\in\\{2,\dots,H\\}$ such that $1/\varepsilon^{\ell}\leq 2^{H}$. There
exists a policy class $\Pi^{(\ell)}$ of size $1/(6\varepsilon^{\ell})$ with
$\mathfrak{C}(\Pi^{(\ell)})\leq O(H^{4\ell+2})$ and a family of MDPs
$\mathcal{M}$ with state space $\mathcal{S}$ of size $H\cdot 2^{2H+1}$, binary
action space, horizon $H$ such that: for any $(\varepsilon/16,1/8)$-PAC
algorithm, there exists an $M\in\mathcal{M}$ in which the algorithm has to
collect at least

$\displaystyle\min\left\\{\frac{1}{120\varepsilon^{\ell}},2^{H/3-3}\right\\}\quad\text{online
trajectories in expectation.}$

###  E.1 Construction of State Space, Action Space, and Policy Class

##### State and Action Spaces.

We define the state space $\mathcal{S}$. In every layer $h\in[H]$, there will
be $2^{2H+1}$ states. The states will be paired up, and each state will be
denoted by either $j[h]$ or $j^{\prime}[h]$, so
$\mathcal{S}_{h}=\\{j[h]:j\in[2^{2H}]\\}\cup\\{j^{\prime}[h]:j\in[2^{2H}]\\}$.
For any state $s\in\mathcal{S}$, we define the _index_ of $s$, denoted
$\mathrm{idx}(s)$ as the unique $j\in[2^{2H}]$ such that
$s\in\\{j[h]\\}_{h\in[H]}\cup\\{j^{\prime}[h]\\}_{h\in[H]}$. In total there
are $H\cdot 2^{2H+1}$ states. The action space is $\mathcal{A}=\\{0,1\\}$.

##### Policy Class.

For the given $\varepsilon$ and $\ell\in\\{2,\dots,H\\}$, we show via a
probabilistic argument the existence of a large policy class $\Pi^{(\ell)}$
which has bounded spanning capacity but is hard to explore. We state several
properties in Lemma 2 which will be exploited in the lower bound.

We introduce some additional notation. For any $j\in[2^{2H}]$ we denote

$\displaystyle\Pi^{(\ell)}_{j}\coloneqq\\{\pi\in\Pi^{(\ell)}:\exists
h\in[H],\pi(j[h])=1\\},$

that is, $\Pi^{(\ell)}_{j}$ are the policies which take an action $a=1$ on at
least one state with index $j$.

We also define the set of _relevant state indices_ for a given policy
$\pi\in\Pi^{(\ell)}$ as

$\displaystyle\mathcal{J}_{\mathrm{rel}}^{\pi}\coloneqq\\{j\in[2^{2H}]:\pi\in\Pi^{(\ell)}_{j}\\}.$

For any policy $\pi$ we denote
$\pi(j_{1:H})\coloneqq(\pi(j[1]),\dots,\pi(j[H]))\in\\{0,1\\}^{H}$ to be the
vector that represents the actions that $\pi$ takes on the states in index
$j$. The vector $\pi(j^{\prime}_{1:H})$ is defined similarly.

######  Lemma 2.

Let $H$, $\varepsilon$, and $\ell$ satisfy the assumptions of Theorem 5. There
exists a policy class $\Pi^{(\ell)}$ of size $N=1/(6\varepsilon^{\ell})$ which
satisfies the following properties.

  * (1)

For every $j\in[2^{2H}]$ we have $\lvert\Pi^{(\ell)}_{j}\rvert\in[\varepsilon
N/2,2\varepsilon N]$.

  * (2)

For every $\pi\in\Pi$ we have
$\lvert\mathcal{J}_{\mathrm{rel}}^{\pi}\rvert\geq\varepsilon/2\cdot 2^{2H}$.

  * (3)

For every $\pi\in\Pi^{(\ell)}_{j}$, the vector $\pi(j_{1:H})$ is unique and
always equal to $\pi(j^{\prime}_{1:H})$.

  * (4)

Bounded spanning capacity: $\mathfrak{C}(\Pi^{(\ell)})\leq c\cdot H^{4\ell+2}$
for some universal constant $c>0$.

###  E.2 Construction of MDP Family

The family
$\mathcal{M}=\\{M_{{\pi^{\star}},\phi}\\}_{{\pi^{\star}}\in\Pi^{(\ell)},\phi\in\Phi}$
will be a family of MDPs which are indexed by a policy ${\pi^{\star}}$ as well
as a _decoder_ function
$\phi:\mathcal{S}\mapsto\\{\textsc{good},\textsc{bad}\\}$, which assigns each
state to be “good” or “bad” in a sense that will be described later on. An
example construction of an MDP $M_{{\pi^{\star}},\phi}$ is illustrated in
Figure 1. For brevity, the bracket notation used to denote the layer that each
state lies in has been omitted in the figure.

##### Decoder Function Class.

The decoder function class $\Phi$ will be the set of all possible mappings
which for every $j\in[2^{2H}]$ and $h\geq 2$ assign exactly one of $j[h]$ or
$j^{\prime}[h]$ to the label Good (where the other is assigned to the label
Bad). There are $(2^{H-1})^{2^{2H}}$ such functions. The label of a state will
be used to describe the transition dynamics. Intuitively, a learner who does
not know the decoder function $\phi$ will not be able to tell if a certain
state has the label Good or Bad when visiting that state for the first time.

##### Transition Dynamics.

The MDP $M_{{\pi^{\star}},\phi}$ will be a uniform distribution over $2^{2H}$
combination locks $\\{\mathsf{CL}_{j}\\}_{j\in[2^{2H}]}$ with disjoint states.
More formally, $s_{1}\sim\mathrm{Uniform}(\\{j[1]\\}_{j\in[2^{2H}]})$. From
each start state $j[1]$, only the $2H-2$ states corresponding to index $j$ at
layers $h\geq 2$ will be reachable in the combination lock $\mathsf{CL}_{j}$.

In the following, we will describe each combination lock $\mathsf{CL}_{j}$,
which forms the basic building block of the MDP construction.

  * $\bullet$

Good/Bad Set. At every layer $h\in[H]$, for each $j[h]$ and $j^{\prime}[h]$,
the decoder function $\phi$ assigns one of them to be Good and one of them to
be Bad. We will henceforth denote $j_{g}[h]$ to be the good state and
$j_{b}[h]$ to be the bad state. Observe that by construction in Eq. (9), for
every $\pi\in\Pi^{(\ell)}$ and $h\in[H]$ we have
$\pi(j_{g}[h])=\pi(j_{b}[h])$.

  * $\bullet$

Dynamics of $\mathsf{CL}_{j}$, if
$j\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}$. Here, the transition dynamics
of the combination locks are deterministic. For every $h\in[H]$,

    * –

On good states $j_{g}[h]$ we transit to the next good state iff the action is
${\pi^{\star}}$:

$\displaystyle P(s^{\prime}\leavevmode\nobreak\ |\leavevmode\nobreak\
j_{g}[h],a)$
$\displaystyle=\begin{cases}\mathbbm{1}\left\\{s^{\prime}=j_{g}[h+1]\right\\},&\text{if
}a={\pi^{\star}}(j_{g}[h])\\\
\mathbbm{1}\left\\{s^{\prime}=j_{b}[h+1]\right\\},&\text{if
}a\neq{\pi^{\star}}(j_{g}[h]).\end{cases}$

    * –

On bad states $j_{b}[h]$ we always transit to the next bad state:

$\displaystyle P(s^{\prime}\leavevmode\nobreak\ |\leavevmode\nobreak\
j_{b}[h],a)=\mathbbm{1}\left\\{s^{\prime}=j_{b}[h+1]\right\\},\quad\text{for
all }a\in\mathcal{A}.$

  * $\bullet$

Dynamics of $\mathsf{CL}_{j}$, if
$j\notin\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}$. If $j$ is not a relevant
index for ${\pi^{\star}}$, then the transitions are uniformly random
regardless of the current state/action. For every $h\in[H]$,

$\displaystyle P(\cdot\leavevmode\nobreak\ |\leavevmode\nobreak\
j_{g}[h],a)=P(\cdot\leavevmode\nobreak\ |\leavevmode\nobreak\
j_{b}[h],a)=\mathrm{Uniform}\left(\\{j_{g}[h+1],j_{b}[h+1]\\}\right),\quad\text{for
all }a\in\mathcal{A}.$

  * $\bullet$

Reward Structure. The reward function is nonzero only at layer $H$, and is
defined as

$\displaystyle
R(s,a)=\mathrm{Ber}\left(\frac{1}{2}+\frac{1}{4}\cdot\mathbbm{1}\\{{\pi^{\star}}\in\Pi^{(\ell)}_{j}\\}\cdot\mathbbm{1}\\{s=j_{g}[H],a={\pi^{\star}}(j_{g}[H])\\}\right)$

That is, we get $3/4$ whenever we reach the $H$-th good state for an index $j$
which is relevant for ${\pi^{\star}}$, and $1/2$ reward otherwise.

##### Reference MDPs.

We define several reference MDPs.

  * •

In the reference MDP $M_{0}$, the initial start state is again taken to be the
uniform distribution, i.e.,
$s_{1}\sim\mathrm{Uniform}(\\{j[1]\\}_{j\in[2^{2H}]})$, and all the
combination locks behave the same and have uniform transitions to the next
state along the chain: for every $h\in[H]$ and $j\in[2^{2H}]$,

$\displaystyle P(\cdot\leavevmode\nobreak\ |\leavevmode\nobreak\
j[h],a)=P(\cdot\leavevmode\nobreak\ |\leavevmode\nobreak\
j^{\prime}[h],a)=\mathrm{Uniform}\left(\\{j[h+1],j^{\prime}[h+1]\\}\right),\quad\text{for
all }a\in\mathcal{A}.$

The rewards for $M_{0}$ are $\mathrm{Ber}(1/2)$ for every
$(s,a)\in\mathcal{S}_{H}\times\mathcal{A}$.

  * •

For any decoder $\phi\in\Phi$, the reference MDP $M_{0,{\pi^{\star}},\phi}$
has the same transitions as $M_{{\pi^{\star}},\phi}$ but the rewards are
$\mathrm{Ber}(1/2)$ for every $(s,a)\in\mathcal{S}_{H}\times\mathcal{A}$.

###  E.3 Proof of Theorem 5

We are now ready to prove the lower bound using the construction of the MDP
family $\mathcal{M}$.

##### Value Calculation.

Consider any $M_{{\pi^{\star}},\phi}\in\mathcal{M}$. For any policy
$\pi\in\mathcal{A}^{\mathcal{S}}$ we use $V_{{\pi^{\star}},\phi}(\pi)$ to
denote the value of running $\pi$ in MDP $M_{{\pi^{\star}},\phi}$. By
construction we can see that

$\displaystyle
V_{{\pi^{\star}},\phi}(\pi)=\frac{1}{2}+\frac{1}{4}\cdot\operatorname{\mathbb{P}}_{{\pi^{\star}},\phi}\left[\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\text{
and
}\pi(\mathrm{idx}(s_{1})_{1:H})={\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\right],$
(6)

where in the above, we defined for any $s_{1}$,
$\pi(\mathrm{idx}(s_{1})_{1:H})\ =\pi(j_{1:H})=(\pi(j[1]),\dots,\pi(j[H]))$,
where $j$ denotes $\mathrm{idx}(s_{1})$. Informally speaking, the second term
counts the additional reward that $\pi$ gets for solving a combination lock
rooted at a relevant state index
$\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}$. By Property
(2) and (3) of Lemma 2, we additionally have
$V_{{\pi^{\star}},\phi}({\pi^{\star}})\geq 1/2+\varepsilon/8$, as well as
$V_{{\pi^{\star}},\phi}(\pi)=1/2$ for all other
$\pi\neq{\pi^{\star}}\in\Pi^{(\ell)}$.

By Eq. (6), if $\pi$ is an $\varepsilon/16$-optimal policy on
$M_{{\pi^{\star}},\phi}$ it must satisfy

$\displaystyle\operatorname{\mathbb{P}}_{{\pi^{\star}},\phi}\left[\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\text{
and
}\pi(\mathrm{idx}(s_{1})_{1:H})={\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\right]\geq\frac{\varepsilon}{4}.$

##### Averaged Measures.

We define the following measures which will be used in the analysis.

  * •

Define
$\operatorname{\mathbb{P}}_{\pi^{\star}}[\cdot]=\frac{1}{\lvert\Phi\rvert}\sum_{\phi\in\Phi}\operatorname{\mathbb{P}}_{{\pi^{\star}},\phi}[\cdot]$
to be the averaged measure where we first pick $\phi$ uniformly among all
decoders and then consider the distribution induced by
$M_{{\pi^{\star}},\phi}$.

  * •

Define the averaged measure
$\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}[\cdot]=\frac{1}{\lvert\Phi\rvert}\sum_{\phi\in\Phi}\operatorname{\mathbb{P}}_{0,{\pi^{\star}},\phi}[\cdot]$
where we pick $\phi$ uniformly and then consider the distribution induced by
$M_{0,{\pi^{\star}},\phi}$.

For both averaged measures the expectations $\mathbb{E}_{{\pi^{\star}}}$ and
$\mathbb{E}_{0,{\pi^{\star}}}$ are defined analogously.

##### Algorithm and Stopping Time.

Recall that an algorithm $\mathbb{A}$ is comprised of two phases. In the first
phase, it collects some number of trajectories by interacting with the MDP in
episodes. We use $\eta$ to denote the (random) number of episodes after which
$\mathbb{A}$ terminates. We also use $\mathbb{A}_{t}$ to denote the
intermediate policy that the algorithm runs in round $t$ for $t\in[\eta]$. In
the second phase, $\mathbb{A}$ outputs666We present the lower bound for the
class of deterministic algorithms that output a deterministic policy. However,
all the arguments could be extended to stochastic algorithms. a policy
${\widehat{\pi}}$. We use the notation
$\mathbb{A}_{f}:\\{\tau^{(t)}\\}_{t\in[\eta]}\mapsto\mathcal{A}^{\mathcal{S}}$
to denote the second phase of $\mathbb{A}$ which outputs ${\widehat{\pi}}$ as
a measurable function of collected data.

For any policy ${\pi^{\star}}$, decoder $\phi$, and dataset $\mathcal{D}$ we
define the event

$\displaystyle\mathcal{E}({\pi^{\star}},\phi,\mathbb{A}_{f}(\mathcal{D})):=\left\\{\operatorname{\mathbb{P}}_{{\pi^{\star}},\phi}\left[\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\
\mathbb{A}_{f}(\mathcal{D})(\mathrm{idx}(s_{1})_{1:H})={\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\right]\geq\frac{\varepsilon}{4}\right\\}.$

The event $\mathcal{E}({\pi^{\star}},\phi,\mathbb{A}_{f}(\mathcal{D}))$ is
measurable with respect to the random variable $\mathcal{D}$, which denotes
the collected data.

Under this notation, the PAC learning guarantee on $\mathbb{A}$ implies that
for every ${\pi^{\star}}\in\Pi^{(\ell)}$, $\phi\in\Phi$ we have

$\displaystyle\operatorname{\mathbb{P}}_{{\pi^{\star}},\phi}\left[\mathcal{E}({\pi^{\star}},\phi,\mathbb{A}_{f}(\mathcal{D}))\right]\geq
7/8.$

Moreover via an averaging argument we also have

$\displaystyle\operatorname{\mathbb{P}}_{{\pi^{\star}}}\left[\mathcal{E}({\pi^{\star}},\phi,\mathbb{A}_{f}(\mathcal{D}))\right]\geq
7/8.$ (7)

##### Lower Bound Argument.

We apply a truncation to the stopping time $\eta$. Define
${T_{\mathrm{max}}}:=2^{H/3}$. Observe that if
$\operatorname{\mathbb{P}}_{\pi^{\star}}[\eta>{T_{\mathrm{max}}}]>1/8$ for
some ${\pi^{\star}}\in\Pi^{(\ell)}$ then the lower bound immediately follows,
since

$\displaystyle\max_{\phi\in\Phi}\mathbb{E}_{{\pi^{\star}},\phi}[\eta]\leavevmode\nobreak\
>\leavevmode\nobreak\ \mathbb{E}_{{\pi^{\star}}}[\eta]\leavevmode\nobreak\
\geq\leavevmode\nobreak\
\operatorname{\mathbb{P}}_{{\pi^{\star}}}[\eta>{T_{\mathrm{max}}}]\cdot{T_{\mathrm{max}}}\leavevmode\nobreak\
\geq\leavevmode\nobreak\ {T_{\mathrm{max}}}/8,$

so there must exist an MDP $M_{{\pi^{\star}},\phi}$ for which $\mathbb{A}$
collects at least ${T_{\mathrm{max}}}/8=2^{H/3-3}$ samples in expectation.

Otherwise we have
$\operatorname{\mathbb{P}}_{\pi^{\star}}[\eta>{T_{\mathrm{max}}}]\leq 1/8$ for
all ${\pi^{\star}}\in\Pi^{(\ell)}$. This further implies that for all
${\pi^{\star}}\in\Pi^{(\ell)}$,

$\displaystyle\operatorname{\mathbb{P}}_{\pi^{\star}}\left[\eta<{T_{\mathrm{max}}}\text{
and }\mathcal{E}({\pi^{\star}},\phi,\mathbb{A}_{f}(\mathcal{D}))\right]$
$\displaystyle=\operatorname{\mathbb{P}}_{\pi^{\star}}\left[\mathcal{E}({\pi^{\star}},\phi,\mathbb{A}_{f}(\mathcal{D}))\right]-\operatorname{\mathbb{P}}_{\pi^{\star}}\left[\eta>{T_{\mathrm{max}}}\text{
and }\mathcal{E}({\pi^{\star}},\phi,\mathbb{A}_{f}(\mathcal{D}))\right]\geq
3/4.$ (8)

However, in the following, we will argue that if Eq. (8) holds then
$\mathbb{A}$ must query a significant number of samples in $M_{0}$.

######  Lemma 3 (Stopping Time Lemma).

Let $\delta\in(0,1/8]$. Let $\mathbb{A}$ be an $(\varepsilon/16,\delta)$-PAC
algorithm. Let ${T_{\mathrm{max}}}\in\mathbb{N}$. Suppose that
$\operatorname{\mathbb{P}}_{\pi^{\star}}\left[\eta<{T_{\mathrm{max}}}\text{
and }\mathcal{E}({\pi^{\star}},\phi,\mathbb{A}_{f}(\mathcal{D}))\right]\geq
1-2\delta$ for all ${\pi^{\star}}\in\Pi^{(\ell)}$. The expected stopping time
for $\mathbb{A}$ on $M_{0}$ is at least

$\displaystyle\mathbb{E}_{0}\left[\eta\right]\geq\left(\frac{\lvert\Pi^{(\ell)}\rvert}{2}-\frac{4}{\varepsilon}\right)\cdot\frac{1}{7}\log\left(\frac{1}{2\delta}\right)-\lvert\Pi^{(\ell)}\rvert\cdot\frac{{T_{\mathrm{max}}}^{2}}{2^{H+3}}\left({T_{\mathrm{max}}}+\frac{1}{7}\log\left(\frac{1}{2\delta}\right)\right).$

Using Lemma 3 with $\delta=1/8$ and plugging in the value of
$\lvert\Pi^{(\ell)}\rvert$ and ${T_{\mathrm{max}}}$, we see that

$\displaystyle\mathbb{E}_{0}[\eta]$
$\displaystyle\geq\left(\frac{\lvert\Pi^{(\ell)}\rvert}{2}-\frac{4}{\varepsilon}\right)\cdot\frac{1}{7}\log\left(\frac{1}{2\delta}\right)-\lvert\Pi^{(\ell)}\rvert\cdot\frac{{T_{\mathrm{max}}}^{2}}{2^{H+3}}\left({T_{\mathrm{max}}}+\frac{1}{7}\log\left(\frac{1}{2\delta}\right)\right)\geq\frac{\lvert\Pi^{(\ell)}\rvert}{20}.$

For the second inequality, we used the fact that $\ell\geq 2$, $H\geq 10^{5}$,
and $\varepsilon<1/10^{7}$.

We have shown that either there exists some MDP $M_{{\pi^{\star}},\phi}$ for
which $\mathbb{A}$ collects at least ${T_{\mathrm{max}}}/8=2^{H/3-3}$ samples
in expectation, or $\mathbb{A}$ must query at least
$\lvert\Pi^{(\ell)}\rvert/20=1/(120\varepsilon^{\ell})$ trajectories in
expectation in $M_{0}$. Putting it all together, the lower bound on the sample
complexity is at least

$\displaystyle\min\left\\{\frac{1}{120\varepsilon^{\ell}},2^{H/3-3}\right\\}.$

This concludes the proof of Theorem 5.∎

###  E.4 Proof of Lemma 2

To prove Lemma 2, we first use a probabilistic argument to construct a certain
binary matrix $B$ which satisfies several properties, and then construct
$\Pi^{(\ell)}$ using $B$ and verify it satisfies Properties (1)-(4).

##### Binary Matrix Construction.

First, we define a block-free property of binary matrices.

######  Definition 5 (Block-free Matrices).

Fix parameters $k,\ell,N,d\in\mathbb{N}$ where $k\leq N$ and $l\leq d$. We say
a binary matrix $B\in\\{0,1\\}^{N\times d}$ is $(k,\ell)$-block-free if the
following holds: for every $I\subseteq[N]$ with $\lvert I\rvert=k$, and
$J\subseteq[d]$ with $\lvert J\rvert=\ell$ there exists some $(i,j)\in I\times
J$ with $B_{ij}=0$.

In words, matrices which are $(k,\ell)$-block-free do not contain a
$k\times\ell$ block of all 1s.

######  Lemma 4.

Fix any $\varepsilon\in(0,1/10)$ and $\ell\in\mathbb{N}$. For any

$\displaystyle
d\in\Big{[}\frac{16\ell\cdot\log(1/\varepsilon)}{\varepsilon},\frac{1}{20}\cdot\exp\Big{(}\frac{1}{48\varepsilon^{\ell-1}}\Big{)}\Big{]},$

there exists a binary matrix $B\in\\{0,1\\}^{N\times d}$ with
$N=1/(6\cdot\varepsilon^{\ell})$ such that:

  1. $(1)$

(Row sum): for every row $i\in[N]$, we have $\sum_{j}B_{ij}\geq\varepsilon
d/2$.

  2. $(2)$

(Column sum): for every column $j\in[d]$, we have
$\sum_{i}B_{ij}\in[\varepsilon N/2,2\varepsilon N]$.

  3. $(3)$

The matrix $B$ is $(\ell\log d,\ell)$-block-free.

###### Proof of Lemma 4..

The existence of $B$ is proven using the probabilistic method. Let
$\widetilde{B}\in\\{0,1\\}^{N\times d}$ be a random matrix where each entry is
i.i.d. chosen to be 1 with probability $\varepsilon$.

By Chernoff bounds (Lemma 18), for every row $i\in[N]$, we have
$\operatorname{\mathbb{P}}[\sum_{j}B_{ij}\leq\tfrac{\varepsilon
d}{2}]\leq\exp(-\varepsilon d/8)$; likewise for every column $j\in[d]$, we
have $\operatorname{\mathbb{P}}[\sum_{j}B_{ij}\notin[\tfrac{\varepsilon
N}{2},2\varepsilon N]]\leq 2\exp(-\varepsilon N/8)$. By union bound, the
matrix $\widetilde{B}$ satisfies the first two properties with probability at
least $0.8$ as long as

$\displaystyle d\geq(8\log 10N)/\varepsilon,\quad\text{and}\quad N\geq(8\log
20d)/\varepsilon.$

One can check that under the choice of $N=1/(6\cdot\varepsilon^{\ell})$ and
the assumption on $d$, both constraints are met.

Now we examine the probability of $\widetilde{B}$ satisfies the block-free
property with parameters $(k\coloneqq\ell\log d,\ell)$. Let $X$ be the random
variable which denotes the number of submatrices which violate the block-free
property in $\widetilde{B}$, i.e.,

$\displaystyle X=\lvert\\{I\times J:I\subset[N],\lvert
I\rvert=k,J\subset[d],\lvert J\rvert=\ell,\widetilde{B}_{ij}=1\ \forall\
(i,j)\in I\times J\\}\rvert.$

By linearity of expectation, we have

$\displaystyle\mathbb{E}[X]\leq N^{k}d^{\ell}\varepsilon^{k\ell}.$

We now plug in the choice $k=\ell\log d$ and observe that as long as $N\leq
1/(2e\cdot\varepsilon^{\ell})$ we have $\mathbb{E}[X]\leq 1/2$. By Markov’s
inequality, $\operatorname{\mathbb{P}}[X=0]\geq 1/2$.

Therefore with positive probability, $\widetilde{B}$ satisfies all 3
properties (otherwise we would have a contradiction via inclusion-exlusion
principle). Thus, there exists a matrix $B$ which satisfies all of the above
three properties, proving the result of Lemma 4. ∎

##### Policy Class Construction.

For the given $\varepsilon$ and $\ell\in\\{2,\dots,H\\}$ we will use Lemma 4
to construct a policy class $\Pi^{(\ell)}$ which has bounded spanning capacity
but is hard to explore. We instantiate Lemma 4 with the given $\ell$ and
$d=2^{2H}$, and use the resulting matrix $B$ to construct
$\Pi^{(\ell)}=\\{\pi_{i}\\}_{i\in[N]}$ with
$\lvert\Pi^{(\ell)}\rvert=N=1/(6\varepsilon^{\ell})$.

Recall that we assume that

$\displaystyle H\geq
h_{0},\quad\text{and}\quad\varepsilon\in\left[\frac{1}{2^{cH}},\frac{1}{100H}\right].$

We claim that under these assumptions, the requirement of Lemma 4 is met:

$\displaystyle
d=2^{2H}\in\left[\frac{16\ell\cdot\log(1/\varepsilon)}{\varepsilon},\frac{1}{20}\cdot\exp\left(\frac{1}{48\varepsilon^{\ell-1}}\right)\right].$

For the lower bound, we can check that:

$\displaystyle\frac{16\ell\cdot\log(1/\varepsilon)}{\varepsilon}\leq 16H\cdot
cH\cdot 2^{cH}\leq 2^{2H},$

where we use the bound $\ell\leq H$ and $\varepsilon\geq 2^{-cH}$. The last
inequality holds for sufficiently small universal constant $c\in(0,1)$ and
sufficiently large $H\geq h_{0}$.

For the upper bound, we can also check that

$\displaystyle\frac{1}{20}\cdot\exp\left(\frac{1}{48\varepsilon^{\ell-1}}\right)\geq\frac{1}{20}\cdot\exp\left(\frac{100H}{48}\right)\geq
2^{2H},$

where we use the bound $\ell\geq 2$ and $\varepsilon\leq 1/(100H)$. The last
inequality holds for sufficiently large $H$. We define the policies as
follows: for every $\pi_{i}\in\Pi^{(\ell)}$ we set

$\displaystyle\text{for every }j\in[2^{2H}]:\quad$
$\displaystyle\pi_{i}(j[h])=\pi_{i}(j^{\prime}[h])=\begin{cases}\mathrm{bit}_{h}(\sum_{a\leq
i}B_{aj})&\text{if}\ B_{ij}=1,\\\ 0&\text{if}\ B_{ij}=0.\end{cases}$ (9)

The function $\mathrm{bit}_{h}:[2^{H}-1]\mapsto\\{0,1\\}$ selects the $h$-th
bit in the binary representation of the input.

##### Verifying Properties $(1)-(4)$ of Lemma 2.

Properties $(1)-(3)$ are straightforward from the construction of $B$ and
$\Pi^{(\ell)}$, since $\pi_{i}\in\Pi^{(\ell)}_{j}$ if and only if $B_{ij}=1$.
The only detail which requires some care is that we require that $2\varepsilon
N<2^{H}$ in order for Property (3) to hold, since otherwise we cannot assign
the behaviors of the policies according to Eq. (9). However, by assumption,
this always holds, since $2\varepsilon N=1/(3\varepsilon^{\ell-1})\leq 2^{H}.$

We now prove Property (4) that $\Pi^{(\ell)}$ has bounded spanning capacity.
To prove this we will use the block-free property of the underlying binary
matrix $B$.

Fix any deterministic MDP $M^{\star}$ which witnesses
$\mathfrak{C}(\Pi^{(\ell)})$ at layer $h^{\star}$. To bound
$\mathfrak{C}(\Pi^{(\ell)})$, we need to count the contribution to
$C^{\mathsf{reach}}_{h^{\star}}(\Pi;M^{\star})$ from trajectories $\tau$ which
are produced by some $\pi\in\Pi^{(\ell)}$ on $M$. We first define a _layer
decomposition_ for a trajectory
$\tau=(s_{1},a_{1},s_{2},a_{2},\dots,s_{H},a_{H})$ as the unique tuple of
indices $(h_{1},h_{2},\dots h_{m})$, where each $h_{k}\in[H]$, that satisfies
the following properties:

  * $\bullet$

The layers satisfy $h_{1}<h_{2}<\dots<h_{m}$.

  * $\bullet$

The layer $h_{1}$ represents the first layer where $a_{h_{1}}=1$.

  * $\bullet$

The layer $h_{2}$ represents the first layer where $a_{h_{2}}=1$ on some state
$s_{h_{2}}$ such that

$\displaystyle\mathrm{idx}(s_{h_{2}})\notin\\{\mathrm{idx}(s_{h_{1}})\\}.$

  * $\bullet$

The layer $h_{3}$ represents the first layer where $a_{h_{3}}=1$ on some state
$s_{h_{3}}$ such that

$\displaystyle\mathrm{idx}(s_{h_{3}})\notin\\{\mathrm{idx}(s_{h_{1}}),\mathrm{idx}(s_{h_{2}})\\}.$

  * $\bullet$

More generally the layer $h_{k}$, $k\in[m]$ represents the first layer where
$a_{h_{k}}=1$ on some state $s_{h_{k}}$ such that

$\displaystyle\mathrm{idx}(s_{h_{k}})\notin\\{\mathrm{idx}(s_{h_{1}}),\dots,\mathrm{idx}(s_{h_{k-1}})\\}.$

In other words, the layer $h_{k}$ represents the $k$-th layer for where action
is $a=1$ on a new state index which $\tau$ has never played $a=1$ on before.

We will count the contribution to
$C^{\mathsf{reach}}_{h^{\star}}(\Pi;M^{\star})$ by doing casework on the
length of the layer decomposition for any $\tau$. That is, for every length
$m\in\\{0,\dots,H\\}$, we will bound $C_{h^{\star}}(m)$, which is defined to
be the total number of $(s,a)$ at layer $h^{\star}$ which, for some
$\pi\in\Pi^{(\ell)}$, a trajectory $\pi\rightsquigarrow\tau$ that has a
$m$-length layer decomposition visits. Then we apply the bound

$\displaystyle
C^{\mathsf{reach}}_{h^{\star}}(\Pi;M^{\star})\leq\sum_{m=0}^{H}C_{h^{\star}}(m).$
(10)

Note that this will overcount, since the same $(s,a)$ pair can belong to
multiple different trajectories with different length layer decompositions.

######  Lemma 5.

The following bounds hold:

  * $\bullet$

For any $m\leq\ell$, $C_{h^{\star}}(m)\leq
H^{m}\cdot\prod_{k=1}^{m}(2kH)=\mathcal{O}(H^{4m})$.

  * $\bullet$

We have $\sum_{m\geq\ell+1}C_{h^{\star}}(m)\leq\mathcal{O}(\ell\cdot
H^{4\ell+1})$.

Therefore, applying Lemma 5 to Eq. (10), we have the bound that

$\displaystyle\mathfrak{C}(\Pi^{(\ell)})\leq\left(\sum_{m\leq\ell}O(H^{4m})\right)+O(\ell\cdot
H^{4\ell+1})\leq O(H^{4\ell+2}).$

This concludes the proof of Lemma 2.∎

###### Proof of Lemma 5.

All of our upper bounds will be monotone in the value of $h^{\star}$, so we
will prove the bounds for $C_{H}(m)$. In the following, fix any deterministic
MDP $M^{\star}$.

First we start with the case where $m=0$. The trajectory $\tau$ must play
$a=0$ at all times; since there is only one such $\tau$, we have $C_{H}(0)=1$.

Now we will bound $C_{H}(m)$, for any $m\in\\{1,\dots,\ell\\}$. Observe that
there are ${H\choose m}\leq H^{m}$ ways to pick the tuple
$(h_{1},\dots,h_{m})$. Now we will fix $(h_{1},\dots,h_{m})$ and count the
contributions to $C_{H}(m)$ for trajectories $\tau$ which have this fixed
layer decomposition, and then sum up over all possible choices of
$(h_{1},\dots,h_{m})$.

In the MDP $M^{\star}$, there is a unique state $s_{h_{1}}$ which $\tau$ must
visit. In the layers between $h_{1}$ and $h_{2}$, all trajectories are only
allowed take $1$ on states with index $\mathrm{idx}(s_{h_{1}})$, but they are
not required to. Thus we can compute that the contribution to $C_{h_{2}}(m)$
from trajectories with the fixed layer decomposition to be at most $2H$. The
reasoning is as follows. At $h_{1}$, there is exactly one $(s,a)$ pair which
is reachable by trajectories with this fixed layer decomposition, since any
$\tau$ must take $a=1$ at $s_{h_{1}}$. Subsequently we can add at most two
reachable pairs in every layer $h\in\\{h_{1}+1,\dots,h_{2}-1\\}$ due to
encountering a state $j[h]$ or $j^{\prime}[h]$ where
$j=\mathrm{idx}(s_{h_{1}})$, and at layer $h_{2}$ we must play $a=1$, for a
total of $1+2(h_{2}-h_{1}-1)\leq 2H$. Using similar reasoning the contribution
to $C_{h_{3}}(m)$ from trajectories with this fixed layer decomposition is at
most $(2H)\cdot(4H)$, and so on. Continuing in this way, we have the final
bound of $\prod_{k=1}^{m}(2kH)$. Since this holds for a fixed choice of
$(h_{1},\dots,h_{m})$ in total we have $C_{H}(m)\leq
H^{m}\cdot\prod_{k=1}^{m}(2kH)=\mathcal{O}(H^{4m})$.

When $m\geq\ell+1$, observe that the block-free property on $B$ implies that
for any $J\subseteq[2^{H}]$ with $\lvert J\rvert=\ell$ we have
$\lvert\cap_{j\in J}\Pi_{j}\rvert\leq\ell\log 2^{2H}$. So for any trajectory
$\tau$ with layer decomposition such that $m\geq\ell$ we can redo the previous
analysis and argue that there is at most $\ell\log 2^{2H}$ multiplicative
factor contribution to the value $C_{H}(m)$ due to _all_ trajectories which
have layer decompositions longer than $\ell$. Thus we arrive at the bound
$\sum_{m\geq\ell+1}C_{H}(m)\leq\mathcal{O}(H^{4\ell})\cdot\ell\log
2^{2H}\leq\mathcal{O}(\ell\cdot H^{4\ell+1})$. ∎

###  E.5 Proof of Lemma 3

The proof of this stopping time lemma follows standard machinery for PAC lower
bounds (Garivier et al., 2019; Domingues et al., 2021; Sekhari et al., 2021).
In the following we use $\mathrm{KL}{\left(P\|Q\right)}$ to denote the
Kullback-Leibler divergence between two distributions $P$ and $Q$ and
$\mathrm{kl}{\left(p\|q\right)}$ to denote the Kullback-Leibler divergence
between two Bernoulli distributions with parameters $p,q\in[0,1]$.

For any ${\pi^{\star}}\in\Pi^{(\ell)}$ we denote the random variable

$\displaystyle
N^{\pi^{\star}}=\sum_{t=1}^{\eta\wedge{T_{\mathrm{max}}}}\mathbbm{1}\left\\{\mathbb{A}_{t}(\mathrm{idx}(s_{1})_{1:H})={\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\text{
and }\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\right\\},$

the number of episodes for which the algorithm’s policy at round
$t\in[\eta\wedge{T_{\mathrm{max}}}]$ matches that of ${\pi^{\star}}$ on a
certain relevant state of ${\pi^{\star}}$.

In the sequel we will prove upper and lower bounds on the intermediate
quantity
$\sum_{{\pi^{\star}}\in\Pi}\mathbb{E}_{0}\left[N^{\pi^{\star}}\right]$ and
relate these quantities to $\mathbb{E}_{0}[\eta]$.

##### Step 1: Upper Bound.

First we prove an upper bound. We can compute that

$\displaystyle\sum_{{\pi^{\star}}\in\Pi}\mathbb{E}_{0}\left[N^{\pi^{\star}}\right]$
$\displaystyle=\sum_{t=1}^{T_{\mathrm{max}}}\sum_{{\pi^{\star}}\in\Pi}\mathbb{E}_{0}\left[\mathbbm{1}\left\\{\eta>t-1\right\\}\mathbbm{1}\left\\{\mathbb{A}_{t}(\mathrm{idx}(s_{1})_{1:H})={\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\text{
and
}\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\right\\}\right]$
$\displaystyle=\sum_{t=1}^{T_{\mathrm{max}}}\mathbb{E}_{0}\left[\mathbbm{1}\left\\{\eta>t-1\right\\}\sum_{{\pi^{\star}}\in\Pi}\mathbbm{1}\left\\{\mathbb{A}_{t}(\mathrm{idx}(s_{1})_{1:H})={\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\text{
and
}\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\right\\}\right]$
$\displaystyle\overset{(i)}{\leq{}}\sum_{t=1}^{T_{\mathrm{max}}}\mathbb{E}_{0}\left[\mathbbm{1}\left\\{\eta>t-1\right\\}\right]\leq\mathbb{E}_{0}\left[\eta\wedge{T_{\mathrm{max}}}\right]\leq\mathbb{E}_{0}\left[\eta\right].$
(11)

Here, the first inequality follows because for every index $j$ and every
${\pi^{\star}}\in\Pi^{(\ell)}_{j}$, each ${\pi^{\star}}$ admits a unique
sequence of actions (by Property (3) of Lemma 2), so any policy
$\mathbb{A}_{t}$ can completely match with at most one of the ${\pi^{\star}}$.

##### Step 2: Lower Bound.

Now we turn to the lower bound. We use a change of measure argument.

$\displaystyle\mathbb{E}_{0}\left[N^{\pi^{\star}}\right]$
$\displaystyle\overset{(i)}{\geq{}}\mathbb{E}_{0,{\pi^{\star}}}\left[N^{\pi^{\star}}\right]-{T_{\mathrm{max}}}\Delta({T_{\mathrm{max}}})$
$\displaystyle=\frac{1}{\lvert\Phi\rvert}\sum_{\phi\in\Phi}\mathbb{E}_{0,{\pi^{\star}},\phi}\left[N^{\pi^{\star}}\right]-{T_{\mathrm{max}}}\Delta({T_{\mathrm{max}}})$
$\displaystyle\overset{(ii)}{\geq{}}\frac{1}{7}\cdot\frac{1}{\lvert\Phi\rvert}\sum_{\phi\in\Phi}\mathrm{KL}{\left(\operatorname{\mathbb{P}}_{0,{\pi^{\star}},\phi}^{\mathcal{F}_{\eta\wedge{T_{\mathrm{max}}}}}\|\operatorname{\mathbb{P}}_{{\pi^{\star}},\phi}^{\mathcal{F}_{\eta\wedge{T_{\mathrm{max}}}}}\right)}-{T_{\mathrm{max}}}\Delta({T_{\mathrm{max}}})$
$\displaystyle\overset{(iii)}{\geq{}}\frac{1}{7}\cdot\mathrm{KL}{\left(\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}^{\mathcal{F}_{\eta\wedge{T_{\mathrm{max}}}}}\|\operatorname{\mathbb{P}}_{{\pi^{\star}}}^{\mathcal{F}_{\eta\wedge{T_{\mathrm{max}}}}}\right)}-{T_{\mathrm{max}}}\Delta({T_{\mathrm{max}}})$

The inequality $(i)$ follows from a change of measure argument using Lemma 6,
with $\Delta({T_{\mathrm{max}}})\coloneqq{T_{\mathrm{max}}}^{2}/2^{H+3}$.
Here, $\mathcal{F}_{\eta\wedge{T_{\mathrm{max}}}}$ denotes the natural
filtration generated by the first $\eta\wedge{T_{\mathrm{max}}}$ episodes. The
inequality $(ii)$ follows from Lemma 7, using the fact that
$M_{0,{\pi^{\star}},\phi}$ and $M_{{\pi^{\star}},\phi}$ have identical
transitions and only differ in rewards at layer $H$ for the trajectories which
reach the end of a relevant combination lock. The number of times this occurs
is exactly $N^{\pi^{\star}}$. The factor $1/7$ is a lower bound on
$\mathrm{kl}{\left(1/2\|3/4\right)}$. The inequality $(iii)$ follows by the
convexity of KL divergence.

Now we apply Lemma 8 to lower bound the expectation for any
$\mathcal{F}_{\eta\wedge{T_{\mathrm{max}}}}$-measurable random variable
$Z\in[0,1]$ as

$\displaystyle\mathbb{E}_{0}\left[N^{\pi^{\star}}\right]$
$\displaystyle\geq\frac{1}{7}\cdot\mathrm{kl}{\left(\mathbb{E}_{0,{\pi^{\star}}}\left[Z\right]\|\mathbb{E}_{{\pi^{\star}}}\left[Z\right]\right)}-{T_{\mathrm{max}}}\Delta({T_{\mathrm{max}}})$
$\displaystyle\geq\frac{1}{7}\cdot(1-\mathbb{E}_{0,{\pi^{\star}}}\left[Z\right])\log\left(\frac{1}{1-\mathbb{E}_{{\pi^{\star}}}\left[Z\right]}\right)-\frac{\log(2)}{7}-{T_{\mathrm{max}}}\Delta({T_{\mathrm{max}}}),$

where the second inequality follows from the bound
$\mathrm{kl}{\left(p\|q\right)}\geq(1-p)\log(1/(1-q))-\log(2)$ (see, e.g.,
Domingues et al., 2021, Lemma 15).

Now we pick
$Z=Z_{\pi^{\star}}\coloneqq\mathbbm{1}\left\\{\eta<{T_{\mathrm{max}}}\text{
and }\mathcal{E}({\pi^{\star}},\phi,\mathbb{A}_{f}(\mathcal{D}))\right\\}$ and
note that $\mathbb{E}_{{\pi^{\star}}}[Z_{\pi^{\star}}]\geq 1-2\delta$ by
assumption. This implies that

$\displaystyle\mathbb{E}_{0}\left[N^{\pi^{\star}}\right]$
$\displaystyle\geq(1-\mathbb{E}_{0,{\pi^{\star}}}\left[Z_{\pi^{\star}}\right])\cdot\frac{1}{7}\log\left(\frac{1}{2\delta}\right)-\frac{\log(2)}{7}-{T_{\mathrm{max}}}\Delta({T_{\mathrm{max}}}).$

Another application of Lemma 6 gives

$\displaystyle\mathbb{E}_{0}\left[N^{\pi^{\star}}\right]$
$\displaystyle\geq(1-\mathbb{E}_{0}\left[Z_{\pi^{\star}}\right])\cdot\frac{1}{7}\log\left(\frac{1}{2\delta}\right)-\frac{\log(2)}{7}-\Delta({T_{\mathrm{max}}})\left({T_{\mathrm{max}}}+\frac{1}{7}\log\left(\frac{1}{2\delta}\right)\right).$

Summing the above over ${\pi^{\star}}\in\Pi^{(\ell)}$, we get

$\displaystyle\sum_{{\pi^{\star}}}\mathbb{E}_{0}\left[N^{\pi^{\star}}\right]$
$\displaystyle\geq\left(\lvert\Pi^{(\ell)}\rvert-\sum_{{\pi^{\star}}}\mathbb{E}_{0}\left[Z_{\pi^{\star}}\right]\right)\cdot\frac{1}{7}\log\left(\frac{1}{2\delta}\right)-\lvert\Pi^{(\ell)}\rvert\cdot\frac{\log(2)}{7}-\lvert\Pi^{(\ell)}\rvert\cdot\Delta({T_{\mathrm{max}}})\left({T_{\mathrm{max}}}+\frac{1}{7}\log\left(\frac{1}{2\delta}\right)\right).$
(12)

It remains to prove an upper bound on
$\sum_{{\pi^{\star}}}\mathbb{E}_{0}\left[Z_{\pi^{\star}}\right]$. We calculate
that

$\displaystyle\sum_{{\pi^{\star}}}\mathbb{E}_{0}\left[Z_{\pi^{\star}}\right]$
$\displaystyle=\sum_{{\pi^{\star}}}\mathbb{E}_{0}\left[\mathbbm{1}\left\\{\eta<{T_{\mathrm{max}}}\text{
and
}\mathcal{E}({\pi^{\star}},\phi,\mathbb{A}_{f}(\mathcal{D}))\right\\}\right]$
$\displaystyle\leq\sum_{{\pi^{\star}}}\mathbb{E}_{0}\left[\mathbbm{1}\left\\{\operatorname{\mathbb{P}}_{\pi^{\star}}\left[\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\text{
and
}\mathbb{A}_{f}(\mathcal{D})(\mathrm{idx}(s_{1})_{1:H})={\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\right]\geq\frac{\varepsilon}{4}\right\\}\right]$
$\displaystyle\leq\frac{4}{\varepsilon}\cdot\mathbb{E}_{0}\left[\sum_{{\pi^{\star}}}\operatorname{\mathbb{P}}_{\pi^{\star}}\left[\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\text{
and
}\mathbb{A}_{f}(\mathcal{D})(\mathrm{idx}(s_{1})_{1:H})={\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\right]\right]$
(13)

The last inequality is an application of Markov’s inequality.

Now we carefully investigate the sum. For any $\phi\in\Phi$, the sum can be
rewritten as

$\displaystyle\sum_{{\pi^{\star}}}\operatorname{\mathbb{P}}_{{\pi^{\star}},\phi}\left[\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\text{
and
}\mathbb{A}_{f}(\mathcal{D})(\mathrm{idx}(s_{1})_{1:H})={\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\right]$
$\displaystyle=\quad$
$\displaystyle\sum_{{\pi^{\star}}}\sum_{s_{1}\in\mathcal{S}_{1}}\operatorname{\mathbb{P}}_{{\pi^{\star}},\phi}\left[s_{1}\right]\operatorname{\mathbb{P}}_{{\pi^{\star}},\phi}\left[\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\text{
and
}\mathbb{A}_{f}(\mathcal{D})(\mathrm{idx}(s_{1})_{1:H})={\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\leavevmode\nobreak\
\mid\leavevmode\nobreak\ s_{1}\right]$ $\displaystyle\overset{(i)}{=}\quad$
$\displaystyle\frac{1}{\lvert\mathcal{S}_{1}\rvert}\sum_{s_{1}\in\mathcal{S}_{1}}\sum_{{\pi^{\star}}}\operatorname{\mathbb{P}}_{{\pi^{\star}},\phi}\left[\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\text{
and
}\mathbb{A}_{f}(\mathcal{D})(\mathrm{idx}(s_{1})_{1:H})={\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\leavevmode\nobreak\
\mid\leavevmode\nobreak\ s_{1}\right]$ $\displaystyle\overset{(ii)}{=}\quad$
$\displaystyle\frac{1}{\lvert\mathcal{S}_{1}\rvert}\sum_{s_{1}\in\mathcal{S}_{1}}\sum_{{\pi^{\star}}}\mathbbm{1}\left\\{\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\text{
and
}\mathbb{A}_{f}(\mathcal{D})(\mathrm{idx}(s_{1})_{1:H})={\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\right\\}.$
(14)

The equality $(i)$ follows because regardless of which MDP $M_{\pi^{\star}}$
we are in, the first state is distributed uniformly over $\mathcal{S}_{1}$.
The equality $(ii)$ follows because once we condition on the first state
$s_{1}$, the probability is either 0 or 1.

Fix any start state $s_{1}$. We can write

$\displaystyle\sum_{{\pi^{\star}}}\mathbbm{1}\left\\{\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\text{
and
}\mathbb{A}_{f}(\mathcal{D})(\mathrm{idx}(s_{1})_{1:H}){\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\right\\}$
$\displaystyle=\sum_{{\pi^{\star}}\in\Pi^{(\ell)}_{\mathrm{idx}(s_{1})}}\mathbbm{1}\left\\{\mathbb{A}_{f}(\mathcal{D})(\mathrm{idx}(s_{1})_{1:H})={\pi^{\star}}(\mathrm{idx}(s_{1})_{1:H})\right\\}=1,$

where the second equality uses the fact that on any index $j$, each
${\pi^{\star}}\in\Pi^{(\ell)}_{j}$ behaves differently (Property (3) of Lemma
2), so $\mathbb{A}_{f}(\mathcal{D})$ can match at most one of these behaviors.
Plugging this back into Eq. (14), averaging over $\phi\in\Phi$, and combining
with Eq. (13), we arrive at the bound

$\displaystyle\sum_{{\pi^{\star}}}\mathbb{E}_{0}\left[Z_{\pi^{\star}}\right]\leq\frac{4}{\varepsilon}.$

We now use this in conjunction with Eq. (12) to arrive at the final lower
bound

$\displaystyle\sum_{{\pi^{\star}}}\mathbb{E}_{0}\left[N^{\pi^{\star}}\right]$
$\displaystyle\geq\left(\lvert\Pi^{(\ell)}\rvert-\frac{4}{\varepsilon}\right)\cdot\frac{1}{7}\log\left(\frac{1}{2\delta}\right)-\lvert\Pi^{(\ell)}\rvert\cdot\frac{\log(2)}{7}-\lvert\Pi^{(\ell)}\rvert\cdot\Delta({T_{\mathrm{max}}})\left({T_{\mathrm{max}}}+\frac{1}{7}\log\left(\frac{1}{2\delta}\right)\right).$
(15)

##### Step 3: Putting it All Together.

Combining Eqs. (11) and (15), plugging in our choice of
$\Delta({T_{\mathrm{max}}})$, and simplifying we get

$\displaystyle\mathbb{E}_{0}\left[\eta\right]$
$\displaystyle\geq\left(\lvert\Pi^{(\ell)}\rvert-\frac{4}{\varepsilon}\right)\cdot\frac{1}{7}\log\left(\frac{1}{2\delta}\right)-\lvert\Pi^{(\ell)}\rvert\cdot\frac{\log(2)}{7}-\lvert\Pi^{(\ell)}\rvert\cdot\Delta({T_{\mathrm{max}}})\left({T_{\mathrm{max}}}+\frac{1}{7}\log\left(\frac{1}{2\delta}\right)\right).$
$\displaystyle\geq\left(\frac{\lvert\Pi^{(\ell)}\rvert}{2}-\frac{4}{\varepsilon}\right)\cdot\frac{1}{7}\log\left(\frac{1}{2\delta}\right)-\lvert\Pi^{(\ell)}\rvert\cdot\frac{{T_{\mathrm{max}}}^{2}}{2^{H+3}}\left({T_{\mathrm{max}}}+\frac{1}{7}\log\left(\frac{1}{2\delta}\right)\right).$

The last inequality follows since $\delta\leq 1/8$ implies
$\log(1/(2\delta))\geq 2\log(2)$.

This concludes the proof of Lemma 3.∎

###  E.6 Change of Measure Lemma

######  Lemma 6.

Let $Z\in[0,1]$ be a $\mathcal{F}_{{T_{\mathrm{max}}}}$-measurable random
variable. Then, for every ${\pi^{\star}}\in\Pi^{(\ell)}$,

$\displaystyle\lvert\mathbb{E}_{0}\left[Z\right]-\mathbb{E}_{0,{\pi^{\star}}}\left[Z\right]\rvert\leq\Delta({T_{\mathrm{max}}}):=\frac{{T_{\mathrm{max}}}^{2}}{2^{H+3}}$

###### Proof.

First, we note that

$\displaystyle\lvert\mathbb{E}_{0}\left[Z\right]-\mathbb{E}_{0,{\pi^{\star}}}\left[Z\right]\rvert\leq\mathrm{TV}\left(\operatorname{\mathbb{P}}_{0}^{\mathcal{F}_{T_{\mathrm{max}}}},\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}^{\mathcal{F}_{T_{\mathrm{max}}}}\right)\leq\sum_{t=1}^{T_{\mathrm{max}}}\mathbb{E}_{0}\left[\mathrm{TV}\left(\operatorname{\mathbb{P}}_{0}[\cdot|\mathcal{F}_{t-1}],\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}[\cdot|\mathcal{F}_{t-1}]\right)\right].$

Here $\operatorname{\mathbb{P}}_{0}[\cdot|\mathcal{F}_{t}]$ denotes the
conditional distribution of the $t$-th trajectory given the first $t-1$
trajectories. Similarly
$\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}[\cdot|\mathcal{F}_{t}]$ is the
averaged over decoders condition distribution of the $t$-th trajectory given
the first $t-1$ trajectories. The second inequality follows by chain rule of
TV distance (see, e.g., Polyanskiy and Wu, 2022, pg. 152).

Now we examine each term
$\mathrm{TV}\left(\operatorname{\mathbb{P}}_{0}[\cdot|\mathcal{F}_{t-1}],\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}[\cdot|\mathcal{F}_{t-1}]\right)$.
Fix a history $\mathcal{F}_{t-1}$ and sequence $s_{1:H}$ where all $s_{i}$
have the same index. We want to bound the quantity

$\displaystyle\left\lvert\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}\left[S_{1:H}^{(t)}=s_{1:H}\leavevmode\nobreak\
\mid\leavevmode\nobreak\
\mathcal{F}_{t-1}\right]-\operatorname{\mathbb{P}}_{0}\left[S_{1:H}^{(t)}=s_{1:H}\leavevmode\nobreak\
\mid\leavevmode\nobreak\ \mathcal{F}_{t-1}\right]\right\rvert,$

where it is understood that the random variable $S_{1:H}^{(t)}$ is drawn
according to the MDP dynamics and algorithm’s policy $\mathbb{A}_{t}$ (which
is in turn a measurable function of $\mathcal{F}_{t-1}$).

We observe that the second term is exactly

$\displaystyle\operatorname{\mathbb{P}}_{0}\left[S_{1:H}^{(t)}=s_{1:H}\leavevmode\nobreak\
\mid\leavevmode\nobreak\
\mathcal{F}_{t-1}\right]=\frac{1}{\lvert\mathcal{S}_{1}\rvert}\cdot\frac{1}{2^{H-1}},$

since the state $s_{1}$ appears with probability
$1/\lvert\mathcal{S}_{1}\rvert$ and the transitions in $M_{0}$ are uniform to
the next state in the combination lock, so each sequence is equally as likely.

For the first term, again the state $s_{1}$ appears with probability
$1/\lvert\mathcal{S}_{1}\rvert$. Suppose that
$\mathrm{idx}(s_{1})\notin\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}$. Then the
dynamics of $\operatorname{\mathbb{P}}_{0,\pi^{\star},\phi}$ for all
$\phi\in\Phi$ are exactly the same as $M_{0}$, so again the probability in
this case is $1/(\lvert\mathcal{S}_{1}\rvert 2^{H-1})$. Now consider when
$\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}$. At some
point $\widehat{h}\in[H+1]$, the policy $\mathbb{A}_{t}$ will deviate from
${\pi^{\star}}$ for the first time (if $\mathbb{A}_{t}$ never deviates from
${\pi^{\star}}$ we set $\widehat{h}=H+1)$. The layer $\widehat{h}$ is only a
function of $s_{1}$ and $\mathbb{A}_{t}$ and does not depend on the MDP
dynamics. The correct decoder must assign
$\phi(s_{1:\widehat{h}-1})=\textsc{Good}$ and
$\phi(s_{\widehat{h}:H})=\textsc{Bad}$, so therefore we have

$\displaystyle\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}\left[S_{1:H}^{(t)}=s_{1:H}\leavevmode\nobreak\
\mid\leavevmode\nobreak\ \mathcal{F}_{t-1}\right]$
$\displaystyle=\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}\left[\phi(s_{1:\widehat{h}-1})=\textsc{Good}\text{
and }\phi(s_{\widehat{h}:H})=\textsc{Bad}\leavevmode\nobreak\
\mid\leavevmode\nobreak\ \mathcal{F}_{t-1}\right]$

If $s_{1}\notin\mathcal{F}_{t-1}$, i.e., we are seeing $s_{1}$ for the first
time, then the conditional distribution over the labels given by $\phi$ is the
same as the unconditioned distribution:

$\displaystyle\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}\left[\phi(s_{1:\widehat{h}-1})=\textsc{Good}\text{
and }\phi(s_{\widehat{h}:H})=\textsc{Bad}\leavevmode\nobreak\
\mid\leavevmode\nobreak\
\mathcal{F}_{t-1}\right]=\frac{1}{\lvert\mathcal{S}_{1}\rvert}\cdot\frac{1}{2^{H-1}}.$

Otherwise, if $s_{1}\in\mathcal{F}_{t-1}$ then we bound the conditional
probability by 1.

$\displaystyle\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}\left[S_{1:H}^{(t)}=s_{1:H}\leavevmode\nobreak\
\mid\leavevmode\nobreak\
\mathcal{F}_{t-1}\right]\leq\frac{1}{\lvert\mathcal{S}_{1}\rvert}.$

Putting this all together we can compute

$\displaystyle\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}\left[S_{1:H}^{(t)}=s_{1:H}\leavevmode\nobreak\
\mid\leavevmode\nobreak\
\mathcal{F}_{t-1}\right]\quad\begin{cases}=\frac{1}{\lvert\mathcal{S}_{1}\rvert}\cdot\frac{1}{2^{H-1}}&\text{if}\quad\mathrm{idx}(s_{1})\notin\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}},\\\\[5.0pt]
=\frac{1}{\lvert\mathcal{S}_{1}\rvert}\cdot\frac{1}{2^{H-1}}&\text{if}\quad\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\text{
and }s_{1}\notin\mathcal{F}_{t-1},\\\\[5.0pt]
\leq\frac{1}{\lvert\mathcal{S}_{1}\rvert}&\text{if}\quad\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}}\text{
and }s_{1}\in\mathcal{F}_{t-1},\\\\[5.0pt] =0&\text{otherwise.}\end{cases}$

Therefore we have the bound

$\displaystyle\left\lvert\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}\left[S_{1:H}^{(t)}=s_{1:H}\leavevmode\nobreak\
\mid\leavevmode\nobreak\
\mathcal{F}_{t-1}\right]-\operatorname{\mathbb{P}}_{0}\left[S_{1:H}^{(t)}=s_{1:H}\leavevmode\nobreak\
\mid\leavevmode\nobreak\ \mathcal{F}_{t-1}\right]\right\rvert$
$\displaystyle\leq\frac{1}{\lvert\mathcal{S}_{1}\rvert}\mathbbm{1}\left\\{\mathrm{idx}(s_{1})\in\mathcal{J}_{\mathrm{rel}}^{\pi^{\star}},s_{1}\in\mathcal{F}_{t-1}\right\\}.$

Summing over all possible sequences $s_{1:H}$ we have

$\displaystyle\mathrm{TV}\left(\operatorname{\mathbb{P}}_{0}[\cdot|\mathcal{F}_{t-1}],\operatorname{\mathbb{P}}_{0,{\pi^{\star}}}[\cdot|\mathcal{F}_{t-1}]\right)$
$\displaystyle\leq\frac{1}{2}\cdot\frac{(t-1)\cdot
2^{H-1}}{\lvert\mathcal{S}_{1}\rvert},$

since the only sequences $s_{1:H}$ for which the difference in the two
measures are nonzero are the ones for which $s_{1}\in\mathcal{F}_{t-1}$, of
which there are $(t-1)\cdot 2^{H-1}$ of them.

Lastly, taking expectations and summing over $t=1$ to ${T_{\mathrm{max}}}$ and
plugging in the value of $\lvert\mathcal{S}_{1}\rvert=2^{2H}$ we have the
final bound. ∎

The next lemma is a straightforward modification of (Domingues et al., 2021,
Lemma 5), with varying rewards instead of varying transitions.

######  Lemma 7.

Let $M$ and $M^{\prime}$ be two MDPs that are identical in transition and
differ in the reward distributions, denote $r_{h}(s,a)$ and
$r^{\prime}_{h}(s,a)$. Assume that for all $(s,a)$ we have $r_{h}(s,a)\ll
r^{\prime}_{h}(s,a)$. Then for any stopping time $\eta$ with respect to
$(\mathcal{F}^{t})_{t\geq 1}$ that satisfies
$\operatorname{\mathbb{P}}_{M}[\eta<\infty]=1$,

$\displaystyle\mathrm{KL}{\left(\operatorname{\mathbb{P}}_{M}^{I_{\eta}}\|\operatorname{\mathbb{P}}_{M^{\prime}}^{I_{\eta}}\right)}=\sum_{s\in\mathcal{S},a\in\mathcal{A},h\in[H]}\mathbb{E}_{M}[N^{\eta}_{s,a,h}]\cdot\mathrm{KL}{\left(r_{h}(s,a)\|r^{\prime}_{h}(s,a)\right)},$

where
$N^{\eta}_{s,a,h}:=\sum_{t=1}^{\eta}\mathbbm{1}\left\\{(S_{h}^{(t)},A_{h}^{(t)})=(s,a)\right\\}$
and $I_{\eta}:\Omega\mapsto\bigcup_{t\geq 1}\mathcal{I}_{t}:\omega\mapsto
I_{\eta(\omega)}(\omega)$ is the random vector representing the history up to
episode $\eta$.

######  Lemma 8 (Lemma 1, Garivier et al. (2019)).

Consider a measurable space $(\Omega,\mathcal{F})$ equipped with two
distributions $\mathbb{P}_{1}$ and $\mathbb{P}_{2}$. For any
$\mathcal{F}$-measurable function $Z:\Omega\mapsto[0,1]$ we have

$\displaystyle\mathrm{KL}{\left(\mathbb{P}_{1}\|\mathbb{P}_{2}\right)}\geq\mathrm{kl}{\left(\mathbb{E}_{1}[Z]\|\mathbb{E}_{2}[Z]\right)}.$

##  Appendix F Proofs for Section 6

###  F.1 Algorithmic Details and Preliminaries

In this subsection, we provide the details of the subroutines that do not
appear in the main body, in Algorithms 3, 4, and 5. The transitions and reward
functions in line 6 in Algorithm 5 are computed using Eqs. (19) and (20),
which are specified below, after introducing additional notation.

Algorithm 3 $\mathsf{DataCollector}$

1:State: $s$, Reacher policy: $\pi_{s}$, Exploration policy set:
$\Pi_{\mathrm{core}}$, Number of samples: $n$.

2:if $s=s_{\top}$ then // Uniform sampling for start state $s_{\top}$

3: for $t=1,\dots,n$ do

4: Sample $\pi^{\prime}\sim\mathrm{Uniform}(\Pi_{\mathrm{core}})$, and run
$\pi^{\prime}$ to collect $\tau=(s_{1},a_{1},\cdots,s_{H},a_{H})$.

5: $\mathcal{D}_{s}\leftarrow\mathcal{D}_{s}\cup\\{\tau\\}$.

6: end for

7:else// $\pi_{s}$-based sampling for all other states $s\neq s_{\top}$

8: Identify the layer $h$ such that $s\in\mathcal{S}_{h}$.

9: for $t=1,\dots,n$ do

10: Run $\pi_{s}$ for the first $h-1$ time steps, and collect trajectory
$(s_{1},a_{1},\cdots,s_{h-1},a_{h-1},s_{h})$.

11: if $s_{h}=s$ then

12: Sample $\pi^{\prime}\sim\mathrm{Uniform}(\Pi_{\mathrm{core}})$, and run
$\pi^{\prime}$ to collect remaining $(s_{h},a_{h},\cdots,s_{H},a_{H})$.

13:
$\mathcal{D}_{s}\leftarrow\mathcal{D}_{s}\cup\\{\tau=(s_{1},a_{1},\cdots,s_{H},a_{H})\\}$.

14: end if

15: end for

16:end if

17:Return dataset $\mathcal{D}_{s}$.

Algorithm 4 $\mathsf{EstReachability}$

1:State space $S^{\mathrm{tab}}$, MRP $\mathfrak{M}$, State
$\bar{s}\in\mathcal{S}^{\mathrm{tab}}$.

2:Let $P$ be the transition of $\mathfrak{M}$.

3:Initialize $V(s)=\mathbbm{1}\left\\{s=\bar{s}\right\\}$ for all $s\in
S^{\mathrm{tab}}$.

4:Repeat $H+1$ times:

5: For all $s\in S^{\mathrm{tab}}$, calculate
$V(s)\leftarrow\sum_{s^{\prime}\in\mathcal{S}^{\mathrm{tab}}}P_{s\to
s^{\prime}}\cdot V(s^{\prime}).$ // Dynamic Programming

6:Return $V(s_{\top})$.

Algorithm 5 $\mathsf{Evaluate}$

1:Policy set $\Pi_{\mathrm{core}}$, Reachable states
$\mathcal{S}^{\mathrm{rch}}$, Datasets
$\\{\mathcal{D}_{s}\\}_{s\in\mathcal{S}^{\mathrm{rch}}}$, Policy $\pi$ to be
evaluated.

2:Compute
$\mathcal{S}_{\pi}^{\mathrm{rch}}\leftarrow\mathcal{S}_{\pi}^{+}\cap\mathcal{S}^{\mathrm{rch}}$
and $S^{\mathrm{tab}}=\mathcal{S}_{\pi}^{\mathrm{rch}}\cup\\{s_{\bot}\\}$.

3:for $s,s^{\prime}$ in $S^{\mathrm{tab}}$ do // Compute transitions and
rewards on $S^{\mathrm{tab}}$

4: Let $h,h^{\prime}$ be such that $s\in\mathcal{S}_{h}$ and
$s^{\prime}\in\mathcal{S}_{h^{\prime}}$

5: if $h<h^{\prime}$ then

6: Calculate $\widehat{P}_{s\to s^{\prime}}^{\pi},\widehat{r}_{s\to
s^{\prime}}^{\pi}$ according to (19) and (20);

7: else

8: Set $\widehat{P}_{s\to s^{\prime}}^{\pi}\leftarrow 0$, $\widehat{r}_{s\to
s^{\prime}}^{\pi}\leftarrow 0$.

9: end if

10:end for

11:Set $\widehat{V}(s)=0$ for all $s\in S^{\mathrm{tab}}$.

12:Repeat for $H+1$ times: // Evaluate $\pi$ by dynamic programming

13: For all $s\in S^{\mathrm{tab}}$, calculate
$\widehat{V}(s)\leftarrow\sum_{S^{\mathrm{tab}}}\widehat{P}_{s\to
s^{\prime}}^{\pi}\cdot\left(\widehat{r}_{s\to
s^{\prime}}^{\pi}+\widehat{V}(s^{\prime})\right).$

14:Return $\widehat{V}(s_{\top})$.

We recall the definition of petals and sunflowers given in the main body (in
Definitions 3 and 4). In the rest of this section, we assume that $\Pi$ is a
$(K,D)$-sunflower with $\Pi_{\mathrm{core}}$ and $\mathcal{S}_{\pi}$ for any
$\pi\in\Pi$.

######  Definition 6 (Petals and Sunflowers (Definitions 3 and 4 in the main
body)).

For a policy set $\bar{\Pi}$, and states
$\bar{\mathcal{S}}\subseteq\mathcal{S}$, a policy $\pi$ is said to be a
$\bar{\mathcal{S}}$-petal on $\bar{\Pi}$ if for all $h\leq h^{\prime}\leq H$,
and partial trajectories
$\tau=(s_{h},a_{h},\cdots,s_{h^{\prime}},a_{h^{\prime}})$ that are consistent
with $\pi$: either $\tau$ is also consistent with some
$\pi^{\prime}\in\bar{\Pi}$, or there exists $i\in(h,h^{\prime}]$ s.t.
$s_{i}\in\bar{\mathcal{S}}$.

A policy class $\Pi$ is said to be a $(K,D)$-sunflower if there exists a set
$\Pi_{\mathrm{core}}$ of Markovian policies with $|\Pi_{\mathrm{core}}|\leq K$
such that for every policy $\pi\in\Pi$ there exists a set
$\mathcal{S}_{\pi}\subseteq\mathcal{S}$, of size at most $D$, so that $\pi$ is
an $S_{\pi}$-petal on $\Pi_{\mathrm{core}}$.

##### Additional notation.

Recall that we assumed that the state space
$\mathcal{S}=\mathcal{S}_{1}\times\dots\mathcal{S}_{H}$ is layered. Thus,
given a state $s$, we can infer the layer $h$ such that $s\in\mathcal{S}_{h}$.
By definition $s_{\top}$ belongs to the layer $h=0$ and $s_{\bot}$ belongs to
the layer $h=H$. In the following, we define additional notation:

  1. $(a)$

Sets $\mathfrak{T}(s\rightarrow s^{\prime};\neg\bar{}\mathcal{S})$: For any
set $\bar{}\mathcal{S}$, and states $s,s^{\prime}\in\mathcal{S}$, we define
$\mathfrak{T}(s\rightarrow s^{\prime};\neg\bar{}\mathcal{S})$ as the set of
all the trajectories that go from $s$ to $s^{\prime}$ without passing through
any state in $\bar{}\mathcal{S}$ in between.

More formally, let state $s$ be at layer $h$, and $s^{\prime}$ be at layer
$h^{\prime}$. Then, $\mathfrak{T}(s\rightarrow
s^{\prime};\neg\bar{}\mathcal{S})$ denotes the set of all the trajectories
$\tau=(s_{1},a_{1},\cdots,s_{H},a_{H})$ that satisfy all of the following:

    1. $\bullet$

$s_{h}=s$, where $s_{h}$ is the state at timestep $h$ in $\tau$.

    2. $\bullet$

$s_{h^{\prime}}=s^{\prime}$, where $s_{h^{\prime}}$ is the state at timestep
$h^{\prime}$ in $\tau$.

    3. $\bullet$

For all $h<\widetilde{h}<h^{\prime}$, the state $s_{\widetilde{h}}$, at time
step $\widetilde{h}$ in $\tau$, does not lie in the set $\bar{}\mathcal{S}$.

Note that when $h^{\prime}\leq h$, we define $\mathfrak{T}(s\rightarrow
s^{\prime};\neg\bar{}\mathcal{S})=\emptyset$. Additionally, we define
$\mathfrak{T}(s_{\top}\rightarrow s;\neg\bar{}\mathcal{S})$ as the set of all
trajectories that go to $s^{\prime}$ (from a start state) without going
through any state in $\bar{}\mathcal{S}$ in between. Finally, we define
$\mathfrak{T}(s\rightarrow s_{\bot};\neg\bar{}\mathcal{S})$ as the set of all
the trajectories that go from $s$ at time step $h$ to the end of the episode
without passing through any state in $\bar{}\mathcal{S}$ in between.

Furthermore, we use the shorthand $\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\coloneqq\mathfrak{T}(s\rightarrow
s^{\prime};\neg\mathcal{S}_{\pi})$ to denote the set of all the trajectories
that go from $s$ to $s^{\prime}$ without passing though any leaf state
$\mathcal{S}_{\pi}$.

  2. $(b)$

Using the above notation, for any $s\in\mathcal{S}$ and set
$\bar{}\mathcal{S}\subseteq\mathcal{S}$, we define
$\bar{d}^{\pi}(s;\neg\bar{\mathcal{S}})$ as the probability of reaching $s$
(from a start state) without passing through any state in $\bar{}\mathcal{S}$
in between, i.e.

$\displaystyle\bar{d}^{\pi}(s;\neg\bar{\mathcal{S}})$
$\displaystyle=\mathbb{P}^{\pi}\left[\tau\leavevmode\nobreak\
\text{reaches}\leavevmode\nobreak\ s\leavevmode\nobreak\ \text{without passing
through any state in $\bar{\mathcal{S}}$ before reaching $s$}\right]$ (16)
$\displaystyle=\mathbb{P}^{\pi}\left[\tau\leavevmode\nobreak\
\in\mathfrak{T}(s_{\top}\rightarrow s;\neg\bar{}\mathcal{S})\right].$

We next recall the notation of Markov Reward Process and formally define both
the population versions of policy-specific MRPs.

##### Markov Reward Process (MRP).

A Markov reward process
$\mathfrak{M}=\mathrm{MRP}(\mathcal{S},P,R,H,s_{\top},s_{\bot})$ is defined
over the state space $\mathcal{S}$ with start state $s_{\top}$ and end state
$s_{\bot}$, for trajectory length $H+2$. Without loss of generality, we assume
that $\\{s_{\top},s_{\bot}\\}\in\mathcal{S}$. The transition kernel is denoted
by $P:\mathcal{S}\times\mathcal{S}\to[0,1]$, such that for any
$s\in\mathcal{S}$, $\sum_{s^{\prime}}P_{s\to s^{\prime}}=1$; the reward kernel
is denoted $R:\mathcal{S}\times\mathcal{S}\to\Delta([0,1])$. Throughout, we
use the notation $\rightarrow$ to signify that the transitions and rewards are
defined along the edges of the MRP.

A trajectory in $\mathfrak{M}$ is of the form
$\tau=(s_{\top},s_{1},\cdots,s_{H},s_{\bot})$, where $s_{h}\in\mathcal{S}$ for
all $h\in[H]$. Furthermore, from any state $s\in\mathcal{S}$, the MRP
transitions777Our definition of Markov Reward Processes (MRP) deviates from
MDPs that we considered in the paper, in the sense that we do not assume that
the state space $\mathcal{S}$ is layered in an MRP. This variation is only
adapted to simplify the proofs and the notation in the rest of the paper. to
another state $s^{\prime}\in\mathcal{S}$ with probability $P_{s\rightarrow
s^{\prime}}$, and obtains the rewards $r_{s\rightarrow s^{\prime}}\sim
R_{s\rightarrow s^{\prime}}$. Thus,

$\displaystyle\mathbb{P}^{\mathfrak{M}}[\tau]=P_{s_{\top}\rightarrow
s_{1}}\cdot\left(\prod_{h=1}^{H-1}P_{s_{h}\rightarrow s_{h+1}}\right)\cdot
P_{s_{H}\rightarrow s_{\bot}},$

and the rewards

$\displaystyle R^{\mathfrak{M}}(\tau)=r_{s_{\top}\rightarrow
s_{1}}+\sum_{h=1}^{H}r_{s_{h}\rightarrow s_{h+1}}+r_{s_{H}\rightarrow
s_{\bot}}.$

Furthermore, in all the MRPs that we consider in the paper, we have
$P_{s_{\bot}\rightarrow s_{\bot}}=1$ and $r_{s_{\bot}\rightarrow s_{\bot}}=0$.

##### Policy-Specific Markov Reward Processes.

A key technical tool in our analysis will be policy-specific MRPs that depend
on the set $\mathcal{S}^{\mathrm{rch}}$ of the states that we have explored so
far. Recall that for any policy $\pi$,
$\mathcal{S}_{\pi}^{+}=\mathcal{S}_{\pi}\cup\\{s_{\top},s_{\bot}\\}$,
$\mathcal{S}_{\pi}^{\mathrm{rch}}=\mathcal{S}_{\pi}^{+}\cap\mathcal{S}^{\mathrm{rch}}$
and
$\mathcal{S}_{\pi}^{\mathrm{rem}}=\mathcal{S}_{\pi}^{+}\setminus(\mathcal{S}_{\pi}^{\mathrm{rch}}\cup\\{s_{\bot}\\})$.
We define the expected and the empirical versions of policy-specific MRPs
below; see Figure 2 for an illustration.

  1. $(a)$

Expected Version of Policy-Specific MRP. We define
$\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}=\mathrm{MRP}(\mathcal{S}_{\pi}^{+},P^{\pi},r^{\pi},H,s_{\top},s_{\bot})$
where

    1. $\bullet$

Transition Kernel $P^{\pi}$: For any $s\in\mathcal{S}_{\pi}^{\mathrm{rch}}$
and $s^{\prime}\in\mathcal{S}_{\pi}^{+}$, we have

$\displaystyle P_{s\to
s^{\prime}}^{\pi}=\mathbb{E}^{\pi}\left[\mathbbm{1}\left\\{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\}\big{|}s_{h}=s\right],$ (17)

where the expectation above is w.r.t. the trajectories drawn using $\pi$ in
the underlying MDP, and $h$ denotes the time step such that
$s\in\mathcal{S}_{h}$ (again, in the underying MDP). Thus, the transition
$P_{s\to s^{\prime}}^{\pi}$ denotes the probability of taking policy $\pi$
from $s$ and directly transiting to $s^{\prime}$ without visiting any other
states in $\mathcal{S}_{\pi}$. Furthermore, $P^{\pi}_{s\rightarrow
s^{\prime}}=\mathbbm{1}\left\\{s^{\prime}=s_{\bot}\right\\}$ for all
$s\in\mathcal{S}_{\pi}^{\mathrm{rem}}\cup\\{s_{\bot}\\}$.

    2. $\bullet$

Reward Kernel $r^{\pi}$: For any $s\in\mathcal{S}_{\pi}^{\mathrm{rch}}$ and
$s^{\prime}\in\mathcal{S}_{\pi}^{+}$, we have

$\displaystyle r_{s\to s^{\prime}}^{\pi}$
$\displaystyle\coloneqq\mathbb{E}^{\pi}\left[R(\tau_{h:h^{\prime}})\mathbbm{1}\left\\{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\}\big{|}s_{h}=s\right],$ (18)

where $R(\tau_{h:h^{\prime}})$ denotes the reward for the partial trajectory
$\tau_{h:h^{\prime}}$ in the underlying MDP. The reward $r_{s\to
s^{\prime}}^{\pi}$ denotes the expectation of rewards collected by taking
policy $\pi$ from $s$ and directly transiting to $s^{\prime}$ without visiting
any other states in $\mathcal{S}_{\pi}$. Furthermore, $r^{\pi}_{s\rightarrow
s^{\prime}}=0$ for all
$s\in\mathcal{S}_{\pi}^{\mathrm{rem}}\cup\\{s_{\bot}\\}$.

Throughout the analysis, we use
$\operatorname{\mathbb{P}}^{\mathfrak{M}}[\cdot]\coloneqq\operatorname{\mathbb{P}}^{\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}}[\cdot]$
and
$\mathbb{E}^{\mathfrak{M}}[\cdot]\coloneqq\mathbb{E}^{\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}}[\cdot]$
as a shorthand, whenever clear from the context.

  2. $(b)$

Empirical Version of Policy-Specific MRPs. Since the learner only has sampling
access to the underlying MDP, it can not directly construct the MRP
$\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$. Instead, in Algorithm 1,
the learner constructs an empirical estimate for
$\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$, defined as
$\widehat{\mathfrak{M}}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}=\mathrm{MRP}(\mathcal{S}_{\pi}^{+},\widehat{P}^{\pi},\widehat{r}^{\pi},H,s_{\top},s_{\bot})$
where

    1. $\bullet$

Transition Kernel $\widehat{P}^{\pi}$: For any
$s\in\mathcal{S}_{\pi}^{\mathrm{rch}}$ and
$s^{\prime}\in\mathcal{S}_{\pi}^{+}$, we have

$\displaystyle\widehat{P}_{s\to
s^{\prime}}^{\pi}=\frac{|\Pi_{\mathrm{core}}|}{|\mathcal{D}_{s}|}\sum_{\tau\in\mathcal{D}_{s}}\frac{\mathbbm{1}\left\\{\pi\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}{\sum_{\pi^{\prime}\in\Pi_{\mathrm{core}}}\mathbbm{1}\left\\{\pi^{\prime}\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}\mathbbm{1}\left\\{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\},$ (19)

where $\Pi_{\mathrm{core}}$ denotes the core of the sunflower corresponding to
$\Pi$ and $\mathcal{D}_{s}$ denotes a dataset of trajectories collected via
$\mathsf{DataCollector}(s,\pi_{s},\Pi_{\mathrm{core}},n_{2})$. Furthermore,
$\widehat{P}^{\pi}_{s\rightarrow
s^{\prime}}=\mathbbm{1}\left\\{s^{\prime}=s_{\bot}\right\\}$ for all
$s\in\mathcal{S}_{\pi}^{\mathrm{rem}}\cup\\{s_{\bot}\\}$.

    2. $\bullet$

Reward Kernel $\widehat{r}^{\pi}$: For any
$s\in\mathcal{S}_{\pi}^{\mathrm{rch}}$ and
$s^{\prime}\in\mathcal{S}_{\pi}^{+}$, we have

$\displaystyle\widehat{r}_{s\to
s^{\prime}}^{\pi}=\frac{|\Pi_{\mathrm{core}}|}{|\mathcal{D}_{s}|}\sum_{\tau\in\mathcal{D}_{s}}\frac{\mathbbm{1}\left\\{\pi\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}{\sum_{\pi^{\prime}\in\Pi_{\mathrm{core}}}\mathbbm{1}\left\\{\pi^{\prime}\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}\mathbbm{1}\left\\{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\}R(\tau_{h:h^{\prime}}),$ (20)

where $\Pi_{\mathrm{core}}$ denotes the core of the sunflower corresponding to
$\Pi$, $\mathcal{D}_{s}$ denotes a dataset of trajectories collected via
$\mathsf{DataCollector}(s,\pi_{s},\Pi_{\mathrm{core}},n_{2})$, and
$R(\tau_{h:h^{\prime}})=\sum_{i=h}^{h^{\prime}-1}r_{i}$. Furthermore,
$\widehat{r}^{\pi}_{s\rightarrow s^{\prime}}=0$ for all
$s\in\mathcal{S}_{\pi}^{\mathrm{rem}}$.

The above approximates the MRP given by (3) and (4) in the main body.

Figure 2: Illustration of an MRP
$\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$ with
$\mathcal{S}_{\pi}=\\{s_{1},s_{2},s_{3}\\}$ and
$\mathcal{S}^{\mathrm{rch}}=\\{s_{1},s_{2}\\}$. In the original MDP $M$,
$s_{1}\in\mathcal{S}_{1}$, $s_{2}\in\mathcal{S}_{3}$, and
$s_{3}\in\mathcal{S}_{2}$. The edges are labeled with the values of
$P^{\pi}_{s\to s^{\prime}}$ and $R^{\pi}_{s\to s^{\prime}}$. Notice that (1)
there are no edges from $s_{2}\to s_{3}$ or $s_{3}\to s_{2}$ because
trajectories cannot go from later layers to earlier ones; (2) since
$s_{3}\notin\mathcal{S}^{\mathrm{rch}}$, there is no edge from $s_{3}\to
s_{2}$, and instead we have $P^{\pi}_{s_{3}\to s_{\bot}}=1$ and
$R^{\pi}_{s_{3}\to s_{\bot}}=0$; (3) $s_{\bot}$ is an absorbing state with no
rewards.

##### Properties of Trajectories in the Policy-Specific MRPs.

We state several properties of trajectories in the policy-specific MRPs, which
will be used in the proofs. Let $\tau=(s_{\top},s_{1},\cdots,s_{H},s_{\bot})$
denote a trajectory from either
$\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$ or
$\widehat{\mathfrak{M}}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$.

  1. $(1)$

For some $k\leq H$ we have $s_{1},\cdots,s_{k}\in\mathcal{S}_{\pi}$ and
$s_{k+1}=\cdots=s_{H}=s_{\bot}$ (if $k=H$ we say the second condition is
trivially met).

  2. $(2)$

Each state in $s_{1},\cdots,s_{k}$ is unique.

  3. $(3)$

Letting $\mathsf{h}(s)$ denote the layer that a state $s\in\mathcal{S}_{\pi}$
is in, we have $\mathsf{h}(s_{1})<\cdots<\mathsf{h}(s_{k})$.

  4. $(4)$

Either (a) $s_{1},\cdots,s_{k}\in\mathcal{S}_{\pi}^{\mathrm{rch}}$, or (b)
$s_{1},\cdots,s_{k-1}\in\mathcal{S}_{\pi}^{\mathrm{rch}}$ and
$s_{k}\in\mathcal{S}_{\pi}^{\mathrm{rem}}$.

##### Parameters Used in Algorithm 1.

Here, we list all the parameters that are used in Algorithm 1 and its
subroutines:

$\displaystyle n_{1}$
$\displaystyle=C_{1}\frac{(D+1)^{4}K^{2}\log(|\Pi|(D+1)/\delta)}{\varepsilon^{2}},$
$\displaystyle n_{2}$
$\displaystyle=C_{2}\frac{D^{3}(D+1)^{2}K^{2}\log(|\Pi|(D+1)^{2}/\delta)}{\varepsilon^{3}},$
(21)

where $C_{1},C_{2}>0$ are absolute numerical constants, which will be
specified later in the proofs.

###  F.2 Supporting Technical Results

We start by stating the following variant of the classical simulation lemma
(Kearns and Singh, 2002; Agarwal et al., 2019; Foster et al., 2021a).

######  Lemma 9 (Simulation lemma (Foster et al., 2021a, Lemma F.3)).

Let $\mathfrak{M}=(\mathcal{S},P,r,H,s_{\top},s_{\bot})$ be a markov reward
process. Then, the empirical version
$\widehat{\mathfrak{M}}=(\mathcal{S},\widehat{P},\widehat{r},H,s_{\top},s_{\bot})$
corresponding to $\mathfrak{M}$ satisfies:

$|V_{\mathrm{MRP}}-\widehat{V}_{\mathrm{MRP}}|\leq\sum_{s\in\mathcal{S}}d_{\mathfrak{M}}(s)\cdot\left(\sum_{s^{\prime}\in\mathcal{S}}|P_{s\to
s^{\prime}}-\widehat{P}_{s\to s^{\prime}}|+\left|r_{s\to
s^{\prime}}-\widehat{r}_{s\to s^{\prime}}\right|\right),$

where $d_{\mathfrak{M}}(s)$ is the probability of reaching $s$ under
$\mathfrak{M}$, and $V_{\mathrm{MRP}}$ and $\widehat{V}_{\mathrm{MRP}}$
denotes the value of $s_{\top}$ under $\mathfrak{M}$ and
$\widehat{\mathfrak{M}}$ respectively.

The following technical lemma shows that for any policy $\pi$, the empirical
version of policy-specific MRP closely approximates its expected version.

######  Lemma 10.

Let Algorithm 1 be run with the parameters given in Eq. (21), and consider any
iteration of the while loop in line 6 with the instantaneous set
$\mathcal{S}^{\mathrm{rch}}$. Further, suppose that
$|\mathcal{D}_{s}|\geq\tfrac{\varepsilon n_{2}}{24D}$ for all
$s\in\mathcal{S}^{\mathrm{rch}}$. Then, with probability at least $1-\delta$,
the following hold:

  1. $(a)$

For all $\pi\in\Pi$, $s\in\mathcal{S}_{\pi}^{\mathrm{rch}}$ and
$s^{\prime}\in\mathcal{S}_{\pi}\cup\\{s_{\bot}\\}$,

$\displaystyle\max\left\\{|P_{s\to s^{\prime}}^{\pi}-\widehat{P}_{s\to
s^{\prime}}^{\pi}|,\left|r_{s\to s^{\prime}}^{\pi}-\widehat{r}_{s\to
s^{\prime}}^{\pi}\right|\right\\}$
$\displaystyle\leq\frac{\varepsilon}{12D(D+1)}.$

  2. $(b)$

For all $\pi\in\Pi$ and $s^{\prime}\in\mathcal{S}_{\pi}\cup\\{s_{\bot}\\}$,

$\displaystyle\max\\{|P_{s_{\top}\to
s^{\prime}}^{\pi}-\widehat{P}_{s_{\top}\to
s^{\prime}}^{\pi}|,|r^{\pi}_{s_{\top}\to
s^{\prime}}-\widehat{r}^{\pi}_{s_{\top}\to
s^{\prime}}|\\}\leq\frac{\varepsilon}{12(D+1)^{2}}.$

In the sequel, we define the event that the conclusion of Lemma 10 holds as
$\mathcal{E}_{\mathrm{est}}$.

###### Proof.

Fix any $\pi\in\Pi$. We first prove the bound for
$s\in\mathcal{S}_{\pi}^{\mathrm{rch}}$. Let $s$ be at layer $h$. Fix any
policy $\pi\in\Pi$, and consider any state
$s^{\prime}\in\mathcal{S}_{\pi}\cup\\{s_{\bot}\\}$, where $s^{\prime}$ is at
layer $h^{\prime}$. Note that since $\Pi$ is a $(K,D)$-sunflower, with its
core $\Pi_{\mathrm{core}}$ and petals ${\\{\mathcal{S}_{\pi}\\}}_{\pi\in\Pi}$,
we must have that any trajectory $\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})$ is also consistent with at least one
$\pi_{e}\in\Pi_{\mathrm{core}}$. Furthermore, for any such $\pi_{e}$, we have

$\displaystyle\operatorname{\mathbb{P}}^{\pi_{e}}\left[\tau_{h:h^{\prime}}\mid
s_{h}=s\right]$ $\displaystyle=\prod_{i=h}^{h^{\prime}-1}P\left[s_{i+1}\mid
s_{i},\pi_{e}(s_{i}),s_{h}=s\right]$
$\displaystyle=\prod_{i=h}^{h^{\prime}-1}P\left[s_{i+1}\mid
s_{i},\pi(s_{i}),s_{h}=s\right]=\operatorname{\mathbb{P}}^{\pi}\left[\tau_{h:h^{\prime}}\mid
s_{h}=s\right],$ (22)

where the second line holds because both
$\pi\rightsquigarrow\tau_{h:h^{\prime}}$ and
$\pi_{e}\rightsquigarrow\tau_{h:h^{\prime}}$. Next, recall from Eq. (17), that

$\displaystyle P_{s\to s^{\prime}}^{\pi}$
$\displaystyle=\mathbb{E}^{\pi}\left[\mathbbm{1}\left\\{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\}\mid s_{h}=s\right].$ (23)

Furthermore, from Eq. (19), recall that the empirical estimate
$\widehat{P}_{s\to s^{\prime}}^{\pi}$ of ${P}_{s\to s^{\prime}}^{\pi}$ is
given by :

$\displaystyle\widehat{P}_{s\to
s^{\prime}}^{\pi}=\frac{1}{|\mathcal{D}_{s}|}\sum_{\tau\in\mathcal{D}_{s}}\frac{\mathbbm{1}\left\\{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\}}{\frac{1}{|\Pi_{\mathrm{core}}|}\sum_{\pi_{e}\in\Pi_{\mathrm{core}}}\mathbbm{1}\left\\{\pi_{e}\rightsquigarrow\tau_{h:h^{\prime}}\right\\}},$
(24)

where the dataset $\mathcal{D}_{s}$ consists of i.i.d. samples, and is
collected in lines 11-13 in Algorithm 3 ($\mathsf{DataCollector}$), by first
running the policy $\pi_{s}$ for $h$ timesteps and if the trajectory reaches
$s$, then executing $\pi_{e}\sim\mathrm{Uniform}(\Pi_{\mathrm{core}})$ for the
remaining time steps (otherwise this trajectory is rejected). Let the law of
this process be $q$. We thus note that,

$\displaystyle\mathbb{E}_{\tau\sim q}\left[\widehat{P}_{s\to
s^{\prime}}^{\pi}\right]$ $\displaystyle=\mathbb{E}_{\tau\sim
q}\left[\frac{\mathbbm{1}\left\\{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\}}{\frac{1}{|\Pi_{\mathrm{core}}|}\sum_{\pi_{e}\in\Pi_{\mathrm{core}}}\mathbbm{1}\left\\{\pi_{e}\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}\mid
s_{h}=s\right]$ $\displaystyle=\sum_{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})}\operatorname{\mathbb{P}}_{q}\left[\tau_{h:h^{\prime}}\mid
s_{h}=s\right]\cdot\frac{1}{\frac{1}{|\Pi_{\mathrm{core}}|}\sum_{\pi_{e}\in\Pi_{\mathrm{core}}}\mathbbm{1}\left\\{\pi_{e}\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}$
$\displaystyle\overset{\left(i\right)}{=}\sum_{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})}\frac{1}{|\Pi_{\mathrm{core}}|}\sum_{\pi^{\prime}_{e}\in\Pi_{\mathrm{core}}}\mathbbm{1}\left\\{\tau\in\mathfrak{T}_{\pi^{\prime}_{e}}(s\rightarrow
s^{\prime})\right\\}\operatorname{\mathbb{P}}^{\pi^{\prime}_{e}}\left[\tau_{h:h^{\prime}}\mid
s_{h}=s\right]\cdot\frac{1}{\frac{1}{|\Pi_{\mathrm{core}}|}\sum_{\pi_{e}\in\Pi_{\mathrm{core}}}\mathbbm{1}\left\\{\pi_{e}\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}$
$\displaystyle\overset{\left(ii\right)}{=}\sum_{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})}\frac{1}{|\Pi_{\mathrm{core}}|}\sum_{\pi^{\prime}_{e}\in\Pi_{\mathrm{core}}}\operatorname{\mathbb{P}}^{\pi}\left[\tau_{h:h^{\prime}}\mid
s_{h}=s\right]\cdot\frac{\mathbbm{1}\left\\{\pi^{\prime}_{e}\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}{\frac{1}{|\Pi_{\mathrm{core}}|}\sum_{\pi_{e}\in\Pi_{\mathrm{core}}}\mathbbm{1}\left\\{\pi_{e}\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}$
$\displaystyle=\sum_{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})}\operatorname{\mathbb{P}}^{\pi}\left[\tau_{h:h^{\prime}}\mid
s_{h}=s\right]$
$\displaystyle\overset{\left(iii\right)}{=}\mathbb{E}^{\pi}\left[\mathbbm{1}\left\\{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\}\mid s_{h}=s\right]=P_{s\to s^{\prime}}^{\pi},$

where $\left(i\right)$ follows from the sampling strategy in Algorithm 3 after
observing $s_{h}=s$, and $\left(ii\right)$ simply uses the relation (22) since
both $\pi^{\prime}_{e}\rightsquigarrow\tau_{h:h^{\prime}}$ and
$\pi\rightsquigarrow\tau_{h:h^{\prime}}$ hold. Finally, in $\left(iii\right)$,
we use the relation (23).

We have shown that $\widehat{P}_{s\to s^{\prime}}^{\pi}$ is an unbiased
estimate of $P^{\pi}_{s\to s^{\prime}}$ for any $\pi$ and
$s,s^{\prime}\in\mathcal{S}_{\pi}^{+}$. Thus, using Hoeffding’s inequality
(Lemma 17), followed by a union bound, we get that with probability at least
$1-\delta/4$, for all $\pi\in\Pi$, $s\in\mathcal{S}_{\pi}^{\mathrm{rch}}$, and
$s^{\prime}\in\mathcal{S}_{\pi}\cup\\{s_{\bot}\\}$,

$\displaystyle|\widehat{P}_{s\to s^{\prime}}^{\pi}-P_{s\to
s^{\prime}}^{\pi}|\leq
K\sqrt{\frac{2\log(4|\Pi|D(D+1)/\delta)}{|\mathcal{D}_{s}|}},$

where the additional factor of $K$ appears because for any
$\tau\in\mathfrak{T}_{\pi}(s\rightarrow s^{\prime})$, there must exist some
$\pi_{e}\in\Pi_{\mathrm{core}}$ that is also consistent with $\tau$ (as we
showed above), which implies that each of the terms in Eq. (24) satisfies the
bound a.s.:

$\displaystyle\left\lvert\frac{\mathbbm{1}\left\\{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\}}{\tfrac{1}{|\Pi_{\mathrm{core}}|}\sum_{\pi_{e}\in\Pi_{\mathrm{core}}}\mathbbm{1}\left\\{\pi_{e}\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}\right\rvert$
$\displaystyle\leq\lvert\Pi_{\mathrm{core}}\rvert=K.$

Since $|\mathcal{D}_{s}|\geq\tfrac{\varepsilon n_{2}}{24D}$ by assumption, we
have

$\displaystyle|\widehat{P}_{s\to s^{\prime}}^{\pi}-P_{s\to
s^{\prime}}^{\pi}|\leq K\sqrt{\frac{48D\log(4|\Pi|D(D+1)/\delta)}{\varepsilon
n_{2}}}.$

Repeating a similar argument for the empirical reward estimation in Eq. (19),
we get that with probability at least $1-\delta/4$, for all $\pi\in\Pi$, and
$s\in\mathcal{S}_{\pi}^{\mathrm{rch}}$ and
$s^{\prime}\in\mathcal{S}_{\pi}\cup\\{s_{\bot}\\}$, we have that

$\displaystyle|\widehat{r}_{s\to s^{\prime}}^{\pi}-r_{s\to
s^{\prime}}^{\pi}|\leq K\sqrt{\frac{48D\log(4|\Pi|D(D+1)/\delta)}{\varepsilon
n_{2}}}.$

Similarly, we can also get for any $\pi\in\Pi$ and
$s^{\prime}\in\mathcal{S}_{\pi}\cup\\{s_{\bot}\\}$, with probability at least
$1-\delta/2$,

$\displaystyle\max\left\\{|\widehat{r}_{s_{\top}\to
s^{\prime}}^{\pi}-r_{s_{\top}\to s^{\prime}}^{\pi}|,|\widehat{P}_{s_{\top}\to
s^{\prime}}^{\pi}-P_{s_{\top}\to s^{\prime}}^{\pi}|\right\\}$
$\displaystyle\leq
K\sqrt{\frac{2\log(4|\Pi|(D+1)/\delta)}{|\mathcal{D}_{s_{\top}}|}}$
$\displaystyle=K\sqrt{\frac{2\log(4|\Pi|(D+1)/\delta)}{n_{1}}},$

where the last line simply uses the fact that
$\lvert\mathcal{D}_{s_{\top}}\rvert=n_{1}$. The final statement is due to a
union bound on the above results. This concludes the proof of Lemma 10.∎

######  Lemma 11.

Fix a policy $\pi\in\Pi$ and a set of reachable states
$\mathcal{S}^{\mathrm{rch}}$, and consider the policy-specific MRP
$\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$ (as defined by Eqs. (17) and
(18)). Then for any $s\in\mathcal{S}_{\pi}^{\mathrm{rem}}$, the quantity
$\bar{d}^{\pi}(s;\neg\mathcal{S}_{\pi}^{\mathrm{rem}})=d^{\mathfrak{M}}(s)$,
where $d^{\mathfrak{M}}(s)$ is the occupancy of state $s$ in
$\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$.

###### Proof.

We use $\bar{\tau}$ to denote a trajectory in
$\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$ and $\tau$ to denote a
“corresponding” (in a sense which will be described shortly) trajectory in the
original MDP $M$. For any $s\in\mathcal{S}_{\pi}^{\mathrm{rem}}$, we have

$\displaystyle d^{\mathfrak{M}}(s)$
$\displaystyle=\sum_{\bar{\tau}\leavevmode\nobreak\
\text{s.t.}\leavevmode\nobreak\
s\in\bar{\tau}}\operatorname{\mathbb{P}}^{\mathfrak{M}}\left[\bar{\tau}\right]=\sum_{k=0}^{H-1}\sum_{\bar{s}_{1},\bar{s}_{2},\cdots,\bar{s}_{k}\in\mathcal{S}_{\pi}^{\mathrm{rch}}}\operatorname{\mathbb{P}}^{\mathfrak{M}}\left[\bar{\tau}=(s_{\top},\bar{s}_{1},\cdots,\bar{s}_{k},s,s_{\bot},\cdots)\right].$

The first equality is simply due to the definition of $d^{\mathfrak{M}}$. For
the second equality, we sum up over all possible sequences which start at
$s_{\top}$, pass through some (variable length) sequence of states
$\bar{s}_{1},\cdots,\bar{s}_{k}\in\mathcal{S}_{\pi}^{\mathrm{rch}}$, then
reach $s$ and the terminal state $s_{\perp}$. By definition of the policy-
specific MRP, we know that once the MRP transits to a state
$s\in\mathcal{S}_{\pi}^{\mathrm{rem}}$, it must then transit to $s_{\bot}$ and
repeat $s_{\bot}$ until the end of the episode.

Now fix a sequence
$\bar{s}_{1},\cdots,\bar{s}_{k}\in\mathcal{S}_{\pi}^{\mathrm{rch}}$. We relate
the term in the summand to the probability of corresponding trajectories in
the original MDP $M$. To avoid confusion, we let
$s_{h_{1}},\dots,s_{h_{k}}\in\mathcal{S}_{\pi}^{\mathrm{rch}}$ denote the
corresponding sequence of states in the original MDP, which are unique and
satisfy $h_{1}<h_{2}<\cdots<h_{k}$. We also denote $s_{h_{k+1}}=s$.

Using the definition of $\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$, we
write

$\displaystyle\operatorname{\mathbb{P}}^{\mathfrak{M}}\left[\bar{\tau}=(s_{\top},\bar{s}_{1},\cdots,\bar{s}_{k},s,s_{\bot},\cdots)\right]$
$\displaystyle=\prod_{i=1}^{k}\operatorname{\mathbb{P}}^{M,\pi}\left[\tau_{h_{i}:h_{i+1}}\in\mathfrak{T}_{\pi}(s_{h_{i}}\rightarrow
s_{h_{i+1}})\mid\tau[h_{i}]=s_{h_{i}}\right]$
$\displaystyle=\operatorname{\mathbb{P}}^{M,\pi}\left[\forall
i\in[k+1],\leavevmode\nobreak\ \tau[h_{i}]=s_{h_{i}},\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \forall
h\in[h_{k+1}]\backslash\\{h_{1},\cdots,h_{k+1}\\},\leavevmode\nobreak\
\tau[h]\notin\mathcal{S}_{\pi}\right].$

Now we sum over all sequences
$\bar{s}_{1},\cdots,\bar{s}_{k}\in\mathcal{S}_{\pi}^{\mathrm{rch}}$ to get

$\displaystyle d^{\mathfrak{M}}(s)$
$\displaystyle=\sum_{k=0}^{H-1}\sum_{s_{h_{1}},\cdots,s_{h_{k}}\in\mathcal{S}_{\pi}^{\mathrm{rch}}}\operatorname{\mathbb{P}}^{M,\pi}\left[\forall
i\in[k+1],\leavevmode\nobreak\ \tau[h_{i}]=s_{h_{i}},\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \forall
h\in[h_{k+1}]\backslash\\{h_{1},\cdots,h_{k+1}\\},\leavevmode\nobreak\
\tau[h]\notin\mathcal{S}_{\pi}\right]$
$\displaystyle=\operatorname{\mathbb{P}}^{M,\pi}\left[s\in\tau\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \forall h\in[h_{k+1}-1],\leavevmode\nobreak\
\tau[h]\notin\mathcal{S}_{\pi}^{\mathrm{rem}}\right]$
$\displaystyle=\operatorname{\mathbb{P}}^{\pi}\left[\tau\in\mathfrak{T}(s_{\top}\rightarrow
s;\neg\mathcal{S}_{\pi}^{\mathrm{rem}})\right]=\bar{d}^{\pi}(s;\neg\mathcal{S}_{\pi}^{\mathrm{rem}}).$

The second equality follows from the definition of
$\mathcal{S}_{\pi}^{\mathrm{rem}}$, and the last line is the definition of the
$\bar{d}$ notation. This concludes the proof of Lemma 11. ∎

######  Lemma 12.

With probability at least $1-2\delta$, any $(\bar{s},\pi)$ that is added into
$\mathcal{T}$ (in line 14 of Algorithm 1) satisfies
$d^{\pi}(\bar{s})\geq\nicefrac{{\varepsilon}}{{12D}}$.

###### Proof.

For any $(\bar{s},\pi)\in\mathcal{T}$, when we collect $\mathcal{D}_{\bar{s}}$
in Algorithm 3, the probability that a trajectory will be accepted (i.e. the
trajectory satisfies the “if” statement in line 11) is exactly
$d^{\pi}({\bar{s}})$. Thus, using Hoeffding’s inequality (Lemma 17), with
probability at least $1-\nicefrac{{\delta}}{{D|\Pi|}}$,

$\left|\frac{|\mathcal{D}_{\bar{s}}|}{n_{2}}-d^{\pi}({\bar{s}})\right|\leq\sqrt{\frac{2\log(D|\Pi|/\delta)}{n_{2}}}.$

Since $|\mathcal{T}|\leq D|\Pi|$, by union bound, the above holds for every
$(\bar{s},\pi)\in\mathcal{T}$ with probability at least $1-\delta$. Let us
denote this event as $\mathcal{E}_{\mathrm{data}}$. Under
$\mathcal{E}_{\mathrm{data}}$, for any $(\bar{s},\pi)$ that satisfies
$d^{\pi}(\bar{s})\geq\tfrac{\varepsilon}{12D}$,

$\displaystyle|\mathcal{D}_{\bar{s}}|$ $\displaystyle\geq
n_{2}d^{\pi}(\bar{s})-\sqrt{2n_{2}\log(D|\Pi|/\delta)}\geq\frac{\varepsilon
n_{2}}{12D}-\frac{\varepsilon n_{2}}{24D}=\frac{\varepsilon n_{2}}{24D},$ (25)

where the second inequality follows by the bound on $d^{\pi}(\bar{s})$ and our
choice of parameter $n_{2}$ in Eq. (21).

In the following, we prove by induction that every $(\bar{s},\pi)$ that is
added into $\mathcal{T}$ in the while loop from lines 8-18 in Algorithm 1
satisfies $d^{\pi}(\bar{s})\geq\tfrac{\varepsilon}{12D}$. This is trivially
true at initialization when $\mathcal{T}=\\{(s_{\top},\mathrm{Null})\\}$,
since every trajectory starts at the dummy state $s_{\top}$, for which we have
$d^{\mathrm{Null}}(s_{\top})=1$.

We now proceed to the induction hypothesis. Suppose that in some iteration of
the while loop, every tuple $(\bar{s},\pi)\in\mathcal{T}$ satisfies
$d^{\pi}(\bar{s})\geq\nicefrac{{\varepsilon}}{{12D}}$, and that
$(\bar{s}^{\prime},\pi^{\prime})$ is a new tuple that will be added to
$\mathcal{T}$. We will show that $(\bar{s}^{\prime},\pi^{\prime})$ will also
satisfy
$d^{\pi^{\prime}}({\bar{s}^{\prime}})\geq\nicefrac{{\varepsilon}}{{12D}}$.

Recall that
$\mathcal{S}_{\pi^{\prime}}^{+}=\mathcal{S}_{\pi^{\prime}}\cup\\{s_{\top},s_{\bot}\\}$,
$\mathcal{S}_{\pi^{\prime}}^{\mathrm{rch}}=\mathcal{S}_{\pi^{\prime}}^{+}\cap\mathcal{S}^{\mathrm{rch}}$,
and
$\mathcal{S}_{\pi^{\prime}}^{\mathrm{rem}}=\mathcal{S}_{\pi^{\prime}}^{+}\setminus\mathcal{S}_{\pi^{\prime}}^{\mathrm{rch}}$.
Let
$\mathfrak{M}^{\pi^{\prime}}_{\mathcal{S}^{\mathrm{rch}}}=\mathrm{MRP}(\mathcal{S}_{\pi^{\prime}}^{+},P^{\pi^{\prime}},r^{\pi^{\prime}},H,s_{\top},s_{\bot})$
be the policy-specific MRP, where $P^{\pi^{\prime}}$ and $r^{\pi^{\prime}}$
are defined in Eqs. (17) and (18) respectively for the policy $\pi^{\prime}$.
Similarly let
$\widehat{\mathfrak{M}}^{\pi^{\prime}}_{\mathcal{S}^{\mathrm{rch}}}=\mathrm{MRP}(\mathcal{S}_{\pi^{\prime}}^{+},\widehat{P}^{\pi^{\prime}},\widehat{r}^{\pi^{\prime}},H,s_{\top},s_{\bot})$
denote the estimated policy-specific MRP, where $\widehat{P}^{\pi^{\prime}}$
and $r^{\pi^{\prime}}$ are defined using (19) and (20) respectively. Note that
for any state $s\in\mathcal{S}_{\pi^{\prime}}^{\mathrm{rch}}$, the bound in
(25) holds.

For the rest of the proof, we assume that the event
$\mathcal{E}_{\mathrm{est}}$, defined in Lemma 10, holds (this happens with
probability at least $1-\delta$). By definition of
$\mathcal{E}_{\mathrm{est}}$, we have

$|P_{s\to s^{\prime}}^{\pi^{\prime}}-\widehat{P}_{s\to
s^{\prime}}^{\pi^{\prime}}|\leq\frac{\varepsilon}{12D(D+1)},\qquad\text{for
all}\qquad s^{\prime}\in\mathcal{S}_{\pi^{\prime}}\cup\\{s_{\bot}\\}.$ (26)

Furthermore, note that
$\widehat{d}^{\pi^{\prime}}(\bar{s}^{\prime})\leftarrow\mathsf{EstReachability}(\mathcal{S}_{\pi^{\prime}}^{+},\widehat{\mathfrak{M}}^{\pi^{\prime}}_{\mathcal{S}^{\mathrm{rch}}},\bar{s}^{\prime})$
since in Algorithm 4 we start with
$V(s)=\mathbbm{1}\left\\{s=\bar{s}^{\prime}\right\\}$. Furthermore, using
Lemma 9, we have

$\displaystyle|\widehat{d}^{\pi^{\prime}}(\bar{s}^{\prime})-d^{\mathfrak{M}}(\bar{s}^{\prime})|$
$\displaystyle\leq(D+1)\sup_{s\in\mathcal{S}_{\pi^{\prime}}^{\mathrm{rch}},s^{\prime}\in\mathcal{S}_{\pi^{\prime}}\cup\\{s_{\bot}\\}}|\widehat{P}_{s\to
s^{\prime}}^{\pi^{\prime}}-P_{s\to s^{\prime}}^{\pi^{\prime}}|$ (27)
$\displaystyle\leq\frac{\varepsilon}{12D(D+1)}\cdot(D+1)=\frac{\varepsilon}{12D}.$

where the second inequality follows from (26). Additionally, Lemma 11 states
that
$d^{\mathfrak{M}}(\bar{s}^{\prime})=\bar{d}^{\pi^{\prime}}(\bar{s}^{\prime};\neg\mathcal{S}_{\pi^{\prime}}^{\mathrm{rem}})$.
Therefore we obtain

$|\bar{d}^{\pi^{\prime}}(\bar{s}^{\prime};\neg\mathcal{S}_{\pi^{\prime}}^{\mathrm{rem}})-\widehat{d}^{\pi^{\prime}}(\bar{s}^{\prime})|\leq\frac{\varepsilon}{12D}.$

Thus, if the new state-policy pair $(\bar{s}^{\prime},\pi^{\prime})$ is added
into $\mathcal{T}$, we will have

$\bar{d}^{\pi^{\prime}}(\bar{s}^{\prime};\neg\mathcal{S}_{\pi^{\prime}}^{\mathrm{rem}})\geq\frac{\varepsilon}{6D}-\frac{\varepsilon}{12D}=\frac{\varepsilon}{12D}.$

Furthermore, by definition of $\bar{d}$ we have

$\bar{d}^{\pi^{\prime}}(\bar{s}^{\prime};\neg\mathcal{S}_{\pi^{\prime}}^{\mathrm{rem}})=\operatorname{\mathbb{P}}^{\pi^{\prime}}\left[\tau\in\mathfrak{T}(s_{\top}\rightarrow\bar{s}^{\prime};\neg\mathcal{S}_{\pi^{\prime}}^{\mathrm{rem}})\right]\leq\operatorname{\mathbb{P}}^{\pi^{\prime}}[\bar{s}^{\prime}\in\tau]=d^{\pi^{\prime}}(\bar{s}^{\prime}),$

so we have proved the induction hypothesis
$d^{\pi^{\prime}}(\bar{s}^{\prime})\geq\nicefrac{{\varepsilon}}{{12D}}$ for
the next round. This concludes the proof of Lemma 12.

∎

The next lemma establishes that Algorithm 1 will terminate after finitely many
rounds, and that after termination will have explored all sufficiently
reachable states.

######  Lemma 13.

With probability at least $1-2\delta$,

  1. $(a)$

The while loop in line 6 in Algorithm 1 will terminate after at most
$\tfrac{12HD\mathfrak{C}(\Pi)}{\varepsilon}$ rounds.

  2. $(b)$

After the termination of the while loop, for any $\pi\in\Pi$, the remaining
states $s\in\mathcal{S}_{\pi}^{\mathrm{rem}}$ that are not added to
$\mathcal{S}^{\mathrm{rch}}$ satisfy
$\bar{d}^{\pi}(s;\neg\mathcal{S}_{\pi}^{\mathrm{rem}})\leq\nicefrac{{\varepsilon}}{{4D}}$.

Notice that according to our algorithm, the same state cannot be added
multiple times into $\mathcal{S}^{\mathrm{rch}}$. Therefore,
$|\mathcal{S}^{\mathrm{rch}}|\leq D|\Pi|$, and the maximum number of rounds of
the while loop is $D|\Pi|$ (i.e., the while loop eventually terminates).

###### Proof.

We prove each part separately.

  1. $(a)$

First, note that from the definition of coverability and Lemma 1, we have

$\sum_{s\in\mathcal{S}}\sup_{\pi\in\Pi}d^{\pi}(s)\leq
HC^{\mathsf{cov}}(\Pi;M)\leq H\mathfrak{C}(\Pi).$

Furthermore, Lemma 12 states that every $(s,\pi_{s})\in\mathcal{T}$ satisfies
$d^{\pi_{s}}(s)\geq\nicefrac{{\varepsilon}}{{12D}}$. Thus, at any point in
Algorithm 1, we have

$\displaystyle\sum_{s\in\mathcal{S}^{\mathrm{rch}}}\sup_{\pi\in\Pi}d^{\pi}(s)$
$\displaystyle\geq\sum_{s\in\mathcal{S}^{\mathrm{rch}}}d^{\pi_{s}}(s)\geq\lvert\mathcal{T}\rvert\cdot\frac{\varepsilon}{12D}.$

Since, $\mathcal{S}^{\mathrm{rch}}\subseteq\mathcal{S}$, the two bounds
indicate that

$|\mathcal{T}|\leq\frac{12HD\mathfrak{C}(\Pi)}{\varepsilon}.$

Since every iteration of the while loop adds one new $(s,\pi_{s})$ to
$\mathcal{T}$, the while loop terminates after at most
$\nicefrac{{12HD\mathfrak{C}(\Pi)}}{{\varepsilon}}$ many rounds.

  2. $(b)$

We know that once the while loop has terminated, for every $\pi\in\Pi$ and
$\bar{s}\in\mathcal{S}_{\pi}^{\mathrm{rem}}$, we must have
$\widehat{d}^{\pi}(\bar{s})\leq\nicefrac{{\varepsilon}}{{6D}}$, or else the
condition in line 13 in Algorithm 1 is violated.

Fix any such $(\bar{s},\pi)$ pair. Inspecting the proof of Lemma 12, we see
that

$\displaystyle|\bar{d}^{\pi}(\bar{s};\neg\mathcal{S}_{\pi}^{\mathrm{rem}})-\widehat{d}^{\pi}(\bar{s})|\leq\frac{\varepsilon}{12D}.$

To conclude, we get

$\bar{d}^{\pi}(s;\neg\mathcal{S}_{\pi}^{\mathrm{rem}})\leq\frac{\varepsilon}{6D}+\frac{\varepsilon}{12D}=\frac{\varepsilon}{4D}.$

∎

######  Lemma 14.

Suppose that the conclusions of Lemmas 10 and 13 hold. Then for every
$\pi\in\Pi$, the estimated value $\widehat{V}^{\pi}$ computed in Algorithm 1
satisfies

$|\widehat{V}^{\pi}-V^{\pi}|\leq\varepsilon.$

###### Proof.

We will break up the proof into two steps. First, we show that for any $\pi$,
the value estimate $\widehat{V}^{\pi}$ obtained using the empirical policy-
specific MRP $\widehat{\mathfrak{M}}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$ is
close to its value in the policy-specific MRP
$\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$, as defined via (17) and
(18). We denote this quantity as $V_{\mathrm{MRP}}^{\pi}$. Then, we will show
that $V_{\mathrm{MRP}}^{\pi}$ is close to $V^{\pi}$, the value of the policy
$\pi$ in the original MDP $M$.

##### Part 1: $\widehat{V}^{\pi}$ is close to $V_{\mathrm{MRP}}^{\pi}$.

Note that the output $\widehat{V}^{\pi}$ of Algorithm 5 is exact the value
function of MRP $\widehat{\mathfrak{M}}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$
defined by Eqs. (19) and (20). When $D=0$, by part (b) of Lemma 10, we obtain

$|\widehat{V}^{\pi}-V_{\mathrm{MRP}}^{\pi}|=|\widehat{r}^{\pi}_{s_{\top}\to
s_{\bot}}-r^{\pi}_{s_{\top}\to
s_{\bot}}|\leq\frac{\varepsilon}{12(D+1)^{2}}\leq\frac{\varepsilon}{2}.$

When $D\geq 1$, using Lemma 10, we have

$\displaystyle|r_{s_{\top}\to s^{\prime}}^{\pi}-\widehat{r}_{s_{\top}\to
s^{\prime}}^{\pi}|\leq\frac{\varepsilon}{12(D+1)^{2}},\quad|P_{s_{\top}\to
s^{\prime}}^{\pi}-\widehat{P}_{s_{\top}\to
s^{\prime}}^{\pi}|\leq\frac{\varepsilon}{12(D+1)^{2}},\quad$
$\displaystyle\forall s^{\prime}\in\mathcal{S}_{\pi}\cup\\{s_{\bot}\\}$
$\displaystyle|r_{s\to s^{\prime}}^{\pi}-\widehat{r}_{s\to
s^{\prime}}^{\pi}|\leq\frac{\varepsilon}{12D(D+1)},\quad|P_{s\to
s^{\prime}}^{\pi}-\widehat{P}_{s\to
s^{\prime}}^{\pi}|\leq\frac{\varepsilon}{12D(D+1)},\quad$
$\displaystyle\forall
s\in\mathcal{S}_{\pi}^{\mathrm{rch}},s^{\prime}\in\mathcal{S}_{\pi}^{+}\cup\\{s_{\bot}\\}.$

By the simulation lemma (Lemma 9), we get

$\displaystyle|\widehat{V}^{\pi}-V_{\mathrm{MRP}}^{\pi}|$ $\displaystyle\leq
2(D+2)\max_{s,s^{\prime}\in\mathcal{S}_{\pi}^{+}}\left(\left|P_{s\to
s^{\prime}}^{\pi}-\widehat{P}_{s\to s^{\prime}}^{\pi}\right|+\left|r_{s\to
s^{\prime}}^{\pi}-\widehat{r}_{s\to s^{\prime}}^{\pi}\right|\right)$
$\displaystyle\leq
2(D+2)\left(\frac{\varepsilon}{12D(D+1)}+\frac{\varepsilon}{12D(D+1)}\right)\leq\frac{\varepsilon}{2}.$

##### Part 2 : $V_{\mathrm{MRP}}^{\pi}$ is close to $V^{\pi}$.

As in the proof of Lemma 11, let us consider different trajectories
$\bar{\tau}$ that are possible in
$\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$. We can represent
$\bar{\tau}=(s_{\top},\bar{s}_{1},\cdots,\bar{s}_{k},s_{\bot},\cdots)$ where
the states $\bar{s}_{1},\cdots,\bar{s}_{k}$ are distinct and all except
possibly $\bar{s}_{k}$ belong to $\mathcal{S}_{\pi}^{\mathrm{rch}}$, and the
states after $s_{\bot}$ are just repeats of $s_{\bot}$ until the end of the
episode. Let $s_{h_{1}},s_{h_{2}},\dots,s_{h_{k}}$ be the same sequence (in
the original MDP $M$) Again, we have

$\displaystyle\operatorname{\mathbb{P}}^{\mathfrak{M}}[\bar{\tau}=(s_{\top},\bar{s}_{1},\cdots,\bar{s}_{k},s_{\bot},\cdots)]$
$\displaystyle=\operatorname{\mathbb{P}}^{\pi}\left[\forall
i\in[k],\leavevmode\nobreak\ \tau[h_{i}]=s_{h_{i}},\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \forall
h\in[H]\backslash\\{h_{1},\cdots,h_{k}\\},\leavevmode\nobreak\
\tau[h]\notin\mathcal{S}_{\pi}\right],$

where recall that $\operatorname{\mathbb{P}}^{\mathfrak{M}}$ denotes
probability under the $\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$, and
$\operatorname{\mathbb{P}}^{\pi}$ denotes the probability under trajectories
drawn according to $\pi$ in the underlying MDP; $\mathbb{E}^{\mathfrak{M}}$
and $\mathbb{E}^{\pi}$ are defined similarly.

Furthermore, the expectation of rewards we collected in
$\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$ with trajectories
$\bar{\tau}$ is

$\displaystyle\mathbb{E}^{\mathfrak{M}}\left[R[\bar{\tau}]\mathbbm{1}\left\\{(s_{\top},\bar{s}_{1},\cdots,\bar{s}_{k},s_{\bot},\cdots)\right\\}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}^{\pi}\left[R[\tau]\mathbbm{1}\left\\{\forall
i\in[k],\leavevmode\nobreak\ \tau[h_{i}]=s_{h_{i}},\leavevmode\nobreak\
\text{and}\leavevmode\nobreak\ \forall
h\in[H]\backslash\\{h_{1},\cdots,h_{k}\\},\leavevmode\nobreak\
\tau[h]\notin\mathcal{S}_{\pi}\right\\}\right].$

Next, we sum over all possible trajectories. However, note that the only
trajectories that are possible in $M$ whose corresponding trajectories are
_not accounted for_ in $\mathfrak{M}^{\pi}_{\mathcal{S}^{\mathrm{rch}}}$ are
precisely those that visit states in $\mathcal{S}_{\pi}$, after visiting some
$s_{h_{k}}$ in the remaining states $\mathcal{S}_{\pi}^{\mathrm{rem}}$ (since,
by construction, the MRP transitions directly to $s_{\bot}$ after encountering
a state in $\mathcal{S}_{\pi}^{\mathrm{rem}}$). Thus,

$V_{\mathrm{MRP}}^{\pi}=\mathbb{E}^{\pi}\left[R[\tau]\left(\mathbbm{1}\left\\{\tau\cap\mathcal{S}_{\pi}^{\mathrm{rem}}=\emptyset\right\\}+\mathbbm{1}\left\\{\exists
k\in[H]:s_{h_{k}}\in\mathcal{S}_{\pi}^{\mathrm{rem}}\text{ and }\forall
h>h_{k}:s_{h}\notin\mathcal{S}_{\pi}\right\\}\right)\right],$

where the first term corresponds to trajectories that do not pass through
$\mathcal{S}_{\pi}^{\mathrm{rem}}$, and the second term corresponds to
trajectories that passes through some state in
$\mathcal{S}_{\pi}^{\mathrm{rem}}$ but then does not go through any other
state in $\mathcal{S}_{\pi}$. On the other hand,

$\displaystyle V^{\pi}=\mathbb{E}^{\pi}\left[R[\tau]\right].$

Clearly, $V_{\mathrm{MRP}}^{\pi}\leq V^{\pi}$. Furthermore, we also have

$\displaystyle V^{\pi}-V_{\mathrm{MRP}}^{\pi}$
$\displaystyle=\mathbb{E}^{\pi}\left[R[\tau]\mathbbm{1}\left\\{\tau\cap\mathcal{S}_{\pi}^{\mathrm{rem}}\neq\emptyset\right\\}-\mathbbm{1}\left\\{\exists
k\in[H]:s_{h_{k}}\in\mathcal{S}_{\pi}^{\mathrm{rem}}\text{ and }\forall
h>h_{k}:s_{h}\notin\mathcal{S}_{\pi}\right\\}\right]$
$\displaystyle\leq\mathbb{E}^{\pi}\left[R[\tau]\mathbbm{1}\left\\{\tau\cap\mathcal{S}_{\pi}^{\mathrm{rem}}\neq\emptyset\right\\}\right]$
$\displaystyle\leq D\cdot\frac{\varepsilon}{4D}=\frac{\varepsilon}{4},$

where the first inequality follows by just ignoring the second indicator term,
and the second inequality follows by taking a union bound over all possible
values of $\mathcal{S}_{\pi}^{\mathrm{rem}}$ as well as the conclusion of
Lemma 13.

Putting it all together, we get that

$\displaystyle|\widehat{V}^{\pi}-V^{\pi}|\leq|V^{\pi}-V_{\mathrm{MRP}}^{\pi}|+|\widehat{V}^{\pi}-V_{\mathrm{MRP}}^{\pi}|\leq\frac{\varepsilon}{4}+\frac{\varepsilon}{2}<\varepsilon.$

This concludes the proof of Lemma 14. ∎

###  F.3 Proof of Theorem 4

We assume the events defined in Lemmas 10, 12 and 13 hold (which happens with
probability at least $1-2\delta$). With our choices of $n_{1},n_{2}$ in Eq.
(21), the total number of samples used in our algorithm is at most

$n_{1}+n_{2}\cdot\frac{12HD\mathfrak{C}(\Pi)}{\varepsilon}=\widetilde{\mathcal{O}}\left(\left(\frac{1}{\varepsilon^{2}}+\frac{HD^{6}\mathfrak{C}(\Pi)}{\varepsilon^{4}}\right)\cdot
K^{2}\log\frac{|\Pi|}{\delta}\right).$

After the termination of the while loop, we know that for any policy
$\pi\in\Pi$ and $s\in\mathcal{S}_{\pi}^{\mathrm{rem}}$ we have

$\bar{d}^{\pi}(s;\neg\mathcal{S}_{\pi}^{\mathrm{rem}})\leq\frac{\varepsilon}{4D}.$

Therefore, by Lemma 14, we know for every $\pi\in\Pi$,
$|\widehat{V}^{\pi}-V^{\pi}|\leq\varepsilon$. Hence the output policy
$\widehat{\pi}\in\mathop{\arg\max}_{\pi}\widehat{V}^{\pi}$ satisfies

$\max_{\pi\in\Pi}V^{\pi}-V^{\widehat{\pi}}\leq
2\varepsilon+\widehat{V}^{\pi}-\widehat{V}^{\widehat{\pi}}\leq 2\varepsilon.$

Rescaling $\varepsilon$ by $2\varepsilon$ and $\delta$ by $2\delta$ concludes
the proof of Theorem 4.∎

###  F.4 Sunflower Property is Insufficient By Itself

We give an example of a policy class $\Pi$ for which the sunflower property
holds for $K,D=\mathrm{poly}(H)$ but $\mathfrak{C}(\Pi)=2^{H}$. Therefore, in
light of Theorem 2, the sunflower property by itself cannot ensure
statistically efficient agnostic PAC RL in the online access model.

The example is as follows: Consider a binary tree MDP with $2^{H}-1$ states
and action space $\mathcal{A}=\\{0,1\\}$. The policy class $\Pi$ will be able
to get to every $(s,a)$ pair in layer $H$. To define the policies, we consider
each possible trajectory $\tau=(s_{1},a_{1},\cdots,s_{H},a_{H})$ and let:

$\displaystyle\Pi\coloneqq\left\\{\pi_{\tau}:\pi_{\tau}(s)=\begin{cases}a_{i}&\text{if
}s_{i}\in\tau,\\\ 0&\text{otherwise},\end{cases}\right\\}.$

Thus it is clear that $\mathfrak{C}(\Pi)=2^{H}$, but the sunflower property
holds with $K=1$, $D=H$ by taking $\Pi_{\mathrm{core}}=\\{\pi_{0}\\}$ (the
policy which always picks $a=0$).

##  Appendix G Infinite Policy Classes

In this section we discuss the extensions of our results to infinite policy
classes.

###  G.1 Definitions and Preliminary Lemmas

We will state our results in terms of the Natarajan dimension, which is a
generalization of the VC dimension used to study multiclass learning. We note
that the results in this section could be stated in terms of other complexity
measures from multiclass learning such as the graph dimension and DS dimension
(see, e.g., Natarajan, 1989; Shalev-Shwartz and Ben-David, 2014; Daniely and
Shalev-Shwartz, 2014; Brukhim et al., 2022a); for simplicity we analyze
guarantees in terms of the Natarajan dimension.

######  Definition 7 (Natarajan Dimension (Natarajan, 1989)).

Let $\mathcal{X}$ be an instance space and $\mathcal{Y}$ be a finite label
space. Given a class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$, we
define its _Natarajan dimension_ , denoted $\mathrm{Ndim}(\mathcal{H})$, to be
the maximum cardinality of a set $C\subseteq\mathcal{X}$ that satisfies the
following: there exists $h_{0},h_{1}:C\to\mathcal{Y}$ such that (1) for all
$x\in C$, $h_{0}(x)\neq h_{1}(x)$, and (2) for all $B\subseteq C$, there
exists $h\in\mathcal{H}$ such that for all $x\in B$, $h(x)=h_{0}(x)$ and for
all $x\in C\backslash B$, $h(x)=h_{1}(x)$.

A notation we will use throughout is the projection operator. For a hypothesis
class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ and a finite set
$X=(x_{1},\cdots,x_{n})\in\mathcal{X}^{n}$, we define the projection of
$\mathcal{H}$ on to $X$ as

$\displaystyle\mathcal{H}\big{|}_{X}\coloneqq\left\\{\left(h(x_{1}),\cdots,h(x_{n})\right):h\in\mathcal{H}\right\\}.$

######  Lemma 15 (Sauer’s Lemma for Natarajan Classes (Haussler and Long,
1995)).

Given a hypothesis class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ with
$\lvert\mathcal{Y}\rvert=K$ and $\mathrm{Ndim}(\mathcal{H})\leq d$, we have
for every $X=(x_{1},\cdots,x_{n})\in\mathcal{X}^{n}$,

$\displaystyle\Big{\lvert}\mathcal{H}\big{|}_{X}\Big{\rvert}\leq\left(\frac{ne(K+1)^{2}}{2d}\right)^{d}.$

######  Theorem 6 (Multiclass Fundamental Theorem (Shalev-Shwartz and Ben-
David, 2014)).

For any class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ with
$\mathrm{Ndim}(\mathcal{H})=d$ and $\lvert\mathcal{Y}\rvert=K$, the minimax
sample complexity of $(\varepsilon,\delta)$ agnostic PAC learning
$\mathcal{H}$ can be bounded as

$\displaystyle\Omega\left(\frac{d+\log(1/\delta)}{\varepsilon^{2}}\right)\leq
n(\Pi;\varepsilon,\delta)\leq\mathcal{O}\left(\frac{d\log
K+\log(1/\delta)}{\varepsilon^{2}}\right).$

######  Definition 8 (Pseudodimension).

Let $\mathcal{X}$ be an instance space. Given a hypothesis class
$\mathcal{H}\subseteq\mathbb{R}^{\mathcal{X}}$, its pseudodimension, denoted
$\mathrm{Pdim}(\mathcal{H})$, is defined as
$\mathrm{Pdim}(\mathcal{H})\coloneqq\mathrm{VC}(\mathcal{H}^{+})$, where
$\mathcal{H}^{+}\coloneqq\left\\{(x,\theta)\mapsto\mathbbm{1}\left\\{h(x)\leq\theta\right\\}:h\in\mathcal{H}\right\\}$.

######  Definition 9 (Covering Numbers).

Given a hypothesis class $\mathcal{H}\subseteq\mathbb{R}^{\mathcal{X}}$,
$\alpha>0$, and $X=(x_{1},\cdots,x_{n})\in\mathcal{X}^{n}$, the covering
number $\mathcal{N}_{1}(\mathcal{H},\alpha,X)$ is the minimum cardinality of a
set $C\subset\mathbb{R}^{n}$ such that for any $h\in\mathcal{H}$ there exists
a $c\in C$ such that $\tfrac{1}{n}\sum_{i=1}^{n}\lvert
h(x_{i})-c_{i}\rvert\leq\alpha$.

######  Lemma 16 (Jiang et al. (2017), see also Pollard (2012); Luc et al.
(1996)).

Let $\mathcal{H}\subset[0,1]^{\mathcal{X}}$ be a real-valued hypothesis class,
and let $X=\left(x_{1},\cdots,x_{n}\right)$ be i.i.d. samples drawn from some
distribution $\mathcal{D}$ on $\mathcal{X}$. Then for any $\alpha>0$

$\displaystyle\operatorname{\mathbb{P}}\left[\sup_{h\in\mathcal{H}}\left\lvert\frac{1}{n}\sum_{i=1}^{n}h(x_{i})-\mathbb{E}[h(x)]\right\rvert>\alpha\right]\leq
8\mathbb{E}\left[\mathcal{N}_{1}(\mathcal{H},\alpha/8,X)\right]\cdot\exp\left(-\frac{n\alpha^{2}}{128}\right).$

Furthermore if $\mathrm{Pdim}(\mathcal{H})\leq d$ then we have the bound

$\displaystyle\operatorname{\mathbb{P}}\left[\sup_{h\in\mathcal{H}}\left\lvert\frac{1}{n}\sum_{i=1}^{n}h(x_{i})-\mathbb{E}[h(x)]\right\rvert>\alpha\right]\leq
8e(d+1)\left(\frac{16e}{\alpha}\right)^{d}\cdot\exp\left(-\frac{n\alpha^{2}}{128}\right),$

which is at most $\delta$ as long as
$n\geq\tfrac{128}{\alpha^{2}}\left(d\log\tfrac{16e}{\alpha}+\log(8e(d+1))+\log\frac{1}{\delta}\right)$.

###  G.2 Generative Model Lower Bound

First we address the lower bound. Observe that it is possible to achieve a
lower bound that depends on $\mathrm{Ndim}(\Pi)$ with the following
construction. First, identify the layer $h\in[H]$ such that the witnessing set
$C$ contains the maximal number of states in $\mathcal{S}_{h}$; by pigeonhole
principle there must be at least $\mathrm{Ndim}(\Pi)/H$ such states in layer
$h$. Then, we construct an MDP which “embeds” a hard multiclass learning
problem at layer $h$ over these states. A lower bound of
$\Omega\left(\tfrac{\mathrm{Ndim}(\Pi)}{H\varepsilon^{2}}\cdot\log\tfrac{1}{\delta}\right)$
follows from Theorem 6.

By combining Theorem 2 with the above we get the following corollary.

######  Corollary 3 (Lower Bound for Generative Model with Infinite Policy
Classes).

For any policy class $\Pi$, the minimax sample complexity
$(\varepsilon,\delta)$-PAC learning $\Pi$ is at least

$\displaystyle
n_{\mathsf{gen}}(\Pi;\varepsilon,\delta)\geq\Omega\left(\frac{\mathfrak{C}(\Pi)+\mathrm{Ndim}(\Pi)/H}{\varepsilon^{2}}\cdot\log\frac{1}{\delta}\right).$

Again, since the generative model setting is easier than online RL, this lower
bound also extends to the online RL setting.

Our bound is additive in $\mathfrak{C}(\Pi)$ and $\mathrm{Ndim}(\Pi)$; we do
not know if it is possible to strengthen this to be a product of the two
factors, as we will achieve in the upper bound in the next section.

###  G.3 Generative Model Upper Bound

For the upper bounds, we can replace the dependence on $\log\lvert\Pi\rvert$
with $\mathrm{Ndim}(\Pi)$ (and additional log factors). In particular, we can
modify the analysis of the $\mathsf{TrajectoryTree}$ to account for infinite
policy classes. Recall that our analysis of $\mathsf{TrajectoryTree}$ required
us to prove a uniform convergence guarantee for the estimate
$\widehat{V}^{\pi}$: with probability at least $1-\delta$, for all
$\pi\in\Pi$, we have
$\lvert\widehat{V}^{\pi}-V^{\pi}\rvert\lesssim\varepsilon$. We previously used
a union bound over $\lvert\Pi\rvert$, which gave us the $\log\lvert\Pi\rvert$
dependence. Now we sketch an argument to replace it with $\mathrm{Ndim}(\Pi)$.

Let $\mathcal{T}$ be the set of all possible trajectory trees. We introduce
the notation $v^{\pi}:\mathcal{T}\to\mathbb{R}$ to denote the function that
takes as input a trajectory tree $\widehat{T}$ (for example, as sampled by
$\mathsf{TrajectoryTree}$) and returns the value of running $\pi$ on it. Then
we can rewrite the desired uniform convergence guarantee:

$\displaystyle\text{w.p.\leavevmode\nobreak\ at least}\leavevmode\nobreak\
1-\delta,\quad\sup_{\pi\in\Pi}\leavevmode\nobreak\
\left\lvert\frac{1}{n}\sum_{i=1}^{n}v^{\pi}(\widehat{T}_{i})-\mathbb{E}\left[v^{\pi}(\widehat{T})\right]\right\rvert\leq\varepsilon.$
(28)

In light of Lemma 16, we will compute the pseudodimension for the function
class $\mathcal{V}^{\Pi}=\left\\{v^{\pi}:\pi\in\Pi\right\\}$. Define the
subgraph class

$\displaystyle\mathcal{V}^{\Pi,+}\coloneqq\left\\{(\widehat{T},\theta)\mapsto\mathbbm{1}\left\\{v^{\pi}(\widehat{T})\leq\theta\right\\}:\pi\in\Pi\right\\}\subseteq\\{0,1\\}^{\mathcal{T}\times\mathbb{R}}$

By definition,
$\mathrm{Pdim}(\mathcal{V}^{\Pi})=\mathrm{VC}(\mathcal{V}^{\Pi,+})$. Fix any
$X=\left\\{(\widehat{T}_{1},\theta_{1}),\cdots,(\widehat{T}_{d},\theta_{d})\right\\}\in(\mathcal{T}\times\mathbb{R})^{d}$.
In order to show that $\mathrm{VC}(\mathcal{V}^{\Pi,+})\leq d$ for some value
of $d$ it suffices to prove that
$\lvert\mathcal{V}^{\Pi,+}\big{|}_{X}\rvert<2^{d}$.

For any index $t\in[d]$, we also denote $\pi(\vec{s}_{i})\in\mathcal{A}^{\leq
H\mathfrak{C}(\Pi)}$ to be the vector of actions selected by $\pi$ on all
$\Pi$-reachable states in $\widehat{T}_{i}$ (of which there are at most
$H\cdot\mathfrak{C}(\Pi)$). We claim that

$\displaystyle\Big{\lvert}\mathcal{V}^{\Pi,+}\big{|}_{X}\Big{\rvert}\leq\left\lvert\left\\{\left(\pi(\vec{s}_{1}),\cdots,\pi(\vec{s}_{d})\right):\pi\in\Pi\right\\}\right\rvert=:\Big{\lvert}\Pi\big{|}_{X}\Big{\rvert}.$
(29)

This is true because once the $d$ trajectory trees are fixed, for every
$\pi\in\Pi$, the value of the vector
$\mathcal{V}^{\\{\pi\\},+}\big{|}_{X}\in\\{0,1\\}^{d}$ is determined by the
trajectory that $\pi$ takes in every trajectory tree. This in turn is
determined by the assignment of actions to every reachable state in all the
$d$ trajectory trees, of which there are at most $\mathfrak{C}(\Pi)\cdot
H\cdot d$ of. Therefore, we can upper bound the size of
$\mathcal{V}^{\Pi,+}\big{|}_{X}$ by the number of ways any $\pi\in\Pi$ assign
actions to every state in $\widehat{T}_{1},\cdots,\widehat{T}_{d}$.

Applying Lemma 15 to Eq. (29), we get that

$\displaystyle\Big{\lvert}\mathcal{V}^{\Pi,+}\big{|}_{X}\Big{\rvert}\leq\left(\frac{H\mathfrak{C}(\Pi)d\cdot
e\cdot(A+1)^{2}}{2\mathrm{Ndim}(\Pi)}\right)^{\mathrm{Ndim}(\Pi)}.$

For the choice of $d=\widetilde{\mathcal{O}}\left(\mathrm{Ndim}(\Pi)\right)$,
the previous display is at most $2^{d}$, thus proving the bound on
$\mathrm{Pdim}(\mathcal{V}^{\Pi})$. Lastly, the bound can be plugged back into
Lemma 16 to get a bound on the error of $\mathsf{TrajectoryTree}$: the
statement in Eq. (28) holds using

$\displaystyle
n=\widetilde{\mathcal{O}}\left(H\mathfrak{C}(\Pi)\cdot\frac{\mathrm{Ndim}(\Pi)+\log\frac{1}{\delta}}{\varepsilon^{2}}\right)\quad\text{samples}.$

This in turn yields a guarantee on $\widehat{\pi}$ returned by
$\mathsf{TrajectoryTree}$.

###  G.4 Online RL Upper Bound

The modified analysis for the online RL upper bound (Theorem 4) proceeds
similarly; we sketch the ideas below.

There are two places in the proof of Theorem 4 which require a union bound
over $\lvert\Pi\rvert$: the event $\mathcal{E}_{\mathrm{est}}$ (defined by
Lemma 10) that the estimated transitions and rewards of the MRPs are close to
their population versions, and the event $\mathcal{E}_{\mathrm{data}}$
(defined by Lemma 12) that the datasets collected are large enough. The latter
is easy to address, since we can simply modify the algorithm’s while loop to
break after $\mathcal{O}\left(\tfrac{HD\mathfrak{C}(\Pi)}{\varepsilon}\right)$
iterations and union bound over the size of the set $\lvert\mathcal{T}\rvert$
instead of the worst-case bound on the size $D\lvert\Pi\rvert$. For
$\mathcal{E}_{\mathrm{data}}$, we follow a similar strategy as the analysis
for the generative model upper bound.

Fix a state $s$. Recall that the estimate for the probability transition
kernel in the MDP in Eq. (19) takes the form

$\displaystyle\widehat{P}_{s\to
s^{\prime}}^{\pi}=\frac{1}{|\mathcal{D}_{s}|}\sum_{\tau\in\mathcal{D}_{s}}\frac{\mathbbm{1}\left\\{\pi\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}{\tfrac{1}{|\Pi_{\mathrm{core}}|}\sum_{\pi^{\prime}\in\Pi_{\mathrm{core}}}\mathbbm{1}\left\\{\pi_{e}\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}\mathbbm{1}\left\\{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\}.$

(The analysis for the rewards is similar, so we omit it from this proof
sketch.)

We set up some notation. Define the function $p^{\pi}_{s\to
s^{\prime}}:(\mathcal{S}\times\mathcal{A}\times\mathbb{R})^{H}\to[0,\lvert\Pi_{\mathrm{core}}\rvert]$
as

$\displaystyle p^{\pi}_{s\to
s^{\prime}}(\tau)\coloneqq\frac{\mathbbm{1}\left\\{\pi\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}{\tfrac{1}{|\Pi_{\mathrm{core}}|}\sum_{\pi^{\prime}\in\Pi_{\mathrm{core}}}\mathbbm{1}\left\\{\pi_{e}\rightsquigarrow\tau_{h:h^{\prime}}\right\\}}\mathbbm{1}\left\\{\tau\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\},$ (30)

with the implicit restriction of the domain to trajectories $\tau$ for which
the denominator is nonzero. We have $\mathbb{E}[p^{\pi}_{s\to
s^{\prime}}(\tau)]=P^{\pi}_{s\rightarrow s^{\prime}}$. Also let
$\Pi_{s}=\left\\{\pi\in\Pi:s\in\mathcal{S}_{\pi}\right\\}$.

Restated in this notation, our objective is to show the uniform convergence
guarantee

$\displaystyle\text{w.p.\leavevmode\nobreak\ at least}\leavevmode\nobreak\
1-\delta,\quad\sup_{\pi\in\Pi_{s},s^{\prime}\in\mathcal{S}_{\pi}}\Big{|}\frac{1}{|\mathcal{D}_{s}|}\sum_{\tau\in\mathcal{D}_{s}}p^{\pi}_{s\to
s^{\prime}}(\tau)-\mathbb{E}[p^{\pi}_{s\to
s^{\prime}}(\tau)]\Big{|}\leq\varepsilon.$ (31)

Again, in light of Lemma 16, we need to compute the pseudodimension for the
function class $\mathcal{P}^{\Pi_{s}}=\left\\{p^{\pi}_{s\to
s^{\prime}}:\pi\in\Pi_{s},s^{\prime}\in\mathcal{S}_{\pi}\right\\}$, since
these are all possible transitions that we might use the dataset
$\mathcal{D}_{s}$ to evaluate. Define the subgraph class

$\displaystyle\mathcal{P}^{\Pi_{s},+}\coloneqq\\{(\tau,\theta)\mapsto\mathbbm{1}\left\\{p^{\pi}_{s\to
s^{\prime}}(\tau)\leq\theta\right\\}:\pi\in\Pi_{s},s^{\prime}\in\mathcal{S}_{\pi}\\}.$

Fix the set
$X=\left\\{(\tau_{1},\theta_{1}),\cdots,(\tau_{d},\theta_{d})\right\\}\in((\mathcal{S}\times\mathcal{A}\times\mathbb{R})^{H}\times\mathbb{R})^{d}$,
where the trajectories $\tau_{1},\cdots,\tau_{d}$ pass through $s$. We also
denote $\mathcal{S}_{X}$ to be the union of all states which appear in
$\tau_{1},\cdots,\tau_{d}$. In order to show a bound that
$\mathrm{Pdim}(\mathcal{P}^{\Pi_{s}})\leq d$ it suffices to prove that
$\lvert\mathcal{P}^{\Pi_{s},+}\big{|}_{X}\rvert<2^{d}$.

We first observe that

$\displaystyle\lvert\mathcal{P}^{\Pi_{s},+}\big{|}_{X}\rvert$
$\displaystyle\leq
1+\sum_{s^{\prime}\in\mathcal{S}_{X}}\left\lvert\left\\{\left(\mathbbm{1}\left\\{p^{\pi}_{s\to
s^{\prime}}(\tau_{1})\leq\theta_{1}\right\\},\cdots,\mathbbm{1}\left\\{p^{\pi}_{s\to
s^{\prime}}(\tau_{d})\leq\theta_{d}\right\\}\right):\pi\in\Pi_{s}\right\\}\right\rvert.$

The inequality follows because for any choice
$s^{\prime}\notin\mathcal{S}_{X}$, we have

$\displaystyle\left(\mathbbm{1}\left\\{p^{\pi}_{s\to
s^{\prime}}(\tau_{1})\leq\theta_{1}\right\\},\cdots,\mathbbm{1}\left\\{p^{\pi}_{s\to
s^{\prime}}(\tau_{d})\leq\theta_{d}\right\\}\right)=\vec{0},$

no matter what $\pi$ is, contributing at most 1 to the count. Furthermore,
once we have fixed $s^{\prime}$ and the $\\{\tau_{1},\cdots,\tau_{d}\\}$ the
quantities
$\tfrac{1}{|\Pi_{\mathrm{core}}|}\sum_{\pi^{\prime}\in\Pi_{\mathrm{core}}}\mathbbm{1}\left\\{\pi_{e}\rightsquigarrow\tau_{i,h:h^{\prime}}\right\\}$
for every $i\in[d]$ are constant (do not depend on $\pi$), so we can
reparameterize
$\theta_{i}^{\prime}\coloneqq\theta_{i}\cdot\tfrac{1}{|\Pi_{\mathrm{core}}|}\sum_{\pi^{\prime}\in\Pi_{\mathrm{core}}}\mathbbm{1}\left\\{\pi_{e}\rightsquigarrow\tau_{i,h:h^{\prime}}\right\\}$
to get:

$\displaystyle\lvert\mathcal{P}^{\Pi_{s},+}\big{|}_{X}\rvert$
$\displaystyle\leq
1+\sum_{s^{\prime}\in\mathcal{S}_{X}}\left\lvert\left\\{(b_{1}(\pi),\cdots,b_{d}(\pi)):\pi\in\Pi\right\\}\right\rvert,$
(32) $\displaystyle\quad\text{where}\quad
b_{i}(\pi)\coloneqq\mathbbm{1}\left\\{\mathbbm{1}\left\\{\pi\rightsquigarrow\tau_{i,h:h^{\prime}}\right\\}\mathbbm{1}\left\\{\tau_{i}\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\}\leq\theta_{i}^{\prime}\right\\}.$

Now we count how many values the vector $(b_{1}(\pi),\cdots,b_{d}(\pi))$ can
take for different $\pi\in\Pi_{s}$. Without loss of generality, we can (1)
assume that the $\theta_{i}^{\prime}=0$ (since a product of indicators can
only take values in $\\{0,1\\}$, and if $\theta^{\prime}\geq 1$ then we must
have $b_{i}(\pi)=1$ for every $\pi$), and (2) $s^{\prime}\in\tau_{i}$ for each
$i\in[d]$ (otherwise $b_{i}(\pi)=0$ for every $\pi\in\Pi$). So we can rewrite
$b_{i}(\pi)=\mathbbm{1}\left\\{\pi\rightsquigarrow\tau_{i,h:h^{\prime}}\right\\}\mathbbm{1}\left\\{\tau_{i}\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\}$. For every fixed choice of $s^{\prime}$ we upper bound
the size of the set as:

$\displaystyle\left\lvert\left\\{\left(b_{1}(\pi),\cdots,b_{d}(\pi)\right):\pi\in\Pi\right\\}\right\rvert$
$\displaystyle\overset{\left(i\right)}{\leq{}}$
$\displaystyle\left\lvert\left\\{\left(\mathbbm{1}\left\\{\pi\rightsquigarrow\tau_{1,h:h^{\prime}}\right\\},\cdots,\mathbbm{1}\left\\{\pi\rightsquigarrow\tau_{d,h:h^{\prime}}\right\\}\right):\pi\in\Pi\right\\}\right\rvert$
$\displaystyle\quad\quad\times\left\lvert\left\\{\left(\mathbbm{1}\left\\{\tau_{1}\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\},\cdots,\mathbbm{1}\left\\{\tau_{d}\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\}\right):\pi\in\Pi\right\\}\right\rvert$
$\displaystyle\overset{\left(ii\right)}{\leq{}}$
$\displaystyle\left\lvert\left\\{\left(\pi(s^{(1)}),\pi(s^{(2)}),\cdots,\pi(s^{(dH)})\right):\pi\in\Pi\right\\}\right\rvert\times\left\lvert\left\\{\left(\mathbbm{1}\left\\{s^{(1)}\in\mathcal{S}_{\pi}\right\\},\cdots,\mathbbm{1}\left\\{s^{(dH)}\in\mathcal{S}_{\pi}\right\\}\right):\pi\in\Pi\right\\}\right\rvert$
$\displaystyle\overset{\left(iii\right)}{\leq{}}$
$\displaystyle\left(\frac{dH\cdot
e(A+1)^{2}}{2\mathrm{Ndim}(\Pi)}\right)^{\mathrm{Ndim}(\Pi)}\times(dH)^{D}.$
(33)

The inequality $\left(i\right)$ follows by upper bounding by the Cartesian
product. The inequality $\left(ii\right)$ follows because (1) for the first
term, the vector
$\left(\mathbbm{1}\left\\{\pi\rightsquigarrow\tau_{1,h:h^{\prime}}\right\\},\cdots,\mathbbm{1}\left\\{\pi\rightsquigarrow\tau_{d,h:h^{\prime}}\right\\}\right)$
is determined by the number of possible behaviors $\pi$ has over all $dH$
states in the trajectories, and (2) for the second term, the vector
$\left(\mathbbm{1}\left\\{\tau_{1}\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\},\cdots,\mathbbm{1}\left\\{\tau_{d}\in\mathfrak{T}_{\pi}(s\rightarrow
s^{\prime})\right\\}\right)$ is determined by which of the $dH$ states lie in
the petal set for $\mathcal{S}_{\pi}$. The inequality $\left(iii\right)$
follows by applying Lemma 15 to the first term and Sauer’s Lemma to the second
term, further noting that every petal $\mathcal{S}_{\pi}$ set has cardinality
at most $D$.

Combining Eqs. (32) and (33) we get the final bound that

$\displaystyle\lvert\mathcal{P}^{\Pi_{s},+}\big{|}_{X}\rvert$
$\displaystyle\leq 1+(dH)^{D+1}\cdot\left(\frac{dH\cdot
e(A+1)^{2}}{2\mathrm{Ndim}(\Pi)}\right)^{\mathrm{Ndim}(\Pi)}.$

To conclude the calculation, we observe that this bound is $<2^{d}$ whenever
$d=\widetilde{\mathcal{O}}(D+\mathrm{Ndim}(\Pi))$, which we can again use in
conjunction with Lemma 16 to prove the desired uniform convergence statement
found in Eq. (31). Ultimately this allows us to replace the
$\log\lvert\Pi\rvert$ with $\widetilde{\mathcal{O}}(D+\mathrm{Ndim}(\Pi))$ in
the upper bound of Theorem 4; the precise details are omitted.

##  Appendix H Connections to Other Complexity Measures

We show relationships between the spanning capacity and several other
combinatorial measures of complexity.

For every $h\in[H]$ we denote the state space at layer $h$ as
$\mathcal{S}_{h}\coloneqq\\{s_{(j,h)}:j\in[K]\\}$ for some $K\in\mathbb{N}$.
We will restrict ourselves to binary action spaces $\mathcal{A}=\\{0,1\\}$,
but the definitions and results can be extended to larger (but finite) action
spaces. In addition, we will henceforth assume that all policy classes $\Pi$
under consideration satisfy the following stationarity assumption.

######  Assumption 1.

The policy class $\Pi$ satisfies _stationarity_ : for every $\pi\in\Pi$ we
have

$\displaystyle\pi(s_{(j,1)})=\pi(s_{(j,2)})=\cdots=\pi(s_{(j,H)})\quad\text{for
every}\leavevmode\nobreak\ j\in[K].$

For any $\pi\in\Pi$ and $j\in[K]$, we use $\pi(j)$ as a shorthand to denote
the value of $\pi(s_{(j,h)})$ for every $h$.

The stationarity assumption is not required but is useful for simplifying the
definitions and results.

###  H.1 Definitions and Relationships

First, we state several complexity measures in learning theory. For further
discussion on these quantities, see (Foster et al., 2021c; Li et al., 2022).

######  Definition 10 (Combinatorial Eluder Dimension).

Fix any stationary base policy $\bar{\pi}$. The _combinatorial eluder
dimension_ of $\Pi$ w.r.t. $\bar{\pi}$, denoted
$\mathrm{dim}_{\mathsf{E}}(\Pi;\bar{\pi})$, is the length of the longest
sequence $(j_{1},\pi_{1}),\dots,(j_{N},\pi_{N})$ such that for every
$\ell\in[N]$:

$\displaystyle\pi_{\ell}(j_{\ell})\neq\bar{\pi}(j_{\ell}),\quad\text{and}\quad{\forall
k<\ell},\leavevmode\nobreak\ \pi_{\ell}(j_{k})=\bar{\pi}(j_{k}).$

We define the combinatorial eluder dimension of $\Pi$ as
$\mathrm{dim}_{\mathsf{E}}(\Pi)\coloneqq\sup_{\pi\in\Pi}\mathrm{dim}_{\mathsf{E}}(\Pi;\bar{\pi})$.888Our
definition of the combinatorial eluder dimension comes from Li et al. (2022)
and is also called the “policy eluder dimension” in the paper Foster et al.
(2021c). In particular, it is defined with respect to a base function
$\bar{\pi}$. This differs in spirit from the original definition (Russo and
Van Roy, 2013) as well as the combinatorial variant (Mou et al., 2020), which
for every $\ell$ asks for witnessing _pairs_ of policies
$\pi_{\ell},\pi_{\ell}^{\prime}$. Our definition is never larger than the
original version since we require that $\pi_{\ell}^{\prime}=\bar{\pi}$ to be
fixed for every $\ell\in[N]$.

######  Definition 11 (Star Number (Hanneke and Yang, 2015)).

Fix any stationary base policy $\bar{\pi}$. The _star number_ of $\Pi$ w.r.t.
$\bar{\pi}$, denoted $\mathrm{dim}_{\mathsf{S}}(\Pi;\bar{\pi})$, is the length
of the longest sequence $(j_{1},\pi_{1}),\dots,(j_{N},\pi_{N})$ such that for
every $\ell\in[N]$:

$\displaystyle\pi_{\ell}(j_{\ell})\neq\bar{\pi}(j_{\ell}),\quad\text{and}\quad{\forall
k\neq\ell},\leavevmode\nobreak\ \pi_{\ell}(j_{k})=\bar{\pi}(j_{k}).$

We define the star number of $\Pi$ as
$\mathrm{dim}_{\mathsf{S}}(\Pi)\coloneqq\sup_{\pi\in\Pi}\mathrm{dim}_{\mathsf{S}}(\Pi;\bar{\pi})$.

######  Definition 12 (Threshold Dimension (Alon et al., 2019; Li et al.,
2022)).

Fix any stationary base policy $\bar{\pi}$. The _threshold dimension_ of $\Pi$
w.r.t. $\bar{\pi}$, denoted $\mathrm{dim}_{\mathsf{T}}(\Pi;\bar{\pi})$, is the
length of the longest sequence $(j_{1},\pi_{1}),\dots,(j_{N},\pi_{N})$ such
that for every $\ell\in[N]$:

$\displaystyle{\forall m\geq\ell},\leavevmode\nobreak\
\pi_{\ell}(j_{m})\neq\bar{\pi}(j_{m}),\quad\text{and}\quad{\forall
k<\ell},\leavevmode\nobreak\ \pi_{\ell}(j_{k})=\bar{\pi}(j_{k}).$

We define the threshold dimension of $\Pi$ as
$\mathrm{dim}_{\mathsf{T}}(\Pi)\coloneqq\sup_{\pi\in\Pi}\mathrm{dim}_{\mathsf{T}}(\Pi;\bar{\pi})$.

##### Relationships Between Complexity Measures.

From (Li et al., 2022, Theorem 8) we have the relationship for every $\Pi$:

$\displaystyle\max\left\\{\mathrm{dim}_{\mathsf{S}}(\Pi),\mathrm{dim}_{\mathsf{T}}(\Pi)\right\\}\leq\mathrm{dim}_{\mathsf{E}}(\Pi)\leq
4^{\max\left\\{\mathrm{dim}_{\mathsf{S}}(\Pi),\mathrm{dim}_{\mathsf{T}}(\Pi)\right\\}}.$
(34)

The lower bound is obvious from the definitions and in general cannot be
improved; the upper bound also cannot be improved beyond constant factors in
the exponent (Li et al., 2022).

We also remark that it is clear from the definitions that VC dimension is a
lower bound on all three (eluder, star, threshold); however,
$\mathrm{VC}(\Pi)$ can be arbitrarily smaller.

###  H.2 Bounds on Spanning Capacity

Now we investigate bounds on the spanning capacity in terms of the
aforementioned quantities.

######  Theorem 7.

For any policy class $\Pi$ satisfying Assumption 1 we have

$\displaystyle\max\left\\{\leavevmode\nobreak\
\min\left\\{\mathrm{dim}_{\mathsf{S}}(\Pi),H+1\right\\},\leavevmode\nobreak\
\min\left\\{2^{\lfloor\log_{2}\mathrm{dim}_{\mathsf{T}}(\Pi)\rfloor},2^{H}\right\\}\leavevmode\nobreak\
\right\\}\leq\mathfrak{C}(\Pi)\leq 2^{\mathrm{dim}_{\mathsf{E}}(\Pi)}.$

We give several remarks on Theorem 7. The proof is deferred to the following
subsection.

It is interesting to understand to what degree we can improve the bounds in
Theorem 7. On the lower bound side, we note that the each of the terms
individually cannot be sharpened:

  * •

For the singleton class $\Pi_{\mathrm{sing}}$ we have
$\mathfrak{C}(\Pi_{\mathrm{sing}})=\min\\{K,H+1\\}$ and
$\mathrm{dim}_{\mathsf{S}}(\Pi_{\mathrm{sing}})=K$.

  * •

For the threshold class
$\Pi_{\mathrm{thres}}\coloneqq\\{\pi_{i}(j)\mapsto\mathbbm{1}\left\\{j\geq
i\right\\}:i\in[K]\\}$, when $K$ is a power of two, it can be shown that
$\mathfrak{C}(\Pi_{\mathrm{thres}})=\min\\{K,2^{H}\\}$ and
$\mathrm{dim}_{\mathsf{T}}(\Pi_{\mathrm{thres}})=K$.

While we also provide an upper bound in terms of
$\mathrm{dim}_{\mathsf{E}}(\Pi)$, we note that there can be a huge gap between
the lower bound and the upper bound. In fact, our upper bound is likely very
loose since we are not aware of any policy class for which the upper bound is
non-vacuous, i.e.
$2^{\mathrm{dim}_{\mathsf{E}}(\Pi)}\ll\min\left\\{2^{H},\lvert\Pi\rvert,2KH\right\\}$
(implying that our bound improves on Proposition 3). It would be interesting
to understand how to improve the upper bound (possibly, to scale polynomially
with $\mathrm{dim}_{\mathsf{E}}(\Pi)$, or more directly in terms of some
function of $\mathrm{dim}_{\mathsf{S}}(\Pi)$ and
$\mathrm{dim}_{\mathsf{T}}(\Pi)$); we leave this as a direction for future
research.

Lastly, we remark that the lower bound of
$\mathfrak{C}(\Pi)\geq\min\\{\Omega(\mathrm{dim}_{\mathsf{T}}(\Pi)),2^{H}\\}$
is a generalization of previous bounds which show that linear policies cannot
be learned with $\mathrm{poly}(H)$ sample complexity (e.g., Du et al., 2019b),
since linear policies (even in 2 dimensions) have infinite threshold
dimension.

####  H.2.1 Proof of Theorem 7

We will prove each bound separately.

Star Number Lower Bound. Let $\bar{\pi}\in\Pi$ and the sequence
$(j_{1},\pi_{1}),\dots,(j_{N},\pi_{N})$ witness
$\mathrm{dim}_{\mathsf{S}}(\Pi)=N$. We construct a deterministic MDP $M$ for
which the cumulative reachability at layer
$h_{\mathrm{max}}\coloneqq\min\\{N,H\\}$ (Definition 1) is at least
$\min\\{N,H+1\\}$. The transition dynamics of $M$ are as follows; we will only
specify the transitions until $h_{\mathrm{max}}-1$ (afterwards, the
transitions can be arbitrary).

  * •

The starting state of $M$ at layer $h=1$ is $s_{(j_{1},1)}$.

  * •

(On-Chain Transitions): For every $h<h_{\mathrm{max}}$,

$\displaystyle P(s^{\prime}\mid s_{(j_{h},h)},a)$
$\displaystyle=\begin{cases}\mathbbm{1}\left\\{s^{\prime}=s_{(j_{h+1},h+1)}\right\\}&\text{if}\leavevmode\nobreak\
a=\bar{\pi}(s_{(j_{h},h)}),\\\\[5.0pt]
\mathbbm{1}\left\\{s^{\prime}=s_{(j_{h},h+1)}\right\\}&\text{if}\leavevmode\nobreak\
a\neq\bar{\pi}(s_{(j_{h},h)}).\end{cases}$

  * •

(Off-Chain Transitions): For every $h<h_{\mathrm{max}}$, state index
$\tilde{j}\neq j_{h}$, and action $a\in\mathcal{A}$,

$\displaystyle P(s^{\prime}\mid
s_{(\tilde{j},h)},a)=\mathbbm{1}\left\\{s^{\prime}=s_{(\tilde{j},h+1)}\right\\}.$

We now compute the cumulative reachability at layer $h_{\mathrm{max}}$. If
$N\leq H$, the the number of $(s,a)$ pairs that $\Pi$ can reach in $M$ is $N$
(namely the pairs $(s_{(j_{1},N)},1),\cdots,(s_{(j_{N},N)},1)$). On the other
hand, if $N>H$, then the number of $(s,a)$ pairs that $\Pi$ can reach in $M$
is $H+1$ (namely the pairs
$(s_{(j_{1},H)},1),\cdots,(s_{(j_{H},H)},1),(s_{(j_{H},H)},0)$). Thus we have
shown that $\mathfrak{C}(\Pi)\geq\min\\{N,H+1\\}$.

Threshold Dimension Lower Bound. Let $\bar{\pi}\in\Pi$ and the sequence
$(j_{1},\pi_{1}),\dots,(j_{N},\pi_{N})$ witness
$\mathrm{dim}_{\mathsf{T}}(\Pi)=N$. We define a deterministic MDP $M$ as
follows. Set $h_{\mathrm{max}}=\min\\{\lfloor\log_{2}N\rfloor,H\\}$. Up until
layer $h_{\mathrm{max}}$, the MDP will be a full binary tree of depth
$h_{\mathrm{max}}$; afterward, the transitions will be arbitrary. It remains
to assign state labels to the nodes of the binary tree (of which there are
$2^{h_{\mathrm{max}}}-1\leq N$). We claim that it is possible to do so in a
way so that every policy $\pi_{\ell}$ for $\ell\in[2^{h_{\mathrm{max}}}]$
reaches a different state-action pair at layer $h_{\mathrm{max}}$. Therefore
the cumulative reachability of $\Pi$ on $M$ is at least
$2^{h_{\mathrm{max}}}=\min\\{2^{\lfloor\log_{2}N\rfloor},2^{H}\\}$ as claimed.

It remains to prove the claim. The states of $M$ are labeled
$j_{2},\cdots,j_{2^{h_{\mathrm{max}}}}$ according to the order they are
traversed using inorder traversal of a full binary tree of depth
$h_{\mathrm{max}}$ (Cormen et al., 2022). One can view the MDP $M$ as a binary
search tree where the action 0 corresponds to going left and the action 1
corresponds to going right. Furthermore, if we imagine that the leaves of the
binary search tree at depth $h_{\mathrm{max}}$ are labeled from left to right
with the values $1.5,2.5,\cdots,2^{h_{\mathrm{max}}}+0.5$, then it is clear
that for any $\ell\in[2^{h_{\mathrm{max}}}]$, the trajectory generated by