# Effective Dimension in Bandit Problems under Censorship

Gauthier Guinet
AWS AI Labs
<EMAIL_ADDRESS>
&Saurabh Amin
MIT
<EMAIL_ADDRESS>
&Patrick Jaillet
MIT
<EMAIL_ADDRESS>
Work done prior to joining Amazon.Dept. of Civil and Environmental Engineering
& Laboratory for Information and Decision Systems.Dept. of Electrical
Engineering and Computer Science & Laboratory for Information and Decision
Systems.

###### Abstract

In this paper, we study both multi-armed and contextual bandit problems in
censored environments. Our goal is to estimate the performance loss due to
censorship in the context of classical algorithms designed for uncensored
environments. Our main contributions include the introduction of a broad class
of censorship models and their analysis in terms of the _effective dimension_
of the problem – a natural measure of its underlying statistical complexity
and main driver of the regret bound. In particular, the effective dimension
allows us to maintain the structure of the original problem at first order,
while embedding it in a bigger space, and thus naturally leads to results
analogous to uncensored settings. Our analysis involves a continuous
generalization of the Elliptical Potential Inequality, which we believe is of
independent interest. We also discover an interesting property of decision-
making under censorship: a transient phase during which initial
misspecification of censorship is self-corrected at an extra cost; followed by
a stationary phase that reflects the inherent slowdown of learning governed by
the effective dimension. Our results are useful for applications of sequential
decision-making models where the feedback received depends on strategic
uncertainty (e.g., agents’ willingness to follow a recommendation) and/or
random uncertainty (e.g., loss or delay in arrival of information).

##  1 Introduction

Bandit problems are prototypical models of sequential decision-making under
uncertainty. They are widely studied due to their applications in recommender
systems, online advertising, medical treatment assignment, revenue management,
network routing and control lattimore2020bandit ; MAL-068 . Our work is
motivated by settings in which the feedback received by the decision-maker in
each round of decision is censored by a stochastic process that depends on the
current action as well as past history of feedbacks and actions. For instance,
in typical missing data problems, the decision-maker needs to deal with
frequent losses of information (or delays in arrival of information) due to
exogeneous failures such as faulty and/or unreliable communication. Missing
observations in dynamical interactions with the environment are a common
concern in diverse fields ranging from operations management to health
sciences to physical sciences YANG20091896 ; HonKin10 ; little2002statistical
. In other settings, such as AI-driven platforms for health alerts, route
guidance, and product recommendations NEURIPS2019_e49eb652 ;
yu2021reinforcement , the reception of feedback depends on whether or not the
decision (or recommendation) is adopted by strategic agents (e.g. patients,
customers or drivers) with private valuations. Thus, from the platform’s
viewpoint, the adoption behavior of heterogeneous agents can be regarded as a
_stochastic censorship process_.

In static environments, the bias induced by the presence of randomly missing
information has been thoroughly studied little2002statistical ; review_missing
. However, in online settings, the dynamics of learning and acting are
inherently coupled: since censorship mediates current information of the
environment, it impacts the outcome of data-driven decision process; this in
turn conditions the future decisions and future censored feedback, creating a
complex and endogenous joint temporal dependency. Our work contributes to the
analysis of such phenomena for a broad classes of decision and censorship
models. Importantly, it is the first _normative inquiry_ of how censorship
impacts the statistical complexity of bandit problems. We develop an analysis
approach that is useful for both estimating the performance loss due to
censorship and refining the classical algorithms designed for uncensored
environments.

###  1.1 Related Work

Within the extensive bandits literature, well-surveyed in
(lattimore2020bandit, ; MAL-068, ), our work is most closely related to
stochastic delayed bandits. Initially, this line of work focused on the joint
evolution of actions and information in settings where the reception of the
latter is delayed dudik2011efficient . Of particular interest is the packet
loss model recently introduced in stoch_unrest_delay , which provides the
regret bound $\mathcal{O}(\frac{1}{p}R_{T})$ where $R_{T}$ is the uncensored
regret and $p$ the censorship probability. Analogous results have been shown
in the context of Combinatorial Multi-Armed Bandits with probabilistically
triggered arms; see for example, JMLR:v17:14-298  and NIPS2017_a8e864d0 . Our
work provides a systematic approach to study more general censorship models,
and sheds light on how the impact of coupled feedback and censorship
realizations on the expected regret can be evaluated in terms of the
_effective dimension_ of the problem.

Importantly, we also tackle the contextual bandit problems, where relatively
few results are available on the regret under missing or censored feedback. A
notable exception is the work of pmlr-v119-vernade20a , who focus on a
different information structure and obtain a scaling of $1/p$ (see Remark
4.4). A related contribution by theshold_pot  provides both a potential-based
analysis of the Upper Confidence Bound algorithm (UCB) for multi-armed bandits
and an algorithmic variant leveraging the Kaplan-Meier estimator, although
their censorship setting is different than ours. In particular, our results
are applicable to settings when delay is significantly large (possibly
infinite). This is in contrast to prior results on bandits with delayed
information structure which assume either that the delay is constant, upper
bounded, has a finite mean, or simply provide regret guarantees that are
linear in the cumulative delays up to time $T$ (dudik2011efficient, ;
joulani2013online, ; queue_delay, ; ZhouGLM, ; pike2018bandits, ). Under such
assumptions on delay, one usually gets a second order additive dependency of
the regret in terms of delay parameters, which practically says that delay is
benign for bandits. On the other hand, we show that censorship leads to a
first order multiplicative dependency on regret and we provide a complete
characterization of this dependency for a wide range of bandits and censorship
models.

Moreover, the abovementioned works primarily focus on modifying well-known
bandit algorithms to account for delays, or propose new delay-robust
algorithms which may be difficult to implement in practice; a notable
exception includes wu2022thompson  but it focuses on Thompson Sampling. In our
work, we instead focus on estimating the performance loss due to censorship
and derive insights on the behavior of well-known UCB class of algorithms
(li2010contextual, ; pmlr-v15-chu11a, ; NIPS2011_e1d5be1c, ). These algorithms
are widely used in practice; moreover, their theoretical study has been shown
to be useful for analysis of broader class of algorithms (notably Thompson
Sampling agrawal2012analysis ; tsVanRoy  and Information-Directed Sampling
(NIPS2014_301ad0e3, ; pmlr-v75-kirschner18a, )).

On a somewhat related note, the literature on non-stochastic multi-armed
bandit problems with delays (NIPS2010_7bb06076, ; pmlr-v49-cesa-bianchi16, ;
NEURIPS2020_33c5f5bf, ) also tackles multiplicative dependency, although in a
different setting than ours. Another related line of work is Partial
Monitoring (JMLR:v11:audibert10a, ; partialmonitor, ) which deals with generic
categorization of learnability, rather than a fine-grained analysis of
dimensionality in relation to censorship, which is our current focus.

Our work contributes to the Generalized Linear Contextual Bandits literature
NIPS2010_c2626d85 ; li2017provably  in two ways: firstly, through the use of
these models in a sequential decision-making framework on which the impact of
censorship is assessed in Sec. 4. Secondly, by showing that our multi-
threshold censorship model $\mathcal{MT}$ induces, at first order, a non-
linear structure that closely mirrors such models. Our results provide new
tools to study this structure. It is useful to note that the notion of
effective dimension has been well-studied in the statistical learning and
kernels literature (GPBandit, ; 6138914, ) (where it is defined for a Gram
matrix $K_{n}$ and regularization $\lambda$ as
$d^{n}_{\text{eff}}(\lambda)=\text{tr}(K_{n}(K_{n}+\lambda\mathbb{I}_{d})^{-1})$).
Our work shows that an analogous quantity governs the regret bound of bandit
problems in censored settings.

Finally, there is a rich literature on classical missing and censored data
problems little2002statistical ; review_missing . Although conditional on the
choice of a given action the missing data/censorship process we study is an
instance of missing-completely-at-random (MCAR), the online action generating
process adds a significant difficulty to the problem: whereas MCAR is
typically studied under a well-defined distributional assumption (e.g. i.i.d.
generation of action), our problem needs to deal with adaptive (hence non
i.i.d.) data generation process with respect to the filtration of past
information. In particular, the structure of missing data set results from
strong endogenous dependencies with past realization of the censorship (see
Sec. 2).

###  1.2 Summary of Results

In Sec. 3, we consider Multi-Armed Bandit (MAB) models and prove that the
regret scales as $\tilde{\mathcal{O}}(d_{\mathit{eff}}\sqrt{T})$ (Thm. 3.1),
where $d_{\mathit{eff}}$ is the effective dimension with value
$\sum_{a\in[d]}\frac{1}{p_{a}}$. In doing so, we recover and generalize
related results from (stoch_unrest_delay, ; JMLR:v17:14-298, ) to more complex
regularized settings and noise models. In particular, we prove that the
effective dimension results from characterizing the so-called censored
cumulative potential $\mathbb{V}_{\alpha}$. Interestingly, we also show that
the adaptive nature of censorship on $\mathbb{V}_{\alpha}$ plays only a second
order role (Prop. 3.7), that is, impact of censorship can be treated in an
offline manner at first order.

Importantly, our study of MAB under censorship instantiates an analysis
framework which extends to Linear Contextual Bandits (LCB) (Sec. 4). Our main
result provides that regret is still governed by the effective dimension, but
now with a dependency of $\tilde{\mathcal{O}}(\sigma\sqrt{d\cdot
d_{\mathit{eff}}}\sqrt{T})$ (Thm. 4.1). To the best of our knowledge, these
regret bounds provide the first theoretical characterization in LCB with
censorship, and contribute to the literature by evaluating the impact of
censorship on the performance of UCB-type algorithms. Our second main
contribution is identifying the effective dimension for a broad class of
multi-threshold models $\mathcal{MT}$ as well as a precise understanding of
the dynamic behavior induced by these models (Thm. 4.6). In particular, we
find that censorship introduces a two-phase behavior: a transient phase during
which the initial censoring misspecification is self-corrected at an
additional cost; followed by a stationary phase that reflects the inherent
slowdown of learning governed by the effective dimension. In extending our
analysis from MAB to LCB, we also develop a continuous generalization of the
widely used Elliptical Potential Inequality (Prop. 4.3), which we believe is
also of independent interest. Finally, our results (Thm. 3.1 and Prop. 3.2 for
MAB and Thm. 4.1 for LCB) suggest that the UCB class of algorithms is indeed a
reliable method for stochastic bandits problems under censorship.

##  2 Problem Setup and Background

#### Bandit Model:

We successively consider stochastic multi-armed bandits (Sec. 3) and Linear
Contextual Bandits (LCB) (Sec. 4) in censored environments. In both settings,
at each round $t\leq T$, the agent observes an action set
$\mathcal{A}_{t}\subset\mathcal{A}$. She then selects an action
$a_{t}\in\mathcal{A}_{t}$ (i.e. an arm) to which a noisy feedback
$r(a_{t})+\epsilon_{t}$ is associated, where $r(a_{t})$ is a bounded reward
and $\epsilon_{t}$ is an i.i.d. sub-Gaussian noise of pseudo-variance
$\sigma^{2}$. For action $a$, the sub-optimality gap at time $t$ is denoted
$\Delta_{t}(a)\triangleq\max_{\tilde{a}\in\mathcal{A}_{t}}r(\tilde{a})-r(a)$,
and the maximal gap $\Delta_{max}\triangleq\max_{a,t}\Delta_{t}(a)$. We now
recall the specifics of each model:

  * •

MAB: There is a finite number of actions $d$, enumerated as
$\mathcal{A}\triangleq[d]$, each having a scalar reward $\theta^{\star}_{a}$.
Arms are independent: playing one arm gives no information about the others.

  * •

LCB: The action set $\mathcal{A}_{t}$ is a subset of the unit ball
$\mathbb{B}_{d}$, possibly infinite. Unless explicitly mentioned, the reward
is assumed to be linear with respect to a latent unknown vector
$\theta^{\star}\in\mathbb{R}^{d}$, i.e. $r(a)=\langle
a,\theta^{\star}\rangle$. Non-stochastic contexts are modeled by the fact that
$\mathcal{A}_{t}$ is drawn by an oblivious adversary. Here one does not need
to rely on the typical i.i.d assumption on their generating process ZhouGLM ;
NIPS2010_c2626d85 .

#### Information Structure:

In the classical uncensored setting, the noisy feedback is immediately
observed post-decision and utilized to make decisions in the next round. We
introduce the following censorship model: an independent Bernoulli random
variable of parameter $p(a_{t})$ denoted as $x_{a_{t}}$ is drawn after each
decision $a_{t}$ and the feedback is observed, i.e., realized, if and only if
$x_{a_{t}}=1$; else the feedback is said to be censored. We recover the
uncensored setting when $p(a)\equiv 1$. Henceforth, in both finite and linear
settings, the Bernoulli parameter corresponding to the censorship probability
depends on the action chosen i.e. our model allows the censorship to be
heterogeneous across actions. Given that the action chosen at time $t$ is a
random variable, $p(a_{t})$ refers to a random variable as well.

Input: Total time $T$, Regularization $\lambda$, Precision $\delta$

for  _$t=1,\dots,T$_ do

Provide reward estimator $\tilde{r}^{\lambda}_{t}$ verifying w.p. $1-\delta$:

$\quad\forall a\in\mathcal{A}_{t},r(a)\leq\tilde{r}^{\lambda}_{t}(a)$;

Play action
$a_{t}=\operatorname{argmax}_{a\in\mathcal{A}_{t}}\tilde{r}^{\lambda}_{t}(a)$
;

if  _$(a_{t},r(a_{t})+\epsilon_{t})$ is realized i.e. $x_{a_{t}}=1$_ then

Update $\tilde{r}^{\lambda}_{t}$;

end if

end for

Algorithm 1 Generic UCB

#### Algorithms:

To study the impact of censorship on bandit problems, we consider the class of
high-probability index algorithms based on the optimism under uncertainty
principle, commonly referred as UCB-algorithms. Following
pmlr-v75-kirschner18a , Algorithm 1 summarizes the generic UCB design
framework. We detail in App.A the specific instances of UCB for MAB (resp.
LCB) used in Sec.3 (resp. Sec.4). Moreover, this family of algorithms strongly
relies on regularized reward estimators $\tilde{r}^{\lambda}_{t}$, where the
regularizer is mostly used to prevent an artificial cold-start exploratory
phase.

#### Performance Criterion:

The frequentist performance of the agent is measured by the notion of pseudo
regret, i.e., the difference between the algorithm’s cumulative reward and the
best total reward. More formally, we introduce for any policy $\pi\in\Pi$:

$\displaystyle
R(T,\pi)=\sum_{t=1}^{T}\max_{a\in\mathcal{A}_{t}}r(a)-\sum_{t=1}^{T}r(a_{t})=\sum_{t=1}^{T}\Delta_{t}(a_{t}).$

We aim to provide guarantees on $\mathbb{E}[R(T,\pi)]$ with respect to the
number of rounds $T$ and quantities that govern the complexity of the problem
(for example number of arms, ambient dimension $d$, parameters of censorship
model or smoothness properties of the reward $r$). Here, the expectation is
with respect to the noise induced by the feedback, the censorship and a
possibly randomized policy.

###  2.1 Notations

Transpose of a vector $u$ is denoted by $u^{\top}$, classical Euclidean inner
product by $\langle.,.\rangle$ and trace operator by $\operatorname{Tr}$. For
positive semi-definite matrix $\boldsymbol{\Sigma}\in\mathbb{R}^{d\times d}$
and for any vector $u\in\mathbb{R}^{d}$, notation $\|u\|_{\Sigma}$ refers to
$\sqrt{u^{\top}\boldsymbol{\Sigma}u}$. We use notation $\mathbb{I}_{d}$ to
denote the $d\times d$ identity matrix. $\mathbb{B}_{d}$ is the unit ball in
$\mathbb{R}^{d}$. $[n]$ is the set of integers $\\{1,2,\cdots,n\\}$. For a
given function $f$, we note $f^{(i)}$ the $i^{th}$ derivative of $f$. To avoid
confusion with the dimension $d$, we use $\partial x$ instead of $dx$ to
denote an infinitesimal increase of $x$. We use the asymptotic notations
$\sim$, $\mathcal{O}$, $\Theta$ and $\tilde{\mathcal{O}}$ ($\mathcal{O}$ when
$\log$ factors are removed). Finally, for an event $\mathcal{H}$, we use
$\neg\mathcal{H}$ to denote its complement.

##  3 Multi-Armed Bandits

###  3.1 Effective Dimension and Regret Bounds

The main result of this section is that censorship effectively enlarges the
dimension of the problem. We define the effective dimension as
$d_{\mathit{eff}}\triangleq\sum_{a\in[d]}\frac{1}{p_{a}}$ and our result (Thm.
3.1) shows that, at first order, the regret is guaranteed to be the same as
the uncensored problem with $d_{\mathit{eff}}$ arms instead of $d$.

######  Theorem 3.1.

Under censorship, the UCB algorithm with regularization $\lambda$ has an
instance-independent expected regret of:

$\displaystyle\mathbb{E}[R(T,\pi_{\text{UCB}})]$
$\displaystyle\leq\tilde{\mathcal{O}}(\sigma\sqrt{d_{\mathit{eff}}T}).$

Furthermore, we obtain analogous regret guarantees for instance-dependent
cases where, at first order, the uncensored dimension $\sum_{a\neq
a^{\star}}\frac{\sigma^{2}}{\Delta_{a}}$ enlarges to $\sum_{a\neq
a^{\star}}\frac{\sigma^{2}}{p_{a}\Delta_{a}}$:

######  Proposition 3.2.

For a fixed action set $\mathcal{A}_{t}\equiv[d]$ and for a-priori known
action gap
$\Delta_{a}\triangleq\max_{\tilde{a}}\theta^{\star}_{\tilde{a}}-\theta^{\star}_{a}$,
the UCB algorithm with regularization $\lambda$ has the instance-dependent
expected regret:

$\displaystyle\mathbb{E}[R(T,\pi_{\text{UCB}})]$
$\displaystyle\leq\mathcal{O}\Big{(}\log(T)\sum_{a\neq
a^{\star}}\frac{1}{p_{a}}\max(\frac{\sigma^{2}}{\Delta_{a}},\Delta_{a})\Big{)}.$

On one hand, a preliminary understanding of censorship posits an increase of
the average "regret per information gain" pmlr-v75-kirschner18a  (as it takes
longer on average to get the same amount of information) but does not change
the underlying complexity of the problem. One the other hand, our results
(Thm. 3.1 and Prop. 3.2) postulate that the censored problem is equivalent at
first order to a higher dimensional problem but explored with the same regret
per information gain.

The abovementioned results extends to a-priori known heteroskedasticity (see
Rem. 3 and 4 in App. B). For this general setting, the effective dimension for
instance-independent (resp. dependent) case is given by
$\sum_{a}\frac{\sigma_{a}^{2}}{p_{a}}$ (resp. $\sum_{a\neq
a^{\star}}\frac{\sigma_{a}^{2}}{p_{a}\Delta_{a}}$), where $\sigma_{a}^{2}$ is
the variance proxy of arm $a$. Although the scaling in
$\sum_{a}\frac{1}{\Delta_{a}p_{a}}$ was already mentioned in
stoch_unrest_delay  for unregularized setting with homogeneous variance
$\sigma^{2}$ and proven to be optimal, our results generalize these findings.

###  3.2 Cumulative Censored Potential

We now provide a proof sketch of Thm. 3.1, and in doing so, we instantiate an
analysis framework that will be extended in Sec. 4. This proof consists in the
successive elimination of the noise induced by the feedback and censorship.
This leads to regret guarantees on a resulting deterministic quantity by
characterizing worst-case learning conditions. The first step of the proof is
a variant of the classical reduction of the UCB regret to another quantity we
refer to as the _expected cumulative censored potential_. Before stating it,
we define at the end of a round $t\in[T]$, the random number of times an arm
$a$ has been pulled as
$\tau_{a}(t)\triangleq\sum_{l=1}^{t}\mathbf{1}\\{a_{l}=a\\}$. Similarly, the
number of times an action $a$ has been realized at the end of round $t$ is
denoted
$N_{a}(t)\triangleq\sum_{l=1}^{t}\mathbf{1}{\\{a_{l}=a,x_{a_{l}}=1\\}}$. We
then have:

######  Lemma 3.3.

