# Branching Reinforcement Learning

Yihan Du  Wei Chen

###### Abstract

In this paper, we propose a novel Branching Reinforcement Learning (Branching
RL) model, and investigate both Regret Minimization (RM) and Reward-Free
Exploration (RFE) metrics for this model. Unlike standard RL where the
trajectory of each episode is a single $H$-step path, branching RL allows an
agent to take multiple base actions in a state such that transitions branch
out to multiple successor states correspondingly, and thus it generates a
tree-structured trajectory. This model finds important applications in
hierarchical recommendation systems and online advertising. For branching RL,
we establish new Bellman equations and key lemmas, i.e., branching value
difference lemma and branching law of total variance, and also bound the total
variance by only $O(H^{2})$ under an exponentially-large trajectory. For RM
and RFE metrics, we propose computationally efficient algorithms
$\mathtt{BranchVI}$ and $\mathtt{BranchRFE}$, respectively, and derive nearly
matching upper and lower bounds. Our regret and sample complexity results are
polynomial in all problem parameters despite exponentially-large trajectories.

Branching reinforcement learning, branching Markov decision process, tree-
structured trajectory

##  1 Introduction

Reinforcement Learning (RL) (Burnetas & Katehakis, 1997; Sutton & Barto, 2018)
models a fundamental sequential decision making problem, where an agent
interacts with the environment over time in order to maximize the obtained
rewards. Standard RL (Jaksch et al., 2010; Agrawal & Jia, 2017; Azar et al.,
2017; Jin et al., 2018; Zanette & Brunskill, 2019) considers taking only a
single action in a state and formulates a single $H$-step path model. However,
in many real-world applications such as recommendation systems (Fu et al.,
2021) and online advertising (Kang et al., 2020), we often need to select
multiple options at a time, and each option can trigger a corresponding
successor state. For example, in category-based shopping recommendation (Fu et
al., 2021), the recommendation system often displays a list of main categories
at the first step, where each one has a probability to be clicked. If a main
category is clicked, at the second step, the system further provides a list of
sub-categories according to the clicked main category. By analogy, at the last
step, the system provides a list of items according to the chosen category
path. In this process, users can select (trigger) more than one category-item
paths, e.g., one may buy IT accessories-printers-laser printers and IT
accessories-scanners-document scanners at once.

To handle such scenarios involving multiple actions and successor states, we
propose a novel Branching Reinforcement Learning (Branching RL) framework,
which is an episodic tree-structured forward model. In each episode, an agent
starts from an initial state and takes a _super action_ that contains multiple
_base actions_ , where each base action in this state has a probability to be
triggered. For each state-base action pair, if triggered successfully, the
agent receives a reward and transitions to a next state; Otherwise, if it is
not triggered, the agent receives zero reward and transitions to an absorbing
state associated with zero reward. Thus, the transitions branch out to
multiple successor states. At the second step, for each branched-out state,
the agent also selects a super action that contains multiple base actions with
trigger probabilities. She only obtains rewards from the triggered state-base
action pairs, and each state-base action pair transitions to a corresponding
next state. Then, the transitions at the second step branch out to more
successor states. By analogy, till the last step, she traverses an $H$-layer
tree-structured trajectory, and only collects rewards at the triggered state-
base action pairs.

Different from standard episodic RL (Azar et al., 2017; Jin et al., 2018;
Zanette & Brunskill, 2019) where each trajectory is a single $H$-step path,
the trajectory of branching RL is an $H$-layer triggered tree with
exponentially increasing states and actions in each layer. This model allows
an agent to take multiple base actions at once and handle multiple successor
states. It can be applied to many hierarchical decision making scenarios, such
as category-based recommendation systems (Fu et al., 2021) and online
advertising (Kang et al., 2020).

Under the branching RL model, we investigate two popular metrics in the RL
literature, i.e., Regret Minimization (RM) and Reward-Free Exploration (RFE).
In regret minimization (Jaksch et al., 2010; Azar et al., 2017; Zanette &
Brunskill, 2019), the agent aims to minimize the gap between the obtained
reward and the reward that can obtained by always taking the optimal policy.
In reward-free exploration (Jin et al., 2020a; Kaufmann et al., 2021; Ménard
et al., 2021), the agent explores the unknown environment (model) without
observation of rewards, in order to estimate the model accurately such that
for any given reward function, she can plan a near-optimal policy using the
estimated model. The performance in RFE is measured by the number of episodes
used during exploration (i.e., sample complexity).

Our work faces several unique challenges: (i) Since branching RL is a tree-
structured forward model which greatly differs from standard RL, existing
analytical tools for standard RL, e.g., Bellman equations, value difference
lemma and law of total variance, cannot be directly applied to our problem.
(ii) With exponentially-large trajectories, it is challenging to analyze the
total variance and derive tight (polynomial) regret and sample complexity
guarantees. (iii) Since the number of possible super actions can be
combinatorially large, how to design a computationally efficient algorithm
that avoids naive enumeration over all super actions is another challenge.

To tackle the above challenges, we establish novel analytical tools, including
branching Bellman equations, branching value difference lemma and branching
law of total variance, and bound the total variance by only $O(H^{2})$ under
exponentially-large trajectories. We also propose computationally efficient
algorithms for both RM and RFE metrics, and provide nearly matching upper and
lower bounds, which are polynomial in all problem parameters despite
exponentially-large trajectories.

To sum up, our contributions in this paper are as follows:

  * •

We propose a novel Branching Reinforcement Learning (Branching RL) framework,
which is an episodic $H$-layer tree-structured forward model and finds
important applications in hierarchical recommendation systems and online
advertising. Under branching RL, we investigate two popular metrics, i.e.,
Regret Minimization (RM) and Reward-Free Exploration (RFE).

  * •

We establish new techniques for branching RL, including branching Bellman
equations, branching value difference lemma and branching law of total
variance, and bound the total variance by only $O(H^{2})$ despite
exponentially-large trajectories.

  * •

For both RM and RFE metrics, we design computationally efficient algorithms
$\mathtt{BranchVI}$ and $\mathtt{BranchRFE}$, respectively, and build near-
optimal upper and lower bounds, which are polynomial in all problem parameters
even with exponentially-large trajectories. When our problem reduces to
standard RL, our results match the state-of-the-arts.

Due to space limit, we defer all proofs to Appendix.

##  2 Related Work

Below we review the literature of standard (episodic and tabular) RL with
regret minimization (RM) and reward-free exploration (RFE) metrics.

Standard RL-RM. For the regret minimization (RM) metric, Jaksch et al. (2010)
propose an algorithm that adds optimistic bonuses on transition probabilities,
and achieves a regret bound with a gap in factors $H,S$ compared to the lower
bound (Jaksch et al., 2010; Osband & Van Roy, 2016). Here $H$ is the length of
an episode, and $S$ is the number of states. Agrawal & Jia (2017) use
posterior sampling and obtain an improved regret bound. Azar et al. (2017)
build confidence intervals directly for value functions rather than transition
probabilities, and provide the first optimal regret. Zanette & Brunskill
(2019) design an algorithm based on both optimistic and pessimistic value
functions, and achieve a tighter problem-dependent regret bounds without
requiring domain knowledge. The above works focus on model-based RL
algorithms. There are also other works (Jin et al., 2018; Zhang et al., 2020)
studying model-free algorithms based on Q-learning with exploration bonus or
advantage functions.

Standard RL-RFE. Jin et al. (2020a) introduce the reward-free-exploration
(RFE) metric and design an algorithm that runs multiple instances of existing
RM algorithm (Zanette & Brunskill, 2019), and their sample complexity has a
gap to the lower bound (Jin et al., 2020a; Domingues et al., 2021) in factors
$H,S$. Kaufmann et al. (2021) propose an algorithm which builds upper
confidence bounds for the estimation error of value functions, and improve the
sample complexity of (Jin et al., 2020a). Ménard et al. (2021) achieve a near-
optimal sample complexity by applying an empirical Bernstein inequality and
upper bounding the overall estimation error.

There are huge differences between standard RL and our branching RL. The
exponentially-large trajectory of branching RL brings unique challenges in
developing Bellman equations and key lemmas, designing computationally
efficient algorithms and deriving optimal (polynomial) bounds. Existing RL
algorithms and analysis cannot be applied to solve our challenges.

##  3 Problem Formulation

In this section, we present the formal formulation of Branching Reinforcement
Learning (Branching RL).

Branching Markov Decision Process (Branching MDP). We consider an episodic
branching MDP defined by a tuple
$\mathcal{M}=(\mathcal{S},A^{\mathtt{univ}},\mathcal{A},m,H,q,p,r)$. Here
$\mathcal{S}=\mathcal{S}^{\mathtt{reg}}\cup\\{s_{\perp}\\}$ is the state space
with cardinality $S$. $\mathcal{S}^{\mathtt{reg}}$ is the set of _regular
states_ , and $s_{\perp}$ is an _ending state_ , which is an absorbing state
with zero reward. $A^{\mathtt{univ}}$ is the set of _base actions_ , which
represents the set of all feasible items in recommendation. Let
$N:=|A^{\mathtt{univ}}|$ denote the number of base actions. A _super action_
$A\subset A^{\mathtt{univ}}$ consists of $m$ ($m\leq N$) base actions, which
stands for a recommended list. $\mathcal{A}$ is the collection of all feasible
_super actions_ and can be combinatorially large. $H$ is the length of an
episode. Throughout the paper, we call a super action an action for short,
call $(s,a)\in\mathcal{S}\times A^{\mathtt{univ}}$ a _state-base action pair_
, and call $(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times
A^{\mathtt{univ}}$ a _regular state-base action pair_.

$q(s,a)$ is the trigger probability of state-base action pair
$(s,a)\in\mathcal{S}\times A^{\mathtt{univ}}$. $p(s^{\prime}|s,a)$ is the
probability of transitioning to state $s^{\prime}$ on state-base action pair
$(s,a)$, for any $(s^{\prime},s,a)\in\mathcal{S}\times\mathcal{S}\times
A^{\mathtt{univ}}$. $r(s,a)\in[0,1]$ is the reward of pair
$(s,a)\in\mathcal{S}\times A^{\mathtt{univ}}$. We assume that reward function
$r$ is deterministic as many prior RL works (Azar et al., 2017; Jin et al.,
2018; Zhang et al., 2020), and our work can generalize to stochastic rewards
easily. Parameters $q,p,r$ are time-homogeneous, i.e., have the same
definitions for different step $h\in[H]$. The ending state $s_{\perp}$ has
zero reward and always transitions back to itself, i.e., $q(s_{\perp},a)=0$,
$p(s_{\perp}|s_{\perp},a)=1$ and $r(s_{\perp},a)=0$ for all $a\in
A^{\mathtt{univ}}$. We define a policy $\pi$ as a collection of $H$ functions
$\\{\pi_{h}\\!:\\!\mathcal{S}\\!\mapsto\\!\mathcal{A}\\}_{h\in[H]}$, and $K$
as the number of episodes.

String-based Notations. As shown in Figure 1, in branching RL, the trajectory
of each episode is an $m$-ary tree, where there are $H$ layers (steps), and
each layer $h\in[H]$ has $m^{h-1}$ states (nodes) and $m^{h}$ state-base
action pairs (edges). We use the following string-based notations to denote a
trajectory: Each tree node in layer $h$ has a string index $\langle
i_{1},\ldots,i_{h-1}\rangle$, with the root node for layer $1$ having the
empty string $\emptyset$, and $i_{1},\ldots,i_{h-1}\in\\{1,2,\ldots,m\\}$. The
$m$ children of this node have indices that concatenate $i_{h}\in[m]$ to the
string, making it $\langle i_{1},\ldots,i_{h-1},i_{h}\rangle$, where $i_{h}$
stands for that this node is the $i_{h}$-th child of the node $\langle
i_{1},\ldots,i_{h-1}\rangle$. Operator $\oplus$ is the concatenation operation
for strings, and $i^{\oplus h}$ denotes the concatenation of $h$ strings
$\Braket{i}$ for any $i\in[m],h\in[H]$. For any string $\sigma$, $|\sigma|$
denotes its length, and thus state $s_{\sigma}$ is at step $|\sigma|+1$.

Online Game. In each episode $k\in[K]$, an agent selects a policy $\pi^{k}$ at
the beginning, and starts from an initial state $s_{\emptyset}$. At step $1$,
she chooses an action
$A_{\emptyset}=\\{a_{\Braket{1}},\dots,a_{\Braket{m}}\\}$ according to
$\pi^{k}_{1}$. Each state-base action pair $(s_{\emptyset},a_{\Braket{i}})$
for $i\in[m]$ has probability $q(s_{\emptyset},a_{\Braket{i}})$ to be
triggered. If triggered successfully, the agent obtains reward
$r(s_{\emptyset},a_{\Braket{i}})$ and this state-base action pair transitions
to a next state $s_{\Braket{i}}\sim p(\cdot|s_{\emptyset},a_{\Braket{i}})$;
Otherwise, if not triggered successfully, she obtains zero reward and this
state-base action pair transitions to the ending state $s_{\perp}$. Hence, the
transitions at step $1$ branch out to $m$ successor states
$s_{\Braket{1}},\dots,s_{\Braket{m}}$. At step $2$, for each state
$s_{\Braket{i}}$ ($i\in[m]$), she chooses an action
$A_{\Braket{i}}=\\{a_{\Braket{i,1}},\dots,a_{\Braket{i,m}}\\}$ according to
$\pi^{k}_{2}$. Then, there are $m^{2}$ state-base action pairs
$\\{(s_{\Braket{i}},a_{\Braket{i,j}})\\}_{i,j\in[m]}$ at step $2$, and each of
them is triggered with probability $q(s_{\Braket{i}},a_{\Braket{i,j}})$. If
triggered successfully, the agent receives reward
$r(s_{\Braket{i}},a_{\Braket{i,j}})$ and this pair transitions to a next state
$s_{\Braket{i,j}}\sim p(\cdot|s_{\Braket{i}},a_{\Braket{i,j}})$; Otherwise,
she receives zero reward and this pair transitions to $s_{\perp}$. Then, the
transitions at step 2 branch out to $m^{2}$ successor states
$\\{s_{\Braket{i,j}}\\}_{i,j\in[m]}$. The episode proceeds by analogy at the
following steps $3,\dots,H$. In the trajectory tree, once the agent reaches
$s_{\perp}$ at some node, she obtains no reward throughout this branch (This
is so-called “ending state”).

Figure 1: Illustrating example with $m=2$ for branching RL.

Branching Value functions and Bellman Equations. For any policy $\pi$, we
define value function $V_{h}^{\pi}:\mathcal{S}\mapsto\mathbb{R}$, so that

$\displaystyle V^{\pi}_{h}(s)=$
$\displaystyle\mathbb{E}_{q,p,\pi}\Big{[}\sum_{\sigma^{\prime}=\emptyset}^{m^{\oplus(H-h)}}\sum_{\ell=1}^{m}q(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})\cdot$
$\displaystyle\quad\quad\quad
r(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})|s_{\sigma}=s\Big{]}$
(1)

gives the expected cumulative reward starting from some state $s$ at step $h$
till the end of this branch, under policy $\pi$. Here $\sigma$ is the index
string for an arbitrary state at step $h$, and thus
$\sigma\\!\in\\!\\{1^{\oplus(h-1)},\dots,m^{\oplus(h-1)}\\}$.
$\sum_{\sigma^{\prime}=\emptyset}^{m^{\oplus(H-h)}}$ denotes the summation
over strings
$\sigma^{\prime}=\emptyset,\Braket{1},\dots,\Braket{m},\Braket{1,1},\dots,\Braket{m,m},\dots,m^{\oplus(H-h)}$,
which effectively enumerates all tree nodes of $H\\!-\\!h\\!+\\!1$ layers. The
expectation is taken with respect to the trajectory, which is dependent on
trigger distribution $q$, transition distribution $p$ and policy $\pi$.

Accordingly, we also define Q-value function
$Q_{h}^{\pi}:\mathcal{S}\times\mathcal{A}\mapsto\mathbb{R}$, so that

$\displaystyle Q^{\pi}_{h}(s,A)=$
$\displaystyle\mathbb{E}_{q,p,\pi}\Big{[}\sum_{\sigma^{\prime}=\emptyset}^{m^{\oplus(H-h)}}\sum_{\ell=1}^{m}q(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})\cdot$
$\displaystyle\quad\quad\quad
r(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})|s_{\sigma}=s,A_{\sigma}=A\Big{]}$

denotes the expected cumulative reward starting from some state-action pair
$(s,A)$ at step $h$ till the end of this branch, under policy $\pi$. From the
definitions of $r,p,q$ for ending state $s_{\perp}$, we have
$V^{\pi}_{h}(s_{\perp})=Q^{\pi}_{h}(s_{\perp},A)=0$ for any
$A\in\mathcal{A},h\in[H],\pi$.

Since $\mathcal{S}$, $\mathcal{A}$ and $H$ are all finite, there exists a
deterministic optimal policy $\pi^{*}$ which has the optimal value
$V_{h}^{*}(s)=\sup_{\pi}V_{h}^{\pi}(s)$ for any $s\in\mathcal{S}$ and
$h\in[H]$. Then, we can establish the Bellman (optimality) equations as
follows:

$\left\\{\begin{aligned} Q^{\pi}_{h}(s,A)=&\sum_{a\in
A}q(s,a)\left(r(s,a)+p(\cdot|s,a)^{\top}V^{\pi}_{h+1}\right)\\\
V^{\pi}_{h}(s)=&Q^{\pi}_{h}(s,\pi_{h}(s))\\\ V^{\pi}_{H+1}(s)=&0,\ \forall
s\in\mathcal{S},\end{aligned}\right.$ $\left\\{\begin{aligned}
Q^{*}_{h}(s,A)=&\sum_{a\in
A}q(s,a)\left(r(s,a)+p(\cdot|s,a)^{\top}V^{*}_{h+1}\right)\\\
V^{*}_{h}(s)=&\max_{A\in\mathcal{A}}Q^{*}_{h}(s,A)\\\ V^{*}_{H+1}(s)=&0,\
\forall s\in\mathcal{S}.\end{aligned}\right.$

Under the framework of branching RL, we consider two important RL settings,
i.e., regret minimization (branching RL-RM) and reward-free exploration
(branching RL-RFE).

Regret Minimization (RM). In branching RL-RM, the agent plays the branching RL
game for $K$ episodes, and the goal is to minimize the following regret

$\displaystyle\mathtt{Regret}(K)=\sum_{k=1}^{K}\left(V_{1}^{*}(s_{\emptyset}^{k})-V_{1}^{\pi_{k}}(s_{\emptyset}^{k})\right).$

Reward-Free Exploration (RFE). Branching RL-RFE consists of two phases, i.e.,
exploration and planning. (i) In the exploration phase, given a fixed initial
state $s_{\emptyset}$, the agent plays the branching RL game _without_ the
observation of reward function $r$, and estimates a trigger and transition
model $(\hat{q},\hat{p})$. (ii) In the planning phase, the agent is given
reward function $r$, and computes the optimal policy $\hat{\pi}^{*}$ under her
estimated model $(\hat{q},\hat{p})$ with respect to $r$. Given an accuracy
parameter $\varepsilon$ and a confidence parameter $\delta$, she needs to
guarantee that for _any_ given reward function $r$, the policy $\hat{\pi}^{*}$
with respect to $r$ is _$\varepsilon$ -optimal_, i.e.,

$\displaystyle V_{1}^{\hat{\pi}^{*}}(s_{\emptyset};r)\geq
V_{1}^{\pi^{*}}(s_{\emptyset};r)-\varepsilon,$

with probability at least $1-\delta$. We measure the performance by _sample
complexity_ , i.e., the number of episodes used in the exploration phase to
guarantee an $\varepsilon$-optimal policy for any given $r$.

In order to ensure that the number of triggered state-base action pairs will
not increase exponentially and designing sample efficient algorithms is
possible in branching RL, we introduce the following assumption.

######  Assumption 1 (Bounded Trigger Probability).

For any $(s,a)\in\mathcal{S}\times A^{\mathtt{univ}}$, we have
$q(s,a)\leq\frac{1}{m}$.

To justify the necessity of Assumption 1, we provide a rigorous lower bound to
show that once relaxing the threshold of trigger probability, any branching RL
algorithm must suffer an exponential regret.

######  Theorem 2.

Suppose that for any $(s,a)\in\mathcal{S}\times A^{\mathtt{univ}}$,
$q(s,a)\leq\bar{q}$ for some threshold parameter $\bar{q}>\frac{1}{m}$. Then,
there exists an instance of branching RL with $H>1$, where the regret of any
algorithm is bounded by
$\Omega(\frac{m\bar{q}((m\bar{q})^{H-1}-1)}{m\bar{q}-1}\sqrt{SNK})$.

We describe the intuition behind this lower bound, and defer the full proof to
Appendix C.2.2. Consider a branching MDP, where at an early step the agent has
to distinguish the optimal action that has trigger probability $\bar{q}$, from
the sub-optimal actions that have trigger probabilities only $\bar{q}-\eta$.
Once the agent takes a sub-optimal action at the early step, such trigger sub-
optimality will impact exponentially many states in the following steps, and
she will suffer a regret of
$m\eta\cdot\left(m\bar{q}+m^{2}\bar{q}^{2}+\dots+m^{H-1}\bar{q}^{H-1}\right)$
in this episode, which is the sum of a geometric progression with common ratio
$m\bar{q}$. If $\bar{q}>\frac{1}{m}$, summing over all episodes, the total
regret is exponentially large with respect to $H$.

Besides this lower bound, Assumption 1 is also mild in practice, since in
real-world applications such as recommendation systems (Fu et al., 2021) and
online advertising (Kang et al., 2020), it is often the case that users are
only attracted to and click on a few items in a recommended list. In addition,
in multi-step (e.g., category-based) recommendation, the interests of users
usually converge to a single branch in the end (in expectation).

When $m=1$, our branching RL reduces to standard episodic RL (Azar et al.,
2017; Jin et al., 2018; Zanette & Brunskill, 2019) with transition probability
$p^{\mathtt{aug}}$, such that $p^{\mathtt{aug}}(s_{\perp}|s,a)=1-q(s,a)$ and
$p^{\mathtt{aug}}(s^{\prime}|s,a)=q(s,a)p(s^{\prime}|s,a)$ for any
$s^{\prime}\neq s_{\perp}$. In this case, our results match the state-of-the-
art results for standard RL in both RM (Azar et al., 2017; Zanette &
Brunskill, 2019) and RFE (Ménard et al., 2021; Zhang et al., 2021) settings.

##  4 Properties of the Branching Markov Decision Process

Before introducing our algorithms for branching RL, in this section, we first
investigate special structural properties of branching MDP, which are critical
to deriving tight (polynomial) regret and sample complexity guarantees.

###  4.1 Branching Value Difference Lemma and Law of Total Variance

Different from standard episodic MDP (Azar et al., 2017; Zanette & Brunskill,
2019) where a trajectory is an $H$-step path, the trajectory of branching MDP
is an $m$-ary tree with each node a state and each edge a state-base action
pair. Thus, many analytical tools in standard MDP, e.g., value difference
lemma (Dann et al., 2017) and law of total variance (Jin et al., 2018; Zanette
& Brunskill, 2019), cannot be directly applied to branching MDP. To handle
this problem, we establish new fundamental techniques for branching MDP,
including branching value difference lemma and branching law of total
variance.

First, we present a branching value difference lemma.

######  Lemma 3 (Branching Value Difference Lemma).

For any two branching MDP
$\mathcal{M}^{\prime}(\mathcal{S},A^{\mathtt{univ}},\mathcal{A},m,H,q^{\prime},p^{\prime},r)$
and
$\mathcal{M}^{\prime\prime}(\mathcal{S},A^{\mathtt{univ}},\mathcal{A},m,H,q^{\prime\prime},p^{\prime\prime},r)$,
the difference in values under the same policy $\pi$ satisfies that

$\displaystyle
V^{\prime\pi}_{h}(s)-V^{\prime\prime\pi}_{h}(s)=\\!\\!\\!\sum_{\sigma^{\prime}=\emptyset}^{m^{\oplus(H-h)}}\\!\sum_{\ell=1}^{m}\mathbb{E}_{q^{\prime\prime},p^{\prime\prime},\pi}\Big{[}\big{(}q^{\prime}(s_{\tau},a_{\tau\oplus\ell})$
$\displaystyle\\!-\\!q^{\prime\prime}(s_{\tau},a_{\tau\oplus\ell})\big{)}\\!\cdot\\!r(s_{\tau},a_{\tau\oplus\ell})+\big{(}q^{\prime}(s_{\tau},a_{\tau\oplus\ell})p^{\prime}(s_{\tau},a_{\tau\oplus\ell})$
$\displaystyle\\!-\\!q^{\prime\prime}(s_{\tau},a_{\tau\oplus\ell})p^{\prime\prime}(s_{\tau},a_{\tau\oplus\ell})\big{)}^{\top}V^{\prime\pi}_{|\tau\oplus\ell|+1}\big{|}s_{\sigma}=s\Big{]},$

where $\tau:=\sigma\oplus\sigma^{\prime}$.

Using Lemma 3 with $\mathcal{M}^{\prime}$ and $\mathcal{M}^{\prime\prime}$
being the optimistic and true models, respectively, we can bound the
difference between optimistic and true values by the deviations between
optimistic and true trigger and transition probabilities, in expectation with
respect to the true model.

Next, we provide a branching law of total variance, which is critical to
analyzing the estimation error of transition.

######  Lemma 4 (Branching Law of Total Variance).

For any policy $\pi$,

$\displaystyle\\!\\!\\!\mathbb{E}_{q,p,\pi}\Big{[}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\\!\\!\sum_{\ell=1}^{m}\textup{Var}_{q,p}\left(V^{\pi}_{|\sigma\oplus\ell|+1}(s_{\sigma\oplus\ell})|s_{\sigma},a_{\sigma\oplus\ell}\right)\Big{]}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{q,p,\pi}\\!\Big{[}\\!\Big{(}\\!\\!\\!\\!\\!\\!\sum_{\sigma=\emptyset}^{m^{\oplus(\\!H-1\\!)}}\\!\\!\\!\\!\sum_{\ell=1}^{m}q(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})\\!-\\!V^{\pi}_{1}\\!(s_{\emptyset})\\!\Big{)}^{\\!\\!2}\Big{]}\\!\\!\\!\\!$
(2) $\displaystyle\leq$
$\displaystyle\mathbb{E}_{q,p,\pi}\Big{[}\Big{(}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\Big{)}^{2}\Big{]}.$ (3)

Here
$\textup{Var}_{q,p}\left(V^{\pi}_{|\sigma\oplus\ell|+1}(s_{\sigma\oplus\ell})|s_{\sigma},a_{\sigma\oplus\ell}\right)$
denotes the variance of value
$V^{\pi}_{|\sigma\oplus\ell|+1}(s_{\sigma\oplus\ell})$ with respect to
$s_{\sigma\oplus\ell}$, which depends on trigger probability
$q(s_{\sigma},a_{\sigma\oplus\ell})$ and transition probability
$p(\cdot|s_{\sigma},a_{\sigma\oplus\ell})$, conditioning on
$(s_{\sigma},a_{\sigma\oplus\ell})$.

Remark 1. Lemma 4 exhibits that under branching MDP, the sum of conditional
variances over all state-base action pairs is equal to the overall variance
considering the whole trajectory, shown by Eq. (2). Furthermore, the overall
variance can be bounded by the total number of regular (triggered) states,
revealed by Eq. (3).

From Lemma 4, we have that to bound the estimation error of transition, which
is related to the sum of conditional variances, it suffices to bound the total
number of triggered states in a trajectory tree (discussed in the following).

###  4.2 The Number of Triggered States

In this subsection, we show that with Assumption 1 that only constrains the
first moment of trigger distribution, we can bound both the first and second
moments of the number of triggered states in a trajectory tree.

######  Lemma 5 (The Number of Triggered States).

For any policy $\pi$,

$\displaystyle\mathbb{E}_{q,p,\pi}\Big{[}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\Big{]}\leq H,$ (4)
$\displaystyle\mathbb{E}_{q,p,\pi}\Big{[}\Big{(}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\Big{)}^{2}\Big{]}\leq 3H^{2}.$ (5)

Remark 2. Eq. (4) gives a universal upper bound of value function as
$V^{\pi}_{h}(s)\leq\left[\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\right]\leq H$ for any $s\in\mathcal{S},h\in[H],\pi$.
Moreover, Eq. (5) provides a sharp upper bound for overall variance, as well
as the sum of conditional variances of transition (by plugging Eq. (5) into
Lemma 4). To our best knowledge, this second moment result is novel.

Lemma 5 shows that despite the exponentially increasing nodes in branching
MDP, its value and overall variance (estimation error) will not explode. This
critical property enables us to avoid an exponentially-large regret or sample
complexity.

Novel Analysis for Triggered States. The analysis of Lemma 5 is highly non-
trivial. We first relax all regular trigger probabilities to $\frac{1}{m}$,
and then investigate the number of triggered states for each step
individually. While we can show that the number of triggered states at each
step is a conditional Binomial random variable, the distribution of their sum
is too complex to express. This incurs a non-trivial challenge on analyzing
the second moment of the total number of triggered states. To tackle this
challenge, we investigate the correlation of triggered states between any two
steps, by exploiting the structure of branching MDP.

_Proof sketch._ Under Assumption 1, to bound the total number of triggered
(regular) states for any branching MDP and policy $\pi$, it suffices to bound
it under a relaxed model $\mathcal{M}^{*}$ with $q(s,a)=q^{*}:=\frac{1}{m}$
for all $(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times A^{\mathtt{univ}}$.
Let $\omega_{h}$ denote the number of triggered states at each step $h$ under
$\mathcal{M}^{*}$, and $\omega:=\sum_{h=1}^{H}\omega_{h}$. Below we prove that
$\mathbb{E}[\omega]\leq H$ and $\mathbb{E}[\omega^{2}]\leq 3H^{2}$.

For $h=1$, $\omega_{h}=1$ deterministically. For $h\geq 2$,
$\omega_{h}|\omega_{h-1}\sim\mathtt{Binomial}(m\omega_{h-1},q^{*})$. According
to the properties of Binomial distribution and $q^{*}:=\frac{1}{m}$, for
$h\geq 2$,

$\displaystyle\mathbb{E}\left[\omega_{h}\right]\hskip
5.0pt=mq^{*}\mathbb{E}\left[\omega_{h-1}\right]=1,$
$\displaystyle\mathbb{E}\left[(\omega_{h})^{2}\right]\\!=\\!mq^{*}(1-q^{*})\mathbb{E}\left[\omega_{h-1}\right]\\!+\\!m^{2}(q^{*})^{2}\mathbb{E}\left[(\omega_{h-1})^{2}\right]$
$\displaystyle\hskip
38.5001pt=(1-q^{*})+\mathbb{E}\left[(\omega_{h-1})^{2}\right]\leq h.$

Hence, we have that
$\mathbb{E}[\omega]=\sum_{h=1}^{H}\mathbb{E}[\omega_{h}]=H$, and

$\displaystyle\mathbb{E}[\omega^{2}]=$
$\displaystyle\sum_{h=1}^{H}\mathbb{E}[(\omega_{h})^{2}]+2\sum_{1<i,j<H}\mathbb{E}[\omega_{i}\omega_{j}]$
$\displaystyle\leq$
$\displaystyle\frac{H(H+1)}{2}+2\sum_{1<i,j<H}\mathbb{E}[\omega_{i}\omega_{j}].$
(6)

Now, the challenge falls on how to bound $\mathbb{E}[\omega_{i}\omega_{j}]$
for any $1<i,j<H$. Let $W_{\sigma}$ be a Bernoulli random variable denoting
whether state $s_{\sigma}$ is triggered for any index string $\sigma$. Then,
we can write $\mathbb{E}[\omega_{i}\omega_{j}]$ as

$\displaystyle\mathbb{E}\Big{[}\big{(}\sum_{\sigma=1^{\oplus(i-1)}}^{m^{\oplus(i-1)}}W_{\sigma}\big{)}\cdot\big{(}\sum_{\sigma^{\prime}=1^{\oplus(j-1)}}^{m^{\oplus(j-1)}}W_{\sigma^{\prime}}\big{)}\Big{]}$
$\displaystyle\overset{\textup{(a)}}{=}$ $\displaystyle
m^{i-1}\mathbb{E}\Big{[}W_{1^{\oplus(i-1)}}\big{(}\sum_{\sigma^{\prime}=1^{\oplus(j-1)}}^{m^{\oplus(j-1)}}W_{\sigma^{\prime}}\big{)}\Big{]}$
$\displaystyle=$ $\displaystyle
m^{i-1}\mathbb{E}\Big{[}W_{1^{\oplus(i-1)}}\big{(}\sum_{\begin{subarray}{c}\sigma^{\prime}=1^{\oplus(j-1)}\\\
\sigma^{\prime}\textup{starts with
}1^{\oplus(i-1)}\end{subarray}}^{m^{\oplus(j-1)}}W_{\sigma^{\prime}}+\sum_{\begin{subarray}{c}\sigma^{\prime}=1^{\oplus(j-1)}\\\
\sigma^{\prime}\textup{does not start with
}1^{\oplus(i-1)}\end{subarray}}^{m^{\oplus(j-1)}}W_{\sigma^{\prime}}\big{)}\Big{]}$
$\displaystyle\overset{\textup{(b)}}{\leq}$ $\displaystyle
m^{i-1}\left(m^{j-i}(q^{*})^{i-1+j-i}+m^{j-1}(q^{*})^{i-1+j-1}\right)$
$\displaystyle=$ $\displaystyle 2.$ (7)

Here (a) comes from the symmetry of trajectory tree. (b) is due to that at
step $j$, the children states of $s_{1^{\oplus(i-1)}}$ have dependency on it
and the other states are independent of it, and
$\mathbb{E}[W_{\sigma}W_{\sigma^{\prime}}]=\Pr[W_{\sigma}=1,W_{\sigma^{\prime}}=1]$
for any $\sigma,\sigma^{\prime}$. By plugging Eq. (7) into Eq. (6), we have
$\mathbb{E}[\omega^{2}]\leq\frac{H(H+1)}{2}+4\frac{H(H-1)}{2}\leq 3H^{2}$.
Thus, we obtain Lemma 5. $\square$

##  5 Branching Reinforcement Learning with Regret Minimization

In this section, we study branching RL-RM, and propose an efficient algorithm
$\mathtt{BranchVI}$ with a near-optimal regret guarantee for large enough $K$.
A lower bound is also established to validate the optimality of
$\mathtt{BranchVI}$.

Algorithm 1 $\mathtt{BranchVI}$

1: Input: confidence parameter $\delta$, $\delta^{\prime}:=\frac{1}{6}\delta$,
$L:=\log(\frac{SNH(m^{H}\vee K)}{\delta^{\prime}})$. Initialize
$\bar{V}^{k}_{h}(s_{\perp})=\underline{V}^{k}_{h}(s_{\perp})=0,\ \forall
h\in[H],k$.

2: for $k=1,2,\dots$ do

3: for $h=H,H-1,\dots,1$ do

4: for $s\in\mathcal{S}\setminus\\{s_{\perp}\\}$ do

5: for $a\in A^{\mathtt{univ}}$ do

6:
$\hat{q}^{k}(s,a)\\!\leftarrow\\!\frac{J^{k}_{\mathtt{sum}}(s,a)}{n^{k}(s,a)}$.
$b^{k,q}(s,a)\\!\leftarrow\\!4\sqrt{\frac{L}{n^{k}(s,a)}}$;

7:
$\hat{p}^{k}(s^{\prime}|s,a)\leftarrow\frac{P^{k}_{\mathtt{sum}}(s^{\prime}|s,a)}{J^{k}_{\mathtt{sum}}(s,a)},\
\forall s^{\prime}\in\mathcal{S}$;

8: $b^{k,qpV}(s,a)\leftarrow
4\sqrt{\frac{\textup{Var}_{s^{\prime}}\left(\bar{V}^{k}_{h+1}(s^{\prime})\right)L}{n^{k}(s,a)}}+4\sqrt{\frac{\\!\mathbb{E}_{s^{\prime}}\\!\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]\\!L}{n^{k}\\!(s,a)}}\\!+\\!\frac{36HL}{n^{k}\\!(s,a)}$;

9:
$f^{k}_{h}(s,a)\leftarrow(\hat{q}^{k}(s,a)+b^{k,q}(s,a))r(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\bar{V}^{k}_{h+1}+b^{k,qpV}(s,a)$;

10: end for

11: $\bar{V}^{k}_{h}(s)\\!\leftarrow\\!\min\\{\max_{A\in\mathcal{A}}\sum_{a\in
A}\\!f^{k}_{h}(s,a),\ H\\}$;

12:
$\pi^{k}_{h}(s)\leftarrow\operatornamewithlimits{argmax}_{A\in\mathcal{A}}\sum_{a\in
A}f^{k}_{h}(s,a)$;

13:
$\underline{V}^{k}_{h}(s)\leftarrow\max\\{\sum_{a\in\pi^{k}_{h}(s)}((\hat{q}^{k}(s,a)-b^{k,q}(s,a))r(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\underline{V}^{k}_{h+1}-b^{k,qpV}(s,a)),\
0\\}$;

14: end for

15: end for

16: Take policy $\pi^{k}$ and observe the trajectory;

17: end for

###  5.1 Algorithm $\mathtt{BranchVI}$

The algorithm design for branching RL faces two unique _challenges_ : (i)
Computation efficiency. Since the action space $\mathcal{A}$ can be
combinatorially large, it is inefficient to explicitly maintain $Q$ function
as in standard RL (Azar et al., 2017; Zanette & Brunskill, 2019); (ii) Tight
optimistic estimator. Naively adapting standard RL algorithms (Azar et al.,
2017; Zanette & Brunskill, 2019) and adding optimistic bonuses on trigger and
transition probabilities, respectively, will lead to a loose regret bound (see
Appendix A for details). To handle these challenges, $\mathtt{BranchVI}$ only
maintains the components of $Q$ function, and uses a maximization oracle to
directly calculate $V$ function. In addition, $\mathtt{BranchVI}$ considers
trigger and transition distributions as a whole and adds a composite bonus.

The procedure of $\mathtt{BranchVI}$ (Algorithm 1) is as follows. In each
episode $k$, we first calculate the empirical trigger and transition
probabilities $\hat{q}^{k},\hat{p}^{k}$, a bonus for trigger probability
$b^{k,q}$, and a composite bonus for trigger and transition probabilities
$b^{k,qpV}$ (Lines 6-8). Here $n^{k}(s,a)$, $J^{k}_{\mathtt{sum}}(s,a)$ and
$P^{k}_{\mathtt{sum}}(s^{\prime}|s,a)$ denote the number of times $(s,a)$ was
visited, the number of times $(s,a)$ was successfully triggered, and the
number of times the agent transitioned to $s^{\prime}$ from $(s,a)$ up to
episode $k$, respectively. Then, we calculate a component function
$f^{k}_{h}(s,a)$, which represents the contribution to value function from
each $(s,a)$ (Line 9).

We allow $\mathtt{BranchVI}$ to access a maximization oracle which can
efficiently calculate $\max_{A\in\mathcal{A}}\sum_{a\in A}w(a)$ and
$\operatornamewithlimits{argmax}_{A\in\mathcal{A}}\sum_{a\in A}w(a)$ for any
vector $\bm{w}\in\mathbb{R}^{N}$ ($N:=|A^{\mathtt{univ}}|$). Since the
objective function $\sum_{a\in A}w(a)$ is linear, such oracle exists for many
combinatorial decision classes, e.g., all $m$-cardinality subsets and
$m$-cardinality matchings. By utilizing this oracle with $f^{k}_{h}(s,a)$, we
can efficiently calculate the optimistic value function $\bar{V}^{k}_{h}(s)$
and policy $\pi^{k}_{h}$, and further compute the pessimistic value function
$\underline{V}^{k}_{h}$ (Lines 11-13). After figuring out
$\bar{V}^{k}_{h}(s),\underline{V}^{k}_{h},\pi^{k}_{h}(s)$ for all $s,h$, we
execute policy $\pi^{k}$ in episode $k$ (Line 16).

Computation Efficiency. We remark that the computation complexity of
$\mathtt{BranchVI}$ is $O(S^{2}N)$, instead of expensive
$O(S^{2}|\mathcal{A}|)$ as one may suffer by naively adapting standard RL
algorithms (Azar et al., 2017; Zanette & Brunskill, 2019). This advantage is
due to that $\mathtt{BranchVI}$ only maintains the component function instead
of the $Q$ function, and utilizes a maximization oracle to directly compute
$V$ function.

###  5.2 Regret Upper Bound for $\mathtt{BranchVI}$

Now we provide the regret guarantee for $\mathtt{BranchVI}$.

######  Theorem 6 (Regret Upper Bound).

With probability at least $1-\delta$, for any episode $K>0$, the regret of
algorithm $\mathtt{BranchVI}$ is bounded by
$O(H\sqrt{SNK}\log(\frac{SNH(m^{H}\vee K)}{\delta})).$ In particular, when
$K\geq m^{H}$, the regret is bounded by

$\displaystyle O\left(H\sqrt{SNK}\log\left(\frac{SNHK}{\delta}\right)\right)$

Remark 3. Theorem 6 shows that, despite the exponentially-large trajectory of
branching RL, $\mathtt{BranchVI}$ enjoys a regret only polynomial in problem
parameters. For large enough $K$ such that $K\geq m^{H}$, Theorem 6 matches
the lower bound (presented in Section 5.3) up to logarithmic factors. In
addition, when branching RL reduces to standard RL (i.e., $m=1$), our result
also matches the state-of-the-arts (Azar et al., 2017; Zanette & Brunskill,
2019).

Branching Regret Analysis. In contrast to standard RL (Azar et al., 2017;
Zanette & Brunskill, 2019), we derive a tree-structured regret analysis based
on special structural properties of branching RL in Section 4.

Using the branching value difference lemma (Lemma 3), we can decompose the
regret into the estimation error from each regular state-base action pair as
follows:

$\displaystyle\mathtt{Regret}(K)\leq\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k,\sigma,\ell}(s,a)\cdot$
$\displaystyle\Big{[}\underbrace{\left(\tilde{q}^{k}(s,a)-q(s,a)\right)r(s,a)}_{\mathtt{Term\
1:\ Triggered\ reward}}$
$\displaystyle+\underbrace{\left(\tilde{q}^{k}(s,a)\tilde{p}^{k}(\cdot|s,a)-\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)\right)^{\top}\bar{V}^{k}_{|\sigma\oplus\ell|+1}}_{\mathtt{Term\
2:\ Triggered\ transition\ optimism}}$
$\displaystyle+\underbrace{\left(\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}V^{*}_{|\sigma\oplus\ell|+1}}_{\mathtt{Term\
3:\ Triggered\ transition\ estimation}}$
$\displaystyle\\!\\!+\\!\\!\underbrace{\left(\hat{q}^{k}\\!(s,a)\hat{p}^{k}\\!(\cdot|s,a)\\!\\!-\\!\\!q(s,a)p(\\!\cdot|s,a\\!)\right)^{\\!\\!\\!\top}\\!\\!\\!\left(\\!\bar{V}^{k}_{|\sigma\oplus\ell|+1}\\!\\!-\\!\\!V^{*}_{|\sigma\oplus\ell|+1}\\!\right)\\!\\!}_{\mathtt{Term\
4:\ Lower\ order\ term}}\Big{]}\\!.$

Here $w_{k,\sigma,\ell}(s,a)$ denotes the probability that
$(s_{\sigma},a_{\sigma\oplus\ell})=(s,a)$ in episode $k$, and $\tilde{q}^{k}$
and $\tilde{p}^{k}$ represent optimistic trigger and transition probabilities,
respectively. In this decomposition, we address the estimation error for
triggered reward ($\mathtt{Term\ 1}$) and triggered transition
($\mathtt{Terms\ 2,3}$) separately, and consider trigger and transition
probabilities as a whole distribution (in $\mathtt{Terms\ 2,3}$). The dominant
terms are $\mathtt{Terms\ 2,3}$, which stand for the estimation error for
triggered transition and depend on the sum of conditional variances. Using
branching law of total variance (Lemma 4) and the second moment bound of
triggered states (Lemma 5), we can bound $\mathtt{Terms\ 2,3}$ by only
$O(H^{2})$ despite exponential state-base action pairs.

We note that it is necessary to separately address triggered reward and
triggered transition, and consider trigger and transition as a whole
distribution in bonus design (Line 8) and regret decomposition. A naive
adaption of standard RL algorithm (Zanette & Brunskill, 2019), which adds
bonuses on trigger and transition probabilities respectively, i.e., replacing
Line 9 with
$f^{k}_{h}(s,a)\leftarrow\left(\hat{q}^{k}(s,a)+b^{k,q}(s,a)\right)\cdot(r(s,a)+\hat{p}^{k}(\cdot|s,a)^{\top}\bar{V}^{k}_{h+1}+b^{k,pV}(s,a)),$
will suffer an extra factor $\sqrt{H}$ in the regret bound. Please see
Appendix A for more discussion.

###  5.3 Regret Lower Bound

In this subsection, we provide a lower bound for branching RL-RM which is
polynomial in problem parameters and demonstrates the optimality of
$\mathtt{BranchVI}$.

######  Theorem 7 (Regret Lower Bound).

There exists an instance of branching RL-RM, where any algorithm must have
$\Omega(H\sqrt{SNK})$ regret.

Remark 4. Theorem 7 validates that the regret of $\mathtt{BranchVI}$ (Theorem
6) is near-optimal for large enough $K$, and reveals that, a polynomial regret
is achievable and tight even with exponentially-large trajectories in
branching RL.

Branching Regret Lower Bound Analysis. Unlike prior standard episodic RL works
(Azar et al., 2017; Jin et al., 2018) which directly adapt the diameter-based
lower bound (Jaksch et al., 2010) to the episodic setting, we derive a new
lower bound analysis for branching RL-RM. We construct a hard instance, where
an agent uniformly enters one of $\Theta(S)$ “bandit states”, i.e., states
with an optimal action and sub-optimal actions, and hereafter always
transitions to a “homogeneous state”, i.e., a state with homogeneous actions.
Then, if the agent makes a mistake in a bandit state, she will suffer
$\Omega(H)$ regret in this episode. By bounding the KL-divergence between this
hard instance and uniform instance, we can derive a desired lower bound.

##  6 Branching Reinforcement Learning with Reward-free Exploration

Algorithm 2 $\mathtt{BranchRFE}$

1: Input: $s_{\emptyset}$, $\varepsilon$, $\delta$,
$\beta(t,\kappa):=\log(SN/\kappa)+S\log(8e(t+1))$ for any $t\in\mathbb{N}$ and
$\kappa\in(0,1)$. Initialize $B^{k}_{h}(s_{\perp})\\!=\\!0,\forall h\in[H],k$
and $B^{k}_{H+1}(s)\\!=\\!0,\forall s\\!\in\\!\mathcal{S},k$.

2: for $k=1,2,\dots$ do

3: for $h=H,H-1,\dots,1$ do

4: for $s\in\mathcal{S}\setminus\\{s_{\perp}\\}$ do

5: for $a\in A^{\mathtt{univ}}$ do

6: $\hat{q}^{k}(s,a)\leftarrow\frac{J^{k}_{\mathtt{sum}}(s,a)}{n^{k}(s,a)}$;

7:
$\hat{p}^{k}(s^{\prime}|s,a)\leftarrow\frac{P^{k}_{\mathtt{sum}}(s^{\prime}|s,a)}{J^{k}_{\mathtt{sum}}(s,a)},\
\forall s^{\prime}\in\mathcal{S}$;

8: $g^{k}_{h}(s,a)\leftarrow
12H^{2}\frac{\beta(n^{k}(s,a),\delta)}{n^{k}(s,a)}+\left(1+\frac{1}{H}\right)\\!\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\\!B^{k}_{h+1}(s)$;

9: end for

10:
$\pi^{k}_{h}(s)\leftarrow\operatornamewithlimits{argmax}_{A\in\mathcal{A}}\sum_{a\in
A}g^{k}_{h}(s,a)$;

11: $B^{k}_{h}(s)\leftarrow\min\\{\max_{A\in\mathcal{A}}\sum_{a\in
A}g^{k}_{h}(s,a),\ H\\}$;

12: end for

13: end for

14: if
$4e\sqrt{B^{k}_{1}(s_{\emptyset})}+B^{k}_{1}(s_{\emptyset})\leq\frac{\varepsilon}{2}$,
return $(\hat{q}^{k},\hat{p}^{k})$;

15: else Take policy $\pi^{k}$ and observe the trajectory;

16: end for

In this section, we investigate branching RL-RFE, and develop an efficient
algorithm $\mathtt{BranchRFE}$ and nearly matching upper and lower bounds of
sample complexity.

###  6.1 Algorithm $\mathtt{BranchRFE}$

In each episode, $\mathtt{BranchRFE}$ estimates the trigger and transition
probabilities, and computes the estimation error $B^{k}_{h}(s)$, which stands
for the cumulative variance of trigger and transition from step $h$ to $H$.
Once the total estimation error $B^{k}_{1}(s_{\emptyset})$ is shrunk below the
required accuracy, $\mathtt{BranchRFE}$ returns the estimated model
$(\hat{q}^{k},\hat{p}^{k})$. Given any reward function $r$, the optimal policy
$\hat{\pi}^{*}$ under $(\hat{q}^{k},\hat{p}^{k})$ with respect to $r$ is
$\varepsilon$-optimal, i.e., $V^{\hat{\pi}^{*}}_{1}(s_{\emptyset};r)\geq
V^{*}_{1}(s_{\emptyset};r)-\varepsilon$, with probability at least $1-\delta$.

We describe $\mathtt{BranchRFE}$ (Algorithm 2) as follows: In each episode
$k$, for each step $h$, $\mathtt{BranchRFE}$ first estimates the trigger and
transition probabilities $\hat{q}^{k},\hat{p}^{k}$ (Lines 6,7), and calculates
the component estimation error $g^{k}_{h}(s,a)$ for each state-base action
pair (Line 8). Then, similar to $\mathtt{BranchVI}$, we utilize a maximization
oracle to efficiently find the action with the maximum estimation error (the
most necessary action for exploration) to be $\pi^{k}_{h}(s)$, and assign such
maximum error to $B^{k}_{h}(s)$ (Lines 10,11). If the square root of total
estimation error $\sqrt{B^{k}_{1}(s_{\emptyset})}$, which represents the
standard deviation of trigger and transition for whole trajectory, is smaller
than $\varepsilon/2$, $\mathtt{BranchRFE}$ stops and outputs the estimated
model $(\hat{q}^{k},\hat{p}^{k})$ (Line 14); Otherwise, it continues to
explore according to the computed policy $\pi^{k}$ (Line 15).

The computation complexity of $\mathtt{BranchRFE}$ is also $O(S^{2}N)$ instead
of $O(S^{2}|\mathcal{A}|)$, since it only computes the component estimation
error for state-base action pairs rather than enumerating super actions, and
utilizes a maximization oracle to calculate $\pi^{k}_{h}(s)$ and
$B^{k}_{h}(s)$.

###  6.2 Sample Complexity Upper Bound for $\mathtt{BranchRFE}$

Now we present the sample complexity for $\mathtt{BranchRFE}$. We say an
algorithm for branching RL-RFE is $(\delta,\varepsilon)$-correct, if it
returns an estimated model $(\hat{q},\hat{p})$ such that given any reward
function $r$, the optimal policy under $(\hat{q},\hat{p})$ with respect to $r$
is $\varepsilon$-optimal with probability at least $1-\delta$.

######  Theorem 8 (Sample Complexity Upper Bound).

For any $\varepsilon>0$ and $\delta\in(0,1)$, algorithm $\mathtt{BranchRFE}$
is $(\delta,\varepsilon)$-correct. Moreover, with probability $1-\delta$, the
number of episodes used in $\mathtt{BranchRFE}$ is bounded by

$O\left(\frac{H^{2}SN}{\varepsilon^{2}}\left(\log\left(\frac{SN}{\delta}\right)+S\log\left(e\cdot
m^{H}\right)\right)\cdot C^{2}\right),$

where $C=\log\left(\left(\log\left(\frac{SN}{\delta}\right)+S\log\left(e\cdot
m^{H}\right)\right)\cdot\frac{HSN}{\varepsilon}\right)$.

Remark 5. Theorem 6 exhibits that even with exponentially-large trajectories
in branching RL, $\mathtt{BranchRFE}$ only needs polynomial episodes to ensure
an $\varepsilon$-optimal policy for any reward function. This sample
complexity is optimal for small enough $\delta$ within logarithmic factors
(compared to the lower bound presented in Section 6.3). In addition, when
degenerating to standard RL (i.e., $m=1$), our result also matches the state-
of-the-arts (Ménard et al., 2021; Zhang et al., 2021).

Branching Sample Complexity Analysis. Unlike standard RL (Ménard et al., 2021;
Zhang et al., 2021) which only bounds the estimation error in a single
$H$-step path, in branching RL we need to unfold and analyze the estimation
error for all state-base action pairs in a trajectory tree. In our analysis,
we utilize special structural properties of branching MDP, e.g., branching law
of total variance (Lemmas 4) and the second moment bound of triggered states
(Lemmas 5), to skillfully bound the total estimation error throughout the
trajectory tree. Despite exponentially-large trajectories, we obtain sample
complexity only polynomial in problem parameters.

###  6.3 Sample Complexity Lower Bound

######  Theorem 9 (Sample Complexity Lower Bound).

There exists an instance of branching RL-RFE, where any
$(\delta,\varepsilon)$-correct algorithm requires
$\Omega(\frac{H^{2}SN}{\varepsilon^{2}}\log\delta^{-1})$ trajectories.

Remark 6. Theorem 9 demonstrates that $\mathtt{BranchRFE}$ (Theorem 8)
achieves a near-optimal sample complexity for small enough $\delta$, and also,
a polynomial sample complexity is achievable and sharp for branching RL-RFE.

##  7 Experiments

In this section, we conduct experiments for branching RL. We set $K=5000$,
$\delta=0.005$, $H=6$, $m=2$, $N\in\\{10,15\\}$,
$\mathcal{S}=\\{s_{\perp},s_{1},\dots,s_{5}\\}$. $\mathcal{A}$ is the
collection of all $m$-cardinality subsets of
$A^{\mathtt{univ}}=\\{a_{1},\dots,a_{N}\\}$, and thus
$|\mathcal{A}|=\binom{N}{m}\in\\{45,105\\}$. The reward function $r(s,a)=1$
for any $(s,a)\in\mathcal{S}\times\mathcal{A}$. The trigger probability
$q(s,a)=\frac{1}{m}$ for any $(s,a)\in\mathcal{S}\times\\{a_{N-1},a_{N}\\}$,
and $q(s,a)=\frac{1}{2m}$ for any $(s,a)\in\mathcal{S}\times
A^{\mathtt{univ}}\setminus\\{a_{N-1},a_{N}\\}$. We set $s_{1}$ as the initial
state for each episode. Under all actions $a\in A^{\mathtt{univ}}$, the
transition probability $q(s^{\prime}|s_{1},a)=0.5$ for any
$s^{\prime}\in\\{s_{2},s_{3}\\}$, and $q(s^{\prime}|s,a)=0.5$ for any
$(s,s^{\prime})\in\\{s_{2},s_{3}\\}\times\\{s_{4},s_{5}\\}$ or
$(s,s^{\prime})\in\\{s_{4},s_{5}\\}\times\\{s_{2},s_{3}\\}$. We perform $50$
independent runs, and report the average regrets and running times (in
legends) across runs.

Since we study a new problem and there is no existing algorithm for branching
RL, we compare our algorithm $\mathtt{BranchVI}$ with two adaptations from
standard RL, i.e., $\mathtt{Euler\mbox{-}Adaptation}$ (Zanette & Brunskill,
2019) and $\varepsilon\mbox{-}\mathtt{Greedy}$ ($\varepsilon=0.01$). The
former uses individual exploration bonuses for trigger and transition, the
latter uses $\varepsilon$-greedy in exploration, and both of them explicitly
maintain Q-functions. As shown in Figure 2, $\mathtt{BranchVI}$ enjoys a lower
regret and a faster running time than the baselines, which demonstrates the
effectiveness of our exploration strategy and the computation efficiency of
our algorithm.

Figure 2: Experiments for branching RL.

##  8 Conclusion and Future Work

In this paper, we formulate a novel branching RL model, and consider both
regret minimization and reward-free exploration metrics. Different from
standard RL where each episode is a single $H$-step path, branching RL is a
tree-structured forward model which allows multiple base actions in a state
and multiple successor states. For branching RL, we build novel fundamental
analytical tools and carefully bound the overall variance. We design efficient
algorithms and provide near-optimal upper and lower bounds.

There are many interesting directions to explore. One direction is to improve
the dependency on $H$ in our regret upper bound (Theorem 6) for small $K$ and
close the gap on factors $H,S$ between sample complexity upper and lower
bounds (Theorems 8,9). Another direction is to extend branching RL from the
tabular setting to function approximation, e.g., representing the value
function in a linear form with respect to the feature vectors of state-action
pairs (Jin et al., 2020b; Zhou et al., 2021).

## References

  * Agrawal & Jia (2017) Agrawal, S. and Jia, R.  Posterior sampling for reinforcement learning: worst-case regret bounds.  In _Advances in Neural Information Processing Systems_ , pp. 1184–1194, 2017.
  * Auer et al. (2002) Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E.  The nonstochastic multiarmed bandit problem.  _SIAM Journal on Computing_ , 32(1):48–77, 2002\.
  * Azar et al. (2017) Azar, M. G., Osband, I., and Munos, R.  Minimax regret bounds for reinforcement learning.  In _International Conference on Machine Learning_ , pp. 263–272. PMLR, 2017.
  * Burnetas & Katehakis (1997) Burnetas, A. N. and Katehakis, M. N.  Optimal adaptive policies for markov decision processes.  _Mathematics of Operations Research_ , 22(1):222–255, 1997.
  * Dann & Brunskill (2015) Dann, C. and Brunskill, E.  Sample complexity of episodic fixed-horizon reinforcement learning.  In _Advances in Neural Information Processing Systems_ , pp. 2818–2826, 2015.
  * Dann et al. (2017) Dann, C., Lattimore, T., and Brunskill, E.  Unifying PAC and regret: uniform PAC bounds for episodic reinforcement learning.  In _Advances in Neural Information Processing Systems_ , pp. 5717–5727, 2017.
  * Domingues et al. (2021) Domingues, O. D., Ménard, P., Kaufmann, E., and Valko, M.  Episodic reinforcement learning in finite MDPs: Minimax lower bounds revisited.  In _Algorithmic Learning Theory_ , pp. 578–598. PMLR, 2021.
  * Fu et al. (2021) Fu, M., Agrawal, A., Irissappane, A. A., Zhang, J., Huang, L., and Qu, H.  Deep reinforcement learning framework for category-based item recommendation.  _IEEE Transactions on Cybernetics_ , 2021.
  * Jaksch et al. (2010) Jaksch, T., Ortner, R., and Auer, P.  Near-optimal regret bounds for reinforcement learning.  _Journal of Machine Learning Research_ , 11(4), 2010.
  * Jin et al. (2018) Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I.  Is Q-learning provably efficient?  In _Advances in Neural Information Processing Systems_ , pp. 4868–4878, 2018.
  * Jin et al. (2020a) Jin, C., Krishnamurthy, A., Simchowitz, M., and Yu, T.  Reward-free exploration for reinforcement learning.  In _International Conference on Machine Learning_ , pp. 4870–4879. PMLR, 2020a.
  * Jin et al. (2020b) Jin, C., Yang, Z., Wang, Z., and Jordan, M. I.  Provably efficient reinforcement learning with linear function approximation.  In _Conference on Learning Theory_ , pp. 2137–2143. PMLR, 2020b.
  * Kang et al. (2020) Kang, S., Jeong, C., and Chung, K.  Tree-based real-time advertisement recommendation system in online broadcasting.  _IEEE Access_ , 8:192693–192702, 2020.
  * Kaufmann et al. (2021) Kaufmann, E., Ménard, P., Domingues, O. D., Jonsson, A., Leurent, E., and Valko, M.  Adaptive reward-free exploration.  In _International Conference on Algorithmic Learning Theory_ , pp. 865–891. PMLR, 2021.
  * Mannor & Tsitsiklis (2004) Mannor, S. and Tsitsiklis, J. N.  The sample complexity of exploration in the multi-armed bandit problem.  _Journal of Machine Learning Research_ , 5:623–648, 2004\.
  * Ménard et al. (2021) Ménard, P., Domingues, O. D., Jonsson, A., Kaufmann, E., Leurent, E., and Valko, M.  Fast active learning for pure exploration in reinforcement learning.  In _International Conference on Machine Learning_ , pp. 7599–7608. PMLR, 2021.
  * Osband & Van Roy (2016) Osband, I. and Van Roy, B.  On lower bounds for regret in reinforcement learning.  _arXiv preprint arXiv:1608.02732_ , 2016.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Zanette & Brunskill (2019) Zanette, A. and Brunskill, E.  Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds.  In _International Conference on Machine Learning_ , pp. 7304–7312. PMLR, 2019.
  * Zhang et al. (2020) Zhang, Z., Zhou, Y., and Ji, X.  Almost optimal model-free reinforcement learning via reference-advantage decomposition.  _Advances in Neural Information Processing Systems_ , 2020.
  * Zhang et al. (2021) Zhang, Z., Du, S. S., and Ji, X.  Nearly minimax optimal reward-free reinforcement learning.  _International Conference on Machine Learning_ , 2021.
  * Zhou et al. (2021) Zhou, D., He, J., and Gu, Q.  Provably efficient reinforcement learning for discounted MDPs with feature mapping.  In _International Conference on Machine Learning_ , pp. 12793–12802. PMLR, 2021.

## Appendix

##  Appendix A Discussion for Algorithm $\mathtt{BranchVI}$

We remark that it is necessary to separately address triggered reward and
triggered transition, and consider trigger and transition as a whole
distribution in bonus design (Line 8 in Algorithm 1) and regret analysis (Eq.
(13)). A counter example is discussed below to support this statement.

If one naively adapts standard RL algorithms (Azar et al., 2017; Zanette &
Brunskill, 2019), she/he may directly add bonuses on trigger and transition
probabilities, respectively, without separating triggered reward and triggered
transition. In this case, $f^{k}_{h}(s,a)$ (Line 9) becomes:

$\displaystyle f^{k}_{h}(s,a)\leftarrow$
$\displaystyle\left(\hat{q}^{k}(s,a)+b^{k,q}(s,a)\right)\left(r(s,a)+\hat{p}^{k}(\cdot|s,a)^{\top}\bar{V}^{k}_{h+1}+b^{k,pV}(s,a)\right)$

Then, in regret decomposition, we will obtain

$\displaystyle\mathtt{Regret}(K)\overset{\textup{(a)}}{\approx}O(1)\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\Big{[}b^{k,q}(s,a)\Big{(}r(s,a)+\underbrace{p(\cdot|s,a)^{\top}\bar{V}^{k}_{|\sigma\oplus\ell|+1}}_{\mathtt{Term\
\Lambda}}\Big{)}+b^{k,p\bar{V}}(s,a)q(s,a)\Big{]},$

where (a) omits second order terms. Since $\mathtt{Term\ \Lambda}$ already
reaches $\Theta(h)$ order, further summing over all episodes $k$ and steps
$h$, we will suffer an extra $\sqrt{H}$ factor in the final result.

One can see from this counter example that, our bonus design and analysis,
which separately handle triggered reward and triggered transition and consider
trigger and transition as a whole distribution, are sharp and enable a near-
optimal regret.

##  Appendix B Proofs for Properties of Branching MDP

In this section, we present the proofs for structural properties of branching
MDP, including branching value difference lemma (Lemma 3), branching law of
total variance (Lemma 4) and the upper bounds of the number of triggered
states (Lemma 5).

###  B.1 Proof of Lemma 3

###### Proof of Lemma 3.

This proof adapts the analysis of Lemma E.15 in (Dann et al., 2017) to
branching RL. According to branching Bellman equations,

$\displaystyle
V^{\prime\pi}_{h}(s_{\sigma})-V^{\prime\prime\pi}_{h}(s_{\sigma})$
$\displaystyle\overset{\textup{(a)}}{=}$
$\displaystyle\sum_{\ell=1}^{m}\Big{(}q^{\prime}(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})-q^{\prime\prime}(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})$
$\displaystyle+q^{\prime}(s_{\sigma},a_{\sigma\oplus\ell})p^{\prime}(s_{\sigma},a_{\sigma\oplus\ell})^{\top}V^{\prime\pi}_{h+1}-q^{\prime\prime}(s_{\sigma},a_{\sigma\oplus\ell})p^{\prime\prime}(s_{\sigma},a_{\sigma\oplus\ell})^{\top}V^{\prime\prime\pi}_{h+1}\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{\ell=1}^{m}\Big{(}q^{\prime}(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})-q^{\prime\prime}(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})$
$\displaystyle+\left(q^{\prime}(s_{\sigma},a_{\sigma\oplus\ell})p^{\prime}(s_{\sigma},a_{\sigma\oplus\ell})-q^{\prime\prime}(s_{\sigma},a_{\sigma\oplus\ell})p^{\prime\prime}(s_{\sigma},a_{\sigma\oplus\ell})\right)^{\top}V^{\prime\pi}_{h+1}$
$\displaystyle+q^{\prime\prime}(s_{\sigma},a_{\sigma\oplus\ell})p^{\prime\prime}(s_{\sigma},a_{\sigma\oplus\ell})^{\top}\left(V^{\prime\pi}_{h+1}-V^{\prime\prime\pi}_{h+1}\right)\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{\ell=1}^{m}\Big{(}q^{\prime}(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})-q^{\prime\prime}(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})$
$\displaystyle+\left(q^{\prime}(s_{\sigma},a_{\sigma\oplus\ell})p^{\prime}(s_{\sigma},a_{\sigma\oplus\ell})-q^{\prime\prime}(s_{\sigma},a_{\sigma\oplus\ell})p^{\prime\prime}(s_{\sigma},a_{\sigma\oplus\ell})\right)^{\top}V^{\prime\pi}_{h+1}\Big{)}$
$\displaystyle+\sum_{\ell=1}^{m}\mathbb{E}_{q^{\prime\prime},p^{\prime\prime},\pi}\left[V^{\prime\pi}_{h+1}(s_{\sigma\oplus\ell})-V^{\prime\prime\pi}_{h+1}(s_{\sigma\oplus\ell})|s_{h}=s\right]$
$\displaystyle=$
$\displaystyle\sum_{\sigma^{\prime}=\emptyset}^{m}\sum_{\ell=1}^{m}\mathbb{E}_{q^{\prime\prime},p^{\prime\prime},\pi}\Big{[}q^{\prime}(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})r(s_{t\ell},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})-q^{\prime\prime}(s_{t\ell},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})r(s_{t\ell},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})$
$\displaystyle+\left(q^{\prime}(s_{t\ell},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})p^{\prime}(s_{t\ell},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})-q^{\prime\prime}(s_{t\ell},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})p^{\prime\prime}(s_{t\ell},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})\right)^{\top}V^{\prime\pi}_{h+1}\Big{]}$
$\displaystyle+\sum_{\sigma^{\prime}=1^{\oplus 2}}^{m^{\oplus
2}}\mathbb{E}_{q^{\prime\prime},p^{\prime\prime},\pi}\left[V^{\prime\pi}_{h+2,\ell}(s_{\sigma^{\prime}})-V^{\prime\prime\pi}_{h+2,\ell}(s_{\sigma^{\prime}})|s_{h}\right]$
$\displaystyle=$
$\displaystyle\sum_{\sigma^{\prime}=\emptyset}^{m^{\oplus(H-h)}}\sum_{\ell=1}^{m}\mathbb{E}_{q^{\prime\prime},p^{\prime\prime},\pi}\Big{[}q^{\prime}(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})r(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})-q^{\prime\prime}(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})r(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})$
$\displaystyle+\left(q^{\prime}(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})p^{\prime}(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})-q^{\prime\prime}(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})p^{\prime\prime}(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})\right)^{\top}V^{\prime\pi}_{|\sigma\oplus\sigma^{\prime}\oplus\ell|+1}\Big{]}$

∎

###  B.2 Proof of Lemma 4

###### Proof of Lemma 4.

First, we prove the equality. This proof adapts the analysis of standard law
of total variance in (Jin et al., 2018; Zanette & Brunskill, 2019) to
branching RL.

$\displaystyle\mathbb{E}_{q,p,\pi}\left[\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\textup{Var}_{s_{\sigma\oplus\ell}\sim
q,p}\left(V^{\pi}_{|\sigma\oplus\ell|+1}(s_{\sigma\oplus\ell})|s_{\sigma},a_{\sigma\oplus\ell}\right)\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{q,p,\pi}\left[\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\left(V^{\pi}_{|\sigma\oplus\ell|+1}(s_{\sigma\oplus\ell})-q(s_{\sigma},a_{\sigma\oplus\ell})p(s_{\sigma},a_{\sigma\oplus\ell})^{\top}V^{\pi}_{|\sigma\oplus\ell|+1}\right)^{2}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{q,p,\pi}\Bigg{[}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\Bigg{(}q(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})+V^{\pi}_{|\sigma\oplus\ell|+1}(s_{\sigma\oplus\ell})$
$\displaystyle-\left(q(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})+q(s_{\sigma},a_{\sigma\oplus\ell})p(s_{\sigma},a_{\sigma\oplus\ell})^{\top}V^{\pi}_{|\sigma\oplus\ell|+1}\right)\Bigg{)}^{2}\Bigg{]}$
$\displaystyle\overset{\textup{(a)}}{=}$
$\displaystyle\mathbb{E}_{q,p,\pi}\Bigg{[}\Bigg{(}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\Big{(}q(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})+V^{\pi}_{|\sigma\oplus\ell|+1}(s_{\sigma\oplus\ell})$
$\displaystyle-\left(q(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})+q(s_{\sigma},a_{\sigma\oplus\ell})p(s_{\sigma},a_{\sigma\oplus\ell})^{\top}V^{\pi}_{|\sigma\oplus\ell|+1}\right)\Big{)}\Bigg{)}^{2}\Bigg{]}$
$\displaystyle\overset{\textup{(b)}}{=}$
$\displaystyle\mathbb{E}_{q,p,\pi}\left[\Bigg{(}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}q(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})+\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}V^{\pi}_{|\sigma\oplus\ell|+1}(s_{\sigma\oplus\ell})-\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}V^{\pi}_{|\sigma|+1}(s_{\sigma})\Bigg{)}^{2}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{q,p,\pi}\left[\left(\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}q(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})-V^{\pi}_{1}(s_{\emptyset})\right)^{2}\right]$

Here (a) comes from the Markov property and that conditioning on the
filtration of step $h$, the triggers and transitions of state-base action
pairs at step $h+1$ are independent. (b) is due to that
$V^{\pi}_{|\sigma|+1}(s_{\sigma})=\sum_{\ell=1}^{m}\left(q(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})+q(s_{\sigma},a_{\sigma\oplus\ell})p(s_{\sigma},a_{\sigma\oplus\ell})^{\top}V^{\pi}_{|\sigma\oplus\ell|+1}\right)$
and we can merge the $m$ terms of state-base action value into
$V^{\pi}_{|\sigma|+1}(s_{\sigma})$.

Now, we prove the inequality.

$\displaystyle\mathbb{E}_{q,p,\pi}\left[\left(\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}q(s_{\sigma},a_{\sigma\oplus\ell})r(s_{\sigma},a_{\sigma\oplus\ell})-V^{\pi}_{1}(s_{\emptyset})\right)^{2}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{q,p,\pi}\left[\left(\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}q(s_{\sigma},a_{\sigma\oplus\ell})\right)^{2}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\left(\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\Big{(}q(s_{\sigma},a_{\sigma\oplus\ell})\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}+q(s_{\sigma},a_{\sigma\oplus\ell})\mathbbm{1}\left\\{s_{\sigma}=s_{\perp}\right\\}\Big{)}\right)^{2}\right]$
$\displaystyle\overset{\textup{(a)}}{\leq}$
$\displaystyle\mathbb{E}\left[\left(\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\frac{1}{m}\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\right)^{2}\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\left(\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\right)^{2}\right]$

where (a) is due to Assumption 1 and $q(s_{\perp},a)=0$ for any $a\in
A^{\mathtt{univ}}$.

∎

###  B.3 Proof of Lemma 5

###### Proof of Lemma 5.

