Fighting Contextual Bandits with Stochastic Smoothing

Young Hun Jung, Ambuj Tewari

Abstract

We introduce a new stochastic smoothing perspective to study adversarial contextual bandit problems. We propose a general algorithm template that represents random perturbation based algorithms and identify several perturbation distributions that lead to strong regret bounds. Using the idea of smoothness, we provide an $O(\sqrt{T})$ zero-order bound for the vanilla algorithm and an $O(L^{*2/3}_{T})$ first-order bound for the clipped version. These bounds hold when the algorithms use with a variety of distributions that have a bounded hazard rate. Our algorithm template includes EXP4 as a special case corresponding to the Gumbel perturbation. Our regret bounds match existing results for EXP4 without relying on the specific properties of the algorithm.
BibTeX
@misc{jung2018fighting,
  author = {Young Hun Jung and Ambuj Tewari},
  title = {{Fighting Contextual Bandits with Stochastic Smoothing}},
  year = {2018},
  eprint = {1810.05188},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1810.05188},
}

Loading related content...

Figure