Forgetting-Factor Regret for Online Zero-Sum Games

This paper studies dynamic equilibrium tracking in online two-player zero-sum games with time-varying convex-concave payoff functions.

Existing regret metrics for online saddle-point problems usually aggregate historical payoffs with uniform weights, and hence may fail to characterize the real-time tracking performance with respect to the current Nash equilibrium (NE).

To address this issue, we introduce a zero-sum game regret function with a forgetting factor, which assigns exponentially decaying weights to past saddle gaps and emphasizes recent performance.

This metric directly links regret minimization to the tracking of time-varying NEs.

Within this framework, we investigate three online algorithms under different computational and information settings.

For first-order feedback, we analyze projected gradient descent-ascent and design a projection-free online Frank-Wolfe method to reduce the computational cost of projections.

For zeroth-order feedback, we develop a deterministic finite-difference method that only uses function-value queries.

For all three algorithms, we establish forgetting-factor regret bounds that explicitly characterize the effects of NE variation, payoff variation, and gradient-estimation error.

We further provide sufficient conditions under which the proposed regret converges to zero, thereby certifying asymptotic tracking of time-varying NEs.

The numerical example validates the theoretical results and illustrates the tracking advantage of the proposed regret metric.