Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time

Thibaut Cuvelier; Richard Combes; Eric Gourdin

Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time

Thibaut Cuvelier
, Richard Combes
, Eric Gourdin

L2S, CNRS, Univ Paris-Sud
Orange Labs

Résultats de recherche: Contribution à un journal › Article de conférence › Revue par des pairs

Résumé

We consider combinatorial semi-bandits with uncorrelated Gaussian rewards. In this article, we propose the first method, to the best of our knowledge, that enables to compute the solution of the Graves-Lai optimization problem in polynomial time for many combinatorial structures of interest. In turn, this immediately yields the first known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.

langue originale	Anglais
Pages (de - à)	505-528
Nombre de pages	24
journal	Proceedings of Machine Learning Research
Volume	132
état	Publié - 1 janv. 2021
Modification externe	Oui
Evénement	32nd International Conference on Algorithmic Learning Theory, ALT 2021 - Virtual, Online Durée: 16 mars 2021 → 19 mars 2021

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

@article{fd3aff78977349398e7f0242839ff21e,

title = "Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time",

abstract = "We consider combinatorial semi-bandits with uncorrelated Gaussian rewards. In this article, we propose the first method, to the best of our knowledge, that enables to compute the solution of the Graves-Lai optimization problem in polynomial time for many combinatorial structures of interest. In turn, this immediately yields the first known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.",

author = "Thibaut Cuvelier and Richard Combes and Eric Gourdin",

note = "Publisher Copyright: {\textcopyright} 2021 T. Cuvelier, R. Combes \& E. Gourdin.; 32nd International Conference on Algorithmic Learning Theory, ALT 2021 ; Conference date: 16-03-2021 Through 19-03-2021",

year = "2021",

month = jan,

day = "1",

language = "English",

volume = "132",

pages = "505--528",

journal = "Proceedings of Machine Learning Research",

issn = "2640-3498",

}

TY - JOUR

T1 - Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time

AU - Cuvelier, Thibaut

AU - Combes, Richard

AU - Gourdin, Eric

PY - 2021/1/1

Y1 - 2021/1/1

N2 - We consider combinatorial semi-bandits with uncorrelated Gaussian rewards. In this article, we propose the first method, to the best of our knowledge, that enables to compute the solution of the Graves-Lai optimization problem in polynomial time for many combinatorial structures of interest. In turn, this immediately yields the first known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.

AB - We consider combinatorial semi-bandits with uncorrelated Gaussian rewards. In this article, we propose the first method, to the best of our knowledge, that enables to compute the solution of the Graves-Lai optimization problem in polynomial time for many combinatorial structures of interest. In turn, this immediately yields the first known approach to implement asymptotically optimal algorithms in polynomial time for combinatorial semi-bandits.

UR - https://www.scopus.com/pages/publications/85132048614

M3 - Conference article

AN - SCOPUS:85132048614

SN - 2640-3498

VL - 132

SP - 505

EP - 528

JO - Proceedings of Machine Learning Research

JF - Proceedings of Machine Learning Research

T2 - 32nd International Conference on Algorithmic Learning Theory, ALT 2021

Y2 - 16 March 2021 through 19 March 2021

ER -

Asymptotically Optimal Strategies For Combinatorial Semi-Bandits in Polynomial Time

Résumé

Autres fichiers et liens

Empreinte digitale

Contient cette citation