Contextual Combinatorial Multi-output GP Bandits with Group Constraints
Authors: Sepehr Elahi
Baran Atalar
Sevda Öğüt
Cem Tekin
Venue: Accepted by TMLR ()

Abstract: In federated multi-armed bandit problems, maximizing global reward while satisfying minimum privacy requirements to protect clients is the main goal. To formulate such problems, we consider a combinatorial contextual bandit setting with groups and changing action sets, where similar base arms arrive in groups and a set of base arms, called a super arm, must be chosen in each round to maximize super arm reward while satisfying the constraints of the rewards of groups from which base arms were chosen. To allow for greater flexibility, we let each base arm have two outcomes, modeled as the output of a two-output Gaussian process (GP), where one outcome is used to compute super arm reward and the other for group reward. We then propose a novel double-UCB GP-bandit algorithm, called Thresholded Combinatorial Gaussian Process Upper Confidence Bounds (TCGP-UCB), which balances between maximizing cumulative super arm reward and satisfying group reward constraints and can be tuned to prefer one over the other. We also define a new notion of regret that combines super arm regret with group reward constraint satisfaction and prove that TCGP-UCB incurs $\tilde{O}(\sqrt{KT\overline{\gamma}_{T}} )$ regret with high probability, where $\overline{\gamma}_{T}$ is the maximum information gain associated with the set of base arm contexts that appeared in the first $T$ rounds and $K$ is the maximum super arm cardinality over all rounds. We lastly show in experiments using synthetic and real-world data and based on a federated learning setup as well as a content-recommendation one that our algorithm performs better then the current non-GP state-of-the-art combinatorial bandit algorithm, while satisfying group constraints.

Published in Transactions on Machine Learning Research (06/2023)
Contextual Combinatorial Multi-output GP Bandits with Group Constraints
Sepehr Elahi
sepehr.clahi@eppt.c
School of Computer and Communication Sciences
EPFL
Baran Atalar*
batalar@onddew.coma
Deportment of Electrical and Compuler Engineering Carnegie Mellon University
Sevda Ögütt
seuda.ogut ogpfff
School of Computer and Communication Sciences
EPFL
Cem Tekin
cemtekin@ee. bilkent. edu.
Department of Electricol and Electronics Engineering
Bilkent University
Reviewed on OpenReview: https: openreview. net/ pormformm? id- Ogb
Abstract
In federated multi-armed bandit problems, maximizing global reward while satisfying mini- mum privacy requirements to protect clients is the main goal. To formulate such problems, we consider a combinatorial contextual bandit setting with groups and changing action sets, where similar base arms arrive in groups and a set of base arms, called super arm, must be chosen in each round maximize super arm reward while satisfying the constraints of the rewards of groups from which base were chosen. To allow for greater flexibility, we let each base arm have two outcomes, modeled the outpul of two-oulput Gaussian process (GP), where one outcome is used to compute super arm reward and the other for group reward. We then propose novel double-UCB GP-bandit algorithm, called Thresholded Combinatorial Gaussian Process Upper Confidence Bounds (TCGP-UCB), which balances between maximizing cumulative super arm reward and satisfying group reward raints and can be tuned to prefer one over the other. We also define new notion of regret that combines super regret with group reward constraint satisfaction and prove that TCGP- UCB incurs Ó (X)) regret with high probability, where 7r is the maximum information gain associated with the set of base arm contexts that appeared in the first T rounds and K is the maximum super arm cardinality over all rounds. We lastly show in experiments using synthetic and real-world data and based on a federated learning setup as well as content-rcommendation one that our algorithm performs better then the current non-GP stato-of-the-art combinatorial bandit algorithm, while satisfying group constraints.
1 Introduction
The multi-armed bandit problem is a prominent example of reinforcement learning that studies the sequential interaction of learner with its environment under partial feedback (Robbins, 1952). Out of the many
"The majority of the work was done when Sepehr Flahi, Baran Atalar and Sevda Ogüi were with the Department of Electrical and Electronics Engincering Bilkent University.
Equal contribution.

---

Published in Transactions on Machine Learning Research (06/2023)
variants of the multi-armed bandit problem, the combinatorial and contextual bandits have been thoroughly investigated due to their rich set of real-life ionss. In combinatorial bandits, the learner selects a super arm, which is a subset of the available base arms in each round (Chen et al., 2013; Cesa-Bianchi & Lugosi, 2012). In the semi-bandit foedback model, at the end of the round, the learner observes the outcomes of the base arms in the selected super arm logether with the super arm reward. In contextual bandits, at the beginning of every round, the learner observes side-information about the outcomes of the base arms available in that round before deciding which arm to select (Slivkins, 2011; Lu al., 2010). In the changing action set variant, there is varying base arm availability in each round. Combinatorial bandits and contextual bandits are deployed in applications ranging from influence maximization in a social network to news article recommendation (Li et al., 2010; Chen et al., 2016b).
In this paper, we consider contextual combinatorial multi-armed bandits with changing action sets (C3-MAB), which models the repeated interaction between an agent and its dynamically changing environment. In each round t, the agent observes the available basc arms and their contexts, selects a subset of the available base arms, which is called a super arm, collects a reward, and observes noisy outcomes of the selected base arms. We consider the scenario in which the base arm availability in each round changes in an arbitrary fashion, known as the changing action sets setting. Therefore, we analyze the regret under any given sequence of base arm availabilities. On the other hand, given a particular base arm and its context, the outcome of the base arm is assumed to come from a fixed distribution parameterized by the arm's context. The goal is to maximize the cumulative reward in a given number of rounds without knowing future context arrivals and the function that maps the contexts to base arm outcomes. Achieving this goal requires careful tuning of exploration and exploitation by adapting decisions in real-time based on the problem structure and past. history. What is new in our sctup is the concept of groups, which are unions of basc arms that share common feature. Our goal is to maximize the cumulative super arm reward while ensuring that the groups comprising the super arm satisfy their constraints.
It is essential to place assumptions on the function mapping contexts to outcomes (i.c., the function that needs to be learned, say f). While other C3-MAB works such as (Nika et al., 2020; Chen et al., 2016;; 2018) place explicit smoothness restrictions on f, we make use of Gaussian processes (GP), which induce smoothness assumption. Morcover, the postcrior mcan and variance resulting from GP gives us high probability confidence bounds on the expected outcome function which leads to a desirable balance between exploration and exploitation (Srinivas et al., 2012).
Our work, and specifically introduction of groups, is motivated by the need to balance between privacy and reward in a federated learning setup. Federated learning (FL) is a distributed machine learning method that allows for training a model across a decentralized ensemble of clients. In FL., clients train a model on their local data and then send their local model to a centralized server. This helps protect the privacy of clients as they do not share their data directly with the server (McMahan et al., 2017). Our work introduces setup that can handle privacy aware FL, where clients have privacy requirements on the maximum amount of data leakage through local model or weight transfer to the server. This is important, as some portions of a client's 's training data can be retrieved just from their shared gradients with the server (Melis et al., 2019; Chen & Campbell, 2021).
In our sctup, base arms represent client-request pairs, groups are clients, and super arms are subsets of client-request pairs. For each such pair, the context is related to the amount of information that the client is to share with the server, specifically, it is the used data set percentage which determines the privacy level of the client. Our aim is to satisfy clients' privacy requirements while maximizing the information obtained from the client's trained model. There is a trade-off between these two goals as using higher percentage of data in training leads to less privacy for clients due to information leakage but a greater amount of information is retrieved from the data by the server. This is also mentioned in (Truong et al., 2021) as a trade-off between efficiency and privacy guarantee and in (Yang et al., 2019) as a trade-off between learning performance and privacy of clients.
This trade-off has motivated us to model the expected outcome function a sample from two-output GP, in order to make use of the inherent correlation between privacy leakage and the information retrieved. The
2

---

Published in Transactions on Machine Learning Research (06/2023)
details of how two-output GP helps us as well a detailed explanation of the application of our problem formulation to a privacy aware federated learning is given in Section 2.8.
1.1 Our contributions
Our contributions are: (i) We propose a new C3-MAB problem with groups and group constraints that is applicable to real-life problems, including a privacy-awars federated learning setup where the goal is to maximize overall reward while respocting users' varying privacy requirements. (ii) We propose a now notion of regret called group regret, and define lotal regret as a weighted combination of group and super arm regret in terms of Ç E [o, 1]. (iii) We use a two-output GP which allows for modeling setups where overall reward and group reward are functions of two different but correlated base arm outcomes. (iv) We use a double UCB approach in our algorithm by having different exploration bonuses for groups and super arms which is dependent on a tunable parameter. (v) We derive an information theoretic regret bound for our algorithm given by (V(((K))77))
By assuming a fixed cardinality for every super arm, we express our regret bound in terms of the classical maximum information gain ?T which is given as ÖlVx+(K)KTT), We also provide kernel-dependent upper bounds of our regret for standard GP kernels.
1.2 Related Work
The combinatorial multi-armed bandit problem has been thoroughly investigated by using upper confidence bounds (Gai et al., 2012; Chen et al., 2013; 2016b) and Thompson sampling algorithms (Wang & Chen, 2018). While we also use a UCB type algorithm, we have groups and group constraints and we operate in a contextual combinatorial setting instead of a solely combinatorial one. In terms of the regret bounds, (Chen et al., 2013; 2016b; Wang & Chen, 2018) incur Ollo T) gap-dependent regret whercas we incur Ö(VT) gap-independent regret. Another variant of the classical bandit, problem which emerged in recent years is the contextual combinatorial multi-armed bandit problem (CC-MAB) (Li et al., 2016; Qin et al., 2014). In the work of (Li et al., 2016), the learner can observe the reward of the super arm and the rewards of a subset of the base arms in the super arm selected due to cascading feedback according to some stopping criteria. In the work of (Qin et al., 2014), the contextual combinatorial MAB problem is applied to online recommendation.
The contextual combinatorial multi-armed bandits with changing action sets problem has been explored in (Chen et al., 2018; Nika et al., 2020). In the work of (Chen et al., 2018), the super arm reward is submodular and since the context space is infinite, they form a partition of the context space with hypercubes depending context information thus addressing the varying availability of arms by exploiting the similaritics between contexts in the same hypercube. The work done by (Nika et al., 2020) makes use of adaptive discretization instead of fixed discretization which addresses the limited similarity information of the arms that can be gathered by fixed discretization.
GP bandits have been utilized in the combinatorial MAB and contextual MAB setup as well as for adaptive discretization (Nuara et al., 2018; Krause & Ong, 2011; Shekhar al., 2018). In the combinatorial MAB setting of (Nuara et al., 2018), it has been shown that discretization works in small action spaces and GPs are used to estimate the model. While adaptive discretization has been shown to be working well in large context spaces and setups with changing action sets, in the case where the number of base arms is finite, assuming the expected base arm outcomes are sample from a GP could be a better approach as it eliminates the need for the explicit assumption that the expected base arm outcomes are Lipschitz continuous. In this paper we also use the smoothness induced by GP instead of performing explicit discretization. A comparison of our problem sctup with other similar works can be found in Table 1.
The thresholding multi-armed bandit problem has been studied in (Locatelli et al., 2016; Mukherjee et al., 2017). These works consider thresholding as having the mean of base arm be above certain value. In (Reverdy et al., 2017), there is the notion of satisficing instead of thresholding, which is a combination of satisfaction, which is the learner's desire to have a reward above a threshold and sufficiency, meaning to have satisfaction for base arms at a certain level of confidence. To our knowledge, there is no previous research which deals with group thresholding or thresholding sctup within the C3-MAB problem. A similar line of research includes that of safety in the multi-armed bandit problem where the action set constrained such that safety constraint is satisfied (Amani et al., 2019; Wang et al., 2021). However, their definition of safety
3

---

Published in Transactions on Machine Learning Research (06/2023)
Table 1: Comparison of our problem setting with previous works (CC stands for contextual-changing action scts).
Work
Context space
CC
Smoothness
Groups
Group thresholds
(Chen et al., 2013)
Finite
No
Explicit
No No
CChen et al., 2018)
Infinite
Yes
Explicit
No
No
(Krause & Ong, 2011)
Compact
No
GP-induced
No
No
(Nika et al., 2020)
Compact
Yes
Explicit
No
No
This work
Compact
Yes
GP-induced
Yes
Yes
is different than the notion of satisfying that we use in the paper. In these papers, the safety constraint is imposed such that it allows for violation of the constraint whereas we can violate threshold in some steps, which leads to incur regret. The tradeoff however is that we are able to explore faster compared to these works though it is not fair to make a comparison our setup and results are not exactly comparable due to different notions of thresholding and also because we are not doing best arm identification. Comparing with the regret bounds of (Amani et al., 2019) they achieve Õ(VT) regret (same as ours) when the safety gap is positive and O(T2/3) regret when the safety gap zero.
Federated learning was proposed by (MeMahan al., 2017) as technique to address privacy and security concerns regarding centralized training performed in main server by collecting private data from the clients. To solve this issue, they propose the FedAvg algorithm that performs local stochastic gradient descent for each client and averages the models from the clients on the main server to update the global model. The work in (Wei et al., 2020) discusses information leakage in federated learning and presents the algorithm NbAFL that works based on the concept of differential privacy by adding artificial noises to the parameters of the clients before aggregating the model. Note that although our setup is motivated by privacy aware FL, our work not positioned in the FL space and thus our algorithm competes with C3-MAB algorithms and not the likes of NbAFL.
2
Problem Formulation
2.1 Base Arms and Base Arm Outcomes
The sequential decision-making problem proceeds over T rounds indexed by / E [T] (1....,Ty In each round t, MM base arms indexed by the set M2 = [M]] arrive. Cardinality of the set of available base arms in any round is bounded above by M < co. Each base arm m E Me comes with a context Zt,m that resides in the context set X. The of available contexts round denoted by X₂ = {=r,m)me..
When selected, base with context yields two-dimensional random outcome r(x) R The two-dimentionalltyy of the outcome will be motivated by groups in Section 2.2. We will refer to the first and second component of r(z) by rz( and r2(z), respectively. From hereon, we refer to the individual components a vector using subscripts. Then, the expected outcome function that is unknown to the learner is represented by f X R2, whose form will be described in detail in Section 2.5. We then define the random outcome as r(x) = f(x) (t)= + where 7 ~ ~O, o2)) represents the two-dimensional observation noise that independent across base arms and rounds, where is known. In our motivating example of federated learning, basc arms represent client-request pairs while the first base arm outcome is the amount of information that the server is able lo retrieve from the client while the second one is the information leakage probability associated with each client-request pair. The context associated with each base arm corresponds to its data set usage percentage.
2.2 Super Arm and Group Rewards
For any vector-valued function h: X Rdd d 2 2, given a k-tuple of contexts x [ai...., [x...., we let h.(x))),
h(x:) = [h(x))...,,h(e Moreover, let ha())) [bx(x1), (((())))...,((()))) where the subscript $ i < d
4

---

