Zeyu Jia111This work was done while Zeyu interned at Amazon<EMAIL_ADDRESS>
Massachusetts Institute of Technology and Randy Jia<EMAIL_ADDRESS>
Amazon and Dhruv Madeka<EMAIL_ADDRESS>
Amazon and Dean P. Foster<EMAIL_ADDRESS>
Amazon

# Linear Reinforcement Learning with Ball Structure Action Space

###### Abstract

We study the problem of Reinforcement Learning (RL) with linear function
approximation, i.e. assuming the optimal action-value function is linear in a
known $d$-dimensional feature mapping. Unfortunately, however, based on only
this assumption, the worst case sample complexity has been shown to be
exponential, even under a generative model. Instead of making further
assumptions on the MDP or value functions, we assume that our action space is
such that there always exist playable actions to explore any direction of the
feature space. We formalize this assumption as a “ball structure” action
space, and show that being able to freely explore the feature space allows for
efficient RL. In particular, we propose a sample-efficient RL algorithm
(BallRL) that learns an $\epsilon$-optimal policy using only
$\tilde{\mathcal{O}}\left(\frac{H^{5}d^{3}}{\epsilon^{3}}\right)$ number of
trajectories.

###### keywords:

Markov Decision Process, Reinforcement Learning

##  1 Introduction

Reinforcement Learning (RL) is a well-studied framework for sequential
decision making that has been successfully applied to real-world problems in
fields such as game-play (Atari, AlphaGo, Starcraft), robotics, operations
management, and more (Mnih et al., 2013; Silver et al., 2016; Vinyals et al.,
2017; Kober et al., 2013). However, many of the existing theoretical results
can not be applied to many practical applications due to intractably-large
number of states and/or actions. A common modeling assumption to address this
issue is to assume the existence of a known feature mapping that maps state
and action to a $d$-dimensional feature vector, and that either the underlying
MDP dynamics or value functions is linear in this feature mapping. In this
work, we consider the common setting where the optimal action-value function
(or $Q^{*}$-function) is linear and can be written as the inner product of the
feature mapping of state-action pairs and some unknown parameter vector. The
primary goal is to determine whether there exists algorithms that can achieve
a near-optimal policy using an efficient number of samples. Here, efficient
sample complexity refers to a polynomial number of samples with respect to the
feature dimension $d$, the horizon $H$, and the size of the action set
$|\mathcal{A}|$.

This setting has garnered much attention recently, however, in the general
case pessimistic results have been shown in Weisz et al. (2021b, 2022); Du et
al. (2019); Wang et al. (2021), which indicate that this problem is
exponentially hard in the horizon $H$ or the size of the action set
$|\mathcal{A}|$. Furthermore, this pessimistic result is true even with access
to a generative model that allows for arbitrary state “resets.” Recently,
several works have made further assumptions on the MDP that allow for
efficient learning when the $Q^{*}$ function is linear (Jin et al., 2020;
Amortila et al., 2022). These typically include additional assumptions on the
transition or reward model, or access to additional side information such as
expert queries. However, many of these assumptions are restrictive,
unrealistic, or unfeasible for many practical use cases, since in the real
world, we typically do not we have well-behaved transition models or access to
expert oracles.

We seek a general yet practical assumption that is novel, realistic, and
amenable to efficient learning. Our work is motivated by the observation that,
in some difficult real-world RL applications such as game-play and operations
management, it may be easier to think of actions (or consecutive actions) in
feature space rather than state space. For example, in a typical dungeon-
survival game with various tasks such as fighting monsters, eating food, or
searching for treasure, the feature space could include combat statistics,
health, and special items. Instead of actions consisting of low-level controls
(e.g. movement, engage, run, etc.), we would consider higher-level “feature
space” actions (e.g. fight monster, eat food, dig for treasure). Now, we
conjecture that if a learning algorithm is always able to play actions to
property explore the feature space, then, combined with a $d$-dimensional
feature mapper that exists in the case of linear RL, it should be able to
learn a near-optimal policy efficiently. In order to mathematically
characterize this property, we introduce the concept of a “ball structure”
action space. This assumes that our action space always lies within a
$d$-dimensional ball of radius $\rho$, so that every direction of the feature
space has a corresponding action that can be taken, and therefore at any time
step, we are able to explore in any direction of the feature space. However, a
perfect ball-shaped action space may be somewhat unrealistic, therefore, we
allow some flexibility on the degree of exploration in each direction by
considering less-restrictive settings, such as when the action is instead
contained within a convex set, or when the radius of the ball is allowed to
differ from one time step to the next.

Our main result is the BallRL (pronounced _baller_) algorithm that leverages
the exploration capabilities of the ball structure assumption and achieves
sample-efficient bounds on learning. The results hold under very mild
trajectory learning/PAC learning setting, i.e. we do not assume have access to
the action space, and each sampled trajectory gives us information only about
action sets along the trajectory, together with total rewards. The algorithm
takes advantage of the ball structure action space for exploration, which can
be shown to be efficient using the closed form solution of the optimal Bellman
Equation, and enjoys a sample complexity bound of
$\tilde{\mathcal{O}}(H^{5}d^{3}/\epsilon^{2})$ for an $\epsilon$-optimal
policy. Furthermore, a similar algorithm and complexity bound hold in the case
of convex action set instead of a ball action set, under additional mild
assumptions. All together, our results show that with a ball structure action
set, we can achieve an exponential improvement in comparison to algorithms to
linear $Q^{*}$ problem without the ball structure assumption. We also
demonstrate that our algorithm is easy to implement and is computationally
efficient as well.

###  1.1 Organization of the Paper

The rest of the paper is structured as follows: in Section 2 and 3 we will
introduce the problem setting and review prior work in the literature for the
linear RL problem. In Section 4 we present our learning algorithm where we
demonstrate that efficient learning is possible assuming a ball structure
action set. In particular, we present two special generalizations of the
assumption: in Section 4.1 consider when every state in step $h$ shares the
same convex action set, and in Section 4.2 we assume the ball structure action
set is allowed to vary by state. Note that the simpler ball structure
assumption is a special case of both settings. We finally conclude in Section
5 with some discussion.

###  1.2 Notations

We will use $\langle\cdot,\cdot\rangle$ and $\|\cdot\|_{2}$ to denote the
inner product and the 2-norm in $\mathbb{R}^{d}$, respectively. Let
$B_{2}(\rho)=\left\\{x\in\mathbb{R}^{d}|\|x\|_{2}\leq\rho\right\\}$ represent
the $L_{2}$-ball of radius $\rho$ in $\mathbb{R}^{d}$. The expectation
$\mathbb{E}^{\pi}$ will denote the expectations over all trajectories obtained
according to $\pi$ and the underlying transition models and reward functions.
We also follow standard big-Oh notation, that is, we will write
$A=\mathcal{O}(B)$ if there exists some positive constant $c$ such that $A\leq
cB$, and write $A=\tilde{\mathcal{O}}(B)$ if there exists some
$c=\mathrm{polylog}(d,H,\delta,1/\epsilon)$ such that $A\leq cB$. Here, $d$ is
the dimension of the feature space, $H$ the time horizon of an episode,
$\delta$ the high probability parameter, and $\epsilon$ the near-optimality
parameter of the learned policy.

##  2 Background

###  2.1 Preliminaries

A Markov Decision Process (Sutton and Barto, 2018; Puterman, 2014) is a well-
known model of the typical reinforcement learning environment. We consider
finite-horizon MDPs which are defined by the tuple
$\mathcal{M}=(\mathcal{S},\mathcal{A},P,H,r,\mu)$, where the horizon
$H\in\mathbb{N}$ and the state space
$\mathcal{S}=\mathcal{S}_{1}\cup\cdots\cup\mathcal{S}_{H}$ is known to the
learner, but the action space $\mathcal{A}(s)$ of each state
$s\in\mathcal{S}$, the transition model
$P:\mathcal{S}\times\mathcal{A}\to\mathcal{S}$, the reward function
$r:\mathcal{S}\to\mathbb{R}$, and initial state distribution $\mu$ are not
known. To avoid confusion, without loss of generality we assume that
$\mathcal{S}_{1},\cdots,\mathcal{S}_{H}$ have no intersection between each
other.

For a given MDP, a policy $\pi:\mathcal{S}\to\mathcal{A}$ is a mapping from
state space to the action space, where $\pi(s)\in\mathcal{A}(s)$ for all
$s\in\mathcal{S}$. For a given policy $\pi$, we define its value functions
($V$) and $Q$ functions according to the following iterative equations:

$\displaystyle V_{H+1}^{\pi}(s_{h+1})$ $\displaystyle=0,\quad
Q_{H+1}(s_{H+1},a_{H+1})=0,\quad\forall s_{H+1},a_{H+1},$ $\displaystyle
Q_{h}^{\pi}(s_{h},a_{h})$
$\displaystyle=r(s_{h},a_{h})+\sum_{s_{h+1}}P(s_{h+1}|s_{h},a_{h})V_{h+1}^{\pi}(s_{h+1}),$
$\displaystyle V_{h}^{\pi}(s_{h})$
$\displaystyle=Q_{h}^{\pi}(s_{h},\pi(s_{h})).$

We further define the optimal $Q$ and $V$ function as:

$Q_{h}^{*}(s_{h},a_{h})=\max_{\pi}Q_{h}^{\pi}(s_{h},a_{h}),\quad
V_{h}^{*}(s_{h})=\max_{\pi}V_{h}^{\pi}(s_{h}).$

For the optimal $Q^{*}$ function we have the optimal Bellman Equations, so
that for all $1\leq h\leq
H,s_{h}\in\mathcal{S}_{h},a_{h}\in\mathcal{A}(s_{h})$,

$Q_{h}^{*}(s_{h},a_{h})=r(s_{h},a_{h})+\sum_{s_{h+1}}P(s_{h+1}|s_{h},a_{h})\max_{a_{h+1}}Q_{h+1}^{*}(s_{h+1},a_{h+1}).$
(1)

A typical reinforcement learning problem objective is to determine an
algorithm that recovers a policy $\pi$ that performs well relative to the
unknown optimal policy $\pi^{*}$; performance is generally defined by
comparing the learned policy’s and optimal policy’s value functions. In the
following section we detail our specific problem setting and objective.

###  2.2 Our problem setting

Due to the intractability of dealing with extremely high-dimensional state
spaces, we make the standard assumption of a linear $Q^{*}$ function for our
problem; that is, the optimal $Q^{*}$ function is linear in a $d$-dimensional
feature mapping of the state and action:

######  Assumption 1 (Non-Stationary Linear $Q^{*}$ Assumption)

For each state-action pair $(s,a)$, there exists a feature vector
$\varphi(s,a)\in\mathbb{R}^{d}$. There are also $H$ unknown parameters
$\theta_{1}^{*},\cdots,\theta_{H}^{*}$, such that the $Q^{*}$-function of
state-action pairs has the following parametrization

$Q_{h}^{*}(s_{h},a_{h})=\langle\varphi(s_{h},a_{h}),\theta_{h}^{*}\rangle,\quad\forall
1\leq h\leq H,s_{h}\in\mathcal{S}_{h},a_{h}\in\mathcal{A}(s_{h}).$

While Assumption 1 appears to be a very strong statement on the optimal $Q$
function, it is known that by itself, the assumption is not enough to
guarantee efficient learning. Therefore, we present our ball structure
assumption that we will show will allow for sample-efficient RL under the
linear $Q^{*}$ assumption.

######  Assumption 2 (Ball Structure Action Set)

Define the $L_{2}$ ball with radius $\rho>0$ as

$B_{2}(\rho)\triangleq\left\\{x\in\mathbb{R}^{d}\big{|}\|x\|_{2}\leq\rho\right\\}.$

For each state $s$, there a feature vector $\varphi(s)\in\mathbb{R}^{d}$ and a
positive number $\rho(s)$ such that

$\left\\{\varphi(s,a)|a\in\mathcal{A}_{s}\right\\}=\varphi(s)+B_{2}(\rho(s)).$

######  Remark 2.1.

Without loss of generality, we can assume that

$\mathcal{A}(s)=B_{2}(\rho_{h}(s))\triangleq\left\\{a\in\mathbb{R}^{d}\big{|}\|a\|_{2}\leq\rho_{h}(s)\right\\},$

and also

$\varphi(s,a)=\varphi(s)+a.$

This is because if there exists two actions $a_{1},a_{2}$ such that
$\varphi(s,a_{1})=\varphi(s,a_{2})$, then Assumption 1 implies that
$Q^{*}(s,a_{1})=Q^{*}(s,a_{2})$. Hence if we remove $a_{2}$ from the action
set, the value of $V^{*}(s_{1})$ will remain the same. Therefore, if we remove
these redundant actions and find a near-optimal policy of the MDP, this policy
must also be a near-optimal policy of the original MDP.

By above, after removing redundant actions, we can assume that
$a\to\varphi(s,a)$ is an injection, meaning $a\to\varphi(s,a)$ is a one-to-one
mapping from $\mathcal{A}(s)$ to $B_{2}(\rho(s))+\varphi(s)$. Hence we can
replace every action $a$ with $\varphi(s,a)-\varphi(s)$, and then we will have
property $\varphi(s,a)=\varphi(s)+a$. Thus, without loss of generality, in the
rest of the paper, we will assume $\varphi(s,a)=\varphi(s)+a$ always holds.

Because the transition model and reward function are unknown at the beginning,
the learner will only be able to access samples, or realizations, of them by
directly interacting with the environment. That is, the learner must execute a
policy to actually observe the outcome of those actions. We will consider the
following _trajectory learning_ setting:

######  Definition 2.2 (Trajectory Learning).

At every iteration, the learner first picks a policy (a function mapping every
state $s\in\mathcal{S}$ to some action in $\mathcal{A}(s)$), and then a
trajectory $(s_{1},s_{2},\cdots,s_{H})$ is sampled according to the true
underlying MDP. Only the following two pieces of information are revealed to
the learner:

  1. 1.

$\mathcal{A}(s_{h})$: The action sets of each state in the trajectory;

  2. 2.

$\sum_{h=1}^{H}R(s_{h},a_{h})$: The sum of total reward of the trajectory,
where $R(s_{h},a_{h})$ denotes the instant reward obtained by taking action
$a_{h}$ at state $s_{h}$, which satisfies
$\mathbb{E}[R(s_{h},a_{h})]=r(s_{h},a_{h})$.

######  Remark 2.3.

Note that our trajectory learning setting is weaker than the standard PAC
learning setting in the literature, where it is assumed that all the
information of the trajectories is revealed, including the states
$s_{1},\cdots,s_{H}$ and the instantaneous rewards $R(s_{h},a_{h})$. Our
algorithm also does not require the use of a generative model that is standard
in some linear $Q^{*}$ works. Therefore, our algorithm applies to both the
common PAC learning setting and generative model setting. For more information
about this, please refer to Section 3.

Finally, in order to measure the performance of our learner’s policy, we
define the closeness to optimality of a policy via the standard notion of an
$\epsilon$-optimal policy:

######  Definition 2.4 ($\epsilon$-optimal policy).

If a policy $\pi$ satisfies

$|V^{\pi}(s_{0})-V^{*}(s_{0})|\leq\epsilon,$

then we call the policy $\pi$ an $\epsilon$-optimal policy. Here, $V^{\pi}$ is
the value function with respect to following the policy $\pi$, and $V^{*}$ is
the value function of the true optimal policy.

Our objective in this work is to develop an algorithm which can find an
$\epsilon$-optimal policy with high probability, by using a polynomial number
(in $d,H$ and $1/\epsilon$) of trajectory learning iterations.

##  3 Related Literature

The linear $Q^{*}$ problem is one of the simplest and most intuitive ways to
describe reinforcement learning with parametrization. Many works have studied
this setting of RL with the goal to develop a sample-efficient algorithm to
learn a near-optimal policy. However, in the most general case, recent work
has yielded only pessimistic results related to this problem. In Weisz et al.
(2021b, 2022); Du et al. (2019); Wang et al. (2021); Foster et al. (2021), the
linear $Q^{*}$ problem has been shown to be exponentially hard in $d$ or $H$
or $|\mathcal{A}|$, even when the number of actions are small. Their main idea
revolves around showing a lower exponential bound by constructing a needle in
haystack-type MDP, i.e., among exponentially many actions there is only one
action that induces rewards, hence in order to find the optimal action the
learner must run policies an exponential number of times. Additionally, they
also adopt the Johnson-Lindenstrauss lemma to show that they can choose these
actions such that every two actions are sufficiently far away from each other,
so that querying non-optimal actions gives limited information of the optimal
action.

Apart from pessimistic results, there are many works which demonstrate that
the linear $Q^{*}$ problem is polynomially solvable with added additional
assumptions. Assumptions are quite varied and numerous, and we attempt to give
an overview of the different types that have allowed for efficient learning.
If for all policies $\pi$, the $Q$-function $Q^{\pi}$ can be linearly
parameterized, then the problem is polynomially solvable by using approximate
policy iteration (Lattimore et al., 2020). If both the transition model and
reward function are deterministic, then the problem is polynomially solvable
by eliminating functions that does not satisfy the linear $Q^{*}$ function
assumptions (Wen and Van Roy, 2013). If a ‘core set’ (that is, features of
every state action pairs can be written as the convex combinations of features
in the core set) exists for the MDP, then the problem is polynomially solvable
(Zanette et al., 2019; Shariff and Szepesvári, 2020). In comparison to our
assumption, our algorithm has access to an orthogonal basis at first, which is
similar to the idea of core set. However, the core set cannot capture our
setting, since the ball cannot be written as convex combination of basis
vectors - simply adopting their algorithm would induce exponential sample
complexity. Under the assumption that the action set is finite, the TensorPlan
Algorithm in Weisz et al. (2021a) can obtain an $\epsilon$-optimal policy
using
$\mathrm{poly}\left(\left(\frac{dH}{\epsilon}\right)^{|\mathcal{A}|}\right)$
number of samples. Alternatively, if we assume access to an expert oracle
which gives the value of $Q^{*}(s,a)$ when queried at state $(s,a)$, the
DELPHI algorithm can solve these linear $Q^{*}$ problem in polynomial time
using no more than $\mathcal{O}(d)$ calls of expert queries (Amortila et al.,
2022).

Beyond the linear $Q^{*}$ problem, there are also several works which achieve
polynomial sample complexity under general assumptions of the MDP’s underlying
properties. If the transition model can be linearly parametrized, then the MDP
problem becomes polynomially solvable as shown in Jin et al. (2020); Yang and
Wang (2019, 2020); Jia et al. (2020). However, a linear transition model is a
fairly strong assumption and generally not a very practical assumption, as
most systems do not behave as such. There are also works focused on
generalized function approximations, e.g. Eluder Dimensions (Ayoub et al.,
2020; Wang et al., 2020), Bellman Rank (Jiang et al., 2017), Bellman Eluder
Dimension (Jin et al., 2021), Bilinear Class (Du et al., 2021), Bellman
Closeness (Jin et al., 2021; Zanette et al., 2020). However, again these
assumptions on the models are either hard to verify in practice or generally
do not occur in real world systems, which makes the use of these algorithms
difficult to justify in practice.

##  4 The BallRL Algorithm

We now present the main result of our paper, that is, an algorithm that
achieves polynomial sample complexity in the linear $Q^{*}$ setting under the
assumption of a ball structure action space. Before proceeding with the
details, we highlight two versions of our algorithm, Convex-BallRL and DiffR-
BallRL, both of which are essentially extensions of the standard ball
structure assumption (Assumption 2). In the first case, we consider convex
action sets where the action sets are identical across state. While every
state necessarily has the same set of actions to take, the magnitude to which
one can explore different directions is permitted to vary, so long the overall
action set is convex. This can be seen as a slightly more realistic version of
the standard ball assumption, as in practice it may be difficult to guarantee
the magnitude of every feature direction to be the same. In the second case,
we consider the standard ball structure action set but allow the action set to
vary depending on the current state. The motivation behind these two slightly
different settings is to represent a more realistic generalization of the
original ball structure presented earlier, as in practical settings action
spaces may not always be uniformly a perfect ball.

###  4.1 Identical Convex Action Sets within One Step

In this section, we make the assumption that the action set
$\mathcal{A}(s_{h})$ is identical for every $s_{h}\in\mathcal{S}_{h}$, and
moreover, we assume the action sets are regular convex sets, which is a
generalization of the ball structure presented in Assumption 2. Intuitively,
the action set is contained between a smaller radius and a larger radius ball.

######  Definition 4.1 (Regular Convex Set).

We call a set $\mathcal{M}\subset\mathbb{R}^{d}$ a regular convex set with
parameter $B\geq 1$ if there exists $\eta\geq\rho>0$ such that
$\frac{\eta}{\rho}=B$ and

$B_{2}(\rho)\subset\mathcal{M}\subset B_{2}(\eta).$

######  Remark 4.2.

Regular convex sets include many different types of structures such as balls,
cubes, ellipsoids, etc. Some specific examples include:

  1. 1.

All balls are regular convex sets with parameter $1$;

  2. 2.

Cubes in $d$ dimension are regular convex sets with parameter $\sqrt{d}$;

  3. 3.

Ellipsoids are regular convex sets with parameter $\frac{a_{\max}}{a_{\min}}$,
where $a_{\max},a_{\min}$ are the longest and shortest axes.

Let us formally characterize our assumption for the setting with convex action
sets.

######  Assumption 3 (Identical Convex Action Sets within One Step)

For every $1\leq h\leq H$, there exists a regular convex set $\mathcal{A}_{h}$
with parameter $B$, such that for all $s_{h}\in\mathcal{S}_{h}$,
$\mathcal{A}(s_{h})=\mathcal{A}_{h}$. Specifically, there exists
$\rho_{1},\cdots,\rho_{H},\eta_{1},\cdots,\eta_{H}$, such that for every
$1\leq h\leq H$ we have

$\frac{\eta_{h}}{\rho_{h}}=B,\qquad
B_{2}(\rho_{h})\subset\mathcal{A}_{h}\subset B_{2}(\eta_{h}).$

Without loss of generality, we also assume that the features still satisfy
$\varphi(s,a)=\varphi(s)+a$.

We develop an algorithm, Convex-BallRL, that works in the trajectory learning
setting (Definition 2.2) under Assumption 1 and 3, and is guaranteed to find
an $\epsilon$-optimal policy using a polynomial number of trajectories.

####  4.1.1 Intuition and key ideas

Before presenting the algorithm itself, we provide some intuition on the key
ideas behind our algorithm. With loss of generality, we assume that we know
the value of $\rho_{1},\cdots,\rho_{H}$ at the beginning. Otherwise, we can
run one trajectory according to any policy, then all the action sets
$\mathcal{A}_{1},\cdots,\mathcal{A}_{H}$ will be revealed to us, from which we
can determine the values of $\rho_{1},\cdots,\rho_{H}$.

We start by observing the following equation due to telescoping of Bellman
Equation (1):

$\mathbb{E}\left[\langle\varphi(s_{1}),\theta_{1}^{*}\rangle\right]+\mathbb{E}\left[\sum_{h=1}^{H}\langle
a_{h},\theta_{h}^{*}\rangle\right]=\sum_{h=1}^{H}\mathbb{E}[R(s_{h},a_{h})]+\sum_{h=1}^{H}\rho_{h+1}\max_{a_{h+1}\in\mathcal{A}_{h+1}}\langle
a_{h+1},\theta_{h+1}^{*}\rangle.$ (2)

Our next observation is that the first term of LHS and the second term of RHS
in (2) are identical for every policy. Hence, if we compare (2) between two
different policies, we can obtain information of $\theta_{h}^{*}$ (according
to $\langle a_{h},\theta_{h}^{*}\rangle$) based on the first term in RHS,
which can be estimated through sampled trajectories. Formally, we choose
$\pi_{0}$ to be the all-zero policy:

$\pi_{0}(s_{h})=\mathbf{0}\in\mathbb{R}^{d},\quad\forall 1\leq h\leq H,$ (3)

and $\pi_{h,i}$ ($1\leq h\leq H,1\leq i\leq d$) to be the following policy:
for $1\leq h^{\prime}\leq H$ and $s_{h^{\prime}}\in\mathcal{S}_{h^{\prime}}$,

$\pi_{h,i}(s_{h^{\prime}})=\begin{cases}\mathbf{0}&\quad\text{if
}h^{\prime}\neq h,\\\ \rho_{h}\mathbf{e}_{i}&\quad\text{if
}h^{\prime}=h\end{cases},$ (4)

where $\mathbf{e}_{i}$ is the $i$-th basis vector in $\mathbb{R}^{d}$.
Comparing (2) according to policy $\pi_{0}$ and also policy $\pi_{h,i}$, we
obtain that

$\rho_{h}\langle\mathbf{e}_{i},\theta_{h}^{*}\rangle=\mathbf{E}^{\pi_{h,i}}\left[\sum_{h=1}^{H}R(s_{h},a_{h})\right]-\mathbf{E}^{\pi_{0}}\left[\sum_{h=1}^{H}R(s_{h},a_{h})\right].$

The right hand side can be estimated according to trajectories from policy
$\pi_{0}$ and $\pi_{h,i}$, which leads to the estimate of $i$-th component of
$\theta_{h}^{*}$.

Finally after getting accurate enough estimations
$\hat{\theta}_{h}\in\mathbb{R}^{d}$ on $\theta_{h}^{*}$, we adopt the greedy
policy, i.e.

$\pi(s_{h})=\mathop{\arg\max}_{a_{h}\in\mathcal{A}_{h}}\langle
a_{h},\hat{\theta}_{h}\rangle,$ (5)

and then show that this policy is a nearly optimal policy.

####  4.1.2 Algorithm and Sample Complexity

The pseudocode for BallRL with convex action sets is given in Algorithm 1. The
main result of this section is the following theorem about its sample
complexity, in particular, that it has polynomial sample complexity. The
complete proof details are provided in Appendix A.

######  Theorem 4.3.

For any $\delta>0$, if we choose

$M=\frac{8H^{2}B^{2}d\log(2dH/\delta)}{\epsilon^{2}},$

then with probability at least $1-\delta$, the output policy from the above
algorithm is an $\epsilon$-optimal policy. The total number of trajectories
used in this algorithm is

$\frac{16H^{3}B^{2}d^{2}\log(2dH/\delta)}{\epsilon^{2}}.$

######  Remark 4.4.

If we assume all action sets have ball structure, then all action sets are
regular convex sets with parameter $1$. Hence the above algorithm is
guaranteed to find an $\epsilon$-optimal policy using
$\tilde{\mathcal{O}}\left(\frac{H^{3}d^{2}}{\epsilon^{2}}\right)$ number of
trajectories.

Algorithm 1 Convex-BallRL

Input:  $d,H,M,\rho_{h}$;

for $h=1:H$ do

for $i=1:d$ do

Choose policy $\pi_{0}$ such that $\pi_{0}(s_{h^{\prime}})=\mathbf{0}$ for any
$s_{h^{\prime}},h^{\prime}\in[H]$.

Choose policy $\pi_{h,i}$ such that $\pi_{h,i}(s_{h^{\prime}})=\mathbf{0}$ if
$h^{\prime}\neq h$ and $\pi_{h,i}(s_{h})=\rho_{h}\mathbf{e}_{i}$ for all
$s_{h}$.

Get $M$ trajectories from policy $\pi_{0}$ and $\pi_{h,i}$ respectively, and
calculate the average of total rewards: $R_{0}$ and $R_{h,i}$.

Let $\hat{\theta}_{h}$ to be the vector whose $i$-th component to be
$\frac{R_{h,i}-R_{0}}{\rho_{h}}$.

Let $a_{h}=\arg\max_{a\in\mathcal{A}_{h}}\langle
a_{h},\hat{\theta}_{h}\rangle.$

Output:  Policy $\pi$: $\pi(s_{h})=a_{h}$ for any $s_{h},h\in[H]$.

###  4.2 Different Radius

