Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths:
The setting is novel, and the analysis is solid.

Weaknesses:
1. 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.
2. 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.
questions: See my comments above.
limitations: No obvious limitation.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: In general it is valuable work and I support the acceptance of this work. It is both novel and well-written.

I will only ask a few questions and make a few suggestions.
                                                                             
general writing/grammar/typos/acronyms/etc

you don't fully ever define "regularization" in the UCB algorithms. Doing so will help the reader.

UCB first appears without its full name in line 56

"leveraging Kaplan-Meier estimator" in line 57 should be "leveraging the Kaplan-Meier estimator"

when you say "a notable exception includes [38]" in lines 64-65, it would be good to mention
what 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.

MAB is defined in lines 85 and in 106


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.

If 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?

For 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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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. 
strengths_and_weaknesses: **Strengths** 

The theoretical results are thorough and the paper is generally well-written, though dense. 


**Weaknesses** 

While 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$? 

Overall, I found sections 3.2-3.3 to be quite dense and difficult to interpret—possibly due to my lack of background on censorship.
questions: See above. 
limitations: Yes.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The authors study bandits under censorship. 
The key contribution is to provide the theoretical performance (the extra risk due to the censorship).  
strengths_and_weaknesses: Strengths: the paper first provides a new concept, effective dimension, to measure the effect of the censorship in the bandits. 

Weaknesses: 
Because the regret analysis should depends on how to handle the censorship, the effective dimension may be specific to algorithm. 
As a pure theoretical paper on effective dimension in bandits with censorship, i don't think the contribution is solid. 

I know little about the censorship, so i may be ignoring the theoretical difficulty and contribution. 


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. 

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

In 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? 

It 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.
review_title: null

Meta-review: metareview: The reviews for this paper have a high variance (ratings 3,4,6,7). The reviewer who gave a 3 seems unfamiliar with the basic bandit literature and I don't find the review particularly insightful. The other three reviewers mention that the theory is useful and solid, and the setting is interesting to them. On the negative side the reviewers mention that the paper is quite dense and some motivating examples would be useful. These are both minor points and, in my opinion, the positive aspects outweigh the negatives. 
confidence: Less certain
Decision: Accept