Uplifting Bandits
Authors: Yu-Guan Hsieh
Shiva Kasiviswanathan
Branislav Kveton
Venue: NeurIPS 2022 Accept (2022)
Keywords: Structure bandits
Regret minimization
Uplift

Abstract: We introduce a new multi-armed bandit model where the reward is a sum of multiple random variables, and each action only alters the distributions of some of these variables. Upon taking an action, the agent observes the realizations of all variables. This model is motivated by marketing campaigns and recommender systems, where the variables represent outcomes on individual customers, such as clicks. We propose UCB-style algorithms that estimate the uplifts of the actions over a baseline. We study multiple variants of the problem, including when the baseline and affected variables are unknown, and prove sublinear regret bounds for all of these. In addition, we provide regret lower bounds that justify the necessity of our modeling assumptions. Experiments on synthetic and real-world datasets demonstrate the benefit of methods that estimate the uplifts over policies that do not use this structure.


Uplifting Bandits
Yu-Guan Hsieh" University Grenoble Alpes
Shiva Prasad Kasiviswanathan
Amazon
yu-guan. gegguanhseeeuuiii-rree aer.eeee-le.reneeeellee..... fr
kasivi masivisw@gmail.com com
Branislav Kveton
Amazon
bkveton@amazon..com com
Abstract
We introduce a multi-armed bandit model where the reward is sum of multiple random variables, and each action only alters the distributions of some of them. After each action, the agent observes the realizations of all the variables. This model is motivated by marketing campaigns and recommender systems, where the variables represent outcomes on individual customers, such as clicks. We propose UCB-style algorithms that estimate the uplifts of the actions over baseline. We study multiple variants of the problem, including when the baseline and affected variables unknown, and prove sublinear regret bounds for all of these. We also provide lower bounds that justify the necessity of our modeling assumptions. Experiments synthetic and real-world datasets show the benefit of methods that estimate the uplifts over policies that do not use this structure.
1 Introduction
Multi-armed bandit (MAB) is an important framework for sequential decision making under un- certainty [8, 19, 20]. In this problem, a learner repeatedly takes action and receives their rewards, while the outcomes of the other actions are unobserved. The goal of the learner is to maximize their cumulative reward over time by balancing exploration (sclect actions with uncertain reward estimates) and exploitation (select actions with high reward estimates). MAB has applications in online advertisement, recommender systems, portfolio management, and dynamic channel selection in wireless networks [7].
One prominent question in the MAB literature is how the dependencies between the actions can be exploited to improve statistical efficiency. Popular examples include linear bundits [11] and combinatorial bandits [9]. In this work, we study different structured bandit problem with the following three features: (i) the reward is the sum of the payoffs of fixed set of variables; (ii) these payoffs observed: and (iii) each action only affects small subset of the variables. This structure arises in many applications, as discussed below.
(a) Online Marketing. An ecommerce platform can opt among several marketing strategies (actions) to encourage customers to make more purchases on their website. As different customers can be sensitive to a different marketing strategy, regarding each of them as variable, it is natural to expect that each action would likely affect only a subset the variables. The payoff associated to customer can be for example the revenue generated by that customer; then the reward is just the total revenue received by the platform.
(b) Product Discount. Consider a company that uses discount strategies to increase their sales. is common to design discount strategies that only apply to a small subset of products. In this case, we
Work done during an internship at Amazon.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Algorithm
UCB
UPUCB (b)
UPUCB
UPUCB-nAff
UPUCB-iLif
Affected variables known
No
Yes
Yes
No
No
Bascline payofts known
No
Yes
No
No
No
Km² A
KT,2
KT,2
(cliplA/Aaaaa Amp L, m)²
Regret Bound
A
Table 1: Summary of our regret bounds for uplifting bandits. Constant and logarithmic factors ignored throughout. For simplicity, we assume here all actions affect exactly L of the m variables and all the suboptimal actions have the same suboptimality gap A. and Aup are respectively the number of actions and lower bound on individual uplift (Aup is formally introduced in Appendix E). The operator clip restricts the value of its first variable to the range defined by its second and third variables, clip(rr, a, 3) max(a, min(3, a)))
can view the sales of each product as variable and each discount strategy as an action, and assume that each action only has significant impact on the sales of those products discounted by this action.
(c) Movie Recommendation. Consider bandit model for movie recommendation where actions correspond to different recommendation algorithms, and the variables are all the movies in the catalog. For each user, define set of binary payoff's that indicate whether the user watches movie in the catalog, and the reward is the number of movies from the catalog that this user watches. Since a recommendation (action) for this user contains (promotes) only a subset of movies, it is reasonable to assume that only their associated payoffs are affected by that action.
Our Contributions. To begin with, we formalize an uplifting bandit model that captures the aforementioned structure, with the term uplift borrowed from the field of uplift modeling [15, 22] to indicate that the actions' effects are incremental over a certain baseline. The model is stochastic, that is, the payoff's of the variables follow an unknown distribution that depends on the chosen action. We study this problem under various assumptions baseline payoff of each variable and (2) the set of affected variables of each action. Our first result (Section 3) shows that when both (1) and (2) are known, a simple modification of the upper confidence bound (UCB) algorithm [3] (Algorithm UPUCB (b)) for estimating the uplifts has a much lower regret than its standard implementation. Roughly speaking, when m the number of variables and L is the number of variables affected by each action, we get a ( regret bound instead of (m²)). This results in a major reduction for L < m, and a distinguishing feature of all our results.
the learners' prior knowledge about (1) the
Going one step further, we design algorithms that have minimax optimal regret bounds without assuming that either (1) or (2) is known. When (1) the baseline payoffs are unknown and (2) the affected variables are known, we compute differences of UCBs to estimate the uplifts (Algorithm UP- UCB). In contrast to standard UCB methods, these differences are not high-pro prgb-probabblity upper bounds on the estimated quantity. This construction reflects the fact that the feedback for any single action also provides information about the baseline. When (2) the affected variables are also unknown, we identify them on the fly to maintain suitable estimates of the uplifts. We study two approaches, which differ in what they know about the affected variables. Algorithm UPUCB-nAIf (Section 6) knows an upper bound on number of affected variables, whereas Algorithm UPUCB-iLift (Appendix E) knows a lower bound on individual uplift. Our regret bounds are summarized in Table 1. These results are further complemented with lower bounds that justify the need for our modeling assumptions (Section 4). To demonstrate the generality of our setup and how our algorithmic ideas extend beyond vanilla multi-armed bandits, we discuss contextual extensions of our model in Section 7. The experiments in Section confirm the benefit of our approach.
not optimistic,, in the sense they
Related Work. The goals of both uplifting modeling and MAB is to help selecting the optimal action. The former achieves it by modelling the incremental effect of an action on individual's behavior. Despite this apparent connection between the two concepts, few papers explicitly link them together. We believe that this because uplifting can be solved by classic bandit algorithms with a redefined reward. This approach was taken in [6, 23).
Instead, our paper focuses on bandit problems in which estimating the uplifts improves the statistical efficiency of the algorithms,, and this is made possible thanks to the 'sparsity" of the actions' effects. Prior to our work, sparsity assumptions in bandits primarily concerned the sparsity of the parameter vectors in linear bandits [2, 5, 16]. A notable exception is Kwon et al. [18] who studied a variant of the MAB where the sparsity is reflected by the fact that the number of arms with positive reward is small. Our work is orthogonal to all of these in that we look at a different form of sparsity. As

