Proceedings

Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed Payoffs

Video Download BibTeX Cite

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. Main track. Pages 2936-2942.

https://doi.org/10.24963/ijcai.2020/406

© 2020 International Joint Conferences on Artificial Intelligence

Abstract

In this paper, we study the problem of stochastic linear bandits with finite action sets. Most of existing work assume the payoffs are bounded or sub-Gaussian, which may be violated in some scenarios such as financial markets. To settle this issue, we analyze the linear bandits with heavy-tailed payoffs, where the payoffs admit finite 1+epsilon moments for some epsilon in (0,1]. Through median of means and dynamic truncation, we propose two novel algorithms which enjoy a sublinear regret bound of widetilde{O}(d^(1/2)T^(1/(1+epsilon))), where d is the dimension of contextual information and T is the time horizon. Meanwhile, we provide an Omega(d^(epsilon/(1+epsilon))T^(1/(1+epsilon))) lower bound, which implies our upper bound matches the lower bound up to polylogarithmic factors in the order of d and T when epsilon=1. Finally, we conduct numerical experiments to demonstrate the effectiveness of our algorithms and the empirical results strongly support our theoretical guarantees.

  1. [Abbasi-yadkori et al., 2011] Yasin Abbasi-yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for lin- ear stochastic bandits. In Advances in Neural Information Processing Systems 24, pages 2312-2320. 2011.
  2. [Abe et al., 2003] Naoki Abe, Alan W Biermann, and Philip M Long. Reinforcement learning with immediate rewards and linear hypotheses. Algorithmica, 37(4):263- 293, 2003.
  3. [Agarwal et al., 2013] A. Agarwal, D. Foster, D. Hsu, S. Kakade, and A. Rakhlin. Stochastic convex optimiza- tion with bandit feedback. SIAM Journal on Optimization, 23(1):213-240, 2013.
  4. [Audibert and Catoni, 2011] Jean-Yves Audibert and Olivier Catoni. Robust linear least squares regression. The Annals of Statistics, 39(5):2766-2794, 2011.
  5. [Auer, 2002] Peter Auer. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3:397-422, 2002.
  6. [Brownlees et al., 2015] Christian Brownlees, Emilien Joly, and Gábor Lugosi. Empirical risk minimization for heavy- tailed losses. The Annals of Statistics, 43(6):2507-2536, 2015.
  7. [Bubeck and Cesa-Bianchi, 2012] Sébastien Bubeck and Nicolò Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 5(1):1-122, 2012.
  8. [Bubeck et al., 2011] Sébastien Bubeck, Gilles Stoltz, and Jia Yuan Yu. Lipschitz bandits without the lipschitz con- stant. In Proceedings of the 22Nd International Confer- ence on Algorithmic Learning Theory, pages 144-158, 2011.
  9. [Bubeck et al., 2013] S. Bubeck, N. Cesa-Bianchi, and G. Lugosi. Bandits with heavy tail. IEEE Transactions on Information Theory, 59(11):7711-7717, 2013.
  10. [Bubeck et al., 2015] Sébastien Bubeck, Ofer Dekel, Tomer Koren, and Yuval Peres. Bandit convex optimization: √ T regret in one dimension. In Proceedings of The 28th Con- ference on Learning Theory, pages 266-278, 2015.
  11. [Catoni, 2012] Olivier Catoni. Challenging the empirical mean and empirical variance: A deviation study. Annales de l'I.H.P. Probabilités et statistiques, 48(4):1148-1185, 2012.
  12. [Chu et al., 2011] Wei Chu, Lihong Li, Lev Reyzin, and Robert Schapire. Contextual bandits with linear payoff functions. In Proceedings of the 14th International Con- ference on Artificial Intelligence and Statistics, pages 208- 214, 2011.
  13. [Cont and Bouchaud, 2000] Rama Cont and Jean-Philipe Bouchaud. Herd behavior and aggregate fluctuations in financial markets. Macroeconomic Dynamics, 4(02):170- 196, 2000.
  14. [Dani et al., 2008] Varsha Dani, Thomas P. Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In Proceedings of the 21st Annual Con- ference on Learning, pages 355-366, 2008.
  15. [Foss et al., 2013] Sergey Foss, Dmitry Korshunov, and Stan Zachary. An Introduction to Heavy-Tailed and Subexpo- nential Distributions. Springer, New York, 2013.
  16. [Golub and Van Loan, 1996] Gene H. Golub and Charles F. Van Loan. Matrix Computations (3rd Ed.). Johns Hopkins University Press, USA, 1996.
  17. [Hsu and Sabato, 2016] Daniel Hsu and Sivan Sabato. Loss minimization and parameter estimation with heavy tails. Journal of Machine Learning Research, 17(18):1-40, 2016.
  18. [Kleinberg et al., 2008] Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Multi-armed bandits in met- ric spaces. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 681-690, 2008.
  19. [Lai and Robbins, 1985] T. L. Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in Applied Mathematics, 6(1):4-22, 1985.
  20. [Lu et al., 2019] Shiyin Lu, Guanghui Wang, Yao Hu, and Lijun Zhang. Optimal algorithms for Lipschitz bandits with heavy-tailed rewards. In Proceedings of the 36th International Conference on Machine Learning, pages 4154-4163, 2019.
  21. [Medina and Yang, 2016] Andres Munoz Medina and Scott Yang. No-regret algorithms for heavy-tailed linear ban- dits. In Proceedings of the 33rd International Conference on International Conference on Machine Learning, pages 1642-1650, 2016.
  22. [Robbins, 1952] Herbert Robbins. Some aspects of the se- quential design of experiments. Bulletin of the American Mathematical Society, 58(5):527-535, 1952.
  23. [Roberts et al., 2015] James A Roberts, Tjeerd W Boonstra, and Michael Breakspear. The heavy tail of the human brain. Current Opinion in Neurobiology, 31:164-172, 2015.
  24. [Shao et al., 2018] Han Shao, Xiaotian Yu, Irwin King, and Michael R. Lyu. Almost optimal algorithms for lin- ear stochastic bandits with heavy-tailed payoffs. In Ad- vances in Neural Information Processing Systems 32, pages 8430-8439, 2018.
  25. [Xue et al., 2020] Bo Xue, Guanghui Wang, Yimu Wang, and Lijun Zhang. Nearly optimal regret for stochastic linear bandits with heavy-tailed payoffs. arXiv preprint, abs/2004.13465, 2020.
  26. [Zhang and Zhou, 2018] Lijun Zhang and Zhi-Hua Zhou. ℓ 1 - regression with heavy-tailed distributions. In Advances in Neural Information Processing Systems 31, pages 1084- 1094, 2018.
  27. [Zhang et al., 2016] Lijun Zhang, Tianbao Yang, Rong Jin, Yichi Xiao, and Zhi-Hua Zhou. Online stochastic linear optimization under one-bit feedback. In Proceedings of the 33rd International Conference on Machine Learning, pages 392-401, 2016.

References were extracted automatically from the PDF and may contain errors.

Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards