# A Bit Better?
Quantifying Information for Bandit Learning

Adithya M. Devraj
<EMAIL_ADDRESS>Benjamin Van Roy
<EMAIL_ADDRESS>Kuang Xu
<EMAIL_ADDRESS>
( Stanford University, Stanford, CA 94305
)

###### Abstract

The information ratio offers an approach to assessing the efficacy with which
an agent balances between exploration and exploitation. Originally, this was
defined to be the ratio between squared expected regret and the mutual
information between the environment and action-observation pair, which
represents a measure of information gain. Recent work has inspired
consideration of alternative information measures, particularly for use in
analysis of bandit learning algorithms to arrive at tighter regret bounds. We
investigate whether quantification of information via such alternatives can
improve the realized performance of information-directed sampling, which aims
to minimize the information ratio.
Acknowledgement: Financial support from Army Research Office (ARO) grant
W911NF2010055 is gratefully acknowledged.

##  1 Introduction

We consider the multi-arm bandit problem with independent arms. At each time,
an agent executes an action and observes a reward. The objective is to
maximize expected cumulative reward over a long time horizon. This problem
crystallizes the _exploration-exploitation_ dilemma.

The agent’s choice of action must balance between expected immediate reward
and information that may increase subsequent rewards. This calls for
quantification of the information gain, or equivalently, the reduction in
uncertainty, that results from observing the outcome of an action. Taking cue
from information theory, it is natural to consider _Shannon entropy_. This
forms the basis of the _information ratio_ , as originally introduced in [18].
This statistic is the ratio between squared expected instantaneous regret and
the mutual information between the multi-armed bandit and the action-reward
pair, or equivalently, the reduction in entropy resulting from observing the
action and reward. It has been used in the analysis and design of several
bandit algorithms [18, 20, 21, 22, 13, 12, 7, 16].

Information-directed sampling (IDS), as originally introduced by [18], selects
at each time a randomized action that minimizes the information ratio. The
algorithm was shown to achieve, for each $K$ and $T$, worst case Bayesian
regret in excess of optimal by a factor of at most $\sqrt{\log(K)}$, where $T$
is the horizon and $K$ is the number of arms. Indeed, Shannon entropy measures
bits acquired by the agent, and while this notion is fundamental to the field
of communication, it is not immediately clear whether this is the right notion
for balancing exploration and exploitation in bandit learning.

In recent work [13], it was shown that the IDS algorithm with information
ratio defined using another information measure known as _Tsallis entropy_
leads to a better regret bound, that is optimal up to a constant factor.

This paper contributes to understanding how to best quantify information for
bandit learning. Specifically, we investigate whether the performance of IDS
with Tsallis entropy exceeds that with Shannon entropy, as suggested by the
aforementioned regret bounds. Alternatively, the apparent advantage could just
be a figment of current analytic techniques. Our findings are as follows:

  * (i)

We show that it is impossible to improve the aforementioned regret bound for
IDS with Shannon entropy, using the current template for analysis based on the
information ratio.

  * (ii)

We propose a modification to this template, which we use to obtain order
optimal bounds for Thompson sampling using Shannon entropy definition of
information ratio, which was not possible using the previous template.

  * (iii)

We present a computational study which suggests that, despite the gap in
regret bounds, the realized performance of IDS with Shannon entropy
approximately matches that of IDS with Tsallis entropy.

### Literature Review

One of the first finite-time regret bounds for Thompson sampling was derived
in [1]. Building on the techniques of [2, 19], it was first shown in [6] that
Thompson sampling achieves an optimal regret bound, up to a constant factor.

The concepts of information ratio and IDS was first introduced in [18, 21]. A
frequentist version of the algorithm was later developed in [8], and was
extended to a linear partial monitoring setting in [9]. An asymptotically
optimal version of IDS was recently introduced in [10].

It was first shown in [20] that an information ratio based analysis can be
used to obtain regret bounds for Thompson sampling. Identical analysis, but
with a different information measure was shown to produce a tighter regret
bound for Thompson sampling in [13]. Information ratio based analysis has also
been useful in adversarial settings [5, 25, 11, 15].

##  2 Problem Formulation

Consider the probability space $(\Omega,{\mathcal{F}},\mathbb{P})$. All random
variables under consideration are defined with respect to this probability
space.

For $K\geq 2$, let $\mathcal{P}$ be the set of probability measures on
$[0,1]^{K}$, and let $P_{*}$ be a (deterministic) probability distribution
over $\mathcal{P}$. Denote $p^{*}$ to be a random variable that takes values
in ${\mathcal{P}}$ such that $\mathbb{P}(p_{*}\in\cdot)=P_{*}(\cdot)$.

Let ${\mathcal{A}}=\\{1,\ldots,K\\}$ denote the action set, and let the
optimal action $A_{*}$ be a random element of $\mathcal{A}$ that satisfies

$A_{*}\in\operatorname*{arg\,max}_{a\in{\mathcal{A}}}\int_{[0,1]^{K}}r_{a}p_{*}(dr)$

with $r_{a}$ denoting the $a^{\text{th}}$ component of $r\in[0,1]^{K}$. Let
$\boldsymbol{R}\mathbin{:=}\\{R_{t}:t=1,\ldots,T\\}$ be a random sequence that
is i.i.d. conditioned on $p_{*}$, with each element distributed according to
$p_{*}$. In other words, for all $s\neq t$, $R_{s}$ is independent of $R_{t}$
conditioned on $p_{*}$, and

$\mathbb{P}(R_{s}\in\cdot|p_{*})=\mathbb{P}(R_{t}\in\cdot|p_{*})=p_{*}(\cdot)$

We also assume that the reward sequence $\boldsymbol{R}$ is independent of
$A_{*}$, conditioned on $p_{*}$, and define

$R_{*}=\max_{a\in{\mathcal{A}}}\int_{[0,1]^{K}}r_{a}p_{*}(dr)$

###  2.1 Policy and Bayesian Regret

At each time-step $t\geq 0$, an agent selects an action $A_{t}$ based on the
history of observations $H_{t}$, and receives a reward $R_{t+1,A_{t}}$, where

$H_{t}\\!=\\!\\{A_{s},R_{s+1,A_{s}}:s=0,1,2,\ldots,t-1\\}\,,\,\,0\leq t\leq
T-1$

and $R_{s,a}$ denotes the $a^{\text{th}}$ component of $R_{s}\in[0,1]^{K}$.
Formally, a policy $\pi$ is a deterministic function, where, for each $t\geq
1$, $\pi(H_{t})$ specifies a probability distribution over the action set
${\mathcal{A}}$. With abuse of notation we will denote this distribution as
$\pi$, where $\pi(a)=\mathbb{P}(A_{t}=a|H_{t})$ denotes the probability with
which the agent chooses action $a$, given the observed history $H_{t}$. Note
that $H_{0}=\emptyset$.

For the Thompson sampling agent, the action sequence
$\\{A_{t}:t=0,1,\ldots,T-1\\}$ satisfies [24, 23],

$\pi^{\mathrm{TS}}(a)=\mathbb{P}(A_{t}=a|H_{t})=\mathbb{P}(A_{*}=a|H_{t})$ (1)

The instance regret associated with a policy $\pi$ is defined to be the regret
of the agent conditioned on $p_{*}$:

$\mathrm{Regret}(T,p_{*},\pi)=\mathbb{E}\left[\sum_{t=0}^{T-1}(R_{*}-R_{t+1,A_{t}})\Big{|}p_{*}\right]$

The objective of interest in this work is the Bayesian regret, that is an
expectation over the randomness of $p_{*}$:

$\mathrm{Regret}(T,\pi)=\mathbb{E}\left[\sum_{t=0}^{T-1}(R_{*}-R_{t+1,A_{t}})\right]$
(2)

where we have overloaded notation with an understanding that the definition of
$\mathrm{Regret}$ depends on its arguments.

###  2.2 Notations and Definitions

We will denote by short hand
$\mathbb{P}_{t}(\cdot)=\mathbb{P}(\cdot|H_{t})=\mathbb{P}(\cdot|A_{0},R_{1,A_{0}},\ldots,A_{t-1},R_{t,A_{t-1}})$,
and ${\mathbb{E}}_{t}[\cdot]={\mathbb{E}}[\cdot|H_{t}]$.

The relative entropy $D_{\mathrm{KL}}(u||v)$ between probability measures $u$
and $v$ on the same measurable space is

$D_{\mathrm{KL}}(u||v)=\begin{cases}\int\log\Big{(}\frac{du}{dv}\Big{)}\,du\qquad&\text{if}\quad
u\ll v\\\ \infty\qquad&\text{otherwise}\end{cases}$ (3)

For a convex function $F:\Re^{K}\to\Re\cup\\{\infty\\}$, we denote by
$\mathrm{dom}(F)=\\{u:F(u)<\infty\\}$ the domain of $F$. For a convex or
differentiable $F$, the Bregman divergence
$D_{F}:\mathrm{dom}(F)\times\mathrm{dom}(F)\to[0,\infty]$ is defined as

$D_{F}(u,v)\mathbin{:=}F(u)-F(v)-\nabla_{u-v}F(v)\,,\,\,u,v\in\Re^{K}$ (4)

where $\nabla_{u-v}F(v)$ denotes the directional derivative of $F$ in the
direction $u-v$, at $v$. Throughout, we will refer to $F$ as the _potential
function_.

We will denote $\Delta^{K-1}$ to be the $(K\\!-\\!1)$-dimensional probability
simplex: $\Delta^{K-1}=\\{u\in[0,1]^{K}:\|u\|_{1}=1\\}$, and

${{\mathrm{diam}_{F}(\Delta^{K-1})\mathbin{:=}\sup_{u,v\in\Delta^{K-1}}F(u)-F(v)}}$
(5)

The relative entropy $D_{\mathrm{KL}}(u||v)$ between categorical distributions
$u,v\in\Delta^{K-1}$ is the Bregman divergence $D_{F}(u,v)$ associated with
the unnormalized negentropy potential

$F(u)=\sum_{i\in{\mathcal{A}}:u_{i}>0}(u_{i}\log(u_{i})-u_{i})$ (6)

Letting $F$ be the $1/2$-Tsallis entropy, we have

$\displaystyle F(u)$ $\displaystyle=-2\sum_{i\in{\mathcal{A}}}\sqrt{u_{i}}$
(7) $\displaystyle D_{F}(u,v)$
$\displaystyle=\sum_{i\in{\mathcal{A}}:v_{i}>0}\frac{(\sqrt{u_{i}}-\sqrt{v_{i}})^{2}}{\sqrt{v_{i}}}$

###  2.3 Information Ratio and Information Directed Sampling

Given $P_{*}$, and a potential function $F$, denote $\Delta_{t}(a)$ to be the
expected instantaneous regret of taking action $a\in{\mathcal{A}}$ at time
$t$:

$\Delta_{t}(a)\mathbin{:=}{\mathbb{E}}_{t}\big{[}R_{*}-R_{t+1,a}\big{]}$

and $g_{t}^{F}(a)$ to be the expected reduction in entropy,

$g_{t}^{F}(a)\mathbin{:=}{\mathbb{E}}_{t}\big{[}D_{F}\big{(}\mathbb{P}_{t+1}(A_{*}\in\cdot),\mathbb{P}_{t}(A_{*}\in\cdot)\big{)}\mid
A_{t}=a\big{]}$

For a policy $\pi$, we overload the notation for $\Delta_{t}(\cdot)$ and
$g_{t}^{F}(\cdot)$ and denote

$\displaystyle\Delta_{t}(\pi)$
$\displaystyle=\sum_{a\in{\mathcal{A}}}\pi(a)\Delta_{t}(a)$ $\displaystyle
g_{t}^{F}(\pi)$ $\displaystyle=\sum_{a\in{\mathcal{A}}}\pi(a)g_{t}^{F}(a)$

For any potential $F$ that satisfies $\mathrm{diam}_{F}(\Delta^{K-1})<\infty$,
the information ratio $\Gamma_{t}^{F}(\pi)$ associated with policy $\pi$ at
time-step $t$ is

$\Gamma_{t}^{F}(\pi)\mathbin{:=}\frac{\big{[}\Delta_{t}(\pi)\big{]}^{2}}{g_{t}^{F}(\pi)}$
(8)

The IDS algorithm greedily minimizes the information ratio at each time-step
[18, 21]:

$\pi^{\mathrm{IDS}}\in\operatorname*{arg\,min}_{\pi}\,\,\Gamma_{t}^{F}(\pi)$
(9)

The original IDS algorithm in [18, 21] considered the special case of $F$
being the negentropy potential. We will refer to the resulting algorithm as
Shannon-IDS or $\mathrm{NDS}$. Extension to $F$ being $1/2$-Tsallis entropy
was considered in [13]. We refer to the resulting algorithm as Tsallis-IDS or
$\mathrm{TDS}$.

##  3 Information Ratio and Bayesian Regret

Here, we review a general information ratio based analysis technique that can
be used to obtain upper bounds for the Bayesian regret of any policy.

Given $T\in\mathbb{N}$, and $F:\Re^{K}\to\Re\cup\\{\infty\\}$, denote
${\overline{{\Gamma}}}^{F}_{T}(\pi)$ to be the average expected information
ratio corresponding to policy $\pi$:

$\displaystyle{\overline{{\Gamma}}}^{F}_{T}(\pi)\mathbin{:=}\frac{1}{T}\,\,{\mathbb{E}}\left[\sum_{t=0}^{T-1}\Gamma_{t}^{F}(\pi)\right]$
(10)

Theorem 3.1 provides an upper bound for the regret of any policy $\pi$ in
terms of ${\overline{{\Gamma}}}^{F}_{T}(\pi)$.

######  Theorem 3.1.

For any policy $\pi$, $T\in\mathbb{N}$, and $K\geq 2$,

${\mathrm{Regret}}(T,\pi)\leq\sqrt{{\overline{{\Gamma}}}^{F}_{T}(\pi)\cdot{\mathrm{diam}_{F}(\Delta^{K-1})}\cdot
T}$ (11)

where $F$ is convex, and satisfies $\mathrm{diam}_{F}(\Delta^{K-1})<\infty$.

The proof is very similar to the proof of Theorem 3 in [13] and is provided in
Appendix D. Similar versions of the result previously appeared in [20, 21].

For any potential function $F$, and policy $\pi$, let $\gamma_{F}(\pi)$ be a
uniform upper bound on the information ratio:

$\Gamma_{t}^{F}(\pi)\leq\gamma_{F}(\pi)\,\,a.s.,\quad t=0,1,\ldots$

The following result is an immediate corollary to Theorem 3.1.

######  Corollary 3.2.

For any policy $\pi$, $T\in\mathbb{N}$, and $K\geq 2$,

${\mathrm{Regret}}(T,\pi)\leq\sqrt{\gamma_{F}(\pi)\cdot{\mathrm{diam}_{F}(\Delta^{K-1})}\cdot
T}$ (12)

where $F$ is convex, and satisfies $\mathrm{diam}_{F}(\Delta^{K-1})<\infty$.

Table 1 summarizes the best known upper bounds for the information ratio and
$\mathrm{diam}_{F}(\Delta^{K-1})$ for the two potential functions of interest.

$F$ | $\gamma_{F}(\pi^{\mathrm{TS}})$ | $\gamma_{F}(\pi^{\mathrm{NDS}})$ | $\gamma_{F}(\pi^{\mathrm{TDS}})$ | $\mathrm{diam}_{F}(\Delta^{K-1})$
---|---|---|---|---
$1/2$-Tsallis | $\sqrt{K}$ | - | $\sqrt{K}$ | $2\sqrt{K}$
Negentropy | ${K}/{2}$ | ${K}/{2}$ | - | $\log(K)$
Table 1: Different potential functions $F$ and the corresponding best known
upper bounds on the information ratio and $\mathrm{diam}_{F}(\Delta^{K-1})$.

The following Proposition 3.3 is a direct consequence of Corollary 3.2 and the
bounds in Table 1.

######  Proposition 3.3.

For all $T\in\mathbb{N}$ and $K\geq 2$,