---

we will see in Section 7, while sparsity in parameter can be cause of sparsity in action effect, the improvement of regret is established with different mechanism.
The additive structure of the reward and observability of individual payoffs also suggest some similarity between our model and that of combinatorial semi-bandits [10, 17, 21]. There, the learner selects at each round a subset of ground items and the reward is generally defined as the sum of the payoff's of the selected items. However, this seeming similarity comes with an important conceptual difference: the set of items, or variables, for which we observe the outcomes are selected in semi- bandits, while for us they are fixed and inherent to the reward generation mechanism. As an example, in Application (c). combinatorial bandit models optimize the number of movies that are watched among the recommended ones, while we also consider movies that are not recommended. In fact, as argued by Wang et al. [24], recommendation is only effective if the user actually watches the movie and would not watch without the recommendation. We refer the readers to Appendix B for more technical details and also comparison with the causal bandit model.
Organization. We introduce our uplifting bandit model along with its various variations in Section 2. Over Sections 3, 5, 6, we provide regret bounds for these variations, with a lower bound presented in Section 4. We discuss contextual extensions in Section 7 and experimental results in Section 8.
2 Problem Description
We start by formally introducing our uplifting bandit model. We illustrate it in Fig. and summarize our notation in Appendix A. Contextual extensions of this model are discussed in Section 7.
A (K, m)-uplifting bandit is a stochastic bandit with K actions and m underlying variables. Each action a E A = {l,..., K) } is associated with a distribution pa on RR" At each round t, the learner chooses an action a, E A and receives reward r; = Eiey (i) where V == {I,..., m) is the set of all variables and y/+ = ke)) ~ pa: is the payoff vector. Our model is distinguished by two assumptions that we describe below.
(I) Limited Number of Affected Variables. Let V V the subset of variables affected by action a and pe be the baseline distribution that the variables' payoff's follow when no action is taken. By definition Da and po have the same marginal distribution on Va = V Va, the variables unaffected by action a.² While the above condition is always satisfied with V = V, we are interested in the case of I,a = card(V* < m, meaning only few variables are affected by a. We define L as uniform bound on T,a, so that max T, < T.. For convenience of notation, we write [T] = (1.....T) T} and Ao = AU(O), where is used for all the quantities related to the baseline.
(II) Observability of Individual Payoff. In addition to the reward rt, we assume that the learner observes all the payoff's (i))ev after an action is taken in round f.
be a random variable with distribution pa, We define (i) = E (i)] and (1) = (1) (e) respectively as the expected value and the noise component of yd (1). We nº (resp. 11") to denote the vector of (μ² (i)kev (resp. (μ (i))ev)))) and refer to ja as the baseline payoffs. The individual uplift associated to a pair (a,1) E A x V is defined as p (i) (t) - p²()), An individual uplift can be positive or negative. We obtain the (total) uplift of an action by summing its individual uplifts over all the variables affected by that action
Uplift and Noise. Let yd
Σ (i)
- xz)))
up
1EV9
Let rd Eiev (i) be the expected reward of an action or of pure observation. We also have ru = r - since (i) = (i) as long as i & vo.
A real-value random variable X is said be Suu-Gaussiian if for all y E R. it holds E(exp(>X)) S exp(a2?2//2) /22). Throughout the paper. we assume that {"(i) is 1-sub-Gaussian for all E Ao and i V. Note that we do not assume that (i)xev are independent, i.c., the elements in the noise vector (S" (e)))) may be correlated, for the following two reasons:
'The terms reward and payoff' distinguish rt and (ve (i))ev.
'If' the actions in fact have small impact on the variables in V", our model is misspecified and incurs additional linear regret whose size is proportional to the impact of the actions on V7, An interesting question is how we design algorithms that adapt to the degree of misspecification.
3

---

IdentiBed
Padding
Actions
Variables
Reward
(a) UPUCB: After suboptimal ac- tion is taken, the confidence intervals of (μ² (i)) and (μ (i)) yyn, shrink (from puple to pink). Hence the uplifting index of decreases while that of increases (from dash solid).
(b) UPUCB-nA (b): To compute the uplifting index of an action, we of variables whose associated confidence intervals not contain the baseline payoff and pad it with the variables with the largest UCBs uplifts.
Baseline
identify
Figure 1: Illustration of the up- lifting handit model. This exam- ple has K 3 actions, variables and each action affects L = 2 variables. Dash lines indi- cate the variables' payoffs follow the baseline distribution po by de- fault.
Figure 2: Explanation about UPUCB and UPUCB UPUCB-nAfis BCCCBBff(( (b) using model from Fig. 1. The five vertical bars correspond to the five actions while the y axis corresponds the value of the payoff.
The independence assumption is not always realistic. In our first example, it excludes any potential correlation between two customers' purchases.
While learner can exploit their knowledge the noise covariance matrix reduce the regret, as for example shown by Degenne and Perchet [12], incorporating such knowledge complicates the algorithm design and analysis. However, believe this is interesting future direction pursue.
Regret. The learner's performance is characterized by their regret. To define it, we denote by a" arg max.e.1 r an action with the largest expected reward and by r* = p = maxaca 7 the largest expected reward. The regret of the learner after 7 rounds is then given by
T Regr = rT Σ y
T 1 1aa= = a)
Σ
Σ
(2)
QEAt=1 t=1
where A r* rd the suboptimality gap of action a. words, we compare the learner's 's cumu- lative (expected) reward against the best we can achieve by taking an optimal action at each round. In the following, we also write A minge A for the minimum non-zero suboptimality gap and refer to it as the suboptimality gap of the problem.
UCB for Uplifting Bandits. The UCB algorithm [4], at each round, constructs upper confidence bound (UCB) on the expected reward of each action and chooses the action with the highest UCB. When applied our model, get a regret of O(Km² log T/ nn-sub-Gaussian (recall that we do not assume independence of the payoffs). However, this approach completely ignores the structure of our problem. As show in Section 3, we can achieve much smaller regret by focusing on the uplifts.
the noise in the reward is
Problem Variations. In the following sections, study several variants of the above basic problem that differ in the prior knowledge about (Pa) )aEAA that the learner possesses.
(a) Knowledge of Baseline Payoffs. We consider two scenarios based on whether the learner knows the baseline payoffs μ = (4 (i)) not.
(b) Knowledge of Affected Variables. We again consider two scenarios based on whether the learner knows the affected variables associated with each action (Va) ) or not.
3 Case of Known Baseline and Known Affected Variables
We start with the simplest setting where both the affected variables and the baseline payoff's are known. To address this problem, we make the crucial observation that for any two actions, the difference in their rewards equals to that of their uplifts. As an important consequence, uplift maximization has the same optimal action total reward maximization, and we can replace rewards by uplifts in the detinition of the regret (2). Formally, write
ri rap max rüp for the largest uplift; then ET r By making this transformation, gain in statistical efficiency because Dt=1
Regr -rupT

---

< T = Ee 100-0((0) (i)) can now be estimated much more efficiently under our notion of sparsity. Since both nº and )a known, directly construct UCB r For this, define for all rounds t E [T], actions E A, and variables E V the quantities
2 2lg((1/8)) No
(i (a, =a} max(1,
N Σ fa, = a], 4 G=V
(3(1)
(3)
where 8' is a tunable parameter. In words, Nř. pg (t), and of represent respectively the number of times that action a is taken, the empirical estimate of 1 (i), and the associated radius of confidence interval calculated at the end of round I. The UCB for action a E AA and variable i Vo at round / is (i) jo (z) + 9-11 We further define of = Eiey (1) -)² (i) as the uplifting index, and refer to UPUCB (b) as the algorithm that takes an action with the largest uplifting index oo each round (Algorithm 3, Appendix A). Here, the suffix (b) indicates that the method operates with the knowledge of the baseline payoffs.
Since UPUCB (b) is nothing but standard UCB with transformed rewards r/ = Eieve, (1) (i)). and E[r]] rup defines exactly the same regret the original reward, a standard analysis for UCB yields the following result.
Proposition 1. Let 8' 6/(2K)). Then the regret of UPUCB (b) (Algorithm 3, Appendix A}, with probability at least - 8, satisfies
((L"))log(2233)
Regr I
Σ AEA:A.50
A" + +
(4)
As expected, the regret bound does not depend on m and scales with 1.2. This is because the transformed reward of action a is only L < m. However, this also comes at a price, as both the baseline payoffs and affected variables need to be known. We address these shortcomings in Sections 5 and On side note, we remark that observing the aggregated payoff Diey' (t( is sufficient for UPUCB (b), but this will not be the case for the other algorithms presented our paper.
The improvement is significant when
Estimating Baseline PayofTs from Observational Data. In practice, the baseline payoff's nd can be estimated from observational data, which gives confidence intervals that (i) lie in with high probability. The uplifting indices can then be constructed by subtracting the lower confidence bounds of p. (i)( from (i). the number of samples n, the widths of the confidence intervals are in O(1/vn) Identification of a" is possible only when the sum of these widths over L variables is at most A, which requires n 1Q(L//A7 Otherwise, these errors persist at each iteration and must be the order of to ensure ((VT) regret.
Gap-Free Bounds. In Proposition 1, we state a high-probability instance-dependent regret bound, and we will continue do so for all the regret upper bounds that we present for the non-contextual variants. This type of result can be directly transformed to bound on E[Regy] by taking ó = 1/T. Following the routine of separating A into two groups depending on their scale, most of our proofs can be modified to obtain a gap-free bound, which is usually in the order of ((I, KT log(T)). We will not state these results to avoid unnecessary repetitions.
4 Lower Bounds
In this section, we shortly discuss the necessity of our modeling assumptions for obtaining the improved regret bounds of Proposition 1. The complete discussion appears in Appendix D.
Intuitively, the regret can be improved both because the noise in the effect of an action is small, and because the observation of this effect does not heavily deteriorate with noise. These two points correspond respectively to assumptions (I) and (II). Moreover, the knowledge on (V*)ae.A allows the learner to distinguish between problems with different structures. Without such distinction, there no chance that the learner can leverage the underlying structure. Therefore, the aforementioned three points are crucial for obtaining (4). Below, we establish this formally for algorithms that are consistent [19] over the class of I-sub-Gaussian uplifting bandits, which means the induced regret of the algorithm on any uplifting bandit with -sub-Gaussian noise satisfies Reg, o(t²) for all >> 0.
5

---

Proposition 2. Let h. be a consistent algorithm over the class of naub-Gaussian uplifting bandits that most uses the knowledge of )as.A. and the fact that the noise is K. m. > O and sequence (T.", ASask ([m) R.)K satisfy A = 0. Assume either of the following holds.
Let
(a) L = m for all a E A, so that in the bandits considered below all actions affect all variables.
(b) Only the reward is observed.
(c) The algorithm x does not make use of any prior knowledge about the arms' expected payoffs (n*) A A (in particular, the knowledge of (V") is not used by T).
Then, there exists 1-sub-Gaussian (K, ml-uplifting bandit whose suboptimality gaps and numbers of affected variables are respectively (A "DEA and Jae such that the regret induced by a on it satisfies: lim imminf--w [| log T
EaEA:A>30 2m
A
Proposition 2 states an instance-dependee lower-bound for a learner that may be equipped with full knowledge of the baseline distribution." 4 Its proof is presented in Appendix D. At this point, what remains unclear is whether similar improvement of the regret still possible when the baseline is unknown when the learner only has access to more restricted knowledge than (V*))e.A- We give affirmative answers to these two questions in the next two sections.
5 Case of Unknown Baseline
In this section, consider the situation where the learner knows the sets of affected variables (V*). but not the baseline payoffs. Since the actual uplift at each round is never observed, the uplifts of the actions can hardly be estimated directly in this case. Instead, we follow two-model approach. Leveraging the fact that pa and po have the same marginal distribution on Va, we can estimate the baseline payoffs by aggregating information from the feedback of different actions. This leads to
2 log(1108) (1)
(.(1) E U. (o) 11i & Vo. max NY)))
(1) = Σ 1 200) =
(5)
Compared to (3), we notice that both No and of are functions of í. This is because for each taken action a, we only increase the counters (i) for those & Va, which causes a non-uniform increase of (i)(i)) Then, by looking at all the rounds that variable i is not influenced by the chosen action, we manage to compute (1 (i), an estimate of (1). To proceed, we define the following UCB
indices for all the pairs (a,i) Ao x V
0
a = 0 and i E NNE Va, if a E A and E Va, otherwise.
(1)
= p (
(1) + G-
(6)
p0 (1) + (0)
The second and the third lines of (6) contain the usual definition of UCBs using the empirical estimates and the radii of the confidence intervals defined in (3) and (5). In the special case that variable is affected by all the actions, it is impossible to estimate (t) but it is enough to compare Ui)) directly against U (i) for any two actions a, a' E A, so we just set (i) to 0 in this case.
We outline the proposed method, UPUCB, in Algorithm 1. The uplifting indices are given by TP = Eieya (i) - (i)). It may be counter-intuittee to compare the differences between two UCBs. Indeed, 7, is longer optimistic estimate of the uplifting effect rap but it captures the essential trade-off between learning action a's payoffs and learning the baseline μOO To provide some intuition, we give an informal justification of UPUCB in Fig. 2a: If a suboptimal action a is taken in round t, the estimates of all (i) move closer to the actual mean from above. As result, T decreases, since all U (i) for E v do. Thus action a less likely to be taken next. Moreover, 7 increases, since (i) decrease for any affected by a" but not a. Thus a" is more likely to be taken next. The effectiveness of UPUCB confirmed by the following theorem.
*Of course, the problem only becomes more challenging if the learner does not know the baseline distribution.

