(Private) Kernelized Bandits with Distributed Biased Feedback

Fengjiao Li, Xingyu Zhou, Bo Ji

Introduction

In the landscape of online learning, the multi-armed bandit (MAB) framework provides a robust model for sequential decision-making under uncertainty. However, as applications scale to global franchises or massive telecommunications networks, the standard assumptions of the MAB model—specifically, receiving direct, unbiased observations of a global reward—often fail. Real-world systems are frequently distributed, where feedback is aggregated from a heterogeneous population of users, each introducing their own local bias.

In the paper "(Private) Kernelized Bandits with Distributed Biased Feedback," authors Fengjiao Li, Xingyu Zhou, and Bo Ji address these complexities. They introduce a novel framework designed to handle kernelized bandits—which model complex, non-linear reward functions—under the constraints of biased feedback, high computational overhead, and the necessity for data privacy.

The Challenge: Bias, Computation, and Communication

Kernelized bandits typically utilize Reproducing Kernel Hilbert Spaces (RKHS) to capture intricate reward patterns. While powerful, they suffer from three primary bottlenecks in distributed environments:

  1. User Heterogeneity and Bias: In a distributed setting, an agent might only observe feedback from a subset of users. If these users are not representative of the global population (e.g., regional preferences in a retail chain), the feedback is inherently biased. Standard algorithms that assume unbiased noise fail to converge to the global optimum in these scenarios.
  2. Computational Complexity: Kernelized bandit algorithms, such as GP-UCB, often require inverting a kernel matrix at every time step. This leads to a computational complexity of $O(T^3)$ over $T$ rounds, which is prohibitive for long horizons.
  3. Communication Overhead: Constant synchronization between a central agent and distributed users creates a massive communication bottleneck, especially when dealing with high-dimensional kernel representations.

The DPBE Algorithm

To overcome these hurdles, the authors propose Distributed Phase-then-Batch-based Elimination (DPBE). The algorithm is built on three strategic pillars:

1. User-Sampling for Bias Mitigation

To address the bias stemming from user heterogeneity, DPBE employs a dynamic user-sampling strategy. In each phase of the algorithm, the agent samples a subset of users. By increasing the number of participants over time—governed by a parameter $\alpha$—the algorithm effectively "smooths out" the local biases, allowing the estimated reward to converge toward the true global mean.

2. Batching and Rare-Switching

To solve the computational and communication issues, DPBE moves away from step-by-step updates. Instead, it utilizes a "batching" approach where the same action is played for a sequence of rounds. Updates to the Gaussian Process (GP) model only occur at the end of these batches. This "rare-switching" strategy significantly reduces the frequency of matrix inversions and limits the amount of data transmitted between users and the central agent.

3. Maximum Variance Reduction

For action selection, DPBE focuses on points within the decision space where the model's uncertainty—represented by the posterior variance—is highest. This ensures that the algorithm explores the space efficiently, quickly discarding sub-optimal regions and focusing on the most promising actions.

Privacy for Free

A significant contribution of this work is the extension of the framework to DP-DPBE, which incorporates Differential Privacy (DP). The authors demonstrate that privacy can be integrated into the distributed feedback loop using central, local, or shuffle DP models.

Crucially, the theoretical analysis reveals a "privacy for free" phenomenon: the additional regret introduced by the noise required for differential privacy is a lower-order term compared to the regret caused by user-sampling and inherent bias. This implies that robust privacy guarantees can be provided with negligible impact on the overall performance of the bandit learner.

Experimental Validation

The researchers evaluated DPBE against state-of-the-art baselines using synthetic and real-world datasets:

  • Synthetic RKHS Functions: Using Squared Exponential (SE) kernels to simulate complex reward landscapes.
  • Optimization Benchmarks: Standard test functions such as the Sphere, Six-hump Camel, and Michalewicz functions.
  • CMU Light Sensor Data: A real-world dataset involving 41 sensors, simulating a distributed sensing environment with heterogeneous nodes.

Key Findings

  • Performance: DPBE achieves sublinear regret, specifically $\tilde{O}(T^{1-\alpha/2} + \sqrt{\gamma_T T})$, where $\gamma_T$ represents the maximum information gain of the kernel.
  • Efficiency: Empirical results showed DPBE to be approximately 30x faster than standard GP-UCB. Furthermore, it reduced communication costs by roughly 3x compared to non-batched distributed variants.
  • Scalability: The algorithm maintained near-optimal performance even as the complexity of the reward function and the number of users increased.

Conclusion and Future Directions

DPBE represents the first algorithm to successfully navigate the intersection of kernelized bandits, biased distributed feedback, and differential privacy. By balancing the trade-offs between bias mitigation and resource efficiency, it provides a practical path for deploying sophisticated online learning models in large-scale, privacy-sensitive environments.

Future research may focus on the "low-communication" regime (where $\alpha < 1$), where bias remains a dominant factor in regret. Closing the theoretical gap between current upper bounds and lower bounds in the presence of biased feedback remains an open and vital challenge for the field.

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 \emph{distributed phase-then-batch-based elimination (\texttt{DPBE})} algorithm, which samples users in phases for collecting feedback to reduce the bias and employs \emph{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 \texttt{DPBE} achieves a sublinear regret of $\tilde{O}(T^{1-\alpha/2}+\sqrt{\gamma_T T})$, where $\alpha\in (0,1)$ is the user-sampling parameter one can tune. Moreover, \texttt{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 \emph{differential privacy} models (including the central, local, and shuffle models), we generalize \texttt{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},
}
Figure