## Abstract

We study high-probability regret bounds for adversarial K-armed bandits with time-varying feedback graphs over T rounds. For general strongly observable graphs, we develop an algorithm that achieves the optimal regret O^{e}((^{PT}_{t=1} α_{t})^{1/2} + max_{t}∈[T_{]} α_{t}) with high probability, where α_{t} is the independence number of the feedback graph at round t. Compared to the best existing result (Neu, 2015) which only considers graphs with self-loops for all nodes, our result not only holds more generally, but importantly also removes any poly(K) dependence that can be prohibitively large for applications such as contextual bandits. Furthermore, we also develop the first algorithm that achieves the optimal high-probability regret bound for weakly observable graphs, which even improves the best expected regret bound of (Alon et al., 2015b) by removing the O(^{√}KT) term with a refined analysis. Our algorithms are based on the online mirror descent framework, but importantly with an innovative combination of several techniques. Notably, while earlier works use optimistic biased loss estimators for achieving high-probability bounds, we find it important to use a pessimistic one for nodes without self-loop in a strongly observable graph.

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

Pages (from-to) | 1074-1100 |

Number of pages | 27 |

Journal | Proceedings of Machine Learning Research |

Volume | 201 |

State | Published - 2023 |

Event | 34th International Conference onAlgorithmic Learning Theory, ALT 2023 - Singapore, Singapore Duration: Feb 20 2023 → Feb 23 2023 |

## Keywords

- bandits with feedback graph
- high-probability regret bounds
- multi-armed bandits

## ASJC Scopus subject areas

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