Under Assumption 1, to bound the total number of triggered (regular) states
for any branching MDP and policy $\pi$, it suffices to bound it under a
relaxed model $\mathcal{M}^{*}$ with $q(s,a)=q^{*}:=\frac{1}{m}$ for all
$(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times A^{\mathtt{univ}}$. Let
$\omega_{h}$ denote the number of triggered states at each step $h$ under
$\mathcal{M}^{*}$, and $\omega:=\sum_{h=1}^{H}\omega_{h}$. Below we prove that
$\mathbb{E}[\omega]\leq H$ and $\mathbb{E}[\omega^{2}]\leq 3H^{2}$.

For $h=1$, $\omega_{h}=1$ deterministically. For $h\geq 2$,
$\omega_{h}|\omega_{h-1}\sim\mathtt{Binomial}(m\omega_{h-1},q^{*})$. According
to the properties of Binomial distribution and $q^{*}:=\frac{1}{m}$, for
$h\geq 2$,

$\displaystyle\mathbb{E}\left[\omega_{h}\right]\hskip
5.0pt=mq^{*}\mathbb{E}\left[\omega_{h-1}\right]=1,$
$\displaystyle\mathbb{E}\left[(\omega_{h})^{2}\right]\\!=\\!mq^{*}(1-q^{*})\mathbb{E}\left[\omega_{h-1}\right]+m^{2}(q^{*})^{2}\mathbb{E}\left[(\omega_{h-1})^{2}\right]$
$\displaystyle\hskip
38.5001pt=(1-q^{*})+\mathbb{E}\left[(\omega_{h-1})^{2}\right]\leq h.$

Hence, we have that
$\mathbb{E}[\omega]=\sum_{h=1}^{H}\mathbb{E}[\omega_{h}]=H$, and

$\displaystyle\mathbb{E}[\omega^{2}]=$
$\displaystyle\sum_{h=1}^{H}\mathbb{E}[(\omega_{h})^{2}]+2\sum_{1<i,j<H}\mathbb{E}[\omega_{i}\omega_{j}]$
$\displaystyle\leq$
$\displaystyle\frac{H(H+1)}{2}+2\sum_{1<i,j<H}\mathbb{E}[\omega_{i}\omega_{j}].$
(8)

Now, the challenge falls on how to bound $\mathbb{E}[\omega_{i}\omega_{j}]$
for any $1<i,j<H$. Let $W_{\sigma}$ be a Bernoulli random variable denoting
whether state $s_{\sigma}$ is triggered for any index string $\sigma$. Then,
we can write $\mathbb{E}[\omega_{i}\omega_{j}]$ as

$\displaystyle\mathbb{E}\Big{[}\big{(}\sum_{\sigma=1^{\oplus(i-1)}}^{m^{\oplus(i-1)}}W_{\sigma}\big{)}\cdot\big{(}\sum_{\sigma^{\prime}=1^{\oplus(j-1)}}^{m^{\oplus(j-1)}}W_{\sigma^{\prime}}\big{)}\Big{]}$
$\displaystyle\overset{\textup{(a)}}{=}$ $\displaystyle
m^{i-1}\mathbb{E}\Big{[}W_{1^{\oplus(i-1)}}\big{(}\sum_{\sigma^{\prime}=1^{\oplus(j-1)}}^{m^{\oplus(j-1)}}W_{\sigma^{\prime}}\big{)}\Big{]}$
$\displaystyle=$ $\displaystyle
m^{i-1}\mathbb{E}\Big{[}W_{1^{\oplus(i-1)}}\big{(}\sum_{\begin{subarray}{c}\sigma^{\prime}=1^{\oplus(j-1)}\\\
\sigma^{\prime}\textup{starts with
}1^{\oplus(i-1)}\end{subarray}}^{m^{\oplus(j-1)}}W_{\sigma^{\prime}}+\sum_{\begin{subarray}{c}\sigma^{\prime}=1^{\oplus(j-1)}\\\
\sigma^{\prime}\textup{does not start with
}1^{\oplus(i-1)}\end{subarray}}^{m^{\oplus(j-1)}}W_{\sigma^{\prime}}\big{)}\Big{]}$
$\displaystyle\overset{\textup{(b)}}{\leq}$ $\displaystyle
m^{i-1}\left(m^{j-i}(q^{*})^{i-1+j-i}+m^{j-1}(q^{*})^{i-1+j-1}\right)$
$\displaystyle=$ $\displaystyle 2.$ (9)

Here (a) comes from the symmetry of trajectory tree. (b) is due to that at
step $j$, the children states of $s_{1^{\oplus(i-1)}}$ have dependency on it
and the other states are independent of it, and
$\mathbb{E}[W_{\sigma}W_{\sigma^{\prime}}]=\Pr[W_{\sigma}=1,W_{\sigma^{\prime}}=1]$
for any $\sigma,\sigma^{\prime}$. By plugging Eq. (9) into Eq. (8), we have
$\mathbb{E}[\omega^{2}]\leq\frac{H(H+1)}{2}+4\frac{H(H-1)}{2}\leq 3H^{2}$.
Thus, we obtain Lemma 5. ∎

##  Appendix C Proofs for Branching RL with Regret Minimization

In this section, we prove the regret upper bound for algorithm
$\mathtt{BranchVI}$ (Theorem 6) and the regret lower bounds for Branching RL-
RM in cases with Assumption 1 (Theorem 7) and without Assumption 1 (Theorem
2).

We first introduce some notations. Let Bernoulli random variable
$X_{k\sigma\ell}(s,a)$ denote whether $(s,a)$ was visited at indices $\sigma$
and $\sigma\oplus\ell$, respectively, in episode $k$, and
$w_{k\sigma\ell}(s,a):=\Pr[X_{k\sigma\ell}(s,a)]$. Let
$X_{k}(s,a):=\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}X_{k\sigma\ell}(s,a)$
denote the number of times that $(s,a)$ was visited in episode $k$, and
$w_{k}(s,a):=\mathbb{E}[X_{k}(s,a)]=\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}w_{k\sigma\ell}(s,a)$.

Let
$n^{k}_{\sigma\ell}(s,a):=\sum_{k^{\prime}<k}X_{k^{\prime}\sigma\ell}(s,a)$
denote the cumulative number of times that $(s,a)$ was visited at indices
$\sigma$ and $\sigma\oplus\ell$, respectively, up to episode $k$. Let
$n^{k}(s,a):=\sum_{k^{\prime}<k}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}X_{k\sigma\ell}(s,a)$
denote the _cumulative_ number of times that $(s,a)$ was visited up to episode
$k$.

In the following proofs, we make the convention that when $m=1$,
$\frac{m^{H+1}-m}{m-1}:=H$. Then, we have $X_{k}(s,a)\leq
m+m^{2}+\dots+m^{H}=\frac{m^{H+1}-m}{m-1}$ for any $m\geq 1$.

###  C.1 Proof of Regret Upper Bound

####  C.1.1 Concentration

In the following, we present several important concentration lemmas and define
concentration events.

######  Lemma 10 (Concentration of Trigger).

$\displaystyle\Pr\left[\left|\hat{q}^{k}(s,a)-q(s,a)\right|\leq
4\sqrt{\frac{\log\left(\frac{SNH(m^{H}\vee
K)}{\delta^{\prime}}\right)}{n^{k}(s,a)}},\
\forall(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times
A^{\mathtt{univ}},\forall k\in[K]\right]\geq 1-2\delta^{\prime}$

###### Proof of Lemma 10.

Since $n^{k}(s,a)\leq\frac{m^{H+1}-m}{m-1}K$, using the Hoeffding inequality
with a union bound over $(s,a)$ and $n^{k}(s,a)$, we have

$\displaystyle\Pr\left[\left|\hat{q}^{k}(s,a)-q(s,a)\right|\leq
2\sqrt{\frac{\log\left(\frac{SN}{\delta^{\prime}}\cdot\frac{m^{H+1}-m}{m-1}K\right)}{n^{k}(s,a)}},\
\forall(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times
A^{\mathtt{univ}},\forall k\in[K]\right]\geq 1-2\delta^{\prime}$

If $\frac{m^{H+1}-m}{m-1}\leq K$, then we have

$\log\left(\frac{SN}{\delta^{\prime}}\cdot\frac{m^{H+1}-m}{m-1}K\right)\leq
2\log\left(\frac{SNHK}{\delta^{\prime}}\right)$

If $\frac{m^{H+1}-m}{m-1}\geq K$, then using $\frac{m^{H+1}-m}{m-1}\leq
Hm^{2H}$, we have

$\displaystyle\log\left(\frac{SN}{\delta^{\prime}}\cdot\frac{m^{H+1}-m}{m-1}K\right)\leq$
$\displaystyle 2\log\left(\frac{SNHm^{2H}}{\delta^{\prime}}\right)$
$\displaystyle\leq$ $\displaystyle
4\log\left(\frac{SNHm^{H}}{\delta^{\prime}}\right)$

Combining the above two cases, we have

$\displaystyle\log\left(\frac{SN}{\delta^{\prime}}\cdot\frac{m^{H+1}-m}{m-1}K\right)\leq$
$\displaystyle 4\log\left(\frac{SNH(m^{H}\vee K)}{\delta^{\prime}}\right)$

Therefore, we have

$\displaystyle\Pr\left[\left|\hat{q}^{k}(s,a)-q(s,a)\right|\leq
4\sqrt{\frac{\log\left(\frac{SNH(m^{H}\vee
K)}{\delta^{\prime}}\right)}{n^{k}(s,a)}},\
\forall(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times
A^{\mathtt{univ}},\forall k\in[K]\right]\geq 1-2\delta^{\prime}$

∎

######  Lemma 11 (Concentration of Triggered Transition).

$\displaystyle\Pr\Bigg{[}$
$\displaystyle\left|\left(\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}V^{*}_{h+1}\right|\leq
4\sqrt{\frac{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)\log\left(\frac{SNH(m^{H}\vee
K)}{\delta^{\prime}}\right)}{n^{k}(s,a)}}$
$\displaystyle+\frac{4H\log\left(\frac{SNH(m^{H}\vee
K)}{\delta^{\prime}}\right)}{n^{k}(s,a)},\
\forall(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times
A^{\mathtt{univ}},\forall k\in[K]\Bigg{]}\geq 1-2\delta^{\prime}$

###### Proof of Lemma 11.

Using the similar analytical procedure as Lemma 10 and the Bernstein’s
inequality, we can obtain this lemma. ∎

######  Lemma 12 (Concentration of Variance).

$\displaystyle\Pr\Bigg{[}$
$\displaystyle\left|\sqrt{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(\bar{V}^{k}_{h+1}(s^{\prime})\right)}-\sqrt{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)}\right|\leq\sqrt{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-V^{*}_{h+1}(s^{\prime})\right)^{2}\right]}$
$\displaystyle\qquad+8H\sqrt{\frac{\log\left(\frac{SNH(m^{H}\vee
K)}{\delta^{\prime}}\right)}{n^{k}(s,a)}},\
\forall(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times
A^{\mathtt{univ}},\forall k\in[K]\Bigg{]}\geq 1-2\delta^{\prime}$ (10)

###### Proof of Lemma 12.

Using the similar analytical procedure as Lemma 10 and Proposition 2 (in
particular, Eq. (53)) in (Zanette & Brunskill, 2019), we can obtain

$\displaystyle\Pr\Bigg{[}$
$\displaystyle\left|\sqrt{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(V^{*}_{h+1}(s^{\prime})\right)}-\sqrt{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)}\right|\leq
8H\sqrt{\frac{\log\left(\frac{SNH(m^{H}\vee
K)}{\delta^{\prime}}\right)}{n^{k}(s,a)}},$ $\displaystyle\
\forall(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times
A^{\mathtt{univ}},\forall k\in[K]\Bigg{]}\geq 1-2\delta^{\prime}$ (11)

With probability $1-2\delta^{\prime}$, for any
$(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times A^{\mathtt{univ}}$ and
$k\in[K]$, we have

$\displaystyle\left|\sqrt{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(\bar{V}^{k}_{h+1}(s^{\prime})\right)}-\sqrt{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)}\right|$ $\displaystyle\leq$
$\displaystyle\left|\sqrt{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(\bar{V}^{k}_{h+1}(s^{\prime})\right)}-\sqrt{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(V^{*}_{h+1}(s^{\prime})\right)}\right|$
$\displaystyle+\left|\sqrt{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(V^{*}_{h+1}(s^{\prime})\right)}-\sqrt{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)}\right|$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\sqrt{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(\bar{V}^{k}_{h+1}(s^{\prime})-V^{*}_{h+1}(s^{\prime})\right)}+8H\sqrt{\frac{\log\left(\frac{SNH(m^{H}\vee
K)}{\delta^{\prime}}\right)}{n^{k}(s,a)}}$ $\displaystyle\leq$
$\displaystyle\sqrt{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-V^{*}_{h+1}(s^{\prime})\right)^{2}\right]}+8H\sqrt{\frac{\log\left(\frac{SNH(m^{H}\vee
K)}{\delta^{\prime}}\right)}{n^{k}(s,a)}}$

where (a) uses Proposition 2 (in particular, Eqs. (52)) in (Zanette &
Brunskill, 2019) and Eq. (11).

∎

To summarize the concentration lemmas used, we define the following
concentration events:

$\displaystyle\mathcal{E}_{\textup{tri}}:=$
$\displaystyle\left[\left|\hat{q}^{k}(s,a)-q(s,a)\right|\leq
4\sqrt{\frac{\log\left(\frac{SNH(m^{H}\vee
K)}{\delta^{\prime}}\right)}{n^{k}(s,a)}},\
\forall(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times
A^{\mathtt{univ}},\forall k\in[K]\right]$
$\displaystyle\mathcal{E}_{\textup{trans}}:=$
$\displaystyle\Bigg{[}\left|\left(\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}V^{*}_{h+1}\right|\leq
4\sqrt{\frac{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)\log\left(\frac{SNH(m^{H}\vee
K)}{\delta^{\prime}}\right)}{n^{k}(s,a)}}$
$\displaystyle+4\frac{H\log\left(\frac{SNH(m^{H}\vee
K)}{\delta^{\prime}}\right)}{n^{k}(s,a)},\
\forall(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times
A^{\mathtt{univ}},\forall k\in[K]\Bigg{]}$
$\displaystyle\mathcal{E}_{\textup{var}}:=$
$\displaystyle\Bigg{[}\left|\sqrt{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(\bar{V}^{k}_{h+1}(s^{\prime})\right)}-\sqrt{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)}\right|\leq\sqrt{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\bar{V}^{k}_{h+1}(s^{\prime})-V^{*}_{h+1}(s^{\prime})\right]^{2}}$
$\displaystyle\qquad+8H\sqrt{\frac{\log\left(\frac{SNH(m^{H}\vee
K)}{\delta^{\prime}}\right)}{n^{k}(s,a)}},\
\forall(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times
A^{\mathtt{univ}},\forall k\in[K]\Bigg{]}$ $\displaystyle\mathcal{E}:=$
$\displaystyle\mathcal{E}_{\textup{tri}}\cap\mathcal{E}_{\textup{trans}}\cap\mathcal{E}_{\textup{var}}$

######  Lemma 13.

Letting $\delta^{\prime}:=\frac{\delta}{6}$, the concentration event
$\mathcal{E}$ satisfies that

$\Pr\left[\mathcal{E}\right]\geq 1-6\delta^{\prime}=1-\delta$

###### Proof of Lemma 13.

We can obtain this lemma by combining Lemmas 10-12. ∎

####  C.1.2 Visitation

Below we present an important bound on visitation, which will be used in the
proof of Theorem 6.

######  Lemma 14 (Regret Bound of Visitation).

Suppose that the concentration event $\mathcal{E}$ holds. Then, it holds that

$\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}\leq SN\log\left(KH\right)$

###### Proof of Lemma 14.

$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\mathbb{E}_{(s_{\sigma},a_{\sigma\oplus\ell})\sim\pi^{k}}\left[\frac{1}{n^{k}(s_{\sigma},a_{\sigma\oplus\ell})}\cdot\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\right]$ $\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\mathbb{E}_{X_{k}\sim\pi^{k}}\left[\sum_{(s,a),s\neq
s_{\perp}}X_{k}(s,a)\frac{1}{n^{k}(s,a)}\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}_{X_{k}\sim\pi^{k}}\left[\sum_{(s,a),s\neq
s_{\perp}}\sum_{k=1}^{K}X_{k}(s,a)\frac{1}{n^{k}(s,a)}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{X_{k}\sim\pi^{k}}\left[\sum_{(s,a),s\neq
s_{\perp}}\sum_{k=1}^{K}X_{k}(s,a)\frac{1}{\sum_{k^{\prime}<k}X_{k^{\prime}}(s,a)}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{X_{k}\sim\pi^{k}}\left[\sum_{(s,a),s\neq
s_{\perp}}\log\left(\sum_{k=1}^{K}X_{k}(s,a)\right)\right]$
$\displaystyle\overset{\textup{(a)}}{\leq}$ $\displaystyle\sum_{(s,a),s\neq
s_{\perp}}\log\left(\mathbb{E}_{X_{k}\sim\pi^{k}}\left[\sum_{k=1}^{K}X_{k}(s,a)\right]\right)$
$\displaystyle\overset{\textup{(b)}}{\leq}$ $\displaystyle
SN\log\left(KH\right),$

where (a) uses Jensen’s inequality, and (b) is due to that for a fixed $(s,a)$
such that $s\neq s_{\perp}$,
$\mathbb{E}[X_{k}(s,a)]\leq\mathbb{E}[\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}]\leq H$, since a single base action cannot be chosen twice
in a state.

∎

####  C.1.3 Optimism and Pessimism

Next, we prove the optimism and pessimism of the constructed value functions
in algorithm $\mathtt{BranchVI}$, and bound the gap between optimistic and
pessimistic value functions. Recall that $L:=\log\left(\frac{SNH(m^{H}\vee
K)}{\delta^{\prime}}\right)$.

######  Lemma 15 (Optimism).

Suppose that the concentration event $\mathcal{E}$ holds. Then,

$\displaystyle\underline{V}^{k}_{h}(s)\leq
V^{*}_{h}(s)\leq\bar{V}^{k}_{h}(s),\ \forall s\in\mathcal{S},h\in[H],k\in[K]$

###### Proof of Lemma 15.

We prove this lemma by induction. Since
$\underline{V}^{k}_{H+1}(s)=V^{*}_{H+1}(s)=\bar{V}^{k}_{H+1}(s)=0,\forall
s\in\mathcal{S}$, it suffices to prove that if $\underline{V}^{k}_{h+1}(s)\leq
V^{*}_{h}(s)\leq\bar{V}^{k}_{h+1}(s),\forall s\in\mathcal{S}$, then
$\underline{V}^{k}_{h}(s)\leq V^{*}_{h}(s)\leq\bar{V}^{k}_{h}(s),\forall
s\in\mathcal{S}$.

First, we prove the optimistic direction, i.e., $\bar{V}^{k}_{h}(s)\geq
V^{*}_{h}(s),\ \forall s\in\mathcal{S}$. In the following, we prove
$\bar{Q}^{\pi^{k}}_{h}(s,A)\geq Q^{*}_{h}(s,A)$ for any $s\in\mathcal{S}$ and
$A\in\mathcal{A}$. If $\bar{Q}^{\pi^{k}}_{h}(s,A)=H$, then
$\bar{Q}^{\pi^{k}}_{h}(s,A)=H\geq Q^{*}_{h}(s,A)$ trivially holds. Otherwise,

$\displaystyle\bar{Q}^{\pi^{k}}_{h}(s,A)\geq$ $\displaystyle\sum_{a\in
A}\left(\left(\hat{q}^{k}(s,a)+b_{k}^{q}(s,a)\right)r(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\bar{V}^{k}_{h+1}+b_{k}^{qpV}(s,a)\right)$
$\displaystyle=$ $\displaystyle\sum_{a\in
A}\Bigg{(}\left(\hat{q}^{k}(s,a)+4\sqrt{\frac{L}{n^{k}(s,a)}}\right)r(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\bar{V}^{k}_{h+1}+4\sqrt{\frac{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(\bar{V}^{k}_{h+1}(s^{\prime})\right)L}{n^{k}(s,a)}}$
$\displaystyle+4\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}+\frac{36HL}{n^{k}(s,a)}\Bigg{)}$
$\displaystyle\geq$ $\displaystyle\sum_{a\in
A}\Bigg{(}q(s,a)r(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\bar{V}^{k}_{h+1}+4\sqrt{\frac{L}{n^{k}(s,a)}}\Big{(}\sqrt{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(\bar{V}^{k}_{h+1}(s^{\prime})\right)}$
$\displaystyle+\sqrt{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]}+8H\sqrt{\frac{L}{n^{k}(s,a)}}\Big{)}+\frac{4HL}{n^{k}(s,a)}\Bigg{)}$
$\displaystyle\overset{\textup{(a)}}{\geq}$ $\displaystyle\sum_{a\in
A}\left(q(s,a)r(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}V^{*}_{h+1}+4\sqrt{\frac{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)L}{n^{k}(s,a)}}+\frac{4HL}{n^{k}(s,a)}\right)$
$\displaystyle\overset{\textup{(b)}}{\geq}$ $\displaystyle\sum_{a\in
A}\left(q(s,a)r(s,a)+q(s,a)p(\cdot|s,a)^{\top}V^{*}_{h+1}\right)$
$\displaystyle=$ $\displaystyle Q^{*}_{h}(s,A),$

where (a) is due to the induction hypothesis and Lemma 12, and (b) comes from
Lemma 11.

Then, we have

$\displaystyle\bar{V}^{k}_{h}(s)=\bar{Q}^{k}_{h}(s,\pi^{k}(s))\geq\bar{Q}^{k}_{h}(s,\pi^{*}(s))\geq
Q^{*}_{h}(s,\pi^{*}(s))=V^{*}_{h}(s)$

Now, we prove the pessimistic direction, i.e., $\underline{V}^{k}_{h}(s)\leq
V^{*}_{h}(s),\ \forall s\in\mathcal{S}$. If $\underline{V}^{k}_{h}(s)=0$, then
$\underline{V}^{k}_{h}(s)=0\leq V^{*}_{h}(s)$ trivially holds. Otherwise,

$\displaystyle\underline{V}^{k}_{h}(s)=$ $\displaystyle\sum_{a\in
A}\left(\left(\hat{q}^{k}(s,a)-b_{k}^{q}(s,a)\right)r(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\underline{V}^{k}_{h+1}-b_{k}^{qpV}(s,a)\right)$
$\displaystyle=$
$\displaystyle\sum_{a\in\pi^{k}(s)}\Bigg{(}\left(\hat{q}^{k}(s,a)-4\sqrt{\frac{L}{n^{k}(s,a)}}\right)r(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\underline{V}^{k}_{h+1}-4\sqrt{\frac{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(\bar{V}^{k}_{h+1}(s^{\prime})\right)L}{n^{k}(s,a)}}$
$\displaystyle-4\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}-\frac{36HL}{n^{k}(s,a)}\Bigg{)}$
$\displaystyle\leq$
$\displaystyle\sum_{a\in\pi^{k}(s)}\Bigg{(}q(s,a)r(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\underline{V}^{k}_{h+1}-4\sqrt{\frac{L}{n^{k}(s,a)}}\Big{(}\sqrt{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(\bar{V}^{k}_{h+1}(s^{\prime})\right)}$
$\displaystyle+\sqrt{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]}+8H\sqrt{\frac{L}{n^{k}(s,a)}}\Big{)}-\frac{4HL}{n^{k}(s,a)}\Bigg{)}$
$\displaystyle\leq$
$\displaystyle\sum_{a\in\pi^{k}(s)}\left(q(s,a)r(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}V^{*}_{h+1}-4\sqrt{\frac{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)L}{n^{k}(s,a)}}-\frac{4HL}{n^{k}(s,a)}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{a\in\pi^{k}(s)}\left(q(s,a)r(s,a)+q(s,a)p(\cdot|s,a)^{\top}V^{*}_{h+1}\right)$
$\displaystyle=$ $\displaystyle Q^{*}_{h}(s,\pi^{k}(s))$ $\displaystyle\leq$
$\displaystyle Q^{*}_{h}(s,\pi^{*}(s))$ $\displaystyle=$ $\displaystyle
V^{*}_{h}(s)$

∎

######  Lemma 16 (Gap between Optimism and Pessimism).

Suppose that the concentration event $\mathcal{E}$ holds. Then, it holds that

$\displaystyle\bar{V}^{\pi^{k}}_{h}(s)\leq\sum_{\sigma^{\prime}=\emptyset}^{m^{\oplus(H-h)}}\sum_{\ell=1}^{m}\mathbb{E}\left[170HL\sqrt{\frac{S}{n^{k}(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})}}\cdot\mathbbm{1}\left\\{s_{\sigma\oplus\sigma^{\prime}}\neq
s_{\perp}\right\\}\Big{|}s_{\sigma}=s,\pi^{k}\right].$

In particular,

$\displaystyle\bar{V}^{\pi^{k}}_{1}(s)-\underline{V}^{\pi^{k}}_{1}(s)\leq\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\mathbb{E}\left[170HL\sqrt{\frac{S}{n^{k}(s_{\sigma},a_{\sigma\oplus\ell})}}\cdot\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\Big{|}s_{\emptyset}=s,\pi^{k}\right]$

###### Proof of Lemma 16.

According to the construction of optimistic and pessimistic value functions,
we have

$\left\\{\begin{aligned} \bar{V}^{\pi^{k}}_{h}(s)\leq&\sum_{a\in
A}\left(\left(\hat{q}^{k}(s,a)+b_{k}^{q}(s,a)\right)r(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\bar{V}^{k}_{h+1}+b_{k}^{qpV}(s,a)\right)\\\
\underline{V}^{\pi^{k}}_{h}(s)\geq&\sum_{a\in
A}\left(\left(\hat{q}^{k}(s,a)-b_{k}^{q}(s,a)\right)r(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\underline{V}^{k}_{h+1}-b_{k}^{qpV}(s,a)\right)\end{aligned}\right.$
(12)

Then,

$\displaystyle\bar{V}^{\pi^{k}}_{h}(s)-\underline{V}^{\pi^{k}}_{h}(s)\leq$
$\displaystyle\sum_{a\in
A}\left(2b_{k}^{q}(s,a)r(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\left(\bar{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)+2b_{k}^{qpV}(s,a)\right)$
$\displaystyle\leq$ $\displaystyle\sum_{a\in
A}\left(2b_{k}^{q}(s,a)r(s,a)+2b_{k}^{qpV}(s,a)+\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\left(\bar{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)\right)$
$\displaystyle\leq$ $\displaystyle\sum_{a\in
A}\Bigg{(}8\sqrt{\frac{L}{n^{k}(s,a)}}r(s,a)+8\sqrt{\frac{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(\bar{V}^{k}_{h+1}(s^{\prime})\right)L}{n^{k}(s,a)}}$
$\displaystyle\\!\\!+8\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}\\!+\\!\frac{72HL}{n^{k}(s,a)}\\!+\\!\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\left(\bar{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)\Bigg{)}$
$\displaystyle\leq$ $\displaystyle\sum_{a\in
A}\Bigg{(}8\sqrt{\frac{L}{n^{k}(s,a)}}r(s,a)+8\sqrt{\frac{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)L}{n^{k}(s,a)}}$
$\displaystyle+16\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}+\frac{136HL}{n^{k}(s,a)}+q(s,a)p(\cdot|s,a)^{\top}\left(\bar{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)$
$\displaystyle+\left(\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}\left(\bar{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)\Bigg{)}$
$\displaystyle\leq$ $\displaystyle\sum_{a\in
A}\Bigg{(}8\sqrt{\frac{L}{n^{k}(s,a)}}r(s,a)+8\sqrt{\frac{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)L}{n^{k}(s,a)}}$
$\displaystyle+16\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}+\frac{136HL}{n^{k}(s,a)}+q(s,a)p(\cdot|s,a)^{\top}\left(\bar{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)$
$\displaystyle+\|\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\|_{1}\|\bar{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\|_{\infty}\Bigg{)}$
$\displaystyle\leq$ $\displaystyle\sum_{a\in
A}\Bigg{(}8\sqrt{\frac{L}{n^{k}(s,a)}}r(s,a)+8\sqrt{\frac{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)L}{n^{k}(s,a)}}$
$\displaystyle+16\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}+\frac{136HL}{n^{k}(s,a)}+q(s,a)p(\cdot|s,a)^{\top}\left(\bar{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)$
$\displaystyle+H\sqrt{\frac{2SL}{n^{k}(s,a)}}\Bigg{)}$ $\displaystyle\leq$
$\displaystyle\sum_{a\in
A}\Bigg{(}170HL\sqrt{\frac{S}{n^{k}(s,a)}}+q(s,a)p(\cdot|s,a)^{\top}\left(\bar{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)\Bigg{)}$
$\displaystyle\leq$
$\displaystyle\sum_{\sigma^{\prime}=\emptyset}^{m^{\oplus(H-h)}}\sum_{\ell=1}^{m}\mathbb{E}\left[170HL\sqrt{\frac{S}{n^{k}(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})}}\cdot\mathbbm{1}\left\\{s_{\sigma\oplus\sigma^{\prime}}\neq
s_{\perp}\right\\}\Big{|}s_{\sigma}=s,\pi^{k}\right]$

Thus,

$\displaystyle\bar{V}^{\pi^{k}}_{1}(s)-\underline{V}^{\pi^{k}}_{1}(s)\leq\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\mathbb{E}\left[170HL\sqrt{\frac{S}{n^{k}(s_{\sigma},a_{\sigma\oplus\ell})}}\cdot\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\Big{|}s_{\emptyset}=s,\pi^{k}\right]$

∎

######  Lemma 17 (Cumulative Gap between Optimism and Pessimism).

Suppose that the concentration event $\mathcal{E}$ holds. Then, it holds that

$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sum_{s^{\prime}}q(s,a)p(s^{\prime}|s,a)\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\leq
28900mH^{4}L^{3}S^{3}N^{2}$

###### Proof of Lemma 17.

$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sum_{s^{\prime}\neq
s_{\perp}}q(s,a)p(s^{\prime}|s,a)\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\sum_{s^{\prime}\neq
s_{\perp}}w_{k\sigma\ell}(s,a)q(s,a)p(s^{\prime}|s,a)\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\sum_{s^{\prime}\neq
s_{\perp}}w_{k\sigma\ell}(s^{\prime},s,a)\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{s^{\prime}\neq
s_{\perp}}\tilde{w}_{k\sigma\ell}(s^{\prime})\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\mathbb{E}_{s_{\sigma\oplus\ell}\sim\pi^{k}}\left[\left(\bar{V}^{k}_{h+1}(s_{\sigma\oplus\ell})-\underline{V}^{k}_{h+1}(s_{\sigma\oplus\ell})\right)^{2}\right]$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\mathbb{E}_{s_{\sigma}\sim\pi^{k}}\left[\left(\bar{V}^{k}_{h}(s_{\sigma})-\underline{V}^{k}_{h}(s_{\sigma})\right)^{2}\right]$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\mathbb{E}_{s_{\sigma}\sim\pi^{k}}\left[\left(\left(\bar{V}^{k}_{h}(s_{\sigma})-\underline{V}^{k}_{h}(s_{\sigma})\right)\cdot\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\right)^{2}\right]$
$\displaystyle\overset{\textup{(a)}}{\leq}$
$\displaystyle\sum_{k=1}^{K}\\!\\!\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\\!\\!\sum_{\ell=1}^{m}\mathbb{E}_{s_{\sigma}\sim\pi^{k}}\left[\left(\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\cdot\\!\\!\\!\\!\\!\\!\sum_{\sigma^{\prime}=\emptyset}^{m^{\oplus(H-h)}}\\!\\!\sum_{\ell=1}^{m}\mathbb{E}\left[170HL\sqrt{\frac{S}{n^{k}(s_{\sigma\oplus\sigma^{\prime}},a_{\sigma\oplus\sigma^{\prime}\oplus\ell})}}\cdot\mathbbm{1}\left\\{s_{\sigma\oplus\sigma^{\prime}}\neq
s_{\perp}\right\\}\Big{|}s_{\sigma},\pi^{k}\right]\right)^{2}\right]$
$\displaystyle\leq$ $\displaystyle
28900H^{2}L^{2}\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\mathbb{E}_{s_{\sigma}\sim\pi^{k}}\left[\left(\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\cdot\mathbb{E}\left[\sum_{(s,a),s\neq
s_{\perp}}X_{k}(s,a)\sqrt{\frac{S}{n^{k}(s,a)}}\right]\right)^{2}\right]$
$\displaystyle=$ $\displaystyle
28900H^{2}L^{2}\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\mathbb{E}_{s_{\sigma}\sim\pi^{k}}\left[\left(\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\right)^{2}\cdot\left(\mathbb{E}\left[\sum_{(s,a),s\neq
s_{\perp}}X_{k}(s,a)\sqrt{\frac{S}{n^{k}(s,a)}}\right]\right)^{2}\right]$
$\displaystyle=$ $\displaystyle
28900H^{2}L^{2}\sum_{k=1}^{K}\left(\mathbb{E}\left[\sum_{(s,a),s\neq
s_{\perp}}X_{k}(s,a)\sqrt{\frac{S}{n^{k}(s,a)}}\right]\right)^{2}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\mathbb{E}_{s_{\sigma}\sim\pi^{k}}\left[\left(\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}\right)^{2}\right]$ $\displaystyle\leq$ $\displaystyle
28900H^{3}L^{2}\sum_{k=1}^{K}\left(\mathbb{E}\left[\sum_{(s,a),s\neq
s_{\perp}}X_{k}(s,a)\right]\right)^{2}\frac{S}{n^{k}(s,a)}$
$\displaystyle\overset{\textup{(b)}}{\leq}$ $\displaystyle
28900mH^{4}L^{2}\sum_{k=1}^{K}\mathbb{E}\left[\sum_{(s,a),s\neq
s_{\perp}}X_{k}(s,a)\right]\frac{S}{n^{k}(s,a)}$ $\displaystyle=$
$\displaystyle 28900mH^{4}L^{2}S\mathbb{E}\left[\sum_{(s,a),s\neq
s_{\perp}}\sum_{k=1}^{K}X_{k}(s,a)\frac{1}{n^{k}(s,a)}\right]$
$\displaystyle\overset{\textup{(c)}}{\leq}$ $\displaystyle
28900mH^{4}L^{3}S^{2}N$

where (a) uses Lemma 16, (b) is due to $\mathbb{E}\left[\sum_{(s,a),s\neq
s_{\perp}}X_{k}(s,a)\right]\leq
m\mathbb{E}[\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\mathbbm{1}\left\\{s_{\sigma}\neq
s_{\perp}\right\\}]\leq mH$ and (c) comes from Lemma 14.

∎

####  C.1.4 Proof of Theorem 6

Now we prove the regret upper bound (Theorem 6) for algorithm
$\mathtt{BranchVI}$.

###### Proof of Theorem 6.

Suppose that the concentration event $\mathcal{E}$ holds.

For any $k\in[K]$ and $(s,a)\in\mathcal{S}\setminus\\{s_{\perp}\\}\times
A^{\mathtt{univ}}$, let $\tilde{q}^{k}(s,a):=\hat{q}^{k}(s,a)+b_{k}^{q}(s,a)$,
$\tilde{q}^{k}(s,a)\tilde{p}^{k}(\cdot|s,a)^{\top}\bar{V}^{k}_{h+1}:=\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\bar{V}^{k}_{h+1}+b_{k}^{qpV}(s,a)$.

##### Step 1: Regret decomposition.

Using Lemma 3, we can decompose $\mathtt{Regret}(K)$ as follows:

$\displaystyle\mathtt{Regret}(K)=$
$\displaystyle\sum_{k=1}^{K}\left(V^{*}_{1}(s)-V^{\pi^{k}}_{1}(s)\right)$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\left(\bar{V}^{k}_{1}(s)-V^{\pi^{k}}_{1}(s)\right)$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\mathbb{E}\Big{[}\left(\tilde{q}^{k}(s_{\sigma},a_{\sigma\oplus\ell})-q(s_{\sigma},a_{\sigma\oplus\ell})\right)r(s_{\sigma},a_{\sigma\oplus\ell})$
$\displaystyle+\left(\tilde{q}^{k}(s_{\sigma},a_{\sigma\oplus\ell})\tilde{p}^{k}(\cdot|s_{\sigma},a_{\sigma\oplus\ell})-q(s_{\sigma},a_{\sigma\oplus\ell})p(\cdot|s_{\sigma},a_{\sigma\oplus\ell})\right)^{\top}\bar{V}^{k}_{h+1}\Big{]}$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\cdot$
$\displaystyle\left[\left(\tilde{q}^{k}(s,a)-q(s,a)\right)r(s,a)+\left(\tilde{q}^{k}(s,a)\tilde{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}\bar{V}^{k}_{h+1}\right]$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\Big{[}\underbrace{\left(\tilde{q}^{k}(s,a)-q(s,a)\right)r(s,a)}_{\mathtt{Term\
1}}$
$\displaystyle+\underbrace{\left(\tilde{q}^{k}(s,a)\tilde{p}^{k}(\cdot|s,a)-\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)\right)^{\top}\bar{V}^{k}_{h+1}}_{\mathtt{Term\
2}}+\underbrace{\left(\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}V^{*}_{h+1}}_{\mathtt{Term\
3}}$
$\displaystyle+\underbrace{\left(\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}\left(\bar{V}^{k}_{h+1}-V^{*}_{h+1}\right)}_{\mathtt{Term\
4}}\Big{]}$ (13)

##### Step 2: Bound the bonus term for triggered rewards – $\mathtt{Term\ 1}$.

$\displaystyle\mathtt{Term\ 1}=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\left(\left(\tilde{q}^{k}(s,a)-q(s,a)\right)r(s,a)\right)$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\left(\left(\hat{q}^{k}(s,a)+4\sqrt{\frac{L}{n^{k}(s,a)}}-q(s,a)\right)r(s,a)\right)$
$\displaystyle=$ $\displaystyle
8\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sqrt{\frac{L}{n^{k}(s,a)}}r(s,a)$
$\displaystyle\leq$ $\displaystyle
8\sqrt{L}\sqrt{\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}}\sqrt{\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)r^{2}(s,a)}$ $\displaystyle\leq$ $\displaystyle
8L\sqrt{SN\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\mathbb{E}\left[\mathbbm{1}\left\\{s^{k}_{\sigma\ell}\neq
s_{\perp}\right\\}\right]}$ $\displaystyle\overset{(a)}{\leq}$ $\displaystyle
8L\sqrt{mSNHK},$ (14)

where (a) uses Lemma 5.

##### Step 3: Bound the bonus term for triggered future values –
$\mathtt{Term\ 2}$.

$\displaystyle\mathtt{Term\ 2}=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\left(\tilde{q}^{k}(s,a)\tilde{p}^{k}(\cdot|s,a)-\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)\right)^{\top}\bar{V}^{k}_{h+1}$
$\displaystyle=$
$\displaystyle\\!\sum_{k=1}^{K}\\!\\!\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\\!\\!\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\Bigg{(}4\sqrt{\frac{\textup{Var}_{s^{\prime}\sim\hat{q},\hat{p}}\left(\bar{V}^{k}_{h+1}(s^{\prime})\right)L}{n^{k}(s,a)}}+4\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}$
$\displaystyle+\frac{36HL}{n^{k}(s,a)}\Bigg{)}$
$\displaystyle\overset{\textup{(a)}}{\leq}$
$\displaystyle\sum_{k=1}^{K}\\!\\!\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\\!\\!\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\Bigg{(}4\sqrt{\frac{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)L}{n^{k}(s,a)}}+8\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}$
$\displaystyle+\frac{68HL}{n^{k}(s,a)}\Bigg{)}$ $\displaystyle=$
$\displaystyle
4\sum_{k=1}^{K}\\!\\!\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\\!\\!\\!\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sqrt{\frac{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)L}{n^{k}(s,a)}}+68HL\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}$
$\displaystyle+8\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}$
$\displaystyle\leq$ $\displaystyle
4\sqrt{L}\sqrt{\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}}\sqrt{\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)}$
$\displaystyle+68HL\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}$
$\displaystyle+8\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}$
$\displaystyle\overset{(b)}{\leq}$ $\displaystyle
4L\sqrt{SN\sum_{k=1}^{K}\mathbb{E}_{\pi^{k}}\left[\sum_{h=1}^{H}\sum_{\ell=1}^{m^{h}}\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)\right]}+68SNHL^{2}$
$\displaystyle+8\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}$
$\displaystyle\overset{(c)}{\leq}$ $\displaystyle
4L\sqrt{3SNKH^{2}}+68SNHL^{2}+8\underbrace{\sum_{k=1}^{K}\\!\\!\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\\!\\!\sum_{\ell=1}^{m}\\!\sum_{(s,a),s\neq
s_{\perp}}\\!\\!\\!\\!\\!w_{k\sigma\ell}(s,a)\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}}_{\mathtt{Term\
2.1}},$ (15)

where (a) uses Lemma 12, (b) comes from Lemma 14 and (c) is due to Lemma 4.

Then, we bound $\mathtt{Term\ 2.1}$ as follows:

$\displaystyle\mathtt{Term\ 2.1}$ (16) $\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}$
$\displaystyle\leq$
$\displaystyle\sqrt{L}\\!\sqrt{\sum_{k=1}^{K}\\!\\!\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\\!\\!\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}}\cdot$
$\displaystyle\sqrt{\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}}$
$\displaystyle\leq$
$\displaystyle\sqrt{L}\\!\sqrt{\sum_{k=1}^{K}\\!\\!\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\\!\\!\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}}\cdot$
$\displaystyle\Bigg{(}\sqrt{\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)q(s,a)p(\cdot|s,a)^{\top}\\!\\!\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}}\\!+\\!$
$\displaystyle\sqrt{\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\left(\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}}\Bigg{)}$
$\displaystyle\leq$
$\displaystyle\\!\sqrt{L}\\!\sqrt{\sum_{k=1}^{K}\\!\\!\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\\!\\!\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}}\cdot$
$\displaystyle\Bigg{(}\sqrt{\sum_{k=1}^{K}\\!\\!\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\\!\\!\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)q(s,a)p(\cdot|s,a)^{\top}\\!\\!\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}}\\!+\\!$
$\displaystyle\sqrt{\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\left|\left(\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right|}\Bigg{)}$
$\displaystyle\leq$
$\displaystyle\\!\sqrt{L}\\!\sqrt{\sum_{k=1}^{K}\\!\\!\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\\!\\!\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}}\cdot$
$\displaystyle\Bigg{(}\sqrt{\sum_{k=1}^{K}\\!\\!\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\\!\\!\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)q(s,a)p(\cdot|s,a)^{\top}\\!\\!\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}}\\!+\\!$
$\displaystyle\sqrt{H}\sqrt{\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\left|\left(\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)\right|}\Bigg{)}$
$\displaystyle\overset{\textup{(a)}}{\leq}$
$\displaystyle\sqrt{L}\sqrt{SNL}\left(\sqrt{28900mH^{4}L^{3}S^{2}N}+\sqrt{H}\sqrt{170S^{2}NH^{2}L^{2}\sqrt{mL}}\right)$
$\displaystyle\leq$ $\displaystyle 184SNH^{2}L^{2}\sqrt{mSL}$ (17)

where (a) comes from Lemmas 14,17 and Eq. (20) (the upper bound of
$\mathtt{Term\ 4}$).

Plugging Eq. (17) into Eq. (15), we obtain

$\displaystyle\mathtt{Term\ 2}=$ $\displaystyle
4L\sqrt{3SNKH^{2}}\\!+\\!68SNHL^{2}\\!+\\!8\underbrace{\sum_{k=1}^{K}\\!\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\\!\\!\sum_{\ell=1}^{m}\\!\sum_{(s,a),s\neq
s_{\perp}}\\!\\!\\!\\!\\!w_{k\sigma\ell}(s,a)\sqrt{\frac{\mathbb{E}_{s^{\prime}\sim\hat{q},\hat{p}}\left[\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}\right]L}{n^{k}(s,a)}}}_{\mathtt{Term\
2.1}}$ $\displaystyle\leq$ $\displaystyle
8HL\sqrt{SNK}+68SNHL^{2}+1472SNH^{2}L^{2}\sqrt{mSL}$ $\displaystyle\leq$
$\displaystyle 8HL\sqrt{SNK}+1540SNH^{2}L^{2}\sqrt{mSL}$ (18)

##### Step 4: Bound the estimate deviation term for triggered future values –
$\mathtt{Term\ 3}$.

$\displaystyle\mathtt{Term\ 3}=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\left(\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}V^{*}_{h+1}$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\left(4\sqrt{\frac{\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)L}{n^{k}(s,a)}}+\frac{4HL}{n^{k}(s,a)}\right)$
$\displaystyle\leq$ $\displaystyle
4\sqrt{L}\sqrt{\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}}\sqrt{\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)}$
$\displaystyle+4HL\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}$ $\displaystyle\leq$
$\displaystyle
4L\sqrt{SN\sum_{k=1}^{K}\mathbb{E}_{\pi^{k}}\left[\sum_{h=1}^{H}\sum_{\ell=1}^{m^{h}}\textup{Var}_{s^{\prime}\sim
q,p}\left(V^{*}_{h+1}(s^{\prime})\right)\right]}+4SNHL^{2}$
$\displaystyle\overset{\textup{(a)}}{\leq}$ $\displaystyle
4L\sqrt{3SNKH^{2}}+4SNHL^{2}$ $\displaystyle\leq$ $\displaystyle
8HL\sqrt{SNK}+4SNHL^{2},$ (19)

where (a) comes from Lemma 4.

##### Step 5: Bound the second order term. – $\mathtt{Term\ 4}$.

$\displaystyle\mathtt{Term\ 4}=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\left(\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}\left(\bar{V}^{k}_{h+1}-V^{*}_{h+1}\right)$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sum_{s^{\prime}}\left(\hat{q}^{k}(s,a)\hat{p}^{k}(s^{\prime}|s,a)-q(s,a)p(s^{\prime}|s,a)\right)\left(\bar{V}^{k}_{h+1}(s^{\prime})-V^{*}_{h+1}(s^{\prime})\right)$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sum_{s^{\prime}}\left|\hat{q}^{k}(s,a)\hat{p}^{k}(s^{\prime}|s,a)-q(s,a)p(s^{\prime}|s,a)\right|\cdot\left(\bar{V}^{k}_{h+1}(s^{\prime})-V^{*}_{h+1}(s^{\prime})\right)$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\cdot$
$\displaystyle\sum_{s^{\prime}}\left(\sqrt{\frac{q(s,a)p(s^{\prime}|s,a)\left(1-q(s,a)p(s^{\prime}|s,a)\right)L}{n^{k}(s,a)}}+\frac{L}{n^{k}(s,a)}\right)\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sum_{s^{\prime}}\sqrt{\frac{q(s,a)p(s^{\prime}|s,a)L}{n^{k}(s,a)}}\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)$
$\displaystyle+\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sum_{s^{\prime}}\frac{HL}{n^{k}(s,a)}$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sqrt{SL\cdot\sum_{s^{\prime}}\frac{q(s,a)p(s^{\prime}|s,a)}{n^{k}(s,a)}\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}}$
$\displaystyle+\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\frac{SHL}{n^{k}(s,a)}$ $\displaystyle\leq$
$\displaystyle\sqrt{SL}\sqrt{\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}}\cdot$
$\displaystyle\sqrt{\underbrace{\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\sum_{s^{\prime}}q(s,a)p(s^{\prime}|s,a)\left(\bar{V}^{k}_{h+1}(s^{\prime})-\underline{V}^{k}_{h+1}(s^{\prime})\right)^{2}}_{\mathtt{Term\
4.1}}}$
$\displaystyle+SHL\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}\frac{w_{k\sigma\ell}(s,a)}{n^{k}(s,a)}$
$\displaystyle\overset{\textup{(a)}}{\leq}$
$\displaystyle\sqrt{SL}\sqrt{SNL}\sqrt{28900mH^{4}L^{3}S^{2}N}+S^{2}NHL^{2}$
$\displaystyle\leq$ $\displaystyle 170S^{2}NH^{2}L^{2}\sqrt{mL}$ (20)

where (a) is due to Lemmas 14,17.

Finally, we combine the upper bounds of $\mathtt{Term\ 1}$, $\mathtt{Term\
2}$, $\mathtt{Term\ 3}$, $\mathtt{Term\ 4}$ and the minimal regret
contribution to bound the total regret.

Plugging Eqs. (14),(18),(19) and (20) into Eq. (13), we have

$\displaystyle\mathtt{Regret}(K)$ $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\sum_{\sigma=\emptyset}^{m^{\oplus(H-1)}}\sum_{\ell=1}^{m}\sum_{(s,a),s\neq
s_{\perp}}w_{k\sigma\ell}(s,a)\Big{[}\underbrace{\left(\tilde{q}^{k}(s,a)-q(s,a)\right)r(s,a)}_{\mathtt{Term\
1}}+\underbrace{\left(\tilde{q}^{k}(s,a)\tilde{p}^{k}(\cdot|s,a)-\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)\right)^{\top}\bar{V}^{k}_{h+1}}_{\mathtt{Term\
2}}$
$\displaystyle+\underbrace{\left(\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}V^{*}_{h+1}}_{\mathtt{Term\
3}}+\underbrace{\left(\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)-q(s,a)p(\cdot|s,a)\right)^{\top}\left(\bar{V}^{k}_{h+1}-V^{*}_{h+1}\right)}_{\mathtt{Term\
4}}\Big{]}$ $\displaystyle\leq$ $\displaystyle
8L\sqrt{mSNHK}+8HL\sqrt{SNK}+1540SNH^{2}L^{2}\sqrt{mSL}+8HL\sqrt{SNK}+4SNHL^{2}$
$\displaystyle+170S^{2}NH^{2}L^{2}\sqrt{mL}$ $\displaystyle=$ $\displaystyle
O\left(HL\sqrt{SNK}\right)$

∎

###  C.2 Regret Lower Bound

In this subsection, we prove the regret lower bounds for branching RL-RM in
cases with Assumption 1 (Theorem 7) and without Assumption 1 (Theorem 2).

####  C.2.1 Proof of Theorem 7

###### Proof of Theorem 7.

Figure 3: The constructed instance with $m=2$ in regret lower bound analysis.

As shown in Figure 3, consider a random instance as follows: There are $N$
base actions, i.e., $A^{\mathtt{univ}}=\\{a_{1},\dots,a_{N}\\}$, and
$d:=\frac{N}{m}$ super actions, i.e.,
$A_{1}=\\{a_{1},\dots,a_{m}\\},A_{2}=\\{a_{m+1},\dots,a_{2m}\\},\dots,A_{d}=\\{a_{m(d-1)+1},\dots,a_{md}\\}$.
The action set is $\mathcal{A}=\\{A_{1},\dots,A_{d}\\}$. The state set is
$\mathcal{S}=\\{s_{\perp},s_{1},s_{2},x_{1},\dots,x_{S-3}\\}$.

The trigger probabilities are as follows: $q(s_{1},a)=q(s_{2},a)=\alpha+\eta$
and $q(s_{\perp},a)=0$ for any $a\in A^{\mathtt{univ}}$.

The transition distributions are as follows: $s_{1}$ is the initial state.
$p(x_{i}|s_{1},a)=\frac{1}{S-3}$ for any $a\in A^{\mathtt{univ}}$.
$p(s_{2}|x_{i},a)=1$ for any $a\in A^{\mathtt{univ}},i\in[S-3]$.
$p(s_{2}|s_{2},a)=1$ and $p(s_{\perp}|s_{\perp},a)=1$ for any $a\in
A^{\mathtt{univ}}$.

The reward function is only dependent on the current state. $r(s,a)=1$ for any
$s\in\mathcal{S}\setminus\\{s_{\perp}\\},a\in A^{\mathtt{univ}}$, and
$r(s_{\perp},a)=0$ for any $a\in A^{\mathtt{univ}}$.

The randomness of this instance is as follows: for each
$x_{i}\in\\{x_{1},\dots,x_{S-3}\\}$, we uniformly choose an action
$A_{j}(x_{i})$ from $A_{1},\dots,A_{d}$ as the optimal action. Let
$q(x_{i},a)=\alpha+\eta$ for all $a\in A_{j}(x_{i})$, and $q(x_{i},a)=\alpha$
for all $a\notin A_{j}(x_{i})$. Let $\alpha+\eta=\frac{1}{m}$.

In words, in each episode, at step $1$, an agent starts from state $s_{1}$ and
takes an action that contains $m$ base actions, where each base action has
trigger probability $\alpha+\eta$. For each state-base action pair at step
$1$, if triggered successfully, it transitions to
$x_{i}\in\\{x_{1},\dots,x_{S-3}\\}$ with probability $\frac{1}{S-3}$;
Otherwise, if triggered successfully, it transitions to ending state
$s_{\perp}$. At step $1$, in a bandit state $x_{i}$, the agent takes an action
$A\in\mathcal{A}$ that contains $m$ base actions, where each base action has
trigger probability $\alpha+\eta$ if $A=A_{j}(x_{i})$, and has trigger
probability only $\alpha$ if $A\neq A_{j}(x_{i})$. At step $2$, for each
state-base action pair, if triggered successfully, it transitions to $s_{2}$;
Otherwise, it transitions to $s_{\perp}$. At step $3$, starting from state
$s_{2}$, the agent takes an action where each contained base action has
trigger probability $\alpha+\eta$. For each state-base action pair at step
$3$, if triggered successfully, it still transitions back to $s_{2}$;
Otherwise, it transitions to $s_{\perp}$. The following steps $4,\dots,H$ are
similar to step $3$, where the agent starts from $s_{2}$ and transitions back
to $s_{2}$ or transitions to $s_{\perp}$.

The optimal policy $\pi_{*}$ is to take action $A_{j}(x_{i})$ at state
$x_{i}$, and we have

$\displaystyle\mathbb{E}[\mathtt{Reward}^{\pi_{*}}]=\mathbb{E}\left[\sum_{k=1}^{K}V^{*}_{1}(s_{1})\right]=K\left(m(\alpha+\eta)+m^{2}(\alpha+\eta)^{2}+\dots+m^{H}(\alpha+\eta)^{H}\right)=HK$
(21)

Fix an algorithm $\mathbb{A}$. Let $\pi^{k}$ denote the policy taken by
$\mathbb{A}$ in episode $k$. For each $x_{i}\in\\{x_{1},\dots,x_{S-3}\\}$, let
$T_{x_{i},A_{j}(x_{i})}:=\sum_{k=1}^{K}\mathbbm{1}\left\\{\pi^{k}(x_{i})=A_{j}(x_{i})\right\\}$
denote the number of episodes where $\mathbb{A}$ chooses $A_{j}(x_{i})$ in
state $x_{i}$. Then, the number of episodes where $\mathbb{A}$ chooses
suboptimal actions in state $x_{i}$ is $K-T_{x_{i},A_{j}(x_{i})}$.

$\displaystyle\mathbb{E}[\mathtt{Reward}^{\mathbb{A}}]=$
$\displaystyle\mathbb{E}\left[\sum_{k=1}^{K}V^{\pi^{k}}_{1}(s_{1})\right]$
$\displaystyle=$ $\displaystyle
Km(\alpha+\eta)+\frac{1}{(S-3)d}\sum_{i=1}^{S-3}\sum_{j=1}^{d}\mathbb{E}\Big{[}T_{x_{i},A_{j}(x_{i})}\left(m^{2}(\alpha+\eta)^{2}+\dots+m^{H}(\alpha+\eta)^{H}\right)$
$\displaystyle+\left(K-T_{x_{i},A_{j}(x_{i})}\right)\left(m^{2}(\alpha+\eta)\alpha+m^{3}(\alpha+\eta)\alpha(\alpha+\eta)+\dots+m^{H}(\alpha+\eta)\alpha(\alpha+\eta)^{H-2}\right)\Big{]}$
$\displaystyle=$ $\displaystyle
Km(\alpha+\eta)+\frac{1}{(S-3)d}\sum_{i=1}^{S-3}\sum_{j=1}^{d}\mathbb{E}\Big{[}T_{x_{i},A_{j}(x_{i})}\left(m^{2}(\alpha+\eta)^{2}+\dots+m^{H}(\alpha+\eta)^{H}\right)$
$\displaystyle+\left(K-T_{x_{i},A_{j}(x_{i})}\right)\left(m^{2}(\alpha+\eta)\alpha+m^{3}(\alpha+\eta)^{2}\alpha+\dots+m^{H}(\alpha+\eta)^{H-1}\alpha\right)\Big{]}$
(22)

