  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{\lambda^*(K)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.
