Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Unimodal bandits: Regret lower bounds and optimal algorithms
KTH, School of Electrical Engineering (EES), Automatic Control.
KTH, School of Electrical Engineering (EES), Automatic Control.
2014 (English)In: 31st International Conference on Machine Learning, ICML 2014, 2014, 799-807 p.Conference paper, Published paper (Refereed)
Abstract [en]

2014 We consider stochastic multi-armed bandits where the expected reward is a unimodal function over partially ordered arms. This important class of problems has been recently investigated in (Cope, 2009; Yu&Mannor, 2011). The set of arms is either discrete, in which case arms correspond to the vertices of a finite graph whose structure represents similarity in rewards, or continuous, in which case arms belong to a bounded interval. For discrete unimodal bandits, we derive asymptotic lower bounds for the regret achieved under any algorithm, and propose OSUB, an algorithm whose regret matches this lower bound. Our algorithm optimally exploits the unimodal structure of the problem, and surprisingly, its asymptotic regret does not depend on the number of arms. We also provide a regret upper bound for OSUB in non-stationary environments where the expected rewards smoothly evolve over time. The analytical results are supported by numerical experiments showing that OSUB performs significantly better than the state-of-the-art algorithms. For continuous sets of arms, we provide a brief discussion. We show that combining an appropriate discretization of the set of arms with the UCB algorithm yields an order-optimal regret, and in practice, outperforms recently proposed algorithms designed to exploit the unimodal structure.

Place, publisher, year, edition, pages
2014. 799-807 p.
Keyword [en]
Artificial intelligence, Learning systems, Stochastic systems, Analytical results, Discretizations, Multi armed bandit, Non-stationary environment, Numerical experiments, Optimal algorithm, State-of-the-art algorithms, Unimodal functions, Algorithms
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
URN: urn:nbn:se:kth:diva-168369Scopus ID: 2-s2.0-84919789435ISBN: 9781634393973 (print)OAI: oai:DiVA.org:kth-168369DiVA: diva2:815975
Conference
31st International Conference on Machine Learning, ICML 2014, 21 June 2014 through 26 June 2014
Note

QC 20150602

Available from: 2015-06-02 Created: 2015-06-02 Last updated: 2015-06-02Bibliographically approved

Open Access in DiVA

No full text

Scopus

Search in DiVA

By author/editor
Combes, RichardProutiere, Alexandre
By organisation
Automatic Control
Electrical Engineering, Electronic Engineering, Information Engineering

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 20 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf