# Value-Biased Maximum Likelihood Estimation for Model-based Reinforcement
Learning in Discounted Linear MDPs

Yu-Heng Hung & Ping-Chun Hsieh
Department of Computer Science
National Yang Ming Chiao Tung University
Hsinchu, Taiwan
<EMAIL_ADDRESS>
&Akshay Mete & P. R. Kumar
Texas A&M University
College Station, Texas, USA
<EMAIL_ADDRESS>
###### Abstract

We consider the infinite-horizon linear Markov Decision Processes (MDPs),
where the transition probabilities of the dynamic model can be linearly
parameterized with the help of a predefined low-dimensional feature mapping.
While the existing regression-based approaches have been theoretically shown
to achieve nearly-optimal regret, they are computationally rather inefficient
due to the need for a large number of optimization runs in each time step,
especially when the state and action spaces are large. To address this issue,
we propose to solve linear MDPs through the lens of Value-Biased Maximum
Likelihood Estimation (VBMLE), which is a classic model-based exploration
principle in the adaptive control literature for resolving the well-known
closed-loop identification problem of Maximum Likelihood Estimation. We
formally show that (i) VBMLE enjoys $\widetilde{O}(d\sqrt{T})$ regret, where
$T$ is the time horizon and $d$ is the dimension of the model parameter, and
(ii) VBMLE is computationally more efficient as it only requires solving one
optimization problem in each time step. In our regret analysis, we offer a
generic convergence result of MLE in linear MDPs through a novel
supermartingale construct and uncover an interesting connection between linear
MDPs and online learning, which could be of independent interest. Finally, the
simulation results show that VBMLE significantly outperforms the benchmark
method in terms of both empirical regret and computation time.

##  1 Introduction

Model-based reinforcement learning (MBRL) is one fundamental paradigm that
learns an optimal policy by alternating between two subroutines: estimation of
the transition dynamics and planning according to the learned dynamics model.
MBRL has been extensively studied in the tabular setting from various
perspectives, including (Auer et al., 2008; Azar et al., 2017), which have
been shown to achieve either optimal regret bounds or sample complexity.
Despite the above success, the conventional tabular MBRL methods are known to
be computationally intractable in RL problems with large state or action
spaces due to the need for direct estimation and access to the per-state
transition probability. To enable MBRL for large state and action spaces, one
important recent attempt is to study Markov decision processes with linear
feature mappings (Zhou et al., 2021b), which is termed linear MDPs
subsequently in this paper. Specifically, linear MDPs assume that the
probability of each transition can be represented by
$\langle\phi(s^{\prime}|s,a),\operatorname{\bm{\theta}}^{*}\rangle$, where
$\phi(\cdot|\cdot,\cdot)$ is a known feature function for each possible
transition, and $\operatorname{\bm{\theta}}^{*}$ parametrizes the transition
probabilities to be learned. This framework can readily encompass various
related formulations, such as tabular MDPs, feature-based linear transition
models (Yang & Wang, 2019), the linear combination of base models (Modi et
al., 2020), and linear value function frameworks (Zanette et al., 2020).

Based on the existing literature of linear MDPs, the existing approaches could
be divided into two primary categories depending on the length of the learning
horizon: episodic MDPs and infinite-horizon discounted MDPs. In episodic MDPs,
one important feature is that the environment state could be conveniently
reset to some initial state when a new episode starts. Several recent works
have explored episodic MDPs through the use of value-targeted regression
techniques, e.g., (Ayoub et al., 2020; Zhou et al., 2021a). A more detailed
survey of the related works for episodic linear MDPs is deferred to Section 2.
By contrast, in infinite-horizon linear MDPs, due to the absence of the
periodic restart, addressing exploration and conducting regret analysis could
be even more challenging than that in episodic MDPs. Some recent attempts
tackles infinite-horizon linear MDPs by designing regression-based approaches
and establishing theoretical guarantees (Zhou et al., 2021a; b; Chen et al.,
2022). However, their algorithms could suffer from high computational
complexity and be intractable in practice for the following reasons: (i) In
the existing regression-based approaches, in each time step, one would need to
solve a constrained optimization problem of the action-value function for each
state-action pair. (ii) Moreover, in order to represent the value function as
a linear combination of the learned parameter vector
$\operatorname{\bm{\theta}}$, it is necessary for those regression-based
approaches to construct a vector
$\phi_{V}(s,a):=\sum_{s^{\prime}\in\mathcal{S}}\phi(s^{\prime}|s,a)V(s^{\prime})$.
As a result, the action-value function can be expressed as follows:
$Q(s,a)=\langle\phi_{V}(s,a),\operatorname{\bm{\theta}}\rangle$. However,
constructing $\phi_{V}$ could be computationally intractable when dealing with
a large state space. These limitations render the regression-based approaches
mentioned above rather challenging to implement and deploy in practice.
Therefore, one important research question remains to be answered: How to
design an efficient model-based RL algorithm for infinite-horizon discounted
linear MDPs with provable regret guarantees?

In this paper, we answer the above question affirmatively. Specifically, to
address the above limitations, we design a tractable approach based on the
classic principle of Value-Biased Maximum Likelihood Estimation (VBMLE) (Kumar
& Lin, 1982), which has shown promising results in recent developments in
bandits (Hung et al., 2021; Hung & Hsieh, 2023) and tabular RL (Mete et al.,
2021), and leverage the value biasing technique to enforce exploration. The
major advantage of VBMLE is that with the help of value biasing, it requires
solving only one optimization problem for learning the dynamics model
parameter at each time step and thereby enjoys a significantly lower
computational complexity than the regression-based approaches. Moreover, we
formally establish $\tilde{\mathcal{O}}({d\sqrt{T}})$ regret bound based on
the following novel insights: (i) We establish a convergence result on the
Maximum Likelihood Estimator for linear MDPs by using a novel supermartingale
approach. (ii) Through this construct, we also find useful connections between
(i) the linear MDPs and online portfolio selection problem as well as (ii)
VBMLE and the Follow-the-Leader algorithm in online learning. We highlight the
main contributions as follows:

  * •

We adapt the classic VBMLE principle to the task of learning the dynamic model
for linear MDPs. Our proposed algorithm addresses model-based RL for linear
MDPs from a distributional perspective, which learns the parameterized
transition directly by maximum likelihood estimation without resorting to
regression, and guides the exploration via value biasing instead of using
concentration inequalities.

  * •

We establish the theoretical regret bound of VBMLE by providing a novel
theorem connected to the confidence ellipsoid of MLE. Furthermore, we uncover
an interesting connection between online learning and our regret analysis.

  * •

We conduct an empirical analysis to assess both the computational complexity
and empirical regret performance. The simulation results demonstrate that
VBMLE exhibits a clear advantage in terms of both effectiveness in regret and
computational efficiency.

##  2 Related Works

VBMLE for Multi-Armed Bandits and RL. Regarding VBMLE, various prior works
have applied this method to different bandit settings and tabular MDP.
Firstly, (Liu et al., 2020) focuses on solving non-contextual bandits with
exponential family reward distributions. Next, (Hung et al., 2021) introduces
two variations of VBMLE: LinRBMLE and GLM-RBMLE. These methods are designed
for solving linear contextual bandits and result in an index policy.
Furthermore, (Hung & Hsieh, 2023) leverages the representation power of neural
networks and proposes NeuralRBMLE. This approach is specifically designed for
solving neural bandits, making no assumptions about the unknown reward
distribution. As for the MDP setting, (Mete et al., 2021) has adapted VBMLE to
solve tabular MDPs, where the states and actions belong to a known finite set,
while (Mete et al., 2022) analyzed the finite performance of a constrained
version of VBMLE. By contrast, this paper takes the very first step towards
understanding the theoretical regret performance of VBMLE in RL beyond the
tabular settings.

Episodic Linear MDPs. Denoting $H$ is the total episode considered, (Cai et
al., 2020) has applied Proximal Policy Optimization (PPO). (Ayoub et al.,
2020) utilizes value target regression as an optimism principle. (Zhou et al.,
2021a) provides a new tail inequality and adapts weighted ridge regression on
UCRL-VTR provided by Ayoub et al. (2020). All of their algorithm achieve a
regret bound of $\mathcal{O}(d\sqrt{H})$. On the other hand, (Jin et al.,
2020) provides a model-free approach that considers the upper confidence bound
on the action-value function. (Wang et al., 2019; 2020) presents a value-based
approach for MDPs with generalized linear function approximation but requires
an optimistic closure assumption, and all of them have
$\mathcal{O}(\sqrt{d^{3}H})$ regret bound.

Infinite-Horizon Discounted Linear MDPs. In the context of infinite-horizon
discounted linear MDPs, (Zhou et al., 2021b) introduced the UCLK algorithm.
This algorithm takes into consideration the confidence set on the least-square
estimator of $\operatorname{\bm{\theta}}^{*}$ and demonstrates a regret upper
bound of $\mathcal{O}(d\sqrt{T}/(1-\gamma)^{2})$. (Zhou et al., 2021a)
introduced an improved version of the UCLK algorithm, called
$\text{UCLK}^{+}$. $\text{UCLK}^{+}$ incorporates weighted ridge regression
into the original UCLK algorithm and achieves a regret bound that matches the
established lower bound of $\mathcal{O}(d\sqrt{T}/(1-\gamma)^{1.5})$. On the
other hand, (Chen et al., 2022) also provide a variant of the UCLK algorithm,
called UPAC-UCLK, which has
$\mathcal{O}(d\sqrt{T}/(1-\gamma)^{2})+\mathcal{O}(\sqrt{T}/(1-\gamma)^{3})$
regret bound but with uniform-PAC sample complexity guarantee.

##  3 Problem Formulation

Markov Decision Processes (MDP) and Linear Feature Mapping. An MDP is denoted
by $\mathcal{M}:=\langle\mathcal{S},\mathcal{A},P,{R},T,\mu_{0}\rangle$, where
$\mathcal{S}$ and $\mathcal{A}$ represent the state and action spaces,
respectively, $P$ is the dynamic model,
$R:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ is the reward function, $T$
is the time horizon, and $\mu_{0}$ is the initial state distribution with
$\mu_{0}(s)>0$111As there is a policy that achieves optimal value for all
initial states $s$, or equivalently, for all initial distributions $\mu_{0}$,
without loss of generality, it is common to take a strictly positive initial
distribution.. A linear MDP is defined by the following:

  * •

There exist an unknown parameter
$\operatorname{\bm{\theta}}^{*}\in\mathbb{R}^{d}$, and a known feature mapping
$\phi(\cdot|\cdot,\cdot):\operatorname{\mathcal{S}}\times\operatorname{\mathcal{A}}\times\operatorname{\mathcal{S}}\rightarrow\mathbb{R}^{d}$,
such that
$P(s^{\prime}|s,a)=\langle\phi(s^{\prime}|s,a),\operatorname{\bm{\theta}}^{*}\rangle,\forall
s^{\prime},s\in\mathcal{S},a\in\mathcal{A}$.

  * •

$\lVert\operatorname{\bm{\theta}}^{*}\rVert_{2}\leq\sqrt{d}$ and
$\lVert\phi(s^{\prime}|s,a)\rVert_{2}\leq L,\forall
s^{\prime},s\in\mathcal{S},a\in\mathcal{A}$.

Moreover, let $\mathbb{P}$ denote the set of parameters that correspond to the
product of the simplices for each (state, action) pair:

$\displaystyle\mathbb{P}:=\left\\{\operatorname{\bm{\theta}}:0\leq\langle\phi(\cdot|s,a),\operatorname{\bm{\theta}}\rangle\leq
1,\sum_{s^{\prime}\in\mathcal{S}}\langle\phi(s^{\prime}|s,a),\operatorname{\bm{\theta}}\rangle=1,\forall
s\in\mathcal{S},a\in\mathcal{A}\right\\},$ (1)

where $\operatorname{\bm{\theta}}$ denotes the parameter of the transition
dynamics model and $\phi(\cdot\rvert s,a)$ is the known feature mapping
function.

A policy $\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$, where
$\Delta(\mathcal{A})$ is the set of all probability distributions on
$\mathcal{A}$, designed to maximize the sum of discounted reward, which is
denoted by the value function:

$\displaystyle
V^{\pi}(s;\operatorname{\bm{\theta}}):=\mathbb{E}_{\begin{subarray}{c}a_{i}\sim\pi(\cdot|s_{i})\\\
s_{i+1}\sim\langle\phi(\cdot|s_{i},a_{i}).\operatorname{\bm{\theta}}\rangle\end{subarray}}\left[\sum_{i=0}^{\infty}\gamma^{i}r(s_{i},a_{i})\Big{|}s_{0}=s\right].$
(2)

Similarly, the action value function $Q^{\pi}(s,a;\operatorname{\bm{\theta}})$
is defined as

$\displaystyle
Q^{\pi}(s,a;\operatorname{\bm{\theta}}):=\mathbb{E}_{\begin{subarray}{c}a_{i}\sim\pi(\cdot|s_{i})\\\
s_{i+1}\sim\langle\phi(\cdot|s_{i},a_{i}).\operatorname{\bm{\theta}}\rangle\end{subarray}}\left[\sum_{i=0}^{\infty}\gamma^{i}r(s_{i},a_{i})\Big{|}s_{0}=s,a_{0}=a\right].$
(3)

Moreover, we let
$J(\pi;\operatorname{\bm{\theta}}):=\mathop{\mathbb{E}}_{s\sim\mu_{0}}[V^{*}(s;\operatorname{\bm{\theta}}^{*})]$
denote the mean reward achievable for the MDP with parameter
$\operatorname{\bm{\theta}}$ under policy $\pi$ over the initial probability
distribution $\mu_{0}$.

Optimal Value and Regret. We then define the optimal value function to be the
maximum value obtained by a policy:
$V^{*}(s;\operatorname{\bm{\theta}})=\max_{\pi}V^{\pi}(s;\operatorname{\bm{\theta}})$.
In the discounted linear MDP setting (Zhou et al., 2021b), the cumulative
regret $\mathcal{R}(T)$ for the MDP with parameter
$\operatorname{\bm{\theta}}^{*}$ is defined to be the total difference of
value function between the optimal policy and the learned policy $\pi_{t}$,
where

$\displaystyle\mathcal{R}(T):=\sum_{t=1}^{T}\left[V^{*}(s_{t};\operatorname{\bm{\theta}}^{*})-V^{\pi_{t}}(s_{t},\operatorname{\bm{\theta}}^{*})\right],\quad
s_{1}\sim\mu_{0}.$ (4)

Based on the fundamental result that there exists a policy that achieves
optimal value for all states, we use $\pi^{*}(\operatorname{\bm{\theta}})$ to
denote an optimal policy with respect to a given model parameter
$\operatorname{\bm{\theta}}$ as

$\displaystyle\pi^{*}(\operatorname{\bm{\theta}}):=\operatorname*{argmax}_{\pi}J(\pi;\operatorname{\bm{\theta}}).$
(5)

##  4 VBMLE for Linear MDPs

Introduction to the VBMLE Principle. We now introduce the idea behind the
classic value biasing principle. Consider first the certainty equivalence
principle (Kumar & Varaiya, 2015) employing the straightforward  Maximum
Likelihood Estimate (MLE) as

$\displaystyle\widehat{\operatorname{\bm{\theta}}}_{t}:=\operatorname*{argmax}_{\operatorname{\bm{\theta}}\in\mathbb{P}}\left\\{\prod_{i=1}^{t-1}p(s_{i+1}|,s_{i},a_{i};\operatorname{\bm{\theta}})\right\\},$
(6)

That is, at each time step $t$, the learner employs the policy
$\pi_{t}^{\text{MLE}}$ that is optimal for the current estimate
$\widehat{\operatorname{\bm{\theta}}}_{t}$. Under appropriate technical
conditions, it has been shown in (Borkar & Varaiya, 1979) that
$\widehat{\operatorname{\bm{\theta}}}_{t}$ converges almost surely to a random
$\widehat{\operatorname{\bm{\theta}}}_{\infty}$, for which

$\displaystyle
p(s^{\prime}|s,\pi_{\infty}^{\text{MLE}}(s);\widehat{\operatorname{\bm{\theta}}}_{\infty})=p(s^{\prime}|s,\pi_{\infty}^{\text{MLE}}(s);\operatorname{\bm{\theta}}^{*}),\forall
s,s^{\prime}\in\mathcal{S}.$ (7)

This convergence property is called the closed-loop identification property;
it means that asymptotically the transition probabilities resulting from the
application of the policy $\pi_{\infty}^{\text{MLE}}$ are correctly estimated.
An important consequence is that
$J(\pi^{*}(\widehat{\operatorname{\bm{\theta}}}_{\infty});\widehat{\operatorname{\bm{\theta}}}_{\infty})=J(\pi^{*}(\widehat{\operatorname{\bm{\theta}}}_{\infty});\operatorname{\bm{\theta}}^{*})$.
Since $\pi_{\infty}^{\text{MLE}}$ is not necessarily optimal for
$\operatorname{\bm{\theta}}^{*}$, this implies that

$\displaystyle J(\pi^{*}(v);\widehat{\operatorname{\bm{\theta}}}_{\infty})\leq
J(\pi^{*}(\operatorname{\bm{\theta}}^{*});\operatorname{\bm{\theta}}^{*}).$
(8)

The idea of the Value-Biased method is to try to undo the bias in (8) by
adding a bias term that favors parameters with larger optimal total return.
This leads to the principle of Value-Biased Maximum Likelihood Estimate
(VBMLE) originally proposed in the adaptive control literature by (Kumar &
Lin, 1982) as follows:

$\displaystyle\operatorname{\bm{\theta}}^{\textbf{VBMLE}}_{t}:=\operatorname*{argmax}_{\operatorname{\bm{\theta}}\in\mathbb{P}}\left\\{\sum\limits_{i=1}^{t-1}\log
p(s_{i+1}|s_{i},a_{i};\operatorname{\bm{\theta}})+\alpha(t)\cdot
J(\pi^{*}(\operatorname{\bm{\theta}});\operatorname{\bm{\theta}})\right\\},$
(9)

where $\alpha(t)$ is a positive increasing sequence that weights the bias in
favor of parameters with larger total return. VBMLE employs this biasing
method to handle the exploration-exploitation trade-off.

VBMLE for Discounted Linear MDPs. In this paper, we adapt the VBMLE principle
to the RL problem in the linear MDP setting. Specifically, at each time step,
the learner would (i) choose the parameter estimate that maximizes the
regularized log-likelihood plus the value-bias as

$\displaystyle\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}:=\operatorname*{argmax}_{\operatorname{\bm{\theta}}\in\mathbb{P}}\left\\{\sum\limits_{i=1}^{t-1}\log\langle\phi(s_{i+1}|s_{i},a_{i}),\operatorname{\bm{\theta}}\rangle+\frac{\lambda}{2}\lVert\operatorname{\bm{\theta}}\rVert_{2}^{2}+\alpha(t)\cdot
V^{*}(s_{t};\operatorname{\bm{\theta}})\right\\},$ (10)

where $\lambda$ is a positive constant for regularization, and then (ii)
employ an optimal policy with respect to
$\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}$. Notice that the
term $V^{*}(s_{t};\operatorname{\bm{\theta}})$ can be computed by using the
standard Value Iteration presented as Algorithm 2 in Appendix. If there are
multiple maximizers for (10), then one could break the tie arbitrarily. For
clarity, we also summarize the procedure of VBMLE in Algorithm 1.

Algorithm 1 VBMLE for Reinforcement Learning in Linear MDPs

1:Input: $\alpha(t)$

2:for $t=1,2,\cdots$ do

3:
$\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}:=\operatorname*{argmax}_{\operatorname{\bm{\theta}}\in\mathbb{P}}\left\\{\sum\limits_{i=1}^{t-1}\log\langle\phi(s_{i+1}|s_{i},a_{i}),\operatorname{\bm{\theta}}\rangle+\frac{\lambda}{2}\lVert\operatorname{\bm{\theta}}\rVert_{2}^{2}+\alpha(t)\cdot
V^{*}(s_{t};\operatorname{\bm{\theta}})\right\\}$.

4:
$a_{t}=\operatorname*{argmax}\limits_{a\in\mathcal{A}}Q^{*}(s_{t},a;\operatorname{\bm{\theta}}^{\textbf{R}}_{t})$

5:end for

Features of VBMLE for Linear MDPs. We highligh the salient features of the
VBMLE method in Algorithm 1 as follows.

  * •

Computational Efficiency: As mentioned earlier, UCLK (Zhou et al., 2021b)
suffers from high computational complexity as it requires computing an
estimate of the model parameter for each state-action pair in each iteration.
This renders UCLK intractable when either the state space or the action space
is large. By contrast, the VBMLE approach, which applies value-bias to guide
the exploration under the MLE, only requires solving one single maximization
problem for the dynamics model parameter $\operatorname{\bm{\theta}}$ in each
iteration, making it computationally efficient and superior. Accordingly,
VBMLE could serve as a more computationally feasible algorithm for RL in
linear MDPs in practice.

  * •

VBMLE is Parameter-Free: As shown in Algorithm 1, the only parameter required
by VBMLE is $\alpha(t)$, which determines the weight of the value bias. As
will be shown in Section 5, one could simply choose $\alpha(t)=\sqrt{t}$ to
achieve the required regret bound, and moreover this simple choice also leads
to superior empirical regret performance. As a result, VBMLE is parameter-free
and therefore does not require any hyperparameter tuning.

  * •

Distributional Perspective: In contrast to the existing RL methods for linear
MDPs (Ayoub et al., 2020; Zhou et al., 2021a; b; Chen et al., 2022) that aim
to learn the unknown parameter via regression on the value function (or termed
value-targeted regression), the proposed VBMLE takes a distributional
perspective through directly learning the whole collection of transition
probabilities through value-biased maximum likelihood estimation. This
perspective has also been adopted by the prior works on applying VBMLE to the
contextual bandit problems (Hung et al., 2021; Hung & Hsieh, 2023).

Differences Between VBMLE for RL and VBMLE for Bandits. Compared to the
existing works on VBMLE for bandits (Hung et al., 2021; Hung & Hsieh, 2023),
VBMLE for RL presents its own salient challenges:

  * •

Non-Concave Objective Function of VBMLE for Linear MDPs: In the context of
bandits, VBMLE learns by maximizing the log-likelihood of observed rewards
with a bias term that depends on the maximum achievable reward. As the
parametric form of the reward distributions is typically unknown in the bandit
setting, (Hung et al., 2021; Hung & Hsieh, 2023) rely on a surrogate
likelihood function (typically belongs to an exponential family) to estimate
the unknown reward distributions and incorporates a reward bias by adding the
immediate maximum reward. As a result, the resulting objective function still
remains a concave function such that its maximizer either enjoys a closed-form
expression or could be solved efficiently by a gradient-based method. By
contrast, VBMLE for RL manages to optimize the log-likelihood with the value
bias, which ends up as a non-concave function. To address this issue, we take
the following approach: (i) For the theoretical regret analysis, we consider
an oracle that returns the maximizer of the constrained optimization problem
induced by VBMLE. (ii) For the practical implementation, we could incorporate
the value iteration into the optimization subroutine and use a gradient-based
method to numerically find an approximate maximizer of VBMLE.

  * •

