# Regret Analysis of the Posterior Sampling-based Learning Algorithm for
Episodic POMDPs

Dengwang Tang  University of Southern California  Rahul Jain  University of
Southern California  Ashutosh Nayyar  University of Southern California
Pierluigi Nuzzo  University of Southern California

###### Abstract

Compared to Markov Decision Processes (MDPs), learning in Partially Observable
Markov Decision Processes (POMDPs) can be significantly harder due to the
difficulty of interpreting observations. In this paper, we consider episodic
learning problems in POMDPs with unknown transition and observation models. We
consider the Posterior Sampling-based Reinforcement Learning (PSRL) algorithm
for POMDPs and show that its Bayesian regret scales as the square root of the
number of episodes. In general, the regret scales exponentially with the
horizon length $H$, and we show that this is inevitable by providing a lower
bound. However, under the condition that the POMDP is undercomplete and weakly
revealing, we establish a polynomial Bayesian regret bound that improves the
regret bound by a factor of $\tilde{\Omega}(H^{2}\sqrt{SA})$ over the recent
result by Liu et al. (2022).

##  1 Introduction

Markov Decision Processes (MDPs) have been widely used to model many
sequential decision problems in engineering and socioeconomic settings. One of
the most powerful features of the MDP model is the presence of the _observable
state_ , which summarizes the effect of all the history. A decision can be
made based only on the state without loss of optimality. Also, planning
algorithms can be developed based on solving smaller subproblems involving
specific starting states at specific times in the system. However, in many
systems, while it is possible to rely on Markovian state representations, such
states are often not perfectly observable, i.e., the observation is partial
(e.g., sensors with limited resolution) or noisy (e.g., sensors with noise) or
both. An imperfect observation itself cannot summarize the effect of the
history, and a decision maker has to take all past actions and observations
into account to make the best decisions possible. Many such settings can be
modeled with Partially Observable Markov Decision Processes (POMDPs). While
many polynomial time planning algorithms exist for finite MDPs, planning for
finite POMDPs is known to be a PSPACE-Complete problem (Papadimitriou and
Tsitsiklis, 1987).

The above discussion concerns mainly with planning problems, where either the
model parameters are known or the agent has access to a simulator of the
environment. In learning problems, where the parameters are unknown to the
agents, the difficulty introduced by imperfect observations can be even more
pronounced. POMDP planning problems can be converted into equivalent MDP
planning problems by considering belief states (Kumar and Varaiya, 2015). Even
though the belief space is uncountably infinite, the belief state is still an
_observable_ summarization of the history, and many approximate planning
algorithms (Shani et al., 2013; Silver and Veness, 2010) are based on this
conversion. However, in learning problems, due to unknown parameters, the
belief state is no longer observable. Therefore, unlike their planning
counterparts, POMDP learning problems cannot be simply reformulated as belief-
state-MDP learning problems. On a more fundamental level, in a POMDP learning
problem, the learning agent needs to reason about possible interpretations of
the observations in terms of the underlying states, which is a challenge not
present in MDP learning problems.

In this work, we consider episodic reinforcement learning problems on finite
horizon POMDPs with finite state, action, and observation spaces. The exact
models of the transition and observation kernels are unknown to the learning
agent. We propose the Posterior Sampling-based Reinforcement Learning (PSRL)
algorithm for POMDPs, which is an adaptation of the posterior sampling method
used in bandit (Agrawal and Goyal, 2012; Russo and Van Roy, 2016) and MDP
learning problems (Osband et al., 2013). We analyze the Bayesian regret of the
PSRL algorithm in two settings, namely, (1) the general case, where no
assumption on the POMDP is imposed; (2) the undercomplete $\alpha$-revealing
POMDPs (Jin et al., 2020; Liu et al., 2022), which quantify the requirement
that the observations must be informative to a certain degree. We show that in
general POMDP learning problems, the regret is
$\mathrm{poly}(S,A,O,H)\cdot\tilde{\mathcal{O}}(\sqrt{(OA)^{H}K})$, where $K$
is the number of episodes and $H$ is the horizon length. We show that the
exponential dependence on $H$ is necessary by proving an
$\Omega(\sqrt{A^{H-1}K})$ lower bound of the regret. Under the assumption that
the POMDP is undercomplete and $\alpha$-revealing, we establish an
$\tilde{\mathcal{O}}\left(\alpha^{-2}H^{2}S^{2}O\sqrt{HA(SA+O)K}\right)$ upper
bound on the Bayesian regret. Our main contributions are as follows:

  * •

To the best of our knowledge, we provide the first theoretical analysis of the
regret of the PSRL algorithm on episodic POMDP learning problems in both
general cases and $\alpha$-weakly revealing POMDPs. Our results show that the
PSRL algorithm always achieves $\tilde{\mathcal{O}}(\sqrt{K})$ regret, where
the constant in front depends on how hard the learning problem is.

  * •

Through the use of a tighter index change lemma (as laid out in Appendix A) in
the setting of undercomplete $\alpha$-revealing POMDPs, our Bayesian regret
bound improves the upper bound by Liu et al. (2022) by a factor of
$\tilde{\Omega}(H^{2}\sqrt{SA})$.

###  1.1 Related Literature

There is an extensive amount of literature on episodic reinforcement learning
for static (i.e., multi-arm bandits) or dynamic systems (i.e., MDPs, POMDPs).
Xiong et al. (2022) offer a list references. We focus our discussion on two
groups of results most related to our work, namely, (1) posterior sampling
based algorithms and (2) POMDP learning algorithms.

#### Posterior Sampling.

Throughout the vast literature on reinforcement learning, there have been two
prominent techniques for balancing exploration and exploitation, namely, (1)
Optimism in the Face of Uncertainty (OFU) (Lai et al., 1985; Auer et al.,
2002, 2008) and (2) Posterior sampling (or Thompson Sampling (Thompson, 1933))
(Agrawal and Goyal, 2012; Osband et al., 2013; Russo and Van Roy, 2016; Ouyang
et al., 2017). In the OFU approach, the learning agent chooses its policy
based on a confidence set of the problem parameter. In the posterior sampling
approach, the learning agent chooses its policy based on a sampled parameter
drawn from the posterior distribution. Most papers on posterior sampling have
focused on either multi-armed bandits with specific prior distributions
(Agrawal and Goyal, 2012; Bubeck and Liu, 2013; Agrawal and Goyal, 2017) or
MDPs (Osband et al., 2013; Ouyang et al., 2017). A series of papers by Russo
and Van Roy (2013, 2014, 2016) established general frameworks for the analysis
of posterior sampling algorithms in various learning settings. These results
cannot be directly applied to POMDPs. However, our analysis is closely
connected to the approach by Russo and Van Roy (2013).

#### POMDP Learning.

There have been many works focusing on episodic learning of finite horizon
POMDPs. In Ross et al. (2007); Poupart and Vlassis (2008) and Ross et al.
(2011), the authors considered Bayesian models for POMDP learning. Despite
presenting some justifications, no sample complexity or regret guarantees for
the entire algorithm are proven in these works. Closely related to the POMDP
learning problem is the parameter estimation problem of Hidden Markov Models
(HMMs), a special case of POMDPs without actions. One of the most recent
methods for this problem is the spectral method (Anandkumar et al., 2012,
2014; Hsu et al., 2012), where results are established under the assumption
that both the state transition and observation kernels have full rank. A
number of POMDP learning algorithms developed based on the spectral method
(Guo et al., 2016; Azizzadenesheli et al., 2016; Xiong et al., 2022) has
therefore carried over the same assumptions. In comparison, while we also
assume that the observation kernels have full rank, our work imposes no
assumption on the state transition kernel. No regret bound is given by Guo et
al. (2016) as their effort focuses on sample complexity. Xiong et al. (2022)
find a $\tilde{\mathcal{O}}(T^{2/3})$ regret bound where $T$ is the learning
horizon. Azizzadenesheli et al. (2016) have a regret bound that scales
linearly with the inverse of the smallest singular value of the transition
kernel.

Jahromi et al. (2022) applied the PSRL algorithm to infinite horizon POMDPs.
They established an $\mathcal{O}(\log T)$ instance-dependent regret bound in
the finite parameter case under certain assumptions, where $T$ is the number
of learning instances, equivalent to $KH$. In the general case, they
established an $\tilde{\mathcal{O}}(T^{2/3})$ regret bound assuming the
existence of a consistent transition kernel estimator with a specific
convergence rate. However, finding such an estimator is often one of the key
difficulties in POMDP learning problems.

Our work is closest to those by Jin et al. (2020) and Liu et al. (2022). Both
works proposed OFU-based algorithms for episodic learning of finite horizon
POMDPs. Both papers considered the undercomplete $\alpha$-weakly revealing
setting where the observation kernels are assumed to have rank $S$ and
smallest singular value above $\alpha$. The algorithm design of both works,
while being conceptually much simpler than spectral-method-based POMDP
algorithms, is still more involved than our PSRL algorithm. As pointed out by
Liu et al. (2022), the sample complexity result in Jin et al. (2020) gives
rise to an $\tilde{\mathcal{O}}(K^{2/3})$ regret bound, where $K$ is the
number of episodes. In undercomplete $\alpha$-weakly revealing settings, Liu
et al. (2022) established an
$\tilde{\mathcal{O}}\left(\alpha^{-2}H^{4.5}S^{2}AO\sqrt{(S^{2}A+SO)K}\right)$
regret bound. Our regret bound improves over these previous results by a
factor of $\tilde{\Omega}(H^{2}\sqrt{SA})$.

###  1.2 Notations

For a positive integer $n$, $[n]:=\\{1,2,\cdots,n\\}$. For two integers
$t_{1}\leq t_{2}$, we use $t_{1}:t_{2}$ to indicate the collection of indices
$\\{t_{1},t_{1}+1,\cdots,t_{2}\\}$. For example, $a_{1:4}$ stands for the
vector $(a_{1},a_{2},a_{3},a_{4})$. For a finite set $\varOmega$,
$\Delta(\varOmega)$ is the set of probability distributions on $\varOmega$.
$\bm{1}_{\mathcal{E}}$ is the indicator function of the event $\mathcal{E}$.
$\mathbf{e}_{i}$ represents a unit vector where the $i$-th entry is 1 and all
other entries are $0$. The dimension of $\mathbf{e}_{i}$ is inferred from the
context in which it is used. $\mathbf{I}$ represents an identity matrix whose
dimension is also inferred from the context. For finite sets
$\varOmega_{1},\varOmega_{2}$, if a function $g$ has the form
$\varOmega_{1}\mapsto\Delta(\varOmega_{2})$, we write
$g(\omega_{2}|\omega_{1}):=[g(\omega_{1})](\omega_{2})$ as if $g$ represents a
conditional probability measure. Similarly, if
$g:\varOmega_{1}\mapsto\Omega_{2}$ then we write
$g(\omega_{2}|\omega_{1}):=\bm{1}_{\\{g(\omega_{1})=\omega_{2}\\}}$.
$\|\mu_{1}-\mu_{2}\|_{\mathrm{TV}}$ represents the total variation distance
between probability distributions $\mu_{1}$ and $\mu_{2}$. For $p>0$,
$\|\cdot\|_{p}$ is the standard $\ell_{p}$-norm for vectors and $\ell_{p}$
induced norm for matrices. $\mathbb{E}$ and $\mathbb{P}$ stands for
expectation and probability, respectively. All logarithms in this paper are
natural logarithms. Finally, we use $\mathcal{O},\Omega$ to represent the
standard big-O and big-Omega notation, which hides the absolute constants
(i.e., constants independent of any problem parameters). We also use
$\tilde{\mathcal{O}},\tilde{\Omega}$ to hide absolute constants along with
logarithmic factors of problem parameters.

##  2 Preliminaries

We consider reinforcement learning problems where a learning agent repeatedly
interacts with the same environment in multiple episodes. The environment can
be described as a finite horizon POMDP with parameters only partially known to
the learning agent.

#### The Environment Model.

A finite POMDP is characterized by a tuple
$(\mathscr{S},\mathscr{A},\mathscr{O},H,b_{1},T,Z,r)$, where $\mathscr{S}$ is
a finite set of states with $|\mathscr{S}|=S$; $\mathscr{A}$ is a finite set
of actions with $|\mathscr{A}|=A$; $\mathscr{O}$ is a finite set of
observations with $|\mathscr{O}|=O$; $H$ is the horizon length;
$b_{1}\in\Delta(\mathscr{S})$ is the distribution of the initial state;
$T=(T_{h})_{h=1}^{H-1},T_{h}:\mathscr{S}\times\mathscr{A}\mapsto\Delta(\mathscr{S})$
are the transition probabilities;
$Z=(Z_{h})_{h=1}^{H},Z_{h}:\mathscr{S}\mapsto\Delta(\mathscr{O})$ are the
observation probabilities;
$r=(r_{h})_{h=1}^{H},r_{h}:\mathscr{O}\times\mathscr{A}\mapsto[0,1]$ are the
instantaneous reward functions. For each POMDP characterized by the above
tuple, we also define the following matrices:
$\mathbb{T}_{h,a}=(T_{h}(s^{\prime}|s,a))_{s^{\prime}\in\mathscr{S},s\in\mathscr{S}}$
is the $S\times S$ probability transition matrix (where the rows represent the
next state) under action $a\in\mathscr{A}$ at time $h$;
$\mathbb{Z}_{h}=(Z_{h}(o|s))_{o\in\mathscr{O},s\in\mathscr{S}}$ is the
$O\times S$ observation probability matrix at time $h$.

A (deterministic) policy $\pi=(\pi_{h})_{h=1}^{H}$ is a collection of mappings
$\pi_{h}:(\mathscr{O}\times\mathscr{A})^{h-1}\times\mathscr{O}\mapsto\mathscr{A}$,
where $\pi_{h}$ is the mapping an agent uses to choose an action at time
$h\in[H]$ based on action and observation history in the current episode. Let
$\varPi$ denote the space of all deterministic policies.

A trajectory $\tau=(o_{h},a_{h})_{h=1}^{H}$ is the complete action and
observation history in a single episode. Let
$\mathscr{T}=(\mathscr{O}\times\mathscr{A})^{H}$ denote the set of
trajectories. Under a policy $\pi\in\varPi$, the probability of a trajectory
$\tau=(o_{h},a_{h})_{h=1}^{H}$ is given by
$\mathbb{P}^{\pi}(\tau)=\pi(\tau)\mathbb{P}^{-}(\tau)$, where

$\displaystyle\pi(\tau)$
$\displaystyle:=\prod_{h=1}^{H}\pi_{h}(a_{h}|\tau_{h-1},o_{h})$ (1)
$\displaystyle\mathbb{P}^{-}(\tau)$
$\displaystyle:=\sum_{s_{1:H}\in\mathscr{S}^{H}}\left[b_{1}(s_{1})Z_{H}(o_{H}|s_{H})\prod_{h=1}^{H-1}Z_{h}(o_{h}|s_{h})T_{h}(s_{h+1}|s_{h},a_{h})\right]$
(2)

where $\tau_{h}\in(\mathscr{O}\times\mathscr{A})^{h}$ is the partial
trajectory made up with the first $h$ observations and actions in
$\tau\in\mathscr{T}$. The above representation is particularly helpful for our
analysis since it separates the “policy part” from the “environment part.” The
environment part can also be written in terms of matrix multiplications as
follows

$\displaystyle\mathbb{P}^{-}(\tau)$
$\displaystyle=\mathbf{e}_{o_{H}}^{T}\mathbb{Z}_{H}\mathbb{T}_{H-1,a_{H-1}}\mathrm{diag}(\mathbb{Z}_{H-1}(o_{H-1},\cdot))\mathbb{T}_{1,a_{1}}\mathrm{diag}(\mathbb{Z}_{1}(o_{1},\cdot))b_{1}$
(3)

where $\mathrm{diag}(\mathbf{w})$ is a diagonal matrix whose main diagonal is
given by the vector $\mathbf{w}$.

The expected total reward in one episode under policy $\pi\in\varPi$, or the
value of a policy $\pi$, is given by

$V^{\pi}:=\sum_{o_{1:H},a_{1:H}}\left(\mathbb{P}^{\pi}(o_{1:H},a_{1:H})\sum_{h=1}^{H}r_{h}(o_{h},a_{h})\right).$
(4)

The maximum total expected reward in one episode over all policies
$\pi\in\varPi$, or the value of the POMDP, is defined as
$V^{*}=\max_{\pi\in\varPi}V^{\pi}$.

#### Learning Agent’s Prior Knowledge.

We assume that $\mathscr{S},\mathscr{A},\mathscr{O},H,r$ are known to the
learning agent. The quantities $b_{1},T$ and $Z$ are (in general) unknown to
the agent. We assume that $b_{1},T,Z$ are parameterized by a parameter
$\theta\in\varTheta$, and the learning agent knows the parameterization (i.e.,
the agent knows the set $\varTheta$, and what
$(b_{1}^{\theta},T^{\theta},Z^{\theta})$ is for each given
$\theta\in\varTheta$). The learning agent’s prior knowledge of the true
environment $\theta^{*}$ is modeled by a distribution111 More formally, we
assume that $\Theta$ is a Borel subset of some $\mathbb{R}^{d}$, the prior
distribution $\nu^{1}$ is a Borel measure, and the parameterization mapping
$\theta\mapsto(b_{1}^{\theta},T^{\theta},Z^{\theta})$ is Borel measurable.
$\nu^{1}\in\Delta(\varTheta)$. In the rest of the paper, we view $\theta^{*}$
as a primitive random variable with distribution $\nu^{1}$. We will also add a
subscript $\theta$ to the quantities defined above (e.g.,
$\mathbb{P}_{\theta}^{\pi}(\tau),\mathbb{P}_{\theta}^{-}(\tau),V_{\theta}^{\pi},V_{\theta}^{*}$)
to signify that they are associated with the POMDP
$(\mathscr{S},\mathscr{A},\mathscr{O},H,b_{1}^{\theta},T^{\theta},Z^{\theta},r)$.

#### Learning Agent’s Interaction with the Environment.

At the beginning of each episode, the learning agent chooses a potentially
randomized policy in $\varPi$ based on past trajectories and policies. More
specifically, for $k\in\mathbb{N}$, let
$\mathcal{D}_{k}:=(\tau^{j},\pi^{j})_{j=1}^{k-1}=(o_{1:H}^{j},a_{1:H}^{j},\pi^{j})_{j=1}^{k-1}$
denote the data which the learning agent possesses at the beginning of the
$k$-th episode, composed of trajectories and policies in the first $k-1$
episodes. At the beginning of the $k$-th episode, the learning agent chooses a
random policy $\pi^{k}\sim\phi_{k}(\mathcal{D}_{k})$ via a mapping
$\phi_{k}:(\mathscr{T}\times\varPi)^{k-1}\mapsto\Delta(\varPi)$ and applies
this policy throughout the $k$-th episode. We refer to
$\phi=(\phi_{k})_{k\in\mathbb{N}}$ as a _learning algorithm_. (We use this
term to distinguish it from the term _policy_ , which we use exclusively for
local mappings in one episode.)

#### Objectives.

Given the prior belief $\nu^{1}\in\Delta(\varTheta)$, the Bayesian regret of a
learning algorithm $\phi$ over $K$ episodes is defined as

$\displaystyle\mathrm{BReg}(\phi,K)$
$\displaystyle:=\mathbb{E}^{\phi}\left[\sum_{k=1}^{K}(V_{\theta^{*}}^{*}-V_{\theta^{*}}^{\pi^{k}})\right]=\int_{\theta\in\varTheta}\mathbb{E}_{\theta}^{\phi}\left[\sum_{k=1}^{K}(V_{\theta}^{*}-V_{\theta}^{\pi^{k}})\right]\mathrm{d}\nu^{1}(\theta)$
(5)

which measures the difference between the maximum possible reward when one
knows $\theta^{*}$ and the actual reward realized by the learning algorithm
$\phi$. The goal of the learning agent is to choose a learning algorithm with
small Bayesian regret.

#### Proposed Algorithm.

We consider the Posterior Sampling-based Reinforcement Learning (PSRL)
algorithm for the POMDP learning problem. In this algorithm, the learning
agent keeps a posterior belief on the true parameter $\theta^{*}$ through
Bayesian updates at the end of each episode, i.e., at the end of episode $k$,
after utilizing the policy $\pi^{k}\in\varPi$ and observing the trajectory
$\tau^{k}$, the agent computes $\nu^{k+1}\in\Delta(\varTheta)$ via

$\dfrac{\mathrm{d}\nu^{k+1}}{\mathrm{d}\nu^{k}}(\theta):=\dfrac{\mathbb{P}_{\theta}^{\tilde{\pi}^{k}}(\tau^{k})}{\int_{\theta^{\prime}\in\varTheta}\mathbb{P}_{\theta^{\prime}}^{\tilde{\pi}^{k}}(\tau^{k})\mathrm{d}\nu_{k}(\theta^{\prime})}.$
(6)

We also assume that the agent has access to an optimization oracle, which
returns an optimal policy for a given POMDP. A more detailed description of
the algorithm is given by Algorithm 1.

Algorithm 1 Posterior sampling-based reinforcement learning (PSRL) algorithm

Input: Prior $\nu^{1}\in\Delta(\varTheta)$; Number of episodes $K$

for $k=1$ to $K$ do

Sample $\tilde{\theta}^{k}\sim\nu^{k}$

Invoke the optimization oracle to obtain a policy
$\tilde{\pi}^{k}\in\arg\max_{\pi\in\varPi}(V_{\tilde{\theta}^{k}}^{\pi})$

Apply $\tilde{\pi}^{k}$ in the $k$-th episode

Collect the trajectory $\tau^{k}$ and compute new posterior
$\nu^{k+1}\in\Delta(\varTheta)$ using (6)

end for

#### Assumptions on the Environment.

In this paper, we analyze the PSRL algorithm in two different settings. The
first setting is the general case, i.e., no assumptions are imposed on the
underlying POMDP. The second setting is the setting of undercomplete
$\alpha$-weakly revealing POMDPs, which was introduced by Jin et al. (2020)
and also considered by Liu et al. (2022).

######  Assumption 1.

(Jin et al., 2020; Liu et al., 2022) The observations are _undercomplete_ ,
i.e., $O\geq S$, and the POMDP is $\alpha$-weakly revealing, i.e., for all
$\theta\in\varTheta$ and all $h\in[H]$, the smallest singular value of the
$O\times S$ observation probability matrix $\mathbb{Z}_{h}^{\theta}$ satisfies
$\sigma_{\min}(\mathbb{Z}_{h}^{\theta})\geq\alpha$.

Intuitively, Assumption 1 states that the observations must give a reasonable
amount of information about the underlying state (Jin et al., 2020).

##  3 Main Results

In this section, we formally state our main results. The first two results
concern the general case, where no assumptions are imposed on the POMDP. We
defer the proof outline of the results to the next section.

######  Theorem 1.

For general POMDP learning problems, the Bayesian regret under the PSRL
algorithm satisfies

$\mathrm{BReg}(\phi^{\mathrm{PSRL}},K)\leq\tilde{\mathcal{O}}\left(H^{2}\sqrt{(S^{2}A+SO)(OA)^{H}K}\right)$
(7)

The proof can be found in Appendix C.4.

######  Remark 1.

Utilizing the fact that the trajectory probability can be separated into a
product of the “policy part” and the “environment part,” the episodic POMDP
learning problem can be seen as a special case of linear bandit problem with
dimension $d=(OA)^{H}$. Applying the standard result on the posterior sampling
algorithm for linear bandits (Russo and Van Roy, 2016) we obtain an
$\tilde{\mathcal{O}}(H\sqrt{O^{2H+1}A^{H}K})$ regret bound, where the
additional $O^{H}$ comes from the fact that $|\varPi|=\Omega(A^{O^{H}})$. The
same regret bound can also be obtained if the LinUCB algorithm (Li et al.,
2010) is applied instead (Lattimore and Szepesvári, 2020). Theorem 1 presents
an improvement over this naive bound by a factor of
$\tilde{\Omega}\left(\sqrt{\frac{O^{H+1}}{H^{2}(S^{2}A+SO)}}\right)$.

The next result shows that, in the general case, the exponential dependence on
$H$ in the regret bound is unavoidable under any learning algorithm.

######  Proposition 1.

For any $A,H\geq 2$ and any $K\geq A^{H-1}$, there exists a POMDP learning
problem with $S=O=2$ such that the Bayesian regret satisfies

$\mathrm{BReg}(\phi,K)\geq\frac{1}{20}\sqrt{A^{H-1}K}.$ (8)

under any learning algorithm $\phi$.

The proof is available in Appendix B.

Next, we state our regret bound in the second setting, where the POMDP is
assumed to be undercomplete and $\alpha$-weakly revealing.

######  Theorem 2.

Under Assumption 1, the Bayesian regret under PSRL algorithm satisfies

$\mathrm{BReg}(\phi^{\mathrm{PSRL}},K)\leq\tilde{\mathcal{O}}\left(\alpha^{-2}H^{2}S^{2}O\sqrt{HA(SA+O)K}\right)$
(9)

The proof can be found in Appendix C.5.

######  Remark 2.

Due to the complexity of solving POMDPs even with known parameters and the
exponential growth of action and observation history, sometimes one may
consider a restricted policy set $\tilde{\varPi}\subset\varPi$ (e.g., finite
memory policies). Both Theorem 1 and Theorem 2 will continue to hold in this
setting if the optimization oracle used in Algorithm 1 returns a best
restricted policy, and the regret is defined with respect to the best
restricted policy.

##  4 Proof Outline

In this section we lay out the proof outline for the results stated in Section
3. The proof details are available in Appendix B in the supplementary file.

###  4.1 Regret Lower Bound

Proposition 1 is motivated by the pathological POMDP example used by
Krishnamurthy et al. (2016) and Jin et al. (2020). In this POMDP, the first
$H-1$ actions act as “rotating dials” to a “combination lock”: One must enter
a specific sequence in order to “unlock” at time $H$. The first $H-1$
observations are completely uninformative, so that the learning agent has no
way to learn if the entered sequence is correct or not until the very last
step. Such a POMDP resembles a multi-armed bandit with $A^{H-1}$ arms.
Krishnamurthy et al. (2016) and Jin et al. (2020) established sample
complexity lower bounds on these POMDPs. However, these results cannot be
directly translated into lower bounds on the cumulative regret. In the proof
of Proposition 1, we apply the standard min-max lower bound technique (Auer et
al., 2002) on modified POMDP examples from Krishnamurthy et al. (2016) and Jin
et al. (2020).

###  4.2 Regret Upper Bound

Our proofs of both theorems follow similar steps as in the result from Liu et
al. (2022). At the center of our proofs is a confidence set
$\bar{\varTheta}(\mathcal{D}_{k})$, which is a finite set of parameters whose
log-likelihood given the data $\mathcal{D}_{k}$ is close to the maximum log-
likelihood. The set is constructed such that with high probability, the true
parameter $\theta^{*}$ is close to some parameter in
$\bar{\varTheta}(\mathcal{D}_{k})$. The specific definition of
$\bar{\varTheta}(\mathcal{D}_{k})$ is provided in Appendix C. The proof of
both theorems will be based on Lemma 1, where we relate the regret bound to
the quality of the confidence set, and Lemma 2, where we establish certain
guarantees on the confidence set.

######  Lemma 1.

The Bayesian regret under the PSRL algorithm can be bounded by

$\displaystyle\mathrm{BReg}(\phi^{\mathrm{PSRL}},K)$ $\displaystyle\leq
2H+H\mathbb{E}\left[\sum_{k=1}^{K}\max_{\bar{\theta}\in\bar{\varTheta}(\mathcal{D}_{k})}\|\mathbb{P}_{\bar{\theta}}^{\tilde{\pi}^{k}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}\|_{\mathrm{TV}}\right]$
(10)

where $\mathbb{P}_{\theta}^{\pi}$ is understood as a probability measure on
$\mathscr{T}$, the set of action-observation trajactories.

The proof of Lemma 1 mostly follows from standard regret decomposition
techniques for PSRL algorithms (see e.g., Osband et al. (2013); Russo and Van
Roy (2014)) and properties of the log-likelihood function. The proof details
can be found in Appendix C.2.

On the other hand, through a martingale defined with the log-likelihood
function, we prove Lemma 2, which provides a guarantee on the quality of the
confidence set.

######  Lemma 2.

Under any learning algorithm $\phi$, with probability at least
$1-\frac{1}{K}$,

$\displaystyle\max_{k\in[K]}\max_{\bar{\theta}\in\bar{\varTheta}(\mathcal{D}_{k})}\sum_{j=1}^{k}\|\mathbb{P}_{\bar{\theta}}^{\pi^{j}}-\mathbb{P}_{\theta^{*}}^{\pi^{j}}\|_{\mathrm{TV}}^{2}\leq\tilde{\mathcal{O}}(HS^{2}A+HSO)$

The proof of Lemma 2 can be found in Appendix C.3.

Given the above lemmas, to obtain an upper bound on the Bayesian regret, the
only remaining task is to use an upper bound of

$\displaystyle\sum_{j=1}^{k}\|\mathbb{P}_{\check{\theta}^{k}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}^{2}$
(11)

to derive an upper bound of

$\displaystyle\sum_{j=1}^{K}\|\mathbb{P}_{\check{\theta}^{j}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}$
(12)

where $\check{\theta}^{k}$ is a parameter in the confidence set
$\bar{\varTheta}(\mathcal{D}_{k})$. The key difference in the above two
expressions lies in the episode index of the “environment estimator”
$\check{\theta}_{k}$: The former measures the difference of the _latest_
estimated environment with the true environment under historical policies,
while the latter measures the cumulative difference derived from the estimated
environments _at the time_. To complete this task, we will make use of the
following “index change” lemma, which is a corollary of the elliptical
potential lemma used in the linear bandit literature (see, e.g., Lattimore and
Szepesvári (2020)).

######  Lemma 3 (Index Change).

Let $x_{k},w_{k}\in\mathbb{R}^{d}$ be such that $\|w_{k}\|_{2}\leq
G_{w},~{}\|x_{k}\|_{2}\leq G_{x}$ for all $k\in[K]$. Suppose that
$\sum_{j=1}^{k}(x_{j}^{T}w_{k})^{2}\leq\beta$ for all $k\in[K]$. Then for any
$\lambda>0$,

$\displaystyle\sum_{k=1}^{K}|x_{k}^{T}w_{k}|\leq\sqrt{(\lambda+\beta)dK\log\left(1+\dfrac{G_{w}^{2}G_{x}^{2}K}{d\lambda}\right)}.$
(13)

The proof of the lemma can be found in Appendix A.

The proof of Theorem 1 follows from a direct application of Lemma 3 on certain
suitably defined $(OA)^{H}$-dimensional vectors. Note that the dimension of
the vectors is the reason for the exponential dependence on $H$.

To obtain a regret polynomial in $H$ under Assumption 1, we follow the same
three-step procedure by Liu et al. (2022), where we use an auxiliary quantity
called the _projected operator distances_. Under Assumption 1, those distances
can be used to both upper and lower bound total variation distances between
trajectory distributions. In the first two steps, we establish relationships
between (11) and (12) and projected operator distances. In the final step, we
apply (a more sophisticated version of) the “index change” lemma on
expressions involving projected operator distances. Since each projected
operator distance can be represented by inner products of $S$-dimensional
rather than $(OA)^{H}$-dimensional vectors, it allows us to obtain a better
constant for the regret bound.

We conclude this section by noting a technical, but important distinction of
our technique from that of Liu et al. (2022) in the proof of Theorem 2.
Instead of using Proposition 22 in Liu et al. (2022), which is based on
$\ell_{1}$-eluder dimension theory, we develop a new result (Proposition 3 in
Appendix A) based on the standard elliptical potential lemma. Our technical
tool is arguably easier to prove and comes with a tighter guarantee, which
ultimately enables us to improve the upper bound by Liu et al. (2022) by a
factor of $\tilde{\Omega}(H^{2}\sqrt{SA})$. We note that the tighter regret
bound is not an advantage of the PSRL algorithm, as our new technique can also
be applied in the original analysis of Liu et al. (2022) for their OFU based
algorithm.

##  5 Learning Multi-Agent POMDPs

In this section, we extend our results to learning problems on multi-agent
POMDPs (MA-POMDPs), which are models that involve multiple learning agents
with the same objective but different information about the system. A
multiple-agent POMDP can be characterized by a tuple
$(I,\mathscr{S},\mathscr{A},\mathscr{O},H,b_{1},P,Z,r)$, where
$I\in\mathbb{N}$ is the number of agents; $\mathscr{S}$ is the state space
with $|\mathscr{S}|=S$; $\mathscr{A}=\prod_{i=1}^{I}\mathscr{A}^{i}$ is the
joint action space with $|\mathscr{A}|=A$;
$\mathscr{O}=\prod_{i=1}^{I}\mathscr{O}^{i}$ is the set of joint observations
with $|\mathscr{O}|=O$; $H\in\mathbb{N}$ is the horizon length;
$b_{1}\in\Delta(\mathscr{S})$ is the distribution of the initial state;
$T=(T_{h})_{h=1}^{H-1},T_{h}:\mathscr{S}\times\mathscr{A}\mapsto\Delta(\mathscr{S})$
is the state transition kernel;
$Z=(Z_{h})_{h=1}^{H},Z_{h}:\mathscr{S}\mapsto\Delta(\mathscr{O})$ is the joint
observation kernel;
$r=(r_{h})_{h=1}^{H},r_{h}:\mathscr{O}\times\mathscr{A}\mapsto[0,1]$ is the
instantaneous reward function.

We assume that $I,\mathscr{S},\mathscr{A},\mathscr{O},H,r$ are known to the
learning agents. The quantities $b_{1},P$ and $Z$ are (in general) unknown to
the agents. In the same way as in Section 2, we assume that $b_{1},P,Z$ are
parameterized by a parameter $\theta\in\varTheta$. The parameter $\theta$ has
a prior distribution $\nu^{1}\in\Delta(\varTheta)$.

In one episode, agent $i$’s individual policy is characterized by a collection
of mappings
$\pi_{\cdot;i}=(\pi_{h;i})_{h=1}^{H},\pi_{h}^{i}:(\mathscr{O}^{i}\times\mathscr{A}^{i})^{h-1}\times\mathscr{O}^{i}\mapsto\mathscr{A}^{i}$,
that depends only on its individual information. A joint policy
$\pi=(\pi_{\cdot;i})_{i\in[I]}$ consists of the individual policies of all
agents. Let $\varPi$ denote the space of all deterministic joint policies.

At the beginning of each learning episode, the learning agents share all of
their action and observation history with each other. Each agent then picks an
individual policy based on the collective history (with possible randomization
over policies) and uses it during the episode. We assume that the agents have
access to a common randomness source, and hence their random policy choices
can be correlated. The Bayesian regret is defined in the same way as in
Section 2, where we compare the expected total reward under the given (joint)
learning algorithm against the best joint policy with respect to the true MA-
POMDP parameter.

Algorithm 2 MA-PSRL algorithm for agent $i$

Input: Prior $\nu^{1}\in\Delta(\varTheta)$; Number of episodes $K$

for $k=1$ to $K$ do

Use common randomness source to sample $\tilde{\theta}^{k}\sim\nu^{k}$

Invoke the MA-POMDP solving oracle to obtain a policy
$\tilde{\pi}^{k}\in\arg\max_{\pi\in\varPi}(V_{\tilde{\theta}^{k}}^{\pi})$

Apply $\tilde{\pi}^{k}_{\cdot;i}$ in the $k$-th episode

At the end of $k$-th episode, Share the local trajectory
$\tau^{k,i}=(a_{1:H;i}^{k},o_{1:H;i}^{k})$ with other agents

Use $\tau^{k}=(\tau^{k,j})_{j\in[I]}$ to compute new posterior
$\nu^{k+1}\in\Delta(\varTheta)$ using (6)

end for

The Multi-Agent PSRL (MA-PSRL) algorithm works in a similar way to its single-
agent counterpart: At the beginning of each episode $k$, a common sample
$\tilde{\theta}^{k}$ is drawn based on the latest posterior distribution based
on the _collective_ action and observation history, then the agents
collectively invoke an MA-POMDP solving oracle to obtain a joint policy
$\tilde{\pi}^{k}$. Note that the above steps can be done separately by each
agent using the common randomness source. Then each agent $i\in[I]$ uses its
individual policy $\tilde{\pi}^{k}_{\cdot;i}$ to take an action during the
episode.

Under the assumption of action and observation sharing at the beginning of
each episode, the MA-POMDP learning problem can be seen as a single-agent
problem where the learning agent knows all the actions and observations but is
artificially restricted to use only policies from $\varPi$, the set of joint
policies. Per Remark 2, we obtain the following result.

######  Proposition 2.

The Bayesian regret of the multi-agent PSRL algorithm applied to a general
POMDP learning problem satisfies

$\mathrm{BReg}(\phi^{\mathrm{PSRL}},K)\leq\tilde{\mathcal{O}}\left(H^{2}\sqrt{(S^{2}A+SO)(OA)^{H}K}\right).$
(14)

Furthermore, if Assumption 1 holds for the joint observation kernel $Z$, then

$\mathrm{BReg}(\phi^{\mathrm{PSRL}},K)\leq\tilde{\mathcal{O}}\left(\alpha^{-2}H^{2}S^{2}O\sqrt{HA(SA+O)K}\right).$
(15)

Note that Assumption 1 in multi-agent POMDP setting does not imply that
individual observations are necessarily informative to a degree. It only
requires the _joint observation_ to be informative. A special case that
satisfies Assumption 1 is the Dec-MDP model where the joint observation
uncovers the underlying state perfectly.

##  6 Conclusion

