Skip to content
Preprint

Noise Shapes the Surplus: Strategic Play Against No-Regret Learners

Oct 2026 · 0 citations
Computer Science

Abstract

Recent work has shown that, in zero-sum games, an optimizer can extract $\Omega(\sqrt{T})$ strategic surplus---cumulative payoff above the minimax benchmark---against noiseless no-regret learners with a constant step size. However, in practice, learners often act on perturbed payoff scores and use decaying learning rates $\eta_t$. Since existing extraction mechanisms rely on exact scores, a natural question is whether noise shields the learner from exploitation and eliminates surplus altogether. We address this question for the widely used class of Follow-the-Regularized-Leader (FTRL) algorithms. Under standard regularity conditions, we establish three results, none of which assumes independence of the noise. First, under summability conditions, passive play of a strategy fixed independently of the horizon earns at most constant surplus. Second, we design a new mechanism that exploits the learner's noise-dependent response: a clairvoyant optimizer who knows the update rule and the limiting mean response secures $\Omega(1/\eta_T)$ surplus whenever that mean is profitable. Third, even when that mean is not profitable, active alternating play extracts $\Omega(\sum_{t<T}\eta_t)$ surplus by exploiting the learner's movement rather than its location, under suitable responsiveness and stability conditions. Finally, at the canonical learning rate $\eta_t\propto t^{-1/2}$, we recover the noiseless $\Omega(\sqrt{T})$ rate for mean-zero, finite-variance perturbations---whether fresh with arbitrary temporal dependence or accumulated from i.i.d. increments---provided the limiting mean response is profitable.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.