2023-07-02-gou23a.md

abstract	openreview	title	layout	series	publisher	issn	id	month	tex_title	firstpage	lastpage	page	order	cycles	bibtex_author	author	date	address	container-title	volume	genre	issued	pdf	extras
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 <em>clique covering</em> of the feedback graph. The key idea is to estimate the reward means of the selected arm’s neighbors by more refined robust estimators, and to construct a graph-based upper confidence bound for selecting candidates. Secondly, we design another elimination-based strategy and improve the regret bound to a gap-based sum with size controlled by the <em>independence number</em> of the feedback graph. For benign graphs, the <em>independence number</em> could be smaller than the size of the <em>clique covering</em>, resulting in tighter regret bounds. Finally, we conduct experiments on synthetic data to demonstrate the effectiveness of our methods.	LUE-tmFTDrm	Stochastic Graphical Bandits with Heavy-Tailed Rewards	inproceedings	Proceedings of Machine Learning Research	PMLR	2640-3498	gou23a	0	Stochastic Graphical Bandits with Heavy-Tailed Rewards	734	744	734-744	734	false	Gou, Yutian and Yi, Jinfeng and Zhang, Lijun	given family Yutian Gou given family Jinfeng Yi given family Lijun Zhang	2023-07-02		Proceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence	216	inproceedings	date-parts 2023 7 2	https://proceedings.mlr.press/v216/gou23a/gou23a.pdf	label link Supplementary PDF https://proceedings.mlr.press/v216/gou23a/gou23a-supp.pdf