Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox
<|reference_start|>Thompson Sampling For Combinatorial Bandits: Polynomial Regret and Mismatched Sampling Paradox: We consider Thompson Sampling (TS) for linear combinatorial semi-bandits and subgaussian rewards. We propose the first known TS whose finite-time regret does not scale exponentially with the dimension of the problem. We further show the "mismatched sampling paradox": A learner who knows the rewards distributions and samples from the correct posterior distribution can perform exponentially worse than a learner who does not know the rewards and simply samples from a well-chosen Gaussian posterior. The code used to generate the experiments is available at https://github.com/RaymZhang/CTS-Mismatched-Paradox<|reference_end|>
@article{zhang2024thompson,
    title={Thompson Sampling For Combinatorial Bandits: Polynomial Regret and
  Mismatched Sampling Paradox},
    author={Raymond Zhang and Richard Combes},
    journal={arXiv preprint arXiv:2410.05441},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.05441},
    primaryClass={stat.ML cs.LG}
}