# Provably Efficient Reinforcement Learning
for Infinite-Horizon Average-Reward Linear MDPs

Kihyuk Hong
University of Michigan
<EMAIL_ADDRESS>
&Yufan Zhang
University of Michigan
<EMAIL_ADDRESS>
&Ambuj Tewari
University of Michigan
<EMAIL_ADDRESS>

###### Abstract

We resolve the open problem of designing a computationally efficient algorithm
for infinite-horizon average-reward linear Markov Decision Processes (MDPs)
with $\widetilde{\mathcal{O}}(\sqrt{T})$ regret. Previous approaches with
$\widetilde{\mathcal{O}}(\sqrt{T})$ regret either suffer from computational
inefficiency or require strong assumptions on dynamics, such as ergodicity. In
this paper, we approximate the average-reward setting by the discounted
setting and show that running an optimistic value iteration-based algorithm
for learning the discounted setting achieves
$\widetilde{\mathcal{O}}(\sqrt{T})$ regret when the discounting factor
$\gamma$ is tuned appropriately. The challenge in the approximation approach
is to get a regret bound with a sharp dependency on the effective horizon
$1/(1-\gamma)$. We use a computationally efficient clipping operator that
constrains the span of the optimistic state value function estimate to achieve
a sharp regret bound in terms of the effective horizon, which leads to
$\widetilde{\mathcal{O}}(\sqrt{T})$ regret.

##  1 Introduction

Reinforcement learning (RL) with infinite-horizon average-reward setting is
appropriate for applications where the interaction of the agent with the
environment has no natural termination condition, such as network routing [20]
and inventory management [11]. Designing and analyzing algorithms for this
setting is challenging because the corresponding Bellman operator is not a
contraction. This prevents the use of optimistic value iteration-based
algorithms, which add bonus terms to the value function, a common approach in
the finite-horizon episodic and infinite-horizon discounted settings.

Faced with this challenge, a seminal work by [15] adopts a model-based
approach in the tabular setting. Their algorithm constructs a confidence set
on the transition model and runs value iterations by choosing an optimistic
model from the confidence set every iteration without adding a bonus term.
Most works in the tabular setting use the idea of constructing a confidence
set on the model [6, 9]. Other works either have suboptimal regret bound [28]
or assume a strong ergodic assumption [28].

The model-based approach for the tabular setting cannot be generalized to
function approximation settings, as the state space can be arbitrarily large,
making sample efficient model estimation difficult. Consequently, works on
infinite-horizon average-reward RL with function approximation are sparse.
Even for the linear MDP setting, all known works either make a strong ergodic
assumption [27] or use computationally inefficient algorithms [27, 14] to
achieve $\widetilde{\mathcal{O}}(\sqrt{T})$ regret.

A recent line of work employs the technique of approximating the infinite-
horizon average-reward RL with tabular MDPs by the discounted setting. The key
idea is that the discounted setting closely approximates the average-reward
setting when the discounting factor is close to 1. The approximation is
beneficial because the discounted setting allows for greater flexibility in
algorithm choice, thanks to the contraction property of the corresponding
Bellman operator. There is a trade-off in choosing $\gamma$: the closer
$\gamma$ is to 1, the lower the approximation error of the discounted setting
but the higher the regret for the discounted setting, which is polynomial in
$1/(1-\gamma)$. [28] use the approximation idea to design a model-free
Q-learning based algorithm, but with suboptimal regret bound of
$\widetilde{\mathcal{O}}(T^{2/3})$ due to suboptimal order of $1/(1-\gamma)$
in their bound. More recently, [31] achieve
$\widetilde{\mathcal{O}}(\sqrt{T})$ regret by improving the order of
$1/(1-\gamma)$ in the regret bound. Their algorithm is model-free and
computationally efficient, demonstrating that the discounted setting
approximation idea can give $\widetilde{\mathcal{O}}(\sqrt{T})$ regret for
infinite-horizon average-reward RL. In this paper, we apply the discounted
setting approximation idea to the linear MDP setting and make the following
contributions.

  * •

Theoretical result. We design the first computationally efficient algorithm
for infinite-horizon average-reward setting with linear MDPs that achieves
$\widetilde{\mathcal{O}}(\text{sp}(v^{\ast})\sqrt{d^{3}T})$ regret. Adapting
to the tabular setting gives a model-free algorithm with a regret bound of
$\widetilde{\mathcal{O}}(\text{sp}(v^{\ast})\sqrt{S^{3}A^{3}T})$, which is
sharper than previous model-free algorithms for the tabular setting.

  * •

Algorithm design for tabular MDPs We demonstrate in the tabular setting that
approximating the average-reward setting by the discounted setting and running
a simple value iteration-based algorithm with span-constrained value function
estimates designed for the discounted setting can give a
$\widetilde{\mathcal{O}}(\sqrt{T})$ regret for the average-reward setting with
the discount factor tuned appropriately.

  * •

Algorithm design for linear MDPs We propose a novel algorithm design of
constructing monotonically increasing action value function by max-pooling
action value functions obtained from value iteration. The pooling approach, in
contrast to taking maximum with previous value functions every iteration,
prevents the covering number of the function class for value functions
exploding exponentially in $T$. We introduce a clipping operator that allows
for constraining span of the value function computationally efficiently even
in the large state space setting.

#### Related work

A comparison of our work to previous works on infinite-horizon average-reward
linear MDPs is shown in Table 1. We say an algorithm is computationally
efficient if it can be run with computational complexity $\text{poly}(d,A,T)$
where $d$ is the dimension of the feature vector, $A$ is the size of action
space and $T$ is the number of time steps. Our work is the first
computationally efficient algorithm to achieve
$\widetilde{\mathcal{O}}(\sqrt{T})$ regret without making a strong ergodicity
assumption. Our regret matches that of FOPO [27], an algorithm that requires
solving a computationally intractable optimization problem for finding
optimistic value function every iteration. We defer the comparison for the
tabular setting and discussion on other related work to Appendix F.

Table 1: Comparison of algorithms for infinite-horizon average-reward linear MDP Algorithm | Regret $\widetilde{\mathcal{O}}(\cdot)$ | Assumption | Computation
---|---|---|---
FOPO [27] | $\text{sp}(v^{\ast})\sqrt{d^{3}T}$ | Bellman optimality equation | Inefficient
OLSVI.FH [27] | $\sqrt{\text{sp}(v^{\ast})}(dT)^{\frac{3}{4}}$ | Bellman optimality equation | Inefficient
LOOP [14] | $\sqrt{\text{sp}(v^{\ast})^{3}d^{3}T}$ | Bellman optimality equation | Inefficient
MDP-EXP2 [27] | $d\sqrt{t_{\text{mix}}^{3}T}$ | Uniform Mixing | Efficient
$\gamma$-LSCVI-UCB (Ours) | $\text{sp}(v^{\ast})\sqrt{d^{3}T}$ | Bellman optimality equation | Efficient

##  2 Preliminaries

#### Notations

Let $\|\bm{x}\|_{A}=\sqrt{x^{T}Ax}$ for $\bm{x}\in\mathbb{R}^{d}$ and a
positive semidefinite matrix $A\in\mathbb{R}^{d\times d}$. Let $a\vee
b=\max\\{a,b\\}$ and $a\wedge b=\min\\{a,b\\}$. Let $\Delta(\mathcal{X})$ be
the set of probability measures on $\mathcal{X}$. Let $[n]=\\{1,\dots,n\\}$
and $[m:n]=\\{m,m+1,\dots,n\\}$. Let
$\text{sp}(v)=\max_{s,s^{\prime}}|v(s)-v(s^{\prime})|$.

###  2.1 Infinite-horizon average-reward MDP setting

We consider a Markov decision process (MDP)
$\mathcal{M}=(\mathcal{S},\mathcal{A},P,r)$ where $\mathcal{S}$ is the state
space, $\mathcal{A}$ is the action space,
$P:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$ is the
probability transition kernel,
$r:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ is the reward function. We
assume $\mathcal{S}$ is a measurable space with possibly infinite number of
elements and $\mathcal{A}$ is a finite set. We assume the reward is
deterministic and the reward function $r$ is known to the learner. The
probability transition kernel $P$ is unknown to the learner.

The interaction protocol between the learner and the MDP is as follows. The
learner interacts with the MDP for $T$ steps, starting from an arbitrary state
$s_{1}\in\mathcal{S}$ chosen by the environment. At each step $t=1,\dots,T$,
the learner chooses an action $a_{t}\in\mathcal{A}$ and observes the reward
$r(s_{t},a_{t})$ and the next state $s_{t+1}$. The next state $s_{t+1}$ is
drawn by the environment from $P(\cdot|s_{t},a_{t})$.

Consider a stationary policy $\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$
where $\pi(a|s)$ specifies the probability of choosing action $a$ at state
$s$. The performance measure of our interest for the policy $\pi$ is the long-
term average reward starting from an initial state $s$ defined as

$J^{\pi}(s)\coloneqq\liminf_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}^{\pi}\left[\sum_{t=1}^{T}r(s_{t},a_{t})|s_{1}=s\right]$

where $\mathbb{E}^{\pi}[\cdot]$ is the expectation with respect to the
probability distribution on the trajectory $(s_{1},a_{1},s_{2},a_{2},\dots)$
induced by the interaction between $P$ and $\pi$. Our evaluation criterion for
the performance of the learner is the regret against the best stationary
policy $\pi^{\ast}$ that maximizes $J^{\pi}(s_{1})$. Writing
$J^{\ast}(s_{1})\coloneqq J^{\pi^{\ast}}(s_{1})$, the regret is defined as

$R_{T}\coloneqq\sum_{t=1}^{T}(J^{\ast}(s_{1})-r(s_{t},a_{t})).$

As discussed by [6], without an additional assumption on the structure of the
MDP, if the agent enters a bad state from which reaching the optimally
rewarding states is impossible, the agent may suffer a linear regret. To avoid
this pathological case, we follow [27] and make the following structural
assumption on the MDP.

######  Assumption A (Bellman optimality equation).

There exist $J^{\ast}\in\mathbb{R}$ and functions
$v^{\ast}:\mathcal{S}\rightarrow\mathbb{R}$ and
$q^{\ast}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ such that for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$, we have

$J^{\ast}+q^{\ast}(s,a)=r(s,a)+Pv^{\ast}(s,a),\quad\quad
v^{\ast}(s)=\max_{a\in\mathcal{A}}q^{\ast}(s,a).$

As shown by [27], under the assumption above, the policy $\pi^{\ast}$ that
deterministically selects an action from
$\operatorname*{argmax}_{a}q^{\ast}(s,a)$ at each state $s\in\mathcal{S}$ is
an optimal policy. Moreover, $\pi^{\ast}$ always gives an optimal average
reward $J^{\pi^{\ast}}(s_{1})=J^{\ast}$ for all initial states
$s_{1}\in\mathcal{S}$. Since the optimal average reward is independent of the
initial state, we can simply write the regret as
$R_{T}=\sum_{t=1}^{T}(J^{\ast}-r(s_{t},a_{t}))$. Functions $v^{\ast}(s)$ and
$q^{\ast}(s,a)$ are the relative advantage of starting with $s$ and $(s,a)$
respectively. We can expect a problem with large $\text{sp}(v^{\ast})$ to be
more difficult since starting with a bad state can be more disadvantageous. As
is common in the literature [6, 28], we assume $\text{sp}(v^{\ast})$ is known
to the learner.

###  2.2 Approximation by infinite-horizon discounted setting

The key idea of this paper, inspired by [31], is to approximate the infinite-
horizon average-reward setting by the infinite-horizon discounted setting with
a discount factor $\gamma\in[0,1)$ tuned carefully. Introducing the
discounting factor allows for a computationally efficient algorithm design
that exploits the contraction property of the Bellman operator for the
infinite-horizon discounted setting. When $\gamma$ is close to 1, we expect
the optimal policy for the discounted setting to be nearly optimal for the
average-reward setting, given the classical result [23] that says the average
reward of a stationary policy is equal to the limit of the discounted
cumulative reward as $\gamma$ goes to $1$. Before stating a lemma that relates
the infinite-horizon average-reward setting and the infinite-horizon
discounted setting, we define the value function under the discounted setting.
For a policy $\pi$, define

$V^{\pi}(s)=\mathbb{E}^{\pi}\left[\sum_{t=1}^{\infty}\gamma^{t-1}r(s_{t},a_{t})|s_{1}=s\right],\quad
Q^{\pi}(s,a)=\mathbb{E}^{\pi}\left[\sum_{t=1}^{\infty}\gamma^{t-1}r(s_{t},a_{t})|s_{1}=s,a_{1}=a\right].$

We suppress the dependency of the value functions on the discounting factor
$\gamma$ for notational convenience. We write the optimal value functions
under the discounted setting as

$V^{\ast}(s)=\max_{\pi}V^{\pi}(s),\quad Q^{\ast}(s,a)=\max_{\pi}Q^{\pi}(s,a).$

The following lemma relates the infinite-horizon average-reward setting and
the discounted setting.

######  Lemma 1 (Lemma 2 in [28]).

For any $\gamma\in[0,1)$, the optimal value function $V^{\ast}$ for the
infinite-horizon discounted setting with discounting factor $\gamma$ satisfies

$\text{sp}(V^{\ast})\leq
2\text{sp}(v^{\ast}),\quad|(1-\gamma)V^{\ast}(s)-J^{\ast}|\leq(1-\gamma)\text{sp}(v^{\ast})~{}~{}\text{for
all}~{}s\in\mathcal{S}.$

As discussed by [28], the lemma above implies that the difference between the
optimal average reward $J^{\ast}$ and the optimal discounted cumulative reward
normalized with the factor $(1-\gamma)$ is small as long as $\gamma$ is close
to 1. Hence, we can expect the policy optimal under the discounted setting is
nearly optimal for the average-reward setting as long as $\gamma$ is close to
1.

##  3 Warmup: tabular setting

In this section, we present an algorithm for the tabular setting with finite
state space $\mathcal{S}$ and finite action space $\mathcal{A}$ with no
additional structure assumed for the reward function and the transition
probability. The algorithm structure and the analysis idea will serve as a
preparation for the linear MDP setting.

Input: Discounting factor $\gamma\in[0,1)$, span $H$, bonus factor $\beta$.

