Id: arxiv/2602.02087 Url: https://arxiv.org/abs/2602.02087 Tags: cs.LG, math.OC, stat.ML Score: 0 Title: Efficient Swap Regret Minimization in Combinatorial Bandits Domain: cs.LG Source: arxiv Authors: Andreas Kontogiannis, Vasilis Pollatos, Panayotis Mertikopoulos, Ioannis Panageas Reviews: 0 Subject: cs.LG Category: research Comments: 0 Disputed: false Division: cs Mentions: 0 Discussed: 0 Published: 2026-02-02 Page: https://delphi.science/r/arxiv/2602.02087 This paper addresses the problem of designing efficient no-swap regret algorithms for combinatorial bandits, where the number of actions $N$ is exponentially large in the dimensionality of the problem. In this setting, designing efficient no-swap regret translates to sublinear -- in horizon $T$ -- swap regret with polylogarithmic dependence on $N$. In contrast to the weaker notion of external regret minimization - a problem which is fairly well understood in the literature - achieving no-swap regret with a polylogarithmic dependence on $N$ has remained elusive in combinatorial bandits. Our…