Non-Index-Type Policies: Prior works on VBMLE for bandits (Liu et al., 2020;
Hung et al., 2021; Hung & Hsieh, 2023) could convert the original VBMLE into
an index-type policy by using arm-specific estimators. This conversion also
facilitates the regret analysis in (Liu et al., 2020; Hung et al., 2021; Hung
& Hsieh, 2023). However, this approach is not applicable in RL for linear MDPs
since the action and state spaces could typically be very large in practice.
As a result, we are not allowed to reuse a similar analytical framework to
characterize the regret of VBMLE in linear MDPs. To address this, we leverage
a supermartingale approach and use an induction argument to establish the
regret bound, as will be shown in Section 5.

##  5 Regret Analysis

In this section, we formally present the regret analysis of the VBMLE
algorithm. To begin with, we introduce the following useful notations:

$\displaystyle\ell_{t}(\operatorname{\bm{\theta}}):=$
$\displaystyle\sum\limits_{i=1}^{t-1}\log\langle\phi(s_{i+1}|s_{i},a_{i}),\operatorname{\bm{\theta}}\rangle+\frac{\lambda}{2}\lVert\operatorname{\bm{\theta}}\rVert_{2}^{2}$
(11) $\displaystyle\operatorname{\bm{\theta}}^{\text{MLE}}_{t}:=$
$\displaystyle\operatorname*{argmax}\limits_{\operatorname{\bm{\theta}}\in\mathbb{P}}\ell_{t}(\operatorname{\bm{\theta}}),$
(12) $\displaystyle\operatorname{\mathbf{A}}_{t}:=$
$\displaystyle\sum_{i=1}^{t-1}\phi(s_{i+1}|s_{i},a_{i})\phi(s_{i+1}|s_{i},a_{i})^{\top}+\lambda
I.$ (13)

If there are multiple maximizers for (12), then one could break the tie
arbitrarily.

######  Assumption 1.

The following information for the transition probability $P$ is known:

  * •

The set of zero transition
$P_{0}:=\\{(s,a,s^{\prime})|P(s^{\prime}|s,a)=0,\forall
s,s^{\prime}\in\mathcal{S},a\in\mathcal{A}\\}$.

  * •

The lower bound non-zero transition probabilities
$p_{\text{min}}:=\min_{(s,a,s^{\prime})\not\in P_{0}}P(s^{\prime}|s,a)$.

We then redefine the probability simplex based on the above assumption as
follows:

$\displaystyle\mathbb{P}:=\bigg{\\{}\operatorname{\bm{\theta}}\bigg{|}$
$\displaystyle\;p_{\text{min}}\leq\langle\phi(s^{\prime}|s,a),\operatorname{\bm{\theta}}\rangle\leq
1,\forall(s,a,s^{\prime})\not\in P_{0};$
$\displaystyle\;\langle\phi(s^{\prime}|s,a),\operatorname{\bm{\theta}}\rangle=0,\forall(s,a,s^{\prime})\in
P_{0};$
$\displaystyle\;\sum_{s^{\prime}\in\mathcal{S}}\langle\phi(s^{\prime}|s,a),\operatorname{\bm{\theta}}\rangle=1,\forall
s\in\mathcal{S},a\in\mathcal{A}\bigg{\\}}.$ (14)

######  Remark 1.

This assumption suggests that the magnitude of the gradient of the log
probability for the observed transition, denoted as
$\lVert\nabla_{\operatorname{\bm{\theta}}}\log{\langle\phi(s_{i+1}|s_{i},a_{i}),\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rangle}\rVert_{2}$,
is bounded from above. A similar assumption is made in (Kumar & Lin, 1982;
Mete et al., 2021).

###  5.1 Convergence Analysis of MLE in Linear MDPs

To begin with, we highlight the main technical challenges as follows: A
natural idea is to leverage the Azuma–Hoeffding inequality on the log-
likelihood ratio:
$\ell_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})-\ell_{t}(\operatorname{\bm{\theta}}^{*})$,
and then find the distance between
$\operatorname{\bm{\theta}}^{\text{MLE}}_{t}$ and the true parameter
$\operatorname{\bm{\theta}}^{*}$. However, it is known that the stochastic
process induced by the maximum log-likelihood ratio is actually a sub-
martingale (shown in Lemma 6 in Appendix for completeness). To address these
issue, we propose several novel techniques: (i) We first propose to construct
a novel super-martingale (cf. Lemma 1) to characterize the convergence rate of
the MLE in linear MDPs, which could be of independent interest beyond RL
problems. Interestingly, this supermartingale consists of a term that could be
interpreted as the regret in the online portfolio selection problem and
thereby offers an interesting connection between linear MDPss and online
learning. (ii) Built on (i), to utilize Azuma-Hoeffding inequality, we need to
carefully handle the sum of squared supermartingale differences, which do not
have an explicit uniform upper bound and require a more sophisticated
argument.

######  Lemma 1 (Lemma C.2 in (Zhou et al., 2021b), Lemma 11 in (Abbasi-
Yadkori et al., 2011)).

Given any $\\{\phi(s_{t+1}|s_{t},a_{t})\\}_{t=1}^{T}\in\mathbb{R}^{d}$
satisfying that $\lVert\phi(s_{t+1}|s_{t},a_{t})\rVert_{2}\leq L$. For all
$\lambda>0$, we have

$\displaystyle\sum_{t=1}^{T}\lVert\phi(s_{t+1}|s_{t},a_{t})\rVert^{2}_{\operatorname{\mathbf{A}}^{-1}_{t}}\leq
2d\log\left(\frac{d\lambda+TL^{2}}{d}\right).$ (15)

######  Lemma 2.

$\forall s\in\mathcal{S},a\in\mathcal{A},\text{and
}\operatorname{\bm{\theta}}\in\mathbb{P}$, we have
$Q^{*}(s,a,\operatorname{\bm{\theta}})\leq\frac{1}{1-\gamma}$.

Lemma 2 is a direct result of that the reward function is bounded by 1, i.e.,
$R(\cdot,\cdot)\leq 1$.

We proceed to construct two useful helper stochastic processes as follows: For
each $t\in\mathbb{N}$,

$\displaystyle X_{t}$
$\displaystyle:=\ell_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1})-\ell_{t}(\operatorname{\bm{\theta}}^{*})+\sum_{i=1}^{t-1}z_{i},$
(16) $\displaystyle z_{t}$
$\displaystyle:=\ell_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})-\ell_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1}).$
(17)

######  Lemma 3 (Azuma–Hoeffding Inequality).

Suppose $\\{X_{1},X_{2},\cdots\\}$ is a martingale or super-martingale. Then
for all positive integers $t$ and all positive reals $\delta$, we have

$\displaystyle\text{Pr}\left(X_{t}-X_{0}\geq\sqrt{2M_{t}\log{\frac{1}{\delta}}}\right)\leq\delta,$
(18)

where $M_{t}:=\sum_{i=1}^{t}(X_{t}-X_{t-1})^{2}$.

######  Lemma 4.

For all $\lambda\geq 0$, the stochastic process
$\\{L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1})\cdot\prod_{i=1}^{t-1}\text{exp}(-z_{i})\\}$
is a martingale, i.e.,

$\displaystyle\mathbb{E}_{s_{t+1}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}\left[L_{t+1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})\cdot\prod_{i=1}^{t}\text{exp}(-z_{i})\bigg{\rvert}\mathcal{F}_{t}\right]=L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1})\cdot\prod_{i=1}^{t-1}\text{exp}(-z_{i}),$
(19)

where $\mathcal{F}_{t}:=\\{s_{1},a_{1},\cdots,s_{t},a_{t}\\}$ denotes the
causal information up to time $t$.

######  Corollary 1.

For all $\lambda\geq 0$, the stochastic process $\\{X_{t}\\}$ is a
supermartingale, i.e.,

$\displaystyle\mathop{\mathbb{E}}_{s_{t+1}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}\left[\ell_{t+1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})-\ell_{t+1}(\operatorname{\bm{\theta}}^{*})-\sum_{i=1}^{t}z_{i}\bigg{|}\mathcal{F}_{t}\right]\leq\ell_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1})-\ell_{t}(\operatorname{\bm{\theta}}^{*})-\sum_{i=1}^{t-1}z_{i}.$
(20)

This corollary can be proved by applying Jensen’s inequality to (19),

Notably, Corollary 1 offers a useful insight that a supermartingale that
involves the log-likelihood ratio could still be constructed despite that
$\ell_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})-\ell_{t}(\operatorname{\bm{\theta}}^{*})$
is a submartingale. This result generalizes the classic result in (Kumar &
Lin, 1982, Lemma 3) for tabular MDPs to the linear MDP setting, and is also
holds for non-regularized MLE ($\lambda=0$). To establish Theorem 1, we define
a useful quantity $\Delta_{t}$ as

$\Delta_{t}:=\sum_{i=1}^{t-1}z_{i}=\sum_{i=1}^{t-1}\log\bigg{(}{\frac{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{i}}}\bigg{)},$
(21)

where $\phi_{i}(s):=\phi(s|s_{i},a_{i})$ is a shorthand for the feature
vector. In the following lemma, we present an upper bound for $\Delta_{t}$.
Recall that $\lVert\phi(s^{\prime}|s,a)\rVert_{2}\leq L$, for all
$s,s^{\prime}\in\operatorname{\mathcal{S}}$ and
$a\in\operatorname{\mathcal{A}}$.

######  Lemma 5.

For all $\lambda\geq 0$, we have

$\displaystyle\Delta_{t}\leq\frac{8d^{2}}{p^{2}_{\text{min}}}\log\left(\frac{d\lambda+(t-1)L^{2}}{d}\right).$
(22)

######  Remark 2 (Connection between linear MDPs and online learning).

Through $\Delta_{t}$ and Lemma 5, we could build an interesting connection
between MLE in linear MDPs and the Follow-the-Leader algorithm (Gaivoronski &
Stella, 2000) in online learning. The connection is two-fold: (i) MLE in
linear MDPs can be viewed as a variant of online portfolio selection problem:
We find that the MLE optimization problem in linear MDPs takes the same form
as the classic online portfolio selection problem (Hazan et al., 2016).
Specifically, the feature vectors and the dynamics model parameter in linear
MDPs correspond to the price vectors and the asset allocation, respectively.
The main difference of the two problems lies in the feasible set and the
constraints. (ii) Iterative MLE is equivalent to Follow-the-Leader algorithm:
Another interesting connection is that applying MLE in each time step would
correspond to the classic Follow-the-Leader algorithm (Gaivoronski & Stella,
2000). Moreover, the term $\Delta_{t}$ in 22 could be interpreted as the
regret of the Follow-the-Leader algorithm in online learning. With that said,
one could verify that Lemma 5 is consistent with the regret quantified in
(Gaivoronski & Stella, 2000).

Based on the supporting lemmas introduced above, we are ready to formally
present the convergence result of MLE in linear MDPs.

######  Theorem 1.

With probability at least $1-\delta$, we have

$\displaystyle\lVert\operatorname{\bm{\theta}}^{*}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}}\leq\frac{37d^{2}}{p^{2}_{\text{min}}}\cdot\log\left(\frac{d\lambda+tL^{2}}{d}\right)\cdot\log{\frac{1}{\delta}},$
(23)

The complete proof of Theorem 1 is provided in Appendix B.1, and here we
provide a proof sketch:

Proof Sketch. Based on the result in Lemma 1, we can apply Azuma–Hoeffding
inequality presented in Lemma 3 to get the high probability bound of log-
likelihood ratio. There are two main challenges that need to be handled: (i)
The first one is the additional term $\Delta_{t}$, we find a connection to the
analysis of the online portfolio selection problem and use a similar approach
to handle it. (ii) The other one is $M_{t}$, which represents the cumulative
difference of the super-martingale. We adopt a similar approach by considering
a stopping time to ensure that this theorem holds with high probability.

###  5.2 Regret Bound of VBMLE

In this subsection, we formally provide the regret bound of the proposed VBMLE
algorithm.

######  Theorem 2.

For all linear kernel MDP
$\mathcal{M}=\langle\mathcal{S},\mathcal{A},P,R,T,\mu_{0}\rangle$, with
probability at least $1-\frac{1}{T}-3\delta$ and choosing
$\alpha(t)=\sqrt{t}$, VBMLE, proposed in Algorithm 1, has a regret upper bound
that satisfies

$\displaystyle\mathcal{R}(T)=\mathcal{O}\left(\frac{d\sqrt{T}\log{T}}{(1-\gamma)^{2}}\right).$
(24)

The complete proof of Theorem 2 is provided in Appendix B.2, and here we
provide a proof sketch:

Proof Sketch.

  1. 1.

Similar to the analysis of the upper-confidence bound approach, which uses the
concentration inequality to replace the term associated with an optimal
policy, under VBMLE we can replace
$V^{*}(s_{t},\operatorname{\bm{\theta}}^{*})$ by applying the objective
function of VBMLE.

  2. 2.

Then, there are two terms that need to be handled: (i)
$\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}-\operatorname{\bm{\theta}}^{*}\rVert_{\operatorname{\mathbf{A}}_{t}}$
and (ii)
$\lVert\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}-\operatorname{\bm{\theta}}^{*}\rVert_{\operatorname{\mathbf{A}}_{t}}$.
We provide a novel theorem of the confidence ellipsoid of the maximum
likelihood estimator in linear MDPs in Theorem 1 to deal with (i).

  3. 3.

In contrast to the regret analysis presented in (Hung et al., 2021), where the
likelihood of an exponential family distribution was considered, analyzing
regret in the linear MDP setting is more complex due to the absence of simple
closed-form expressions for both $\operatorname{\bm{\theta}}^{\text{MLE}}_{t}$
and $\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}$.
Additionally, in this context, the bias term is not linear with respect to
$\operatorname{\bm{\theta}}$, even if we represent it as
$Q^{*}(s_{t},a_{t};\operatorname{\bm{\theta}})=\langle\sum_{s^{\prime}\in\mathcal{S}}\phi(s^{\prime}|s_{t},a_{t})V^{*}(s_{t},\operatorname{\bm{\theta}}),\operatorname{\bm{\theta}}\rangle$.
To address these challenges, we adopt a novel approach by completing the
square of
$\lVert\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}-\operatorname{\bm{\theta}}^{*}\rVert_{\operatorname{\mathbf{A}}_{t}}$
and successfully overcome the problems mentioned above.

##  6 Numerical Experiments

We demonstrate the empirical performance of VBMLE in terms of both regret and
computation time in this section. we conduct experiments on a simple
environment with discrete state and action spaces. To provide a detailed
understanding of how we transitioned from the tabular MDP to the linear MDP
setting, we have outlined the procedure in the Appendix C.1. The following
result includes a comparison between VBMLE and UCLK, a well-known algorithm
used in the context of infinite horizon linear MDPs. Details regarding the
selected hyperparameters can be found in Appendix C.2.

  * •

Empirical Regret: Figure 1 provides the empirical regret of VBMLE and UCLK
across various sizes of linear MDPs, and the results demonstrate that VBMLE
outperforms UCLK in terms of regret performance. We also provide the standard
deviation of the regret at the final step in Table 2. VBMLE also has better
robustness with an order of magnitude smaller standard deviation than UCLK.

  * •

Computation Time: Theoratically, UCLK requires $U|\mathcal{S}||\mathcal{A}|$
times of solving the optimization problem per step, where $U$ is the times of
value iteration, and VBMLE only requires once. Table 1 displays the
computation time per step within the same environment as depicted in Figure
1(a). It is evident that the computational complexity of UCLK renders the
algorithm impractical in large MDP settings.

  * •

Distance between the learned $\operatorname{\bm{\theta}}$ and
$\operatorname{\bm{\theta}}^{*}$: Figure 2(a) shows the comparison of
$\lVert\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{2}$
and
$\lVert\operatorname{\bm{\theta}}^{\textbf{UCLK}}_{t}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{2}$.
Notably, due to UCLK learning distinct parameter for each state-action pair,
we also plot
$\min_{s,a}\lVert\operatorname{\bm{\theta}}^{\textbf{UCLK}}_{t}(s,a)-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{2}$
and
$\frac{1}{|\mathcal{S}||\mathcal{A}|}\sum_{(s,a)}\lVert\operatorname{\bm{\theta}}^{\textbf{UCLK}}_{t}(s,a)-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{2}$
for UCLK. The result shows that VBMLE learned a more accurate representation
of true parameter $\operatorname{\bm{\theta}}^{*}$.

$\begin{array}[]{c
c}\lx@intercol\mbox{\bf}\hfil\lx@intercol&\lx@intercol\mbox{\bf}\hfil\lx@intercol\\\
\scalebox{0.49}{\includegraphics[width=397.48499pt]{./figures/S_3_A_2.eps}}&\scalebox{0.49}{\includegraphics[width=397.48499pt]{./figures/S_5_A_4.eps}}\\\
\mbox{(a) $|\mathcal{S}|=3,|\mathcal{A}|=2$}&\mbox{(b)
$|\mathcal{S}|=5,|\mathcal{A}|=4$}\end{array}$

Figure 1: Regret averaged over $20$ trials with $T=500$.

$\begin{array}[]{c
c}\lx@intercol\mbox{\bf}\hfil\lx@intercol&\lx@intercol\mbox{\bf}\hfil\lx@intercol\\\
\scalebox{0.49}{\includegraphics[width=397.48499pt]{./figures/diff_theta_learned.eps}}&\scalebox{0.49}{\includegraphics[width=397.48499pt]{./figures/diff_theta_R.eps}}\\\
\mbox{(a) Distance between learned $\theta$ and $\theta^{*}$}&\mbox{(b)
$\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}}$}\end{array}$

Figure 2: Observation of the distance over with $T=2500$. Table 1: Computation time per step of VBMLE and UCLK under different sizes of tabular MDPs. | $|\mathcal{S}|=3,|\mathcal{A}|=2$ | $|\mathcal{S}|=5,|\mathcal{A}|=4$ | $|\mathcal{S}|=15,|\mathcal{A}|=4$
---|---|---|---
UCLK |  $3.135$s |  $49.763$s | $\geq 35\text{hr}$
VBMLE |  $0.793$s |  $2.359$s |  $42.232$s

##  7 Conclusion

We proposed a provably effective and computationally efficient algorithm for
solving linear MDPs, called VBMLE. The sample complexity of the proposed is
proved to be upper bounded by
$\mathcal{O}\left(d\sqrt{T}\log{T}/(1-\gamma)^{2}\right)$. The proposed
algorithm is different from the traditional value-target regression approach
and leverages the MLE with value bias to learn the dynamic. We provide a novel
theorem to show the confidence ellipsoid of MLE and the simulation result
demonstrates the empirical performance of VBMLE.

## References

  * Abbasi-Yadkori et al. (2011) Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  _Advances in neural information processing systems_ , 24:2312–2320, 2011.
  * Auer et al. (2008) Peter Auer, Thomas Jaksch, and Ronald Ortner.  Near-optimal regret bounds for reinforcement learning.  _Advances in neural information processing systems_ , 21, 2008.
  * Ayoub et al. (2020) Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang.  Model-based reinforcement learning with value-targeted regression.  In _International Conference on Machine Learning_ , pp. 463–474. PMLR, 2020.
  * Azar et al. (2017) Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos.  Minimax regret bounds for reinforcement learning.  In _International Conference on Machine Learning_ , pp. 263–272. PMLR, 2017.
  * Borkar & Varaiya (1979) Vivek Borkar and P Varaiya.  Adaptive control of Markov chains, I: Finite parameter set.  _IEEE Transactions on Automatic Control_ , 24(6):953–957, 1979.
  * Cai et al. (2020) Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang.  Provably efficient exploration in policy optimization.  In _International Conference on Machine Learning_ , pp. 1283–1294. PMLR, 2020.
  * Chen et al. (2022) Yuanzhou Chen, Jiafan He, and Quanquan Gu.  On the sample complexity of learning infinite-horizon discounted linear kernel mdps.  In _International Conference on Machine Learning_ , pp. 3149–3183. PMLR, 2022.
  * Gaivoronski & Stella (2000) Alexei A Gaivoronski and Fabio Stella.  Stochastic nonstationary optimization for finding universal portfolios.  _Annals of Operations Research_ , 100:165–188, 2000.
  * Hazan et al. (2016) Elad Hazan et al.  Introduction to online convex optimization.  _Foundations and Trends® in Optimization_ , 2(3-4):157–325, 2016.
  * Hung & Hsieh (2023) Yu-Heng Hung and Ping-Chun Hsieh.  Reward-biased maximum likelihood estimation for neural contextual bandits: A distributional learning perspective.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 37, pp. 7944–7952, 2023.
  * Hung et al. (2021) Yu-Heng Hung, Ping-Chun Hsieh, Xi Liu, and P. R. Kumar.  Reward-biased maximum likelihood estimation for linear stochastic bandits.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , pp. 7874–7882, 2021.
  * Jin et al. (2020) Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In _Conference on Learning Theory_ , pp. 2137–2143. PMLR, 2020.
  * Kumar & Lin (1982) P Kumar and Woei Lin.  Optimal adaptive controllers for unknown markov chains.  _IEEE Transactions on Automatic Control_ , 27(4):765–774, 1982.
  * Kumar & Varaiya (2015) PR Kumar and Pravin Varaiya.  _Stochastic Systems: Estimation, Identification, and Adaptive Control_ , volume 75.  SIAM, 2015.
  * Liu et al. (2020) Xi Liu, Ping-Chun Hsieh, Yu Heng Hung, Anirban Bhattacharya, and P. R. Kumar.  Exploration Through Reward Biasing: Reward-Biased Maximum Likelihood Estimation for Stochastic Multi-Armed Bandits.  In _International Conference on Machine Learning_ , pp. 6248–6258. PMLR, 2020.
  * Mete et al. (2021) Akshay Mete, Rahul Singh, Xi Liu, and P. R. Kumar.  Reward biased maximum likelihood estimation for reinforcement learning.  In _Learning for Dynamics and Control_ , pp. 815–827, 2021.
  * Mete et al. (2022) Akshay Mete, Rahul Singh, and P. R. Kumar.  Augmented RBMLE-UCB Approach for Adaptive Control of Linear Quadratic Systems.  In _Advances in Neural Information Processing Systems_ , 2022.
  * Modi et al. (2020) Aditya Modi, Nan Jiang, Ambuj Tewari, and Satinder Singh.  Sample complexity of reinforcement learning using linearly combined model ensembles.  In _International Conference on Artificial Intelligence and Statistics_ , pp. 2010–2020. PMLR, 2020.
  * Wang et al. (2020) Ruosong Wang, Russ R Salakhutdinov, and Lin Yang.  Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension.  _Advances in Neural Information Processing Systems_ , 33:6123–6135, 2020.
  * Wang et al. (2019) Yining Wang, Ruosong Wang, Simon S Du, and Akshay Krishnamurthy.  Optimism in reinforcement learning with generalized linear function approximation.  _arXiv preprint arXiv:1912.04136_ , 2019.
  * Yang & Wang (2019) Lin Yang and Mengdi Wang.  Sample-optimal parametric q-learning using linearly additive features.  In _International Conference on Machine Learning_ , pp. 6995–7004. PMLR, 2019.
  * Zanette et al. (2020) Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill.  Learning near optimal policies with low inherent bellman error.  In _International Conference on Machine Learning_ , pp. 10978–10989. PMLR, 2020.
  * Zhou et al. (2021a) Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari.  Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.  In _Conference on Learning Theory_ , pp. 4532–4576. PMLR, 2021a.
  * Zhou et al. (2021b) Dongruo Zhou, Jiafan He, and Quanquan Gu.  Provably efficient reinforcement learning for discounted mdps with feature mapping.  In _International Conference on Machine Learning_ , pp. 12793–12802. PMLR, 2021b.

##  Appendix A Proofs of the Supporting Lemmas

To begin with, we provide several useful definitions as follows. Define the
likelihood ratio as

$L_{t}(\operatorname{\bm{\theta}}):=\prod_{i=1}^{t-1}\frac{\text{Pr}(s_{i+1}|s_{i},a_{i};\operatorname{\bm{\theta}})}{\text{Pr}(s_{i+1}|s_{i},a_{i};\operatorname{\bm{\theta}}^{*})}\cdot\text{exp}\left(\frac{\lambda}{2}\lVert\operatorname{\bm{\theta}}\rVert_{2}^{2}\right).$
(25)

######  Lemma 6.

$\displaystyle
L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t}):=\max_{\operatorname{\bm{\theta}}\in\mathbb{P}}L_{t}(\operatorname{\bm{\theta}})$
(26)

is a sub-martingale.

###### Proof.

Given the causal information $\mathcal{F}_{t}$, we have

$\displaystyle\mathbb{E}_{s_{t+1}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}\left[\max_{\operatorname{\bm{\theta}}\in\mathbb{P}}L_{t+1}(\operatorname{\bm{\theta}})\big{\rvert}\mathcal{F}_{t}\right]\geq$
$\displaystyle\max_{\operatorname{\bm{\theta}}\in\mathbb{P}}\mathbb{E}_{s_{t+1}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}\left[L_{t+1}(\operatorname{\bm{\theta}})\big{\rvert}\mathcal{F}_{t}\right]$
(27) $\displaystyle=$
$\displaystyle\max_{\operatorname{\bm{\theta}}\in\mathbb{P}}\left\\{\sum_{s^{\prime}\in\mathcal{S}}\text{Pr}(s^{\prime}|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})\cdot\frac{\text{Pr}(s^{\prime}|s_{t},a_{t};\operatorname{\bm{\theta}})}{\text{Pr}(s^{\prime}|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}\cdot
L_{t}(\operatorname{\bm{\theta}})\right\\}$ (28) $\displaystyle=$
$\displaystyle L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t}),$ (29)

where (27) holds by
$\max\limits_{\operatorname{\bm{\theta}}\in\mathbb{P}}L_{t+1}(\operatorname{\bm{\theta}})\geq
L_{t+1}(\operatorname{\bm{\theta}}^{\prime})$, and

$\displaystyle\operatorname{\bm{\theta}}^{\prime}:=\operatorname*{argmax}\limits_{\operatorname{\bm{\theta}}\in\mathbb{P}}\left\\{\mathbb{E}_{s_{t+1}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}\left[L_{t+1}(\operatorname{\bm{\theta}})\big{\rvert}\mathcal{F}_{t}\right]\right\\}.$
(30)

∎

######  Remark 3.

The lemma shows that it is not able to apply Azuma–Hoeffding inequality on the
maximum likelihood ratio. However, we can still add an additional term to
construct a supermartingale:

$\displaystyle\mathbb{E}_{s_{t+1}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}\left[\max_{\operatorname{\bm{\theta}}\in\mathbb{P}}L_{t+1}(\operatorname{\bm{\theta}})\cdot\prod_{i=1}^{t}\left(\sum_{s^{\prime}\in\mathcal{S}}h_{t}(s^{\prime})\right)^{-1}\big{\rvert}\mathcal{F}_{t}\right]=L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})\cdot\prod_{i=1}^{t-1}\left(\sum_{s^{\prime}\in\mathcal{S}}h_{t}(s^{\prime})\right)^{-1}$
(31)

where

$\displaystyle
h_{t}(s^{\prime}):=\max_{\operatorname{\bm{\theta}}\in\mathbb{P}}\left\\{\frac{L_{t}(\operatorname{\bm{\theta}})}{L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})}\cdot\text{Pr}(s^{\prime}|s_{t},a_{t};\operatorname{\bm{\theta}})\right\\}.$
(32)

It’s important to note that there are two primary challenges when dealing with
$h_{t}(s^{\prime})$:

  * •

Dependency on state space size: The first challenge arises from the fact that
$\sum_{s^{\prime}\in\mathcal{S}}h_{t}(s^{\prime})$ exhibits a dependency on
the size of the state space. This dependence can complicate the regret
analysis, especially in cases where the state space is large.

  * •

State-dependent maximization: The second challenge is related to the
maximization inside $h_{t}(s^{\prime})$, which is also influenced by the
specific state $s^{\prime}$ under consideration. Formally, the absence of a
closed-form expression for this maximization makes it challenging to conduct a
straightforward analysis.

To address the above two challenges, we then introduce a new supermartingale
associate to the likelihood ratio evaluated on the previous step’s maximum
likelihood estimator.

###  A.1 Proof of Lemma 1

Recall that

$\displaystyle X_{t}$
$\displaystyle:=\ell_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1})-\ell_{t}(\operatorname{\bm{\theta}}^{*})+\sum_{i=1}^{t-1}z_{i},$
(33) $\displaystyle z_{t}$
$\displaystyle:=\ell_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})-\ell_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1}).$
(34)

For ease of exposition, we restate Lemma 1 as follows.

######  Lemma.

The stochastic process
$\\{L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1})\cdot\prod_{i=1}^{t-1}\text{exp}(-z_{i})\\}$
is a martingale, i.e.,

$\displaystyle\mathbb{E}_{s_{t+1}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}\left[L_{t+1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})\cdot\prod_{i=1}^{t}\text{exp}(-z_{i})\bigg{\rvert}\mathcal{F}_{t}\right]=L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1})\cdot\prod_{i=1}^{t-1}\text{exp}(-z_{i}),$
(35)

where $\mathcal{F}_{t}:=\\{s_{1},a_{1},\cdots,s_{t},a_{t}\\}$ denotes the
causal information up to time $t$.

###### Proof.

Recall the definition of likelihood ratio in (25). We have

$\displaystyle\mathbb{E}_{s_{t+1}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}\left[L_{t+1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})\cdot\prod_{i=1}^{t}\text{exp}(-z_{i})\bigg{\rvert}\mathcal{F}_{t}\right]$
$\displaystyle=$
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}}\text{Pr}(s^{\prime}|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})\cdot
L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})\cdot\frac{\text{Pr}(s^{\prime}|s_{t},a_{t};\operatorname{\bm{\theta}}^{\text{MLE}}_{t})}{\text{Pr}(s^{\prime}|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}\cdot\prod_{i=1}^{t}\text{exp}(-z_{i}),$
(36) $\displaystyle=$ $\displaystyle
L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})\cdot\prod_{i=1}^{t}\text{exp}(-z_{i}),$
(37) $\displaystyle=$ $\displaystyle
L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1})\cdot\prod_{i=1}^{t-1}\text{exp}(-z_{i}),$
(38)

where (36) holds by the definition of the expectation, (37) holds due to
$\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\in\mathbb{P}$ and
$\mathcal{F}_{t}$-measurability, and (38) holds by
$\exp(z_{t})=\frac{L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})}{L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1})}$.
We complete this proof.  ∎

###  A.2 Proof of Lemma 5

Recall the definition of $\Delta_{t}$ from (21) as

$\Delta_{t}:=\sum_{i=1}^{t-1}\log{\bigg{(}\frac{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{i}}\bigg{)}}+\frac{\lambda}{2}\left(\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert_{2}^{2}-\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{0}\rVert_{2}^{2}\right),$
(39)

where $\phi_{i}(s):=\phi(s|s_{i},a_{i})$ is a shorthand for the feature
vector. For ease of exposition, we restate Lemma 5 as follows.

######  Lemma.

For all $\lambda\geq 0$, we have that

$\displaystyle\Delta_{t}\leq\frac{8d^{2}}{p^{2}_{\text{min}}}\log\left(\frac{d\lambda+(t-1)L^{2}}{d}\right).$
(40)

###### Proof.

To begin with, we have

$\displaystyle\Delta_{t+1}=$
$\displaystyle\sum_{i=1}^{t-1}\log{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}}-\sum_{i=1}^{t-1}\log{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{i}}$
$\displaystyle+\frac{\lambda}{2}\left(\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}\rVert_{2}^{2}-\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{0}\rVert_{2}^{2}\right)+\log{\frac{\phi_{t}(s_{t+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}}{\phi_{t}(s_{t+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}}$
(41) $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{t-1}\log{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}-\sum_{i=1}^{t-1}\log{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{i}}$
$\displaystyle+\frac{\lambda}{2}\left(\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert_{2}^{2}-\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{0}\rVert_{2}^{2}\right)+\log{\frac{\phi_{t}(s_{t+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}}{\phi_{t}(s_{t+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}}$
(42) $\displaystyle\leq$
$\displaystyle\sum_{i=1}^{t-1}\log{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}-\sum_{i=1}^{t-1}\log{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{i}}$
$\displaystyle+\frac{\lambda}{2}\left(\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert_{2}^{2}-\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{0}\rVert_{2}^{2}\right)+\frac{\langle\phi_{t}(s_{t+1}),\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rangle}{\phi_{t}(s_{t+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}$
(43) $\displaystyle\leq$
$\displaystyle\Delta_{t}+\Big{\lVert}\frac{\phi_{t}(s_{t+1})}{\phi_{t}(s_{t+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}\Big{\rVert}_{\operatorname{\mathbf{A}}^{-1}}\cdot\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert_{\operatorname{\mathbf{A}}},$
(44)

where (42) holds by
$\operatorname{\bm{\theta}}^{\text{MLE}}_{t}=\operatorname*{argmax}_{\operatorname{\bm{\theta}}\in\mathbb{P}}\ell_{t}(\operatorname{\bm{\theta}})$,
(43) holds by the fact that $\log(x+1)\leq x$, and (44) holds by
Cauchy–Schwarz inequality under any positive definite matrix
$\operatorname{\mathbf{A}}$. To handle
$\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert_{\operatorname{\mathbf{A}}}$,
we start from the fact that
$\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}=\operatorname*{argmax}_{\operatorname{\bm{\theta}}\in\mathbb{P}}\ell_{t+1}(\operatorname{\bm{\theta}})$,
which leads to the following inequality:

$\displaystyle 0\leq$
$\displaystyle\ell_{t+1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1})-\ell_{t+1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})$
(45) $\displaystyle=$
$\displaystyle(\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t})^{\top}\nabla_{\operatorname{\bm{\theta}}}\left(\ell_{t}(\operatorname{\bm{\theta}})+\log\phi_{t}(s_{t+1})^{\top}\operatorname{\bm{\theta}}\right)\big{\rvert}_{\operatorname{\bm{\theta}}=\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}-\frac{1}{2}\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert^{2}_{\operatorname{\mathbf{A}}_{t+1}(\operatorname{\bm{\theta}}^{\prime}_{t+1})}$
(46) $\displaystyle\leq$
$\displaystyle\frac{\phi_{t}(s_{t+1})^{\top}}{\phi_{t}(s_{t+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t})-\frac{1}{2}\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert^{2}_{\operatorname{\mathbf{A}}_{t+1}(\operatorname{\bm{\theta}}^{\prime}_{t+1})},$
(47)

where (46) holds by Taylor’s theorem and
$\operatorname{\mathbf{A}}_{t+1}(\operatorname{\bm{\theta}}^{\prime}_{t+1}):=-\nabla^{2}_{\operatorname{\bm{\theta}}}\ell_{t+1}(\operatorname{\bm{\theta}})|_{\operatorname{\bm{\theta}}=\operatorname{\bm{\theta}}^{\prime}_{t+1}}$
($\operatorname{\bm{\theta}}^{\prime}_{t+1}$ is some convex combination
between $\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}$ and
$\operatorname{\bm{\theta}}^{\text{MLE}}_{t}$), and (47) holds due to the
necessary condition of optimality for constrained problem as
$\nabla_{\operatorname{\bm{\theta}}}\ell_{t}(\operatorname{\bm{\theta}})|_{\operatorname{\bm{\theta}}=\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}^{\top}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t})\leq
0$. Then, by reordering (47) and applying Cauchy–Schwarz inequality, we have

$\displaystyle\frac{1}{2}\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t+1}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert_{\operatorname{\mathbf{A}}_{t+1}(\operatorname{\bm{\theta}}^{\prime}_{t+1})}\leq\lVert\frac{\phi_{t}(s_{t+1})^{\top}}{\phi_{t}(s_{t+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}\rVert_{\operatorname{\mathbf{A}}^{-1}_{t+1}(\operatorname{\bm{\theta}}^{\prime}_{t+1})}.$
(48)

By plugging
$\operatorname{\mathbf{A}}=\operatorname{\mathbf{A}}_{t+1}(\operatorname{\bm{\theta}}^{\prime}_{t+1})$
into (44) as well as combining (44) and (48), we have

$\displaystyle\Delta_{t+1}\leq$
$\displaystyle\Delta_{t}+2\Big{\lVert}\frac{\phi_{t}(s_{t+1})}{\phi_{t}(s_{t+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}\Big{\rVert}^{2}_{\operatorname{\mathbf{A}}^{-1}_{t+1}(\operatorname{\bm{\theta}}^{\prime}_{t+1})},$
(49) $\displaystyle\leq$
$\displaystyle\Delta_{t}+\frac{2}{p^{2}_{\text{min}}}\cdot\lVert\phi_{t}(s_{t+1})\rVert^{2}_{\operatorname{\mathbf{A}}^{-1}_{t}},$
(50)

where (50) holds by Assumption 1 and
$\operatorname{\mathbf{A}}^{-1}_{t+1}(\operatorname{\bm{\theta}}^{\prime}_{t+1})\preceq\operatorname{\mathbf{A}}^{-1}_{t+1}\preceq\operatorname{\mathbf{A}}^{-1}_{t}$
given the definition in (13). Then, by applying Lemma 1 to (50), we have

$\displaystyle\Delta_{t+1}\leq\frac{8d^{2}}{p^{2}_{\text{min}}}\log\left(\frac{d\lambda+tL^{2}}{d}\right),\quad\forall
t\in\mathbb{N}.$ (51)

∎

##  Appendix B Proofs of the Main Theorems

###  B.1 Proof of Theorem 1

For ease of exposition, we restate Theorem 1 as follows.

######  Theorem.

At each time $t$, with probability at least $1-\delta$, we have

$\displaystyle\lVert\operatorname{\bm{\theta}}^{*}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}}\leq\beta_{t},$
(52)

where
$\beta_{t}:=\frac{37d^{2}}{p^{2}_{\text{min}}}\cdot\log\left(\frac{d\lambda+tL^{2}}{d}\right)\cdot\log{\frac{1}{\delta}}$.

###### Proof.

By Corollary 1 and Azuma–Hoeffding inequality in Lemma 3, we have

$\displaystyle\text{Pr}\left(\ell_{t+1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})-\ell_{t+1}(\operatorname{\bm{\theta}}^{*})-\sum_{i=1}^{t}z_{i}\geq\sqrt{2M_{t}\log{\frac{1}{\delta}}}\right)\leq\delta,$
(53)

where
$M_{t}:=\sum_{i=1}^{t}\left(\log{L_{i+1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{i})}-\log{L_{i}(\operatorname{\bm{\theta}}^{\text{MLE}}_{i-1})}-z_{i}\right)^{2}$.

  * •

Regarding
$\ell_{t+1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})-\ell_{t+1}(\operatorname{\bm{\theta}}^{*})$,
we have

$\displaystyle\ell_{t+1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})-\ell_{t+1}(\operatorname{\bm{\theta}}^{*})=$
$\displaystyle\;\ell_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})-\ell_{t}(\operatorname{\bm{\theta}}^{*})+\log{\frac{\phi(s_{t+1}|s_{t},a_{t})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}{\phi(s_{t+1}|s_{t},a_{t})^{\top}\operatorname{\bm{\theta}}^{*}}}$
(54) $\displaystyle\geq$
$\displaystyle\;\frac{1}{2}\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{-\nabla^{2}_{\operatorname{\bm{\theta}}}\ell_{t}(\operatorname{\bm{\theta}})|_{\operatorname{\bm{\theta}}=\operatorname{\bm{\theta}}^{\prime}}}+\log{\frac{\phi(s_{t+1}|s_{t},a_{t})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}{\phi(s_{t+1}|s_{t},a_{t})^{\top}\operatorname{\bm{\theta}}^{*}}}$
(55) $\displaystyle\geq$
$\displaystyle\;\frac{1}{2}\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}}-\frac{1}{p_{\text{min}}},$
(56)

where (55) holds by Taylor’s theorem, the necessary condition of optimality
for constrained problems
$\nabla_{\operatorname{\bm{\theta}}}\ell_{t}(\operatorname{\bm{\theta}})|_{\operatorname{\bm{\theta}}=\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}^{\top}(\operatorname{\bm{\theta}}^{*}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t})\leq
0$, and $\operatorname{\bm{\theta}}^{\prime}$ is some convex combination of
$\operatorname{\bm{\theta}}^{\text{MLE}}_{t}$ and
$\operatorname{\bm{\theta}}^{*}$, and (56) holds by
$\operatorname{\mathbf{A}}_{t}\preceq-\nabla^{2}_{\operatorname{\bm{\theta}}}\ell_{t}(\operatorname{\bm{\theta}})|_{\operatorname{\bm{\theta}}=\operatorname{\bm{\theta}}^{\prime}}$,
$\operatorname{\bm{\theta}}^{*}\in\mathbb{P}$ and Assumption 1.

  * •

For $\sum_{i=1}^{t}z_{i}$, denoting $\phi_{t}(s):=\phi(s|s_{t},a_{t})$, we
have

$\displaystyle\sum_{i=1}^{t}z_{i}=$
$\displaystyle\log\left(\frac{L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})}{L_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1})}\cdot\frac{L_{t-1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1})}{L_{t-1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t-2})}\cdot\cdots\cdot\frac{L_{1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{1})}{L_{1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{0})}\right)$
(57)
$\displaystyle=\log\left(\frac{\phi_{t-1}(s_{t})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\cdot\phi_{t-2}(s_{t-1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\cdot\cdots}{\phi_{t-1}(s_{t})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t-1}\cdot\phi_{t-2}(s_{t-1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t-2}\cdot\cdots}\right)+\frac{\lambda}{2}\left(\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert_{2}^{2}-\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{0}\rVert_{2}^{2}\right)$
(58)
$\displaystyle=\sum_{i=1}^{t-1}\log{\frac{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{i}}}+\frac{\lambda}{2}\left(\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert_{2}^{2}-\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{0}\rVert_{2}^{2}\right)$
(59)
$\displaystyle\leq\frac{8d^{2}}{p^{2}_{\text{min}}}\log\left(\frac{d\lambda+(t-1)L^{2}}{d}\right),$
(60)

where (60) holds by Lemma 5.

  * •

For $M_{t}$, we have

$\displaystyle M_{t}=$
$\displaystyle\sum_{i=1}^{t}\left(\log{L_{i+1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{i})}-\log{L_{i}(\operatorname{\bm{\theta}}^{\text{MLE}}_{i-1})}-z_{i}\right)^{2}$
(61) $\displaystyle=$
$\displaystyle\sum_{i=1}^{t}\left(\log{\frac{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{\text{MLE}}_{i}}{\phi_{i}(s_{i+1})^{\top}\operatorname{\bm{\theta}}^{*}}}\right)^{2}$
(62) $\displaystyle\leq$
$\displaystyle\frac{1}{p^{2}_{\text{min}}}\sum_{i=1}^{t}\lVert\phi_{i}(s_{i+1})\rVert^{2}_{\operatorname{\mathbf{A}}^{-1}_{i}}\cdot\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{i}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{\operatorname{\mathbf{A}}_{i}}$
(63) $\displaystyle\leq$ $\displaystyle\frac{\max_{i\leq
t}\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{i}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{\operatorname{\mathbf{A}}_{i}}}{p^{2}_{\text{min}}}\sum_{i=1}^{t}\lVert\phi_{i}(s_{i+1})\rVert^{2}_{\operatorname{\mathbf{A}}^{-1}_{i}}$
(64) $\displaystyle\leq$ $\displaystyle\max_{i\leq
t}\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{i}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{\operatorname{\mathbf{A}}_{i}}\cdot\frac{2d}{p^{2}_{\text{min}}}\cdot\log\left(\frac{d\lambda+tL^{2}}{d}\right)$
(65)

where (63) holds by Assumption 1 and Cauchy–Schwarz inequality, and (65) holds
by Lemma 1.

Then, combining (56), (60) and (65) into (53), for all $t$, we have

$\displaystyle\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}}\leq$
$\displaystyle\frac{1}{p_{\text{min}}}+\frac{8d^{2}}{p^{2}_{\text{min}}}\log\left(\frac{d\lambda+tL^{2}}{d}\right)$
$\displaystyle+\max_{i\leq
t}\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{i}-\operatorname{\bm{\theta}}^{*}\rVert_{\operatorname{\mathbf{A}}_{i}}\cdot\sqrt{\frac{4d}{p^{2}_{\text{min}}}\cdot\log\left(\frac{d\lambda+tL^{2}}{d}\right)\cdot\log{\frac{1}{\delta}}}$
(66)

holds with probability at least $1-\delta$. Letting
$k_{t}:=\operatorname*{argmax}_{i\leq
t}\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{i}-\operatorname{\bm{\theta}}^{*}\rVert_{\operatorname{\mathbf{A}}_{i}}\leq
t$ and denoting the following indicator functions:

$\displaystyle
J:=\mathbbm{1}\left\\{\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}}\geq\frac{37d^{2}}{p^{2}_{\text{min}}}\cdot\log\left(\frac{d\lambda+tL^{2}}{d}\right)\cdot\log{\frac{1}{\delta}}\right\\}$
(67) $\displaystyle D_{i}:=\mathbbm{1}\\{k_{t}=i\\},\forall i\leq t,$ (68)

Then, by (66) and the definition of $k_{t}$, we have

$\displaystyle\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}}\leq$
$\displaystyle\;\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{k_{t}}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{\operatorname{\mathbf{A}}_{k_{t}}}$
(69) $\displaystyle\leq$
$\displaystyle\;\frac{1}{p_{\text{min}}}+\frac{8d^{2}}{p^{2}_{\text{min}}}\log\left(\frac{d\lambda+k_{t}L^{2}}{d}\right)$
$\displaystyle\;+\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{k_{t}}-\operatorname{\bm{\theta}}^{*}\rVert_{\operatorname{\mathbf{A}}_{k_{t}}}\cdot\sqrt{\frac{4d}{p^{2}_{\text{min}}}\cdot\log\left(\frac{d\lambda+k_{t}L^{2}}{d}\right)\cdot\log{\frac{1}{\delta}}}$
(70)

holds with probability at least $1-\delta$, which implies

$\displaystyle\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}}\leq\frac{37d^{2}}{p^{2}_{\text{min}}}\cdot\log\left(\frac{d\lambda+tL^{2}}{d}\right)\cdot\log{\frac{1}{\delta}}:=\beta_{t}.$
(71)

By the fact that $\sum_{i=1}^{t}\text{Pr}(D_{i}=1)=1$ and
$\text{Pr}(J|D_{i}=1)\leq\delta,\forall i\in[t]$ shown above, we have

$\displaystyle\text{Pr}(J)=\sum_{i=1}^{t}\text{Pr}(D_{i}=1)\text{Pr}(J|D_{i}=1)\leq\delta.$
(72)

We complete the proof. ∎

######  Lemma.

At each time $t$, with probability at least $1-\delta$, we have

$\displaystyle\nabla_{\operatorname{\bm{\theta}}}\ell_{t}(\operatorname{\bm{\theta}})|_{\operatorname{\bm{\theta}}=\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}^{\top}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t}-\operatorname{\bm{\theta}}^{*})\leq\beta^{\prime}_{t},$
(73)