In this paper, we considered episodic reinforcement learning in finite horizon
POMDPs. We proposed the Posterior Sampling-based Reinforcement Learning (PSRL)
algorithm for this problem. Compared to spectral estimation-based and
optimism-based algorithms for learning in POMDPs, PSRL algorithm design is
remarkably simple and requires no hyper-parameter tuning. We showed that the
Bayesian regret under the PSRL algorithm is always
$\tilde{\mathcal{O}}(\sqrt{K})$, where $K$ is the number of learning episodes.
In general, the regret bound depends exponentially on $H$, the horizon length
of the POMDP, which we showed is unavoidable via a complementary lower bound
on the Bayesian regret. On the other hand, under the assumption that the POMDP
is undercomplete and $\alpha$-weakly revealing, we established a Bayesian
regret bound of $\tilde{\mathcal{O}}(\alpha^{-2}H^{2}S^{2}\sqrt{HA(SA+O)K})$,
which improves the regret bound by Liu et al. (2022) by a factor of
$\tilde{\Omega}(H^{2}\sqrt{SA})$. We finally extended our results to a multi-
agent setting under the assumption that agents share their observations and
actions at the beginning of each new episode. In future work, we will try to
derive a regret bound for the PSRL algorithm under the overcomplete setting
(Liu et al., 2022). Another line of work is to identify other types of
conditions on the POMDP that could ensure a polynomial dependence of the
regret on $S,A,O,H$ under the PSRL algorithm.

## References

  * Agrawal and Goyal (2012) S. Agrawal and N. Goyal.  Analysis of Thompson sampling for the multi-armed bandit problem.  In _Conference on learning theory_ , pages 39–1. JMLR Workshop and Conference Proceedings, 2012.
  * Agrawal and Goyal (2017) S. Agrawal and N. Goyal.  Near-optimal regret bounds for Thompson sampling.  _Journal of the ACM (JACM)_ , 64(5):1–24, 2017.
  * Anandkumar et al. (2012) A. Anandkumar, D. Hsu, and S. M. Kakade.  A method of moments for mixture models and hidden Markov models.  In _Conference on Learning Theory_ , pages 33–1. JMLR Workshop and Conference Proceedings, 2012.
  * Anandkumar et al. (2014) A. Anandkumar, R. Ge, D. Hsu, S. M. Kakade, and M. Telgarsky.  Tensor decompositions for learning latent variable models.  _Journal of machine learning research_ , 15:2773–2832, 2014.
  * Auer et al. (2002) P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire.  The nonstochastic multiarmed bandit problem.  _SIAM journal on computing_ , 32(1):48–77, 2002.
  * Auer et al. (2008) P. Auer, T. Jaksch, and R. Ortner.  Near-optimal regret bounds for reinforcement learning.  _Advances in neural information processing systems_ , 21, 2008.
  * Azizzadenesheli et al. (2016) K. Azizzadenesheli, A. Lazaric, and A. Anandkumar.  Reinforcement learning of POMDPs using spectral methods.  In _Conference on Learning Theory_ , pages 193–256. PMLR, 2016.
  * Bubeck and Liu (2013) S. Bubeck and C.-Y. Liu.  Prior-free and prior-dependent regret bounds for Thompson sampling.  _Advances in neural information processing systems_ , 26, 2013.
  * Carpentier et al. (2020) A. Carpentier, C. Vernade, and Y. Abbasi-Yadkori.  The elliptical potential lemma revisited.  _arXiv preprint arXiv:2010.10182_ , 2020.
  * Guo et al. (2016) Z. D. Guo, S. Doroudi, and E. Brunskill.  A PAC RL algorithm for episodic POMDPs.  In _Artificial Intelligence and Statistics_ , pages 510–518. PMLR, 2016.
  * Hsu et al. (2012) D. Hsu, S. M. Kakade, and T. Zhang.  A spectral algorithm for learning hidden Markov models.  _Journal of Computer and System Sciences_ , 78(5):1460–1480, 2012.
  * Jahromi et al. (2022) M. J. Jahromi, R. Jain, and A. Nayyar.  Online learning for unknown partially observable MDPs.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1712–1732. PMLR, 2022.
  * Jin et al. (2020) C. Jin, S. Kakade, A. Krishnamurthy, and Q. Liu.  Sample-efficient reinforcement learning of undercomplete POMDPs.  _Advances in Neural Information Processing Systems_ , 33:18530–18539, 2020.
  * Krishnamurthy et al. (2016) A. Krishnamurthy, A. Agarwal, and J. Langford.  PAC reinforcement learning with rich observations.  _Advances in Neural Information Processing Systems_ , 29, 2016.
  * Kumar and Varaiya (2015) P. R. Kumar and P. Varaiya.  _Stochastic systems: Estimation, identification, and adaptive control_.  SIAM, 2015.
  * Lai et al. (1985) T. L. Lai, H. Robbins, et al.  Asymptotically efficient adaptive allocation rules.  _Advances in applied mathematics_ , 6(1):4–22, 1985.
  * Lattimore and Szepesvári (2020) T. Lattimore and C. Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Levin and Peres (2017) D. A. Levin and Y. Peres.  _Markov chains and mixing times_ , volume 107.  American Mathematical Soc., 2017.
  * Li et al. (2010) L. Li, W. Chu, J. Langford, and R. E. Schapire.  A contextual-bandit approach to personalized news article recommendation.  In _Proceedings of the 19th international conference on World wide web_ , pages 661–670, 2010.
  * Liu et al. (2022) Q. Liu, A. Chung, C. Szepesvári, and C. Jin.  When is partially observable reinforcement learning not scary?  In _Conference on Learning Theory_ , pages 5175–5220. PMLR, 2022.
  * Osband et al. (2013) I. Osband, D. Russo, and B. Van Roy.  (More) efficient reinforcement learning via posterior sampling.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Ouyang et al. (2017) Y. Ouyang, M. Gagrani, A. Nayyar, and R. Jain.  Learning unknown Markov decision processes: A Thompson sampling approach.  _Advances in neural information processing systems_ , 30, 2017.
  * Papadimitriou and Tsitsiklis (1987) C. H. Papadimitriou and J. N. Tsitsiklis.  The complexity of markov decision processes.  _Mathematics of operations research_ , 12(3):441–450, 1987.
  * Poupart and Vlassis (2008) P. Poupart and N. Vlassis.  Model-based bayesian reinforcement learning in partially observable domains.  In _Proc Int. Symp. on Artificial Intelligence and Mathematics,_ , pages 1–2, 2008.
  * Ross et al. (2007) S. Ross, B. Chaib-draa, and J. Pineau.  Bayes-adaptive POMDPs.  _Advances in neural information processing systems_ , 20, 2007.
  * Ross et al. (2011) S. Ross, J. Pineau, B. Chaib-draa, and P. Kreitmann.  A bayesian approach for learning and planning in partially observable markov decision processes.  _Journal of Machine Learning Research_ , 12(5), 2011.
  * Russo and Van Roy (2013) D. Russo and B. Van Roy.  Eluder dimension and the sample complexity of optimistic exploration.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Russo and Van Roy (2014) D. Russo and B. Van Roy.  Learning to optimize via posterior sampling.  _Mathematics of Operations Research_ , 39(4):1221–1243, 2014.
  * Russo and Van Roy (2016) D. Russo and B. Van Roy.  An information-theoretic analysis of Thompson sampling.  _The Journal of Machine Learning Research_ , 17(1):2442–2471, 2016.
  * Shani et al. (2013) G. Shani, J. Pineau, and R. Kaplow.  A survey of point-based POMDP solvers.  _Auton. Agent Multi-Agent Syst._ , 27:1–51, 2013.
  * Silver and Veness (2010) D. Silver and J. Veness.  Monte-Carlo planning in large POMDPs.  _Adv. Neural. Inf. Process. Syst._ , 23, 2010.
  * Thompson (1933) W. R. Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3-4):285–294, 1933.
  * Xiong et al. (2022) Y. Xiong, N. Chen, X. Gao, and X. Zhou.  Sublinear regret for learning POMDPs.  _Production and Operations Management_ , 31(9):3491–3504, 2022.

##  Appendix A Index Change Results

In this section we prove the two index change lemmas we used for the proof of
regret upper bounds.

###  A.1 Proof of Lemma 3

We start from the following version of the elliptical potential lemma
presented in Carpentier et al. (2020).

######  Lemma 4 (Elliptical Potential Lemma (Carpentier et al., 2020)).

Let $x_{k}\in\mathbb{R}^{d}$ for all $k\in[K]$ be such that $\|x_{k}\|_{2}\leq
1$. Let $\lambda>0$. Set
$\mathbf{V}_{k}=\lambda\mathbf{I}+\sum_{j=1}^{k}x_{j}x_{j}^{T}$. Then,
$\sum_{k=1}^{K}\sqrt{x_{k}^{T}\mathbf{V}_{k}^{-1}x_{k}}\leq\sqrt{dK\log\left(1+\frac{K}{d\lambda}\right)}$.

Through rescaling, without loss of generality, assume that $\|w_{k}\|_{2}\leq
G_{w}G_{x}$ and $\|x_{k}\|_{2}\leq 1$. Let $\lambda>0$. Define
$\mathbf{V}_{k}=\frac{\lambda}{G_{w}^{2}G_{x}^{2}}\mathbf{I}+\sum_{j=1}^{k}x_{j}x_{j}^{T}$.
Let $\mathbf{V}_{k}^{1/2}$ be the symmetric square root matrix of the positive
definite matrix $\mathbf{V}_{k}$. Using the elliptical potential lemma, we
have

$\displaystyle\quad~{}\sum_{k=1}^{K}|x_{k}^{T}w_{k}|=\sum_{k=1}^{K}|(\mathbf{V}_{k}^{-1/2}x_{k})^{T}\mathbf{V}_{k}^{1/2}w_{k}|$
(16)
$\displaystyle\leq\sum_{k=1}^{K}\|\mathbf{V}_{k}^{-1/2}x_{k}\|_{2}\cdot\|\mathbf{V}_{k}^{1/2}w_{k}\|_{2}=\sum_{k=1}^{K}\sqrt{x_{k}^{T}\mathbf{V}_{k}^{-1}x_{k}}\sqrt{w_{k}^{T}\mathbf{V}_{k}w_{k}}$
(17)
$\displaystyle\leq\sqrt{dK\log\left(1+\dfrac{KG_{w}^{2}G_{x}^{2}}{d\lambda}\right)}\max_{k\in[K]}\sqrt{w_{k}^{T}\mathbf{V}_{k}w_{k}}$
(18)

For each $k\in[K]$, we have

$\displaystyle w_{k}^{T}\mathbf{V}_{k}w_{k}$
$\displaystyle=\frac{\lambda}{G_{x}^{2}G_{w}^{2}}\|w_{k}\|_{2}^{2}+\sum_{j=1}^{k}(x_{j}^{T}w_{k})^{2}\leq\lambda+\beta.$
(19)

Therefore, we conclude that

$\displaystyle\sum_{k=1}^{K}|x_{k}^{T}w_{k}|$
$\displaystyle\leq\sqrt{\left(\lambda+\beta\right)dK\log\left(1+\dfrac{KG_{w}^{2}G_{x}^{2}}{d\lambda}\right)}$
(20)

for any $\lambda>0$.

###  A.2 An Important Technical Result for Theorem 2

The following index change result is key to improve the regret bound of Liu et
al. (2022).

######  Proposition 3.

Let $w_{k,l,m},x_{k,l,n}\in\mathbb{R}^{d}$ for
$k\in[K],l\in[L],m\in[M],n\in[N]$. Suppose that

$\displaystyle\sum_{j=1}^{k}\left(\sum_{(l,m,n)\in[L]\times[M]\times[N]}|w_{k,l,m}^{T}x_{j,l,n}|\right)^{2}\leq\beta,$
(21) $\displaystyle\sum_{l=1}^{L}\sum_{m=1}^{M}\|w_{k,l,m}\|_{1}\leq G_{w},$
(22) $\displaystyle\sum_{l=1}^{L}\sum_{n=1}^{N}\|x_{k,l,n}\|_{1}\leq G_{x},$
(23)

for all $k\in[K]$. Then for any $\lambda>0$,

$\displaystyle\sum_{k=1}^{K}\sum_{(l,m,n)\in[L]\times[M]\times[N]}|w_{k,l,m}^{T}x_{k,l,n}|$
$\displaystyle\leq\sqrt{\left(\lambda+\beta\right)dLMK\log\left(1+\dfrac{MG_{w}^{2}G_{x}^{2}K}{dL\lambda}\right)}$
(24)

######  Remark 3.

The RHS of (24) is tighter than the bound of Proposition 22 by Liu et al.
(2022) (which plays a similar role in their analysis) in several ways: (1) The
bound by Liu et al. (2022) has a $\log^{2}(KN)$ term. In the context of its
application in the main theorem, this term results in an extra $\Omega(H^{2})$
term, since $N$ is the number of partial trajectories, which is exponential in
$H$. (2) As Liu et al. (2022) also pointed out, the bound by Liu et al. (2022)
depends linearly on $d$ instead of $\sqrt{d}$. (3) The bound by Liu et al.
(2022) scales linearly with $G_{x}G_{w}$, while in our bound the dependence is
logarithmic.

###### Proof of Proposition 3.

Define $I_{k,l,m,n}:=\mathrm{sgn}(w_{k,l,m}^{T}x_{k,l,n})$ and
$\bar{x}_{k,l,m}:=\sum_{n=1}^{N}x_{k,l,n}I_{k,l,m,n}$, we can then write the
LHS of (24) as
$\sum_{k=1}^{K}\sum_{(l,m)\in[L]\times[M]}w_{k,l,m}^{T}\bar{x}_{k,l,m}$.

Let $w_{k}=(w_{k,l,m})_{(l,m)\in[L]\times[M]}$ and
$\bar{x}_{k}=(\bar{x}_{k,l,m})_{(l,m)\in[L]\times[M]}$ be seen as
$(dLM)$-dimensional vectors. First, we have

$\displaystyle\sum_{j=1}^{k}(w_{k}^{T}\bar{x}_{j})^{2}$
$\displaystyle=\sum_{j=1}^{k}\left(\sum_{(l,m)\in[L]\times[M]}w_{k,l,m}^{T}\bar{x}_{j,l,m}\right)^{2}$
(25)
$\displaystyle=\sum_{j=1}^{k}\left(\sum_{(l,m,n)\in[L]\times[M]\times[N]}w_{k,l,m}^{T}x_{j,l,n}I_{j,l,m,n}\right)^{2}$
(26)
$\displaystyle\leq\sum_{j=1}^{k}\left(\sum_{(l,m,n)\in[L]\times[M]\times[N]}|w_{k,l,m}^{T}x_{j,l,n}|\right)^{2}\leq\beta.$
(27)

We also have

$\displaystyle\|w_{k}\|_{2}$
$\displaystyle\leq\|w_{k}\|_{1}=\sum_{l=1}^{L}\sum_{m=1}^{M}\|w_{k,l,m}\|_{1}\leq
G_{w},$ (28) $\displaystyle\|\bar{x}_{k}\|_{2}$
$\displaystyle\leq\|\bar{x}_{k}\|_{1}=\sum_{l=1}^{L}\sum_{m=1}^{M}\|\bar{x}_{k,l,m}\|_{1}\leq\sum_{l=1}^{L}\sum_{m=1}^{M}\sum_{n=1}^{N}\|x_{k,l,n}\|_{1}\leq
MG_{x}.$ (29)

The result is then established by applying Lemma 3 on the $(dLM)$-dimensional
vectors $w_{k}$ and $\bar{x}_{k}$. ∎

##  Appendix B Proof of Proposition 1

We construct the random POMDP instance as follows: Let $\epsilon\in(0,1)$ be
determined later and let $\mathscr{S}=\mathscr{O}=\\{0,1\\}$, where $0$
represents the “good” state and $1$ represents the “bad” state. Let the
parameter space $\varTheta=\mathscr{A}^{H-1}$ be the space of
$(H-1)$-sequences of actions. For each $\theta=(\theta_{1:H-1})\in\varTheta$,
the final state is “good” only if the agent follows the action sequence
$\theta_{1:H-1}$, i.e.,

$\displaystyle b_{0}^{\theta}$ $\displaystyle=\delta_{0}$ (30) $\displaystyle
T_{h}^{\theta}(s,a)$ $\displaystyle=\begin{cases}\delta_{0}&\text{if
}s=0\text{ and }a=\theta_{h}\\\ \delta_{1}&\text{otherwise}\end{cases}$ (31)

where $\delta_{s}\in\Delta(\mathscr{S})$ represents the deterministic
distribution supported on state $s$.

The observation kernel $Z^{\theta}$ is the same for all $\theta\in\varTheta$:
Observations are uniformly random for all underlying states at all times
$h\in[H-1]$. At the final timestamp, the observation kernel
$\mathbb{Z}_{H}^{\theta}:\mathscr{S}\mapsto\Delta(\mathscr{O})$ is given by

$\displaystyle
Z_{H}^{\theta}(o|s)=\begin{cases}\frac{1}{2}+\epsilon&s=0,o=0\\\
\frac{1}{2}-\epsilon&s=0,o=1\\\ \frac{1}{2}&s=1\end{cases}$ (32)

The reward function is given by $r_{h}\equiv 0$ for $h\in[H-1]$ and
$r_{H}(o,a)=\bm{1}_{\\{o=0\\}}$. The prior distribution $\nu^{1}$ is the
uniform distribution on $\varTheta$.

For the convenience of the proof, we define an additional POMDP
$(b_{1}^{\mathbf{u}},T^{\mathbf{u}},Z^{\mathbf{u}})$ by

$\displaystyle b_{1}^{\mathbf{u}}$ $\displaystyle=\delta_{0}$ (33)
$\displaystyle T_{h}^{\mathbf{u}}(s,a)$ $\displaystyle=\delta_{0}\quad\forall
s\in\mathscr{S},a\in\mathscr{S}$ (34) $\displaystyle Z_{h}^{\mathbf{u}}(o|s)$
$\displaystyle=\frac{1}{2}\quad\forall o\in\mathscr{O},s\in\mathscr{S}$ (35)

For any policy $\pi\in\varPi$ and any trajectory
$\tau=(o_{1:H},a_{1:H})\in\mathscr{T}$, the trajectory probability satisfies

$\displaystyle\mathbb{P}_{\theta}^{\pi}(\tau)$
$\displaystyle=\pi(\tau)\cdot\dfrac{1}{2^{H-1}}\left(\frac{1}{2}+\epsilon\iota_{\theta}(a_{1:H-1},o_{H})\right)$
(36) $\displaystyle\mathbb{P}_{\mathbf{u}}^{\pi}(\tau)$
$\displaystyle=\pi(\tau)\cdot\dfrac{1}{2^{H}}$ (37)

where

$\displaystyle\iota_{\theta}(a_{1:H-1},o_{H}):=\begin{cases}1&\text{if
}a_{1:H-1}=\theta\text{ and }o_{H}=0\\\ -1&\text{if }a_{1:H-1}=\theta\text{
and }o_{H}=1\\\ 0&\text{if }a_{1:H-1}\neq\theta\end{cases}$ (38)

