SCIENCE@home

Beating Stochastic and Adversarial Semi-bandits Optimally and Simultaneously

Julian Zimmert,Haipeng Luo,Chen-Yu Wei

Published 2019 in International Conference on Machine Learning

ABSTRACT

We develop the first general semi-bandit algorithm that simultaneously achieves $\mathcal{O}(\log T)$ regret for stochastic environments and $\mathcal{O}(\sqrt{T})$ regret for adversarial environments without knowledge of the regime or the number of rounds $T$. The leading problem-dependent constants of our bounds are not only optimal in some worst-case sense studied previously, but also optimal for two concrete instances of semi-bandit problems. Our algorithm and analysis extend the recent work of (Zimmert & Seldin, 2019) for the special case of multi-armed bandit, but importantly requires a novel hybrid regularizer designed specifically for semi-bandit. Experimental results on synthetic data show that our algorithm indeed performs well uniformly over different environments. We finally provide a preliminary extension of our results to the full bandit feedback.

PUBLICATION RECORD

  • Publication year

    2019

  • Venue

    International Conference on Machine Learning

  • Publication date

    2019-01-25

  • Fields of study

    Mathematics, Computer Science

  • Identifiers
    arXiv 1901.08779
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-36 of 36 references · Page 1 of 1

CITED BY

Showing 1-87 of 87 citing papers · Page 1 of 1