{"id":"314619b5-4598-4662-a91a-66b87b52894b","arxiv_id":"2507.09928","paper_version":2,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":1,"one_line_summary":"A smoothed Frank-Wolfe algorithm with bandit feedback is shown to drive a generalized QRE gap to zero, but the gap function does not separate the true equilibrium from pure strategy profiles.","lead":"The paper proposes a decentralized, bandit-feedback learning algorithm for computing generalized quantal response equilibria, a bounded-rationality refinement of Nash equilibrium, and proves a finite-time convergence bound. The proof's convergence measure is flawed because it is zero at all pure strategy profiles, so the guarantee does not establish convergence to the intended equilibrium.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The gap function V is zero on all pure profiles, and since V is continuous and the exploration probability ε_t→0, the theorem's conclusion V(π(T))→0 cannot certify convergence to the GQRE.","rationale":"The reader's weakest assumption correctly identifies the gap function's zero set as the load-bearing issue. The paper's own Appendix B concedes V=0 on all pure profiles, and the proof of Theorem 3.1 uses V only as a Lyapunov function with negative drift proportional to V. Since the exploration parameter ε_t decays to zero, the domain of the iterates approaches the boundary of the simplex, where V vanishes without the profile being a GQRE. The theorem's conclusion V(π(T))→0 is therefore compatible with convergence to a pure non-equilibrium profile, so it does not substantiate the paper's claim of computing the GQRE. This is an internal gap in the proof, not a disagreement with community consensus. The paper does contain useful elements: the GQRE existence argument, the VI characterization, the verification lemma, and encouraging numerics. However, the central theoretical guarantee is not supported as stated. The reader's verdict of REJECT with moderate confidence is appropriate; the issue is potentially repairable by replacing V with a gap function that is positive and continuous away from the GQRE over the closure of the explored domain, or by proving a uniform lower bound on V outside a neighborhood of the GQRE, but neither is present. No separate concern about the C-smoothness sketch changes this assessment; the boundary zero-set alone is decisive.","tokens_in":25616,"tokens_out":5527,"duration_ms":71692,"concrete_test":"Run Algorithm 1 on a small strongly monotone game satisfying Assumptions 2.1 and 2.2, e.g., a 2×2 instance from Section 4's construction (µ=1, skew=0.3) with entropy regularizers, so the unique GQRE is fully mixed. Use the prescribed γ_t, ε_t, and M_t for T large (e.g., T=10^5) and record V(π_t), ||π_t − π_GQRE||, and min_{i,a} π_{i,t}(a). If V→0 while ||π_t − π_GQRE|| remains bounded away from 0 and min probability tends to 0, the theorem's conclusion is vacuous as a GQRE guarantee. An analytical companion check: because V is continuous and V(δ)=0 for every pure profile δ, exhibit a full-support sequence π^n→δ with V(π^n)→0; the drift bound in Appendix A contains no term depending on min_{i,a} π_{i,t}(a), so nothing in the proof excludes such a sequence from being followed by the algorithm.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 3.1 is stated as a convergence guarantee for computing the unique GQRE, but its conclusion is only R(T)=E[V(π_T)]→0. For that conclusion to imply convergence to the GQRE, V must be a valid distance-like certificate on the region visited by the algorithm. Appendix B proves V(π)>0 for non-GQRE π with full support, but explicitly notes that V is 0 for all pure strategy profiles. Since Lemma A.1 establishes that V is C-smooth (hence continuous), any sequence of full-support iterates tending to a pure profile has V→0, even if that pure profile is not the GQRE. The algorithm's iterates always satisfy π_{i,t}(a) ≥ ε_t, with ε_t = 1/((t+1) max_i |A_i|) → 0, so they are permitted to approach pure profiles. The drift inequality used in the proof, E[V(π_{t+1})|π_t] ≤ (1−γ_t)V(π_t)+O(γ_t^2), only forces V to decay; it contains no term that penalizes approach to the boundary, so it does not rule out V→0 along a sequence converging to a pure non-GQRE profile. The paper's assertion in Appendix B that 'the issue of the gap function being zero at pure strategy profiles doesn't cause trouble' is unsupported: no argument shows the dynamics cannot approach the boundary. Thus the central claim that Algorithm 1 converges to the GQRE is not established by the theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Generalized Quantal Response Equilibrium (GQRE), a generalized quantal response solution concept based on agent-specific strongly convex penalties, and shows existence, uniqueness under diagonal dominance, and a variational inequality characterization. It proposes a decentralized smoothed Frank–Wolfe algorithm with bandit feedback from a simulator oracle and proves a finite-time bound on a smoothed gap function (Theorem 3.1). Numerical experiments compare the method against several baselines on strongly monotone and low-rank games.","tokens_in":25854,"tokens_out":6449,"duration_ms":85108,"significance":"If the convergence claim were fully established, the paper would offer a useful contribution: a programmable framework for solution concepts with bounded rationality, a decentralized algorithm that works with noisy bandit feedback rather than exact gradients, and a finite-time analysis of a non-standard smoothed Frank–Wolfe scheme. The VI-based verification result (Lemma 2.2) and the simulation oracle treatment are also concrete and potentially reusable. The main obstacle is that the proved object, convergence of V(π_T) to zero, is not equivalent to convergence to the unique GQRE; the gap function is not a valid distance certificate on the closure of the algorithm's domain. Because the paper's central claim is exactly that Algorithm 1 'computes the GQRE,' this issue is load-bearing.","major_comments":[{"comment":"The assertion in Appendix B that 'the issue of the gap function being zero at pure strategy profiles doesn't cause trouble' is unsupported and is load-bearing for the main theorem. Lemma A.1 establishes that V is C-smooth, hence continuous, and V vanishes at every pure strategy profile. The algorithm's iterates are constrained to Δ(A_i, ε_t) with ε_t → 0, so they may approach pure profiles. Consequently, the conclusion lim_{T→∞} V(π(T)) = 0 in probability does not imply that π(T) converges to the unique GQRE; a sequence of iterates could approach a pure non-GQRE profile while V tends to zero. The drift inequality in the proof contains no term that penalizes approach to the boundary, so it does not rule this out. To sustain the claimed convergence to GQRE, the authors must either prove that pure non-GQRE profiles cannot be limit points of Algorithm 1, or replace V with a certificate that is positive on all non-GQRE profiles in the closure of the domain, or explicitly restate the theorem as convergence to the zero set of V rather than to the GQRE.","section":"Appendix B and Theorem 3.1"},{"comment":"The proof of C-smoothness of V is a sketch that does not provide the ingredients needed for the drift argument. The bound ∥∇V(π_1) − ∇V(π_2)∥ ≤ C∥π_1 − π_2∥ uses constants α_V, α_H, α_s, and c_0 that are not defined, and the claim that λ(π) is Lipschitz is stated as 'easily shown' without a derivation. Since the quadratic upper bound in equation (16) is used to control V(π(t+1)) − V(π(t)), the missing Lipschitz verification is part of the proof of Theorem 3.1. This section needs to be completed with explicit constants in terms of the game data and Assumptions 2.1–2.2.","section":"Appendix A, Lemma A.1"},{"comment":"The second-order expansion of the KL divergence near π_1 has an incorrect sign: for π̃_1(δ) = π_1 + δ(s_1 − π_1), the KL divergence is approximately (δ²/2) Σ_a (s_{1,a} − π_{1,a})² / π_{1,a}, not a negative quantity as written. The subsequent inequality '⟨·⟩ − ηKL ≈ δϵ − δ²η Σ ...' therefore does not follow as written. The conclusion that V_1(π) > 0 for small δ can still be recovered with a correct expansion because the linear term dominates for sufficiently small δ, but the proof needs correction.","section":"Appendix B, gap positivity proof"}],"minor_comments":[{"comment":"The phrase 'smoothened Franke-Wolfe' contains a typo; it should be 'Frank–Wolfe'.","section":"Section 1"},{"comment":"The theorem is called a 'no-regret guarantee,' but R(T) is the expected value of the gap function, not a regret with respect to a comparator sequence; the terminology should be clarified.","section":"Theorem 3.1 and Appendix A"},{"comment":"The claimed 'efficiency' should be qualified by the simulator sample complexity: with γ_t = 1/(t+1) and ε_t = 1/((t+1) max_i |A_i|), the choice M_t = ⌈1/(ε_t γ_t²)⌉ gives cumulative simulator uses of order Ω(T⁴), which is polynomial but very large for practical T.","section":"Section 3, after Algorithm 1"},{"comment":"The notation in the statement 'the gradient of KL(π̃|π_i) is 0 at π̃ = π_i' is informal; it should state that the first-order term in the KL divergence vanishes at that point, which is the actual argument being used.","section":"Appendix B, first paragraph"},{"comment":"The experimental comparison reports averages over 20 runs but gives no error bars or variance information, making it difficult to assess the claim of 'much more stable' performance.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The gap-function boundary problem is the central technical issue. If the authors cannot show that pure non-GQRE profiles are not limit points, or cannot modify the certificate so that it is positive on the closure of the domain, the paper's main claim of convergence to the GQRE will not be supportable. The remaining contributions (the solution concept, VI characterization, and algorithm design) are of interest, but the decision should depend on whether the convergence claim can be repaired with a sound proof."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a decent algorithmic paper with a real gap in the central guarantee. The GQRE concept is a special case of Allen and Rehbeck (2021), and the algorithm is in the family studied by Pena (2019), but the specific projection step and the non-asymptotic bandit analysis are genuinely new. The numerical work is broad and suggestive, and the authors are upfront about the concept not being novel. If the main theorem held, this would be a useful contribution to bounded-rationality learning.\n\nThe problem is that Theorem 3.1 claims convergence to the unique GQRE, but the proof only shows V(π_T) → 0 for a gap function V that is zero on all pure strategy profiles. Appendix B proves V(π) > 0 only for non-GQRE profiles with full support, and explicitly notes that V is zero at pure profiles. Since the algorithm's exploration level ε_t goes to zero, the iterates are allowed to approach the boundary, and the drift inequality has no term that penalizes movement toward the boundary. A sequence of full-support iterates can converge to a pure non-GQRE profile while V decays to zero. The paper's assertion that this \"doesn't cause trouble\" is not supported by any argument. That is load-bearing: the theorem's conclusion no longer certifies convergence to the intended equilibrium.\n\nThere are other, smaller weaknesses. The C-smoothness proof (Lemma A.1) is sketched; constants appear without derivation, and the Lipschitz bound for λ(π) is asserted rather than shown. The experiments have no code and no error bars, though the trends are consistent across many game classes.\n\nWho should read this: people working on decentralized learning for QRE-type equilibria, and those who study gap functions for smoothed Frank-Wolfe. The flaw looks repairable—either prove that the iterates stay uniformly away from pure profiles, or redefine the gap so that it is a distance certificate on the actual domain visited by the algorithm. But as written, the main claim overreaches. I would send it to a serious referee, not desk reject it, because the topic is relevant and the fix is plausibly within reach. My own verdict would be skeptical until the boundary issue is resolved.","headline":"The algorithm is a reasonable extension and the bandit analysis is new, but the main theorem does not establish convergence to GQRE because the gap function vanishes on pure profiles and the iterates may approach the boundary.","tokens_in":26466,"tokens_out":2462,"would_cite":false,"duration_ms":30729,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A10","91A26","49J40"],"pacs":[],"model":"deepseek-v4-flash","headline":"A decentralized learning rule provably drives a smoothed game gap to zero at rate O(log T/T), giving finite-time convergence to generalized quantal response equilibria.","keywords":["generalized quantal response equilibrium","bounded rationality","decentralized learning","smoothed Frank-Wolfe","bandit feedback","no-regret learning","variational inequality","smoothed gap function"],"falsifier":"Compute the unique GQRE of the strongly monotone $20 \\times 20$ game from Section 4 by solving its monotone variational inequality, then run Algorithm 1 with the paper's prescribed $\\gamma_t$, $\\epsilon_t$, and $M_t$ over many seeds, recording $V(\\pi_T)$ together with the $\\ell^1$ distance $\\|\\pi_T - \\pi^*\\|$ to that equilibrium. A single trajectory with tiny $V(\\pi_T)$ but $\\|\\pi_T - \\pi^*\\|$ bounded away from zero, for instance an iterate parked near a pure profile, would show the inference $V \\to 0 \\Rightarrow \\pi \\to \\mathrm{GQRE}$ is false. The closed-form version of the same test is to check whether $V$ has a positive lower bound on the exploration simplex $\\Delta(A_i, \\epsilon)$ outside a neighborhood of the GQRE; since the paper's own formula makes $V$ vanish at every pure point, any game with an interior GQRE has non-equilibrium points of that domain where $V = 0$.","tokens_in":25336,"feed_emoji":"🎲","tokens_out":17717,"duration_ms":169151,"temperature":0.7,"pith_summary":"The paper aims to make bounded-rational equilibria computable by independent agents. It defines the generalized quantal response equilibrium (GQRE), in which each player maximizes its expected payoff minus a player-specific convex penalty, and shows such equilibria exist and are unique under a strict diagonal-dominance condition by identifying them with Nash equilibria of a related concave game. The central claim is that a decentralized smoothed Frank-Wolfe algorithm, whose only information comes from a simulator that samples repeated plays, converges to the GQRE with finite-time guarantees: the expected smoothed gap satisfies $\\mathbb{E}[V(\\pi_T)] \\le C_7/T + C_6 \\log(T)/T$, and the gap vanishes in probability. If correct, this gives what the paper argues is the first finite-time guarantee for decentralized bandit-feedback computation of a quantal-response-style equilibrium in general-sum games, a regime where Nash equilibria are provably hard to learn.","feed_headline":"Provably learns bounded-rational equilibria from noisy play","feed_subtitle":"Agents using only their own noisy rewards converge to the quantal response equilibrium at rate O(log T/T).","key_machinery":"The load-bearing object is the smoothed gap function $V(\\pi)$, a regularized analogue of the Nash gap that serves as the Lyapunov function of the proof. For each player, $V_i(\\pi) = \\max_{s \\in \\Delta(A_i)} \\langle s - \\pi_i, \\nabla_{\\pi_i} u_i^{f_i}(\\pi)\\rangle - \\eta \\, \\mathrm{KL}(s, \\pi_i)$, which the Donsker-Varadhan variational formula evaluates in closed form as $\\eta \\log \\langle \\pi_i, \\exp(\\nabla u_i^{f_i}/\\eta)\\rangle - \\langle \\pi_i, \\nabla u_i^{f_i}\\rangle$, and it is zero exactly at the GQRE on fully mixed profiles. The update that makes the gap drift downward is the KL-smoothed Frank-Wolfe direction $s_i^*(\\pi) = \\arg\\max_{s} \\langle s, \\nabla u_i^{f_i}\\rangle - \\eta \\, \\mathrm{KL}(s, \\pi_i)$, a softmax over actions, followed by projection onto the $\\epsilon_t$-exploration simplex $\\Delta(A_i; \\epsilon_t)$ so every action keeps probability at least $\\epsilon_t$. The noise is controlled by taking $M_t = \\lceil 1/(\\epsilon_t \\gamma_t^2)\\rceil$ samples per step, which keeps the bandit gradient estimator, with variance of order $1/(M \\pi_i(a_i))$, commensurate with the step size $\\gamma_t = 1/(t+1)$.","core_discovery":"The core discovery is an equivalence that turns a behavioral equilibrium into a familiar object, plus an algorithm that exploits it. A GQRE of the original game is exactly a Nash equilibrium of the perturbed game with utilities $u_i^{f_i}(\\pi) = \\lambda_i u_i(\\pi) - f_i(\\pi_i)$, so existence and uniqueness follow from the classical theory of concave games, and the fixed-point definition acquires a variational-inequality characterization along with a polynomial-time verification test. The algorithmic content is the smoothed gap function $V(\\pi) = \\sum_{i}\\left[\\eta \\log\\langle \\pi_i, \\exp(\\nabla u_i^{f_i}/\\eta)\\rangle - \\langle \\pi_i, \\nabla u_i^{f_i}\\rangle\\right]$, a regularized Nash gap that is nonnegative and vanishes exactly at the GQRE on the interior of the strategy simplex. Theorem 3.1 shows that when agents update through the induced KL-smoothed best response, project onto a shrinking $\\epsilon_t$-exploration simplex, and draw $M_t = \\lceil 1/(\\epsilon_t \\gamma_t^2)\\rceil$ simulator samples per round to tame the unbounded variance of the payoff-gradient estimates, the expected gap obeys $\\mathbb{E}[V(\\pi_T)] \\le C_7/T + C_6 \\log(T)/T$ and $V(\\pi_T)$ tends to zero in probability.","pith_inferences":["The theorem as written concludes $V(\\pi_T) \\to 0$ in probability; because $V$ is identically zero on pure profiles, the stronger reading that the iterates converge to the unique GQRE needs an extra argument ruling out the boundary of the simplex, or a modified gap with an $\\epsilon$-dependent term that stays positive at distance from the GQRE even at pure profiles.","The $\\Omega(T^4)$ simulator budget is an artifact of setting $M_t \\sim 1/(\\epsilon_t \\gamma_t^2)$; variance-clipping importance weights or a gentler exploration schedule might reach the same rate with far fewer samples, which is a directly testable variant of the algorithm.","The Jordan three-player experiments indicate that when strict diagonal dominance fails, the smoothed Frank-Wolfe dynamics lose convergence for large $\\lambda$, paralleling known impossibility results for uncoupled gradient dynamics; this suggests Assumption 2.2 is close to necessary, though the paper does not prove a formal necessary condition.","Since the variational-inequality analysis is written for polytopal strategy spaces, the same machinery should transfer to polymatrix or coupling-constrained games; a natural next test is whether the smoothed gap retains its negative drift when $\\Delta(A_i)$ is replaced by a general polytope with a Bregman distance."],"forward_implications":["If Theorem 3.1 holds as stated, it supplies the first finite-time, decentralized, bandit-feedback algorithm for computing GQRE in general-sum games, with the total simulator budget growing only polynomially ($\\sum_{t=1}^T M_t = \\Omega(T^4)$).","The smoothed gap function is not tailored to this update: the paper argues it serves as a Lyapunov function for the broader family of generalized conditional-subgradient and mirror-descent schemes, so the $O(\\log T / T)$ rate carries over to previously proposed variance-handling variants for bandit games.","In matrix games, GQRE predictions become empirically testable where Nash is not: each agent needs only its own realized payoffs, so experimental subjects or software agents with no knowledge of the payoff matrix can be checked against the equilibrium the algorithm reaches.","The polynomial-time verification test gives agents a data-based stopping rule, since a strategy profile can be certified as an $\\epsilon$-GQRE by checking finitely many pure-action inequalities.","Because the regularizers $f_i$ are chosen per player, the same algorithm computes equilibria for heterogeneous behavioral types (entropy, R\\'enyi, squared-$\\ell^2$, and total-variation penalties), which the paper demonstrates numerically.","The proof of the no-regret bound uses a negative-drift argument on $V$, combined with Markov's inequality to turn the drift into a convergence-in-probability statement from the telescoping sum of step sizes."],"supporting_citations":[{"why":"Defines the logit quantal response equilibrium that GQRE generalizes and supplies the canonical KL-entropy example.","marker":"(McKelvey and Palfrey, 1995)"},{"why":"Supplies the existence and uniqueness theory for concave games via diagonal dominance, which Theorem 2.1 and Assumption 2.2 rest on directly.","marker":"(Rosen, 1965)"},{"why":"Provides the generalized conditional-subgradient and mirror-descent family that the smoothed Frank-Wolfe algorithm instantiates, giving the asymptotic noiseless-gradient convergence that the paper extends to finite time with bandit noise.","marker":"(Pena, 2019)"},{"why":"Source of the bandit-feedback setting with unbounded gradient-estimate variance; its uniform-mix variance-control scheme is a baseline that Theorem 3.1 also covers.","marker":"(Heliou et al., 2017)"},{"why":"Introduces the implicit-exploration variance-control trick (adding a constant to the denominator) that the paper cites as an alternative scheme covered by its analysis.","marker":"(Kocák et al., 2014)"},{"why":"Provides the monotone variational-inequality framework used in Lemma 2.1 to characterize GQRE and justify gradient-type computation.","marker":"(Facchinei and Pang, 2003)"},{"why":"Establishes the Lipschitz property of the softmax map used to bound the drift of the noisy smoothed best response in the proof of Theorem 3.1.","marker":"(Gao and Pavel, 2017)"},{"why":"Defines the three-player game where gradient-only dynamics provably fail to reach equilibrium, used in the numerics to probe behavior when Assumption 2.2 fails.","marker":"(Jordan, 1993)"},{"why":"Proposes the perturbed-utility equilibrium concept that subsumes GQRE and frames the divergence-based choice modeling in the paper.","marker":"(Allen and Rehbeck, 2021)"}],"fun_headline_variants":["Learning bounded-rational equilibria from noisy rewards","No-regret algorithm learns GQRE from bandit feedback","Smoothed gap function yields fast GQRE convergence","Bounded-rational equilibrium via decentralized learning","Bandit plays converge to GQRE at O(log T/T) rate"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that a vanishing smoothed gap forces the iterates to the GQRE: the paper proves $V(\\pi) > 0$ only at fully mixed non-equilibrium profiles, while $V$ is zero at every pure strategy profile, and the algorithm's iterates, confined to $\\Delta(A_i, \\epsilon_t)$ with $\\epsilon_t \\to 0$, range over profiles arbitrarily close to those boundary zeros; the paper's assertion that reaching a non-equilibrium pure profile does not cause trouble is stated but not proved.","fun_headline_variants_meta":{"raw":{"variants":["Learning bounded-rational equilibria from noisy rewards","No-regret algorithm learns GQRE from bandit feedback","Smoothed gap function yields fast GQRE convergence","Bounded-rational equilibrium via decentralized learning","Bandit plays converge to GQRE at O(log T/T) rate"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000648,"raw_usage":{"total_tokens":3015,"prompt_tokens":1022,"completion_tokens":1993,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":638,"completion_tokens_details":{"reasoning_tokens":1926}},"tokens_in":638,"tokens_out":1993,"duration_ms":18250,"temperature":1.0,"reasoning_tokens":1926,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:44:28.958234+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the unique GQRE of the strongly monotone $20 \\times 20$ game from Section 4 by solving its monotone variational inequality, then run Algorithm 1 with the paper's prescribed $\\gamma_t$, $\\epsilon_t$, and $M_t$ over many seeds, recording $V(\\pi_T)$ together with the $\\ell^1$ distance $\\|\\pi_T - \\pi^*\\|$ to that equilibrium. A single trajectory with tiny $V(\\pi_T)$ but $\\|\\pi_T - \\pi^*\\|$ bounded away from zero, for instance an iterate parked near a pure profile, would show the inference $V \\to 0 \\Rightarrow \\pi \\to \\mathrm{GQRE}$ is false. The closed-form version of the same test is to check whether $V$ has a positive lower bound on the exploration simplex $\\Delta(A_i, \\epsilon)$ outside a neighborhood of the GQRE; since the paper's own formula makes $V$ vanish at every pure point, any game with an interior GQRE has non-equilibrium points of that domain where $V = 0$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the existence and uniqueness theory for concave games via diagonal dominance, which Theorem 2.1 and Assumption 2.2 rest on directly."},{"cited_title":"and Pang, J.-S","cited_arxiv_id":null,"evidence_quote":"Provides the monotone variational-inequality framework used in Lemma 2.1 to characterize GQRE and justify gradient-type computation."}],"review_version":1}