$\displaystyle{\mathrm{Regret}}(T,\pi^{\mathrm{TS}})$
$\displaystyle\leq\sqrt{2KT}$ (13a)
$\displaystyle{\mathrm{Regret}}(T,\pi^{\mathrm{TDS}})$
$\displaystyle\leq\sqrt{2KT}$ (13b)
$\displaystyle{\mathrm{Regret}}(T,\pi^{\mathrm{NDS}})$
$\displaystyle\leq\sqrt{\frac{1}{2}KT\log(K)}$ (13c)

The proof of (13a) and (13b) of Proposition 3.3 can be found in [13] (see
Corollary 4 and Lemma 7), and the proof of (13c) in [21] (see Corollary 1 and
Proposition 2). A proof overview is provided in Appendix A.

It is clear from Proposition 3.3 that the bound for Tsallis-IDS exhibits a
more graceful dependence on $K$, compared to Shannon-IDS. To obtain a
$\sqrt{KT}$ bound for Shannon-IDS, one will need a ${K/\log(K)}$ upper bound
on $\gamma_{F}(\pi^{\mathrm{NDS}})$, so that
$\gamma_{F}(\pi^{\mathrm{NDS}})\cdot\mathrm{diam}_{F}(\Delta^{K-1})$ will have
an order $K$ upper bound. Theorem 16 in the following section shows that this
is not possible.

##  4 A Didactic Example

The goal here is to show that it is impossible to improve the regret bound for
Shannon-IDS using the current analysis. We will also observe that these bounds
do not reflect the true behavior of the algorithm in practice, and identify a
possible explanation for this.

From here on, unless otherwise mentioned, $F$ refers to the negentropy
potential. We will also restrict our theoretical results to the following
family of bandit problems that has been a standard for proving lower bounds
for bandit algorithms: see for example the proof of Theorem 5.1 in [3] and
also the proof of Theorem 1 in [17].

######  Example 4.1.

Let $p\in(0,1)$ and $\varepsilon\in(0,1-p)$. For $1\leq i\leq K$, denote
$p_{*}^{i}\in{\mathcal{P}}$ such that, for each $1\leq k\leq K$, the marginals
are

$p_{*}^{i}(k)=\begin{cases}\mathrm{Bernoulli}(p+\varepsilon)\,\qquad&\text{if}\,\,i=k\\\
\mathrm{Bernoulli}(p)\,\qquad&\text{if}\,\,i\neq k\end{cases}$ (14)

$P_{*}$ is a probability distribution on ${\mathcal{P}}$ such that

$P_{*}(p_{*}^{i})={1}/{K}\,,\qquad 1\leq i\leq K$ (15)

The following result establishes a lower bound on the Shannon information
ratio using Example 4.1.

######  Theorem 4.1.

Consider the bandit problem in Example 15. For all $K\geq 2$, there exists
$t\geq 0$, $p\in(0,1)$, and $\epsilon^{*}\in(0,1-p)$, such that, for all
$\epsilon\in(0,\epsilon^{*}]$, and any policy $\pi$,

$\Gamma_{t}^{F}(\pi)\geq{\frac{K}{20}}\qquad a.s..$ (16)

The proof of Theorem 16 is contained in Appendix B. This result shows that the
upper bounds in the second row of Table 1 are tight, up to a constant scaling.

Theorem 16 further implies that it is impossible to get an order $\sqrt{KT}$
bound for Shannon-IDS using Corollary 3.2: since
$\gamma_{F}(\pi^{\mathrm{NDS}})\geq{K}/{20}$, and
$\mathrm{diam}_{F}(\Delta^{K-1})=\log(K)$,

$\sqrt{\gamma_{F}(\pi^{\mathrm{NDS}})\cdot{\mathrm{diam}_{F}(\Delta^{K-1})}\cdot
T}\geq\sqrt{\frac{1}{20}KT\log(K)}$

On the other hand, the same line of analysis yields a $\sqrt{2KT}$ bound for
Tsallis-IDS.

The gap between the upper bounds of Shannon-IDS and Tsallis-IDS raises the
immediate question of whether it reflects real difference in practical
performance of the algorithms. To obtain some intuition, we conduct
simulations by applying Thompson sampling, Shannon-IDS and Tsallis-IDS to the
bandit problem in Example 4.1.

Figure 1: Expected cumulative Regret of Thompson sampling, Shannon-IDS and
Tsallis-IDS applied to Example 15. The shaded regions indicate $2\sigma$
confidence intervals.

In Figure 1 we plot the expected cumulative regret of the three algorithms for
$K\in\\{40,50,80,100\\}$. The details of the experiments are postponed to
Section 6, but the key observation we make is that there is little difference
between the performances of Shannon-IDS and Tsallis-IDS. We certainly don’t
observe the kind of performance gap suggested by Proposition 3.3: For $K=100$,
and $T=2\times 10^{6}$, (13b) and (13c) suggest a performance gap of

$\sqrt{KT}\left(\sqrt{\frac{1}{2}\log(K)}-\sqrt{2}\right)=1.5\times 10^{3}$

which is clearly not the case.

Figure 2: Empirical average and $2\sigma$ confidence intervals of
$\Gamma_{t}^{F}(\pi^{\mathrm{IDS}})$ corresponding to Example 15.

To understand the mystery behind the discrepancy between the theory and
practical performance, in Figure 2 we plot the empirical average of
$\Gamma_{t}^{F}(\pi^{\mathrm{NDS}})$ and $\Gamma_{t}^{F}(\pi^{\mathrm{TDS}})$
scaled by $\mathrm{diam}_{F}(\Delta^{K-1})$. The scaling makes sure that the
units corresponding to the two plots match. The dashed plots indicate the
worst case bounds on the information ratio for each of the two algorithms.

The plots in Figure 2 identify a plausible explanation for the gap in theory
and practice: The theoretical results use worst case information ratio to
bound the regret, but $\Gamma_{t}^{F}$ is clearly a time-varying quantity.
More importantly, even though at $t=0$,
${\mathbb{E}}[\Gamma_{t}^{F}(\pi^{\mathrm{IDS}})]$ closely matches the worst-
case bounds, it is monotonically decreasing for $t>0$. This suggests that it
is crucial to take into account the temporal nature of the information ratio
in analysis. And based on Figure 2, an application of Theorem 3.1 will predict
similar performance bounds for Shannon-IDS and Tsallis-IDS, consistent with
our observation in Figure 1.

##  5 Accounting for Temporal Variation of Information Ratio

The lower bound we established in Section 4 implies that it is not possible to
obtain an order $\sqrt{KT}$ regret bound for Shannon-IDS using a particular
template for analysis, which depends on the information ratio through its
maximum over time. Our experimental results suggest it may be possible to
establish such a bound via an analysis that accounts for temporal variation of
the information ratio.

In this section, we propose a new template for analysis. We will use this to
obtain an order $\sqrt{KT}$ bound for Thompson sampling via studying the
Shannon information ratio, and in particular, its time variation. Similarly
with Shannon-IDS, the bound for Thompson sampling can not be established
without taking this time variation into account.

Theorem 5.1 below can be regarded as a generalization of Corollary 3.2. The
key difference between the two results is that Theorem 5.1 accounts for the
time-varying nature of information ratio, whereas Corollary 3.2 does not.

######  Theorem 5.1.

For all $T\in\mathbb{N}$, $K\geq 2$,
$\boldsymbol{\delta}=\\{\delta_{t}:\delta_{t}\in[0,1]\,,0\leq t\leq T-1\\}$,
$\gamma_{FX}\in\Re^{+}\cup\\{\infty\\}$, and policies $\pi$, such that

$\mathbb{P}\left(\Gamma_{t}^{F}(\pi)\leq\gamma_{FX}\right)\geq
1-\delta_{t}\,,\quad t=0,\ldots,T-1$

we have

$\displaystyle{\mathrm{Regret}}(T,\pi)\\!\leq\\!\sqrt{\gamma_{FX}\\!\cdot\\!{\mathrm{diam}_{F}(\Delta^{K-1})}\cdot
T}+\varepsilon\\!\cdot\\!\sum_{t=0}^{T-1}\delta_{t}$

The proof of Theorem 5.1 is contained in Appendix D. Note that the result
coincides with Corollary 3.2 in the special case $\delta_{t}=0$,
$t=0,\ldots,T-1$.

Proposition 18 is an application of Theorem 5.1, and establishes an order
$\sqrt{KT}$ regret bound for Thompson sampling via an analysis of the Shannon
information ratio.

######  Proposition 5.2.

For all $K\geq 2$, and $t\geq 0$,

$\mathbb{P}\left(\Gamma_{t}^{F}(\pi^{\mathrm{TS}})\leq 8\right)\geq
1-\frac{1}{\varepsilon}\cdot\sqrt{\frac{8K}{t}}$ (17)

Consequently, for all $T\in\mathbb{N}$, $K\geq 2$,

${\mathrm{Regret}}(T,\pi^{\mathrm{TS}})\leq 6\sqrt{2KT}$ (18)

The proof of (17) is presented in Section E of the appendix. The regret bound
(18) then follows from Theorem 5.1, by letting
$\delta_{t}=\frac{1}{\varepsilon}\cdot\sqrt{\frac{8K}{t}}$,
$\pi=\pi^{\mathrm{TS}}$, and $\gamma_{FX}=8$.

##  6 Computational Results

In this section we present numerical results that reiterate the key points of
our main theoretical results. We consider two sets of experiments: (i) Example
15 that was used to establish a lower bound in Theorem 16, and (ii) the Beta-
Bernoulli setting.

In each of the settings, we compare performances of three algorithms in terms
of their expected cumulative regret: (i) Thompson sampling that assigns action
probabilities according to (1), (ii) Shannon-IDS: (9) with $F$ defined in (6),
and (iii) Tsallis-IDS: (9) with $F$ defined in (7).

In addition to comparing algorithm performance, we also estimate and compare
Shannon information ratio and Tsallis information ratio in each experiment.
This gives us an under-the-hood view of each algorithm.

###  6.1 Experimental Results for Example 15

Recall Example 15 defined in (14) and (15).

We show results for $K\in\\{40,50,80,100\\}$, and in each case, we let
$p=1/2$, and $\epsilon=p/K$. The total number of time-steps $T$ for each
experiment was chosen to satisfy

$T\geq\frac{2}{5}\frac{K^{4}}{K-1}\log(K)$

These choices of $p$, $\epsilon$, and $T$ satisfy the conditions required to
establish a stronger lower bound than the one in Theorem 16 (details are
contained Appendix B). Note that for $K=80$ and $100$, the best known regret
bound for Shannon-IDS, which is $\sqrt{\frac{1}{2}KT\log(K)}$, is larger than
the best known regret bound for Tsallis-IDS, which is $\sqrt{2KT}$.

At each $t=0,\ldots,T-1$, an agent selections an action
$A_{t}\in{\mathcal{A}}$ and observes $R_{t+1,A_{t}}\in\\{0,1\\}$. Given
$H_{t}=\\{A_{s},R_{s+1,A_{s}}:s=0,1,2,\ldots,t-1\\}$, we can compute the
posterior distribution on the optimal action:

$\mathbb{P}_{t}(A_{*}=a)=\frac{(1+\epsilon/p)^{s_{a}(t)}(1-\epsilon/(1-p))^{f_{a}(t)}}{\sum_{a^{\prime}\in{\mathcal{A}}}(1+\epsilon/p)^{s_{a^{\prime}}(t)}(1-\epsilon/(1-p))^{f_{a^{\prime}}(t)}}$

where,

$\displaystyle s_{a}(t)$
$\displaystyle=\sum_{s=1}^{t-1}R_{s+1,A_{s}}\cdot\mathbb{I}\\{A_{s}=a\\}$
$\displaystyle f_{a}(t)$
$\displaystyle=\sum_{s=1}^{t-1}(1-R_{s+1,A_{s}})\cdot\mathbb{I}\\{A_{s}=a\\}$

are the total number of $1$’s and $0$’s observed from arm $a$ at time $t-1$.
Using the above closed form expressions, it is straightforward to obtain the
three algorithms from their definitions – complete implementation details are
in Appendix F.

In Figure 1 we plot the expected cumulative regret of the three algorithms.
The empirical average of the cumulative regret was obtained by simulating
$N=200$ independent trajectories for $K\in\\{40,50,80\\}$, and $N=160$ for
$K=100$. The shaded regions indicates $2\sigma$ confidence intervals.

It is clear from these plots that the two IDS algorithms have better
performance compared to Thompson sampling. The performance difference between
Shannon-IDS and Tsallis-IDS is within a margin of statistical error.

Figure 3: Empirical average and $2\sigma$ confidence intervals of
$\Gamma_{t}^{F}(\pi^{\mathrm{TS}})$ corresponding to the counter Example 15.

In Figure 2 we plot the estimate of
${\mathbb{E}}[\Gamma_{t}^{F}(\pi^{\mathrm{IDS}})]\times\mathrm{diam}_{F}(\Delta^{K-1})$
as a function of $t$, for the two IDS algorithms. The scaling of the
information ratio by $\mathrm{diam}_{F}(\Delta^{K-1})$ ensures that we are
comparing plots with the same units. It is clear that using empirical
estimates of
${\mathbb{E}}[\Gamma_{t}^{F}(\pi^{\mathrm{IDS}})]\times\mathrm{diam}_{F}(\Delta^{K-1})$
in Theorem 3.1 will result in near-identical performance bounds for Shannon-
IDS and Tsallis-IDS. This is consistent with our observations in Figure 1. The
dashed lines indicate the worst case bounds of
$\Gamma_{t}^{F}(\pi^{\mathrm{IDS}})\times\mathrm{diam}_{F}(\Delta^{K-1})$
which was used to obtain performance bounds in Corollary 3.2. The plots
suggest that this will surely lead to looser bounds. More importantly,
comparing algorithms based on these looser bounds may lead to a premature
conclusion that Tsallis-IDS is better than Shannon-IDS.

In Figure 3 we plot the estimate of
${\mathbb{E}}[\Gamma_{t}^{F}(\pi^{\mathrm{TS}})]\times\mathrm{diam}_{F}(\Delta^{K-1})$
for the two cases of $F$ being negentropy potential, and $1/2$-Tsallis
entropy. We make similar conclusions as before: Though the worst case upper
bound on these quantities can be significantly different for the two different
information ratios, when plotted as a function of time, both are observed to
be converging to zero. In-fact, we observe that the Shannon information ratio
is converging to zero faster than the Tsallis information ratio, implying that
an application of Theorem 3.1 will result in a better regret bound for
Thompson sampling, with Shannon information ratio analysis.

Figure 4: Expected cumulative Regret of Thompson sampling, Shannon IDS and
Tsallis IDS applied to Beta-Bernoulli bandits with $K\in\\{20,40,60,80\\}$.
Shaded regions indicate $2\sigma$ confidence intervals.

###  6.2 Beta Bernoulli

In our second set of experiments, we consider a $K$-arm bandit problem with
independent arms and Bernoulli rewards. Specifically, we consider the Beta-
Bernoulli setting, wherein the mean reward for each of the $K$ arms are
independently sampled from $\mathrm{Beta}(1,1)$, which is the uniform
distribution on $[0,1]$. We show results for $K\in\\{20,40,60,80\\}$.

While the implementation of Thompson sampling for this setting is well-known,
the implementation of Shannon-IDS and Tsallis-IDS is not straightforward. In-
fact, it is practically not possible to exactly compute the information ratio
at each time-step, as it involves evaluating integrals that don’t have nice
closed-form expressions. We can, however, compute approximations of the
information ratio, that can be used to obtain approximate versions of the two
IDS algorithms. Complete details of implementation are contained in Appendix F
(also see Section 6.1 of [21]; in particular Example 8 and Algorithm 2).

In Figure 4 we compare the performances of Thompson sampling, Shannon-IDS and
Tsallis-IDS by plotting the expected cumulative regret. The empirical average
of the cumulative regret was obtained by running $N=500$ independent runs for
each $K$. Once again, we notice that there’s little difference in performances
of the two IDS algorithms. Both of them are clearly superior to Thompson
sampling.

