acceptodds
Under review as a conference paper at ICLR 2027

Adaptive Maximin Learning with Intermittent Opponent Observations

Abstract

We study an unknown zero-sum matrix game against an adaptive opponent, with learner actions, opponent actions, and rounds. Rewards are always observed; opponent actions are independently revealed with unknown probability . The benchmark is the best mean payoff a fixed action can guarantee against every opponent action. Regret is the expected sum of this value minus the mean payoff of each chosen action pair. A base policy given only achieves worst-case regret and two gap-dependent logarithmic bounds. One uses revealed actions and scales as for . The other holds with the same constant for every at a strict pure saddle, a pair of actions that are unique best responses to each other. On a family with tied opponent best responses, the revealed-action bound has a matching fixed-instance lower bound for policies with logarithmic worst-case regret on every fixed matrix at every fixed . An enhanced policy combines row-reward estimates with revealed-action frequencies. It uses the same inputs, preserves the base guarantees, and attains dependence on a different two-row family for .

Primary area:
learning theory
Keywords:
Online learning, zero-sum matrix games, pure-strategy maximin regret, bandit feedback, intermittent opponent observations, instance-dependent regret.

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_prHhOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper considers a two-player matrix game with random reward revelations and seeks to minimize the expected pseudo-regret that benchmarks against the maximin matrix entry (reward mean). It proposes a combined framework of UCB and FTRL to achieve the best-of-three-worlds type of bounds in Theorem 1, and provides a lower bound for the bound with respect to the revelation frequency. In addition, it gives an illustrative example in Section 5 for a two-action game, where the dependence on the revelation frequency can be further improved.

Critical strengths
  • This work achieves three types of upper bounds simultaneously in one algorithm. Although the combination is not delicate, it is indeed effective.
  • The illustrative example in Section 5 is interesting and implies a direction to be studied further.
Critical weaknesses
  • The presentation is overall less than satisfying: some of the writing is clearly not polished (such as Line 351 "For Cc>0C_c>0, Cc≥12C_c\ge \frac12, ..."), some of it is overwhelmed with unnecessarily detailed technical description and computation (such as Section 4), and some leaves core pieces of the only algorithm to the appendix (the FTRL to Appendix B). In particular, I would appreciate if the authors could give high-level explanations before or amidst the technical details throughout the paper and if they could formally introduce the FTRL in the main text (it is not even written as a clear algorithm in the appendix).
  • The example in Section 5 is way too "toy" to be an illustrative example for exploiting the column frequency estimation to further optimize the upper bound. Importantly, there is not a right-to-the-point summary that gives the spirit of this example (correct me if I miss it, but I only find computations of the example in Section 5). If I understand correctly, it is saying: If the opponent plays col 2 frequently enough to make row 2 attractive, then the regret incurred is nonpositive and offsets future regret; otherwise, it is clear that row 1 is safe and the regret is therefore low. Equally importantly, this section should include a claim that extends this idea to all or a family of two-action games and use the current example as a special case, for the completeness of this work. Otherwise it looks like a preliminary result of this direction as it is now.
Questions for authors
  • Can the authors give clear high-level descriptions of the key ideas, in Section 3, 4, and 5, and include them in later revision?
  • Can the authors address my concerns in the weaknesses above?
  • Can the authors provide a more general statement for the idea in the two-action example in Section 5?
1 comment
AuthorsOpenReview ↗

Response to Reviewer prHh

Thank you for pointing to the missing step in the explanation of Section 5. Your interpretation of the frequent-column case is correct. In the other case the learner still needs to establish a payoff gap from noisy observations. Here is the argument we would put before the calculations.

A statement for a family of two-action games. Suppose the two rows are (v,v+b)(v,v+b) and (v−a,v+c)(v-a,v+c) with a,c>0a,c>0 and b≥0b\geq0. The first row guarantees vv. For a common column-2 frequency θ\theta, the second row's deficit relative to vv is d(θ)=a−(a+c)θd(\theta)=a-(a+c)\theta. The first row's advantage over it is g(θ)=d(θ)+bθg(\theta)=d(\theta)+b\theta. Two consequences explain the example. If the second row matches or beats the first, its deficit is nonpositive. If θ≤a/[2(a+c)]\theta\leq a/[2(a+c)], the first row has a payoff advantage of at least a/2a/2. Between these cases, any positive deficit is at most the payoff advantage. This also explains why the sign of regret in (2) matters.

For an adaptive opponent, the comparison needs the same frequency for both rows. On rounds when the safe row leads and the other row is eligible, let WW be the sum of the other row's play probabilities and OO their sum on column-2 rounds. For W>0W>0 take θ=O/W\theta=O/W. The two estimates in (18) use exactly these weights. In (17), a=αa=\alpha, b=βb=\beta, and c=1/2−αc=1/2-\alpha, so Wd=αW−O/2Wd=\alpha W-O/2 and Wg=Wd+βOWg=Wd+\beta O. Rewards control WgWg through (20). Revealed frequencies help recover the first-column payoff through (19). When sufficiently many observations accumulate, the confidence intervals exclude the losing alternative. The payoff identities above hold across this larger family. The rate in Theorem 2 uses the specific payoffs in (17).

How Sections 3 and 4 fit together. The leader is the row with the most optimistic estimate of its guaranteed payoff. Assigning it at least half the probability makes its reward observable often enough to test that estimate. The remaining probability lets eligible rows challenge it. Every round provides a reward for this comparison. A revealed column also identifies a matrix entry, so eventually a row can be ruled out as a challenger on the strength of a particular column. Equation (11) separates the cost of the leader/reference play from the cost of the challengers. At a strict saddle, playing the safe row off the saddle column earns a surplus that absorbs part of the comparison cost. For the entry bound, (16) instead counts losses on labeled rounds and uses independent revelation to translate the count into total expected regret.

The FTRL step. In Algorithm 1 the input to FTRL is the vector utu_t of estimated losses relative to the leader, whose conditional mean is given in (10). With G=∑s<tusG=\sum_{s<t}u_s, it chooses xt=arg⁡min⁡x∈Δm(⟨G,x⟩+∑iλtiF(xi)−64∑ilog⁡xi),zti=Txti+1/mT+1,x_t=\arg\min_{x\in\Delta_m}\left(\langle G,x\rangle+\sum_i\lambda_{ti}F(x_i)-64\sum_i\log x_i\right),\qquad z_{ti}=\frac{T x_{ti}+1/m}{T+1}, where F(x)=−2x+(1−x)log⁡(1−x)+xF(x)=-2\sqrt{x}+(1-x)\log(1-x)+x. The update starts at λ1i=16\lambda_{1i}=16 and changes only the coefficient of the sampled feedback coordinate, by (B.15). Putting this optimization and its update together in one main-text algorithm box, and moving the constant calculations to the appendix, would make Algorithm 1 easier to follow.

Finally, line 351 uses the payoff range. Every positive gap Δ=v−Aij\Delta=v-A_{ij} is at most 2, so each such entry contributes 1/Δ≥1/21/\Delta\geq1/2 to CcC_c. This is what allows the confidence-failure term in (16) to be absorbed when there is a positive gap.

Reviewer_BQd5OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies the problem of online learning against an adaptive and adversarial opponent in zero-sum games, where the opponent's actions are only intermittently observed with an unknown probability q∈[0,1]q \in [0, 1]. It proposes a single strategy that simultaneously achieves optimal worst-case regret bounds and various instance-dependent logarithmic regret bounds. The paper's contributions focus on theoretical analysis.

Critical strengths

Strength:

  • A novel unified adaptive strategy that achieves optimal worst-case regret bounds, a logarithmic bound that applies when a strict pure-strategy saddle point exists, and a logarithmic bound based on estimates derived from revealed actions.
  • Tight Information-Theoretic Lower Bound of 1/q1/q (Proposition 1).
  • Rigiroous theoretical analysis.
