2021/10/28 by Sattar Vakili, Jonathan Scarlett, Vakili, Sattar +3 · 2 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Cognitive Radio Networks and Spectrum Sensing #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Statistics Theory (math.ST)
paper · pdf · doi:10.48550/arxiv.2110.15458
openalex publication_date 2021/10/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Confidence intervals are a crucial building block in the analysis of various online learning problems. The analysis of kernel based bandit and reinforcement learning problems utilize confidence intervals applicable to the elements of a reproducing kernel Hilbert space (RKHS). However, the existing confidence bounds do not appear to be tight, resulting in suboptimal regret bounds. In fact, the existing regret bounds for several kernelized bandit algorithms (e.g., GP-UCB, GP-TS, and their variants) may fail to even be sublinear. It is unclear whether the suboptimal regret bound is a fundamental shortcoming of these algorithms or an artifact of the proof, and the main challenge seems to stem from the online (sequential) nature of the observation points. We formalize the question of online confidence intervals in the RKHS setting and overview the existing results.