Initialize: $Q_{1}(s,a),V_{1}(s)\leftarrow\frac{1}{1-\gamma}$;
$N_{0}(s,a,s^{\prime})\leftarrow 0,N_{0}(s,a)\leftarrow 1$, for all
$(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$.

1 Receive initial state $s_{1}$.

2 for  _time step $t=1,\dots,T$_ do

3 Take action $a_{t}=\operatorname*{argmax}_{a}Q_{t}(s_{t},a)$. Receive reward
$r(s_{t},a_{t})$. Receive next state $s_{t+1}$.

4 $N_{t}(s_{t},a_{t},s_{t+1})\leftarrow N_{t-1}(s_{t},a_{t},s_{t+1})+1$,
$N_{t}(s_{t},a_{t})\leftarrow N_{t-1}(s_{t},a_{t})+1$.

5 (Other entries of $N_{t}$ remain the same as $N_{t-1}$.)

6 $\widehat{P}_{t}(s^{\prime}|s,a)\leftarrow
N_{t}(s,a,s^{\prime})/N_{t}(s,a)$.

7
$Q_{t+1}(s,a)\leftarrow(r(s,a)+\gamma(\widehat{P}_{t}V_{t})(s,a)+\beta\sqrt{1/N_{t}(s,a)})\wedge
Q_{t}(s,a)$.

8 $\widetilde{V}_{t+1}(s)\leftarrow(\max_{a}Q_{t+1}(s,a))\wedge V_{t}(s)$.

9
$V_{t+1}(s)\leftarrow\widetilde{V}_{t+1}(s)\wedge(\min_{s^{\prime}}\widetilde{V}_{t+1}(s^{\prime})+H)$.

10

Algorithm 1 $\gamma$-UCB-CVI for Tabular Setting

Our algorithm called discounted upper confidence bound clipped value iteration
($\gamma$-UCB-CVI) adapts UCBVI [5] designed for the finite-horizon episodic
setting to the infinite-horizon discounted setting. Every time step, the
algorithm performs an approximate Bellman backup with a bonus term (Line 1),
which ensures optimism $Q_{t}\geq Q^{\ast}$ for all $t=1,\dots,T$. A key
difference from UCBVI is the clipping step (Line 1) that ensures the value
function estimate $V_{t}$ has span bounded by $H$. With the discounting factor
$\gamma$ tuned carefully and setting $H$ to $2\cdot\text{sp}(v^{\ast})$, we
get the following regret bound.

######  Theorem 2.

Under Assumption A, there exists a constant $c>0$ such that, for any fixed
$\delta\in(0,1)$, if we run Algorithm 1 with $\gamma=1-\sqrt{1/T}$, $H=2\cdot
sp(v^{\ast})$, $\beta=cH\sqrt{S\log(SAT/\delta)}$ then with probability at
least $1-\delta$, the total regret is bounded by

$R_{T}\leq\mathcal{O}\left(\text{sp}(v^{\ast})\sqrt{S^{2}AT\log(SAT/\delta)}\right).$

The constant $c$ is chosen in Lemma 3. Our regret bound matches the best
previously known regret bound for computationally efficient algorithm in this
setting. We believe we can improve our bound by a factor of $\sqrt{S}$ with a
refined analysis using Bernstein inequality, following the idea of the refined
analysis for UCBVI provided by [5]. We leave the improvement to future work.

For the remainder of the section, we give a sketch of the proof of regret
bound given in Theorem 2. The key to the proof is the following concentration
inequality for the model estimate.

######  Lemma 3.

Under the setting of Theorem 2, there exists a constant $c$ such that for any
fixed $\delta\in(0,1)$, if we let $\mathfrak{E}$ be the event that:

$|(\widehat{P}_{t}-P)V_{t}(s,a)|\leq
c\cdot\text{sp}(v^{\ast})\sqrt{S\log(SAT/\delta)/N_{t}(s,a)},~{}~{}\forall(s,a,t)\in\mathcal{S}\times\mathcal{A}\times[T],$

then $\mathbb{P}(\mathfrak{E})\geq 1-\delta$.

See Appendix B.1 for a proof. With the concentration inequality, we can show
the following optimism result. See Appendix B.2 for a proof.

######  Lemma 4 (Optimism).

Under the setting of Theorem 2, on the event $\mathfrak{E}$ defined in Lemma
3, we have

$V_{t}(s)\geq V^{\ast}(s),\quad Q_{t}(s,a)\geq Q^{\ast}(s,a)$

for all $(s,a,t)\in\mathcal{S}\times\mathcal{A}\times[T]$.

Now, we show the regret bound. By the value iteration step (Line 1) of
Algorithm 1 and the concentration inequality in Lemma 3, we have for all
$t=2,\dots,T$ that

$\displaystyle r(s_{t},a_{t})$ $\displaystyle\geq
Q_{t}(s_{t},a_{t})-\gamma(\widehat{P}_{t-1}V_{t-1})(s_{t},a_{t})-\beta\sqrt{1/N_{t-1}(s_{t},a_{t})}$
$\displaystyle\geq
V_{t}(s_{t})-\gamma(PV_{t-1})(s_{t},a_{t})-2\beta\sqrt{1/N_{t-1}(s_{t},a_{t})}$

where the second inequality follows by
$V_{t}(s_{t})\leq\widetilde{V}_{t}(s_{t})\leq\max_{a}Q_{t}(s_{t},a)=Q_{t}(s_{t},a_{t})$.
Hence, the regret can be bounded by the following decomposition.

$\displaystyle R_{T}$
$\displaystyle=TJ^{\ast}-\sum_{t=1}^{T}r(s_{t},a_{t})\leq
TJ^{\ast}-\sum_{t=2}^{T}(V_{t}(s_{t})-\gamma(PV_{t-1})(s_{t},a_{t}))+2\beta\sum_{t=2}^{T}\sqrt{1/N_{t-1}(s_{t},a_{t})}$
$\displaystyle=\underbrace{\sum_{t=2}^{T}(J^{\ast}-(1-\gamma)V_{t}(s_{t}))}_{(a)}+\gamma\underbrace{\sum_{t=2}^{T}(V_{t-1}(s_{t+1})-V_{t}(s_{t}))}_{(b)}$
$\displaystyle\quad\quad\quad\quad+\gamma\underbrace{\sum_{t=2}^{T}(PV_{t-1}(s_{t},a_{t})-V_{t-1}(s_{t+1}))}_{(c)}+~{}2\underbrace{\beta\sum_{t=2}^{T}1/\sqrt{1/N_{t-1}(s_{t},a_{t})}}_{(d)}+~{}J^{\ast}.$

#### Bounding term $\bm{(a)}$

We can bound

$\sum_{t=2}^{T}(J^{\ast}-(1-\gamma)V_{t}(s_{t}))\leq\sum_{t=2}^{T}(J^{\ast}-(1-\gamma)V^{\ast}(s_{t}))\leq
T(1-\gamma)\text{sp}(v^{\ast}),$

where the first inequality follows from optimism (Lemma 4), and the second
inequality uses Lemma 1 that relates $J^{\ast}$ to $(1-\gamma)V^{\ast}$.

#### Bounding term $\bm{(b)}$

Note that $V_{t}(s)$ is decreasing in $t$ for any fixed $s\in\mathcal{S}$, and
the most it can decrease is $\frac{1}{1-\gamma}$. Thus, term $(b)$ is bounded
by

$\displaystyle\sum_{t=2}^{T}(V_{t-1}(s_{t+1})-V_{t}(s_{t}))$
$\displaystyle\leq\frac{1}{1-\gamma}+\sum_{t=2}^{T}(V_{t-1}(s_{t+1})-V_{t+1}(s_{t+1}))$
$\displaystyle\leq\frac{1}{1-\gamma}+\sum_{s\in\mathcal{S}}\sum_{t=2}^{T}(V_{t-1}(s)-V_{t+1}(s))\leq\frac{2S}{1-\gamma}.$

The bound above is polynomial in $S$, the size of the state space, which is
undesirable in the linear MDP setting where $S$ can be arbitrarily large. The
main challenge of this paper, as we will see in the later section, is
sidestepping this issue for linear MDPs.

#### Bounding term $\bm{(c)}$

Term $(c)$ is the sum of a martingale difference sequence where each term is
bounded by $\text{sp}(v^{\ast})$. Hence, by the Azuma-Hoeffding inequality,
with probability at least $1-\delta$, term $(c)$ is bounded by
$\text{sp}(v^{\ast})\sqrt{2T\log\frac{1}{\delta}}$. Note that without
clipping, each term of the martingale difference sequence can only be bounded
by $\frac{1}{1-\gamma}$ leading to a bound of
$\widetilde{\mathcal{O}}(\frac{1}{1-\gamma}\sqrt{T})$, which is too loose for
achieving a regret bound of $\widetilde{\mathcal{O}}(\sqrt{T})$.

#### Bounding term $\bm{(d)}$

We can bound the sum of the bonus terms $(d)$ by

$\beta\sum_{t=2}^{T}\sqrt{1/N_{t-1}(s_{t},a_{t})}\leq\beta\sum_{s\in\mathcal{S},a\in\mathcal{A}}\sum_{n=1}^{N_{T}(s,a)}\sqrt{\frac{1}{n}}\leq
2c\cdot\text{sp}(v^{\ast})\sqrt{S^{2}AT\log(SAT/\delta)},$

where the last inequality holds because $\sum_{s,a}N_{T}(s,a)=T$ and the left-
hand side of the last inequality is maximized when $N_{T}(s,a)=T/SA$ for all
$s,a$.

Combining the above, and rescaling $\delta$, it follows that with probability
at least $1-\delta$, we have

$R_{T}\leq\mathcal{O}\left(T(1-\gamma)\text{sp}(v^{\ast})+\frac{S}{1-\gamma}+\text{sp}(v^{\ast})\sqrt{T\log(1/\delta)}+\text{sp}(v^{\ast})\sqrt{S^{2}AT\log(SAT/\delta)}\right).$

Choosing $\gamma$ such that $1-\gamma=\sqrt{1/T}$, we get

$R_{T}\leq\mathcal{O}\left(\text{sp}(v^{\ast})\sqrt{S^{2}AT\log(SAT/\delta)}\right).$

##  4 Linear MDP setting

In this section, we apply the key ideas developed from the previous section to
the linear MDP setting. The linear MDP setting is defined as follows.

######  Assumption B (Linear MDP [17]).

We assume that the transition and the reward functions can be expressed as a
linear function of a known $d$-dimensional feature map
$\bm{\varphi}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}^{d}$ such that
for any $(s,a)\in\mathcal{S}\times\mathcal{A}$, we have

$r(s,a)=\langle\bm{\varphi}(s,a),\bm{\theta}\rangle,\quad
P(s^{\prime}|s,a)=\langle\bm{\varphi}(s,a),\bm{\mu}(s^{\prime})\rangle$

where $\bm{\mu}(s^{\prime})=(\mu_{1}(s^{\prime}),\dots,\mu_{d}(s^{\prime}))$
for $s^{\prime}\in\mathcal{S}$ is a vector of $d$ unknown (signed) measures on
$\mathcal{S}$ and $\bm{\theta}\in\mathbb{R}^{d}$ is a known parameter for the
reward function.

As is commonly done in works on linear MDPs[17], we further assume, without
loss of generality (see [27] for justification), the following boundedness
conditions:

$\|\bm{\varphi}(s,a)\|_{2}\leq 1~{}\text{for
all}~{}(s,a)\in\mathcal{S}\times\mathcal{A},\quad\|\bm{\theta}\|_{2}\leq\sqrt{d},\quad\|\bm{\mu}(\mathcal{S})\|_{2}\leq\sqrt{d}.$
(1)

Input: Discounting factor $\gamma\in(0,1)$, regularization constant
$\lambda>0$, span $H$, bonus factor $\beta$.

Initialize: $t\leftarrow 1$, $k\leftarrow 1$, $t_{k}\leftarrow 1$,
$\Lambda_{1}\leftarrow\lambda I$, $\bar{\Lambda}_{0}\leftarrow\lambda I$,
$V_{1}(\cdot)\leftarrow\frac{1}{1-\gamma}$,
$Q_{1}(\cdot,\cdot)\leftarrow\frac{1}{1-\gamma}$.

1 Receive state $s_{1}$. Initialize history:
$\mathcal{H}_{1}\leftarrow\\{s_{1}\\}$.

2 for  _time step $t=1,\dots,T$_ do

3 Take action $a_{t}=\operatorname*{argmax}_{a}Q_{t}(s_{t},a)$. Receive reward
$r(s_{t},a_{t})$. Receive next state $s_{t+1}$.

4
$\bm{w}_{t}\leftarrow\Lambda_{k}^{-1}\sum_{\tau=1}^{t_{k}-1}\bm{\varphi}(s_{\tau},a_{\tau})(V_{t}(s_{\tau+1})-\min_{s^{\prime}}V_{t}(s^{\prime}))$.

5
$\widetilde{Q}_{t+1}(\cdot,\cdot)\leftarrow\left(r(\cdot,\cdot)+\gamma(\langle\bm{\varphi}(\cdot,\cdot),\bm{w}_{t}\rangle+\min_{s^{\prime}}V_{t}(s^{\prime})+\beta\|\bm{\varphi}(\cdot,\cdot)\|_{\Lambda_{k}^{-1}})\right)\wedge\frac{1}{1-\gamma}$.

6 $\widetilde{V}_{t+1}(\cdot)\leftarrow\max_{a}\widetilde{Q}_{t+1}(\cdot,a)$.

$V_{t+1}(\cdot)\leftarrow\widetilde{V}_{t+1}(\cdot)\wedge(\min_{s^{\prime}}\widetilde{V}_{t+1}(s^{\prime})+H)$.
// Clipping oracle

7
$Q_{t+1}(\cdot,\cdot)\leftarrow\max_{\tau\in[t_{k}:t]}\widetilde{Q}_{\tau+1}(\cdot,\cdot)$.

8
$\bar{\Lambda}_{t}\leftarrow\bar{\Lambda}_{t-1}+\bm{\varphi}(s_{t},a_{t})\bm{\varphi}(s_{t},a_{t})^{T}$.

9 if  _$2\det(\Lambda_{k}) <\det(\bar{\Lambda}_{t})$_ then

10 $k\leftarrow k+1$, $t_{k}\leftarrow t+1$.

11 $\Lambda_{k}\leftarrow\bar{\Lambda}_{t}$.

12

13

Algorithm 2 $\gamma$-LSCVI-UCB for linear MDP setting with clipping oracle

As discussed by [17], although the transition model $P$ is linear in the
$d$-dimensional feature mapping $\bm{\varphi}$, $P$ still has $|\mathcal{S}|$
degrees of freedom as the measure $\bm{\mu}$ is unknown, making the estimation
of the model $P$ difficult. For sample efficient learning, we rely on the fact
that $Pv(s,a)$ is linear in $\bm{\varphi}(s,a)$ for any function
$v:\mathcal{S}\rightarrow\mathbb{R}$ so that
$Pv(s,a)=\langle\bm{\varphi}(s,a),\bm{w}^{\ast}_{v}\rangle$ for some
$\bm{w}^{\ast}_{v}$, since

$Pv(s,a)\coloneqq\int_{s^{\prime}\in\mathcal{S}}v(s^{\prime})P(ds^{\prime}|s,a)=\int_{s^{\prime}\in\mathcal{S}}v(s^{\prime})\langle\bm{\varphi}(s,a),\bm{\mu}(ds^{\prime})\rangle=\langle\bm{\varphi}(s,a),\int_{s^{\prime}\in\mathcal{S}}v(s^{\prime})\bm{\mu}(ds^{\prime})\rangle.$

#### Challenges

Naively adapting the algorithm design and analysis for the tabular setting to
the linear MDP setting will give a regret bound polynomial in $S$, the size of
the state space, when bounding
$\sum_{t=1}^{T}(V_{t-1}(s_{t+1})-V_{t}(s_{t}))$. Also, algorithmically making
the state value function monotonically decrease in $t$ by taking minimum with
the previous estimate every iteration, as is done in the tabular setting for
the telescoping sum argument, will make the covering number of the function
class for the value function exponential in either $T$ or $S$ [12]. A major
challenge in algorithm design and analysis is to sidestep these issues.

###  4.1 Algorithm with clipping oracle

Unlike the tabular case, a naive clipping is computationally inefficient due
to large state space since the clipping requires finding the minimum of a
value function. In this section, we present an algorithm that assumes a
clipping oracle that can find the minimum of a value function
$V:\mathcal{S}\rightarrow\mathbb{R}$. We will present an algorithm that uses a
computationally efficient clipping operator in the next section.

Our algorithm discounted least-squares clipped value iteration with upper
confidence bound ($\gamma$-LSCVI-UCB) adapts LSVI-UCB [17] developed for the
episodic setting to the discounted setting. A key difference from LSVI-UCB is
that we clip the state value function estimates to constrain the span, which
is crucial for statistical efficiency that saves a factor of $1/(1-\gamma)$ in
the regret bound. Also, we use the value target
$V_{t}-\min_{s^{\prime}}V_{t}(s^{\prime})$ instead of $V_{t}$ for the ridge
regression (Line 2) to get a bound on $\|\bm{w}_{t}\|_{2}$ that scales with
$\text{sp}(v^{\ast})$ instead of $1/(1-\gamma)$ necessary for achieving
$\widetilde{\mathcal{O}}(\sqrt{T})$ regret.

Recall that in tabular setting, we make the state value function $V_{t}$
monotonically decreasing for bounding
$\sum_{t}V_{t-1}(s_{t})-V_{t+1}(s_{t+1})$ with telescoping sum. As discussed
previously, in the linear MDP setting, the log covering number of the function
class for the value function will scale with $T$ if we make $V_{t}$
monotonically decreasing by taking minimum with previous value functions,
making regret bound vacuous. To sidestep issue, we take a different analysis
path that bounds difference of action values
$\sum_{t}Q_{t+1}(s_{t+1},a_{t+1})-Q_{t+1}(s_{t},a_{t})$. Instead of using
telescoping sum by making $Q_{t}$ monotonically decreasing, which can only
give $SA/(1-\gamma)$ bound undesirable for the linear MDP setting, we make
$Q_{t}$ monotonically increasing. To avoid the covering number issue, we
construct $Q_{t}$ by max-pooling action value function estimates
$\widetilde{Q}_{t}$ (Line 2). To avoid vacuous regret bound due to increasing
$Q_{t}$, we use the rarely-switching covariance matrix trick (Line 2) [26]
such that $\widetilde{Q}_{t}$ used for max-pooling become better estimates
every episode. The algorithm has the following guarantee.

######  Theorem 5.

Under Assumptions A and B, running Algorithm 2 with inputs
$\gamma=1-\sqrt{\log(T)/T}$, $\lambda=1$, $H=2\cdot\text{sp}(v^{\ast})$ and
$\beta=2c_{\beta}\cdot\text{sp}(v^{\ast})d\sqrt{\log(dT/\delta)}$ guarantees
with probability at least $1-\delta$,

$R_{T}\leq\mathcal{O}(\text{sp}(v^{\ast})\sqrt{d^{3}T\log(dT/\delta)}).$

The constant $c_{\beta}$ is an absolute constant defined in Lemma 19. Adapting
to the tabular setting by letting $d=SA$ and
$\bm{\varphi}(s,a)=\bm{e}_{(s,a)}$ [17], the regret bound becomes
$\mathcal{O}(\text{sp}(v^{\ast})\sqrt{S^{3}A^{3}T\log(SAT/\delta)})$. This is
a sharper bound than the best existing bound with model-free algorithm for the
tabular setting. See Appendix F for a detailed comparison with previous model-
free algorithms for the tabular setting. We expect careful analysis of the
variance of the value estimate [12] may improve our regret by a factor of
$\sqrt{d}$. We leave the improvement to future work.

In the remainder of the section, we provide a sketch of the proof of the
regret bound given in Theorem 5. We first show that the value iteration step
in Line 2 with the bonus term
$\beta\|\bm{\phi}(\cdot,\cdot)\|_{\Lambda_{k}^{-1}}$ with appropriately chosen
$\beta$ ensures the value function estimates $V_{t}$ and $Q_{t}$ to be
optimistic estimates of $V^{\ast}$ and $Q^{\ast}$ respectively. The argument
is based on the following concentration inequality for the regression
coefficients.

######  Lemma 6 (Informal).

Under the linear MDP setting, with probability at least $1-\delta$, we have
for all $t=1,\dots,T$ and for all $(s,a)\in\mathcal{S}\times\mathcal{A}$ that

$|\langle\bm{\varphi}(s,a),\bm{w}_{t}\rangle-\langle\bm{\varphi}(s,a),\bm{w}_{t}^{\ast}\rangle|\leq\beta\|\bm{\varphi}(s,a)\|_{\Lambda_{t}^{-1}}$

where $\bm{w}_{t}^{\ast}$ is the parameter such that
$\langle\bm{\varphi}(\cdot,\cdot),\bm{w}_{t}^{\ast}\rangle=P(V_{t}-\min_{s^{\prime}}V_{t}(s^{\prime}))(\cdot,\cdot)$
and $\beta=\widetilde{\mathcal{O}}(Hd)$.

See Lemma 19 in Appendix C.1 for a formal statement with proof. With the
concentration inequality, we can show the following optimism result. See
Appendix C.2 for an induction-based proof.

######  Lemma 7 (Optimism).

Under the linear MDP setting, running Algorithm 2 with input
$H=2\cdot\text{sp}(v^{\ast})$ guarantees with probability at least $1-\delta$
that for all $t=1,\dots,T$ and for all $(s,a)\in\mathcal{S}\times\mathcal{A}$,

$V_{t}(s)\geq V^{\ast}(s),\quad Q_{t}(s,a)\geq\widetilde{Q}_{t}(s,a)\geq
Q^{\ast}(s,a).$

Now, we prove the regret bound. Let $t$ be a time step in episode $k$ and
$\tau_{t}(s,a)=\operatorname*{argmax}_{\tau\in[t_{k}:t]}\widetilde{Q}_{\tau+1}(s,a)$
such that $Q_{t+1}(s,a)=\widetilde{Q}_{\tau_{t}(s,a)+1}(s,a)$. Note that
$\tau_{t}(s,a)\leq t$. By the definition of $\widetilde{Q}_{t}(\cdot,\cdot)$,
we have for all time step $t$ in episode $k$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$ that

$\displaystyle r(s,a)$ $\displaystyle\geq
Q_{t+1}(s,a)-\gamma(\langle\bm{\varphi}(s,a),\bm{w}_{\tau_{t}(s,a)}\rangle+\min_{s^{\prime}}V_{\tau_{t}(s,a)}(s^{\prime})-\beta\|\bm{\varphi}(s,a)\|_{\Lambda_{k}^{-1}})$
$\displaystyle\geq Q_{t+1}(s,a)-\gamma
PV_{\tau_{t}(s,a)}(s,a)-4\gamma\beta\|\bm{\varphi}(s,a)\|_{\Lambda_{t}^{-1}}$

where the second inequality uses the concentration bound for the regression
coefficients in Lemma 6 and the fact that $\tau_{t}(s,a)$ is a time step in
episode $k$. It also uses $\|\bm{x}\|_{\Lambda_{k}^{-1}}\leq
2\|\bm{x}\|_{\Lambda_{t}^{-1}}$ due to the episode starting condition and
Lemma 25. Hence,

$\displaystyle R_{T}$ $\displaystyle=\sum_{t=1}^{T}(J^{\ast}-r(s_{t},a_{t}))$
$\displaystyle\leq\sum_{t=1}^{T}(J^{\ast}-Q_{t+1}(s_{t},a_{t})+\gamma
PV_{\tau_{t}(s_{t},a_{t})}(s_{t},a_{t})+4\beta\|\bm{\varphi}(s_{t},a_{t})\|_{\Lambda_{t}^{-1}})$
$\displaystyle=\underbrace{\sum_{t=1}^{T}(J^{\ast}-(1-\gamma)V_{\tau_{t}(s_{t},a_{t})}(s_{t+1}))}_{(a)}+\gamma\underbrace{\sum_{t=1}^{T}(V_{\tau_{t}(s_{t},a_{t})}(s_{t+1})-Q_{t+1}(s_{t},a_{t}))}_{(b)}$
$\displaystyle\hskip
28.45274pt+\gamma\underbrace{\sum_{t=1}^{T}(PV_{\tau_{t}(s_{t},a_{t})}(s_{t},a_{t})-V_{\tau_{t}(s_{t},a_{t})}(s_{t+1}))}_{(c)}+4\underbrace{\beta\sum_{t=1}^{T}\|\bm{\varphi}(s_{t},a_{t})\|_{\Lambda_{t}^{-1}}}_{(d)}$

where the first inequality uses the bound for $r(s_{t},a_{t})$. With the same
argument as in the tabular case, the term $(a)$, the approximation error of
discounted setting, can be bounded by $T(1-\gamma)\text{sp}(v^{\ast})$ due to
the optimism $V_{\tau_{t}(s_{t},a_{t})}(s_{t+1})\geq V^{\ast}(s_{t+1})$. Term
$(d)$, the sum of bonus terms, can be bounded by
$\mathcal{O}(\beta\sqrt{dT\log T})$ using Cauchy-Schwartz and Lemma 24. The
term $(c)$ is a sum of a martingale difference sequence since
$\tau_{t}(s_{t},a_{t})\leq t$ and can be bounded by
$\mathcal{O}(\text{sp}(v^{\ast})\sqrt{T\log(1/\delta)})$ using
$\text{sp}(V_{t+1})\leq 2\cdot\text{sp}(v^{\ast})$ by the clipping step in
Line 2. To bound term $(b)$ note that

$\displaystyle V_{\tau_{t}(s_{t},a_{t})}(s_{t+1})$
$\displaystyle\leq\widetilde{V}_{\tau_{t}(s_{t},a_{t})}(s_{t+1})$
$\displaystyle=\max_{a}\widetilde{Q}_{\tau_{t}(s_{t},a_{t})}(s_{t+1},a)\leq\max_{a}Q_{t+1}(s_{t+1},a)=Q_{t+1}(s_{t+1},a_{t+1})$

where the second inequality uses the fact that $Q_{t+1}$ is a maximum over all
$\widetilde{Q}_{\tau}$ with $\tau\in[t_{k}:t]$ and the last inequality is by
the fact that algorithm chooses $a_{t+1}$ that maximizes
$Q_{t+1}(s_{t+1},\cdot)$. Hence,

$\displaystyle\sum_{t=1}^{T}(V_{\tau_{t}(s_{t},a_{t})}(s_{t+1})-Q_{t+1}(s_{t},a_{t}))$
$\displaystyle\leq\sum_{t=1}^{T}(Q_{t+1}(s_{t+1},a_{t+1})-Q_{t+1}(s_{t},a_{t}))$
$\displaystyle\leq\sum_{t=1}^{T}(Q_{t}(s_{t},a_{t})-Q_{t+1}(s_{t},a_{t}))+\mathcal{O}(1/(1-\gamma))$
$\displaystyle\leq\mathcal{O}(K/(1-\gamma))\leq\mathcal{O}(d\log(T)/(1-\gamma)).$

where we use the notation $K$ to denote the total number of episodes. The
second inequality uses the fact that $Q_{t}\leq\frac{1}{1-\gamma}$ and the
third inequality uses the monotonicity $Q_{t}\leq Q_{t+1}$ whenever both $t-1$
and $t$ are in the same episode. There can be at most $K$ time steps where
$t-1$ and $t$ are not in the same episode, in which cases we can use a crude
bound of $\mathcal{O}(K/(1-\gamma))$. Since the episode is advanced when the
determinant of the covariance matrix doubles, it can be shown that
$K\leq\mathcal{O}(d\log(T))$ (Lemma 26), which is used in the last inequality.
Combining all the bounds, and using
$\beta=\mathcal{O}(\text{sp}(v^{\ast})d\sqrt{\log(dT/\delta)}$, we get

$R_{T}\leq\mathcal{O}\left(T(1-\gamma)\text{sp}(v^{\ast})+\frac{d}{1-\gamma}\log(T)+\text{sp}(v^{\ast})\sqrt{T\log(1/\delta)}+\text{sp}(v^{\ast})\sqrt{d^{3}T\log(dT/\delta)}\right).$

Setting $\gamma=1-\frac{\sqrt{\log T}}{\sqrt{T}}$, we get

$R_{T}\leq\mathcal{O}\left(\text{sp}(v^{\ast})\sqrt{d^{3}T\log(dT/\delta)}\right).$

###  4.2 Algorithm with computationally efficient clipping operator

As discussed previously, the clipping oracle is computationally inefficient
for large state space. For computationally efficient algorithm, we introduce a
clipping operator that only requires finding the minimum over a finite set of
inputs. The clipping operator denoted by $\textsc{Clip}_{A}(f,H)$ takes in as
inputs the function $f:\mathcal{X}\rightarrow\mathbb{R}$ to clip, a finite set
of inputs $A\subseteq\mathcal{X}$ and the target span $H>0$, and returns a
clipped function. The clipping operator is defined as follows.

######  Definition 8 (Clipping operator).

Let $\mathcal{X}$ be a set and let $f:\mathcal{X}\rightarrow\mathbb{R}$ be a
real-valued function. For a finite set $A\subseteq\mathcal{X}$ and a positive
number $H>0$, define an operator $\textsc{Clip}_{A}$ by

$\textsc{Clip}_{A}(f,H)(x)=(f(x)\vee\min_{y\in A}f(y))\wedge(\min_{y\in
A}f(y)+H).$

By design, the clipped function $\textsc{Clip}_{A}(f,H)$ is in the range
$[\min_{y\in A}f(y),\min_{y\in A}f(y)+H]$. Note that even when the size of the
space $\mathcal{X}$ is large or even infinite, evaluating
$\textsc{Clip}_{A}(f,H)(x)$ for any $x\in\mathcal{X}$ can be done by
evaluating $f(y)$ only at $y\in A\cup\\{x\\}$. Also, evaluating the global
minimum of a clipped function $\textsc{Clip}_{A}(f,H)$ requires evaluating
$f(y)$ at $y\in A$ only. For other properties of the the clipping operator we
use in the analysis, see Appendix A.

Following is a computationally efficient algorithm for the linear MDP setting
using the efficient clipping operator. A key difference from the algorithm
from the previous section is that the algorithm stores all the states visited
up to time step $t$ in $\mathcal{H}_{t}=\\{s_{1},\dots,s_{t}\\}$. At each time
step, when a new state $s_{t+1}$ is received, the algorithm recomputes all the
value functions in the current episode using $\mathcal{H}_{t+1}$ as the set of
inputs for clipping.

Input: Discounting factor $\gamma\in(0,1)$, regularization constant
$\lambda>0$, span $H$, bonus factor $\beta$.

Initialize: $t\leftarrow 1$, $k\leftarrow 1$, $t_{k}\leftarrow 1$,
$\Lambda_{1}\leftarrow\lambda I$, $\bar{\Lambda}_{0}\leftarrow\lambda I$,
$V_{1}^{(u)}(\cdot)\leftarrow\frac{1}{1-\gamma},\forall u\in[T]$,
$Q_{1}(\cdot,\cdot)\leftarrow\frac{1}{1-\gamma}$.

1 Receive state $s_{1}$. Initialize history:
$\mathcal{H}_{1}\leftarrow\\{s_{1}\\}$.

2 for  _time step $t=1,\dots,T$_ do

3 Take action $a_{t}=\operatorname*{argmax}_{a}Q_{t}(s_{t},a)$. Receive reward
$r(s_{t},a_{t})$. Receive next state $s_{t+1}$.

4 $\mathcal{H}_{t+1}\leftarrow\mathcal{H}_{t}\cup\\{s_{t+1}\\}$.

// Recompute all value functions using $\mathcal{H}_{t+1}$ for clipping.

5 for  _$u=1,\dots,t$_ do

6
$\bm{w}^{(t+1)}_{u}\leftarrow\Lambda_{k}^{-1}\sum_{\tau=1}^{t_{k}-1}\bm{\varphi}(s_{\tau},a_{\tau})(V^{(t+1)}_{u}(s_{\tau+1})-\min_{s^{\prime}}V^{(t+1)}_{u}(s^{\prime}))$.

7
$\widetilde{Q}^{(t+1)}_{u+1}(\cdot,\cdot)\leftarrow\left(r(\cdot,\cdot)+\gamma(\langle\bm{\varphi}(\cdot,\cdot),\bm{w}^{(t+1)}_{u}\rangle+\min_{s^{\prime}}V^{(t+1)}_{u}(s^{\prime})+\beta\|\bm{\varphi}(\cdot,\cdot)\|_{\Lambda_{k}^{-1}})\right)\wedge\frac{1}{1-\gamma}$.

8
$\widetilde{V}^{(t+1)}_{u+1}(\cdot)\leftarrow\max_{a}\widetilde{Q}^{(t+1)}_{u+1}(\cdot,a)$.

9
$V^{(t+1)}_{u+1}\leftarrow\textsc{Clip}_{\mathcal{H}_{t+1}}(\widetilde{V}^{(t+1)}_{u+1},H)$.

10

11
$Q_{t+1}(\cdot,\cdot)\leftarrow\max_{\tau\in[t_{k}:t]}\widetilde{Q}^{(t+1)}_{\tau+1}(\cdot,\cdot)$.

12
$\bar{\Lambda}_{t}\leftarrow\bar{\Lambda}_{t-1}+\bm{\varphi}(s_{t},a_{t})\bm{\varphi}(s_{t},a_{t})^{T}$.

13 if  _$2\det(\Lambda_{k}) <\det(\bar{\Lambda}_{t})$_ then

14 $k\leftarrow k+1$, $t_{k}\leftarrow t+1$.

15 $\Lambda_{k}\leftarrow\bar{\Lambda}_{t}$.

16

17

Algorithm 3 $\gamma$-LSCVI-UCB for linear MDP setting with efficient clipping
operator

It can be shown that the computationally efficient version of our algorithm
has the same regret bound guarantee as stated in the following theorem. See
Appendix D for a proof.

######  Theorem 9.

Under Assumptions A and B, running Algorithm 3 with inputs
$\gamma=1-\sqrt{\log(T)/T}$, $\lambda=1$, $H=2\cdot\text{sp}(v^{\ast})$ and
$\beta=2c_{\beta}\cdot\text{sp}(v^{\ast})d\sqrt{\log(dT/\delta)}$ guarantees
with probability at least $1-\delta$,

$R_{T}\leq\mathcal{O}(\text{sp}(v^{\ast})\sqrt{d^{3}T\log(\text{sp}(v^{\ast})dT/\delta)}).$

The constant $c_{\beta}$ is an absolute constant defined in Lemma 21.

##  5 Conclusion

In this paper, we propose the first computationally efficient algorithm with
order optimal regret bound for infinite-horizon average-reward linear MDPs.
Our algorithm approximates the average-reward setting by the discounted
setting with a carefully tuned discounting factor. A key technique that allows
for order optimal regret bound is bounding the span of the value function in
each value iteration step via clipping. An interesting future work would be to
generalize these ideas to a general function approximation setting.

##  6 Acknowledgements

We acknowledge the support of NSF via grant IIS-2007055.

## References

## References

  * [1] Yasin Abbasi-Yadkori, David Pal and Csaba Szepesvari  “Online-to-confidence-set conversions and application to sparse stochastic bandits”  In _Artificial Intelligence and Statistics_ , 2012, pp. 1–9  PMLR
  * [2] Yasin Abbasi-Yadkori, Dávid Pál and Csaba Szepesvári  “Improved algorithms for linear stochastic bandits”  In _Advances in neural information processing systems_ 24, 2011
  * [3] Peter Auer, Thomas Jaksch and Ronald Ortner  “Near-optimal regret bounds for reinforcement learning”  In _Advances in neural information processing systems_ 21, 2008
  * [4] 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_ , 2020, pp. 463–474  PMLR
  * [5] Mohammad Gheshlaghi Azar, Ian Osband and Rémi Munos  “Minimax regret bounds for reinforcement learning”  In _International conference on machine learning_ , 2017, pp. 263–272  PMLR
  * [6] Peter Bartlett and Ambuj Tewari  “REGAL: a regularization based algorithm for reinforcement learning in weakly communicating MDPs”  In _Uncertainty in Artificial Intelligence: Proceedings of the 25th Conference_ , 2009, pp. 35–42  AUAI Press
  * [7] Liyu Chen, Rahul Jain and Haipeng Luo  “Learning infinite-horizon average-reward Markov decision process with constraints”  In _International Conference on Machine Learning_ , 2022, pp. 3246–3270  PMLR
  * [8] Ronan Fruit, Matteo Pirotta and Alessandro Lazaric  “Improved analysis of ucrl2 with empirical bernstein inequality”  In _arXiv preprint arXiv:2007.05456_ , 2020
  * [9] Ronan Fruit, Matteo Pirotta, Alessandro Lazaric and Ronald Ortner  “Efficient bias-span-constrained exploration-exploitation in reinforcement learning”  In _International Conference on Machine Learning_ , 2018, pp. 1578–1586  PMLR
  * [10] Arnob Ghosh, Xingyu Zhou and Ness Shroff  “Achieving sub-linear regret in infinite horizon average reward constrained mdp with linear function approximation”  In _The Eleventh International Conference on Learning Representations_ , 2023
  * [11] Ilaria Giannoccaro and Pierpaolo Pontrandolfo  “Inventory management in supply chains: a reinforcement learning approach”  In _International Journal of Production Economics_ 78.2 Elsevier, 2002, pp. 153–161
  * [12] Jiafan He, Heyang Zhao, Dongruo Zhou and Quanquan Gu  “Nearly minimax optimal reinforcement learning for linear markov decision processes”  In _International Conference on Machine Learning_ , 2023, pp. 12790–12822  PMLR
  * [13] Jiafan He, Dongruo Zhou and Quanquan Gu  “Nearly minimax optimal reinforcement learning for discounted MDPs”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 22288–22300
  * [14] Jianliang He, Han Zhong and Zhuoran Yang  “Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation”  In _The Twelfth International Conference on Learning Representations_ , 2024
  * [15] Thomas Jaksch, Ronald Ortner and Peter Auer  “Near-optimal Regret Bounds for Reinforcement Learning”  In _Journal of Machine Learning Research_ 11, 2010, pp. 1563–1600
  * [16] Xiang Ji and Gen Li  “Regret-optimal model-free reinforcement learning for discounted mdps with short burn-in time”  In _Advances in Neural Information Processing Systems_ 36, 2024
  * [17] Chi Jin, Zhuoran Yang, Zhaoran Wang and Michael I Jordan  “Provably efficient reinforcement learning with linear function approximation”  In _Conference on learning theory_ , 2020, pp. 2137–2143  PMLR
  * [18] Yujia Jin and Aaron Sidford  “Towards tight bounds on the sample complexity of average-reward MDPs”  In _International Conference on Machine Learning_ , 2021, pp. 5055–5064  PMLR
  * [19] Shuang Liu and Hao Su  “Regret bounds for discounted mdps”  In _arXiv preprint arXiv:2002.05138_ , 2020
  * [20] Zoubir Mammeri  “Reinforcement learning based routing in networks: Review and classification of approaches”  In _Ieee Access_ 7 IEEE, 2019, pp. 55916–55950
  * [21] Ronald Ortner  “Regret bounds for reinforcement learning via markov chain concentration”  In _Journal of Artificial Intelligence Research_ 67, 2020, pp. 115–128
  * [22] Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar and Rahul Jain  “Learning unknown markov decision processes: A thompson sampling approach”  In _Advances in neural information processing systems_ 30, 2017
  * [23] Martin L Puterman  “Markov decision processes: discrete stochastic dynamic programming”  John Wiley & Sons, 2014
  * [24] Jinghan Wang, Mengdi Wang and Lin F Yang  “Near sample-optimal reduction-based policy learning for average reward mdp”  In _arXiv preprint arXiv:2212.00603_ , 2022
  * [25] Shengbo Wang, Jose Blanchet and Peter Glynn  “Optimal Sample Complexity for Average Reward Markov Decision Processes”  In _arXiv preprint arXiv:2310.08833_ , 2023
  * [26] Tianhao Wang, Dongruo Zhou and Quanquan Gu  “Provably efficient reinforcement learning with linear function approximation under adaptivity constraints”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 13524–13536
  * [27] Chen-Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo and Rahul Jain  “Learning infinite-horizon average-reward mdps with linear function approximation”  In _International Conference on Artificial Intelligence and Statistics_ , 2021, pp. 3007–3015  PMLR
  * [28] Chen-Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma and Rahul Jain  “Model-free reinforcement learning in infinite-horizon average-reward markov decision processes”  In _International conference on machine learning_ , 2020, pp. 10170–10180  PMLR
  * [29] Yue Wu, Dongruo Zhou and Quanquan Gu  “Nearly minimax optimal regret for learning infinite-horizon average-reward mdps with linear function approximation”  In _International Conference on Artificial Intelligence and Statistics_ , 2022, pp. 3883–3913  PMLR
  * [30] Zihan Zhang and Xiangyang Ji  “Regret minimization for reinforcement learning by evaluating the optimal bias function”  In _Advances in Neural Information Processing Systems_ 32, 2019
  * [31] Zihan Zhang and Qiaomin Xie  “Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes”  In _The Thirty Sixth Annual Conference on Learning Theory_ , 2023, pp. 5476–5477  PMLR
  * [32] Matthew Zurek and Yudong Chen  “Span-Based Optimal Sample Complexity for Average Reward MDPs”  In _arXiv preprint arXiv:2311.13469_ , 2023

##  Appendix A Clipping operator

######  Lemma 10 (Properties of clipping operator).

Let $f,g:\mathcal{X}\rightarrow\mathbb{R}$. Then, for all finite sets
$A,B\subseteq\mathcal{X}$ and all $H>0$, the following properties hold.

  1. (i)

If $\text{sp}(f)\leq H$ then $\textsc{Clip}_{\mathcal{X}}(f,H)=f$.

  2. (ii)

$\text{sp}(\textsc{Clip}_{A}(f,H))\leq H$.

  3. (iii)

$\textsc{Clip}_{A}(f,H)(x)\leq f(x)$ for all $x\in A$.

  4. (iv)

If $A\subseteq B$ then,
$\textsc{Clip}_{A}(f,H)(x)\geq\textsc{Clip}_{B}(f,H)(x)$ for all
$x\in\mathcal{X}$.

  5. (v)

If $f(x)\geq g(x)$ for all $x\in\mathcal{X}$, then
$\textsc{Clip}_{A}(f,H)(x)\geq\textsc{Clip}_{A}(g,H)(x)$ for all
$x\in\mathcal{X}$.

###### Proof.

Recall that the clipping operator is defined as

$\textsc{Clip}_{A}(f,H)(x)=(f(x)\vee\min_{y\in A}f(y))\wedge(\min_{y\in
A}f(y)+H).$

The property (i) can be seen directly from the definition. Suppose
$\text{sp}(f)\leq H$. Then, we have
$f(x)\in[\min_{y\in\mathcal{X}}f(y),\min_{y\in\mathcal{X}}f(y)+H]$. It follows
that for any $x\in\mathcal{X}$, we have

$\displaystyle\textsc{Clip}_{\mathcal{X}}(f,H)(x)$
$\displaystyle=(f(x)\vee\min_{y\in\mathcal{X}}f(y))\wedge(\min_{y\in\mathcal{X}}f(y)+H)$
$\displaystyle=f(x)\wedge(\min_{y\in\mathcal{X}}f(y)+H)$ $\displaystyle=f(x).$

The property (ii), follows from the fact that for any $x\in\mathcal{X}$, we
have $\textsc{Clip}_{A}(f,H)(x)\in[\min_{y\in A}f(y),\min_{y\in A}f(y)+H]$.

To show property (iii), fix any $x\in A$. If $f(x)\in[\min_{y\in
A}f(y),\min_{y\in A}f(y)+H]$, then $\textsc{Clip}_{A}(f,H)(x)=f(x)$ and the
property holds. On the other hand, if $x\notin[\min_{y\in A}f(y),\min_{y\in
A}f(y)+H]$, then it must be that $f(x)>\min_{y\in A}f(y)+H$ since
$f(x)\geq\min_{y\in A}f(y)$ due to the fact that $x\in A$. In this case,
$\textsc{Clip}_{A}(f,H)(x)=\min_{y\in A}f(y)+H\leq f(x)$. In both cases, we
have $\textsc{Clip}_{A}(f,H)(x)\leq f(x)$ as desired.

To show Property (iv), fix $x\in\mathcal{X}$ and let $A\subseteq B$. The
containment $A\subseteq B$ implies $\min_{y\in A}f(y)\geq\min_{y\in B}f(y)$.
It follows that

$\displaystyle\textsc{Clip}_{A}(f,H)(x)$ $\displaystyle=(f(x)\vee\min_{y\in
A}f(y))\wedge(\min_{y\in A}f(y)+H)$ $\displaystyle\geq(f(x)\vee\min_{y\in
B}f(y))\wedge(\min_{y\in B}f(y)+H)$ $\displaystyle=\textsc{Clip}_{B}(f,H)(x)$

as desired.

Property (v) follows directly from the definition of the clipping operator. ∎

##  Appendix B Tabular Setting

######  Lemma 11 (Concentration of Scalar-Valued Self-Normalized Processes
[1]).

Let $\\{\varepsilon_{t}\\}_{t=1}^{\infty}$ be a real-valued stochastic process
with corresponding filtration $\\{\mathcal{F}_{t}\\}_{t=0}^{\infty}$. Let
$\varepsilon_{t}|\mathcal{F}_{t-1}$ be zero-mean and $\sigma$-subgaussian. Let
$\\{Z_{t}\\}_{t=0}^{\infty}$ be an $\mathbb{R}$-valued stochastic process
where $Z_{t}\in\mathcal{F}_{t-1}$. Assume $W>0$ is deterministic. Then for any
$\delta>0$, with probability at least $1-\delta$, we have for all $t\geq 0$
that

$\frac{(\sum_{s=1}^{t}Z_{s}\varepsilon_{s})^{2}}{W+\sum_{s=1}^{t}Z_{s}^{2}}\leq
2\sigma^{2}\log\left(\frac{\sqrt{W+\sum_{s=1}^{t}Z_{t}^{2}}}{\delta\sqrt{W}}\right).$

###  B.1 Proof of Lemma 3

Note that the value functions $V_{t}$ defined in the algorithm always lie in
the following function class.

$\mathcal{V}_{\text{tabular}}=\\{v\in\mathbb{R}^{\mathcal{S}}:\text{sp}(v)\leq
2\text{sp}(v^{\ast}),~{}v(s)\in[0,\textstyle\frac{1}{1-\gamma}]~{}\text{for
all}~{}s\in\mathcal{S}\\}.$

We first bound the error for a fixed value function in
$\mathcal{V}_{\text{tabular}}$. Afterward, we will use a covering argument to
get a uniform bound over $\mathcal{V}_{\text{tabular}}$.

######  Lemma 12.

Fix any $V\in\mathcal{V}_{\text{tabular}}$. There exists some constant $C$
such that for any $\delta\in(0,1)$, with probability at least $1-\delta$, we
have:

$|(\widehat{P}_{t}-P)V(s,a)|\leq
C\text{sp}(v^{\ast})\sqrt{\frac{\log(SAT/\delta)}{N_{t}(s,a)}}$

for all $(s,a)\in\mathcal{S}\times\mathcal{A}$ and $t=1,\dots,T$.

###### Proof.

