# (Private) Kernelized Bandits with Distributed Biased Feedback

arXiv: https://arxiv.org/abs/2301.12061 · HTML: https://mlsanity.com/paper/2301.12061/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 45 references that are in the map.
- First posted on arXiv 28 Jan 2023.

## Builds on (most cited first, 29 of 29)

- [Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization](https://mlsanity.com/paper/1603.06560/) (2016)
- [Federated Learning in Mobile Edge Networks: A Comprehensive Survey](https://mlsanity.com/paper/1909.11875/) (2019)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Gaussian Processes and Kernel Methods: A Review on Connections and Equivalences](https://mlsanity.com/paper/1807.02582/) (2018)
- [On Information Gain and Regret Bounds in Gaussian Process Bandits](https://mlsanity.com/paper/2009.06966/) (2020)
- [Learning with Good Feature Representations in Bandits and in RL with a Generative Model](https://mlsanity.com/paper/1911.07676/) (2019)
- [Distributed Differential Privacy via Shuffling](https://mlsanity.com/paper/1808.01394/) (2018)
- [Federated Bayesian Optimization via Thompson Sampling](https://mlsanity.com/paper/2010.10154/) (2020)
- [Gaussian Process Bandit Optimization with Few Batches](https://mlsanity.com/paper/2110.07788/) (2021)
- [High-Dimensional Experimental Design and Kernel Bandits](https://mlsanity.com/paper/2105.05806/) (2021)
- [Misspecified Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2111.05008/) (2021)
- [Optimal Order Simple Regret for Gaussian Process Bandits](https://mlsanity.com/paper/2108.09262/) (2021)
- [Prochlo: Strong Privacy for Analytics in the Crowd](https://mlsanity.com/paper/1710.00901/) (2017)
- [Bandit optimisation of functions in the Mat'ern kernel RKHS](https://mlsanity.com/paper/2001.10396/) (2020)
- [An Optimal Private Stochastic-MAB Algorithm Based on an Optimal Private Stopping Rule](https://mlsanity.com/paper/1905.09383/) (2019)
- [Shuffle Private Linear Contextual Bandits](https://mlsanity.com/paper/2202.05567/) (2022)
- [Differentially Private Multi-Armed Bandits in the Shuffle Model](https://mlsanity.com/paper/2106.02900/) (2021)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Bayesian Optimization under Heavy-tailed Payoffs](https://mlsanity.com/paper/1909.07040/) (2019)
- [Local Differential Privacy for Bayesian Optimization](https://mlsanity.com/paper/2010.06709/) (2020)
- [Shuffle Private Stochastic Convex Optimization](https://mlsanity.com/paper/2106.09805/) (2021)
- [Distributed Differential Privacy in Multi-Armed Bandits](https://mlsanity.com/paper/2206.05772/) (2022)
- [Near-linear Time Gaussian Process Optimization with Adaptive Batching and Resparsification](https://mlsanity.com/paper/2002.09954/) (2020)
- [Pure Exploration in Kernel and Neural Bandits](https://mlsanity.com/paper/2106.12034/) (2021)
- [Collaborative Pure Exploration in Kernel Bandit](https://mlsanity.com/paper/2110.15771/) (2021)
- [Scaling Gaussian Process Optimization by Evaluating a Few Unique Candidates Multiple Times](https://mlsanity.com/paper/2201.12909/) (2022)
- [No-Regret Algorithms for Private Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2102.12467/) (2021)
- [A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits](https://mlsanity.com/paper/2202.01850/) (2022)
- [Differentially Private Linear Bandits with Partial Distributed Feedback](https://mlsanity.com/paper/2207.05827/) (2022)

## Built on by (most cited first, 3 of 3)

- [On Differentially Private Federated Linear Contextual Bandits](https://mlsanity.com/paper/2302.13945/) (2023)
- [Differentially Private Episodic Reinforcement Learning with Heavy-tailed Rewards](https://mlsanity.com/paper/2306.01121/) (2023)
- [Federated Online Prediction from Experts with Differential Privacy: Separations and Regret Speed-ups](https://mlsanity.com/paper/2409.19092/) (2024)

## Abstract (arXiv)

In this paper, we study kernelized bandits with distributed biased feedback. This problem is motivated by several real-world applications (such as dynamic pricing, cellular network configuration, and policy making), where users from a large population contribute to the reward of the action chosen by a central entity, but it is difficult to collect feedback from all users. Instead, only biased feedback (due to user heterogeneity) from a subset of users may be available. In addition to such partial biased feedback, we are also faced with two practical challenges due to communication cost and computation complexity. To tackle these challenges, we carefully design a new emphdistributed phase-then-batch-based elimination (textttDPBE) algorithm, which samples users in phases for collecting feedback to reduce the bias and employs maximum variance reduction to select actions in batches within each phase. By properly choosing the phase length, the batch size, and the confidence width used for eliminating suboptimal actions, we show that textttDPBE achieves a sublinear regret of tildeO(T1-α/2+√γT T), where α∈ (0,1) is the user-sampling parameter one can tune. Moreover, textttDPBE can significantly reduce both communication cost and computation complexity in distributed kernelized bandits, compared to some variants of the state-of-the-art algorithms (originally developed for standard kernelized bandits). Furthermore, by incorporating various differential privacy models (including the central, local, and shuffle models), we generalize textttDPBE to provide privacy guarantees for users participating in the distributed learning process. Finally, we conduct extensive simulations to validate our theoretical results and evaluate the empirical performance.