where
$\beta^{\prime}_{t}:=\frac{22d^{2}}{p^{2}_{\text{min}}}\log\left(\frac{d\lambda+tL^{2}}{d}\right)\cdot\max\\{1,\log{\frac{1}{\delta}}\\}$.

###### Proof.

This lemma can be proved by the same argument as Theorem 1. By the fact that
$\ell_{t+1}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})-\ell_{t+1}(\operatorname{\bm{\theta}}^{*})\geq\nabla_{\operatorname{\bm{\theta}}}\ell_{t}(\operatorname{\bm{\theta}})|_{\operatorname{\bm{\theta}}=\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}^{\top}(\operatorname{\bm{\theta}}^{*}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t})-\frac{1}{p_{\text{min}}}$,
(53), (60), and (65), we also have

$\displaystyle\nabla_{\operatorname{\bm{\theta}}}\ell_{t}(\operatorname{\bm{\theta}})|_{\operatorname{\bm{\theta}}=\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}^{\top}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t}-\operatorname{\bm{\theta}}^{*})\leq$
$\displaystyle\frac{1}{p_{\text{min}}}+\frac{8d^{2}}{p^{2}_{\text{min}}}\log\left(\frac{d\lambda+k_{t}L^{2}}{d\lambda}\right)$
$\displaystyle+\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{k_{t}}-\operatorname{\bm{\theta}}^{*}\rVert_{\operatorname{\mathbf{A}}_{k_{t}}}\cdot\sqrt{\frac{4d}{p^{2}_{\text{min}}}\cdot\log\left(\frac{d\lambda+k_{t}L^{2}}{d}\right)\cdot\log{\frac{1}{\delta}}}$
(74) $\displaystyle\leq$
$\displaystyle\frac{22d^{2}}{p^{2}_{\text{min}}}\log\left(\frac{d\lambda+tL^{2}}{d}\right)\cdot\max\\{1,\log{\frac{1}{\delta}}\\}:=\beta^{\prime}_{t},$
(75)

where (75) holds by plugging (71) into (74). ∎

###  B.2 Proof of Theorem 2

Recalling that

$\displaystyle\beta_{t}:=\frac{37d^{2}}{p^{2}_{\text{min}}}\cdot\log\left(\frac{d\lambda+tL^{2}}{d}\right)\cdot\log{\frac{1}{\delta}}$
(76)
$\displaystyle\beta^{\prime}_{t}=\frac{22d^{2}}{p^{2}_{\text{min}}}\log\left(\frac{d\lambda+tL^{2}}{d}\right)\cdot\max\\{1,\log{\frac{1}{\delta}}\\},$
(77)

we then state the detailed form of the regret upper bound.

######  Theorem.

For all linear kernel MDP
$\mathcal{M}=\langle\mathcal{S},\mathcal{A},P,R,T,\mu_{0}\rangle$, with
probability at least $1-\frac{1}{T}-\delta$, VBMLE, proposed in Algorithm 1,
has regret upper bound satisfies that

$\displaystyle\mathcal{R}(T)=$
$\displaystyle\sum_{t=1}^{T}\left(V^{*}(s_{t},\operatorname{\bm{\theta}}^{*})-V^{\pi_{t}}(s_{t};\operatorname{\bm{\theta}}^{*})\right)$
$\displaystyle\leq$
$\displaystyle\left(\frac{\beta_{T}}{2p^{2}_{\text{min}}}+\beta^{\prime}_{T}\right)\cdot\sum_{t=1}^{T}\frac{1}{\alpha(t)}+\frac{4\gamma}{1-\gamma}\sqrt{T\log{\frac{1}{\delta}}}$
$\displaystyle+\frac{2\gamma}{p_{\text{min}}(1-\gamma)^{2}}\sqrt{T\log{\frac{1}{\delta}}}+\frac{\sqrt{\beta_{T}}\gamma}{p_{\text{min}}(1-\gamma)^{2}}\left(1+\sqrt{T\cdot
2d\log\left(\frac{d\lambda+TL^{2}}{d}\right)}\right)$
$\displaystyle+\frac{2d\cdot\alpha(T)}{(1-\gamma)}\cdot\log\left(\frac{d\lambda+TL^{2}}{d}\right).$
(78)

By choosing $\alpha(t)=\sqrt{t}$, we have
$\mathcal{R}(T)=\mathcal{O}(d\sqrt{T}\log{T}/(1-\gamma)^{2})$.

###### Proof.

By the definition of the cumulative regret in (4), we have

$\displaystyle\mathcal{R}(T)=$
$\displaystyle\sum_{t=1}^{T}\left(V^{*}(s_{t},\operatorname{\bm{\theta}}^{*})-V^{\pi_{t}}(s_{t};\operatorname{\bm{\theta}}^{*})\right)$
(79) $\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T}\left(V^{*}(s_{t},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})-V^{\pi_{t}}(s_{t};\operatorname{\bm{\theta}}^{*})+\frac{\ell_{t}(\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})-\ell_{t}(\operatorname{\bm{\theta}}^{*})}{\alpha(t)}\right)$
(80) $\displaystyle=$
$\displaystyle\mathcal{R}^{\prime}(T)+\sum_{t=1}^{T}\frac{\ell_{t}(\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})-\ell_{t}(\operatorname{\bm{\theta}}^{*})}{\alpha(t)}$
(81)

where (80) holds due to the following inequality:

$\displaystyle\ell_{t}(\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})+\alpha(t)V^{*}(s_{t};\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})\geq\ell_{t}(\operatorname{\bm{\theta}}^{*})+\alpha(t)V^{*}(s_{t};\operatorname{\bm{\theta}}^{*})$
(82) $\displaystyle\implies$ $\displaystyle
V^{*}(s_{t};\operatorname{\bm{\theta}}^{*})\leq
V^{*}(s_{t};\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})+\frac{\ell_{t}(\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})-\ell_{t}(\operatorname{\bm{\theta}}^{*})}{\alpha(t)},$
(83)

and (81) holds by
$\mathcal{R}^{\prime}(T):=\sum^{T}_{t=1}(V^{*}(s_{t},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})-V^{\pi_{t}}(s_{t};\operatorname{\bm{\theta}}^{*}))$.
For the term
$\sum_{t=1}^{T}(\ell_{t}(\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})-\ell_{t}(\operatorname{\bm{\theta}}^{*}))/\alpha(t)$,
we have

$\displaystyle\sum_{t=1}^{T}\frac{\ell_{t}(\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})-\ell_{t}(\operatorname{\bm{\theta}}^{*})}{\alpha(t)}=$
$\displaystyle\sum_{t=1}^{T}\frac{\ell_{t}(\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})-\ell_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})}{\alpha(t)}+\sum_{t=1}^{T}\frac{\ell_{t}(\operatorname{\bm{\theta}}^{\text{MLE}}_{t})-\ell_{t}(\operatorname{\bm{\theta}}^{*})}{\alpha(t)}$
(84) $\displaystyle\leq$
$\displaystyle-\sum_{t=1}^{T}\frac{1}{2\alpha(t)}\lVert\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}(\operatorname{\bm{\theta}}^{\prime})}+\sum_{t=1}^{T}\frac{1}{2\alpha(t)}\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}(\operatorname{\bm{\theta}}^{\prime\prime})}$
$\displaystyle-\sum_{t=1}^{T}\frac{\nabla_{\operatorname{\bm{\theta}}}\ell_{t}(\operatorname{\bm{\theta}})|_{\operatorname{\bm{\theta}}=\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}^{\top}(\operatorname{\bm{\theta}}^{*}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t})}{\alpha(t)}$
(85) $\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T}\frac{1}{2p^{2}_{\text{min}}\alpha(t)}\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}-\operatorname{\bm{\theta}}^{*}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}}-\sum_{t=1}^{T}\frac{\nabla_{\operatorname{\bm{\theta}}}\ell_{t}(\operatorname{\bm{\theta}})|_{\operatorname{\bm{\theta}}=\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}^{\top}(\operatorname{\bm{\theta}}^{*}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t})}{\alpha(t)}$
$\displaystyle-\sum_{t=1}^{T}\frac{1}{2\alpha(t)}\lVert\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}}$
(86) $\displaystyle\leq$
$\displaystyle\left(\frac{\beta_{T}}{2p^{2}_{\text{min}}}+\beta^{\prime}_{T}\right)\cdot\sum_{t=1}^{T}\frac{1}{\alpha(t)}-\sum_{t=1}^{T}\frac{1}{2\alpha(t)}\lVert\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}(\operatorname{\bm{\theta}}^{\prime})},$
(87)

where (85) holds by applying Taylor’s theorem with
$\operatorname{\bm{\theta}}^{\prime}\in(\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}},\operatorname{\bm{\theta}}^{\text{MLE}}_{t}),\operatorname{\bm{\theta}}^{\prime\prime}\in(\operatorname{\bm{\theta}}^{\text{MLE}}_{t},\operatorname{\bm{\theta}}^{*})$,
and the fact that
$\nabla_{\operatorname{\bm{\theta}}}\ell_{t}(\operatorname{\bm{\theta}})|_{\operatorname{\bm{\theta}}=\operatorname{\bm{\theta}}^{\text{MLE}}_{t}}^{\top}(\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t})\leq
0$, (86) holds due to
$-p^{2}_{\text{min}}\nabla^{2}_{\operatorname{\bm{\theta}}}\ell_{t}(\operatorname{\bm{\theta}})\preceq\operatorname{\mathbf{A}}_{t}\preceq-\nabla^{2}_{\operatorname{\bm{\theta}}}\ell_{t}(\operatorname{\bm{\theta}}),\forall\operatorname{\bm{\theta}}\in\mathbb{P}$,
and (87) holds with probability at least $1-\sum_{t=1}^{T}\frac{1}{T^{2}}$ by
(71), (73), and replacing $\delta$ with $\frac{1}{T^{2}}$ in $\beta_{T}$ and
$\beta^{\prime}_{T}$, Lemma 1, and Cauchy–Schwarz inequality. Then, we have

$\displaystyle\mathcal{R}^{\prime}(T)=$
$\displaystyle\;\sum_{t=1}^{T}\left[V^{*}(s_{t},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})-V^{\pi_{t}}(s_{t};\operatorname{\bm{\theta}}^{*})\right]$
(88) $\displaystyle=$
$\displaystyle\;\gamma\sum_{t=2}^{T+1}\left[\mathbb{E}_{s^{\prime}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}[V^{*}(s^{\prime},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})]-\mathbb{E}_{s^{\prime}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}[V^{\pi_{t}}(s^{\prime},\operatorname{\bm{\theta}}^{*})]\right]$
(89) $\displaystyle=$
$\displaystyle\;\gamma\sum_{t=2}^{T+1}\bigg{[}\underbrace{\mathbb{E}_{s^{\prime}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}[{\color[rgb]{0,0,0}V^{*}(s^{\prime},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}-V^{\pi_{t}}(s^{\prime},\operatorname{\bm{\theta}}^{*})]-{\color[rgb]{0,0,0}\left(V^{*}(s_{t+1},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})-V^{\pi_{t}}(s_{t+1},\operatorname{\bm{\theta}}^{*})\right)}}_{:=B_{1}}$
$\displaystyle\;+\underbrace{\mathbb{E}_{s^{\prime}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}[V^{*}(s^{\prime},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})]{\color[rgb]{0,0,0}-V^{\pi_{t}}(s_{t+1},\operatorname{\bm{\theta}}^{*})}}_{:=B_{2}}$
$\displaystyle\;\underbrace{-\mathbb{E}_{s^{\prime}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}[{\color[rgb]{0,0,0}V^{*}(s^{\prime},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}]{\color[rgb]{0,0,0}+V^{*}(s_{t+1},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}}_{:=B_{3}}\bigg{]}$
(90) $\displaystyle\leq$
$\displaystyle\frac{4\gamma}{1-\gamma}\sqrt{T\log{\frac{1}{\delta}}}+B_{2}$
(91)

where (89) holds by
$\pi_{t}=\operatorname*{argmax}_{\pi}V^{\pi}(s_{t},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})$,
and (91) holds with probability at least $1-\sum_{t=1}^{T}\frac{2}{t^{2}}$ by
applying Azuma Hoeffding inequality in Lemma 3 on $B_{1}$ and $B_{3}$, which
are martingale difference sequences. For $B_{2}$, we have

$\displaystyle\gamma\sum_{t=2}^{T+1}\left[\mathbb{E}_{s^{\prime}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}[V^{*}(s^{\prime},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})]-V^{\pi_{t}}(s_{t+1},\operatorname{\bm{\theta}}^{*})\right]$
$\displaystyle=$
$\displaystyle\gamma\sum_{t=2}^{T+1}\left[\mathbb{E}_{s^{\prime}\sim\text{Pr}(\cdot|s_{t},a_{t};{\color[rgb]{0,0,0}\operatorname{\bm{\theta}}^{*}})}\left[{\color[rgb]{0,0,0}\frac{\text{Pr}(s^{\prime}|s_{t},a_{t};\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}{\text{Pr}(s^{\prime}|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}}V^{*}(s^{\prime},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})\right]-V^{\pi_{t}}(s_{t+1},\operatorname{\bm{\theta}}^{*})\right]$
(92) $\displaystyle=$
$\displaystyle\underbrace{\gamma\sum_{t=2}^{T+1}\left[\mathbb{E}_{s^{\prime}\sim\text{Pr}(\cdot|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}\left[\frac{\text{Pr}(s^{\prime}|s_{t},a_{t};\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}{\text{Pr}(s^{\prime}|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}V^{*}(s^{\prime},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})\right]{\color[rgb]{0,0,0}-\frac{\text{Pr}(s_{t+1}|s_{t},a_{t};\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}{\text{Pr}(s_{t+1}|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}V^{*}(s_{t+1},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}\right]}_{:=B_{4}}$
$\displaystyle+\gamma\sum_{t=2}^{T+1}\left[{\color[rgb]{0,0,0}\frac{\text{Pr}(s_{t+1}|s_{t},a_{t};\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}{\text{Pr}(s_{t+1}|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}V^{*}(s_{t+1},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}-V^{\pi_{t}}(s_{t+1},\operatorname{\bm{\theta}}^{*})\right]$
(93) $\displaystyle=$ $\displaystyle
B_{4}+\gamma\mathcal{R}^{\prime}(T)+\frac{2\gamma}{1-\gamma}+\gamma\sum_{t=2}^{T+1}\left[\left(\frac{\text{Pr}(s_{t+1}|s_{t},a_{t};\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}{\text{Pr}(s_{t+1}|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}-1\right)V^{*}(s_{t+1},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})\right]$
(94) $\displaystyle\leq$
$\displaystyle\frac{2\gamma}{p_{\text{min}}(1-\gamma)}\sqrt{T\log{\frac{1}{\delta}}}+\underbrace{\gamma\sum_{t=2}^{T+1}\left[\left(\frac{\text{Pr}(s_{t+1}|s_{t},a_{t};\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}{\text{Pr}(s_{t+1}|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}-1\right)V^{*}(s_{t+1},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})\right]}_{:=B_{5}}+\gamma\mathcal{R}^{\prime}(T)+\frac{2\gamma}{1-\gamma}$
(95)

where (92) holds by importance sampling, (93) holds by adding and subtracting
${\color[rgb]{0,0,0}\text{Pr}(s_{t+1}|s_{t},a_{t};\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})/\text{Pr}(s_{t+1}|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}\cdot
V^{*}(s_{t+1},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})$,
(94) holds by Lemma 2, and (95) holds with probability at least $1-\delta$ by
applying Azuma-Hoeffding inequality in Lemma 3 on $B_{4}$. Then, for the term
$B_{5}$, we have

$\displaystyle B_{5}=$
$\displaystyle\gamma\sum_{t=2}^{T+1}\left[\left(\frac{\text{Pr}(s_{t+1}|s_{t},a_{t};\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})}{\text{Pr}(s_{t+1}|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})}-1\right)V^{*}(s_{t+1},\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}})\right]$
(96) $\displaystyle\leq$
$\displaystyle\frac{\gamma}{p_{\text{min}}(1-\gamma)}\sum_{t=1}^{T}|\langle\phi(s_{t+1}|s_{t},a_{t}),\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}-\operatorname{\bm{\theta}}^{*}\rangle|+\frac{\gamma}{p_{\text{min}}(1-\gamma)}$
(97) $\displaystyle\leq$
$\displaystyle\frac{\gamma}{p_{\text{min}}(1-\gamma)}\sum_{t=1}^{T}\lVert\phi(s_{t+1}|s_{t},a_{t})\rVert_{\operatorname{\mathbf{A}}_{t}^{-1}}\cdot\lVert\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert_{\operatorname{\mathbf{A}}_{t}}$
$\displaystyle+\frac{\gamma}{p_{\text{min}}(1-\gamma)}\sum_{t=1}^{T}\lVert\phi(s_{t+1}|s_{t},a_{t})\rVert_{\operatorname{\mathbf{A}}_{t}^{-1}}\cdot\lVert\operatorname{\bm{\theta}}^{\text{MLE}}_{t}-\operatorname{\bm{\theta}}^{*}\rVert_{\operatorname{\mathbf{A}}_{t}}+\frac{\gamma}{p_{\text{min}}(1-\gamma)}$
(98) $\displaystyle\leq$
$\displaystyle\frac{\gamma}{p_{\text{min}}(1-\gamma)}\sum_{t=1}^{T}\lVert\phi(s_{t+1}|s_{t},a_{t})\rVert_{\operatorname{\mathbf{A}}_{t}^{-1}}\cdot\lVert\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert_{\operatorname{\mathbf{A}}_{t}}$
$\displaystyle+\frac{\sqrt{\beta_{T}}\gamma}{p_{\text{min}}(1-\gamma)}\left(1+\sqrt{T\cdot
2d\log\left(\frac{d\lambda+TL^{2}}{d}\right)}\right)$ (99)

where (97) holds by $p_{\text{min}}\leq\min_{t\leq
T}\text{Pr}(s_{t+1}|s_{t},a_{t};\operatorname{\bm{\theta}}^{*})$, which is
defined in Assumption 1, (98) holds by Cauchy–Schwarz inequality and triangle
inequality, and (99) holds by Theorem 1 with probability at least
$1-\frac{1}{T}$ by replacing $\delta$ with $\frac{1}{T^{2}}$ in $\beta_{T}$
and Lemma 1. Combining the final term in (87) and (99), we have

$\displaystyle\sum_{t=1}^{T}\left(-\frac{1}{2\alpha(t)}\lVert\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert^{2}_{\operatorname{\mathbf{A}}_{t}}+\frac{\gamma}{p_{\text{min}}(1-\gamma)}\lVert\phi(s_{t+1}|s_{t},a_{t})\rVert_{\operatorname{\mathbf{A}}_{t}^{-1}}\lVert\operatorname{\operatorname{\bm{\theta}}^{\textbf{V}}_{t}}-\operatorname{\bm{\theta}}^{\text{MLE}}_{t}\rVert_{\operatorname{\mathbf{A}}_{t}}\right)$
$\displaystyle\leq$
$\displaystyle\left(\frac{\gamma}{4p_{\text{min}}(1-\gamma)}\right)^{2}\sum_{t=1}^{T}\alpha(t)\lVert\phi(s_{t+1}|s_{t},a_{t})\rVert^{2}_{\operatorname{\mathbf{A}}_{t}^{-1}}$
(100) $\displaystyle=$ $\displaystyle\alpha(T)\cdot
2d\log\left(\frac{d\lambda+TL^{2}}{d}\right),$ (101)

where (100) holds by completing the square, and (101) holds by Lemma 1.
Letting $\alpha(t)=\sqrt{t}$ and combining (81), (87), (91), (95), (99), and
(101), we complete the proof. ∎

##  Appendix C Implementation Details

###  C.1 Environment

  * •

$\phi(\cdot|s,a)$: We employ a neural network architecture with two linear
hidden layers, each utilizing the Rectified Linear Unit (ReLU) activation
function applied to every neuron. The network’s input is created by
concatenating the one-hot vectors derived from the state and action indices.
The output of this network is subsequently transformed into a set of $d$ final
layers, each having a dimension of $hidden\\_size\times|\mathcal{S}|$, and
employing the softmax activation function. The resulting outputs from these
final layers are concatenated to yield the final output, which can be
represented as
$\\{\phi(s^{\prime}|s,a)\\}_{s^{\prime}\in\mathcal{S}}\in\mathbb{R}^{d\times|\mathcal{S}|}$.

  * •

$\operatorname{\bm{\theta}}^{*}$: By initializing the parameter vector
$\operatorname{\bm{\theta}}^{*}$ with random values such that the summation of
its elements equals 1, we can readily verify that the
$\operatorname{\bm{\theta}}^{*}$ resides within the probability simplex.

All the simulations are conducted on the device with (i) CPU: Intel Core
i7-11700K, (ii) RAM: 32 GB, (iii) GPU: RTX 3080Ti, and (iv) OS: Windows 10.

###  C.2 Hyper-parameters

$\gamma$ | $0.9$
---|---
Temperature of the softmax function | $0.01$
$\lambda$ | $1$
$\delta$ for UCLK | $0.1$

##  Appendix D Additional Simulation Result

Figure 3 shows the regret performance of VBMLE under a larger linear MDP, with
$|\mathcal{S}|=15,|\mathcal{A}|=4$. We don’t provide the result of UCLK since
it is impractical in terms of computation time. The result includes two
variants of the biased term designed in VBMLE:

  * •

Approximated VBMLE: The biased term equals to
$\sum_{s^{\prime}\in\mathcal{S}}\langle\phi(s^{\prime}|s_{t},a_{t})V^{*}(s^{\prime};\operatorname{\bm{\theta}}^{\textbf{V}}_{t-1}),\operatorname{\bm{\theta}}\rangle$.
Notice that the term
$V^{*}(s^{\prime};\operatorname{\bm{\theta}}^{\textbf{V}}_{t-1})$ is detached
from $\operatorname{\bm{\theta}}$.

  * •

Exact VBMLE: The biased term $V^{*}(s_{t};\operatorname{\bm{\theta}})$ is
constructed by value iteration (2), which is the same implementation as that
in Figure 1.

###  D.1 Standard Deviation of Figure 1

Table 2: The table shows the standard deviation of cumulative regret at $t=500$. | $|\mathcal{S}|=3,|\mathcal{A}|=2$ | $|\mathcal{S}|=5,|\mathcal{A}|=4$
---|---|---
UCLK | $79.289$ | $23.982$
VBMLE | $1.874$ | $1.830$
Algorithm 2 Value Iteration

1:Input: $\delta,U,\operatorname{\bm{\theta}}$

2:$V^{(1)}(\cdot;\operatorname{\bm{\theta}})=\frac{1}{1-\gamma}$

3:for $u=1,2,\cdots,U$ do

4:
$V^{(u+1)}(\cdot;\operatorname{\bm{\theta}})=\max_{a}\left\\{R(\cdot,a)+\gamma\sum\limits_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a;\operatorname{\bm{\theta}})V^{(u)}(\cdot;\operatorname{\bm{\theta}})\right\\}$

5:end for

6:Return $V^{(U+1)}(\cdot;\operatorname{\bm{\theta}})$

$\begin{array}[]{c}\lx@intercol\mbox{\bf}\hfil\lx@intercol\\\
\scalebox{0.49}{\includegraphics[width=397.48499pt]{./figures/S_15_A_4.eps}}\\\
\mbox{(a) $|\mathcal{S}|=15,|\mathcal{A}|=4$}\end{array}$

Figure 3: Regret averaged over $20$ trials with $T=500$