Almost Optimal Algorithms for Linear Stochastic Bandits with Heavy-Tailed Payoffs
Refereed conference paper presented and published in conference proceedings


全文

其它資訊
摘要In linear stochastic bandits, it is commonly assumed that payoffs are with sub-Gaussian noises. In this paper, under a weaker assumption on noises, we study the problem of \underline{lin}ear stochastic {\underline b}andits with h{\underline e}avy-{\underline t}ailed payoffs (LinBET), where the distributions have finite moments of order 1+ϵ, for some ϵ∈(0,1]. We rigorously analyze the regret lower bound of LinBET as Ω(T11+ϵ), implying that finite moments of order 2 (i.e., finite variances) yield the bound of Ω(T‾‾√), with T being the total number of rounds to play bandits. The provided lower bound also indicates that the state-of-the-art algorithms for LinBET are far from optimal. By adopting median of means with a well-designed allocation of decisions and truncation based on historical information, we develop two novel bandit algorithms, where the regret upper bounds match the lower bound up to polylogarithmic factors. To the best of our knowledge, we are the first to solve LinBET optimally in the sense of the polynomial order on T. Our proposed algorithms are evaluated based on synthetic datasets, and outperform the state-of-the-art results.
著者Han Shao, Xiaotian Yu, Irwin King, Michael R. Lyu
會議名稱32nd Conference on Neural Information Processing Systems (NIPS)
會議開始日02.12.2018
會議完結日08.12.2018
會議地點Montreal, Canada
會議國家/地區加拿大
會議論文集題名Advances in Neural Information Processing Systems 31 (NIPS 2018)
出版年份2018
月份12
國際標準期刊號1049-5258
語言美式英語

上次更新時間 2019-12-12 於 04:06