Combinatorial Neural Bandits
Jul 24, 2023
Speakers
Taehyun Hwang
Speaker · 0 followers
Kyuwook Chai
Speaker · 0 followers
Min-hwan Oh
Speaker · 0 followers
About
We consider a contextual combinatorial bandit problem where in each round a learning agent selects a subset of arms and receives feedback on the selected arms according to their score. The score of an arm is an unknown function of the arm's feature. Approximating this unknown score function with deep neural networks, we propose algorithms: Combinatorial Neural UCB (CN-UCB) and Combinatorial Neural Thompson Sampling (CN-TS). We prove that CN-UCB achieves 𝒪̃(d̃√(T)) or 𝒪̃(√(d̃ T K)) regret, where d̃ is the effective dimension of a neural tangent kernel matrix, K is the size of a subset of arms, and T is the time horizon. For CN-TS, we adapt an optimistic sampling technique to ensure the optimism of the sampled combinatorial action, establish a worst-case (frequentist) regret of 𝒪̃(d̃√(TK)).To the best of our knowledge, these are the first combinatorial neural bandit algorithms with regret performance guarantees. In particular, CN-TS is the first Thompson sampling algorithm with the worst-case regret guarantees for the general contextual combinatorial bandit problem. The numerical experiments demonstrate the superior performances of our proposed algorithms.We consider a contextual combinatorial bandit problem where in each round a learning agent selects a subset of arms and receives feedback on the selected arms according to their score. The score of an arm is an unknown function of the arm's feature. Approximating this unknown score function with deep neural networks, we propose algorithms: Combinatorial Neural UCB (CN-UCB) and Combinatorial Neural Thompson Sampling (CN-TS). We prove that CN-UCB achieves 𝒪̃(d̃√(T)) or 𝒪̃(√(d̃ T K)) regret, wher…
Like the format? Trust SlidesLive to capture your next event!
Professional recording and live streaming, delivered globally.
Sharing
Recommended Videos
Presentations on similar topic, category or speaker
On Coresets for Clustering in Small Dimensional Euclidean Spaces
Watch later
DualHSIC: HSIC-Bottleneck and Alignment for Continual Learning
Watch later
Zifeng Wang, …
Provable Data Subset Selection For Efficient Neural Networks Training
Watch later
Murad Tukan, …
Efficient RL via Disentangled Environment and Agent Representations
Watch later
Kevin Gmelin, …
Likelihood Adjusted Semidefinite Programs for Clustering Heterogeneous Data
Watch later
Yubo Zhuang, …
Adversarial Attacks on Aligned LLMs
Watch later
Zico Kolter, …