## Abstract

Both asymptotic and non-asymptotic instance-dependent regret bounds are known for the stochastic multi-armed bandit problem. Such regret bounds are known to be tight up to lower order terms in the setting of Gaussian rewards (Garivier et al., 2019). We revisit the related problem of stochastic online learning with feedback graphs, where asymptotically optimal instance dependent algorithms are known. Surprisingly, the notion of optimal finite-time regret is not a uniquely defined property in this context and in general, it is decoupled from the asymptotic rate. We pose two open problems. First we ask for a characterization of the finite-time instance-dependent optimal regret. Next, we ask for a characterization of the set of graphs for which the finite time regret is bounded by the asymptotically optimal rate, for reasonable values of the time horizon.

Original language | English (US) |
---|---|

Pages (from-to) | 5644-5649 |

Number of pages | 6 |

Journal | Proceedings of Machine Learning Research |

Volume | 178 |

State | Published - 2022 |

Event | 35th Conference on Learning Theory, COLT 2022 - London, United Kingdom Duration: Jul 2 2022 → Jul 5 2022 |

## ASJC Scopus subject areas

- Artificial Intelligence
- Software
- Control and Systems Engineering
- Statistics and Probability