UAI 2023poster3 citations
Stochastic Graphical Bandits with Heavy-Tailed Rewards
Yutian Gou, Jinfeng Yi, Lijun Zhang
Abstract
We consider stochastic graphical bandits, where after pulling an arm, the decision maker observes rewards of not only the chosen arm but also its neighbors in a feedback graph. Most of existing work assumes that the rewards are drawn from bounded or at least sub-Gaussian distributions, which however may be violated in many practical scenarios such as social advertising and financial markets. To settle this issue, we investigate stochastic graphical bandits with heavy-tailed rewards, where the distributions have finite moments of order $1+\epsilon$, for some $\epsilon\in(0, 1]$. Firstly, we develop one UCB-type algorithm, whose expected regret is upper bounded by a sum of gap-based quantities over the
BibTeX
@InProceedings{pmlr-v216-gou23a,
title = {Stochastic Graphical Bandits with Heavy-Tailed Rewards},
author = {Gou, Yutian and Yi, Jinfeng and Zhang, Lijun},
booktitle = {Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence},
pages = {734--744},
year = {2023},
editor = {Evans, Robin J. and Shpitser, Ilya},
volume = {216},
series = {Proceedings of Machine Learning Research},
month = {31 Jul--04 Aug},
publisher = {PMLR},
pdf = {https://proceedings.mlr.press/v216/gou23a/gou23a.pdf},
url = {https://proceedings.mlr.press/v216/gou23a.html},
abstract = {We consider stochastic graphical bandits, where after pulling an arm, the decision maker observes rewards of not only the chosen arm but also its neighbors in a feedback graph. Most of existing work assumes that the rewards are drawn from bounded or at least sub-Gaussian distributions, which however may be violated in many practical scenarios such as social advertising and financial markets. To settle this issue, we investigate stochastic graphical bandits with heavy-tailed rewards, where the distributions have finite moments of order $1+\epsilon$, for some $\epsilon\in(0, 1]$. Firstly, we develop one UCB-type algorithm, whose expected regret is upper bounded by a sum of gap-based quantities over the