{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-02","reactions":{}}