# Thompson Sampling for Infinite-Horizon Discounted Decision Processes

Daniel Adelman  Booth School of Business, The University of Chicago, Chicago,
IL 60637  Cagla Keceli  Booth School of Business, The University of Chicago,
Chicago, IL 60637  Alba V. Olivares Nadal  UNSW Business School, University of
New South Wales, Sydney, Australia

###### Abstract

We model a Markov decision process, parametrized by an unknown parameter, and
study the asymptotic behavior of a sampling-based algorithm, called Thompson
sampling. The standard definition of regret is not always suitable to evaluate
a policy, especially when the underlying chain structure is general. We show
that the standard (expected) regret can grow (super-)linearly and fails to
capture the notion of learning in realistic settings with non-trivial state
evolution. By decomposing the standard (expected) regret, we develop a new
metric, called the expected residual regret, which forgets the immutable
consequences of past actions. Instead, it measures regret against the optimal
reward moving forward from the current period. We show that the expected
residual regret of the Thompson sampling algorithm is upper bounded by a term
which converges exponentially fast to 0. We present conditions under which the
posterior sampling error of Thompson sampling converges to 0 almost surely. We
then introduce the probabilistic version of the expected residual regret and
present conditions under which it converges to 0 almost surely. Thus, we
provide a viable concept of learning for sampling algorithms which will serve
useful in broader settings than had been considered previously.

##  1 Introduction

We consider a control problem in which a decision-maker (DM) interacts with an
environment without knowing the value of a parameter encoded into this
environment. This environment is modeled by a discrete-time Markov decision
process (MDP). The DM applies a control and, in return, the system moves to
the next state and generates a reward. Neither of the outputs are
deterministic; they are contingent on the current state, control and value of
the unknown parameter. Using the state transition and reward information, the
DM picks a control which yields the subsequent transition and reward.

Our model is mainly shaped by the stochastic adaptive control literature and,
in particular, complements Kim (2017). Numerous prominent papers parametrize
MDP’s by an unknown parameter and estimate this parameter using different
methods. We investigate the asymptotic performance of a popular parameter
estimation algorithm, Thompson sampling (TS), first described by Thompson
(1933). Aiming to maximize the total reward, yet not knowing the underlying
parameter that determines the rewards and state transitions, the DM faces a
trade-off between choosing controls tied to unexplored parameter candidates
and choosing controls which are likely to yield high rewards. This exploration
vs. exploitation trade-off is often addressed in online decision-making
problems by TS. After estimating the unknown parameter by TS, the DM selects a
control while assuming the estimate is the true parameter.

Despite the logarithmic expected regret guarantees in bandit settings (Agrawal
and Goyal 2012), we document through examples that the expected regret no
longer has logarithmic guarantees when the chain structure underneath the MDP
is generic. In particular, we document how the expected regret can grow
(super-)linearly. This means that the standard notion of expected regret used
in the literature, i.e., the gap between the cumulative reward of the DM and
the cumulative reward of an omniscient agent, is not fully informative when
the underlying chain is general. The expected regret is unable to discern that
learning is taking place, even though it is. These kinds of examples may be
implicitly known to researchers who work in this area, yet they have not been
documented in the literature to the best of our knowledge.

We provide the first theoretical results that capture a different notion of
(expected) regret of the TS algorithm. In particular, we extend a result of
Kim (2017) (on the convergence of the expected posterior error) to discounted-
reward MDP’s and to general state and control spaces. We assume Borel state-
control spaces, allowing the spaces to be infinite. Thus, our work allows
questions of regret and sampling algorithms to be addressed in broader
settings in which they have not been addressed before. Extending the
performance guarantees of the new notion of regret to MDP’s with a general
chain structure is an important potential avenue of study.

The literature on parametrized MDP’s almost always considers the long-run
average regret per period. In contrast, we study guarantees when the
performance criterion is the expected infinite-horizon discounted reward.
Since problems of economic significance are often most properly formulated
with discounting, having the objective function formulated as an infinite-
horizon discounted reward problem would allow the ideas of learning through
sampling to be applied in these settings.

We develop a general canonical probability space for adaptive learning
algorithms based on sampling, of which TS is a special case. Kim (2017) and
Banjević and Kim (2019) construct a similar probability space for TS, but do
not include the sampled parameters in the sample space. We are not aware of
other work which incorporates this canonical formulation. Having the sampling
algorithms posed in a coherent framework allows for it to be understood and
studied rigorously. For example, the formulation makes evident that the
underlying process is history-dependent, i.e., not Markovian. To make this
clear, we will refer to the adaptive version of the process with an unknown
parameter as $\theta$-MDP instead of MDP.

We offer a novel decomposition of the standard notion of expected regret. Our
notion of expected regret can be computed at any finite period $n$, from the
vantage point of a DM in period 0. We identify three distinct components of
the expected regret, only one of which is always suitable for learning
problems. The first component is the expected regret associated with the past,
i.e., from period 0 up to period $n$. This quantifies the difference between
the expected reward received by the DM and the expected reward of the policy
which knows the true parameter. The second component is the expected regret
that emanates from the policy’s state in period $n$, which is inextricably
tied to the past decisions. It captures the expected infinite-horizon (future)
consequences of being in a suboptimal state in period $n$. The third and final
component captures the DM’s ability to implement what is optimal moving
forward, conditional on the period-$n$ state. This component is the only
component that is “controllable” by the DM, once they have arrived at the
period-$n$ state. It reflects how the best opportunities available to the DM
from period $n$ onward compare to how the system will evolve under the
sampling policy. Our analysis focuses on this concept which we call _expected
residual regret_. The expected residual regret forgets both the past and the
future “sunk” portions of the total regret.

Decomposing the standard expected regret is a novel approach to view and
quantify the performance of a policy. Through this decomposition, we connect
the notion of expected regret to a concept called _asymptotic discount
optimality_ (ADO) (Schäl 1987, Hernández-Lerma 2012). We demonstrate how the
ADO concept relates to expected residual regret. To the best of our knowledge,
this concept has not been used within the sampling context before and has not
been connected to the notion of (expected) regret.

We show that the posterior belief on the true parameter converges to 1 when TS
is implemented; this behavior is called _complete learning_. Complete learning
is a stronger result than learning in expectation, i.e., expected posterior
belief, because it gives assurance about the individual sample paths. To the
best of our knowledge, most results are on the expected-valued version of
posterior belief. The notion of complete learning has been studied frequently
in bandit contexts, including the prominent work of Freedman (1963), yet to
our knowledge it has not been applied to Borel state-control spaces and has
not been analyzed under the discounted reward criterion. In the adaptive
learning literature, there is an alternative to TS, known as the minimum
contrast estimator, which is shown to achieve complete learning (Hernández-
Lerma 2012). However, complete learning has not been connected to the concept
of ADO, and there is no notion of probabilistic ADO.

Building on expected residual regret, we define its sample-path version,
called _probabilistic residual regret_ or _residual regret_. Similar to
expected residual regret, it captures the DM’s ability to implement what is
optimal moving forward, but starting from the random state of the MC in period
$n$. It quantifies the difference in optimal rewards and TS-driven rewards.
Therefore, the probabilistic residual regret is a random quantity whose
expected value is the expected residual regret. Conceptually, probabilistic
residual regret is similar to complete learning as they are both concerned
with individual sample paths.

The paper is organized as follows. In Section 2, we provide additional
literature review. Then we motivate the need to modify the definition of
expected regret since the standard notion of expected regret can grow linearly
in non-trivial settings. In Section 3, we model the sampling algorithm and
formulate the canonical probability space which involves the sampled
parameters. In Section 4, we characterize TS by defining the posterior update
and control selection mechanisms. In Section 5, we decompose the standard
notion of expected regret into components and interpret each component,
highlighting expected residual regret as the only “actionable” component. In
Section 6, we provide an asymptotic analysis of the expected residual regret.
In Section 7, we show that TS exhibits complete learning, i.e., the posterior
sampling error converges to 0 almost surely. We also show that probabilistic
residual regret converges to 0 almost surely.

##  2 Literature Review and Motivation

Here, we highlight papers of similar setup and provide an example where the
standard expected regret fails to discern learning.

###  2.1 Literature Review

TS has proved not only successful for multi-armed bandit problems (MAB) (a
degenerate case of MDP); but also for parametrized MDP’s, i.e.,
$\theta$-MDP’s, which need not be Markovian. The work on $\theta$-MDP’s
typically requires assumptions on the underlying chain to give performance
guarantees on the expected regret. For example, Kim (2017) shows that TS
achieves asymptotically optimal expected regret when the Markov chain under
the optimal policy, which knows the true parameter, is ergodic.111A Markov
chain is _ergodic_ if the transition matrix corresponding to every
deterministic stationary policy consists of a single recurrent class (Puterman
2014). Another example is Gopalan and Mannor (2015), which provides a
probabilistic logarithmic upper bound on the expected regret of TS, assuming
that the starting state is recurrent under the optimal policy generated by any
of the possible parameters. Although Kearns and Singh (2002) and Leike et al.
(2016) assume a more general chain setting, they study decision processes over
finite state-control spaces. In contrast to the finite state-control spaces or
the expected average-reward criterion of these works, we assume a general
state-control space, under the discounted-reward criterion, similar to Schäl
(1987). We impose additional assumptions on the underlying chain to be able to
extend the work of Kim (2017) into our more general setting.

Kim (2017) shows that the expected posterior sampling error decays
exponentially. We extend this result to a broader framework. We also show that
the probabilistic version of the posterior sampling error decays
exponentially, which we believe has not been explored yet.

Our work mostly complements Kim (2017) and Banjević and Kim (2019). Both works
show good performance guarantees for Thompson sampling under parameter
uncertainty, yet our work has a stronger connection with the former since we
also assume a finite parameter space. The latter adopts a continuous parameter
space, similar to Hernández-Lerma (2012), which results in a setting that is
harder to analyze.

The stream of work that analyzes the behavior of TS do not usually consider
infinite-horizon, and are most often in the MAB setting, with history-
independent samples to the best of our knowledge. Kalkanli and Ozgur (2020)
analyze the asymptotic behavior of TS with history-dependence, but in the
context of the MAB problem. Although we utilize different methodologies than
theirs, our work carries this analysis into the under-explored context of the
$\theta$-MDP.

###  2.2 Motivation

TS has been shown to have good performance in the MAB setting. The MAB problem
is equivalent to a $\theta$-MDP with no state, or alternatively, a one-step
$\theta$-MDP. In each decision period $t$, the DM samples a parameter from the
posterior distribution. By treating the sample as the true parameter, the DM
chooses a control, i.e., plays one of the constantly-many arms, and
immediately observes a reward. The reward of each arm is generated according
to some fixed (unknown) distribution and the objective is to maximize the
total expected reward. Arms’ rewards are generated independently of each
other. Let $\mu_{i}$ denote the (unknown) expected reward of arm $i$ and
$i(t)$ be the arm played in period $t$. The expected finite-time regret is the
expected total difference between the optimal strategy of pulling the arm with
the highest mean and the strategy followed by the DM, i.e.,

$\displaystyle E[\textnormal{Regret}(n)]\coloneqq
E\left[\sum_{t=1}^{n}(\mu^{*}-\mu_{i(t)})\right].$

where $\mu^{*}\coloneqq\max_{i}\mu_{i}$. In the pioneering Lai and Robbins
(1985), the (expected) regret of any bandit algorithm is lower bounded, in the
limit, by

$E[\textnormal{Regret}(n)]\geq\left[\sum_{i=2}^{K}\frac{\Delta_{i}}{D(\mu_{i}||\mu^{*})}+o(1)\right]\ln(n),$
(1)

where $D$ denotes the Kullback–Leibler divergence and
$\Delta_{i}\coloneqq\mu^{*}-\mu_{i}$. The bound in (1) shows that the best
achievable expected regret is of order $\ln(n)$. Complementing the logarithmic
lower bound for any bandit algorithm, Agrawal and Goyal (2012) upper bounds
the expected regret of the TS algorithm by

$\displaystyle E[\textnormal{Regret}(n)]\leq
O\left(\left(\sum_{i=2}^{K}\frac{1}{\Delta_{i}^{2}}\right)^{2}\ln(n)\right).$

Since the order of the upper bound on the expected regret of TS matches the
logarithmic lower bound for any algorithm in (1), the expected regret of TS
grows logarithmically. We underline that these results are valid for the MAB
setting. These results can also apply to the $\theta$-MDP setting with a
trivial state process, such that the stochastic process is driven by an iid
state process222The states evolve independently of the controls and have the
same probability distribution.. In addition, they assume no discounting of the
rewards. Our setting is fundamentally different, i.e., the states evolve based
on the controls and are not identically distributed, hence these results do
not apply in general. Example 2.1 illustrates a simple yet non-trivial state
process.

######  Example 2.1 (Expected regret grows linearly).

Consider the three-state process shown in Figure 1. In period $t=0$, the DM
lies in $x_{0}$ and can choose either control $A$ or $B$, with an immediate
reward of 0. Control $A$ leads to the state $x_{A}$, and from then onward only
control $A$ can be chosen; the DM is “stuck”. Control $B$ leads to the state
$x_{B}$, and similarly, only control $B$ can be chosen from then onward. The
true parameter can either be $A$ or $B$. We represent the one-step reward
generating function by $R^{A}(\cdot)$ when $A$ is the true parameter, and
$R^{B}(\cdot)$ otherwise. We assume that the prior belief on the true
parameter is not degenerate, i.e., not equal to 1.

$x_{0}$$x_{A}$$x_{B}$$A$$B$ $R^{A}(x_{A})=1$
---
$R^{B}(x_{A})=0$
$R^{A}(x_{B})=0$
---
$R^{B}(x_{B})=1$
Figure 1: Constant reward depending only on the first control, picked at t=0.

In Example 2.1 if the first guess is right, the DM receives a reward of 1
forever and otherwise receives no reward at all. Thus, unlike in the setting
of Agrawal and Goyal (2012), in broader settings the expected finite-horizon
regret does not necessarily grow logarithmically.

Consider Example 2.1 with an alternative setup such that when the guess at
$t=0$ is correct, the reward generated in the corresponding state is equal to
the number of periods the policy has spent in that state. If the DM makes a
wrong guess they are stuck with 0 reward forever, while the oracle earns a
sequence of increasing rewards. Here, the expected (undiscounted) regret grows
super-linearly. While the standard expected regret grows linearly or super-
linearly, nonetheless learning still happens. If the DM receives a reward of 1
in the next period, then they immediately learn whether $A$ or $B$ drives the
reward process. This example shows the motivation to construct an alternative,
more “lenient”, notion of expected regret that forgets the immutable
consequences of past actions.

##  3 Model Setup

We study a discounted-reward stochastic control problem over an infinite
horizon. The underlying MDP is indexed by some parameter $\theta$. In Section
3.1, we formulate the MDP when the DM knows $\theta$, building on the
mathematical framework of Hernández-Lerma (2012). In the subsequent sections,
we assume the DM solves the $\theta$-MDP using estimates of $\theta$, i.e.,
without knowing the value of $\theta$. We construct the probability space in
Section 3.2. This lays the groundwork for TS.

###  3.1 Markov Decision Process for Known $\theta$

Consider a discrete-time MDP,
$(\mathcal{X},\mathcal{U},\\{\mathcal{U}(x),x\in\mathcal{X}\\},f^{\theta},q^{\theta})$.
In our setting, the reward and state transition densities depend on the
parameter $\theta\in\mathcal{P}$, which is a single point in the finite
parameter space $\mathcal{P}$. Later, when $\theta$ is assumed to be unknown,
we will represent the random sample drawn in period $t$ by $\Theta_{t}$ and
its realization by $\theta_{t}$. We reserve upper-case letters to denote
random variables, lower-case letters to realizations of random variables,
script letters to spaces and sometimes sets, and bold upper-case letters to
elements of $\sigma$-algebras to be defined. Let $\mathbb{R}$ denote the set
of real numbers, and $\mathcal{B}(\cdot)$ the Borel $\sigma$-algebra of a
topological space.

The tuple
$(\mathcal{X},\mathcal{U},\\{\mathcal{U}(x),x\in\mathcal{X}\\},f^{\theta},q^{\theta})$
consists of:

  1. 1.

State space $\mathcal{X}$, a Borel space. We denote the system state in period
$t\in\\{0,1,2,\dots\\}$ by $X_{t}\in\mathcal{X}$.

  2. 2.

Control space $\mathcal{U}$, a Borel space. The control applied in period $t$
is $U_{t}\in\mathcal{U}$.

  3. 3.

Set of admissible controls $\mathcal{U}(x)$, which is a compact subset of
$\mathcal{U}$ for every $x\in\mathcal{X}$. Let
$\mathcal{U}=\bigcup_{x\in\mathcal{X}}\mathcal{U}(x)$. The set of admissible
state-control pairs,

$\mathbb{K}\coloneqq\\{(x,u)\mid x\in\mathcal{X},\,u\in\mathcal{U}(x)\\},$