In Figures 5 and 6 we plot the estimates of
${\mathbb{E}}[\Gamma_{t}^{F}(\pi^{\mathrm{IDS})}]$ and
${\mathbb{E}}[\Gamma_{t}^{F}(\pi^{\mathrm{TS}})]$ with $2\sigma$ confidence
intervals. We observe that the information ratios decrease much more quickly
in this setting, compared to the counter example in Section 6.1. Hence the
$\log$-scale for the $Y$-axes. More importantly, the scaled Shannon
information ratio is consistently smaller than the scaled Tsallis information
ratio, except at $t=0$.

These observations reassert our key point: Accounting for temporal variation
of information ratio in regret analysis is crucial for obtaining tight bounds.
These new bounds _may_ have different implications compared to the existing
bounds.

Figure 5: Empirical average and $2\sigma$ confidence intervals of
$\Gamma_{t}^{F}(\pi^{\mathrm{IDS}})$ as a function of $t$ for the Beta-
Bernoulli experiment. Figure 6: Empirical average and $2\sigma$ confidence
intervals of $\Gamma_{t}^{F}(\pi^{\mathrm{TS}})$ as a function of $t$ for the
Beta-Bernoulli experiment.

##  7 Example: Sparse Linear Bandits with Non-Uniform Prior

The experimental results we have shown so far do not indicate a clear
favourite between Shannon-IDS and Tsallis-IDS. In this section we explore
whether it is possible to identify a problem instance where one algorithm is
clearly superior to the other.

Ideally, we would have liked to design a multi-arm bandit problem that exactly
falls under our problem formulation of Section 2, and then compare the two IDS
algorithms on this problem. However, we were unable to find such an example.
Instead, we propose here a sparse linear bandit problem, where the agent makes
an observation in addition to the reward. We will show that Tsallis-IDS
performs strictly worse than Shannon-IDS in this class of problems.

The example we propose is closely related to Example 3 of [21]. For
simplicity, assume $K=2^{m}+1$ for some $m\in\mathbb{N}$. Given $K\geq 3$, let
the action set ${\mathcal{A}}=\\{0,1\\}^{K}$. For $1\leq i\leq K$, denote
$e_{i}$ to be the $i^{\text{th}}$ basis vector: $e_{i}\in\Re^{K}$,
$e_{i}(k)=\mathbb{I}_{i=k}$. The prior is assumed to be non-uniform:

$P_{*}(e_{i})=\begin{cases}\frac{1}{2}\,\qquad&\text{if}\,\,\quad i=1\\\
\frac{1}{2(K-1)}\,\qquad&\text{if}\,\,\quad i\neq 1\end{cases}$

Upon choosing an action $a\in{\mathcal{A}}$, the agent receives a reward
$R_{t+1,a}$ at time-step $t$, where

$R_{t+1,a}=\begin{cases}1\,\qquad&\text{if}\quad a=p_{*}\\\
-1\,\qquad&\text{if}\quad a=e_{i}\,,1\leq i\leq K,a\neq p_{*}\\\
0\,\qquad&\text{otherwise}\end{cases}$

In addition to receiving a reward at each time-step, the agent also observes
$y=a^{\intercal}p_{*}$.

Since the optimal action is $p_{*}$, the goal of any optimal agent should be
to identify $p_{*}$ as quickly as possible. Therefore, it is obvious that the
optimal action in the first iteration is either $a=e_{1}$ or
$a=[0,1,\ldots,1]$. Either of these actions will reveal the true parameter
$p_{*}$ with probability $1/2$, and with the other $1/2$ probability,
$p_{*}\in\\{e_{2},\ldots,e_{K}\\}$. In addition, both these actions result in
the same expected instantaneous regret of $0$.

Suppose $p_{*}$ is not revealed in the first iteration, the optimal sequence
of actions from the second iteration on-wards is to perform a binary search.
That is, in the second iteration, first half of the last $K-1$ components of
$a$ are chosen to be ones, and the second half of the last $K-1$ components
are chosen to be zeros, and the process repeats until $p_{*}$ is identified.
In the worst case, the total number of iterations required to find the optimal
action via this procedure is $m+1$ iterations.

Simple computations show that the Shannon-IDS algorithm precisely follows
these steps. This is due to the fact that these sequence of actions result in
maximum expected reduction in Shannon entropy at each iteration. On the other
hand, simple computation shows that for $K\geq 5$, picking a sub-optimal
action $a=[1,1,0,\ldots,0]$ in the first iteration results in greater expected
reduction in $1/2$-Tsallis entropy compared to action $a=[1,0,\ldots,0]$ or
$a=[0,1,\ldots,1]$. Since all these actions incur $0$ expected reward, the
Tsallis-IDS algorithm _does not_ choose one of the two optimal actions at
$t=0$. This implies that the Tsallis-IDS algorithm provably takes a greater
number of iterations to identify $p_{*}$ in expectation.

An interesting observation we make is that the Thompson sampling agent will
require order $K$ iterations in expectation to identify $p_{*}$. This is
because it assigns non-zero probabilities only to actions
$a\in\\{e_{1},e_{2},\ldots,e_{K}\\}$, and rules out a single action in each
iteration.

##  8 Conclusion

While the sparse linear bandit problem in Section 7 was very much a stylized
example, it demonstrates the existence of a class of problems where
quantifying information via Shannon entropy is clearly better.

We searched for a problem where we could demonstrate the advantage of using
Tsallis-IDS over Shannon-IDS in a similar manner, but we did not succeed. In
fact, the original motivation for considering Example 15 was to design a hard
problem where Shannon-IDS will fail. However, despite the gap in the
performance bounds, we showed that in practice, the realized performance gap
between the two algorithms is negligible. Whether there exists a bandit
problem where Tsallis-IDS is provably better than Shannon-IDS remains an open
question.

Additional theoretical and computational results identified a plausible
explanation for the gap in the bounds: Existing techniques that upper bound
the regret use worst case bounds on the information ratio, however, this
quantity is highly time-varying, and taking into account this property is
crucial to obtaining tighter bounds.

While the results presented in this paper are preliminary, it opens up a lot
of avenues for future research. Few of them are listed below.

  * (i)

A challenging work for the future is to generalize the order $\sqrt{KT}$ bound
in Proposition 18 for any $P_{*}$, for both Thompson sampling and Shannon-IDS.
This result, if true, will close the gap in performance bounds for the two IDS
algorithms.

  * (ii)

Our paper restricted to the case wherein the information gain (and
consequently the information ratio) was defined with respect to the posterior
on the optimal action. Extension of the results to general continuous action
spaces, such as general linear bandits requires defining a notion of
_satisficing_ action, that can be thought of as an approximation to the
optimal action that is easier to learn. In this set-up, the information gain
is defined with respect to the satisficing action [22, 7]. While the rate-
distortion theory provides natural tools for analysis Shannon-IDS in this
framework, it is interesting to find out if an analog exists for Tsallis-IDS.

  * (iii)

An interesting future work is figuring out how to automate the choice of
information gain function depending on the application. While we have still
not identified a problem where Tsallis-IDS is provably better, the existence
of such a problem can not be ruled out, and a generic algorithm that adapts
the information gain function according to a specific application may be
extremely useful in practice.

## References

  * [1] S. Agrawal and N. Goyal.  Further optimal regret bounds for thompson sampling.  In Artificial intelligence and statistics, pages 99–107. PMLR, 2013\.
  * [2] J.-Y. Audibert and S. Bubeck.  Minimax policies for adversarial and stochastic bandits.  In COLT, pages 217–226, 2009.
  * [3] P. Auer, N. Cesa-Bianchi, Y. Freund, and R. E. Schapire.  The nonstochastic multiarmed bandit problem.  SIAM journal on computing, 32(1):48–77, 2002.
  * [4] S. Bubeck, N. Cesa-Bianchi, et al.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  Foundations and Trends® in Machine Learning, 5(1):1–122, 2012.
  * [5] S. Bubeck, O. Dekel, T. Koren, and Y. Peres.  Bandit convex optimization:$\backslash$sqrtt regret in one dimension.  In Conference on Learning Theory, pages 266–278. PMLR, 2015.
  * [6] S. Bubeck and C.-Y. Liu.  Prior-free and prior-dependent regret bounds for thompson sampling.  In 2014 48th Annual Conference on Information Sciences and Systems (CISS), pages 1–9. IEEE, 2014.
  * [7] S. Dong and B. Van Roy.  An information-theoretic analysis for thompson sampling with many actions.  In Advances in Neural Information Processing Systems, pages 4157–4165, 2018.
  * [8] J. Kirschner and A. Krause.  Information directed sampling and bandits with heteroscedastic noise.  In Conference On Learning Theory, pages 358–384. PMLR, 2018.
  * [9] J. Kirschner, T. Lattimore, and A. Krause.  Information directed sampling for linear partial monitoring.  In Conference on Learning Theory, pages 2328–2369. PMLR, 2020.
  * [10] J. Kirschner, T. Lattimore, C. Vernade, and C. Szepesvári.  Asymptotically optimal information-directed sampling.  arXiv preprint arXiv:2011.05944, 2020.
  * [11] T. Lattimore.  Improved regret for zeroth-order adversarial bandit convex optimisation.  arXiv preprint arXiv:2006.00475, 2020.
  * [12] T. Lattimore and A. György.  Mirror descent and the information ratio.  arXiv preprint arXiv:2009.12228, 2020.
  * [13] T. Lattimore and C. Szepesvári.  An information-theoretic approach to minimax regret in partial monitoring.  arXiv preprint arXiv:1902.00470, 2019.
  * [14] T. Lattimore and C. Szepesvári.  Bandit algorithms.  Cambridge University Press, 2020.
  * [15] T. Lattimore and C. Szepesvári.  Exploration by optimisation in partial monitoring.  In Conference on Learning Theory, pages 2488–2515. PMLR, 2020.
  * [16] X. Lu and B. Van Roy.  Information-theoretic confidence bounds for reinforcement learning.  In Advances in Neural Information Processing Systems, pages 2461–2470, 2019.
  * [17] S. Mannor and J. N. Tsitsiklis.  The sample complexity of exploration in the multi-armed bandit problem.  Journal of Machine Learning Research, 5(Jun):623–648, 2004.
  * [18] D. Russo and B. Van Roy.  Learning to optimize via information-directed sampling.  In Advances in Neural Information Processing Systems, pages 1583–1591, 2014.
  * [19] D. Russo and B. Van Roy.  Learning to optimize via posterior sampling.  Mathematics of Operations Research, 39(4):1221–1243, 2014.
  * [20] D. Russo and B. Van Roy.  An information-theoretic analysis of thompson sampling.  The Journal of Machine Learning Research, 17(1):2442–2471, 2016\.
  * [21] D. Russo and B. Van Roy.  Learning to optimize via information-directed sampling.  Operations Research, 66(1):230–252, 2018.
  * [22] D. Russo and B. Van Roy.  Satisficing in time-sensitive bandit learning.  arXiv preprint arXiv:1803.02855, 2018.
  * [23] D. Russo, B. Van Roy, A. Kazerouni, I. Osband, and Z. Wen.  A tutorial on thompson sampling.  arXiv preprint arXiv:1707.02038, 2017.
  * [24] W. R. Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  Biometrika, 25(3/4):285–294, 1933.
  * [25] J. Zimmert and T. Lattimore.  Connections between mirror descent, thompson sampling and the information ratio.  arXiv preprint arXiv:1905.11817, 2019.

Appendix

## Overview of the Appendix

First, we introduce notation that is used throughout the Appendix.

In Section A we give a proof overview of Proposition 3.3. We also discuss the
implications of the result.

In Section B, we provide the proof of Theorem 16.

In Section C we strengthen the lower bound of Theorem 16. Specifically, we
show that the lower bound carries through even with an extended definition of
information ratio (see (42)) that includes a “slack” parameter (as in [22,
13]). We also show that replacing a uniform (in time) almost sure upper bound
on the information ratio, such as the one used in Corollary 3.2 (and in
previous literature), with a uniform (in time) _high probability_ upper bound
is insufficient to obtain an order $\sqrt{KT}$ bound for _any_ policy, using
Shannon information ratio analysis. These results highlight the need for
analysis techniques that take into account the temporal nature of information
ratio.

In Section D we provide proofs of Theorems 3.1 and 5.1. We also provide a new
template for analysis of the Bayesian regret of any policy in the form of
Theorem D.2, which is a generalization of Theorem 5.1. Contrary to previous
analysis techniques, the proposed method accounts for he time-varying nature
of the information ratio.

In Section E we provide the proof of Proposition 18. The proof will use the
results of Section D to prove an order $\sqrt{KT}$ bound for Thompson sampling
using Shannon information ratio analysis.

Section F contains details of our numerical results, as well as some
additional experimental results.

## Notations

For a random variable $X$, we will denote by $P_{t}(X)$, the probability
distribution function of $X$, conditioned on $H_{t}$:

$P_{t}(X)\equiv\mathbb{P}_{t}(X\in\cdot)$

Similarly, we denote

$\displaystyle P_{t}(X|Y)$ $\displaystyle\equiv\mathbb{P}_{t}(X\in\cdot|Y)$
$\displaystyle P_{t}(X|Y=y)$
$\displaystyle\equiv\mathbb{P}_{t}(X\in\cdot|Y=y)$

Unless otherwise mentioned, throughout the supplementary material, $F$ is the
negentropy potential:

$F(u)=\sum_{i\in{\mathcal{A}}:u_{i}>0}(u_{i}\log(u_{i})-u_{i})\,,\qquad
u\in\Delta^{K-1}$

##  Appendix A Proof Overview of Proposition 3.3

###  A.1 Proof overview

It was shown in [13] that the information ratio for Thompson sampling
satisfies,

$\Gamma^{F}_{t}(\pi^{\mathrm{TS}})\leq\sqrt{K}\quad a.s.,\quad t=0,1,\ldots$
(19)

where $F$ is the $1/2$-Tsallis entropy. Using the fact that
${\mathrm{diam}_{F}(\Delta^{K-1})}\leq 2\sqrt{K}$, and applying Theorem 3.1,
we obtain (13a). The bound in (13b) follows similar arguments: With the same
potential $F$, using (9) and (19), we can show that,

$\Gamma^{F}_{t}(\pi^{\mathrm{TDS}})\leq\sqrt{K}\quad a.s.,\quad t=0,1,\ldots$

Applying Theorem 3.1 once again yields (13b).

Deriving the bound in (13c) naturally requires consideration of the negentropy
potential. It was shown in [20] that the information ratio for Thompson
sampling satisfies (see Proposition 3):

$\Gamma^{F}_{t}(\pi^{\mathrm{TS}})\leq K/2\quad a.s.,\quad t=0,1,\ldots$ (20)

where $F$ is the negentropy potential. With the same potential function, using
(9) and (20), it can be shown that (see Proposition 2 of [21])

$\Gamma^{F}_{t}(\pi^{\mathrm{NDS}})\leq K/2\quad a.s.,\quad t=0,1,\ldots$

Since we have ${\mathrm{diam}_{F}(\Delta^{K-1})}\\!\leq\\!\log(K)$ for the
negentropy potential, applying Theorem 3.1 results in (13c). ∎

###  A.2 Comments on the proof

The information ratio analysis of Thompson sampling was first introduced in
[20], using the negentropy potential. In comparison to (13a), the resulting
upper bound had an additional $\sqrt{\frac{1}{4}\log(K)}$ factor, as in the
right hand side of (13c). It is interesting to note that a change in the
definition of information ratio via a change in the information gain function
leads to a tighter bound.

##  Appendix B Proof of a Lower Bound for the Information Ratio

Here we will show that for the counter example described in Section 4, the
lower bound in Theorem 16 holds.

In Section C we show that our results will hold for a much more generalized
definition of the information ratio (8), of which the definition considered in
[13] is a special case.

As a first step, we precisely describe the counter example that we use to
establish the lower bound.

Fix the number of arms $K$. Let $p\in(0,1)$, and
$\varepsilon\in(0,\varepsilon^{*}]$, where $0<\varepsilon^{*}<1-p$ satisfies
the following inequalities111Many of the inequalities in (21) can be combined,
but we write each of them out to ease verification of the proof.:

$\displaystyle\varepsilon^{*}$ $\displaystyle<\min\\{p,1-p\\}$ (21a)
$\displaystyle\left(\frac{\varepsilon^{*}}{K}\right)^{2}$
$\displaystyle\leq\frac{1}{2}\cdot p(1-p)$ (21b)
$\displaystyle\left(\frac{\varepsilon^{*}}{K}\right)^{2}$
$\displaystyle\leq\frac{1}{4}\cdot p(1-p)$ (21c)
$\displaystyle\frac{\varepsilon^{*}}{K}$
$\displaystyle\leq\frac{1}{4}\cdot\frac{p(1-p)}{|2p-1|}$ (21d)
$\displaystyle\varepsilon^{*}$
$\displaystyle\leq\frac{(K-1)}{K^{2}}\cdot\frac{p}{(1-p)}$ (21e)
$\displaystyle\varepsilon^{*}$ $\displaystyle\leq\frac{(1-p)}{K}$ (21f)
$\displaystyle\varepsilon^{*}$
$\displaystyle\leq\frac{(K-1)}{K}\cdot\frac{2}{3}\cdot\frac{(1-p)}{p}$ (21g)

For $1\leq i\leq K$, denote $p_{*,i}\in{\mathcal{P}}$ (recall, ${\mathcal{P}}$
is the set of all probability measures on $[0,1]^{K}$) such that, for each
$1\leq k\leq K$, the marginals are

$p_{*,i}(k)=\begin{cases}\mathrm{Bernoulli}(p+\varepsilon)\,\qquad&\text{if}\,\,i=k\\\
\mathrm{Bernoulli}(p)\,\qquad&\text{if}\,\,i\neq k\end{cases}$ (22)

Throughout this section, we let $P_{*}$ be the probability distribution on
${\mathcal{P}}$ such that

$P_{*}(p_{*,i})=\frac{1}{K}\,,\qquad 1\leq i\leq K$ (23)

In this section, we’ll prove the following Proposition. The proof of Theorem
16 follows directly from this result.

######  Proposition B.1.

For all policies $\pi$, $K\geq 2$, $p\in(0,1)$, and
$\varepsilon\in(0,\varepsilon^{*}]$, the following holds a.s. at $t=0$:

$\displaystyle g_{t}^{F}(\pi)$
$\displaystyle\leq\frac{(K-1)\varepsilon^{2}}{K^{2}}\cdot\frac{5}{2p(1-p)}$
(24) $\displaystyle\Delta_{t}(\pi)$ $\displaystyle=\frac{\varepsilon(K-1)}{K}$
(25)

Consequently,

$\Gamma_{t}^{F}{(\pi)}\geq{{\frac{2}{5}}\cdot p(1-p)\cdot(K-1)}$ (26)

###### Proof of Theorem 16.

The proof follows directly from Proposition 26 by letting $p=1/2$ in (26), and
using the fact that $K\geq 2$. ∎

### Proof of Proposition 26

The proof relies on Lemmas 27 and B.3.

######  Lemma B.2.

For each $t\geq 0$,

$\displaystyle\mathbb{P}_{t}(R_{t+1,a}=0|A_{*}=a_{*})$
$\displaystyle=\begin{cases}1-(p+\varepsilon)\,\,&\text{If}\,\,a_{*}=a\\\
1-p\,\,&\text{If}\,\,a_{*}\neq a\end{cases}$ (27a)
$\displaystyle\mathbb{P}_{t}(R_{t+1,a}=1|A_{*}=a_{*})$
$\displaystyle=\begin{cases}p+\varepsilon\,\,&\text{If}\,\,a_{*}=a\\\
p\,\,&\text{If}\,\,a_{*}\neq a\end{cases}$ (27b)
$\displaystyle\mathbb{P}_{t}(R_{t+1,a}=0)$
$\displaystyle=1-p-\varepsilon\cdot\mathbb{P}_{t}(A_{*}=a)$ (27c)
$\displaystyle\mathbb{P}_{t}(R_{t+1,a}=1)$
$\displaystyle=p+\varepsilon\cdot\mathbb{P}_{t}(A_{*}=a)$ (27d)

###### Proof.

Expressions (27a) and (27b) are straightforward from the definition of Example
15. The marginals are also straightforward to compute:

$\displaystyle\mathbb{P}_{t}(R_{t+1,a}=0)$
$\displaystyle=\sum_{a_{*}\in{\mathcal{A}}}\mathbb{P}_{t}(A_{*}=a_{*})\cdot\mathbb{P}_{t}(R_{t+1,a}=0|A_{*}=a_{*})$
(28) $\displaystyle=(1-p)-\mathbb{P}_{t}(A_{*}=a)\cdot\varepsilon$
$\displaystyle\mathbb{P}_{t}(R_{t+1,a}=1)$
$\displaystyle=\sum_{a_{*}\in{\mathcal{A}}}\mathbb{P}_{t}(A_{*}=a_{*})\cdot\mathbb{P}_{t}(R_{t+1,a}=1|A_{*}=a_{*})$
$\displaystyle=p+\mathbb{P}_{t}(A_{*}=a)\cdot\varepsilon$

∎

The following result is an extension of Proposition 2 of [20] which considered
the special case of Thompson sampling agent.

######  Lemma B.3.

For any policy $\pi$,

$\displaystyle g_{t}^{F}(\pi)$
$\displaystyle=\sum_{a_{*},a\in{\mathcal{A}}}\pi(a)\cdot\mathbb{P}_{t}(A_{*}=a_{*})\Big{[}D_{{\mathrm{KL}}}\Big{(}P_{t}\big{(}R_{t+1,a}|A_{*}=a_{*}\big{)}||P_{t}\big{(}R_{t+1,a}\big{)}\Big{)}\Big{]}$
(29) $\displaystyle\Delta_{t}(\pi)$
$\displaystyle=\sum_{a\in{\mathcal{A}}}\mathbb{P}_{t}(A_{*}=a)\cdot\mathbb{E}_{t}\big{[}R_{t+1,a}|A_{*}\\!=\\!a\big{]}-\sum_{a\in{\mathcal{A}}}\pi(a)\cdot\mathbb{E}_{t}\big{[}R_{t+1,a}\big{]}$
(30)

The proof of Lemma B.3 follows exactly along the lines of proof of Proposition
2 in [20], except that $\mathbb{P}_{t}(A_{t}=a)=\mathbb{P}_{t}(A_{*}=a)$ in
their proof (which holds for Thompson sampling) is replaced by
$\mathbb{P}_{t}(A_{t}=a)=\pi(a)$.

We are now ready to prove Proposition 26.

###### Proof of Proposition 26.

Recall that at $t=0$, $\mathbb{P}_{t}(A_{*}=a)=1/K$ for each
$a\in{\mathcal{A}}$. It follows from (27c) and (27d) of Lemma 27 that for each
$a\in{\mathcal{A}}$,

$\displaystyle\mathbb{P}_{t}(R_{t+1,a}=0)$
$\displaystyle=(1-p)-\frac{\varepsilon}{K}$ (31)
$\displaystyle\mathbb{P}_{t}(R_{t+1,a}=1)$
$\displaystyle=p+\frac{\varepsilon}{K}$

Using (27a), (27b) of Lemma 27 and (31) in the expression for relative entropy
(3), we obtain:

$\displaystyle
D_{{\mathrm{KL}}}\Big{(}P_{t}\big{(}R_{t+1,a}|A_{*}\\!=\\!a_{*}\big{)}||P_{t}\big{(}R_{t+1,a}\big{)}\Big{)}$
$\displaystyle\\!=\\!\begin{cases}(1\\!-\\!p\\!-\\!\varepsilon)\log\left(\frac{1-p-\varepsilon}{1-p-\varepsilon/K}\right)+(p\\!+\\!\varepsilon)\log\left(\frac{p+\varepsilon}{p+\varepsilon/K}\right)&\,\,\,\text{If}\,\,a=a_{*}\\\\[5.0pt]
(1\\!-p)\log\left(\frac{1-p}{1-p-\varepsilon/K}\right)+p\log\left(\frac{p}{p+\varepsilon/K}\right)&\,\,\,\text{If}\,\,a\neq
a_{*}\end{cases}$ (32)

Next, using the fact that $\mathbb{P}_{t}(A_{*}=a_{*})=1/K$ for each
$a_{*}\in{\mathcal{A}}$, we have

$\displaystyle\sum_{a_{*}\in{\mathcal{A}}}\mathbb{P}_{t}(A_{*}=a_{*})\Big{[}D_{{\mathrm{KL}}}\Big{(}P_{t}\big{(}R_{t+1,a}|A_{*}=a_{*}\big{)}||P_{t}\big{(}R_{t+1,a}\big{)}\Big{)}\Big{]}$
(33) $\displaystyle\hskip
72.26999pt=\Big{(}\frac{K-1}{K}\Big{)}\left((1\\!-p)\log\left(\frac{1-p}{1-p-\varepsilon/K}\right)+p\log\left(\frac{p}{p+\varepsilon/K}\right)\right)$
$\displaystyle\hskip
86.72377pt+\frac{1}{K}\left((1\\!-\\!p\\!-\\!\varepsilon)\log\left(\frac{1-p-\varepsilon}{1-p-\varepsilon/K}\right)+(p\\!+\\!\varepsilon)\log\left(\frac{p+\varepsilon}{p+\varepsilon/K}\right)\right)$

Note that the right hand side of (33) does not depend on $a$ anymore.
Substituting (33) into (29) of Lemma B.3, we have, for any policy $\pi$ (since
$\sum_{a\in{\mathcal{A}}}\pi(a)=1$),

$\displaystyle g_{t}^{F}(\pi)=$
$\displaystyle\Big{(}\frac{K-1}{K}\Big{)}\left((1\\!-p)\log\left(\frac{1-p}{1-p-\varepsilon/K}\right)+p\log\left(\frac{p}{p+\varepsilon/K}\right)\right)$
$\displaystyle+\frac{1}{K}\left((1\\!-\\!p\\!-\\!\varepsilon)\log\left(\frac{1-p-\varepsilon}{1-p-\varepsilon/K}\right)+(p\\!+\\!\varepsilon)\log\left(\frac{p+\varepsilon}{p+\varepsilon/K}\right)\right)$

A simplification of the right hand side yields:

$\displaystyle g_{t}^{F}(\pi)$
$\displaystyle=-(1\\!-\\!p)\log\left(1\\!-\\!\frac{\varepsilon}{K(1-p)}\right)\\!-\\!p\log\left(1\\!+\\!\frac{\varepsilon}{Kp}\right)$
(34)
$\displaystyle+\frac{1}{K}\left((1\\!-\\!p)\log\left(1\\!-\\!\frac{\varepsilon}{1\\!-\\!p}\right)\\!+\\!p\log\left(1\\!+\\!\frac{\varepsilon}{p}\right)\right)$
$\displaystyle+\frac{1}{K}\Big{(}\varepsilon\log\left(p+\varepsilon\right)-\varepsilon\log\left(1-p-\varepsilon\right)+\varepsilon\log\left(1-p-\varepsilon/K\right)-\varepsilon\log\left(p+\varepsilon/K\right)\Big{)}$

We use the following inequalities that are obtained using Taylor series to
upper bound each of the terms in (34): For $0<x<1$,

$\displaystyle\log(1+x)$ $\displaystyle\leq x-\frac{x^{2}}{2}+\frac{x^{3}}{3}$
(35a) $\displaystyle-\log(1+x)$ $\displaystyle\leq-x+\frac{x^{2}}{2}$ (35b)
$\displaystyle\log(1-x)$ $\displaystyle\leq-x-\frac{x^{2}}{2}$ (35c)
$\displaystyle-\log(1-x)$ $\displaystyle\leq
x+\frac{x^{2}}{2}+\frac{x^{3}}{3(1-x)}$ (35d)

We can upper bound the first two terms in (34) using (35b) and (35d) (here we
use condition (21a) for $\varepsilon$)

$\displaystyle-(1\\!-\\!p)\log\left(1\\!-\\!\frac{\varepsilon}{K(1-p)}\right)\\!-\\!p\log\left(1\\!+\\!\frac{\varepsilon}{Kp}\right)$
$\displaystyle\leq(1\\!-\\!p)\left(\frac{\varepsilon}{K(1-p)}\\!+\\!\frac{\varepsilon^{2}}{2K^{2}(1-p)^{2}}\\!+\\!\frac{\varepsilon^{3}}{3K^{3}(1-p)^{3}}\cdot\Big{(}1-\frac{\varepsilon}{K(1-p)}\Big{)}^{-1}\right)$
$\displaystyle\qquad\qquad\\!-\\!p\left(\frac{\varepsilon}{Kp}-\frac{\varepsilon^{2}}{2K^{2}p^{2}}\right)$
$\displaystyle=\frac{\varepsilon^{2}}{2K^{2}(1-p)}\\!+\\!\frac{\varepsilon^{3}}{3K^{2}(1-p)}\cdot\frac{1}{K(1-p)-\varepsilon}\\!+\\!\frac{\varepsilon^{2}}{2K^{2}p}$
$\displaystyle\leq\frac{\varepsilon^{2}}{2K^{2}p(1-p)}\\!+\\!\frac{\varepsilon^{3}}{3K^{2}(K-1)(1-p)^{2}}$
(36)

where in the last inequality we have used $\varepsilon\leq(1-p)$. Along
similar lines, we can bound the second two terms in (34) using (35a) and
(35c):

$\displaystyle\frac{1}{K}\left((1\\!-\\!p)\log\left(1\\!-\\!\frac{\varepsilon}{1\\!-\\!p}\right)\\!+\\!p\log\left(1\\!+\\!\frac{\varepsilon}{p}\right)\right)\leq\frac{-\varepsilon^{2}}{2Kp(1-p)}+\frac{\varepsilon^{3}}{3p^{2}}$
(37)

Now, consider the last four terms of (34):

