Nash Regret Guarantees for Linear Bandits

Ayush Sawarni, Soumybrata Pal, Siddharth Barman

We obtain essentially tight upper bounds for a strengthened notion of regret in the stochastic linear bandits framework. The strengthening -- referred to as Nash regret -- is defin…