is assumed to be a measurable subset of the product space
$\mathcal{X}\times\mathcal{U}$.

  4. 4.

Given $x_{t}$ and $u_{t}$ in period $t$, the system generates random reward
$R_{t}\in\mathscr{R}_{c}\subset\mathbb{R}_{+}$, where $\mathscr{R}_{c}$ is
compact and measurable according to a conditional distribution
$F^{\theta}(\cdot\mid x_{t},u_{t})$. The conditional distribution
$F^{\theta}(\cdot\mid x,u)$ admits a measurable, continuous, one-step reward
density333Radon-Nikodym derivative of $F^{\theta}$ with respect to $\lambda$.
$f^{\theta}:\mathscr{R}_{c}\to\mathbb{R}_{+}$ with respect to a
$\sigma$-finite measure $\lambda$ on
$(\mathscr{R}_{c},\mathcal{B}(\mathscr{R}_{c}))$, such that

$F^{\theta}(\mathbf{R}\mid x,u)\coloneqq\int_{\mathbf{R}}f^{\theta}(r\mid
x_{t}=x,u_{t}=u)\,d\lambda(r),\quad\forall\mathbf{R}\in\mathcal{B}(\mathscr{R}_{c}),(x,u)\in\mathbb{K}.$

The expected reward in period $t$ is

$\displaystyle
r^{\theta}(x_{t},u_{t})\coloneqq\int_{\mathscr{R}_{c}}rf^{\theta}(r\mid
x_{t},u_{t})d\lambda(r),\quad\forall\,(x_{t},u_{t})\in\mathbb{K}.$ (2)

  5. 5.

Given $x_{t}$ and $u_{t}$ in period $t$, the system transitions into random
state $X_{t+1}$ according to a conditional distribution $Q^{\theta}(\cdot\mid
x_{t},u_{t})$. The conditional distribution $Q^{\theta}(\cdot\mid x,u)$ admits
a one-step transition density444Radon-Nikodym derivative of $Q^{\theta}$ with
respect to $\eta$ $q^{\theta}:\mathbb{K}\to\mathcal{X}$ with respect to a
$\sigma$-finite measure $\eta$ on $(\mathcal{X},\mathcal{B}(\mathcal{X}))$
such that

$Q^{\theta}(\mathbf{X}\mid x,u)\coloneqq\int_{\mathbf{X}}q^{\theta}(y\mid
x_{t}=x,u_{t}=u)d\eta(y),\quad\forall\mathbf{X}\in\mathcal{B}(\mathcal{X}).$

Similarly, given $x_{t}$ and $u_{t}$ in period $t$,

$Q^{\theta}(\mathbf{X}\mid
x,u)\coloneqq\textnormal{Prob}(X_{t+1}\in\mathbf{X}\mid
x_{t}=x,u_{t}=u),\quad\forall\mathbf{X}\in\mathcal{B}(\mathcal{X}).$

######  Remark.

Since $f^{\theta}(\cdot\mid x_{t},u_{t})$ is continuous on compact set
$\mathscr{R}_{c}$, it attains its minimum and maximum in $\mathscr{R}_{c}$.
Thus, there exists a constant $M\geq 0$ such that
$|r^{\theta}(x_{t},u_{t})|\leq M$ $\forall(x_{t},u_{t})\in\mathbb{K}$. To see
why this holds, note that

$\displaystyle|r^{\theta}(x_{t},u_{t})|\leq\int_{\mathscr{R}_{c}}|rf^{\theta}(r\mid
x_{t},u_{t})|d\lambda(r)$
$\displaystyle\leq\int_{\mathscr{R}_{c}}\max(|rf^{\theta}(r\mid
x_{t},u_{t})|)d\lambda(r)$
$\displaystyle=\max_{r\in\mathscr{R}_{c}}|rf^{\theta}(r\mid
x_{t},u_{t})|\lambda(\mathscr{R}_{c})<\infty,$

where the first inequality follows by (2) and Jensen’s inequality, and the
equality holds since $\max(|rf^{\theta}(r\mid x_{t},u_{t})|)$ is constant in
$r$. Then, $\max\limits_{r\in\mathscr{R}_{c}}|rf^{\theta}(r\mid x_{t},u_{t})|$
is finite because $f^{\theta}(\cdot\mid x_{t},u_{t})$ is continuous on a
compact set, and $\lambda(\mathscr{R}_{c})$ is finite since
$\mathscr{R}_{c}\subset\mathbb{R}_{+}$ is compact and $\lambda$ is a
$\sigma$-finite measure.

The DM aims to maximize the infinite-horizon expected total discounted reward.
The _optimal value function_ $\nu^{\theta}(x)$ represents the maximum such
reward starting from state $x$, and it depends on the true parameter $\theta$.
It is known from Hernández-Lerma and Lasserre (2012) that this problem is
solved by the Bellman equation in (3).

$\nu^{\theta}(x)\coloneqq\sup_{u\in\mathcal{U}(x)}\left\\{r^{\theta}(x,u)+\beta\int_{y\in\mathcal{X}}\nu^{\theta}(y)dQ^{\theta}(dy\mid
x,u)\right\\},\quad\forall x\in\mathcal{X},\theta\in\mathcal{P},$ (3)

where $\beta\in[0,1)$ is the discounting factor. If $\nu^{\theta}(x)$ is a
solution to (3), let $\mu^{\theta}$ denote the corresponding optimal policy
for parameter $\theta$. Under sufficient technical conditions, $\mu^{\theta}$
is a stationary, deterministic, and Markovian policy. As showing these
conditions holds in this setting are outside of our scope, we make the
following assumption:

######  Assumption 0.

For all $\theta\in\mathcal{P}$, there exists a unique solution to (3) such
that the supremum is attained, and there exists an optimal policy
$\mu^{\theta}$ that is stationary, deterministic, and Markovian.

######  Remark.

The condition in Assumption  ‣ 3.1 is necessary for all of the main results of
the paper. Therefore, we will not specifically refer to it in the Lemma,
Proposition and Theorem statements.

In this section, we formulated an MDP parametrized by a known parameter
$\theta$. In Section 3.2, we define the optimal policy in the adaptive
setting, i.e., where $\theta$ is an unknown (fixed) parameter.

###  3.2 Adaptive Learning with Sampling

From this point forward we take $\theta$ to be an unknown and fixed parameter.
A control problem parametrized by an unknown parameter is called an _adaptive_
control problem, we refer the reader to Hernández-Lerma (2012) for a
comprehensive definition. As defined in Section 3.1, the reward density and
transition density are parametrized by the (finitely-many) parameter values.
Since we reserve $\theta$ for the true parameter, $f^{\gamma}(\cdot\mid x,u)$
and $q^{\gamma}(\cdot\mid x,u)$ represent the reward and transition density of
an arbitrary parameter $\gamma\in\mathcal{P}$. Since $\theta$ is the
underlying true parameter, $f^{\theta}(\cdot\mid x,u)$ and
$q^{\theta}(\cdot\mid x,u)$ represent the reward and transition density which
drive the actual (observed) process, i.e., the observed reward and the
observed next state.

Next, we estimate the unknown parameter $\theta$ using a generic sampling
algorithm.

####  3.2.1 Overview of Sampling Algorithm.

Had $\theta$ been known to the DM, the DM would have maximized the objective
function by solving the optimization problem in (3) for known $\theta$, under
Assumption  ‣ 3.1. Given the parameter uncertainty, the problem evolves into a
learning problem, where the DM needs to choose suitable controls while
gathering information on $\theta$. To specify how the DM chooses controls in
each period $t$, we first define the data available at the beginning of each
period $t$, i.e., the history. We will use history and admissible history
interchangeably. In contrast to the setting with known parameter $\theta$,
when $\theta$ is unknown the learning procedure makes use of the entire
history, i.e., is not Markovian.

$\pi_{t}(\cdot\mid H_{t})$$f^{\theta}(\cdot\mid
X_{t},U_{t})$$q^{\theta}(\cdot\mid
X_{t},U_{t})$$X_{t}$$\theta_{t}$$U_{t}$$R_{t}$$X_{t+1}$$H_{t}$$H_{t+1}$ Figure
2: Evolution of the stochastic process, in the case when $\theta$ is not
known.

Figure 2 illustrates the random variables which drive the learning process,
ordered in the sequence of occurrence. The DM observes the history information
from period 0 up to period $t$, denoted by $H_{t}$. The history vector
contains all information up to and including $X_{t}$, i.e., the state in
period $t$. Provided by the system designer, the function $\pi_{t}(\cdot\mid
H_{t})$ takes $H_{t}$ as input and returns the distribution on the period-$t$
sample $\Theta_{t}$. Although $\pi_{t}(\cdot\mid H_{t})$ is a deterministic
function of $H_{t}$, it is random due to random $H_{t}$. Next, the DM draws a
sample $\Theta_{t}$ from the parameter pool, with probability equal to
$\pi_{t}(\Theta_{t}\mid H_{t})$. The randomness of $\Theta_{t}$ arises from
two sources: due to its dependence on random $H_{t}$ through
$\pi_{t}(\cdot\mid H_{t})$, and the random nature of sampling. Given the
history, the DM solves an optimization problem yielding the “optimal” control
$U_{t}\in\mathcal{U}(X_{t})$, assuming the true $\theta$ equals $\theta_{t}$,
the realized sample. The history includes only admissible controls, defined in
Section 3.1. The state-control pair $(X_{t},U_{t})$ gives rise to a random
reward $R_{t}$, which depends on $\theta$. $R_{t}$ is drawn from the reward
density $f^{\theta}(\cdot\mid X_{t},U_{t})$. Finally, given the transition
density $q^{\theta}(\cdot\mid X_{t},U_{t})$ and the current state-control
pair, the system transitions into a random next state $X_{t+1}$.

The collection of $H_{t}$, $\Theta_{t}$, $U_{t}$, $R_{t}$ and $X_{t+1}$
constitutes $H_{t+1}$. The system designer provides $f^{\gamma}(\cdot\mid
x,u)$ and $q^{\gamma}(\cdot\mid x,u)$ for all candidate values
$\gamma\in\mathcal{P}$, which are utilized to update the belief vector, to be
defined in Section 4. Nevertheless, the evolution of the process depends only
on $\theta$, i.e., nature acts according to $f^{\theta}(\cdot\mid x,u)$ and
$q^{\theta}(\cdot\mid x,u)$. After observing the rewards and transitions in
period $t$, the DM updates their belief vector $\pi_{t+1}(\cdot\mid H_{t+1})$
in period $t+1$. Conditional on the state-control pair, the reward and
transitions are mutually independent.555Yet, there can be alternative settings
where an exogenous random variable impacts both $R_{t}$ and $X_{t+1}$,
resulting in dependence between the reward and the next state.

####  3.2.2 Canonical Formulation.

The space of admissible histories up to period $t$ is denoted by
$\mathcal{H}_{t}$. For $t=0$, we have $\mathcal{H}_{0}\coloneqq\mathcal{X}$,
i.e., $H_{0}\coloneqq X_{0}$. For $t\geq 1$, the space of admissible histories
has product form,

$\mathcal{H}_{t}\coloneqq(\mathcal{X}\times\mathcal{P}\times\mathcal{U}\times\mathscr{R}_{c})^{t}\times\mathcal{X}=\mathcal{H}_{t-1}\times\mathcal{P}\times\mathcal{U}\times\mathscr{R}_{c}\times\mathcal{X}.$

The history spaces $\mathcal{H}_{0}$ and $\mathcal{H}_{t}$ ($t=1,2,\dots$) are
endowed with their product Borel $\sigma$-algebras $\mathcal{B}(\mathcal{X})$,
$\mathcal{B}(\mathcal{P})$, $\mathcal{B}(\mathcal{U}(x))$ and
$\mathcal{B}(\mathscr{R}_{c})$. The history random variable follows the
recursion

$\displaystyle
H_{t}\coloneqq(X_{0},\Theta_{0},U_{0},R_{0},\dots,X_{t-1},\Theta_{t-1},U_{t-1},R_{t-1},X_{t}),$
(4)

with $(X_{t},U_{t})\in\mathbb{K}$, where $t\in\mathbb{N}_{\geq 2}$ denotes the
period. The history vector’s realization is denoted by

$h_{t}\coloneqq(x_{0},\theta_{0},u_{0},r_{0},\dots,x_{t-1},\theta_{t-1},u_{t-1},r_{t-1},x_{t}),$

similarly, with $(x_{t},u_{t})\in\mathbb{K}$. In addition,
$\overline{\mathcal{H}}_{0}\coloneqq\mathcal{H}_{0}=\mathcal{X}$, and for
$t\geq 1$, $\mathcal{H}_{t}$ is a subspace of

$\overline{\mathcal{H}}_{t}\coloneqq(\mathcal{X}\times\mathcal{P}\times\mathcal{U}\times\mathscr{R}_{c})^{t}\times\mathcal{X}=\mathcal{H}_{t-1}\times\mathcal{P}\times\mathcal{U}\times\mathscr{R}_{c}\times\mathcal{X}.$

The infinite sequence of four-tuples $\overline{\mathcal{H}}_{\infty}$ is the
sample space, denoted by $\Omega$,

$\Omega=\overline{\mathcal{H}}_{\infty}\coloneqq(\mathcal{X}\times\mathcal{P}\times\mathcal{U}\times\mathscr{R}_{c})^{\infty}=\mathcal{X}\times\mathcal{P}\times\mathcal{U}\times\mathscr{R}_{c}\times\mathcal{X}\times\mathcal{P}\times\mathcal{U}\times\mathscr{R}_{c}\dots$

$\Omega$ is the space of histories
$\overline{H}_{t}=(X_{0},\Theta_{0},U_{0},R_{0},X_{1},\Theta_{1},U_{1},R_{1},\dots)$
with $X_{t}\in\mathcal{X}$, $\Theta_{t}\in\mathcal{P}$, $U_{t}\in\mathcal{U}$,
$R_{t}\in\mathscr{R}_{c}$ for $t\geq 0$. The state, parameter, control and
reward variables are defined as projections from $\Omega$ to sets
$\mathcal{X}$, $\mathcal{P}$, $\mathcal{U}$ and $\mathscr{R}_{c}$,
respectively.

A typical element of the sample space, $\omega\in\Omega$, is an infinite
sequence of the form below:

$\omega=(x_{0},\theta_{0},u_{0},r_{0},x_{1},\theta_{1},u_{1},r_{1},\dots)\text{
where }x_{t}\in\mathcal{X}\text{, }\theta_{t}\in\mathcal{P}\text{,
}u_{t}\in\mathcal{U}\text{, }r_{t}\in\mathscr{R}_{c},\quad\forall\,t\geq 0.$

######  Definition.

The posterior distribution ($\pi_{t}(\cdot\mid
H_{t}):\mathcal{P}\mid\mathcal{H}_{t}\to\mathbb{R}_{+}$) is a belief
distribution over $\Theta_{t}\in\mathcal{P}$. It is a function of the random
and time-dependent history $H_{t}$.

######  Definition.

A randomized policy $\mu=\\{\mu_{t}\\}$ is a sequence of stochastic kernels
$\mu_{t}$ on $\mathcal{U}$ given $\mathcal{H}_{t}$ and $\mathcal{P}$,
satisfying

$\mu_{t}(\mathcal{U}(x_{t})\mid h_{t},\theta_{t})=1\text{ for all
}h_{t}\in\mathcal{H}_{t},\,\theta_{t}\in\mathcal{P},\text{ and }t\geq 0.$

where $\mu_{t}$ is an element of the set of admissible control policies,
denoted by $\mathcal{M}$.

$\mathcal{B}(\Omega)$ is the corresponding product $\sigma$-algebra of
$\Omega$. The final element of the probability space is the probability
measure $\mathbb{P}_{x_{0}}^{\mu,\theta}:\mathcal{B}(\Omega)\to[0,1]$. It
represents the probability measure when policy $\mu\in\mathcal{M}$ is used,
the initial state is $X_{0}=x_{0}$, and the true parameter is $\theta$. The
expectation operator with respect to $\mathbb{P}_{x_{0}}^{\mu,\theta}$ is
$\mathbb{E}_{x_{0}}^{\mu,\theta}$. Whenever this expectation is taken, we take
the random variables $(X_{n},\Theta_{n},U_{n},R_{n})_{\forall n}$ as generated
by $\mathbb{P}_{x_{0}}^{\mu,\theta}$. We have a collection of sample paths
that are parametrized by $\mu$, $\theta$ and $x_{0}$. The operands of these
operators are specified by the underlying state process induced by $\mu$,
$\theta$ and $x_{0}$. We emphasize that the space of admissible histories,
$\mathcal{H}_{t}$, is contained in $\Omega=\overline{\mathcal{H}}_{\infty}$,
and therefore, the (admissible) history random variable $H_{t}$ is defined on
$(\Omega,\mathcal{B}(\Omega),\mathbb{P}_{x_{0}}^{\mu,\theta})$.

