IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2312.15595.html
   My bibliography  Save this paper

Zero-Inflated Bandits

Author

Listed:
  • Haoyu Wei
  • Runzhe Wan
  • Lei Shi
  • Rui Song

Abstract

Many real applications of bandits have sparse non-zero rewards, leading to slow learning rates. A careful distribution modeling that utilizes problem-specific structures is known as critical to estimation efficiency in the statistics literature, yet is under-explored in bandits. To fill the gap, we initiate the study of zero-inflated bandits, where the reward is modeled as a classic semi-parametric distribution called zero-inflated distribution. We carefully design Upper Confidence Bound (UCB) and Thompson Sampling (TS) algorithms for this specific structure. Our algorithms are suitable for a very general class of reward distributions, operating under tail assumptions that are considerably less stringent than the typical sub-Gaussian requirements. Theoretically, we derive the regret bounds for both the UCB and TS algorithms for multi-armed bandit, showing that they can achieve rate-optimal regret when the reward distribution is sub-Gaussian. The superior empirical performance of the proposed methods is shown via extensive numerical studies.

Suggested Citation

  • Haoyu Wei & Runzhe Wan & Lei Shi & Rui Song, 2023. "Zero-Inflated Bandits," Papers 2312.15595, arXiv.org.
    • Handle: RePEc:arx:papers:2312.15595
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2312.15595
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Weron, Rafal, 1996. "Correction to: "On the Chambers–Mallows–Stuck Method for Simulating Skewed Stable Random Variables"," MPRA Paper 20761, University Library of Munich, Germany, revised 2010.
    2. Huiming Zhang & Haoyu Wei, 2022. "Sharper Sub-Weibull Concentrations," Mathematics, MDPI, vol. 10(13), pages 1-29, June.
    3. Bogucki, Robert, 2015. "Suprema of canonical Weibull processes," Statistics & Probability Letters, Elsevier, vol. 107(C), pages 253-263.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Furrer, Hansjorg & Michna, Zbigniew & Weron, Aleksander, 1997. "Stable Lévy motion approximation in collective risk theory," Insurance: Mathematics and Economics, Elsevier, vol. 20(2), pages 97-114, September.
    2. Huiming Zhang & Haoyu Wei & Guang Cheng, 2023. "Tight Non-asymptotic Inference via Sub-Gaussian Intrinsic Moment Norm," Papers 2303.07287, arXiv.org, revised Jan 2024.
    3. Dassios, Angelos & Qu, Yan & Zhao, Hongbiao, 2018. "Exact simulation for a class of tempered stable," LSE Research Online Documents on Economics 86981, London School of Economics and Political Science, LSE Library.
    4. J.-F. Chamayou, 2001. "Pseudo random numbers for the Landau and Vavilov distributions," Computational Statistics, Springer, vol. 16(1), pages 131-152, March.
    5. Weron, Rafał, 2004. "Computationally intensive Value at Risk calculations," Papers 2004,32, Humboldt University of Berlin, Center for Applied Statistics and Economics (CASE).
    6. Fei Wang & Yuhao Deng, 2023. "Non-Asymptotic Bounds of AIPW Estimators for Means with Missingness at Random," Mathematics, MDPI, vol. 11(4), pages 1-14, February.
    7. Luc Devroye & Lancelot James, 2014. "On simulation and properties of the stable law," Statistical Methods & Applications, Springer;Società Italiana di Statistica, vol. 23(3), pages 307-343, August.
    8. Tsionas, Mike, 2012. "Simple techniques for likelihood analysis of univariate and multivariate stable distributions: with extensions to multivariate stochastic volatility and dynamic factor models," MPRA Paper 40966, University Library of Munich, Germany, revised 20 Aug 2012.
    9. Xiaowei Yang & Xinqiao Liu & Haoyu Wei, 2022. "Concentration inequalities of MLE and robust MLE," Papers 2210.09398, arXiv.org, revised Dec 2022.
    10. John C. Frain, 2007. "Small sample power of tests of normality when the alternative is an alpha-stable distribution," Trinity Economics Papers tep0207, Trinity College Dublin, Department of Economics.
    11. Harry Pavlopoulos & George Chronis, 2023. "On highly skewed fractional log‐stable noise sequences and their application," Journal of Time Series Analysis, Wiley Blackwell, vol. 44(4), pages 337-358, July.
    12. Chronis, George A., 2016. "Modelling the extreme variability of the US Consumer Price Index inflation with a stable non-symmetric distribution," Economic Modelling, Elsevier, vol. 59(C), pages 271-277.
    13. Taufer, Emanuele, 2015. "On the empirical process of strongly dependent stable random variables: asymptotic properties, simulation and applications," Statistics & Probability Letters, Elsevier, vol. 106(C), pages 262-271.
    14. Goddard, John & Onali, Enrico, 2012. "Self-affinity in financial asset returns," International Review of Financial Analysis, Elsevier, vol. 24(C), pages 1-11.
    15. Guarcello, C., 2021. "Lévy noise effects on Josephson junctions," Chaos, Solitons & Fractals, Elsevier, vol. 153(P2).
    16. Mbakob Yonkeu, R. & David, Afungchui, 2022. "Coherence and stochastic resonance in the fractional-birhythmic self-sustained system subjected to fractional time-delay feedback and Lévy noise," Chaos, Solitons & Fractals, Elsevier, vol. 165(P1).
    17. Guo, Yongfeng & Wang, Linjie & Wei, Fang & Tan, Jianguo, 2019. "Dynamical behavior of simplified FitzHugh-Nagumo neural system driven by Lévy noise and Gaussian white noise," Chaos, Solitons & Fractals, Elsevier, vol. 127(C), pages 118-126.
    18. Kotchoni, Rachidi, 2012. "Applications of the characteristic function-based continuum GMM in finance," Computational Statistics & Data Analysis, Elsevier, vol. 56(11), pages 3599-3622.
    19. Szymon Borak & Adam Misiorek & Rafał Weron, 2010. "Models for Heavy-tailed Asset Returns," SFB 649 Discussion Papers SFB649DP2010-049, Sonderforschungsbereich 649, Humboldt University, Berlin, Germany.
    20. Danish A. Ahmed & Sergei V. Petrovskii & Paulo F. C. Tilles, 2018. "The “Lévy or Diffusion” Controversy: How Important Is the Movement Pattern in the Context of Trapping?," Mathematics, MDPI, vol. 6(5), pages 1-27, May.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2312.15595. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.