Published in Transactions on Machine Learning Research (06/2023)
indicates the ith element. We denote by S 2Mz the set of feasible super arms in round i, which is given to the learner, and by S = U2218 the overall feasible set of super arms. We assume that the maximum number of base arms in super arm does not exceed a fixed K E N that is known to the learner. That is, for any S E S, we have, |S| < K. We denote the super arm chosen in round by St-
The reward of a super arm S S depends on the outcomes of base arms in S. We represent the contexts of the base arms in super arm S by the context vector æt.s and the reward of super arm S by random variable USS ri (zr,s)), where U is deterministic function. Moreover, we have that the expected super arm reward is a function of only the set of base arms in S and their expected outcome vector, given by uS, fi( = ESU (f. We assume that for all S E S, the expected super arm reward function u is monotonically non-decreasing with respect to the expected outcome vector. We also assume that u varies smoothly as a function of expected base arm outcomes. Both assumptions are standard in the C3-MAB literature (Nika et al., 2020) and are stated formally below.
A Assumption (Monotonicity). For all S E and for any h = 1 if hm S 9m, Vm < (S], then w(S, h) S u(S.g).
E TR and g = [m,,-.. -... e
Assumption 2 (Lipschitz continuity). For all 8 E S, there erists B' > 0 such that for any [ M|s1 E TRIST and = (,,,..,,,................... 9|s] E RISI, we have (u(S, () & B E' 1hg - gEl-
Groups are defined as the sets of base arms (i.e., client-request pairs) from the same client and they have round-varying cardinalities due to changing action sets. We denote by G, the set of feasible groups in round and the reward of a group G E Ge depends on the second outcome of the base arms in G St. Let L2,G represent the vector of contexts of base arms in G.² We only have one restriction on the set of arriving groups, and that disjointness, given below.
Assumption 3 (Group disjointness). For any round L, we have that all groups in Ge are puirwise disjoinl.
We represent the reward of a group G by the random variable (C(GGnS,,22a0,,. of a group depends on the observed base arms since the observed base arm outcomes in a group are ones that belong to the chosen super arm. We stress that VG here is a deterministic function of its argument and the randomness comes from r2- As typical in the CMAB literature, given the base arm outcome function f, we assume that expected group reward is function of only the set of base arms in G GnS, and their expected outcome vector. Therefore, we define to n St, (a(xx,ans))) B[VG n St, (as,, and og are vector functions and take as input G n Sel dimensional vector. 3 Lastly, similar to the super arm reward function, we impose monotonicity and Lipschitz continuity assumptions ions on the group reward function.
Notice that the reward
Note that Vo
Assumption 4 (Monotonicity). For all A C G, for all G E Gr, and for all t E [T] and for any h = [hI..... ||1l E || and g = .9.4) E BlAi, if hm I Im. Vm S IA], then vg S va(g).
Assumption 5 (Lipschitz contimuity). For all A C G, for all G E G. and for all L E [T], there erists B > 0 such that for any h = [ A1)" E RIAI and g = [g] . AI)" E AR we have (va(h) - vG (g) S |4 BA EA1 [h. - gel-
We define B =
BA, which will be later used in proofs. In federated learning, group reward is related to the information leakage probability of each base arm in a group. Therefore, it represents the privacy level of a client.
max
VAGG, vEEly
In line with prior work (Nika et al., 2021), we assume that the learner knows and vg for all G perfectly, but does not know f beforehand. We propose extended semi-bandit feedback model, where when super arm S, is selected in round t, the learner observes Urr((xs)) Vo(r2(2ans.)) for G E G. and r(z,,,) for m E S at the end of the round.
We will suppress S from U(S.... and u(S....) when S is clear from context,
We will drop from 25 when clear from context. We will suppress G St from Vn Sty...) and me(G n S6,.... when clear from context.
5

---

Published in Transactions on Machine Learning Research (06/2023)
2.3 Regret
Our learning objective is to choose super arms that yield maximum rewards while ensuring that the groups containing the base arms of the chosen super arms satisfy a certain level of quality, which is characterized by the group threshold. In accordance with our goal, we define regret notions for both super arms and groups. In our regret analysis, as typical in contextual bandits (Nika et al., 2020), we assume that the sequence (X, St, S., 9-) is fixed, hence context arrivals are not affected by past actions. We assume that each group G E G. has a threshold Tr which represents the minimum reward that the group requires when one or more of its forming base arms are in the chosen super arm. For instance, in federated learning, It represents the minimum desired privacy level of each client, specifically the probability that the client's data does not. leak. This is important as we want to maintain privacy for clients during training. We say that group G' E 9: satisfies its threshold when va(f2(xans 2 Tt. We then define the group regret as
T
(T)
Σ Im GE9
h (ooo-oo[((xooss))-
where [+4 == max 03.
Let S; S S, represent the set of super whose forming base arms' membering groups satisfy their thresholds, mathematically given by S = {S S V(G E Gr), vo (a(a 2 7.a). The super arm regret is defined as the standard a-approximation regret in CMAB:
(T( a Σ (f.) Eu(h(orss)),
E=1
where opt (ft) = maxses; u(Ji For this definition to make sense, we impose the following assumption. Assumption 6 (At least one good super arm). Given a round t, have that St # 0.
The assumption above is reasonable assumption for real-world scenario, we are simply requiring that there exists at least one super arm whose forming base arms satisfy their respective groups. Further note that any optimal super arm St E arg maxses; ul u(fi( (xx,s)) is restricted to satisfy all its corresponding groups and this will be further explained in Section 2.4.2. Otherwise, the policy which always selects the optimal super arms will incur linear group regret.
The total regret is defined as a weighted combination of group and super arm regrets. We have been inspired by the scalarization approach (Boyd & Vandenberghe, 2004) which has been used in multi-objective reinforeement learning (Van Moffaert et al., 2013) and in multi-objective multi armed bandits (Yahyaa et al., 2014). We use similar regret definition to that in (Yahyaa et al., 2014) where they use scalarized regret for multi-objectives. This is also applicable to our case as we want to balance between prioritizing super arm reward and group reward. Given the trade-off parameter E [0, 1], we define it as
R(T) = (R) -1 (T).
(1)
Setting <= 1 reduces the problem to satisfying problem in a combinatorial setup, while setting ( = 0 reduces the problem to regret minimization in standard CMAB (Chen et al., 2013).
2.4 Computation Oracle
In the traditional C3-MAB setting where group constraints are not considered, there cxists one optimization problem, namely identifying a super arm to play in each round (Chen et al., 2016a; Nika et al., 2020). However, in our new setup where group constraints are considered, an additional optimization problem needs to be solved identify super arms whose comprising groups i.c., the groups that the basc arms of the selectod super arm belong to satisfy their constraints. To do so, first we identify good subgroups and then filter out the super arms whose intersections with groups is not good subgroup.

---

Published in Transactions on Machine Learning Research (06/2023)
2.4.1 Identifying Good Subgroups
We define a good subgroup of G to be any subset of G that satisfies G's constraint. For instance, given G = 2,, 3, 4}, YG = 6, and VG being the sum operator, then the following subsets are all good subgroups as they all satisfy the constraint: [2, (3,4), (1, 4), (2, 4), (1,3, 4), 21, 3, 4]. Then, given that f.. is the estimate of the base arm outcome used for computing group reward, f2, in round t, the good subgroup identification problem in round can be formally expressed as identifying the set Gr.good defined as E Gr.oood (G' E Ge
and (f n, }. Thus, in round t, we have Gi.oodd Oraclegap(fi.
2.4.2 Identifying the Optimal Super Arm
Once Gt.good is identified, the next task is to identify the super arm that yiclds the highest reward. Using the set of good subgroups returned by Oraclegp, the optimization problem of finding the optimal super arm in round t, St, given the estimate of the base arm outcome used for computing super arm reward, fú,1, can be written as S, arg max ( | E S and AG E Gr, SnG Gr.gooa In other words, S, the super arm that yields the highest reward calculated using fr,1 and whose interscctions with any group is a good subgroup (i.c., satisfics that group's constraints). Note that if ft.good is computed to be 0 then Sy is simply the super arm that yields the highest reward. Then, we make use an a-approximate oracle, called Oraclespe; where u(fi.1 (1,, Oraclee.p (f.,)) 2 ax opt(fr.1. Our algorithm, which will be described in detail in Section 3, will make use of both oracles. Lastly, it should be noted that both oracles are deterministie given their inputs.
2.5 Structure of Base Arm Outcomes
To ensure that the learner performs well, some regularity conditions necessary f. For our paper, we model f as sample from two-output GP, defined below.
Definition 1. A luooouupull Ganssian Process with index set X is collection of 2-dimensional random variables (f(x))xex which satisfy the condition that (f(x1)...., (2x)) has a multivariate normal distribution for all (x,,...,,,, and n N. The probability law of the GP is governed by its vector-valued mean function given by x + p(z) [z)] E I22 and its matriz matria-valued valued covariance function given by (2) + k(x1, = [[(((x)) (f
(T] R2x2
We assume that we have bounded variance, that is, (x, S 1 for every E X and j E (1,2). This is standard assumption generally used in GP bandits (Srinivas et al., 2012).
2.6 Posterior Distribution of Base Arm Outcomes
Our learning algorithm will make use of the posterior distribution of the two-oulput GP-sampled function f- Given a fixed N N we consider a. finite sequence क[N] = ".b....,,]]] of contexts with corresponding outcome vector (2N-dimeesionaa) Fin] == [r(T)) ,...,,........ ("" and the corresponding expected outcome vector -2N-dimensoonal) fiNj (T .....
"(N)"" "TT. For every n N, we have r(ä.) f(ā)) + n. where nr is the noise corresponding to that outcome. The posterior distribution of f given r(v] is that of a two-output GP characterized by its mean μn and its covariance by which are given as follows:
(N()) = (KiN (+)) +02l2N) "[N-] K (N - k(ī, (K) o I2N) (xx))"k (T')
Here (+) = (1(8,,))... k(E, E R2X2N and
((ū1,
k k(ā,,ūN)
K KiN
k(āN, F1)
k(āN,
7

---

Published in Transactions on Machine Learning Research (06/2023)
Server
Client
Client
Client Gel
o
Request
Request
Request
Request D
Request E
Request F
Request A
Request G
Request C
Request B
Request H
Request F
Figure I: Illustration of a privacy-aware lederated learning setup. A central server offer different clients, who have varying privacy requirements, tasks that require the client to train a model using a given portion of their local data set.
Overall, the posterior of f(x) is given by N(uN(x), kN(2,,)) and for each E 21, the posterior distribution of (z) is (()gy()) (z))²), where (ozx(x))² k (2, x).. Moreover, the posterior distribution of the outcome r(z) is given by (u)(()) AN (2, + 0222)
2.7 The Information Gain
Regret bounds for GP bandits depend on how well f can be learned from sequential interaction. The learning difficulty quant by the information gain, which accounts for the reduction entropy of a random vector after a sequence of (correlated) observations. For a length N sequence of contexts ø[N]: evaluations of contexts in NN), given by fIN], and the corresponding sequence of outcomes T[]]; the information gain is defined as [(r(N] f(n)) == (((()) Hrr (f(N) where H(-) and H--I-) represent the entropy and the conditional entropy operators, respectively. Essentially, the information gain quantifies the reduction in the entropy of fIN] given r[N]- The maximum information gain over the context set X' is denoted by Ni = sup e Iy(T(M): fIN)). Similarly as before, j E (1,2).
It important to understand that " the maximum information gain for an N-tuple of contexts from X. For large context spaces, Ni can be very large. As we have varying base arm availability from round to round due to changing action sets, we only need to know the maximum information gain that associated with fixed sequence of base arm contexts arrivals. As we have finite maximum information gain, this motivates us to relate the regret bounds to the informativeness of the available basc arms. To adapt the definition of the maximum information gain to our setup with changing action sets and to ensure tight bounds, we define a new term 7jT- We let 2, C 2% for f 2 be the set sets of context vectors which correspond to the base arms in the feasible set of super arms S,. We let E, == Øt,s be an element Z, for a super arm S and we let E[-] == [*T...., 27). Then the maximum information gain which associated with the context arrivals Xy,.... Xr is
7T
max IST (r (x(m))
The information gain for any element sequence of feasible super arms has maximum given by Tr. As it will be shown in Section 4, our regret bounds depend TjT-
8

---

Published in Transactions on Machine Learning Research (06/2023)
2.8 Motivation
Our first motivation is crowdsourcing setup, depicted in Figure 1. At each round t, |9el groups, hence clients, are available. Each client has one or more requests and these client-request pairs correspond to base arms, m E M, Super arms are comprised of combinations of these pairs. The chosen super arm St includes the client-request pairs having bold arrows. These pairs also have dashed arrows as they train their data locally before sending their model back to the server. Base arm outcomes, namely f. are the amount of information that the server retrieves and also the information leakage probability associated with each pair. The amount of retrieved information which is related to super arm reward (u) is aimed to be maximized, and the information leakage probability which is inversely related to the group reward (vG) is aimed to satisfy certain privacy threshold (7,G). The context coming at each round t for base arm m, denoted by Tr,,, is the data set usage percentage for each client-request pair and hence affects base arm outcomes. The data set usage percentage affects information that the server retricves since a higher percentage means the client is using more of its data to train the model and this percentage also affects the information leakage probability since training on larger portions of dataset leads to more information leaked as explored in (Melis et al., 2019). The server cares about the clients' privacy requirements as privacy is important factor which influences the likelihood of client enrolling in future crowdsourcing, jobs. Essentially, client is less likely to participate in future crowdsourcing, jobs from a server if the server repeatedly requests the client to perform tasks which cause data leakage beyond the privacy leakage preference of the client. Also in this setup, it is not possible for clients to reject tasks which are assigned to them, however, the server assigns tasks which disregard the privacy preference of the clients, the clients will likely become dissatisfied with the server and unlikely to use for future jobs.* 4 The clients leaving corresponds changing arm sets in this model since when a client leaves its corresponding requests are also no longer available.
Another motivation for our setup is movie recommendation with content caching. In this formulation, base arms can be movic-user pairs and context can represent the aligmment between the users' interests and the movies' contents, which is captured by the rating. Groups can be laken to be the users that are in the same location and super arms can again be the combination of various base arms. When a super arm is selected, movies of the base arms that are contained this super arm are cached their respective locations, hence, maximizing super arm reward is related to caching content that will be watched and liked by people. In this problem, we want to identify which movies to recommend and cache and in which locations we should cache these movies. Hence, we want to maximize the super arm reward which is function of the ratings of the movics that we recommend to the users, in order to cache these movics since they are rated highly. But we also want to ensure that the movies that we cached at a certain location are well-liked on average by the users at that location since this is the main goal of caching. This corresponds to maximizing group reward. We give a more detailed explanation with mathematical notation for these two setups in Section 5.
3 Algorithm
We design an optimistic algorithm that uses GP UCBs in order to identify groups that satisfy thresholds and super arms that maximize rewards. We name our algorithu Thresholded Combinatorial GP-UCB (TCGP-UCB) with pseudo-code given in Algorithm TCGP-UCB uses the double UCB principle, using different exploration bonuses for group and super arm selection. These bonuses are adjusted based the trade-off parameter < given in the regret definition in equation 1.
For every available base arm, two indices which are upper confidence bounds on the two expected outcomes are defined by considering the parameter Ç E [0, 1]. Consider base arm m with its associated context, Tt,m- We define its reward index as
1 4 (((e.)))= = 141 (FL.m) +
1- ( (
Note that our setup general and we make no assumption on past base arm contexts affecting futurr ones.
9

---

Published in Transactions on Machine Learning Research (06/2023)
where Mije-1] (2), and d (2 stand for the posterior mean and variance. Similarly, we define the satisfying index of base arm
((t.))) 12 + &( ( 022 (1 (ft,m))
We give the indices ()) to Oraclegrp: which returns the set of good subgroups, gogoo We form the set of feasible super arms whose groups expected to satisfy their constraints, S/, by using the returned good subgroups and St. If the oracle computes goog to be the empty set, then we set S = St- Otherwise, we have that S { S. VG E 9t SnG gongo Then, we give the indices (x(e, of the base arms that construct S to Oraclespri which returns an a-optimal super arm.
Algorithm TCGP-UCB
1: Input: X, K, M. 6, GP Prior: GP(uo, k)
2: for 1=11=.... T do
3: Observe base arms in Mr; their contexts X, their groups 9t, and feasible super arms S
4: for Zt,m m E M₁ do
Calculate MI--1] (m),)) and T (1 using GP posterior
Compute indices (x),,m and (z1,m) end for
8: Gr Gr.good < Oraclegrp(( (2 Gr) Form the set S using good and S
10: S. + Oraclespe (fe (Te. St)
11: Observe base arm outcomes r, collect group rewards Va and super arm reward U
12: end for
4 Theoretical Analysis
Next is our main result which asserts high probability upper bound the total regret of our algorithm in terms of Tr. The supplemental document contains further details and proofs of our results, most of which follow directly from those of (Nika et al., 2021). Throughout this section, we take j E {1,2].
Theorem 1. Super arm regret and group regret incurred by TCGP-UCK UCB in T rounds are upper bounded with probability at least - 8 where d E 1), T E N and Br = 2 log (M /33) as follows:
RT(T) ((((K)Br
where Ci(K)= (X + and
R,(T) S (orKK)rKKTrr
where =a(K)=2BB² ( +02).
Hence, the lotal regret is bounded by:
R(T) < (C(K)S
where C(K) 8(B ())(())(()(+++))))))))+)))) + 7. max Fer and X-K is the marimum eigenvalue of Eq--1 (z.), for < (i.e., marimum eigenvalue of all covariance matrices of selected actions).
Remark 1. Note the dependence of the bounds on the maximum eigenvalue of all covariance matrices throughoul all rounds, denoted by X* (K), which is a function of K. The worsl cases upper bounds on X* are known to be O(K) (Zhan, 2005), which case we obtain linear dependence on K in the regret bounds. This dependence comes from the fact that base arm outcomes are not independent of each other. On the other hand, when the base arm oulcomes all independend, the covariance matrices in each round would be diagonal with X* maxxsT G (2t,x) < 1, and thus, incur regret bounds of the form O( (KTT))
10

---

Published in Transactions on Machine Learning Research (06/2023)
Next, state lower and upper bounds Tr in terms of the classical information gain. This gives measure of how tight our bounds are with respect to previous bounds in the GP bandit literature.
Theorem 2. Letting T Σt= [So] be the sum of cordinalities of selected actions up to time T, have that
Tr YT
Purthermore, if [S K and X; X, for all t [T], then we have
K TKT S 7T S TKT
Using this characterization of Tr, we can now provide regret bound that depends on the classical notion of maximum information gain.
Theorem 3. Pir 8 1) and let T,K K E. Under the conditions of Theorem 1 and assuming that |S| K for any S E S, let T = Σ [Sc). Then, the total regret incurred by TCGP-UCB in T rounds is upper bounded with the following with probability at least 6:
R(T) S ((())TKKTT)
where
T J ACX:A||T
(((((E)):
(2)
while C and 3r are the same Theorem
Finally, using kernel-dependent explicit bounds on "T given in (Srinivas et al., 2012; Vakili et al., 2020), we state corollary of Theorem 3 that gives similar bounds on the total regret incurred by TCGP-UCB.
Corollary 1. Let 5 E (0,1) T, E and let X C RR. be compact and convex. Under the conditions of Theorem 3 and for the following kernels, the total regret incurred by TCGP-UCD in T rounds upper bounded (up to polylog factors) with probability at least 1 - as follows:
For the linear kernel we have: R(T) Ô (VX(K)DKT))
2. For the RBF kernel we have: R(T) S 5ō <N((KWDKK))
3. For the Matérn kernel we have: R(T) < 1 (N())((()0000)))0000))))
where is the Matérn parameter.
5 Experiments
We perform two sets of experiments. In the first one, we use synthetic dataset and privacy-aware federated learning setup to show that our algorithm outperforms the non-GP state-of-the-art while maintaining user privacy requirements. In the second experiment, consider content caching-aware movie recommendation setup. We also perform further simulations in Appendix B to investigate the effect of the trade-off parameter, Ç.
5.1
Privacy-aware Federated Learning
5.1.1
Setup
We consider privacy-aware federated learning setup comprised of server and clients. The server's goal is to train model using clients' data. However, clients do not wish to directly share their data
11

---

Published in Transactions on Machine Learning Research (06/2023)
with the server and instead train the model on portion of their local dataset, with the portion decided by the server, which they then send to the server. Thus, in each round, the server must serve requests to the available clients and select the portion of their dataset to locally train on. More- over, each client has different privacy requirements regarding the maximum amount of data that can be leaked.
In each round, we simulate the number of available clients using a Poisson distribution with mean 50. Then, the server can make request to each client to ask them to use portion of their dataset for training the local model and then send the updated model to the server. We allow for x E {0.01, 0.02..... ..000.. Thus, for each client there are 100 possible requests. We then represent each request-client pair as a base arm with a one-dimensional context in [0, 1] that represents how much of the dataset the request asks for the client to use. We allow for the same client to receive multiple requests, as a client may have different local datasets on which he can train multiple local models. The maximum number of requests that each client can simultancously receive one round follow a Poisson distribution with mcan
After picking base arms (i.e., client-request pairs), the clients train the models on their local datasets and then return their model updates. We model the amount of useful information that the server gained from each request as a sigmoid-like function. More specifically, given context x, we have that the expected super arm outcome of æ is fi(x)= = -=xp(5-102) This model is justified by observing that very little data leads to overfitting and hence the first flat region for small z, and once the amount of data surpasses some threshold, noticeable gain in the amount of useful information transferable from the local model can be seen, hence the linear portion of fi. We define the random outcome to be (x) = (z) + 7/, where 171 is zero-mean Gaussian noise with a standard deviation of 0.05. Lastly, as the amount of data keeps increasing, we have diminishing
returns in the amount of useful information, captured by the flat region of f1 for large x. Then, the super arm reward is the sum of all the information learned from all requests. Thus, u(fi (xs)) = >! (z()..
We model each client's privacy requirement using a privacy leakage threshold in [0. 1], where clients intend for the amount of information leaked from their local dataset to be below this threshold, where we sample the leakage threshold of each client uniformly at random from [0, 1]. When clients train on larger portions of their datasets, more of their training set and hence information is leaked (Melis et al., 2019). We model this leakage as fa(z) = 0.05 + cxp(- We justify this model by first noting that if very few training samples are used, then near-exact versions of the training samples can be extracted from the model updates or gradients (Melis et al., 2019). However, as the number of training samples increases, the leakage also decreases but never goes to O. Additionally, where na is zero-mean Gaussian noise with standard deviation of 0.05. Finally, defining groups set of client-request pairs from the same client, group reward- better called loss in this scenario-is is the total leakage amount of all the requests of the client.5
define the random group outcome to be r2(2) = f2(x) 722
5.1.2 Algorithms
We run the simulation using slightly modified version of our algorithm, STCGP-UCB, and the non nPn-GP C3-MAB state-of-the-art algorithm, ACC-UCB of (Nika et al., 2020).
STCGP-UCB
We run a slightly modified version of our algorithm that uses sparse appromixation to GPs, called STCGP- UCB, where we use the sparse approximation to the GP posterior described in (Titsias, 2009). In this sparse approximation, instead of using all of the arm contexts up to round to compute the posterior, a small element subset of them is used, called the inducing points. By using a sparse approximation, the time complexity of the posterior updating procedure reduces from O(K3 + (2K) ... + (KT)3) ((3374) to O KT*). In our simulation, we set = 10. We also set 8 = 0.05, Ç = 0.5, and use two squared exponential kernels with both lengi hscale and variance set to 1.
Even though group reward is defined the non-leakage probability; considering the total leakage is also acceptable as our proofs still hold.
12

---

Published in Transactions on Machine Learning Research (06/2023)
ACC-UCB
We set = 1, = = and N = 2, as given in Definition 1 of (Nika et al., 2020). The initial (root) context cell, Xo.1, is a line centered at (0.5).
5.1.3 Results
We run the simulation for 100 rounds with eight independent runs, averaging over the results of each run. We plot the super arm and group regret in Figure 2. First, notice that ACC-UCB incurs lincar group regret as does not take group thresholds inlo account. On the other hand, STCGP-UCB incurs very low group regret as accounts for group thresholds. Additionally, the super arm regret of STCGP-UCB less than that of ACC-UCB, indicating that even though STCGP-UCB balancing between minimizing both group and super regret, it still outperforms ACC-UCB. This is likely due to the use of GPs, which allow for faster convergence to f.
Cumulative super arm regret
X 10
x10
3
ACC-UCB STCGP-UCB
Cumulative group regret
1.5
2
1.0
0.5
0.0
0
20
40
60
80
100
Round (t)
Figure 2: Cumulative super arm and group regret of ACC-UCB and STCGP-UCB, Super arm and group regret represented by blue and orange, respectively. Morcover, ACC-UCB and STCGP-UCB represented by solid and dashed lines, respectively. Shaded regions indicate = std.
5.2
Caching- aware Movie Recommendation
5.2.1
Setup
We evaluate the proposed algorithm in real-world dataset where our setup, similar to that of (Nika et al., 2021), is movie recommendation with content caching. We use the MovieLens 25M dataset with a slight modification (Harper Konstan, 2015). This dataset consists of users, movies, and the ratings given to the movies by users. In order motivate our definition of groups, we also add a randomly generated location for each user coming from set of 10 different locations and define movic-user pairs (i.c., base arms) that have the same location as group. Moreover, every movie has genre metadata coming from group of 20 genres such as, but not limited to, action, adventure, and comedy. Every rating given to movie by user falls between 0.5 and 5.0, with increments of 0.5. In this datasct, we take into account only the ratings after 2015 and users who have rated at least 200 movies.
each round t, we randomly choose Ht movies from the available set of movies, where H, is Poisson distributed with a mean of Next, we randomly select P. users who have reviewed the selected movics, where Pe is Poisson distributed with mean of 200. If user j has rated movie i, then the context of this base (Le., the pair of movie and user j) is given by æzj. This context is computed as æaj (u,.g:)/10.
13

---

Published in Transactions on Machine Learning Research (06/2023)
where u is the average of the genres of the movies that user j rated, weighed by their rating, 9: is the genre vector of movie i, and 10 is a normalizing factor.
We let movie-user pairs that are in the same location be groups and combinations of various movie-user pairs be super arms. We let the feasible set of super arms be any super arm with a size of K = 20. The expected base arm outcome function that is used for super arm reward computation, fI, given by fi (1 = æ and the super arm reward calculated as:
u(fi(er))) ΣE> E f((ass)
which is subject to Fi,j E st,s. This is motivated by the fact that when we are trying maximize super arm reward, we are actually trying to pick the super arm whose base arms (i.e., movie-user pairs) are the ones in which the users' interests were aligned with the genre of the movies that were recommended to them.
Then, we define the expected basc arm outcome function that is used for group reward computation, f2, [2(mL 2/(1 + + ) 1 and calculate the group reward according to the Dixit-Stiglitz model, as used in the simulations of (Chen et al., 2018), given by
1/3
Hy.
P
va (f(f(((oo)s)) =
Σ
Σ
f2(
where Pt, is the number of users who have rated the ith movie and reside in the Ith location, and Ha. is the number of movies that have been rated by at least one user residing in the Ith location. Notice that this is a submodular function and the generality of our method enables us deal with such functions. The movies of the base arms of the chosen super arm are cached, therefore, groups want to have their base arms to be contained in the selected super arm much as possible, hence, the outcome function f2 is a sigmoid- like function which gives higher weight to the movies having higher rating. On the other hand, the outcome function fi is the identity function and treats all the base arms fairly without favoring one over the other. Lastly, we get the random outcome used in our simulations by adding aero-mean Gaussian noise with standard deviation 0.05 to the expected outcomes.
5.2.2 Algorithms
We run the simulation using the same algorithms the previous simulation, namely algorithm with sparse GP approximator, STCGP-UCB, and the non-GP C3-MAB statc-of-the-art, ACC-UCB of (Nika et al., 2020).
STCGP-UCB In our simulation, we set the number of inducing points to s = 5. We also set 0.05, 0055, and use two Matern kernels with both lengthscale and variance set
ACC-UCB
We set 1i 1, = p 0.5, and N = 2, as given in Definition 1 of (Nika et al., 2020). The initial (root) context cell, Xo.1, is a line centered at (0.5).
5.2.3 Results
We run the simulation for 200 rounds with twenty independent runs, averaging over the results of each run. We plot the cumulative super reward of each algorithm divided by that of the benchmark in Figure 3. As seen in the Figure, both algorithms managed to quickly learn which contexts are high-outcome, when it comes to the super arm reward. However, TCGP-UCB clearly learns much faster than ACC-UCB, In just t = 26 rounds, TCGP-UCB achieves an average cumulative reward of 0.80 0.11, whercas it takes ACC-UCB more than twice as many rounds to reach the same reward; it reaches 0.80 + 0.06 round 59.
We divide 10 and normalize the context because the maximum number genres that movie has in the dataset. 10.
14

---

Published in Transactions on Machine Learning Research (06/2023)
Scaled cumulative reward
1.0
100
0.8
Group constraints met
80
0.6
60
0.4
40
A STCGP-UCB
STCGP-UCB
0.2
20
ACC-UCB
ACC-UCB
0.0
0
50
100
150
200
0
50
100
150
200
Round (7)
Round (t)
Figure Cumulative super arm reward of each al- gorithm in each round divided by that of the bench- mark, averaged over twenty independent runs. Error bands represent + std.
Figure 4: Percentage of groups corresponding to picked super arms in each round that satisfied their constraints, averaged over twenty independent runs. Error bands represent std.
Moreover, the final cumulative reward of TCGP-UCB is also higher than that of ACC-UCB, albeit not by much: 0.988 = 0.031 compared with 0.970 + 0.027. Both the quickness of learning and higher final reward can likely be attributed to the fact that TCGP-UCB uses GP, whose posterior update allows for faster learning than the adaptive discretization approach of ACC-UCB.
We also recorded the number of satisfied groups in each round for each algorithm. In other words, we kept track of the percentage of groups corresponding the picked super arm in cach round had their constraints met. We plot. this result in Figure First, we observe that the percentage of group constraints that TCGP-UCB satisfies quickly converges above 0.95 in 50 rounds. However, ACC-UCB struggles greatly with satisfying group constraints and manages to converge to around 50% of group constraints met. This discrepancy is simply because TCGP-UCB takes group constraints into account, while ACC-UCB does not.
6 Conclusion
We considered the C3-MAB problem with semi-bandit feedback, where in each round the agent has to play a feasible subset of the base arms in order to maximize the cumulative reward while satisfy group constraints. Our setup was motivated by privacy aware federated Icarning, where the goal is to optimize overall training result while satisfying clients' privacy requirements. Under the assumption that the expected base arm outcomes are drawn from two-output GP and that the expected reward is Lipschitz continuous with respect to the expected base outcomes, we proposed TCGP-UCB, double UCB algorithm that incurs D(Vx*(K)TT)) regret in T rounds. In experiments, UCB computation, while simultaneously outperforming the state-of-the-art non-GP-based C3-MAB algorithm in a synthetic and real-world setup. Our comparisons also indicated that GPs can transfer knowledge among contexts better than partitioning the contexts into groups of similar contexts based on a similarity metric. An interesting future research direction involves investigating how dependencies between base arms can be used for more efficient exploration. Then, when the oracle selects base arms scquentially, it possible update the posterior variances of the not yet selected base by conditioning the selected, but not yet. observed, base arms.
showed that sparse GPs can be used to speed up
15

---

Published in Transactions on Machine Learning Research (06/2023)
References
Sanae Amani, Mahnoosh Alizadeh, and Christos Thrampoulidis. Linear stochastic bandits under safety constraints, 2019.
Stephen Boyd and Lieven Vandenberghe. Conver Optimization. Cambridge University Press, March 2004. ISBN 0521833787.
Nicolo Cesa-Bianch, and Gábor Lugosi. Combinatorial bandits. J. Comput. Syst, Sci., 78(5):1404 1422, 2012.
Cangxiong Chen and Neill D. F. Campbell. Understanding training-data. leakage from gradients in neural networks for image classification, 2021.
Lixing Chen, Jie Xu, and Zhuo Lu. Contextual combinatorial multi-armed bandits with volatile arms and submodular reward. In Proc. Adu. Newral Inf. Process. Syst., pp- 3247-3256, 2018.
Wei Chen, Yajun Wang, and Yang Yuan. Combinatorial multi-armed bandit: General framework and applications. In Proc. 30th Int. Conf. Mach. Learn., pp. 151-159. PMLR, 2013.
Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu. Combinatorial multi armed bandit with general reward functions. In Proc. Adu. Neural Inf. Process. Syst., pp. 1659-1667, 2016a.
Wei Chen, Yajun Wang, Yang Yuan, and Qinshi Wang. Combinatorial multi-armed bandit and its extension probabilistically triggered arms. J. Mach. Learn. Res., 17(1):1746 1778, 2016b.
Yi Gai, Bhaskar Krishnamachari, and Rahul Jain. Combinatorial network optimization with unknown variables: Multi-armed bandits with linear rewards and individual observations. IEEE/ACM Trans. Netw., 20(5):1466 1478, 2012.
F. Maxwell Harper and Josoph A. Konstan, The movielens datasets: History and context. ACM Trans. Interact. Intell. Syst., 5(4), December 2015. ISSN 2160-6455. doi: 10.1145/2827872.
Andreas Krause and Cheng Ong- Contextual gaussian process bandit optimization. In J. Shawc-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger (eds.), Adv. in Neural Inf. Process. Syst., volume 24. Curran Associates, Inc., 2011.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized article recommendation. In Proc. 19th Trl. Conf. World Wide Web, pp. 661 2010.
Shuai Li, Baoxiang Wang, Shengyu Zhang, and Wei Chen. Contextual combinatorial cascading bandits. In Proc. 33rd Int. Conf. Mach. Learn., pp.
PMLR, 2016.
Andrea Locatelli, Maurilio Gutzeit, and Alexandra Carpentier. An optimal algorithm for the thresholding bandit problem. In Maria Florina Balcan and Kilian Q. Weinberger (eds.), Proc. of The 33rd Int. Conf. on Mach. Learn., volume 48, pp. 1690-1698. PMLR, 20-22 Jun 2016.
Tyler Lu, Dávid Pál, and Martin Pál. Contextual multi- bandits. In Proc. 13th Int. Conf. Artif. Intell. and Statist., pp. 485 492, 2010.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication- Efficient Learning of Deep Networks from Decentralized Data. In Aarti Singh and Jerry Zhu (eds.), Proc. of the 20th Int. Conf. on Artif. Intell. and Statist., volume 54, pp. 1273-1282. PMLR, 20-22 Apr 2017.
Luca Mclis, Congzheng Song, Emiliano De Cristofaro, and Vitaly Shmatikov. Exploiting unintended feature leakage in collaborative learning. In 2019 IEEE Symp. on Sec. and Priv. (SP), pp. 691 706. IEEE, 2019.
Subhojyoti Mukherjec, Kolar Purushothama Naveen, Nandan Sudarsanam, and Balaraman Ravindran. Thresholding bandits with augmented UCB. CoRR, abs/ 11s/1170..0281, 2017.
Andi Nika, Sepchr Elahi, and Cem Tekin. Contextual combinatorial volatile multi-armed bandit with adaptive discretization. In Proc. 23rd Int. Conf. Artif. Intell, and Statist., volume 108, pp. 1486- 188611966, 26-25 Aug 2020.
16

---

Published in Transactions on Machine Learning Research (06/2023)
Andi Nika, Sepehr Elahi, and Cem Tekin. Contextual combinatorial bandits with changing action sets via gaussian processes. CoRR,
2021.
Alessandro Nuara, Francesco Trovò, Nicola Gatti, and Marcello Restelli. A combinatoriall-anddii algorithm for the online joint bid/budget optimization of pay-per-click advertising campaigns. Proc. of the AAAI Conf. on Artif. Intell., 32, 02 2018. doi: 10.1609 1..ai...321..111
Lijing Qin, Shouyuan Chen, and Xiaoyan Zhu. Contextual combinatorial bandit and its application on diversified online recommendation. In Proc. of the 2014 SIAM Int. Conf. on Data Min., pp- 461-469.
SIAM, 2014.
Paul Reverdy, Vaibhav Srivastava, and Naomi Ehrich Leonard. Satisficing in multi-armed bandit problems. IEEE Trans. on Auto. Cont., 62(8))3788 3803, 2017. doi: 10.1109/TAC.2016 2644380.
Herbert Robbins. Some aspects of the sequential design of experiments. Bulle. of the Amer. Math. Soc., 58 (6):527-535, 1952.
Shubhanshu Shekhar, Tara Javidi, et al. Gaussian process bandits with adaptive discretization. Electron. J. Stat., 12(2):3820-387) 3874, 2018.
Aleksandrs Slivkins. Contextual bandits with similarity information. In Proc. 24th Annu. Conf. Learn. Theory., pp. 679 702, 2011.
N. Srinivas, A. Krause, S. M. Kakade, and M. W. Seeger. Information- regret bounds for gaussian process optimization in the bandit setting. IEEE Trons. Inf. Theory, 58(5):3220 3265, 2012.
Michalis K Titsias. Variational learning of inducing variables in sparse gaussian processes. In Proc. 12th Int. Conf. Artif. Intell. and Statist., pp. 567 574, 2009.
Nguyen Truong, Kai Sun, Siyao Wang, Florian Guitton, and YiKe Guo. Privacy preservation in federated learning: An insightful survey from the gdpr perspective. Comp. & Sec., 110:102402, 2021. ISSN 0167-4048. doi: https://doi.org// 10. 1016//.cosee221..10...
Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. aiviv preprint ar Xiv:2200090000 2020.
Kristof Van Moffaert, Madalina M. Drugan, and Ann Nowé. Scalarized multi-objective reinforcement learning: Novel design techniques. In 2013 IEEE Symp. on Adop. Dyn. Prog. and Reinf. Learn. (ADPRL). pp. 191-199, 2013. doi: 10.1109/AMM 10.1109/ADPRL.200 /DD.ADDDR......11.5000
Siwci Wang and Wei Chen. Thompson sampling for combinatorial semi-bandits. volume 80 of Proc. of Mach. Learn. Res,, pp. 5114 5122. PMLR, 10 15 Jul 2018.
Zhenlin Wang, Andrew Wagenmaker, and Kevin Jamicson. Best arm identification with safcty constraints, 2021.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H. Yang, Farhad Farokhi, Shi Jin, Tony Q. S. Quek, and H. Vincent Poor. Foderated learning with difforential privacy: Algorithms and performance analysis. IEEE Trans. on Inf. Foren. and Sec., 15:3454 3469, 2020. doi: 10.110/TTIF... 299..998875.
Christopher KI Williams and Francesco Vivarelli. Upper and lower bounds on the learning curve for gaussian processes. Mach. Learn., 40(1):77-100 102, 2000.
Saba Q. Yahyaa, Madalina M. Drugan, and Bernard Manderick. The scalarized multi-objective multi-armed bandit problem: An empirical study of its exploration vs. exploitation tradeofT. In 2014 Inter. Joint Conf. on Neur. Net. (IJCNN), pp. 2290 229722227.2220 2014. doi: 10.1109/IJCNN 20W.CNN..2.....8.000 2014.689930..
Mengwei Yang. Linqi Song, Jie Xu, Congduan Li, and Guozhen Tan. The tradcoff between privacy and accuracy in anomaly detection using federated xgboost, 2019.
Xingzhi Zhan. Extremal eigenvalues of real symmetric matrices with entries in an interval. SIAM jour. on malr. analy. and appli., (7))):511-888 860, 2005.
17

---

Published in Transactions on Machine Learning Research (06/2023)
A Table of Notation
We provide table of notation that the proof section can be easily followed.
Symbol
Explanation
m
Variable to denote a base arm Variable to denote group
G
S
Variable to denote super arm Variable to denote the chosen super arm round t Set of base arms that are available at round Number of base arms that become available at round t Set of feasible groups in round
S,
Mr
Gt
ggooo
Set of groups whose expected rewards are above their thresholds
S,
Set of feasible super arms round
S
Set of super arms whose corresponding groups satisfy their thresholds
S
Set of feasible super arms whose corresponding groups' reward indices are above their thresholds
S
Overall feasible of super arms Context
X
Set of available contexts in round t Context associated with base arm m Context vector of base arms in G Context vector of base arms in Random outcome of base arm with context x Expected outcome of base arm with context x (0, o2) independent observation noise Random super reward
Ttm
r(x)
f(x)
((S,,((z1,))
m(S, (i (a),s)
Expected super arm reward function Random group reward Expected group reward function Threshold for group at round Trade-off parameter
Va(12(z),
(o(f((x,.cns)))
n.
ie (Fe.m)
Index of base arm m round t which is given to Oraclespe (reward index) Index of base Maximum information gain which is associated with the context arrivals X, Xr Maximum information gain given N base arm outcome observations Maximum possible number of base arms in a super arm
(3(,m)
at round t which is given to Oraclegrp (satisfying index)
Tr
K
When state that 2 b with and b being vectors, mean that every component of a is greater than equal to the corresponding component of b. This holds for other comparison operators as well. Also, omit G from Dg and Vo: and S from US.....) and u(S....) when it is obvious from the context. In the definition of St and S/ the term corresponding groups means the groups that contain the base arms of the chosen super arm.
B Additional Experimental Results
B.1 Changing Trade-off Parameter (c)
In this simulation showcase the behavior of our algorithm for changing trade-off parameter (C) values.
18

---

Published in Transactions on Machine Learning Research (06/2023)
B.1.1 Setup
We use synthetic setup where we generate the arm and group data needed for the simulation. Similar to the main paper simulations, in each round I, we first sample the number of groups, [9e|, from a Poisson distribution with mean 50. Then, for each group we generate the contexts of the base arms in that group, where the number of base arms is sampled from a Poisson distribution with mean 5. Each base arm has a two-dimensional (2D) context that is sampled uniformly from [0, 1]2. Then, we sample the expocted outcome of each base arm of each group from GP with zero mean and two squared exponential kernels, each given by
k(x,x))= exp (-2
1 212 100 (ann-(l)))
r'1))
where set 1 = 0.5. Note that given that we the simulation for T 100 rounds, there will be expected number of 25000 arms and to sample GP function with that many points will need to compute the Cholesky decomposition of a 625 million element matrix, which would be very resource-heavy. Instead, we first sample 6000 2D contexts from [o, 1]2 and then sample the GP function at those points. Then, during our simulation, we sample each base arm's context r and corresponding expected outcome f(x) from the generaled sets. Finally, we set. r(x) = f(x) + 7, where r ~ (O 12). We set the group reward, v, to be the variance of the outcomes the group and we set the threshold to be the 80% percentile of the group rewards of all groups in all rounds of the simulation. We use a high percentile value to increase the difficulty of the group thresholding, so that minimizing super arm regret does not necessarily yield minimizing group regret. Finally, the super arm reward is the linear sum of the base arms.
B.1.2 Results
We run our algorithm using five different values of Ç, lincarly spaced between 0.001 and 0.999. Figure 5 shows the final super arm and group regret of each run (i.e., the cumulative regrets al the end of the simulation). First, notice a trade-off between super arm and group regret. As one increases, the other decreases. This is expected because to minimize group regret, groups with arms whose outcomes are spread out and have high variance must be picked, but to minimize super arm regret, groups with high outcomes must be picked. Second, as Ç increases, the super arm regret increases while the group regret decreases. This because the variance of the indices given to the first oracle (f'), which determines which groups pass their thresholds, decreases as Ç approaches 1. Thus, the larger & is, the stricter the first oracle is. Conversely, the smaller Ç is the laxer the first oracle and the stricter the second oracle, which determines which super arm to play.
0.00
0.25
Final group regret
0.50
260
0.76
1.00
255
250
600
800
1000
1200
1400
1600
Final super arm regret
Figure 5: Final super arm and group regret for different trade-off parameter, Ç, values
19

---

Published in Transactions on Machine Learning Research (06/2023)
C Proofs
C.1 Auxiliary Proofs
In this part, we will prove results that will be used in the proofs of the theorems in the paper.
Throughout this section, we take j E {1,2}. We denote by rs the vector base arm outcome observations made until the beginning of round t, where
T 1 (1 (f.. (2)-
2 1, the posterior distribution of [(x) given the observation vector Titt-1] is (x), (aage- (x))3), for any E N. In our analysis, we will resort to the following Gaussian tail bound
For any
P - > (/ S 2 eexp
-Be for Br 20.
(3)
The following lemma shows that the base arm indices upper bound the expected outcomes with high probability.
Lemma 1. (Lemma of (Nika et al., 2021)) Pir ā E (0, 1), and set 8r 2oo (M (M32))335). Let F, (A) 2 Vr E N₂ (ff(=)-)))--aa 1] S (1 (z)). We have P(F,) 2 5.
Now, state that the modified indices upper bound the expected base arm outcomes with high probability under the events Fj.
Lemma 2. The following arguments hold under Fi F2F..
(xx)) 2 (1))) 14 2 1, E X (x) 2 /2(2), 2 1, Vo E E.
(4)
Proof. Fix 2 1 and x E Xg Under event F1, we have the following chain of inequalities
fi(x) P1n-1 (x) S ( (B))
1
[(x) ((o)-~((t-fp (1) 1- ( (v 3:)0
(5)
[1()) S (1)-1((1) + - (v (0)o1p-11(() = in(x)
Proceeding in the same fashion for event Fz we obtain
fa(x) p27-- (x) < ( (v B1) (B)))o2(-11(22
(6)
fa(x) < ( { 11)00p1-11(0) 11(x),
where equation 5 and equation 6 follow from the fact that - 2 1 and & 2 when ( E [0. 1].
Next, we show that the set of feasible super arms whose corresponding groups satisfy their thresholds is a subset of the set of feasible super arms whose groups' reward indices are above their thresholds. We later use this result Lemma
Lemma 3. Fix 1), The following argument holds under the event Fg when the group reward function o salisfies the monotonicity assumplion given Assumplion 1.
S. VI
20

---

Published in Transactions on Machine Learning Research (06/2023)
Proof. For any St and for all G we have:
St E S - v 2 7t
(7)
- v (22 - 71,0 2 0
oii -,, 2
(8)
= St E S
(9)
where equation 7 follows from the definition of S/ equation 8 follows from the inequality that ((i ons,) ((ff(ax.cns.) Since ((r,,))) 2 f2(2),ors,) under the event F2 and v is monotone by assumption, this inequality is valid. Lastly, equation 9 follows from the fact that Oraclegp is an exact oracle and will return the groups where ((((( Gr As this reasoning is true for any Se, we indicate that S S.
Detail:
S: = {S E S. V(G E Ge), vo(fa(zr,cns)) 2 n.)).
S = {5 S, VG E Gr, SnG gr.good)
Grgo (G' C G E G. and No (i( 2 ),,
i (z),m) = u2 (1 + ( ( (V3))02(-1)(01mm) (2),m))
Next, we upper bound the group regret in terms of the posterior variances of base arms. Note that group regret is incurred when a selected group's expected reward is below its threshold whereas its index is above. Therefore, whenever a group G incurs group regret in round t, then ((f2 < H. < ((((( must happen. This observation plays a key role in the analysis of the next lemma. Moreover, we use the notation Lt to denote the context of the kth base arm in G Sy at round for convenience, unless otherwise stated.
Lemma 4. Fix t 1, and consider G E Gr. The following argument holds under the event F2:
IGnSi
heo - ((c=,((((().css))) (5+
B BUB B
Σ
in (āc,)))
(10)
Proof. ha, - u(f2(2t })]+ > implics that v(f2(2),onss)) < n, and (((((z)..ns)) 2 M.G. Therefore, whenever G incurs group regret holds that v(f2(xt,ons))) < n, S (((((a))
< N. - ((s(x, < ((((a))))s)))
(f
0 - ((s(,,(((((), < v1 v (2(
lans
< Bans
(T,,)) - f2(
(11)
|Gnsil
IGNS
< Bons.
Σ
(e) f2( + Bons.
Σ
/
1
k
(12)
IGnS
<
B(
B.)
Σ
1o
(13)
A=1
where equation follows from the Lipschitz continuity of o; equation 12 follows from the definition of index and the triangle incquality; for equation 13 we use Lemma and the definition of B.
21

---

Published in Transactions on Machine Learning Research (06/2023)
Next, upper bound the gap of selected super arm in round t (aka simple regret) in terms of the posterior variances of base arms. Hereafter, we use the notation J4,k to denote the context Lt,si of the kth selected base arm St,k at round t for convenience, unless otherwise stated. Note that St E arg max (x,) is the optimal super arm in round
Lemma 5. Given round 2 1, let S; (s,,...... ((ss1 denote the optimal super amm in round Then, the following argument holds under the event F1:
Se Be
(
a (uff((i)ss)) u(fi(xss))) - 1 (
0
(T.k))
(14)
k=
Proof. We define He arg sa u((c(ze,s)). Given that event F, holds, we have:
a u(i(((rs;;)) ((fi(ar.s:)) a. ( )) - u(Ji(zr,s:))
(15)
S u(in((., - (
(16)
S u(ic((r,ss)) - (ar(s))
(17)
18
B'
(T(TT( (T,,
(18)
[S.]
1
B'
|iist-1 (Te,K) (T. + B'
(v Br 3:)0 (T(,s)
(19)
k=1
S&
2 (2-5)
B'
8
(
(20)
1 (-()
k=
where equation 15 follows from monotonicity of and the fact that fi S ie (e(,,,,),)) ) for k S [S (Lemma 2); equation 16 follows from the definition of H, and the fact that St S S on event F2 (Lemma 3), in other words, max u(i((a),))) 2 maxses; u(ir(ar.s)) since St C S/; equation 17 holds since S, is the super arm chosen by the a-approximation oracle; equation 18 follows from the Lipschitz continuity u; equation 19 follows from the definition of index and the triangle incquality; for equation 20 we use Lemma
Before proving theorems, prove our last lemma which enables have regrets bounds in terms of the information gain. We note that both of our oracles are deterministic and our algorithm doesn't give any extra randomization.
Lemma 6. (Lemma 3 of (Nika et al., 2021)) Let z: = æt.s, be the vector of selected contexts at time t 2 1.
Given T 2 1, we have:
T SS
1 (15(2)))) 2 2X0-2X'(K) +
Σ
2
1(-11 (Te
t=
where Z(r] .2....., 22 T is the vector of all selected conterts until round T and X* the marimun eigenvalue of matric (E1e-11 (2(T)))=- ((7)))
22

---

Published in Transactions on Machine Learning Research (06/2023)
C.2 Proof of Theorem 1
From Lemma 4 we have:
T
RT(T)- = Σ
h - uff2(ar,ons))))
t=1 GEG
GnSS
5 s+1
B BT
(
1=1 GED,
|.
(+1
B
BT
02 (Tr,A)]
(21)
using the fact that VBL is monotonically increasing in t. Also, we changed the notation of εt with Tt,s as we are summing through all the base arms in St in equation 21. We have:
2
1+1 C
s
R2(T) <
B²Br
102 1] (TaAA)
(22)
T
C (+1
Ba BTT
02
12 (Ir
(23)
1=1
k=1
(+1)
T
Se1
Ba B Σ
|
Σ
(0 (z),
(24)
A=1
1Sd
(+1>
Bd BTBTK Σ
(o2 (I), 2
(+1)
T
18.1
B² BTOT 2
(02(e11((Ze.))²
(25)
1=1k=
(+1)
2( (M(o)) +1
B² 3r (
(26)
< 3 T
(27)
where for equation 23 and equation 24 we have used the Cauchy-Schwar inequality twice; in equation 25 we just multiply by x² and o 2; equation 26 follows from Lemma 6 and for equation 27 use the definition of Yer. Taking the square root of both sides we obtain our desired result. From Lemma we have:
(T(T) opt(Si) Σ u u(fi(Eess))
18
(2-9) B' BT
l
(
(28)
using the fact that V3, is monotonically increasing in t. We have:
2
(2-3)
R²(T) <
BB
Σ
0 [ I (21
(29)
23

---

Published in Transactions on Machine Learning Research (06/2023)
The middle steps the same equation 23-cquation 26 except that we have (--5)² (B")2 instead of
c+1
B² the constant multiplier. Also, 0i instead of Ø2. Hence, the last steps are modified
RT s 2(0 ( +1 (1-8)² 2 (
S C2(K))K,TTiT
Taking the square root of both sides we obtain our desired result. Finally, in order obtaín the total regret use:
R(T)= - (1- v BBrKTTT
$
where 7T = max feax(T1r TIT: 727). In order to eliminate the { dependence we modify this expression as follows:
1) 2(Br) 2 ( (2(x(((++0())
R(T) -
<V 2B2
VBKKTT
(30)
1-c
(2 + 1))(
v
+02)
VirkTTr
[c]
| - cl
(2 1) + ( - VBrKTT
(31)
BBIC + |BI[+ BB112 c1) v KT
2((( +
2((((()) + +02)
+15+1)+ B2 B1 BTKITT
(32)
S (2( + 02)
2B + 2B' VBrKTTr
(33)
VCKK)BKKTTT
where equation 30 follows from writing the expressions of C1 and C2 to the required places; equation 31 follows from Ç E [0, I]; equation 32 follows from the assumptions that B > 0 and B' 0 and also from E [0, 1] and equation 33 comes from writing the maximizing Ç values in < + 1 and 2 - Ç.
C.3 Proof of Theorem 2
The proof is the same as that of Theorem 2 of (Nika et al., 2021).
C.4 Proof of Theorem 3
We first state an auxiliary fact that will be used in the proof (for proof see (Williams & Vivarelli, 2000)). Fact 1. The predictive variance of given contert is monotonically non-increasing (L.e., given x E X' and the vector of selected samples Uh....,,N-1I, we have ( I (x), for any N 2 1).
The proof of Thcorem casily follows from Theorem 2 and this fact.
C.5 Proof of Corollary
This is a direct application of the explicit bounds on Yr given in Thcorem 5 of (Srinivas et al., 2012) to the bound we obtained in Theorem 3. For the Matérn kernel, we have used the tighter bounds from (Vakili al., 2020).
24


Reviews:
[{"review_id": "UC026v9TQl", "reviewer": "Reviewer_qMp3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Summary:** The problem seems interesting. However, my main issue with the paper is that it was very unclear in parts and difficult to read. \n\n**Contribution:** Overall I find the contribution to be minor. The problem statement is somewhat interested (and as mentioned above related to work in Safety and bandits), but the solution is somewhat un-inspired and maybe the only obvious thing to do. In addition, the experimental section is lacking, and only consists of one baseline.  The theoretical results seem fine, but again perhaps fairly straightforward from existing results in GP bandits.\n\n**Missing references:** This work is also to the work on safety in the multi-armed bandits literature. You may want to include citations to:\n\nWang, Zhenlin, Andrew J. Wagenmaker, and Kevin Jamieson. \"Best arm identification with safety constraints.\" *International Conference on Artificial Intelligence and Statistics*. PMLR, 2022.\n\nAmani, Sanae, Mahnoosh Alizadeh, and Christos Thrampoulidis. \"Linear stochastic bandits under safety constraints.\" *Advances in Neural Information Processing Systems*, 32 (2019).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of contextual combinatorial GP bandits with group constraints. Motivated by an example arising from federated learning, the authors consider a multi-armed bandit problem with changing arm sets, where in each round the agent chooses a “super-arm” to pull. The super-arm is a subset of the arms, and the agent observes rewards for each arm in the subset along with the reward of the super arm. Their goal is to a) minimize the total regret of pulling sub-optimal super arms, b) minimize the regret that arises from not satisfying “group constraints”. Groups are also subsets of the arms, and the agent needs to ensure that the reward received from various intersections between groups and subsets are above a threshold. The authors define the problem, provide an algorithm and some theory, and then an experiment. ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Generally I do not feel the need when reviewing the paper to provide feedback paragraph-by-paragraph. However, in this case, the paper was incredibly challenging to read and I think that if the authors address my concerns below, it may help greatly.\n\nList:\n\n- 2.2\n    - This section is one of the most important in the paper since it defines the problem, but it was also very challenging to understand. To even parse the problem statement, I had to refer to Chen ‘18 many times.\n    - The notation of $r_1, r_2$ are just used without being properly defined. In addition $f_1$ and $f_2$ are just used as well.\n    - What does the notation $x_{t,S}$ refer to? Presumably the contexts of the vectors in $S$ - but this notation is not defined.\n    - In Assumption 1, 2,3,4 - you use $\\mathbf{f}$. However, $f$ is the expected reward function. It is very confusing for the reader.\n- 2.4.1\n    - What is “a comprising group”?\n    - “which satisfy”\n    - Maybe use: $ G’\\subset 2^{|M_t|}| \\exists G, G’\\subset G, …  $\n    - In general I did not understand this discussion.\n- 2.4.2\n    - Should it be $u(f_1(x_t…))$? What is $\\hat{f}_{t,1}$?\n- 2.8\n    - I must confess, I did not understand this section at all. The Federated learning/crowdsourcing application seems interesting - but I don’t understand what is happening in this section. Firstly, what is a “client request pair”? I Googled this term and failed to find it. Also, what is “information leakage”? How about “data set usage”? Is it possible to give an application which is maybe a little less technical and easier to understand? There also seems to be an aspect of the problem which refers to clients leaving - is this related to the changing arm sets in the model? I only got some sense of what was happening here by looking at the setup in 5.1. You may want to reorganize this discussion.\n- Section 3\n    - What is the notation $[[t-1]]$?\n    - What is a satisfying index?\n    - In the algorithm, should line 8 be in the algorithm box?\n    - Line 12 - is this where you observe $V_G$ and $r$? if so, then use this notation.\n- Section 5\n    - In Section 5.1: Maybe don’t use $x$ for the portion of the dataset since it is already the context?\n    - Maybe in the legend of Figure 2, you can explain what the blue lines are instead of just in the caption?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "gZgmG9vI9u", "reviewer": "Reviewer_9crF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, this paper needs to show novelties or large contributions in one of the following two aspects.\n\n    This paper's setup is not justified with reasonable real-world applications. There are too many additional requirements attached to the setup, which may limit the practical applications of the algorithm in the real world.\n    This paper does not show high-quality theoretical results. To be more specific, the upper bounds of the algorithms have terms such as \\gamma which is related to the maximal information gain. However, there is no clear statement about i) whether this term is necessary which can be shown by lower bound results but not included in this paper; and ii) How the \\gamma term may increase with the number of actions, or other conditions of the environment.\n\nIn conclusion, this paper studies a new problem whose real-world applications/practical needs are not well illustrated. Besides, the theoretical results in this paper have many areas to improve. Thus, I tend to vote a major revision.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of regret minimization of conspiratorial contextual bandits with groups and changing actions in the federated bandit scenario. The paper proposes a new algorithm TCGP-UCB for this new bandit problem and shows a regret upper bound \\tilde{O}(\\sqrt{KT\\gamma}), where K is the number of arms, T is the time horizon, and \\gamma is a parameter determined by the bandit bandit environment. The paper also conducts some numerical simulations and show improvements\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Make more justifications about the setup of the paper, including how it can be applied in practical use cases.  \n2. Show that the theoretical upper bound of the algorithm in this paper is good enough by i) making it clear how the \\gamma term would change with the instance and why it is necessary; and ii) show lower bound results of the problem. ", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "h6SwBDr66H", "reviewer": "Reviewer_98o9", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\nI think that the paper is motivated by a specific applicative example (federated learning with privacy constraints)\n\n\nCons:\nThe problem definition is somehow not coherent with the target application.\n\nI think the newly defined regret concept can be further investigated to fit better the considered applicative case. \n\nThe dependence of the information gained w.r.t. the characterizing quantity of the setting should be detailed. \n\nThe experimental section is not fully convincing since it has been based on a single synthetic experiment whose parameters are not likely to represent a real-world case.\n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies a specific instance of the combinatorial mab problem in which the distribution of the reward and the constraint we have on a subset of the arms follows a GP distribution. The authors propose an algorithm based on the UCB approach to minimize a specific definition of regret that takes into account the suboptimality of the selected arms and the violation of the abovementioned constraints. The authors propose a theoretical analysis of the proposed algorithm and a brief experimental analysis of the proposed solution.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Regret definition: can you extend the framework to consider the number of times the constraint is violated?\nFrom the definition of the problem you provided in section 2.8, is seems that a regret formulation in which the number of violations is considered would be more appropriate.\n\nInformation gain: It would help to evaluate the complexity of the model having an explicit relationship between the two information gains.\nMoreover, while it is well studied the behaviour of the information gain on standard GP, I would like to have more information and comments on this new definition of information gain. For instance, how does it scales with standard linear and gaussian kernels\n\nParameter \\zeta: it is not clear what this parameter is in the setting you are describing. Indeed, the two regrets are not comparable, therefore considering them in a linearly combined way does not provide any information on the goodness of the proposed method.\n\nComparison: you should compare this approach with other gaussian or GP-based solutions for CMAB. For instance:\n- Wang, Siwei, and Wei Chen. \"Thompson sampling for combinatorial semi-bandits.\" International Conference on Machine Learning. PMLR, 2018.\n- Nuara, Alessandro, et al. \"A combinatorial-bandit algorithm for the online joint bid/budget optimization of pay-per-click advertising campaigns.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 32. No. 1. 2018.\n\nThe experimental section is really poor. The experiments are limited to a specific synthetically generated setting and are not providing enough evidence comparing what is proposed here with state-of-the-art. The same comment hold also for the experiments provided in the supplemental material.\n\nMinor changes:\nWe consider the scenario when -> We consider the scenario in which\nSection 1.1 please explain the difference between \\bar{\\gamma}_T and \\gamma_T\nIn accord with our goal -> In accordance with our goal,\nreduces the problem to a combinatorial version of satisfying -> not clear\n", "broader_impact_concerns": "I do not think that the paper has ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers seem to be happy with the effort the authors put in addressing their concerns. The quality of the paper has improved compared to the initial submission. I agree with the reviewers that from a bandit perspective the contribution of the paper is minor and adding more baselines can strengthen the experimental section. However, the reviewers found the overall quality of the paper satisfactory and they think it could be useful for TMLR audience. I vote for the acceptance and strongly recommend the authors to ensure that they address all the reviewers' comments in the final version of the paper.
Decision: Accept (poster)