A randomized, history-dependent policy $\mu$ induces a probability measure
$\mathbb{P}_{x_{0}}^{\mu,\theta}$ on $(\Omega,\mathcal{B}(\Omega))$. By the
Ionescu-Tulcea Theorem, proved in Proposition 7.28 of Shreve (1978), for any
given policy $\mu=\\{\mu_{t}\\}\in\mathcal{M}$, any initial state
$X_{0}=x_{0}$ and true parameter $\theta\in\mathcal{P}$, there exists a unique
probability measure $\mathbb{P}_{x_{0}}^{\mu,\theta}$ on
$(\Omega,\mathcal{B}(\Omega))$, satisfying:

  1. (a)

$\mathbb{P}_{x_{0}}^{\mu,\theta}(\mathcal{H}_{\infty})=1$,

  2. (b)

$\mathbb{P}_{x_{0}}^{\mu,\theta}(X_{0}=x_{0})=1$,

  3. (c)

$\mathbb{P}_{x_{0}}^{\mu,\theta}(\Theta_{t}=\theta_{t}\mid
h_{t})=\pi_{t}(\theta_{t}\mid h_{t})$ for all $\theta_{t}\in\mathcal{P}$ given
$h_{t}\in\mathcal{H}_{t}$ and $t\geq 0$,

  4. (d)

$\mathbb{P}_{x_{0}}^{\mu,\theta}(U_{t}\in\mathbf{U}\mid
h_{t},\theta_{t})=\mu_{t}(\mathbf{U}\mid h_{t},\theta_{t})$ for all
$\mathbf{U}\in\mathcal{B}(\mathcal{U})$ given $h_{t}\in\mathcal{H}_{t}$,
$\theta_{t}\in\mathcal{P}$, and $t\geq 0$,

  5. (e)

$\mathbb{P}_{x_{0}}^{\mu,\theta}(R_{t}\in\mathbf{R}\mid
h_{t},\theta_{t},u_{t})=\int_{\mathbf{R}}f^{\theta}(r\mid
x_{t},u_{t})d\lambda(r)$ for all $\mathbf{R}\in\mathcal{B}(\mathscr{R}_{c})$
given $h_{t}\in\mathcal{H}_{t}$, $\theta_{t}\in\mathcal{P}$,
$u_{t}\in\mathcal{U}(x_{t})$, and $t\geq 0$. When conditioned on $x_{t}$ and
$u_{t}$, $R_{t}$ is independent of $\theta_{t}$ and
$h_{t}\setminus\\{x_{t}\\}$.

  6. (f)

$\mathbb{P}_{x_{0}}^{\mu,\theta}(X_{t+1}\in\mathbf{X}\mid
h_{t},\theta_{t},u_{t},r_{t})=\int_{\mathbf{X}}q^{\theta}(y\mid
x_{t},u_{t})d\eta(y)$ for all $\mathbf{X}\in\mathcal{B}(\mathcal{X})$ given
$h_{t}\in\mathcal{H}_{t}$, $\theta_{t}\in\mathcal{P}$,
$u_{t}\in\mathcal{U}(x_{t})$, $r_{t}\in\mathscr{R}_{c}$, and $t\geq 0$. When
conditioned on $x_{t}$ and $u_{t}$, $X_{t+1}$ is independent of $\theta_{t}$,
$r_{t}$ and $h_{t}\setminus\\{x_{t}\\}$.

The probability measure $\mathbb{P}_{x_{0}}^{\mu,\theta}$ induced by the
policy $\mu$ satisfies all (a)-(f), where

  1. (a)

is by the definition of probability measure.

  2. (b)

is by construction, it implies the initial state of the process is $x_{0}$
with probability 1.

  3. (c)

shows the history-dependent posterior distribution, from which the sample
$\theta_{t}$ is generated.

  4. (d)

is the decision rule, i.e., the collection of policies. In each period $t$,
the DM selects controls not only by the current state $x_{t}$, but by the
entire history vector $h_{t}$. The decision rule also depends on the sample
$\theta_{t}$. Since $h_{t}$ ends with $x_{t}$, we add $\theta_{t}$ as a
condition.

  5. (e)

characterizes the random reward drawn from the distribution which knows the
noisy version of $\theta$. Given $x_{t}$ and $u_{t}$, the random reward
$R_{t}$, generated from density $f^{\theta}(\cdot\mid X_{t},U_{t})$, does not
depend on the sample $\theta_{t}$. Since $\theta_{t}$ does not give any
additional information, it can be dropped. If not conditioned on $x_{t}$ and
$u_{t}$, then $R_{t}$ depends on $h_{t}$, $\theta_{t}$, and $u_{t}$.

  6. (f)

is the state transition law. Set $\mathbf{X}$ represents the states that are
accessible from $x_{t}$. Given $x_{t}$ and $u_{t}$, the random next state
$X_{t+1}$, generated from density $q^{\theta}(\cdot\mid x_{t},u_{t})$, is
independent of $\theta_{t}$ and $r_{t}$. Since $\theta_{t}$ and $r_{t}$ are
superfluous, they can be dropped. If not conditioned on $x_{t}$ and $u_{t}$,
then $X_{t+1}$ depends on $h_{t}$, $\theta_{t}$, $u_{t}$ and $r_{t}$.

When the expectation is over one step instead of the entire process, we use a
different notations, i.e., different than $\mathbb{E}_{x_{0}}^{\mu,\theta}$.
If the expectation is taken with respect to the random reward, we denote it by
$E_{f^{\theta}}[\cdot\mid x,u]$, where density $f^{\theta}$ is with respect to
$\sigma$-finite measure $\lambda$. If the expectation is with respect to the
random next state, the operator is $E_{q^{\theta}}[\cdot\mid x,u]$, where
density $q^{\theta}$ is with respect to the $\sigma$-finite measure $\eta$. If
it is with respect to both the random reward and the random next state, then
we use $E_{f^{\theta}q^{\theta}}[\cdot\mid x,u]$. Whenever there is a $\cdot$
in these expectation operators, the $\cdot$ implies a random variable.

####  3.2.3 Objective Function (Performance Criteria).

Given the initial state $x_{0}$ and the discount factor $\beta\in(0,1)$, the
expected discounted reward over the infinite-horizon of implementing a policy
$\mu$ from period $t=0$ onward is

$V_{x_{0}}^{\mu,\theta}(0)\coloneqq\mathbb{E}_{x_{0}}^{\mu,\theta}\left[\sum_{t=0}^{\infty}\beta^{t}R_{t}\right],\quad\forall\mu\in\mathcal{M},\,x_{0}\in\mathcal{X}.$
(5)

When the rewards from period $0$ up until $n-1$ are dismissed and the
discounting starts from period $n$ onward, we have

$V_{x_{0}}^{\mu,\theta}(n)\coloneqq\mathbb{E}_{x_{0}}^{\mu,\theta}\left[\sum_{t=n}^{\infty}\beta^{t-n}R_{t}\right].$
(6)

As in (5), the DM implements policy $\mu$, starting from (known) state $x_{0}$
in period 0. However, the rewards in (6) are accumulated only from period
$t=n$ onward, when the (random) system state is $X_{n}$. We will use the
notation $n$ when we fix a specific time period and $t$ when we take
summations.

For a given policy, the DM should know the value of $\theta$ to compute (5)
and (6). Alternatively, the DM can statistically estimate these quantities if
they have access to the reward density and transition density of the oracle to
simulate the policy.

Recall from (3) that the optimal value function of the standard MDP problem is
$\nu^{\theta}(x)$, with optimal policy $\mu^{\theta}$. In the adaptive
setting, when the DM is assumed to know $\theta$, the optimal policy is
$\mu^{\theta}$. Hence, without loss of generality, we define
$\nu^{\theta}(x_{0})$ in (7) with respect to
$\mathbb{E}_{x_{0}}^{\mu,\theta}$, i.e.,

$\nu^{\theta}(x_{0})\coloneqq\sup_{\mu\in\mathcal{M}}V_{x_{0}}^{\mu,\theta}(0)=\sup_{\mu\in\mathcal{M}}\mathbb{E}_{x_{0}}^{\mu,\theta}\left[\sum_{t=0}^{\infty}\beta^{t}R_{t}\right]=\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}\left[\sum_{t=0}^{\infty}\beta^{t}R_{t}\right],\quad\forall
x_{0}\in\mathcal{X},$ (7)

where $\nu^{\theta}(x_{0})$ is equal to $\nu^{\theta}(x)$ in (3) when
$x=x_{0}$, $\forall x\in\mathcal{X}$.

The process starts from state $x_{0}$ in period 0. We call $\mu^{\theta}$ the
$\theta$-optimal policy. Under Assumption  ‣ 3.1, this policy is stationary,
deterministic, and Markovian.

##  4 Thompson Sampling

Given the formulation of the adaptive control problem, there is flexibility in
how the evolution of the stochastic process can be “customized”. The
specification arises two-fold: by the posterior update and the control
selection. Until now, we denoted a general admissible policy by
$\mu=\\{\mu_{t}\\}$ and the belief update rule by $\pi_{t}(\cdot\mid h_{t})$.
From here onward, we adopt a particular policy, Thompson sampling (TS). We
define the TS policy by specifying the decision rule $\mu$ and the function
$\pi_{t}(\cdot\mid h_{t})$ to update the belief vector. While the DM chooses
$\mu$, the system designer determines $\pi_{t}$. We use TS, TS algorithm, TS
decision rule, and TS policy interchangeably throughout the paper. Also, we
denote TS by $\tau$, which we will formally define later in this section. The
probability measure induced by TS and its corresponding expectation operator
are denoted by $\mathbb{P}_{x_{0}}^{\tau,\theta}$ and
$\mathbb{E}_{x_{0}}^{\tau,\theta}$, respectively.

###  4.1 Posterior Update

The TS algorithm generates an estimate $\theta_{t}$ in each period, by using
the “synthetic” belief update function $\pi_{t}(\theta_{t}\mid H_{t})$.
Initially, the DM holds the prior belief $\pi_{0}(\theta_{0}\mid h_{0})>0$ on
the true parameter $\theta$. That is, the unknown $\theta$ is modeled by the
$|\mathcal{P}|$-valued random variable $\Theta_{t}$, with initial prior
distribution

$\pi_{0}(\theta_{0}\mid
h_{0})\coloneqq\mathbb{P}_{x_{0}}^{\tau,\theta}(\Theta_{0}=\theta_{0}\mid
h_{0}),\quad\forall\theta_{0}\in\mathcal{P}.$

At the beginning of period $t$, the DM updates her belief over the parameter
candidates, by computing the (random) posterior distribution

$\displaystyle\pi_{t}(\theta_{t}\mid
H_{t})\coloneqq\mathbb{P}_{x_{0}}^{\tau,\theta}(\Theta_{t}=\theta_{t}\mid
H_{t}),\quad\forall\theta_{t}\in\mathcal{P}.$ (8)

The expected value of $\pi_{t}(\theta_{t}\mid H_{t})$,

$\displaystyle\pi_{t}(\theta_{t})\coloneqq\mathbb{E}_{x_{0}}^{\tau,\theta}[\pi_{t}(\theta_{t}\mid
H_{t})],$

is deterministic, and its dependence on $(x_{0},\tau,\theta)$ is implicit. We
employ Bayes’ Theorem to conduct the update,

$\pi_{t}(\theta_{t}\mid
H_{t})\coloneqq\frac{\mathcal{L}_{t}^{\theta_{t}}(H_{t})\pi_{0}(\theta_{0}\mid
h_{0})}{\sum\limits_{\gamma\in\mathcal{P}}\mathcal{L}_{t}^{\gamma}(H_{t})\pi_{0}(\gamma\mid
h_{0})},$ (9)

where $\mathcal{L}_{t}^{\gamma}(H_{t}):\mathcal{H}_{t}\to\mathbb{R}$ is the
(history-dependent) likelihood function. For any $\gamma\in\mathcal{P}$,

$\displaystyle\mathcal{L}_{t}^{\gamma}(H_{t})\coloneqq\prod_{s=1}^{t}f^{\gamma}(R_{s-1}\mid
X_{s-1},U_{s-1})q^{\gamma}(X_{s}\mid X_{s-1},U_{s-1}).$

The joint density $f^{\gamma}(\cdot\mid x,u)q^{\gamma}(\cdot\mid x,u)$
specifies a joint probability measure on $[0,1]\times\mathcal{X}$,

$\rho^{\gamma}_{x,u}(\mathbf{R},\mathbf{X})\coloneqq\int_{\mathbf{R}}f^{\gamma}(r\mid
x,u)d\lambda(r)\int_{\mathbf{X}}q^{\gamma}(y\mid x,u)d\eta(y),$

for
$\mathbf{R}\subseteq\mathcal{B}(\mathscr{R}_{c}),\,\mathbf{X}\subseteq\mathcal{B}(\mathcal{X})$.
Then, for any parameter value $\gamma\in\mathcal{P}$, the ratio of the Radon-
Nikodym derivative is

$\frac{d\rho^{\theta}_{x,u}}{d\rho^{\gamma}_{x,u}}=\frac{f^{\theta}(\cdot\mid
x,u)q^{\theta}(\cdot\mid x,u)}{f^{\gamma}(\cdot\mid x,u)q^{\gamma}(\cdot\mid
x,u)}.$

######  Definition.

The relative entropy of $\rho^{\theta}_{x,u}$ with respect to
$\rho^{\gamma}_{x,u}$ is

$\mathcal{K}(\rho^{\theta}_{x,u}\mid\rho^{\gamma}_{x,u})\coloneqq
E_{f^{\theta}q^{\theta}}\left[\log\left(\frac{d\rho^{\theta}_{x,u}}{d\rho^{\gamma}_{x,u}}\right)\right],$

given $\rho^{\theta}_{x,u}$ is absolutely continuous with respect to
$\rho^{\gamma}_{x,u}$.

Note that the expectation operator $E_{f^{\theta}q^{\theta}}[\cdot\mid x,u]$
was defined earlier in Section 3.2, such that we integrate over the random
reward and next state, for one step only. Next, we specify the decision rule
to characterize the TS policy.

###  4.2 Decision Rule

######  Definition.

The Thompson sampling policy $\tau=\\{\tau_{t}\\}$ is a sequence of stochastic
kernels $\tau_{t}$ on $\mathcal{U}$ given $h_{t}$ and $\theta_{t}$, satisfying

$\tau_{t}(\cdot\mid h_{t},\theta_{t})\coloneqq\mu^{\theta_{t}}(\cdot\mid
x_{t}).$

Under Assumption  ‣ 3.1, $\mu^{\theta_{t}}$ is a stationary, deterministic,
and Markovian policy. Since $\mu^{\theta_{t}}$ only depends on $x_{t}$, (by
definition) the $\tau$ policy depends on $x_{t}$, instead of $h_{t}$. In each
period $t$, the TS decision rule samples $\theta_{t}$ and employs
$\mu^{\theta_{t}}$, i.e., it picks the control that maximizes the expected
infinite-horizon discounted reward by treating $\theta_{t}$ as the true value
of the unknown parameter $\theta$. The TS decision rule is deterministic,
given $\theta_{t}$. However, until the (random and history-dependent) sample
$\Theta_{t}$ is drawn from the posterior distribution $\pi_{t}(\theta_{t}\mid
H_{t})$, it is a randomized decision rule.

Recall the evolution of the stochastic process from Section 3.2.1. Based on
the state-control pair, the DM observes a noisy reward generated by
$f^{\theta}(\cdot\mid x_{t},u_{t})$, and thus, cannot immediately identify the
true value $\theta$. Then, through the transition density
$q^{\theta}(\cdot\mid x_{t},u_{t})$, the current state transitions into the
next state. After observing the reward and the transition, the DM updates the
posterior on every $\gamma\in\mathcal{P}$ using (9). Afterwards, a new
parameter estimate $\theta_{t+1}$ is sampled from the updated distribution,
leading to the next control $u_{t+1}$.

We underline that the history vector includes the sample, i.e.,
$H_{t}\coloneqq(X_{0},\Theta_{0},U_{0},R_{0},\dots)$ contains the period-$t$
sample $\theta_{t}$, which renders the TS policy well defined on the
probability space
$(\Omega,\mathcal{B}(\Omega),\mathbb{P}_{x_{0}}^{\tau,\theta})$, defined in
Section 3.2.

######  Lemma 4.1 (Degenerate prior).

TS is equivalent to the $\theta$-optimal policy when the prior distribution is
degenerate, i.e., $\pi_{0}(\theta\mid h_{0})=1$.

We defer the proof of Lemma 4.1 to Appendix A.

##  5 Decomposition of Expected Regret

The objective of this section is to decompose the standard regret into
interpretable components and illustrate how the third component, i.e.,
residual regret, decays to 0 through a numerical example. Because we are in an
infinite-horizon setting, we can consider expected regret in any given fixed
period $n$ in the future, as assessed in period 0. In what follows, we
decompose this “expected regret process” into three different components, two
of which that cannot be changed from period $n$ onward and a third which can
be influenced. The first component is the traditional notion of expected
finite-horizon regret.

###  5.1 Standard Notion of Expected Regret

One would naturally quantify the expected regret of an admissible policy by
taking the difference between the optimal value function and the TS policy’s
value function. By the definitions in (5) and (7), this difference is equal to

$\displaystyle E[\textnormal{Regret}^{\theta}(0,\infty)]$
$\displaystyle\coloneqq\nu^{\theta}(x_{0})-V_{x_{0}}^{\tau,\theta}(0)$
$\displaystyle=\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}\left[\sum_{t=0}^{\infty}\beta^{t}R_{t}\right]-\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\sum_{t=0}^{\infty}\beta^{t}R_{t}\right],$
(10)

where $(0,\infty)$ represents the starting and ending periods, inclusive. The
expected infinite-horizon regret $E[\textnormal{Regret}^{\theta}(0,\infty)]$
is a function of two different expectation operators, so the expectation “$E$”
represents a label rather than a formal mathematical expression. We emphasize
that even though $R_{t}$ appears in both terms of (10), one of them is driven
by the process generated by $\mu^{\theta}$, while the other one is driven by
$\tau$.

By construction, $E[\textnormal{Regret}^{\theta}(0,\infty)]$ can be
partitioned into two components; a finite component that tallies rewards up
until some period $n-1$, and the remainder that goes into infinity, i.e.,

$E[\textnormal{Regret}^{\theta}(0,\infty)]\coloneqq
E[\textnormal{Regret}^{\theta}(0,n-1)]+E[\textnormal{Regret}^{\theta}(n,\infty)].$
(11)

When $\beta\in[0,1)$, the difference in (10) is the expected value of the
regret felt by the DM discounted back to period 0, i.e., in period-$0$
“dollars”. To express the regret of the $\theta$-MDP in period-$n$ dollars, we
multiply (10) with $\beta^{-n}$, to obtain

$\displaystyle
E[\textnormal{Regret}^{\theta}_{n}(0,\infty)]\coloneqq(\nu^{\theta}(x_{0})-V_{x_{0}}^{\tau,\theta}(0))\beta^{-n}$
(12)
$\displaystyle=\left[\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}\left[\sum_{t=0}^{\infty}\beta^{t}R_{t}\right]-\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\sum_{t=0}^{\infty}\beta^{t}R_{t}\right]\right]\beta^{-n}$
(13)
$\displaystyle=\left[\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}\left[\sum_{t=0}^{n-1}\beta^{t}R_{t}\right]-\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\sum_{t=0}^{n-1}\beta^{t}R_{t}\right]\right]\beta^{-n}$
(14)
$\displaystyle\qquad+\left[\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}\left[\sum_{t=n}^{\infty}\beta^{t}R_{t}\right]-\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\sum_{t=n}^{\infty}\beta^{t}R_{t}\right]\right]\beta^{-n}.$
(15)

The subscript $n$ in $E[\textnormal{Regret}^{\theta}_{n}(0,\infty)]$
corresponds to the period at which the money is evaluated. This shows that the
decomposition (11) also applies to the regret expressed in any period-$n$
dollars.

$E[\textnormal{Regret}_{n}^{\theta}(0,\infty)]\coloneqq
E[\textnormal{Regret}_{n}^{\theta}(0,n-1)]+E[\textnormal{Regret}_{n}^{\theta}(n,\infty)].$

When $\beta=1$, there is no difference between (10) and (13). We decompose
(13) into two components, namely (14) and (15). In particular, (14) represents
the expected finite-horizon regret, and by dividing it by $\beta^{n}$ we
convert it to period-$n$ dollars. We denote it by
$E[\textnormal{Regret}^{\theta}_{n}(0,n-1)]$. Recall that $\mu^{\theta}$ is an
optimal policy for the infinite-horizon discounted reward maximization
problem, with value $\nu^{\theta}(x_{0})$. When $\beta=1$,
$E[\textnormal{Regret}^{\theta}_{n}(0,n-1)]$ becomes the traditional expected
regret over a finite horizon. We observe from Example 2.1 that the non-
discounted version of $E[\textnormal{Regret}^{\theta}_{n}(0,n-1)]$ violates
the order of $\ln(n)$. The expected regret component (15) can be interpreted
as the expected infinite-horizon regret, starting in period $n$, in period-$n$
dollars. Distributing $\beta^{-n}$ inside, (15) can alternatively be written
as

$\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}\left[\sum_{t=n}^{\infty}\beta^{t-n}R_{t}\right]-\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\sum_{t=n}^{\infty}\beta^{t-n}R_{t}\right].$
(16)

By the first remark in Section 3.1, the infinite geometric series property,
and assuming $\beta\in[0,1)$, (16) is upper bounded by $\frac{2M}{1-\beta}$,
which is a constant independent of $n$. When $\beta=1$, (16) may grow to
infinity in $n$.

We revisit Example 2.1, which was introduced in Section 2.2. The value of the
$\tau$ policy $V_{x_{0}}^{\tau,\theta}(0)$ is equal to the probability that
the initial sample is equal to the true parameter $\theta$ times the infinite-
horizon reward of having the first guess right. In the case of sampling the
true parameter at $t=0$, the DM earns a reward of 1 in all periods, except for
the first period ($t=0$). In this case, the total discounted reward accrued
starting at $t=1$ is $\frac{1}{1-\beta}$. By the definition of
$V_{x_{0}}^{\tau,\theta}(0)$, we convert the total reward into period-$0$
dollars by multiplying $\frac{1}{1-\beta}$ with $\beta$. Therefore,

$V_{x_{0}}^{\tau,\theta}(0)=\pi_{0}(\theta\mid h_{0})\frac{\beta}{1-\beta}.$

The value of the $\theta$-optimal policy in period-$0$ dollars is

$\nu^{\theta}(x_{0})=\frac{\beta}{1-\beta}.$

Hence, by (13) the expected infinite-horizon regret of the $\tau$ policy is

$E[\textnormal{Regret}^{\theta}_{n}(0,\infty)]\coloneqq(\nu^{\theta}(x_{0})-V_{x_{0}}^{\tau,\theta}(0))\beta^{-n}=\left((1-\pi_{0}(\theta\mid
h_{0}))\frac{\beta}{1-\beta}\right)\beta^{-n}.$

We now inspect the limiting behavior of this metric (as $n\to\infty$). When
the discount factor $0\leq\beta<1$, we have

$\lim_{n\to\infty}E[\textnormal{Regret}^{\theta}_{n}(0,\infty)]=\lim_{n\to\infty}\left((1-\pi_{0}(\theta\mid
h_{0}))\frac{\beta}{1-\beta}\right)\beta^{-n}=\infty.$ (17)

The expected finite-horizon regret (14) of the $\tau$ policy is

$\displaystyle E[\textnormal{Regret}^{\theta}_{n}(0,n-1)]$
$\displaystyle\coloneqq\left(\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}\left[\sum_{t=0}^{n-1}\beta^{t}R_{t}\right]-\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\sum_{t=0}^{n-1}\beta^{t}R_{t}\right]\right)\beta^{-n}$
$\displaystyle=\left(\sum_{t=1}^{n-1}\beta^{t}-\pi_{0}(\theta\mid
h_{0})\sum_{t=1}^{n-1}\beta^{t}\right)\beta^{-n}$
$\displaystyle=\left(\sum_{t=1}^{n-1}\beta^{t}(1-\pi_{0}(\theta\mid
h_{0}))\right)\beta^{-n}$ (18)
$\displaystyle=\frac{\beta(1-\beta^{n-1})\beta^{-n}}{1-\beta}(1-\pi_{0}(\theta\mid
h_{0}))=\frac{\beta^{1-n}-1}{1-\beta}(1-\pi_{0}(\theta\mid h_{0})).$

Similar to (17), we inspect the limiting behavior of the expected finite-time
regret, which yields

$\displaystyle\lim_{n\to\infty}E[\textnormal{Regret}^{\theta}_{n}(0,n-1)]=\lim_{n\to\infty}\frac{\beta^{1-n}-1}{1-\beta}(1-\pi_{0}(\theta\mid
h_{0}))=\infty.$

When $\beta=1$ (18) is equal to $(n-1)(1-\pi_{0}(\theta\mid h_{0}))$, thus the
expected finite-time regret grows linearly, not logarithmically as in Agrawal
and Goyal (2012).

###  5.2 Components of Expected Regret

We now propose an alternative decomposition of
$E[\textnormal{Regret}^{\theta}_{n}(0,\infty)]$. By construction, the second
term in (16) is equal to the value function of the $\tau$ policy, i.e.,
$V_{x_{0}}^{\tau,\theta}(n)$. Moreover, the first term in (16) is equal to the
expectation of the optimal value function with respect to the $\theta$-optimal
policy, i.e.,

$\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}[\nu^{\theta}(X_{n})]\coloneqq\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}\left[\mathbb{E}_{X_{n}}^{\mu^{\theta},\theta}\left[\sum_{t=0}^{\infty}\beta^{t}R_{t}^{\prime}\right]\right]=\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}\left[\sum_{t=n}^{\infty}\beta^{t-n}R_{t}\right].$
(19)

In (19), $X_{n}$ is generated by running the $\mu^{\theta}$ policy starting in
period $t=0$ from state $x_{0}$. Conditional on the random “starting” state
$X_{n}$, $\\{R_{0}^{\prime},R_{1}^{\prime},\dots\\}$ is the random reward
process generated by the optimal policy $\mu^{\theta}$. When unconditioned on
$X_{n}$, $R_{t}^{\prime}\sim R_{t+n}$ given starting state $x_{0}$. Adding and
subtracting $\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]$, and
regrouping yields the following decomposition.

$\displaystyle E[\textnormal{Regret}^{\theta}_{n}(0,\infty)]$
$\displaystyle\coloneqq(\nu^{\theta}(x_{0})-V_{x_{0}}^{\tau,\theta}(0))\beta^{-n}$
$\displaystyle=E[\textnormal{Regret}_{n}^{\theta}(0,n-1)]$ (Expected finite-
time regret) (20)
$\displaystyle\qquad+\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}[\nu^{\theta}(X_{n})]-\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]$
(Expected state regret) (21)
$\displaystyle\qquad+\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]-V_{x_{0}}^{\tau,\theta}(n)$
$\displaystyle\textnormal{(Expected residual regret)}.$ (22)

Notice that (20) is the same quantity as (14). Next, we discuss (21) and (22).

####  5.2.1 Expected State Regret.

The expected state regret (21) captures the unavoidable future consequences of
landing in a suboptimal state after implementing TS for $n$ periods, which we
formally define below.

######  Definition.

The expected state regret,

$\mathcal{S}_{x_{0}}^{\tau,\theta}(n)\coloneqq\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}[\nu^{\theta}(X_{n})]-\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})],$

is the expected forward-looking regret under an optimal policy from period $n$
onward. It quantifies the difference between landing in a random state $X_{n}$
when the $\tau$ policy is started in period 0 versus a potentially different
random state $X_{n}$, had an optimal policy been followed instead from the
starting period.

Although it tallies the difference in rewards starting from period $n$ into
the infinite future, we only denote the starting period $n$ inside the
parenthesis.

$x_{0}$Sample path under policy $\mu^{\theta}$$x_{0}$Sample path under policy
$\tau$$X_{1}$$X_{1}$$X_{n}$$X_{n}$$\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}[\nu^{\theta}(X_{n})]$$\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]$Same
starting statePotentially differentPotentially differentOracle reveals
$\theta$Keep runningpolicy $\mu^{\theta}$After time $n$,adopt policy
$\mu^{\theta}$ Figure 3: Illustration of two different sample paths giving
rise to the expected state regret.

The random state $X_{n}$ in
$\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}[\nu^{\theta}(X_{n})]$ is induced by
running the $\mu^{\theta}$ policy for $n$ periods, whereas the random $X_{n}$
in $\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]$ arises under the
$\tau$ policy. Starting from the respective random states $X_{n}$, both sample
paths follow the $\theta$-optimal policy. Figure 3 illustrates two
representative sample paths. If there is no state process or if the state
process is iid, then these two terms would be equal. Since our problem
involves a nontrivial state process, the DM who implements the $\tau$ policy
may end up in a “bad” part of the state space, leading to an unavoidable,
positive penalty. Recall that $\nu^{\theta}(\cdot)$ is the optimal value
function of the DM who _knows_ the true $\theta$. After period $n$, the DM
cannot do any better than $\mu^{\theta}$.

$x_{0}$$x_{A}$$x_{B}$$A$$B$ $R^{A}(x_{A},1)=1$
---
$R^{B}(x_{A},1)=0$
1 $R^{A}(x_{A},2)=1$
---
$R^{B}(x_{A},2)=0.5$
2 $R^{B}(x_{B},2)=1$
---
$R^{A}(x_{B},2)=0.1$
2 $R^{B}(x_{B},1)=1$
---
$R^{A}(x_{B},1)=0$
1 Figure 4: Deterministic reward depending on the control, where true
parameter is B.

######  Example 5.1 (Absorption into an unfavorable set of states).

Consider Figure 4. Similar to Example 2.1, in period $n=0$, the DM can choose
either $A$ or $B$ with an immediate reward of 0. After being absorbed into one
of $x_{A}$ or $x_{B}$, the DM can pick either control 1 or 2 and receives a
deterministic reward, as a function of the control and true parameter. Suppose
the true parameter $\theta$ is $B$, which is unknown to the DM who performs
TS.

If $\pi(A\mid x_{0})\approx 1$, then the DM would initially sample $A$, and
consequently would stay in $x_{A}$ forever. The $\tau$ policy may then pick
control 1 (generating a reward of 0) or pick control 2 (generating a reward of
0.5). Recall that the system designer provides the transition and reward
densities, i.e., the reward structures $R^{A}(\cdot)$ and $R^{B}(\cdot)$ are
both known to the DM. Since the rewards are deterministic and have different
values, regardless of the control picked at $n=1$, the $\tau$ policy will
immediately learn that $\theta=B$. Hence, $\tau$ will always pick control 2
from $n=2$ onward, incurring a reward of 0.5. The $\theta$-optimal policy will
pick parameter $B$ in period $n=0$, receiving a reward of 1 forever. Then, by
(21), the undiscounted expected total regret of being in state $x_{A}$, as
opposed to $x_{B}$, increases linearly, by $1-0.5=0.5$ in each period. In
contrast, the final term (22) equals 0 when $n\geq 2$. Once landing in state
$x_{A}$, after 1 period both TS and an optimal policy will choose the same
control, i.e., control 2, forever. However, (22) does not always converge to 0
as rapidly. In the next section, we illustrate that when the rewards are not
deterministic, the $\tau$ policy learns more slowly.

####  5.2.2 Expected Residual Regret.

Now, we will formally introduce the third component of the expected infinite-
horizon expected regret, i.e., (22), and study its asymptotic behavior.

######  Definition.

The expected residual regret, i.e., $\mathcal{R}_{x_{0}}^{\tau,\theta}(n)$, is
the expected forward-looking regret from period $n$ onward into the infinite
future. This regret is between a policy which implements $\tau$ until it
switches to the optimal policy $\mu^{\theta}$ in period $n$ as opposed to
continuing with $\tau$. Formally,

$\mathcal{R}_{x_{0}}^{\tau,\theta}(n)\coloneqq\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]-V_{x_{0}}^{\tau,\theta}(n).$
(23)

Similar to the expected state regret, we only denote the starting period $n$
inside the parenthesis. Consider the first term of (23),

$\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]\coloneqq\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\sup_{\mu\in\mathcal{M}}V_{X_{n}}^{\mu,\theta}(0)\right]=\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\sup_{\mu\in\mathcal{M}}\mathbb{E}_{X_{n}}^{\mu,\theta}\left[\sum_{t=0}^{\infty}\beta^{t}R_{t}\right]\right].$

The $\theta$-optimal policy starts from a random state $X_{n}$, which is
driven by running the $\tau$ policy for $n$ periods, starting at $x_{0}$.
Recall Sections 3.2.2 and 4 for details. The expectation is taken over all
paths leading to all possible $X_{n}$. Hence,
$\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]$ is a deterministic
quantity. Consider the second term of (23), $V_{x_{0}}^{\tau,\theta}(n)$,
which is equal to (6) by substituting the $\tau$ policy,

$V_{x_{0}}^{\tau,\theta}(n)\coloneqq\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\sum_{t=n}^{\infty}\beta^{t-n}R_{t}\right].$

The expectation operator is induced by $\tau$, the starting state $x_{0}$ and
the true parameter $\theta$. Hence, similar to the first term,
$V_{x_{0}}^{\tau,\theta}(n)$ does not forget the past; periods $0$ to $(n-1)$
impact the state wherein the process finds itself in period $n$. Both
$\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]$ and
$V_{x_{0}}^{\tau,\theta}(n)$ discard the rewards generated during the first
$n$ periods; however, they are not independent of the past, since the random
state $X_{n}$ is driven by the tuple ($x_{0},\tau,\theta$). In summary, we
decompose the standard regret into three components, i.e.

$\displaystyle
E[\textnormal{Regret}^{\theta}(0,\infty)]=E[\textnormal{Regret}^{\theta}_{n}(0,n-1)]+\mathcal{S}_{x_{0}}^{\tau,\theta}(n)+\mathcal{R}_{x_{0}}^{\tau,\theta}(n).$
(24)

Notice that in (24) $\mathcal{S}_{x_{0}}^{\tau,\theta}(n)$ and
$\mathcal{R}_{x_{0}}^{\tau,\theta}(n)$ tally the difference in rewards
starting from $n$ into infinity, while
$E[\textnormal{Regret}^{\theta}(0,\infty)]$ and
$E[\textnormal{Regret}^{\theta}_{n}(0,n-1)]$ specify both the starting and
ending periods inside the parenthesis.
$E[\textnormal{Regret}^{\theta}_{n}(0,n-1)]$ is the accumulation of the past
losses, before period $n$. This component of the expected regret is sunk, in
the sense that the DM cannot change it starting from period $n$. Similarly,
the expected state regret $\mathcal{S}_{x_{0}}^{\tau,\theta}(n)$ is the
accumulation of the future losses, as a result of irrevocably being in a given
state in period $n$, thus is also sunk.
$E[\textnormal{Regret}^{\theta}_{n}(0,n-1)]$ and
$\mathcal{S}_{x_{0}}^{\tau,\theta}(n)$ measure the past and future
consequences, respectively, of adopting TS from period $0$ up until period
$n$. From the perspective of a DM who is already in period $n$, neither can be
influenced. In contrast, we regard the expected residual regret
$\mathcal{R}_{x_{0}}^{\tau,\theta}(n)$ as “controllable” because, starting in
period $n$, a DM can choose a policy other than TS from that period onward.
Therefore, amongst the three components, only expected residual regret
represents the efficacy of continuing with $\tau$ into the future.

Next, we illustrate how the expected residual regret quantifies the
effectiveness of future decisions through an example. If the DM picks the best
control(s) from period $n$ onward, no matter how unfavorable the state $X_{n}$
is, the expected residual regret starting in that period is 0.

####  5.2.3 Illustration of Expected Residual Regret.

To illustrate how learning occurs in a setting with stochastic rewards,
consider a single-state $\theta$-MDP example. We show how the expected
residual regret is driven down to 0 as a result of $\tau$ learning over time.

$x_{0}$ $R^{A}(x_{0},1)\sim N(0.5,0.1)$
---
$R^{B}(x_{0},1)\sim N(0.3,0.1)$
1 $R^{A}(x_{0},2)\sim N(0.4,0.1)$
---
$R^{B}(x_{0},2)\sim N(0.8,0.1)$
2 Figure 5: Stochastic rewards depending on the control, where the true
parameter is B.

######  Example 5.2 (Expected residual regret converges to 0).

Consider the single-state $\theta$-MDP in Figure 5. The underlying reward
structure is illustrated on the arcs, which represent the controls. The
rewards are stochastic. Based on the true parameter (which we assume is $B$)
and the control picked at every step, the reward is generated from a normal
distribution with known mean and variance. Not knowing the current state, the
DM draws a sample from the posterior distribution in each period and obtains
either $\Theta_{t}=A$ or $\Theta_{t}=B$. The initial prior belief on $A$ is
0.5. In each step of the process, if the sample drawn is $A$, then the DM
picks control 1. This is because control 1 has an expected reward of 0.5 when
sampling $A$, while control 2 has an expected reward of 0.4. On the other
hand, if the DM samples $B$, then they pick control 2 since the corresponding
expected reward is higher.

Figure 6(a) illustrates the evolution of the expected belief on the “wrong”
parameter $\mathbb{E}_{x_{0}}^{\tau,B}[\pi_{n}(A)]$, i.e., the expected
posterior sampling error, averaged over 100 runs of TS policy. We observe that
the DM learns the true parameter $B$ not immediately, but after approximately
40 iterations. Beyond that point, the DM always picks control 2, in order to
maximize the infinite-horizon expected total reward. Figure 6(b) illustrates
the decline in the expected residual regret for the same example.

Consider a hybrid policy that switches from $\tau$ to $\mu^{B}$ after running
$\tau$ for $n$ periods. Since the true parameter is $B$, the reward
distributions follow $N(0.3,0.1)$ and $N(0.8,0.1)$ when control 1 or 2 is
selected, respectively, i.e., the realizations of $R^{B}(x_{0},1)$ and
$R^{B}(x_{0},2)$ are the rewards associated with control 1 and 2,
respectively. Therefore, the expected reward of control 2 is greater than the
expected reward of control 1 and the $\mu^{B}$ policy always picks control 2,
i.e.,

$\int rf^{B}(x_{0},2)\,dr=0.8>\int rf^{B}(x_{0},1)\,dr=0.3.$

From period $n$ onward, a hybrid policy gains total expected reward of

$\displaystyle\mathbb{E}_{x_{0}}^{\tau,B}[\nu^{B}(X_{n})]$
$\displaystyle=\mathbb{E}_{x_{0}}^{\tau,B}\left[\mathbb{E}_{X_{n}}^{\mu^{B},B}\left[\sum_{t=0}^{\infty}\beta^{t}R_{t}\right]\right]$
$\displaystyle=\sum_{t=0}^{\infty}\beta^{t}0.8=\frac{0.8}{1-\beta}=\nu^{B}(x_{0}).$

We emphasize that $n$ corresponds to a fixed time period, while $t$ is used
when summing over the rewards. Consider the $\mu_{1}$ policy that always picks
control 1. Had the DM implemented such a policy, the expected residual regret
would have been

$\displaystyle\mathcal{R}_{x_{0}}^{\mu_{1},B}(n)$
$\displaystyle\coloneqq\mathbb{E}_{x_{0}}^{\mu_{1},B}[\nu^{B}(X_{n})]-V_{x_{0}}^{\mu_{1},B}(n)$
$\displaystyle=\frac{0.8}{1-\beta}-\mathbb{E}_{x_{0}}^{\mu_{1},B}\left[\sum_{t=n}^{\infty}\beta^{t-n}R_{t}\right]$
$\displaystyle=\sum_{t=0}^{\infty}\beta^{t}0.8-\sum_{t=n}^{\infty}\beta^{t-n}0.3=\sum_{t=0}^{\infty}\beta^{t}0.5=\frac{0.5}{1-\beta}.$

Thus, $\frac{0.5}{1-\beta}$ is an upper bound on the expected residual regret
for all $n$. After some number of periods, the rate at which the policy $\tau$
picks control 1 becomes negligible. Once the policy no longer picks control 1,
the DM has figured out the true parameter is $B$. If we call this period
$\tilde{n}$, the expected residual regret becomes

$\mathcal{R}_{x_{0}}^{\tau,B}(n)\coloneqq\mathbb{E}_{x_{0}}^{\tau,B}[\nu^{B}(X_{n})]-V_{x_{0}}^{\tau,B}(n)=\sum_{t=0}^{\infty}\beta^{t}0.8-\sum_{t=n}^{\infty}\beta^{t-n}0.8=0,\quad\forall
n\geq\tilde{n}.$

Starting from $n=0$ and using Example 5.2 assumptions, the expected residual
regret can be computed as

$\mathcal{R}_{x_{0}}^{\tau,B}(n)=\sum_{t=0}^{\infty}\beta^{t}0.8-\left(\mathbb{E}_{x_{0}}^{\tau,B}[\pi_{n}(A)]\frac{0.3}{1-\beta}+\mathbb{E}_{x_{0}}^{\tau,B}[\pi_{n}(B)]\frac{0.8}{1-\beta}\right).$

Figure 6(b) shows the evolution of $\mathcal{R}_{x_{0}}^{\tau,B}$ for
$\beta=0.9$. When a different $\beta\in[0,1)$ is chosen, the trajectory
remains the same, but the expected residual regret values are different for
small $n$.

$0$$20$$40$$60$$80$$100$$0$$0.2$$0.4$$n$$\mathbb{E}_{x_{0}}^{\tau,B}[\pi_{n}(A)]$
(a) Evolution of expected posterior sampling error

$0$$20$$40$$60$$80$$100$$0$$1$$2$$n$$\mathcal{R}_{x_{0}}^{\tau,B}(n)$ (b)
Evolution of expected residual regret

Figure 6: Evolution of expected posterior and expected residual regret in
Example 5.2 when first sample is wrong

##  6 Analysis of Expected Residual Regret for Thompson Sampling

The goal of this section is to show that the expected residual regret of TS
vanishes (i.e., converges to 0) in an exponential rate. To do so, we first
relate the concept of ADO (Hernández-Lerma 2012) to the expected residual
regret, showing that they are equivalent in our setting. This allows us to
combine the machinery of Hernández-Lerma (2012) with Kim (2017) to obtain our
result.

###  6.1 ADO and Expected Residual Regret

To study adaptive control problems in the discounted case, Schäl (1987)
introduced an asymptotic definition of optimality, asymptotic discount
optimality. Hernández-Lerma (2012) describes the idea behind it as “to allow
the system to run during a learning period of $n$ stages” and defines an
asymptotically discount optimal (ADO) policy as follows:

######  Definition (ADO).

A policy $\mu$ is called _asymptotically discount optimal_ (ADO) if,

$\displaystyle\left|V_{x_{0}}^{\mu,\theta}(n)-\mathbb{E}_{x_{0}}^{\mu,\theta}[\nu^{\theta}(X_{n})]\right|\to
0\textnormal{ as }n\to\infty,\quad\forall x_{0}\in\mathcal{X},$

where $\nu^{\theta}(X_{n})$ is defined by (7) and $V_{x_{0}}^{\mu,\theta}(n)$
by (6).

We label an ADO policy as $\theta$-ADO to emphasize the dependence on the
underlying parameter $\theta$. Traditionally, expected regret is formulated
without the absolute value (Lai and Robbins 1985). It follows that the
expected residual regret is equivalent to the $\theta$-ADO expression, i.e.,

$\displaystyle\mathcal{R}^{\tau,\theta}_{x_{0}}(n)\coloneqq\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]-V_{x_{0}}^{\tau,\theta}(n)=|V_{x_{0}}^{\tau,\theta}(n)-\mathbb{E}_{x_{0}}^{\mu,\theta}[\nu^{\theta}(X_{n})]|.$
(25)

Showing (25) will be instrumental in bounding the expected residual regret.

######  Lemma 6.1.

The absolute value in the $\theta$-ADO expression can be omitted in our
setting, i.e.,

$|V_{x_{0}}^{\tau,\theta}(n)-\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]|=\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]-V_{x_{0}}^{\tau,\theta}(n).$

The statement in Lemma 6.1 is self-evidently true, but because the notation is
cumbersome in this setting, we defer the proof to Appendix A.

Rather than calling policies $\theta$-ADO, we say that they have “vanishing
expected residual regret”.

######  Definition.

A policy $\mu$ has vanishing expected residual regret if,

$\lim_{n\to\infty}\mathcal{R}^{\mu,\theta}_{x_{0}}(n)\coloneqq\lim_{n\to\infty}\left[\mathbb{E}_{x_{0}}^{\mu,\theta}[\nu^{\theta}(X_{n})]-V_{x_{0}}^{\mu,\theta}(n)\right]=0,\quad\forall
x_{0}\in\mathcal{X},$

where $\theta$ is the true parameter and $X_{n}$ is the random period-$n$
state, which is obtained by running an admissible policy $\mu$ for $n$
periods.

If TS has vanishing expected residual regret, then eventually its expected
performance converges to that of an optimal policy.

###  6.2 Temporal Difference Error

To bound the expected residual regret, we first establish a connection to the
temporal-difference error function (Sutton and Barto 2018). This will later
allow us to provide a bound for the former by bounding the latter. This
function, which is parametrized by $\theta$, quantifies the discrepancy
between the reward-to-go of choosing the optimal control instead of an
arbitrary control in a given state.

######  Definition (Hernández-Lerma, 2012).

We denote the temporal-difference error function by
$\phi^{\theta}:\mathbb{K}\to\mathbb{R}$, where

$\phi^{\theta}(x,u)\coloneqq
r^{\theta}(x,u)+\beta\int\nu^{\theta}(y)Q^{\theta}(dy\mid
x,u)-\nu^{\theta}(x).$

The first two terms of $\phi^{\theta}(x,u)$ constitute the reward-to-go of
choosing (an arbitrary) control $u\in\mathcal{U}(x)$ in state $x$, while
$\nu^{\theta}(x)$ is the reward-to-go of choosing the optimal control in $x$.

######  Lemma 6.2 (Temporal-difference error).

For every initial state $x_{0}\in\mathcal{X}$, a policy $\mu$ has vanishing
expected residual regret, i.e.,

$\lim_{n\to\infty}\left[\mathbb{E}_{x_{0}}^{\mu,\theta}[\nu^{\theta}(X_{n})]-V_{x_{0}}^{\mu,\theta}(n)\right]=0,\quad\forall
x_{0}\in\mathcal{X},$

if and only if $\phi^{\theta}(X_{t},U_{t})\to 0$ in
probability-$\mathbb{P}_{x_{0}}^{\mu,\theta}$ for every $x_{0}\in\mathcal{X}$.

We defer the proof of Lemma 6.2 to Appendix A, which has been adapted from
Hernández-Lerma (2012) to our setting. The proof establishes a connection
between the expected residual regret and the expected value of
$\phi^{\theta}$. In particular, for a policy $\mu$,

$\mathcal{R}^{\mu,\theta}_{x_{0}}(n)=-\sum_{t=n}^{\infty}\beta^{t-n}\mathbb{E}_{x_{0}}^{\mu,\theta}\phi^{\theta}(X_{t},U_{t}).$
(26)

###  6.3 Expected Residual Regret Bounds

In this section, we provide convergence results for TS. We will bound the
expected residual regret by bounding
$\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})\mid\theta_{t}\neq\theta]$
and $\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})]$,
respectively. The DM draws a sample in each period $t$, represented by the
random variable $\Theta_{t}$. Recall from Section 4.1, given the true
parameter $\theta\in\mathcal{P}$,

$\pi_{t}(\theta\mid
H_{t})=\mathbb{P}^{\tau,\theta}_{x_{0}}(\Theta_{t}=\theta\mid H_{t})$ (27)

is the probability that the sample $\Theta_{t}$ is equal to $\theta$,
conditional on $H_{t}$. Since the condition is not a known $h_{t}$, (27) is
also a random variable. Similarly,

$1-\pi_{t}(\theta\mid
H_{t})=\mathbb{P}_{x_{0}}^{\tau,\theta}(\Theta_{t}\neq\theta\mid H_{t})$ (28)

is the (random) probability that the sample $\Theta_{t}$ is _not_ equal to
$\theta$, given (random) $H_{t}$. Taking the expectation of both sides of
(28),

$\mathbb{E}_{x_{0}}^{\tau,\theta}[1-\pi_{t}(\theta\mid
H_{t})]=\mathbb{E}_{x_{0}}^{\tau,\theta}[\mathbb{P}_{x_{0}}^{\tau,\theta}(\Theta_{t}\neq\theta\mid
H_{t})],$ (29)

resolves the uncertainty of $H_{t}$. By the law of iterated expectations, (29)
simplifies into

$\displaystyle
1-\pi_{t}(\theta)=\mathbb{P}_{x_{0}}^{\tau,\theta}(\Theta_{t}\neq\theta),$
(30)

i.e., the posterior probability that the sample is _not_ equal to the true
parameter $\theta$. Then, by the law of total expectation, we partition the
expectation of $\phi^{\theta}$, i.e.,

$\displaystyle\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})]=\mathbb{P}_{x_{0}}^{\tau,\theta}(\Theta_{t}\neq\theta)$
$\displaystyle\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})\mid\Theta_{t}\neq\theta]$
$\displaystyle+\mathbb{P}_{x_{0}}^{\tau,\theta}(\Theta_{t}=\theta)$
$\displaystyle\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})\mid\Theta_{t}=\theta],$

where $U_{t}$ is the control that maximizes the reward-to-go by treating the
sampled estimate $\Theta_{t}$ as the true value of the unknown parameter
$\theta$. We can simply rewrite the probability terms to obtain,

$\displaystyle\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})]=(1-\pi_{t}(\theta))$
$\displaystyle\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})\mid\Theta_{t}\neq\theta]$
$\displaystyle+\pi_{t}(\theta)$
$\displaystyle\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})\mid\Theta_{t}=\theta].$

But then, when $\Theta_{t}=\theta$, by the decision rule $\tau_{t}(U_{t}\mid
h_{t},\theta)$, the optimal control (of state $x_{t}$) is taken, and the
temporal difference error $\phi^{\theta}(X_{t},U_{t})$ becomes 0, by
definition. Hence, when $\Theta_{t}=\theta$,

$\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})]=(1-\pi_{t}(\theta))\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})\mid\Theta_{t}\neq\theta].$
(31)

Note that, although we express the $\tau$ policy as a sequence of stochastic
kernels, it is a deterministic policy by Assumption  ‣ 3.1, when conditioned
on $\theta_{t}$. Before presenting the main result of this section, we first
bound the expectation of $\phi^{\theta}(X_{t},U_{t})$ in Lemma 6.3, then
extend a result from Kim (2017) into our setting by Lemma 6.4.

######  Lemma 6.3 (Lower bound on expected $\phi^{\theta}$).

The expected value of $\phi^{\theta}(X_{t},U_{t})$, conditional on
$\Theta_{t}\neq\theta$, is lower bounded by a non-positive constant, i..e,

$\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})\mid\Theta_{t}\neq\theta]\geq-2M\left(\frac{1+\beta}{1-\beta}\right),$
(32)

where $M\geq 0$ is the upper bound on the absolute value of the expected
reward, per Remark Remark.

###### Proof of Lemma 6.3.

In this proof, we slightly modify the $U_{t}$ notation to indicate its
dependence on the sample. Let $U_{t}^{\Theta_{t}}$ denote the control picked
when sample $\Theta_{t}$ is drawn from $\mathcal{P}$, and let $U_{t}^{\theta}$
represent the control picked when knowing $\theta$. Otherwise, we cannot
distinguish the $U_{t}$ controls.

$\displaystyle\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t}^{\Theta_{t}})\mid\Theta_{t}\neq\theta]=$
$\displaystyle\mathbb{E}_{x_{0}}^{\tau,\theta}[R_{t}(X_{t},U_{t}^{\Theta_{t}})+\beta\int\nu^{\theta}(x_{t+1})q^{\theta}(dx_{t+1}\mid
X_{t},U_{t}^{\Theta_{t}})\,d\eta\mid\Theta_{t}\neq\theta]$
$\displaystyle\qquad-\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{t})\mid\Theta_{t}\neq\theta],$

which is equal to

$\displaystyle\mathbb{E}_{x_{0}}^{\tau,\theta}\left[R_{t}(X_{t},U_{t}^{\Theta_{t}})+\beta\int\nu^{\theta}(x_{t+1})q^{\theta}(dx_{t+1}\mid
X_{t},U_{t}^{\Theta_{t}})\,d\eta\mid\Theta_{t}\neq\theta\right]$
$\displaystyle\qquad-\mathbb{E}_{x_{0}}^{\tau,\theta}\left[R_{t}(X_{t},U_{t}^{\theta})+\beta\int\nu^{\theta}(x_{t+1})q^{\theta}(dx_{t+1}\mid
X_{t},U_{t}^{\theta})\,d\eta\mid\Theta_{t}\neq\theta\right].$

We can rearrange the above expression to obtain

$\displaystyle\,\mathbb{E}_{x_{0}}^{\tau,\theta}[R_{t}(X_{t},U_{t}^{\Theta_{t}})\mid\Theta_{t}\neq\theta]-\mathbb{E}_{x_{0}}^{\tau,\theta}[R_{t}(X_{t},U_{t}^{\theta})\mid\Theta_{t}\neq\theta]$
(33)
$\displaystyle\qquad+\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\beta\int\nu^{\theta}(x_{t+1})q^{\theta}(dx_{t+1}\mid
X_{t},U_{t}^{\Theta_{t}})\,d\eta\mid\Theta_{t}\neq\theta\right]$ (34)
$\displaystyle\qquad-\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\beta\int\nu^{\theta}(x_{t+1})q^{\theta}(dx_{t+1}\mid
X_{t},U_{t}^{\theta})\,d\eta\mid\Theta_{t}\neq\theta\right].$ (35)

Then, we introduce the function
$g^{\theta}:\mathcal{X}\times\mathcal{P}\to\mathbb{R}_{+}$

$g^{\theta}(x,\theta)\coloneqq\int\nu^{\theta}(y)q^{\theta}(dy\mid
x,U_{t}^{\theta})\,d\eta,$ (36)

such that (34) is

$\beta\mathbb{E}_{x_{0}}^{\tau,\theta}[g^{\theta}(X_{t},\Theta_{t})\mid\Theta_{t}\neq\theta]$

and (35) is

$-\beta\mathbb{E}_{x_{0}}^{\tau,\theta}[g^{\theta}(X_{t},\theta)\mid\Theta_{t}\neq\theta].$

By Remark Remark and the infinite series property, we have

$\left|\nu^{\theta}(x)\right|\leq\frac{M}{1-\beta},\quad\forall
x\in\mathcal{X}.$

By (36),

$\left|g^{\theta}(x,\theta)\right|\leq\frac{M}{1-\beta}\int q^{\theta}(dy\mid
x,U_{t}^{\theta})\,d\eta\leq\frac{M}{1-\beta}.$

Taking the conditional expectation yields the same upper and lower bounds,
i.e.,

$\left|\mathbb{E}_{x_{0}}^{\tau,\theta}[g^{\theta}(x,\theta)\mid\Theta_{t}\neq\theta]\right|\leq\frac{M}{1-\beta}.$

We lower bound (34)

$\beta\mathbb{E}_{x_{0}}^{\tau,\theta}[g^{\theta}(X_{t},\Theta_{t})\mid\Theta_{t}\neq\theta]\geq\frac{-\beta
M}{1-\beta},$

and upper bound (35)

$\beta\mathbb{E}_{x_{0}}^{\tau,\theta}[g^{\theta}(X_{t},\theta)\mid\Theta_{t}\neq\theta]\leq\frac{\beta
M}{1-\beta},$

to get a lower bound on their difference,

$\beta\mathbb{E}_{x_{0}}^{\tau,\theta}[g^{\theta}(X_{t},\Theta_{t})\mid\Theta_{t}\neq\theta]-\beta\mathbb{E}_{x_{0}}^{\tau,\theta}[g^{\theta}(X_{t},\theta)\mid\Theta_{t}\neq\theta]\geq\frac{-2\beta
M}{1-\beta}.$

The difference between the first two reward terms, i.e., (33), can be no
smaller than $-2M$, thus

$\displaystyle\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t}^{\Theta_{t}})\mid\Theta_{t}\neq\theta]\geq-2M+\frac{2\beta
M}{1-\beta}=-2M\left(\frac{1+\beta}{1-\beta}\right).$

∎

Lemma 4 of Kim (2017) bounds the expected probability that $\theta$ is not
selected in period $t$. We will now extend this result to the discounted
infinite-horizon framework. However, for us to be able to generalize the
finite-dimensional state and control spaces that Kim (2017) deals with into
Borel (possibly infinite) spaces, we need to make the following assumption.

######  Assumption 1.

We assume

$\displaystyle\inf\limits_{x\in\mathcal{X},u\in\mathcal{U},r\in\mathscr{R}_{c}}f^{\gamma}(r\mid
x,u)>0,\quad\forall\gamma\in\mathcal{P}$ (37)

and

$\displaystyle\inf_{x\in\mathcal{X},u\in\mathcal{U},y\in\mathcal{X}}q^{\gamma}(y\mid
x,u)>0,\quad\forall\gamma\in\mathcal{P}.$ (38)

For any $x\in\mathcal{X}$, $u\in\mathcal{U}$, and any distinct parameter
value, $\gamma\neq\theta\in\mathcal{P}$, there exists a positive constant
$\epsilon(x,u,\theta,\gamma)>0$ such that

$\displaystyle\inf_{x\in\mathcal{X},u\in\mathcal{U}}\mathcal{K}(\rho_{x,u}^{\theta}\mid\rho_{x,u}^{\gamma})>\epsilon(x,u,\theta,\gamma).$
(39)

We underline that under finite state and control spaces, Assumption 1
simplifies into the prerequisites of Kim (2017). As Kim (2017) explains, (39)
in Assumption 1 ensures that given $\theta\neq\gamma$, the probability
measures $\rho^{\theta}_{x,u}$ and $\rho^{\gamma}_{x,u}$ are distinguishable
as measured by the relative entropy. In Appendix B we illustrate the
implications of Assumption 1 through Example 5.2. Example 2.1 violates this
assumption.

We further emphasize that Assumption 1 implies that the exploration is
passive; that is, the DM learns everything about the environment regardless of
their actions. We acknowledge that, in contrast to active exploration, passive
exploration is less efficient. Yet, without making additional assumptions on
the underlying Markov structure, i.e., making the paper less general, it does
not appear that we can extend the result in Kim (2017) to this broader
framework.

The following lemma extends a result from Kim (2017) to our setting.

######  Lemma 6.4 (Extension of Lemma 4 of Kim (2017)).

Under Assumption 1, Lemma 4 of Kim (2017) extends to our setting. That is to
say, implementing TS and starting from any $x_{0}\in\mathcal{X}$, there exists
constants $a_{\theta}$, $b_{\theta}>0$ such that

$\displaystyle\mathbb{E}_{x_{0}}^{\tau,\theta}\left[1-\pi_{t}(\theta\mid
H_{t})\right]\leq a_{\theta}e^{-b_{\theta}t},$ (40)

where $a_{\theta}$ and $b_{\theta}$ are defined as in Kim (2017).

Because Lemma 6.4 is an adaptation of Lemma 4 of Kim (2017) into our setting,
we defer it to the Appendix. By the law of iterated expectations, (40)
simplifies into

$1-\pi_{t}(\theta)\leq a_{\theta}e^{-b_{\theta}t}.$ (41)

We are now ready to introduce the main result of this section.

######  Proposition 6.5 (Upper bound on
$\mathcal{R}_{x_{0}}^{\tau,\theta}(n)$).

When Assumption 1 holds, the expected residual regret converges to 0
exponentially fast.

$\mathcal{R}_{x_{0}}^{\tau,\theta}(n)\coloneqq\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]-V_{x_{0}}^{\tau,\theta}(n)\,\,\leq\,\,\frac{2M(1+\beta)a_{\theta}e^{-b_{\theta}n}}{(1-\beta)^{2}},$

where $a_{\theta}$ and $b_{\theta}$ are positive constants, defined in Lemma 4
of Kim (2017).

###### Proof of Proposition 6.5.

Equations (31), (32) and (41) together yield

$-\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})]\leq\frac{2M(1+\beta)a_{\theta}e^{-b_{\theta}t}}{1-\beta}.$
(42)

By the proof of Lemma 6.2, $\phi^{\theta}(X_{t},U_{t})$ and
$\mathcal{R}_{x_{0}}^{\tau,\theta}(n)$ are related, see (26). Then, by (42),
the right-hand side of (26) is upper bounded,

$-\sum_{t=n}^{\infty}\beta^{t-n}\mathbb{E}_{x}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})]\leq\sum_{t=n}^{\infty}\beta^{t-n}\frac{2M(1+\beta)a_{\theta}e^{-b_{\theta}t}}{1-\beta}.$

Since $b_{\theta}\geq 0$, we have $e^{-b_{\theta}t}\leq e^{-b_{\theta}n}$ for
all $t\geq n$. Thus, the above equation becomes

$-\sum_{t=n}^{\infty}\beta^{t-n}\mathbb{E}_{x}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})]\leq\sum_{t=n}^{\infty}\beta^{t-n}\frac{2M(1+\beta)a_{\theta}e^{-b_{\theta}n}}{1-\beta}.$
(43)

By (26) and applying the infinite geometric series formula to (43), we obtain

$\displaystyle-\sum_{t=n}^{\infty}\beta^{t-n}\mathbb{E}_{x_{0}}^{\tau,\theta}[\phi^{\theta}(X_{t},U_{t})]$
$\displaystyle=\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]-V_{x_{0}}^{\tau,\theta}(n)$
$\displaystyle=\mathcal{R}_{x_{0}}^{\tau,\theta}(n)\leq\frac{2M(1+\beta)a_{\theta}e^{-b_{\theta}n}}{(1-\beta)^{2}},$

thus showing that the upper bound on the expected residual regret decays
exponentially. ∎

##  7 Complete Learning and Probabilistic Residual Regret

The goal of this section is to define a probabilistic version of the expected
residual regret (the expected value of the probabilistic version is the
expected residual regret itself, i.e., $\mathcal{R}_{x_{0}}^{\tau,\theta}(n)$,
and show the conditions under which it converges
$\mathbb{P}_{x_{0}}^{\tau,\theta}$-almost surely to 0 in this framework. We
show that the posterior distribution of TS converges
$\mathbb{P}_{x_{0}}^{\tau,\theta}$-almost surely to a point mass at $\theta$.
This behavior is called _complete learning_.

###  7.1 Complete Learning

Kim (2017) has shown that the expected posterior sampling error of TS
converges to 0 exponentially fast (see Lemma 6.4). Our result builds on this
result by using the Dominated Convergence Theorem. Formally,

######  Assumption 2 (Existence of the limit of $\pi_{t}(\theta\mid H_{t})$).

Suppose that $\lim\limits_{t\to\infty}\pi_{t}(\theta\mid H_{t})$ exists
$\mathbb{P}_{x_{0}}^{\tau,\theta}$-a.s.

By imposing this assumption, we avoid the nonexistence of the limit due to
oscillation. Under Assumption 1, the expected posterior sampling error of TS
vanishes. We will show that this, i.e.,
$\lim\limits_{t\to\infty}\mathbb{E}_{x_{0}}^{\tau,\theta}[\pi_{t}(\theta\mid
H_{t})]=1$, and Assumption 2 together imply

$\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})=1,\quad\mathbb{P}_{x_{0}}^{\tau,\theta}\textnormal{-almost surely}.$

The next lemma is the final piece to show the occurrence of complete learning.

######  Lemma 7.1.

Suppose that TS does not exhibit complete learning, i.e.,
$\lim\limits_{t\to\infty}\pi_{t}(\theta\mid H_{t})<1$,
$\mathbb{P}_{x_{0}}^{\tau,\theta}$-a.s. Then, there exists an $n\geq 1$ s.t.

$\mathbb{P}_{x_{0}}^{\tau,\theta}\left(\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})<1-\frac{1}{n}\right)>0,\quad\mathbb{P}_{x_{0}}^{\tau,\theta}\textnormal{-almost
surely.}$

The proof of Lemma 7.1 is in Appendix A.

######  Theorem 1 (TS learns $\theta$ as $t\to\infty$).

Suppose that Assumptions 1 and 2 hold. Then,

$\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})=1,\quad\mathbb{P}_{x_{0}}^{\tau,\theta}\textnormal{-almost surely.}$

###### Proof of Theorem 1.

By Lemma 6.4, Assumption 2, and the Dominated Convergence Theorem, it follows
that

$1=\lim_{t\to\infty}\mathbb{E}_{x_{0}}^{\tau,\theta}[\pi_{t}(\theta\mid
H_{t})]=\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})\right],\quad\mathbb{P}_{x_{0}}^{\tau,\theta}\textnormal{-a.s.}$

Then,

$\displaystyle 1$
$\displaystyle=\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})\right]$
$\displaystyle=\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})\Big{|}\left\\{\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})<1-\frac{1}{n}\right\\}\right]\mathbb{P}_{x_{0}}^{\tau,\theta}\left(\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})<1-\frac{1}{n}\right)$
$\displaystyle\qquad+\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})\Big{|}\left\\{\lim_{t\to\infty}\pi_{t}(\theta\mid H_{t})\geq
1-\frac{1}{n}\right\\}\right]\mathbb{P}_{x_{0}}^{\tau,\theta}\left(\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})\geq 1-\frac{1}{n}\right)$
$\displaystyle\leq(1-1/n)\mathbb{P}_{x_{0}}^{\tau,\theta}\left(\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})<1-\frac{1}{n}\right)+1-\mathbb{P}_{x_{0}}^{\tau,\theta}\left(\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})<1-\frac{1}{n}\right)$
$\displaystyle=1-\frac{1}{n}\mathbb{P}_{x_{0}}^{\tau,\theta}\left(\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})<1-\frac{1}{n}\right),\quad\mathbb{P}_{x_{0}}^{\tau,\theta}\textnormal{-a.s.}$

However, by Lemma 7.1, $\lim\limits_{t\to\infty}\pi_{t}(\theta\mid H_{t})<1$
implies

$\displaystyle 1$
$\displaystyle=\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})\right]$ $\displaystyle\leq
1-\frac{1}{n}\mathbb{P}_{x_{0}}^{\tau,\theta}\left(\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})<1-\frac{1}{n}\right)<1,\quad\mathbb{P}_{x_{0}}^{\tau,\theta}\textnormal{-almost
surely,}$

leading to contradiction. For all $n\geq 1$, it must be that

$\mathbb{P}_{x_{0}}^{\tau,\theta}\left(\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})<1-\frac{1}{n}\right)=0,\quad\mathbb{P}_{x_{0}}^{\tau,\theta}\textnormal{-almost
surely.}$

Thus, we must have $\lim\limits_{t\to\infty}\pi_{t}(\theta\mid H_{t})=1$,
$\mathbb{P}_{x_{0}}^{\tau,\theta}$-almost surely. This completes the proof. ∎

###  7.2 Vanishing Probabilistic Residual Regret

We define the residual regret as the “probabilistic” version of the expected
residual regret, which was defined in Section 5.2.2. In the remainder of this
section, we use the terms probabilistic residual regret and residual regret
interchangeably. The residual regret almost mimics the definition in (23);
however, it is a random expectation, and is obtained by conditioning on the
random history $H_{n}$, generated by running TS from period 0 to $n$.

