On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problems
On Abruptly-Changing and Slowly-Varying Multiarmed Bandit Problems
复制标题
DOI：
10.23919/acc.2018.8431265
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Lai Wei;Vaibhav Srivastava
中科院分区：
文献类型：
--
作者：
Lai Wei;Vaibhav Srivastava
研究了非平稳随机多臂强盗（MAB）问题，提出了两种遗传算法，即有限记忆确定性探索和利用排序（LM-DSEE）和滑动窗口置信上界（SW-UCB#）.我们严格分析这些算法在不断变化和缓慢变化的环境中，并表征其性能。我们表明，这些算法在任何一种环境中的预期累积遗憾的时间，即次线性函数的上限，后悔的时间平均值渐近收敛于零。我们用数字说明来补充我们的分析。
We study the non-stationary stochastic multi-armed bandit (MAB) problem and propose two generic algorithms, namely, Limited Memory Deterministic Sequencing of Exploration and Exploitation (LM-DSEE) and Sliding-Window Upper Confidence Bound# (SW-UCB#). We rigorously analyze these algorithms in abruptly-changing and slowly-varying environments and characterize their performance. We show that the expected cumulative regret for these algorithms in either of the environments is upper bounded by sublinear functions of time, i.e., the time average of the regret asymptotically converges to zero. We complement our analysis with numerical illustrations.