$(A^{*}_{t})_{t\in\mathbb{N}}$ is stationary, then, by Proposition 1,

$\displaystyle\bar{H}(A^{*})$
$\displaystyle\leq\frac{1+\log(\tau_{\textup{eff}})+H(A_{t}^{*}|A_{t}^{*}\neq
A_{t-1}^{*})}{\tau_{\textup{eff}}}$
$\displaystyle\leq\frac{1+\log(\tau_{\textup{eff}})+H(\theta_{t})}{\tau_{\textup{eff}}}$
$\displaystyle\leq\frac{1+\log(\tau_{\textup{eff}})+p\ln(2/\epsilon)}{\tau_{\textup{eff}}}.$

Combining this with Theorem 1 and the information ratio bound in Lemma 2 gives

$\bar{\Delta}_{\infty}(\pi^{\rm TS})\leq\sqrt{2\cdot\sigma^{2}\cdot
k\times\frac{1+\log(\tau_{\textup{eff}})+p\ln(2/\epsilon)}{\tau_{\textup{eff}}}}=\tilde{O}\left(\sigma\sqrt{\frac{p\cdot
k}{\tau_{\textup{eff}}}}\right).$

###  A.8 Proof of Theorem 2

The proof is almost identical to that of Theorem 1. Let
$\Delta_{t}^{\dagger}:=\mathbb{E}[R_{t,A_{t}^{\dagger}}-R_{t,A_{t}}]$,
$G_{t}^{\dagger}:=I(A_{t}^{\dagger};(A_{t},O_{t,A_{t}})|\mathcal{F}_{t-1})$,
and $\Gamma_{t}^{\dagger}={\Delta_{t}^{\dagger}}^{2}/G_{t}^{\dagger}$. Then,

$\sum_{t=1}^{T}\Delta_{t}^{\dagger}=\sum_{t=1}^{T}\sqrt{\Gamma_{t}^{\dagger}}\sqrt{G_{t}^{\dagger}}\leq\sqrt{\sum_{t=1}^{T}\Gamma_{t}^{\dagger}}\sqrt{\sum_{t=1}^{T}G_{t}^{\dagger}}\leq\sqrt{\Gamma(\pi;A^{\dagger})\cdot
T\cdot\sum_{t=1}^{T}G_{t}^{\dagger}},$

and

$\displaystyle\sum_{t=1}^{T}G_{t}^{\dagger}$
$\displaystyle=\sum_{t=1}^{T}I(A_{t}^{\dagger};(A_{t},O_{t,A_{t}})|\mathcal{F}_{t-1})$
$\displaystyle\leq I(A_{1:T}^{\dagger};\mathcal{F}_{T})$ $\displaystyle\leq
I(A_{1:T}^{\dagger};(\theta_{1:T},\mathcal{F}_{T}))$
$\displaystyle=I(A_{1:T}^{\dagger};\theta_{1:T})+I(A_{1:T}^{\dagger};\mathcal{F}_{t}|\theta_{1:T})$
$\displaystyle=I(A_{1:T}^{\dagger};\theta_{1:T}),$

where the last step uses the fact that
$I(A_{1:T}^{\dagger};\mathcal{F}_{t}|\theta_{1:T})=0$ since
$A_{1:T}^{\dagger}\perp\mathcal{F}_{t}|\theta_{1:T}$ according to Definition
4. Combining these results,

$\bar{\Delta}_{T}(\pi;A^{\dagger})=\frac{\sum_{t=1}^{T}\Delta_{t}^{\dagger}}{T}\leq\sqrt{\frac{\Gamma(\pi;A^{\dagger})\cdot\sum_{t=1}^{T}G_{t}^{\dagger}}{T}}\leq\sqrt{\Gamma(\pi;A^{\dagger})\cdot\bar{I}_{T}(A_{1:T}^{\dagger};\theta_{1:T})}.$

The bound on $\bar{\Delta}_{\infty}(\pi;A^{\dagger})$ simply follows by taking
limit on both sides.

###  A.9 Proof of Proposition 4

We state and prove a concrete version of Proposition 4.

######  Proposition 6 (Concrete version of Proposition 4).

If $|\mathcal{A}|\geq 2$ and $T\geq 2$, then

$\bar{\mathcal{R}}_{T}(D)\leq\frac{2\bar{V}_{T}}{D}\cdot\left(1+\log\left(1+\min\left\\{T,\frac{D}{2\bar{V}_{T}}\right\\}\right)+\log|\mathcal{A}|\right)+\frac{3\log(|\mathcal{A}|T)}{T},$

and

$\displaystyle\inf_{\pi}\bar{\Delta}_{T}(\pi)$ $\displaystyle\leq
5\cdot\left(\Gamma_{U}\cdot\log|\mathcal{A}|\cdot\bar{V}_{T}\right)^{1/3}\cdot\sqrt{\log\left(1+\min\left\\{T,\frac{\big{(}\Gamma_{U}\cdot\log|\mathcal{A}|\big{)}^{1/3}}{\bar{V}_{T}^{2/3}}\right\\}\right)}+\sqrt{\frac{3\Gamma_{U}\log(|\mathcal{A}|T)}{T}}$
$\displaystyle\leq
10\cdot\left(\Gamma_{U}\cdot\log|\mathcal{A}|\cdot\bar{V}_{T}\right)^{1/3}\cdot\log(T)+\sqrt{\frac{3\Gamma_{U}\log(|\mathcal{A}|T)}{T}}.$

###### Proof.

For brevity we define $\mu_{t}(a):=\mathbb{E}[R_{t,a}|\theta_{t}]$ so that
$\Delta_{t}(a)=\mu_{t}(A_{t}^{*})-\mu_{t}(a)$.

Fix $D$ and consider a satisficing action sequence $A^{\dagger}$ that gets
synchronized to $A^{*}$ whenever $D$-gap occurs:

$A_{t}^{\dagger}=\left\\{\begin{array}[]{ll}A_{t}^{*}&\text{if }t=1\text{ or
}\mu_{t}(A_{t}^{*})\geq\mu_{t}(A_{t-1}^{\dagger})+D,\\\
A_{t-1}^{\dagger}&\text{otherwise}.\end{array}\right.$

It is obvious that $\bar{\Delta}_{T}(A^{\dagger};A^{*})\leq D$ since
$\mu_{t}(A_{t}^{*})-\mu_{t}(A_{t}^{\dagger})\leq D$.

##### Step 1.

Let $V_{T}:=\bar{V}_{T}\times T$, and
$S_{T}^{\dagger}:=\mathbb{E}\left[1+\sum_{t=2}^{T}\mathbb{I}\\{A_{t}^{\dagger}\neq
A_{t-1}^{\dagger}\\}\right]$. We first show that
$S_{T}^{\dagger}\leq\frac{2V_{T}}{D}+1$ by arguing that the total variation
must increase at least by $D/2$ whenever the satisficing action switches.
Observe that, in every sample path,

$\displaystyle
2\times\sum_{t=2}^{T}\sup_{a\in\mathcal{A}}\left|\Delta_{t}(a)-\Delta_{t-1}(a)\right|$
$\displaystyle\geq\sum_{t=2}^{T}\left|\Delta_{t}(A_{t}^{*})-\Delta_{t-1}(A_{t}^{*})\right|+\left|\Delta_{t}(A_{t-1}^{\dagger})-\Delta_{t-1}(A_{t-1}^{\dagger})\right|$
$\displaystyle=\sum_{t=2}^{T}\left|\Delta_{t}(A_{t}^{*})-\Delta_{t-1}(A_{t}^{*})\right|+\left|\Delta_{t-1}(A_{t-1}^{\dagger})-\Delta_{t}(A_{t-1}^{\dagger})\right|$
$\displaystyle\geq\sum_{t=2}^{T}\left(\Delta_{t}(A_{t}^{*})-\Delta_{t-1}(A_{t}^{*})\right)+\left(\Delta_{t-1}(A_{t-1}^{\dagger})-\Delta_{t}(A_{t-1}^{\dagger})\right)$
$\displaystyle=\sum_{t=2}^{T}\left(\Delta_{t}(A_{t}^{*})-\Delta_{t}(A_{t-1}^{\dagger})\right)-\left(\Delta_{t-1}(A_{t}^{*})-\Delta_{t-1}(A_{t-1}^{\dagger})\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\sum_{t=2}^{T}\left(\mu_{t}(A_{t}^{*})-\mu_{t}(A_{t-1}^{\dagger})\right)-\left(\mu_{t-1}(A_{t}^{*})-\mu_{t-1}(A_{t-1}^{\dagger})\right)$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\geq}}\sum_{t=2}^{T}\left(\mu_{t}(A_{t}^{*})-\mu_{t}(A_{t-1}^{\dagger})\right)-\left(\mu_{t-1}(A_{t-1}^{*})-\mu_{t-1}(A_{t-1}^{\dagger})\right)$
$\displaystyle=\sum_{t=2}^{T}\left(\mu_{t}(A_{t}^{*})-\mu_{t}(A_{t}^{\dagger})\right)-\left(\mu_{t-1}(A_{t-1}^{*})-\mu_{t-1}(A_{t-1}^{\dagger})\right)+\left(\mu_{t}(A_{t}^{\dagger})-\mu_{t}(A_{t-1}^{\dagger})\right)$
$\displaystyle=\left(\mu_{T}(A_{T}^{*})-\mu_{T}(A_{T}^{\dagger})\right)-\left(\mu_{1}(A_{1}^{*})-\mu_{1}(A_{1}^{\dagger})\right)+\sum_{t=2}^{T}\left(\mu_{t}(A_{t}^{\dagger})-\mu_{t}(A_{t-1}^{\dagger})\right)$
$\displaystyle=\left(\mu_{T}(A_{T}^{*})-\mu_{T}(A_{T}^{\dagger})\right)-0+\sum_{t=2}^{T}\left(\mu_{t}(A_{t}^{\dagger})-\mu_{t}(A_{t-1}^{\dagger})\right)\mathbb{I}\\{A_{t}^{\dagger}\neq
A_{t-1}^{\dagger}\\}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\geq}}0+\sum_{t=2}^{T}D\cdot\mathbb{I}\\{A_{t}^{\dagger}\neq
A_{t-1}^{\dagger}\\},$

