Efficient Uncoupled Learning Dynamics with $\tilde{O}\!\left(T^{-1/4}\right)$ Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback

AI summary

Overview

Research area: Online learning in games / game theory and optimization — specifically last-iterate convergence of uncoupled learning dynamics in two-player zero-sum bilinear saddle-point problems under bandit feedback.

Technical level: Advanced. The paper is a theory contribution built on Follow-The-Regularized-Leader (FTRL) and Optimistic FTRL (OFTRL), the RVU (Regret bounded by Variation in Utilities) property, self-concordant-style norm pairs from convex geometry, and experimental design for linear bandits. It assumes comfort with convex analysis, dual norms, Bregman divergences and subgaussian concentration.

Scope: The paper designs and analyzes an uncoupled, computationally efficient learning algorithm whose iterates converge in the last-iterate sense to a Nash equilibrium with high probability at rate Õ(T^{-1/4}) in bilinear saddle-point problems over compact convex action sets under standard bandit feedback.

What This Paper Is About

In a two-player zero-sum game, each player picks an action from a compact convex set and only observes the payoff of the action it actually played — a "bandit feedback" model, rather than the richer gradient feedback where the whole payoff vector is revealed. Average-iterate convergence (the running average of strategies approaches equilibrium) is well understood, but average-iterate guarantees do not describe what a learner actually does day to day, and many standard algorithms provably fail to converge in the last-iterate sense. The paper asks whether there exists an uncoupled learning algorithm whose actual per-round iterates converge to a Nash equilibrium with high probability under standard bandit feedback over convex sets, and answers yes, with rate Õ(T^{-1/4}).

Key Contributions

1. First high-probability last-iterate guarantee under standard bandit feedback over convex sets. The paper constructs uncoupled learning dynamics such that the pair (x_k, y_k) is an ε_k-approximate Nash equilibrium with probability at least 1 − δ, where ε_k = poly(n, m, log(k/δ)) · k^{-1/4}. The authors state this is the first such result for bilinear saddle-point problems over compact convex action sets.

2. Improved rate over the prior convex-set result. The rate k^{-1/4} improves on the k^{-1/6} rate of Dong et al. (2024), which only established last-iterate convergence in expectation rather than high probability.

3. A new reward estimation scheme for standard bandit feedback. Because players observe only ⟨x_{t,s}, A y_{t,s}⟩, estimating the utility vector θ̄_t^x = A ŷ_t requires a pairing/transformation trick: matched round pairs are used so that a transformed reward is an unbiased estimate of the linear model, with the transformed noise shown to be zero-mean 8-subgaussian. The sampling procedure blends the running average x̄_t with an exploration distribution drawn from experimental design for linear bandits.

4. Geometry-tailored regularizers and norm pairs. The paper defines a primal-dual norm pair tied to the action set via its symmetrization K := conv(X ∪ (−X)), approximates K by an ellipsoid E = {x : x^T H x ≤ 1} with E ⊆ K ⊆ αE where α := sqrt(d(d+1)), and uses φ(x) = ½ x^T H x as the regularizer. This regularizer is shown to be 1-strongly convex with respect to the primal norm and to have Bregman divergence bounded by 2d(d+1). The algorithm remains computationally efficient, requiring only a linear optimization oracle over each player's action set.

Main Findings

• Main theorem (Theorem 2.5): With X ⊆ R^n and Y ⊆ R^m convex and compact, and both players running Algorithm 1 with step size η = 1/6, then with probability at least 1 − δ, for every k ≥ 1 the iterate (x_k, y_k) is an ε_k-approximate Nash equilibrium with ε_k = poly(n, m, log(k/δ)) · k^{-1/4}.

• Uncoupled, high probability, last-iterate: The guarantee is on the actual iterates (x_k, y_k), not on their expectation, and holds with probability at least 1 − δ. The authors contrast this with convergence-in-expectation results, which do not ensure convergence along a single trajectory.

• Estimator concentration (Lemma 2.1): The constructed estimator θ̂_t^x satisfies Pr(sup_{x ∈ X} |⟨x, θ̂_t^x − θ̄_t^x⟩| ≤ 48 sqrt(n³/t³)) ≥ 1 − δ/(4t²). This requires an exploration distribution uniform over a subset S = {x_1, …, x_n} ⊂ X satisfying sup_{x ∈ X} x^T V^{-1} x ≤ 2n² with V := (1/n) Σ_{i=1}^n x_i x_i^T ≻ 0.

