Improved Regret Bounds for Bandits with Expert Advice
<|reference_start|>Improved Regret Bounds for Bandits with Expert Advice: In this research note, we revisit the bandits with expert advice problem. Under a restricted feedback model, we prove a lower bound of order $\sqrt{K T \ln(N/K)}$ for the worst-case regret, where $K$ is the number of actions, $N>K$ the number of experts, and $T$ the time horizon. This matches a previously known upper bound of the same order and improves upon the best available lower bound of $\sqrt{K T (\ln N) / (\ln K)}$. For the standard feedback model, we prove a new instance-based upper bound that depends on the agreement between the experts and provides a logarithmic improvement compared to prior results.<|reference_end|>
@article{cesa-bianchi2024improved,
    title={Improved Regret Bounds for Bandits with Expert Advice},
    author={Nicol`o Cesa-Bianchi, Khaled Eldowa, Emmanuel Esposito, Julia
  Olkhovskaya},
    journal={arXiv preprint arXiv:2406.16802},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.16802},
    primaryClass={cs.LG stat.ML}
}