{"id":"a39f46be-e0c7-4295-915b-c4c94d9b6e55","arxiv_id":"2505.05014","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"First sample-complexity bounds, up to a gap, for identifying non-redundancy of skew-symmetric games in dueling bandits.","lead":"This paper studies a dueling bandit problem for non-transitive games: from noisy pairwise comparisons, decide whether every move in a zero-sum game is used by rational players. It gives an algorithm and sample-complexity bounds expressed through a new matrix parameter φ(A), with a gap between upper and lower bounds.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Upper-bound proof applies Lemma 17 with a data-dependent threshold; the step in Theorem 10 is invalid.","rationale":"The paper's main constructive contribution is Algorithm 1 and Theorem 10. For the upper bound to hold, the data-dependent early-stopping conditions (a) and (b) must be justified. The proof's only justification is an appeal to Lemma 17 with ϵ set to a random variable. This is a genuine logical gap, not a mere omission: the random threshold is a function of the same averages whose concentration the lemma addresses, so the probability of {|Â−A|∞ < ϵ} conditional on stopping cannot be bounded by 1−δ. The reader's flagged Lemma 25 is also load-bearing for the finite-n lower bounds, but it is a finite symbolic computation and may be true; the early-stopping gap affects the central algorithm and would need a substantially different argument (e.g., uniform concentration or a fixed design) to repair. I therefore agree with the CONDITIONAL verdict, but I locate the weakest link in Theorem 10 rather than in Lemma 25. My read does not change the reader's verdict, since the paper remains promising but not yet verified.","tokens_in":20606,"tokens_out":19903,"duration_ms":194245,"concrete_test":"Re-derive the stopping time τ = inf{t : t > 2φ(Â_t)^2/π̂min(Â_t)^2 log(2n^2/δ)} and attempt to prove Lemma 17 for this data-dependent ϵ without fixing ϵ in advance. A decisive check is the scalar analogue: let X_i ~ N(0,1), μ̂_n = (1/n)ΣX_i, and define the stopping rule n > 2/(|μ̂_n|/2)^2 log(1/δ). In this analogue, P(|μ̂_n| < |μ̂_n|/2) = 0, showing that the conjunction 't large relative to the data-dependent threshold' does not imply the deviation is small. Applying the identical logical step to Algorithm 1's line 9 shows the theorem's proof does not follow from Lemma 17.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central upper bound (Theorem 10) rests on the correctness of early stops (a) and (b) in Algorithm 1 (lines 9–15). The proof states: 'If t > 2φ(Â)^2/π̂min^2 log(2n^2/δ) then max|aij − âij| < π̂min/φ(Â) by Lemma 17.' This is not a valid application of Lemma 17. Lemma 17 asserts that for a fixed ϵ > 0, once t ≥ (2/ϵ^2) log(2n^2/δ), the finite-sample deviation of the averages Â(t) from A is below ϵ with probability at least 1−δ. In Algorithm 1, the threshold ϵ = π̂min(Â)/φ(Â) is a function of the same empirical averages whose deviation the lemma is meant to bound. The stopping event and the deviation event are dependent, so the high-probability statement cannot be conditioned on the stopping rule. The same issue invalidates condition (b), which uses ϵ = α/φ(Â). Without (a)/(b), Lemmas 14 and 15 are never triggered with the required confidence, and the claimed sample-complexity bound O(U^2 / max{α^2, πmin^2} log(n/δ)) is unsupported. This is a proof gap in the paper's main positive result; it is more load-bearing than the also serious unproved Lemma 25, which affects only the lower-bound construction and is independently checkable for finitely many n.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper introduces a dueling-bandit formulation for deciding whether a zero-sum symmetric game with unknown skew-symmetric payoff matrix A in [-1,1]^{n x n} is non-redundant, i.e., whether every Nash equilibrium is completely mixed. By Kaplansky's theorem this is possible only for odd n. The main algorithmic contribution is Algorithm 1, an adaptive round-based sampler that estimates A from pairwise duels and stops either with a 'non-redundant' or an 'alpha-redundant' conclusion. Theorem 10 claims correctness with probability at least 1-delta and sample complexity O(U^2 / max{alpha^2, pi_min^2} log(n/delta)) under an assumed upper bound U on phi(A), where phi(A) measures the magnitude of entries of the inverse matrices A_j^{-1}. The lower-bound section constructs a parametric family Q(n,kappa,s) and proves, modulo an omitted rank lemma and computer-assisted cofactor bounds, an Omega(1/alpha^2 log(1/delta)) lower bound and, for n = 5,7,...,19, an Omega(phi(A)^2 log(1/delta)) lower bound.","tokens_in":20931,"tokens_out":6991,"duration_ms":70294,"significance":"If the central proof is repaired, the paper is a genuinely novel contribution: it is, to my knowledge, the first to study sample complexity of non-redundancy identification in nontransitive dueling bandits, and it identifies a problem-dependent parameter phi(A) that is natural in view of Kaplansky's determinant/Pfaffian characterization. The explicit lower-bound family Q(n,kappa,s) is a strength: it is a concrete instance family, and the paper correctly separates the phi(A)-dependence from the pi_min-dependence via Proposition 33. The authors also reference supplemental scripts for finite-n verification, which is a useful step toward reproducibility, although the text does not include the code or its output in a verifiable form.","major_comments":[{"comment":"The proof of Theorem 10 applies Lemma 17 at the data-dependent stopping times used in Algorithm 1, lines 9-15. Lemma 17 gives a high-probability deviation bound for a fixed epsilon and a fixed time t. In the algorithm, the thresholds epsilon = pi_hat_min / phi(A_hat) and epsilon = alpha / phi(A_hat) are functions of the same empirical averages whose deviation is being bounded, and the stopping event and the good-deviation event are dependent. Therefore the statement 'If t > 2phi(A_hat)^2 / pi_hat_min^2 log(2n^2/delta) then max|a_ij - a_hat_ij| < pi_hat_min / phi(A_hat) by Lemma 17' is not a valid application of the lemma. The same issue invalidates condition (b). Without a time-uniform confidence argument or an explicit union bound over a discretized grid of thresholds, Lemmas 14 and 15 are not triggered with the claimed confidence, and the central upper-bound guarantee in Theorem 10 is not established as written.","section":"Section 3.2, Theorem 10 and Lemma 17"},{"comment":"Lemma 25 states that rank(Q(n,kappa,s)) = n-1 unless s is in {0, 2kappa}, and the proof is omitted with the text 'the lemma is proved by some artificial and systematic elementary row operations, but it is quite lengthy and we omit the detail.' This lemma is load-bearing: Lemmas 24, and consequently Theorems 18 and 19, require Q+ and Q- to be valid instances satisfying Condition 1. If Lemma 25 is false for some n = 5,...,19, the lower-bound construction collapses. The supplemental script proof_sol.py is referenced, but it is not included in the manuscript text and cannot substitute for a proof or at least a fully machine-checked certificate covering the finitely many n used in the theorems. This gap must be closed before the lower bounds can be considered established.","section":"Section C.1, Lemma 25"},{"comment":"The proof of Proposition 32, which is essential for the phi(A)^2 lower bound, depends on Proposition 30 and Proposition 31. Proposition 30 gives only a proof sketch with a cofactor expansion claim stated without derivation, and Proposition 31 asserts a bound 'By our calculation with proof_cof.py' without presenting the symbolic expressions or the script output. These are not merely presentation details: they are the quantitative ingredients that turn the Omega(1/alpha^2) bound into Omega(phi(A)^2). For a journal publication, the authors should either provide complete proofs for these finite-n statements or include a reproducible symbolic computation with explicit verification conditions.","section":"Section C.4, Propositions 30 and 31"}],"minor_comments":[{"comment":"The abstract and the concluding remarks state the upper bound as O(phi(A)^2 / ...), while Theorem 10 requires a known U with phi(A) <= U and the algorithm's budget T uses U. These statements should be reconciled, since the proven bound is in terms of U, not directly in terms of phi(A).","section":"Abstract and Section 5"},{"comment":"Line 12 of Algorithm 2 says 'terminate Algorithm 1', but the algorithm being described is Algorithm 2; this is a typo that should be corrected.","section":"Algorithm 2, line 12"},{"comment":"Lemma 11 assumes max_{i,j} |b_ij - c_ij| <= epsilon, but the proof uses strict inequality at the step 'the hypothesis max|B_ij - C_ij| < epsilon'. The statement and proof should be made consistent.","section":"Lemma 11"},{"comment":"The proof of Lemma 17 writes the union bound as a sum over all i,j, while the algorithm samples only unordered pairs {i,j}; the displayed count binom(n,2) is correct, but the summation notation is misleading.","section":"Lemma 17"},{"comment":"There are several minor typographical errors, such as 'principle Pfaffians' for 'principal Pfaffians' and 'dual' for 'duel'; these should be corrected in a revision.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper has a plausible and interesting approach, and I do not see evidence of circularity or intentional obscurity. The main obstacle is that the upper-bound proof uses a fixed-time Hoeffding argument at a data-dependent stopping time, which is a genuine technical gap rather than a stylistic issue. The lower-bound construction is explicit, but the omitted rank lemma and the computer-assisted bounds need to be supplied in full. I would encourage the authors to revise with a proper time-uniform concentration argument; if that is done, the paper could be acceptable, but in its current form the central claims are not fully supported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe problem this paper introduces is genuinely new and worth knowing: in a dueling bandit with a skew-symmetric payoff matrix, decide whether the game is non-redundant, meaning every Nash equilibrium puts positive weight on every arm. That is a natural question for nontransitive relations, and as far as I can tell it has not been studied before. The paper also contains a genuinely nice construction. The lower-bound instance Q(n,κ,s) is a skew-symmetric matrix whose rank is n−1 except at two exceptional values of s, with φ(A) blowing up while πmin stays bounded away from zero. That construction is the strongest part of the work.\n\nThe main theorem, however, has a proof gap that is not cosmetic. In the proof of Theorem 10, the algorithm stops when t exceeds 2φ(Â)^2/π̂min^2 log(2n^2/δ), and the argument invokes Lemma 17 to claim that the empirical deviations are below π̂min/φ(Â). Lemma 17 is a fixed-sample Hoeffding bound for a fixed ε. Here ε is a function of the same empirical averages the bound is meant to control. The stopping time and the deviation event are dependent, so the advertised 1−δ guarantee is not established. The same problem appears in condition (b), where ε = α/φ(Â). As written, the upper bound O(U^2/max{α^2,πmin^2} log(n/δ)) is unsupported.\n\nThere are smaller issues. Lemma 25, which says the constructed matrix has rank n−1 except at s∈{0,2κ}, is stated without proof and deferred to a Python script that is not included. The lower bounds Theorems 18 and 19 rely on it; for finitely many n it is checkable, but it is still a hole. The abstract also overstates the result: the problem is really the α-redundancy relaxation, and the upper bound needs a known U bounding φ(A). Those are statement problems, not deep flaws. The related-work survey is accurate, and the use of Kaplansky's characterization to motivate the problem is appropriate.\n\nThe lower-bound argument for Ω(1/α^2) looks standard, and the Bretagnolle–Huber step is fine. If the stopping-time issue can be fixed, for instance by a union bound over a discretization of ε or by changing the stopping rule to use only the fixed U, the paper would be solid. As it stands, the main result is not proven.\n\nI would send it to a serious referee: the problem is new, the hard instance is worth preserving, and the gap seems fixable. But I would not cite the bounds in my own work until the proof is repaired.","headline":"New problem with a clever hard instance, but the main upper-bound proof applies a fixed-sample Hoeffding bound to a data-dependent stopping time, so the central theorem is not proven as written.","tokens_in":21456,"tokens_out":3226,"would_cite":false,"duration_ms":33860,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A05","68Q25","91A10"],"pacs":[],"model":"deepseek-v4-flash","headline":"For odd $n \\ge 5$, a dueling-bandit learner can identify whether a nontransitive game is non-redundant using $O(\\varphi(A)^2/\\max\\{\\alpha^2,\\pi_{\\min}^2\\}\\log(n/\\delta))$ duels, and for $n=5,\\ldots,19$ any algorithm needs…","keywords":["dueling bandits","non-transitive games","sample complexity","completely mixed games","Nash equilibrium support","skew-symmetric matrix","PAC identification","rock-paper-scissors"],"falsifier":"Symbolically compute the rank of $Q(n,\\kappa,s)$ for each odd $n = 5,7,\\ldots,19$ over the field of rational functions in $\\kappa$ and $s$; if the rank ever falls below $n-1$ for an $s$ outside $\\{0,2\\kappa\\}$, the hard pair $Q^+$ and $Q^-$ is not a valid non-redundant versus redundant pair, and the $\\Omega(\\varphi(A)^2)$ lower bound collapses. The paper's supplemental script checks only small $n$, so an independent exact computation would settle the unproved lemma.","tokens_in":20364,"feed_emoji":"🎲","tokens_out":16025,"duration_ms":141587,"temperature":0.7,"pith_summary":"This paper asks how many pairwise duel outcomes are needed to tell whether every move in a nontransitive win-lose relation is indispensable. For a skew-symmetric payoff matrix $A \\in [-1,1]^{n \\times n}$ with odd $n \\ge 5$, non-redundant means every Nash equilibrium puts positive probability on every move, while $\\alpha$-redundant means no equilibrium puts probability at least $\\alpha$ on all moves. The paper proves that an $(\\alpha,\\delta)$-PAC algorithm can make this decision using $O(\\varphi(A)^2 / \\max\\{\\alpha^2, \\pi_{\\min}^2\\} \\cdot \\log(n/\\delta))$ duels, where $\\pi_{\\min}$ is the smallest equilibrium probability and $\\varphi(A)$ grows as certain submatrices of $A$ approach singularity. It also proves lower bounds $\\Omega(\\alpha^{-2} \\log(1/\\delta))$ for every $n$ and $\\Omega(\\varphi(A)^2 \\log(1/\\delta))$ for $n = 5,7,\\ldots,19$, so the determinant-like factor is not an artifact of the algorithm. This matters because outside the three-move case nontransitive comparisons appear in real ranking and dice problems, and a test for useless moves is a step toward discarding them.","feed_headline":"Nontransitive games: how many duels prove no move is useless?","feed_subtitle":"An algorithm and matching lower bound set the sample cost of telling a game with all essential moves from an α-redundant one.","key_machinery":"The engine is the $\\epsilon$-Nash polytope $P_A(\\epsilon) = \\{x \\in S_n : x^\\top A \\ge -\\epsilon 1^\\top\\}$, where $S_n$ is the set of unit-sum vectors. Under the paper's rank condition, its vertices are $v_j^\\top = \\pi^\\top - \\epsilon(1^\\top A_j^{-1} - \\pi^\\top)$, with $A_j$ the matrix $A$ whose $j$-th column is replaced by all ones and $\\pi$ the unique equilibrium solving $\\pi^\\top A = 0^\\top$ with coordinate sum one. The decision problem becomes polytope inclusion: if $P_A(\\epsilon)$ is contained in the strictly positive orthant then the game is non-redundant, while missing the $\\alpha$-safe set $S^\\alpha_n$ certifies $\\alpha$-redundancy. The parameter $\\varphi(A) = \\max_{j,i} |(1^\\top A_j^{-1} - \\pi)_i|$ controls how fast this polytope deforms under perturbation, and Algorithm 1 stops exactly when Hoeffding concentration guarantees the estimated polytope cannot cross the true one.","core_discovery":"The central discovery is that non-redundancy of a nontransitive game is identifiable in the dueling-bandit model with a sample complexity governed by $\\varphi(A)$, the size of the entries of $1^\\top A_j^{-1} - \\pi^\\top$ where $A_j$ replaces column $j$ by the all-ones vector and $\\pi$ is the unique Nash equilibrium of $A$. For any odd $n \\ge 5$ satisfying the paper's Condition 1, Algorithm 1 estimates $A$ by dueling all pairs, computes an estimated equilibrium $\\hat\\pi$ from the estimated matrix $\\hat A$, and checks whether the $\\epsilon$-Nash polytope $\\hat P(\\epsilon)$ lies inside the positive orthant or stays away from the $\\alpha$-safe region. The paper proves all four stopping conclusions are correct once the estimation error is below thresholds set by $\\varphi$ and $\\pi_{\\min}$, giving the upper bound $O(\\varphi(A)^2 / \\max\\{\\alpha^2, \\pi_{\\min}^2\\} \\log(n/\\delta))$. For hardness, it constructs matrices $Q^+$ and $Q^-$ that agree everywhere except one entry, are respectively non-redundant and redundant, and have $\\varphi(Q) \\simeq (2n-8)/|s|$; separating them forces $\\Omega(1/\\alpha^2 \\log(1/\\delta))$ duels, and for $n=5,\\ldots,19$ the same construction yields $\\Omega(\\varphi(A)^2 \\log(1/\\delta))$ with the aid of computer-symbolic calculations.","pith_inferences":["The restriction of the $\\varphi(A)^2$ lower bound to $n \\le 19$ is most plausibly a by-product of computer verification, not a structural boundary; a proof of the omitted rank lemma for every odd $n$ would probably extend the same construction unchanged.","An adaptive sampling rule that spends duels only on pairs where the estimated polytope boundary is uncertain could close or narrow the gap between the upper and lower bounds; the authors list adaptive sampling as future work.","The hard pair $Q^\\pm$ differs in exactly one comparison, so the non-redundancy problem contains a two-hypothesis test in miniature; the same template may transfer to the related task of finding all indispensable moves, which the paper leaves open.","A practical consequence the authors do not spell out: when $\\varphi(A)$ is large, exact non-redundancy is expensive, and settling for an $\\alpha$-redundancy certificate can be cheaper by a factor of roughly $(\\varphi(A)/\\alpha)^2$."],"forward_implications":["For odd $n \\ge 5$, the identification problem is PAC-learnable in the dueling-bandit model: uniform all-pair dueling plus an $\\epsilon$-Nash-polytope check decides non-redundancy versus $\\alpha$-redundancy within the stated bound.","The lower bound $\\Omega(\\alpha^{-2} \\log(1/\\delta))$ applies to every $n$, so no reformulation can avoid paying more duels as the margin $\\alpha$ shrinks.","For $n = 5,7,\\ldots,19$, the lower bound $\\Omega(\\varphi(A)^2 \\log(1/\\delta))$ shows the cost is not determined merely by the smallest equilibrium probability; matrices with nearly singular column-replaced submatrices are intrinsically harder.","Because every even skew-symmetric matrix is redundant, the answer for even $n$ is decided immediately and all nontrivial cases are odd $n \\ge 5$.","For $n = 3$ the sample complexity is $\\Theta(\\Delta^{-2} \\log(1/\\delta))$ with $\\Delta = \\min\\{|a|,|b|,|c|\\}$, so the paper isolates the additional difficulty that appears for five or more moves."],"supporting_citations":[{"why":"Establishes that a skew-symmetric game is completely mixed exactly when its rank is n-1 and the null vector is strictly positive, the definition the paper tests.","marker":"[15]"},{"why":"Gives the principal-Pfaffian characterization and the explicit positive null vector that the algorithm estimates as the Nash equilibrium.","marker":"[16]"},{"why":"Supplies the dueling-bandit comparison model and the ε-Nash polytope technique that Algorithm 1 adapts.","marker":"[23]"},{"why":"Provides the sub-Gaussian concentration inequality used to turn duel counts into high-probability accuracy of the estimated matrix.","marker":"[36]"},{"why":"Supplies the change-of-measure lower-bound machinery used to prove the Ω(1/α² log(1/δ)) bound.","marker":"[17]"},{"why":"Gives the Bretagnolle–Huber inequality used in the alternative α-lower-bound argument.","marker":"[5]"},{"why":"Gives the normal KL-divergence formula used to compute the per-duel cost 2α² between the hard instances.","marker":"[33]"}],"fun_headline_variants":["How many duels prove no move is superfluous?","Sample cost to certify every move matters in dueling bandits","Rock-paper-scissors: duels to prove no throw is redundant","Dueling bandits: sample complexity of nonredundant games"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower-bound construction assumes that a specially designed payoff matrix, called Q(n,κ,s), has rank n-1 for every parameter value except two boundary values; the paper states this as an unproved lemma and defers to a supplemental computer script instead of giving a proof.","fun_headline_variants_meta":{"raw":{"variants":["How many duels prove no move is superfluous?","Sample cost to certify every move matters in dueling bandits","Rock-paper-scissors: duels to prove no throw is redundant","Dueling bandits: sample complexity of nonredundant games"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.0012,"raw_usage":{"total_tokens":5040,"prompt_tokens":1134,"completion_tokens":3906,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":750,"completion_tokens_details":{"reasoning_tokens":3831}},"tokens_in":750,"tokens_out":3906,"duration_ms":27681,"temperature":1.0,"reasoning_tokens":3831,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T23:16:49.713827+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Symbolically compute the rank of $Q(n,\\kappa,s)$ for each odd $n = 5,7,\\ldots,19$ over the field of rational functions in $\\kappa$ and $s$; if the rank ever falls below $n-1$ for an $s$ outside $\\{0,2\\kappa\\}$, the hard pair $Q^+$ and $Q^-$ is not a valid non-redundant versus redundant pair, and the $\\Omega(\\varphi(A)^2)$ lower bound collapses. The paper's supplemental script checks only small $n$, so an independent exact computation would settle the unproved lemma.","supporting_citations":[{"cited_title":"Kaplansky","cited_arxiv_id":null,"evidence_quote":"Establishes that a skew-symmetric game is completely mixed exactly when its rank is n-1 and the null vector is strictly positive, the definition the paper tests."},{"cited_title":"Kaplansky","cited_arxiv_id":null,"evidence_quote":"Gives the principal-Pfaffian characterization and the explicit positive null vector that the algorithm estimates as the Nash equilibrium."},{"cited_title":"Maiti, K","cited_arxiv_id":null,"evidence_quote":"Supplies the dueling-bandit comparison model and the ε-Nash polytope technique that Algorithm 1 adapts."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the sub-Gaussian concentration inequality used to turn duel counts into high-probability accuracy of the estimated matrix."},{"cited_title":"Kaufmann, O","cited_arxiv_id":null,"evidence_quote":"Supplies the change-of-measure lower-bound machinery used to prove the Ω(1/α² log(1/δ)) bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the normal KL-divergence formula used to compute the per-duel cost 2α² between the hard instances."}],"review_version":1}