Robust and differentially private stochastic linear bandits
This work addresses privacy and security concerns in online decision-making systems, such as recommendation engines, by providing a novel integration of differential privacy and robustness in bandit algorithms.
The paper tackles the stochastic linear bandit problem by developing algorithms that ensure differential privacy and robustness against adversarial reward corruption, achieving regret bounds under two privacy models.
In this paper, we study the stochastic linear bandit problem under the additional requirements of differential privacy, robustness and batched observations. In particular, we assume an adversary randomly chooses a constant fraction of the observed rewards in each batch, replacing them with arbitrary numbers. We present differentially private and robust variants of the arm elimination algorithm using logarithmic batch queries under two privacy models and provide regret bounds in both settings. In the first model, every reward in each round is reported by a potentially different client, which reduces to standard local differential privacy (LDP). In the second model, every action is "owned" by a different client, who may aggregate the rewards over multiple queries and privatize the aggregate response instead. To the best of our knowledge, our algorithms are the first simultaneously providing differential privacy and adversarial robustness in the stochastic linear bandits problem.