{"id":"041a528f-c137-4cdf-aec1-5c0d28422e95","arxiv_id":"2412.18297","paper_version":2,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For repeated games against an unknown optimizer type, the paper gives polynomial-time optimal no-regret commitment, near-optimal general commitment when the game or support size is constant, a polynomial-per-step maximin algorithm, and an NP-hardness result.","lead":"This paper gives algorithms for a learner who repeatedly plays a game against an opponent whose payoffs are drawn from a known distribution, when the opponent rationally responds to the learner's committed algorithm. The main results are polynomial-time optimal no-regret commitments, near-optimal unconstrained commitments when the game or type support is small, and a polynomial-per-step worst-case maximin algorithm.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The no-swap-regret menu is mis-specified: Eq. (2) and Lemma 2.6 are internally inconsistent, and Theorem 3.2's LP relies on them.","rationale":"The reader identified the menu framework inherited from [ACS24] as the weakest assumption, but the paper's own formal definitions of the no-swap-regret menu are internally inconsistent. Equation (2) is a false characterization, and Lemma 2.6 swaps the roles of x and y. These are not mere notation choices: the LP (4) in Section 3 uses M_NSR to compute v_i and to certify the menu M=conv(M_NSR∪{ϕ_i}) is no-regret, so the proof of Theorem 3.2—the paper's headline polynomial-time result—depends on the correct statement of these objects. The intended mathematics is standard and can be repaired, but as written the manuscript's central proof contains a formal gap. I therefore recommend a conditional accept: the authors should correct Eq. (2) and Lemma 2.6 and confirm that Lemma 3.1 and Theorem 3.2 remain valid under the corrected definitions. This does not affect the broader structure of the paper, and other results (Section 4) are largely independent of this specific misstatement, but the no-regret commitment result is not sound without the fix.","tokens_in":26809,"tokens_out":42229,"duration_ms":356157,"concrete_test":"Independently re-derive Lemma 3.1 using the corrected no-swap-regret condition (∑_{i,j}φ_ij uL(i,j) ≥ ∑_i max_{i'}∑_j φ_ij uL(i',j)) and the corrected Lemma 2.6 (extreme points x⊗y with y∈Δ_n, x∈BR_L(y)). Then verify that the LP (4)—with constraints ϕ_i∈M_NR, uO_i(ϕ_i)≥uO_i(ϕ_i') for all i,i', and uO_i(ϕ_i)≥v_i where v_i is the Stackelberg leader value of type i—is exactly equivalent to the three conditions of Lemma 3.1. If the equivalence fails, Theorem 3.2 does not follow from the corrected definitions.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Equation (2) states that a CSP is no-swap-regret if, for each j∈[n], ∑_{i∈[m]} φ_{ij}uL(i,j) ≥ ∑_{j∈[n]} max_{i*_j∈[m]} ∑_{i∈[m]} φ_{ij}uL(i*_j,j). This is not the correct no-swap-regret characterization: the left side is not summed over j, while the right side is, making the constraint impossible for typical payoffs. The correct condition is ∑_{i,j} φ_{ij}uL(i,j) ≥ ∑_i max_{i'} ∑_j φ_{ij}uL(i',j), which follows from the paper's own definition of no-swap-regret algorithms (max over swap functions π:[m]→[m]). Relatedly, Lemma 2.6 says the extreme points of M_NSR are x⊗y with x∈Δ_m and y∈BR_L(x), but the Stackelberg reinterpretation in the same section requires y∈Δ_n and x∈BR_L(y)—the roles are swapped. These two statements define the set M_NSR and its Stackelberg values v_i, and they are used directly in Lemma 3.1 and the LP (4) to prove Theorem 3.2. If a reader implements the manuscript as written, the LP constraints and the construction M=conv(M_NSR∪{ϕ_i}) may not correspond to valid no-regret menus. The intended statements are standard and likely correct from [ACS24], but the manuscript's formal text is internally inconsistent, so the central polynomial-time no-regret commitment result is not sound as written.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":27127,"tokens_out":18800,"duration_ms":166985,"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":[{"comment":"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":"Section 2.3, Eq. (2)"},{"comment":"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":"Section 2.4, Lemma 2.6"},{"comment":"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":"Section 4.3, Theorem 4.18"},{"comment":"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.","section":"Section 4.3, Algorithm 2"}],"minor_comments":[{"comment":"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":"Section 2.1"},{"comment":"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":"Section 3, proof of Theorem 3.2"},{"comment":"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":"Section 4.1, proof of Theorem 4.1"},{"comment":"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).","section":"Section 4.1, Theorem 4.8"},{"comment":"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":"Appendix B.4, Lemma B.2 proof"},{"comment":"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).","section":"Section 4.3, Theorem 4.17"}],"recommendation":"major_revision","confidential_remarks":"The paper relies heavily on the authors' own prior work [ACS24] for the menu characterization (Theorems 2.1, 2.3, 2.4, Lemma 2.5), without reproving it. Since that paper is published, this is acceptable, but the boundary between imported results and new results should be stated more explicitly; the internal inconsistencies in Section 2.3-2.4 make this boundary hard to audit. The main results are likely salvageable with local corrections, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the paper is the real deal: it gives the first efficient algorithms for optimal commitment to a learning algorithm against a distribution of opponent types, and the no-regret LP (4) is a clean resolution of the singleton-only gap left by earlier work. Second, there is a genuine typo/role-inversion bug in the formal definitions that needs to be fixed before the paper is sound as written. Eq. (2) is not the no-swap-regret condition: the left side is missing the sum over j, and the condition as written compares a column value to a sum over all columns. Lemma 2.6 has the BR_L arguments swapped; it should be y∈Δ_n and x∈BR_L(y), not x∈Δ_m and y∈BR_L(x). Those two statements are inconsistent with each other, and both feed into Lemma 3.1 and LP (4), so a reader implementing the manuscript literally would not be building the no-swap-regret menu. The intended statements are standard and almost certainly inherited correctly from ACS24, so my read is that this is a fixable presentation error, not a hidden counterexample to Theorem 3.2. But the authors need to rewrite that section and re-verify the LP constraints against the corrected definitions.\n\nWhat is genuinely new and good: the CSP-assignment view, the polytope characterization for no-regret commitment, the reduction of general commitment to approachability with separation oracles, and especially the abortable maximin algorithm in Section 4.3, which is clever and convincing—the idea of letting the opponent certify non-approachability is solid, and the proof of Theorem 4.17 checks out to me. The hardness reduction in Theorem 4.15 is also clean.\n\nSoft spots beyond the typo: Lemma 4.5's ball-radius WLOG is hand-waved; it is a minor technical issue. The paper leans heavily on ACS24 without reproving the menu characterization. That is acceptable because ACS24 is published, but a short appendix stating the exact statements would help. No code is provided, which is normal for a theory paper.\n\nBottom line: for researchers in learning in games and algorithmic Stackelberg commitment, this is a paper worth reading and citing. It deserves a serious referee. I would send it out with the clear expectation that the authors fix Eq. (2), Lemma 2.6, and the surrounding definitions before acceptance. If those are corrected, the central results stand.","headline":"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.","tokens_in":27674,"tokens_out":9606,"would_cite":true,"duration_ms":85807,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["algorithmic game theory","learning in games","menus","Stackelberg commitment","no-regret algorithms","no-swap-regret","Blackwell approachability","Bayesian Stackelberg problem"],"falsifier":"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.","tokens_in":26552,"feed_emoji":"🎯","tokens_out":6893,"duration_ms":67633,"temperature":0.7,"pith_summary":"This paper asks a commitment question: if a learner must repeatedly play an unknown strategic opponent drawn from a known distribution of types, what learning algorithm should they commit to? Its central finding is that for no-regret algorithms this choice can be made optimally in polynomial time: the optimal algorithm is the one whose menu of attainable correlated play solves a linear program. Without the no-regret constraint, the paper shows how to build an $\\varepsilon$-optimal menu in time polynomial in the game and support sizes whenever either is constant, and proves that exactly testing such menus is NP-hard in general. For the maximin objective it gives an algorithm that converges to the optimal worst-case per-round payoff in polynomial time per round without ever computing the optimal value. If these results hold, a learner can treat algorithm choice as a tractable menu-design problem rather than an intractable search over programs.","feed_headline":"No-regret play against unknown opponents is polynomial-time","feed_subtitle":"A menu LP finds the best algorithm to commit to; with no-regret dropped, near-optimal menus remain tractable.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the menu framework, the characterization of valid menus (Theorem 2.1), and the no-regret sandwich theorems (2.3-2.5) on which the entire reduction rests.","marker":"[ACS24]"},{"why":"Provides the exponential-in-dimension algorithm that decides approachability of a candidate set, and the NP-hardness of approachability used for the hardness reduction.","marker":"[MT09]"},{"why":"The original Blackwell approachability theorem underlies the menu-to-algorithm implementations and the separation-oracle reductions.","marker":"[Bla56]"},{"why":"Defines the Bayesian Stackelberg problem and gives the efficient Stackelberg computation used to compute the values $v_i$ inside the no-regret LP.","marker":"[CS06]"},{"why":"Anytime Hedge is the subroutine whose regret bound controls the deviation of the abortable maximin algorithm's running CSP from the candidate menu.","marker":"[FS96]"},{"why":"Provides an efficient no-swap-regret algorithm, the concrete fallback subroutine used to implement the base menu in Algorithm 1.","marker":"[BM07]"},{"why":"Prior solution for the singleton-type case (known opponent payoff) that the paper generalizes to a distribution over opponent types.","marker":"[ZT15]"}],"fun_headline_variants":["No-regret vs unknowns: poly-time optimal","Poly-time optimal play vs unknown opponents","Menu LP yields poly-time no-regret play","Unknown-opponent games: optimal play is poly-time","Tractable optimal no-regret play vs rivals"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["No-regret vs unknowns: poly-time optimal","Poly-time optimal play vs unknown opponents","Menu LP yields poly-time no-regret play","Unknown-opponent games: optimal play is poly-time","Tractable optimal no-regret play vs rivals"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001641,"raw_usage":{"total_tokens":6576,"prompt_tokens":1055,"completion_tokens":5521,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":671,"completion_tokens_details":{"reasoning_tokens":5450}},"tokens_in":671,"tokens_out":5521,"duration_ms":39141,"temperature":1.0,"reasoning_tokens":5450,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T04:50:34.617357+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}