PaperlayerView exact revision on arXiv

Source-linked AI summary

Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback

Yuheng Zhang

arXiv:2609.34812v1cs.LGcs.GT

TL;DR

The paper asks whether observing opponent actions permits instance-dependent polylogarithmic Nash regret in arbitrary finite matrix games with bandit payoff feedback, a guarantee previously limited to 2 × 2 games under that feedback. OPB achieves O(log^2 T) Nash regret against adaptive opponents, including when equilibria are nonunique, by coordinating a reference strategy with uncertainty-scaled local adjustments.

  • Problem

    With bandit payoff feedback, prior polylogarithmic Nash-regret guarantees covered only 2 × 2 games, leaving open whether observed opponent actions suffice in arbitrary finite dimensions.

    Source: §1 · p. 2

  • Method

    OPB constructs a reference strategy that leaves room for local adjustments, then orders independent payoff differences by estimation accuracy and scales adjustments by uncertainty.

    Source: §1 · p. 3

  • Results

    OPB achieves instance-dependent O(log^2 T) Nash regret in arbitrary finite dimensions against adaptive opponents, including games with nonunique equilibria.

    Source: §1 · p. 2, §5 · p. 11

  • Takeaways & Limitations

    The result establishes that observing opponent actions suffices for polylogarithmic Nash regret in general finite matrix games with bandit payoff feedback.

    Source: §5 · p. 11

    The setting assumes a fixed unknown payoff matrix and observed opponent actions, while allowing the opponent to respond to the learner's strategy and history-dependent reward noise.

    Source: §2 · p. 3

Abstract

from arXiv · show

We study Nash regret minimization in unknown finite matrix games with bandit payoff feedback and observed opponent actions. We develop Optimistic Payoff Balancing (OPB), which achieves instance-dependent $\mathcal{O}(\log^2 T)$ Nash regret against arbitrary adaptive opponents, including games with nonunique equilibria. This resolves the open problem posed by Maiti et al. (2025), extending their polylogarithmic guarantee under bandit feedback from $2\times2$ games to arbitrary finite dimensions. To handle nonunique equilibria, we construct a reference strategy that leaves room for local adjustments. We order independent payoff differences by estimation accuracy and scale these adjustments by uncertainty, allowing the learner to exploit the opponent's imbalance to offset estimation costs. Our result thus shows that observing opponent actions suffices for polylogarithmic Nash regret in general finite matrix games.

1 Introduction

The paper asks whether observed opponent actions make instance-dependent polylogarithmic Nash regret possible in arbitrary finite matrix games with bandit payoff feedback. OPB answers affirmatively, extending the bandit-feedback guarantee beyond the 2 × 2 setting and handling adaptive opponents and nonunique equilibria.

1 Introduction

  • Maiti et al. (2025) established the guarantee for arbitrary dimensions with full-matrix feedback but only for 2 × 2 games under bandit feedback.Unequal rates at which opponents reveal columns make higher-dimensional payoff estimation harder.Source: §1 · p. 2
  • OPB achieves instance-dependent O(log^2 T) Nash regret for arbitrary finite games against adaptive opponents, including games with nonunique equilibria.The finite constant depends on the fixed payoff matrix, including its dimensions.Source: §1 · p. 2
  • OPB handles nonunique equilibria by maximizing a joint logarithmic objective over row probabilities and column slacks, leaving room for local adjustments.The resulting reference supports rows used by an optimum and slacks for columns that can exceed the optimum's value.Source: §1 · p. 3
  • OPB orders independent payoff differences by estimation accuracy and scales each adjustment range by its uncertainty.Confidence-bound shrinkage prevents a truly zero coefficient from triggering an update.Source: §1 · p. 3
  • Persistent payoff imbalance lets local updates earn surplus reward that absorbs accumulated estimation costs, yielding logarithmic regret per epoch and an overall O(log^2 T) bound.The selection order ensures repeated visits either advance sample counts to a reconstruction threshold or create persistent imbalance.Source: §1 · p. 3

2 Preliminaries

The preliminaries define the unknown zero-sum game and the informed bandit setting, where the learner observes both the sampled payoff and the opponent's action. They frame the goal as achieving a finite, game-dependent bound on Nash regret.

2 Preliminaries

  • An equilibrium row strategy guarantees expected reward at least the game value against every opponent strategy, and either player may have multiple equilibrium strategies.Source: §2 · p. 3
  • The learner controls the row player in a fixed unknown payoff matrix, while the opponent may respond to the learner's mixed strategy and the history.The sampled actions are drawn independently conditional on the history and chosen strategies; the learner observes both actions and a noisy payoff.Source: §2 · p. 3
  • Nash regret measures cumulative reward shortfall relative to the game value; small regret keeps cumulative reward close to that value during learning.Source: §2 · p. 4
  • The stated goal is one algorithm that needs neither the payoff matrix nor the time horizon and has a finite bound depending only on the fixed matrix, including its dimensions.Source: §2 · p. 4

3 Achieving Polylogarithmic Nash Regret

This section presents OPB’s periodic payoff estimation and local strategy updates based on observed opponent actions, establishing instance-dependent polylogarithmic Nash regret in arbitrary finite games, including those with nonunique equilibria. Its proof tracks an adjusted optimum with bounded variation, bounds regret per epoch logarithmically, and sums the run bounds.

3.1 Algorithm Design

  • OPB assigns unresolved entries payoff 1 until they reach h observations, then uses empirical means; this optimistic completion costs at most 2nmh in expected payoff.The model is rebuilt at count thresholds h, 2h, 4h, ... while accumulated observations are retained.Source: §3.1 · pp. 4, 5, 8
  • To handle nonunique equilibria, OPB builds an interior reference with room for local adjustments and selects independent binding-column payoff differences using an accuracy-ordered confidence test.For sufficiently accurate estimates, the reference retains rows used by any optimum and has positive surplus against nonbinding columns; the certificate rejects directions attributable to estimation noise.Source: §3.1 · pp. 5–7
  • OPB scales adjustment ranges to payoff uncertainty, shrinks uncertain payoff coefficients toward zero, and uses observed opponent actions for projected updates that correct estimation bias and exploit persistent column imbalance.The update uses the same entry confidence bounds to set both the adjustment range and conservative gradient.Source: §3.1 · pp. 7–8

3.2 Regret Guarantee

  • O(log^2 T) Nash regret is achieved in arbitrary finite matrix games against adaptive opponents, resolving the open problem posed by Maiti et al. (2025).The guarantee permits nonunique Nash equilibria for both players and requires no prior knowledge of equilibrium supports or game-dependent separation parameters.Source: §3.2 · pp. 9–10
  • On a simultaneous confidence event, the proof sketch shows that the center and certificate identify optimal row supports, binding columns, and independent differences, while count ordering limits visits to certain binding columns before reconstruction.Local strategies maintain positive probability on selected rows and surplus against nonbinding columns; the analysis frames estimation cost against available payoff advantage.Source: §3.2 · p. 10
  • The comparison point adjusts a true optimum to correct empirical payoff differences while keeping its norm at most 3/4 and total coordinate variation at most K_A V.Projected gradient ascent is compared with u_l(t) + 1/4 sgn(d_l); the shift contributes advantage U, while comparator variation and coefficient errors cost at most K_A(ell + V).Source: §3.2 · p. 10
  • For sufficiently large H, epoch regret is at most K_A ell; when b = 0, the epoch deficit is already nonpositive.The proof obtains this bound after ensuring K_A epsilon <= 1.Source: §3.2 · p. 10
  • O_A(log^2(eT)) regret holds after summing conditional run bounds, for every run prefix and hence the full horizon.The proof also absorbs smaller horizons into the instance-dependent constant.Source: §3.2 · p. 10

4 Related Work

Prior work studies regret minimization, instance-dependent guarantees, and equilibrium learning under differing feedback and opponent assumptions. This work addresses the Nash benchmark against arbitrary opponents in finite matrix games.

4 Related Work

  • Under bandit feedback, no-regret learning competes with the best fixed action, while later work studies instance-dependent bounds in bandits and self-play games.The section traces this line from regret-minimization foundations to adaptive algorithms.Source: §4 · pp. 10–11
  • For arbitrary opponents, prior work studies regret against the Nash or pure maximin value, benchmarks that distinguish mixed-strategy guarantees from pure-action guarantees.The paper positions its result as addressing the Nash benchmark in arbitrary finite games.Source: §4 · p. 11
  • Equilibrium-learning work develops guarantees across game classes, but studies settings where all players follow specified algorithms rather than one learner facing an arbitrary opponent.The cited line includes last-iterate convergence and finite-sample learning from payoff observations.Source: §4 · p. 11

5 Conclusion

OPB achieves instance-dependent polylogarithmic Nash regret under bandit feedback with observed opponent actions, including against adaptive opponents and in games with nonunique equilibria. The conclusion attributes this guarantee to a reference strategy that supports local adjustments, and the paper reports AI assistance in writing and proof-related work.

5 Conclusion

  • OPB achieves instance-dependent O(log^2 T) Nash regret against arbitrary adaptive opponents, including games with nonunique equilibria.The conclusion says the result resolves Maiti et al. (2025)'s open problem for arbitrary dimensions under bandit feedback.Source: §5 · p. 11
  • Jointly centering row probabilities and column slacks leaves room for local strategy adjustments even when equilibria are nonunique.OPB orders independent payoff differences by estimation accuracy and scales adjustments by uncertainty to exploit opponent imbalance and offset estimation costs.Source: §5 · p. 11
  • The conclusion states that observing opponent actions suffices for polylogarithmic Nash regret in general finite matrix games.Source: §5 · p. 11

AI use statement

  • The authors report using GPT-6 Astra to polish writing, assist with proof calculations, and check correctness, while reviewing AI-assisted content and taking responsibility for the final paper.Source: AI use statement · p. 11

A Proof of Theorem 1

The proof analyzes a planned-length run conditional on its starting history, then combines estimation-cost and payoff-offset bounds to establish Theorem 1. Its constants and thresholds depend only on the fixed game matrix.

A Proof of Theorem 1

  • The proof conditions on any starting history and analyzes a run with planned length H.Source: A Proof of Theorem 1 · p. 14
  • Lemma 2 bounds optimistic-completion costs and simultaneous sampling; Lemmas 3 and 4 recover relevant rows and columns and provide valid coefficient intervals.Source: A Proof of Theorem 1 · p. 14
  • Lemmas 5 and 6 pair accumulated estimation cost with a negative payoff contribution that absorbs it, and the proof combines them for Theorem 1.Source: A Proof of Theorem 1 · p. 14
  • The appendix uses finite positive constants and finite thresholds that depend only on A, uniformly over the listed completed matrices, row sets, reference columns, and selected-column lists.Source: A Proof of Theorem 1 · p. 14

A.1 Optimistic completion and sampling bounds

Lemma 2 bounds expected Nash regret by separating the cost of incomplete entries from regret in completed games. It also supplies simultaneous sampling bounds and a bound on the number of epoch reconstructions.

A.1 Optimistic completion and sampling bounds

  • Expected Nash regret is bounded by the sampling term plus a completion-cost term of 2nmh.The completion cost arises because each entry contributes at most h observations, each with cost at most two.Source: §A.1 · pp. 14–15
  • On an event of probability at least 1 − H^-2, the sampling bounds hold simultaneously across entries, attained positive counts, and rounds through H.The stated event probability is bounded by nm(2H + 1)e^-ℓ ≤ H^-2.Source: §A.1 · p. 14
  • At most O_n,m(1 + log H) epochs intersect any prefix, because each entry crosses each doubling count threshold at most once.Reconstructions occur when an entry count reaches h, 2h, 4h, and subsequent doubling thresholds.Source: §A.1 · pp. 14–15

A.2 Identifying the optimal support and binding columns

The lemma identifies the optimal row support, binding columns, and independent payoff differences from empirical constructions. It also provides a reference strategy with room for feasible local updates.

A.2 Identifying the optimal support and binding columns

  • The joint center identifies which row probabilities and column slacks vanish throughout the optimal set, enabling construction of an interior reference strategy.The center has only O_A(ε) total mass outside the identified row support; restricting it to that support preserves the game value.Source: §A.2 · pp. 16–17
  • For sufficiently large H, the selected row and column sets match the true optimal support and binding columns, and the constructed local strategies retain positive probabilities and nonbinding slacks.For every z in the stated update range, the strategy remains normalized and satisfies the lower bounds β_A.Source: §A.2 · p. 16
  • Every point in Z lies within K_Aε of the optimal row set, by a distance-to-optimal-set bound and the entrywise accuracy of acquired entries.Artificial entries agree exactly with the completion, and the game value is Lipschitz in the largest entrywise error.Source: §A.2 · p. 16
  • The accepted trial differences recover the true greedy independent list when estimation error is sufficiently small.An accepted certificate implies invertibility and independence of the true projected differences; finiteness yields recovery of the true list for sufficiently small ε.Source: §A.2 · p. 17

A.3 Confidence bounds for the true coefficients

Binding columns admit unique representations in the selected payoff-difference coordinates. Confidence intervals and shrinkage then preserve the signs of nonzero coefficients while controlling estimation error.

A.3 Confidence bounds for the true coefficients

  • The coefficient confidence intervals contain the true coefficients, and shrinking each interval to its nearest point to zero preserves every nonzero coefficient’s sign.The corrected coefficient’s distance from the true coefficient is at most 2b_lj.Source: §A.3 · pp. 18–19
  • Each binding-column difference has a unique representation in the selected payoff-difference basis, with coefficients bounded over the finite family of true matrices and lists.For b = 0, each binding column equals v(B)1.Source: §A.3 · p. 18
  • When a binding column has infinite observation count, its difference and both coefficient vectors are zero.Source: §A.3 · p. 19

A.4 Column visits and accumulated estimation error

The visit and estimation bounds separate sampling uncertainty from payoff advantage due to persistent opponent-column imbalance. The visit bound uses the ordering of selected differences to control active counts.

A.4 Column visits and accumulated estimation error

  • V measures accumulated estimation cost, while U measures payoff advantage available from persistent opponent-column imbalance.Both quantities are set to zero when b = 0.Source: §A.4 · p. 19
  • Active visits in each coordinate are bounded by K_A(q_l + |d_l|), linking visit counts to sample scales and the opponent’s column imbalance.The passage describes this as stronger than a direct epoch-length bound: many active visits must either exhaust available samples or create a large payoff advantage U.Source: §A.4 · p. 19
  • The selected-difference order bounds active visits by separating columns with counts above and below q_l; columns with zero coefficient have only the lower-count visits active.The lower-count visits satisfy N_low ≤ K_A q_l.Source: §A.4 · p. 20

A.5 Regret within an epoch

The epoch analysis compares play with a constructed true optimum and bounds regret using payoff advantage and comparator variation. When the advantage is zero, the epoch deficit is nonpositive.

A.5 Regret within an epoch

  • When b = 0, every round’s deficit is nonpositive, so the epoch regret is nonpositive.The lemma also bounds epoch regret in terms of U and V when b is nonzero.Source: §A.5 · p. 20
  • The constructed comparison strategy p* is a true optimum and retains positive surplus against every nonbinding column.The proof constructs it from an optimal comparison strategy while preserving a probability distribution.Source: §A.5 · pp. 20–21
  • The estimated comparison is bounded by K_A(1 + V), with V capturing comparator variation.The projected-gradient argument also accounts for changing comparators and replacement of estimated coefficients by true coefficients.Source: §A.5 · pp. 21–22

A.6 Proof of the main theorem

The proof bounds regret within epochs, then sums the bounds across geometrically growing runs. This yields a logarithmic-squared regret bound for every horizon.

A.6 Proof of the main theorem

  • Each epoch contributes at most O_A(ℓ), and every run prefix contributes at most O_A(log^2(eH)).The bound includes b = 0; smaller planned lengths are absorbed into the same finite constant.Source: §A.6 · p. 22
  • The bound holds uniformly over permitted opponents and reward processes, for every planned length and prefix.The proof applies the run bounds conditionally at each fresh run and sums them when time T falls within a run.Source: §A.6 · pp. 22–23
  • R_T ≤ C(A) log^2(eT) for every integer T ≥ 1.The first run has length H_0 = 2 and contributes only a constant.Source: §A.6 · p. 23
Loading 2609.34812v1…