(Private) Kernelized Bandits with Distributed Biased Feedback

Fengjiao Li, Xingyu Zhou, Bo Ji

In the world of online learning, the "multi-armed bandit" problem is a classic: how do you choose a sequence of actions to maximize rewards when you don't know the underlying reward function? While standard versions of this problem assume you get a direct, noisy look at the truth, real-world applications—like dynamic pricing for a global franchise or configuring a massive cellular network—are rarely that simple.

A new paper titled "(Private) Kernelized Bandits with Distributed Biased Feedback" by Fengjiao Li, Xingyu Zhou, and Bo Ji introduces a robust framework for these complex, distributed scenarios.

TL;DR

The authors propose DPBE (Distributed Phase-then-Batch-based Elimination), the first algorithm to tackle kernelized bandits where feedback is distributed across a population and inherently biased due to user heterogeneity. DPBE achieves sublinear regret while significantly slashing communication and computation costs, all while offering "privacy for free" through various differential privacy models.

What Problem Does This Paper Address?

Most bandit algorithms assume that when you take an action, you receive a noisy but unbiased observation of the global reward. In reality, rewards are often the aggregate of many distributed users.

Imagine McDonald’s headquarters trying to optimize a new burger price. They can’t see every transaction in real-time. Instead, they might collect data from a subset of local stores. However, a store in New York has different customer preferences than one in rural Ohio. This "user heterogeneity" means the feedback is biased—it doesn't perfectly represent the global population.

Furthermore, kernelized bandits (which use Reproducing Kernel Hilbert Spaces to model complex, non-linear functions) are notoriously "heavy." They usually require $O(T^3)$ computation time because they involve inverting large matrices at every step. In a distributed system, sending data back and forth constantly also creates a massive communication bottleneck.

Methods

The authors introduce the Distributed Phase-then-Batch-based Elimination (DPBE) algorithm. It tackles the three-headed monster of bias, computation, and communication through three clever design choices:

  1. User-Sampling: To mitigate the bias from individual heterogeneous users, the agent samples a subset of users in each phase. By increasing the number of participants over time (controlled by a parameter $\alpha$), the agent "smooths out" the bias.
  2. Batching & Rare-Switching: Instead of updating the model after every single round, DPBE plays the same action for a "batch" of rounds. This reduces the number of times the agent has to perform expensive Gaussian Process (GP) updates and shrinks the dimensions of the matrices involved in those calculations.
  3. Maximum Variance Reduction: For action selection, the algorithm chooses points where the model’s uncertainty (posterior variance) is highest. This ensures efficient exploration of the decision space.

The authors also extend this to DP-DPBE, incorporating Differential Privacy (DP). They show how to inject noise into the aggregated feedback to protect user data under central, local, and shuffle DP models.

Datasets

The researchers validated DPBE and its private variants using three distinct types of data:

  • Synthetic Functions: Functions sampled from an RKHS with a Squared Exponential (SE) kernel.
  • Global Optimization Benchmarks: Standard mathematical test functions including the Sphere, Six-hump Camel, and Michalewicz functions.
  • Real-World Data: The CMU Intelligent Workplace Light Sensor Data, which contains light level readings from 41 sensors over time, used to simulate a distributed sensing environment.

Key Insights and Ideas

  • "Privacy for Free": One of the most striking findings is that the additional regret (error) introduced by privacy-preserving noise is a "lower-order term." In simpler terms, the error caused by user-sampling and inherent bias is much larger than the error added to keep the data private. This means you can have privacy without a significant hit to performance.
  • The Power of Batching: By reformulating the GP update to work on batches rather than individual rounds, the authors reduced the computational complexity from $O(T^3)$ to something much closer to linear in $T$, making kernelized bandits practical for much larger horizons.
  • The $\alpha$ Trade-off: The user-sampling parameter $\alpha$ acts as a dial. A higher $\alpha$ reduces bias (lower regret) but increases communication costs because more users must report back.

Key Results

  • Regret: DPBE achieves a sublinear regret of $\tilde{O}(T^{1-\alpha/2} + \sqrt{\gamma_T T})$, where $\gamma_T$ is the maximum information gain of the kernel.
  • Efficiency: In simulations, DPBE was roughly 30x faster than standard GP-UCB and reduced communication costs by about 3x compared to non-batched versions.
  • Scalability: The algorithm maintained near-optimal performance even as the complexity of the underlying reward function increased, outperforming state-of-the-art baselines like BPE and GP-UCB in distributed, biased settings.

Limitations and Future Work

While DPBE performs excellently in the "high-communication" regime ($\alpha \geq 1$), the authors note that in the "low-communication" regime ($\alpha < 1$), the bias term in the regret can become dominant.

An open theoretical challenge remains: closing the gap. Current lower bounds for kernelized bandits don't account for user-sampling or biased feedback. Future work could involve deriving tighter bounds that specifically capture the trade-offs between privacy, communication, and bias mitigation. Additionally, exploring different batching strategies (beyond rare-switching) might further optimize the computation-regret frontier.

Summary updated

Abstract

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 distributed phase-then-batch-based elimination (DPBE) 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 DPBE achieves a sublinear regret of ~O(T1-&#945;/2 +&#8730;&#947;T T), where &#945; &#8712; (0,1) is the user-sampling parameter one can tune. Moreover, DPBE 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 DPBE 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.
BibTeX
@article{li2023private,
  author = {Fengjiao Li and Xingyu Zhou and Bo Ji},
  title = {{(Private) Kernelized Bandits with Distributed Biased Feedback}},
  journal = {Proc. ACM Meas. Anal. Comput. Syst.},
  year = {2023},
  doi = {10.1145/3579318},
}

Loading related content...

Figure