Achieving Near-Optimal Regret for Bandit Algorithms with Uniform Last-Iterate Guarantee

arXiv:2402.12711v1 Announce Type: new
Abstract: Existing performance measures for bandit algorithms such as regret, PAC bounds, or uniform-PAC (Dann et al., 2017), typically evaluate the cumulative performance, while allowing the play of an arbitrarily bad arm at any finite time t. Such a behavior can be highly detrimental in high-stakes applications. This paper introduces a stronger performance measure, the uniform last-iterate (ULI) guarantee, capturing both cumulative and instantaneous performance of bandit algorithms. Specifically, ULI characterizes the instantaneous performance since it …

abstract algorithms arm arxiv behavior cs.lg iterate near performance stat.ml type uniform