$\displaystyle\frac{1}{K}\Big{(}\varepsilon\log\left(p\\!+\\!\varepsilon\right)\\!$
$\displaystyle-\\!\varepsilon\log\left(1\\!-\\!p\\!-\\!\varepsilon\right)\\!+\\!\varepsilon\log\left(1\\!-\\!p\\!-\\!\varepsilon/K\right)\\!-\\!\varepsilon\log\left(p\\!+\\!\varepsilon/K\right)\Big{)}$
$\displaystyle=\frac{1}{K}\Big{(}\varepsilon\log\left(1\\!+\\!\frac{(K-1)\varepsilon}{K(p\\!+\\!\varepsilon/K)}\right)-\varepsilon\log\left(1\\!-\\!\frac{(K-1)\varepsilon}{K(1\\!-\\!p\\!-\\!\varepsilon/K)}\right)$
$\displaystyle\overset{(a)}{\leq}\frac{1}{K}\left(\frac{(K-1)\varepsilon^{2}}{K(p\\!+\\!\varepsilon/K)}\\!+\\!\frac{(K-1)\varepsilon^{2}}{K(1\\!-\\!p\\!-\\!\varepsilon/K)}\\!+\\!\frac{(K-1)^{2}\varepsilon^{3}}{2K^{2}(1\\!-\\!p\\!-\\!\varepsilon/K)^{2}}\cdot\left(1-\frac{(K-1)\varepsilon}{K(1-p-\varepsilon/K)}\right)^{-1}\right)$
$\displaystyle=\frac{(K-1)\varepsilon^{2}}{K}\left(\frac{1}{Kp\\!+\\!\varepsilon}+\\!\frac{1}{K\\!-\\!Kp\\!-\\!\varepsilon}\right)\\!+\\!\frac{(K-1)^{2}\varepsilon^{3}}{2K^{2}(1\\!-\\!p\\!-\\!\varepsilon/K)}\cdot\frac{1}{K(1-p-\varepsilon)}$
$\displaystyle\overset{(b)}{\leq}\frac{(K-1)\varepsilon^{2}}{K^{2}}\cdot\frac{1}{(p\\!+\\!\varepsilon/K)(1\\!-\\!p\\!-\\!\varepsilon/K)}\\!+\\!\frac{(K-1)^{2}\varepsilon^{3}}{2K^{3}(1\\!-\\!p\\!-\\!\varepsilon)^{2}}$
(38)

where $(a)$ uses (35a) and (35d), and $(b)$ uses
$(1-p-\varepsilon/K)^{-1}\leq(1-p-\varepsilon)^{-1}$.

Substituting (36), (37), and (38) into (34), we have:

$\displaystyle g_{t}^{F}(\pi)$
$\displaystyle\leq\frac{(K-1)\varepsilon^{2}}{K^{2}}\left(\frac{1}{(p+\varepsilon/K)(1-p-\varepsilon/K)}-\frac{1}{2p(1-p)}\right)+\tilde{g}(\varepsilon,K,p)$
(39) $\displaystyle\tilde{g}(\varepsilon,K,p)$
$\displaystyle=\frac{\varepsilon^{3}}{3K^{2}(K-1)(1-p)^{2}}+\frac{\varepsilon^{3}}{3p^{2}}+\frac{(K-1)^{2}\varepsilon^{3}}{2K^{3}(1-p-\varepsilon)^{2}}$
(40)

To obtain the final bound (24), we need to choose $\varepsilon$ small enough
so that:

$\displaystyle\frac{1}{(p+\varepsilon/K)(1-p-\varepsilon/K)}$
$\displaystyle\leq\frac{2}{p(1-p)}$ (41a)
$\displaystyle\frac{\varepsilon^{3}}{3K^{2}(K-1)(1-p)^{2}}+\frac{\varepsilon^{3}}{3p^{2}}+\frac{(K-1)^{2}\varepsilon^{3}}{2K^{3}(1-p-\varepsilon)^{2}}$
$\displaystyle\leq\frac{(K-1)\varepsilon^{2}}{K^{2}}\cdot\frac{1}{p(1-p)}$
(41b)

Applying (21b)-(21d), we obtain (41a) . And applying (21e)-(21g), we obtain
(41b).

Substituting (41a) and (41b) into (40) and (39) gives us the final bound (24).

We next show that (25) holds. Using (30) of Lemma B.3,

$\displaystyle\Delta_{t}(\pi)$
$\displaystyle=\sum_{a\in{\mathcal{A}}}\mathbb{P}_{t}(A_{*}=a)\mathbb{E}_{t}\big{[}R_{t+1,a}|A_{*}\\!=\\!a\big{]}-\sum_{a\in{\mathcal{A}}}\pi(a)\mathbb{E}_{t}\big{[}R_{t+1,a}\big{]}$
$\displaystyle=p+\varepsilon-\sum_{a\in{\mathcal{A}}}\pi(a)\cdot\Big{(}p+\frac{\varepsilon}{K}\Big{)}$
$\displaystyle=\frac{K-1}{K}\cdot\varepsilon$

where we have used (27b) and (27d) along with the fact that
$\mathbb{P}_{t}(A_{*}=a)=1/K$ for each $a\in{\mathcal{A}}$ to obtain the
second equality.

The final bound (26) follows from definition (8).

∎

##  Appendix C Strengthening the Lower Bound of Section B

###  C.1 Definitions and Goals

We first introduce some definitions that are useful for extending our results
in the main draft.

For any potential $F$ that satisfies $\mathrm{diam}_{F}(\Delta^{K-1})<\infty$,
and $\alpha\in\Re^{+}$, we consider the following generalized definition of
information ratio $\Gamma_{t}^{F}(\pi,\alpha)$ associated with policy $\pi$ at
time-step $t$:

$\Gamma_{t}^{F}(\pi,\alpha)\mathbin{:=}\frac{\big{(}\Delta_{t}(\pi)-\alpha\big{)}^{2}}{g_{t}^{F}(\pi)}$
(42)

The above definition of the information ratio is the same as the one
considered in [13] (see for example, Corollary 4), but written in a different
form. The definition of information ratio in (8) (and in Section B) is a
special case of (42), with $\alpha=0$.

For any potential $F$ that satisfies $\mathrm{diam}_{F}(\Delta^{K-1})<\infty$,
$T\geq 0$, policy $\pi$, $\alpha\in\Re^{+}$, and $\delta\in[0,1]$, we define

$\displaystyle{\mathrm{Regret}}^{\mathrm{F}}(T,\pi,\alpha,\delta)$
$\displaystyle\mathbin{:=}\sqrt{\gamma_{F}(T,\pi,\alpha,\delta)\cdot
T\cdot{\mathrm{diam}_{F}(\Delta^{K-1})}}+\left(\alpha+\delta\cdot\mathrm{Reg}_{\max}\right)\cdot
T$ (43)

where $\gamma_{F}(T,\pi,\alpha,\delta)$ is any deterministic constant that
satisfies, for each $0\leq t\leq T-1$,

$\displaystyle\mathbb{P}\Big{(}\Gamma_{t}^{F}(\alpha,\pi)\leq\gamma_{F}(T,\pi,\alpha,\delta)\Big{)}\geq
1-\delta$ (44)

and

$\mathrm{Reg}_{\max}=\max_{t\geq 0\,,a\in{\mathcal{A}}}\Delta_{t}(a)$ (45)

Note that the upper bound $\gamma_{F}(\pi)$ defined in Section 3 (above
Corollary 3.2) is a special case of $\gamma_{F}(T,\pi,\alpha,\delta)$, with
$\alpha=\delta=0$, and $T=\infty$. And the right hand side of (12) in
Corollary 3.2 is a special case of
${\mathrm{Regret}}^{\mathrm{F}}(T,\pi,\alpha,\delta)$, with $\alpha=\delta=0$.

The goal of this section is to show that,

  * (i)

generalizing the definition of information in (8) to the one in (42), and

  * (ii)

replacing a uniform (in time) a.s. upper bound on the information ratio, such
as the one used in Corollary 3.2, with a uniform (in time) high probability
upper bound as in (44)

both are insufficient to obtain an order $\sqrt{KT}$ bound for _any_ policy,
using Shannon information ratio analysis.

This highlights the need for analysis techniques that take into account the
temporal nature of information ratio that was introduced in Section 5.

###  C.2 An Upper Bound on ${\mathrm{Regret}}$ using
${\mathrm{Regret}}^{\mathrm{F}}$

As a first step, the following result shows how
${\mathrm{Regret}}^{\mathrm{F}}$ can be used to upper bound the Bayesian
regret of any policy $\pi$. The proof uses Lemma D.1 that is proved in Section
D.

######  Theorem C.1.

For any policy $\pi$, $T\geq 1$, $K\geq 2$, $\alpha\in\Re^{+}$,
$\delta\in[0,1]$,

${\mathrm{Regret}}(T,\pi)\leq{\mathrm{Regret}}^{\mathrm{F}}(T,\pi,\alpha,\delta)$
(46)

where $F$ is convex, and satisfies $\mathrm{diam}_{F}(\Delta^{K-1})<\infty$.

###### Proof.

Recalling the definition of Bayesian regret (2),

$\displaystyle\mathrm{Regret}(T,\pi)$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{T-1}(R_{*}-R_{t+1,A_{t}})\right]$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{T-1}\left(R_{*}-\alpha-
R_{t+1,A_{t}}\right)\right]+\alpha\cdot T$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{T-1}\left(\mathbb{E}_{t}\left[R_{*}-\alpha-
R_{t+1,A_{t}}\right]\right)\right]+\alpha\cdot T$ (47)

From the generalized definition of information ratio in (42),

$\displaystyle\mathbb{E}\Big{[}{\mathbb{E}}_{t}\left[R_{*}-\alpha-
R_{t+1,A_{t}}\right]\Big{]}$
$\displaystyle=\mathbb{E}\left[\sqrt{\Gamma_{t}^{F}(\pi,\alpha)\cdot{\mathbb{E}}_{t}\big{[}D_{F}\big{(}P_{t+1}(A_{*}),P_{t}(A_{*})\big{)}\big{]}}\,\right]$
$\displaystyle\leq\sqrt{\gamma_{F}(T,\pi,\alpha,\delta)}\cdot\mathbb{E}\left[\sqrt{{\mathbb{E}}_{t}\big{[}D_{F}\big{(}P_{t+1}(A_{*}),P_{t}(A_{*})\big{)}\big{]}}\,\right]+\delta\cdot\mathrm{Reg}_{\max}$
(48)

where $\gamma_{F}(T,\pi,\alpha,\delta)$ is a high probability upper bound on
the information ratio that satisfies (44), and we have used the following two
inequalities to obtain (48): For each $0\leq t\leq T-1$,

$\displaystyle\mathbb{P}\left(\Gamma_{t}^{F}(\pi,\alpha)\leq\gamma_{F}(T,\pi,\alpha,\delta)\right)$
$\displaystyle\geq 1-\delta$ $\displaystyle\mathbb{E}_{t}\left[R_{*}-\alpha-
R_{t+1,A_{t}}\right]$ $\displaystyle\leq\mathrm{Reg}_{\max}$

Using (48) in (47):

$\displaystyle\mathrm{Regret}(T,\pi)$
$\displaystyle\leq\sqrt{\gamma_{F}(T,\pi,\alpha,\delta)}\cdot\mathbb{E}\left[\sum_{t=0}^{T-1}\sqrt{{\mathbb{E}}_{t}\big{[}D_{F}\big{(}P_{t+1}(A_{*}),P_{t}(A_{*})\big{)}\big{]}}\right]+\left(\alpha+\delta\cdot\mathrm{Reg}_{\max}\right)\cdot
T$ (49)

Applying Cauchy Schwarz and then using Lemma D.1,

$\displaystyle\mathrm{Regret}(T,\pi)$
$\displaystyle\overset{(a)}{\leq}\sqrt{\gamma_{F}(T,\pi,\alpha,\delta)\cdot
T\cdot\mathbb{E}\left[\sum_{t=0}^{T-1}{\mathbb{E}}_{t}\big{[}D_{F}\big{(}P_{t+1}(A_{*}),P_{t}(A_{*})\big{)}\big{]}\right]}+\left(\alpha+\delta\cdot\mathrm{Reg}_{\max}\right)\cdot
T$ $\displaystyle\overset{(b)}{\leq}\sqrt{\gamma_{F}(T,\pi,\alpha,\delta)\cdot
T\cdot\mathbb{E}\left[\sum_{t=0}^{T-1}{\mathbb{E}}_{t}\big{[}F\big{(}P_{t+1}(A_{*})\big{)}\big{]}-F\big{(}P_{t}(A_{*})\big{)}\right]}+\left(\alpha+\delta\cdot\mathrm{Reg}_{\max}\right)\cdot
T$ $\displaystyle=\sqrt{\gamma_{F}(T,\pi,\alpha,\delta)\cdot
T\cdot\mathbb{E}\left[\sum_{t=0}^{T-1}F\big{(}P_{t+1}(A_{*})\big{)}-F\big{(}P_{t}(A_{*})\big{)}\right]}+\left(\alpha+\delta\cdot\mathrm{Reg}_{\max}\right)\cdot
T$ $\displaystyle\overset{(c)}{\leq}\sqrt{\gamma_{F}(T,\pi,\alpha,\delta)\cdot
T\cdot\mathrm{diam}_{F}(\Delta^{k-1})}+\left(\alpha+\delta\cdot\mathrm{Reg}_{\max}\right)\cdot
T$ $\displaystyle={\mathrm{Regret}}^{\mathrm{F}}(T,\pi,\alpha,\delta)$

where $(a)$ is an application of Cauchy Schwarz, $(b)$ is from Lemma D.1, and
$(c)$ follows from the definition of $\mathrm{diam}_{F}(\cdot)$.

∎

###  C.3 A More General Lower Bound

Here, we will show the following lower bound for Example 4.1, with
$\varepsilon\in(0,\varepsilon^{*}]$, where $\varepsilon^{*}$ satisfies (21).

######  Theorem C.2.

For all $K\geq 2$, $p\in(0,1)$, and $\varepsilon\in(0,\varepsilon^{*}]$, there
exists $T\in\mathbb{N}$, such that, for any policy $\pi$, $\alpha\in\Re^{+}$,
and $\delta\in[0,1]$,

${\mathrm{Regret}}^{\mathrm{F}}(T,\pi,\alpha,\delta)\geq\sqrt{{\frac{2}{5}}\cdot
p(1-p)\cdot(K-1)\cdot T\cdot\log(K)}$ (50)

The following is a direct Corollary to Theorem C.2, which follows from the
fact that $K\geq 2$, and $p=1/2$ maximizes the right hand side of (50).

######  Corollary C.3.

For all $K\geq 2$, there exists $T\geq 0$, $p\in(0,1)$, and
$\epsilon^{*}\in(0,1-p)$, such that, for all $\epsilon\in(0,\epsilon^{*}]$,
and any policy $\pi$,

${\mathrm{Regret}}^{\mathrm{F}}(T,\pi,\alpha,\delta)\geq\sqrt{\frac{1}{20}\cdot
K\cdot T\cdot\log(K)}$

Organization of Proof of Theorem C.2: The proof of Theorem C.2 is split into
three parts. First, in Section C.4, we show that the lower bound holds for
$\alpha=\delta=0$. Next, in Section C.5, we show that the lower bound holds
for any $\alpha\geq 0$ and $\delta=0$. Finally, we show in Section C.6 that
the result also holds for all $\alpha\geq 0$ and $\delta\in[0,1]$.

###  C.4 Proof of lower bound for $\alpha=\delta=0$

We show the following Proposition in this section.

######  Proposition C.4 (Lower Bound for $\alpha=\delta=0$).

For all $K\geq 2$, $p\in(0,1)$, $\varepsilon\in(0,\varepsilon^{*}]$,
$T\in\mathbb{N}$, policy $\pi$, and $\alpha=\delta=0$,

${\mathrm{Regret}}^{\mathrm{F}}(T,\pi,\alpha,\delta)\geq\sqrt{{\frac{2}{5}}\cdot
p(1-p)\cdot(K-1)\cdot T\cdot\log(K)}$ (51)

###### Proof of Proposition C.4.

The proof directly follows from the definition of
${\mathrm{Regret}}^{\mathrm{F}}$ in (43) and (26) of Proposition 26: Since we
have shown that when $\alpha=0$ and $t=0$,

$\Gamma_{t}^{F}{(\pi,\alpha)}=\Gamma_{t}^{F}{(\pi)}\geq{{\frac{2}{5}}\cdot
p(1-p)\cdot(K-1)}\,\,\,\,a.s.,$

we have

$\gamma_{F}(T,\pi,\alpha,\delta)\geq{{\frac{2}{5}}\cdot p(1-p)\cdot(K-1)}$

Substituting $\alpha=\delta=0$ in (43), and using the fact that
${\mathrm{diam}_{F}(\Delta^{K-1})}=\log(K)$ when $F$ is negentropy, we obtain
(51). ∎

###  C.5 Proof of Lower Bound for $\delta=0$ and $\alpha\geq 0$

Here we generalize the result of Proposition C.4 for $\alpha\geq 0$.

######  Proposition C.5 (Lower Bound for $\delta=0$ and $\alpha\geq 0$).

For all $K\geq 2$, $p\in(0,1)$, $\varepsilon\in(0,\varepsilon^{*}]$,
$\alpha\in\Re^{+}$, $T\in\mathbb{N}$, and $\delta=0$, and any policy $\pi$,

${\mathrm{Regret}}^{\mathrm{F}}(T,\pi,\alpha,\delta)\geq\sqrt{{\frac{2}{5}}\cdot
p(1-p)\cdot\frac{\left(\varepsilon(K-1)-\alpha
K\right)^{2}}{(K-1)\cdot\varepsilon^{2}}\cdot T\cdot\log(K)}+\alpha T$ (52)

Consequently, if $T\in\mathbb{N}$ satisfies

$T\geq\frac{2}{5}\cdot
p(1-p)\cdot\frac{K^{2}}{(K-1)}\cdot\frac{\log(K)}{\varepsilon^{2}}$ (53)

then,

$\min_{\alpha\in\Re^{+}}{\mathrm{Regret}}^{\mathrm{F}}(T,\pi,\alpha,\delta)\geq\sqrt{{\frac{2}{5}}\cdot
p(1-p)\cdot(K-1)\cdot T\cdot\log(K)}$ (54)

The proof of Proposition 54 relies on the following result.

######  Lemma C.6.

For all $K\geq 2$, $p\in(0,1)$, $\varepsilon\in(0,\varepsilon^{*}]$, and
$\alpha\in\Re^{+}$, the following holds a.s. at $t=0$:

$\displaystyle g_{t}^{F}(\pi)$
$\displaystyle\leq\frac{(K-1)\varepsilon^{2}}{K^{2}}\cdot\frac{5}{2p(1-p)}$
(55) $\displaystyle\Delta_{t}(\pi)-\alpha$
$\displaystyle=\frac{\varepsilon(K-1)}{K}-\alpha$ (56)