######  Definition.

The residual regret $\mathbb{R}_{x_{0}}^{\tau,\theta}(n)$ is a random
expectation that represents the forward-looking regret from period $n$ onward
into the infinite future. This regret is between a policy which implements
$\tau$ until it switches to the optimal policy $\mu^{\theta}$ in period $n$ as
opposed to continuing with $\tau$. Formally,

$\displaystyle\mathbb{R}_{x_{0}}^{\tau,\theta}(n)$
$\displaystyle\coloneqq\nu^{\theta}(X_{n})-\mathbb{E}^{\tau,\theta}_{x_{0}}\left[\sum_{t=n}^{\infty}\beta^{t-n}R_{t}\mid
H_{n}\right]$ (44)
$\displaystyle=\sup_{\mu\in\mathcal{M}}\mathbb{E}_{x_{0}}^{\mu,\theta}\left[\sum_{t=n}^{\infty}\beta^{t-n}R_{t}\mid
H_{n}\right]-\mathbb{E}^{\tau,\theta}_{x_{0}}\left[\sum_{t=n}^{\infty}\beta^{t-n}R_{t}\mid
H_{n}\right]$ (45)
$\displaystyle=\mathbb{E}_{x_{0}}^{\mu^{\theta},\theta}\left[\sum_{t=n}^{\infty}\beta^{t-n}R_{t}\mid
H_{n}\right]-\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\sum_{t=n}^{\infty}\beta^{t-n}R_{t}\mid
H_{n}\right],$ (46)

where the conditioning on the random history vector is denoted explicitly.

The residual regret is constructed in a way such that its expected value is
the expected residual regret itself, i.e.,

$\displaystyle\mathcal{R}_{x_{0}}^{\tau,\theta}(n)=\mathbb{E}_{x_{0}}^{\tau,\theta}[\mathbb{R}_{x_{0}}^{\tau,\theta}(n)].$
(47)

Recall the interpretation of the first term of (46); the stochastic process is
driven by a “hybrid” policy that follows the $\tau$ policy for the first $n$
periods, and then adopts the optimal policy $\mu^{\theta}$ in period $n$ after
the oracle reveals $\theta$. It is a random quantity due to the random
starting state $X_{n}$ in period $n$, induced by TS. The second term is the
random expected infinite sum obtained by implementing TS, starting from random
state $X_{n}$, and omitting the rewards from period $0$ to $n-1$.

Next, we show that the residual regret converges to 0 in the limit
$\mathbb{P}_{x_{0}}^{\tau,\theta}$-a.s., assuming it exists.

######  Assumption 3 (Existence of the limit of
$\mathbb{R}_{x_{0}}^{\tau,\theta}(n)$).

Suppose that $\lim\limits_{n\to\infty}\mathbb{R}_{x_{0}}^{\tau,\theta}(n)$
exists $\mathbb{P}_{x_{0}}^{\tau,\theta}$-a.s.

From (44) observe that the residual regret is the difference of two terms.
Consider the first term $\nu^{\theta}(X_{n})$. Under some technical
conditions, if the limit of the state process $\\{X_{n}\\}$ exists, then the
limit of $\nu^{\theta}(X_{n})$ exists. However, since we do not impose any
restrictions on the underlying chain structure and the underlying stochastic
process is history-dependent, we cannot guarantee that
$\lim\limits_{n\to\infty}X_{n}$ exists, and thus, there could be cases where
$\lim\limits_{n\to\infty}\nu^{\theta}(X_{n})$ does not converge666We do not
require aperiodicity; the chain could be periodic, leading to oscillating
rewards.. Therefore, we directly assume that the limit of the residual regret
exists. Similar to the expected residual regret, the following corollary shows
that under certain conditions the probabilistic residual regret also vanishes
in the limit.

######  Corollary 7.2.

When the conditions of Proposition 6.5 and Assumption 3 hold, the residual
regret of TS vanishes, i.e.,

$\lim\limits_{n\to\infty}\mathbb{R}_{x_{0}}^{\tau,\theta}(n)=0,\quad\mathbb{P}_{x_{0}}^{\tau,\theta}\textnormal{-almost
surely}.$

###### Proof of Corollary 7.2.

Recall that the probabilistic residual regret converges
$\mathbb{P}_{x_{0}}^{\tau,\theta}\textnormal{-a.s.}$ to 0 if there exists a
null set $\mathbf{A}\in\mathcal{B}(\Omega)$ with
$\mathbb{P}_{x_{0}}^{\tau,\theta}(\mathbf{A})=0$ such that the statement holds
if $\omega\notin\mathbf{A}$. Given Assumption 3, it suffices to show that
$\forall$ $\epsilon>0$, $\nexists$ $\mathbf{A}\in\mathcal{B}(\Omega)$ with
$\mathbb{P}_{x_{0}}^{\tau,\theta}(\mathbf{A})=\epsilon>0$ such that
$\lim\limits_{n\to\infty}\mathbb{R}_{x_{0}}^{\tau,\theta}(n)\neq 0$
$\forall\,\omega\in\mathbf{A}$. We prove this by contradiction.

Suppose that $\exists$ $\mathbf{A}\in\mathcal{B}(\Omega)$ with
$\mathbb{P}_{x_{0}}^{\tau,\theta}(\mathbf{A})=\epsilon^{\prime}>0$ for some
$\epsilon^{\prime}>0$ such that
$\lim\limits_{n\to\infty}\mathbb{R}_{x_{0}}^{\tau,\theta}(n)\neq 0$
$\forall\,\omega\in\mathbf{A}$. Since $\mathbb{R}_{x_{0}}^{\tau,\theta}(n)>0$
by construction, this limit is strictly positive, i.e.,
$\lim\limits_{n\to\infty}\mathbb{R}_{x_{0}}^{\tau,\theta}(n)>0$
$\forall\,\omega\in\mathbf{A}$.

Then, for any $\delta>0$, we define $\mathbf{A}_{\delta}$ as the largest
measurable subset of $\mathbf{A}$ such that
$\mathbf{A}_{\delta}\subset\\{\omega\in\mathcal{B}(\Omega):\lim\limits_{n\to\infty}\mathbb{R}_{x_{0}}^{\tau,\theta}(n)>\delta\\}$.
According to Assumption 3 and the supposition in the previous paragraph,
$\exists$ $\delta^{\prime}$ such that
$\mathbb{P}_{x_{0}}^{\tau,\theta}(\mathbf{A}_{\delta^{\prime}})=\epsilon^{\prime}>0$.
Then, we can write

$\displaystyle\lim\limits_{n\to\infty}\mathcal{R}_{x_{0}}^{\tau,\theta}(n)$
$\displaystyle=\lim\limits_{n\to\infty}\mathbb{E}_{x_{0}}^{\tau,\theta}[\mathbb{R}_{x_{0}}^{\tau,\theta}(n)]$
(48)
$\displaystyle=\lim\limits_{n\to\infty}\left\\{\int_{\mathbf{A}_{\delta^{\prime}}}\mathbb{R}_{x_{0}}^{\tau,\theta}(n)\,d\mathbb{P}_{x_{0}}^{\tau,\theta}(\omega)+\int_{\mathcal{B}(\Omega)\setminus\mathbf{A}_{\delta^{\prime}}}\mathbb{R}_{x_{0}}^{\tau,\theta}(n)\,d\mathbb{P}_{x_{0}}^{\tau,\theta}(\omega)\right\\}$
(49)
$\displaystyle=\int_{\mathbf{A}_{\delta^{\prime}}}\lim\limits_{n\to\infty}\mathbb{R}_{x_{0}}^{\tau,\theta}(n)\,d\mathbb{P}_{x_{0}}^{\tau,\theta}(\omega)+\int_{\mathcal{B}(\Omega)\setminus\mathbf{A}_{\delta^{\prime}}}\lim\limits_{n\to\infty}\mathbb{R}_{x_{0}}^{\tau,\theta}(n)\,d\mathbb{P}_{x_{0}}^{\tau,\theta}(\omega)$
(50) $\displaystyle>\delta^{\prime}\epsilon^{\prime}>0,$ (51)

which contradicts Proposition 6.5. By construction, the first term in (49)
converges to a number strictly greater than 0, and the second term converges
to some non-negative number. Because $\mathbb{R}_{x_{0}}^{\tau,\theta}(n)$
exists by Assumption 3 and is finite777Since the rewards are finite-valued, in
any period, the difference in rewards of the first and second terms is bounded
by a constant. By the infinite geometric series property, and assuming
$\beta\in[0,1)$, $\mathbb{R}_{x_{0}}^{\tau,\theta}(n)$ is finite. , by the
Dominated Convergence Theorem, we can express (49) as (50), But then, (51)
contradicts with Proposition 6.5. This implies that our supposition cannot
hold, and thus, the residual regret converges
$\mathbb{P}_{x_{0}}^{\tau,\theta}\text{-a.s.}$ to 0. ∎

##  8 Concluding Remarks and Discussion

Fixing a finite period $n$, we decompose the expected infinite-horizon regret
into three components. Two of the components are not actionable by the DM. The
first component is the expected regret of the past. The second is the regret
expected to be accrued in the future due to the random state the $\theta$-MDP
is in period $n$, which is a consequence of implementing a possibly suboptimal
policy and cannot be revoked by the DM. The third component, which we called
the expected residual regret, captures what a rational DM would consider as
expected regret. It determines whether the DM will do the best moving forward,
given their state in period $n$. Hence, we evaluate TS by only this third
component, i.e., the expected residual regret.

We reiterate that our results hold for chain settings where
$q^{\gamma}(\cdot\mid x,u)$ is strictly positive
$\forall\gamma\in\mathcal{P}$, which rules out chains with absorbing states.
Yet, by construction, the expected residual regret is a viable concept
independent of the underlying chain structure; it is applicable to any
structure. Hence, deriving the performance of the residual regret in broader
settings is a potential direction of further research.

In our setting, we show that the expected residual regret of TS decays
exponentially to 0 in the worst case (Proposition 6.5). We explore the
conditions under which the posterior sampling error converges to 0 with almost
sure probability (Theorem 1). At the crux of these theorems are certain
sufficient conditions, which we present in Assumption 2, which rule out
oscillating functions that would prevent complete learning. Finally, we show
that a probabilistic version of the expected residual regret vanishes
(Corollary 7.2), similar to its expected-valued version. At the crux of this
corollary is the sufficiency condition that we present in Assumption 3. A
future direction of research is to study the implications of Assumptions 2 and
3 in specific problem contexts. In addition to conditions on the underlying
chain structure, complete learning may be a necessary but not sufficient
condition for Assumption 3 to hold.

To the best of our knowledge, the notion of an ADO policy from the adaptive
learning literature had not been connected to TS. By leveraging connections
between these settings, we offer a novel concept of learning. Under some mild
assumptions, we provide guarantees of learning in both expected and
probabilistic senses in settings with general state and control spaces, using
the infinite-horizon discounted reward criterion. An interesting extension of
the setup in this paper is to analyze the performance of the novel concept of
learning (i.e., expected residual regret) under broader settings, e.g., under
general chain structures.

## Appendix

##  Appendix A Proofs of Lemmas

###### Proof of Lemma 4.1..

When the Bayesian update is conducted with a degenerate distribution, it
returns a degenerate distribution. We show this by induction. We have
$\pi_{0}(\theta\mid h_{0})=1$ and assume $\pi_{n}(\theta\mid H_{n})=1$.

$\displaystyle\pi_{n+1}(\theta\mid H_{n+1})\coloneqq$
$\displaystyle\frac{\mathcal{L}^{\theta}(H_{n+1})\pi_{0}(\theta\mid
h_{0})}{\sum_{\gamma\in\mathcal{P}}\mathcal{L}^{\gamma}(H_{n+1})\pi_{0}(\gamma\mid
h_{0})}$ $\displaystyle=$
$\displaystyle\frac{\mathcal{L}^{\theta}(H_{n+1})\pi_{0}(\theta\mid
h_{0})}{\mathcal{L}^{\theta}(H_{n+1})\pi_{0}(\theta\mid
h_{0})+\sum_{\gamma\neq\theta\in\mathcal{P}}\mathcal{L}^{\gamma}(H_{n+1})\pi_{0}(\gamma\mid
h_{0})}=\frac{\mathcal{L}^{\theta}(H_{n+1})}{\mathcal{L}^{\theta}(H_{n+1})}=1.$

Since the posterior distribution is degenerate, TS always samples the true
parameter $\theta$ from the parameter space. Therefore, the DM who runs the
$\tau$ policy ends up implementing the $\theta$-optimal policy. ∎

###### Proof of Lemma 6.1..

Consider the $\theta$-ADO statement,
$|V_{x_{0}}^{\mu,\theta}(n)-\mathbb{E}_{x_{0}}^{\mu,\theta}[\nu^{\theta}(X_{n})]|$.
It can be rewritten as

$\displaystyle|V_{x_{0}}^{\mu,\theta}(n)-\mathbb{E}_{x_{0}}^{\mu,\theta}[\nu^{\theta}(X_{n})]|$
(52)
$\displaystyle=\left|\mathbb{E}_{x_{0}}^{\tau,\theta}\sum_{t=n}^{\infty}\beta^{t-n}R_{t}-\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]\right|$
$\displaystyle=\left|\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\mathbb{E}_{x_{0}}^{\tau,\theta}\left(\sum_{t=n}^{\infty}\beta^{t-n}R_{t}\mid
X_{n}\right)-\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})\mid
X_{n}]\right]\right|$
$\displaystyle=\left|\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\mathbb{E}_{x_{0}}^{\tau,\theta}\left(\sum_{t=n}^{\infty}\beta^{t-n}R_{t}\mid
X_{n}\right)-\nu^{\theta}(X_{n})\right]\right|$
$\displaystyle=\left|\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\mathbb{E}_{x_{0}}^{\tau,\theta}\left(\sum_{t=n}^{\infty}\beta^{t-n}R_{t}(X_{t},U_{t})\mid
X_{n}\right)-\sup_{\mu\in\mathcal{M}}\mathbb{E}_{X_{n}}^{\mu,\theta}\left[\sum_{t=0}^{\infty}\beta^{t}R_{t}(X_{t},U_{t})\right]\right]\right|.$
(53)

The second equality is by the law of iterated expectations, and the fourth by
substituting in the definition of the optimal value function. Evidently, the
first term of (53) is upper bounded by the second term. Thus, (53) is equal to

$\displaystyle\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\sup_{\mu\in\mathcal{M}}\mathbb{E}_{X_{n}}^{\mu,\theta}\left[\sum_{t=0}^{\infty}\beta^{t}R_{t}(X_{t},U_{t})\right]-\mathbb{E}_{x_{0}}^{\tau,\theta}\left(\sum_{t=n}^{\infty}\beta^{t-n}R_{t}(X_{t},U_{t})\mid
X_{n}\right)\right],$

for any initial state $x_{0}\in\mathcal{X}$. Rewriting the optimal value
function in closed form, we obtain

$\displaystyle\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\nu^{\theta}(X_{n})-\mathbb{E}_{x_{0}}^{\tau,\theta}\left(\sum_{t=n}^{\infty}\beta^{t-n}R_{t}(X_{t},U_{t})\mid
X_{n}\right)\right],$

which is equal to

$\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]-\mathbb{E}_{x_{0}}^{\tau,\theta}\left[\sum_{t=n}^{\infty}\beta^{t-n}R_{t}(X_{t},U_{t})\right]=\mathbb{E}_{x_{0}}^{\tau,\theta}[\nu^{\theta}(X_{n})]-V_{x_{0}}^{\tau,\theta}(n).$

∎

###### Proof of Lemma 6.2..

This proof is an adaptation of Theorem 3.6 of Hernández-Lerma (2012). By the
definition in Section 6.1,

$\phi^{\theta}(X_{t},U_{t})=\mathbb{E}_{x_{0}}^{\mu,\theta}[R_{t}(X_{t},U_{t})+\beta\nu^{\theta}(X_{t+1})-\nu^{\theta}(X_{t})\mid
H_{t},U_{t}],$

for any initial state $x_{0}\in\mathcal{X}$, admissible policy
$\mu\in\mathcal{M}$, true parameter value $\theta$, $t\geq 0$. For any $t\geq
1$, history in period $t$ is
$h_{t}=(x_{0},\theta_{0},a_{0},r_{0},x_{1},\theta_{1},a_{1},r_{1},\dots,x_{t})$.
Multiplying by $\beta^{t-n}$ yields

$\beta^{t-n}\phi^{\theta}(X_{t},U_{t})=\mathbb{E}_{x_{0}}^{\mu,\theta}[\beta^{t-n}R_{t}(X_{t},U_{t})+\beta^{t-n+1}\nu^{\theta}(X_{t+1})-\beta^{t-n}\nu^{\theta}(X_{t})\mid
H_{t},U_{t}].$

Taking the expectation of both sides and by the law of total expectation, we
obtain

$\mathbb{E}_{x_{0}}^{\mu,\theta}[\beta^{t-n}\phi^{\theta}(X_{t},U_{t})]=\mathbb{E}_{x_{0}}^{\mu,\theta}[\beta^{t-n}R_{t}(X_{t},U_{t})+\beta^{t-n+1}\nu^{\theta}(X_{t+1})-\beta^{t-n}\nu^{\theta}(X_{t})].$

Summing over all $t\geq n$ gives

$\displaystyle\sum_{t=n}^{\infty}\beta^{t-n}\mathbb{E}_{x_{0}}^{\mu,\theta}[\phi^{\theta}(X_{t},U_{t})]$
$\displaystyle=\sum_{t=n}^{\infty}\mathbb{E}_{x_{0}}^{\mu}[\beta^{t-n}R_{t}(X_{t},U_{t})]$
$\displaystyle\qquad+\mathbb{E}_{x_{0}}^{\mu,\theta}\left[\sum_{t=n}^{\infty}(\beta^{t-n+1}\nu^{\theta}(X_{t+1})-\beta^{t-n}\nu^{\theta}(X_{t}))\right].$

The above simplifies into

$\displaystyle\sum_{t=n}^{\infty}\beta^{t-n}\mathbb{E}_{x_{0}}^{\mu,\theta}[\phi^{\theta}(X_{t},U_{t})]=V_{x_{0}}^{\mu,\theta}(n)-\mathbb{E}_{x_{0}}^{\mu,\theta}[\nu^{\theta}(X_{n})].$

Recalling the result of Lemma 6.1 as,

$\displaystyle-\sum_{t=n}^{\infty}\beta^{t-n}\mathbb{E}_{x_{0}}^{\mu,\theta}[\phi^{\theta}(X_{t},U_{t})]=\mathbb{E}_{x_{0}}^{\mu,\theta}[\nu^{\theta}(X_{n})]-V_{x_{0}}^{\mu,\theta}(n).$

In the limit, $\mu$ has vanishing expected residual regret (is $\theta$-ADO);
that is, for every $x_{0}\in\mathcal{X}$,

$\lim_{n\to\infty}(\mathbb{E}_{x_{0}}^{\mu,\theta}[\nu^{\theta}(X_{n})]-V_{x_{0}}^{\mu,\theta}(n))=0,$

if and only if, for every $x_{0}\in\mathcal{X}$,

$\lim_{n\to\infty}-\sum_{t=n}^{\infty}\beta^{t-n}\mathbb{E}_{x_{0}}^{\mu,\theta}[\phi^{\theta}(X_{t},U_{t})]=0.$

This is equivalent to, for every $x_{0}\in\mathcal{X}$,

$\lim_{t\to\infty}-\mathbb{E}_{x_{0}}^{\mu,\theta}[\phi^{\theta}(X_{t},U_{t})]=0.$

Hence, a policy $\mu$ has vanishing expected residual regret if and only if,
for every $x_{0}\in\mathcal{X}$,

$\lim_{t\to\infty}\mathbb{E}_{x_{0}}^{\mu,\theta}[\phi^{\theta}(X_{t},U_{t})]=0.$

By Theorem 4.1.4 of Chung (2001), if
$\mathbb{E}_{x_{0}}^{\mu,\theta}[\phi^{\theta}(X_{t},U_{t})]$ converges to 0,
then $\phi^{\theta}(X_{t},U_{t})$ converges to 0 in
probability-$\mathbb{P}_{x_{0}}^{\mu,\theta}$, for every
$x_{0}\in\mathcal{X}$, proving the forward direction of Lemma 6.2. It remains
to show the reverse direction to complete the proof. By the same theorem of
Chung (2001), for a uniformly bounded sequence $\\{\phi^{\theta}\\}$,
convergence in probability and $\mathcal{L}^{p}$ (in expectation) are
equivalent. By the first remark in Section 3.1, it follows that
$\\{\phi^{\theta}\\}$ is bounded by some finite number. Hence,
$\phi^{\theta}(X_{t},U_{t})\to 0$ in
probability-$\mathbb{P}_{x_{0}}^{\mu,\theta}$ implies
$\mathbb{E}_{x_{0}}^{\mu,\theta}[\phi^{\theta}(X_{t},U_{t})]\to 0$ as $t\to
0$. ∎

###### Proof of Lemma 6.4..

We walk the reader through the proof of Kim (2017) while using our notation.
The proof initially defines the stochastic process, for any
$\gamma\neq\theta$,

$Z_{t}^{\gamma}=\sum_{s=0}^{t}\log\Lambda_{s}^{\gamma},$

where, using our notation,

$\displaystyle\Lambda_{0}^{\gamma}$ $\displaystyle=1$
$\displaystyle\Lambda_{s}^{\gamma}$
$\displaystyle=\frac{f^{\theta}(R_{s-1}\mid
X_{s-1},U_{s-1})q^{\theta}(X_{s}\mid X_{s-1},U_{s-1})}{f^{\gamma}(R_{s-1}\mid
X_{s-1},U_{s-1})q^{\gamma}(X_{s}\mid X_{s-1},U_{s-1})},$

for $0<s\leq t$. Next, Kim (2017) defines filtration $(\mathcal{H}_{t}:t\geq
0)$ by $\mathcal{H}_{t}=\sigma(H_{t})$, where $H_{t}$ is by the definition in
(4). Then, it follows that the stochastic process $Z_{t}^{\gamma}$ is a
submartingale with respect to $\mathcal{H}_{t}$ under probability measure
$\mathbb{P}_{x_{0}}^{\tau,\theta}$. It is crucial that $Z_{t}^{\gamma}$ is a
submartingale. Kim (2017) decomposes it into an $\mathcal{H}_{t}$ martingale
under $\mathbb{P}_{x_{0}}^{\tau,\theta}$,

$M_{t}^{\gamma}\coloneqq\sum_{s=0}^{t}(\log\Lambda^{\gamma}_{s}-\mathbb{E}^{\tau,\theta}_{x_{0}}[\log\Lambda^{\gamma}_{s}\mid\mathcal{H}_{s-1}]),$

and a predictable process,

$A_{t}^{\gamma}\coloneqq\sum_{s=0}^{t}\mathbb{E}^{\tau,\theta}_{x_{0}}[\log\Lambda^{\gamma}_{s}\mid\mathcal{H}_{s-1}].$

We explain how the proof extends to our setting through Assumption 1. The
argument is twofold. The first requirement is that the increments of
$M_{t}^{\gamma}$ are bounded above and below by some $d$, i.e.,

$\displaystyle|\log\Lambda^{\gamma}_{s}-\mathbb{E}^{\tau,\theta}_{x_{0}}[\log\Lambda^{\gamma}_{s}\mid\mathcal{H}_{s-1}]|\leq
d,$ (54)

for some $d>0$. To see that (54) holds in our setting, note that by (37) and
(38), i.e., $f^{\gamma}(r\mid x,u)$ and $q^{\gamma}(y\mid x,u)$ are bounded
away from 0, we have that $|\log f^{\gamma}(r\mid x,u)|<\infty$ and $|\log
q^{\gamma}(y\mid x,u)|<\infty$. This satisfies (54), which is needed for
Azuma’s inequality, a crucial step of Kim (2017)’s proof, to hold. The second
requirement of the adaptation of the proof is

$\displaystyle\sum\limits_{s=0}^{t}\mathbb{E}_{x_{0}}^{\tau,\theta}[\log\Lambda^{\gamma}_{s}\mid\mathcal{H}_{s-1}]\geq\epsilon
t,$ (55)

i.e., (55) is an increasing predictable process. By (39), it follows that

$\displaystyle\mathbb{E}^{\tau,\theta}_{x_{0}}[\log\Lambda^{\gamma}_{s}\mid\mathcal{H}_{s-1}]>\epsilon(x,u,\theta,\gamma)\coloneqq\epsilon,\quad\forall
s\leq t,$ (56)

i.e., each increment of $A_{t}^{\gamma}$ is strictly positive, which satisfies
(55). The reader is referred to Kim (2017) for the details of why (56) holds.
∎

###### Proof of Lemma 7.1..

By the definition of almost-sure convergence, we have

$\mathbb{P}_{x_{0}}^{\tau,\theta}\left(\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})<1\right)=1.$

Therefore,

$\displaystyle
1=\mathbb{P}_{x_{0}}^{\tau,\theta}\left(\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})<1\right)$
$\displaystyle=\mathbb{P}_{x_{0}}^{\tau,\theta}\left(\bigcup_{n=1}^{\infty}\left\\{\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})<1-\frac{1}{n}\right\\}\right)$
$\displaystyle\leq\sum_{n=1}^{\infty}\mathbb{P}_{x_{0}}^{\tau,\theta}\left(\lim_{t\to\infty}\pi_{t}(\theta\mid
H_{t})<1-\frac{1}{n}\right).$

where the inequality is by Boole’s inequality. Hence, Lemma 7.1 is verified. ∎

##  Appendix B Analysis of Assumption 1

Recall Assumption 1. Since Example 5.2 has a finite state space, (39) boils
down to: For any $x\in\mathcal{X}$, $u\in\mathcal{U}$, and any two distinct
parameter value, $\gamma\neq\theta\in\mathcal{P}$, there exists a positive
constant $\epsilon(x,u,\theta,\gamma)>0$ such that

$\mathbb{K}(\nu_{\theta}^{x,u}\mid\nu_{\gamma}^{x,u})\geq\epsilon(x,u,\theta,\gamma).$

The above condition holds if and only if (by definition)

$E_{f^{\theta}q^{\theta}}\left[\log\left(\frac{d\nu_{\theta}^{x,u}}{d\nu_{\gamma}^{x,u}}\right)\right]=E_{f^{\theta}q^{\theta}}\left[\log\left(\frac{f^{\theta}(\cdot\mid
x,u)q^{\theta}(\cdot\mid x,u)}{f^{\gamma}(\cdot\mid x,u)q^{\gamma}(\cdot\mid
x,u)}\right)\right]\geq\epsilon(x,u,\theta,\gamma),$

where $E_{f^{\theta}q^{\theta}}[\cdot\mid x,u]$ is defined in Section 3.2. For
illustration purposes, we make the same assumption we had in Example 5.2; the
$\theta$-MDP has only one state. This implies the transition kernel,
$q^{\theta}(\cdot\mid x,u)$, is deterministic and we simplify the relative
entropy expression. Due to the simpler version of the relative entropy, we
utilize the expectation operator $E_{f^{\theta}}[\cdot\mid x,u]$, also defined
in Section 3.2. It suffices to find a constant
$\epsilon(x,u,\theta,\gamma)>0$, for any $x_{A}$ (in this case
$\mathcal{X}=\\{x_{0}\\}$ where $x_{0}=x_{A}$), any $u\in\mathcal{U}$ (control
1 or 2), $\theta=B$ and $\gamma=A$, such that

$E_{f^{\theta}}\left[\log\left(\frac{f^{\theta}(\cdot\mid
x,u)}{f^{\gamma}(\cdot\mid
x,u)}\right)\right]\geq\epsilon(x,u,\theta,\gamma).$

We have,

$\displaystyle E_{f^{\theta}}\left[\log\left(\frac{\frac{1}{\sqrt{2\pi
0.1}}e^{-\frac{(r-\mu^{\theta})^{2}}{2(0.1)}}\Big{|}x,u}{\frac{1}{\sqrt{2\pi
0.1}}e^{-\frac{(r-\mu^{\gamma})^{2}}{2(0.1)}}\Big{|}x,u}\right)\right]$
$\displaystyle=E_{f^{\theta}}\left[\log\left(\frac{e^{-(r-\mu^{\theta})^{2}}\big{|}x,u}{e^{-(r-\mu^{\gamma})^{2}}\big{|}x,u}\right)\right]$
$\displaystyle=E_{f^{\theta}}\left[\log\left(e^{-(r-\mu^{\theta})^{2}+(r-\mu^{\gamma})^{2}}\big{|}x,u\right)\right],$

which can be simplified as

$E_{f^{\theta}}[-(r-\mu^{\theta})^{2}+(r-\mu^{\gamma})^{2}\mid x,u].$

Case 1: When the state is $x_{A}$ and control 2 is picked by the TS policy,
$r\sim N(0.8,0.1)$, and

$\displaystyle E_{f^{\theta}}[-(r-0.8)^{2}+(r-0.4)^{2}\mid x_{A},2]$
$\displaystyle=-Var[r\mid x_{A},2]+E_{f^{\theta}}[(r-0.4)^{2}\mid x_{A},2]$
$\displaystyle=-0.1+E_{f^{\theta}}[r^{2}-0.8r+0.16\mid x_{A},2]$
$\displaystyle=-0.1+E_{f^{\theta}}[r^{2}\mid x_{A},2]-0.8E_{f^{\theta}}[r\mid
x_{A},2]+0.16$ $\displaystyle=-0.1+Var[r\mid x_{A},2]+(E_{f^{\theta}}[r\mid
x_{A},2])^{2}-0.8E_{f^{\theta}}[r\mid x_{A},2]+0.16$
$\displaystyle=-0.1+0.1+0.64-0.64+0.16=0.16.$

Case 2: When the state is $x_{A}$ and control 1 is picked by the TS policy,
$r\sim N(0.3,0.1)$, and

$\displaystyle E_{f^{\theta}}[-(r-0.3)^{2}+(r-0.5)^{2}\mid x_{A},1]$
$\displaystyle=-Var[r\mid x_{A},1]+E_{f^{\theta}}[(r-0.5)^{2}\mid x_{A},1]$
$\displaystyle=-0.1+E_{f^{\theta}}[r^{2}-r+0.25\mid x_{A},1]$
$\displaystyle=-0.1+E_{f^{\theta}}[r^{2}\mid x_{A},1]-E_{f^{\theta}}[r\mid
x_{A},1]+0.25$ $\displaystyle=-0.1+Var[r\mid x_{A},1]+(E_{f^{\theta}}[r\mid
x_{A},1])^{2}-E_{f^{\theta}}[r\mid x_{A},1]+0.25$
$\displaystyle=-0.1+0.1+0.09-0.3+0.25=0.04.$

As long as $0<\epsilon(x,u,\theta,\gamma)\leq 0.04$, Assumption 1 holds for
Example 5.2.

## References

  * Agrawal and Goyal (2012) Agrawal S, Goyal N (2012) Analysis of thompson sampling for the multi-armed bandit problem. _Conference on Learning Theory_ , 39–1.
  * Banjević and Kim (2019) Banjević D, Kim MJ (2019) Thompson sampling for stochastic control: The continuous parameter case. _IEEE Transactions on Automatic Control_ 64(10):4137–4152.
  * Chung (2001) Chung KL (2001) _A course in probability theory_ (Academic press).
  * Freedman (1963) Freedman DA (1963) On the asymptotic behavior of bayes’ estimates in the discrete case. _The Annals of Mathematical Statistics_ 1386–1403.
  * Gopalan and Mannor (2015) Gopalan A, Mannor S (2015) Thompson sampling for learning parameterized markov decision processes. _Conference on Learning Theory_ , 861–898.
  * Hernández-Lerma (2012) Hernández-Lerma O (2012) _Adaptive Markov control processes_ , volume 79 (Springer Science & Business Media).
  * Hernández-Lerma and Lasserre (2012) Hernández-Lerma O, Lasserre JB (2012) _Discrete-time Markov control processes: basic optimality criteria_ , volume 30 (Springer Science & Business Media).
  * Kalkanli and Ozgur (2020) Kalkanli C, Ozgur A (2020) Asymptotic convergence of thompson sampling. _arXiv e-prints_ arXiv–2011.
  * Kearns and Singh (2002) Kearns M, Singh S (2002) Near-optimal reinforcement learning in polynomial time. _Machine learning_ 49:209–232.
  * Kim (2017) Kim MJ (2017) Thompson sampling for stochastic control: The finite parameter case. _IEEE Transactions on Automatic Control_ 62(12):6415–6422.
  * Lai and Robbins (1985) Lai TL, Robbins H (1985) Asymptotically efficient adaptive allocation rules. _Advances in applied mathematics_ 6(1):4–22.
  * Leike et al. (2016) Leike J, Lattimore T, Orseau L, Hutter M (2016) Thompson sampling is asymptotically optimal in general environments. _arXiv preprint arXiv:1602.07905_ .
  * Puterman (2014) Puterman ML (2014) _Markov Decision Processes.: Discrete Stochastic Dynamic Programming_ (John Wiley & Sons).
  * Schäl (1987) Schäl M (1987) Estimation and control in discounted stochastic dynamic programming. _Stochastics: An International Journal of Probability and Stochastic Processes_ 20(1):51–71.
  * Shreve (1978) Shreve SE (1978) _Stochastic optimal control: The discrete time case_ (Academic Press).
  * Sutton and Barto (2018) Sutton RS, Barto AG (2018) _Reinforcement learning: An introduction_ (MIT press).
  * Thompson (1933) Thompson WR (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. _Biometrika_ 25(3/4):285–294.