Fix any $(s,a)\in\mathcal{S}\times\mathcal{A}$. By definition, we have:

$(\widehat{P}_{t}-P)V(s,a)=\frac{1}{N_{t}(s,a)}\sum_{\tau=1}^{t}\mathbb{I}\\{s_{\tau}=s,a_{\tau}=a\\}[V(s_{\tau+1})-PV(s,a)].$

Let $\varepsilon_{t}=\mathbb{I}\\{s_{t}=s,a_{t}=a\\}[V(s_{t+1})-PV(s,a)]$,
$Z_{t}=\mathbb{I}\\{s_{t}=s,a_{t}=a\\}$, and $W=1$. Since the range of
$\varepsilon_{t}$ is bounded by $2\text{sp}(v^{\ast})$, it is
$\text{sp}(v^{\ast})$-subgaussian. By Lemma 11, we know for some constant $C$,
with probability at least $1-\frac{\delta}{SA}$, for all $t=1,\dots,T$, we
have

$\displaystyle|(\widehat{P}_{t}-P)V(s,a)|$
$\displaystyle\leq\frac{2\sum_{s=1}^{t}Z_{s}\varepsilon_{s}}{1+\sum_{s=1}^{t}Z_{t}^{2}}$
$\displaystyle\leq
C\text{sp}(v^{\ast})\sqrt{\frac{\log(SA\sqrt{N_{t}(s,a)}/\delta)}{N_{t}(s,a)}}$
$\displaystyle\leq
C\text{sp}(v^{\ast})\sqrt{\frac{\log(SAT/\delta)}{N_{t}(s,a)}}.$

Applying a union bound for all $(s,a)\in\mathcal{S}\times\mathcal{A}$ gives us
the desired inequality.

∎

We use $\mathcal{N_{\epsilon}}$ to denote the $\epsilon$-covering number of
$\mathcal{V}_{\text{tabular}}$ with respect to the distance
$\text{dist}(V,V^{\prime})=\|V-V^{\prime}\|_{\infty}$. Since
$\mathcal{V}_{\text{tabular}}$ is contained in
$\\{v\in\mathbb{R}^{\mathcal{S}}:v(s)\in[0,\frac{1}{1-\gamma}]~{}\text{for
all}~{}s\in\mathcal{S}\\}$, of which $\epsilon$-covering number is bounded by
$(\frac{1}{\epsilon(1-\gamma)})^{|\mathcal{S}|}$, we have

$\log\mathcal{N}_{\epsilon}\leq S\log\frac{1}{\epsilon(1-\gamma)}.$

Finally, we prove the uniform concentration desired.

###### Proof of Lemma 3.

For any $V\in\mathcal{V}$, we know there exists a $\widetilde{V}$ in the
$\epsilon$-covering such that $V=\widetilde{V}+\Delta_{V}$ where
$\sup_{s}|\Delta_{V}(s)|\leq\epsilon$. Thus we have

$|(\widehat{P}_{t}-P)V_{t}(s,a)|\leq|(\widehat{P}_{t}-P)\widetilde{V}(s,a)|+|(\widehat{P}_{t}-P)\Delta_{V}(s,a)|\leq|(\widehat{P}_{t}-P)\widetilde{V}(s,a)|+2\epsilon.$

We then apply Lemma 12 and a union bound to obtain:

$|(\widehat{P}_{t}-P)V_{t}(s,a)|\leq
C\text{sp}(v^{\ast})\sqrt{\frac{\log(SAT\mathcal{N}_{\epsilon}/\delta)}{N_{t}(s,a)}}+2\epsilon\leq
C\text{sp}(v^{\ast})\sqrt{\frac{S\log\frac{SAT}{\delta\epsilon(1-\gamma)}}{N_{t}(s,a)}}+2\epsilon.$

Picking $\epsilon=\frac{1}{\sqrt{T}}$ concludes the proof. ∎

###  B.2 Proof of Lemma 4

###### Proof of Lemma 4.

We prove by induction on $t\geq 1$. The base case $t=1$ is trivial since
Algorithm 1 initializes $V_{1}(\cdot)=\frac{1}{1-\gamma}$,
$Q_{1}(\cdot,\cdot)=\frac{1}{1-\gamma}$. Now, suppose $V_{1},\dots,V_{t}\geq
V^{\ast}$ and $Q_{1},\dots,Q_{t}\geq Q^{\ast}$.

We fist show that $Q_{t+1}(s,a)\geq Q^{\ast}(s,a)$. By the Bellman optimality
equation for the discounted setting, we have for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$ that

$Q^{\ast}(s,a)=r(s,a)+\gamma(PV^{\ast})(s,a).$

Fix any pair $(s,a)\in\mathcal{S}\times\mathcal{A}$. By the definition of
$Q_{t+1}$ in Line 1 of Algorithm 1, we have either $Q_{t+1}(s,a)=Q_{t}(s,a)$
or
$Q_{t+1}(s,a)=r(s,a)+\gamma(\widehat{P}_{t}V_{t})(s,a)+\beta\sqrt{1/N_{t}(s,a)}$.
The former case is done by the induction hypothesis. Suppose
$Q_{t+1}(s,a)=r(s,a)+\gamma(\widehat{P}_{t}V_{t}-PV^{\ast})(s,a)+\beta\sqrt{1/N_{t}(s,a)}$.
Then,

$Q_{t+1}(s,a)-Q^{\ast}(s,a)=\gamma(\widehat{P}_{t}V_{t}-PV^{\ast})(s,a)+\beta\sqrt{1/N_{t}(s,a)}.$

By Lemma 3,

$\displaystyle(\widehat{P}_{t}V_{t}-PV^{\ast})(s,a)$
$\displaystyle=(\widehat{P}_{t}-P)V_{t}(s,a)+P(V_{t}-V^{\ast})(s,a)$
$\displaystyle\geq
P(V_{t}-V^{\ast})(s,a)-C\cdot\text{sp}(v^{\ast})\sqrt{\frac{S\log(SAT/\delta)}{N_{t}(s,a)}}.$

By our choice of the bonus factor $\beta$ and the induction hypothesis, we get

$Q_{t+1}(s,a)-Q^{\ast}(s,a)\geq P(V_{t}-V^{\ast})(s,a)\geq 0.$

Then we show $V_{t+1}(s)\geq V^{\ast}(s)$. By the definition of
$\widetilde{V}_{t+1}$ in Line 1 of Algorithm 1, we either have
$\widetilde{V}_{t+1}(s)=V_{t}(s)$ or
$\widetilde{V}_{t+1}(s)=\max_{a}Q_{t+1}(s,a)$. The former case is done by the
induction hypothesis. Suppose $\widetilde{V}_{t+1}(s)=\max_{a}Q_{t+1}(s,a)$,
then by the optimism of the $Q$ function we just proved, we have

$\widetilde{V}_{t+1}(s)-V^{\ast}(s)=\max_{a}Q_{t+1}(s,a)-Q^{\ast}(s,a_{s}^{\ast})\geq
Q_{t+1}(s,a_{s}^{\ast})-Q^{\ast}(s,a_{s}^{\ast})\geq 0,$

where $a_{s}^{\ast}=\operatorname*{argmax}_{a}Q^{\ast}(s,a)$. Finally, by the
definition of $V_{t+1}$ in Line 1 of Algorithm 1, we have
$V_{t+1}(s)=\widetilde{V}_{t+1}(s)\wedge(\min_{s^{\prime}}\widetilde{V}_{t+1}(s^{\prime})+\text{sp}(v^{\ast}))\geq\widetilde{V}_{t+1}(s)\geq
V^{\ast}(s)$. ∎

##  Appendix C Linear MDP Setting

######  Lemma 13 (Concentration of vector-valued self-normalized processes
[2]).

Let $\\{\varepsilon_{t}\\}_{t=1}^{\infty}$ be a real-valued stochastic process
with corresponding filtration $\\{\mathcal{F}_{t}\\}_{t=0}^{\infty}$. Let
$\varepsilon_{t}|\mathcal{F}_{t-1}$ be zero-mean and $\sigma$-subgaussian. Let
$\\{\phi_{t}\\}_{t=0}^{\infty}$ be an $\mathbb{R}^{d}$-valued stochastic
process where $\phi_{t}\in\mathcal{F}_{t-1}$. Assume $\Lambda_{0}$ is a
$d\times d$ positive definite matrix, and let
$\Lambda_{t}=\Lambda_{0}+\sum_{s=1}^{t}\phi_{s}\phi_{s}^{T}$. Then for any
$\delta>0$, with probability at least $1-\delta$, we have for all $t\geq 0$
that

$\left\|\sum_{s=1}^{t}\phi_{s}\varepsilon_{s}\right\|_{\Lambda_{t}^{-1}}^{2}\leq
2\sigma^{2}\log\left(\frac{\text{det}(\Lambda_{t})^{1/2}\text{det}(\Lambda_{0})^{-1/2}}{\delta}\right).$

###  C.1 Concentration bound for regression coefficients

######  Lemma 14.

Let $V:\mathcal{S}\rightarrow[0,B]$ be a bounded function. Then, there exists
a parameter $\bm{w}_{V}^{\ast}\in\mathbb{R}^{d}$ such that
$PV(s,a)=\langle\varphi(s,a),\bm{w}_{V}\rangle$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and

$\|\bm{w}_{V}^{\ast}\|_{2}\leq B\sqrt{d}.$

###### Proof.

By Assumption B, we have

$PV(s,a)=\int_{\mathcal{S}}V(s^{\prime})P(ds^{\prime}|s,a)=\int_{\mathcal{S}}V(s^{\prime})\langle\bm{\varphi}(s,a),\bm{\mu}(ds^{\prime})\rangle=\langle\bm{\varphi}(s,a),\int_{\mathcal{S}}V(s^{\prime})d\bm{\mu}(s^{\prime})\rangle.$

Hence,
$\bm{w}_{V}^{\ast}=\int_{\mathcal{S}}V(s^{\prime})d\bm{\mu}(s^{\prime})$
satisfies $PV(s,a)=\langle\bm{\varphi}(s,a),\bm{w}_{V}\rangle$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$. Also, such $\bm{w}_{V}$ satisfies

$\|\bm{w}_{V}\|_{2}=\left\|\int_{\mathcal{S}}V(s^{\prime})d\bm{\mu}(s^{\prime})\right\|_{2}\leq
B\left\|\int_{\mathcal{S}}d\bm{\mu}(s^{\prime})\right\|_{2}\leq B\sqrt{d}$

where the first inequality holds since $\bm{\mu}$ is a vector of positive
measures and $V(s^{\prime})\geq 0$. The last inequality is by the boundedness
assumption (1) on $\bm{\mu}(\mathcal{S})$. ∎

######  Lemma 15.

Let $\bm{w}$ be a ridge regression coefficient obtained by regressing
$y\in[0,B]$ on $\bm{x}\in\mathbb{R}^{d}$ using the dataset
$\\{(\bm{x}_{i},y_{i})\\}_{i=1}^{n}$ so that
$\bm{w}=\Lambda^{-1}\sum_{i=1}^{n}\bm{x}_{i}y_{i}$ where
$\Lambda=\sum_{i=1}^{n}\bm{x}\bm{x}^{T}+\lambda I$. Then,

$\|\bm{w}\|_{2}\leq B\sqrt{dn/\lambda}.$

###### Proof.

For any unit vector $\bm{u}\in\mathbb{R}^{d}$ with $\|\bm{u}\|_{2}=1$, we have

$\displaystyle|\bm{u}^{T}\bm{w}|$
$\displaystyle=\left|\bm{u}^{T}\Lambda^{-1}\sum_{i=1}^{n}\bm{x}_{i}y_{i}\right|$
$\displaystyle\leq B\sum_{i=1}^{n}|\bm{u}^{T}\Lambda^{-1}\bm{x}_{i}|$
$\displaystyle\leq
B\sum_{i=1}^{n}\sqrt{\bm{u}^{T}\Lambda^{-1}\bm{u}}\sqrt{\bm{x}_{i}^{T}\Lambda^{-1}\bm{x}_{i}}$
$\displaystyle\leq\frac{B}{\sqrt{\lambda}}\sum_{i=1}^{n}\sqrt{\bm{x}_{i}^{T}\Lambda^{-1}\bm{x}_{i}}$
$\displaystyle\leq\frac{B}{\sqrt{\lambda}}\sqrt{n}\sqrt{\sum_{i=1}^{n}{\bm{x}_{i}^{T}\Lambda^{-1}\bm{x}_{i}}}$
$\displaystyle\leq B\sqrt{dn/\lambda}$

where the second inequality and the fourth inequality are by Cauchy-Schwartz,
the third inequality is by $\Lambda\succeq\lambda I$, and the last inequality
is by Lemma 23.

The desired result follows from the fact that
$\|\bm{w}\|_{2}=\max_{\bm{u}:\|\bm{u}\|_{2}=1}|\bm{u}^{T}\bm{w}|$. ∎

The following self-normalized process bound is an adaption of Lemma D.4 in
[17]. Their proof defines the bound $B$ to be a value that satisfies
$\|V\|_{\infty}\leq B$. Upon observing their proof, it is easy to see that we
can strengthen their result to only require $\text{sp}(V)\leq B$. The
following lemma is the strengthened version.

######  Lemma 16 (Adaptation of Lemma D.4 in [17]).

Let $\\{x_{t}\\}_{t=1}^{\infty}$ be a stochastic process on state space
$\mathcal{S}$ with corresponding filtration
$\\{\mathcal{F}_{t}\\}_{t=0}^{\infty}$. Let $\\{\phi_{t}\\}_{t=0}^{\infty}$ be
a $\mathbb{R}^{d}$-valued stochastic process where
$\phi_{t}\in\mathcal{F}_{t-1}$, and $\|\phi_{t}\|_{2}\leq 1$. Let
$\Lambda_{n}=\lambda I+\sum_{t=1}^{n}\phi_{t}\phi_{t}^{T}$. Then for any
$\delta>0$ and any given function class $\mathcal{V}$, with probability at
least $1-\delta$, for all $k\geq 0$, and any $V\in\mathcal{V}$ satisfying
$\text{sp}(V)\leq B$, we have

$\left\|\sum_{t=1}^{n}\phi_{t}(V(x_{t})-\mathbb{E}[V(x_{t})|\mathcal{F}_{t-1}])\right\|_{\Lambda_{n}^{-1}}^{2}\leq
4B^{2}\left[\frac{d}{2}\log\left(\frac{n+\lambda}{\lambda}\right)+\log\frac{\mathcal{N}_{\varepsilon}}{\delta}\right]+\frac{8n^{2}\varepsilon^{2}}{\lambda}$

where $\mathcal{N}_{\varepsilon}$ is the $\varepsilon$-covering number of
$\mathcal{V}$ with respect to the distance
$\text{dist}(V,V^{\prime})=\sup_{x}|V(x)-V^{\prime}(x)|$.

######  Lemma 17 (Adaptation of Lemma D.6 in [17]).

Let $\mathcal{V}_{\text{linear}}$ be a class of functions mapping from
$\mathcal{S}$ to $\mathbb{R}$ with the following parametric form

$V(\cdot)=\text{clip}(\max_{a}w^{T}\varphi(\cdot,a)+C+\beta\sqrt{\varphi(\cdot,a)^{T}\Lambda^{-1}\varphi(\cdot,a)},m,M)$
(2)