Critical weaknesses
  • There is no empirical study even in simulated data.
  • Missing several highly relevant prior works: - Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback, Ito et al., COLT 2025. - On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedback, Maiti et al., SAGT 2025.
Questions for authors

Address weakness points

1 comment
AuthorsOpenReview ↗

Response to Reviewer BQd5

Thank you for identifying these two papers and for raising the absence of simulations.

Empirical scope. Our question is whether one learner, given only the dimensions and horizon, can attain both gap-dependent guarantees against an arbitrary adaptive opponent. A simulation could illustrate play against a chosen opponent. At moderate horizons, however, the explicit confidence bounds are conservative (Theorem A.1), and the observed regret depends on how frequently that opponent chooses informative or favorable columns. Such a curve would give little evidence about which worst-opponent dependence on qq or the gaps is necessary. The paper therefore makes a theoretical claim and leaves practical finite-horizon performance unevaluated.

A concrete comparison is already possible without fitting a rate. Take the two matrices in Section 2 at q=1q=1. In the first, (Cs,Cc)=(4/ε,4)(C_s,C_c)=(4/\varepsilon,4), so shrinking ε\varepsilon leaves the revealed-entry guarantee intact. In the second, (Cs,Cc)=(16,4+1/ε)(C_s,C_c)=(16,4+1/\varepsilon), so shrinking ε\varepsilon leaves the strict-saddle guarantee intact. The same policy obtains the better bound in each game without knowing which game it faces. Proposition 1 separately gives a family where the 1/q1/q cost of the entry guarantee is necessary as TT grows. These examples address the distinction the algorithm was designed to capture.

Related work. Both citations belong in the discussion. Ito, Luo, Tsuchiya and Wu (COLT 2025) prove instance-dependent bounds on the players' external pseudo-regret in bandit self-play. In particular they obtain logarithmic regret in the pure-equilibrium case when both players run Tsallis-INF. Our guarantee concerns the row player even when the column player adapts arbitrarily to its announced distribution. The COLT 2026 paper of Ito et al. cited in our Table 1 is a separate work. It studies this one-sided pure maximin benchmark and gives the two algorithmic guarantees that motivate our simultaneous bound. Ito et al., COLT 2025 · Ito et al., COLT 2026

Maiti, Jamieson and Ratliff (SAGT 2025) also consider a unilateral learner against an adversarial opponent. Their benchmark is the mixed Nash value VV, which satisfies V≥vV\geq v. On a common sequence of play, the two regrets differ by exactly T(V−v)T(V-v), so a Nash-regret upper bound also bounds our regret under the same feedback assumptions. Their bandit result covers 2×22\times2 games and observes the realized column every round. Their general-dimensional result uses noisy full-matrix feedback. Our question is what a learner can guarantee in general dimensions from one reward per round when column labels arrive with an unknown probability, including q=0q=0. The overlap at q=1q=1 and the difference at q<1q<1 are both important. Maiti et al., SAGT 2025

Reviewer_S2cEOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies an unknown zero-sum matrix game. At each round, the opponent sees the learner’s row distribution before choosing a column, and then the learner samples a row and receives a reward. The particular setting studied in this paper is that the learner sees the exact column with an unknown probability qq. The paper gives one base algorithm that satisfies three regret bounds: a general worst-case bound, a bound for strict pure saddles, and a bound that uses qq. It proves a matching lower bound for the qq-related bound on a specific family of games. It also gives a stronger result for a special 2×22\times2 family.

Critical strengths

The paper proposes a single algorithm that satisfies 3 bounds. This is a useful result. The proof and techniques are described in detailed. An asymptotic lower bound is given for one of the bound related to qq.