Since the learning agent has perfect recall, the minimum Bayesian regret
(equivalently, the maximum total expected reward) in $K$ episodes can be
attained through some deterministic learning algorithm $\phi$. Therefore,
without loss of generality, we only consider deterministic learning
algorithms. More specifically, we assume that the learning algorithm is given
by $\phi=(\phi_{j})_{j\in\mathbb{N}}$ and $\phi_{j}$ maps the trajectories in
the first $j-1$ episodes to a policy in $\varPi$. Fix $\phi$, let
$\mathbb{P}_{\theta}$ and $\mathbb{E}_{\theta}$ represent the probability
distribution and expectation of random variables involving (potentially)
multiple episodes, assuming that the underlying POMDP is given by $\theta$,
and the learning algorithm $\phi$ is applied. Similarly, let
$\mathbb{P}_{\mathbf{u}}$ and $\mathbb{E}_{\mathbf{u}}$ represent the
probability distribution and expectation of random variables under the POMDP
defined by $(b_{1}^{\mathbf{u}},T^{\mathbf{u}},Z^{\mathbf{u}})$ and learning
algorithm $\phi$.

For each $\theta\in\varTheta$, define
$N_{\theta,K}:=\sum_{j=1}^{K}\bm{1}_{\\{a_{1:H-1}^{j}=\theta\\}}$ to be a
random variable denoting the number of episodes in which the learning agent’s
action sequence matches $\theta$.

######  Lemma 5.

For any $\theta\in\varTheta$, we have

$\mathbb{E}_{\theta}[N_{\theta,K}]\leq\mathbb{E}_{\mathbf{u}}[N_{\theta,K}]+\frac{K}{2}\sqrt{-\mathbb{E}_{\mathbf{u}}[N_{\theta,K}]\log(1-4\epsilon^{2})}$
(39)

###### Proof.

First, we have

$\displaystyle\quad~{}\mathbb{E}_{\theta}[N_{\theta,K}]-\mathbb{E}_{\mathbf{u}}[N_{\theta,K}]$
(40)
$\displaystyle\leq\sum_{\tilde{\tau}^{1:K}:\tilde{\tau}^{j}=(\tilde{o}_{1:H}^{j},\tilde{a}_{1:H}^{j})\in\mathscr{T}}\left[\sum_{j=1}^{K}\bm{1}_{\\{\tilde{a}_{1:H-1}^{j}=\theta\\}}\right][\mathbb{P}_{\theta}(\tilde{\tau}^{1:K})-\mathbb{P}_{\mathbf{u}}(\tilde{\tau}^{1:K})]_{+}$
(41) $\displaystyle\leq
K\|\mathbb{P}_{\mathbf{u}}(\tau^{1:K})-\mathbb{P}_{\theta}(\tau^{1:K})\|_{\mathrm{TV}}$
(42)

By Pinsker’s Inequality,

$\displaystyle\|\mathbb{P}_{\mathbf{u}}(\tau^{1:K})-\mathbb{P}_{\theta}(\tau^{1:K})\|_{\mathrm{TV}}\leq\sqrt{\dfrac{1}{2}\mathbf{D}_{\mathrm{KL}}(\mathbb{P}_{\mathbf{u}}(\tau^{1:K})\|\mathbb{P}_{\theta}(\tau^{1:K}))}$
(43)

where $\mathbf{D}_{\mathrm{KL}}(\mu_{1}\|\mu_{2})$ is the KL divergence
between distributions $\mu_{1}$ and $\mu_{2}$. Using the chain rule for the KL
divergence, we have

$\displaystyle\quad~{}\mathbf{D}_{\mathrm{KL}}(\mathbb{P}_{\mathbf{u}}(\tau^{1:K})\|\mathbb{P}_{\theta}(\tau^{1:K}))$
(44)
$\displaystyle=\sum_{j=1}^{K}\mathbf{D}_{\mathrm{KL}}(\mathbb{P}_{\mathbf{u}}(\tau^{j}|\tau^{1:j-1})\|\mathbb{P}_{\theta}(\tau^{j}|\tau^{1:j-1}))$
(45)
$\displaystyle=\sum_{j=1}^{K}\sum_{\tilde{\tau}^{1:j-1}\in\mathscr{T}^{j-1}}\mathbb{P}_{\mathbf{u}}(\tilde{\tau}^{1:j-1})\mathbf{D}_{\mathrm{KL}}(\mathbb{P}_{\mathbf{u}}(\tau^{j}|\tilde{\tau}^{1:j-1})\|\mathbb{P}_{\theta}(\tau^{j}|\tilde{\tau}^{1:j-1}))$
(46)

where in (45),
$\mathbf{D}_{\mathrm{KL}}(\mathbb{P}_{\mathbf{u}}(\tau^{j}|\tau^{1:j-1})\|\mathbb{P}_{\theta}(\tau^{j}|\tau^{1:j-1}))$
is the conditional KL divergence.

For a fixed history $\tilde{\tau}^{1:j-1}$ before episode $j$, let
$\tilde{\pi}^{j}=\phi_{j}(\tilde{\tau}^{1:j-1})$ be the corresponding policy
the learning algorithm uses in episode $j$. Using (36) and (37) we have

$\displaystyle\quad~{}\mathbf{D}_{\mathrm{KL}}(\mathbb{P}_{\mathbf{u}}(\tau^{j}|\tilde{\tau}^{1:j-1})\|\mathbb{P}_{\theta}(\tau^{j}|\tilde{\tau}^{1:j-1}))$
(47)
$\displaystyle=\sum_{\tilde{\tau}\in\mathscr{T}}\mathbb{P}_{\mathbf{u}}^{\tilde{\pi}^{j}}(\tilde{\tau})\log\left(\dfrac{\mathbb{P}_{\mathbf{u}}^{\tilde{\pi}^{j}}(\tilde{\tau})}{\mathbb{P}_{\theta}^{\tilde{\pi}^{j}}(\tilde{\tau})}\right)$
(48)
$\displaystyle=\mathbb{P}_{\mathbf{u}}^{\tilde{\pi}^{j}}(a_{1:H-1}=\theta,o_{H}=0)\log\left(\dfrac{1}{1+2\epsilon}\right)+\mathbb{P}_{\mathbf{u}}^{\tilde{\pi}^{j}}(a_{1:H-1}=\theta,o_{H}=1)\log\left(\dfrac{1}{1-2\epsilon}\right)$
(49)
$\displaystyle=\dfrac{1}{2}\mathbb{P}_{\mathbf{u}}^{\tilde{\pi}^{j}}(a_{1:H-1}=\theta)\left[\log\left(\dfrac{1}{1+2\epsilon}\right)+\log\left(\dfrac{1}{1-2\epsilon}\right)\right]$
(50)
$\displaystyle=\dfrac{1}{2}\mathbb{P}_{\mathbf{u}}^{\tilde{\pi}^{j}}(a_{1:H-1}=\theta)[-\log(1-4\epsilon^{2})]=\dfrac{1}{2}\mathbb{P}_{\mathbf{u}}(a_{1:H-1}^{j}=\theta|\tilde{\tau}^{1:j-1})[-\log(1-4\epsilon^{2})].$
(51)

Therefore,

$\displaystyle\quad~{}\mathbf{D}_{\mathrm{KL}}(\mathbb{P}_{\mathbf{u}}(\tau^{1:K})\|\mathbb{P}_{\theta}(\tau^{1:K}))$
(52)
$\displaystyle=\dfrac{1}{2}\sum_{j=1}^{K}\sum_{\tilde{\tau}^{1:j-1}}\mathbb{P}_{\mathbf{u}}(\tilde{\tau}^{1:j-1})\mathbb{P}_{\mathbf{u}}(a_{1:H-1}^{j}=\theta|\tilde{\tau}^{1:j-1})\left[-\log(1-4\epsilon^{2})\right]$
(53)
$\displaystyle=\dfrac{1}{2}\sum_{j=1}^{K}\mathbb{P}_{\mathbf{u}}(a_{1:H-1}^{j}=\theta)\left[-\log(1-4\epsilon^{2})\right]=-\dfrac{1}{2}\mathbb{E}_{\mathbf{u}}[N_{\theta,K}]\log\left(1-4\epsilon^{2}\right)$
(54)

and finally,

$\displaystyle\mathbb{E}_{\theta}[N_{\theta,K}]-\mathbb{E}_{\mathbf{u}}[N_{\theta,K}]$
$\displaystyle\leq
K\sqrt{\dfrac{1}{2}\mathbf{D}_{\mathrm{KL}}(\mathbb{P}_{\mathbf{u}}(\tau^{1:K})\|\mathbb{P}_{\theta}(\tau^{1:K}))}$
(55)
$\displaystyle=\dfrac{K}{2}\sqrt{-\mathbb{E}_{\mathbf{u}}[N_{\theta,K}]\log\left(1-4\epsilon^{2}\right)}$
(56)

∎

The conditional expected total reward $G_{\theta,K}$ under the algorithm
$\phi$, given that the underlying POMDP is $\theta$, satisfies

$\displaystyle G_{\theta,K}$
$\displaystyle:=\mathbb{E}_{\theta}\left[\sum_{j=1}^{K}\sum_{h=1}^{H}r_{h}(o_{h}^{j},a_{h}^{j})\right]=\sum_{j=1}^{K}\mathbb{P}_{\theta}(o_{H}^{j}=0)$
(57)
$\displaystyle=\sum_{j=1}^{K}\left[\left(\frac{1}{2}+\epsilon\right)\mathbb{P}_{\theta}(a_{1:H-1}^{j}=\theta)+\frac{1}{2}\mathbb{P}_{\theta}(a_{1:H-1}^{j}\neq\theta)\right]$
(58)
$\displaystyle=\dfrac{K}{2}+\epsilon\sum_{j=1}^{K}\mathbb{P}_{\theta}(a_{1:H-1}^{j}=\theta)=\frac{K}{2}+\epsilon\mathbb{E}_{\theta}[N_{\theta,K}]$
(59)

Define $\bar{N}_{\theta,K}:=\mathbb{E}_{\mathbf{u}}[N_{\theta,K}]$ to be a
fixed function of $\theta$ and $K$. Using Lemma 5, we have

$\displaystyle G_{\theta,K}$
$\displaystyle\leq\frac{K}{2}+\epsilon\left(\bar{N}_{\theta,K}+\dfrac{K}{2}\sqrt{-\bar{N}_{\theta,K}\log\left(1-4\epsilon^{2}\right)}\right)$
(60)

If $\theta^{*}$ is randomly drawn from $\varTheta$ following $\nu^{1}$, the
uniform distribution on $\varTheta$, we have

$\displaystyle\mathbb{E}_{\theta^{*}\sim\nu^{1}}\left[\bar{N}_{\theta^{*},K}\right]$
$\displaystyle=\dfrac{1}{A^{H-1}}\sum_{\theta\in\varTheta}\bar{N}_{\theta,K}=\dfrac{1}{A^{H-1}}\sum_{\theta\in\varTheta}\mathbb{E}_{\mathbf{u}}[N_{\theta,K}]$
(61)
$\displaystyle=\dfrac{1}{A^{H-1}}\mathbb{E}_{\mathbf{u}}\left[\sum_{\theta\in\varTheta}N_{\theta,K}\right]=\dfrac{K}{A^{H-1}},$
(62)

and the expected total reward satisfies

$\displaystyle\quad~{}\mathbb{E}_{\theta^{*}\sim\nu^{1}}\left[G_{\theta^{*},K}\right]$
(63)
$\displaystyle\leq\dfrac{K}{2}+\epsilon\left(\mathbb{E}_{\theta^{*}\sim\nu^{1}}[\bar{N}_{\theta^{*},K}]+\dfrac{K}{2}\mathbb{E}_{\theta^{*}\sim\nu^{1}}\left[\sqrt{\bar{N}_{\theta^{*},K}}\right]\sqrt{-\log(1-4\epsilon^{2})}\right)$
(64)
$\displaystyle\leq\dfrac{K}{2}+\epsilon\left(\mathbb{E}_{\theta^{*}\sim\nu^{1}}[\bar{N}_{\theta^{*},K}]+\dfrac{K}{2}\sqrt{\mathbb{E}_{\theta^{*}\sim\nu^{1}}\left[\bar{N}_{\theta^{*},K}\right]}\sqrt{-\log(1-4\epsilon^{2})}\right)$
(65)
$\displaystyle=\dfrac{K}{2}+\epsilon\left(\dfrac{K}{A^{H-1}}+\dfrac{K}{2}\sqrt{\dfrac{K}{A^{H-1}}}\sqrt{-\log(1-4\epsilon^{2})}\right)$
(66)

For each POMDP parameterized by $\theta\in\varTheta$, if one uses the open-
loop policy $a_{h}=\theta_{h}$ for $h\in[H-1]$, then the expected total reward
is $\frac{1}{2}+\epsilon$. This means that the optimal value satisfies
$V_{\theta}^{*}\geq\frac{1}{2}+\epsilon$.

Therefore, the Bayesian regret is lower bounded by

$\displaystyle\mathrm{BReg}(\phi,K)$
$\displaystyle\geq\left(\dfrac{1}{2}+\epsilon\right)K-\mathbb{E}_{\theta^{*}\sim\nu^{1}}\left[G_{\theta^{*},K}\right]$
(67)
$\displaystyle\geq\epsilon\left(K-\dfrac{K}{A^{H-1}}-\dfrac{K}{2}\sqrt{\dfrac{K}{A^{H-1}}}\sqrt{-\log(1-4\epsilon^{2})}\right)$
(68)

Theorem 1 can then be established by choosing
$\epsilon=\frac{1}{4}\sqrt{\frac{A^{H-1}}{K}}$ and the inequality
$-\log(1-x)\leq 4\log\left(\frac{4}{3}\right)x$ for $x\in[0,\frac{1}{4}]$ in
the same way as in Auer et al. (2002).

##  Appendix C Proof of Regret Upper Bounds

In this section, we prove both Theorem 1 and Theorem 2. Our proofs are
inspired by the framework for establishing regret bounds for posterior
sampling by Russo and Van Roy (2014) and the techniques of Liu et al. (2022).

In this section, $\mathbb{P}_{\theta}^{\pi}$ is seen as a probability
distribution on $\mathscr{T}$, the set of observable trajectories. Without
loss of generality, we assume that the parameterization is direct, i.e.,
$\varTheta$ is a subset of $[0,1]^{S+(H-1)S^{2}A+HSO}$, where the coordinates
represent $(b_{1},T,Z)$.

While our parameter set $\varTheta$ could be uncountably infinite, we
construct a finite set $\bar{\varTheta}$ that serves as a surrogate for
$\varTheta$ for technical reasons.

######  Proposition 4.

For any $\epsilon>0$ such that $\epsilon^{-1}\in\mathbb{N}$, there exists a
finite set $\bar{\varTheta}\subset[0,1]^{S+(H-1)S^{2}A+HSO}$ and a measurable
function $\iota:\varTheta\mapsto\bar{\varTheta}$ such that

$\log(|\bar{\varTheta}|)\leq(HS^{2}A+HSO)\log\left(\dfrac{\max\\{S,O\\}}{\epsilon}+1\right)$
(69)

and the following holds: For any $\theta\in\varTheta$,
$\theta^{\prime}=\iota(\theta)$ satisfies

$\displaystyle\|\mathbb{P}_{\theta^{\prime}}^{\pi}-\mathbb{P}_{\theta}^{\pi}\|_{\mathrm{TV}}\leq
2H\epsilon\qquad\forall\pi\in\varPi$ (70)
$\displaystyle\mathbb{P}_{\theta^{\prime}}^{-}(\tau)\geq(1+\epsilon)^{-2H}\mathbb{P}_{\theta}^{-}(\tau)\qquad\forall\tau\in\mathscr{T}$
(71)

Recall that $\mathbb{P}_{\theta}^{-}$ represents the open-loop probability and
is defined in (2). The proof of Proposition 4 is presented in Appendix C.1. In
the rest of the section, we set $\epsilon=1/(2HK)$ and assume that
$\bar{\varTheta}$ and $\iota$ satisfy the condition of Proposition 4. By
removing points in $\bar{\varTheta}$, without loss of generality, we assume
that $\iota$ is surjective, i.e., for every $\bar{\theta}\in\bar{\varTheta}$
there exists $\theta\in\varTheta$ such that $\bar{\theta}=\iota(\theta)$.

Define the log-likelihood function

$\ell(\theta,\mathcal{D}_{k}):=\sum_{j=1}^{k-1}\log(\mathbb{P}_{\theta}^{\pi^{j}}(\tau^{j}))$
(72)

and the maximum log-likelihood function

$\bar{\ell}^{*}(\mathcal{D}_{k}):=\max_{\theta\in\bar{\varTheta}}\ell(\theta,\mathcal{D}_{k}).$
(73)

Note that in (73) the maximum is taken over the finite set $\bar{\varTheta}$,
not $\varTheta$.

Quick Fact 1: If $\bar{\theta}=\iota(\theta)$, then

$\displaystyle\ell(\bar{\theta},\mathcal{D}_{k})$
$\displaystyle\geq\ell(\theta,\mathcal{D}_{k})-2(k-1)H\log(1+\epsilon)$ (74)
$\displaystyle\geq\ell(\theta,\mathcal{D}_{k})-2(k-1)H\epsilon\geq\ell(\theta,\mathcal{D}_{k})-1$
(75)

Quick Fact 2: As a corollary to Quick Fact 1, for any $\theta\in\varTheta$,
$\ell(\theta,\mathcal{D}_{k})\leq\bar{\ell}^{*}(\mathcal{D}_{k})+1$.

We now define the discrete confidence set

$\bar{\varTheta}(\mathcal{D}_{k}):=\\{\bar{\theta}\in\bar{\varTheta}:\ell(\bar{\theta},\mathcal{D}_{k})\geq\bar{\ell}^{*}(\mathcal{D}_{k})-\log(K|\bar{\varTheta}|)-1\\}.$
(76)

The following lemmas form the foundation of our proof. In Lemma 6, we bound
the Bayesian regret with the quality of the confidence set in terms of the TV
distance between distributions on trajectories. In Lemma 7, we provide certain
guarantee on the quality of the confidence sets.

######  Lemma 6 (Lemma 1, restated).

The Bayesian regret under PSRL algorithm can be bounded by

$\mathrm{BReg}(\phi^{\mathrm{PSRL}},K)\leq
2H+H\mathbb{E}\left[\sum_{k=1}^{K}\max_{\bar{\theta}\in\bar{\varTheta}(\mathcal{D}_{k})}\|\mathbb{P}_{\bar{\theta}}^{\tilde{\pi}^{k}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}\|_{\mathrm{TV}}\right]$
(77)

######  Lemma 7 (Lemma 2, restated).

Under any learning algorithm $\phi$, with probability at least
$1-\frac{1}{K}$,