In this section, we abandon the assumption that all states $s_{h}$ in step $h$
share identical action sets, and allow for the action set to vary depending on
the state. However, we again assume that the action set corresponding to each
state is a ball as in Assumption 2. We further assume that the norm of
$\theta_{h}$ are all the same for $1\leq h\leq H$, and also that the norm of
features, rewards and radius are bounded:

######  Assumption 4 (Boundedness)

For each state $s\in\mathcal{S}$, action $a\in\mathcal{A}(s)$, we have

$\|\varphi(s,a)\|_{2}\leq 1;$

For some $\Theta\in[0,1]$, we have

$\|\theta_{1}\|_{2}=\cdots=\|\theta_{H}\|_{2}=\Theta;$

For every trajectories $(s_{1},a_{1},\cdots,s_{H},a_{H})$, we have

$0\leq\sum_{h=1}^{H}R(s_{h},a_{h})\leq 1,\quad
0\leq\sum_{h=1}^{H}\rho(s_{h})\leq 1.$

We again aim to develop an algorithm that works under Definition 2.2
(trajectory learning), but under Assumption 1 (Linear $Q^{*}$ assumption), 2
(Ball Structure Assumption) and 4 (Boundedness Assumption).

####  4.2.1 Intuition and key ideas

We begin by presenting the following key ideas of our algorithm:

##### To Exploit the Ball Structure Action space

Similar to (2) in Convex-BallRL, our algorithm is again based on the
telescoping of Bellman Equation (1), which exploits the ball structure of the
action space:

$\langle\varphi(s_{1}),\theta_{1}^{*}\rangle+\mathbb{E}^{\pi}\left[\sum_{h=1}^{H}\langle
a_{h},\theta_{h}^{*}\rangle\right]=\mathbb{E}^{\pi}\left[\sum_{h=1}^{H}R(s_{h},a_{h})\right]+\Theta\cdot\mathbb{E}^{\pi}\left[\sum_{h=1}^{H}\rho(s_{h+1})\right].$
(6)

##### Estimation of Norm by Grid Search

According to (6), we can estimate $\theta_{1}^{*},\cdots,\theta_{H}^{*}$ in
the LHS based on the RHS. However, $\Theta$, which is the norm of the unknown
parameters $\theta_{1}^{*},\cdots,\theta_{H}^{*}$, is difficult to estimate.
Hence in our algorithm, we adopt a grid search method for the value of
$\Theta$: choosing $\xi=l\varepsilon$ for $1\leq l\leq\frac{1}{\varepsilon}$,
so that at least one such $\xi$ is $\varepsilon$-close to the true $\Theta$.
Therefore, if we develop our policy based on these $\xi$, then at least one
policy will necessarily be an $\epsilon$-optimal policy.

##### Hierarchical Exploration

For the exploration in our algorithm, we will choose actions to be
$\rho(s_{h})\mathbf{e}_{i}$ for $1\leq i\leq d$ in order to give information
about the $i$-th component of $\theta_{h}^{*}$. However, one problem is that
this estimation has accuracy at most $1/\rho(s_{h})$, which will explode as
$\rho(s_{h})$ goes to zero. To deal with this problem, we consider a
hierarchical exploration method:

Suppose the policy we currently use for exploration is $\pi_{e}$, and the
greedy policy we calculated is $\pi$. We can show that the exploration will
guarantee $1/({\mathbb{E}^{\pi_{e}}[\rho(s_{h})]}\sqrt{M})$ accuracy on
$\theta_{h}^{*}$ (up to logarithmic factors), and hence the error of $\pi$ is
$\mathbb{E}^{\pi}[\rho(s_{h})]/({\mathbb{E}^{\pi_{e}}[\rho(s_{h})]}\sqrt{M})$.
Therefore, if for every $1\leq h\leq H$ we all have
$\mathbb{E}^{\pi}[\rho(s_{h})]\leq 2{\mathbb{E}^{\pi_{e}}[\rho(s_{h})]}$, then
the error of the greedy policy is of order $2/\sqrt{M}$, which can be bounded
by choosing some proper $M$. Otherwise, we use the greedy policy $\pi$ to
construct another exploration policy as follows:

$\displaystyle\pi_{h,0}(s_{h^{\prime}})$
$\displaystyle=\begin{cases}\pi(s_{h^{\prime}})&\quad\text{if }1\leq
h^{\prime}<h;\\\ 0&\quad\text{if }h^{\prime}\geq h;\end{cases}$ (7)
$\displaystyle\pi_{h,i}(s_{h^{\prime}})$
$\displaystyle=\begin{cases}\pi(s_{h^{\prime}})&\quad\text{if }1\leq
h^{\prime}<h;\\\ \rho(s_{h})\mathbf{e}_{i}&\quad\text{if }h^{\prime}=h;\\\
0&\quad\text{if }h^{\prime}\geq h.\end{cases}$

Then these new policies $\pi_{h,i}$ will guarantee that
$\mathbb{E}^{\pi_{h,i}}[\rho(s_{h})]\geq 2\mathbb{E}^{\pi_{e}}[\rho(s_{h})]$,
i.e. the value of $\mathbb{E}^{\pi_{e}}[\rho(s_{h})]$ becomes at least twice
of its previous value. Therefore, we can show that this process will end in at
most $H\log(1/\varepsilon)$ number of times, provided that the initial value
of $\mathbb{E}^{\pi_{e}}[\rho(s_{h})]$ is at least $\varepsilon$.

##### Ignore Small Radius

We will show that if within a policy $\pi$, the expected radius
$\mathbb{E}^{\pi}[\rho(s_{h})]$ at step $h$ is smaller than $\varepsilon$,
then the effect of different actions within this step can be ignored, and we
do not need to carry out the above exploration in this step.

####  4.2.2 Algorithm and Sample Complexity

Combine these ideas together, we construct the following Algorithm 2.

Algorithm 2 DiffR-BallRL

Input:  $d,H,M_{1},M_{2},\varepsilon,\eta,L=1/\eta$;

Let $\rho_{h}=0,\rho_{h}^{l}=1$ for all $1\leq h\leq H,1\leq l\leq L$.

Let policy $\pi_{l}^{\prime}$ to be the policy such that $\pi(s_{h})=0$ for
all $s_{h}\in\mathcal{S}_{h}$ and $1\leq h\leq H$ and $1\leq l\leq L$.

while $\exists 1\leq h\leq H$ and $1\leq l\leq L$ such that $\rho_{h}^{l}\geq
2\rho_{h}$ and $\rho_{h}^{l}\geq\varepsilon$ do

Fix $h,l$ to be the one that $\rho_{h}^{l}\geq\rho_{h}$, and construct Policy
$\pi_{h,0}$ and $\pi_{h,i}$ ($1\leq i\leq d$) based on policy
$\pi_{l}^{\prime}$ according to (7) (use $\pi=\pi_{l}^{\prime}$ in (7)).

Collect $M_{1}$ trajectories according to policy $\pi_{h,i}$ for $0\leq i\leq
d$ each, and calculate the average of total reward
$\sum_{h^{\prime}=1}^{H}R(s_{h},a_{h})$, and average of
$\sum_{h=2}^{H}\rho(s_{h})$ as $R_{h,i}$ and $s_{h,i}$, respectively.

$\rho_{h}\leftarrow\rho_{h}^{l}.$

for $l=1:L$ do

Let $\xi=l\eta$.

Calculate
$\hat{\theta}_{h,i}^{l}=\frac{(s_{h,i}-s_{h,0})\xi+R_{h,i}-R_{h,0}}{\rho_{h}}$
for $1\leq i\leq d$.

Let $\hat{\theta}_{h}^{l}=\sum_{i=1}^{d}\hat{\theta}_{h,i}^{l}\mathbf{e}_{i}$.

Construct policy $\pi_{l}^{\prime}$:
$\pi_{l}^{\prime}(s_{h^{\prime}})=\mathop{\arg\max}_{a_{h^{\prime}}\in
B_{2}(\rho(s_{h^{\prime}}))}\left\langle
a_{h^{\prime}},\hat{\theta}_{h^{\prime}}^{l}\right\rangle,\quad\forall
s_{h^{\prime}}\in\mathcal{S}_{h^{\prime}},1\leq h^{\prime}\leq H.$

For $1\leq l\leq L$, run policy $\pi_{l}^{\prime}$ each for $M_{2}$ times, and
calculate the average total reward $R_{1},\cdots,R_{L}$, and also calculate
the average of $\rho(s_{h^{\prime}})$ as
$\rho_{h^{\prime}}^{1},\cdots,\rho_{h^{\prime}}^{L}$ for $1\leq h^{\prime}\leq
H$.

Let $l=\mathop{\arg\max}R_{l}$ and $\pi=\pi^{\prime}_{l}$.

Output: Policy $\pi$.

Finally, we arrive at our main result - that DiffR-BallRL is sample efficient.
The proof details are provided in Appendix B.

######  Theorem 4.5.

For any $0<\delta<1$, with the choice

$\displaystyle\varepsilon=\frac{\epsilon}{8H},\quad\delta^{\prime}=\frac{\delta}{(d+3HL)(1+H\log_{2}(1/\varepsilon))},\quad\eta=\frac{\epsilon}{8Hd},$
$\displaystyle
M_{2}=2\log(1/\delta^{\prime})\cdot\frac{16(2+4H+2Hd)^{2}}{\epsilon^{2}},\quad
M_{1}=2\log(1/\delta^{\prime})\cdot\frac{256H^{2}d^{2}}{\epsilon^{2}},\quad
L=\frac{1}{\eta}$

Algorithm 2 will output an $\epsilon$-optimal policy with probability at least
$1-\delta$. This algorithm will use at most

$\tilde{\mathcal{O}}\left(\frac{H^{5}d^{3}}{\epsilon^{3}}\right)$

number of trajectories.

##### Proof Sketch of Theorem 4.5.

Our first step of the proof is to use Bellman Equation to prove (6):

$\langle\varphi(s_{1}),\theta_{1}^{*}\rangle+\mathbb{E}^{\pi}\left[\sum_{h=1}^{H}\langle
a_{h},\theta_{h}^{*}\rangle\right]=\mathbb{E}^{\pi}\left[\sum_{h=1}^{H}R(s_{h},a_{h})\right]+\Theta\cdot\mathbb{E}^{\pi}\left[\sum_{h=1}^{H}\rho(s_{h+1})\right],$

which can be obtained through telescoping the following closed form of Bellman
Equation at step $h$:

$\mathbb{E}^{\pi}\left[\langle\varphi(s_{h}),\theta_{h}^{*}\rangle+\langle
a_{h},\theta_{h}^{*}\rangle\right]=\mathbb{E}^{\pi}\left[R(s_{h},a_{h})+\rho(s_{h+1})\cdot\|\theta_{h+1}\|_{2}+\langle\varphi(s_{h+1}),\theta_{h+1}^{*}\rangle\right].$

Our second step is a result bounding the value function error of the greedy
policies:

$\mathbb{E}[V_{1}^{*}(s_{1})]-\mathbb{E}[V_{1}^{\pi}(s_{1})]\leq
2\sum_{h=1}^{H}\mathbb{E}^{\pi}[\rho(s_{h})]\cdot\left\|\hat{\theta}_{h}-\theta_{h}^{*}\right\|_{2}.$

Therefore, if $\mathbb{E}^{\pi}[\rho(s_{h})]$ is small for some $h$ (say less
than $\epsilon$), then we can ignore this term, since it will never make big
difference on the error. In the following, we assume that
$\mathbb{E}^{\pi}[\rho(s_{h})]\geq\epsilon$.

Next, we observe that there exists some $\Theta^{\prime}=l_{0}\eta$ such that
$|\Theta^{\prime}-\Theta|\leq\eta$. And for the iteration $l_{0}$, according
to Hoeffding inequality we can get

$\rho_{h}\left\|\theta_{h}-\hat{\theta}_{h}^{l_{0}}\right\|_{2}\leq\eta
d+2d\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{1}}}+d\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}}$

with high probability, where $\rho_{h}$ is the expectation of $\rho(s_{h})$
according to the exploration policy.

Finally, if $\rho_{h}^{l_{0}}$ of the greedy policy satisfies that
$\rho_{h}^{l_{0}}\leq\rho_{h}$, then the above inequality can guarantee that
this greedy policy is near optimal. Otherwise, the value of $\rho_{h}$ will
become twice as before according to our algorithm, and this process will
terminate in $\log(1/\epsilon)$ number of iterations, since according to our
assumption the initial value of $\rho_{h}$ is at least $\epsilon$, and
$\rho_{h}$ cannot be large than 1.

Combining these steps together, we can show that the algorithm will end in
certain number of iterations, and when the algorithm ends, it will output a
near optimal policy with high probability.

##  5 Conclusion

We presented the BallRL reinforcement learning algorithm that provides sample-
efficient learning guarantees when the optimal action-value function is linear
and actions exhibit a ball structure. We further generalized the ball
structure to both convex actions sets and changing ball radius between states.
Our techniques demonstrate that there is hope for efficient learning in linear
RL when actions can sufficiently explore the feature space. The ball structure
assumption itself is a sufficient, but not fully necessary condition to ensure
full exploration of the feature space. We believe that the idea of the action
set allowing for sufficient exploration can be achieved (perhaps
approximately) in many practical settings.

An interesting research direction is to dive deeper into assuming the actions
lie in convex sets instead of a pure ball structure. While the problem can be
solved when the action set is consistent between all actions, it remains to be
shown if convex sets can vary between states. Additionally, with different
radii, our algorithm is polynomially efficient when unknown parameters across
the horizon share the same norm. It would be valuable to see whether this
assumption can be removed and parameters allowed to have different norms.

We thank Philip Amortila for helpful discussions.

## References

  * Amortila et al. (2022) Philip Amortila, Nan Jiang, Dhruv Madeka, and Dean P Foster.  A few expert queries suffices for sample-efficient rl with resets and linear value approximation.  _arXiv preprint arXiv:2207.08342_ , 2022.
  * Ayoub et al. (2020) Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang.  Model-based reinforcement learning with value-targeted regression.  In _International Conference on Machine Learning_ , pages 463–474. PMLR, 2020.
  * Du et al. (2021) Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang.  Bilinear classes: A structural framework for provable generalization in rl.  In _International Conference on Machine Learning_ , pages 2826–2836. PMLR, 2021.
  * Du et al. (2019) Simon S Du, Sham M Kakade, Ruosong Wang, and Lin F Yang.  Is a good representation sufficient for sample efficient reinforcement learning?  _arXiv preprint arXiv:1910.03016_ , 2019.
  * Foster et al. (2021) Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin.  The statistical complexity of interactive decision making.  _arXiv preprint arXiv:2112.13487_ , 2021.
  * Jia et al. (2020) Zeyu Jia, Lin Yang, Csaba Szepesvari, and Mengdi Wang.  Model-based reinforcement learning with value-targeted regression.  In _Learning for Dynamics and Control_ , pages 666–686. PMLR, 2020\.
  * Jiang et al. (2017) Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E Schapire.  Contextual decision processes with low bellman rank are pac-learnable.  In _International Conference on Machine Learning_ , pages 1704–1713. PMLR, 2017.
  * Jin et al. (2020) Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In _Conference on Learning Theory_ , pages 2137–2143. PMLR, 2020\.
  * Jin et al. (2021) Chi Jin, Qinghua Liu, and Sobhan Miryoosefi.  Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms.  _Advances in neural information processing systems_ , 34:13406–13418, 2021.
  * Kober et al. (2013) Jens Kober, J Andrew Bagnell, and Jan Peters.  Reinforcement learning in robotics: A survey.  _The International Journal of Robotics Research_ , 32(11):1238–1274, 2013.
  * Lattimore et al. (2020) Tor Lattimore, Csaba Szepesvari, and Gellert Weisz.  Learning with good feature representations in bandits and in rl with a generative model.  In _International Conference on Machine Learning_ , pages 5662–5670. PMLR, 2020.
  * Mnih et al. (2013) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing atari with deep reinforcement learning.  _arXiv preprint arXiv:1312.5602_ , 2013.
  * Puterman (2014) Martin L Puterman.  _Markov decision processes: discrete stochastic dynamic programming_.  John Wiley & Sons, 2014.
  * Shariff and Szepesvári (2020) Roshan Shariff and Csaba Szepesvári.  Efficient planning in large mdps with weak linear function approximation.  _Advances in Neural Information Processing Systems_ , 33:19163–19174, 2020.
  * Silver et al. (2016) David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  _Nature_ , 529(7587):484–489, 2016.
  * Sutton and Barto (2018) Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Vinyals et al. (2017) Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, et al.  Starcraft ii: A new challenge for reinforcement learning.  _arXiv preprint arXiv:1708.04782_ , 2017.
  * Wang et al. (2020) Ruosong Wang, Russ R Salakhutdinov, and Lin Yang.  Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension.  _Advances in Neural Information Processing Systems_ , 33:6123–6135, 2020.
  * Wang et al. (2021) Yuanhao Wang, Ruosong Wang, and Sham Kakade.  An exponential lower bound for linearly realizable mdp with constant suboptimality gap.  _Advances in Neural Information Processing Systems_ , 34:9521–9533, 2021.
  * Weisz et al. (2021a) Gellért Weisz, Philip Amortila, Barnabás Janzer, Yasin Abbasi-Yadkori, Nan Jiang, and Csaba Szepesvári.  On query-efficient planning in mdps under linear realizability of the optimal state-value function.  In _Conference on Learning Theory_ , pages 4355–4385. PMLR, 2021a.
  * Weisz et al. (2021b) Gellért Weisz, Philip Amortila, and Csaba Szepesvári.  Exponential lower bounds for planning in mdps with linearly-realizable optimal action-value functions.  In _Algorithmic Learning Theory_ , pages 1237–1264. PMLR, 2021b.
  * Weisz et al. (2022) Gellért Weisz, Csaba Szepesvári, and András György.  Tensorplan and the few actions lower bound for planning in mdps under linear realizability of optimal value functions.  In _International Conference on Algorithmic Learning Theory_ , pages 1097–1137. PMLR, 2022.
  * Wen and Van Roy (2013) Zheng Wen and Benjamin Van Roy.  Efficient exploration and value function generalization in deterministic systems.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Yang and Wang (2019) Lin Yang and Mengdi Wang.  Sample-optimal parametric q-learning using linearly additive features.  In _International Conference on Machine Learning_ , pages 6995–7004. PMLR, 2019.
  * Yang and Wang (2020) Lin Yang and Mengdi Wang.  Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound.  In _International Conference on Machine Learning_ , pages 10746–10756. PMLR, 2020.
  * Zanette et al. (2019) Andrea Zanette, Alessandro Lazaric, Mykel J Kochenderfer, and Emma Brunskill.  Limiting extrapolation in linear approximate value iteration.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Zanette et al. (2020) Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill.  Learning near optimal policies with low inherent bellman error.  In _International Conference on Machine Learning_ , pages 10978–10989. PMLR, 2020.