Subtracting Eq. (22) by Eq. (21), we have

$\displaystyle\mathbb{E}[\mathtt{Regret}^{\mathbb{A}}]=$
$\displaystyle\mathbb{E}[\mathtt{Reward}^{\pi_{*}}]-\mathbb{E}[\mathtt{Reward}^{\mathbb{A}}]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{k=1}^{K}\left(V^{*}_{1}(s_{1})-V^{\pi^{k}}_{1}(s_{1})\right)\right]$
$\displaystyle=$
$\displaystyle\frac{1}{(S-3)d}\sum_{i=1}^{S-3}\sum_{j=1}^{d}\mathbb{E}\Big{[}\\!\\!\left(K-T_{x_{i},A_{j}(x_{i})}\right)\\!\left(m(\alpha+\eta)m\eta+m^{2}(\alpha+\eta)^{2}m\eta+\dots+m^{H-1}(\alpha+\eta)^{H-1}m\eta\right)\\!\\!\Big{]}$
$\displaystyle=$
$\displaystyle\frac{1}{(S-3)d}\sum_{i=1}^{S-3}\sum_{j=1}^{d}\mathbb{E}\Big{[}\left(K-T_{x_{i},A_{j}(x_{i})}\right)(H-1)m\eta\Big{]}$
$\displaystyle=$ $\displaystyle
m\eta(H-1)\left(K-\frac{1}{(S-3)d}\sum_{i=1}^{S-3}\sum_{j=1}^{d}\mathbb{E}\left[T_{x_{i},A_{j}(x_{i})}\right]\right)$
(23)

Let $\mathbb{E}_{A_{j}(x_{i})}[\cdot]$ denote the expectation operator under
the instance $\mathcal{I}_{A_{j}(x_{i})}$ where the optimal action of state
$x_{i}$ is $A_{j}(x_{i})$.

Let $\mathbb{E}_{x_{i},\mathtt{unif}}[\cdot]$ denote the expectation operator
under the instance where all actions $A\in\mathcal{A}$ at state $x_{i}$ have
the same trigger probability, i.e., $q(x_{i},a)=\alpha$ for any $a\in
A^{\mathtt{univ}}$, and other distribution settings are the same as
$\mathcal{I}_{A_{j}(x_{i})}$.

Note that the KL-divergence between the above two instances is
$m\cdot\textup{KL}\left(\mathtt{Bernoulli}(\alpha)||\mathtt{Bernoulli}(\alpha+\eta)\right)\leq
m\cdot\frac{\eta^{2}}{(\alpha+\eta)(1-(\alpha+\eta))}\leq
m\cdot\frac{\eta^{2}}{c_{1}}$ with $(\alpha+\eta)(1-(\alpha+\eta))\geq c_{1}$
for some absolute positive constant $c_{1}$. After a pull of
$(x_{i},A_{j}(x_{i}))$, we receive an observation of such difference between
the two instances.

Using Lemma A.1 in (Auer et al., 2002), we have

$\displaystyle\mathbb{E}_{A_{j}(x_{i})}\left[T_{x_{i},A_{j}(x_{i})}\right]\leq$
$\displaystyle\mathbb{E}_{x_{i},\mathtt{unif}}\left[T_{x_{i},A_{j}(x_{i})}\right]$
$\displaystyle+\frac{K}{2}\sqrt{\frac{1}{2}\cdot\frac{1}{S-3}\mathbb{E}_{x_{i},\mathtt{unif}}\left[T_{x_{i},A_{j}(x_{i})}\right]\cdot
m\textup{KL}\left(\mathtt{Bernoulli}(\alpha)||\mathtt{Bernoulli}(\alpha+\eta)\right)}$
$\displaystyle\overset{\textup{(a)}}{\leq}$
$\displaystyle\mathbb{E}_{x_{i},\mathtt{unif}}\left[T_{x_{i},A_{j}(x_{i})}\right]+\frac{K}{2}\sqrt{\frac{m}{2c_{1}(S-3)}\mathbb{E}_{x_{i},\mathtt{unif}}\left[T_{x_{i},A_{j}(x_{i})}\right]\eta^{2}}$
$\displaystyle=$
$\displaystyle\mathbb{E}_{x_{i},\mathtt{unif}}\left[T_{x_{i},A_{j}(x_{i})}\right]+\frac{K\eta}{2}\sqrt{\frac{m}{2c_{1}(S-3)}\mathbb{E}_{x_{i},\mathtt{unif}}\left[T_{x_{i},A_{j}(x_{i})}\right]}$

Since
$\sum_{j=1}^{d}\mathbb{E}_{x_{i},\mathtt{unif}}\left[T_{x_{i},A_{j}(x_{i})}\right]=\sum_{j=1}^{d}\sum_{k=1}^{K}\mathbb{E}_{x_{i},\mathtt{unif}}\left[\pi^{k}(A_{j}(x_{i})|x_{i})\right]=K$,
we have

$\displaystyle\sum_{j=1}^{d}\mathbb{E}_{A_{j}(x_{i})}\left[T_{x_{i},A_{j}(x_{i})}\right]\leq$
$\displaystyle\sum_{j=1}^{d}\mathbb{E}_{x_{i},\mathtt{unif}}\left[T_{x_{i},A_{j}(x_{i})}\right]+\frac{K\eta}{2}\sum_{j=1}^{d}\sqrt{\frac{m}{2c_{1}(S-3)}\mathbb{E}_{x_{i},\mathtt{unif}}\left[T_{x_{i},A_{j}(x_{i})}\right]}$
$\displaystyle\leq$
$\displaystyle\sum_{j=1}^{d}\mathbb{E}_{x_{i},\mathtt{unif}}\left[T_{x_{i},A_{j}(x_{i})}\right]+\frac{K\eta}{2}\sqrt{\frac{dm}{2c_{1}(S-3)}\sum_{j=1}^{d}\mathbb{E}_{x_{i},\mathtt{unif}}\left[T_{x_{i},A_{j}(x_{i})}\right]}$
$\displaystyle=$ $\displaystyle
K+\frac{K\eta}{2}\sqrt{\frac{dmK}{2c_{1}(S-3)}}$

and thus

$\displaystyle\frac{1}{(S-3)d}\sum_{i=1}^{S-1}\sum_{j=1}^{d}\mathbb{E}_{A_{j}(x_{i})}\left[T_{x_{i},A_{j}(x_{i})}\right]\leq$
$\displaystyle\frac{1}{d}\left(K+\frac{K\eta}{2}\sqrt{\frac{dmK}{2c_{1}(S-3)}}\right)$
$\displaystyle=$ $\displaystyle
K\left(\frac{1}{d}+\frac{\eta}{2}\sqrt{\frac{mK}{2c_{1}d(S-3)}}\right)$ (24)

Plugging Eq. (24) into Eq. (23), we obtain

$\displaystyle\mathbb{E}[\mathtt{Regret}^{\mathbb{A}}]\geq$ $\displaystyle
m\eta(H-1)\left(K-\frac{1}{(S-3)d}\sum_{i=1}^{S-3}\sum_{j=1}^{d}\mathbb{E}\left[T_{x_{i},A_{j}(x_{i})}\right]\right)$
$\displaystyle\geq$ $\displaystyle
m\eta(H-1)K\left(1-\frac{1}{d}-\frac{\eta}{2}\sqrt{\frac{mK}{2c_{1}d(S-3)}}\right)$
(25)

Let $\eta=c_{2}\sqrt{\frac{d(S-3)}{mK}}$ for some small enough constant
$c_{2}$, we have

$\displaystyle\mathbb{E}[\mathtt{Regret}^{\mathbb{A}}]=$
$\displaystyle\Omega\left((H-1)\sqrt{(S-3)dmK}\right)$ $\displaystyle=$
$\displaystyle\Omega\left(H\sqrt{SNK}\right)$

∎

####  C.2.2 Proof of Theorem 2

###### Proof of Theorem 2.

This proof uses the same instance and analytical procedure as the proof of
Theorem 7, except that we set $\alpha+\eta=\bar{q}$ for some trigger
probability threshold $\bar{q}>\frac{1}{m}$.

Then, Eq. (23) becomes

$\displaystyle\mathbb{E}[\mathtt{Regret}^{\mathbb{A}}]=$
$\displaystyle\mathbb{E}[\mathtt{Reward}^{\pi_{*}}]-\mathbb{E}[\mathtt{Reward}^{\mathbb{A}}]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\sum_{k=1}^{K}\left(V^{*}_{1}(s_{1})-V^{\pi^{k}}_{1}(s_{1})\right)\right]$
$\displaystyle=$
$\displaystyle\frac{1}{(S-3)d}\\!\sum_{i=1}^{S-3}\sum_{j=1}^{d}\\!\mathbb{E}\Big{[}\\!\\!\left(K-T_{x_{i},A_{j}(x_{i})}\right)\\!\left(m\bar{q}\cdot
m\eta+m^{2}\bar{q}^{2}\cdot m\eta+\dots+m^{H-1}\bar{q}^{H-1}\cdot
m\eta\right)\\!\\!\Big{]}$ $\displaystyle=$
$\displaystyle\frac{1}{(S-3)d}\sum_{i=1}^{S-3}\sum_{j=1}^{d}\mathbb{E}\Big{[}\left(K-T_{x_{i},A_{j}(x_{i})}\right)\frac{m\bar{q}\left((m\bar{q})^{H-1}-1\right)}{m\bar{q}-1}\cdot
m\eta\Big{]}$ $\displaystyle=$
$\displaystyle\frac{m\bar{q}\left((m\bar{q})^{H-1}-1\right)}{m\bar{q}-1}\cdot
m\eta\left(K-\frac{1}{(S-3)d}\sum_{i=1}^{S-3}\sum_{j=1}^{d}\mathbb{E}\left[T_{x_{i},A_{j}(x_{i})}\right]\right)$
(26)

and Eq (25) becomes

$\displaystyle\mathbb{E}[\mathtt{Regret}^{\mathbb{A}}]\geq$
$\displaystyle\frac{m\bar{q}\left((m\bar{q})^{H-1}-1\right)}{m\bar{q}-1}\cdot
m\eta\left(K-\frac{1}{(S-3)d}\sum_{i=1}^{S-3}\sum_{j=1}^{d}\mathbb{E}\left[T_{x_{i},A_{j}(x_{i})}\right]\right)$
(27) $\displaystyle\geq$
$\displaystyle\frac{m\bar{q}\left((m\bar{q})^{H-1}-1\right)}{m\bar{q}-1}\cdot
m\eta
K\left(1-\frac{1}{d}-\frac{\eta}{2}\sqrt{\frac{mK}{2c_{1}d(S-3)}}\right)$ (28)

Let $\eta=c_{2}\sqrt{\frac{d(S-3)}{mK}}$ for some small enough constant
$c_{2}$, we have

$\displaystyle\mathbb{E}[\mathtt{Regret}^{\mathbb{A}}]=$
$\displaystyle\Omega\left(\frac{m\bar{q}\left((m\bar{q})^{H-1}-1\right)}{m\bar{q}-1}\sqrt{(S-3)dmK}\right)$
$\displaystyle=$
$\displaystyle\Omega\left(\frac{m\bar{q}\left((m\bar{q})^{H-1}-1\right)}{m\bar{q}-1}\sqrt{SNK}\right)$

Therefore, when relaxing the trigger probability threshold in Assumption 1 to
some $\bar{q}>\frac{1}{m}$, any algorithm for branching RL-RM must suffer an
exponential regret.

∎

##  Appendix D Proofs for Branching RL with Reward-Free Exploration

In this section, we prove sample complexity upper and lower bounds (Theorems
8,9) for branching RL-RFE.

###  D.1 Proof for Sample Complexity Upper Bound

####  D.1.1 Augmented Transition Distribution

First, we introduce an augmented transition distribution
$p^{\mathtt{aug}}(\cdot|s,a)$ and connect it with trigger distribution
$q(s,a)$ and transition distribution $p(\cdot|s,a)$.

For any $(s,a)\in\mathcal{S}\times A^{\mathtt{univ}}$, let
$p^{\mathtt{aug}}(\cdot|s,a)$ denote the augmented transition distribution on
$\mathcal{S}$, which satisfies that

$\displaystyle p^{\mathtt{aug}}(s_{\perp}|s,a)$ $\displaystyle=1-q(s,a),$
$\displaystyle p^{\mathtt{aug}}(s^{\prime}|s,a)$
$\displaystyle=q(s,a)p(s^{\prime}|s,a),\ \forall
s^{\prime}\in\mathcal{S}\setminus\\{s_{\perp}\\}.$

For any episode $k$, we can also define the empirical augmented transition
distribution as

$\displaystyle\hat{p}^{\mathtt{aug},k}(s_{\perp}|s,a)$
$\displaystyle=1-\hat{q}^{k}(s,a),$
$\displaystyle\hat{p}^{\mathtt{aug},k}(s^{\prime}|s,a)$
$\displaystyle=\hat{q}^{k}(s,a)\hat{p}^{k}(s^{\prime}|s,a),\ \forall
s^{\prime}\in\mathcal{S}\setminus\\{s_{\perp}\\}.$

######  Lemma 18.

For any function $f(\cdot)$ defined on $\mathcal{S}$ such that
$f(s_{\perp})=0$ (e.g., $f$ can be the value function $V^{\pi}_{h}(\cdot)$,
$\forall h\in[H],\pi$), it holds that

$\displaystyle p^{\mathtt{aug}}(\cdot|s,a)^{\top}f$
$\displaystyle=q(s,a)p(\cdot|s,a)^{\top}f,$ (29)
$\displaystyle\hat{p}^{\mathtt{aug},k}(\cdot|s,a)^{\top}V_{h+1}$
$\displaystyle=\hat{q}^{k}(s,a)\hat{p}^{k}(\cdot|s,a)^{\top}f.$ (30)

###### Proof of Lemma 18.

We prove Eq. (29) as follows:

$\displaystyle p^{\mathtt{aug}}(\cdot|s,a)^{\top}f$
$\displaystyle=\sum_{s^{\prime}\in\mathcal{S}}p^{\mathtt{aug}}(s^{\prime}|s,a)f(s^{\prime})$
$\displaystyle=\sum_{s^{\prime}\in\mathcal{S}\setminus\\{s_{\perp}\\}}q(s,a)p(s^{\prime}|s,a)f(s^{\prime})$
$\displaystyle=q(s,a)p(\cdot|s,a)^{\top}f$

Eq. (30) can be proved in a similar manner. ∎

####  D.1.2 Concentration

In the following, we introduce a concentration lemma.

######  Lemma 19 (KL-divergence Based Concentration of Triggered Transition).

Defining event

$\displaystyle\mathcal{G}:=\left\\{\textup{KL}\left(\hat{p}^{\mathtt{aug},k}(\cdot|s,a)\|p^{\mathtt{aug}}(\cdot|s,a)\right)\leq\frac{\log\left(\frac{SN}{\delta^{\prime}}\right)+S\log\left(8e(n^{k}(s,a)+1)\right)}{n^{k}(s,a)},\
\forall(s,a)\in\mathcal{S}\times A^{\mathtt{univ}},\forall k\right\\},$

it holds that

$\displaystyle\Pr\left[\mathcal{G}\right]\geq 1-\delta.$

###### Proof of Lemma 19.

Using Theorem 3 and Lemma 3 in (Ménard et al., 2021), we can obtain this
lemma. ∎

####  D.1.3 KL Divergence-based Technical Tools

Below, we present several useful KL divergence-based technical tools.

######  Lemma 20 (Lemma 10 in (Ménard et al., 2021)).

Let $p_{1}$ and $p_{2}$ be two distributions on $\mathcal{S}$ such that
$\textup{KL}(p_{1},p_{2})\leq\alpha$. Let $f$ be a function defined on
$\mathcal{S}$ such that for any $s\in\mathcal{S}$, $0\leq f(s)\leq b$. Then,

$\left|p_{1}f-p_{2}f\right|\leq\sqrt{2\textup{Var}_{p_{2}}(f)\alpha}+\frac{2}{3}b\alpha$

######  Lemma 21 (Lemma 11 in (Ménard et al., 2021)).

Let $p_{1}$ and $p_{2}$ be two distributions on $\mathcal{S}$ such that
$\textup{KL}(p_{1},p_{2})\leq\alpha$. Let $f$ be a function defined on
$\mathcal{S}$ such that for any $s\in\mathcal{S}$, $0\leq f(s)\leq b$. Then,

$\displaystyle\textup{Var}_{p_{2}}(f)\leq
2\textup{Var}_{p_{1}}(f)+4b^{2}\alpha$
$\displaystyle\textup{Var}_{p_{1}}(f)\leq
2\textup{Var}_{p_{2}}(f)+4b^{2}\alpha$

######  Lemma 22 (Lemma 12 in (Ménard et al., 2021)).

Let $p_{1}$ and $p_{2}$ be two distributions on $\mathcal{S}$ such that
$\textup{KL}(p_{1},p_{2})\leq\alpha$. Let $f,g$ be two functions defined on
$\mathcal{S}$ such that for any $s\in\mathcal{S}$, $0\leq f(s),g(s)\leq b$.
Then,

$\displaystyle\textup{Var}_{p_{1}}(f)\leq$ $\displaystyle
2\textup{Var}_{p_{1}}(g)+2bp_{1}|f-g|$
$\displaystyle\textup{Var}_{p_{2}}(f)\leq$
$\displaystyle\textup{Var}_{p_{1}}(f)+3b^{2}\alpha\|p_{1}-p_{2}\|_{1}$

####  D.1.4 Estimation Error

Next, we state an important lemma on estimation error.

######  Lemma 23 (Estimation Error).

Suppose that the concentration event $\mathcal{G}$ holds. Then, for any
episode $k$, policy $\pi$ and reward function $r$,

$\displaystyle\left|\hat{V}^{k,\pi}_{1}(s;r)-V^{\pi}_{1}(s;r)\right|\leq
4e\sqrt{B^{k}_{1}(s)}+B^{k}_{1}(s).$

###### Proof of Lemma 23.