Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning

Reinforcement learning (RL) algorithms are typically evaluated using metrics like regret or PAC bounds, which focus on cumulative performance and allow for arbitrarily bad policies at any point. This can be problematic for high-stakes applications where both cumulative and instantaneous performance are critical. This research introduces a new metric, the Uniform Last-Iterate (ULI) guarantee, to address this gap. ULI provides a stronger guarantee by ensuring that the algorithm’s suboptimality decreases monotonically with time, preventing revisits to poor policies.

The researchers demonstrate that achieving near-optimal ULI guarantees directly implies near-optimal cumulative performance. They then investigate the achievability of ULI for various RL settings, showing that elimination-based algorithms and specific adversarial algorithms can attain near-optimal ULI. However, they also prove that optimistic algorithms cannot achieve this level of performance, highlighting that ULI is a strictly stronger metric than existing ones. The introduction of ULI and the accompanying theoretical results enhance our understanding of RL algorithm behavior and have implications for real-world applications.