Improved Algorithms for Adversarial Bandits with Unbounded Losses
This work addresses a fundamental challenge in online learning for scenarios with unpredictable, unbounded losses, offering improved algorithms with theoretical guarantees and practical performance gains.
The paper tackles the adversarial multi-armed bandits problem with unbounded losses, where algorithms lack prior knowledge on loss sizes, by introducing UMAB-NN and UMAB-G algorithms for non-negative and general unbounded losses, achieving the first adaptive and scale-free regret bound without uniform exploration and outperforming existing methods in empirical evaluations.
We consider the Adversarial Multi-Armed Bandits (MAB) problem with unbounded losses, where the algorithms have no prior knowledge on the sizes of the losses. We present UMAB-NN and UMAB-G, two algorithms for non-negative and general unbounded loss respectively. For non-negative unbounded loss, UMAB-NN achieves the first adaptive and scale free regret bound without uniform exploration. Built up on that, we further develop UMAB-G that can learn from arbitrary unbounded loss. Our analysis reveals the asymmetry between positive and negative losses in the MAB problem and provide additional insights. We also accompany our theoretical findings with extensive empirical evaluations, showing that our algorithms consistently out-performs all existing algorithms that handles unbounded losses.