##  Appendix A Proof of Theorem 4.3

######  Proof A.1 (Proof of Theorem 4.3).

First of all, according to Bellman Equation (1), we have

$\displaystyle\quad\langle\varphi(s_{h}),\theta_{h}^{*}\rangle+\langle
a_{h},\theta_{h}^{*}\rangle=Q_{h}^{*}(s_{h},a_{h})$
$\displaystyle=r(s_{h},a_{h})+\sum_{s_{h+1}}P(s_{h+1}|s_{h},a_{h})V_{h+1}^{*}(s_{h+1})$
$\displaystyle=r(s_{h},a_{h})+\sum_{s_{h+1}}P(s_{h+1}|s_{h},a_{h})\max_{a_{h+1}\in\mathcal{A}_{h+1}}\langle\varphi(s_{h+1})+a_{h+1},\theta_{h+1}^{*}\rangle$
$\displaystyle=r(s_{h},a_{h})+\sum_{s_{h+1}}P(s_{h+1}|s_{h},a_{h})\langle\varphi(s_{h+1}),\theta_{h+1}^{*}\rangle+\sum_{s_{h+1}}P(s_{h+1}|s_{h},a_{h})\rho_{h+1}\max_{a_{h+1}\in\mathcal{A}_{h+1}}\langle
a_{h+1},\theta_{h+1}^{*}\rangle$
$\displaystyle=\mathbb{E}\left[R(s_{h},a_{h})+\langle\varphi(s_{h+1}),\theta_{h+1}^{*}\rangle+\rho_{h+1}\max_{a_{h+1}\in\mathcal{A}_{h+1}}\langle
a_{h+1},\theta_{h+1}^{*}\rangle\Big{|}s_{h},a_{h}\right],$

where $R(s_{h},a_{h})$ is the instant reward we obtain after choosing action
$a_{h}$ from state $s_{h}$ ($R(s_{h},a_{h})$ has mean $r(s_{h},a_{h})$). Hence
for a given fixed policy $\pi$, suppose a trajectory following this policy is
$(s_{1},a_{1},\cdots,s_{H},a_{H})$, then we have

$\mathbb{E}^{\pi}\left[\langle\varphi(s_{h}),\theta_{h}^{*}\rangle\right]+\mathbb{E}^{\pi}[\langle
a_{h},\theta_{h}^{*}\rangle]=\mathbb{E}^{\pi}[\langle\varphi(s_{h+1}),\theta_{h+1}^{*}\rangle]+\mathbb{E}^{\pi}\left[R(s_{h},a_{h})\right]+\rho_{h+1}\max_{a_{h+1}\in\mathcal{A}_{h+1}}\langle
a_{h+1},\theta_{h+1}^{*}\rangle.$

Summing this up from $h=1$ to $h=H$ and noticing that $\theta_{h+1}^{*}=0$, we
obtain that

$\mathbb{E}^{\pi}\left[\langle\varphi(s_{1}),\theta_{1}^{*}\rangle\right]+\mathbb{E}^{\pi}\left[\sum_{h=1}^{H}\langle
a_{h},\theta_{h}^{*}\rangle\right]=\sum_{h=1}^{H}\mathbb{E}^{\pi}[R(s_{h},a_{h})]+\sum_{h=1}^{H}\rho_{h+1}\max_{a_{h+1}\in\mathcal{A}_{h+1}}\langle
a_{h+1},\theta_{h+1}^{*}\rangle.$

With our choice of $\pi_{0}$ (the policy which choose action $0$ at any state
and step), we obtain

$\mathbb{E}^{\pi_{0}}\left[\langle\varphi(s_{1}),\theta_{1}^{*}\rangle\right]=\sum_{h=1}^{H}\mathbb{E}^{\pi_{0}}[R(s_{h},a_{h})]+\sum_{h=1}^{H}\rho_{h+1}\max_{a_{h+1}\in\mathcal{A}_{h+1}}\langle
a_{h+1},\theta_{h+1}^{*}\rangle.$

We notice that for every policy $\pi$,
$\mathbb{E}^{\pi}\left[\langle\varphi(s_{1}),\theta_{1}^{*}\rangle\right]$ are
identical. Hence after subtracting the above two equations, we get

$\mathbb{E}^{\pi}\left[\sum_{h=1}^{H}\langle
a_{h},\theta_{h}^{*}\rangle\right]=\mathbb{E}^{\pi}\left[\sum_{h=1}^{H}R(s_{h},a_{h})\right]-\mathbb{E}^{\pi_{0}}\left[\sum_{h=1}^{H}R(s_{h},a_{h})\right].$
(8)

With our choice of policy $\pi_{h,i}$, the above equation indicates that

$\rho_{h}\theta_{h,i}^{*}=\rho_{h}\langle\mathbf{e}_{i},\theta_{h}^{*}\rangle=\mathbb{E}^{\pi_{h,i}}\left[\sum_{h=1}^{H}R(s_{h},a_{h})\right]-\mathbb{E}^{\pi_{0}}\left[\sum_{h=1}^{H}R(s_{h},a_{h})\right],$

where $\theta_{h,i}^{*}$ is the $i$-th component of $\theta_{h}^{*}$.
According to our algorithm, we have
$\rho_{h}\hat{\theta}_{h,i}=R_{h,i}-R_{h,0}$, and we also have

$\mathbf{E}\left[R_{h,i}-R_{h,i}\right]=\mathbb{E}^{\pi_{h,i}}\left[\sum_{h=1}^{H}R(s_{h},a_{h})\right]-\mathbb{E}^{\pi_{0}}\left[\sum_{h=1}^{H}R(s_{h},a_{h})\right]=\rho_{h}\theta_{h,i}^{*}.$

Therefore, according to Hoeffding inequality, with probability at least
$1-2\delta^{\prime}$ we have,

$\rho_{h}\left|\hat{\theta}_{h,i}-\theta_{h,i}^{*}\right|\leq
2\sqrt{\frac{\log(1/\delta^{\prime})}{2M}}=\sqrt{\frac{2\log(1/\delta^{\prime})}{M}},$

if we assume that $\sum_{h=1}^{H}R(s_{h},a_{h})\in[0,1]$ always holds. This
indicates that with probability at least $1-2dH\delta^{\prime}$, for every
$1\leq h\leq H$,

$\rho_{h}\left\|\hat{\theta}_{h}-\theta_{h}^{*}\right\|_{2}\leq\sqrt{\frac{2d\log(1/\delta^{\prime})}{M}}.$

Moreover, since $a_{h}=\arg\max_{a\in\mathcal{A}_{h}}\langle
a_{h},\hat{\theta}_{h}\rangle,$ we have

$\displaystyle\langle a_{h},\theta_{h}^{*}\rangle-\langle
a_{h}^{*},\theta_{h}^{*}\rangle$ $\displaystyle=\langle
a_{h},\theta_{h}^{*}-\hat{\theta}_{h}\rangle+\langle
a_{h},\hat{\theta}_{h}\rangle-\langle
a_{h}^{*},\hat{\theta}_{h}\rangle+\langle
a_{h}^{*},\hat{\theta_{h}}-\theta_{h}^{*}\rangle$ $\displaystyle\leq\langle
a_{h},\theta_{h}^{*}-\hat{\theta}_{h}\rangle+\langle
a_{h}^{*},\hat{\theta_{h}}-\theta_{h}^{*}\rangle$ $\displaystyle\leq
2\eta_{h}\cdot\|\theta_{h}-\hat{\theta}_{h}\|_{2}$ $\displaystyle\leq
2B\cdot\sqrt{\frac{2d\log(1/\delta^{\prime})}{M}},$

where the first inequality is due to
$a_{h}=\arg\max_{a\in\mathcal{A}_{h}}\langle a_{h},\hat{\theta}_{h}\rangle$,
and the second inequality is due to $a_{h},a_{h}^{*}\in\mathcal{A}_{h}\subset
B_{2}(\eta_{h})$. Therefore, according to (8) we have

$V^{*}(s_{1})-V^{\pi}(s_{1})\leq
2BH\sqrt{\frac{2d\log(1/\delta^{\prime})}{M}}.$

With our choice of $\delta^{\prime}=\frac{\delta}{2dH}$ and
$M=\frac{8H^{2}B^{2}d\log(2dH/\delta)}{\epsilon^{2}}$, we have with
probability at least $1-\delta$, the output policy $\pi$ satisfies that

$V^{*}(s_{1})-V^{\pi}(s_{1})\leq\epsilon.$

##  Appendix B Proof of Theorem 4.5

To prove the complexity of our algorithm, we first show the following several
lemmas:

######  Lemma B.1.

For each policy $\pi$, we have the following equation

$\langle\varphi(s_{1}),\theta_{1}^{*}\rangle+\mathbb{E}^{\pi}\left[\sum_{h=1}^{H}\langle
a_{h},\theta_{h}^{*}\rangle\right]=\mathbb{E}^{\pi}\left[\sum_{h=1}^{H}R(s_{h},a_{h})\right]+\Theta\cdot\mathbb{E}^{\pi}\left[\sum_{h=1}^{H}\rho(s_{h+1})\right],$
(9)

where we use the notation that $\rho(s_{H+1})=0$.

######  Proof B.2.

According to the Bellman Equation (1) at step $h$, we have