where step (a) uses the definition of $\Delta_{t}(a)$, step (b) uses the fact
that $\mu_{t-1}(A_{t}^{*})\leq\mu_{t-1}(A_{t-1}^{*})$, and step (c) holds
since $\mu_{T}(A_{T}^{*})-\mu_{T}(A_{T}^{\dagger})\geq 0$ and if
$A_{t}^{\dagger}\neq A_{t-1}^{\dagger}$ then $A_{t}^{*}=A_{t}^{\dagger}$ and
$\mu_{t}(A_{t}^{*})-\mu_{t}(A_{t-1}^{\dagger})\geq D$. By taking expectation
on both sides, we obtain $2\times V_{T}\geq
D\times\mathbb{E}[\sum_{t=2}^{T}\mathbb{I}\\{A_{t}^{\dagger}\neq
A_{t-1}^{\dagger}\\}]=D\times(S_{T}^{\dagger}-1)$.

##### Step 2.

We further bound $\bar{\mathcal{R}}_{T}(D)$ by utilizing Proposition 2:

$\bar{\mathcal{R}}_{T}(D)\leq\bar{I}_{T}(A^{\dagger};\theta)\leq\bar{H}_{T}(A^{\dagger})\leq\frac{S_{T}^{\dagger}}{T}\cdot\left(1+\log\left(1+\frac{T}{S_{T}^{\dagger}}\right)+\log|\mathcal{A}|\right)+\frac{\log
T}{T}.$

Let $x\wedge y=\min\\{x,y\\}$ and $x\vee y=\max\\{x,y\\}$. Since $1\leq
S_{T}^{\dagger}\leq\left(\frac{2V_{T}}{D}+1\right)\wedge T$,

$\displaystyle\bar{\mathcal{R}}_{T}(D)$
$\displaystyle\leq\frac{S_{T}^{\dagger}}{T}\cdot\left(1+\log\left(1+\frac{T}{S_{T}^{\dagger}}\right)+\log|\mathcal{A}|\right)+\frac{\log
T}{T}$
$\displaystyle\leq\frac{2V_{T}/D+1}{T}\cdot\left(1+\log\left(1+\frac{T}{S_{T}^{\dagger}}\right)+\log|\mathcal{A}|\right)+\frac{\log
T}{T}$
$\displaystyle\leq\frac{2V_{T}}{DT}\cdot\left(1+\log\left(1+\frac{T}{S_{T}^{\dagger}}\right)+\log|\mathcal{A}|\right)+\frac{1+\log(1+T)+\log|\mathcal{A}|}{T}+\frac{\log
T}{T}$
$\displaystyle\leq\frac{2V_{T}}{DT}\cdot\left(1+\log\left(1+T\wedge\left(1\vee\frac{DT}{2V_{T}}\right)\right)+\log|\mathcal{A}|\right)+\frac{2\log
T+3\log|\mathcal{A}|}{T}+\frac{\log T}{T}$
$\displaystyle=\frac{2V_{T}}{DT}\cdot\left(1+\log\left(1+T\wedge\left(1\vee\frac{DT}{2V_{T}}\right)\right)+\log|\mathcal{A}|\right)+\frac{3\log(|\mathcal{A}|T)}{T},$

