Venue: NeurIPS 2022 Conference

Reviews:

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 studies a variant of multi-armed bandits, where each action can change the distribution of some random variables (which otherwise follow baseline distributions), and the observed reward is a sum of these random variables. The learner's goal is to find the best action while keeping the cumulative regret as low as possible.

To do this, the authors use the ideas from the uplifting modeling (modeling the incremental effect of an action on an individual variable) and propose upper confidence bound (UCB)-based algorithms that estimate uplifts over a baseline distribution. They prove that all algorithms have sub-linear regret upper bounds and empirically validate the performance of algorithms.
strengths_and_weaknesses: #### **Strengths of paper:**
1. The problem setting is well motivated. The authors consider different settings (i.e., known or unknown affected variables and baseline payoffs) and develop new ideas (either exploiting underlying problem structure or adding some mild assumptions) to design algorithms for these settings.

2. The authors propose upper confidence bound (UCB) based algorithms named UPUCB (bl), UPUCB, UPUCB-nAff(bl), and UPUCB-nAff for four different settings. These algorithms exploit underlying problem structure (and additional assumptions for the most challenging setting, i.e., unknown affected variables and baseline payoffs) and show that these algorithms have sub-linear regret.

3. The authors have empirically validated the different performance aspects of the proposed algorithms. 


#### **Weakness of paper:**
1. The setting when the affected variable and baseline payoffs are known can be modeled as a special case of the combinatorial bandit problem, which is the simplest form of the problem (also discussed in the supplementary material). I notice that the authors have missed the most recent work in this direction by Perrault et al., 2020 (Paper: Statistical Efficiency of Thompson Sampling for Combinatorial Semi-Bandits, NeurIPS 2020).

2. Since the lower bound for the simplest case can be adapted from the lower bound given in Perrault et al., 2020. Hence, it is unclear how the lower bound presented in the paper is different. 

3. The contextual extension discussed in Section 7 is a simple extension when the affected variables and baseline payoffs are known. Even for other settings, after having the underlying ideas for non-contextual cases, I am not sure what are the difficulties to extend for contextual setting (as estimating reward needs to be changed and for that exiting contextual bandit's results can be used).
questions: Please address the weakness raised in **Strengths And Weaknesses**. I can change my score based on the authors' responses.
limitations: The lower bound given in Section 4 (already similar results exist for combinatorial semi-bandits) and contextual extensions consider in Section 7 are not significant results. Since this work is a theoretical paper, I do not find any direct negative societal impact.
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 introduces the framework of uplifting bandits - wherein an action affects a subset of intermediate variables and the rewards are the sum of the random variables. The uplift of an action is then computed by comparing it against the baseline where no variable is affected. Variants of the UCB algorithm are proposed that use varying amounts of knowledge about the structure of the problem and result in improvement in regret. 
strengths_and_weaknesses: Strengths:
- Introduces a bandit framework that better models some applications mentioned in the paper
- The paper is clearly written and the illustrations make the dense material easy to follow
Weaknesses:
- The algorithms proposed rely on a significant amount of knowledge of the structure of the problem that is often not realisable in real settings. Figure 3(b) shows an example where knowledge and lack thereof make a large difference in performance compared to methods completely agnostic of the structure of the problem

L122: achieve (typo)

questions: To my understanding, if the covariance matrices in the “Gaussian Uplifting Bandit” experiment were to be changed to be (significantly) different for each action, the structure agnostic algorithms (UCB and TS) would perform relative better than the UCB variants. Do the authors have ane experiments about the same, or a comment on the sensitivity of the algorithms this variance in the noise covariance matrix?
limitations: Yes, the limitations have been addressed by the authors. The potential negative societal impact of these algorithms in the applications mentioned has not been discussed.
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: The paper studies a MAB problem where the reward has an additive structure. Each arm affects a subset of terms of the overall reward, and the goal is to maximize reward while not knowing which subsets are affected (e.g, their reward distributions changing) by which arms.

strengths_and_weaknesses: From one view, this problem can be thought of as a combinatorial bandit problem where you have n sets to choose from and each set leads to a different payoff. What difference does a baseline different from 0 make in the analysis and development of the online algorithm? If the baseline is 0, isn't this the same as the set optimization problem? Given these two points of view, the paper does not make it clear why the general combinatorial bandit strategies do not apply. In fact some of them explicitly make use of the objective function structure (linear, Lipschitz etc) and derive regret bounds. (The individual payoffs of elements in the set are assumed to be observable in the paper whereas its not needed in the general case.) It is hard to make out from the paper what the significant differences and disadvantages are of applying these ideas? Or is it that the structure proposed in the paper does not map to a clean offline combinatorial problem at all?

Can the authors clarify: "In contrast to standard UCB methods, these differences are not optimistic". What does this mean (I am likely missing a nuance here)?

Since uplift modeling is a popular approach in causal inference (and applied to all the usecases mentioned in the paper), this causes wrong expectations to be set and misleads the reader (even though the authors mention this and cite 11,16).
questions: See above.
limitations: Yes.
review_title: null

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: The paper tackles the problem of detecting whether or not a strategy provides an "uplift" compared to a default one. As example applications, we have e-commerce, advertising and recommendation systems etc. where a strategy consists of a desired change from the status quo (a baseline) of a product affecting a subset of users. The goal is to determine if there is an uplift in the reward of the new strategy relative to the baseline, defined in this example as the sum of observations over all users. The setting is studied when the baseline and number of users are each known or unknown. 
The paper proposes 2 algorithms (one for when the baseline reward is known and one for when the "users" affected by a strategy are unknown) accompanied by instance specific regret upper bounds. The relevance of the algorithms is demonstrated in a set of experiments on artificial data and on the Criteo Uplift dataset.
strengths_and_weaknesses: Disclaimer: I have not read the Appendix.

Strengths:
- The problem of detecting "uplift" is relevant in practice
- The paper tackles 3 variation of this setting where different information is given
- Interesting approach to examine differences of UCBs among CTRs in Algorithm 1 (UpUCB)
- The setting with unknown affected variables is the most significant of the ones presented here for practitioners
-  Numerical experiments show expected performance gain against a common-sense baseline.

Weaknesses:
- Presentation needs to be greatly improved and expose the paper's contribution over the related work more clearly. A large amount of material is deferred to the Appendix making the paper seem to not be self-contained. For instance, the results in the proofs are not obvious and I would have expected at least sketches being presented in the main paper. It is unclear why using an index based on the difference of UCBs works and I am left with a lot of questions about the quality of the evidence presented in the main body of the paper.
- The setting where both baseline and affected variables are known feels to not provide much novelty. I think this section can be sacrificed in order to provide further details about the other settings and contribution relative to prior work.
- From what I can tell, when the affected variables are known the setting reduces to the treatments affecting all variables (since we can always ignore all variables where we know there is no impact) and the regime where $m << L$ no longer holds. I believe more attention should be given to the 3rd setting where the affected variables are not known, at the expense of the others 2 settings: both baseline and affected variables are known, and only the affected variables are known.
- When the affected variables are unknown, the assumption that the same variables are always affected becomes a bit too strong to be met in real life scenarios, which I believe hurts the significance of the results. I would have liked to see much more attention given to this setting and more explanations as to why this assumption (time invariance of affected variables) is justified. As is, I feel the setting is slightly artificial and the most relevant to practice would be: a) all affected variables are known (we know which users are in an A/B test) and b) the affected variables are unknown and which variables are affected is not constant (if we don't know which users are in a test we can't guarantee returning users will make it in the same treatment).
- The baselines in the experiments seem a bit weak given that in the setting where the affected variables are known, we can just ignore all the unaffected variables.
questions: When the affected arms is known, if we just use a regular UCB-algorithm that only considers the affected arms (since we know the rewards of all others will be the same), will this not result in the same kind of regret scaling as that proposed here for this setting?

How does the mechanism in UpUCB work from the perspective of the regret analysis? I would like to see this explained in the main body of the paper in order to consider raising my score for soundness. Similarly, I would have liked to see regret analysis proof architectures in the main paper. I feel the results at the moment lean too much on material deferred to the supplementary material.

Can the setting generalise to when the set affected variables change over time? For instance, if some variables are affected for one play, but others on the next etc. This would make the case where the affected variables are known more interesting and relevant in practice, in my opinion. Are there settings where we do not know the affected arms, but they are constant over time?

Is there a deeper reason why the baselines do not only consider rewards collected from affected variables (when the affected variables are known)?
limitations: I do not believe the paper has negative ethical implications.
I do believe the authors did not adequately discuss the limitations of their work.
review_title: null

Meta-review: metareview: The paper's main contribution is, in my opinion, conceptual. It introduces a new multi-armed bandit problem with arms ('interventions') that affect a sparse set of downstream variables, a 'baseline effect' and an additive reward ('uplift') structure. The motivation for this is drawn from uplift modeling and its associated causal inference from marketing and e-commerce domains. 

While this could, on one hand, be cast aside as 'yet another' combinatorial-type bandit problem, I believe that it brings to the table an interesting and thought-provoking information and decision structure to reason about, setting it apart from typical variations of bandit problems. Though one of the reviewers questions its scope as being rather narrow, I believe it is worth taking a risk ('pulling an exploratory arm'!) and see this paper published in the hope that it spurs other fruitful work in this interface of marketing and ML. 

I note also that the paper is written in a clear and lucid fashion, and urge the author(s) to suitable incorporate their suggested additions and clarifications arising from the engagement with the reviewers into the final version. 
confidence: Certain
Decision: Accept