---

Algorithm UPUCB
1: Input: Error probability 8', the sets of variables each action affects (V a E A}
2: Initialization: Take each action once
3: for [= K + 1,.... 7 do
4: Compute the UCB indices following (6)
5: For a E A. set of + -ie (U)(() (t))
6: Select action at E arg max REA
Theorem Let 8/(4KLT). Then the regret of UPUCB (Algorithm with probability least 1 - 6, satisfies:
8(L + L 2 2
Log(44KLT
+ +
Regr
A
AEA:A">0
Idea of proof. The full proof of Theorem is presented Appendix C.2, and proceeds as following.
1. With concentration of measure, we show that with probability 1 6, it holds [ (t) (z) - of and (1) μ (:)] s ef (i) for all relevant estimates. It is thus sufficient show that (7) holds when these inequalities are satisfied.
suboptimal action a can only be taken if its uplifting index larger than that of a", i.e., Eu UP(()) 2 Eieva (Uf (i) UP(()) Rearranging, we get
Σ + 'E
Σ Up(1) 2
Σ UF (1)
Σ U9(1). iEVe
(8)
iEVa
Using the inequalities mentioned in the previous point and A rup Tup bounding the two sides of (8), we deduce A < 22 EiEva (p- (0)
Note that for all i Va \ Va, whenever action is taken, the count of No also increases by 1. We have thus ( 2 N and accordingly ( S ct-1. We then get A < 2(L La c
This allows to bound the number of times that action is taken and conclude.
As in Proposition 1, the regret of Theorem 1 is in O(KT² log T/A). In fact, all decisions in UPUCB are made on uncertain estimates of at most I. variables; thus the statistical efficiency scales with and not m. A detailed comparison with Proposition 1 reveals that the difference is in the order of K (L )2 log T/ A; this is only significant when the optimal actions affect many more variables then the suboptimal ones. Hence, the price of knowing the baseline payoff's is generally quite small.
Case of Unknown Affected Variables
Now study the more challenging setting where the affected variables (V*)ae are unknown to the learner. Proposition states that improvement is impossible the learner does not have any prior knowledge exploit the structure. To circumvent this negative result, we study two weak assumptions motivated by practice: learner has access to (i) an upper bound on the number of affected variables or (ii) lower bound on individual uplift. Due to space constraints, we only present the first setting here and defer the discussion of the other to Appendix E.
For the rest of this section, assume that we know upper bound the number of affected variables (i.e., L 2 max.e. L.). We design algorithms with O(KL log T/ A) regret bounds that takes L input. We consider the cases of known and unknown baseline payoffs.
Known Baseline Payoffs. To illustrate our ideas, we start by assuming that the baseline payoffs are known. We propose optimistic algorithm that maintains UCB on the total uplift with an overestimate the order of L. Let Nř, of, and já (i) defined as (3). The UCB, uplifting indices, and the confidence intervals for each (action, variable) pair (a, i) E A x V are
(1) Af_ (1) ci 1. (1) U. (1) (i), (1) [p ( (i) cf ( + c- (9)
In the rest of the paper, refer pf (i) as the individual uplifting index of the pair (a, i). It is
7

---

Algorithm 2 UPUCB-nAff
1: Input: Error probability 8', Upper bound L on the number of variables that each action affects
2: Initialization: Take each action once
3: for w./.= K + 1....: 7 do
4: Choose be E arg max Nº_1 and compute UCBs and confidence intervals using (9)
5: for a E A do
6: Set V/ +- {iEV: () =
7: For i E V, compute (1) + (1) - U (1)
8:
Set I t max(0, 2L - card (v:)) and 47 arg max cgvVe card(C) Eiec (i())
9: Compute uplifting index of DiEDe uc; (i)
10: Select action a₁ E arg max,
an overestimate of the individual uplift Púp (i). As for C7 (i), is the confidence interval that (i) lies in with high probability. Our algorithm, UPUCB-nAff (b) with nAff for number of affected, leverages two important procedures to compute an optimistic estimate of the uplift rup" identification of affected variables, and padding with variables with the highest individual uplifting indices.
To begin, UPUCB nAff (b) constructs the set of identified variables 1 = f V: (i) & (T) which contained in V with high probability. fact, by concentration of measure, with high probability (i) E (t), in which case (i) & CP (i) indicates E V However, Vi is not also need to provide an upper bound for Eieva,D Dr Map (i), the uplift contributed by the unidentified affected variables. Since the individual uplifting index pf (i) is in fact UCB the individual uplift mip(1) (i) here and card(V") L, we can
guaranteed to capture all the affected variables,
simply choose the L - card( (V:) variables in V Dr with the largest (i). Let us refer to this set as CT. We then get a proper UCB on the uplift of action by computing T Σierp ce (i). This process is summarized in Algorithm 4 in Appendix A and illustrated in Fig. 2b.
Unknown Baseline Payoff'. Now we focus on the most challenging setting, where also the baseline payoffs are unknown. In this case, neither the sets of identified variables nor the uplifting indices of UPUCB-nAff (b) can be defined. We also cannot estimate the baseline payoffs using (5) since the sets of affected variables are unknown. To overcome these challenges, we note that for any two actions a, a' E A, μ and μ² only differ on ya UV" and card(V" UV') I 2L. Therefore, μº and u differ in at most 2L variables, and we recover a similar problem structure by taking the payoffs of any action the baseline.
Combining this idea with the elements that we have introduced previously, we obtain UPUCB-nAff (Algorithm 2). In each round, UPUCB-nAff starts by picking a most frequently taken action b, (Line 4) whose payoffs are treated as the baseline that round. Then, in Line UPUCB-nAff chooses variables that are guaranteed be either in y or yd, This generalizes the identification step of
UPUCB-nAff (b). The individual uplifting indices (i) (i) - (i) are computed in Line 7. The differences of UCBs are inspired by a similar construction in UPUCB. Line 8 constitutes the padding step, during which variables with the highest uplifting indices are selected, and finally in Line 9 we combine the above to get the uplifting index of the action. To see why similar to UPUCB-NI infff (b), suppose that one action has been taken frequently. Then the baseline payoffs are precisely estimated and do not change much between consecutive rounds.
is
Regret. Both UPUCB-nAff (b) and UPUCB-nAF choose O(L) variables for estimating the uplift of an action, and the decisions are based on these estimates. Therefore, the statistical efficiencies of these al algorithms only scale with J. and not m. This in turn translates into an improvement of the regret, as demonstrated by the thcorem below.
Theorem 2.
Let 8' = 62KKmT). Then the regret of UPUCB- (Algorithm 2) (resp. UPUCB- nAff (b). Algorithm 4), with probability at least 1 6, satisfies:
aI 12g(22TT/ +
Regr S
Σ
(10)
A
AEA:A
where 512 (resp. 32) in the above inequality.
8

---

Idea proof. The full proof of Theorem 2 is presented in Appendix C.3. We outline below the main steps to prove the result for UPUCB-nAf(t)..
1. With concentration of measure, with probability 1 - 6 it holds (1) E CC)(). Then, as explained
in the text, D C Va and of is an upper bound on rup: especially Tp" 2 Tup
2. For i $ Di. by definition (i) E C₁. from which we deduce 0 S pl S 26-11
With Di S V
and bg C CV\ Di we can then write
Σ
(E(1)
Σ IEL
(E()) S du + 4LG-11-
NEV; U CT
SEVO
We have also used (V=) & L, caF) & I,, and pf( - 1. (i) + 20--1-
3. Whenever suboptimal action a is taken, we have Ti² 2 7f. Combined with the two previous point we then deduced A < 4Lee-1- Subsequently, we bound the number of times that each suboptimal action a is taken to conclude.
The proof of Theorem is notable for two reasons. First, tracking of the identified variables guarantees that the uplifting index Tf does not overestimate the uplift uu too much. Take UPUCB-nAfT (b) as an example. An alternative to constructing a UCB on rüp to choose the L variables with the highest individual uplifting indices (i). However, this would result in severe overestimate when a negative individual uplift is present. Second, to prove (10) for UPUCB-nAff, we use that the widths of confidence intervals of the chosen b, are always smaller than those of the taken action. This is ensured by taking by as the most frequent action (Line 4 in Algorithm 2).
Contextual Extensions
In this section, we briefly discuss potential contextual extensions of our model; a detailed case study is presented in Appendix F. As in contextual bandits, context is a side information that helps the learner to make a more informed decision, which results in higher reward. To incorporate context, one possibility is to associate each variable with a feature vector (1) E Rd. The subscript t indicates that the context can change from one round another. We also associate each action with function I so that the expected payoff of action a acting on a variable with feature (;,(i)
(i) is f (xx (f)). The round / is then rd (xx) Eiey I (1)) The optimal action in round t is a arg max r (x;) and the regret of a learner that takes the actions (0t) is
expected reward of choosing
given by Regy = Σt= Eiev (xx(()) (i)))
The key structure in our model (Section 2) is that there exists a baseline payoff vector 2 such that for any given action a, μ² (t) 14 (i) holds for most i V. Given context, this translates into the existence of a baseline function fo such that for any given a and t, (1) = (xx holds for most i V. The uplift of action is defined ri ( = Σiev
- (z.
For concreteness, let us consider model with linear payoffs. Then, each action associated with an unknown parameter H and the expected payoff is the scalar product of 6 and the feature of the variable, i.e., (z,(() (i))= = (0", xz (i)). We also assume the aforementioned equality to hold for the baseline function fd and we use 1 ii V (0", .I)( + (0", xx. xi)) } for the variables affected by action a at round f. One sufficient condition for Vi to be small is sparsity in both the parameter
difference 0e = 0 0 and the context vector (i). In fact, (0e, .z, (i)) (00, æ (i)) as long as the supports of 6hp and z, (i) are disjoint. We assume card(V?)) is uniformly bounded by L below.
Clearly, our algorithms can be directly applied as long as we can construct a UCB on (0". .x2 (i)). This can for example be done using the construction of linear UCB [1]. In this way, the decision of the learner is again based on the uncertain estimates of at most O(L) variables, and we expect similar improvements as our earlier theorems. As an example, when both 0 and Vi are known, UPUCB (b) adapted to this situation constructs UCB for Eieve (0p.- =r(()), and it is straightforward
to show that the regret of such algorithm can be as small as O(LdvKT In contrast, if the leamnrr works directly with the total reward, the regret is in LmdvKT).
'we present gap- free bounds here and thus we get L versus m in the place of 2 versus m². As in previous sections, these bounds apply to potentially dependent noise.

---

8 Numerical Experiments
In this section, we present numerical experiments to demonstrate the benefit of estimating uplifts our model. We compare our methods introduced in Sections 3, 5 and 6 against UCB and Thompson sampling with Gaussian prior and Gaussian noise that only use the observed rewards (rt))t(T- To ensure a fair comparison, we tune all the considered algorithms and report results for the parame- ters that yield the best average performance. The detailed procedure, and additional experimental details and results, are provided in Appendices and H. The experiments for the contextual extension in Section 7 are presented in Appendix F.3.
LCB
UpUCB (b)
Upuco
UpUCB-AAT AAI
Regrat
Upucc--M
Thampson
x10
(a) Gaussian uplifting
Gaussian Uplifting Bandit. We first study our algo- rithms a Gaussian uplifting bandit with K m 100 variables, and 7, = 10 for all E A meaning that each action affects 10 variables." The expected pay- off's contained in [0, 1]. and the covariance matrix of the noise is taken the same for all the actions. The subop- timality gap of the created problem is around 0.2, and the variance of the total noise Σiev (i) is around 80.
Regret
actions,
4 to
Thompson sampling
Pterations
(b) Bernoulii uplifting
Figure 3: Experimental results on a synthetic and real-world dataset. All the curves are averaged over 100 runs and the shaded areas represent the standard errors.
Bernoulli Uplifting Bandit with Criteo Uplift. We use the Criteo Uplift Prediction Dataset [13] with 'visit' as the outcome variable to build Bernoulli uplifting bandit, where the payoff of each variable has Bernoulli distribu- tion. This dataset is designed for uplift modeling, and has outcomes for both treated and untreated individuals. Thus it is suitable for our simulations. To build the model, we sample 10a examples from the dataset, and use K-means to partition these samples into 20 clusters of various sizes. The 10a examples are taken as our variables. We consider 20 actions that correspond to treating individuals of each cluster, and construct independent Bernoulli payoff's using the visit rates of the treated/untreated individuals of the clusters following a procedure detailed in Appendix G.2. Here, L = 12654 and A around 30.
Results. Fig. confirms that we can effectively achieve much smaller regret by restricting our attention to the uplift. Moreover, when the sets of affected are known, the loss of not knowing the baseline payoffs seems to be minimal. On the other hand, not knowing the affected variables has more severe effect in the second experiment. In fact, the design of UPUCB-nA nAff (b) heavily rely on the additive structure of the uplifting index, and can thus hardly benefit from the payoff independence which allow the other four algorithms to achieve smaller regret in this case.
and UPUCB-
This paper studies multi-armed bandit problems where the rewards are sums of observable variables. When each action only affects a limited number of these variables, much smaller regret can be achieved, and we developed algorithms with such guarantees under different forms of knowledge that the learner possesses.
While study here UCB-style algorithm, believe that understanding how similar improvement can be achieved by other types of algorithms such as Thompson sampling and information directed sampling is an important question. Moreover, further extending our work to cope with non-stationary or even adversarial bandits is another promising direction to pursue. As for the former, a direct combination with existing techniques [14] can readily make our algorithms bypass the stationarity assumption that we make throughout the paper.
References
[1] Yasin Abbasi- Yadkor, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in Neural Information Processing Systems, 24:2312-2320, 2011.
'y Gaussian uplifting bandit mean that the noise vectors (E") Gaussian.
10

---

[2] Yasin Abbasi- Yadkori. David Pal, and Csaba Szepesvari. Online-to-contiunn co--oofidence-se conversions and application to sparse stochastic bandits. In Artificial Intelligence and Statistics, pages 1-9. PMLR, 2012.
[3] Peter Auer. Using confidence bounds exploitation-exploratio trade-offs. Journal of Machine Learning Research, 3(Nov).397-422, 2002.
[4] Peter Auer, Nicolo Besa-Bianchi, and Paul Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-2560 2002.
[5] Hamsa Bastani and Mohsen Bayati. Online decision making with high-dimensional covariates. Operations Research, 68(1):276-2944 2020.
[6] Jeroen Berrevoets, Sam Verboven, and Wouter Verbeke. Treatment effect optimisation in dynamic environments. Journal of Causal Inference, 10(1):106-122, 2022.
[7] Djallel Bouneffouf, Irina Rish, and Charu Aggarwal. Survey on applications of multi-armed and contextual bandits. In 2020 IEEE Congress on Evolutionary Computation (CEC), pages 1-8. IEEE, 2020.
[8] Sébastien Bubeck and Nicolo Cesa-Bianchi Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Machine Learning, 5(1):1-122, 2012.
[9] Nicolo Cesa-Bianchi and Gábor Lugosi. Combinatorial bandits. Journal of Computer and System Sciences, 78(5): 104--422, 2012.
[10] Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In International Conference Machine Learning, pages 151-159 PMLR, 2013.
[11] Varsha Dani, Thomas P Hayes, and Sham M Kakade. Stochastic linear optimization under bandit feedback. In Conference on Learning Theory, pages 355-366, 2008
[12] Rémy Degenne and Vianney Perchet. Combinatorial semi-bandit with known covariance. In Advances in Neural Information Processing Systems, pages 2972-2980, 2016.
[13] Eustache Diemert, Artem Betlei, Christophe Renaudin, and Massih-Reza Amini. A large scale benchmark for uplift modeling. In International Conference on Knowledge Discovery and Data Mining. ACM, 2018
[14] Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In International Conference on Algorithmic Learning Theory, pages 174-188. Springer, 2011.
[15] Pierre Gutierrez and Jean-Yves Gérardy. Causal inference and uplift modelling: A review of the literature. In International Conference Predictive Applications and APIs, pages 1-13. PMLR, 2017.
[16] Botao Hao, Tor Lattimore, and Wei Deng. Information directed sampling for sparse linear bandits. In Advances in Neural Information Processing Systems, 2021.
[17] Branislav Kveton, Zheng Wen, Azin Ashkan, and Csaba Szepesvari. Tight regret bounds for stochastic combinatorial semi-bandits. Artificial Intelligence and Statistics, pages 535-543. PMLR, 2015,
[18] Joon Kwon, Vianney Perchet, and Claire Vernade. Sparse stochastic bandits. In Conference on Learning Theory, volume 65, 2017.
[19] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in applied mathematics, 6(1):4 22, 1985.
[20] Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.

---

[21] Pierre Perrault, Etienne Boursier, Michal Valko. and Vianney Perchet. Statistical efficiency of thompson sampling for combinatorial mani-bandits. Advances in Neural Information Processing Systems, 245429-5440, 2020.
[22] Nicholas Radcliffe. Using control groups to target predicted lift: Building and assessing uplift model. Direct Marketing Analytics Journal, pages 14-21, 2007.
[23] Neela Sawant, Chitti Babu Namballa, Narayanan Sadagopan, and Houssam Nassif. Contextual multi-armed bandits for causal marketing. In International Conference Machine Learning. 2018.
[24] Yixin Wang, Dawen Liang, Laurent Charlin, and David M Blei. Causal inference for recom- mender systems. In Fourteenth ACM Conference on Recommender Systems, pages 426-431, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We have discussed potential extensions, which reflects the limitation of the current work.
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms them?
[Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as URL)? [Yes] Provided in the supplmental material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section and Appendices F.3, G and H.
(c) Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)? [Yes]
(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)? [Yes] See Appendix G
4. If you are using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See Appendix G
(c) Did you include any new assets either in the supplemental material or URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [No]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applica- ble? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "cKo2CIDrUM", "reviewer": "Reviewer_H2gA", "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.\n\nTo 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.", "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.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "#### **Strengths of paper:**\n1. 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.\n\n2. 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.\n\n3. The authors have empirically validated the different performance aspects of the proposed algorithms. \n\n\n#### **Weakness of paper:**\n1. 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).\n\n2. 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. \n\n3. 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).", "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": "aW6uQCsW1U", "reviewer": "Reviewer_b8e3", "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. \nThe 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.", "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?\n\nHow 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.\n\nCan 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?\n\nIs 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.\nI do believe the authors did not adequately discuss the limitations of their work.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Disclaimer: I have not read the Appendix.\n\nStrengths:\n- The problem of detecting \"uplift\" is relevant in practice\n- The paper tackles 3 variation of this setting where different information is given\n- Interesting approach to examine differences of UCBs among CTRs in Algorithm 1 (UpUCB)\n- The setting with unknown affected variables is the most significant of the ones presented here for practitioners\n-  Numerical experiments show expected performance gain against a common-sense baseline.\n\nWeaknesses:\n- 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.\n- 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.\n- 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.\n- 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).\n- 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.", "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": "4xc7k2fslt", "reviewer": "Reviewer_xacy", "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. ", "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.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Introduces a bandit framework that better models some applications mentioned in the paper\n- The paper is clearly written and the illustrations make the dense material easy to follow\nWeaknesses:\n- 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\n\nL122: achieve (typo)\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": "3Gdo5cJ3D9", "reviewer": "Reviewer_wS6g", "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.\n", "questions": "See above.", "limitations": "Yes.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "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?\n\nCan 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)?\n\nSince 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).", "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