where the parameters $(w,\beta,C,\Lambda,m,M)$ satisfy $\|w\|\leq L$,
$\beta\in[0,B]$, $C\in[0,D]$, $m\leq M$ and the minimum eigenvalue satisfies
$\lambda_{\text{min}}(\Lambda)\geq\lambda$. The clip function defined as
$\text{clip}(v(\cdot),m,M)=\min\\{\max\\{v(\cdot),m\\},M\\}$ for $m\leq M$
forces the function value to be in the interval $[m,M]$. Assume
$\|\bm{\varphi}(s,a)\|\leq 1$ for all $(s,a)$ pairs, and let
$\mathcal{N}_{\varepsilon}$ be the $\varepsilon$-covering number of
$\mathcal{V}$ with respect to the distance
$\text{dist}(V,V^{\prime})=\sup_{x}|V(x)-V^{\prime}(x)|$. Then

$\log\mathcal{N}_{\varepsilon}\leq
d\log(1+8L/\varepsilon)+\log(1+4D/\varepsilon)+d^{2}\log[1+8d^{1/2}B^{2}/(\lambda\varepsilon^{2})].$

######  Lemma 18 (Adaptation of Lemma B.3 in [17]).

Under the linear MDP setting in Theorem 5 for the $\gamma$-LSCVI-UCB algorithm
with clipping oracle (Algorithm 2), let $c_{\beta}$ be the constant in the
definition of $\beta=c_{\beta}Hd\sqrt{\log(dT/\delta)}$. There exists an
absolute constant $C$ that is independent of $c_{\beta}$ such that for any
fixed $\delta\in(0,1)$, the event $\mathfrak{E}$ defined by

$\forall
t\in[T]:~{}~{}\left\|\sum_{u=1}^{\tau_{t}-1}\varphi(s_{u},a_{u})[V_{t}(s_{u+1})-PV_{t}(s_{u},a_{u})]\right\|_{\Lambda_{k_{t}}^{-1}}\leq
C\cdot Hd\sqrt{\log((c_{\beta}+1)dT/\delta)}$

satisfies $P(\mathfrak{E})\geq 1-\delta$ where $k_{t}$ is the episode index of
time step $t$ and $\tau_{t}$ is the starting time step of episode $k_{t}$.

###### Proof.

For all $t=1,\dots,T$, by Lemma 15, we have $\|\bm{w}_{t}\|_{2}\leq
H\sqrt{dt/\lambda}$. Hence, by combining Lemma 17 and Lemma 16, we have for
any $\varepsilon>0$ that, with probability at least $1-\delta$,

$\displaystyle\bigg{\|}\sum_{u=1}^{\tau_{t}-1}\varphi(s_{u},a_{u})[V_{t}(s_{u+1})-PV_{t}(s_{u},a_{u})]\bigg{\|}_{\Lambda_{k_{t}}^{-1}}^{2}$
$\displaystyle\leq
4H^{2}\left[\frac{2}{d}\log\left(\frac{t+\lambda}{\lambda}\right)+d\log\left(1+\frac{4H\sqrt{dt}}{\varepsilon\sqrt{\lambda}}\right)+d^{2}\log\left(1+\frac{8d^{1/2}\beta^{2}}{\varepsilon^{2}\lambda}\right)+\log\left(\frac{1}{\delta}\right)\right]$
$\displaystyle\quad\quad+\frac{8t^{2}\varepsilon^{2}}{\lambda}$

where we use the fact that $\tau_{t}\leq t$. Choosing $\varepsilon=Hd/t$ and
$\lambda=1$, there exists an absolute constant $C>0$ independent of
$c_{\beta}$ such that, with probability at least $1-\delta$,

$\bigg{\|}\sum_{u=1}^{\tau_{t}-1}\varphi(s_{u},a_{u})[V_{t}(s_{u+1})-PV_{t}(s_{u},a_{u})]\bigg{\|}_{\Lambda_{k_{t}}^{-1}}^{2}\leq
C^{2}\cdot d^{2}H^{2}\log((c_{\beta}+1)dT/\delta),$

which concludes the proof. ∎

######  Lemma 19 (Concentration of regression coefficients).

Under the event $\mathfrak{E}$ defined in Lemma 18, there exists an absolute
constant $c_{\beta}$ such that for $\beta=c_{\beta}\cdot
Hd\sqrt{\log(dT/\delta)}$, we have

$|\langle\bm{u},\bm{w}_{t}-\bm{w}_{t}^{\ast}\rangle|\leq\beta\|\bm{u}\|_{\Lambda_{k_{t}}^{-1}}$

for all $t=1,\dots,T$ and for all vector $\bm{u}\in\mathbb{R}^{d}$ where
$k_{t}$ is the episode index for time step $t$ and
$\bm{w}_{t}^{\ast}\coloneqq\int(V_{t}(s)-\min_{s^{\prime}}V_{t}(s^{\prime}))d\bm{\mu}(s)$
is a parameter that satisfies
$\langle\bm{\varphi}(s,a),\bm{w}_{t}^{\ast}\rangle=PV_{t}(s,a)-\min_{s^{\prime}}V_{t}(s^{\prime})$.

###### Proof.

For convenience, we introduce the notation
$\bar{V}_{t}(s)=V_{t}(s)-\min_{s^{\prime}}V_{t}(s^{\prime})$. With this
notation, we can write

$\bm{w}_{t}=\Lambda_{k_{t}}^{-1}\sum_{u=1}^{\tau_{t}-1}\bm{\varphi}(s_{u},a_{u})\bar{V}_{t}(s_{u+1})$

where $\tau_{t}$ is the starting time step of episode $k_{t}$. We can
decompose $\langle\bm{u},\bm{w}_{t}\rangle$ as

$\displaystyle\langle\bm{u},\bm{w}_{t}\rangle=\underbrace{\langle\bm{u},\Lambda_{k_{t}}^{-1}\sum_{u=1}^{\tau_{t}-1}\bm{\varphi}(s_{u},a_{u})P\bar{V}_{t}(s_{u},a_{u})\rangle}_{(a)}+\underbrace{\langle\bm{u},\Lambda_{k_{t}}^{-1}\sum_{u=1}^{\tau_{t}-1}\bm{\varphi}(s_{u},a_{u})(\bar{V}_{t}(s_{u+1})-P\bar{V}_{t}(s_{u},a_{u}))}_{(b)}.$

Since $\bm{w}_{t}^{\ast}=\int\bar{V}_{t}(s)d\bm{\mu}(s)$ and
$V_{t}(s)\in[0,H]$ for all $s\in\mathcal{S}$, it follows by Lemma 14 that
$\|\bm{w}_{t}^{\ast}\|_{2}\leq H\sqrt{d}$. Hence, the first term $(a)$ in the
display above can be bounded as

$\displaystyle\langle\bm{u},\Lambda_{k_{t}}^{-1}\sum_{u=1}^{\tau_{t}-1}\bm{\varphi}(s_{u},a_{u})PV_{t}(s_{u},a_{u})\rangle$
$\displaystyle=\langle\bm{u},\Lambda_{k_{t}}^{-1}\sum_{u=1}^{\tau_{t}-1}\bm{\varphi}(s_{u},a_{u})\bm{\varphi}(s_{u},a_{u})^{T}\bm{w}_{t}^{\ast}\rangle$
$\displaystyle=\langle\bm{u},\bm{w}_{t}^{\ast}\rangle-\lambda\langle\bm{u},\Lambda_{k_{t}}^{-1}\bm{w}_{t}^{\ast}\rangle$
$\displaystyle\leq\langle\bm{u},\bm{w}_{t}^{\ast}\rangle+\lambda\|\bm{u}\|_{\Lambda_{k_{t}}^{-1}}\|\bm{w}_{t}^{\ast}\|_{\Lambda_{k_{t}}^{-1}}$
$\displaystyle\leq\langle\bm{u},\bm{w}_{t}^{\ast}\rangle+H\sqrt{\lambda
d}\|\bm{u}\|_{\Lambda_{k_{t}}^{-1}}$

where the first inequality is by Cauchy-Schwartz and the second inequality is
by Lemma 14. Under the event $\mathfrak{E}$ defined in Lemma 18, the second
term $(b)$ can be bounded by

$\displaystyle\langle\bm{u},\Lambda_{k_{t}}^{-1}\sum_{u=1}^{\tau_{t}-1}\bm{\varphi}(s_{u},a_{u})$
$\displaystyle(\bar{V}_{t}(s_{u+1})-P\bar{V}_{t}(s_{u},a_{u}))$
$\displaystyle\leq\|\bm{u}\|_{\Lambda_{k_{t}}^{-1}}\bigg{\|}\sum_{u=1}^{\tau_{t}-1}\bm{\varphi}(s_{u},a_{u})(V_{t}(s_{u+1})-PV_{t}(s_{u},a_{u}))\bigg{\|}_{\Lambda_{k_{t}}^{-1}}$
$\displaystyle\leq C\cdot
Hd\sqrt{\log((c_{\beta}+1)dT/\delta)}\cdot\|\bm{u}\|_{\Lambda_{k_{t}}^{-1}}.$

Combining the two bounds and rearranging, we get

$\langle\bm{u},\bm{w}_{t}-\bm{w}^{\ast}_{t}\rangle\leq C\cdot
Hd\sqrt{(\log(c_{\beta}+1)dT/\delta)}\cdot\|\bm{u}\|_{\Lambda_{k_{t}}^{-1}}$

for some absolute constant $C$ independent of $c_{\beta}$. Lower bound of
$\langle\bm{u},\bm{w}_{t}-\bm{w}_{t}^{\ast}\rangle$ can be shown similarly,
establishing

$|\langle\bm{u},\bm{w}_{t}-\bm{w}_{t}^{\ast}\rangle|\leq C\cdot
Hd\sqrt{\log((c_{\beta}+1)dT/\delta)}\cdot\|\bm{u}\|_{\Lambda_{k_{t}}^{-1}}.$

It remains to show that there exists a choice of absolute constant $c_{\beta}$
such that

$C\sqrt{\log(c_{\beta}+1)+\log(dT/\delta)}\leq
c_{\beta}\sqrt{\log(dT/\delta)}.$

Noting that $\log(dT/\delta)\geq\log 2$, this can be done by choosing an
absolute constant $c_{\beta}$ that satisfies $C\sqrt{\log
2+\log(c_{\beta}+1)}\leq c_{\beta}\sqrt{\log 2}$. ∎

###  C.2 Optimism

###### Proof of Lemma 7.

We prove by induction on $t=1,\dots,T$. The base case $t=1$ is trivial since
$V_{1}(s)=\frac{1}{1-\gamma}\geq V^{\ast}(s)$ for all $s\in\mathcal{S}$ and
$Q_{1}(s,a)=\frac{1}{1-\gamma}\geq Q^{\ast}(s,a)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

Now, suppose the optimism results $V_{\tau}(s)\geq V^{\ast}(s)$ and
$Q_{\tau}(s,a)\geq Q^{\ast}(s,a)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$ hold for $\tau=1,\dots,t$. For
convenience, we use the notation
$\bar{V}_{t}(s)=V_{t}(s)-\min_{s^{\prime}}V_{t}(s^{\prime})$. Using the
concentration bounds of regression coefficients $\bm{w}_{t}$ provided in Lemma
19, we can lower bound $\widetilde{Q}_{t+1}(s,a)$ as follows. Writing
$k=k_{t}$ as the episode index for the time step $t$,

$\displaystyle\widetilde{Q}_{t+1}(s,a)$
$\displaystyle=\left(r(s,a)+\gamma(\langle\bm{\varphi}(s,a),\bm{w}_{t}\rangle+\min_{s^{\prime}}V_{t}(s^{\prime})+\beta\|\bm{\varphi}(s,a)\|_{\Lambda_{k_{t}}^{-1}}\right)\wedge\frac{1}{1-\gamma}$
$\displaystyle\geq\left(r(s,a)+\gamma(\langle\bm{\varphi}(s,a),\bm{w}_{t}^{\ast}\rangle+\min_{s^{\prime}}V_{t}(s^{\prime}))\right)\wedge\frac{1}{1-\gamma}$
$\displaystyle=(r(s,a)+\gamma PV_{t}(s,a))\wedge\frac{1}{1-\gamma}$
$\displaystyle\geq(r(s,a)+\gamma PV^{\ast}(s,a))\wedge\frac{1}{1-\gamma}$
$\displaystyle=Q^{\ast}(s,a)$

where $\bm{w}_{t}^{\ast}$ is a parameter that satisfies
$\langle\bm{\varphi}(s,a),\bm{w}_{t}^{\ast}\rangle=P\bar{V}_{t}(s,a)$. The
second inequality is by the induction hypothesis $V_{t}\geq V^{\ast}$ and the
last equality is by the Bellman optimality equation for the discounted setting
and the fact that $Q^{\ast}\leq\frac{1}{1-\gamma}$.

We established $\widetilde{Q}_{t+1}(s,a)\geq Q^{\ast}(s,a)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$. Trivially, we have
$Q_{t+1}(s,a)=\max_{\tau\in[t_{k}:t]}\widetilde{Q}_{\tau+1}(s,a)\geq
Q^{\ast}(s,a)$. It remains to show that $V_{t+1}(s)\geq V^{\ast}(s)$ for all
$s\in\mathcal{S}$. Recall that the algorithm defines
$\widetilde{V}_{t+1}(\cdot)=\max_{a}\widetilde{Q}_{t+1}(\cdot,a)$. Hence, for
all $s\in\mathcal{S}$, we have

$\displaystyle\widetilde{V}_{t+1}(s)-V^{\ast}(s)$
$\displaystyle=\max_{a}\widetilde{Q}_{t+1}(s,a)-V^{\ast}(s)$
$\displaystyle\geq Q_{t+1}(s,a_{s}^{\ast})-Q^{\ast}(s,a_{s}^{\ast})$
$\displaystyle\geq 0$

where we use the notation
$a_{s}^{\ast}=\operatorname*{argmax}_{a}Q^{\ast}(s,a)$ so that
$V^{\ast}(s)=Q^{\ast}(s,a_{s}^{\ast})$, establishing
$\widetilde{V}_{t+1}(s)\geq V^{\ast}(s)$ for all $s\in\mathcal{S}$. Hence, for
all $s\in\mathcal{S}$, we have

$\displaystyle V_{t+1}(s)$
$\displaystyle=\widetilde{V}_{t+1}(s)\wedge(\min_{s^{\prime}}\widetilde{V}_{t+1}(s^{\prime})+2\cdot\text{sp}(v^{\ast}))$
$\displaystyle\geq
V^{\ast}(s)\wedge(\min_{s^{\prime}}V^{\ast}(s^{\prime})+2\cdot\text{sp}(v^{\ast}))$
$\displaystyle=V^{\ast}(s)$

where the last equality is due to $\text{sp}(V^{\ast})\leq
2\text{sp}(v^{\ast})$ by Lemma 1. By induction, the proof for the optimism
results $V_{t}(s)\geq V^{\ast}(s)$ and
$Q_{t}(s,a)\geq\widetilde{Q}_{t}(s,a)\geq Q^{\ast}(s,a)$ for $t=1,\dots,T$ are
complete. ∎

##  Appendix D Linear MDP setting with computationally efficient clipping

###  D.1 Concentration bound for regression coefficients

######  Lemma 20 (Adaptation of Lemma B.3 in [17]).

Under the linear MDP setting in Theorem 9 for the $\gamma$-LSCVI-UCB algorithm
with computationally efficient clipping oracle (Algorithm 3), let $c_{\beta}$
be the constant in the definition of
$\beta=c_{\beta}Hd\sqrt{\log(dT/\delta)}$. There exists an absolute constant
$C$ that is independent of $c_{\beta}$ such that for any fixed
$\delta\in(0,1)$, the event $\mathfrak{E}_{2}$ defined by

$\displaystyle\forall t\in[T],t^{\prime}\in[t:T]$
$\displaystyle:~{}~{}\left\|\sum_{u=1}^{\tau_{t}-1}\varphi(s_{u},a_{u})[V_{t}^{(t^{\prime})}(s_{u+1})-PV_{t}^{(t^{\prime})}(s_{u},a_{u})]\right\|_{\Lambda_{k_{t}}^{-1}}$
$\displaystyle\hskip 170.71652pt\leq C\cdot
Hd\sqrt{\log((c_{\beta}+1)dT/\delta)}$

satisfies $P(\mathfrak{E}_{2})\geq 1-\delta$ where $k_{t}$ is the episode
index of time step $t$ and $\tau_{t}$ is the starting time step of episode
$k_{t}$.

###### Proof.

For all $t=1,\dots,T$ and $t^{\prime}\in[t:T]$, by Lemma 15, we have
$\|\bm{w}_{t}^{(t^{\prime})}\|_{2}\leq H\sqrt{dt/\lambda}$. Hence, by
combining Lemma 17 and Lemma 16, using the fact that $V_{t}^{(t^{\prime})}$
has the parametric form (2), we have for any $\varepsilon>0$ that, with
probability at least $1-\delta$,

$\displaystyle\bigg{\|}\sum_{u=1}^{\tau_{t}-1}\varphi(s_{u},a_{u})[V_{t}^{(t^{\prime})}(s_{u+1})-PV_{t}^{(t^{\prime})}(s_{u},a_{u})]\bigg{\|}_{\Lambda_{k_{t}}^{-1}}^{2}$
$\displaystyle\leq
4H^{2}\left[\frac{2}{d}\log\left(\frac{t+\lambda}{\lambda}\right)+d\log\left(1+\frac{4H\sqrt{dt}}{\varepsilon\sqrt{\lambda}}\right)+d^{2}\log\left(1+\frac{8d^{1/2}\beta^{2}}{\varepsilon^{2}\lambda}\right)+\log\left(\frac{1}{\delta}\right)\right]$
$\displaystyle\quad\quad+\frac{8t^{2}\varepsilon^{2}}{\lambda}$

where we use the fact that $\tau_{t}\leq t$. Choosing $\varepsilon=Hd/t$ and
$\lambda=1$, there exists an absolute constant $C>0$ independent of
$c_{\beta}$ such that, with probability at least $1-\delta$,

$\bigg{\|}\sum_{u=1}^{\tau_{t}-1}\varphi(s_{u},a_{u})[V_{t^{\prime}}^{(t)}(s_{u+1})-PV_{t^{\prime}}^{(t)}(s_{u},a_{u})]\bigg{\|}_{\Lambda_{k_{t}}^{-1}}^{2}\leq
C^{2}\cdot d^{2}H^{2}\log((c_{\beta}+1)dT/\delta),$

which concludes the proof. ∎

######  Lemma 21 (Concentration of regression coefficients).

Under the event $\mathfrak{E}_{2}$ defined in Lemma 20, there exists an
absolute constant $c_{\beta}$ such that for $\beta=c_{\beta}\cdot
Hd\sqrt{\log(dT/\delta)}$, we have

$|\langle\bm{u},\bm{w}_{t}^{(t^{\prime})}-\bm{w}_{t}^{(t^{\prime})}{}^{\ast}\rangle|\leq\beta\|\bm{u}\|_{\Lambda_{k_{t}}^{-1}}$

for all $t=1,\dots,T$, $t^{\prime}\in[t:T]$ and for all vector
$\bm{u}\in\mathbb{R}^{d}$ where $k_{t}$ is the episode index for time step $t$
and
$\bm{w}_{t}^{(t^{\prime})}{}^{\ast}\coloneqq\int(V_{t}^{(t^{\prime})}(s)-\min_{s^{\prime}}V_{t}^{(t^{\prime})}(s^{\prime}))d\bm{\mu}(s)$
is a parameter that satisfies
$\langle\bm{\varphi}(s,a),\bm{w}_{t}^{(t^{\prime})}{}^{\ast}\rangle=PV_{t}^{(t^{\prime})}(s,a)-\min_{s^{\prime}}V_{t}^{(t^{\prime})}(s^{\prime})$.

###### Proof.

The proof is analogous to the proof of Lemma 19. ∎

###  D.2 Optimism

######  Lemma 22 (Optimism).

Under the linear MDP setting in Theorem 9, running Algorithm 3 with input
$H=2\cdot\text{sp}(v^{\ast})$ guarantees with probability at least $1-\delta$
that for all $t=1,\dots,T$, $t^{\prime}\in[t:T]$ and for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$, we have

$V_{t}^{(t^{\prime})}(s)\geq
V^{\ast}(s),\quad\widetilde{Q}_{t}^{(t^{\prime})}(s,a)\geq Q^{\ast}(s,a).$

###### Proof.

We prove under the event $\mathfrak{E}_{2}$ defined in Lemma 20, which holds
with probability at least $1-\delta$. We prove by induction on $t=1,\dots,T$.
The base case $t=1$ is trivial since $V_{1}^{(u)}(s)=\frac{1}{1-\gamma}\geq
V^{\ast}(s)$ for all $u\in[T]$ and for all $s\in\mathcal{S}$, and
$Q_{1}(s,a)=\frac{1}{1-\gamma}\geq Q^{\ast}(s,a)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

Now, suppose the optimism results $V_{u}^{(u^{\prime})}(s)\geq V^{\ast}(s)$
and $Q_{u}(s,a)\geq Q^{\ast}(s,a)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$ hold for $u=1,\dots,t$ and
$u^{\prime}\in[u:T]$. For convenience, we use the notation
$\bar{V}_{t}^{(t^{\prime})}(s)=V_{t}^{(t^{\prime})}(s)-\min_{s^{\prime}}V_{t}^{(t^{\prime})}(s^{\prime})$
for all $t,t^{\prime}$. Using the concentration bounds of regression
coefficients $\bm{w}_{t}^{(t^{\prime})}$ provided in Lemma 21, we can lower
bound $\widetilde{Q}_{t+1}^{(u)}(s,a)$ for any $u\in[t+1:T]$ as follows.
Writing $k_{t}$ as the episode index for time step $t$, we have

$\displaystyle\widetilde{Q}_{t+1}^{(u)}(s,a)$
$\displaystyle=\left(r(s,a)+\gamma(\langle\bm{\varphi}(s,a),\bm{w}_{t}^{(u)}\rangle+\min_{s^{\prime}}V_{t}^{(u)}(s^{\prime})+\beta\|\bm{\varphi}(s,a)\|_{\Lambda_{k_{t}}^{-1}}\right)\wedge\frac{1}{1-\gamma}$
$\displaystyle\geq\left(r(s,a)+\gamma(\langle\bm{\varphi}(s,a),\bm{w}_{t}^{(u)}{}^{\ast}\rangle+\min_{s^{\prime}}V_{t}^{(u)}(s^{\prime}))\right)\wedge\frac{1}{1-\gamma}$
$\displaystyle=(r(s,a)+\gamma PV_{t}^{(u)}(s,a))\wedge\frac{1}{1-\gamma}$
$\displaystyle\geq(r(s,a)+\gamma PV^{\ast}(s,a))\wedge\frac{1}{1-\gamma}$
$\displaystyle=Q^{\ast}(s,a)$

where $\bm{w}_{t}^{\ast}$ is a parameter that satisfies
$\langle\bm{\varphi}(s,a),\bm{w}_{t}^{\ast}\rangle=P\bar{V}_{t}(s,a)$. The
second inequality is by the induction hypothesis $V_{t}^{(u)}\geq V^{\ast}$
for $u\in[t:T]$ and the last equality is by the Bellman optimality equation
for the discounted setting and the fact that $Q^{\ast}\leq\frac{1}{1-\gamma}$.

We established $\widetilde{Q}_{t+1}^{(u)}(s,a)\geq Q^{\ast}(s,a)$ for all
$u\in[t+1:T]$ and for all $(s,a)\in\mathcal{S}\times\mathcal{A}$. It remains
to show that $V_{t+1}^{(u)}(s)\geq V^{\ast}(s)$ for all $u\in[t+1:T]$ and for
all $s\in\mathcal{S}$. Recall that the algorithm defines
$\widetilde{V}_{t+1}^{(u)}(\cdot)=\max_{a}\widetilde{Q}_{t+1}^{(u)}(\cdot,a)$.
Hence, for all $s\in\mathcal{S}$, we have

$\displaystyle\widetilde{V}_{t+1}^{(u)}(s)-V^{\ast}(s)$
$\displaystyle=\max_{a}\widetilde{Q}_{t+1}^{(u)}(s,a)-V^{\ast}(s)$
$\displaystyle\geq Q_{t+1}^{(u)}(s,a_{s}^{\ast})-Q^{\ast}(s,a_{s}^{\ast})$
$\displaystyle\geq 0$

where we use the notation
$a_{s}^{\ast}=\operatorname*{argmax}_{a}Q^{\ast}(s,a)$ so that
$V^{\ast}(s)=Q^{\ast}(s,a_{s}^{\ast})$, establishing
$\widetilde{V}_{t+1}^{(u)}(s)\geq V^{\ast}(s)$ for all $s\in\mathcal{S}$.
Hence, for all $s\in\mathcal{S}$ and for all $u\in[t+1:T]$, we have

$\displaystyle V_{t+1}^{(u)}(s)$
$\displaystyle=\textsc{Clip}_{\mathcal{H}_{t+1}}(\widetilde{V}_{t+1}^{(u)},2\cdot\text{sp}(v^{\ast}))(s)$
$\displaystyle\geq\textsc{Clip}_{\mathcal{H}_{t+1}}(V^{\ast},2\cdot\text{sp}(v^{\ast}))(s)$
$\displaystyle\geq\textsc{Clip}_{\mathcal{S}}(V^{\ast},2\cdot\text{sp}(v^{\ast}))(s)$
$\displaystyle=V^{\ast}(s)$

where the first inequality is by the order preserving property (v) of the
clipping operator, the second inequality is by property (iv) of the clipping
operator, and the last equality is due to $\text{sp}(V^{\ast})\leq
2\text{sp}(v^{\ast})$ by Lemma 1 and property (i) of the clipping operator. By
induction, the proof for the optimism results $V_{t}^{(u)}(s)\geq V^{\ast}(s)$
and $\widetilde{Q}_{t}^{(u)}(s,a)\geq Q^{\ast}(s,a)$ for $t=1,\dots,T$ and for
$u\in[t:T]$ are complete. ∎

###  D.3 Regret bound

###### Proof of Theorem 9.

Let $t$ be a time step in episode $k$ and let
$\tau_{t}(s,a)=\operatorname*{argmax}_{\tau\in[t_{k}:t]}\widetilde{Q}_{\tau+1}^{(t+1)}(s,a)$
such that $Q_{t+1}(s,a)=\widetilde{Q}_{\tau_{t}(s,a)+1}^{(t+1)}(s,a)$. Note
that $\tau_{t}(s,a)\leq t$. Using this notation, by the definition of
$\widetilde{Q}_{t}^{(t+1)}(\cdot,\cdot)$, we have for all time step $t$ in
episode $k$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$ that

$\displaystyle r(s,a)$ $\displaystyle\geq
Q_{t+1}(s,a)-\gamma(\langle\bm{\varphi}(s,a),\bm{w}_{\tau_{t}(s,a)}^{(t+1)}\rangle+\min_{s^{\prime}}V_{\tau_{t}(s,a)}^{(t+1)}(s^{\prime})-\beta\|\bm{\varphi}(s,a)\|_{\Lambda_{k}^{-1}})$
$\displaystyle\geq Q_{t+1}(s,a)-\gamma
PV_{\tau_{t}(s,a)}^{(t+1)}(s,a)-4\gamma\beta\|\bm{\varphi}(s,a)\|_{\Lambda_{t}^{-1}}$

where the second inequality uses the concentration bound for the regression
coefficients in Lemma 6 and the fact that $\tau_{t}(s,a)$ is a time step in
episode $k$. It also uses $\|\bm{x}\|_{\Lambda_{k}^{-1}}\leq
2\|\bm{x}\|_{\Lambda_{t}^{-1}}$ due to the episode starting condition (Line 3
in Algorithm 3) and Lemma 25. Hence,

$\displaystyle R_{T}$ $\displaystyle=\sum_{t=1}^{T}(J^{\ast}-r(s_{t},a_{t}))$
$\displaystyle\leq\sum_{t=1}^{T}(J^{\ast}-Q_{t+1}(s_{t},a_{t})+\gamma
PV_{\tau_{t}(s_{t},a_{t})}^{(t+1)}(s_{t},a_{t})+4\beta\|\bm{\varphi}(s_{t},a_{t})\|_{\Lambda_{t}^{-1}})+\mathcal{O}(1)$
$\displaystyle=\underbrace{\sum_{t=1}^{T}(J^{\ast}-(1-\gamma)V_{\tau_{t}(s_{t},a_{t})}^{(t+1)}(s_{t+1}))}_{(a)}+\gamma\underbrace{\sum_{t=1}^{T}(V_{\tau_{t}(s_{t},a_{t})}^{(t+1)}(s_{t+1})-Q_{t+1}(s_{t},a_{t}))}_{(b)}$
$\displaystyle\hskip
28.45274pt+\gamma\underbrace{\sum_{t=1}^{T}(PV_{\tau_{t}(s_{t},a_{t})}^{(t+1)}(s_{t},a_{t})-V_{\tau_{t}(s_{t},a_{t})}^{(t+1)}(s_{t+1}))}_{(c)}+4\beta\underbrace{\sum_{t=1}^{T}\|\bm{\varphi}(s_{t},a_{t})\|_{\Lambda_{t}^{-1}}}_{(d)}+~{}\mathcal{O}(1)$

where the first inequality uses the lower bound for $r(s_{t},a_{t})$ we
established previously and the fact that $J^{\ast}=\mathcal{O}(1)$.

#### Bounding term $(a)$

With the same argument as in the tabular case, the term $(a)$, the regret due
to approximation error of discounted setting, can be bounded by
$T(1-\gamma)\text{sp}(v^{\ast})$ due to the optimism
$V_{\tau_{t}(s_{t},a_{t})}^{(t+1)}(s_{t+1})\geq V^{\ast}(s_{t+1})$ by Lemma
22.

#### Bounding term $(b)$

Note that

$\displaystyle V_{\tau_{t}(s_{t},a_{t})}^{(t+1)}(s_{t+1})$
$\displaystyle=\textsc{Clip}_{\mathcal{H}_{t+1}}(\widetilde{V}_{\tau_{t}(s_{t},a_{t})}^{(t+1)},H)$
$\displaystyle\leq\widetilde{V}_{\tau_{t}(s_{t},a_{t})}^{(t+1)}(s_{t+1})$
$\displaystyle=\max_{a}\widetilde{Q}_{\tau_{t}(s_{t},a_{t})}^{(t+1)}(s_{t+1},a)$
$\displaystyle\leq\max_{a}Q_{t+1}(s_{t+1},a)$
$\displaystyle=Q_{t+1}(s_{t+1},a_{t+1})$

where the first inequality uses the property (iii) and the second inequality
uses the fact that $Q_{t+1}$ is a maximum over all $\widetilde{Q}_{\tau}$ with
$\tau\in[t_{k}:t]$ and the last inequality is by the fact that algorithm
chooses $a_{t+1}$ that maximizes $Q_{t+1}(s_{t+1},\cdot)$. Hence,

$\displaystyle\sum_{t=1}^{T}(V_{\tau_{t}(s_{t},a_{t})}^{(t+1)}(s_{t+1})-Q_{t+1}(s_{t},a_{t}))$
$\displaystyle\leq\sum_{t=1}^{T}(Q_{t+1}(s_{t+1},a_{t+1})-Q_{t+1}(s_{t},a_{t}))$
$\displaystyle\leq\sum_{t=1}^{T}(Q_{t}(s_{t},a_{t})-Q_{t+1}(s_{t},a_{t}))+\mathcal{O}(1/(1-\gamma))$
$\displaystyle\leq\mathcal{O}(K/(1-\gamma))$
$\displaystyle\leq\mathcal{O}(d\log(T/\lambda)/(1-\gamma)).$

where we use the notation $K$ to denote the total number of episodes. The
second inequality uses the fact that $Q_{t}\leq\frac{1}{1-\gamma}$ and the
third inequality uses the monotonicity $Q_{t}\leq Q_{t+1}$ for whenever both
$t-1$ and $t$ are in the same episode. There can be at most $K$ time steps
where $t-1$ and $t$ are not in the same episode, in which cases we can use a
crude bound of $\mathcal{O}(K/(1-\gamma))$. Since the episode is advanced when
the determinant of the covariance matrix doubles, it can be shown that
$K\leq\mathcal{O}(d\log(T/\lambda))$ (Lemma 26), which is used in the last
inequality.

#### Bounding term $(c)$

Contrary to the analysis for the algorithm using a clipping oracle, the term
$(c)$ is not a sum of a martingale difference sequence since the function
$V_{\tau_{t}(s_{t},a_{t})}^{(t+1)}$ is dependent on the state $s_{t+1}$ since
it is clipped function using the set of inputs $\mathcal{H}_{t+1}$. To bound
this term, we use a covering argument. Recall that any $V_{t}^{(t^{\prime})}$
is of the form

$V(\cdot)=\text{clip}(\max_{a}w^{T}\varphi(\cdot,a)+C+\beta\sqrt{\varphi(\cdot,a)^{T}\Lambda^{-1}\varphi(\cdot,a)},m,M)$

where $\|\bm{w}\|_{2}\leq\mathcal{O}(\text{sp}(v^{\ast})\sqrt{dT/\lambda})$ by
Lemma 15 and $C\in[0,\frac{1}{1-\gamma}]$ and
$\beta=\mathcal{O}(\text{sp}(v^{\ast})d\sqrt{\log(dT/\delta)})$ and
$\Lambda\succeq\lambda I$. Hence, by Lemma 17, the $\varepsilon$-covering
number $\mathcal{N}_{\varepsilon}$ of the function class of the form above is
bounded by

$\log\mathcal{N}_{\varepsilon}\leq\mathcal{O}(d\log(\text{sp}(v^{\ast})dT/(\lambda\varepsilon))+\log(1/(\varepsilon(1-\gamma)))+d^{2}\log(\text{sp}(v^{\ast})d/(\lambda\varepsilon^{2})).$

Denoting by $W_{t}=V_{\tau_{t}(s_{t},a_{t})}^{(t+1)}$ and letting
$W_{t}^{\prime}$ be the closest center of the $\varepsilon$-cover, we can
bound Term $(c)$ using union bound over the cover centers by

$\displaystyle\sum_{t=1}^{T}(PW_{t}(s_{t},a_{t})-W_{t}(s_{t+1}))$
$\displaystyle=\sum_{t=1}^{T}(PW_{t}^{\prime}(s_{t},a_{t})-W_{t}^{\prime}(s_{t+1}))$
$\displaystyle\hskip
56.9055pt+\sum_{t=1}^{T}(P(W_{t}-W_{t}^{\prime})(s_{t},a_{t})-(W_{t}-W_{t}^{\prime})(s_{t+1}))$
$\displaystyle\leq\mathcal{O}(\text{sp}(v^{\ast})\sqrt{T\log(\mathcal{N}_{\varepsilon}/\delta)})+2\varepsilon
T$

where the inequality is by Azuma-Hoeffding and the fact that
$\text{sp}(W_{t})\leq 2\cdot\text{sp}(v^{\ast})$ by clipping step in Line 3.
Choosing $\varepsilon=\frac{1}{T}$, we can further bound the term by

$\sum_{t=1}^{T}(PW_{t}(s_{t},a_{t})-W_{t}(s_{t+1}))\leq\mathcal{O}\left(\text{sp}(v^{\ast})d\sqrt{T\log\left(\frac{\text{sp}(v^{\ast})dT}{\lambda(1-\gamma)\delta}\right)}\right).$

#### Bounding term $(d)$

Term $(d)$, the sum of bonus terms, can be bounded by
$\mathcal{O}(\sqrt{dT\log T})$ using Cauchy-Schwartz and Lemma 24 if we choose
$\lambda=1$.

Combining all the bounds, and using
$\beta=\mathcal{O}(\text{sp}(v^{\ast})d\sqrt{\log(dT/\delta)})$, we get

$R_{T}\leq\mathcal{O}\left(T(1-\gamma)\text{sp}(v^{\ast})+\frac{d\log(T)}{1-\gamma}+\text{sp}(v^{\ast})d\sqrt{T\log\frac{\text{sp}(v^{\ast})dT}{(1-\gamma)\delta}}+\text{sp}(v^{\ast})\sqrt{d^{3}T\log(dT/\delta)}\right).$

Choosing the discounting factor to be $\gamma=1-\sqrt{\log(T)/T}$, we get

$R_{T}\leq\mathcal{O}(\text{sp}(v^{\ast})\sqrt{d^{3}T\log(\text{sp}(v^{\ast})dT/\delta)}).$

∎

##  Appendix E Other technical lemmas

######  Lemma 23 (Lemma D.1 in [17]).

Let $\Lambda_{t}=\sum_{i=1}^{t}\bm{\phi}_{i}\bm{\phi}_{i}^{T}+\lambda I$ where
$\bm{\phi}_{i}\in\mathbb{R}^{d}$ and $\lambda>0$. Then,

$\sum_{i=1}^{t}\bm{\phi}_{i}^{T}\Lambda_{t}^{-1}\bm{\phi}_{i}\leq d.$

######  Lemma 24 (Lemma 11 in [2]).

Let $\\{\bm{\phi}_{t}\\}_{t\geq 1}$ be a bounded sequence in $\mathbb{R}^{d}$
with $\|\bm{\phi}_{t}\|_{2}\leq 1$ for all $t\geq 1$. Let $\Lambda_{0}=I$ and
$\Lambda_{t}=\sum_{i=1}^{t}\bm{\phi}_{i}\bm{\phi}_{i}^{T}+I$ for $t\geq 1$.
Then,

$\sum_{i=1}^{t}\bm{\phi}_{i}^{T}\Lambda_{i-1}^{-1}\bm{\phi}_{i}\leq
2\log\det(\Lambda_{t})\leq 2d\log(1+t).$

######  Lemma 25 (Lemma 12 in [2]).

Suppose $A,B\in\mathbb{R}^{d\times d}$ are two positive definite matrices
satisfying $A\succeq B$. Then, for any $\bm{x}\in\mathbb{R}^{d}$, we have

$\|\bm{x}\|_{A}\leq\|\bm{x}\|_{B}\sqrt{\frac{\det(A)}{\det(B)}}.$

######  Lemma 26 (Bound on number of episodes).

The number of episodes $K$ in Algorithm 2 is bounded by

$K\leq\frac{d}{\text{log}2}\text{log}\left(1+\frac{T}{\lambda d}\right).$

###### Proof.

Let $\\{\Lambda_{k},\bar{\Lambda}_{k},k\in[K]\\}$ be as defined in Algorithm
2. Note that

$\text{tr}(\bar{\Lambda}_{T})=\text{tr}(\lambda
I_{d})+\sum_{t=1}^{T}\text{tr}(\varphi(s_{t},a_{t})\varphi(s_{t},a_{t})^{T})=\lambda
d+\sum_{t=1}^{T}\|\varphi(s_{t},a_{t})\|_{2}^{2}\leq\lambda d+T.$

By the AM–GM inequality, we have

$\det(\bar{\Lambda}_{T})\leq\left(\frac{\text{tr}(\bar{\Lambda}_{T})}{d}\right)^{d}\leq\left(\frac{\lambda
d+T}{d}\right)^{d}.$

Since we update $\Lambda_{k}$ only when $\bar{\Lambda}_{t}$ doubles,
$\text{det}(\bar{\Lambda}_{T})\geq\text{det}(\Lambda_{K})\geq\text{det}(\Lambda_{1})\cdot
2^{K}=\lambda^{d}\cdot 2^{K}$. Thus, we obtain

$K\leq\frac{d}{\text{log}2}\text{log}\left(1+\frac{T}{\lambda d}\right)$

as desired.

∎

##  Appendix F Additional related work

Table 2: Comparison of algorithms for infinite-horizon average-reward RL in tabular setting Class | Algorithm | Regret $\widetilde{\mathcal{O}}(\cdot)$ | Assumption | Computation
---|---|---|---|---
Model-based | UCRL2 [3] | $DS\sqrt{AT}$ | Bounded diameter | Efficient
REGAL [6] | $\text{sp}(v^{\ast})\sqrt{SAT}$ | Weakly communicating | Inefficient
PSRL [22] | $\text{sp}(v^{\ast})S\sqrt{AT}$ | Weakly communicating | Efficient
OSP [21] | $\sqrt{t_{\text{mix}}SAT}$ | Ergodic | Inefficient
SCAL [9] | $\text{sp}(v^{\ast})S\sqrt{AT}$ | Weakly communicating | Efficient
UCRL2B [8] | $S\sqrt{DAT}$ | Bounded diameter | Efficient
EBF [30] | $\sqrt{\text{sp}(v^{\ast})SAT}$ | Weakly communicating | Inefficient
$\gamma$-UCB-CVI (Ours) | $\text{sp}(v^{\ast})S\sqrt{AT}$ | Bellman optimality equation | Efficient
Model-free | Optimistic Q-learning [28] | $\text{sp}(v^{\ast})(SA)^{\frac{1}{3}}T^{\frac{2}{3}}$ | Weakly communicating | Efficient
MDP-OOMD [28] | $\sqrt{t_{\text{mix}}^{3}\eta AT}$ | Ergodic | Efficient
UCB-AVG [31] | $\text{sp}(v^{\ast})S^{5}A^{2}\sqrt{T}$ | Weakly communicating | Efficient
$\gamma$-LSCVI-UCB (Ours) | $\text{sp}(v^{\ast})\sqrt{S^{3}A^{3}T}$ | Bellman optimality equation | Efficient
| Lower bound [3] | $\Omega(\sqrt{DSAT})$ | Efficient |

#### Infinite-horizon average-reward setting with tabular MDP

We focus on works on infinite-horizon average-reward setting with tabular MDP
that assume either the MDP is weakly communicating or the MDP has a bounded
diameter. For other works and comparisons, see Table 2. Seminal work by [3] on
infinite-horizon average-reward setting in tabular MDPs laid the foundation
for the problem. Their model-based algorithm called UCRL2 constructs a
confidence set on the transition model and run an extended value iteration
that involves choosing the optimistic model in the confidence set each
iteration. They achieve a regret bound of $\mathcal{O}(DS\sqrt{AT})$ where $D$
is the diameter of the true MDP. [6] improve the regret bound of UCRL2 by
restricting the confidence set of the model to only include models such that
the span of the induced optimal value function is bounded. Their algorithm,
called REGAL, achieves a regret bound that scales with the span of the optimal
value function $\text{sp}(v^{\ast})$ instead of the diameter of the MDP.
However, REGAL is computationally inefficient. [9] propose a model-based
algorithm called SCAL, which is a computationally efficient version of REGAL.
[30] propose a model-based algorithm called EBF that achieves the minimax
optimal regret of $\mathcal{O}(\sqrt{\text{sp}(v^{\ast})SAT})$ by maintaining
a tighter model confidence set by making use of the estimate for the optimal
bias function. However, their algorithm is computationally inefficient. There
is another line of work on model-free algorithms for this setting. [28]
introduce a model-free Q-learning-based algorithm called Optimistic
Q-learning. Their algorithm is a reduction to the discounted setting. Although
model-free, their algorithm has a suboptimal regret of $\mathcal{O}(T^{2/3})$.
Recently, [31] introduce a Q-learning-based algorithm called UCB-AVG that
achieves regret bound of $\mathcal{O}(\sqrt{T})$. Their algorithm, which is
also a reduction to the discounted setting, is the first model-free to achieve
the order optimal regret bound. Their main idea is to use the optimal bias
function estimate to increase statistical efficiency.

#### Infinite-horizon average-reward setting with linear mixture MDP

The linear mixture MDP setting is closely related to the linear MDP setting in
that the Bellman operator admits a compact representation. However, linear
mixture MDP parameterizes the probability transition model such that the
transition probability is linear in the low-dimensional feature representation
of state-action-state triplets. Such a structure allows a sample efficient
estimation of the model, enabling the design of an optimism-based algorithm
using a confidence set on the model, much like the model-based approach for
the tabular setting. [29] and [4] design algorithms for this setting using a
confidence set on the model.

#### Infinite-horizon average-reward setting with general function
approximation

[14] study infinite-horizon average reward with general function
approximation. They propose an algorithm called LOOP which is a modified
version of the fitted Q-iteration with optimistic planning and lazy policy
updates. Although their algorithm when adapted to the linear MDP set up
achieves $\mathcal{O}(\sqrt{\text{sp}(v^{\ast})^{3}d^{3}T})$, which is
comparable to our work, their algorithm is computationally inefficient.

#### Infinite-horizon average-reward setting with linear MDPs

There is another work by [10] on the infinite-horizon average-reward setting
with linear MDPs. They study a more general constrained MDP setting where the
goal is to maximize average reward while minimizing the average cost. They
achieve $\widetilde{\mathcal{O}}(\text{sp}(v^{\ast})\sqrt{d^{3}T})$ regret,
same as our work, but they make an additional assumption that the optimal
policy is in a smooth softmax policy class. Also, their algorithm requires
solving an intractable optimization problem.

#### Reduction of average-reward to discounted setting

The technique of reducing the average-reward setting to the discounted setting
is used by [18, 24, 32, 25] to solve the sample complexity problem of
producing a nearly optimal policy given access to a simulator in the tabular
setting. [31, 28]

#### Reduction of average-reward to finite-horizon episodic setting

There are works that reduce the average-reward setting to the finite-horizon
episodic setting. However, in general, this reduction can only give regret
bound of $\mathcal{O}(T^{2/3})$. [7] study the constrained tabular MDP setting
and propose an algorithm that uses the finite-horizon reduction. Their
algorithm gives regret bound of $\mathcal{O}(T^{2/3})$. [27] study the linear
MDP setting and propose a finite-horizon reduction that uses the LSVI-UCB
[17]. Their reduction gives regret bound of $\mathcal{O}(T^{2/3})$.

#### Online RL in infinite-horizon discounted setting

The literature on online RL in the infinite-horizon discounted setting is
sparse because there is no natural notion of regret in this setting without
additional assumption on the structure of the MDP. The seminal paper by [19]
introduce a notion of regret in the discounted setting and propose a
Q-learning-based algorithm for the tabular setting and provides a regret
bound. [13] propose a model-based algorithm that adapts UCBVI [5] to the
discounted setting and achieve a nearly minimax optimal regret bound. [16]
propose a model-free algorithm with nearly minimax optimal regret bound.