Corruption Robust Thompson Sampling for Gaussian Bandits

Yinglun Xu, Zhiwei Wang, Gagandeep Singh
Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, PMLR 300:307-315, 2026.

Abstract

Thompson sampling is one of the most popular learning algorithms for online sequential decision-making problems and has rich real-world applications. However, traditional Thompson sampling algorithms are limited by the assumption that the rewards received are uncorrupted, which may not hold in real-world applications where adversarial reward poisoning exists. To make Thompson sampling more reliable, our goal is to make it robust against adversarial reward poisoning. Particularly, we consider a strong attack threat model where an adversary applies corruption after observing the agent’s actions. The main challenge is that one can no longer compute the actual posteriors for the true reward, as the agent can only observe the rewards after corruption. In this work, we solve this problem by computing pseudo-posteriors that are less likely to be manipulated by the attack. Particularly, we focus on two popular settings: stochastic bandits and contextual linear bandits with priors as Gaussian distributions. \textbf{We are the first} to propose robust algorithms based on Thompson sampling for the two bandit settings in both cases where the agent is aware or unaware of the attacker’s budget. We theoretically show that our algorithms guarantee near-optimal regret under any attack strategy.

Cite this Paper

BibTeX
@InProceedings{pmlr-v300-xu26b, title = { Corruption Robust Thompson Sampling for Gaussian Bandits }, author = {Xu, Yinglun and Wang, Zhiwei and Singh, Gagandeep}, booktitle = {Proceedings of The 29th International Conference on Artificial Intelligence and Statistics}, pages = {307--315}, year = {2026}, editor = {Khan, Emtiyaz and Li, Yingzhen and Solin, Arno and Ramdas, Aaditya}, volume = {300}, series = {Proceedings of Machine Learning Research}, month = {02--05 May}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v300/main/assets/xu26b/xu26b.pdf}, url = {https://proceedings.mlr.press/v300/xu26b.html}, abstract = { Thompson sampling is one of the most popular learning algorithms for online sequential decision-making problems and has rich real-world applications. However, traditional Thompson sampling algorithms are limited by the assumption that the rewards received are uncorrupted, which may not hold in real-world applications where adversarial reward poisoning exists. To make Thompson sampling more reliable, our goal is to make it robust against adversarial reward poisoning. Particularly, we consider a strong attack threat model where an adversary applies corruption after observing the agent’s actions. The main challenge is that one can no longer compute the actual posteriors for the true reward, as the agent can only observe the rewards after corruption. In this work, we solve this problem by computing pseudo-posteriors that are less likely to be manipulated by the attack. Particularly, we focus on two popular settings: stochastic bandits and contextual linear bandits with priors as Gaussian distributions. \textbf{We are the first} to propose robust algorithms based on Thompson sampling for the two bandit settings in both cases where the agent is aware or unaware of the attacker’s budget. We theoretically show that our algorithms guarantee near-optimal regret under any attack strategy. } }
Endnote
%0 Conference Paper %T Corruption Robust Thompson Sampling for Gaussian Bandits %A Yinglun Xu %A Zhiwei Wang %A Gagandeep Singh %B Proceedings of The 29th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2026 %E Emtiyaz Khan %E Yingzhen Li %E Arno Solin %E Aaditya Ramdas %F pmlr-v300-xu26b %I PMLR %P 307--315 %U https://proceedings.mlr.press/v300/xu26b.html %V 300 %X Thompson sampling is one of the most popular learning algorithms for online sequential decision-making problems and has rich real-world applications. However, traditional Thompson sampling algorithms are limited by the assumption that the rewards received are uncorrupted, which may not hold in real-world applications where adversarial reward poisoning exists. To make Thompson sampling more reliable, our goal is to make it robust against adversarial reward poisoning. Particularly, we consider a strong attack threat model where an adversary applies corruption after observing the agent’s actions. The main challenge is that one can no longer compute the actual posteriors for the true reward, as the agent can only observe the rewards after corruption. In this work, we solve this problem by computing pseudo-posteriors that are less likely to be manipulated by the attack. Particularly, we focus on two popular settings: stochastic bandits and contextual linear bandits with priors as Gaussian distributions. \textbf{We are the first} to propose robust algorithms based on Thompson sampling for the two bandit settings in both cases where the agent is aware or unaware of the attacker’s budget. We theoretically show that our algorithms guarantee near-optimal regret under any attack strategy.
APA
Xu, Y., Wang, Z. & Singh, G.. (2026). Corruption Robust Thompson Sampling for Gaussian Bandits . Proceedings of The 29th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 300:307-315 Available from https://proceedings.mlr.press/v300/xu26b.html.

Related Material