PaperlayerView exact revision on arXiv

Source-linked AI summary

Thompson Sampling for Learning in Zero-Sum Games

Kenshi Abe, Kaito Ariu, Po-An Wang

arXiv:2610.18899v1cs.GTstat.ML

TL;DR

Whether plain Thompson sampling can learn equilibrium play in unknown zero-sum games remains poorly understood, because sampling an equilibrium may not reveal the payoff information needed to correct estimates. The paper analyzes centralized self-play with a posterior-sampled payoff matrix and establishes regret rates, an exact leading coefficient, and lower bounds. The rates are O(√T) for games with a unique equilibrium and O(log T) for pure equilibria.

  • Problem

    Plain Thompson sampling’s behavior for learning equilibrium play in unknown zero-sum games remains poorly understood.

    Source: §1 · p. 1

  • Method

    Under centralized self-play, Nash-TS samples one payoff matrix from the posterior and plays a Nash equilibrium of that sampled game.

    Source: §1 · p. 1, §3 · p. 3

  • Results

    For every fixed game with a unique Nash equilibrium, expected cumulative duality gap is O(√T), improving to O(log T) for pure equilibria, with an exact square-root-term coefficient and matching lower bounds in stated classes.

    Source: §1 · p. 1, §8 · p. 8

  • Takeaways & Limitations

    The square-root coefficient depends only on equilibrium strategies and noise level, while payoff entries outside equilibrium supports contribute only lower-order terms.

    Source: §1 · p. 1, §8 · p. 8

    The analysis leaves games with multiple equilibria and the gap between finite-horizon upper and lower bounds for future work.

    Source: §8 · p. 8

Abstract

from arXiv · show

Thompson sampling (TS) achieves logarithmic and asymptotically optimal regret in classical stochastic bandits, but its behavior in multi-agent learning remains less understood. We study TS in an unknown finite two-player zero-sum matrix game with Gaussian bandit feedback. Under centralized self-play, TS samples a single payoff matrix from the posterior and plays a Nash equilibrium of the sampled game. For every fixed zero-sum game with a unique Nash equilibrium, we show that the expected cumulative duality gap is $O(\sqrt T)$. The rate improves to $O(\log T)$ for pure equilibria. We then identify the exact coefficient of the $\sqrt T$ term, which depends only on the equilibrium strategies and the noise level. We also establish a minimax lower bound matching the square-root dependence on $T$ and an instance-dependent lower bound matching the logarithmic dependence on $T$ for a class of games with a unique pure equilibrium. Experiments support the predicted rates and coefficient.

1 INTRODUCTION

The paper studies whether plain Thompson sampling can learn equilibrium play in unknown zero-sum games, where posterior sampling may not provide the information needed to correct payoff estimates. Under centralized self-play, it establishes regret rates and matching lower bounds for specified game classes.

1 INTRODUCTION

  • Plain Thompson sampling samples a payoff matrix from the posterior and plays a Nash equilibrium of that sampled game, but its behavior in games remains poorly understood.The technical challenge is that playing a sampled equilibrium need not provide information sufficient to correct inaccurate payoff estimates.Source: §1 · p. 1
  • O(√T) expected cumulative duality gap holds for every fixed game with a unique Nash equilibrium, improving to O(log T) for pure equilibria.The analysis separates a square-root contribution from estimating payoffs within equilibrium supports and a logarithmic contribution from excluding actions outside them; the former vanishes for pure equilibria.Source: §1 · pp. 1–2
  • The square-root term’s exact coefficient depends only on the equilibrium strategies and noise level, so entries outside equilibrium supports contribute only lower-order terms.Source: §1 · pp. 1–2
  • The square-root dependence on T is unavoidable in the worst case, even for games with a unique fully mixed Nash equilibrium.Source: §1 · pp. 1–2
  • For uniformly efficient policies, logarithmic dependence on T is unavoidable on fixed instances in a subclass of games with a unique pure equilibrium.Source: §1 · pp. 1–2

2 RELATED LITERATURE

Prior work studies learning in games under bandit feedback, posterior sampling in games, and Thompson sampling in classical bandits. This paper distinguishes Nash-TS by its centralized equilibrium selection and guarantees for games with a unique equilibrium.

Thompson sampling in stochastic bandits

  • Classical stochastic-bandit results include logarithmic and problem-independent regret bounds for Bernoulli bandits and asymptotic optimality for Bernoulli and one-dimensional exponential-family bandits.Source: §2 · p. 2

Learning in games with bandit feedback

  • In self-play, Ito et al. (2025) establish instance-dependent regret bounds, achieving logarithmic regret when a pure Nash equilibrium exists.Source: §2 · p. 2
  • Yang et al. (2025) and Nayak et al. (2026) establish eO(√T) cumulative duality-gap bounds, with logarithmic factors hidden.Source: §2 · p. 2

Posterior sampling for games

  • Nash-TS uses neither regularization nor continued forced exploration after initialization, and obtains O(√T) expected cumulative duality gap, O(log T) for pure equilibria, and an exact leading coefficient.The contrasted matrix-game TS variant combines regularized equilibrium computation with continued explicit exploration and has an eO(T^3/4) cumulative-gap bound in probability while allowing multiple equilibria.Source: §2 · p. 2

3 PRELIMINARIES

The paper studies a fixed but unknown payoff matrix in a two-player zero-sum game, with the row player maximizing and the column player minimizing expected payoff. It evaluates learning using the cumulative duality gap under centralized bandit feedback.

Two-player zero-sum matrix games

  • The row and column players receive expected payoffs xᵀA⋆y and −xᵀA⋆y, respectively, so their objectives are max-min.Source: §3 · p. 2

Nash equilibrium and duality gap

  • A strategy profile is pure when each player assigns probability one to one action, and fully mixed when each assigns positive probability to every action.Source: §3 · p. 2
  • The duality gap sums both players’ gains from switching to best responses; it is nonnegative and equals zero exactly at Nash equilibria.Source: §3 · p. 2

Problem setting

  • A centralized learner chooses both strategies, draws both players’ actions independently, and observes only the noisy payoff for the realized action pair.The noise variance is known and unselected action-pair payoffs remain unobserved; cumulative duality gap is the evaluation objective.Source: §3 · p. 3

4 NASH THOMPSON SAMPLING

Nash-TS repeatedly samples a payoff matrix from the posterior and plays a Nash equilibrium of the sampled game. It initializes by observing every action pair once, then updates the posterior for only the realized pair.

4 NASH THOMPSON SAMPLING

  • Nash-TS samples a payoff matrix from the posterior, selects one of its Nash equilibria, draws both players’ actions independently, and updates the observed entry.Source: §4 · p. 3, §4.2 · pp. 3–4

4.1 Posterior Sampling

  • The learner observes each pure-strategy pair once during the first mn rounds to obtain a proper posterior.It then uses observations and empirical means to sample matrix entries independently from their posteriors.Source: §4.1 · p. 3

4.2 Equilibrium Selection and Posterior Update

  • After selecting an equilibrium of the sampled matrix, the learner draws the two actions independently and updates only the posterior for the realized action pair.Nash-TS is anytime and does not require knowledge of the horizon.Source: §4.2 · pp. 3–4

5 CUMULATIVE GAP UPPER BOUNDS

Under a unique Nash equilibrium, Nash-TS achieves square-root cumulative duality-gap growth in general and logarithmic growth for pure equilibria. The analysis identifies the exact square-root coefficient and separates support estimation from the cost of excluding outside actions.

5.1 Finite-Horizon Bound

  • O(√T) is the general expected cumulative duality-gap bound, improving to O(log T) for a unique pure equilibrium.The bound assumes a fixed game with a unique Nash equilibrium; its square-root term vanishes for pure equilibria, while its logarithmic term vanishes for fully mixed equilibria.Source: §5.1 · p. 4
  • For mixed equilibria, estimation errors can shift probabilities within the true supports; for pure equilibria, matching supports force play of the true actions and eliminate the square-root term.The logarithmic term accounts for sampled play using actions outside the true supports.Source: §5.1 · p. 4

5.2 Exact Asymptotics

  • For every fixed game with a unique non-pure equilibrium, the expected cumulative duality gap is Θ(√T), with exact leading coefficient 2Λcore.With noise level fixed, Λcore depends on the game through its equilibrium strategies and supports; it is zero for pure equilibria and positive otherwise.Source: §5.2 · p. 5
  • For equilibria uniform on their supports, the leading coefficient scales as σ√d log d, independently of the number of actions outside the supports.Here d is the support size.Source: §5.2 · p. 5

5.3 Proof Sketch

  • Although Nash-TS has no explicit exploration after initialization, posterior draws occur with probability bounded below and can induce positive-probability play of every support action.This supplies observations of support entries, allowing their estimation errors to shrink with observation counts.Source: §5.3 · pp. 5–6
  • Outside-support actions that still appear profitable retain an insufficiently observed entry; after O(log T) observations, large posterior errors contribute only O(1) rounds in expectation.Bounding the remaining rounds by the number of observations below that threshold yields the logarithmic contribution.Source: §5.3 · p. 6

6 CUMULATIVE GAP LOWER BOUNDS

The section establishes lower bounds matching the square-root and logarithmic dependence on T of the upper bounds, respectively, for fully mixed games and fixed separable instances with a pure equilibrium. The logarithmic lower bound applies to uniformly efficient policies.

6 CUMULATIVE GAP LOWER BOUNDS

  • The cumulative duality-gap lower bounds match the square-root dependence on T in the minimax sense and the logarithmic dependence on fixed separable instances with a pure equilibrium.The section states these results as matching the corresponding upper-bound rates.Source: §6 · p. 6

6.1 Minimax Lower Bound

  • For every policy, some bounded-payoff game with a unique fully mixed equilibrium has an unavoidable square-root dependence on T in its worst-case cumulative duality gap.The result holds for m = n ≥ 4 and payoff radius R > 0.Source: §6.1 · p. 7

6.2 Instance-Dependent Lower Bound

  • On a separable family with a unique pure equilibrium, uniformly efficient policies incur an unavoidable logarithmic dependence on T on each fixed instance.The proof uses alternatives that make one suboptimal row or column uniquely optimal and a Gaussian change-of-measure argument.Source: §6.2 · p. 7
  • The instance-dependent result gives an explicit asymptotic lower bound for cumulative duality gap under Gaussian feedback, complementing a related external-regret lower bound under Bernoulli feedback.Ito et al. (2025) prove the related result for separable games with a pure Nash equilibrium.Source: §6.2 · p. 7

7 EXPERIMENTS

Across six benchmarks, Nash-TS has the smallest final mean cumulative duality gap, with especially strong comparisons on pure- and boundary-mixed-equilibrium games. On mixed-equilibrium games, its normalized cumulative gap approaches the coefficient predicted by the analysis.

7 EXPERIMENTS

  • The experiments compare Nash-TS with PMO-LB and symmetric UCB across games with pure, fully mixed, boundary mixed, and multiple equilibria, plus random games with 25 or 50 actions per player.Runs use T = 10^5 observations, Gaussian noise with standard deviation σ = 1/5, and 100 trials per game.Source: §7 · p. 7
  • Nash-TS attains the smallest final mean gap on all six benchmarks, substantially outperforming PMO-LB on pure and boundary-mixed games while performing similarly on the fully mixed game.It also performs well on a multiple-equilibria game and random games with 25 and 50 actions per player.Source: §7 · p. 7, Figure 1 · p. 8
  • On the two mixed-equilibrium games, Nash-TS’s cumulative gap divided by t approaches the coefficient predicted by Theorem 5.2.The curves are means over 100 trials; the dashed lines show 2Λcore.Source: §7 · p. 7, Figure 2 · p. 8

8 CONCLUSION

The conclusion summarizes Nash-TS’s cumulative-gap rates, exact leading coefficient, and matching lower bounds. The appendix characterizes how uniqueness constrains nearby equilibria and when a restricted-game equilibrium remains valid and unique in the full game.

8 CONCLUSION

  • For fixed games with a unique Nash equilibrium, Nash-TS has expected cumulative duality gap O(√T), improving to O(log T) for pure equilibria, and its exact √T coefficient depends on equilibrium strategies and noise level.The lower bounds establish optimal dependence on T in the minimax sense for fully mixed games and on fixed separable instances with a pure equilibrium.Source: §8 · p. 8
  • The conclusion identifies extending the analysis to multiple equilibria and narrowing the finite-horizon gap between upper and lower bounds as future directions.The experiments include a multiple-equilibria game, but the analysis assumes uniqueness.Source: §8 · p. 8

A EQUILIBRIUM GEOMETRY UNDER UNIQUENESS

  • With a unique Nash equilibrium, sufficiently close support submatrices have a unique fully mixed equilibrium that varies continuously with the submatrix.The equilibrium support sizes are equal.Source: A EQUILIBRIUM GEOMETRY UNDER UNIQUENESS · p. 11

The outside margins satisfy

  • A restricted-game equilibrium extended by zeros is an equilibrium of the full game exactly when all outside margins are nonpositive; strictly negative existing margins ensure uniqueness.Nonpositive margins alone do not ensure uniqueness when an outside margin is zero.Source: The outside margins satisfy · p. 11
  • To retain the restricted equilibrium as the unique full-game equilibrium, payoff estimates need be accurate only on entries with at least one index in the equilibrium supports.No accuracy bound is required on entries whose two indices are both outside those supports.Source: The outside margins satisfy · p. 12

A.1 Proof of Lemma A.1

This appendix section develops technical tools for the analysis, including stability and gap bounds for perturbed games and estimates for Gaussian sums, interval probabilities, and conditional Gaussian vectors. It also records notation for the unique-equilibrium instance and provides bounds for tail control, convergence, and uniform probability estimates.

A.1 Proof of Lemma A.1

  • Nearby core games have a unique fully mixed equilibrium, and the proof extends this equilibrium’s uniqueness from the core systems.Continuity of the system solutions preserves positivity near the original game; the proof then rules out any other equilibrium.Source: §A.1 · pp. 12–13

A.2 Proof of Lemma A.2

  • The core gap coefficient is 2 when d ≥ 2 and 0 when d = 1, yielding the bound min{χ_core/p^2, 2/p}.The proof combines the core coefficient with bounds expressed using the equilibrium probabilities.Source: §A.2 · p. 14

A.3 Proof of Lemma A.3

  • Uniqueness of the fully mixed equilibrium implies positive directional bounds for zero-sum perturbations in both players’ strategy spaces.The proof establishes positive constants κ_x and κ_y, including the d = 1 case.Source: §A.3 · p. 14

A.4 Proof of Lemma A.4

  • The zero extension of a restricted equilibrium is a full-game equilibrium exactly when all outside-action margins are nonpositive; strict negativity ensures uniqueness.Strictly negative outside margins force both players’ equilibrium probabilities on outside actions to be zero.Source: §A.4 · p. 15

A.5 Proof of Lemma A.5

  • Under the stated entrywise accuracy condition, Lemmas A.1 and A.4 give a unique full-game equilibrium by extending the core equilibrium.The passage also indicates that a product bound follows, but does not provide its form.Source: §A.5 · p. 15

B.1 Proof of Lemma B.1

  • Gaussian estimates control finite maxima and sample means, including a same-order lower bound for maxima of independent standard Gaussians.The proof uses Gaussian moment and tail bounds with Jensen’s inequality and a union bound.Source: B GAUSSIAN ESTIMATES · p. 15, §B.1 · p. 18

B.2 Proof of Lemma B.2

  • The expected decreasing order statistics of absolute Gaussian values are bounded without requiring independence.The proof applies tail bounds and integrates them over the order-statistic index.Source: B GAUSSIAN ESTIMATES · p. 15, §B.2 · p. 19

B.3 Proof of Lemma B.3

  • When deterministic shifts sum to zero, Gaussian variation in a subset of coordinates gives a lower bound on the expected maximum.The proof decomposes the Gaussian variables and averages over permutations of the shifts.Source: B GAUSSIAN ESTIMATES · p. 16, §B.3 · p. 19

B.4 Proof of Lemma B.4

  • Exponential martingales, a union bound over signs and sequences, and integration yield tail and expectation bounds for the maximal normalized partial sums.The proof defines U_D,k as the maximum over sequences and sample sizes N ≥ k of |S_a,N|/N.Source: §B.4 · pp. 19–20

B.5 Proof of Lemma B.5

  • Gaussian tail bounds are integrated against a specified derivative to establish finiteness, including the case r = 0.The integral is finite because its integrand is a polynomial times an exponentially decaying term.Source: §B.5 · p. 20

B.6 Proof of Lemma B.6

  • Kolmogorov’s maximal inequality controls increments around deterministic indices, and Slutsky’s theorem yields the stated limits, including independent N(0, 2) bracketed variables.The indices satisfy n_a(t)/t → ν_a > 0, and the deterministic-index sums are independent N(0, 1).Source: §B.6 · p. 20

B.7 Proof of Lemma B.7

  • Standardization and Gaussian symmetry give lower bounds on interval probabilities using the interval length and the standardized distance from the mean.The proof treats intervals avoiding zero separately from intervals containing zero, then establishes a second claim using a positive lower bound on L/τ.Source: §B.7 · p. 21

B.8 Proof of Lemma B.8

  • A Gaussian vector is decomposed into independent Gaussian components, enabling a bound on its infinity norm when the scalar component lies in (0, L].On that event, ∥Z∥∞ ≤ ∥W∥∞ + (M + L)/p.Source: §B.8 · p. 21

B.9 Proof of Lemma B.9

  • The proof establishes that q*(c) is positive almost surely and that R(c) is finite almost surely, using Gaussian tail bounds and finite moments.It applies Lemma B.5 to bound the expectation of 1/q*(c) and to establish finiteness of the other terms.Source: §B.9 · pp. 21–22

B.10 Proof of Lemma B.10

  • For fixed noise sequences, the proof derives a uniform lower probability bound over the stated index vectors and weights, and establishes a finite-moment claim.It fixes α = 3∆/(8σ), applies Lemma B.7 with ℓ = L/(2σ), and uses independence across sequences to bound moments.Source: §B.10 · p. 22

C.1 Notation

  • The proof defines the outside-action margins and tracks which core entries remain under-sampled, alongside events where the sampled core is near and its equilibrium is played.It also fixes the unique-equilibrium instance, its equilibrium supports and value, and notation for the realized core and conditional probabilities.Source: §C.1 · p. 23

C.2 Proof of Theorem 5.1

The proof develops controls on equilibrium-support behavior, bad rounds, and posterior errors, decomposing the duality-gap bound into nonlocal, core-error, and outside-margin contributions. These controls yield dimension-dependent bounds on the cumulative duality-gap constant, with special cases for pure or fully mixed equilibria.

C.3 Proof of Lemma C.1

  • A finite constant Bloc bounds the nonlocal-round contribution for every horizon, with dependence only on (A⋆, σ, m, n).Applying Lemma C.1 controls the first sum in the proof’s decomposition.Source: §C.2 · p. 24

C.4 Proof of Lemma C.2

  • Conditioned on the complete noise sequences and past actions, sampled entries are independent with the asserted conditional Gaussian distributions.The fixed equilibrium-selection rule and independent action sampling give probability xt,i yt,j of choosing action pair (i, j).Source: §C.2 · p. 24

C.5 Proof of Lemma C.3

  • For any fixed set of D entries, the expected cumulative posterior error is bounded when each entry’s indicator is at most its observation indicator.The theorem proof applies this lemma to the d² core entries and their observed-round indicators.Source: §C.2 · pp. 24–25

C.7 Proof of Lemma C.5

  • The occupation bound uses finite constants when players have outside-support actions, and sets both constants to zero when neither does.When both players have outside actions, the proof uses a horizon-independent random variable with finite expectation; with exactly one, it uses a separate comparison lemma.Source: §C.2 · p. 25, §C.7 · pp. 30–31

C.2 Proof of Theorem 5.1

  • The three-part bound uses finite instance-dependent constants; its mixing term vanishes for pure equilibria, while its outside-action term vanishes for fully mixed equilibria.The constants depend only on (A⋆, σ, m, n).Source: §C.2 · p. 26

C.6 Proof of Lemma C.4

  • With probability at least 1 − δ, positive outside-row or outside-column margins on near rounds require some relevant entry count to be below the threshold.The lemma also bounds its failure probability by δ.Source: §C.6 · pp. 29–30

C.8 Proof of Lemma C.6

  • For localized cores, outside-row and outside-column margins are negative with high probability, while a positive outside-row margin under the stated conditions forces sampling probability on core actions.The proof compares positive-margin events with observations of low-count entries and derives a lower bound on xt,i yt,j when an outside row has a positive margin and other outside rows have negative margins.Source: §C.8 · pp. 31–32
  • The proof controls the second term by splitting rows according to empirical-error accuracy, bounding errors uniformly over counts, and combining good-core estimates with the finite Bbad bound.Bbad depends only on (A⋆, σ, m, n).Source: §C.8 · p. 33

C.9 Proof of Lemma C.8

  • Almost surely on Neart, no outside margin is zero; the embedded restricted equilibrium is the unique equilibrium exactly when all outside margins are strictly negative.Strict negativity forces equilibrium strategies to assign zero probability to actions outside the restricted supports.Source: §C.9 · p. 34

C.10 Proof of Lemma C.7

  • When an outside row margin θ is positive but at most λ(M2; g, κy), every sampled-game equilibrium has yj ≥ p/2 and xiyj ≥ η(M1, M2; g, κy) for j in J⋆.The lemma assumes a unique Nash equilibrium and bounds the other outside margins by −g.Source: §C.10 · pp. 35–36

C.11 Proof of Lemma C.9

  • For games with actions outside the equilibrium support, Lemma C.11 supplies row and column controls that yield a finite Bbad, uniformly over rounds and localized cores.The bound depends only on (A⋆, σ, m, n).Source: §C.11 · pp. 37–38

C.12 Proof of Lemma C.10

  • A positive outside-row margin θ forces a value gap v(B) − vC ≥ 2θpη(M1, M2; g, κy).The proof obtains this by combining a lower bound on the value gap with its upper bound by xiθ.Source: §C.12 · p. 38

C.13 Proof of Lemma C.11

  • Gaussian bounds apply simultaneously across current count vectors and localized cores, controlling near-zero positive outside-row margins; the same construction handles columns.The column argument swaps the row and column margin and gradient parameters.Source: §C.13 · pp. 38–39

C.14 Dimension Dependence of the Cumulative Duality Gap Bound

  • With geometric quantities and σ fixed, Cocc is O(1 + log(2d)) in one-sided cases and O((1 + log(2mn))^2) for two-sided supports.The two-sided bound uses d(m + n − d) ≤ mn; products of reciprocal probabilities contribute to C0, whose dimension dependence is unrestricted.Source: §C.14 · p. 39

D.1 Proof of Theorem 5.2

The proofs establish an expectation limit for the horizon-independent recursion, use it to bound cumulative duality gap, and derive the coefficient’s Gaussian structure. They also prove core consistency and a lower bound for the uniform equilibrium case.

D.2 Proof of Lemma D.1

  • The expected quantity in Lemma D.1 converges to Λ_core, with the proof controlling its first term by uniform integrability and its second term by equilibrium continuity.The argument splits the expectation according to observation counts.Source: §D.1 · p. 40, §D.2 · p. 42

D.1 Proof of Theorem 5.2

  • The upper- and lower-bound arguments combine to identify the asymptotic coefficient through core Gaussian maxima, whose terms are centered Gaussians with variance 2σ^2/y⋆.The other expected maximum is nonnegative, and the two scalar terms cancel when d = 1.Source: §D.1 · p. 41

D.3 Proof of Lemma D.2

  • Core consistency yields observation frequencies converging jointly in probability to the equilibrium frequencies, followed by a Gaussian limit with independent entries of variance 2σ^2/x⋆_j.The proof obtains the frequency convergence by controlling posterior error and equilibrium continuity.Source: §D.3 · p. 44

D.4 Proof of Corollary 5.3

  • For a uniform equilibrium, each of the two Gaussian families consists of independent N(0, 2σ^2d) variables, so the lower bound applies to both.The coefficient is written as the sum of two expected maxima.Source: §D.4 · p. 44

E PROOFS FOR THE MINIMAX LOWER BOUND

The proof constructs a bounded family of games with unique fully mixed equilibria, analyzes posterior uncertainty under the learning policy, and concludes that some admissible game attains the lower bound.

E PROOFS FOR THE MINIMAX LOWER BOUND

  • The constructed games A_μ have unique fully mixed equilibria when ∥μ∥∞ ≤ R/(8m).The proof uses payoff equalization to determine the equilibrium strategies.Source: E PROOFS FOR THE MINIMAX LOWER BOUND · pp. 44–45
  • The observation likelihood has Gaussian coordinates, and at least ⌊m/2⌋ rows retain posterior variance at least τ^2/3.The likelihood argument cancels the policy’s parameter-independent sampling kernels.Source: E PROOFS FOR THE MINIMAX LOWER BOUND · p. 45
  • A Gaussian union bound controls the loss outside the bounded parameter set before its contribution is subtracted from the lower-bound estimate.The proof then applies the resulting bound to the restricted prior.Source: E PROOFS FOR THE MINIMAX LOWER BOUND · p. 45
  • Some admissible parameter μ attains the minimax lower bound established by the proof.The prior is restricted to bounded games before this conclusion.Source: E PROOFS FOR THE MINIMAX LOWER BOUND · p. 45

F PROOFS FOR THE INSTANCE-DEPENDENT LOWER BOUND

The proof obtains an instance-dependent lower bound by comparing a game with perturbed alternatives, using the information required to distinguish them under a uniformly efficient policy.

F PROOFS FOR THE INSTANCE-DEPENDENT LOWER BOUND

G EXPERIMENTAL DETAILS AND ADDITIONAL RESULTS

Appendix G describes the experimental setup and compares Nash-TS with VMG and Greedy. Nash-TS has a smaller final mean cumulative gap than VMG on all six games, while Greedy shows substantially greater variability.

G.1 Computational Setup

  • Experiments ran on a Mac with an Apple M2 Max chip and 32 GB RAM; HiGHS computed equilibria, while SciPy supported the Figure 2 coefficient calculation.The coefficient was computed by numerical integration of Gaussian-maximum expectations.Source: §G.1 · p. 46

G.2 Game Instances

  • The four structured games cover unique pure, fully mixed, and boundary equilibria, plus a game with a row-player equilibrium segment.The fourth game has a unique column-player equilibrium; random payoff games use 25 or 50 actions per player, with entries drawn independently and uniformly from [−1, 1].Source: §G.2 · p. 47, Table 1 · p. 47

G.3.1 PMO-LB

  • PMO-LB uses doubling epochs, epoch-only empirical payoff matrices, and log-barrier game solutions, setting entries unobserved during an epoch to zero.Its regularization scale is selected using 20 validation runs per game; Gaussian observations are unclipped, so the original [−1, 1] guarantee does not directly apply.Source: §G.3.1 · p. 47

G.3.2 Symmetric UCB

  • Symmetric UCB applies O’Donoghue et al. (2021)’s rule to both players using a shared empirical payoff matrix and counts, with c = 1 and no tuning.It observes every payoff entry once at initialization; the single-learner guarantee does not directly provide a cumulative duality-gap bound for this symmetric implementation.Source: §G.3.2 · p. 48

G.4.1 Comparison with VMG

  • Nash-TS has a smaller final mean cumulative gap than VMG on all six games.Figure 3 averages 100 trials; VMG sums equilibrium-strategy gaps once per iteration, using two observations per iteration.Source: §G.4.1 · p. 48, Figure 3 · p. 49

G.4.2 Comparison with Greedy

  • Greedy shows substantially greater variability than Nash-TS, PMO-LB, and symmetric UCB, consistent with premature commitment to noisy initial estimates.Figure 4 reports mean cumulative duality gaps with one-standard-error bands.Source: §G.4.2 · p. 49, Figure 4 · p. 50
Loading 2610.18899v1…