where the last inequality uses $1\leq 2\log|\mathcal{A}|$ for
$|\mathcal{A}|\geq 2$ and $\log(1+T)\leq 2\log T$ for $T\geq 2$.

##### Step 3.

To simplify notation, let $k:=|\mathcal{A}|$, and $\kappa:=1+\log k$. We
consider a satisficing action sequence $A^{\dagger}$ constructed with
$D=D^{*}:=\left(2\cdot\Gamma_{U}\cdot\kappa\cdot\bar{V}_{T}\right)^{1/3}$. By
Theorem 3, with
$\tau^{*}:=T\wedge\left(1\vee\frac{D^{*}}{2\bar{V}_{T}}\right)$,

$\displaystyle\inf_{\pi}\bar{\Delta}_{T}(\pi)$ $\displaystyle\leq
D^{*}+\sqrt{\Gamma_{U}\times\bar{\mathcal{R}}_{T}(D^{*})}$ $\displaystyle\leq
D^{*}+\sqrt{\Gamma_{U}\times\left[\frac{2\bar{V}_{T}}{D^{*}}\cdot\left(\kappa+\log\left(1+\tau^{*}\right)\right)+\frac{3\log(kT)}{T}\right]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}D^{*}+\sqrt{\Gamma_{U}\times\left[\frac{2\bar{V}_{T}}{D^{*}}\cdot\left(\kappa+\log\left(1+\tau^{*}\right)\right)\right]}+\sqrt{\frac{3\Gamma_{U}\log(kT)}{T}}$
$\displaystyle=D^{*}+\sqrt{\frac{2\Gamma_{U}\kappa\bar{V}_{T}}{D^{*}}\times\left(1+\frac{\log\left(1+\tau^{*}\right)}{\kappa}\right)}+\sqrt{\frac{3\Gamma_{U}\log(kT)}{T}}$
$\displaystyle=D^{*}+D^{*}\times\sqrt{1+\frac{\log\left(1+\tau^{*}\right)}{\kappa}}+\sqrt{\frac{3\Gamma_{U}\log(kT)}{T}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}2.6\times
D^{*}\times\sqrt{\log\left(1+\tau^{*}\right)}+\sqrt{\frac{3\Gamma_{U}\log(kT)}{T}},$

where step (a) uses $\sqrt{x+y}\leq\sqrt{x}+\sqrt{y}$ for any $x,y\geq 0$, and
step (b) uses $\kappa\geq 1$ and $\log\left(1+\tau^{*}\right)\geq\log 2$.
Since $\kappa\leq 3\log k$, we have

$D^{*}=(2\cdot\Gamma_{U}\cdot\kappa\cdot\bar{V}_{T})^{1/3}\leq(6\cdot\Gamma_{U}\cdot\log
k\cdot\bar{V}_{T})^{1/3}\leq 1.9\cdot(\Gamma_{U}\cdot\log
k\cdot\bar{V}_{T})^{1/3}.$

Therefore,

$\inf_{\pi}\bar{\Delta}_{T}(\pi)\leq 5\cdot(\Gamma_{U}\cdot\log
k\cdot\bar{V}_{T})^{1/3}\times\sqrt{\log\left(1+\min\left\\{T,\frac{(\Gamma_{U}\cdot\log
k\cdot\bar{V}_{T})^{1/3}}{\bar{V}_{T}}\right\\}\right)}+\sqrt{\frac{3\Gamma_{U}\log(kT)}{T}}.$

The final claim is obtained by observing that $\sqrt{\log(1+T)}\leq 2\log T$
for $T\geq 2$. ∎

##  Appendix B Comparison with Liu et al. [2023]

In this section, we provide a detailed comparison between our work and Liu et
al. [2023].

Both papers adopt a Bayesian perspective that models the nonstationarity
through a stochastic latent parameter process whose law is known to the
decision maker. Both papers consider Thompson sampling (TS), which is the rule
that employs probability matching with respect to the optimal action sequence
$A^{*}$. The primary concern in Liu et al. [2023] revolves around the
potential shortcomings of TS in rapidly changing environments where learning
$A^{*}$ is hopeless. Our paper considers this shortcoming of TS in Section 7.
To tackle this challenge, both studies propose some variants of TS designed to
‘satisfice’, i.e., aim to learn and play a different target other than
$A^{*}$.