Consequently, for all $K\geq 2$, $p\in(0,1)$,
$\varepsilon\in(0,\varepsilon^{*}]$, $\alpha\in\Re^{+}$, and any policy $\pi$,
at $t=0$,

$\Gamma_{t}^{F}{(\pi,\alpha)}\geq{\frac{2}{5}}\cdot
p(1-p)\cdot\frac{\left(\varepsilon(K-1)-\alpha
K\right)^{2}}{(K-1)\cdot\varepsilon^{2}}\,\,\,a.s..$ (57)

###### Proof.

The proof of (55) is the same as proof of (24) in Proposition 26. The proof of
(56) is also straightforward from (25). The final inequality (57) is direct
from the definition of generalized information ratio in (42). ∎

###### Proof of Proposition 54.

Recall that $\gamma_{F}(T,\pi,\alpha,\delta)$ is a deterministic constant that
satisfies (44). Lemma 57 implies, for $\delta=0$,

$\gamma_{F}(T,\pi,\alpha,\delta)\geq{\frac{2}{5}}\cdot
p(1-p)\cdot\frac{\left(\varepsilon(K-1)-\alpha
K\right)^{2}}{(K-1)\cdot\varepsilon^{2}}$

Using this lower bound in the definition of $\mathrm{Regret}^{\mathrm{F}}$
(cf. (43)), we obtain (52).

The right hand side of (52) can be simplified as follows:

$\displaystyle\sqrt{{\frac{2}{5}}\cdot
p(1-p)\cdot\frac{\left(\varepsilon(K-1)-\alpha
K\right)^{2}}{(K-1)\cdot\varepsilon^{2}}\cdot T\cdot\log(K)}+\alpha T$
$\displaystyle=\left|(K-1)-\frac{\alpha
K}{\varepsilon}\right|\cdot\sqrt{\frac{2p(1-p)}{5(K-1)}\cdot
T\cdot\log(K)}+\alpha T$ $\displaystyle=\begin{cases}\sqrt{\frac{2}{5}\cdot
p(1-p)\cdot(K-1)\cdot
T\cdot\log(K)}+\alpha\left(T-\frac{K}{\varepsilon}\cdot\sqrt{\frac{2p(1-p)}{5(K-1)}\cdot
T\cdot\log(K)}\right)&\quad\text{if}\quad\alpha\leq\frac{\varepsilon(K-1)}{K}\\\\[10.00002pt]
-\sqrt{\frac{2}{5}\cdot p(1-p)\cdot(K-1)\cdot
T\cdot\log(K)}+\alpha\left(T+\frac{K}{\varepsilon}\cdot\sqrt{\frac{2p(1-p)}{5(K-1)}\cdot
T\cdot\log(K)}\right)&\quad\text{if}\quad\alpha>\frac{\varepsilon(K-1)}{K}\end{cases}$
(58)

Optimizing the right hand side of (58) over $\alpha$, we have, if $T$
satisfies (53):

$T\geq\frac{2}{5}\cdot
p(1-p)\cdot\frac{K^{2}}{(K-1)}\cdot\frac{\log(K)}{\varepsilon^{2}}$

then (54) holds:

$\min_{\alpha\in\Re^{+}}{\mathrm{Regret}}^{\mathrm{F}}(T,\pi,\alpha,\delta)\geq\sqrt{{\frac{2}{5}}\cdot
p(1-p)\cdot(K-1)\cdot T\cdot\log(K)}$

∎

###  C.6 Proof of Theorem C.2

From its definition in (45), note that $\mathrm{Reg}_{\max}=\epsilon$ for the
counter example. Suppose $\delta\in[0,1]$ satisfies

$\delta>\sqrt{\frac{1}{20}\cdot\frac{K\log(K)}{T}}\cdot\frac{1}{\epsilon}$

Then, from the definition (43), we have, for any $\alpha\in\Re^{+}$,

$\displaystyle{\mathrm{Regret}}^{\mathrm{F}}(T,\pi,\alpha,\delta)$
$\displaystyle\geq T\cdot\delta\cdot\epsilon$
$\displaystyle>\sqrt{\frac{1}{20}KT\log(K)}$

implying that (50) holds. In the rest of the proof we will assume

$\delta\leq\sqrt{\frac{1}{20}\cdot\frac{K\log(K)}{T}}\cdot\frac{1}{\epsilon}$
(59)

Now suppose

$T\geq\max\left\\{\frac{K\log(K)}{5\epsilon^{2}}\,\,,\quad\frac{2}{5}\cdot
p(1-p)\cdot\frac{K^{2}}{(K-1)}\cdot\frac{\log(K)}{\epsilon^{2}}\right\\}$ (60)

Then, (59) implies $\delta\leq 0.5$.

Inequality (57) of Lemma 57 implies that for all
$\epsilon\in(0,\epsilon^{*}]$, and $t=0$,

$\Gamma_{t}^{F}{(\pi,\alpha)}\geq{\frac{2}{5}}\cdot
p(1-p)\cdot\frac{\left(\varepsilon(K-1)-\alpha
K\right)^{2}}{(K-1)\cdot\varepsilon^{2}}\,\,\,a.s..$ (61)

Recall that $\gamma_{F}(T,\pi,\alpha,\delta)$ is any deterministic constant
that satisfies (44). Inequality (61) implies that for large $T$ that satisfies
(60) (since we have $\delta\leq 0.5$ in this case),

$\gamma_{F}(T,\pi,\alpha,\delta)\geq{\frac{2}{5}}\cdot
p(1-p)\cdot\frac{\left(\epsilon(K-1)-\alpha
K\right)^{2}}{(K-1)\cdot\epsilon^{2}}$

Using the above bound in (43),

${\mathrm{Regret}}^{\mathrm{F}}(T,\pi,\alpha,\delta)\geq\sqrt{{\frac{2}{5}}\cdot
p(1-p)\cdot\frac{\left(\epsilon(K-1)-\alpha
K\right)^{2}}{(K-1)\cdot\epsilon^{2}}\cdot T\cdot\log(K)}+\alpha T$ (62)

Following along the lines of Proposition 54 (in particular, see (54)), it
follows that for all $T$ that satisfies (60),

${\mathrm{Regret}}^{\mathrm{F}}(T,\pi,\alpha,\delta)\geq\sqrt{{\frac{2}{5}}\cdot
p(1-p)\cdot(K-1)\cdot T\cdot\log(K)}$

for all $\alpha\in\Re^{+}$, and $\delta\in[0,1]$. ∎

##  Appendix D Proofs of Theorems 3.1 and 5.1

Both results will need the following result which is taken from proof of
Theorem 3 in [13].

######  Lemma D.1.

For any convex function $F:\Delta^{K-1}\to\Re\cup\\{\infty\\}$,

${\mathbb{E}}_{t}\big{[}D_{F}\big{(}P_{t+1}(A_{*}),P_{t}(A_{*})\big{)}\big{]}\leq{\mathbb{E}}_{t}\big{[}F\big{(}P_{t+1}(A_{*})\big{)}\big{]}-F\big{(}P_{t}(A_{*})\big{)}$

###### Proof.

For each $0\leq t\leq T-1$, let ${\mathcal{F}}_{t}$ denote the
$\sigma$-algebra generated by $H_{t}$. Note that since $H_{0}=\emptyset$,
${\mathcal{F}}_{0}=\\{\emptyset,\Omega\\}$.

Note that $\\{P_{t+1}(A_{*}):0\leq t\leq T-1\\}$ is a Martingale adapted to
$\\{{\mathcal{F}}_{t}:0\leq t\leq T-1\\}$:

$\mathbb{E}_{t}\big{[}P_{t+1}(A_{*})\big{]}=P_{t}(A_{*})$ (63)

From the definition of Bregman divergence (4),

$\displaystyle\mathbb{E}_{t}\left[D_{F}(P_{t+1}(A_{*}),P_{t}(A_{*}))\right]$
$\displaystyle\hskip
28.90755pt=\mathbb{E}_{t}\left[\left(F(P_{t+1}(A_{*}))\\!-\\!F(P_{t}(A_{*}))-\frac{F\left(hP_{t+1}(A_{*})\\!+\\!(1\\!-\\!h)P_{t}(A_{*})\right)-F\left(P_{t}(A_{*})\right)}{h}\right)\right]$
$\displaystyle\hskip 28.90755pt\overset{(a)}{\leq}\liminf_{h\to
0+}\left(\mathbb{E}_{t}\left[F(P_{t+1}(A_{*}))\\!-\\!F(P_{t}(A_{*}))-\frac{F\left(hP_{t+1}(A_{*})\\!+\\!(1\\!-\\!h)P_{t}(A_{*})\right)-F\left(P_{t}(A_{*})\right)}{h}\right]\right)$
$\displaystyle\hskip
28.90755pt=\mathbb{E}_{t}\left[F(P_{t+1}(A_{*}))\right]-F(P_{t}(A_{*}))+\liminf_{h\to
0+}\frac{F\left(P_{t}(A_{*})\right)-\mathbb{E}_{t}\left[F\left(hP_{t+1}(A_{*})+(1\\!-\\!h)P_{t}(A_{*})\right)\right]}{h}$
$\displaystyle\hskip
28.90755pt\overset{(b)}{\leq}\mathbb{E}_{t}\left[F(P_{t+1}(A_{*}))\right]-F(P_{t}(A_{*}))+\liminf_{h\to
0+}\frac{F\left(P_{t}(A_{*})\right)-F\left(\mathbb{E}_{t}\left[hP_{t+1}(A_{*})+(1\\!-\\!h)P_{t}(A_{*})\right]\right)}{h}$
$\displaystyle\hskip
28.90755pt\overset{(c)}{=}\mathbb{E}_{t}\left[F(P_{t+1}(A_{*}))\right]-F(P_{t}(A_{*}))$

where $(a)$ follows from Fatou’s lemma, $(b)$ follows from convexity of $F$,
and $(c)$ from (63).

∎

###### Proof of Theorem 3.1.

Recalling the definition of Bayesian regret (2), we have

$\displaystyle\mathrm{Regret}(T,\pi)$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{T-1}(R_{*}-R_{t+1,A_{t}})\right]$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{T-1}\left(\mathbb{E}_{t}\left[R_{*}-R_{t+1,A_{t}}\right]\right)\right]$
$\displaystyle\overset{(a)}{=}\mathbb{E}\left[\sum_{t=0}^{T-1}\sqrt{\Gamma_{t}^{F}(\pi)}\cdot\sqrt{{\mathbb{E}}_{t}\big{[}D_{F}\big{(}P_{t+1}(A_{*}),P_{t}(A_{*})\big{)}\big{]}}\,\right]$
$\displaystyle\overset{(b)}{\leq}\sqrt{\mathbb{E}\left[\sum_{t=0}^{T-1}\Gamma_{t}^{F}(\pi)\right]}\cdot\sqrt{\mathbb{E}\left[\sum_{t=0}^{T-1}{\mathbb{E}}_{t}\big{[}D_{F}\big{(}P_{t+1}(A_{*}),P_{t}(A_{*})\big{)}\big{]}\right]}\,$
$\displaystyle\overset{(c)}{\leq}\sqrt{{\overline{{\Gamma}}}^{F}_{T}(\pi)\cdot
T}\cdot\sqrt{\mathbb{E}\left[\sum_{t=0}^{T-1}{\mathbb{E}}_{t}\big{[}F\big{(}P_{t+1}(A_{*})\big{)}\big{]}-F\big{(}P_{t}(A_{*})\big{)}\right]}\,$
$\displaystyle\overset{(d)}{=}\sqrt{{\overline{{\Gamma}}}^{F}_{T}(\pi)\cdot
T}\cdot\sqrt{\mathbb{E}\left[F\big{(}P_{T}(A_{*})\big{)}-F\big{(}P_{0}(A_{*})\big{)}\right]}\,$
$\displaystyle\overset{(e)}{\leq}\sqrt{{\overline{{\Gamma}}}^{F}_{T}(\pi)\cdot{\mathrm{diam}_{F}(\Delta^{K-1})}\cdot
T}$

where $(a)$ follows from the definition of information ratio in (8), $(b)$
follows from Hölder’s inequality, $(c)$ follows from the definition of
${\overline{{\Gamma}}}^{F}_{T}(\pi)$ in (10), and from Lemma D.1, $(d)$
follows from the fact that the summation in $(c)$ is telescoping, and finally,
$(e)$ follows from the definition of ${\mathrm{diam}_{F}(\Delta^{K-1})}$ in
(5).

∎

###### Proof of Theorem 5.1.

Recalling the definition of Bayesian regret (2), we have

$\displaystyle\mathrm{Regret}(T,P_{*},\pi)$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{T-1}(R_{*}-R_{t+1,A_{t}})\right]$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{T-1}\left(\mathbb{E}_{t}\left[R_{*}-R_{t+1,A_{t}}\right]\right)\right]$
(64)

From the definition of information ratio in (8),

$\displaystyle\mathbb{E}\Big{[}{\mathbb{E}}_{t}\left[R_{*}-R_{t+1,A_{t}}\right]\Big{]}$
$\displaystyle=\mathbb{E}\left[\sqrt{\Gamma_{t}^{F}(\pi)\cdot{\mathbb{E}}_{t}\big{[}D_{F}\big{(}P_{t+1}(A_{*}),P_{t}(A_{*})\big{)}\big{]}}\,\right]$
$\displaystyle\leq\sqrt{\gamma_{FX}}\cdot\mathbb{E}\left[\sqrt{{\mathbb{E}}_{t}\big{[}D_{F}\big{(}P_{t+1}(A_{*}),P_{t}(A_{*})\big{)}\big{]}}\,\right]+\delta_{t}\cdot\varepsilon$
(65)

where we have used the following two inequalities to obtain (65): For each
$0\leq t\leq T-1$,

$\displaystyle\mathbb{P}\left(\Gamma_{t}^{F}(\pi)\leq\gamma_{FX}\right)$
$\displaystyle\geq 1-\delta_{t}$
$\displaystyle\mathbb{E}_{t}\left[R_{*}-R_{t+1,A_{t}}\right]$
$\displaystyle\leq\varepsilon$

Using (65) in (64):

$\displaystyle\mathrm{Regret}(T,\pi)$
$\displaystyle\leq\sqrt{\gamma_{FX}}\cdot\mathbb{E}\left[\sum_{t=0}^{T-1}\sqrt{{\mathbb{E}}_{t}\big{[}D_{F}\big{(}P_{t+1}(A_{*}),P_{t}(A_{*})\big{)}\big{]}}\right]+\varepsilon\cdot\sum_{t=0}^{T-1}\delta_{t}$
(66)

Applying Cauchy Schwarz and then applying Lemma D.1,

$\displaystyle\mathrm{Regret}(T,\pi)$
$\displaystyle\overset{(a)}{\leq}\sqrt{\gamma_{FX}\cdot
T\cdot\mathbb{E}\left[\sum_{t=0}^{T-1}{\mathbb{E}}_{t}\big{[}D_{F}\big{(}P_{t+1}(A_{*}),P_{t}(A_{*})\big{)}\big{]}\right]}+\varepsilon\cdot\sum_{t=0}^{T-1}\delta_{t}$
$\displaystyle\overset{(b)}{\leq}\sqrt{\gamma_{FX}\cdot
T\cdot\mathbb{E}\left[\sum_{t=0}^{T-1}{\mathbb{E}}_{t}\big{[}F\big{(}P_{t+1}(A_{*})\big{)}\big{]}-F\big{(}P_{t}(A_{*})\big{)}\right]}+\varepsilon\cdot\sum_{t=0}^{T-1}\delta_{t}$
$\displaystyle=\sqrt{\gamma_{FX}\cdot
T\cdot\mathbb{E}\left[\sum_{t=0}^{T-1}F\big{(}P_{t+1}(A_{*})\big{)}-F\big{(}P_{t}(A_{*})\big{)}\right]}+\varepsilon\cdot\sum_{t=0}^{T-1}\delta_{t}$
$\displaystyle\overset{(c)}{\leq}\sqrt{\gamma_{FX}\cdot
T\cdot\mathrm{diam}_{F}(\Delta^{k-1})}+\varepsilon\cdot\sum_{t=0}^{T-1}\delta_{t}$

where $(a)$ is an application of Cauchy Schwarz, $(b)$ follows from Lemma D.1,
and $(c)$ follows from the definition of $\mathrm{diam}_{F}(\cdot)$ in (5).

∎

###  D.1 Generalizing Theorem 5.1 beyond Example 15

Theorem 5.1 was specific to example 15. Here, we generalize this result to
propose a new template for analysis that can be used to upper bound the
Bayesian regret of any policy $\pi$. Contrary to the template proposed in
Section C (and the one that is commonly used in literature), the template we
propose here accounts for the temporal nature of the information ratio.

As in Section C, we will consider the generalized definition of information
ratio defined in (42): For any potential $F$ that satisfies
$\mathrm{diam}_{F}(\Delta^{K-1})<\infty$, and $\alpha\in\Re^{+}$, the
information ratio $\Gamma_{t}^{F}(\pi,\alpha)$ associated with policy $\pi$ at
time-step $t$ is

$\Gamma_{t}^{F}(\pi,\alpha)\mathbin{:=}\frac{\big{(}\Delta_{t}(\pi)-\alpha\big{)}^{2}}{g_{t}^{F}(\pi)}$

For any potential $F$ that satisfies $\mathrm{diam}_{F}(\Delta^{K-1})<\infty$,
$T\geq 0$, policy $\pi$,
$\boldsymbol{\alpha}=\\{\alpha_{t}:\alpha_{t}\in\Re^{+}\,,0\leq t\leq T-1\\}$,
and $\boldsymbol{\delta}=\\{\delta_{t}:\delta_{t}\in[0,1]\,,0\leq t\leq
T-1\\}$, define,

$\displaystyle{\mathrm{Regret}}^{\mathrm{FX}}(T,\pi,\boldsymbol{\alpha},\boldsymbol{\delta})\mathbin{:=}\sqrt{\gamma_{FX}(T,\pi,\boldsymbol{\alpha},\boldsymbol{\delta})\cdot
T\cdot{\mathrm{diam}_{F}(\Delta^{K-1})}}+\sum_{t=0}^{T-1}\left(\alpha_{t}+\delta_{t}\cdot\mathrm{Reg}_{\max}\right)$
(67)

where $\gamma_{FX}(T,\pi,\boldsymbol{\alpha},\boldsymbol{\delta})$ is any
deterministic constant that satisfies, for each $0\leq t\leq T-1$,

$\displaystyle\mathbb{P}\Big{(}\Gamma_{t}^{F}(\alpha_{t},\pi)\leq\gamma_{FX}(T,\pi,\boldsymbol{\alpha},\boldsymbol{\delta})\Big{)}\geq
1-\delta_{t}$ (68)

and $\mathrm{Reg}_{\max}$ is defined in (45):

$\mathrm{Reg}_{\max}=\max_{t\geq 0\,,a\in{\mathcal{A}}}\Delta_{t}(a)$

The proof of Theorem D.2 follows along exactly the same lines as the proof of
Theorem 3.1 and is thus omitted.

######  Theorem D.2.

For any policy $\pi$, $T\in\mathbb{N}$, $K\geq 2$,
$\boldsymbol{\alpha}=\\{\alpha_{t}:\alpha_{t}\in\Re^{+}\,,0\leq t\leq T-1\\}$
and $\boldsymbol{\delta}=\\{\delta_{t}:\delta_{t}\in[0,1]\,,0\leq t\leq
T-1\\}$,

$\displaystyle{\mathrm{Regret}}(T,\pi)\leq{\mathrm{Regret}}^{\mathrm{FX}}(T,\pi,\boldsymbol{\alpha},\boldsymbol{\delta})$

where $F$ is convex, and satisfies $\mathrm{diam}_{F}(\Delta^{K-1})<\infty$.

∎

Comments on Theorem D.2

Note that ${\mathrm{Regret}}^{\mathrm{FX}}$ and $\gamma_{FX}$ in (67) and (68)
are strict generalizations of ${\mathrm{Regret}}^{\mathrm{F}}$ and
$\gamma_{F}$ defined in (43) and (44) of Section C. That is, by letting
$\delta_{t}\equiv\delta$ and $\alpha_{t}\equiv\alpha$ for each $0\leq t\leq
T-1$, the definitions coincide.

Crucially, the analysis introduced in this section accounts for the time-
varying nature of the information ratio, since, a uniform high probability
upper bound such as the one in (44) may be too strict for analysis, but a
bound such as (68) allows for flexibility. Therefore, an algorithm that
achieves, for example, an order $\sqrt{KT}$ bound using an application of
Theorem D.2 need not achieve a similar bound using an application of, for
example, Corollary 3.2 or Theorem C.1 that use uniform (over time) upper
bounds on the information ratio in the analysis.

This was precisely the case for Thompson sampling applied to Example 15, for
which we proved a lower bound of order $\sqrt{KT\log(K)}$ for
${\mathrm{Regret}}^{\mathrm{F}}$ in Section C, and an upper bound of
$\sqrt{KT}$ in Proposition 18 (that is an application of Theorem D.2) with $F$
the negentropy potential.

##  Appendix E Proof of Proposition 18

To prove Proposition 18, we only need to show (17), which is formalized in the
following Proposition E.1. The final bound (18) then follows from Theorem 5.1.

######  Proposition E.1.

For all $t\geq 1$, $K\geq 2$, $p\in(0,1)$, and $\varepsilon\in(0,1-p)$,

$\displaystyle\mathbb{P}\left(\Gamma_{t}^{F}(\pi^{\mathrm{TS}})\leq{8}\right)$
$\displaystyle\geq 1-\frac{1}{\varepsilon}\cdot\sqrt{\frac{8K}{t}}$ (69)

∎

###### Proof of Proposition 18.

Letting $\gamma_{FX}=8$, and
$\delta_{t}=\frac{1}{\varepsilon}\cdot\sqrt{\frac{8K}{t}}$ for each $t\geq 0$,
and $\pi=\pi^{\mathrm{TS}}$, it follows from Theorem 5.1 and Proposition E.1
that

$\displaystyle{\mathrm{Regret}}(T,\pi^{\mathrm{TS}})$
$\displaystyle\leq\sqrt{\gamma_{FX}\cdot{\mathrm{diam}_{F}(\Delta^{K-1})}\cdot
T}+\varepsilon\cdot\sum_{t=0}^{T-1}\delta_{t}$
$\displaystyle=\sqrt{8\cdot\log(K)\cdot
T}+\sum_{t=0}^{T-1}\sqrt{\frac{8K}{t}}$
$\displaystyle\leq\sqrt{8\cdot\log(K)\cdot T}+2\sqrt{8KT}$ $\displaystyle\leq
3\sqrt{8KT}$

∎

The rest of the section is dedicated to the proof of Proposition E.1.

Denote:

$\displaystyle
q_{t}\mathbin{:=}\max_{a}\,\pi^{\mathrm{TS}}(a)=\max_{a}\mathbb{P}_{t}(A_{*}=a)$
(70)

We will first show the following result that upper bounds
$\Gamma_{t}^{F}(\pi^{\mathrm{TS}})$ as a function of $q_{t}$.

######  Proposition E.2.

For each $t\geq 0$, the following holds a.s.:

$\displaystyle{\mathbb{E}}_{t}\left[R_{*}-R_{t+1,A_{t}}\right]$
$\displaystyle\leq\varepsilon\cdot(1-q_{t}^{2})$ (71a) $\displaystyle
g_{t}^{F}(\pi^{\mathrm{TS}})$ $\displaystyle\geq 2\cdot\varepsilon^{2}\cdot
q_{t}^{2}\cdot(1-q_{t})^{2}$ (71b)
$\displaystyle\Gamma_{t}^{F}(\pi^{\mathrm{TS}})$
$\displaystyle\leq\frac{(1+q_{t})^{2}}{2\cdot q_{t}^{2}}$ (71c)

Consequently, if $\frac{1}{2}<q_{t}\leq 1$ for each $t$, then,

$\Gamma_{t}^{F}(\pi^{\mathrm{TS}})\leq 8$ (72)

###### Proof.

Applying Lemma B.3 (for Thompson sampling, we let
$\pi(a)=\mathbb{P}_{t}(A_{*}=a)$ in the Lemma) and Lemma 27:

$\displaystyle{\mathbb{E}}_{t}\big{[}R_{*}-R_{t+1,A_{t}}\big{]}$
$\displaystyle\overset{(a)}{=}\sum_{a\in{\mathcal{A}}}\mathbb{P}_{t}(A_{*}\\!=\\!a)\left(\mathbb{E}_{t}\big{[}R_{t+1,a}|A_{*}\\!=\\!a\big{]}-\mathbb{E}_{t}\big{[}R_{t+1,a}\big{]}\right)$
$\displaystyle\overset{(b)}{=}\sum_{a\in{\mathcal{A}}}\mathbb{P}_{t}(A_{*}\\!=\\!a)\left(\varepsilon-\varepsilon\cdot\mathbb{P}_{t}(A_{*}\\!=\\!a)\right)$
$\displaystyle=\varepsilon\cdot\left(1-\sum_{a\in{\mathcal{A}}}\mathbb{P}_{t}^{2}(A_{*}\\!=\\!a)\right)$
$\displaystyle\leq\varepsilon\cdot\left(1-\left[\max_{a}\,\mathbb{P}_{t}(A_{*}\\!=\\!a)\right]^{2}\right)$
$\displaystyle=\varepsilon\cdot\left(1-q_{t}^{2}\right)$

where $(a)$ follows from Lemma B.3 and $(b)$ follows from Lemma 27. We have
shown (71a).

To prove (71b), we will use the following inequality (which is a consequence
of Pinsker’s) from [18] (see Fact 9 and the inequality that follows
immediately below on page 15):

${\mathbb{E}}_{t}\big{[}R_{t+1,a}|A_{*}=a_{*}\big{]}-{\mathbb{E}}_{t}\big{[}R_{t+1,a}\big{]}\leq\sqrt{\frac{1}{2}D_{{\mathrm{KL}}}\Big{(}P_{t}\big{(}R_{t+1,a}|A_{*}\\!=\\!a_{*}\big{)}||P_{t}\big{(}R_{t+1,a}\big{)}\Big{)}}$
(73)

Combing (29) of Lemma B.3 with (73):

$\displaystyle g_{t}^{F}(\pi^{\mathrm{TS}})$
$\displaystyle=\sum_{a_{*},a\in{\mathcal{A}}}\mathbb{P}_{t}(A_{*}\\!=\\!a)\mathbb{P}_{t}(A_{*}\\!=\\!a_{*})\Big{[}D_{{\mathrm{KL}}}\Big{(}P_{t}\big{(}R_{t+1,a}|A_{*}\\!=\\!a_{*}\big{)}||P_{t}\big{(}R_{t+1,a}\big{)}\Big{)}\Big{]}$
$\displaystyle\geq
2\cdot\sum_{a_{*},a\in{\mathcal{A}}}\mathbb{P}_{t}(A_{*}\\!=\\!a)\mathbb{P}_{t}(A_{*}\\!=\\!a_{*})\cdot\left({\mathbb{E}}_{t}\big{[}R_{t+1,a}|A_{*}=a_{*}\big{]}-{\mathbb{E}}_{t}\big{[}R_{t+1,a}\big{]}\right)^{2}$
$\displaystyle\overset{(a)}{\geq}2\cdot\varepsilon^{2}\cdot\left(\max_{a}\mathbb{P}_{t}(A_{*}\\!=a)\right)^{2}\cdot\left(1-\max_{a}\mathbb{P}_{t}(A_{*}\\!=a)\right)^{2}$
$\displaystyle=2\cdot\varepsilon^{2}\cdot
q_{t}^{2}\cdot\left(1-q_{t}\right)^{2}$

Where $(a)$ follows from Lemma 27: we have ignored all terms in the summation
except the one corresponding to $a=a_{*}$, and $a$ being the maximizer of
$\mathbb{P}_{t}(A_{*}=a)$. We have now shown (71b).

The final inequality (71c) follows from the definition (8).

∎

Next, in the following proposition we show that for large $t$, the posterior
$\mathbb{P}_{t}(A_{*}=\cdot)$ is concentrated.

######  Proposition E.3.

For all $t\geq 1$, $K\geq 2$, $p\in(0,1)$, and $\varepsilon\in(0,1-p)$,

$\displaystyle\mathbb{P}\left(q_{t}>\frac{1}{2}\right)$ $\displaystyle\geq
1-\frac{1}{\varepsilon}\cdot\sqrt{\frac{8K}{t}}$ (74)

∎

### Proof of Proposition E.3

Recall the definition of $\Delta_{t}$: for each $a\in{\mathcal{A}}$, and
$t\geq 0$,

$\Delta_{t}(a)=\mathbb{E}_{t}\left[R_{*}-R_{t+1,a}\right]$

The following result is a special case of Proposition 8 of [21]:

######  Lemma E.4 (Proposition 8 of [21]).

For each $T\geq 1$, suppose the actions $\\{A_{t}:0\leq t\leq T-1\\}$ are
selected according to $\mathbb{P}_{t}(A_{t}=a)=\mathbb{P}_{t}(A_{*}=a)$, then,

${\mathbb{E}}\left[\min_{a}\Delta_{T}(a)\right]\leq\frac{{\mathrm{Regret}}(T,\pi^{\mathrm{TS}})}{T}$

First, note that the quantity on the left hand side depends on the particular
policy (in this case, Thompson sampling), since the posterior that affects
$\Delta_{T}(a)$ is a function of the past actions that are chosen according to
the policy. Lemma E.4 says that, if we can bound the worst case regret (over
all priors) for Thompson sampling, we can bound
${\mathbb{E}}\left[\min_{a}\Delta_{T}(a)\right]$. And since we know from [13]
that for any distribution $P_{*}$ on ${\mathcal{P}}$,

${\mathrm{Regret}}(T,\pi^{\mathrm{TS}})\leq\sqrt{2KT}$

we have:

${\mathbb{E}}\left[\min_{a}\Delta_{T}(a)\right]\leq\sqrt{\frac{2K}{T}}$ (75)

Lemma 76 just follows from definitions.

######  Lemma E.5.

For each $t\geq 0$,

$\min_{a}\Delta_{t}(a)=\varepsilon\cdot\left(1-\max_{a}\mathbb{P}_{t}(A_{*}=a)\right)$
(76)

###### Proof.

We just need to observe that

$\displaystyle\Delta_{t}(a)$
$\displaystyle=\mathbb{E}_{t}\left[R_{*}-R_{t+1,a}\right]$
$\displaystyle=p+\varepsilon-p-\varepsilon\cdot\mathbb{P}_{t}(A_{*}=a)$
$\displaystyle=\varepsilon\cdot\left(1-\mathbb{P}_{t}(A_{*}=a)\right)$

where the second equality follows from Lemma 27. ∎

We are now ready to give the proof of Proposition E.3.

###### Proof of Proposition E.3.

Note that:

$\displaystyle\min_{a}\mathbb{P}_{t}(A_{*}\neq a)$
$\displaystyle=1-\max_{a}\mathbb{P}_{t}(A_{*}=a)$ (77)
$\displaystyle=\frac{1}{\varepsilon}\left[\min_{a}\Delta_{t}(a)\right]$

where the second equality follows from Lemma 76.

Taking expectations on both sides, and then applying (75),

$\displaystyle{\mathbb{E}}\left[\min_{a}\mathbb{P}_{t}(A_{*}\neq a)\right]$
$\displaystyle=\frac{1}{\varepsilon}\cdot{\mathbb{E}}\left[\min_{a}\Delta_{t}(a)\right]$
$\displaystyle\leq\frac{1}{\varepsilon}\cdot\sqrt{\frac{2K}{t}}$ (78)

Applying Markov’s inequality, we have:

$\displaystyle\mathbb{P}\left(\min_{a}\mathbb{P}_{t}(A_{*}\neq
a)\geq\frac{1}{2}\right)\leq\frac{1}{\varepsilon}\sqrt{\frac{8K}{t}}$ (79)

This implies the required bound (74):