$\displaystyle Q_{h}^{*}(s_{h},a_{h})$
$\displaystyle=r(s_{h},a_{h})+\sum_{s_{h+1}}P(s_{h+1}|s_{h},a_{h})V_{h+1}^{*}(s_{h+1})$
$\displaystyle=r(s_{h},a_{h})+\sum_{s_{h+1}}P(s_{h+1}|s_{h},a_{h})\max_{a_{h+1}\in\mathcal{A}(s_{h+1})}\langle\varphi(s_{h+1})+a_{h+1},\theta_{h+1}^{*}\rangle$
$\displaystyle=r(s_{h},a_{h})+\sum_{s_{h+1}}P(s_{h+1}|s_{h},a_{h})\max_{a_{h+1}\in
B_{2}(\rho(s_{h+1}))}\langle\varphi(s_{h+1})+a_{h+1},\theta_{h+1}^{*}\rangle$
$\displaystyle=r(s_{h},a_{h})+\sum_{s_{h+1}}P(s_{h+1}|s_{h},a_{h})\rho(s_{h+1})\|\theta_{h+1}^{*}\|_{2}+\sum_{s_{h+1}}P(s_{h+1}|s_{h},a_{h})\langle\varphi(s_{h+1}),\theta_{h+1}^{*}\rangle$
$\displaystyle=\mathbb{E}^{\pi}\left[R(s_{h},a_{h})+\rho_{h+1}\|\theta_{h+1}^{*}\|_{2}+\langle\varphi(s_{h+1}),\theta_{h+1}^{*}\rangle\big{|}s_{h},a_{h}\right]$
$\displaystyle=\mathbb{E}^{\pi}\left[R(s_{h},a_{h})+\rho_{h+1}\cdot\Theta+\langle\varphi(s_{h+1}),\theta_{h+1}^{*}\rangle\big{|}s_{h},a_{h}\right].$

Since

$Q_{h}^{*}(s_{h},a_{h})=\langle\varphi(s_{h},a_{h}),\theta_{h}^{*}\rangle=\langle\varphi(s_{h}),\theta_{h}^{*}\rangle+\langle
a_{h},\theta_{h}^{*}\rangle,$

if we take the expectation over $s_{h}$ and $a_{h}$, we will have

$\mathbb{E}^{\pi}\left[\langle\varphi(s_{h}),\theta_{h}^{*}\rangle+\langle
a_{h},\theta_{h}^{*}\rangle\right]=\mathbb{E}^{\pi}\left[R(s_{h},a_{h})+\rho(s_{h+1})\cdot\Theta+\langle\varphi(s_{h+1}),\theta_{h+1}^{*}\rangle\right].$

Telescoping this equation from $h=1$ to $h=H$, we will get (9).

The following lemma indicates that if we have accurate enough estimation on
the $\theta_{1},\cdots,\theta_{H}$, then the greedy policy is a nearly optimal
policy.

######  Lemma B.3.

Suppose we have estimation $\hat{\theta}_{1},\cdots,\hat{\theta}_{H}$, which
satisfy

$\left\|\hat{\theta}_{h}-\theta_{h}^{*}\right\|_{2}\leq\varepsilon_{h},\quad\forall
1\leq h\leq H.$

If consider policy $\pi$ to be the greedy policy with respect to
$\hat{\theta}_{1},\cdots,\hat{\theta}_{H}$, then we have, e.g.

$\pi(s_{h})=\mathop{\arg\max}_{a_{h}\in\mathcal{A}(s_{h})}\left\langle\varphi(s_{h},a_{h}),\hat{\theta}_{h}\right\rangle,$

then we have

$V_{1}^{*}(s_{1})-V_{1}^{\pi}(s_{1})\leq
2\sum_{h=1}^{H}\mathbb{E}[\rho(s_{h})]\varepsilon_{h}.$

######  Proof B.4.

We use $\pi^{*}(s)$ to denote the action of $s$ in the best policy (which is
deterministic). Then we have

$V_{1}^{*}(s_{1})=Q_{1}^{*}(s_{1},\pi^{*}(s_{1}))=\langle\varphi(s_{1}),\theta_{1}^{*}\rangle+\langle\pi^{*}(s_{1}),\theta_{1}^{*}\rangle.$

We further have

$\displaystyle\langle\pi^{*}(s_{1}),\theta_{1}^{*}\rangle$
$\displaystyle=\left\langle\pi^{*}(s_{1}),\theta_{1}^{*}-\hat{\theta}_{1}\right\rangle+\left\langle\pi^{*}(s_{1}),\hat{\theta}_{1}\right\rangle\leq\rho(s_{1})\cdot\left\|\theta_{1}^{*}-\hat{\theta}_{1}\right\|_{2}+\left\langle\pi^{*}(s_{1}),\hat{\theta}_{1}\right\rangle$
$\displaystyle\leq\rho(s_{1})\cdot\left\|\theta_{1}^{*}-\hat{\theta}_{1}\right\|_{2}+\left\langle\pi(s_{1}),\hat{\theta}_{1}\right\rangle=\rho(s_{1})\cdot\left\|\theta_{1}^{*}-\hat{\theta}_{1}\right\|_{2}+\left\langle\pi(s_{1}),\theta_{1}^{*}\right\rangle+\left\langle\pi(s_{1}),\hat{\theta}_{1}-\theta_{1}^{*}\right\rangle$
$\displaystyle\leq
2\rho(s_{1})\cdot\left\|\theta_{1}^{*}-\hat{\theta}_{1}\right\|_{2}+\left\langle\pi(s_{1}),\theta_{1}^{*}\right\rangle,$

where the first and last inequality are due to
$\pi(s_{1}),\pi^{*}(s_{1})\in\mathcal{A}(s_{1})$, and the second inequality is
due to the definition of $\pi(s_{1})$ (greedy policy $w.r.t$
$\hat{\theta}_{1}$). Therefore, we obtain that

$\displaystyle V_{1}^{*}(s_{1})-V^{\pi}(s_{1})$ $\displaystyle\leq
2\rho(s_{1})\cdot\left\|\theta_{1}^{*}-\hat{\theta}_{1}\right\|_{2}+\left\langle\pi(s_{1}),\theta_{1}^{*}\right\rangle+\langle\varphi(s_{1}),\theta_{1}^{*}\rangle-V^{\pi}(s_{1})$
$\displaystyle=2\rho(s_{1})\cdot\left\|\theta_{1}^{*}-\hat{\theta}_{1}\right\|_{2}+Q^{*}_{1}(s_{1},\pi(s_{1}))-V^{\pi}(s_{1})$
$\displaystyle=2\rho(s_{1})\cdot\left\|\theta_{1}^{*}-\hat{\theta}_{1}\right\|_{2}+r(s_{1},\pi(s_{1}))+\mathbb{E}^{\pi}[V_{2}^{*}(s_{2})]-\left(r(s_{1},\pi(s_{1}))+\mathbb{E}^{\pi}[V_{2}^{\pi}(s_{2})]\right)$
$\displaystyle=2\rho(s_{1})\cdot\left\|\theta_{1}^{*}-\hat{\theta}_{1}\right\|_{2}+\mathbb{E}^{\pi}\left[V_{2}^{*}(s_{2})-V_{2}^{\pi}(s_{2})\right].$

We can continue the same process for $V_{2}$, and obtain that

$\mathbb{E}^{\pi}\left[V_{2}^{*}(s_{2})-V_{2}^{\pi}(s_{2})\right]\leq
2\mathbb{E}^{\pi}[\rho(s_{2})]\cdot\left\|\theta_{2}^{*}-\hat{\theta}_{2}\right\|_{2}+\mathbb{E}^{\pi}\left[V_{3}^{*}(s_{3})-V_{3}^{\pi}(s_{3})\right].$

Keeping doing this until we get $V_{H+1}^{*}(s_{H+1})-V_{H+1}^{\pi}(s_{H+1})$,
which is zero, we obtain that

$V_{1}^{*}(s_{1})-V_{1}^{\pi}(s_{1})\leq
2\sum_{h=1}^{H}\mathbb{E}[\rho(s_{h})]\cdot\left\|\theta_{h}^{*}-\hat{\theta}_{h}\right\|_{2}.$

Therefore, when
$\left\|\theta_{h}^{*}-\hat{\theta}_{h}\right\|_{2}\leq\varepsilon_{h}$, we
will have

$V_{1}^{*}(s_{1})-V_{1}^{\pi}(s_{1})\leq
2\sum_{h=1}^{H}\mathbb{E}[\rho(s_{h})]\varepsilon_{h}$

######  Proof B.5 (Proof of Theorem 4.5).

We will divide our proof in the following parts:

##### Concentration Inequalities

In the following, we fix all parameters within one ‘while’ loop in the
algorithm.

According to the Boundedness Assumption (Assumption 4), and Hoeffding
inequality, we have that each of the following inequalities holds with
probability at least $1-\delta^{\prime}$ separately for $0\leq i\leq d$,

$\displaystyle\left|R_{h,i}-\mathbb{E}^{\pi_{h,i}}\left[\sum_{h^{\prime}=1}^{H}R(s_{h^{\prime}},a_{h^{\prime}})\right]\right|\leq\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{1}}}$
(10)
$\displaystyle\left|s_{h,i}-\mathbb{E}^{\pi_{h,i}}\left[\sum_{h^{\prime}=1}^{H}\rho(s_{h^{\prime}+1})\right]\right|\leq\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{1}}}.$

We further notice that the before step $h$, policy $\pi_{h,i}$ and policy
$\pi_{h,0}$ are both same as policy $\pi$, and for every $h^{\prime}>h$ and
$s_{h^{\prime}}\in\mathcal{S}_{h^{\prime}}$, we both have
$\pi_{h,i}(s_{h^{\prime}})=\pi_{h,0}(s_{h^{\prime}})=0$. Therefore, according
to (9), we have

$\displaystyle\mathbb{E}^{\pi}[\rho(s_{h})]\cdot\langle\mathbf{e}_{i},\theta_{h}^{*}\rangle$
$\displaystyle=\mathbb{E}^{\pi_{h,i}}\left[\sum_{h^{\prime}=1}^{H}\langle
a_{h^{\prime}},\theta_{h^{\prime}}^{*}\rangle\right]-\mathbb{E}^{\pi_{h,0}}\left[\sum_{h^{\prime}=1}^{H}\langle
a_{h^{\prime}},\theta_{h^{\prime}}^{*}\rangle\right]$ (11)
$\displaystyle=\mathbb{E}^{\pi_{h,i}}\left[\sum_{h^{\prime}=1}^{H}R(s_{h^{\prime}},a_{h^{\prime}})\right]+\Theta\cdot\mathbb{E}^{\pi_{h,i}}\left[\sum_{h^{\prime}=1}^{H}\rho(s_{h^{\prime}+1})\right]$
$\displaystyle\quad-\mathbb{E}^{\pi_{h,0}}\left[\sum_{h^{\prime}=1}^{H}R(s_{h^{\prime}},a_{h^{\prime}})\right]-\Theta\cdot\mathbb{E}^{\pi_{h,0}}\left[\sum_{h^{\prime}=1}^{H}\rho(s_{h^{\prime}+1})\right].$

According to (10), if we further assume $|\Theta-\xi|\leq\eta$, then with
probability at least $1-2(d+1)\delta^{\prime}$, we have for every $1\leq i\leq
d$,

$|\text{RHS of
}\eqref{eq-10}-((s_{h,i}-s_{h,0})\xi+R_{h,i}-R_{h,0})|\leq\eta+\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{1}}}+\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{1}}}=\eta+2\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{1}}},$

where we have used the fact that $|s_{h,i}-s_{h,0}|\leq 1$ and also
$|\Theta|\leq 1.$ Moreover, in the last ‘while’ loop, with probability at
least $1-LH\delta$, according to Hoeffding inequality we have

$\left|\rho_{h}^{l}-\mathbb{E}^{\pi_{l}^{\prime}}\left[\rho(s_{h})\right]\right|\leq\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}},\quad\forall
1\leq l\leq L,1\leq h\leq H.$

Hence we have with probability at least $1-(2d+3)\delta^{\prime}$,

$\left|\rho_{h}\langle\mathbf{e}_{i},\theta_{h}^{*}\rangle-((s_{h,i}-s_{h,0})\xi+R_{h,i}-R_{h,0})\right|\leq\eta+2\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{1}}}+\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}}.$

According to our algorithm, there exists one $l$ such that
$|l\eta-\Theta|\leq\eta$, we write this $l$ as $l_{0}$. Then with
$\xi=l_{0}\eta$, we have

$\hat{\theta}_{h,i}^{l_{0}}=\frac{(s_{h,i}-s_{h,0})\xi+R_{h,i}-R_{h,0}}{\rho_{h}}.$

Therefore, we obtain that

$\left|\rho_{h}\left(\langle\mathbf{e}_{i},\theta_{h}^{*}\rangle-\hat{\theta}_{h,i}^{l_{0}}\right)\right|\leq\eta+2\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{1}}}+\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}}.$

According to our construction of $\hat{\theta}_{h}^{l_{0}}$, we have

$\rho_{h}\left\|\theta_{h}-\hat{\theta}_{h}^{l_{0}}\right\|_{2}\leq\eta
d+2d\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{1}}}+d\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}}.$

If in the next ‘while’ loop, the condition does not satisfy, then before the
next loop, for every $1\leq h\leq H$ and $1\leq l\leq L$, we will have
$\rho_{h}^{l}\leq\varepsilon$ or $\rho_{h}^{l}\leq\rho_{h}$. Hence for
$l_{0}$, we also have either $\rho_{h}^{l_{0}}\leq\varepsilon$ or
$\rho_{h}^{l_{0}}\leq\rho_{h}$ for $1\leq h\leq H$. With loss of generality,
we can assume $\left\|\hat{\theta}_{h}^{l_{0}}\right\|_{2}\leq 1$, otherwise
we can consider
$\hat{\theta}_{h}^{l_{0}}\leftarrow\hat{\theta}_{h}^{l_{0}}/\|\hat{\theta}_{h}^{l_{0}}\|_{2}$,
which will induce the same policy, and
$\left\|\theta_{h}-\hat{\theta}_{h}^{l_{0}}\right\|_{2}$ will decrease under
this operation. According to Hoeffding inequality and union bound, we have
with probability at least $1-HL\delta^{\prime}$, for every $1\leq l\leq L$ and
$1\leq h\leq H$,

$\left|\rho_{h}^{l}-\mathbb{E}^{\pi_{l}^{\prime}}(\rho(s_{h}))\right|\leq\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}}.$

Hence according to Lemma B.3, we have

$V_{1}^{*}(s_{1})-V_{1}^{\pi_{l_{0}}^{\prime}}(s_{1})\leq
2\sum_{h=1}^{H}\mathbb{E}^{\pi_{l_{0}}^{\prime}}[\rho(s_{h})]\left\|\theta_{h}-\hat{\theta}_{h}^{l_{0}}\right\|_{2}.$

If we assume the above high-probability event all hold, then we have

$\text{RHS}\leq
4H\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}}+2\sum_{h=1}^{H}\rho_{h}^{l_{0}}\left\|\theta_{h}-\hat{\theta}_{h}^{l_{0}}\right\|_{2},$

where we use the fact that
$\left\|\theta_{h}-\hat{\theta}_{h}^{l_{0}}\right\|_{2}\leq 2$ since
$\|\theta_{h}\|_{2}\leq 1$ and $\|\hat{\theta}_{h}^{l_{0}}\|_{2}\leq 1$ both
hold. According to the condition that we do not enter the next ‘while’ loop,
the last term above can be upper bounded by

$2H\cdot\left(\varepsilon+\eta
d+2d\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{1}}}+d\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}}\right).$

Therefore, we obtain that with probability at least
$1-d\delta^{\prime}-2HL\delta^{\prime}$

$V_{1}^{*}(s_{1})-V_{1}^{\pi_{l_{0}}^{\prime}}(s_{1})\leq 2H\varepsilon+2H\eta
d+4H\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}}+4Hd\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{1}}}+2Hd\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}}.$

Further again according to Hoeffding inequality, we know that with probability
at least $1-HL\delta$, we have

$\left|R_{l}-V_{1}^{\pi_{l_{0}}^{\prime}}(s_{0})\right|\leq\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}}.$

If we assume

$l_{1}=\mathop{\arg\max}_{l}R_{l},$

then we have

$V_{1}^{\pi_{l_{0}}^{\prime}}(s_{0})-V_{1}^{\pi}(s_{0})=V_{1}^{\pi_{l_{0}}^{\prime}}(s_{0})-V_{1}^{\pi_{l_{1}}^{\prime}}(s_{0})\leq
2\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}}+R_{l_{0}}-R_{l_{1}}\leq
2\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}}.$

Therefore, we have proved that if the ‘while’ loop ends, then with probability
at least $1-d\delta^{\prime}-3HL\delta^{\prime}$, the output policy $\pi$
satisfies that

$V_{1}^{*}(s_{1})-V_{1}^{\pi}(s_{1})\leq 2H\varepsilon+2H\eta
d+(2+4H+2Hd)\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{2}}}+4Hd\sqrt{\frac{2\log(1/\delta^{\prime})}{M_{1}}}.$

##### Bound on Iterations in ‘While’ Loop

What left in this proof is to show that the ‘while’ loop will terminate within
some certain number of iterations.

We notice that starting from the third iterations of the ‘while’ loop, if we
choose some $h$ which satisfies the loop condition, then the value of
$\rho_{h}$ will at least be twice of the previous loop. And the value of
$\rho_{h}$ will be at least $\varepsilon$ in order to enter the loop.
Moreover, the value of $\rho_{h}$ will never exceed $1$ due to the boundedness
assumption. Therefore, the loop will at most run

$1+H\log_{2}\left(\frac{1}{\varepsilon}\right)$

times.

Therefore, choosing $\varepsilon=\frac{\epsilon}{8H}$,
$\delta^{\prime}=\frac{\delta}{(d+3HL)(1+H\log_{2}(1/\varepsilon))}$,
$\eta=\frac{\epsilon}{8Hd}$,
$M_{2}=2\log(1/\delta^{\prime})\cdot\frac{16(2+4H+2Hd)^{2}}{\epsilon^{2}}$ and
$M_{1}=2\log(1/\delta^{\prime})\cdot\frac{256H^{2}d^{2}}{\epsilon^{2}}$ and
$L=\frac{1}{\eta}$, then our algorithm will output an $\epsilon$-optimal
policy using at most

$\left(M_{1}Hd+M_{2}HL\right)\cdot\left(1+H\log_{2}\left(\frac{1}{\varepsilon}\right)\right)=\tilde{\mathcal{O}}\left(\frac{H^{5}d^{3}}{\epsilon^{3}}\right)$

number of samples.