%0 Journal Article %1 esfandiari2019regret %A Esfandiari, Hossein %A Karbasi, Amin %A Mehrabian, Abbas %A Mirrokni, Vahab %D 2019 %K bandits bounds readings %T Regret Bounds for Batched Bandits %U http://arxiv.org/abs/1910.04959 %X We present simple and efficient algorithms for the batched stochastic multi-armed bandit and batched stochastic linear bandit problems. We prove bounds for their expected regrets that improve over the best-known regret bounds for any number of batches. In particular, our algorithms in both settings achieve the optimal expected regrets by using only a logarithmic number of batches. We also study the batched adversarial multi-armed bandit problem for the first time and find the optimal regret, up to logarithmic factors, of any algorithm with predetermined batch sizes.

@article{esfandiari2019regret, abstract = {We present simple and efficient algorithms for the batched stochastic multi-armed bandit and batched stochastic linear bandit problems. We prove bounds for their expected regrets that improve over the best-known regret bounds for any number of batches. In particular, our algorithms in both settings achieve the optimal expected regrets by using only a logarithmic number of batches. We also study the batched adversarial multi-armed bandit problem for the first time and find the optimal regret, up to logarithmic factors, of any algorithm with predetermined batch sizes.}, added-at = {2020-02-27T15:38:47.000+0100}, author = {Esfandiari, Hossein and Karbasi, Amin and Mehrabian, Abbas and Mirrokni, Vahab}, biburl = {https://www.bibsonomy.org/bibtex/2fc63a76486548e8c1f48a4ef3817f358/kirk86}, description = {[1910.04959] Regret Bounds for Batched Bandits}, interhash = {4db682518e1e89260bc5bf0865cb8ff9}, intrahash = {fc63a76486548e8c1f48a4ef3817f358}, keywords = {bandits bounds readings}, note = {cite arxiv:1910.04959}, timestamp = {2020-02-27T15:38:47.000+0100}, title = {Regret Bounds for Batched Bandits}, url = {http://arxiv.org/abs/1910.04959}, year = 2019 }