$\displaystyle\mathbb{P}\left(\min_{a}\mathbb{P}_{t}(A_{*}\neq
a)\geq\frac{1}{2}\right)$
$\displaystyle\leq\frac{1}{\varepsilon}\sqrt{\frac{8K}{t}}$
$\displaystyle\implies\mathbb{P}\left(\max_{a}\mathbb{P}_{t}(A_{*}=a)\leq\frac{1}{2}\right)$
$\displaystyle\leq\frac{1}{\varepsilon}\sqrt{\frac{8K}{t}}$
$\displaystyle\implies\mathbb{P}\left(\max_{a}\mathbb{P}_{t}(A_{*}=a)>\frac{1}{2}\right)$
$\displaystyle\geq 1-\frac{1}{\varepsilon}\sqrt{\frac{8K}{t}}$ (80)

∎

###### Proof of Proposition E.1.

It follows directly by combining Proposition 72 and Proposition E.3. ∎

##  Appendix F Details of Experimental Results and Additional Experimental
Results

###  F.1 Implementation Details for Numerical Results in Section 6.1

Here we give details on implementation of Thompson sampling, Shannon-IDS and
Tsallis-IDS applied to Example 15.

For this example, for each $t\geq 0$, given
$H_{t}=\\{A_{s},R_{s+1,A_{s}}:s=0,1,2,\ldots,t-1\\}$, we can compute the
posterior distribution on the optimal action:

$\mathbb{P}_{t}(A_{*}=a)=\frac{(1+\epsilon/p)^{s_{a}(t)}(1-\epsilon/(1-p))^{f_{a}(t)}}{\sum_{a^{\prime}\in{\mathcal{A}}}(1+\epsilon/p)^{s_{a^{\prime}}(t)}(1-\epsilon/(1-p))^{f_{a^{\prime}}(t)}}$
(81)

where,

$\displaystyle s_{a}(t)$
$\displaystyle=\sum_{s=1}^{t-1}R_{s+1,A_{s}}\cdot\mathbb{I}\\{A_{s}=a\\}$
$\displaystyle f_{a}(t)$
$\displaystyle=\sum_{s=1}^{t-1}(1-R_{s+1,A_{s}})\cdot\mathbb{I}\\{A_{s}=a\\}$

are the total number of $1$’s and $0$’s observed from arm $a$ at time $t-1$.
From (81), we can implement each of the algorithms as described below.

####  F.1.1 Thompson Sampling

At each iteration $t\geq 0$, Thompson sampling simply chooses action $a$ with
probability $\pi^{\mathrm{TS}}(a)$, where
$\pi^{\mathrm{TS}}(a)=\mathbb{P}_{t}(A_{*}=a)$.

####  F.1.2 Shannon-IDS

It follows from Lemma B.3 that at each time-step, the numerator and
denominator of the information ratio $\Gamma_{t}^{F}(\pi)$ defined in (8) can
be computed using:

$\displaystyle g_{t}^{F}(\pi)$
$\displaystyle=\sum_{a_{*},a\in{\mathcal{A}}}\pi(a)\mathbb{P}_{t}(A_{*}=a_{*})\Big{[}D_{{\mathrm{KL}}}\Big{(}P_{t}\big{(}R_{t+1,a}|A_{*}=a_{*}\big{)}||P_{t}\big{(}R_{t+1,a}\big{)}\Big{)}\Big{]}$
(82) $\displaystyle\Delta_{t}(\pi)$
$\displaystyle=\sum_{a\in{\mathcal{A}}}\mathbb{P}_{t}(A_{*}=a)\mathbb{E}_{t}\big{[}R_{t+1,a}|A_{*}\\!=\\!a\big{]}-\sum_{a\in{\mathcal{A}}}\pi(a)\mathbb{E}_{t}\big{[}R_{t+1,a}\big{]}$
(83)

In (82), the KL divergence has the following closed form (see (32), and the
proof of Proposition 26 for the derivation):

$\displaystyle
D_{{\mathrm{KL}}}\Big{(}P_{t}\big{(}R_{t+1,a}|A_{*}\\!=\\!a_{*}\big{)}||P_{t}\big{(}R_{t+1,a}\big{)}\Big{)}$
$\displaystyle\hskip
57.81621pt\\!=\\!\begin{cases}\displaystyle(1\\!-\\!p\\!-\\!\varepsilon)\log\left(\frac{1-p-\varepsilon}{1-p-\varepsilon\cdot\mathbb{P}_{t}(A_{*}=a)}\right)+(p\\!+\\!\varepsilon)\log\left(\frac{p+\varepsilon}{p+\varepsilon\cdot\mathbb{P}_{t}(A_{*}=a)}\right)&\,\,\,\text{If}\,\,a=a_{*}\\\\[13.99995pt]
\displaystyle(1\\!-p)\log\left(\frac{1-p}{1-p-\varepsilon\cdot\mathbb{P}_{t}(A_{*}=a)}\right)+p\log\left(\frac{p}{p+\varepsilon\cdot\mathbb{P}_{t}(A_{*}=a)}\right)&\,\,\,\text{If}\,\,a\neq
a_{*}\end{cases}$ (84)

Similarly, the right hand side of (83) can be evaluated for the counter
example as (once again, see proof of Proposition 26 for the derivation):

$\Delta_{t}(\pi)=\varepsilon-\sum_{a\in{\mathcal{A}}}\pi(a)\cdot\varepsilon\cdot\mathbb{P}_{t}(A_{*}=a)$

From the above calculations, at each iteration $t\geq 0$, the Shannon-IDS
agent chooses action $a$ with probability $\pi^{\mathrm{NDS}}$:

$\pi^{\mathrm{NDS}}\in\operatorname*{arg\,min}_{\pi}\,\,\Gamma_{t}^{F}(\pi)\equiv\operatorname*{arg\,min}_{\pi}\,\,\frac{\big{[}\Delta_{t}(\pi)\big{]}^{2}}{g_{t}^{F}(\pi)}$
(85)

In our implementation, we use the fact that it is sufficient to search over
all two-action support policies to solve (85) (see [21], in particular
Algorithm 3).

####  F.1.3 Tsallis-IDS

The Tsallis information gain can be computed using the following expressions:
$g_{t}^{F}(\pi)=\sum_{a}\pi(a)g_{t}^{F}(a)$, where

$\displaystyle
g_{t}^{F}(a)=\sum_{a_{*}\in{\mathcal{A}}}\sqrt{\mathbb{P}_{t}(A_{*}=a_{*})}\Bigg{(}\left(\sqrt{\mathbb{P}_{t}\big{(}R_{t+1,a}=0\big{)}}-\sqrt{\mathbb{P}_{t}\big{(}R_{t+1,a}=0|A_{*}=a_{*}\big{)}}\right)^{2}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\left(\sqrt{\mathbb{P}_{t}\big{(}R_{t+1,a}=1\big{)}}-\sqrt{\mathbb{P}_{t}\big{(}R_{t+1,a}=1|A_{*}=a_{*}\big{)}}\right)^{2}\Bigg{)}$
(86)
$\displaystyle=\begin{cases}\displaystyle\sum_{a_{*}\in{\mathcal{A}}}\sqrt{\mathbb{P}_{t}(A_{*}=a_{*})}\Big{(}\left(\sqrt{1\\!-\\!p\\!-\\!\varepsilon\mathbb{P}_{t}(A_{*}=a)}-\sqrt{1\\!-\\!p\\!-\\!\varepsilon}\right)^{2}+\left(\sqrt{p\\!+\\!\varepsilon\mathbb{P}_{t}(A_{*}=a)}-\sqrt{p\\!+\\!\varepsilon}\right)^{2}\Big{)}&a=a_{*}\\\
\displaystyle\sum_{a_{*}\in{\mathcal{A}}}\sqrt{\mathbb{P}_{t}(A_{*}=a_{*})}\Big{(}\left(\sqrt{1\\!-\\!p\\!-\\!\varepsilon\mathbb{P}_{t}(A_{*}=a)}-\sqrt{1\\!-\\!p}\right)^{2}+\left(\sqrt{p\\!+\\!\varepsilon\mathbb{P}_{t}(A_{*}=a)}-\sqrt{p}\right)^{2}\Big{)}&a\neq
a_{*}\end{cases}$ (87)

The derivation of (86) follows from the definition of $g_{t}^{F}$, and can be
found in [13] (see proof of Theorem 7 in Appendix B). The right hand side of
(86) can be simplified to (87) using Lemma 27. At each iteration $t\geq 0$,
computing $g_{t}^{F}(\pi)$ from (87) is straightforward using (81).

From the above calculations, at each iteration $t\geq 0$, the Tsallis-IDS
agent chooses action $a$ with probability $\pi^{\mathrm{TDS}}$:

$\pi^{\mathrm{TDS}}\in\operatorname*{arg\,min}_{\pi}\,\,\frac{\big{[}\Delta_{t}(\pi)\big{]}^{2}}{g_{t}^{F}(\pi)}$
(88)

Once again, it is sufficient to search over all two-action support policies to
solve (88).

###  F.2 Implementation Details for Beta Bernoulli Bandits in Section 6.2

Here we give details of the implementation for the results in Section 6.2.

In the Beta-Bernoulli setting, at time $0$, the mean $\theta_{a}$ of each arm
$a\in{\mathcal{A}}$ is assumed to be independent and beta-distributed with
prior parameters $(\beta_{0,a}^{1},\beta_{0,a}^{2})$. In our experiments, we
let $(\beta_{0,a}^{1},\beta_{0,a}^{2})=(1,1)$.

For $t\geq 0$, after taking action $A_{t}$ and observing
$R_{t+1,A_{t}}\in\\{0,1\\}$, the posterior parameters
$(\beta_{t+1,a}^{1},\beta_{t+1,a}^{2})$ can be computed using

$\displaystyle\beta_{t+1,a}^{1}$
$\displaystyle=\beta_{t,a}^{1}+R_{t+1,A_{t}}\cdot\mathbb{I}_{A_{t}=a}$
$\displaystyle\beta_{t+1,a}^{2}$
$\displaystyle=\beta_{t,a}^{2}+(1-R_{t+1,A_{t}})\cdot\mathbb{I}_{A_{t}=a}$

####  F.2.1 Thompson Sampling

At time-step $t$, the Thompson sampling agent samples
$\theta_{a}^{\prime}\sim(\beta_{t,a}^{1},\beta_{t,a}^{2})$ and chooses action
$A_{t}=a_{*}$ where:

$a_{*}=\operatorname*{arg\,max}_{a}\,\,\theta_{a}^{\prime}.$

####  F.2.2 Shannon-IDS

At each time-step, the Shannon-IDS agent computes the information ratio
according to the definition in (8). For the Beta-Bernoulli problem, Algorithm
2 of [21] (on page 12) can be used to compute the numerator and denominator of
the information ratio. The algorithm takes as input the current beta
parameters $(\beta_{t,a}^{1},\beta_{t,a}^{2})$.

As discussed in [21], the algorithm can not readily be implemented on a
computer because several steps of the algorithm involves computing integrals
of continuous functions. In our implementation, we approximate the integrals
using summations via discretization. Once the information ratio is computed,
Algorithm 3 of [21] can be used to obtain the policy that minimizes the
information ratio.

####  F.2.3 Tsallis-IDS

The Tsallis-IDS algorithm follows along the same lines as the Shannon-IDS
algorithm, except for a modification of the information gain computation step.
Specifically, to compute the information ratio, we use Algorithm 2 of [21], by
replacing line 10 of the algorithm with:

$\vec{g}_{a}\leftarrow\sum_{a^{\prime}}\sqrt{p^{*}(a^{\prime})}\cdot\left(\left(\sqrt{\frac{\beta_{a}^{1}}{\beta_{a}^{1}+\beta_{a}^{2}}}-\sqrt{M_{a|a^{\prime}}}\right)^{2}+\left(\sqrt{\frac{\beta_{a}^{2}}{\beta_{a}^{1}+\beta_{a}^{2}}}-\sqrt{1-M_{a|a^{\prime}}}\right)^{2}\right)$

The rest of the steps are identical to Shannon-IDS.

###  F.3 Additional Experimental Results for Example 15

For a given potential $F$, and a policy $\pi$, define

$\widehat{\Gamma}^{F}_{t}(\pi)\mathbin{:=}\frac{\Big{(}{\mathbb{E}}\big{[}\Delta_{t}(\pi)\big{]}\Big{)}^{2}}{\mathbb{E}[g_{t}^{F}(\pi)]}$
(89)

Contrary to $\Gamma_{t}^{F}$ defined in (8), $\widehat{\Gamma}^{F}_{t}$ is
_not_ a random variable, since we are taking expectation over all possible
histories in both the numerator and denominator. By a simple modification of
the proof of Theorem 3.1, it is not difficult to show that (see for example
[22, 7] that consider the special case of Shannon information ratio), for any
policy $\pi$,

$\displaystyle{\mathrm{Regret}}(T,\pi)$
$\displaystyle\leq\\!\sqrt{\widehat{{\overline{{\Gamma}}}}_{T}(\pi)\\!\cdot\\!T\\!\cdot\\!{\mathrm{diam}_{F}(\\!\Delta^{K-1}\\!)}}$
(90) $\displaystyle\widehat{{\overline{{\Gamma}}}}_{T}(\pi)$
$\displaystyle=\frac{1}{T}\sum_{t=0}^{T-1}\widehat{\Gamma}^{F}_{t}(\pi)$

Figure 7: Estimate of $\widehat{\Gamma}^{F}_{t}$ plotted as a function of time
for Thompson sampling applied to the counter example of Section 4.

Figure 8: Estimate of $\widehat{\Gamma}^{F}_{t}(\pi^{\mathrm{IDS}})$ plotted
as a function of time for Shannon-IDS and Tsallis-IDS applied to the counter
example 15.

In Figure 7 we plot the estimate of the scaled information ratio
$\widehat{\Gamma}^{F}_{t}(\pi^{\mathrm{TS}})\times\mathrm{diam}_{F}(\Delta^{K-1})$
as a function $t$, for each of the two potential functions: negentropy and
$1/2$-Tsallis entropy. The exact expectations in both the numerator and
denominator of $\widehat{\Gamma}^{F}_{t}(\pi)$ in (89) was replaced by the
empirical averages obtained using the $N$ sample paths.

It is interesting to see that as $t$ gets large, the information ratio
corresponding to both potentials quickly converge, even though they have a
noticeable difference at $t=0$. This is especially true when $K$ is large, in
which case it is known that the initial difference between the scaled
information ratios is large. The dashed lines indicate the worst case bounds
on $\widehat{\Gamma}^{F}_{t}(\pi)\times\mathrm{diam}_{F}(\Delta^{K-1})$ for
the two potentials.

In Figure 8 we plot estimate of
$\widehat{\Gamma}^{F}_{t}(\pi^{\mathrm{IDS}})\times\mathrm{diam}_{F}(\Delta^{K-1})$
for the two IDS algorithms. Different from Thompson sampling, we notice that
the information ratio decreases more drastically, and after reaching a certain
threshold, it seems to stabilize. For $K=40$, we notice that for $t\geq
4\times 10^{5}$, there’s a lot of chattering of the information ratios. We
conjecture that this is the region where the algorithms have identified the
optimal arm, and the information gain and the instantaneous regret, both are
near zero.

###  F.4 Additional Experimental Results for Beta Bernoulli

Figure 9: Estimate of $\widehat{\Gamma}_{t}^{F}(\pi^{\mathrm{TS}})$ as a
function of time, for $K=60$ and $K=80$ Beta-Bernoulli. Figure 10: Empirical
average and $2\sigma$ confidence intervals of
$\widehat{\Gamma}_{t}^{F}(\pi^{\mathrm{IDS}})$ as a function of time, for
$K=60$ and $K=80$ Beta-Bernoulli.

In Figures 9 and 10 we plot scaled $\widehat{\Gamma}^{F}_{t}$ for Thompson
sampling and IDS algorithms as a function of time. We observe that the
information ratios decrease much more quickly in this experiment, compared to
the counter example of Section 4. More importantly, we notice that the scaled
information ratio for negentropy is consistently lower than the scaled
information ratio for the $1/2$-Tsallis entropy, despite the worst case bound
being larger for both $K=60$ and $K=80$.