A Note on Bounding Regret of the C²UCB Contextual Combinatorial Bandit

2019/02/20 by Bastian Oetomo, Oetomo, Bastian, Malinga Perera +5
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #Advanced Wireless Network Optimization #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.1902.07500

openalex publication_date 2019/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We revisit the proof by Qin et al. (2014) of bounded regret of the C²UCB contextual combinatorial bandit. We demonstrate an error in the proof of volumetric expansion of the moment matrix, used in upper bounding a function of context vector norms. We prove a relaxed inequality that yields the originally-stated regret bound.

Related

• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions
• Second Order Bounds for Contextual Bandits with Function Approximation
• Thompson Sampling Regret Bounds for Contextual Bandits with sub-Gaussian rewards
• Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes
• Tight Regret Bounds for Infinite-armed Linear Contextual Bandits