$\begin{split}\max_{k\in[K]}\max_{\bar{\theta}\in\bar{\varTheta}(\mathcal{D}_{k})}\sum_{j=1}^{k}\|\mathbb{P}_{\bar{\theta}}^{\pi^{j}}-\mathbb{P}_{\theta^{*}}^{\pi^{j}}\|_{\mathrm{TV}}^{2}\leq
3\log(K|\bar{\varTheta}|)+3\end{split}$ (78)

The proofs of Lemmas 6 and 7 can be found in Appendices C.2 and C.3.

Given the above lemmas, to obtain an upper bound on the Bayesian regret, the
remaining task is purely algebraic and can be described as follows: Use an
upper bound of

$\displaystyle\sum_{j=1}^{k}\|\mathbb{P}_{\check{\theta}^{k}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}^{2}$
(TR-MLE)

to derive an upper bound of

$\displaystyle\sum_{j=1}^{K}\|\mathbb{P}_{\check{\theta}^{j}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}$
(TR-REG)

where
$\check{\theta}^{k}\in\operatorname*{arg\,max}_{\bar{\theta}\in\bar{\varTheta}(\mathcal{D}_{k})}\|\mathbb{P}_{\bar{\theta}}^{\tilde{\pi}^{k}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}\|_{\mathrm{TV}}$.

The key difference between (TR-MLE) and (TR-REG) lies in the indexing, where
the former measures the difference of the _latest_ estimated environment with
the true environment under historical policies, while the latter measures the
cumulative differences derived from the estimated environment _at the time_.

BReg($\phi,K$)Lemma 6(TR-REG)(TR-MLE)$\log(K|\bar{\varTheta}|)$Lemma 7(OP-
REG)(OP-MLE)Step 1Step 3Step 2Lemma 3 Figure 1: Proof road map of Theorem 1
(dashed) and Theorem 2 (solid). For Theorem 2, the bound is developed via an
auxiliary quantity called the projected operator distances. In this diagram,
$A\rightarrow B$ means “A is upper bounded by some function of B.” While “TR”
stands for “trajectory-based”, “OP” stands for “operator-based.”

###  C.1 Proof of Proposition 4

For any finite set $\mathcal{X}$, define
$\bar{\Delta}^{\epsilon}(\mathcal{X})\subset\Delta(\mathcal{X})$ by

$\bar{\Delta}^{\epsilon}(\mathcal{X})=\left\\{\dfrac{v}{\|v\|_{1}}:\dfrac{v_{x}}{\epsilon/|\mathcal{X}|}\in\mathbb{Z}_{+},v_{x}\leq
1\quad\forall x\in\mathcal{X}\right\\}.$ (79)

Then we have
$|\bar{\Delta}^{\epsilon}(\mathcal{X})|\leq\left(\frac{|\mathcal{X}|}{\epsilon}+1\right)^{|\mathcal{X}|}$.
Furthermore, for any $\mu\in\Delta(\mathcal{X})$, set

$v=\dfrac{1}{|\mathcal{X}|/\epsilon}\lceil(|\mathcal{X}|/\epsilon)\mu\rceil,\qquad\bar{\mu}=\dfrac{v}{\|v\|_{1}},$
(80)

we have $\|v-\mu\|_{1}\leq\epsilon$ and

$\displaystyle\|v\|_{1}$ $\displaystyle\leq\|\mu\|_{1}+\|v-\mu\|_{1}\leq
1+\epsilon.$ (81)

Therefore,

$\displaystyle\|\mu-\bar{\mu}\|_{\mathrm{TV}}$
$\displaystyle\leq\dfrac{1}{2}\|\mu-v\|_{1}+\dfrac{1}{2}\|v-\bar{\mu}\|_{1}\leq\dfrac{1}{2}\epsilon+\dfrac{1}{2}\left(\|v\|_{1}-1\right)\leq\epsilon$
(82) $\displaystyle\bar{\mu}$
$\displaystyle\geq\dfrac{\mu}{\|v\|_{1}}\geq\dfrac{\mu}{1+\epsilon}.$ (83)

Now, define
$\bar{\varTheta}=\left[\bar{\Delta}^{\epsilon}(\mathscr{S})\right]^{1+(H-1)SA}\times\left[\bar{\Delta}^{\epsilon}(\mathscr{O})\right]^{HS}$.
We have

$\displaystyle\log|\bar{\varTheta}|$
$\displaystyle\leq[1+(H-1)SA]S\log\left(\dfrac{S}{\epsilon}+1\right)+HSO\log\left(\dfrac{O}{\epsilon}+1\right)$
(84)
$\displaystyle\leq(HS^{2}A+HSO)\log\left(\dfrac{\max\\{S,O\\}}{\epsilon}+1\right).$
(85)

For any $\theta\in\varTheta$, let $\bar{\theta}\in\bar{\varTheta}$ be such
that each component of $\bar{\theta}$ is obtained by quantizing and
renormalizing the corresponding component in $\theta$ according to (80). Then,
for any $\tau=(o_{h},a_{h})_{h=1}^{H}\in\mathscr{T}$, using (2) and (83) we
have
$\mathbb{P}_{\bar{\theta}}^{-}(\tau)\geq(1+\epsilon)^{-2H}\mathbb{P}_{\theta}^{-}(\tau)$,
establishing (71).

Next we establish (70) for $\theta$ and $\bar{\theta}$. Define a coupled POMDP
with state space $\mathscr{S}^{2}$, action space $\mathscr{A}^{2}$,
observation space $\mathscr{O}^{2}$, horizon $H$ as follows

  * •

The initial distribution $\bm{b}_{1}^{\theta,\bar{\theta}}$ is an optimal
coupling222A coupling of two distributions
$\nu_{1},\nu_{2}\in\Delta(\varOmega)$ is a joint distribution
$\nu_{12}\in\Delta(\varOmega\times\varOmega)$ with marginal distributions
$\nu_{1}$ and $\nu_{2}$. An optimal coupling (Levin and Peres, 2017) is a
coupling that attains the minimum value of the mismatch probability
$\nu_{12}(\\{(\omega_{1},\omega_{2}):\omega_{1}\neq\omega_{2}\\})$, which
equals $\|\nu_{1}-\nu_{2}\|_{\mathrm{TV}}$. See Levin and Peres (2017) for a
construction of such coupling. of $b_{1}^{\theta}$ and $b_{1}^{\bar{\theta}}$;

  * •

The transition kernel
$\mathbf{T}^{\theta,\bar{\theta}}:(\mathscr{S}\times\mathscr{A})^{2}\mapsto\Delta(\mathscr{S}^{2})$
is such that for any
$h\in[H-1],s,\bar{s}\in\mathscr{S},a,\bar{a}\in\mathscr{A}$, the joint
distribution $\mathbf{T}_{h}^{\theta,\bar{\theta}}(s,a,\bar{s},\bar{a})$ is an
optimal coupling of $T_{h}^{\theta}(s,a)$ and
$T_{h}^{\bar{\theta}}(\bar{s},\bar{a})$.

  * •

The observation kernel
$\mathbf{Z}^{\theta,\bar{\theta}}:\mathscr{S}^{2}\mapsto\Delta(\mathscr{O}^{2})$
is such that for any
$h\in[H],s,\bar{s}\in\mathscr{S},o,\bar{o}\in\mathscr{O}$, the joint
distribution $\mathbf{Z}_{h}^{\theta,\bar{\theta}}(s,\bar{s})$ is an optimal
coupling of $Z^{\theta}_{h}(s)$ and $Z^{\bar{\theta}}_{h}(\bar{s})$.

In the coupled POMDP, at any given step, if the current states are the same
for both components, then the current observation would be the same with
probability at least $1-\epsilon$; if the current state and action pairs are
the same for both components, then the next states would be the same with
probability at least $1-\epsilon$. Consequently, if the same policy
$\pi\in\varPi$ is applied on both components, then with probability at least
$(1-\epsilon)^{2H}\geq 1-2H\epsilon$, the two trajectories
$\tau,\bar{\tau}\in\mathscr{T}$ coincide. Due to the fact that the TV distance
equals the minimum mismatch probability of any coupling (Levin and Peres,
2017), we conclude that
$\|\mathbb{P}_{\theta}^{\pi}-\mathbb{P}_{\bar{\theta}}^{\pi}\|_{\mathrm{TV}}\leq
2H\epsilon$.

###  C.2 Proof of Lemma 6 (Lemma 1, restated)

First, the episode $k$ regret satisfies

$\displaystyle\quad~{}\mathbb{E}[V_{\theta^{*}}^{*}]-\mathbb{E}[V_{\theta^{*}}^{\tilde{\pi}^{k}}]$
(86)
$\displaystyle=\mathbb{E}[V_{\tilde{\theta}^{k}}^{*}]-\mathbb{E}[V_{\theta^{*}}^{\tilde{\pi}^{k}}]=\mathbb{E}[V_{\tilde{\theta}^{k}}^{\tilde{\pi}^{k}}-V_{\theta^{*}}^{\tilde{\pi}^{k}}]$
(87)
$\displaystyle=\mathbb{E}\left[\sum_{\tau=(o_{h},a_{h})_{h=1}^{H}\in\mathscr{T}}[\mathbb{P}_{\tilde{\theta}^{k}}^{\tilde{\pi}^{k}}(\tau)-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}(\tau)]\sum_{h=1}^{H}r_{h}(o_{h},a_{h})\right]$
(88) $\displaystyle\leq
H\mathbb{E}\left[\sum_{\tau\in\mathscr{T}}[\mathbb{P}_{\tilde{\theta}^{k}}^{\tilde{\pi}^{k}}(\tau)-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}(\tau)]_{+}\right]=H\mathbb{E}[\|\mathbb{P}_{\tilde{\theta}^{k}}^{\tilde{\pi}^{k}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}\|_{\mathrm{TV}}]$
(89)

where in the first identity we used the fact that $\theta^{*}$ has the same
unconditional distribution as $\tilde{\theta}^{k}$.

Using Lemma 10 and the fact that conditioning on $\mathcal{D}_{k}$,
$\theta^{*}$ has the same distribution as $\tilde{\theta}^{k}$, we have
$\ell(\tilde{\theta}^{k},\mathcal{D}_{k})\geq\bar{\ell}^{*}(\mathcal{D}_{k})-\log(K|\bar{\varTheta}|)$
with probability at least $1-\frac{1}{K}$. Let
$\vartheta^{k}=\iota\left(\tilde{\theta}^{k}\right)$, we have
$\ell(\vartheta^{k},\mathcal{D}_{k})\geq\ell(\tilde{\theta}^{k},\mathcal{D}_{k})-1$
almost surely due to Quick Fact 1. Therefore, we conclude that

$\displaystyle\mathbb{P}\left(\vartheta^{k}\in\bar{\varTheta}(\mathcal{D}_{k})\right)$
$\displaystyle=\mathbb{P}\left(\ell(\vartheta^{k},\mathcal{D}_{k})\geq\bar{\ell}^{*}(\mathcal{D}_{k})-\log(K|\bar{\varTheta}|)-1\right)\geq
1-\dfrac{1}{K}$ (90)

Also note that
$\|\mathbb{P}_{\tilde{\theta}^{k}}^{\tilde{\pi}^{k}}-\mathbb{P}_{\vartheta^{k}}^{\tilde{\pi}^{k}}\|_{\mathrm{TV}}\leq
2H\epsilon=\frac{1}{K}$ almost surely. Therefore

$\displaystyle\mathbb{E}[\|\mathbb{P}_{\tilde{\theta}^{k}}^{\tilde{\pi}^{k}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}\|_{\mathrm{TV}}]$
$\displaystyle\leq\mathbb{E}[\|\mathbb{P}_{\vartheta^{k}}^{\tilde{\pi}^{k}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}\|_{\mathrm{TV}}]+\dfrac{1}{K}$
(91)
$\displaystyle\leq\mathbb{E}[\|\mathbb{P}_{\vartheta^{k}}^{\tilde{\pi}^{k}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}\|_{\mathrm{TV}}\cdot\bm{1}_{\\{\vartheta^{k}\in\bar{\varTheta}(\mathcal{D}_{k})\\}}]+\mathbb{P}(\vartheta^{k}\not\in\bar{\varTheta}(\mathcal{D}_{k}))+\dfrac{1}{K}$
(92)
$\displaystyle\leq\mathbb{E}\left[\max_{\bar{\theta}\in\bar{\varTheta}(\mathcal{D}_{k})}\|\mathbb{P}_{\bar{\theta}}^{\tilde{\pi}^{k}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}\|_{\mathrm{TV}}\right]+\dfrac{2}{K}$
(93)

and finally

$\displaystyle\mathrm{BReg}(\phi^{\mathrm{PSRL}},K)$
$\displaystyle\leq\sum_{k=1}^{K}H\left(\mathbb{E}\left[\max_{\bar{\theta}\in\bar{\varTheta}(\mathcal{D}_{k})}\|\mathbb{P}_{\bar{\theta}}^{\tilde{\pi}^{k}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}\|_{\mathrm{TV}}\right]+\dfrac{2}{K}\right)$
(94) $\displaystyle\leq
2H+H\mathbb{E}\left[\sum_{k=1}^{K}\max_{\bar{\theta}\in\bar{\varTheta}(\mathcal{D}_{k})}\|\mathbb{P}_{\bar{\theta}}^{\tilde{\pi}^{k}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}\|_{\mathrm{TV}}\right].$
(95)

###  C.3 Proof of Lemma 7 (Lemma 2, restated)

Consider the distribution on the learning process conditioning on
$\theta^{*}=\theta$. Fix $\theta^{\prime}\in\bar{\varTheta}$. Define
$\mathcal{F}_{k-1}$ to be the $\sigma$-algebra generated from
$(\mathcal{D}_{k},{\pi}^{k})$ and
$Z_{k}=\log\left(\dfrac{\mathbb{P}_{\theta^{\prime}}^{{\pi}^{k}}(\tau^{k})}{\mathbb{P}_{\theta}^{{\pi}^{k}}(\tau^{k})}\right)$.
Then the quantity $\psi_{k}$ defined in Lemma 8 satisfies

$\displaystyle\psi_{k}\left(\frac{1}{2}\right)$
$\displaystyle=\log\mathbb{E}_{\theta}\left[\exp\left(\frac{1}{2}\log\left(\dfrac{\mathbb{P}_{\theta^{\prime}}^{{\pi}^{k}}(\tau^{k}))}{\mathbb{P}_{\theta}^{{\pi}^{k}}(\tau^{k})}\right)\right)~{}\Big{|}~{}\mathcal{D}_{k},{\pi}^{k}\right]$
(96)
$\displaystyle=\log\left(\sum_{\tau\in\mathscr{T}:\mathbb{P}_{\theta}^{{\pi}^{k}}(\tau)>0}\mathbb{P}_{\theta}^{{\pi}^{k}}(\tau)\sqrt{\dfrac{\mathbb{P}_{\theta^{\prime}}^{{\pi}^{k}}(\tau)}{\mathbb{P}_{\theta}^{{\pi}^{k}}(\tau)}}\right)=\log\left(\sum_{\tau\in\mathscr{T}}\sqrt{\mathbb{P}_{\theta^{\prime}}^{{\pi}^{k}}(\tau)\mathbb{P}_{\theta}^{{\pi}^{k}}(\tau)}\right)$
(97)
$\displaystyle\leq\left(\sum_{\tau\in\mathscr{T}}\sqrt{\mathbb{P}_{\theta^{\prime}}^{{\pi}^{k}}(\tau)\mathbb{P}_{\theta}^{{\pi}^{k}}(\tau)}\right)-1=\sum_{\tau\in\mathscr{T}}\left(\sqrt{\mathbb{P}_{\theta^{\prime}}^{{\pi}^{k}}(\tau)\mathbb{P}_{\theta}^{{\pi}^{k}}(\tau)}-\frac{1}{2}\mathbb{P}_{\theta^{\prime}}^{{\pi}^{k}}(\tau)-\frac{1}{2}\mathbb{P}_{\theta}^{{\pi}^{k}}(\tau)\right)$
(98)
$\displaystyle=-\dfrac{1}{2}\sum_{\tau\in\mathscr{T}}\left(\sqrt{\mathbb{P}_{\theta^{\prime}}^{{\pi}^{k}}(\tau)}-\sqrt{\mathbb{P}_{\theta}^{{\pi}^{k}}(\tau)}\right)^{2}\leq-\dfrac{1}{2}\|\mathbb{P}_{\theta^{\prime}}^{{\pi}^{k}}-\mathbb{P}_{\theta}^{{\pi}^{k}}\|_{\mathrm{TV}}^{2}$
(99)

where we have used the inequality $\log(t)\leq t-1$, and the last inequality
is due to Lemma 9.

Applying Lemma 8, for any $\xi>0$, with probability at least $1-e^{-\xi}$,

$\displaystyle\sum_{j=1}^{k-1}\left(\frac{1}{2}Z_{j}+\frac{1}{2}\|\mathbb{P}_{\theta^{\prime}}^{{\pi}^{j}}-\mathbb{P}_{\theta}^{{\pi}^{j}}\|_{\mathrm{TV}}^{2}\right)\leq\sum_{j=1}^{k-1}\left(\frac{1}{2}Z_{j}-\psi_{j}\left(\frac{1}{2}\right)\right)<\xi\qquad\forall
k\in[K]$ (100)

or equivalently,

$\displaystyle\sum_{j=1}^{k-1}\|\mathbb{P}_{\theta^{\prime}}^{{\pi}^{j}}-\mathbb{P}_{\theta}^{{\pi}^{j}}\|_{\mathrm{TV}}^{2}<2\xi-\sum_{j=1}^{k-1}Z_{j}=2\xi+\ell(\theta,\mathcal{D}_{k})-\ell(\theta^{\prime},\mathcal{D}_{k})\qquad\forall
k\in[K]$ (101)

Using the fact that TV distances are bounded by 1, adding in the $k$-th term,
(101) implies

$\displaystyle\max_{k\in[K]}\sum_{j=1}^{k}\|\mathbb{P}_{\theta^{\prime}}^{{\pi}^{j}}-\mathbb{P}_{\theta}^{{\pi}^{j}}\|_{\mathrm{TV}}^{2}<2\xi+1+\ell(\theta,\mathcal{D}_{k})-\ell(\theta^{\prime},\mathcal{D}_{k}).$
(102)

Now, if $\theta^{\prime}\in\bar{\varTheta}(\mathcal{D}_{k})$, then

$\displaystyle\quad~{}\ell(\theta,\mathcal{D}_{k})-\ell(\theta^{\prime},\mathcal{D}_{k})\leq\bar{\ell}^{*}(\mathcal{D}_{k})+1-\ell(\theta^{\prime},\mathcal{D}_{k})\leq\log(K|\bar{\varTheta}|)+2$
(103)

where the first inequality is due to Quick Fact 2, and the second inequality
is due to the definition of $\bar{\varTheta}(\mathcal{D}_{k})$.

Finally, we have

$\displaystyle\quad~{}\mathbb{P}_{\theta}\left(\max_{k\in[K]}\max_{\theta^{\prime}\in\bar{\varTheta}(\mathcal{D}_{k})}\sum_{j=1}^{k-1}\|\mathbb{P}_{\theta^{\prime}}^{{\pi}^{j}}-\mathbb{P}_{\theta}^{{\pi}^{j}}\|_{\mathrm{TV}}^{2}\geq
3\log\left(K|\bar{\varTheta}|\right)+3\right)$ (104)
$\displaystyle=\mathbb{P}_{\theta}\left(\exists
k\in[K],\theta^{\prime}\in\bar{\varTheta}(\mathcal{D}_{k}),~{}~{}\sum_{j=1}^{k-1}\|\mathbb{P}_{\theta^{\prime}}^{{\pi}^{j}}-\mathbb{P}_{\theta}^{{\pi}^{j}}\|_{\mathrm{TV}}^{2}\geq
3\log\left(K|\bar{\varTheta}|\right)+3\right)$ (105)
$\displaystyle\leq\mathbb{P}_{\theta}\left(\exists
k\in[K],\theta^{\prime}\in\bar{\varTheta},~{}~{}\sum_{j=1}^{k-1}\|\mathbb{P}_{\theta^{\prime}}^{{\pi}^{j}}-\mathbb{P}_{\theta}^{{\pi}^{j}}\|_{\mathrm{TV}}^{2}\geq
2\log\left(K|\bar{\varTheta}|\right)+1+\ell(\theta,\mathcal{D}_{k})-\ell(\theta^{\prime},\mathcal{D}_{k})\right)$
(106)
$\displaystyle\leq\sum_{\theta^{\prime}\in\bar{\varTheta}}\mathbb{P}_{\theta}\left(\max_{k\in[K]}\sum_{j=1}^{k-1}\|\mathbb{P}_{\theta^{\prime}}^{{\pi}^{j}}-\mathbb{P}_{\theta}^{{\pi}^{j}}\|_{\mathrm{TV}}^{2}\geq
2\log\left(K|\bar{\varTheta}|\right)+1+\ell(\theta,\mathcal{D}_{k})-\ell(\theta^{\prime},\mathcal{D}_{k})\right)$
(107)
$\displaystyle\leq\sum_{\theta^{\prime}\in\bar{\varTheta}}\exp\left(-\log(K|\bar{\varTheta}|)\right)=\dfrac{1}{K}.$
(108)

The above holds for any $\theta\in\varTheta$. Therefore, we conclude that with
probability at least $1-\frac{1}{K}$,

$\displaystyle\max_{k\in[K]}\max_{\theta^{\prime}\in\bar{\varTheta}(\mathcal{D}_{k})}\sum_{j=1}^{k}\|\mathbb{P}_{\theta^{\prime}}^{{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{{\pi}^{j}}\|_{\mathrm{TV}}^{2}<3\log\left(K|\bar{\varTheta}|\right)+3.$
(109)

###  C.4 Proof of Theorem 1

Define $(OA)^{H}$-dimensional vectors $x_{k},w_{k}$ via

$\displaystyle x_{k}(\tau)$ $\displaystyle:=\tilde{\pi}^{k}(\tau)$ (110)
$\displaystyle w_{k}(\tau)$
$\displaystyle:=\frac{1}{2}|\mathbb{P}_{\check{\theta}^{k}}^{-}(\tau)-\mathbb{P}_{\theta^{*}}^{-}(\tau)|$
(111)

for each trajectory $\tau\in\mathscr{T}$, then (TR-MLE) can be written as
$\sum_{j=1}^{k}(w_{k}^{T}x_{j})^{2}$ and (TR-REG) can be written as
$\sum_{k=1}^{K}w_{k}^{T}x_{k}$. We have

$\displaystyle\|x_{k}\|_{2}$
$\displaystyle\leq\|x_{k}\|_{1}=\sum_{\tau\in\mathscr{T}}\tilde{\pi}^{k}(\tau)=O^{H}$
(112) $\displaystyle\|w_{k}\|_{2}$
$\displaystyle\leq\|w_{k}\|_{1}=\sum_{\tau\in\mathscr{T}}\frac{1}{2}|\mathbb{P}_{\check{\theta}^{k}}^{-}(\tau)-\mathbb{P}_{\theta^{*}}^{-}(\tau)|=A^{H}\sum_{\tau\in\mathscr{T}}\frac{1}{2}|\mathbb{P}_{\check{\theta}^{k}}^{\mathbf{unif}}(\tau)-\mathbb{P}_{\theta^{*}}^{\mathbf{unif}}(\tau)|\leq
A^{H}$ (113)

where $\mathbf{unif}$ represents the policy of picking a uniform random action
at all times.

Lemma 7, in particular, implies that $\sum_{j=1}^{k}(w_{k}^{T}x_{j})^{2}\leq
3\log(K|\bar{\varTheta}|)+3$ with probability at least $1-\frac{1}{K}$.

Applying Lemma 3 with $\lambda=1$, with probability $1-\frac{1}{K}$, we obtain

$\eqref{eq:REG}\leq\sqrt{(1+\beta)(OA)^{H}K\log\left[1+(OA)^{H}K\right]}$
(114)

where $\beta:=3\log(K|\bar{\varTheta}|)+3=\tilde{\mathcal{O}}(HS^{2}A+HSO)$.

Since TV distances are bounded by 1, we also have $\eqref{eq:REG}\leq K$ with
probability 1, hence

$\displaystyle\mathbb{E}[\eqref{eq:REG}]$
$\displaystyle\leq\sqrt{(1+\beta)(OA)^{H}K\log\left[1+(OA)^{H}K\right]}+1$
(115)

Finally, using Lemma 6, we conclude that

$\displaystyle\mathrm{BReg}(\phi^{\mathrm{PSRL}},K)$ $\displaystyle\leq
2H+H\mathbb{E}\left[\eqref{eq:REG}\right]$ (116) $\displaystyle\leq
2H+H\sqrt{(1+\beta)(OA)^{H}K\log\left[1+(OA)^{H}K\right]}+H$ (117)
$\displaystyle=\tilde{\mathcal{O}}\left(H\sqrt{H\beta(OA)^{H}K}\right)=\tilde{\mathcal{O}}\left(H^{2}\sqrt{(S^{2}A+SO)(OA)^{H}K}\right).$
(118)

###  C.5 Proof of Theorem 2

To obtain a bound polynomial in $H$, we will follow the indirect approach as
illustrated in Figure 1 and incorporate Assumption 1 along the way. The steps
here follow closely that of Liu et al. (2022). However, through the use of an
index change lemma with a tighter upper bound guarantee (our Proposition 3 in
Appendix A, compared to Proposition 22 by Liu et al. (2022)), we are able to
establish a regret bound for weakly $\alpha$-revealing POMDPs with improved
dependency on $H,S,$ and $A$.

Before we start the proof, we first establish a few quick results from
Assumption 1:

Quick Fact 3: $\alpha\leq\sqrt{S}$.

###### Proof.

We have
$\sigma_{\min}(\mathbb{Z}_{h}^{\theta})\leq\|\mathbb{Z}_{h}^{\theta}\|_{2}\leq\sqrt{S}\|\mathbb{Z}_{h}^{\theta}\|_{1}$.
Furthermore,
$\|\mathbb{Z}_{h}^{\theta}\|_{1}=\max_{s\in\mathscr{S}}\sum_{o\in\mathscr{O}}|\mathbb{Z}_{h}^{\theta}(o,s)|=1$.
∎

Quick Fact 4: Let $\mathbb{Z}_{h}^{\theta\dagger}$ be the Moore-Penrose
inverse of $\mathbb{Z}_{h}^{\theta}$. We have
$\|\mathbb{Z}_{h}^{\theta\dagger}\|_{1}\leq\dfrac{\sqrt{S}}{\alpha}$ for
$\theta\in\varTheta$.

###### Proof.

$\|\mathbb{Z}_{h}^{\theta\dagger}\|_{1}\leq\sqrt{S}\|\mathbb{Z}_{h}^{\theta\dagger}\|_{2}=\sqrt{S}\sigma_{\max}(\mathbb{Z}_{h}^{\theta\dagger})=\dfrac{\sqrt{S}}{\sigma_{\min}(\mathbb{Z}_{h}^{\theta})}\leq\dfrac{\sqrt{S}}{\alpha}$.
∎

Similarly to the proof of Theorem 1, in this proof, we attempt to bound (TR-
REG) with (TR-MLE). Note that while Assumption 1 is imposed on the set
$\varTheta$, both (TR-REG) and (TR-MLE) involve some
$\bar{\theta}\in\bar{\varTheta}$. The fact that $\bar{\varTheta}$ is not a
subset of $\varTheta$ prevents us from applying Assumption 1. Therefore, we
need the following step. Recall that we have assumed that the quantization map
$\iota$ is surjective. Let $\hat{\theta}^{k}\in\varTheta$ be such that
$\check{\theta}^{k}=\iota(\hat{\theta}^{k})$, then we have
$\|\mathbb{P}_{\check{\theta}^{k}}^{\pi}-\mathbb{P}_{\hat{\theta}^{k}}^{\pi}\|_{\mathrm{TV}}\leq
2H\epsilon=\frac{1}{K}$. Therefore, we have

$\displaystyle\sum_{j=1}^{k}\|\mathbb{P}_{\hat{\theta}^{k}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}^{2}$
$\displaystyle\leq\sum_{j=1}^{k}\left(\|\mathbb{P}_{\check{\theta}^{k}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}+\dfrac{1}{K}\right)^{2}=\sum_{j=1}^{k}\left(\|\mathbb{P}_{\check{\theta}^{k}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}^{2}+\dfrac{2}{K}\|\mathbb{P}_{\check{\theta}^{k}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}+\dfrac{1}{K^{2}}\right)$
(119)
$\displaystyle\leq\left(\sum_{j=1}^{k}\|\mathbb{P}_{\check{\theta}^{k}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}^{2}\right)+k\left(\dfrac{2}{K}+\dfrac{1}{K^{2}}\right)\leq\eqref{eq:MLE}+2+\dfrac{1}{K}$
(120)

and

$\displaystyle\eqref{eq:REG}\leq\sum_{j=1}^{K}\left(\|\mathbb{P}_{\hat{\theta}^{j}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}+\dfrac{1}{K}\right)\leq\left(\sum_{j=1}^{K}\|\mathbb{P}_{\hat{\theta}^{j}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}\right)+1.$
(121)

Therefore, our task for this proof is to use

$\displaystyle\sum_{j=1}^{k}\|\mathbb{P}_{\hat{\theta}^{k}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}^{2}$
(TR-MLE-II)

to bound

$\displaystyle\sum_{j=1}^{K}\|\mathbb{P}_{\hat{\theta}^{j}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}.$
(TR-REG-II)

#### Step 1: Bound (TR-REG-II) with Projected Distances of Observable
Operators.

Recall that the probability of a trajectory of a POMDP can be written with
matrix multiplications. Recall that
$\mathbb{T}_{h,a}\in\mathbb{R}^{\mathscr{S}\times\mathscr{S}}$ is the
probability transition matrix (where the rows represent the next state) under
action $a\in\mathscr{A}$ at time $h\in[H-1]$. Recall that
$\mathbb{Z}_{h}\in\mathbb{R}^{\mathscr{O}\times\mathscr{S}}$ is the
observation probability matrix. For each
$h\in[H-1],a\in\mathscr{A},o\in\mathscr{O}$, define the _observable operator_
matrix (Jin et al., 2020)

$\mathbf{B}_{h}^{\theta}(a,o):=\mathbb{Z}_{h+1}^{\theta}\mathbb{T}_{h,a}^{\theta}\mathrm{diag}(\mathbb{Z}_{h}^{\theta}(o,\cdot))\mathbb{Z}_{h}^{\theta\dagger}$
(122)

where $\mathbb{Z}_{h}^{\theta\dagger}$ is the Moore-Penrose inverse of
$\mathbb{Z}_{h}^{\theta}$. Note that due to Assumption 1,
$\mathbb{Z}_{h}^{\theta}$ has full column rank, hence
$\mathbb{Z}_{h}^{\theta\dagger}\mathbb{Z}_{h}^{\theta}=\mathbf{I}$. We can
rewrite the environment part of the probability of a trajectory as

$\mathbb{P}_{\theta}^{-}(o_{1:H},a_{1:H})=\mathbf{e}_{o_{H}}^{T}\mathbf{B}_{H-1}^{\theta}(a_{H-1},o_{H-1})\cdots\mathbf{B}_{1}^{\theta}(a_{1},o_{1})\mathbb{Z}_{1}^{\theta}b_{1}^{\theta}$
(123)

For a full trajectory $\tau=(o_{1:H},a_{1:H})\in\mathscr{T}$, let
$\tau_{h}=(o_{1:h},a_{1:h})$ denote its corresponding partial trajectory up to
time $h$ and $\tau_{-h}=(o_{h+1:H},a_{h+1:H})$ denote its corresponding
partial trajectory from time $h+1$ to $H$. Define
$\mathbf{v}_{0}^{\theta}=\mathbb{Z}_{1}^{\theta}b_{1}^{\theta}$ and
$\mathbf{v}_{h}^{\theta}(\tau_{h}):=\mathbf{B}_{h}^{\theta}(a_{h},o_{h})\cdots\mathbf{B}_{1}^{\theta}(a_{1},o_{1})\mathbf{v}_{0}^{\theta}$.
With some abuse of notation, define

$\mathbf{B}_{H:h}^{\theta}(\tau_{-(h-1)}):=\begin{cases}\mathbf{e}_{o_{H}}^{T}&h=H\\\
\mathbf{e}_{o_{H}}^{T}\mathbf{B}_{H-1}^{\theta}(a_{H-1},o_{H-1})\cdots\mathbf{B}_{h}^{\theta}(a_{h},o_{h})&h<H\end{cases}$
(124)

In the rest of the step, we will prove the following claim.

Claim: With probability 1, we have
$\eqref{eq:REG2}\leq\dfrac{\sqrt{S}}{\alpha}\sum_{h=0}^{H-1}(\text{OP-
REG-}h)$, where

$\displaystyle(\text{OP-REG-}0):=$
$\displaystyle\dfrac{1}{2}\sum_{j=1}^{K}\|\mathbf{v}_{0}^{\theta^{*}}-\mathbf{v}_{0}^{\hat{\theta}^{j}}\|_{1}$
(125) $\displaystyle(\text{OP-REG-}h):=$
$\displaystyle\dfrac{1}{2}\sum_{j=1}^{K}\sum_{\tau_{h}\in(\mathscr{O}\times\mathscr{A})^{h}}\tilde{\pi}^{j}(\tau_{h})\|[\mathbf{B}_{h}^{\theta^{*}}(a_{h},o_{h})-\mathbf{B}_{h}^{\hat{\theta}^{j}}(a_{h},o_{h})]\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})\|_{1}\qquad\forall
h\in[H-1]$ (126)

are the _projected operator distances_.

From (123), using telescoping sums, for any $\pi\in\varPi$ and parameters
$\theta,\theta^{\prime}$ we have

$\displaystyle\quad~{}\|\mathbb{P}_{\theta}^{\pi}-\mathbb{P}_{\theta^{\prime}}^{\pi}\|_{\mathrm{TV}}=\dfrac{1}{2}\sum_{\tau\in\mathscr{T}}\pi(\tau)|\mathbb{P}_{\theta}^{-}(\tau)-\mathbb{P}_{\theta^{\prime}}^{-}(\tau)|$
(127)
$\displaystyle\leq\dfrac{1}{2}\sum_{\tau\in\mathscr{T}}\pi(\tau)|\mathbf{B}_{H:1}^{\theta^{\prime}}(\tau)[\mathbf{v}_{0}^{\theta}-\mathbf{v}_{0}^{\theta^{\prime}}]|+$
(128)
$\displaystyle+\dfrac{1}{2}\sum_{\tau\in\mathscr{T}}\pi(\tau)\sum_{h=1}^{H-1}|\mathbf{B}_{H:h+1}^{\theta^{\prime}}(\tau_{-h})[\mathbf{B}_{h}^{\theta}(a_{h},o_{h})-\mathbf{B}_{h}^{\theta^{\prime}}(a_{h},o_{h})]\mathbf{v}_{h-1}^{\theta}(\tau_{h-1})|$
(129)

Using Lemma 12, we have

$\displaystyle\sum_{\tau\in\mathscr{T}}\pi(\tau)|\mathbf{B}_{H:1}^{\theta^{\prime}}(\tau)[\mathbf{v}_{0}^{\theta}-\mathbf{v}_{0}^{\theta^{\prime}}]|\leq\dfrac{\sqrt{S}}{\alpha}\|\mathbf{v}_{0}^{\theta}-\mathbf{v}_{0}^{\theta^{\prime}}\|_{1}$
(130)

Also through Lemma 12, for each $h\in[H-1]$ we have

$\displaystyle\quad~{}\sum_{\tau\in\mathscr{T}}\pi(\tau)|\mathbf{B}_{H:h+1}^{\theta^{\prime}}(\tau_{-h})[\mathbf{B}_{h}^{\theta}(a_{h},o_{h})-\mathbf{B}_{h}^{\theta^{\prime}}(a_{h},o_{h})]\mathbf{v}_{h-1}^{\theta}(\tau_{h-1})|$
(131)
$\displaystyle=\sum_{\tau_{h}\in(\mathscr{O}\times\mathscr{A})^{h}:\pi(\tau_{h})>0}\pi(\tau_{h})\sum_{\tau_{-h}\in(\mathscr{O}\times\mathscr{A})^{H-h}}\pi(\tau_{-h}|\tau_{h})|\mathbf{B}_{H:h+1}^{\theta^{\prime}}(\tau_{-h})[\mathbf{B}_{h}^{\theta}(a_{h},o_{h})-\mathbf{B}_{h}^{\theta^{\prime}}(a_{h},o_{h})]\mathbf{v}_{h-1}^{\theta}(\tau_{h-1})|$
(132)
$\displaystyle\leq\sum_{\tau_{h}\in(\mathscr{O}\times\mathscr{A})^{h}:\pi(\tau_{h})>0}\pi(\tau_{h})\cdot\dfrac{\sqrt{S}}{\alpha}\|[\mathbf{B}_{h}^{\theta}(a_{h},o_{h})-\mathbf{B}_{h}^{\theta^{\prime}}(a_{h},o_{h})]\mathbf{v}_{h-1}^{\theta}(\tau_{h-1})\|_{1}$
(133)

where for each $\pi\in\varPi$ and
$\tau_{h}\in(\mathscr{O}\times\mathscr{A})^{h}$, $\pi(\tau_{h})$ is defined in
a similar way as $\pi(\tau)$ except that $\tau_{h}$ is a partial trajectory.
For $\pi,\tau_{h}$ such that $\pi(\tau_{h})>0$, $\pi(\tau_{-h}|\tau_{h})$ is
defined as $\pi(\tau_{h},\tau_{-h})/\pi(\tau_{h})$.

We conclude that (TR-REG-II) can be bounded by

