High-Probability Last-Iterate Convergence for Adaptively Regularized Mirror Descent in Games with Bandit Feedback

Regularization is a powerful technique for establishing last-iterate convergence, typically by augmenting the payoff functions with auxiliary terms that induce strong monotonicity of the game operator to stabilize learning dynamic. Existing approaches commonly rely on a gradually vanishing regularization coefficient so that the resulting last-iterate strategies can approach an NE of the original unregularized game. In this work, we study two-player zero-sum games under bandit feedback, where each player observes only the payoff associated with its sampled action, and introduce a fixed-coefficient regularization framework that perturbs the payoff based on the distance to an anchoring strategy. Specifically, we propose an adaptively regularized mirror descent algorithm equipped with a log-barrier regularizer, which periodically updates the anchoring strategy while keeping the regularization coefficient fixed. Through a dual-norm analysis, we prove that the resulting uncoupled algorithm achieves an anytime high-probability last-iterate convergence rate of $\tilde{\mathcal{O}}(t^{-1/4})$ in both matrix games and extensive-form games (EFGs). We further establish a constant-probability lower bound of $\Omega (T^{-1/2})$ over a fixed horizon under the same strictly uncoupled bandit information model, revealing the remaining gap between our upper bound and the best possible convergence rate suggested by the lower bound. Experiments on four EFG benchmarks demonstrate the competitive performance of our method against existing baselines.