Critical weaknesses
  1. The paper does not give a matching lower bound for the strict-saddle bound in Theorem 1. The lower bound considers a setting with no strict saddle. Theorem 1 gives a three upper bounds in the strict-saddle setting, so the upper bound is the minimum of the three, but It is unclear whether this upper bound is tight. The given lower bound is also asymptotic, so it does not prove tightness for all possible parameters m,T,qm,T,q.

  2. The extra result in Section 5 applies only to a narrow 2×22\times2 family. It is unclear if the result or the technique can be extended.

  3. The results rely on a specific setting. The opponent sees the learner’s distribution, but not the action actually sampled. This makes the opponent weaker. The paper gives little discussion of when this model applies or how the results might change if the opponent sees the sampled action. Revealing the column to the learner has probability qq in the current setting, but this probability can also change over time, or the revealing can be adversary.

Questions for authors

Please refer to the "Critical Weaknesses".

1 comment
AuthorsOpenReview ↗

Response to Reviewer S2cE

Thank you for asking where the bounds are tight and which parts depend on the observation model.

Tightness at a strict saddle. Theorem 1 is a simultaneous upper bound. Whether its minimum is sharp on a given strict-saddle matrix remains open. Proposition 1 fixes both a matrix in its tied-best-response family and a reveal probability q>0q>0 before taking TT to infinity. For any policy with logarithmic worst-opponent regret on every fixed matrix at every fixed positive qq, the worst-opponent regret on that matrix is Ω(Cclog⁡T/q)\Omega(C_c\log T/q). This establishes the cost of missing labels on that family. At the reward-only endpoint q=0q=0, Theorem 2 of Ito et al. (COLT 2026) already gives a complementary lower bound. For two rows and two columns, small gaps and sufficiently large TT, some game forces regret at least a constant times min⁡(1/(αβ),T)\min(1/(\alpha\beta),\sqrt T). This helps explain the gap product in CsC_s. Tightness of the three-way minimum across positive qq and finite horizons remains unresolved. Ito et al., Theorem 2

There is also a reason to look beyond these two gap parameters. In Corollary D.5, two families of strict-saddle matrices have the same Cs,Cc,q,TC_s,C_c,q,T and differ in one payoff. Even when the learner knows the two possible row orderings and their payoffs, but does not know which ordering it faces, the ratio of the families' minimax regrets grows without bound. The off-saddle payoff determines how much exploration can earn back.

Scope of Section 5. The q−1/2q^{-1/2} upper bound is for (17) and its row swap. Its underlying identity is more general. Against a common column mixture, a row paying v−av-a in column 1 and v+cv+c in column 2 has mean deficit a−(a+c)θa-(a+c)\theta, where θ\theta is the weight of column 2. If column 2 masks the loss in column 1 often enough, that row itself earns the benchmark. When the weight is small, the observed rewards contain information about its first entry. Turning this identity into a regret rate requires controlling the accuracy of the frequency and payoff estimates. Theorem 2 does that for (17). Extending the rate to a broader class is open.

Order of play and missing labels. The model covers simultaneous moves with private randomization. An opponent may know the learner's announced policy and adjust to it every round, while the particular row draw stays private until both sides commit. This timing gives Pr⁡(It=i∣Ft−1,Jt)=pt(i)\Pr(I_t=i\mid\mathcal F_{t-1},J_t)=p_t(i), the identity behind the reward comparison in (10). If the opponent sees the sampled row first, it can choose a different column for each row. Comparing two rows against the same realized column using (10) then loses its justification.

Independence of the labels has a separate role. For the signed conditional deficit dt=v−∑ipt(i)AiJtd_t=v-\sum_i p_t(i)A_{iJ_t}, (16) uses E∑tBtdt=qRT\mathbb E\sum_t B_td_t=qR_T. With a time-varying conditional reveal probability qtq_t, the corresponding expression is E∑tqtdt\mathbb E\sum_t q_td_t. Replacing qq by its time average would therefore mix different deficits with different weights. An adversarial observer could, for example, reveal only one column, leaving the other entirely unlabeled. The reveal-dependent guarantees in our paper are for independent, constant-probability labeling.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.