图 书 馆
KL-UCB算法用于有界随机带及其以外The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond |
|
| 课程网址: | https://videolectures.net/videos/colt2011_garivier_bandits |
| 主讲教师: | Aurélien Garivier |
| 开课单位: | COLT 2011-布达佩斯 |
| 开课时间: | 2011-08-02 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | This paper presents a finite-time analysis of the KL-UCB algorithm, an online, horizon-free index policy for stochastic bandit problems. We prove two distinct results: first, for arbitrary bounded rewards, the KL-UCB algorithm satis fies a uniformly better regret bound than UCB and its variants; second, in the special case of Bernoulli rewards, it reaches the lower bound of Lai and Robbins. Furthermore, we show that simple adaptations of the KL-UCB algorithm are also optimal for specifi c classes of (possibly unbounded) rewards, including those generated from exponential families of distributions. A large-scale numerical study comparing KL-UCB with its main competitors (UCB, MOSS, UCB-Tuned, UCB-V, DMED) shows that KL-UCB is remarkably efficient and stable, including for short time horizons. KL-UCB is also the only method that always performs better than the basic UCB policy. Our regret bounds rely on deviations results of independent interest which are stated and proved in the Appendix. As a by-product, we also obtain an improved regret bound for the standard UCB algorithm. |
| 关 键 词: | KL-UCB算法; 有界随机带; 索引策略 |
| 课程来源: | 视频讲座网 |
| 数据采集: | 2024-10-22：liyq |
| 最后编审: | 2024-10-22：liyq |
| 阅读次数: | 7 |