Bernoulli multi-armed bandit problem under delayed feedback
DOI:
https://doi.org/10.17721/1812-5409.2021/1.2Keywords:
multi-armed bandit problem, stochastic environment with delays, numerical experimentsAbstract
Online learning under delayed feedback has been recently gaining increasing attention. Learning with delays is more natural in most practical applications since the feedback from the environment is not immediate. For example, the response to a drug in clinical trials could take a while. In this paper, we study the multi-armed bandit problem with Bernoulli distribution in the environment with delays by evaluating the Explore-First algorithm. We obtain the upper bounds of the algorithm, the theoretical results are applied to develop the software framework for conducting numerical experiments.
Pages of the article in the issue: 20 - 26
Language of the article: English
References
THOMPSON, W. R. (1933) On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika. 25 (3/4). p. 285-294.
JOULANI, P., GYORGY, A., & SZEPESVARI, C. (2013) Online learning under delayed feedback. In International Conference on Machine Learning. p. 1453- 1461. PMLR.
ROBBINS, H. (1952) Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society. 58 (5). p. 527-535.
LAI, T. L., & ROBBINS, H. (1985) Asymptotically efficient adaptive allocation rules. Advances in applied mathematics. 6 (1). p. 4-22.
ANSCOMBE, F. J. (1963) Sequential medical trials. Journal of the American Statistical Association. 58 (302). p. 365–383.
SLIVKINS, A. (2019) Introduction to multi-armed bandits. Foundations and Trends in Machine Learning. 12 (1–2). p. 1–286.
BUBECK, S., & CESA-BIANCHI, N. (2012) Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning. 5 (1). p. 1–122.
BULDYGIN, V. V., KOZACHENKO, YU. V. (2000) Metric Characterization of Random Variables and Random Processes. AMS, Providence, RI, 257 p.
KOZACHENKO, YU. V., POGORILYAK, O. O., ROZORA, I. V., & TEGZA, A. M. (2016) Simulation of stochastic processes with given accuracy and reliability. Elsevier.
HOEFFDING, W. (1963) Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association. 58 (301). p. 13–30.
LATTIMORE, T., & SZEPESVARI, C. (2020) Bandit algorithms. Cambridge University Press, 537 p.
SANDERCOCK, P., NIEWADA, M., & CZLONKOWSKA, A. (2011) International stroke trial collaborative Group. The international stroke trial database. Trials. 12 (1). p. 101.
DZHOHA, A. (2021) Multi-armed bandit problem under delayed feedback: numerical experiments. [Online] Available from: https://github.com/djo/delayed-bandit
Downloads
Published
Issue
Section
License
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
