| Paper ID | MLSP-22.4 |
| Paper Title |
NEAR-OPTIMAL ALGORITHMS FOR PIECEWISE-STATIONARY CASCADING BANDITS |
| Authors |
Lingda Wang, Huozhi Zhou, University of Illinois at Urbana-Champaign, United States; Bingcong Li, University of Minnesota - Twin Cities, United States; Lav R. Varshney, Zhizhen Zhao, University of Illinois at Urbana-Champaign, United States |
| Session | MLSP-22: Sequential Learning |
| Location | Gather.Town |
| Session Time: | Wednesday, 09 June, 15:30 - 16:15 |
| Presentation Time: | Wednesday, 09 June, 15:30 - 16:15 |
| Presentation |
Poster
|
| Topic |
Machine Learning for Signal Processing: [MLR-SLER] Sequential learning; sequential decision methods |
| IEEE Xplore Open Preview |
Click here to view in IEEE Xplore |
| Virtual Presentation |
Click here to watch in the Virtual Conference |
| Abstract |
Cascading bandit (CB) is a popular model for web search and online advertising. However, the stationary CB model may be too simple to cope with real-world problems, where user preferences may change over time. Considering piecewise-stationary environments, two efficient algorithms, \texttt{GLRT-Ca}-\texttt{scadeUCB} and \texttt{GLRT-CascadeKL-UCB}, are developed. Comparing with existing works, the proposed algorithms: i) are free of change-point-dependent information for choosing parameters; ii) have fewer tuning parameters; iii) improve regret upper bounds. We also show that the proposed algorithms are optimal up to logarithm terms by deriving a minimax lower bound $\Omega(\sqrt{NLT})$ for piecewise-stationary CB. The efficiency of the proposed algorithms is validated through numerical tests on a real-world benchmark dataset. |
