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

Research output: Contribution to journal › Conference article › peer-review

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.

Original language	English
Pages (from-to)	505-528
Number of pages	24
Journal	Proceedings of Machine Learning Research
Volume	132
Publication status	Published - 1 Jan 2021
Externally published	Yes
Event	32nd International Conference on Algorithmic Learning Theory, ALT 2021 - Virtual, Online Duration: 16 Mar 2021 → 19 Mar 2021

Cite this

@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.

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

Abstract

Fingerprint

Cite this