More specifically, Liu et al. [2023] proposes a brilliant algorithm called
_predictive sampling_ (PS) that improves over TS by ‘‘deprioritizing acquiring
information that quickly loses usefulness’’. Using our notation, PS’s learning
target is
$A_{t}^{\dagger}=\operatorname*{\mathrm{argmax}}_{a\in\mathcal{A}}\mathbb{E}[R_{t,a}|\mathcal{F}_{t-1},(R_{t^{\prime},a^{\prime}})_{a^{\prime}\in\mathcal{A},t^{\prime}\geq
t+1}]$, the arm that would have been played by a Bayesian decision maker
informed of all future rewards but not the latent parameters.666 In its
implementation, it generates a fictitious future scenario, and makes an
inference on the best arm after simulating the posterior updating procedure
with respect to this future scenario. This makes the algorithm to take into
account the total amount of information about the current state that the
decision maker can potentially accumulate in the future, and hence prevents it
from being overly optimistic about the learnability of the target. A similar
idea can be found in Min et al. [2019] for the stationary bandit problems with
a finite-time horizon. By ignoring the unresolvable uncertainty in the latent
states — i.e. that which remains even conditioned on all future reward
observations — PS avoids wasteful exploration. We remark that one of our
suggested satisificing action sequence designs, Example 12, was motivated from
Liu et al. [2023]. But our satisficing TS does not cannot fully generalize PS
since we have restricted the learning target to be determined independently
from the algorithm’s decisions (see Definition 4), while $A_{t}^{\dagger}$
above depends on the history of observations under the algorithm.

Liu et al. [2023] uses an information-ratio analysis to bound an algorithm’s
‘foresight regret’ in terms of the total possible ‘predictive information.’
Their custom modifications to the information-ratio analysis in Russo and Van
Roy [2016] enable an analysis of predictive sampling which seems not to be
possible otherwise. By contrast, our analysis does not apply to predictive
sampling, but produces a wealth of results that do not follow from Liu et al.
[2023]. We elaborate on three main differences in the information-theoretic
analysis.

First, Liu et al. [2023] bound a custom suboptimality measure which they call
foresight regret, whereas we bound conventional (‘dynamic’) regret. Compared
to the conventional regret which we denote by $\bar{\Delta}_{T}(\pi;A^{*})$,
foresight regret can serve as a tighter benchmark that better quantifies the
range of achievable performance, since it is always non-negative while not
exceeding the conventional regret. For the same reason, however, their results
do not provide upper bounds on the conventional regret , a metric treated in a
huge preceding literature. Since our work bounds the conventional regret
metric, it enables us to recover results that are comparable to the existing
literature; see for instance Section 9.

Second, whereas Liu et al. [2023] introduce a new information ratio, partly
specialized to predictive sampling, we use the same information ratio as in
Russo and Van Roy [2016] and many subsequent papers. Using the conventional
definition of the information ratio enables us to systematically inherit all
the upper bounds established for stationary settings (See Sec. 6.1). Liu et
al. [2023] provide an upper bound on their modified information ratio for a
particular nonstationary environment they termed ‘modulated $k$-armed
Bernoulli bandit,’ (this is identical to our Example 5) but more research is
required to bound it in other settings.

Finally, due to using a different definitions of the information ratio, our
bounds depend on different notions of the maximial cumulative information
gain. The corresponding term in our Theorem 1 is simply the entropy rate of
the optimal action process (and elsewhere, a mutual information rate). As one
of the most fundamental metrics in information theory, numerous techniques can
be employed to bound this entropy rate as in Section 5.2. The regret bound in
Liu et al. [2023] involves a term which they call cumulative predictive
information. They bound this quantity in the special case of modulated
$k$-armed bandits (equivalent to Example 5). In that example, their bound on
cumulative predictive information is roughly $k$ times larger than our bound
on the entropy rate of the optimal action process. As a result, Liu et al.
[2023] obtain a final regret bound that scales with $k$ (see theorem 5 of Liu
et al. [2023]) whereas our bound scales with $\sqrt{k\log(k)}$ (see Example
6).

##  Appendix C Numerical Experiment in Detail

We here illustrate the detailed procedure of the numerical experiment
conducted in Section 1.1.

##### Generative model.

We say a stochastic process
$(X_{t})_{t\in\mathbb{N}}\sim\mathcal{GP}(\sigma_{X}^{2},\tau_{X})$ if
$(X_{1},\ldots,X_{t})$ follows a multivariate normal distribution satisfying

$\mathbb{E}[X_{i}]=0,\quad\text{Cov}(X_{i},X_{j})=\sigma_{X}^{2}\exp\left(-\frac{1}{2}\left(\frac{i-j}{\tau_{X}}\right)^{2}\right),$

for any $i,j\in[t]$ and any $t\in\mathbb{N}$. Note that this process is
stationary, and given horizon $T$ a sample path $(X_{1},\ldots,X_{T})$ can be
generated by randomly drawing a multivariate normal variable from the
distribution specified by $\sigma_{X}^{2}$ and $\tau_{X}$.

As described in Section 1.1, we consider a nonstionary two-arm Gaussian bandit
with unit noise variance:

$R_{t,a}=\underbrace{\theta_{t}^{\rm cm}+\theta_{t,a}^{\rm
id}}_{:=\mu_{t,a}}+\epsilon_{t,a},\quad\forall a\in\\{1,2\\},t\in\mathbb{N},$

where $\epsilon_{t,a}$’s are i.i.d. noises $\sim\mathcal{N}(0,1^{2})$,
$\big{(}\theta_{t}^{\rm cm}\big{)}_{t\in\mathbb{N}}$ is the common variation
process $\sim\mathcal{GP}(1^{2},\tau^{\rm cm})$, and $\big{(}\theta_{t,a}^{\rm
id}\big{)}_{t\in\mathbb{N}}$ is arm $a$’s idiosyncratic variation process
$\sim\mathcal{GP}(1^{2},\tau^{\rm id})$.

Note that the optimal action process is completely determined by $\theta^{\rm
id}$:

$A_{t}^{*}=\left\\{\begin{array}[]{cc}1&\text{if }\theta_{t,1}^{\rm
id}\geq\theta_{t,2}^{\rm id}\\\ 2&\text{if }\theta_{t,1}^{\rm
id}<\theta_{t,2}^{\rm id}\end{array}\right.,$

and the optimal action switches more frequently when $\tau^{\rm id}$ is small
(compare Figure 6 with Figure 1).

Figure 6: A sample path generated with $\tau^{\rm cm}=\tau^{\rm id}=10$ (cf.,
Figure 1 was generated with $\tau^{\rm cm}=10$ and $\tau^{\rm id}=50$).

Consequently, the problem’s effective horizon $\tau_{\rm
eff}:=1/\mathbb{P}(A_{t}^{*}\neq A_{t-1}^{*})$, defined in (8), depends only
on $\tau^{\rm id}$. To visualize this relationship, we estimate $\tau_{\rm
eff}$ using the sample average of the number of switches occurred over
$T=1000$ periods (averaged across 100 sample paths), while varying $\tau^{\rm
id}$ from $1$ to $100$. See Figure 7. As expected, $\tau_{\rm eff}$ is linear
in $\tau^{\rm id}$ (more specifically, $\tau_{\rm
eff}\approx\pi\times\tau^{\rm id}$ by Rice formula).

Figure 7: The effective time horizon $\tau_{\rm eff}$ as a function of
$\tau^{\rm id}\in\\{1,5,10,\ldots,100\\}$, estimated from 100 sample paths
randomly generated.

##### Tested bandit algorithms.

Given the generative model described above, we evaluate four algorithms –
Thompson sampling (TS), Sliding-Window TS (SW-TS; Trovo et al. [2020]),
Sliding-Window Upper-Confidence-Bound (SW-UCB; Garivier and Moulines [2011]),
and Uniform.

_Thompson sampling_ (TS) is assumed to know the dynamics of latent state
processes as well as the exact values of $\tau^{\rm cm}$ and $\tau^{\rm id}$
(i.e., no model/prior misspecification). More specifically, in each period
$t$, $\pi^{\rm TS}$ draws a random sample $(\tilde{\theta}_{t,1}^{\rm
id},\tilde{\theta}_{t,2}^{\rm id})$ of the latent state $(\theta_{t,1}^{\rm
id},\theta_{t,2}^{\rm id})$ from its posterior distribution, and then selects
the arm
$A_{t}\leftarrow\operatorname*{\mathrm{argmax}}_{a\in\\{1,2\\}}\tilde{\theta}_{t,a}^{\rm
id}$. Here, the posterior distribution of $(\theta_{t,1}^{\rm
id},\theta_{t,2}^{\rm id})$ given the history
$\mathcal{F}_{t-1}=(A_{1},R_{1},\ldots,A_{t-1},R_{t-1})$ is a multivariate
normal distribution that can be computed as follows. Given the past action
sequence $(A_{1},\ldots,A_{t-1})\in\mathcal{A}^{t-1}$, the (conditional)
distribution of $(R_{1},\ldots,R_{t-1},\theta_{t,1}^{\rm id},\theta_{t,2}^{\rm
id})$ is given by

$\left.\left[\begin{array}[]{c}R_{1}\\\ \vdots\\\ R_{t-1}\\\ \theta_{t,1}^{\rm
id}\\\ \theta_{t,2}^{\rm
id}\end{array}\right]\right|(A_{1},\ldots,A_{t-1})\sim\mathcal{N}\left(0\in\mathbb{R}^{(t-1)+2},\left[\begin{array}[]{cc}\Sigma_{t,RR}\in\mathbb{R}^{(t-1)\times(t-1)}&\Sigma_{t,\theta
R}^{\top}\in\mathbb{R}^{(t-1)\times 2}\\\ \Sigma_{t,\theta
R}\in\mathbb{R}^{2\times(t-1)}&\Sigma_{t,\theta\theta}\in\mathbb{R}^{2\times
2}\end{array}\right]\right),$

where the pairwise covariances are given by
$(\Sigma_{t,RR})_{ij}:=\text{Cov}(R_{i},R_{j}|A_{i},A_{j})=\mathbb{I}\\{i=j\\}\cdot\text{Var}(\epsilon_{i,a})+\text{Cov}(\theta_{i}^{\rm
cm},\theta_{j}^{\rm
cm})+\mathbb{I}\\{A_{i}=A_{j}\\}\cdot\text{Cov}(\theta_{i,a}^{\rm
id},\theta_{j,a}^{\rm id})$ for $i,j\in[t-1]$, $(\Sigma_{t,\theta
R})_{ai}:=\text{Cov}(R_{i},\theta_{t,a}^{\rm
id}|A_{i})=\mathbb{I}\\{A_{i}=a\\}\cdot\text{Cov}(\theta_{i,a}^{\rm
id},\theta_{t,a}^{\rm id})$ for $a\in[2]$ and $i\in[t-1]$, and
$\Sigma_{t,\theta\theta}$ is the identity matrix. Additionally given the
reward realizations,

$\left.\left[\begin{array}[]{c}\theta_{t,1}^{\rm id}\\\ \theta_{t,2}^{\rm
id}\end{array}\right]\right|\mathcal{F}_{t-1}\sim\mathcal{N}(\hat{\mu}_{t}\in\mathbb{R}^{2},\hat{\Sigma}_{t}\in\mathbb{R}^{2\times
2}),\quad\text{where}\quad\hat{\mu}_{t}:=\Sigma_{t,\theta
R}\Sigma_{t,RR}^{-1}\left[\begin{array}[]{c}R_{1}\\\ \vdots\\\
R_{t-1}\end{array}\right],\quad\hat{\Sigma}_{t}:=\Sigma_{t,\theta\theta}-\Sigma_{t,\theta
R}\Sigma_{t,RR}^{-1}\Sigma_{t,\theta R}^{\top}.$

_Sliding-Window TS_ is a simple modification of stationary Thompson sampling
such that behaves as if the environment is stationary but discards all
observations revealed before $L$ periods ago. More specifically, in each
period $t$, $\pi^{\rm SW-TS}$ with window length $L$ draws a random sample of
mean rewards $\tilde{\mu}_{t,a}$ from
$\mathcal{N}(\hat{\mu}_{t,a},\hat{\sigma}_{t,a}^{2})$ where

$\hat{\mu}_{t,a}:=\frac{\sum_{s=\max\\{1,t-L\\}}^{t-1}R_{s}\mathbb{I}\\{A_{s}=a\\}}{1+N_{t,a}},\quad\hat{\sigma}_{t,a}^{2}:=\frac{1}{1+N_{t,a}},\quad
N_{t,a}:=\sum_{s=\max\\{1,t-L\\}}^{t-1}\mathbb{I}\\{A_{s}=a\\},$

and then selects the arm
$A_{t}\leftarrow\operatorname*{\mathrm{argmax}}_{a\in\mathcal{A}}\tilde{\mu}_{t,a}$.
Here, $L$ is a control parameter determining the degree of adaptivity.

Similarly, _Sliding-Window UCB_ implements a simple modification of UCB such
that computes UCB indices defined as

$U_{t,a}:=\hat{\mu}_{t,a}+\beta\frac{1}{\sqrt{N_{t,a}}},\quad\hat{\mu}_{t,a}:=\frac{\sum_{s=\max\\{1,t-L\\}}^{t-1}R_{s}\mathbb{I}\\{A_{s}=a\\}}{N_{t,a}},\quad
N_{t,a}:=\sum_{s=\max\\{1,t-L\\}}^{t-1}\mathbb{I}\\{A_{s}=a\\},$

and then selects the arm
$A_{t}\leftarrow\operatorname*{\mathrm{argmax}}_{a\in\mathcal{A}}U_{t,a}$.
Here, $L$ is a control parameter determining the degree of adaptivity, and
$\beta$ is a control parameter determining the degree of exploration.

_Uniform_ is a naïve benchmark policy that always selects one of two arms
uniformly at random. One can easily show that $\bar{\Delta}_{T}(\pi^{\rm
Uniform})\approx 0.57$ in our setup, regardless of the choice of $\tau^{\rm
cm}$ and $\tau^{\rm id}$.

##### Simulation results.

Given a sample path specified by $\theta$, we measure the (pathwise) Cesàro
average regret of an action sequence $A$ as

$\bar{\Delta}_{T}(A;\theta):=\frac{1}{T}\sum_{t=1}^{T}(\mu_{t}^{*}-\mu_{t,A_{t}}),\quad\text{where}\quad\mu_{t,a}:=\theta_{t}^{\rm
cm}+\theta_{t,a}^{\rm id},\quad\mu_{t}^{*}:=\max_{a\in\mathcal{A}}\mu_{t,a}.$

Given an environment specified by $(\tau^{\rm cm},\tau^{\rm id})$, we estimate
the per-period regret of an algorithm $\pi$ using $S$ sample paths:

$\hat{\bar{\Delta}}_{T}(\pi;\tau^{\rm cm},\tau^{\rm
id}):=\frac{1}{S}\sum_{s=1}^{S}\bar{\Delta}_{T}(A^{\pi,(s)};\theta^{(s)}),$

where $\theta^{(s)}$ is the $s^{\text{th}}$ sample path (that is shared by all
algorithms) and $A^{\pi,(s)}$ is the action sequence taken by $\pi$ along this
sample path. In all experiments, we use $T=1000$ and $S=1000$.

We first report convergence of instantaneous regret in Figure 8: we observe
that $\mathbb{E}[\mu_{t}^{*}-\mu_{t,A_{t}}]$ quickly converges to a constant
after some initial transient periods, numerically verifying the conjecture
made in Remark 1. While not reported here, we also observe that the Cesàro
average $\bar{\Delta}_{T}(A;\theta)$ converges to the same limit value as
$T\rightarrow\infty$ in every sample path, suggesting the ergodicity of the
entire system.

Figure 8: Convergence of instantaneous regret
$\mathbb{E}[\mu_{t}^{*}-\mu_{t,A_{t}}]$ in the case of $\tau^{\rm
cm}=\tau^{\rm id}=50$. The solid lines report the instantaneous regret of the
algorithms, averaged across $S=1000$ sample paths, and the dashed horizontal
lines represent the estimated per-period regret.

We next examine the effect of $\tau^{\rm id}$ and $\tau^{\rm cm}$ on the
performance of algorithms, and provide the detailed simulation results that
complement Figure 2 of Section 1.1. While varying $\tau^{\rm id}$ and
$\tau^{\rm cm}$, we measure the per-period regret
$\hat{\bar{\Delta}}_{T}(\pi;\tau^{\rm cm},\tau^{\rm id})$ of algorithms
according to the procedure described above. We observe from Figure 9 that for
every algorithm its performance is mainly determined by $\tau^{\rm id}$,
independent of $\tau^{\rm cm}$, numerically confirming our main claim – the
difficulty of problem can be sufficiently characterized by the entropy rate of
optimal action sequence, $\bar{H}(A^{*})$, which depends only on $\tau^{\rm
id}$. We additionally visualize the upper bound on TS’s regret that our
analysis predicts (Example 7). We also observe that TS performs best across
all settings, perhaps because TS exploits the prior knowledge about
nonstationarity of the environment, whereas SW-TS or SW-UCB performs well when
the window length roughly matches $\tau^{\rm id}$.

Figure 9: The effect of $\tau^{\rm id}$ (left) and $\tau^{\rm cm}$ (right) on
the performance of algorithms. The dashed line in the left plot represents the
upper bound on $\bar{\Delta}_{\infty}(\pi^{\rm TS})$, implied by Corollary 1
and Example 7.