• Regularizer properties: φ(x) = ½ x^T H x is 1-strongly convex with respect to the primal norm ‖·‖_X (Lemma 2.3), and its Bregman divergence satisfies D_φ(x, y) ≤ 2d(d+1) for any x, y ∈ X (Proposition 2.4).

• Primal-dual norm pair (Lemma 2.2, attributed to Chandrasekaran et al. (2012)): With ‖z‖{*,X} := max{x ∈ X} |⟨x, z⟩| and ‖z‖X := max{‖y‖_{*,X} ≤ 1} ⟨y, z⟩, both are norms, they are dual to each other, and {y : ‖y‖_X ≤ 1} = conv(X ∪ −X).

• Algorithmic parameters (Algorithm 1): batch size B_t = log(8t²/δ) · t³, mixing parameter λ_t = t^{-2}, step size η = 1/6, initialization x_1 = E_{x ∼ D}[x]. Within each phase, with probability 1/2 the player plays x̄_t, and with probability 1/2 plays (1 − λ_t) x̄_t + λ_t z_{t,s} for z_{t,s} ∼ D_X.

• Phase utility and update: u_t^x := A ỹ_t, u_t^y := −A^T x̃_t; estimates are formed as û_t^x ← t · θ̂_t^x − (t − 1) · θ̂_{t−1}^x, and the update is an OFTRL step: x̃_{t+1} ← arg max_{x ∈ X} {⟨x, Σ_{ℓ=1}^t û_ℓ + û_t⟩ − (1/η) φ(x)}.

• Analysis chain: The duality gap of the averaged pair (x̄_T, ȳ_T) is bounded using the RVU property (Lemma 3.1, from Syrgkanis et al. (2015)), adapted to hold with estimation error in Lemma 3.2, which bounds the sum of per-round utility terms by a Bregman divergence term, 2‖T Δ_T^x‖{*,X}, 36η Σ ‖t Δ_t^x‖²{,X}, 4η Σ ‖u_t − u_{t−1}‖²_{,X}, a negative stability term −(3/16η) Σ ‖x̃_t − x̃_{t−1}‖²_X, and O(η + log T). Since iterates in phase T take the form ((1 − λ_T) x̄_T + λ_T z_x, (1 − λ_T) ȳ_T + λ_T z_y), they are O(β_T + λ_T)-approximate Nash equilibria.

• Comparison to prior bandit-feedback rates: Cai et al. (2023) obtained T^{-1/8} with high probability and T^{-1/6} in expectation; Cai et al. (2025) improved the high-probability rate to T^{-1/5}; Fiegel et al. (2025) established a lower bound of Ω(T^{-1/3}) for that setting. Those results concern probability simplices under a variant of bandit feedback, which the paper emphasizes is fundamentally different and not directly comparable. For convex sets under standard bandit feedback, Dong et al. (2024) is cited as the only established result, at T^{-1/6}, in expectation only.

• No empirical results reported: The provided paper content is a theory paper containing definitions, lemmas, propositions, theorems and proofs; it reports no experiments, datasets or benchmark evaluations.

Methodology in Plain English

The paper starts from a framework recently introduced by Cai et al. (2025) that turns an average-iterate-convergent algorithm into one with last-iterate guarantees by running it in phases. In phase t, a block of B_t rounds is played, and the algorithm plays strategies close to the running average x̄_t of earlier phase outputs; the resulting observations are used to estimate the opponent's average play, which is fed back as a utility vector into the base algorithm. Because the played strategies stay near x̄_t, convergence of the average translates into convergence of the actual iterates.

The hard part in the convex-set, standard-bandit setting is estimation. A player only sees the scalar payoff ⟨x_{t,s}, A y_{t,s}⟩ of the action it chose, so it cannot directly read off the utility vector A ŷ_t. The authors solve this by playing each phase in two kinds of rounds — one playing exactly x̄_t and one playing x̄_t perturbed by a random exploration point — pairing the rounds and dividing the reward difference by the mixing parameter λ_t. This produces an unbiased linear estimate of the utility vector with well-behaved subgaussian noise. To make the estimate reliable in all directions, the exploration points are chosen as a uniform distribution over a small set of points whose empirical covariance acts as a design matrix (this is the experimental-design ingredient from linear bandits).

The second ingredient is the regularizer. Instead of the negative entropy used for probability simplices, the authors build an ellipsoid that tightly sandwiches the symmetric hull of the action set, and use half the squared ellipsoidal norm as the regularizer. They define a norm pair — remember the action set rather than a fixed Euclidean norm — such that the estimator's error measured in the dual norm stays small, and the regularizer is strongly convex in the primal norm with small Bregman divergence. Plugging these into an optimistic FTRL update and applying the RVU inequality, with extra terms to account for estimation error, gives the final Õ(T^{-1/4}) bound. All optimization steps reduce to linear optimization over the action sets, so the method stays computationally efficient.

Why This Matters

For research, this closes a gap the authors identify: previously, no high-probability last-iterate guarantees existed for bilinear saddle-point problems over compact convex sets under standard bandit feedback, and the closest convex-set result (Dong et al., 2024) held only in expectation and at T^{-1/6}. The paper also shows how experimental design and geometry-specific regularizers can be fused with FTRL-style game dynamics, and it contextualizes its rate against the Ω(T^{-1/3}) lower bound from Fiegel et al. (2025), leaving an explicit gap between T^{-1/4} and T^{-1/3} (noting that lower bound is for a different feedback model).

Real-world applications the paper explicitly motivates:

• Algorithmic pricing, where firms choose from a continuum of prices and observe only their own realized profit.
• Resource allocation, where agents choose continuous allocations and see only their own payoff.
• Routing, where players select from a continuum of route flows with only their own realized cost.
• Multi-agent robotics, where continuous control strategies are selected and only local rewards are observed.
• Language model alignment, where the paper notes related ideas also appear (Munos et al., 2023).

Industry relevance: the algorithm is uncoupled — it does not observe the opponent's actions, does not know the opponent's action set, or even its dimension — which matches deployed settings where agents cannot share internal information. It requires only a linear optimization oracle over each player's action set, so it can be implemented in polynomial time in settings where such an oracle is available, and the high-probability guarantee removes the need to average multiple independent runs to learn an equilibrium.

Future Directions

• Closing the rate gap. The paper achieves Õ(T^{-1/4}) while a lower bound of Ω(T^{-1/3}) is cited for the related probability-simplex bandit setting (Fiegel et al., 2025); whether T^{-1/4} is tight for convex sets under standard bandit feedback is left open.

• Extending beyond bilinear games. The analysis is specific to bilinear saddle-point problems; whether the estimator-plus-geometry-regularizer approach extends to broader monotone games (where only asymptotic last-iterate convergence without finite-time rates is currently known, per Tatarenko and Kamgarpour, 2019) is an open question.

• Dependence on problem parameters. The rate carries poly(n, m, log(k/δ)) factors; tightening the polynomial dependence on dimensions n and m and on the geometry constants (such as the ellipsoid approximation factor sqrt(d(d+1))) is a natural next step.

• Alternative feedback models and computational oracles. The paper explicitly notes the variant bandit feedback type used by Cai et al. (2023, 2022) for probability simplices is fundamentally different and not directly comparable; unifying results across feedback models, and characterizing which action sets admit practical linear optimization oracles for this method, remain open directions.

Target Audience

This paper is aimed at researchers in online learning and game theory, optimization, and multi-agent reinforcement learning who work on equilibrium computation and last-iterate convergence. It will also interest theoretically minded practitioners in mechanism design, online marketplaces and control who need guaranteed convergence under bandit-style information, and readers familiar with FTRL/OFTRL, dual norms, and concentration inequalities. Beginners will find the technical sections difficult without background in convex analysis and online convex optimization.

Authors’ abstract

In this paper, we study last-iterate convergence of learning algorithms in bilinear saddle-point problems, a preferable notion of convergence that captures the day-to-day behavior of learning dynamics. We focus on the challenging setting where players select actions from compact convex sets and receive only bandit feedback. Our main contribution is the design of an uncoupled learning algorithm that guarantees last-iterate convergence to the Nash equilibrium with high probability. We establish a convergence rate of $\tilde{O}(T^{-1/4})$ up to polynomial factors in problem parameters. Crucially, our proposed algorithm is computationally efficient, requiring only an efficient linear optimization oracle over the players' compact action sets. The algorithm is obtained by combining techniques from experimental design and the classic Follow-The-Regularized-Leader (FTRL) framework, with a carefully chosen regularizer function tailored to the geometry of the action set of each learner.