$\displaystyle\quad~{}\sum_{j=1}^{K}\|\mathbb{P}_{\hat{\theta}^{j}}^{\tilde{\pi}^{j}}-\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{j}}\|_{\mathrm{TV}}$
(134)
$\displaystyle\leq\frac{\sqrt{S}}{2\alpha}\sum_{j=1}^{K}\left(\|\mathbf{v}_{0}^{\theta^{*}}-\mathbf{v}_{0}^{\hat{\theta}^{j}}\|_{1}+\sum_{h=1}^{H-1}\sum_{\tau_{h}\in(\mathscr{O}\times\mathscr{A})^{h}}\tilde{\pi}^{j}(\tau_{h})\left\|[\mathbf{B}_{h}^{\theta^{*}}(a_{h},o_{h})-\mathbf{B}_{h}^{\hat{\theta}^{j}}(a_{h},o_{h})]\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})\right\|_{1}\right)$
(135)

proving the claim.

#### Step 2: Bound Projected Distances of Observable Operators with (TR-MLE-
II).

In this step we prove the following claim

Claim: With probability at least $1-\frac{1}{K}$,

$\displaystyle(\text{OP-MLE-}0):=$
$\displaystyle\dfrac{1}{2}\|\mathbf{v}_{0}^{\hat{\theta}^{k}}-\mathbf{v}_{0}^{\theta^{*}}\|_{1}\leq\sqrt{\frac{\beta}{k}}$
(136) $\displaystyle(\text{OP-MLE-}h):=$
$\displaystyle\sum_{j=1}^{k}\left(\dfrac{1}{2}\sum_{\tau_{h}}\tilde{\pi}^{j}(\tau_{h})\|[\mathbf{B}_{h}^{\theta^{*}}(a_{h},o_{h})-\mathbf{B}_{h}^{\hat{\theta}^{k}}(a_{h},o_{h})]\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})\|_{1}\right)^{2}\leq\dfrac{4S}{\alpha^{2}}\beta$
(137)

for all $k\in[K]$, where $\beta:=3\log(K|\bar{\varTheta}|)+5+\dfrac{1}{K}$.

Observe that the vectors $\mathbf{v}_{0}^{\theta}\in\mathbb{R}^{\mathscr{O}}$
and $\mathbf{v}_{h}^{\theta}(\tau_{h})\in\mathbb{R}^{\mathscr{O}}$ defined in
Step 1 have the following probabilistic interpretation

$\displaystyle\mathbf{v}_{0}^{\theta}(o_{1})$
$\displaystyle=\mathbb{P}_{\theta}(o_{1})\qquad\forall o_{1}\in\mathscr{O}$
(138)
$\displaystyle\pi(\tau_{h})\cdot[\mathbf{v}_{h}^{\theta}(\tau_{h})](o_{h+1})$
$\displaystyle=\mathbb{P}_{\theta}^{\pi}(\tau_{h},o_{h+1})\qquad\forall\tau_{h}\in(\mathscr{O}\times\mathscr{A})^{h},o_{h+1}\in\mathscr{O}$
(139)

Therefore, for all $\theta,\theta^{\prime}\in\varTheta,\pi\in\varPi$, we have

$\displaystyle\frac{1}{2}\|\mathbf{v}_{0}^{\theta}-\mathbf{v}_{0}^{\theta^{\prime}}\|_{1}$
$\displaystyle=\frac{1}{2}\sum_{o_{1}}|\mathbb{P}_{\theta}(o_{1})-\mathbb{P}_{\theta^{\prime}}(o_{1})|\leq\|\mathbb{P}_{\theta}^{\pi}-\mathbb{P}_{\theta^{\prime}}^{\pi}\|_{\mathrm{TV}}$
(140)
$\displaystyle\frac{1}{2}\sum_{\tau_{h}}\pi(\tau_{h})\|\mathbf{v}_{h}^{\theta}(\tau_{h})-\mathbf{v}_{h}^{\theta^{\prime}}(\tau_{h})\|_{1}$
$\displaystyle=\frac{1}{2}\sum_{\tau_{h}}\sum_{o_{h+1}}|\mathbb{P}_{\theta}^{\pi}(\tau_{h},o_{h+1})-\mathbb{P}_{\theta^{\prime}}^{\pi}(\tau_{h},o_{h+1})|\leq\|\mathbb{P}_{\theta}^{\pi}-\mathbb{P}_{\theta^{\prime}}^{\pi}\|_{\mathrm{TV}}$
(141)

where we have used the fact that the total variation distance between two
marginal distributions is no more than that between the original
distributions. Therefore, we have

$\displaystyle\quad~{}k\left(\frac{1}{2}\|\mathbf{v}_{0}^{\hat{\theta}^{k}}-\mathbf{v}_{0}^{\theta^{*}}\|_{1}\right)^{2}=\sum_{j=1}^{k}\left(\frac{1}{2}\|\mathbf{v}_{0}^{\hat{\theta}^{k}}-\mathbf{v}_{0}^{\theta^{*}}\|_{1}\right)^{2}\leq\eqref{eq:MLE2}$
(142)
$\displaystyle\quad~{}\sum_{j=1}^{k}\left(\frac{1}{2}\sum_{\tau_{h}}\tilde{\pi}^{j}(\tau_{h})\|\mathbf{v}_{h}^{\hat{\theta}^{k}}(\tau_{h})-\mathbf{v}_{h}^{\theta^{*}}(\tau_{h})\|_{1}\right)^{2}\leq\eqref{eq:MLE2}$
(143)

We proceed to bound the projected operator distance. First, for any
$\tau_{h}\in(\mathscr{O}\times\mathscr{A})^{h}$ we have

$\displaystyle\quad~{}\|[\mathbf{B}_{h}^{\theta^{*}}(a_{h},o_{h})-\mathbf{B}_{h}^{\hat{\theta}^{k}}(a_{h},o_{h})]\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})\|_{1}$
(144)
$\displaystyle\leq\|\mathbf{B}_{h}^{\theta^{*}}(a_{h},o_{h})\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})-\mathbf{B}_{h}^{\hat{\theta}^{k}}(a_{h},o_{h})\mathbf{v}_{h-1}^{\hat{\theta}^{k}}(\tau_{h-1})\|_{1}+\|\mathbf{B}_{h}^{\hat{\theta}^{k}}(a_{h},o_{h})[\mathbf{v}_{h-1}^{\hat{\theta}^{k}}(\tau_{h-1})-\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})]\|_{1}$
(145)
$\displaystyle=\|\mathbf{v}_{h}^{\theta^{*}}(\tau_{h})-\mathbf{v}_{h}^{\hat{\theta}^{k}}(\tau_{h})\|_{1}+\|\mathbf{B}_{h}^{\hat{\theta}^{k}}(a_{h},o_{h})[\mathbf{v}_{h-1}^{\hat{\theta}^{k}}(\tau_{h-1})-\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})]\|_{1}$
(146)

where $\tau_{h-1}\in(\mathscr{O}\times\mathscr{A})^{h-1}$ is the partial
trajectory made of the first $h-1$ observations and actions in $\tau_{h}$.

Therefore, using the inequality $(x_{1}+x_{2})^{2}\leq 2x_{1}^{2}+2x_{2}^{2}$,
we have

$\displaystyle\quad~{}\sum_{j=1}^{k}\left(\frac{1}{2}\sum_{\tau_{h}}\tilde{\pi}^{j}(\tau_{h})\|[\mathbf{B}_{h}^{\theta^{*}}(a_{h},o_{h})-\mathbf{B}_{h}^{\hat{\theta}^{k}}(a_{h},o_{h})]\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})\|_{1}\right)^{2}$
(147) $\displaystyle\leq
2\underbrace{\sum_{j=1}^{k}\left(\frac{1}{2}\sum_{\tau_{h}}\tilde{\pi}^{j}(\tau_{h})\|\mathbf{v}_{h}^{\theta^{*}}(\tau_{h})-\mathbf{v}_{h}^{\hat{\theta}^{k}}(\tau_{h})\|_{1}\right)^{2}}_{=:\xi_{1}}$
(148)
$\displaystyle+2\underbrace{\sum_{j=1}^{k}\left(\frac{1}{2}\sum_{\tau_{h}}\tilde{\pi}^{j}(\tau_{h})\|\mathbf{B}_{h}^{\hat{\theta}^{k}}(a_{h},o_{h})[\mathbf{v}_{h-1}^{\hat{\theta}^{k}}(\tau_{h-1})-\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})]\|_{1}\right)^{2}}_{\xi_{2}}$
(149)

From (143) we know that $\xi_{1}\leq\eqref{eq:MLE2}$. It remains to bound
$\xi_{2}$. We have

$\displaystyle\quad~{}\frac{1}{2}\sum_{\tau_{h}}\tilde{\pi}^{j}(\tau_{h})\|\mathbf{B}_{h}^{\hat{\theta}^{k}}(a_{h},o_{h})[\mathbf{v}_{h-1}^{\hat{\theta}^{k}}(\tau_{h-1})-\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})]\|_{1}$
(150)
$\displaystyle=\frac{1}{2}\sum_{\tau_{h-1}}\tilde{\pi}^{j}(\tau_{h-1})\sum_{a_{h},o_{h}}\tilde{\pi}_{h}^{j}(a_{h}|\tau_{h-1},o_{h})\|\mathbf{B}_{h}^{\hat{\theta}^{k}}(a_{h},o_{h})[\mathbf{v}_{h-1}^{\hat{\theta}^{k}}(\tau_{h-1})-\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})]\|_{1}$
(151)
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\leq}}\dfrac{\sqrt{S}}{2\alpha}\sum_{\tau_{h-1}}\tilde{\pi}^{j}(\tau_{h-1})\|\mathbf{v}_{h-1}^{\hat{\theta}^{k}}(\tau_{h-1})-\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})\|_{1}$
(152)

where in (*) we have used Lemma 11.

Therefore, using (143), we have

$\displaystyle\xi_{2}\leq\sum_{j=1}^{k}\left(\frac{\sqrt{S}}{2\alpha}\sum_{\tau_{h-1}}\tilde{\pi}^{j}(\tau_{h-1})\|\mathbf{v}_{h-1}^{\hat{\theta}^{k}}(\tau_{h-1})-\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})\|_{1}\right)^{2}\leq\dfrac{S}{\alpha^{2}}\eqref{eq:MLE2}$
(153)

and consequently

$\displaystyle\quad~{}\sum_{j=1}^{k}\left(\frac{1}{2}\sum_{\tau_{h}}\tilde{\pi}^{j}(\tau_{h})\|[\mathbf{B}_{h}^{\theta^{*}}(a_{h},o_{h})-\mathbf{B}_{h}^{\hat{\theta}^{k}}(a_{h},o_{h})]\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})\|_{1}\right)^{2}$
(154) $\displaystyle\leq 2(\xi_{1}+\xi_{2})\leq
2\left(1+\dfrac{S}{\alpha^{2}}\right)\eqref{eq:MLE2}\leq\dfrac{4S}{\alpha^{2}}\eqref{eq:MLE2}.$
(155)

From Lemma 7 and (120), we know that with probability at least
$1-\frac{1}{K}$, we have $\eqref{eq:MLE2}\leq
3\log(K|\bar{\varTheta}|)+5+\dfrac{1}{K}=\beta$. The claim then follows from
(142) and (155).

#### Step 3: Bound (OP-REG) with Results on (OP-MLE) via Index Change Lemma.

In the final step, for each $h=0,1,\cdots,H-1$, we utilize Proposition 3 to
provide an upper bound of each (OP-REG-$h$) via the high-probability bound on
(OP-MLE-$h$).

Suppose that both (136) and (137) are true. First, we have

$\displaystyle(\text{OP-REG-}0)$
$\displaystyle=\sum_{k=1}^{K}\dfrac{1}{2}\|\mathbf{v}_{0}^{\hat{\theta}^{k}}-\mathbf{v}_{0}^{\theta^{*}}\|_{1}\leq\sum_{k=1}^{K}\sqrt{\dfrac{\beta}{k}}\leq
2\sqrt{\beta K}.$ (156)

Now, fix $h\in[H-1]$, we will use (OP-MLE-$h$) to bound (OP-REG-$h$).

Define the following quantities: For
$k\in[K],a\in\mathscr{A},o,\tilde{o}\in\mathscr{O},\tau_{h-1}\in(\mathscr{O}\times\mathscr{A})^{h-1}$,
define $w_{k,a,o,\tilde{o}},x_{k,a,o,\tau_{h-1}}\in\mathbb{R}^{\mathscr{S}}$
by

$\displaystyle w_{k,a,o,\tilde{o}}^{T}$
$\displaystyle:=\frac{1}{2}\mathbf{e}_{\tilde{o}}^{T}[\mathbf{B}_{h}^{\theta^{*}}(a,o)-\mathbf{B}_{h}^{\hat{\theta}^{k}}(a,o)]\mathbb{Z}_{h}^{\theta^{*}}$
(157) $\displaystyle x_{k,a,o,\tau_{h-1}}$
$\displaystyle:=\tilde{\pi}^{k}(\tau_{h})\mathbb{Z}_{h}^{\theta^{*}\dagger}\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})$
(158)

where $\tau_{h}\in(\mathscr{O}\times\mathscr{A})^{h}$ is a trajectory such
that $a_{h}=a,o_{h}=o$, and the first $h-1$ steps are made of $\tau_{h-1}$.
Then, (OP-MLE-$h$) can be written as

$\sum_{j=1}^{k}\left(\sum_{(a,o)\in\mathscr{A}\times\mathscr{O}}\sum_{\tilde{o}\in\mathscr{O}}\sum_{\tau_{h-1}\in(\mathscr{O}\times\mathscr{A})^{h-1}}|w_{k,a,o,\tilde{o}}^{T}x_{j,a,o,\tau_{h-1}}|\right)^{2}.$

Note that we have used the fact that
$\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})$ is in the (column) span of
$\mathbb{Z}_{h}^{\theta^{*}}$ (and hence
$\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})=\mathbb{Z}_{h}^{\theta^{*}}\mathbb{Z}_{h}^{\theta^{*}\dagger}\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})$).

Furthermore, for each $k\in[K]$, we have

$\displaystyle\quad~{}\sum_{(a,o)\in\mathscr{A}\times\mathscr{O}}\sum_{\tau_{h-1}\in(\mathscr{O}\times\mathscr{A})^{h-1}}\|x_{k,a,o,\tau_{h-1}}\|_{1}$
(159)
$\displaystyle=\sum_{(a,o)\in\mathscr{A}\times\mathscr{O}}\sum_{\tau_{h-1}\in(\mathscr{O}\times\mathscr{A})^{h-1}}\|\tilde{\pi}^{k}(\tau_{h})\mathbb{Z}_{h}^{\theta^{*}\dagger}\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})\|_{1}$
(160)
$\displaystyle=\sum_{(a,o)\in\mathscr{A}\times\mathscr{O}}\sum_{\tau_{h-1}\in(\mathscr{O}\times\mathscr{A})^{h-1}}\tilde{\pi}^{k}_{h}(a|\tau_{h-1},o)\|\tilde{\pi}^{k}(\tau_{h-1})\mathbb{Z}_{h}^{\theta^{*}\dagger}\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})\|_{1}$
(161)
$\displaystyle=\sum_{(a,o)\in\mathscr{A}\times\mathscr{O}}\sum_{\tau_{h-1}\in(\mathscr{O}\times\mathscr{A})^{h-1}}\tilde{\pi}^{k}_{h}(a|\tau_{h-1},o)\sum_{s_{h}\in\mathscr{S}}\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}(\tau_{h-1},s_{h})$
(162)
$\displaystyle=\sum_{o\in\mathscr{O}}\sum_{\tau_{h-1}\in(\mathscr{O}\times\mathscr{A})^{h-1}}\sum_{s_{h}\in\mathscr{S}}\mathbb{P}_{\theta^{*}}^{\tilde{\pi}^{k}}(\tau_{h-1},s_{h})=O.$
(163)

We also have

$\displaystyle\quad~{}\sum_{(a,o)\in\mathscr{A}\times\mathscr{O}}\sum_{\tilde{o}\in\mathscr{O}}\|w_{k,a,o,\tilde{o}}\|_{1}$
(164)
$\displaystyle=\sum_{s\in\mathscr{S}}\sum_{(a,o)\in\mathscr{A}\times\mathscr{O}}\left\|\frac{1}{2}[\mathbf{B}_{h}^{\theta^{*}}(a,o)-\mathbf{B}_{h}^{\hat{\theta}^{k}}(a,o)]\mathbb{Z}_{h}^{\theta^{*}}\mathbf{e}_{s}\right\|_{1}$
(165)
$\displaystyle\leq\sum_{s\in\mathscr{S}}\dfrac{1}{2}\left(\sum_{(a,o)\in\mathscr{A}\times\mathscr{O}}\left\|\mathbf{B}_{h}^{\theta^{*}}(a,o)\mathbb{Z}_{h}^{\theta^{*}}\mathbf{e}_{s}\right\|_{1}+\sum_{(a,o)\in\mathscr{A}\times\mathscr{O}}\left\|\mathbf{B}_{h}^{\hat{\theta}^{k}}(a,o)\mathbb{Z}_{h}^{\theta^{*}}\mathbf{e}_{s}\right\|_{1}\right)$
(166)
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\leq}}\sum_{s\in\mathscr{S}}A\dfrac{\sqrt{S}}{\alpha}\|\mathbb{Z}_{h}^{\theta^{*}}\mathbf{e}_{s}\|_{1}=\dfrac{S^{1.5}A}{\alpha}$
(167)

where in (*) we have used Lemma 11.

Applying Proposition 3 with $\lambda=\frac{S}{\alpha^{2}}$, we have

$\displaystyle(\text{OP-REG-}h)$
$\displaystyle=\dfrac{1}{2}\sum_{k=1}^{K}\sum_{\tau_{h}}\tilde{\pi}^{k}(\tau_{h})\|[\mathbf{B}_{h}^{\theta^{*}}(a_{h},o_{h})-\mathbf{B}_{h}^{\hat{\theta}^{k}}(a,o)]\mathbf{v}_{h-1}^{\theta^{*}}(\tau_{h-1})\|_{1}$
(168)
$\displaystyle=\sum_{k=1}^{K}\sum_{(a,o)\in\mathscr{A}\times\mathscr{O}}\sum_{\tilde{o}\in\mathscr{O}}\sum_{\tau_{h-1}\in(\mathscr{O}\times\mathscr{A})^{h-1}}|w_{k,a,o,\tilde{o}}^{T}x_{k,a,o,\tau_{h-1}}|$
(169)
$\displaystyle\leq\sqrt{\left(\dfrac{S}{\alpha^{2}}+\dfrac{4S}{\alpha^{2}}\beta\right)SAO^{2}K\log\left(1+SAO^{2}K\right)}$
(170) $\displaystyle\leq 3\alpha^{-1}SO\sqrt{A\beta
K\log\left(1+SAO^{2}K\right)}.$ (171)

Using Step 1, we conclude that with probability at least $1-\frac{1}{K}$,

$\displaystyle\eqref{eq:REG2}$
$\displaystyle\leq\dfrac{\sqrt{S}}{\alpha}\left((\text{OP-
REG-0})+\sum_{h=1}^{H-1}(\text{OP-REG-}h)\right)$ (172)
$\displaystyle\leq\dfrac{\sqrt{S}}{\alpha}\left(2\sqrt{\beta K}+(H-1)\cdot
3\alpha^{-1}SO\sqrt{A\beta K\log\left(1+SAO^{2}K\right)}\right)$ (173)
$\displaystyle\leq 3\alpha^{-2}HSO\sqrt{SA\beta K\log(1+SAO^{2}K)}.$ (174)

Since TV distances are bounded by $1$, we also have $\eqref{eq:REG2}\leq K$
with probability 1. Therefore, we have

$\mathbb{E}\left[\eqref{eq:REG2}\right]\leq 3\alpha^{-2}HSO\sqrt{SA\beta
K\log(1+SAO^{2}K)}+1.$ (175)

Finally, using Lemma 6 and (121) we have

$\displaystyle\mathrm{BReg}(\phi^{\mathrm{PSRL}},K)$ $\displaystyle\leq
2H+H\mathbb{E}\left[\eqref{eq:REG}\right]$ (176) $\displaystyle\leq
3H+H\mathbb{E}\left[\eqref{eq:REG2}\right]$ (177)
$\displaystyle=\mathcal{O}\left(\alpha^{-2}H^{2}SO\sqrt{SA\beta
K\log(1+SAO^{2}K)}\right)$ (178)
$\displaystyle=\tilde{\mathcal{O}}\left(\alpha^{-2}H^{2}S^{2}O\sqrt{HA(SA+O)K}\right)$
(179)

where in the last line we used the fact that
$\beta=\tilde{\mathcal{O}}(\log(|\bar{\varTheta}|))=\tilde{\mathcal{O}}(HS^{2}A+HSO)$.

##  Appendix D Miscellaneous Auxiliary Results

######  Lemma 8.

Let $\\{Z_{k}\\}_{k=1}^{K}$ be a real-valued random process adapted to the
filtration $\\{\mathcal{F}_{k}\\}_{k=0}^{K}$. Suppose that
$\psi_{k}(\lambda)=\log\mathbb{E}[\exp(\lambda Z_{k})|\mathcal{F}_{k-1}]$ is
well-defined for some $\lambda\in\mathbb{R}$. Then, for any $x>0$,

$\mathbb{P}\left(\max_{k\in[K]}\sum_{j=1}^{k}[\lambda
Z_{j}-\psi_{j}(\lambda)]<x\right)\geq 1-e^{-x}$ (180)

###### Proof.

Define $M_{0}=1$ and $M_{k}=\exp\left(\sum_{j=1}^{k}[\lambda
Z_{j}-\psi_{j}(\lambda)]\right)$, then

$\displaystyle\mathbb{E}[M_{k}|\mathcal{F}_{k-1}]$
$\displaystyle=\exp\left(\sum_{j=1}^{k-1}[\lambda
Z_{j}-\psi_{j}(\lambda)]\right)\cdot\mathbb{E}\left[\exp(\lambda
Z_{k}-\psi_{k}(\lambda))|\mathcal{F}_{k-1}\right]$ (181)
$\displaystyle=M_{k-1}\dfrac{\mathbb{E}[\exp(\lambda
Z_{k})|\mathcal{F}_{k-1}]}{\exp(\psi_{k}(\lambda))}=M_{k-1}.$ (182)

Therefore, $M_{k}$ is a martingale with mean
$\mathbb{E}[M_{k}]=\mathbb{E}[M_{0}]=1$. By Doob’s Martingale Inequality, we
have

$\mathbb{P}\left(\max_{k\in[K]}M_{k}\geq
e^{x}\right)\leq\mathbb{E}[M_{K}]e^{-x}=e^{-x}\qquad\forall x>0$ (183)

The lemma is then established by taking the logarithm of both sides of the
inequality in the condition. ∎

######  Lemma 9.

Let $p,q\in\Delta_{d}$ be two probability distributions on the finite set
$[d]$, then
$\sum_{i=1}^{d}(\sqrt{p_{i}}-\sqrt{q}_{i})^{2}\geq\|p-q\|_{\mathrm{TV}}^{2}$.

###### Proof.

We have

$\displaystyle\|p-q\|_{\mathrm{TV}}^{2}$
$\displaystyle=\frac{1}{4}\left(\sum_{i=1}^{d}|p_{i}-q_{i}|\right)^{2}=\frac{1}{4}\left(\sum_{i=1}^{d}|(\sqrt{p_{i}}+\sqrt{q_{i}})(\sqrt{p_{i}}-\sqrt{q_{i}})|\right)^{2}$
(184)
$\displaystyle\leq\dfrac{1}{4}\left(\sum_{i=1}^{d}(\sqrt{p_{i}}+\sqrt{q_{i}})^{2}\right)\left(\sum_{i=1}^{d}(\sqrt{p_{i}}-\sqrt{q_{i}})^{2}\right)$
(185)
$\displaystyle\leq\dfrac{1}{4}\left(\sum_{i=1}^{d}(2p_{i}+2q_{i})\right)\left(\sum_{i=1}^{d}(\sqrt{p_{i}}-\sqrt{q_{i}})^{2}\right)=\sum_{i=1}^{d}(\sqrt{p_{i}}-\sqrt{q_{i}})^{2}$
(186)

∎

######  Lemma 10.

Let $\bar{\varTheta}$ be as specified in Proposition 4 and
$\ell,\bar{\ell}^{*}$ be as defined in (72) and (73). For each $k\in[K]$, with
probability at least $1-\delta$, we have
$\ell(\theta^{*},\mathcal{D}_{k})\geq\bar{\ell}^{*}(\mathcal{D}_{k})-\log(|\bar{\varTheta}|/\delta)$.

###### Proof.

For any $\bar{\theta}\in\bar{\varTheta}$ and any $j\in[K]$, we have

$\displaystyle\mathbb{E}\left[\dfrac{\mathbb{P}_{\bar{\theta}}^{\pi^{j}}(\tau^{j})}{\mathbb{P}_{\theta^{*}}^{\pi^{j}}(\tau^{j})}~{}\Big{|}~{}\mathcal{D}_{j},\theta^{*},\pi^{j}\right]=\sum_{\tilde{\tau}\in\mathscr{T}:\mathbb{P}_{\theta^{*}}^{\pi^{j}}(\tilde{\tau})>0}\mathbb{P}_{\theta^{*}}^{\pi^{j}}(\tilde{\tau})\dfrac{\mathbb{P}_{\bar{\theta}}^{\pi^{j}}(\tilde{\tau})}{\mathbb{P}_{\theta^{*}}^{\pi^{j}}(\tilde{\tau})}\leq
1$ (187)

Therefore,

$\displaystyle\quad~{}\mathbb{E}\left[\exp\left(\ell(\bar{\theta},\mathcal{D}_{k})-\ell(\theta^{*},\mathcal{D}_{k})\right)\right]$
(188)
$\displaystyle=\mathbb{E}\left[\prod_{j=1}^{k-1}\dfrac{\mathbb{P}_{\bar{\theta}}^{\pi^{j}}(\tau^{j})}{\mathbb{P}_{\theta^{*}}^{\pi^{j}}(\tau^{j})}~{}\Big{|}~{}\theta^{*}\right]=\mathbb{E}\left[\mathbb{E}\left[\prod_{j=1}^{k-1}\dfrac{\mathbb{P}_{\bar{\theta}}^{\pi^{j}}(\tau^{j})}{\mathbb{P}_{\theta^{*}}^{\pi^{j}}(\tau^{j})}~{}\Big{|}~{}\mathcal{D}_{k-1},\theta^{*}\right]\right]$
(189)
$\displaystyle=\mathbb{E}\left[\prod_{j=1}^{k-2}\dfrac{\mathbb{P}_{\bar{\theta}}^{\pi^{j}}(\tau^{j})}{\mathbb{P}_{\theta^{*}}^{\pi^{j}}(\tau^{j})}\mathbb{E}\left[\dfrac{\mathbb{P}_{\bar{\theta}}^{\pi^{k-1}}(\tau^{k-1})}{\mathbb{P}_{\theta^{*}}^{\pi^{k-1}}(\tau^{k-1})}~{}\Big{|}~{}\mathcal{D}_{k-1},\theta^{*}\right]\right]\leq\mathbb{E}\left[\prod_{j=1}^{k-2}\dfrac{\mathbb{P}_{\bar{\theta}^{\prime}}^{\pi^{j}}(\tau^{j})}{\mathbb{P}_{\theta^{*}}^{\pi^{j}}(\tau^{j})}\right]\leq...\leq
1$ (190)

Using Markov Inequality, we have for any $\delta>0$

$\mathbb{P}\left(\ell(\bar{\theta},\mathcal{D}_{k})-\ell(\theta^{*},\mathcal{D}_{k})\geq\log\left(\dfrac{1}{\delta}\right)\right)\leq\delta.$
(191)

Using Union Bound, we obtain

$\mathbb{P}\left(\max_{\bar{\theta}\in\bar{\varTheta}}\ell(\bar{\theta},\mathcal{D}_{k})-\ell(\theta^{*},\mathcal{D}_{k})\geq\log\left(\dfrac{1}{\delta}\right)\right)\leq|\bar{\varTheta}|\delta.$
(192)

The lemma is then obtained by replacing $\delta$ with
$\delta/|\bar{\varTheta}|$. ∎

######  Lemma 11.

Assume that Assumption 1 is true and $\mathbf{B}_{h}^{\theta}$ is as defined
in (122). Let $x\in[0,1]^{\mathscr{A}\times\mathscr{O}}$ be such that
$\sum_{a\in\mathscr{A}}x(a,o)=1$ for all $o\in\mathscr{O}$. For any
$\theta\in\varTheta$ and any $\mathbf{w}\in\mathbb{R}^{\mathscr{O}}$, we have

$\sum_{a,o}x(a,o)\|\mathbf{B}_{h}^{\theta}(a,o)\mathbf{w}\|_{1}\leq\dfrac{\sqrt{S}}{\alpha}\|\mathbf{w}\|_{1}$
(193)

###### Proof.

Fix $s\in\mathscr{S}$, let $\mathbf{e}_{s}\in\mathbb{R}^{\mathscr{S}}$ be its
corresponding indicator vector. Since
$\mathbb{Z}_{h+1}^{\theta}\mathbb{T}_{h,a}^{\theta}\mathrm{diag}(\mathbb{Z}_{h}^{\theta}(o,\cdot))$
is a non-negative matrix, we have

$\displaystyle\quad~{}\|\mathbb{Z}_{h+1}^{\theta}\mathbb{T}_{h,a}^{\theta}\mathrm{diag}(\mathbb{Z}_{h}^{\theta}(o,\cdot))\mathbf{e}_{s}\|_{1}$
(194)
$\displaystyle=\bm{1}^{T}\mathbb{Z}_{h+1}^{\theta}\mathbb{T}_{h,a}^{\theta}\mathrm{diag}(\mathbb{Z}_{h}^{\theta}(o,\cdot))\mathbf{e}_{s}$
(195)
$\displaystyle=\bm{1}^{T}\mathbb{T}_{h,a}^{\theta}\mathrm{diag}(\mathbb{Z}_{h}^{\theta}(o,\cdot))\mathbf{e}_{s}=\bm{1}^{T}\mathrm{diag}(\mathbb{Z}_{h}^{\theta}(o,\cdot))\mathbf{e}_{s}=\mathbb{Z}_{h}^{\theta}(o,s)$
(196)

Therefore, for any $\mathbf{w}\in\mathbb{R}^{\mathscr{O}}$

$\displaystyle\quad~{}\sum_{a,o}x(a,o)\|\mathbf{B}_{h}^{\theta}(a,o)\mathbf{w}\|_{1}=\sum_{a,o}x(a,o)\|\mathbb{Z}_{h+1}^{\theta}\mathbb{T}_{h,a}^{\theta}\mathrm{diag}(\mathbb{Z}_{h}^{\theta}(o,\cdot))(\mathbb{Z}_{h}^{\theta\dagger}\mathbf{w})\|_{1}$
(198)
$\displaystyle\leq\sum_{a,o}x(a,o)\sum_{s\in\mathscr{S}}\left|[\mathbb{Z}_{h}^{\theta\dagger}\mathbf{w}](s)\right|\cdot\|\mathbb{Z}_{h+1}^{\theta}\mathbb{T}_{h,a}^{\theta}\mathrm{diag}(\mathbb{Z}_{h}^{\theta}(o,\cdot))\mathbf{e}_{s}\|_{1}$
(199)
$\displaystyle=\sum_{a,o}x(a,o)\sum_{s\in\mathscr{S}}\left|[\mathbb{Z}_{h}^{\theta\dagger}\mathbf{w}](s)\right|\cdot\mathbb{Z}_{h}^{\theta}(o,s)=\sum_{o}\left(\sum_{a}x(a,o)\right)\sum_{s\in\mathscr{S}}\left|[\mathbb{Z}_{h}^{\theta\dagger}\mathbf{w}](s)\right|\cdot\mathbb{Z}_{h}^{\theta}(o,s)$
(200)
$\displaystyle=\sum_{s\in\mathscr{S}}\left|(\mathbb{Z}_{h}^{\theta\dagger}\mathbf{w})_{s}\right|\sum_{o}\mathbb{Z}_{h}^{\theta}(o,s)=\sum_{s\in\mathscr{S}}\left|[\mathbb{Z}_{h}^{\theta\dagger}\mathbf{w}](s)\right|=\|\mathbb{Z}_{h}^{\theta\dagger}\mathbf{w}\|_{1}\leq\dfrac{\sqrt{S}}{\alpha}\|\mathbf{w}\|_{1}$
(201)

where we used Quick Fact 4 in the last inequality. ∎

######  Lemma 12.

Assume that Assumption 1 is true and $\mathbf{B}_{H:h+1}^{\theta}$ is as
defined in (124). Fix $0\leq h<H$. For any policy $\pi\in\varPi$, any
$\tau_{h}\in(\mathscr{O}\times\mathscr{A})^{h}$ such that $\pi(\tau_{h})>0$,
any $\theta\in\varTheta$, and any $\mathbf{w}\in\mathbb{R}^{\mathscr{O}}$, we
have

$\sum_{\tau_{-h}\in(\mathscr{O}\times\mathscr{A})^{H-h}}\pi(\tau_{-h}|\tau_{h})|\mathbf{B}_{H:h+1}^{\theta}(\tau_{-h})\mathbf{w}|\leq\dfrac{\sqrt{S}}{\alpha}\|\mathbf{w}\|_{1}.$
(202)

###### Proof.

Fix $\tau_{h}\in(\mathscr{O}\times\mathscr{A})^{h}$. First, when $h=H-1$, we
have $\mathbf{B}_{H:h+1}^{\theta}(\tau_{-h})=\mathbf{e}_{o_{H}}^{T}$ and

$\displaystyle\sum_{\tau_{-h}\in(\mathscr{O}\times\mathscr{A})^{H-h}}\pi(\tau_{-h}|\tau_{h})|\mathbf{B}_{H:h+1}^{\theta}(\tau_{-h})\mathbf{w}|=\sum_{a_{H},o_{H}}\pi_{h}(a_{H}|\tau_{H-1},o_{H})|\mathbf{w}(o_{H})|=\sum_{o_{H}}|\mathbf{w}(o_{H})|=\|\mathbf{w}\|_{1}.$
(203)

For the rest of the proof, assume $h<H-1$. First, note that

$\mathbf{B}_{H:h+1}^{\theta}(\tau_{-h})=\underbrace{\mathbf{e}_{o_{H}}^{T}\mathbb{Z}_{H}^{\theta}\mathbb{T}_{H-1,a_{H-1}}^{\theta}\mathrm{diag}(\mathbb{Z}_{H-1}^{\theta}(o_{H-1},\cdot))\cdots\mathbb{T}_{h+1,a_{h+1}}^{\theta}\mathrm{diag}(\mathbb{Z}_{h+1}^{\theta}(o_{h+1},\cdot))}_{=:\tilde{\mathbf{B}}_{H:h+1}^{\theta}(\tau_{-h})}\mathbb{Z}_{h+1}^{\theta\dagger}$
(204)

For any $s_{h+1}\in\mathscr{S}$, we have

$\displaystyle\pi(\tau_{-h}|\tau_{h})|\tilde{\mathbf{B}}_{H:h+1}^{\theta}(\tau_{-h})\mathbf{e}_{s_{h+1}}|=\pi(\tau_{-h}|\tau_{h})\mathbb{P}_{\theta}^{-}(\tau_{-h}|s_{h+1})=\mathbb{P}_{\theta}^{\pi(\tau_{h},\cdot)}(\tau_{-h}|s_{h+1})$
(205)

where $\pi(\tau_{h},\cdot)$ is the partial policy for timestamps $h+1$ to $H$
obtained by fixing the historical trajectory $\tau_{h}$.

Therefore, for any $\mathbf{w}\in\mathbb{R}^{\mathscr{O}}$,

$\displaystyle\quad~{}\sum_{\tau_{-h}}\pi(\tau_{-h}|\tau_{h})|\mathbf{B}_{H:h+1}^{\theta}(\tau_{-h})\mathbf{w}|=\sum_{\tau_{-h}}\pi(\tau_{-h}|\tau_{h})|\tilde{\mathbf{B}}_{H:h+1}^{\theta}(\tau_{-h})(\mathbb{Z}_{h}^{\theta\dagger}\mathbf{w})|$
(206)
$\displaystyle\leq\sum_{\tau_{-h}}\sum_{s_{h+1}\in\mathscr{S}}\pi(\tau_{-h}|\tau_{h})|\tilde{\mathbf{B}}_{H:h+1}^{\theta}(\tau_{-h})\mathbf{e}_{s_{h+1}}|\cdot\left|(\mathbb{Z}_{h}^{\theta\dagger}\mathbf{w})_{s_{h+1}}\right|=\sum_{\tau_{-h}}\sum_{s_{h+1}\in\mathscr{S}}\mathbb{P}_{\theta}^{\pi(\tau_{h},\cdot)}(\tau_{-h}|s_{h+1})\left|(\mathbb{Z}_{h}^{\theta\dagger}\mathbf{w})_{s_{h+1}}\right|$
(207)
$\displaystyle=\sum_{s_{h+1}\in\mathscr{S}}\left(\sum_{\tau_{-h}}\mathbb{P}_{\theta}^{\pi(\tau_{h},\cdot)}(\tau_{-h}|s_{h+1})\right)\cdot\left|(\mathbb{Z}_{h}^{\theta\dagger}\mathbf{w})_{s_{h+1}}\right|=\|\mathbb{Z}_{h}^{\theta\dagger}\mathbf{w}\|_{1}\leq\dfrac{\sqrt{S}}{\alpha}\|\mathbf{w}\|_{1}$
(208)

where we used Quick Fact 4 in the last inequality.

∎