Robust sequential design for piecewise-stationary multi-armed bandit problem in the presence of outliers

Yaping Wang, Zhicheng Peng, Riquan Zhang and Qian Xiao

Statistical Theory and Related Fields, 2021, vol. 5, issue 2, 122-133

Abstract: The multi-armed bandit (MAB) problem studies the sequential decision making in the presence of uncertainty and partial feedback on rewards. Its name comes from imagining a gambler at a row of slot machines who needs to decide the best strategy on the number of times as well as the orders to play each machine. It is a classic reinforcement learning problem which is fundamental to many online learning problems. In many practical applications of the MAB, the reward distributions may change at unknown time steps and the outliers (extreme rewards) often exist. Current sequential design strategies may struggle in such cases, as they tend to infer additional change points to fit the outliers. In this paper, we propose a robust change-detection upper confidence bound (RCD-UCB) algorithm which can distinguish the real change points from the outliers in piecewise-stationary MAB settings. We show that the proposed RCD-UCB algorithm can achieve a nearly optimal regret bound on the order of $ O(\sqrt {SKT\log T}) $ O(SKTlog⁡T), where T is the number of time steps, K is the number of arms and S is the number of stationary segments. We demonstrate its superior performance compared to some state-of-the-art algorithms in both simulation experiments and real data analysis. (See https://github.com/woaishufenke/MAB_STRF.git for the codes used in this paper.)

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/24754269.2021.1902687 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tstfxx:v:5:y:2021:i:2:p:122-133

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tstf20

DOI: 10.1080/24754269.2021.1902687

Access Statistics for this article

Statistical Theory and Related Fields is currently edited by Zhao Wei

More articles in Statistical Theory and Related Fields from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().