Given an uniform regularization of $\lambda>0$, the UCB algorithm verifies:

$\displaystyle\mathbb{E}[R(T,\pi_{\text{UCB}})]\leq
2\sqrt{6\sigma^{2}\log(T)}\mathbb{E}[\mathbb{V}_{\frac{1}{2}}(T,\pi_{\text{UCB}})]+2\lambda\|\theta^{\star}\|_{\infty}\mathbb{E}[\mathbb{V}_{1}(T,\pi_{\text{UCB}})]+\frac{2d\Delta_{max}}{T}$

where, for any $\alpha>0$ and $\pi\in\Pi$, the cumulative potential under
censorship is given by:

$\displaystyle\mathbb{V}_{\alpha}(T,\pi)=\sum_{t=1}^{T}(N_{a_{t}}(t-1)+\lambda)^{-\alpha}.$

Without censorship, the cumulative potential translates the average rate of
decay of uncertainty on the reward of different arms and is closely linked to
the divergence between the true reward distribution and the empirical
distribution of observed rewards pmlr-v119-shekhar20a . Introducing censorship
transforms the classical deterministic decay rate into a stochastic one. For a
typical reward distribution, the rate of decay is proportional to a term in
$n^{-\alpha}$ or can be upper bounded by such a term (see for e.g.
pmlr-v119-shekhar20a ), where $n$ is the number of observed rewards.
Therefore, a higher $\alpha$ corresponds to faster learning.

In contrast to the classical non-regularized analysis or to the LCB case of
Sec. 4, we observe two different orders of $\alpha$ ($\nicefrac{{1}}{{2}}$ and
$1$) coming from the use of the $L_{\infty}$-norm instead of the $L_{2}$-norm.
Taken independently, they lead to respective contributions of
$\mathcal{O}(d_{\mathit{eff}}\log(T))$ and
$\mathcal{O}(\sqrt{d_{\mathit{eff}}T})$. Note that by working with a general
$\alpha$, our analysis naturally extends beyond sub-Gaussian noise to more
general assumptions about the Laplace transform of noise (e.g., lighter or
heavier tails), as discussed in Rem.2. To further study $\mathbb{V}_{\alpha}$,
we introduce the following property:

######  Proposition 3.4.

For all $\alpha>0$, $\delta\in]0,1]$ and given $\psi_{\alpha}$ a primitive of
$x\mapsto x^{-\alpha}$, we have:

$\displaystyle\max_{\pi\in\Pi}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]$
$\displaystyle\leq\frac{d_{\mathit{eff}}}{(1-\delta)^{\alpha}}\left[\psi_{\alpha}(\frac{T}{d_{\mathit{eff}}}+\frac{\lambda}{1-\delta})-\psi_{\alpha}(\frac{\lambda}{1-\delta})\right]+\frac{24d_{\mathit{eff}}\log(T)+d}{\lambda^{\alpha}}+\frac{4d_{\mathit{eff}}}{\lambda^{\alpha}\delta^{2}T^{12\delta^{2}}}.$

The proof of this proposition involves two steps: firstly, we remove the
stochastic dependence induced by the censorship through concentration
properties (See App. B), and we then solve the resulting policy maximization
problem (Lemma 3.5). In the first step, we consider for a given
$\delta\in]0,1]$ the event:

$\displaystyle\mathcal{H}_{CEN}(\delta)$ $\displaystyle=\left\\{\exists
a\in[d],t\in[T],N_{a}(t)<(1-\delta)p_{a}\tau_{a}(t)\quad\text{and}\quad\tau_{a}(t)\geq
T_{0}(a)\right\\},$

where $T_{0}(a)\triangleq 24\log(T)/p_{a}+1$ and claim that
$\mathbb{P}(\mathcal{H}_{CEN}(\delta))\leq\frac{4d_{\mathit{eff}}}{\delta^{2}}T^{-12\delta^{2}}$,
improving a result of stoch_unrest_delay . Here $\mathcal{H}_{CEN}$ denotes
the event where there is a significant gap between the realized and expected
number of observed rewards. We consider its complement in our analysis of the
principal order of regret. This allows us to lower bound for each action, the
realized number of reward observations by a multiple of the number of times
that action was selected, thus eliminating the randomness induced by
censoring.

Our second step makes use of the following lemma (also known as a water-
filling process in information theory ITbook ):

######  Lemma 3.5.

For $\psi_{\alpha}$ a primitive of $x\mapsto x^{-\alpha}$ where
$\alpha\in]0,1]$, regularization
$(\lambda_{a})_{a\in[d]}\in(\mathbb{R}_{>0})^{d}$ and censorship vector
$(p_{a})_{a\in[d]}$, the solution of the optimization problem:

$\displaystyle\max_{\tau_{1}\dots,\tau_{d}\geq 0}\quad$
$\displaystyle\sum_{a\in[d]}\frac{1}{p_{a}}\Big{(}\psi_{\alpha}(p_{a}\tau_{a}+\lambda_{a})-\psi_{\alpha}(\lambda_{a})\Big{)}\quad\textrm{s.t.}\quad\sum_{a\in[d]}\tau_{a}=T$

is given by $\tau^{\star}_{a}=\frac{1}{p_{a}}[C-\lambda_{a}]^{+}$, where $C$
ensures the total budget constraint $\sum_{a\in[d]}\tau^{\star}_{a}=T$. In
particular, with
$\lambda_{\text{eff}}\triangleq\frac{1}{d_{\mathit{eff}}}\sum_{a\in[d]}\frac{\lambda_{a}}{p_{a}}$
and $\lambda_{a}^{0}\triangleq
d_{\mathit{eff}}(\lambda_{a}-\lambda_{\text{eff}})$, the optimal solution is
given by
$\tau^{\star}_{a}\triangleq\frac{1}{p_{a}d_{\mathit{eff}}}(T-\lambda_{a}^{0})$
for $T\geq\displaystyle\max_{a}\lambda_{a}^{0}$ and the optimal value is
$d_{\mathit{eff}}\psi_{\alpha}(\frac{T}{d_{\mathit{eff}}}+\lambda_{\text{eff}})-\sum_{a\in[d]}\frac{1}{p_{a}}\psi_{\alpha}(\lambda_{a})$.

For unregularized algorithms, this framework can be easily applied to provide
instances-dependent guarantees by adding constraints of type $\tau_{a}\leq
f(\Delta_{a})$ within Lemma 3.5. Optimal guarantees under regularization such
as the ones given in Prop. 3.2 require however to consider both orders of
$\mathbb{V}_{\alpha}$ ($\nicefrac{{1}}{{2}}$ and $1$) simultaneously and not
independently, leading to slight variations as shown in the proof of Prop.
3.2. Next, we further discuss the properties of $\mathbb{V}_{\alpha}$ given
its importance in our analysis.

###  3.3 Evaluating Adaptivity Gain

It is well known that adaptivity is a key feature of sequential decision
problems: optimal policies use feedback from previous decisions to decide the
next action to take based on the data, and in comparison non-adaptive policies
can be quite suboptimal. Somewhat interestingly, the main result of this
section is that adaptivity in the context of censoring does not provide a
significant advantage to the decision maker. More precisely, being able to
observe which decisions have been censored and adapting to this information
does not bring more than a second order gain. In proving this result, we
quantify and gain insight into the expected performance of policies that are
adaptive to the realization of the censorship process, in comparison to a
class of non-adaptive (i.e., offline) policies.

In fact, through the introduction of $\mathcal{H}_{CEN}(\delta)$ and for any
$\alpha\in[0,1]$, $\delta\in]0,1]$, we showed in Prop. 3.4 the upper bound
$\frac{d_{\mathit{eff}}}{(1-\delta)^{\alpha}}\psi_{\alpha}(\frac{T}{d_{\mathit{eff}}}+\frac{\lambda}{1-\delta})$
for the learning complexity $\max\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]$ where
the maximum is taken over the class of adaptive policies
$\Pi_{\mathit{adapt}}$, i.e., measurable with respect to the censorship. Note
that the exact value of such maximum is notoriously difficult to study due to
the adaptive nature of censorship induced by the decision-making process.
Next, we introduce $\Pi_{\mathit{off}}$, the class of policies that are not
adaptive with respect to the censorship and we prove that :

######  Lemma 3.6.

For $\alpha\in]0,1]$ and $\lambda>0$, we have
$\displaystyle\max_{\pi\in\Pi_{\text{off}}}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]\sim
d_{\mathit{eff}}\psi_{\alpha}(\frac{T}{d_{\mathit{eff}}}+\lambda)$.

In other words, restricting attention to offline policies is sufficient to
obtain the correct scaling. The next step to complete our claim is the
asymptotic expansion:

######  Proposition 3.7.

For $\alpha\in]0,1]$, by denoting
$\displaystyle\gamma_{\alpha}(\mathbf{p})\triangleq\frac{\alpha}{2d_{\mathit{eff}}^{1-\alpha}}\sum_{a\in[d]}\frac{1}{p_{a}}\Big{(}\sum_{\tilde{a}\neq
a}\frac{1-p_{\tilde{a}}}{p_{\tilde{a}}}\Big{)}$, we have:

$\displaystyle\max_{\pi\in\Pi_{\text{adapt}}}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]-\max_{\pi\in\Pi_{\text{off}}}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]=\gamma_{\alpha}(\mathbf{p})\frac{1}{T^{\alpha}}+o(\frac{1}{T^{\alpha}}).$
($\star$)

Moreover, if for a given $\beta\in]0,1[$, we introduce
$\Pi_{\text{single}}(\beta T)$ the policy class whose censorship information
set has a single updating at time $\lfloor\beta T\rfloor$, we have:

$\displaystyle\max_{\pi\in\Pi_{\text{single}}(\beta
T)}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]-\max_{\pi\in\Pi_{\text{off}}}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]=\gamma_{\alpha}(\mathbf{p})\frac{\beta}{T^{\alpha}}+o(\frac{1}{T^{\alpha}}).$
($\star\star$)

Thus, $\gamma_{\alpha}(\mathbf{p})$ can be viewed as an adaptivity gain
resulting from the continuous correction of the cumulative variance induced by
the action selection process. Essentially, it is closely related to the Jensen
Gap of an appropriate random variable and the proof involves the study of the
Taylor expansion of the potential function $\psi_{\alpha}$. ($\star\star$ ‣
3.7) tells us that a single observation of the censorship realization is
sufficient to obtain a near-optimal gain in adaptivity. We present a proof
sketch of Prop. 3.7 in App. B. This shows that censorship in MAB can be
treated in an offline manner at first order.

##  4 Contextual Bandit

In this section, we study Linear Contextual Bandits (LCBs) under censorship.
The regret analysis for the generic censorship model in Sec. 2 is
significantly more complex for LCB than for MAB. This is due to the fact that
different actions contribute differently to the information acquisition,
leading to a non-linear phenomenon governing the trade-off between reward and
information gain (see Sec.4.4).

###  4.1 Multi-threshold Models and Regret Bounds

To address the abovementioned challenge, we now introduce a simple _multi-
threshold_ censorship model, which enables a precise regret analysis. In
particular, we consider that feedback is censored according to the following
action-dependant probability:

$\displaystyle
p:a\in\mathbb{B}_{d}\mapsto\sum_{j=0}^{k}\mathbf{1}\\{\sin(\phi_{j})\leq\langle
a,u\rangle<\sin(\phi_{j+1})\\}p_{j},$ ($\mathcal{MT}$)

where $(\phi_{j})_{j\leq k+1}$ is an increasing sequence verifying
$\phi_{0}=-\frac{\pi}{2}$, $\phi_{k+1}=\frac{\pi}{2}$ and $u\in\mathbb{R}^{d}$
is a unit vector. We assume that $(p_{j})_{j\leq k}$ is decreasing, i.e. the
censorship is increasing with $j$ in direction $u$. Henceforth, we refer to
the interval $[\sin(\phi_{j}),\sin(\phi_{j+1})[$ as _region $j$_. Note that
simple models such as uniform censorship are subsumed by this family (for $k$
equals $0$).

Figure 1: Example of a multi-threshold model for $k=2$ (Green). Logistic
censorship model (Red)

The two main features of the multi-threshold model are: the _radial_ aspect
(the censorship probability depends on the action through a scalar product
with a given vector) and the _monotonicity_ (the censorship is monotone in the
value of this scalar product). Note that $\mathcal{MT}$ can be seen as a
piecewise constant approximation of any Generalized Linear Model (GLM)
mccullagh1989generalized . Thus, the simplicity of this censorship model is
not an inherently limiting factor on the generality of our subsequent results.

Moreover, $\mathcal{MT}$ admits a natural behavioral interpretation: Such a
distribution can be seen as induced by a population model of heterogeneous
random-utility maximizing agents. A single threshold model (i.e. $k$ equals
$1$) corresponds to a given agent type, and the multi-threshold model
naturally results from aggregate responses of heterogeneous population
DynamicDiscreteChoice .

We now state the main result of this section:

######  Theorem 4.1.

For a given multi-threshold censorship model $\mathcal{MT}$, there exits
$d_{\mathit{eff}}$ such that the UCB algorithm with regularization $\lambda$
has an instance-independent expected regret of:

$\displaystyle\mathbb{E}[R(T,\pi_{\text{UCB}})]$
$\displaystyle\leq\tilde{\mathcal{O}}(\sigma\sqrt{d\cdot
d_{\mathit{eff}}}\sqrt{T}).$

Importantly, note the mapping from the original dimension $d$ to the enlarged
$\sqrt{d\cdot d_{\mathit{eff}}}$, in contrast to the previous dilation
$d\mapsto d_{\mathit{eff}}$ for the case of MAB problems. An extension to
Generalized Linear Contextual Bandits is provided in App. C.6 where we show
that the dimension is governed by $\sqrt{d\cdot d_{\mathit{eff}}}/\kappa$,
with $\kappa$ corresponding to a minimum of the derivative of the link
function (encompassing the smoothness of the GLM at its maximum)
(li2017provably, ; NIPS2010_c2626d85, ). We conjecture that this result still
holds if we relax the monotonicity property of $\mathcal{MT}$ although it will
require some modifications in the proofs of section D. On the other hand, we
believe that the radial property is necessary, considering the related
literature on GLMs (further discussed in App. C.6) where it appears
prominently.

###  4.2 Generalized Cumulative Censored Potential

Analogous to the MAB case, we now introduce for LCB the random matrices
corresponding to the effective realization
$\mathbb{W}^{C}_{t}\triangleq\lambda\mathbb{I}_{d}+\sum_{n=1}^{t}x_{a_{t}}a_{t}a_{t}^{\top}$
and the expected realization
$\mathbb{W}_{t}\triangleq\lambda\mathbb{I}_{d}+\sum_{n=1}^{t}p(a_{t})a_{t}a_{t}^{\top}$.
We also introduce the continuous counterpart of $\mathbb{W}_{t}$ defined as
$\mathbb{W}(t)\triangleq\lambda\mathbb{I}_{d}+\int_{u=0}^{t}p(a(u))a(u)a(u)^{\top}\partial
u$, where $(a(u))_{u\leq T}$ is an integrable deterministic path.111In this
section, the generic notation $X(t)$ is used for continuous time quantities
and $X_{t}$ for discrete time. We emphasise that the use of continuous
counterpart is key in enabling our next results. As in the MAB case, we bound
the regret although now using a generalization of $\mathbb{V}_{\alpha}$:

######  Lemma 4.2.

For all $\delta\in]0,1]$, there exists a constant
$\tilde{\beta_{\delta}}(T)=\Theta(\sqrt{d\log(T)})$ such that

$\displaystyle\mathbb{E}[R(T,\pi_{\text{UCB}})]\leq
2\tilde{\beta_{\delta}}(T)\sqrt{T\mathbb{E}[\mathbb{V}_{1}(T,\pi_{\textit{UCB}})]}+\delta
T\Delta_{max},$

where, for $\alpha>0$ and $\pi\in\Pi$, the linear extension of the cumulative
censored potential is given by:

$\displaystyle\mathbb{V}_{\alpha}(T,\pi)\triangleq\sum_{t=1}^{T}\|a_{t}\|^{2}_{(\mathbb{W}^{C}_{t-1})^{-\alpha}}=\sum_{t=1}^{T}\operatorname{Tr}((\mathbb{W}^{C}_{t-1})^{-\alpha}a_{t}a_{t}^{\top}).$

The proof idea is analogous (albeit more complex) than in the finite action
case (see App. C). In order to get a handle on $\mathbb{V}_{\alpha}$, we again
leverage a two-step approach: first we eliminate the randomness due to
censorship (here, we utilize matrix martingale inequalities) and then optimize
the resulting deterministic quantity seen through a continuous lens. The first
step requires the following result:

######  Proposition 4.3.

For any $\delta\in]0,1]$, $\lambda>0$, $\alpha>0$ and policy $\pi\in\Pi$, we
have:

$\displaystyle\mathbb{E}[V_{\alpha}(T,\pi)]\leq\frac{\delta}{\lambda^{\alpha}}+C(\delta)^{\alpha}\operatorname{Tr}\Big{(}\int_{0}^{T}\mathbb{W}(t)^{-\alpha}a(t)a(t)^{\top}\partial
t\Big{)},$

where $C(\delta)\triangleq
8(\lambda+1)\max(\log(d/\delta))/\lambda,1)/\lambda$.

The key idea of this result is to observe that the telescopic sum on which the
classical Elliptical Potential lemma (NIPS2011_e1d5be1c, ; adpt_cofond_Russo,
; carpentier2020elliptical, ) heavily relies on is, in fact, the discrete
approximation of an integral over a matrix path. This critical methodological
contribution is further discussed in Rem. 1 and 5.

######  Remark 1.

One way to fully appreciate the generality of this result is to consider the
simpler case of classical uncensored environment for which we obtain for
$\alpha>0,\alpha\neq 1$:

$\displaystyle\sum_{t=1}^{T}\|a_{t}\|^{2}_{\mathbb{W}_{t-1}^{-\alpha}}$
$\displaystyle\leq\Big{(}\frac{\lambda+1}{\lambda}\Big{)}^{\alpha}\frac{\operatorname{Tr}\Big{(}\int_{0}^{T}\partial\mathbb{W}(t)^{1-\alpha}\Big{)}}{1-\alpha}=\Big{(}\frac{\lambda+1}{\lambda}\Big{)}^{\alpha}\frac{\operatorname{Tr}(\mathbb{W}^{1-\alpha}_{T}-\mathbb{W}^{1-\alpha}_{0})}{1-\alpha}.$

For $\alpha=1$, a similar reasoning is applied using the formula
$\operatorname{Tr}(\log(A))=\log(\det A)$:

$\displaystyle\sum_{t=1}^{T}\|a_{t}\|^{2}_{\mathbb{W}_{t-1}^{-1}}$
$\displaystyle\leq\frac{\lambda+1}{\lambda}\int_{0}^{T}\frac{\partial\log\det(\mathbb{W}(t))}{\partial
t}\partial
t=\frac{\lambda+1}{\lambda}\operatorname{Tr}(\log\mathbb{W}_{T}-\log\mathbb{W}_{0})=\frac{\lambda+1}{\lambda}\log\frac{\det\mathbb{W}_{T}}{\det\mathbb{W}_{0}}.$

A deeper study of the eigenvalues of $\mathbb{W}^{1-\alpha}_{T}$ then yields
the worst-case upper bound $d^{\alpha}(d\lambda+T)^{1-\alpha}/(1-\alpha)$ for
$\alpha<1$ and $d\lambda^{1-\alpha}/(\alpha-1)$ for $\alpha>1$, recovering
more naturally and extending the results of (carpentier2020elliptical, ).
Thus, analogous to the water filling process highlighted in the MAB case in
Lemma 3.5, we now consider a spectral water-filling process ITbook  optimizing
over the eigenvalues of $\psi_{\alpha}(\mathbb{W}_{T})$ with a slight abuse of
notations ( $\mathbb{W}^{1-\alpha}_{T}$ and $\log\mathbb{W}_{T}$ in this
discussion).

Following Rem.1, for the general censored case the challenge now becomes to
identify a suitable matrix operator on which the aforementioned spectral
maximization can be performed. By applying Lemma 4.2, we henceforth focus on
the case of $\alpha=1$ for which Prop. 4.3 implies that for any policy:

$\displaystyle\operatorname{Tr}\Big{(}\int_{0}^{T}\mathbb{W}(t)^{-1}a(t)a(t)^{\top}\partial
t\Big{)}=\int_{0}^{T}\frac{1}{p(a(t))}\frac{\partial\log\det(\mathbb{W}(t))}{\partial
t}\partial t.$

Next, we focus on maximizing this integral over the policy class $\Pi$ and
again recover the notion of effective dimension.

###  4.3 Effective Dimension in Linear Settings

We now highlight immediate properties of the effective dimension, and then
present its general study for the multi-threshold model $\mathcal{MT}$.

######  Lemma 4.4.

Let us consider an uniform censorship model $p:a\mapsto\bar{p}$. By leveraging
the case of equality in the Arithmetic-Geometric inequality applied to the
eigenvalues of $\mathbb{W}_{T}$, we then simply deduce the associated
effective dimension $d_{\mathit{eff}}\triangleq d/\bar{p}$:

$\displaystyle\max_{\pi\in\Pi}\int_{0}^{T}\frac{1}{\bar{p}}\frac{\partial\log\det(\mathbb{W}(t))}{\partial
t}\partial t$ $\displaystyle=d_{\mathit{eff}}\log(1+\frac{T}{\lambda
d_{\mathit{eff}}}).$

In fact, the logarithmic scaling of this quantity persists while moving beyond
the uniform censorship assumption. This also highlights the importance of the
leading dimension factor, crudely upper bounded by $d/p_{\mathit{min}}$ in the
next lemma:

######  Lemma 4.5.

For any censorship function $p$, by introducing lower and upper bounds
$(p_{\mathit{min}},p_{\mathit{max}})$ of $p$, we have:

$\displaystyle\frac{d}{p_{\mathit{max}}}\log(1+\frac{p_{\mathit{min}}T}{d\lambda})\leq\max_{\pi\in\Pi}\int_{0}^{T}\frac{1}{p(a(t))}\frac{\partial\log\det(\mathbb{W}(t))}{\partial
t}\partial
t\leq\frac{d}{p_{\mathit{min}}}\log(1+\frac{p_{\mathit{max}}T}{d\lambda}).$

Related problems in the Generalized Linear Models literature ZhouGLM ;
li2017provably ; NIPS2010_c2626d85  are implicitly solved in the spirit of
Lemma 4.5, where a minimum of the derivative of the link function plays the
role of $p_{\mathit{min}}$ above. However, when the function $p$ varies with
action $a$, a more careful analysis is required to derive useful dimensional
bounds. Our next major result addresses this gap in the literature by
improving the bounds provided in Lemma 4.5:

######  Theorem 4.6.

For a multi-threshold censorship model $\mathcal{MT}$, we have:

$\displaystyle\max_{\pi\in\Pi}\int_{0}^{T}\frac{1}{p(a(t))}\frac{\partial\log\det(\mathbb{W}(t))}{\partial
t}\partial t=d_{\mathit{eff}}\log(T)+o(\log(T)),$ ($\mathcal{P}$)

where $d_{\mathit{eff}}$ is the effective dimension. Furthermore,
$d_{\mathit{eff}}$ is characterized by two cases:

  * •

Case 1: Single region $j$ effective dimension
$d_{\mathit{eff}}=\frac{d}{p_{j}}$.

  * •

Case 2: Bi-region $(i,j)$ effective dimension, with $i<j$:

$\displaystyle d_{\mathit{eff}}$
$\displaystyle=\frac{1}{p_{j}}\left[(d-1)\frac{1-l(i,j)}{\frac{p_{i}}{p_{j}}-l(i,j)}+\frac{u(i,j)-1}{u(i,j)-\frac{p_{i}}{p_{j}}}\right]<\frac{d}{p_{j}}.$
($\mathcal{D}$)

where $l(i,j)\triangleq\frac{\sin^{2}(\phi_{i})}{\sin^{2}(\phi_{j})}$ and
$u(i,j)\triangleq\frac{\cos^{2}(\phi_{i})}{\cos^{2}(\phi_{j})}$.

The implications of these cases are further discussed in Fig.2 in App. D.
Notice that a necessary condition for the bi-region $(i,j)$ effective
dimension to arise is the constraint on $\frac{p_{i}}{p_{j}}$:

$\displaystyle\max(1,\underbrace{\frac{dl(i,j)u(i,j)}{u(i,j)+(d-1)l(i,j)}}_{\triangleq
s^{\star}(i,j)})<\frac{p_{i}}{p_{j}}<\underbrace{\frac{(d-1)u(i,j)+l(i,j)}{d}}_{\triangleq
r^{\star}(i,j)}$

In the limit $\frac{p_{i}}{p_{j}}\rightarrow r^{\star}(i,j)$,
$d_{\mathit{eff}}$ goes again to $d/p_{j}$. We interpret this limiting case as
locally hard in the sense that censorship in region $j$ is sufficiently
important in comparison to all other regions to impose a maximal effective
dimension to the problem, irrespective of the values of $p_{i}$, matching
Lemma 4.5. On the other hand, for the other limiting case (under additional
mild assumptions), we find that $d_{\mathit{eff}}$ also goes to $d/p_{j}$, but
now for a uniformly hard reason: that is, censorship is approximately constant
and equal to $p_{j}$, recovering the Lemma 4.4. Finally, in between these two
extremes lies the minimum effective dimension for a given value of
$\frac{p_{i}}{p_{j}}$.

###  4.4 Temporal dynamics of $\mathbb{W}(t)$

The proof of Thm. 4.6 requires the characterization of the dynamics of the
optimal policy of ($\mathcal{P}$). Importantly, we discover that the evolution
of $\mathbb{W}(t)$ is described by two qualitatively different regimes as
outlined next. It turns out that our continuous approach to analyzing
cumulative censored potential is an important tool to obtaining this result.

#### Transient Regime:

There exists a decreasing sequence of censorship regions
$\\{i_{1}=k,\dots,i_{l}\\}$ of length $l\in[k+1]$ and associated time sequence
$\\{t_{0}\triangleq 0,t_{1},\dots,t_{l}\\}$ such that whenever $t_{j}\leq
t\leq t_{j+1}$ for a given index $j\leq l-1$, the evolution of $\mathbb{W}(t)$
is given by:

$\displaystyle\mathbb{W}(t)$
$\displaystyle=p_{i_{j+1}}(t-t_{j})\mathbb{W}_{i_{j+1}}+\mathbb{W}(t_{j})=p_{i_{j+1}}(t-t_{j})\mathbb{W}_{i_{j+1}}+\sum_{n=1}^{j}p_{i_{n}}(t_{n}-t_{n-1})\mathbb{W}_{i_{n}}+\lambda\mathbb{I}_{d},$

where $\mathbb{W}_{i}$ denotes the $d\times d$ diagonal matrix
$\text{diag}(\frac{\cos^{2}(\phi_{i})}{d-1},\dots,\frac{\cos^{2}(\phi_{i})}{d-1},\sin^{2}(\phi_{i}))$.
Interestingly, the initial misspecification of censorship is self-corrected
during this transient step but at an extra cost. This characterization of
transient regime highlights an important consequence of using classical
algorithms in censored environments.

#### Steady State Regime:

Post-transient regime, the dynamics of $\mathbb{W}(t)$ enter a steady state
regime, where one of the two cases necessarily arise:222These cases are fully
characterized in terms of parameters of censorship model in Lemmas D.1, D.2,
D.3 and Cor. D.1.1..

  * •

Case 1: Single region $i_{l}$. This case arises when the last element of the
time sequence $t_{l}$ is equal to $+\infty$ and we have the single region
evolution for all $t\geq t_{l-1}$:

$\displaystyle\mathbb{W}(t)$
$\displaystyle=p_{i_{l}}(t-t_{l-1})\mathbb{W}_{i_{l}}+\mathbb{W}(t_{l-1})=p_{i_{l}}(t-t_{l-1})\mathbb{W}_{i_{l}}+\sum_{n=1}^{l-1}p_{i_{n}}(t_{n}-t_{n-1})\mathbb{W}_{i_{n}}+\lambda\mathbb{I}_{d}.$

The effective dimension corresponding to this dynamics is $d/p_{i_{l}}$, with
the following equality for $T\geq t_{l-1}$:

$\displaystyle\int_{0}^{T}\frac{1}{p(a(t))}\frac{\partial\log\det(\mathbb{W}(t))}{\partial
t}\partial
t=\frac{1}{p_{i_{l}}}\log\det(\mathbb{W}(T))+\sum_{n=1}^{l-1}(\frac{1}{p_{i_{n}}}-\frac{1}{p_{i_{n+1}}})\log\det\mathbb{W}(t_{n}).$

  * •

Case 2: Bi-region $(i_{l+1},i_{l})$. This case arises when the steady-state
dynamics of $\mathbb{W}(t)$ span the two regions $(i_{l+1},i_{l})$ with
$i_{l+1}<i_{l}$. For all $t\geq t_{l}$, we have the evolution:

$\displaystyle\mathbb{W}(t)$ $\displaystyle\propto
p_{i_{l+1}}(t+\lambda^{\star})\begin{pmatrix}\cos^{2}(\phi_{i_{l}})(u(i_{l+1},i_{l})-\frac{p_{i_{l+1}}}{p_{i_{l}}})\mathbb{I}_{d-1}&(0)\\\
(0)&\sin^{2}(\phi_{i_{l}})(\frac{p_{i_{l+1}}}{p_{j}}-l(i_{l+1},i_{l}))\end{pmatrix}.$

where $\lambda^{\star}$ and the proportionality factor are specified in SI.
The corresponding effective dimension is given by ($\mathcal{D}$) and the
following equality holds for all $T\geq t_{l}$:

$\displaystyle\int_{0}^{T}\frac{1}{p(a(t))}\frac{\partial\log\det(\mathbb{W}(t))}{\partial
t}\partial
t=d_{\mathit{eff}}\log(1+\frac{T-t_{l}}{t_{l}+\lambda^{\star}})+\sum_{n=1}^{l}(\frac{1}{p_{i_{n}}}-\frac{1}{p_{i_{n+1}}})\log\det\mathbb{W}(t_{n}).$

For further discussions on transient and steady state regimes, we refer to
Fig.3, 4 and 5. in App. D.

##  5 Concluding Remarks

In this work, we demonstrate that the complexity of bandit learning under
censorship is governed by the notion of effective dimension. To do so, we
developed a novel analysis framework which enables us to precisely estimate
this quantity for a broad class of multi-threshold censorship models. An
important future work would be to extend our model and approach to Bayesian
settings, which will likely provide us with useful insights on the cumulative
censored potential $\mathbb{V}_{\alpha}$, as initiated by hamidi2021randomized
. Future work also includes relaxing the Missing Completely at Random (MCAR)
property in favor of time-dependent censorship models such as Markov Decision
Processes (MDPs). We believe that tools similar to those developed in our
potential-based analysis can be applied in this case. Finally, the
contributions of our work may be of interest to the recent value alignment
literature, where the question of learnability under humain-AI interactions is
central. mab_val_align ; hadfieldmenell2016cooperative ; christiano2017deep .

We do not envision any negative societal impacts of our work other than that
of bandits algorithms deployed in AI-driven platforms.

## Acknowledgments and Disclosure of Funding

This research project is supported by the AFOSR FA9550-19-1-0263 “Building
attack resilience into complex networks” Grant. The authors would like to
thank Prem Talwai and the anonymous reviewers for providing insightful
comments and suggestions.

## References

  * [1] Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
  * [2] Jacob Abernethy, Kareem Amin, and Ruihao Zhu.  Threshold bandit, with and without censored feedback.  In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS’16, page 4896–4904, Red Hook, NY, USA, 2016. Curran Associates Inc.
  * [3] Shipra Agrawal and Navin Goyal.  Analysis of thompson sampling for the multi-armed bandit problem.  In Conference on learning theory, pages 39–1. JMLR Workshop and Conference Proceedings, 2012.
  * [4] Victor Aguirregabiria and Pedro mira.  Dynamic Discrete Choice Structural Models: A Survey.  Technical Report tecipa-297, University of Toronto, Department of Economics, 2007.
  * [5] Sylvain Arlot.  Rééchantillonnage et Sélection de modèles.  Theses, Université Paris Sud - Paris XI, December 2007.
  * [6] Jean-Yves Audibert and Sébastien Bubeck.  Regret bounds and minimax policies under partial monitoring.  Journal of Machine Learning Research, 11(94):2785–2836, 2010.
  * [7] Xueying Bai, Jian Guan, and Hongning Wang.  A model-based reinforcement learning with adversarial training for online recommendation.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [8] Alexandra Carpentier, Claire Vernade, and Yasin Abbasi-Yadkori.  The elliptical potential lemma revisited, 2020.
  * [9] Nicolo Cesa-Bianchi, Claudio Gentile, Yishay Mansour, and Alberto Minora.  Delay and cooperation in nonstochastic bandits.  In Vitaly Feldman, Alexander Rakhlin, and Ohad Shamir, editors, 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pages 605–622, Columbia University, New York, New York, USA, 23–26 Jun 2016. PMLR.
  * [10] Lawrence Chan, Dylan Hadfield-Menell, Siddhartha Srinivasa, and Anca Dragan.  The assistive multi-armed bandit.  In Proceedings of the 14th ACM/IEEE International Conference on Human-Robot Interaction, HRI ’19, page 354–363. IEEE Press, 2019.
  * [11] Wei Chen, Yajun Wang, Yang Yuan, and Qinshi Wang.  Combinatorial multi-armed bandit and its extension to probabilistically triggered arms.  Journal of Machine Learning Research, 17(50):1–33, 2016.
  * [12] Paul Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei.  Deep reinforcement learning from human preferences, 2017.
  * [13] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire.  Contextual bandits with linear payoff functions.  In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 208–214, Fort Lauderdale, FL, USA, 11–13 Apr 2011. PMLR.
  * [14] Thomas M. Cover and Joy A. Thomas.  Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing).  Wiley-Interscience, USA, 2006.
  * [15] Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford, Lev Reyzin, and Tong Zhang.  Efficient optimal learning for contextual bandits.  arXiv preprint arXiv:1106.2369, 2011.
  * [16] Sarah Filippi, Olivier Cappe, Aurélien Garivier, and Csaba Szepesvári.  Parametric bandits: The generalized linear case.  In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
  * [17] Dylan Hadfield-Menell, Anca Dragan, Pieter Abbeel, and Stuart Russell.  Cooperative inverse reinforcement learning, 2016.
  * [18] Nima Hamidi and Mohsen Bayati.  The randomized elliptical potential lemma with an application to linear thompson sampling, 2021.
  * [19] Hoda Heidari, Michael Kearns, and Aaron Roth.  Tight policy regret bounds for improving and decaying bandits.  In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI’16, page 1562–1570. AAAI Press, 2016.
  * [20] James Honaker and Gary King.  What to do about missing values in time series cross-section data.  American Journal of Political Science, 54(3):561–581, 2010 2010\.
  * [21] Shinji Ito, Daisuke Hatano, Hanna Sumita, Kei Takemura, Takuro Fukunaga, Naonori Kakimura, and Ken-Ichi Kawarabayashi.  Delay and cooperation in nonstochastic linear bandits.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 4872–4883. Curran Associates, Inc., 2020.
  * [22] Pooria Joulani, Andras Gyorgy, and Csaba Szepesvari.  Online learning under delayed feedback.  In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1453–1461, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR.
  * [23] Johannes Kirschner and Andreas Krause.  Information directed sampling and bandits with heteroscedastic noise.  In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet, editors, Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pages 358–384. PMLR, 06–09 Jul 2018.
  * [24] Tal Lancewicki, Shahar Segal, Tomer Koren, and Y. Mansour.  Stochastic multi-armed bandits with unrestricted delay distributions.  In ICML, 2021.
  * [25] Tor Lattimore and Csaba Szepesvari.  An information-theoretic approach to minimax regret in partial monitoring.  In COLT, 2019.
  * [26] Tor Lattimore and Csaba Szepesvári.  Bandit algorithms.  Cambridge University Press, 2020.
  * [27] Lihong Li, Wei Chu, John Langford, and Robert E Schapire.  A contextual-bandit approach to personalized news article recommendation.  In Proceedings of the 19th international conference on World wide web, pages 661–670, 2010.
  * [28] Lihong Li, Yu Lu, and Dengyong Zhou.  Provably optimal algorithms for generalized linear contextual bandits.  In International Conference on Machine Learning, pages 2071–2080. PMLR, 2017.
  * [29] R.J.A. Little and D.B. Rubin.  Statistical analysis with missing data.  Wiley series in probability and mathematical statistics. Probability and mathematical statistics. Wiley, 2002.
  * [30] Travis Mandel, Yun-En Liu, Emma Brunskill, and Zoran Popović.  The queue method: Handling delay, heuristics, prior data, and evaluation in bandits.  In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI’15, page 2849–2856. AAAI Press, 2015.
  * [31] P. McCullagh and J.A. Nelder.  Generalized Linear Models, Second Edition.  Chapman and Hall/CRC Monographs on Statistics and Applied Probability Series. Chapman & Hall, 1989.
  * [32] Gergely Neu, Andras Antos, András György, and Csaba Szepesvári.  Online markov decision processes under bandit feedback.  In J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta, editors, Advances in Neural Information Processing Systems, volume 23. Curran Associates, Inc., 2010.
  * [33] Therese D. Pigott.  A review of methods for missing data.  Educational Research and Evaluation, 7(4):353–383, 2001.
  * [34] Ciara Pike-Burke, Shipra Agrawal, Csaba Szepesvari, and Steffen Grunewalder.  Bandits with delayed, aggregated anonymous feedback.  In International Conference on Machine Learning, pages 4105–4113. PMLR, 2018.
  * [35] Chao Qin and Daniel Russo.  Adaptivity and confounding in multi-armed bandit experiments, 2022.
  * [36] Daniel Russo and Benjamin Van Roy.  An information-theoretic analysis of thompson sampling.  Journal of Machine Learning Research, 17(68):1–30, 2016.
  * [37] Daniel Russo and Benjamin Van Roy.  Learning to optimize via information-directed sampling.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
  * [38] Shubhanshu Shekhar, Tara Javidi, and Mohammad Ghavamzadeh.  Adaptive sampling for estimating probability distributions.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8687–8696. PMLR, 13–18 Jul 2020\.
  * [39] Aleksandrs Slivkins.  Introduction to multi-armed bandits.  Foundations and Trends® in Machine Learning, 12(1-2):1–286, 2019\.
  * [40] Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger.  Gaussian process optimization in the bandit setting: No regret and experimental design.  In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML’10, page 1015–1022, Madison, WI, USA, 2010. Omnipress.
  * [41] Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger.  Information-theoretic regret bounds for gaussian process optimization in the bandit setting.  IEEE Transactions on Information Theory, 58(5):3250–3265, 2012\.
  * [42] Claire Vernade, Alexandra Carpentier, Tor Lattimore, Giovanni Zappella, Beyza Ermis, and Michael Brückner.  Linear bandits with stochastic delayed feedback.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 9712–9721. PMLR, 13–18 Jul 2020\.
  * [43] Qinshi Wang and Wei Chen.  Improving regret bounds for combinatorial semi-bandits with probabilistically triggered arms and its applications.  In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
  * [44] Han Wu and Stefan Wager.  Thompson sampling with unrestricted delays.  arXiv preprint arXiv:2202.12431, 2022.
  * [45] Fuwen Yang and Yongmin Li.  Set-membership filtering for systems with sensor saturation.  Automatica, 45(8):1896–1902, 2009.
  * [46] Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin.  Reinforcement learning in healthcare: A survey.  ACM Computing Surveys (CSUR), 55(1):1–36, 2021.
  * [47] Zhengyuan Zhou, Renyuan Xu, and Jose Blanchet.  Learning in generalized linear contextual bandits with stochastic delays.  In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes]

    3. (c)

Did you discuss any potential negative societal impacts of your work? [Yes]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]
See Sec. 3 and 4 as well as SI.

    2. (b)

Did you include complete proofs of all theoretical results? [Yes]  See SI.

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [N/A]

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [N/A]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [N/A]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [N/A]

    2. (b)

Did you mention the license of the assets? [N/A]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [N/A]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

##  Appendix A Preliminaries

In this section, we first provide the instances of the UCB algorithm used in
Sec.3 and Sec.4. We also indicate in Tab.1 the notations used throughout the
paper to help the reader.

