Effective Dimension in Bandit Problems under Censorship
Authors: Gauthier Guinet
Saurabh Amin
Patrick Jaillet
Venue: NeurIPS 2022 Accept (2022)
Keywords: Bandit Algorithms
Missing Data
Censored Processes
Statistical Learning Theory

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).

Effective Dimension in Bandit Problems under Censorship
Gauthier Guinet AWS AI Labs guinetggoamazon.c com
Saurabh Amin f MIT amins@mit edu
Patrick Jaillet MIT jaillet@mit. edu
Abstract
In this paper, we study both multi-armed and contextual bandit problems in cen- sored environments. Our goal is estimate the performance loss due censorship in the context of classical algorithms designed for uncensored environments. Our main contributions include the introduction of 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 first order, while embedding in a bigger space, and thus naturally leads to results analogous uncensored settings. Our analysis involves continuous generalization the Elliptical Potential Inequality, which we believe is of independent interest. We also discover interesting property of decision- making under censorship: a transient phase during which initial misspecification of censorship is celf-corrected reflects the inherent slowdown of learning governed by the effective dimension. Our results useful for applications of sequential decision-making models where the feedback received depends on strategic uncertainty (e.g., agents' willingness to follow recommendation) and/or random uncertainty (e.g., loss delay in arrival of information).
an extra cost; followed by a stationary phase that
Introduction
Bandit problems are prototypical models of sequential decision -maiing under uncertainty. They widely studied due to their applications in recommender systems, online advertising, medical treatment assignment, revenue management, network routing and control 26 39). Our work is motivated by settings in which the feedback received by the decision-maker in each round of decision censored by 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 deal with frequent losses of information (or delays in arrival of information) due to exogeneous failures such faulty and/or unreliable communication. Missing observations in dynamical interactions with the environment are a common concern in diverse fields ranging from operations management In other settings. such as AI-driven platforms for health alerts, route guidance, and product recommendations 77 46], the reception of feedback depends on whether not the decision (or recommendation) is adopted by strategic agents (c.g. patients, customers or drivers) with private valuations. Thus, from the platform's 's viewpoint, the adoption behavior of heterogeneous agents can be regarded as a stochastic censorship process.
health sciences to physical sciences M
20
2
Work done prior joining Amazon. Dept. of Civil and Environmental Engineering & Laboratory for Information and Decision Systems. I Dept. of Electrical Engincering and Computer Science Laboratory for Information Decision Systems.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In static environments, the bias induced by the presence of randomly missing information has been thoroughly studied [29 331. 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 126 39
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 [T5] Of particular interest the packet loss model recently introduced in (241, which provides the regret bound O ! Rr) where Rr 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, [II and 43. Our work provides 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.
p
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 [42], who
focus on a different information structure and obtain a scaling of 1/p (see Remark 4.4 related contribution by [2] provides both potential-based analysis of the Upper Confidence Bound algorithm (UCB) for multi-armed bandits and an algorithmic variant leveraging the Saplan-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 Under such assumptions delay, 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 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.
delays up time T [15 22
30
4r
usually gets a second
Moreover, the abovementioned works primarily focus on modifying well-known bandit algorithms to account for delays, propose new delay-robust algorithms which may be difficult implement in practice; a notable exception includes [4]] but 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 2 [
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 3 36 and Information- -roorattion-Direetedd Sampling [37 (23).
On somewhat related note, the literature on non-stochastic multi-armed bandit problems with delays [32 g. 21 also tackles multiplicative dependency, although in a different setting than ours. Another related line of work is Partial Monitoring G. 25 which deals with generic categorization of learnability, rather than a fine- -nn-grdi analysis of dimensionality in relation to censorship. which is our current focus.
two ways: firstly, through the use of these models in a sequential dxcision-making framework on which the impact of censorship is assessed in Sec. + Secondly, by showing that our multi-threshhe censorship modeI[[T 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 40 41 (where it is defined for Gram matrix K,, and regularization as (A) = tr( K, (K, + ATa) DD. Our work shows that an analogous quantity governs the regret bound of bandit problems in censored settings.
Our work contributes to the Generalized Linear Contextual Bandits literature 16

---

Finally, there is rich literature on classical missing and censored data problems 22 B3] Although conditional on the choice of given action the missing data/censorship process we study an instance of
(MCAR), the online action generating process adds significant difficulty 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 ii.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.
1.2 Summary of Results
In Sec. consider Multi-Armed Bandit (MAB) models and prove that the regret scales as O (Thm. 3.1 where deø is the effective dimension with value Σae(d] J. In doing so, we recover and generalze related results from 24
| 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 Va- Interestingly, we also show that the adaptive nature of censorship on Va 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 MAB under censorship instantiates an analysis framework which extends to Linear Contextual Bandits (LCB) (Sec. D. Our main result provides that regret is still governed by the effective dimension, but now with dependency of ( deø vT) (Thm. 4.1p To the best of our knowledge, these regret bounds provide the first thcoretical characterization in LCB with censorship. and contribute to the literature by evaluating the impact of censorship the performance of UCB-type algorithms. Our second main contribution is identifying the effective dimension for broad class of multi-threshole models M7 as well
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 Ellliptical Potential Inequality (Prop. 4.3) which we
believe is also of independent interest. Finally, our results (Thm. 3.I and Prop. 3.2 for MAB and Thm. 4. for LCB) suggest that the UCB class of algorithms is indeed a reliable method for stochastic bandits problems under censorship.
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 < T, the agent observes an action A, A. She then selects an action 0, E Ar (i.e.
arm) to which a noisy feedback r(a)) + e, is associated, where r(a,) is a bounded reward and e, is an i.i.d. sub- aub-Gaussian noise of pseudo-variance o2. For action a, the sub-optimality gap at time I is denoted (a) A m r(ā)- r(a), and the maximal gap Amar max.,1 (e(a). We recall the specifics of each model:
MAB: There is finite number of actions d, enumerated as A A [d], each having a scalar reward 8%. Arms are independent: playing one arm gives no information about the others.
LCB: The action set A, is subset of the unit ball B., possibly infinite. Unless explicitly mentioned, the reward is assumed to be linear with respect to a latent unknown vector H* Rd. i.e. r(a) (a, f*). Non-stochastic contexts are modeled by the fact that A, is drawn by an oblivious adversary. Here one does not need to rely on the typical i.i.d [6].
assumption on their generating process
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: independent Bernoulli random variable of parameter p(a:) denoted as Ja, is drawn after each decision o, and the feedback observed, i.e., realized, if and only if Fa, = 1; else the feedback is said to be censored. We recover the uncensored setting when p(a) = 1. Henceforth,
3

---

in both finite and linear settings, the Bernoulli parameter corresponding to the censorship probability depends on the action chosen i.c. our model allows the censorship to be heterogeneous across actions. Given that the action chosen at time is random variable, p(a+) refers to random variable well.
Algorithms: To study the impact of cen- sorship on bandit problems, we consider the class of high-probabilit, index algorithms based on the optimism under uncertainty prin- ciple, commonly referred as UCB-al UCB-algorithms. Following [23]] Algorithm summarizes the generic UCB design framework. We detail in App A the specific instances of UCB for MAB (resp. LCB) used in Sec (resp. See Pb. Moreover, this family of algorithms strongly relies on regularized reward estimators ri. where the regularizer is mostly used to pre- vent artificial cold-start exploratory phase.
Algorithm I: Generic UCB
Input: Total time T, Regularization X, Precision 8 T for / = ., do
Provide reward estimator it verifying w.p. 1-6:
|
Va E r()) (a)):
Play action (4 argmax (a):
if (a,,)(a)) Et) is realized i.e. To. = 1 then Update P
end end
Performance Criterion: The frequentist performance of the agent is measured by the notion of pseudo regret, i.e., the difference between the algorithm's 's cumulative reward and the best total reward. More formally, we introduce for any policy π E
R(T,T) T) = Σ max r(a) - r(())) E
dEA:
We aim to provide guarantees on [[[(T, m)] with respect to the number 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 with respect to the noise induced by the feedback, the censorship and possibly randomized policy.
2.1 Notations
Transpose of a vector u denoted by T. classical Euclidean inner product by (...) and trace operator by Tr. For positive to Vu" Eu. We use notation La to denote the d x identity matrix. B, the unit ball in Rd [n] the set of integers {1, 2. ... n}. For a given function f, we note f(i) the 7th derivative of f. To avoid confusion with the dimension d, we use öz instead of dz to denote an infinitesimal increase of x. We use the asymptotic notations ~, O, θ and O (O when log factors are removed). Finally, for an event H. we use H to denote its complement.
matrix Σ dxd and for any vector R notation |/u|| refers
3 Multi-Armed Bandits
3.1 Effective Dimension and Regret Bounds
The main result of this section that censorship effectively enlarges the dimension the problem. p.
We define the effective dimension as deø e En 1 and our result (Thm. 3.1 shows that, at first order, the regret is guaranteed to be the same as the uncensored problem with deff arms instead of d. Theorem 3.1. Under censorship. the UCB algorithm with regularization X has instance- independent expected regret of:
B[R(T,TUCB)) < do
Furthermore, we obtain analogous regret guarantees for instance-dependent cases where, at first order, the uncensored dimension Eutar A.
a² enlarges to Engar P.
Proposition 3.2. For a fixed action set A, = [d] and for a-priori known action gap Aa & max; 0g 6r the UCB algorithm with regularization X has the iistance-depence expected regret:
B[R(T, TUCB) I 00 (o(g)((T)
Σ
max o²
Aa)).
A
Pa
agaa

---

On one hand, a preliminary understanding of censorship posits an increase of the average "regrer per information gain" [23 (as 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. and and Prop. 3.2) postulate that the censored problem is equivalent at first order higher dimensional problem but explored with the same regret per information gain.
The abovementioned results extends to a-priori known heteroskedasticity (see Rem. E and App. B.. For this general setting, the effective dimension for instance-independee (resp. dependent) case is
o² given by Ea o (resp. Enpin" P.A." ) where o the variance proxy of arm a. Although the scaling in En A. already mentioned in 24! for unregularized setting with homogeneous variance o²
and proven to be optimal, our results generalize these findings.
3.2 Cumulative Censored Potential
We now provide a proof sketch of Thm. 3. and doing so, we instantiate an analysis framework that will be extended in Sec. g 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 E [T], the random number of times an arm has been pulled (1) A Ei= fat = a). Similarly, the number of times action has been realized at the end of round denoted N. (1) 2 Σi= 1aa)
= a, Dag = 1]. We then have: Lemma 3.3. Given an uniform regularization of X > 0, the UCB algorithm verifies:
2dA maz
B (R(T, (UCS)) < log()) 1 (T, TUC)) + 2A 1l mUCB)]
T
where, for any > 0 and π E II, the cumulative potential under censorship is given by:
T (T(T, Σ (No, (t 1) a
t=1
Without censorship, the cumulative potential translates the average rate of decay of uncertainty on the reward of different arms and is closely linked the divergence between the true reward distribution and the empirical distribution of observed rewards BSI Introducing censorship transforms the classical deterministic decay rate into stochastic one. For a typical reward distribution, the rate of decay is proportional to a term in n or can be upper bounded by such term (see for e.g. [8) where n is the number of observed rewards. Therefore, a higher a corresponds to faster learning.
In contrast to the classical non-regularized analysis or to the LCB case of Sec. we observe two different orders of a (1/2 and 1) coming from the of the nnom instead of the I---nomm. Taken independently, they lead respective contributions of (deff log(T)) and O T) Note that by working with a general a, our analysis naturally extends beyond Gaussian noise to more general assumptions about the Laplace transform of noise (e.g.. lighter heavier tails), as discussed in Rem 2 To further study Vo. we introduce the following property:
Proposition 3.4. For all a > EJO, 1] and given taa a primitive of xf x x we have:
max VI. < deff REll
[ deff 1-8"
T +
A
X
+ 24d log(T) d
4d
(1- 8) bbl ba(
val
aa
X
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 8 Ej0, 1] the event:
HCEN(O) = (Ea E [d],t (T)) < (1 (t) and Ta(t) 2 To(a)),
where To(a) A 24 log(T) + and claim that (((CEE(0)) < 1268 improving result of !i Here HCEN denotes the event where there is significant gap between the realized and expected
5

---

number of observed rewards. We consider its complement in our analysis of the principal order of regret. This allows to lower bound for each action, the realized number of reward observations by 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 [4]):
Lemma 3.5. For va primitive of x + x- where a eJ0, 1}, regularization (Na)aE(d) E (Rxo)* and censorship vector (Pa)oEld) the solution of the optimization problem:
Σ
1 Pa
(Pa + Aa) vsa(aa))
Σ Ta=T
max
To...Ta00
aE|d]
aE|d]
given by TO 110 >alt, where ensures the total budget constraint Ene(d] To T. In particular, with Xen - days Eoeid da and Xa A deft(2 >og)) the optimal solution is given by Pa Tat Pedar (T- (T-2 for max X and the optimal value is deff v day + +hez) -Eaedd pa va
For unregularized algorithms, this framework can be easily applied to provide instances-dependen guarantees by adding constraints of type Ta < f(Aa) within Lemma 3.3 Optimal guarantees under regularization such as the ones given in Prop. 3.2 require however to consider both orders of V. (1/2 and 1) simultancously and not independently, leading to slight variations as shown in the proof of Prop. 3.2 Next, we further discuss the properties of Va given its importance in analysis.
3.3 Evaluating Adaptivity Gain
It is well known that adaptivity is 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 significant advantage 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 the realization of the censorship process, in comparison to class of non- non-adaptive (i.e., offline) policies.
In fact, through the introduction of HEEN (6) and for any [0, 1]. ō E)0, 1J. we showed in Prop. I P23) for the learning complexity max B[V a (T, *)] where the
dar 3.4 the upper bound πT- Va ( maximum is taken over the class of adaptive policies Iagdope. i.e., measurable with respect to the censorship. Note that the exact value of such maximum notoriously difficult to study due to the adaptive nature of censorship induced by the decision-makin process. Next, we introduce IT Tof the class of policies that are not adaptive with respect to the censorship and we prove that
T
Lemma 3.6. For eJ0, 1] and À > O, we have max E[V. (T, ~ deft val
A).
FEll.g
def
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 e|0, 1), by denoting "aa (p)
a 2d
-
we have:
l-
clf
aE(d
Pa
a
Pa
1
max ETV max E (T, T) %a (p) x T
ol
TETT.Y
To
To
Moreover, if for a given 3 sJ0, 11, we introduce ( the policy class whose censorship information set has single updating time [ST], we have:
3 max E (T, x)] (p) To ol (l HElL.
ETV.(T,
(**)
T TEllagg
Thus, Yo (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 Vo. (**) tells us that single observation of the censorship realization is sufficient to obtain near-optimal gain in adaptivity. We present proof sketch of Prop.
App. B
This shows that censorship MAB can be treated 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. - 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.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:
p:a B Σ ((sin(d;) S (a, u) sin(
(MT)
where (0y)ssk+1 is an increasing sequence verifying do = - Φx+1 and u E IR is unit vector. We assume that (p))isk is decreasing, i.e. the censorship is increasing with j in direction Henceforth, we refer to the interval ( sin (0)+1) [ as region j. Note that simple models such as uniform censorship are subsumed by this family (for is equals 0).
The two main features of the multi-threshold model are: the radial aspect (the censorship probability depends on the action through scalar product with given vector) and the mono- tonicity (the censorship is monotone in the value of this scalar product). Note that MT can be seen as a piecewise constant approximation of any Generalized Linear Model (GLM) [3]] Thus, the simplicity of this censorship model is not an inherently limiting factor on the general- ity of our subsequent results.
p(a)
Pl
P2
(a, u))
Moreover, MT admits natural behavioral in- terpretation: Such a distribution can be seen induced by population model of hetero- geneous random-utility maximizing agents. A single threshold model (i.e. k equals 1) cor- responds to given agent type, and the multi- threshold model naturally results from aggregate responses of heterogeneous population [4]
sin(dn)
sin(di)
sin(dd))
sin (ps)
Figure I: Example of a multi- multi-threshold model for
k 2 (Green). Logistic censorship model (Red)
We now state the main result of this section:
Theorem 4.1. For given mulii-hresholld censorship model algorithm with regularization X has an instance-indend indeeeeeed expected regret of:
IMT there exits dag such that the UCB
E[ TucH)] < Olaa/d degTT)
Importantly, note the mapping from the original dimension d to the enlarged dd deff- in contrast to the previous dilation + deft for the case of MAB problems. An extension to Generalized Linear Contextual Bandits is provided in App. C.6 where show that the dimension is governed by /d- -deff// KR, with & corresponding to minimum of the derivative of the link function (encompassing the smoothness of the GLM at maximum) relax the monotonicity property of 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 GLMs (further discussed in App. C.6) where appears prominently.
28 i6
We conjecture that this result still holds if we
7

---

4.2 Generalized Cumulative Censored Potential
Analogous to the MAB case, we now introduce for LCB the random matrices corresponding to the effective realization w & TاK + In Te,a and the expected realization W, - PIa E ((r)aaa)) We also introduce the continuous counterpart of W, defined as (()) _ AIa + (u)aa(())((())) (aaaau)TTa ou, where (a(u))usT is an integrable deterministic path 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 generalization of V.:
Lemma 4.2. For all Ej0, 1}, there exists a constant (T) = (VVllog(T)) such that
E R(T, suCB)) S (5 TuCB)] + 87A
where, for a > and æ E II, the linear extension of the cumulative censored potential given by:
(T( 2 Σ laellwwe .) Σ (r((WW))--aa
The proof idea is analogous (albeit more complex) than in the finite action case (see App. C In order to get handle V.. we again leverage 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 continuous lens. The first step requires the following result:
Proposition 4.3. For any d EJO, 11, x > 0, a
and policy E I1, we have:
8 a Cr J w(()=%(((a(() Ta),
ETV.
-
where C()) A 1))+1) max(log (d/ 1)/2
The key idea of this result is to observe that the telescopic sum which the classical Elliptical heavily relies on is, in fact, the discrete approximation of an integral over
Potential lemma 0 35 g
matrix path. This critical methodological contribution is further discussed in Rem. Mand S
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 a >> 0, a # 1:
A+1y a Tr (10 (w(())-))
A + -1A+1
a Tr( 1- 68! ())-a)
Σ lael Ie 1
1-a
a
For 1, similar reasoning is applied using the formula Tr(log(A)) llog(dee A):
X + X+1 S" 2 log (eeee((())) at
X Tr(log Wr log Wo) X + 1
log del WT X det Wo
| 1all?
Öt
A deeper study of the eigenvalues of Wh-a then yields the worst-case upper bound d' (d) a) T)'-0/(1 aa) for a 1 and dx d(a-"/(a 1) for a > 1, recovering more naturally and ex- tending the results of [ Thus, analogous to the water filling process highlighted in the MAB case in Lemma 3.3 we now consider a spectral water-filling process (14] optimizing over the eigenvalues of V. (WT) with a slight abuse of notations! W and log WT in this discussion).
Following Rem
for the general censored case the challenge now becomes 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 a = for which Prop. 4.3 implies that for any policy:
Tr ( w(() a(())(()) = p(a(())
alog det(())(()))) dt.
Øt
Next, we focus maximizing this integral over the policy class II and again recover the notion of effective dimension.
In this section, the generic notation X (t) is used for continuous time quantities and X. for discrete time.

---

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 MT
Lemma 4.4. Let consider uniform censorship model p P. By leveraging the case of equality in the Aritmmtiic-Gemmeticc inequality applied to the eigenvalues of Wr, we then simply deduce the associated effective dimension deff 2 d/p:
a log det( 0t = deØ log(1 +
max XEI1
Ōt
Adef
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/ Pmin in the next lemma: Lemma 4.5. For any censorship function p. by introducing lower and upper bounds (Penin: Pmax) of we have:
d
log(1 + Pmiin T
PT alog det (W(()
Pmaan
S max NEll JO p(a(t))
01 S log(1
+
Pmaar
dx
Ōt
Ponin
dA
Related problems in the Generalized Linear Models literature the spirit of Lemma 4.5 where a minimum of the derivative of the link function plays the role of
28 16 are implicitly solved in
Pmin above. However, when the function varies with action a, more careful analysis is required to derive useful dimensional bounds. Our next major result addresses this gap the literature by improving the bounds provided in Lemma 4.5
Theorem 4.6. For a multi-threshuut censorship model M7
have:
1
θ Olog
max
ōt dey log(T) o(log(T)),
(P)
p(a(t)) Ot
where days is the effective dimension. Furthermore, detr charucterized by two cases:
Case 1: Single region effective dimension def d. pj"
.
Case 2: Bi-region (i.j) effective dimension, with < j: I(i,])
+ u(i,))
deff Pj
(d 1) ps 1(1,5)
u(i.5)
Pt
Pj
P5
where [(i,j) A sin (d.) and u(i, sen)
cos? ((x)
cos? (o,))
The implications of these cases are further discussed in Fig in App. D Notice that a necessary condition for the bi-region (i,j) effective dimension to arise is the constraint on Pi:
di (i.((,(()))
(d (i () + ((i.j)
m1 u(i + (d 1)((1,))
Pi
Pj
d
(t,))
Er (6.d)
In the limit Ps + (i, dey goes again to d/pj- We interpret this limiting case as locally hard in the sense that censorship in region is sufficiently important in comparison to all other regions impose maximal effective dimension to the problem, irrespective of the values of p., matching Lemma 4.5 On the other hand, for the other limiting case (under additional mild assumptions), we find that def also goes d/pj. but now for a uniformly hard reason: that is, censorship is approximately constant and equal to Pj. recovering the Lemma 4.4 Finally, in between these two extremes lies the minimum effective dimension for given value of
4.4 Temporal dynamics of (()
The proof of Thm. 4.6 requires the characterization of the dynamics of the optimal policy of (P) Importantly, we discover that the evolution of (()) is described by two qualitatively different regimes as outlined next. turns out that our continuous approach to analyzing cumulative censored potential an important tool to obtaining this result.

---

Transient Regime: There exists decreasing sequence of censorship regions {ir = k..... ......,)) -t) of length E [K+ 1] and associated time sequence (fo 0, f1....,4h 41) such that whenever 1j S 1++1 for a given index j s 1, the evolution of W(t) is given by:
((1) - Pisti (1 W, W(G) - Piş+i (1 (;)
Σ Pin (In - ln- 1n-1) + AIla
where W, denotes the d diagonal matrix diag( initial misspecification of censorship is self-corrected during this transient step but at extra cost. This characterization of transient regime highlights an important consequence of using classical algorithms in censored environments.
cos (dx)
0o8 (ds) sin 2 (Q:)). Interestingly, the
d-1
Steady State Regime: Post-transient regime, the dynamics of W(t) enter a steady state regime, where one of the two cases necessarily arise
Single region it. This case arises when the last element of the time sequence ty is equal to too and we have the single region evolution for all 1t-1:
Case 1:
W(t) = Pt, (t 1af-tt-l f1-1 + W(ti-1) -t- 1
+
Σ
Pb.. (tn - W + Alda
==1
The effective dimension corresponding to this dynamics is d/pt. with the following equality for T 2 4111:
Jo
1 log (W)()) Øt p(a(t))
log det (W(T))
+
log det W(,,).
Ot
Pi
Pop
Pin-1
n=1
Case 2: Bi-region (i+4, i.). This case arises when the steady-state dynamics of W(t) span the two regions (i141, in) with 1 < it. For all t 2 44, we have the evolution:
coss((sx) (u(ir+1, it) P4,
Pu+1 Illa-
(0)
W(t) X Pi+t (t + X*)
Pitl ((1+1,40) 6i1) Ps
(0)
sin 2 (o., )
where X and the proportionality factor are specified in SI. The corresponding effective dimension is given by D and the following equality holds for all 2 l::
T 1 Olog det 0t dess log(1 + p(a(t))
T T tu ti + x+
1
log det (t.).
Ōt
P
Pi.-1
For further discussions on transient and steady state regimes, we refer to Fig
and in App.
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 novel analysis framework which enables us to precisely estimate this quantity for broad class of 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 Va. as initiated by [[8]. 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 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-Al interactions is central. 10
censorship models. An
12]
We do envision any negative societal impacts of our work other than that of bandits algorithms deployed in Al-driven platforms.
'These cases are fully characterized in terms of parameters of censorship model in Lemmas D.I
D.2
D3
and Cor. D.I.I
10

---

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 cen- sored 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, July 2007.
[5] Sylvain Arlot. Rééchantillomagg 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, 1109))2775-2836, 2010.
[7] Xueying Bai, Jian Guan, and Hongning Wang. A model-based reinforcement learning with adversarial training for online recommendation. In Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, 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 Gesa-Bianchs 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 Fumann-Rbba 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. Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, volume 15 of Proceedings of Machine Learning Research, pages 108-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 Telecommunicatioons and Signal Processing). -ntes--ntercccence, USA, 2006.
11

---

[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: / 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-Taylon, 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 31 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 cotrmatiionthhorette 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. 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 statisties. 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. Proceedings of the Twenty-Ninth AAA/ Conference Artificial Intelligence, AAAI'5, 15, page 2849-2856. AAAI Press, 2015.
[31] McCullagh and J.A. Nelder. Generalized Linear Models, Second Edition. Chapman and Hall/CRC Monographs on Statistics and Applied Probability Series, Chapman & Hall, 1989.
12

---

[32] Gergely Neu, Andras Antos, András György, and Csaba Szepesvári. Online markov decision processes under bandit feedback. In J. Lafferty. Williams, J. Shawe-Tayke 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 delayed, aggregated anonymous feedback. In International Conference on Machine Learning, pages 4105-4113. PMIR, R, 2018.
Shipra Agrawal, Csaba Szepesvari, and Steffen Grunewalder. Bandits with
[35] Chao Qin and Daniel Russo. Adaptivity and confounding in multi- bandit experiments, 2022.
[36] Daniel Russo and Benjamin Van Roy. An information-theoretii analysis of thompson sampling. Journal of Machine Leurning 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, 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. Proceedings of the 27th International Conference International Conference Muchine Leurning, ICML' 10, page 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 Transac- lions on Information Theory.
[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. Ben- gio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information P Processing Systems, volume 30. Curran Associates, Inc., 2017.
[44] Han Wu and Stefan Wager. Thompson sampling with unrestricted delays. arXiv preprint 2202 12431, 2022.
[45] Fuwen Yang and Yongmin Li. Set-membership filtering for systems with sensor saturation. Automatica, 1866) 2009.
[46] Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in healthcare: 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 H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'AchééBuue, E. Fox, and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
13


Reviews:
[{"review_id": "rjq_tdNMdbe", "reviewer": "Reviewer_qkWU", "summary": "The authors provide analysis on UCB-like algorithms for the case where rewards are censored with action-dependent probability. They show that regret bounds are, loosely-speaking, worsened in the same way as would happen for uncensored problems where the dimensionality of the problem is increased.", "questions": "In the \"Information Structure\" paragraph 120-124 it took me a moment to understand whether the Bernoulli parameter p_{a_t} depends on the value of a_t. In the non-contextual/non-conditional case, is there a different censoring probability for each action value? Or is there just one Bernoulli parameter.\n\nIf there are action-specific Bernoulli parameters: Alg 1 only updates the gap estimator when a reward is observed. Are there variants that also take into account with which probability each action's reward's are observed? (using an estimate of the p's)? Are there any advantages to such algorithms? I'm thinking of re-weighting estimators in causal inference and survival analysis. What analysis is possible w.r.t. your dimensionality and regret results for such algorithms, if they exist / are relevant?\n\nFor the contextual bandits, it seems that the censoring model is such that p (the observation probability) depends on the action a. What about cases where it also depends on the context? (by the way the context seems not to be instantiated as a variable in 4.1?) If censoring depends on the context also, which of your analysis would be possible and which wouldn't?", "limitations": "Yes. But please clarify which censoring your analysis applies to and which kind of censoring would be hard to analyze using your framework.\n\n\n  ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In general it is valuable work and I support the acceptance of this work. It is both novel and well-written.\n\nI will only ask a few questions and make a few suggestions.\n                                                                             \ngeneral writing/grammar/typos/acronyms/etc\n\nyou don't fully ever define \"regularization\" in the UCB algorithms. Doing so will help the reader.\n\nUCB first appears without its full name in line 56\n\n\"leveraging Kaplan-Meier estimator\" in line 57 should be \"leveraging the Kaplan-Meier estimator\"\n\nwhen you say \"a notable exception includes [38]\" in lines 64-65, it would be good to mention\nwhat is distinct about it and your relationship to that work. Otherwise you are asking to the reader to do extra work to figure out why you are mentioning it.\n\nMAB is defined in lines 85 and in 106\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SVGxkrI0Ifv", "reviewer": "Reviewer_R7Ls", "summary": "The authors study bandits under censorship. \nThe key contribution is to provide the theoretical performance (the extra risk due to the censorship).  ", "questions": "In the introduction, the paper mentions the difference from the Rubin's missing-completely-at-random.  But more details on the difficulty in online learning are need.  It also help to assess the theoretical contribution of this paper. \n\nThe relation to the delayed bandits is not clear. It seems the result is similar to the delayed bandit, although the effective dimension is a new concept from this paper. \n\nIn the definition of the censorship model, the parameters are fixed but rely on the action a_t? If so, p_a is fixed given a, although p_{a_t} varies over t.  How much is the difference of missing-completely-at-random? \n\nIt seems that a key notation is ignored. \\tilde{\\Delta}_t^{\\lambda} is ignored. It lets reading the paper difficulty.  Because the regret analysis seriously depends on how to address the censorship in the algorithm.  This issue is important for understanding this paper. ", "limitations": "The Generic UCB algorithm relies on a previous work.   A clear presentation should be needed. ", "rating": 3, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: the paper first provides a new concept, effective dimension, to measure the effect of the censorship in the bandits. \n\nWeaknesses: \nBecause the regret analysis should depends on how to handle the censorship, the effective dimension may be specific to algorithm. \nAs a pure theoretical paper on effective dimension in bandits with censorship, i don't think the contribution is solid. \n\nI know little about the censorship, so i may be ignoring the theoretical difficulty and contribution. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "OSzaNzy6VkT", "reviewer": "Reviewer_hhGV", "summary": "This work considers bandit with censorship where the reward of the pulled arm may not be observed. Authors analyzed the regret upper bounds of existing algorithms under the new proposed setting.", "questions": "See my comments above.", "limitations": "No obvious limitation.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe setting is novel, and the analysis is solid.\n\nWeaknesses:\n1. As a new setting, the author does not provide motivating examples. While some previous works may relate to the setting, the author should answer why do we need a general setting.\n2. No new algorithm is proposed. If presenting new algorithm is challenging, I think authors should discuss why it is challenging and the drawbacks of existing algorithm when applied to the new setting.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7C9z5XpGIgR", "reviewer": "Reviewer_5N2o", "summary": "This paper analyzes the regret of UCB under different censorship models using the effective dimension of the problem, leading to other insights including the learning process during censorship and the elliptical potential inequality. Both multi-armed and linear contextual bandits are included. ", "questions": "See above. ", "limitations": "Yes. ", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths** \n\nThe theoretical results are thorough and the paper is generally well-written, though dense. \n\n\n**Weaknesses** \n\nWhile the main results, e.g. Theorem 3.1 and Prop 3.2, look familiar and reasonable, I could have personally benefitted from more exposition and intuition on some of the more complex expressions introduced. Examples that come to mind include the cumulative potential under censorship (L172) and $H_{CEN}$ (L182).  I.e. what is the intuition of $\\mathbb{V}_\\alpha$ at different $\\alpha$? \n\nOverall, I found sections 3.2-3.3 to be quite dense and difficult to interpret—possibly due to my lack of background on censorship.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept