Uniform Last-Iterate Guarantee for Bandits and Reinforcement Learning
This work addresses the need for reliable performance in high-stakes applications by providing a stronger metric that ensures policies do not become arbitrarily bad at any finite time, though it is incremental as it builds on existing bandit and RL frameworks.
The paper tackles the problem of ensuring both cumulative and instantaneous performance in reinforcement learning by introducing a new metric called uniform last-iterate (ULI) guarantee, which bounds per-round suboptimality and prevents revisiting bad policies, and demonstrates that near-optimal ULI implies near-optimal cumulative performance but not vice versa, with positive results for finite-armed bandits, a negative result for optimistic algorithms, and efficient algorithms for linear bandits and online RL achieving ULI guarantees.
Existing metrics for reinforcement learning (RL) such as regret, PAC bounds, or uniform-PAC (Dann et al., 2017), typically evaluate the cumulative performance, while allowing the agent to play an arbitrarily bad policy at any finite time t. Such a behavior can be highly detrimental in high-stakes applications. This paper introduces a stronger metric, uniform last-iterate (ULI) guarantee, capturing both cumulative and instantaneous performance of RL algorithms. Specifically, ULI characterizes the instantaneous performance by ensuring that the per-round suboptimality of the played policy is bounded by a function, monotonically decreasing w.r.t. round t, preventing revisiting bad policies when sufficient samples are available. We demonstrate that a near-optimal ULI guarantee directly implies near-optimal cumulative performance across aforementioned metrics, but not the other way around. To examine the achievability of ULI, we first provide two positive results for bandit problems with finite arms, showing that elimination-based algorithms and high-probability adversarial algorithms with stronger analysis or additional designs, can attain near-optimal ULI guarantees. We also provide a negative result, indicating that optimistic algorithms cannot achieve near-optimal ULI guarantee. Furthermore, we propose an efficient algorithm for linear bandits with infinitely many arms, which achieves the ULI guarantee, given access to an optimization oracle. Finally, we propose an algorithm that achieves near-optimal ULI guarantee for the online reinforcement learning setting.