Table 1: Summary of Notations Bandit Problem Variables
---
$T$ | $\triangleq$ |  Total number of rounds of the sequential decision-making problem.
$d$ | $\triangleq$ |  Number of arms in Sec.3, Dimension of action feature vector in Sec.4.
$(\mathcal{A}_{t},\mathcal{A})$ | $\triangleq$ |  Action set at time $t$; Union of all action sets $\mathcal{A}_{t}$.
$a_{t}$ | $\triangleq$ |  Action picked at time $t$; selected by policy $\pi$, seen as a function of previous history.
$(\epsilon_{t},\sigma^{2})$ | $\triangleq$ |  Stochastic feedback noise a time $t$. Sub-Gaussian with pseudo-variance parameter $\sigma^{2}$. If $\sigma^{2}$ depends on the action selected (heteroskedasticity), we use $\sigma^{2}_{a}$ instead.
$(r,\theta^{\star})$ | $\triangleq$ |  Unknown reward function, maps action to scalar reward. Parameterized by unknown latent state $\theta^{\star}$.
$\Delta_{t}(a)$ | $\triangleq$ |  Sub-optimality gap of action $a$ at time $t$, reward difference with optimal decision of clairvoyant policy
$(\Delta_{a},\Delta_{\max})$ | $\triangleq$ |  If $\Delta_{t}(a)$ is independent of $t$, we use $\Delta_{a}\equiv\Delta_{t}(a)$. $\Delta_{\max}$ is an upper bound of $\Delta_{t}(a)$ for all actions $a$ and time $t$.
$R(T,\pi)$ | $\triangleq$ |  Pseudo regret of policy $\pi$ over $T$ rounds.
Censorship Variables
$p_{a}$ | $\triangleq$ |  Probability that action $a$ is censored if selected, used in Sec. 3. Notation $p(a)$ is used in Sec.4 to emphasize the dependency of $p$ on action $a$.
$(\phi_{j},u,p_{j})$ | $\triangleq$ |  Parameters of the multi-threshold censorship model. Vector $u$ defines the direction of censorship, $(\phi_{j})_{j\leq k+1}$ define the censorship regions with fixed censorship probability and $(p_{j})_{j\leq k}$ define the probability of being censored for each region $j$.
$x_{a_{t}}$ | $\triangleq$ |  Random variable indicating if feedback is censored as round $t$. Follows i.i.d Bernoulli distribution of parameter $p(a_{t})$.
Algorithmic and Analysis Variables
$\lambda$ | $\triangleq$ |  Regularization tuning parameter. $\lambda_{a}$ is used if heterogeneous action-based regularization.
$\tilde{\Delta}^{\lambda}_{t}(a)$ | $\triangleq$ |  High-probability upper bound on the sub-optimality gap, used in UCB algorithms.
$\mathbb{V}_{\alpha}(T,\pi)$ | $\triangleq$ |  Random cumulative censored potential, seen as a function of policy $\pi$ and number of rounds $T$. First introduced in Sec.3 and extended in Sec.4.
$\psi_{\alpha}$ | $\triangleq$ |  Primitive of the function $x\mapsto x^{-\alpha}$, for a given $\alpha>0$.
$N_{a}(t)$ | $\triangleq$ |  Total number of time action $a$ is realized at the end of round $t$ by policy $\pi$. Used in Sec.3.
$\tau_{a}(t)$ | $\triangleq$ |  Total number of time action $a$ is played at the end of round $t$ by policy $\pi$. Used in Sec.3.
$\mathbb{W}_{t}^{C}$ | $\triangleq$ |  Censored Design Matrix. Linear generalization of $(N_{a}(t))_{a\in[d]}$. Used in Sec.4.
$\mathbb{W}_{t}$ | $\triangleq$ |  Expected Design Matrix. Linear generalization of $(p_{a}\tau_{a}(t))_{a\in[d]}$. Used in Sec.4.
$\mathbb{W}(t)$ | $\triangleq$ |  Continuous generalization of the expected design matrix$\mathbb{W}_{t}$.

###  A.1 UCB algorithms

  * •

UCB-MAB: Following [26], the UCB algorithms for the MAB case with homogeneous
regularization $\lambda>0$ uses the following optimistic reward estimator at
time $t$:

$\displaystyle\tilde{r}^{\lambda}_{t}(a)\triangleq\hat{\theta}^{\lambda}_{t}(a)+\sqrt{\frac{6\sigma^{2}\log(T)}{\lambda+N_{a}(t-1)}}+\frac{\lambda\|\theta^{\star}\|_{\infty}}{\lambda+N_{a}(t-1)}.$

It is based on the use of the regularized empirical mean to estimate the
reward of action $a$ at the end of round $t$:

$\displaystyle\hat{\theta}^{\lambda}_{t}(a)$
$\displaystyle\triangleq\frac{1}{N_{a}(t)+\lambda}\sum_{\tau=1}^{t}(r(a_{\tau})+\tau)\mathbf{1}\\{a_{\tau}=a,x_{a_{\tau}}=1\\}$
$\displaystyle=\frac{N_{a}(t)}{N_{a}(t)+\lambda}\theta_{a}^{\star}+\frac{1}{N_{a}(t)+\lambda}\sum_{\tau=1}^{t}\epsilon_{a_{\tau}}\mathbf{1}\\{a_{\tau}=a,x_{a_{\tau}}=1\\}.$

The high-confidence property of this algorithm is proven in Lemma
B.1.333Typically, an upper bound on $\|\theta^{\star}\|_{\infty}$ for MAB
(resp. $\|\theta^{\star}\|_{2}$ for LCB) is used instead of this unknown
quantity. We keep $\|\theta^{\star}\|_{\infty}$ (resp.
$\|\theta^{\star}\|_{2}$) not to overload notations but our results
immediately extends to the use of the latter.Under a-priori known
heteroskedasticity, the reward estimator can be expressed as:

$\displaystyle\tilde{r}^{\lambda}_{t}(a)\triangleq\hat{\theta}^{\lambda}_{t}(a)+\sqrt{\frac{6\sigma_{a}^{2}\log(T)}{\lambda+N_{a}(t-1)}}+\frac{\lambda\|\theta^{\star}\|_{\infty}}{\lambda+N_{a}(t-1)}.$

  * •

UCB for LCB Following [1, 26], the UCB algorithms for the LCB case with
homogeneous regularization $\lambda>0$ uses the following optimistic reward
estimator at time $t$:

$\displaystyle\tilde{r}^{\lambda}_{t}(a)$ $\displaystyle\triangleq\langle
a,\hat{\theta}^{\lambda}_{t-1}\rangle+\beta_{t-1}(\delta)\|a\|_{\mathbb{W}^{C}_{t-1}},$

where we introduced the random quantity:

$\displaystyle\beta_{t-1}(\delta)\triangleq\sqrt{\sigma^{2}\log\left(\frac{\det(\mathbb{W}^{C}_{t-1})}{\det(\lambda\mathbb{I}_{d})}\right)+2\sigma^{2}\log(\frac{1}{\delta})}+\sqrt{\lambda}\|\theta^{\star}\|_{2}$

It is based on the use of the regularized least square estimator to estimate
the vector $\theta^{\star}$ at the end of round $t$:

$\displaystyle\hat{\theta}^{\lambda}_{t}=(\mathbb{W}^{C}_{t})^{-1}\sum_{\tau=1}^{t}(\epsilon_{\tau}+\langle
a_{\tau},\theta^{\star}\rangle)x_{a_{\tau}}a_{\tau}$

The high-confidence property of this estimator is proven in Lemma C.1.

##  Appendix B Proof of Sec. 3 \- Multi-Armed Bandits

In this section, we prove the results in Sec.3 on the MAB case. We start by
proving Lemmas 3.3, B.1, B.2, 3.5 and Prop. 3.4. Thanks to those results, we
then tackle Thm. 3.1 and Prop. 3.2. To conclude the section, we further study
the properties of the adaptivity gain, by proving Lemma 3.6 and Prop. 3.7.
Recall that effective dimension $d_{\mathit{eff}}$ is referring to
$\sum_{a\in[d]}\frac{1}{p_{a}}$ in this section.

###  B.1 Proof of Lemma 3.3

See 3.3

###### Proof.

At a given round $t\in[T]$, we have under the event
$\neg\mathcal{H}_{\text{UCB}}^{\lambda}$ introduced in Lemma B.1:

$\displaystyle\Delta_{t}(a_{t})=\max_{a\in\mathcal{A}_{t}}\theta^{\star}_{a}-\theta^{\star}_{a_{t}}\leq
2\sqrt{6\sigma^{2}\frac{\log(T)}{N_{a_{t}}(t-1)+\lambda}}+2\frac{\lambda\|\theta^{\star}\|_{\infty}}{\lambda+N_{a_{t}}(t-1)},$

where the inequality comes from the definition of the UCB algorithm and the
conditioning on $\neg\mathcal{H}_{\text{UCB}}^{\lambda}$. We find there the
origin of the two different orders of $N_{a}$ ($\nicefrac{{1}}{{2}}$ and $1$).
Taken independently, those lead to a contribution of respectively
$\mathcal{O}(d_{\mathit{eff}}\log(T))$ and
$\mathcal{O}(\sqrt{d_{\mathit{eff}}T})$ . More precisely, we have:

$\displaystyle R(T,\pi_{\text{UCB}}|\neg\mathcal{H}_{\text{UCB}}^{\lambda})$
$\displaystyle\leq
2\sqrt{6\sigma^{2}\log(T)}\sum_{t=1}^{T}\sqrt{\frac{1}{N_{a_{t}}(t-1)+\lambda}}+2\lambda\|\theta^{\star}\|_{\infty}\sum_{t=1}^{T}\frac{1}{N_{a_{t}}(t-1)+\lambda}$
$\displaystyle=2\sqrt{6\sigma^{2}\log(T)}\mathbb{V}_{\frac{1}{2}}(T,\pi_{\text{UCB}})+2\lambda\|\theta^{\star}\|_{\infty}\mathbb{V}_{1}(T,\pi_{\text{UCB}}).$

Therefore, thanks to Lemma B.1, we deduce that:

$\displaystyle R(T,\pi_{\text{UCB}})$
$\displaystyle\leq(1-\mathbb{P}(\mathcal{H}_{\text{UCB}}^{\lambda}))R(T,\pi_{\text{UCB}}|\neg\mathcal{H}_{\text{UCB}}^{\lambda})+\mathbb{P}(\mathcal{H}_{\text{UCB}}^{\lambda})\Delta_{max}T$
$\displaystyle\leq
2\sqrt{6\sigma^{2}\log(T)}\mathbb{V}_{\frac{1}{2}}(T,\pi_{\text{UCB}})+2\lambda\|\theta^{\star}\|_{\infty}\mathbb{V}_{1}(T,\pi_{\text{UCB}})+\frac{2d\Delta_{max}}{T}.$

Finally, we conclude that:

$\displaystyle\mathbb{E}[R(T,\pi_{\text{UCB}})]\leq
2\sqrt{6\sigma^{2}\log(T)}\mathbb{E}[\mathbb{V}_{\frac{1}{2}}(T,\pi_{\text{UCB}})]+2\lambda\|\theta^{\star}\|_{\infty}\mathbb{E}[\mathbb{V}_{1}(T,\pi_{\text{UCB}})]+\frac{2d\Delta_{max}}{T}.$

∎

###  B.2 Statement and Proof of Lemma B.1

The main step in this reduction from regret to cumulative censored potential
is the study of the failure of optimism event thanks to the following result:

######  Lemma B.1.

For a regularization $\lambda>0$ and $\delta\in]0,1]$, we introduce the event:

$\displaystyle\mathcal{H}_{\text{UCB}}^{\lambda}=\Big{\\{}\exists
a\in[d],t\in[T],|\hat{\theta}^{\lambda}_{t}(a)-\theta^{\star}_{a}|>\sqrt{\frac{6\sigma^{2}\log(T)}{\lambda+N_{a}(t)}}+\frac{\lambda\|\theta^{\star}\|_{\infty}}{\lambda+N_{a}(t)}\Big{\\}}.$

We then have
$\mathbb{P}(\mathcal{H}_{\text{UCB}}^{\lambda})\leq\frac{2d}{T^{2}}$.

###### Proof.

Although this event is similar to the one introduced in the classical UCB
proof idea, the subtlety comes from the randomness induced by the censorship
as well as the impact of regularization. The main idea is adopt a worst-case
agnostic approach. First, let’s note that for a given $t\in[T],a\in[d]$, we
have:

$\displaystyle|\hat{\theta}^{\lambda}_{t}(a)-\theta^{\star}_{a}|$
$\displaystyle=|\frac{1}{N_{a}(t)+\lambda}\sum_{\tau=1}^{t}\epsilon_{\tau}\mathbf{1}\\{a_{\tau}=a,x_{a_{\tau}}=1\\}-\frac{\lambda}{N_{a}(t)+\lambda}\theta^{\star}_{a}|$
$\displaystyle\leq|\frac{1}{N_{a}(t)+\lambda}\sum_{\tau=1}^{t}\epsilon_{\tau}\mathbf{1}\\{a_{\tau}=a,x_{a_{\tau}}=1\\}|+\frac{\lambda}{N_{a}(t)+\lambda}\|\theta^{\star}\|_{\infty}.$

Therefore, for a given $a\in[d],t\in[T]$, by introducing the event
$\mathcal{B}_{(t,a)}\triangleq\Big{\\{}|\hat{\theta}^{\lambda}_{t}(a)-\theta^{\star}_{a}|>\sqrt{\frac{6\sigma^{2}\log(T)}{\lambda+N_{a}(t)}}+\frac{\lambda\|\theta^{\star}\|_{\infty}}{\lambda+N_{a}(t)}\Big{\\}}$,
we deduce:

$\displaystyle\mathcal{B}_{(t,a)}$
$\displaystyle\subset\Big{\\{}|\frac{1}{N_{a}(t)+\lambda}\sum_{\tau=1}^{t}\epsilon_{\tau}\mathbf{1}\\{a_{\tau}=a,x_{a_{\tau}}=1\\}|+\frac{\lambda}{N_{a}(t)+\lambda}\|\theta^{\star}\|_{\infty}>\sqrt{\frac{6\sigma^{2}\log(T)}{\lambda+N_{a}(t)}}+\frac{\lambda\|\theta^{\star}\|_{\infty}}{\lambda+N_{a}(t)}\Big{\\}}$
$\displaystyle\subset\Big{\\{}|\frac{1}{N_{a}(t)+\lambda}\sum_{\tau=1}^{t}\epsilon_{\tau}\mathbf{1}\\{a_{\tau}=a,x_{a_{\tau}}=1\\}|>\sqrt{\frac{6\sigma^{2}\log(T)}{\lambda+N_{a}(t)}}\Big{\\}}.$

Then, we have:

$\displaystyle\mathbb{P}(\mathcal{H}_{\text{UCB}}^{\lambda})$
$\displaystyle=\displaystyle\mathbb{P}\Big{(}\bigcup_{a\in[d]}\bigcup_{t\in[T]}\mathcal{B}_{(t,a)}\Big{)}$
$\displaystyle\leq\mathbb{P}\Big{(}\bigcup_{a\in[d]}\bigcup_{t\in[T]}\Big{\\{}|\frac{1}{N_{a}(t)+\lambda}\sum_{\tau=1}^{t}\epsilon_{\tau}\mathbf{1}\\{a_{\tau}=a,x_{a_{\tau}}=1\\}|>\sqrt{\frac{6\sigma^{2}\log(T)}{\lambda+N_{a}(t)}}\Big{\\}}\Big{)}$
$\displaystyle\leq\sum_{a\in[d]}\mathbb{P}\Big{(}\bigcup_{t\in[T]}\Big{\\{}|\frac{1}{N_{a}(t)+\lambda}\sum_{\tau=1}^{t}\epsilon_{\tau}\mathbf{1}\\{a_{\tau}=a,x_{a_{\tau}}=1\\}|>\sqrt{\frac{6\sigma^{2}\log(T)}{\lambda+N_{a}(t)}}\Big{\\}}\Big{)}$
$\displaystyle=\sum_{a\in[d]}\mathbb{P}\Big{(}\bigcup_{k\in[T]}\bigcup_{t\in[T]}\Big{\\{}|\frac{1}{N_{a}(t)+\lambda}\sum_{\tau=1}^{t}\epsilon_{\tau}\mathbf{1}\\{a_{\tau}=a,x_{a_{\tau}}=1\\}|^{2}>\frac{6\sigma^{2}\log(T)}{\lambda+N_{a}(t)};N_{a}(t)=k\Big{\\}}\Big{)}$
$\displaystyle=\sum_{a\in[d]}\sum_{k\in[T]}\mathbb{P}(N_{a}(t)=k)\mathbb{P}\Big{(}\bigcup_{t\in[T]}\Big{\\{}|\frac{1}{k+\lambda}\sum_{\tau=1}^{t}\epsilon_{\tau}\mathbf{1}\\{a_{\tau}=a,x_{a_{\tau}}=1\\}|^{2}>\frac{6\sigma^{2}\log(T)}{k}\Big{|}N_{a}(t)=k\Big{\\}}\Big{)}$
$\displaystyle\leq\sum_{a\in[d]}\sum_{k\in[T]}\mathbb{P}\Big{(}\bigcup_{t\in[T]}\Big{\\{}|\frac{1}{k+\lambda}\sum_{\tau=1}^{t}\epsilon_{\tau}\mathbf{1}\\{a_{\tau}=a,x_{a_{\tau}}=1\\}|^{2}>\frac{6\sigma^{2}\log(T)}{\lambda+k}\Big{|}N_{a}(t)=k\Big{\\}}\Big{)}$
$\displaystyle=\sum_{a\in[d]}\sum_{k\in[T]}\mathbb{P}\Big{(}|\frac{\sum_{l=1}^{k}\epsilon_{l}}{k+\lambda}|^{2}>\frac{6\sigma^{2}\log(T)}{\lambda+k}\Big{)},$

where we successively used union bounds over the action set and number of
realizations and conditioned over number of realizations $k$. We re-indexed
the random sub-Gaussian variables $(\epsilon_{t})$ for last expression thanks
to the i.i.d property. Then, for a given $k$, using Hoeffding inequality for
sub-Gaussian variables, we have:

$\displaystyle\mathbb{P}\Big{(}|\frac{\sum_{l=1}^{k}\epsilon_{l}}{k+\lambda}|^{2}>\frac{6\sigma^{2}\log(T)}{k+\lambda}\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}|\sum_{l=1}^{k}\epsilon_{l}|>\sqrt{6\sigma^{2}(k+\lambda)\log(T)}\Big{)}$
$\displaystyle\leq
2\exp\\{-\frac{6\sigma^{2}(k+\lambda)\log(T)}{2k\sigma^{2}}\\}$
$\displaystyle\leq\frac{2}{T^{3}}$

where the used that fact that $\sum_{l=1}^{k}\epsilon_{l}$ is sub-Gaussian of
pseudo-variance parameter $k\sigma^{2}$ Therefore, this yields:

$\displaystyle\sum_{a\in[d]}\sum_{k\in[T]}\mathbb{P}\Big{(}|\frac{\sum_{l=1}^{k}\epsilon_{l}}{k+\lambda}|^{2}>\frac{6\sigma^{2}\log(T)}{k+\lambda}\Big{)}\leq\frac{2d}{T^{2}}.$

Finally, we conclude that
$\mathbb{P}(\mathcal{H}_{\text{UCB}}^{\lambda})\leq\frac{2d}{T^{2}}$. ∎

######  Remark 2.

We note that assuming tails distribution for the reward noise $\epsilon$ of
the form:

$\displaystyle\mathbb{P}\left(\epsilon\geq
x\right)\leq\exp\Big{\\{}\frac{-x^{1+q}}{2\sigma^{2}}\Big{\\}}$

for a given $q>0$, as suggested for instance in [47], would lead the use of
the confidence interval:

$\displaystyle\mathcal{H}_{\text{UCB}}^{\lambda,q}=\Big{\\{}\exists
a\in[d],t\in[T],|\hat{\theta}^{\lambda}_{t}(a)-\theta^{\star}_{a}|>\Big{(}6\sigma^{2}\log(T)\Big{)}^{\frac{1}{1+q}}\Big{(}\lambda+N_{a}(t)\Big{)}^{-\frac{q}{1+q}}+\frac{\lambda\|\theta^{\star}\|_{\infty}}{\lambda+N_{a}(t)}\Big{\\}}.$

Indeed, the same reasoning as above would then yield:

$\displaystyle\mathbb{P}\Big{(}|\frac{\sum_{l=1}^{k}\epsilon_{l}}{k+\lambda}|>(6\sigma^{2}\log(T))^{\frac{1}{1+q}}(k+\lambda)^{-\frac{a}{1+q}}\Big{)}$
$\displaystyle=\mathbb{P}\Big{(}|\sum_{l=1}^{k}\epsilon_{l}|>(6\sigma^{2}(k+\lambda)\log(T))^{\frac{1}{1+q}}\Big{)}$
$\displaystyle\leq
2\exp\\{-\frac{6\sigma^{2}(k+\lambda)\log(T)}{2k\sigma^{2}})\\}\leq\frac{2}{T^{3}}$

and therefore
$\mathbb{P}(\mathcal{H}_{\text{UCB}}^{\lambda,q})\leq\frac{2d}{T^{2}}$. For
$q=1$, we recover the sub-Gaussian case, which in turns lead to the study of
$\mathbb{V}_{1/2}$, as done in Lemma 3.3. For general $q>0$, we would would
then consider $\mathbb{V}_{q/(1+q)}$, which lead to the upper bound
$\mathcal{O}(d_{\mathit{eff}}^{q/(1+q)}T^{1/(1+q)})$ through the use of Prop.
3.4.

###  B.3 Statement and Proof of Lemma B.2

######  Lemma B.2.

For any $\delta\in]0,1]$, $\lambda>0$ and censorship model, let’s introduce
the event:

$\displaystyle\mathcal{H}^{I}_{\text{CEN}}(\delta)$
$\displaystyle=\left\\{\exists
a\in[d],t\in[T],N_{a}(t)<(1-\delta)p_{a}\tau_{a}(t)\quad\text{and}\quad\tau_{a}(t)\geq
T_{0}(a)\right\\},$

where $T_{0}(a)\triangleq 24\log(T)/p_{a}+1$. We then have
$\mathbb{P}(\mathcal{H}^{I}_{\text{CEN}}(\delta))\leq\frac{4d_{\mathit{eff}}}{\delta^{2}}T^{-12\delta^{2}}$.

###### Proof.

First, we apply successively two unions bounds over the action set and the
number of realizations, mirroring the analysis of [24]:

$\displaystyle\mathbb{P}(\mathcal{H}^{I}_{\text{CEN}}(\delta))$
$\displaystyle\leq\sum_{a\in[d]}\mathbb{P}\Big{(}\Big{\\{}\exists
t\in[T],\tau_{a}(t)\geq
T_{0}(a),N_{a}(t)<(1-\delta)p_{a}\tau_{a}(t)\Big{\\}}\Big{)}$
$\displaystyle=\sum_{a\in[d]}\mathbb{P}\Big{(}\bigcup_{k_{a}\in[T_{0}(a),T]}\bigcup_{t\in[T]}\Big{\\{}\tau_{a}(t)\geq
T_{0}(a),N_{a}(t)<(1-\delta)p_{a}\tau_{a}(t),\tau_{a}(t)=k_{a}\Big{\\}}\Big{)}$
$\displaystyle\leq\sum_{a\in[d]}\sum_{k_{a}\geq
T_{0}(a)}\mathbb{P}\Big{(}\bigcup_{t\in[T]}\Big{\\{}N_{a}(t)<(1-\delta)p_{a}\tau_{a}(t)\Big{|}\tau_{a}(t)=k_{a}\Big{\\}}\Big{)}.$

We then use a multiplicative Chernoff inequality for Binomial Distribution to
deduce:

$\displaystyle\sum_{a\in[d]}\sum_{k_{a}\geq
T_{0}(a)}\mathbb{P}\Big{(}N_{a}(t)$
$\displaystyle<(1-\delta)p_{a}\tau_{a}(t)\Big{|}\tau_{a}(t)=k_{a}\Big{)}\leq\sum_{a\in[d]}\sum_{k_{a}\geq
T_{0}(a)}\exp\\{-\frac{\delta^{2}k_{a}p_{a}}{2}\\}.$

The novelty of our proof is to leverage a integral comparison to deduce the
improved control:

$\displaystyle\sum_{a\in[d]}\sum_{k_{a}\geq
T_{0}(a)}\exp\\{-\frac{\delta^{2}k_{a}p_{a}}{2}\\}$ $\displaystyle\leq
2\sum_{a\in[d]}\left[-\frac{2}{\delta^{2}p_{a}}\exp\\{-\frac{\delta^{2}k_{a}p_{a}}{2}\\}\right]^{\tau_{a}(t)}_{T_{0}(a)-1}$
$\displaystyle\leq\frac{4}{\delta^{2}}d_{\mathit{eff}}\frac{1}{T^{12\delta^{2}}}-\frac{4}{\delta^{2}}\sum_{a\in[d]}\frac{1}{p_{a}}\exp\\{-\frac{\delta^{2}\tau_{a}(t)p_{a}}{2}\\}\leq\frac{4}{\delta^{2}}d_{\mathit{eff}}\frac{1}{T^{12\delta^{2}}}.$

Picking for instance $\delta=\frac{1}{2}$ yields
$\mathbb{P}(\mathcal{H}^{I}_{\text{CEN}}(\frac{1}{2}))\leq\frac{16d_{\mathit{eff}}}{T^{3}}$.
∎

###  B.4 Proof of Lemma 3.5

See 3.5

###### Proof.

We first introduce the Lagrangian of the problem
$\mathcal{L}(\tau_{1},\dots,\tau_{d},\mu):=\sum_{a\in[d]}\frac{1}{p_{a}}\Big{(}\psi_{\alpha}(p_{a}\tau_{a}+\lambda_{a})-\psi_{\alpha}(\lambda_{a})\Big{)}+\mu(T-\sum_{a\in[d]}\tau_{a})$.
Differentiating with respect to $\tau_{a}$ for all $a\in[d]$ yields the
equations:

$\displaystyle\frac{1}{(p_{a}\tau_{a}+\lambda_{a})^{\alpha}}-\mu=0.$

We then write it equivalently as:

$\displaystyle\tau_{a}=\frac{1}{p_{a}}[\mu^{-1/\alpha}-\lambda_{a}].$

However, since $(\tau_{a})$ must be nonnegative, it may not always be possible
to find a solution of this form. We then verify using KKT conditions that the
solution:

$\displaystyle\tau_{a}=\frac{1}{p_{a}}[C-\lambda_{a}]^{+},$

where $C$ ensures the total budget constraint
$\sum_{a\in[d]}\tau^{\star}_{a}=T$, is optimal. In particular, whenever
$T\geq\max_{a}\lambda_{a}^{0}$, we recover the solution provided in the second
part the Lemma. ∎

###  B.5 Proof of Prop. 3.4

See 3.4

###### Proof.

For a given $\alpha\in]0,1]$, we condition on the event
$\mathcal{H}^{I}_{\text{CEN}}(\delta)$ introduced in Lemma B.2 and consider
the cases $\tau_{a}(t)\geq T_{0}(a)$ and $\tau_{a}(t)<T_{0}(a)$. This yields
for any policy $\pi\in\Pi$:

$\displaystyle\mathbb{V}_{\alpha}(T,\pi|\mathcal{H}^{I}_{\text{CEN}}(\delta))$
$\displaystyle\leq\frac{\sum_{a\in[d]}T_{0}(a)}{\lambda^{\alpha}}+\sum_{t=1}^{T}\left((1-\delta)p_{a_{t}}\tau_{a_{t}}(t-1)+\lambda\right)^{-\alpha}$
$\displaystyle\leq\frac{24d_{\mathit{eff}}\log(T)+d}{\lambda^{\alpha}}+\frac{1}{(1-\delta)^{\alpha}}\sum_{t=1}^{T}\left(p_{a_{t}}\tau_{a_{t}}(t-1)+\frac{\lambda}{1-\delta}\right)^{-\alpha}$
$\displaystyle\leq\frac{24d_{\mathit{eff}}\log(T)+d}{\lambda^{\alpha}}+\frac{1}{(1-\delta)^{\alpha}}\sum_{a\in[d]}\int_{0}^{\tau_{a}(T)}\left(p_{a}u+\frac{\lambda}{1-\delta}\right)^{-\alpha}\partial
u$
$\displaystyle=\frac{24d_{\mathit{eff}}\log(T)+d}{\lambda^{\alpha}}+\frac{1}{(1-\delta)^{\alpha}}\sum_{a\in[d]}\frac{1}{p_{a}}[\psi_{\alpha}(p_{a}\tau_{a}(T)+\frac{\lambda}{1-\delta})-\psi_{\alpha}(\frac{\lambda}{1-\delta})].$

We then apply the Lemma 3.5 with constant
$\tilde{\lambda}\triangleq\lambda/(1-\delta)$ to deduce:

$\displaystyle\max_{\pi\in\Pi}\mathbb{V}_{\alpha}(T,\pi|\neg\mathcal{H}^{I}_{\text{CEN}}(\delta))\leq\frac{24d_{\mathit{eff}}\log(T)+d}{\lambda^{\alpha}}+\frac{d_{\mathit{eff}}}{(1-\delta)^{\alpha}}\Big{[}\psi_{\alpha}(\frac{T}{d_{\mathit{eff}}}+\frac{\lambda}{1-\delta})-\psi_{\alpha}(\frac{\lambda}{1-\delta})\Big{]}.$

Then, we conclude thanks to Lemma B.2 that:

$\displaystyle\max_{\pi\in\Pi}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]$
$\displaystyle\leq\mathbb{P}(\neg\mathcal{H}^{I}_{\text{CEN}}(\delta))\max_{\pi\in\Pi}\mathbb{V}_{\alpha}(T,\pi|\neg\mathcal{H}^{I}_{\text{CEN}}(\delta))+(1-\mathbb{P}(\neg\mathcal{H}^{I}_{\text{CEN}}(\delta)))\frac{1}{\lambda^{\alpha}}$
$\displaystyle\leq\frac{1}{(1-\delta)^{\alpha}}d_{\mathit{eff}}\left[\psi_{\alpha}(\frac{T}{d_{\mathit{eff}}}+\frac{\lambda}{1-\delta})-\psi_{\alpha}(\frac{\lambda}{1-\delta})\right]+\frac{24d_{\mathit{eff}}\log(T)+d}{\lambda^{\alpha}}$
$\displaystyle+\frac{4}{\delta^{2}}d_{\mathit{eff}}\frac{1}{\lambda^{\alpha}T^{12\delta^{2}}}.$

In particular, for $\alpha=1$ and $\delta=\frac{1}{2}$, this involves:

$\displaystyle\max_{\pi\in\Pi}\mathbb{E}[\mathbb{V}_{1}(T,\pi)]\leq
2d_{\mathit{eff}}\log(\frac{T}{2\lambda}+1)+\frac{24d_{\mathit{eff}}\log(T)+d}{\lambda}+16d_{\mathit{eff}}\frac{1}{\lambda
T^{2}},$

and for $\alpha=\frac{1}{2}$ and $\delta=\frac{1}{2}$, this yields:

$\displaystyle\max_{\pi\in\Pi}\mathbb{E}[\mathbb{V}_{\frac{1}{2}}(T,\pi)]\leq\sqrt{2}d_{\mathit{eff}}\left[\sqrt{\frac{T}{d_{\mathit{eff}}}+2\lambda}-\sqrt{2\lambda}\right]+\frac{24d_{\mathit{eff}}\log(T)+d}{\sqrt{\lambda}}+16d_{\mathit{eff}}\frac{1}{\sqrt{\lambda}T^{2}}.$

∎

###  B.6 Proof of Thm. 3.1

See 3.1

###### Proof.

We first apply Lemma 3.3 to deduce:

$\displaystyle\mathbb{E}[R(T,\pi_{\text{UCB}})]$ $\displaystyle\leq
2\sqrt{6\sigma^{2}\log(T)}\mathbb{E}[\mathbb{V}_{\frac{1}{2}}(T,\pi_{\text{UCB}})]+2\lambda\|\theta^{\star}\|_{\infty}\mathbb{E}[\mathbb{V}_{1}(T,\pi_{\text{UCB}})]+\frac{2d\Delta_{max}}{T}$
$\displaystyle\leq
2\sqrt{6\sigma^{2}\log(T)}\max_{\pi\in\Pi}\mathbb{E}[\mathbb{V}_{\frac{1}{2}}(T,\pi)]+2\lambda\|\theta^{\star}\|_{\infty}\max_{\pi\in\Pi}\mathbb{E}[\mathbb{V}_{1}(T,\pi)]+\frac{2d\Delta_{max}}{T}.$

We then apply proposition 3.4, with $\delta=1/2$ in order to deduce:

$\displaystyle\mathbb{E}[R(T,\pi_{\text{UCB}})]$ $\displaystyle\leq
2\sqrt{6\sigma^{2}\log(T)}\Big{(}\sqrt{2}d_{\mathit{eff}}\Big{[}\sqrt{\frac{T}{d_{\mathit{eff}}}+2\lambda}-\sqrt{2\lambda}\Big{]}+\frac{24d_{\mathit{eff}}\log(T)+d}{\sqrt{\lambda}}+16d_{\mathit{eff}}\frac{1}{\sqrt{\lambda}T^{2}}\Big{)}$
$\displaystyle+2\lambda\|\theta^{\star}\|_{\infty}\Big{(}2d_{\mathit{eff}}\log\Big{(}\frac{T}{2\lambda}+1\Big{)}+\frac{24d_{\mathit{eff}}\log(T)+d}{\lambda^{\alpha}}+16d_{\mathit{eff}}\frac{1}{\lambda
T^{2}}\Big{)}+\frac{2d\Delta_{max}}{T}.$

By taking $\lambda=o(\log(T))$ and considering only the leading order, we
conclude that:

$\displaystyle\mathbb{E}[R(T,\pi_{\text{UCB}})]\leq\tilde{\mathcal{O}}(\sigma\sqrt{d_{\mathit{eff}}T}).$

Note that our proof easily allows to get high-probability bounds on regret
instead of bounds on its expected value. ∎

######  Remark 3.

We now extend Thm. 3.1 to heteroskedastic MAB. In this model, the pseudo-
variance of the sub-Gaussian noisy reward is arm-dependent and denoted
$\sigma_{a}$. Moreover, the value of $\sigma_{a}$ is known to the designer of
the algorithm, that is, it can be used as a parameter for the UCB algorithm.
We first apply a slightly modified version of Lemma 3.3 to deduce:

$\displaystyle\mathbb{E}[R(T,\pi_{\text{UCB}})]$ $\displaystyle\leq
2\sqrt{6\log(T)}\mathbb{E}[\bar{\mathbb{V}}_{\frac{1}{2}}(T,\pi_{\text{UCB}})]+2\lambda\|\theta^{\star}\|_{\infty}\mathbb{E}[\mathbb{V}_{1}(T,\pi_{\text{UCB}})]+\frac{2d\Delta_{max}}{T},$

where for $\alpha>0$ and $\pi\in\Pi$, we introduced the variance-based
cumulative potential:

$\displaystyle\bar{\mathbb{V}}_{\alpha}(T,\pi)=\sum_{t=1}^{T}(\frac{N_{a_{t}}(t-1)}{\sigma^{1/\alpha}_{a_{t}}}+\frac{\lambda}{\sigma^{1/\alpha}_{a_{t}}})^{-\alpha}.$

Thus, heteroskedasticity induces the mapping $\breve{p_{a}}\equiv
p_{a}/\sigma^{1/\alpha}_{a}$ and
$\breve{\lambda}_{a}\equiv\lambda/\sigma^{1/\alpha}_{a}$. Following the proof
of Prop. 3.4, we deduce for any $\alpha>0$ and time allocation
$(\tau_{a}(T))_{a\in[d]}$:

$\displaystyle\mathbb{V}_{\alpha}(T,\pi|\mathcal{H}^{I}_{\text{CEN}}(\delta))$
$\displaystyle\leq\frac{24d_{\mathit{eff}}\log(T)+d}{\lambda^{\alpha}}+\frac{1}{(1-\delta)^{\alpha}}\sum_{a\in[d]}\frac{1}{\breve{p_{a}}}[\psi_{\alpha}(\breve{p_{a}}\tau_{a}(T)+\frac{\breve{\lambda}_{a}}{1-\delta})-\psi_{\alpha}(\frac{\breve{\lambda}_{a}}{1-\delta})].$

In order to apply Lemma 3.5, we introduce the notation:

$\displaystyle\breve{d}_{\mathit{eff}}=\sum_{a\in[d]}\frac{\sigma^{1/\alpha}_{a}}{p_{a}},\quad\breve{\lambda}_{\mathit{eff}}=\frac{\lambda}{1-\delta}\frac{d_{\mathit{eff}}}{\breve{d}_{\mathit{eff}}}\quad\text{and}\quad\breve{\lambda}_{a}^{0}=\frac{\lambda\breve{d}_{\mathit{eff}}}{1-\delta}(\frac{1}{\sigma^{1/\alpha}_{a}}-\frac{d_{\mathit{eff}}}{\breve{d}_{\mathit{eff}}}).$

and we deduce that whenever $T\geq\max_{a}\breve{\lambda}_{a}^{0}$, we have:

$\displaystyle\mathbb{V}_{\alpha}(T,\pi|\mathcal{H}^{I}_{\text{CEN}}(\delta))$
$\displaystyle\leq\frac{24d_{\mathit{eff}}\log(T)+d}{\lambda^{\alpha}}+\frac{1}{(1-\delta)^{\alpha}}\Big{[}\breve{d}_{\mathit{eff}}\psi_{\alpha}(\frac{T}{\breve{d}_{\mathit{eff}}}+\breve{\lambda}_{\mathit{eff}})-\sum_{a\in[d]}\frac{\sigma^{1/\alpha}_{a}}{p_{a}}\psi_{\alpha}(\frac{\lambda}{(1-\delta)\sigma^{1/\alpha}_{a}})\Big{]}.$

In particular, by considering the case $\alpha=\nicefrac{{1}}{{2}}$ and only
the leading order, we deduce that:

$\displaystyle\mathbb{E}[R(T,\pi_{\text{UCB}})]\leq\tilde{\mathcal{O}}\Big{(}\sqrt{\breve{d}_{\mathit{eff}}T}\Big{)},$

where as affirmed
$\breve{d}_{\mathit{eff}}=\sum_{a\in[d]}\frac{\sigma_{a}^{2}}{p_{a}}$.

###  B.7 Proof of Prop. 3.2

See 3.2

###### Proof.

As in the proof of Lemma 3.4, for a given round $t\in[T]$, we have under the
event $\neg\mathcal{H}_{\text{UCB}}^{\lambda}$

$\displaystyle\Delta_{a}=\max_{\tilde{a}\in\mathcal{A}}\theta^{\star}_{\tilde{a}}-\theta^{\star}_{a}\leq
2\sqrt{6\sigma^{2}\frac{\log(T)}{N_{a_{t}}(t-1)+\lambda}}+2\frac{\lambda\|\theta^{\star}\|_{\infty}}{\lambda+N_{a_{t}}(t-1)}.$

It is as an inequality of the second degree and thus for any $t\in[T]$,
$a\in[d]$:

$\displaystyle
x_{1}\left(\sqrt{\frac{1}{\lambda+N_{a}(t)}}\right)^{2}+x_{2}\sqrt{\frac{1}{\lambda+N_{a}(t)}}-\Delta_{a}\geq
0,$

where $x_{1}=2\lambda\|\theta^{\star}\|_{\infty}$ and
$x_{2}=2\sqrt{6\sigma^{2}\log(T)}$. Solving it yields:

$\displaystyle\sqrt{\frac{1}{\lambda+N_{a}(t)}}\geq\frac{1}{2x_{1}}(-x_{2}+\sqrt{x_{2}^{2}+4\Delta_{a}x_{1}}),$

or equivalently:

$\displaystyle N_{a}(T)$
$\displaystyle\leq\Big{(}\frac{4\lambda\|\theta^{\star}\|_{\infty}}{\sqrt{24\sigma^{2}\log(T)+8\Delta_{a}\lambda\|\theta^{\star}\|_{\infty}}-\sqrt{24\sigma^{2}\log(T)}}\Big{)}^{2}-\lambda\triangleq\Theta(T),$

where we used the notation $\Theta(T)$ to simplify the presentation.Therefore,
under $\neg\mathcal{H}^{I}_{\text{CEN}}(\frac{1}{2})$, we have:

$\displaystyle\tau_{a}(t)\leq\max(T_{0}(a),\frac{2}{p_{a}}\Theta(T)).$

This yields a conditional regret of:

$\displaystyle R(T|$
$\displaystyle\neg(\mathcal{H}^{I}_{\text{CEN}}(\frac{1}{2})\cup\mathcal{H}^{\lambda}_{\text{UCB}}))\leq\sum_{a\in[d],a\neq
a^{\star}}\Delta_{a}\tau_{a}(T)=\sum_{a\in[d],a\neq
a^{\star}}\frac{2\Delta_{a}}{p_{a}}\max(12\log(T)+\frac{p_{a}}{2},\Theta(T)),$

where
$a^{\star}\triangleq\operatorname{argmax}_{\tilde{a}\in\mathcal{A}}\theta^{\star}_{\tilde{a}}$
and an expected regret of:

$\displaystyle\mathbb{E}[R(T,\pi_{\mathit{UCB}})]$
$\displaystyle\leq\sum_{a\in[d],a\neq
a^{\star}}\frac{2\Delta_{a}}{p_{a}}\max(12\log(T)+\frac{p_{a}}{2},\Theta(T))+\frac{d\Delta_{max}}{T}+\frac{16d_{\mathit{eff}}\Delta_{max}}{T^{2}}.$

In particular, for the regularization $\lambda=o(\log(T))$, we have the
asymptotic:

$\displaystyle\Theta(T)=\Big{(}\frac{4\lambda\|\theta^{\star}\|_{\infty}}{\sqrt{24\sigma^{2}\log(T)+8\Delta_{a}\lambda\|\theta^{\star}\|_{\infty}}-\sqrt{24\sigma^{2}\log(T)}}\Big{)}^{2}=\frac{24\sigma^{2}\log(T)}{\Delta_{a}^{2}}+\frac{8\lambda\|\theta^{\star}\|_{\infty}}{2\Delta_{a}}+o(1).$

And thus, we conclude that:

$\displaystyle\mathbb{E}[R(T,\pi_{\mathit{UCB}})]$
$\displaystyle\leq\mathcal{O}\Big{(}\log(T)\sum_{a\in[d],a\neq
a^{\star}}\frac{1}{p_{a}}\max(\frac{\sigma^{2}}{\Delta_{a}},\Delta_{a})\Big{)}.$

Again, note that our proof easily allows to get high-probability bounds on
regret instead of bounds on its expected value. ∎

######  Remark 4.

As in the instance-independent case, previous reasoning immediately extends to
a-priori known heteroskedasticity and yields the upper bound:

$\displaystyle\mathbb{E}[R(T,\pi_{\mathit{UCB}})]$
$\displaystyle\leq\mathcal{O}\Big{(}\log(T)\sum_{a\in[d],a\neq
a^{\star}}\frac{1}{p_{a}}\max(\frac{\sigma_{a}^{2}}{\Delta_{a}},\Delta_{a})\Big{)}.$

Next, we provide additional insights to the main result of this section. In
particular, we seek to gain intuition about how the policies that are adaptive
to the realization of censorship process would perform in expectation against
a class of non-adaptive (i.e. offline ) policies. In order to precisely derive
asymptotic behavior of such policies, we introduce and study a continuous
counterpart of the discrete original policy maximization problem
$\max_{\pi\in\Pi}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]$.

Lemma 3.6 provides the basis for continuous approach in the case of offline
policies by leveraging concentration inequalities for inverse Binomial
distribution. We then extend this approach in the proof of Prop. 3.7. This
extension enables us to provide an exact expression for the asymptotic gain of
a policy class that monitors the censorship at a single point in time, as well
as estimate the gain from fully adaptive policies.

###  B.8 Proof of Lemma 3.6

See 3.6

###### Proof.

Given the offline nature of the policy class, we have:

$\displaystyle\max_{\pi\in\Pi_{\text{off}}}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]=\max_{(\tau_{a})_{a\in[d]}}\sum_{a\in[d]}\mathbb{E}\Big{[}\sum_{n=1}^{\tau_{a}}\frac{1}{(X^{a}_{n-1}+\lambda)^{\alpha}})\Big{]}=\max_{(\tau_{a})_{a\in[d]}}\sum_{a\in[d]}\sum_{n=1}^{\tau_{a}}\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n-1}+\lambda)^{\alpha}})\Big{]}$

where we have re-indexed $(N_{a}(t))$ by actions, where $(\tau_{a})_{a\in[d]}$
is a time allocation such that $\sum_{a\in[d]}\tau_{a}=T$ and where for a
given action $a$, $(X^{a}_{n})_{n\leq\tau_{a}}$ are dependent random variables
verifying $X_{n+1}=X^{a}_{n}+\mathcal{B}(p_{a})$ and
$X^{a}_{n}\sim\mathcal{B}(n,p_{a})$.

To lower bound this quantity, we fix a time allocation $(\tau_{a})_{a\in[d]}$
and use the fact that $x\mapsto x^{-\alpha}$ is convex with Jensen’s
inequality to deduce:

$\displaystyle\sum_{n=1}^{\tau_{a}}\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n-1}+\lambda)^{\alpha}})\Big{]}$
$\displaystyle\geq\sum_{n=1}^{\tau_{a}}\frac{1}{(\mathbb{E}[X^{a}_{n-1}]+\lambda)^{\alpha}}=\sum_{n=1}^{\tau_{a}}\frac{1}{(p_{a}(n-1)+\lambda)^{\alpha}}=\frac{1}{\lambda^{\alpha}}+\sum_{n=1}^{\tau_{a}-1}\frac{1}{(p_{a}n+\lambda)^{\alpha}}$

We then leverage the fact that
$(px+\lambda)^{-\alpha}\geq\int_{x-1}^{x}(pu+\lambda)^{-\alpha}\partial u$ to
deduce:

$\displaystyle\sum_{n=1}^{\tau_{a}}\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n-1}+\lambda)^{\alpha}})\Big{]}\geq\frac{1}{\lambda^{\alpha}}+\sum_{a\in[d]}\int_{0}^{\tau_{a}-1}\frac{1}{(p_{a}x+\lambda)^{\alpha}}\partial
x=\frac{1}{\lambda^{\alpha}}+\frac{1}{p_{a}}\Big{[}\psi_{\alpha}(p_{a}(\tau_{a}-1)+\lambda)-\psi_{\alpha}(\lambda)\Big{]}$

and therefore, for any time allocation $(\tau_{a})_{a\in[d]}$, we have:

$\displaystyle\max_{\pi\in\Pi_{\text{off}}}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]\geq\frac{d}{\lambda^{\alpha}}+\sum_{a\in[d]}\frac{1}{p_{a}}\Big{[}\psi_{\alpha}(p_{a}(\tau_{a}-1)+\lambda)-\psi_{\alpha}(\lambda)\Big{]}$

Although the maximum over time allocation is given by Lemma 3.5, we simply use
the allocation $(\frac{T}{p_{a}d_{\mathit{eff}}})_{a\in[d]}$ to deduce:

$\displaystyle\max_{\pi\in\Pi_{\text{off}}}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]\geq\sum_{a\in[d]}\frac{1}{p_{a}}\psi_{\alpha}(\frac{T}{d_{\mathit{eff}}}+\lambda-\frac{1}{p_{a}})+\frac{d}{\lambda^{\alpha}}-\sum_{a\in[d]}\frac{1}{p_{a}}\psi_{\alpha}(\lambda)$

By making the distinction between $\alpha=1$ and $\alpha<1$ to obtain the
explicit expression of $\psi_{\alpha}$, we then show that the LHS is
equivalent to
$d_{\mathit{eff}}\psi_{\alpha}(\frac{T}{d_{\mathit{eff}}}+\lambda)$. The proof
of the upper bound is more involved. In proving it, let’s first assume that:

######  Claim B.3.

For all $a\in[d]$, $n\geq 1$, there exists a constant $C_{2}^{a}$ such that:

$\displaystyle\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n}+\lambda)^{\alpha}})\Big{]}\leq(1+\frac{C_{2}^{a}}{(np_{a})^{1/4}})\frac{1}{(p_{a}n+\lambda)^{\alpha}}$

Given this result, we deduce:

$\displaystyle\sum_{n=1}^{\tau_{a}-1}\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n}+\lambda)^{\alpha}})\Big{]}\leq\sum_{n=1}^{\tau_{a}-1}(1+\frac{C_{2}^{a}}{(np_{a})^{1/4}})\frac{1}{(p_{a}n+\lambda)^{\alpha}}.$

Therefore, we have:

$\displaystyle\max_{(\tau_{a})_{a\in[d]}}\sum_{a\in[d]}\sum_{n=1}^{\tau_{a}}\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n-1}+\lambda)^{\alpha}})\Big{]}$
$\displaystyle\leq\frac{d}{\lambda^{\alpha}}+\max_{(\tau_{a})_{a\in[d]}}\sum_{a\in[d]}\sum_{n=1}^{\tau_{a}}\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n}+\lambda)^{\alpha}})\Big{]}$
$\displaystyle\leq\sum_{a\in[d]}\frac{1}{\lambda^{\alpha}}+\max_{(\tau_{a})_{a\in[d]}}\sum_{a\in[d]}\sum_{n=1}^{\tau_{a}}\frac{1}{(p_{a}n+\lambda)^{\alpha}}$
$\displaystyle\quad\quad\quad+(\max_{a\in[d]}C_{2}^{a})\max_{(\tau_{a})_{a\in[d]}}\sum_{a\in[d]}\sum_{n=1}^{\tau_{a}}\frac{1}{(p_{a}n)^{1/4}}\frac{1}{(p_{a}n+\lambda)^{\alpha}}.$

We first consider the second maximization problem and note that:

$\displaystyle\max_{(\tau_{a})_{a\in[d]}}\sum_{a\in[d]}\sum_{n=1}^{\tau_{a}}\frac{1}{(p_{a}n)^{1/4}}\frac{1}{(p_{a}n+\lambda)^{\alpha}}$
$\displaystyle\leq\lambda^{1/4}\max_{(\tau_{a})_{a\in[d]}}\sum_{a\in[d]}\sum_{n=1}^{\tau_{a}}\frac{1}{(p_{a}n+\lambda)^{\alpha+1/4}}$
$\displaystyle=\mathcal{O}(d_{\mathit{eff}}\psi_{\alpha+\frac{1}{4}}(\frac{T}{d_{\mathit{eff}}}+\lambda))$
$\displaystyle=o(d_{\mathit{eff}}\psi_{\alpha}(\frac{T}{d_{\mathit{eff}}}+\lambda))$

where we used an integral comparison and Lemma 3.5 to deduce the $\mathcal{O}$
scaling and the fact that $\alpha\in]0,1]$ the deduce the $o$ scaling.
Similarly, we know that the first maximization problem scales as
$d_{\mathit{eff}}\psi_{\alpha}(\frac{T}{d_{\mathit{eff}}}+\lambda)$ through
another integral comparison and use of Lemma 3.5. Given this, we conclude that
the upper bound is equivalent to
$d_{\mathit{eff}}\psi_{\alpha}(\frac{T}{d_{\mathit{eff}}}+\lambda)$. Thanks to
those two results, we finally affirm that:

$\displaystyle\displaystyle\max_{\pi\in\Pi_{\text{off}}}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]\sim
d_{\mathit{eff}}\psi_{\alpha}(\frac{T}{d_{\mathit{eff}}}+\lambda).$

The last step needed is to prove Claim. B.3. In doing so, we extend Lemma
$5.3$ of [5] to more general inverse power function (i.e. $\alpha\neq 1$) with
regularization $\lambda>0$. We first introduce a tuning parameter $u\geq 0$
and write:

$\displaystyle(\mathbb{E}[X^{a}_{n}]+\lambda)^{\alpha}\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n}+\lambda)^{\alpha}}\Big{]}$
$\displaystyle=(np_{a}+\lambda)^{\alpha}\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n}+\lambda)^{\alpha}}\mathbf{1}\\{X^{a}_{n}\leq
u\mathbb{E}[X^{a}_{n}]\\}\Big{]}$
$\displaystyle\quad\quad\quad+\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n}+\lambda)^{\alpha}}\mathbf{1}\\{X^{a}_{n}>u\mathbb{E}[X^{a}_{n}]\\}\Big{]}$
$\displaystyle\leq\frac{(np_{a}+\lambda)^{\alpha}}{\lambda^{\alpha}}\mathbb{P}(X^{a}_{n}\leq
u\cdot np_{a})+(\frac{np_{a}+\lambda}{u\cdot np_{a}+\lambda})^{\alpha}.$

Using a Berstein inequality for Binomiale variable, we have for all $\theta>0$
and $n\in\mathbb{N}$:

$\displaystyle\mathbb{P}\left(X_{n}^{a}\leq\left(1-\sqrt{2\theta}-\frac{\theta}{3}\right)np_{a}\right)\leq
e^{-\theta np_{a}}.$

Thus, for all $0<\theta\leq\frac{3(\sqrt{5}-\sqrt{3})^{2}}{2}$, by setting
$u\equiv(1-\sqrt{2\theta}-\frac{\theta}{3})\geq 0$, we obtain that:

$\displaystyle(\mathbb{E}[X^{a}_{n}]+\lambda)^{\alpha}\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n}+\lambda)^{\alpha}}\Big{]}\leq\frac{(np_{a}+\lambda)^{\alpha}}{\lambda^{\alpha}}e^{-\theta
np_{a}}+\Big{(}\frac{np_{a}+\lambda}{(1-\sqrt{2\theta}-\frac{\theta}{3})np_{a}+\lambda}\Big{)}^{\alpha}.$

By taking $\theta=A\frac{\log(np_{a}+\lambda)}{np_{a}}$ for another tunable
parameter $A$ and for $n$ large enough to ensure
$A\frac{\log(np_{a}+\lambda)}{np_{a}}\leq\frac{3(\sqrt{5}-\sqrt{3})^{2}}{2}$,
this yields:

$\displaystyle(\mathbb{E}[X^{a}_{n}]+\lambda)^{\alpha}\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n}+\lambda)^{\alpha}}\Big{]}$
$\displaystyle\leq\frac{(np_{a}+\lambda)^{\alpha}}{\lambda^{\alpha}(np_{a}+\lambda)^{A}}+\Big{(}\frac{np_{a}+\lambda}{(1-\sqrt{2A\frac{\log(np_{a}+\lambda)}{np_{a}}}-A\frac{\log(np_{a}+\lambda)}{3np_{a}})np_{a}+\lambda}\Big{)}^{\alpha}$
$\displaystyle=\frac{(np_{a}+\lambda)^{\alpha}}{\lambda^{\alpha}(np_{a}+\lambda)^{A}}+\Big{(}\frac{np_{a}+\lambda}{np_{a}+\lambda-\sqrt{2Anp_{a}\log(np_{a}+\lambda)}-\frac{A\log(np_{a}+\lambda)}{3}}\Big{)}^{\alpha}$

For $n$ sufficiently large to ensure
$\frac{3\sqrt{2Anp_{a}\log(np_{a})}+A\log(np_{a})}{3(np_{a}+\lambda)}\leq 1/2$
and given that $\alpha\in]0,1]$, we then have:

$\displaystyle\Big{(}\frac{1}{1-\frac{2\sqrt{2Anp_{a}\log(np_{a}+\lambda)}+A\log(np_{a}+\lambda)}{3(np_{a}+\lambda)}}\Big{)}^{\alpha}$
$\displaystyle\leq\Big{(}1+2\frac{3\sqrt{2Anp_{a}\log(np_{a}+\lambda)}+A\log(np_{a}+\lambda)}{3(np_{a}+\lambda)}\Big{)}^{\alpha}$
$\displaystyle\leq
1+2\alpha\frac{3\sqrt{2Anp_{a}\log(np_{a}+\lambda)}+A\log(np_{a}+\lambda)}{3(np_{a}+\lambda)}$

To conclude, we take take $A\equiv(\alpha+1)$ and this ensure that for $n$
sufficiently large, we obtain:

$\displaystyle(\mathbb{E}[X^{a}_{n}]+\lambda)^{\alpha}\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n}+\lambda)^{\alpha}}\Big{]}$
$\displaystyle\leq
1+2\alpha\frac{3\sqrt{2(\alpha+1)np_{a}\log(np_{a}+\lambda)}+(\alpha+1)\log(np_{a}+\lambda)}{3(np_{a}+\lambda)}$
$\displaystyle\quad\quad\quad+\frac{1}{\lambda^{\alpha}(np_{a}+\lambda)}.$

The leading order of this quantity is $\sqrt{\frac{log(n)}{n}}=o(n^{-1/4})$
and therefore, we conclude that there exists a constant $C_{2}^{a}$, depending
on $\lambda,\alpha$ and $p_{a}$ such that for all $n\geq 1$:

$\displaystyle(\mathbb{E}[X^{a}_{n}]+\lambda)^{\alpha}\mathbb{E}\Big{[}\frac{1}{(X^{a}_{n}+\lambda)^{\alpha}}\Big{]}\leq
1+\frac{C_{2}^{a}}{(np_{a})^{1/4}},$

where $C_{2}^{a}$ is artificially increased to remove the two lower bounds
conditions on $n$. ∎

###  B.9 Proof of Prop. 3.7

See 3.7

Thus, we find that the power of a single monitoring is sufficient to ensure
almost the same gain as adaptivity i.e. constant monitoring. The linear
dependency in $T_{0}$ (due to the linear increase of variance in Binomial
models) is also surprising. In non-asymptotic regime, it is still true but for
$\beta$ verifying $0<\beta_{-}\leq\beta\leq\beta_{+}<1$ for given
$(\beta_{-},\beta_{+})$. We also observe a more general concave property of
the single monitoring gain seen as a function of $T_{0}$, with limits equals
to $0$ on the borders on the interval. We conjecture that this concavity is
likely to turn in a submodular dependency for several monitoring shots.

###### Proof.

Single Monitoring: We first prove a slightly extended version of ($\star\star$
‣ 3.7) by considering a monitoring at time $T_{0}$ and we recover the results
of Prop. 3.7 by setting $T_{0}\equiv\beta T$, for a given $\beta\in]0,1[$. For
the first step of the proof, we consider the continuous approximation of
$\displaystyle\max_{\pi\in\Pi_{\text{single}}(T_{0})}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]$
given by the optimization problem over continuous variables:

$\displaystyle\max_{\tau_{a}(T_{0}),\tau_{a}(T)}$
$\displaystyle\mathbb{E}\Big{[}\sum_{a\in[d]}\frac{1}{p_{a}}[\psi_{\alpha}(N_{a}(T))-\psi_{\alpha}(N_{a}(T_{0}))]+\sum_{a\in[d]}\frac{1}{p_{a}}[\psi_{\alpha}(N_{a}(T_{0}))-\psi_{\alpha}(\lambda)]\Big{]}$
s.t. $\displaystyle\sum_{a\in[d]}\tau_{a}(T_{0})=T_{0},$
($\mathcal{S}\mathcal{M}$) $\displaystyle\sum_{a\in[d]}\tau_{a}(T)=T,$
$\displaystyle\forall a\in[d],\quad\tau_{a}(T)\geq\tau_{a}(T_{0}).$

In $\mathcal{S}\mathcal{M}$, the single monitoring $\max$ player initially
commits to an allocation of the $T_{0}$ first rounds through the policy
$(\tau_{a}(T_{0}))_{a\in[d]}$, with resulting gain expressed as the second
term of the maximization problem. The player then observes the realization
$N_{a}(T_{0})\sim\mathcal{B}(\tau_{a}(T_{0}),p_{a})$ and allocates the rest of
the $T-T_{0}$ budget through the allocation $(\tau_{a}(T))_{a\in[d]}$, with
resulting gain expressed as the first term of the maximization problem. .
Therefore, the single monitoring gain assesses the value of observing the
deviation of $N_{a}(T_{0})$ from its expectation $\tau_{a}(T_{0})p_{a}$. In an
analogous way, we then introduce the continuous approximation of
$\displaystyle\max_{\pi\in\Pi_{\text{off}}}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]$
given by:

$\displaystyle\max_{\tau_{a}(T)}$
$\displaystyle\quad\mathbb{E}\Big{[}\sum_{a\in[d]}\frac{1}{p_{a}}[\psi_{\alpha}(N_{a}(T))-\psi_{\alpha}(\lambda)]\Big{]}$
s.t. $\displaystyle\sum_{a\in[d]}\tau_{a}(T)=T.$
($\mathcal{O}\mathcal{F}\mathcal{F}$)

In $\mathcal{O}\mathcal{F}\mathcal{F}$, $(N_{a}(T_{0}))_{a\in[d]}$ is not
observed and thus can not be leveraged by the offline player to adapt the
second part of the allocation. On what follows, we use
$\mathbf{E}[\mathbf{N}]$ and $\mathbf{V}[\mathbf{N}]$ to denote respectively
the mean and variance of $\mathbf{N}$, the empirical discrete distribution
over $(N_{a}(T_{0}))_{a\in[d]}$ with associated weights
$(1/p_{a}d_{\mathit{eff}})_{a\in[d]}$. Given a realization of
$(N_{a}(T_{0}))_{a\in[d]}$, we use Lemma 3.5 to deduce the optimal choice of
$(\tau_{a}(T))_{a\in[d]}$ in $\mathcal{S}\mathcal{M}$ and resulting expected
conditional gain:

$\displaystyle\sum_{a\in[d]}\underbrace{\frac{1}{p_{a}}\Big{[}\psi_{\alpha}(\frac{T-T_{0}}{d_{\mathit{eff}}}+\mathbf{E}[\mathbf{N}])-\psi_{\alpha}(N_{a}(T_{0}))\Big{]}}_{\textit{Gain
between $T_{0}$ and $T$ for arm
$a$}}+\sum_{a\in[d]}\underbrace{\frac{1}{p_{a}}\Big{[}\psi_{\alpha}(N_{a}(T_{0}))-\psi_{\alpha}(\lambda)\Big{]}}_{\textit{Gain
between $0$ and $T_{0}$ for arm $a$}},$

where the formula is valid under the assumption $\forall a\in[d]$,
$T-T_{0}\geq d_{\mathit{eff}}(N_{a}(T_{0})-\mathbf{E}[\mathbf{N}])$. Such
assumption encompass the fact that the remaining budget $T-T_{0}$ should be
sufficient to correct the deviation observed. Logically, we know that on
expectation $\mathbb{E}[N_{a}(T_{0})-\mathbf{E}[\mathbf{N}]]=0$, that is no
systematic deviation is expected. For for all realization of randomness, the
following deterministic crude upper bound hold:

$\displaystyle d_{\mathit{eff}}(N_{a}(T_{0})-\mathbf{E}[\mathbf{N}])\leq
d_{\mathit{eff}}(1-\frac{1}{d_{\mathit{eff}}p_{a}})\frac{T_{0}}{p_{a}d_{\mathit{eff}}}$

this in turn imposes:

$\displaystyle\frac{T_{0}}{T}\leq\min_{a\in[d]}\frac{1}{1+\frac{d_{\mathit{eff}}-\frac{1}{p_{a}}}{p_{a}d_{\mathit{eff}}}}.$

For instance, in the uniform censorship model, this yields condition
$\frac{T_{0}}{T}\leq\frac{dp}{dp+d-1}$. Nevertheless, this is overly
conservative and we can get considerably stronger results by considering high-
probability concentration results on $N_{a}(T_{0})$. Indeed, thanks to
Chernoff Bounds for Binomial distribution, we have for $\delta\equiv
T_{0}^{-1/4}$, that with probability at least
$1-2d\exp\\{-\delta^{2}T_{0}/3d_{\mathit{eff}}\\}$, for all $a$,
$(1-\delta)T_{0}/d_{\mathit{eff}}\leq
N_{a}(T_{0})\leq(1+\delta)T_{0}/d_{\mathit{eff}}$. In particular, this yields
$(1-\delta)T_{0}/d_{\mathit{eff}}\leq\mathbf{E}[\mathbf{N}]\leq(1+\delta)T_{0}/d_{\mathit{eff}}$.
Under this event, we have
$d_{\mathit{eff}}(N_{a}(T_{0})-\mathbf{E}[\mathbf{N}])\leq 2\delta T_{0}$,
which imposes $T\geq(1+2\delta)T_{0}=T_{0}+2T_{0}^{3/4}$. In particular, for
$T_{0}\equiv\beta T$, where $\beta\in]0,1[$, such condition will always be
verified for $T$ large enough.

On the other hand, still using Lemma 3.5, we write the conditional expected
gain of the offline policy on this same realization of $(N_{a}(T))_{a\in[d]}$
for $\mathcal{O}\mathcal{F}\mathcal{F}$ as:

$\displaystyle\sum_{a\in[d]}\underbrace{\frac{1}{p_{a}}\Big{[}\psi_{\alpha}(\frac{T-T_{0}}{d_{\mathit{eff}}}+N_{a}(T_{0}))-\psi_{\alpha}(N_{a}(T_{0}))\Big{]}}_{\textit{Gain
between $T_{0}$ and $T$ for arm
$a$}}+\sum_{a\in[d]}\underbrace{\frac{1}{p_{a}}\Big{[}\psi_{\alpha}(N_{a}(T_{0}))-\psi_{\alpha}(\lambda)\Big{]}}_{\textit{Gain
between $0$ and $T_{0}$ for arm $a$}}.$

where $\psi_{\alpha}(N_{a}(T_{0}))$ is artificially introduced. The difference
between the two comes from the possibility for the monitoring policy to
homogenize the realized $N_{a}(T_{0})$ into a uniform
$\mathbf{E}[\mathbf{N}]$. The random difference
$\mathcal{G}_{\mathit{single}}(T_{0})$, seen as a function of the realization
of $(N_{a}(T_{0}))$ is then equal to:

$\displaystyle\mathcal{G}_{\mathit{single}}(T_{0})$
$\displaystyle\triangleq\sum_{a\in[d]}\frac{1}{p_{a}}[\psi_{\alpha}(\frac{T-T_{0}}{d_{\mathit{eff}}}+\mathbf{E}[\mathbf{N}])-\psi_{\alpha}(\frac{T-T_{0}}{d_{\mathit{eff}}}+N_{a}(T_{0}))]$
$\displaystyle=d_{\mathit{eff}}\Big{[}\bar{\psi}_{\alpha}(\mathbf{E}[\mathbf{N}])-\mathbf{E}[\bar{\psi}_{\alpha}(\mathbf{N})]\Big{]},$

which is exactly the Jensen’s gap of the concave function
$\bar{\psi}_{\alpha}:x\mapsto\psi_{a}(\frac{T-T_{0}}{d_{\mathit{eff}}}+x)$.
The main insight is that this gap is then asymptotically equivalent to:

$\displaystyle\bar{\psi}_{\alpha}(\mathbf{E}[\mathbf{N}])-\mathbf{E}[\bar{\psi}_{\alpha}(\mathbf{N})]\sim-\frac{\bar{\psi}^{(2)}_{\alpha}(\mathbf{E}[\mathbf{N}])}{2}\mathbf{V}[\mathbf{N}],$

where the RHS is positive, given that
$\bar{\psi}^{(2)}_{\alpha}(\mathbf{E}[\mathbf{N}])$ is negative. To show this,
we use the original proof of Jensen’s inequality and introduce the interval
$I\triangleq[\min_{a}N_{a}(T_{0}),\max_{a}N_{a}(T_{0})]$ to leverage the mean
value theorem. This then yields:

$\displaystyle\frac{\min_{y\in
I}-\bar{\psi}^{(2)}_{\alpha}(y)}{-\bar{\psi}^{(2)}_{\alpha}(\mathbf{E}[\mathbf{N}])}\leq
2\frac{\bar{\psi}_{\alpha}(\mathbf{E}[\mathbf{N}])-\mathbf{E}[\bar{\psi}_{\alpha}(\mathbf{N})]}{-\bar{\psi}^{(2)}_{\alpha}(\mathbf{E}[\mathbf{N}])\mathbf{V}[\mathbf{N}]}\leq\frac{\max_{y\in
I}-\bar{\psi}^{(2)}_{\alpha}(y)}{-\bar{\psi}^{(2)}_{\alpha}(\mathbf{E}[\mathbf{N}])}$

Whenever $T_{0}$ is a constant independent of $T$, for $T\rightarrow+\infty$
by explicitly writing the definition of the upper and lower bounds, we have
almost surely:

$\displaystyle\frac{\min_{y\in
I}-\bar{\psi}^{(2)}_{\alpha}(y)}{-\bar{\psi}^{(2)}_{\alpha}(\mathbf{E}[\mathbf{N}])}\rightarrow
1\quad\text{and}\quad\frac{\max_{y\in
I}-\bar{\psi}^{(2)}_{\alpha}(y)}{-\bar{\psi}^{(2)}_{\alpha}(\mathbf{E}[\mathbf{N}])}\rightarrow
1$

Difficulties arises when $T_{0}$ is a function of $T$, as in the statement of
the result where $T_{0}\equiv\beta T$. By considering the same concentration
event as the one introduced above, we have:

$\displaystyle\frac{\min_{y\in
I}-\psi^{(2)}_{\alpha}(y)}{-\bar{\psi}^{(2)}_{\alpha}(\mathbf{E}[\mathbf{N}])}$
$\displaystyle=\min_{y\in
I}\Big{(}\frac{T-T_{0}+d_{\mathit{eff}}\mathbf{E}[\mathbf{N}]}{T-T_{0}+d_{\mathit{eff}}y}\Big{)}^{{}^{1+\alpha}}\geq\Big{(}\frac{T-T_{0}+(1-\delta)T_{0}}{T-T_{0}+(1+\delta)T_{0}}\Big{)}^{{}^{1+\alpha}}$
$\displaystyle\leq\Big{(}\frac{T-\delta T_{0}}{T+\delta
T_{0}}\Big{)}^{{}^{1+\alpha}}=\Big{(}\frac{T-T_{0}^{3/4}}{T+T_{0}^{3/4}}\Big{)}^{{}^{1+\alpha}}\rightarrow
1.$

and similarly:

$\displaystyle\frac{\max_{y\in
I}-\psi^{(2)}_{\alpha}(y)}{-\bar{\psi}^{(2)}_{\alpha}(\mathbf{E}[\mathbf{N}])}$
$\displaystyle=\max_{y\in
I}\Big{(}\frac{T-T_{0}+d_{\mathit{eff}}\mathbf{E}[\mathbf{N}]}{T-T_{0}+d_{\mathit{eff}}y}\Big{)}^{{}^{1+\alpha}}\leq\Big{(}\frac{T-T_{0}+(1+\delta)T_{0}}{T-T_{0}+(1-\delta)T_{0}}\Big{)}^{{}^{1+\alpha}}$
$\displaystyle\leq\Big{(}\frac{T+\delta T_{0}}{T-\delta
T_{0}}\Big{)}^{{}^{1+\alpha}}=\Big{(}\frac{T+T_{0}^{3/4}}{T-T_{0}^{3/4}}\Big{)}^{{}^{1+\alpha}}\rightarrow
1.$

Thus, thanks to the exponential concentration, we conclude that:

$\displaystyle\mathbb{E}[\mathcal{G}_{\mathit{single}}(T_{0})]=\frac{d_{\mathit{eff}}}{2}\mathbb{E}[\bar{\psi}_{\alpha}(\mathbf{E}[\mathbf{N}])-\mathbf{E}[\bar{\psi}_{\alpha}(\mathbf{N})]]\sim-\frac{d_{\mathit{eff}}}{2}\mathbb{E}[\bar{\psi}^{(2)}_{\alpha}(\mathbf{E}[\mathbf{N}])\mathbf{V}[\mathbf{N}]].$

Next, we affirm that:

$\displaystyle\mathbb{E}[\bar{\psi}^{(2)}_{\alpha}(\mathbf{E}[\mathbf{N}])\mathbf{V}[\mathbf{N}]]$
$\displaystyle\overset{a)}{\sim}\mathbb{E}\Big{[}\bar{\psi}^{(2)}_{\alpha}(\mathbf{E}[\mathbf{N}])\Big{]}\mathbb{E}\Big{[}\mathbf{V}[\mathbf{N}]\Big{]}\overset{b)}{\sim}\bar{\psi}^{(2)}_{\alpha}(\mathbb{E}[\mathbf{E}[\mathbf{N}]])\mathbb{E}\Big{[}\mathbf{V}[\mathbf{N}]\Big{]},$

where $a)$ leverages the previous bounds and where we use for $b)$ similar
concentration results on inverse of Binomial as done for the proof of Lemma
3.6.. We then use the fact that
$\mathbb{E}[\mathbf{E}[\mathbf{N}]]=T_{0}/d_{\mathit{eff}}$ to conclude:

$\displaystyle\mathbb{E}[\mathcal{G}_{\mathit{single}}(T_{0})]\sim-\frac{d_{\mathit{eff}}}{2}\psi^{(2)}_{\alpha}(\frac{T}{d_{\mathit{eff}}})\mathbb{E}\Big{[}\mathbf{V}[\mathbf{N}]\Big{]}.$
($\mathcal{V}$)

We consider this result to be one of the main insight for adaptivity, as it
involves that at first order, the gain grows linearly in the expected value of
the empirical variance of the arm allocation process. In opposition to the
single monitoring policy, the adaptive policy continuously exploits such
variance. Yet, in doing so, it creates a second order induced variance but we
then show that this phenomena is negligible at first order. To reach a result
with explicit dependency on the censorship probability $(p_{a})_{a\in[d]}$, we
note that:

$\displaystyle\mathbb{E}[\mathbf{V}[\mathbf{N}]]=\frac{T_{0}}{d_{\mathit{eff}}^{3}}\sum_{a\in[d]}\frac{1}{p_{a}}\Big{[}\sum_{b\neq
a}\frac{1-p_{b}}{p_{b}}\Big{]},$

and therefore:

$\displaystyle\mathbb{E}\Big{[}\mathcal{G}_{\mathit{single}}(T_{0})\Big{]}$
$\displaystyle\sim\frac{\alpha}{2d_{\mathit{eff}}^{2}}(\frac{d_{\mathit{eff}}}{T})^{1+\alpha}T_{0}\sum_{a\in[d]}\frac{1}{p_{a}}\Big{[}\sum_{b\neq
a}\frac{1-p_{b}}{p_{b}}\Big{]}=\gamma_{\alpha}(\mathbf{p})\frac{T_{0}}{T^{1+\alpha}}.$

In particular, for $T_{0}=\beta T$, this yields
$\mathbb{E}\Big{[}\mathcal{G}_{\mathit{single}}(\beta
T)\Big{]}=\gamma_{\alpha}(\mathbf{p})\frac{\beta}{T^{\alpha}}+o(\frac{1}{T^{\alpha}})$.

The second step closely mirrors the proof of Lemma 3.6 and consists in
justifying the use of the continuous approximation for the two optimization
problems ($\mathcal{O}\mathcal{F}\mathcal{F}$) and ($\mathcal{S}\mathcal{M}$).
As in Lemma 3.6, we show that the difference between the continuous and
discrete optimization results at most in a second order gain of
$o(\frac{1}{T^{\alpha}})$, even when maximized as a decoupled quantity. By
combining those two results, we finally deduce as announced:

$\displaystyle\max_{\pi\in\Pi_{\text{single}}(\beta
T)}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]-\max_{\pi\in\Pi_{\text{off}}}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]\sim\mathbb{E}\Big{[}\mathcal{G}_{\mathit{single}}(\beta
T)\Big{]}=\gamma_{\alpha}(\mathbf{p})\frac{\beta}{T^{\alpha}}+o(\frac{1}{T^{\alpha}})$

Complete Adaptivity

We next tackle the proof of ($\star$ ‣ 3.7), where the main idea is to show
that a formula analogous to ($\mathcal{V}$) holds for the variance of a suited
random process. First, using the same proof technique as in Sec. 4 of [19]
thanks to the decaying property of the reward in function of the number of
realization, we show that the optimal adaptive policy is the greedy policy,
that is the policy that picks at time $t$ the action:

$\displaystyle
a_{t}\triangleq\operatorname{argmax}_{a\in\mathcal{A}_{t}}(N_{a}(t-1)+\lambda)^{-\alpha},$

with arbitrary but consistent tie-breaking. In particular, this ensures that
for all actions $a,b$ and time $t$, we have $|N_{a}(t)-N_{b}(t)|\leq 1$. We
then introduce the offline and adaptive allocations:

$\displaystyle\tau_{a}^{off}(T)$
$\displaystyle\triangleq\frac{T}{p_{a}d_{eff}}\quad\text{and}\quad\tau_{a}^{on}(T)\triangleq\sum_{i=1}^{N_{a}(T)}\frac{1}{p_{a}}+\xi^{a}_{i}=\frac{N_{a}(T)}{p_{a}}+S^{a}(N_{a}(T))$

where $\frac{1}{p_{a}}+\xi^{a}_{i}$ is the total random number of allocation
it takes for action $a$ to be realized in the $i^{th}$ selection,
$\xi^{a}_{i}$ being equal the centered deviation with respect to the expected
value $\frac{1}{p_{a}}$. Of key importance in our proof is $S^{a}(N_{a}(T))$,
the cumulative deviation defined as $\sum_{i=1}^{N_{a}(T)}\xi^{a}_{i}$. Note
that it is well approximated in large $T$ regime as a random sum of $N_{a}(T)$
i.i.d. geometric centered variable of parameter $p_{a}$. Given this and the
total budget constraint, we have the simple relation
$\tau_{a}^{on}(T)=\tau_{a}^{off}(T)+\frac{1}{d_{eff}}\sum_{b}[\frac{S^{a}(N_{a}(T))}{p_{b}}-\frac{S^{b}(N_{b}(T))}{p_{a}}]$.
A relevant quantity to introduce is the random allocation difference
$\Delta\tau_{a,b}$ between actions $a$ and $b$ defined by:

$\displaystyle\Delta\tau_{a,b}\triangleq\frac{1}{d_{eff}}(\frac{S^{a}(N_{a}(T))}{p_{b}}-\frac{S^{b}(N_{b}(T))}{p_{b}})$

Using this notation, we simply have
$\tau_{a}^{on}=\tau_{a}^{off}+\sum_{b}\Delta\tau_{a,b}$. We then introduce the
random sets
$I^{+}\triangleq\\{a:\tau_{a}^{on}\geq\tau_{a}^{off}\\}=\\{a:\sum_{b}\Delta\tau_{a,b}\geq
0\\}$ and
$I^{-}\triangleq\\{a:\tau_{a}^{on}<\tau_{a}^{off}\\}=\\{a:\sum_{b}\Delta\tau_{a,b}<0\\}$.
On the one hand, $I^{+}$ represents the set of actions that are more sampled
by the adaptive policy than by the offline policy i.e. that leads to a gain
thanks to the greedy property. One the other hand, $I^{-}$ is the set of
actions under-selected by the adaptive policy, leading to a loss although
inferior in absolute value to the resulting gain of $I^{+}$. As for the proof
of the single monitoring case, we condition on the realization $(N_{a}(T))$
and use a continuous approximation given this conditioning to study the
difference of gain. Thus, we have the action gain for $a\in I^{+}$,:

$\displaystyle g_{a}$
$\displaystyle\triangleq\frac{1}{p_{a}}[\psi_{\alpha}(N_{a}(T))-\psi_{\alpha}(N_{a}(T)-p_{a}\sum_{b}\Delta\tau_{a,b})]$
$\displaystyle\approx\frac{1}{p_{a}}\Big{[}p_{a}\Big{(}\sum_{b}\Delta\tau_{a,b}\Big{)}\psi_{\alpha}^{(1)}(N_{a}(T))-\frac{(p_{a}\sum_{b}\Delta\tau_{a,b})^{2}}{2}\psi_{\alpha}^{(2)}(N_{a}(T))\Big{]}.$

On the other hand, for $a\in I^{-}$, we have the action loss still under the
continuous approximation:

$\displaystyle l_{a}$
$\displaystyle\triangleq\frac{1}{p_{a}}[\psi_{\alpha}(N_{a}(T)+p_{a}\sum_{b}\Delta\tau_{a,b})-\psi_{\alpha}(N_{a}(T))]$
$\displaystyle\approx\frac{1}{p_{a}}\Big{[}p_{a}\Big{(}\sum_{b}\Delta\tau_{a,b}\Big{)}\psi_{\alpha}^{(1)}(N_{a}(T))+\frac{(p_{a}\sum_{b}\Delta\tau_{a,b})^{2}}{2}\psi_{\alpha}^{(2)}(N_{a}(T))\Big{]}.$

By introducing $\mathcal{G}_{\text{adapt}}\triangleq\sum_{a\in
I^{+}}g_{a}-\sum_{a\in I^{-}}l_{a}$, the adaptive equivalent of
$\mathcal{G}_{\text{single}}$ and combining previous two results, we deduce:

$\displaystyle\mathcal{G}_{\text{adapt}}$ $\displaystyle=\sum_{a\in
I^{+}}\frac{1}{p_{a}}\Big{[}p_{a}\Big{(}\sum_{b}\Delta\tau_{a,b}\Big{)}\psi_{\alpha}^{(1)}(N_{a}(T))-\frac{(p_{a}\sum_{b}\Delta\tau_{a,b})^{2}}{2}\psi_{\alpha}^{(2)}(N_{a}(T))\Big{]}$
$\displaystyle\quad\quad-\sum_{a\in
I^{-}}\frac{1}{p_{a}}\Big{[}p_{a}\Big{(}\sum_{b}\Delta\tau_{a,b}\Big{)}\psi_{\alpha}^{(1)}(N_{a}(T))+\frac{(p_{a}\sum_{b}\Delta\tau_{a,b})^{2}}{2}\psi_{\alpha}^{(2)}(N_{a}(T))\Big{]}$
$\displaystyle=\sum_{a\in
I^{+}}\Big{(}\sum_{b}\Delta\tau_{a,b}\Big{)}\psi_{\alpha}^{(1)}(N_{a}(T))-\sum_{a\in
I^{-}}\Big{(}\sum_{b}\Delta\tau_{a,b}\Big{)}\psi_{\alpha}^{(1)}(N_{a}(T))$
$\displaystyle\quad\quad-\frac{1}{2}\sum_{a\in[d]}(p_{a}\sum_{b}\Delta\tau_{a,b})^{2}\psi_{\alpha}^{(2)}(N_{a}(T))$

We then leverage the Taylor expansion
$\psi_{\alpha}^{(1)}(N_{a}(T))=\psi_{\alpha}^{(1)}(\bar{N}(T))+\psi_{\alpha}^{(2)}(\bar{N}(T))(\bar{N}(T)-N_{a}(T))$,
where $\bar{N}(T)\triangleq\sum_{a\in[d]}N_{a}(t)/d$. We know that the second
term is asymptotically negligible given that $\alpha>0$ and that the
difference between $\bar{N}(T)$ and $N_{a}(T)$ is constant with exponential
probability, thanks to the greedy policy property. We combine this result with
the fact that by definition $\sum_{a\in
I^{+}}\sum_{b}\Delta\tau_{a,b}-\sum_{a\in I^{-}}\sum_{b}\Delta\tau_{a,b}=0$ to
deduce that at first order:

$\displaystyle\mathcal{G}_{\text{adapt}}=-\frac{1}{2}\psi_{\alpha}^{(2)}(\bar{N}(T))\sum_{a\in[d]}(p_{a}\sum_{b}\Delta\tau_{a,b})^{2}$
($\mathcal{L}$)

We see formula ($\mathcal{L}$) as the adaptive analogous of ($\mathcal{V}$).
Indeed, it involves the product of the second derivative
$\frac{1}{2}\psi_{\alpha}^{(2)}(\bar{N}(T))$, evaluated on a quantity
concentrating at $T/d_{\mathit{eff}}$ with a variance term associated to the
adaptive action allocation process. We remark that for any $a\in[d]$:

$\displaystyle\mathbb{E}\Big{[}(\sum_{b}\Delta\tau_{a,b})^{2}\Big{]}$
$\displaystyle=\frac{1}{d_{\mathit{eff}}^{2}}\mathbb{E}\Big{[}([\sum_{b\neq
a}\frac{1}{p_{b}}]S^{a}(N_{a}(T))-\frac{1}{p_{a}}\sum_{b\neq
a}S^{b}(N_{b}(T)))^{2}\Big{]}$
$\displaystyle=\frac{1}{d_{\mathit{eff}}^{2}}\left[(d_{\mathit{eff}}-\frac{1}{p_{a}})^{2}\mathbb{V}[S^{a}(N_{a}(T))]+\sum_{b\neq
a}\frac{1}{p_{a}^{2}}\mathbb{V}[S^{b}(N_{b}(T))]\right]$

and therefore, by summing:

$\displaystyle\sum_{a\in[d]}p_{a}\mathbb{E}\Big{[}(\sum_{b}\Delta\tau_{a,b})^{2}\Big{]}$
$\displaystyle=\frac{1}{d_{\mathit{eff}^{2}}}\sum_{a\in[d]}p_{a}\Big{[}(\sum_{b\neq
a}\frac{1}{p_{b}})^{2}\mathbb{V}[S^{a}(N_{a}(T))]+\sum_{b\neq
a}\frac{1}{p_{a}^{2}}\mathbb{V}[S^{b}(N_{b}(T))]\Big{]}$
$\displaystyle=\frac{1}{d_{\mathit{eff}^{2}}}\sum_{a\in[d]}\Big{[}p_{a}(d_{\mathit{eff}}-\frac{1}{p_{a}})^{2}+d_{\mathit{eff}}-\frac{1}{p_{a}}\Big{]}\mathbb{V}[S^{a}(N_{a}(T))]$
$\displaystyle=\sum_{a\in[d]}p_{a}\frac{d_{\mathit{eff}}-\frac{1}{p_{a}}}{d_{\mathit{eff}}}\mathbb{V}[S^{a}(N_{a}(T))].$

To obtain the leading order of $\mathbb{V}[S^{a}(N_{a}(T))]$, we use Wald’s
second equation and the fact that $S^{a}(N_{a}(T))$ is approximated by a sum
of geometric random variable of parameter $p_{a}$, modulo a asymptotically
negligible summing constraint due to the fixed total budget $T$. This yields
$\mathbb{V}[S^{a}(N_{a}(T))]\sim\frac{1-p_{a}}{p_{a}^{2}}\mathbb{E}[N_{a}(T)]\sim\frac{1-p_{a}}{p_{a}^{2}}\mathbb{E}[\bar{N}(T)]$,
where the last results leverages again the fact that the difference between
the two quantities is constant with exponential probability. We conclude with
further algebraic calculation that:

$\displaystyle\mathbb{E}[\mathcal{G}_{\text{adapt}}]$
$\displaystyle\sim-\mathbb{E}[\frac{\psi_{\alpha}^{(2)}}{2}(\bar{N}(T))]\sum_{a\in[d]}p_{a}\frac{d_{\mathit{eff}}-\frac{1}{p_{a}}}{d_{\mathit{eff}}}\frac{1-p_{a}}{p_{a}^{2}}\mathbb{E}[\bar{N}(T)]$
$\displaystyle\sim\frac{\alpha}{2}(\frac{d_{\mathit{eff}}}{T})^{1+\alpha}\sum_{a\in[d]}\frac{1}{p_{a}}\Big{[}\sum_{b\neq
a}\frac{1-p_{b}}{p_{b}}\Big{]}\frac{T}{d_{\mathit{eff}}^{2}}$
$\displaystyle\sim\gamma_{\alpha}(\mathbf{p})\frac{1}{T^{\alpha}}.$

By justifying again that the continuous gain approximation leads to terms of
order $o(\frac{1}{T^{\alpha}})$, as done in the proof of Lemma 3.6, we
conclude that:

$\displaystyle\max_{\pi\in\Pi_{\text{adapt}}}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]-\max_{\pi\in\Pi_{\text{off}}}\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]=\gamma_{\alpha}(\mathbf{p})\frac{1}{T^{\alpha}}+o(\frac{1}{T^{\alpha}}).$

∎

##  Appendix C Proof of Sec. 4 \- Contextual Bandits

In this section, we prove Thm. 4.1 of Sec.4, extending the results of MAB to
LCB. To do so, we prove Lemmas 4.2, C.1 and Prop. 4.3. Note that the proof of
Thm. 4.6 is differed to next section. We conclude the section by discussing
the extension of our analysis to Generalized Linear Contextual Bandits.

###  C.1 Proof of Lemma 4.2

See 4.2

###### Proof.

We have under the event $\neg\mathcal{H}_{\text{UCB}}^{II}(\delta)$ introduced
in Lemma C.1 and thanks to Holder inequality:

$\displaystyle\Delta_{t}(a)\triangleq\max_{\tilde{a}\in\mathcal{A}_{t}}\langle\theta^{\star},\tilde{a}\rangle-\langle\theta^{\star},a_{t}\rangle\leq
2\beta_{\delta}(t-1)\|a_{t}\|_{(\mathbb{W}^{C}(t-1))^{-1}}.$

Therefore, the conditional regret is upper-bounded by:

$\displaystyle
R(T|\neg\mathcal{H}_{\text{UCB}}^{II}(\delta))\leq\beta_{\delta}(T)\sum_{t=1}^{T}\|a_{t}\|_{(\mathbb{W}^{C}(t-1))^{-1}}=\beta_{\delta}(T)\tilde{\mathbb{V}}_{\frac{1}{2}}(T,\pi),$

where we introduced
$\tilde{\mathbb{V}}_{\frac{1}{2}}(T,\pi)\triangleq\sum_{t=1}^{T}\|a_{t}\|_{\mathbb{W}^{C}(t-1)^{-1}}$.
Cauchy Schwartz inequality then allows to make the junction
$\tilde{\mathbb{V}}_{\frac{1}{2}}(T,\pi)\leq\sqrt{T}\sqrt{\mathbb{V}_{1}(T,\pi)}$.
We then introduce $\tilde{\beta}_{\delta}(T)$ a deterministic upper bound on
$\beta_{\delta}(T)$:

$\displaystyle\beta_{\delta}(T)$
$\displaystyle=\sqrt{\sigma^{2}\log\left(\frac{\det(\mathbb{W}^{C}_{T})}{\det(\lambda\mathbb{I}_{d})}\right)+2\sigma^{2}\log(\frac{1}{\delta})}+\sqrt{\lambda}\|\theta^{\star}\|_{2}$
$\displaystyle\leq\underbrace{\sqrt{\sigma^{2}d\log(1+\frac{T}{d\lambda})+2\sigma^{2}\log(\frac{1}{\delta})}+\sqrt{\lambda}\|\theta^{\star}\|_{2}}_{\triangleq\tilde{\beta}_{\delta}(T)}$
$\displaystyle=\Theta(\sqrt{d\log(T)}).$

Using the concavity of square root and Jensen’s inequality, we have
$\mathbb{E}[\sqrt{\mathbb{V}_{1}(T,\pi)}]\leq\sqrt{\mathbb{E}[\mathbb{V}_{1}(T,\pi)]}$.
Finally, thanks to Lemma C.1, we conclude that:

$\displaystyle\mathbb{E}[R(T,\pi_{\text{UCB}})]\leq
2\tilde{\beta_{\delta}}(T)\sqrt{T\mathbb{E}[\mathbb{V}_{1}(T,\pi_{\textit{UCB}})]}+\delta
T\Delta_{max}.$

∎

###  C.2 Statement and Proof of Lemma C.1

Analogous to Lemma B.1 for the MAB case, one key step in the proof is
introduction of the failure of optimism event. Nevertheless, note the
difference with the choice of norm.

######  Lemma C.1.

For any $\delta\in]0,1]$, uniform regularization $\lambda>0$ and censored
action generating process $(\mathbb{W}^{C}_{t})_{t\leq T}$, let’s introduce
the event:

$\displaystyle\mathcal{H}_{\text{UCB}}^{II}(\delta)\triangleq\Big{\\{}\exists
t\geq
0,\|\hat{\theta}^{\lambda}_{t}-\theta^{\star}\|_{\mathbb{W}^{C}_{t}}>\underbrace{\sqrt{\sigma^{2}\log\left(\frac{\det(\mathbb{W}^{C}_{t})}{\det(\lambda\mathbb{I}_{d})}\right)+2\sigma^{2}\log(\frac{1}{\delta})}+\sqrt{\lambda}\|\theta^{\star}\|_{2}}_{\triangleq\beta_{\delta}(t)}\Big{\\}}.$

We then have $\mathbb{P}(\mathcal{H}_{\text{UCB}}^{II}(\delta))\leq\delta$.

###### Proof.

The proof closely mirrors the self-normalized bound for vector-valued
martingales of Thm.$1$ from [1]. The main subtlety is to apply the results to
the censored measurable vectors $(x_{a_{t}}a_{t})$ instead of classically
$(a_{t})$. This yields that with probability $1-\delta$, for all $t\geq 0$:

$\displaystyle\|\sum_{n=1}^{t}\epsilon_{n}x_{a_{n}}a_{n}\|^{2}_{\mathbb{W}_{t}^{C}}\leq\sigma^{2}\log\frac{\det(\mathbb{W}_{t}^{C})}{\det(\lambda\mathbb{I}_{d})}+2\log(\frac{1}{\delta}).$

Thus, still on this event, for any $t\geq 0$ and action $a\in\mathbb{R}^{d}$,
we have by definition of $\hat{\theta}^{\lambda}_{t}$ (Sec.A.1):

$\displaystyle\langle a,\hat{\theta}^{\lambda}_{t}\rangle-\langle
a,\theta^{\star}\rangle=\langle
a,(\mathbb{W}_{t}^{C})^{-1}\sum_{n=1}^{t}\epsilon_{n}x_{a_{n}}a_{n}\rangle-\lambda\langle
a,(\mathbb{W}_{t}^{C})^{-1}\theta^{\star}\rangle,$

and therefore, thanks to Cauchy-Schwartz inequality:

$\displaystyle|\langle a,\hat{\theta}^{\lambda}_{t}\rangle-\langle
a,\theta^{\star}\rangle|\leq\|a\|_{(\mathbb{W}_{t}^{C})^{-1}}\Big{(}\|\sum_{n=1}^{t}\epsilon_{t}x_{a_{t}}a_{t}\|_{\mathbb{W}_{t}^{C}}+\lambda^{1/2}\|\theta^{\star}\|_{2}\Big{)}$

Using previous result, for all $a\in\mathbb{B}_{d},t\geq 0$, with probability
$1-\delta$, we have:

$\displaystyle|\langle a,\hat{\theta}^{\lambda}_{t}\rangle-\langle
a,\theta^{\star}\rangle|\leq\sigma\sqrt{\log\Big{(}\frac{\det(\mathbb{W}_{t}^{C})}{\det(\lambda\mathbb{I}_{d})}\Big{)}+2\log(\frac{1}{\delta})}+\lambda^{1/2}\|\theta^{\star}\|_{2}$

To conclude, we classically plug-in the value
$a=\mathbb{W}_{t}^{C}(\hat{\theta}^{\lambda}_{t}-\theta^{\star})$ and divide
both sides by
$\|\hat{\theta}^{\lambda}_{t}-\theta^{\star}\|_{\mathbb{W}_{t}^{C}}$ to get
that for all $t\geq 0$, with probability $1-\delta$, we have:

$\displaystyle\|\hat{\theta}^{\lambda}_{t}-\theta^{\star}\|_{\mathbb{W}^{C}_{t}}\leq\sigma\sqrt{\log\Big{(}\frac{\det(\mathbb{W}^{C}_{t})}{\det(\lambda\mathbb{I}_{d})}\Big{)}+2\log(\frac{1}{\delta})}+\lambda^{1/2}\|\theta^{\star}\|_{2}$

and therefore, by definition
$\mathbb{P}(\mathcal{H}_{\text{UCB}}^{II}(\delta))\leq\delta$.

∎

###  C.3 Proof of Prop. 4.3

See 4.3

###### Proof.

First, we use Lemma C.2 to deduce that under
$\mathcal{H}_{\text{CEN}}^{II}(\delta)$:

$\displaystyle\mathbb{V}_{\alpha}(T,\pi|\mathcal{H}_{\text{CEN}}^{II}(\delta))=\sum_{t=1}^{T}\operatorname{Tr}((\mathbb{W}^{C}_{t-1})^{-\alpha}a_{t}a_{t}^{\top})\leq
c_{\delta}^{\alpha}\sum_{t=1}^{T}\operatorname{Tr}(\mathbb{W}_{t-1}^{-\alpha}a_{t}a_{t}^{\top}).$

For all $t\geq 1$, we then use the fact that
$W_{t}\preceq(1+\frac{1}{\lambda})W_{t-1}$ to deduce
$\operatorname{Tr}(\mathbb{W}_{t-1}^{-\alpha}a_{t}a_{t}^{\top})\leq(1+\frac{1}{\lambda})^{\alpha}\operatorname{Tr}(\mathbb{W}_{t}^{-\alpha}a_{t}a_{t}^{\top})$.
The last and most important step is the integral comparison:

$\displaystyle\sum_{t=1}^{T}\operatorname{Tr}(\mathbb{W}_{t}^{-\alpha}a_{t}a_{t}^{\top})\leq\int_{0}^{T}\operatorname{Tr}(\mathbb{W}(t)^{-\alpha}a(t)a(t)^{\top})\partial
t=\operatorname{Tr}\Big{(}\int_{0}^{T}\mathbb{W}(t)^{-\alpha}a(t)a(t)^{\top}\partial
t\Big{)}.$

In the previous result, the continuous extension $(a(t),\mathbb{W}(t))_{t\leq
T}$ of $(a_{t},\mathbb{W}_{t})_{t\in[T]}$ for a given policy $\pi$ is defined
for any time $t\geq 1$ as:

$\displaystyle a(t)\triangleq a_{\lfloor
t\rfloor}\quad\text{and}\quad\mathbb{W}(t)\triangleq\int_{u=1}^{t}p_{a(u)}a(u)a(u)^{\top}\partial
u=\mathbb{W}_{\lfloor t\rfloor}+(t-\lfloor t\rfloor)p(a_{\lceil
t\rceil})a_{\lceil t\rceil}a_{\lceil t\rceil}^{\top}.$

This yields the result:

$\displaystyle\mathbb{V}_{\alpha}(T,\pi|\mathcal{H}_{\text{CEN}}^{II}(\delta))\leq
c_{\delta}^{\alpha}(1+\frac{1}{\lambda})^{\alpha}\operatorname{Tr}\Big{(}\int_{0}^{T}\mathbb{W}(t)^{-\alpha}a(t)a(t)^{\top}\partial
t\Big{)}.$

Finally, we conclude thanks to Lemma C.2 that:

$\displaystyle\mathbb{E}[\mathbb{V}_{\alpha}(T,\pi)]\leq\frac{\delta}{\lambda^{\alpha}}+C(\delta)^{\alpha}\operatorname{Tr}\Big{(}\int_{0}^{T}\mathbb{W}(t)^{-\alpha}a(t)a(t)^{\top}\partial
t\Big{)}.$

∎

######  Remark 5.

The main tour de force of the continuous approximation we employ is to relax
the maximization problem by considering the class of continuous deterministic
integrable policies, which is considerably more tractable from an analysis
perspective. On the one hand, it allows to get closed-form solution for the
maximization problem whereas the discrete approach can only deal with
approximations and upper bounds. On the other hand, it clearly reveals the
underlying matrix function the discrete approach is approximating and
henceforth allows to leverage powerful integration results. We leverage again
this idea in the context of Sec.4 to tackle impact of censorship.

To illustrate the abovementioned points, we remark that for the simpler case
of classical uncensored environment, we obtain for $\alpha>0,\alpha\neq 1$:

$\displaystyle\sum_{t=1}^{T}\|a_{t}\|^{2}_{\mathbb{W}_{t-1}^{-\alpha}}$
$\displaystyle\leq\Big{(}\frac{\lambda+1}{\lambda}\Big{)}^{\alpha}\frac{\operatorname{Tr}\Big{(}\int_{0}^{T}\partial\mathbb{W}(t)^{1-\alpha}\Big{)}}{1-\alpha}=\Big{(}\frac{\lambda+1}{\lambda}\Big{)}^{\alpha}\frac{\operatorname{Tr}(\mathbb{W}^{1-\alpha}_{T}-\mathbb{W}^{1-\alpha}_{0})}{1-\alpha}.$

For $\alpha<1$, we then have thanks to Lemma 3.5 the worst case bound
$\operatorname{Tr}(\mathbb{W}_{T}^{1-\alpha})\leq
d^{\alpha}(d\lambda+T)^{1-\alpha}$ and henceforth: