Comference Paper

Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox

We show that the lower bound for Linear Bandit for ellipsoidal action set is Ω(min⁡(dσT+d∥θ∥A,∥θ∥AT))\Omega(\min(d \sigma \sqrt{T} + d \|\theta\|_{A}, \|\theta\|_{A} T)) and that for any algorithm hard problem for linear bandit are everywhere. We give a low complexity algorithm with mathching regret upperbound.

Jun 30, 2025

Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox

We propose the first known Thompson Sampling for combinatorial bandits whose finite-time regret does not scale exponentially with the dimension of the problem. Suprisingly, considering any subgaussian distribution as a gaussian can produce exponentialy better result.

Dec 9, 2024