REVIEW 4 major objections 6 minor 12 references
Learning to Play Against Unknown Opponents
T0 review · 4 major / 6 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read The paper proves that optimal no-regret commitment against a distribution of strategic opponents reduces to one linear program over correlated profiles, and that unconstrained and maximin variants are tractable in the stated parameter…
desk verdict Genuinely new algorithms for optimal commitment against a distribution of opponents, but with a real indexing/role-swap bug in Eq. (2) and Lemma 2.6 that needs fixing before the paper is sound as written. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the menu of a learning algorithm: the convex set of asymptotic correlated strategy profiles (CSPs) the opponent can induce by playing against it. The load-bearing tools are the characterization that a closed convex set is a menu exactly when, for every opponent mixed action $y$, some learner mixed action $x$ puts $x \otimes y$ in the set, and the sandwich theorem that every no-regret menu contains $M_{NSR}$ and is contained in $M_{NR}$. These translate algorithm design into choosing points in a polytope, via the LP of Lemma 3.1, or into Blackwell-approachability checks on candidate sets $C(\Phi) = \{\phi : \text{each optimizer type prefers its assigned profile}\}$; the approachability checks supply the separation oracle for the general commitment problem and the abortable implementation used by the maximin algorithm.
What would settle it
Run the implementing algorithm from Appendix B.3 on the $3 \times 2$ game of Theorem 3.3: the menu construction claims the learner can force utility $5$ while any no-swap-regret baseline gives only $3$, so if a long-run simulation of the constructed algorithm fails to converge to a correlated profile with learner utility $5$, the menu-to-algorithm transfer is false.
Extended reading notes
Core claim
The paper's core claim is that committing to a learning algorithm in this strategic setting is equivalent to committing to a menu: a closed convex set of correlated strategy profiles that the opponent can asymptotically induce. Under no-regret, every valid menu is sandwiched between $M_{NSR}$ and $M_{NR}$, and this sandwich lets the paper write the set of valid assignments of profiles to optimizer types as an explicit polytope. Solving one linear program then gives the optimal no-regret menu, and the menu can be implemented algorithmically by offering each type their assigned profile and falling back to a no-swap-regret algorithm. For general unconstrained commitment, the paper establishes an $\varepsilon$-optimal menu by separating candidate menus via Blackwell approachability, in time $(mnk/\varepsilon)^{O(\min(mn,k))}$; it proves a matching bottleneck by showing that deciding whether a convex set is a valid menu is NP-hard. Finally, for the maximin objective it constructs an algorithm that guarantees the optimizer never pushes the learner below $OPT - \varepsilon$, even though $OPT$ itself is conjectured NP-hard to compute.
Load-bearing premise
The load-bearing premise is the menu characterization inherited from prior work: a closed convex set of correlated profiles is an implementable asymptotic menu of some learning algorithm exactly when every opponent mixed strategy $y$ admits a learner mixed strategy $x$ with $x \otimes y$ in the set, and the menu's value equals the algorithm's value; if that correspondence breaks for finite horizons or approximate best responses, all of the constructions inherit the gap.
Editorial extensions
If this is right
- A learner who is willing to commit to no-regret play can, in time poly($n,m,k$), find the exact optimal commitment against a prior over opponent payoffs; no search over learning algorithms is needed.
- Because any concave objective over the assignment can be substituted into the LP, the same polynomial-time result covers learner utilities that depend on the opponent's type and worst-case (maximin) objectives in the no-regret setting.
- When no-regret is not imposed, near-optimal commitment is constructible in polynomial time unless both the game and the support of the prior grow; if both grow, even checking whether a candidate menu is valid is NP-hard.
- The maximin algorithm achieves $OPT - \varepsilon$ per round in polynomial time per iteration, and it delegates part of the computation of the optimal menu to the opponent: either the opponent accepts a good correlated profile or demonstrates that the current candidate menu is unapproachable.
- The constructions are implementable, not merely existential: the menu-to-algorithm translation via Blackwell approachability yields learning algorithms with polynomial per-round time complexity.
Reading between the lines
- Beyond the paper, the LP formulation suggests that selecting among a finite family of known learning baselines in a Bayesian strategic interaction could be reduced to the same menu sandwich whenever a base menu and an upper menu are both valid, making the no-regret result a template for other constrained commitment problems.
- A testable extension of the maximin construction is that the same abort-and-retry loop should work for any one-dimensional objective defined by a concave function of the CSP assignment, and would hit hardness for higher-dimensional objectives exactly where approachability certificates become NP-hard to find.
- If deciding menu validity is NP-hard in general, practical solvers for the unconstrained problem will likely have to commit to menus with special structure, such as menus defined by few optimizer-type constraints, or invoke the optimizer as an oracle the way the maximin algorithm does.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies a repeated general-sum game in which a learner commits to a learning algorithm before an optimizer, drawn from a known prior over payoff types, best responds to that commitment. The learner's goal is to maximize either expected utility or worst-case (maximin) utility. Using the asymptotic-menu framework of [ACS24], the authors give four main results: (1) under a no-regret constraint on the learner's algorithm, the optimal menu can be found in polynomial time by solving an explicit LP over correlated-strategy-profile assignments (Theorem 3.2); (2) without the no-regret constraint, an approximately optimal menu can be found in time (mnk/ε)^{O(min(mn,k))} using separation oracles built from Blackwell approachability (Theorem 4.1); (3) deciding whether a given candidate menu is valid is NP-hard (Theorem 4.15); and (4) for the maximin objective, an explicit learning algorithm runs in polynomial time per round and guarantees utility within ε of the optimal value without computing that value (Theorem 4.17). The paper also includes a counterexample showing that no-swap-regret algorithms are not always optimal for the learner.
Significance. If the main results hold, the paper settles the computational complexity of optimal no-regret commitment and gives a strong algorithmic framework for general commitment via menus and approachability. The polynomial-time result for no-regret commitment is surprising given the NP-hardness of Bayesian Stackelberg problems in related settings, and the maximin algorithm is a genuinely novel use of abortable approachability to sidestep a known NP-hard decision problem. The paper makes good use of the menu machinery from [ACS24] and the reductions to Blackwell approachability are conceptually clean. However, because several of the central formal statements about no-swap-regret menus are internally inconsistent as printed, the correctness of the main theorems cannot currently be certified from the text; the intended statements appear standard and locally fixable, so the contribution remains promising.
major comments (4)
- [Section 2.3, Eq. (2)] Equation (2) as printed is not a valid definition of a no-swap-regret CSP. The left-hand side has a free index j while the right-hand side sums over j, and the formula does not match the swap-regret definition given above it. The correct condition is sum_{i,j} phi_ij u_L(i,j) >= sum_i max_{i' in [m]} sum_j phi_ij u_L(i',j), equivalently the linear inequalities sum_j phi_ij(u_L(i',j)-u_L(i,j)) <= 0 for all i,i'. Because M_NSR, Lemma 2.6, the Stackelberg values v_i, and the constraints of LP (4) all rest on this definition, the current text does not support the proof of Theorem 3.2 as written. The definition should be corrected and the imported properties of M_NSR should be restated consistently with it.
- [Section 2.4, Lemma 2.6] Lemma 2.6 has a type mismatch: BR_L is defined on Delta_n and returns subsets of Delta_m, but the lemma states x in Delta_m and y in BR_L(x). The intended statement, consistent with the earlier observation that M_NSR is valid because for each y in Delta_n it contains x tensor y for some x in BR_L(y), and with the Stackelberg discussion immediately following it, is that M_NSR is the convex hull of {x tensor y : y in Delta_n, x in BR_L(y)}. As printed, the lemma cannot be used to identify v_i = max_{phi in M_NSR} u_{O,i}(phi) with the optimizer's Stackelberg leader value. This identification is exactly how Lemma 2.6 is used in Algorithm 1 and LP (4), so the statement must be corrected and its proof or reference made consistent.
- [Section 4.3, Theorem 4.18] The displayed chain of inequalities in the proof of bound (8) is not a valid argument as written: it introduces an undefined y* and performs an algebraic step that does not follow from the preceding display. The intended bound can be obtained directly from the Anytime Hedge guarantee and the choice condition. Let r_t be the reward vector and note that the choice condition gives <p_t, r_t> <= 0 for every t. If M_tau = max_i sum_{t<=tau} r_{t,i} and S_tau = sum_{t<=tau} <p_t, r_t>, then the Hedge regret bound gives M_tau - S_tau = O(sqrt(tau log k)); since S_tau <= 0, it follows that M_tau = O(sqrt(tau log k)). This bound is load-bearing because it justifies the inclusion M(BlackwellAbort(Phi)) subset C(Phi), which in turn is essential for Theorem 4.17. The proof should be rewritten with this argument.
- [Section 4.3, Algorithm 2] Algorithm 2 can fail on games where no CSP gives the learner utility 1. Line 5 defines phi_i as an argmax over F(V), but if V=1 and F(1) is empty, phi_i is undefined and the algorithm cannot proceed. Such games exist even though all payoffs lie in [-1,1], e.g., when every entry of u_L is 0.5. The algorithm should initialize V with a feasible upper bound on OPT, such as V0 = max_{phi in Delta_mn} u_L(phi), or should explicitly handle the case F(V)= by decreasing V before computing Phi(V). Without this fix, Theorem 4.17 is not established for all games in the stated domain.
minor comments (6)
- [Section 2.1] In the definition of a no-regret algorithm, the phrase 'regardless of the sequence of actions (x_1,...,x_T) taken by the optimizer' should refer to the optimizer's actions y_t; throughout the paper x_t denotes the learner's mixed strategy.
- [Section 3, proof of Theorem 3.2] The sentence 'verifying that phi_i in M_NR can be done by checking that the regret with respect to each of the n pure learner actions is non-positive' should say m pure learner actions, not n.
- [Section 4.1, proof of Theorem 4.1] The case split 'If mn < d' is vacuous because d = min(mn,k); it should read 'If mn < k' so that the choice between the oracle of Theorem 4.11 and that of Theorem 4.14 is meaningful.
- [Section 4.1, Theorem 4.8] This theorem uses the symbol d without defining it in the statement. It should clarify that d denotes the dimension of the vector-valued payoff (mn for the candidate-menu oracle, k for the utility-set oracle), rather than the global min(mn,k).
- [Appendix B.4, Lemma B.2 proof] In the proof, the expression phi_k in M(B_{T_k}^K) appears to contain a typo; it should refer to the finite-horizon menu of the particular sub-algorithm B_k at horizon T_k, not to a fixed K.
- [Section 4.3, Theorem 4.17] The statement that Algorithm 2 'runs in time poly(n,m,k) per iteration' is too weak for a complexity claim; the total number of iterations is O(1/epsilon), so the full guarantee should state that the overall running time is poly(n,m,k,1/epsilon).
Circularity Check
No circular reduction: the no-regret, general-commitment, and maximin results are genuine optimizations over menu/CSP polytopes; reliance on [ACS24] is prior-work support, not a fitted prediction or definitional equivalence.
full rationale
The paper's derivation chain is not circular. For the no-regret commitment result, Lemma 3.1 proves an iff characterization of valid CSP assignments using the sandwich relation M_NSR within M within M_NR, and the LP (4) is exactly this characterization with a linear objective; nothing is fitted to the target optimum or defined in terms of it. The general commitment results optimize over the convex sets R and S and use [MT09] as an external approachability oracle; the maximin construction uses Anytime Hedge and Blackwell approachability, with the optimizer's role being to certify unapproachability rather than to supply the claimed value. The main self-citation is to [ACS24] for the menu characterization (Theorems 2.1, 2.3, 2.4, Lemmas 2.5 and 2.6, and the appendix implementation). This reliance is load-bearing in the sense that the results are stated in menu language, but it is a prior theorem rather than an assumed premise equivalent to the paper's conclusions; its assumptions do not include the unknown-opponent optimization target, and no equation in this paper reduces that target to the menu characterization by construction. The apparent internal inconsistency in Eq. (2) and the type confusion in Lemma 2.6 are correctness or typo concerns, not circularity. I therefore find no significant circularity.
Assumptions & free parameters
assumptions (8)
- domain assumption A closed convex M is a valid asymptotic menu iff for every y in the simplex there exists x with x tensor y in M (Theorem 2.1 of [ACS24]).
- domain assumption For every no-regret algorithm A, MNSR is contained in M(A) and M(A) is contained in MNR; all no-swap-regret algorithms have menu exactly MNSR (Theorems 2.3 and 2.4, Lemma 2.5 of [ACS24]).
- standard math Blackwell approachability theorem: a response-satisfiable set is approachable (Theorem 4.7).
- standard math The Mannor-Tsitsiklis algorithm decides approachability of an explicit polytope in time exponential in the payoff dimension (Theorem 4.8 of [MT09]).
- ad hoc to paper Cutting-plane optimization over P requires a small ball of radius rmin with log(1/rmin) polynomial; the authors assert this is WLOG by expanding R and S by epsilon/100.
- domain assumption An optimal valid menu attaining the supremum OPT exists.
- domain assumption The optimizer knows the committed algorithm, plays a sequence approximately maximizing own payoff up to o(T), and breaks ties in the learner's favor.
- standard math Stackelberg equilibria in normal-form games can be computed in polynomial time (Theorem 2.7 of [CS06]).
Cite this review
Pith. "Pith review of Learning to Play Against Unknown Opponents." pith.science (2026). https://pith.science/paper/F2OXQDFX
@misc{pith2026241218297,
author = {Pith},
title = {Pith review of: Learning to Play Against Unknown Opponents},
year = {2026},
howpublished = {\url{https://pith.science/paper/F2OXQDFX}},
note = {Machine review of arXiv:2412.18297}
}
abstract
We consider the problem of a learning agent who has to repeatedly play a general sum game against a strategic opponent who acts to maximize their own payoff by optimally responding against the learner's algorithm. The learning agent knows their own payoff function, but is uncertain about the payoff of their opponent (knowing only that it is drawn from some distribution $\mathcal{D}$). What learning algorithm should the agent run in order to maximize their own total utility, either in expectation or in the worst-case over $\mathcal{D}$? When the learning algorithm is constrained to be a no-regret algorithm, we demonstrate how to efficiently construct an optimal learning algorithm (asymptotically achieving the optimal utility) in polynomial time for both the in-expectation and worst-case problems, independent of any other assumptions. When the learning algorithm is not constrained to no-regret, we show how to construct an $\varepsilon$-optimal learning algorithm (obtaining average utility within $\varepsilon$ of the optimal utility) for both the in-expectation and worst-case problems in time polynomial in the size of the input and $1/\varepsilon$, when either the size of the game or the support of $\mathcal{D}$ is constant. Finally, for the special case of the maximin objective, where the learner wishes to maximize their minimum payoff over all possible optimizer types, we construct a learner algorithm that runs in polynomial time in each step and guarantees convergence to the optimal learner payoff. All of these results make use of recently developed machinery that converts the analysis of learning algorithms to the study of the class of corresponding geometric objects known as menus.
Reference graph
Works this paper leans on
-
[5]
[DDFG23] Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson , and Noah Golowich. From external to swap regret 2.0: An efficient reduction and oblivious adversary fo r large action spaces. arXiv preprint arXiv:2310.19786,
-
[6]
Efficient learning and computation of linear correlated equilibrium in general convex games
[DFF+24] Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Ch arilaos Pipis, and Jon Schnei- der. Efficient learning and computation of linear correlated equilibrium in general convex games. arXiv preprint arXiv:2412.20291 ,
-
[9]
Robust no -regret learning in min-max stackelberg games
21 [GZG22] Denizalp Goktas, Jiayi Zhao, and Amy Greenwald. Robust no -regret learning in min-max stackelberg games. arXiv preprint arXiv:2203.14126 ,
-
[10]
Auctions between regret-m inimizing agents
[KN22a] Yoav Kolumbus and Noam Nisan. Auctions between regret-m inimizing agents. In Proceedings of the ACM Web Conference 2022 , pages 100–111,
work page 2022
-
[1997]
C ontracting with a learning agent
[GKS+24] Guru Guruganesh, Yoav Kolumbus, Jon Schneider, Inbal Talga m-Cohen, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Joshua R Wang, and S Matthew Weinberg. C ontracting with a learning agent. arXiv preprint arXiv:2401.16198 ,
-
[2006]
Persuading a Behavioral Agent: Approximately Best Responding and Learning
[CL23] Yiling Chen and Tao Lin. Persuading a behavioral agent: Appro ximately best responding and learning. arXiv preprint arXiv:2302.03719 ,
-
[2007]
[BMSW18] Mark Braverman, Jieming Mao, Jon Schneider, and Matt We inberg. Selling to a no-regret buyer. In Proceedings of the 2018 ACM Conference on Economics and Comp utation, pages 523–538,
work page 2018
-
[2008]
Fast swap regret minimizat ion and applications to approx- imate correlated equilibria
[PR23] Binghui Peng and Aviad Rubinstein. Fast swap regret minimizat ion and applications to approx- imate correlated equilibria. arXiv preprint arXiv:2310.19647 ,
Show all 12 references
-
[2019]
Schapire
[FS96] Yoav Freund and Robert E. Schapire. Game theory, on-line p rediction and boosting. In Avrim Blum and Michael J. Kearns, editors, Proceedings of the Ninth Annual Conference on Computa- tional Learning Theory, COLT 1996, Desenzano del Garda, Ita ly, June 28-July 1, 1996 ,...
1996
-
[2022]
Learning and approximating the optimal strategy to commit to
[LCM09] Joshua Letchford, Vincent Conitzer, and Kamesh Munaga la. Learning and approximating the optimal strategy to commit to. In Algorithmic Game Theory: Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18-20,
2009
-
[2023]
Efficient stackelberg strategies for finitely repeated games
[CAK23] Natalie Collina, Eshwar Ram Arunachaleswaran, and Michael K earns. Efficient stackelberg strategies for finitely repeated games. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems , pages 643–651,
2023
-
[2024]
[AHPY24] Nivasini Ananthakrishnan, Nika Haghtalab, Chara Podimat a, and Kunhe Yang
Association for C omputing Machinery. [AHPY24] Nivasini Ananthakrishnan, Nika Haghtalab, Chara Podimat a, and Kunhe Yang. Is knowl- edge power? on the (im) possibility of learning from strategic interac tion. arXiv preprint arXiv:2408.08272,
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.