Pith. sign in

REVIEW 3 major objections 5 minor 43 references

Sample Complexity of Identifying the Nonredundancy of Nontransitive Games in Dueling Bandits

T0 review · 3 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2505.05014 v1 pith:AMAXBM74 submitted 2025-05-08 cs.GT

Shang Lu , Shuji Kijima This is my paper · ORCID
classification cs.GT MSC 91A0568Q2591A10
keywords duelingbanditsnon-transitivegamessamplecomplexitycompletelymixedNashequilibriumsupportskew-symmetricmatrixPACidentificationrock-paper-scissors
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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$.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

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.

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 (3)
  1. [Section 3.2, Theorem 10 and Lemma 17] 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.
  2. [Section C.1, Lemma 25] 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.
  3. [Section C.4, Propositions 30 and 31] 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.
minor comments (5)
  1. [Abstract and Section 5] 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).
  2. [Algorithm 2, line 12] 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.
  3. [Lemma 11] 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.
  4. [Lemma 17] 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.
  5. [Throughout] There are several minor typographical errors, such as 'principle Pfaffians' for 'principal Pfaffians' and 'dual' for 'duel'; these should be corrected in a revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: parameters and lower-bound instances are explicit; flagged proof gaps are correctness issues, not definitional circularity.

full rationale

The paper's derivation is not circular. The central identification algorithm estimates A and tests conditions on π̂, φ(Â), and the є-Nash polytope; α, U, πmin, and φ(A) are inputs or explicit instance parameters, and no fitted quantity is renamed as a prediction. The lower bound uses an explicit pair Q(n,κ,±α); the Ω(φ(A)^2) claim follows from an explicit bound φ(Q) ≤ (4n²+1)/(3|s|), not from a self-referential definition. The only self-citation, [22], is an introductory example and is not load-bearing. Flagged as non-circular correctness gaps: (i) Proof of Theorem 10 applies Lemma 17 with data-dependent thresholds є=π̂min/φ(Â) and є=α/φ(Â); Lemma 17 is stated for fixed є, so the stopping event and concentration event are dependent. (ii) Section C.1, Lemma 25 is asserted with 'we omit the detail' and deferred to proof_sol.py; absent that lemma, the n=5,...,19 lower-bound instances may not satisfy Condition 1. (iii) The abstract claims O(φ(A)^2) while Theorem 10 assumes a known U with φ(A)≤U. These are proof-completeness and statement gaps, not equivalence of the conclusion to the input by construction.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The derivation rests on Kaplansky's characterization of completely mixed symmetric games, the input restrictions in Conditions 1 and 2, and several computer-assisted algebraic claims about the lower-bound construction Q(n,κ,s). The most fragile items are Lemma 25 and Propositions 30/31, which are not fully proved in the text and depend on unshipped scripts.

free parameters (2)
  • U (upper bound on φ(A))
    Algorithm 1 is stated with T depending on U and the theorem assumes φ(A) ≤ U. The abstract reports the bound as O(φ(A)^2...), which requires U to be a tight known estimate; otherwise the sample complexity is O(U^2...). This hidden dependence is a free assumption.
  • α (redundancy margin)
    Introduced to define α-redundancy; the algorithm only separates non-redundant from α-redundant, so exact identification is relaxed. It appears in both upper and lower bounds.
assumptions (5)
  • standard math Kaplansky's characterization of completely mixed skew-symmetric matrices (Theorems 1 and 2)
    Used to characterize non-redundant matrices and to reduce the problem to checking rank and the sign pattern of principal Pfaffians (cited from [15,16]).
  • domain assumption Condition 1: A is skew-symmetric, rank(A) = n−1, and the null vector has nonzero sum
    Restricts the input class so that A_j is nonsingular (Lemma 7); the algorithm is undefined outside this class. The paper argues random matrices satisfy it with probability tending to 1.
  • domain assumption Condition 2: duel outcomes are 1-sub-Gaussian with mean a_ij and mutually independent
    Standard stochastic bandit model; powers the Hoeffding-based confidence bound (Lemma 17).
  • ad hoc to paper Lemma 25: rank(Q(n,κ,s)) = n−1 unless s ∈ {0, 2κ}
    Unproved statement used to make Q+ and Q− valid non-redundant/redundant instances for the lower bounds. The text says the proof is omitted and defers to a script for small n.
  • ad hoc to paper Propositions 30 and 31: determinant and cofactor bounds for Q(n,κ,s)
    Established by 'proof sketch' or 'by our calculation with proof_cof.py', needed for the φ(Q) upper bound in Proposition 32 and hence for Theorem 19.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Sample Complexity of Identifying the Nonredundancy of Nontransitive Games in Dueling Bandits." pith.science (2026). https://pith.science/paper/AMAXBM74

@misc{pith2026250505014,
  author       = {Pith},
  title        = {Pith review of: Sample Complexity of Identifying the Nonredundancy of Nontransitive Games in Dueling Bandits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/AMAXBM74}},
  note         = {Machine review of arXiv:2505.05014}
}
abstract

Dueling bandit is a variant of the Multi-armed bandit to learn the binary relation by comparisons. Most work on the dueling bandit has targeted transitive relations, that is, totally/partially ordered sets, or assumed at least the existence of a champion such as Condorcet winner and Copeland winner. This work develops an analysis of dueling bandits for non-transitive relations. Jan-ken (a.k.a. rock-paper-scissors) is a typical example of a non-transitive relation. It is known that a rational player chooses one of three items uniformly at random, which is known to be Nash equilibrium in game theory. Interestingly, any variant of Jan-ken with four items (e.g., rock, paper, scissors, and well) contains at least one useless item, which is never selected by a rational player. This work investigates a dueling bandit problem to identify whether all $n$ items are indispensable in a given win-lose relation. Then, we provide upper and lower bounds of the sample complexity of the identification problem in terms of the determinant of $A$ and a solution of $\mathbf{x}^{\top} A = \mathbf{0}^{\top}$ where $A$ is an $n \times n$ pay-off matrix that every duel follows.

Figures

Figures reproduced from arXiv: 2505.05014 by the authors.

Figure 1
Figure 1. Examples of nontransitive win-lose relation. [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

43 extracted references · 39 canonical work pages

  1. [1]

    Ailon, Z

    N. Ailon, Z. Karnin, and T. Joachims. Reducing dueling bandits to cardinal bandits. In Proceedings of the 31st International Conference on Machine Learning , volume 32, pages 856–864, 2014

    work page 2014

  2. [2]

    Audibert, S

    J. Audibert, S. Bubeck, and R. Munos. Best arm identification in multi-armed bandits. In Proceedings of the 23rd Annual Conference on Learning Theory, pages 41–53, 2010

    work page 2010

  3. [3]

    P. Auer. Using confidence bounds for exploitation-exploration trade-offs. Journal of Machine Learning Research, 3:397–422, 2002

    work page 2002

  4. [4]

    Bubeck and N

    S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends® in Machine Learning, 5(1):1–122, 2012

    work page 2012

  5. [5]

    C. L. Canonne. A short note on an inequality between KL and TV, 2023. URL https: //arxiv.org/abs/2202.07198

    arXiv 2023

  6. [6]

    L. Carlitz. Representations by skew forms in a finite field. Archiv der Mathematik, 5:19–31, 1954

    work page 1954

  7. [7]

    Dudík, K

    M. Dudík, K. Hofmann, R. E. Schapire, A. Slivkins, and M. Zoghi. Contextual dueling bandits. In Proceedings of The 28th Conference on Learning Theory, volume 40, pages 563–587, 2015

    work page 2015

  8. [8]

    Even-Dar, S

    E. Even-Dar, S. Mannor, and Y . Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 7(39):1079–1105, 2006

    2006

Show all 43 references
  1. [9]

    Fulman and L

    J. Fulman and L. Goldstein. Stein’s method and the rank distribution of random matrices over finite fields. The Annals of Probability, 43(3):1274 – 1314, 2015

    2015

  2. [10]

    M. Gardner. Mathematical games. Scientific American, 231(4):120–125, 1974

    1974

  3. [11]

    Garivier and O

    A. Garivier and O. Cappé. The KL-UCB algorithm for bounded stochastic bandits and beyond. In Proceedings of the the 24th Annual Conference on Learning Theory , volume 19, pages 359–376, 2011

    2011

  4. [12]

    Garivier and E

    A. Garivier and E. Kaufmann. Optimal best arm identification with fixed confidence. In Proceedings of the 29th Annual Conference on Learning Theory, volume 49, pages 998–1027, 2016

    2016

  5. [13]

    S. Ito, H. Luo, T. Tsuchiya, and Y . Wu. Instance-dependent regret bounds for learning two-player zero-sum games with bandit feedback, 2025. URL https://arxiv.org/abs/2502.17625

    2025 arXiv

  6. [14]

    Jamieson and R

    K. Jamieson and R. Nowak. Best-arm identification algorithms for multi-armed bandits in the fixed confidence setting. In Proceedings of the 48th Annual Conference on Information Sciences and Systems, pages 1–6, 2014

    2014

  7. [15]

    Kaplansky

    I. Kaplansky. A contribution to von Neumann’s theory of games. Annals of Mathematics, 46(3): 474–479, 1945. 10

    1945

  8. [16]

    Kaplansky

    I. Kaplansky. A contribution to von Neumann’s theory of games. II. Linear Algebra and its Applications, 226:371–373, 1995

    1995

  9. [17]

    Kaufmann, O

    E. Kaufmann, O. Cappé, and A. Garivier. On the complexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17(1):1–42, 2016

    2016

  10. [18]

    D. Kim, R. Kim, W. Lee, Y . Lim, and Y . So. Balanced nontransitive dice: Existence and probability. The Electronic Journal of Combinatorics, pages 1–21, 2024

    2024

  11. [19]

    Komiyama, J

    J. Komiyama, J. Honda, H. Kashima, and H. Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In Proceedings of the 32nd International Conference on Machine Learning, volume 40, pages 1141–1154, 2015

    2015

  12. [20]

    Komiyama, J

    J. Komiyama, J. Honda, and H. Nakagawa. Copeland dueling bandit problem: Regret lower bound, optimal algorithm, and computationally efficient algorithm. In Proceedings of the 33rd International Conference on Machine Learning, volume 48, pages 1235–1244, 2016

    2016

  13. [21]

    Lai and H

    T. Lai and H. Robbins. Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 6(1):4–22, 1985

    1985

  14. [22]

    Lu and S

    S. Lu and S. Kijima. Is there a strongest die in a set of dice with the same mean pips? Proceedings of the AAAI Conference on Artificial Intelligence, 36(5):5133–5140, 2022

    2022

  15. [23]

    Maiti, K

    A. Maiti, K. Jamieson, and L. Ratliff. Instance-dependent sample complexity bounds for zero-sum matrix games. In Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, volume 206, pages 9429–9469, 2023

    2023

  16. [24]

    Maiti, K

    A. Maiti, K. Jamieson, and L. J. Ratliff. Logarithmic regret for matrix games against an adversary with noisy bandit feedback, 2023. URL https://arxiv.org/abs/2306.13233

    2023 arXiv

  17. [25]

    Maiti, R

    A. Maiti, R. Boczar, K. Jamieson, and L. Ratliff. Near-optimal pure exploration in matrix games: A generalization of stochastic bandits & dueling bandits. In Proceedings of the 27th International Conference on Artificial Intelligence and Statistics, volume 238, pages 2602–2610, 2024

    2024

  18. [26]

    Mannor and J

    S. Mannor and J. N. Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. Journal of Machine Learning Research, 5:623–648, 2004

    2004

  19. [27]

    Matousek and B

    J. Matousek and B. Gärtner. Understanding and Using Linear Programming. Springer Berlin Heidelberg, 2006

    2006

  20. [28]

    H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527 – 535, 1952

    1952

  21. [29]

    C. M. Rump. Strategies for rolling the efron dice. Mathematics Magazine, 74(3):212–216, 2001

    2001

  22. [30]

    R. P. Savage. The paradox of nontransitive dice. The American Mathematical Monthly, 101(5): 429–436, 1994

    1994

  23. [31]

    Schaefer

    A. Schaefer. Balanced non-transitive dice II: Tournaments, 2017. URL https://arxiv.org/ abs/1706.08986

    2017 arXiv

  24. [32]

    Schaefer and J

    A. Schaefer and J. Schweig. Balanced nontransitive dice. The College Mathematics Journal, 48 (1):10–16, 2017

    2017

  25. [33]

    J. Soch. Proof: Kullback-leibler divergence for the normal distribution. URL https:// statproofbook.github.io/P/norm-kl.html

  26. [34]

    Urvoy, F

    T. Urvoy, F. Clerot, R. Féraud, and S. Naamane. Generic exploration and K-armed voting bandits. In S. Dasgupta and D. McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28, pages 91–99, 2013

    2013

  27. [35]

    von Neumann and O

    J. von Neumann and O. Morgenstern. Theory of games and economic behavior . Princeton university press, 1944. 11

    1944

  28. [36]

    M. J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint . Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019

    2019

  29. [37]

    Yue and T

    Y . Yue and T. Joachims. Interactively optimizing information retrieval systems as a dueling bandits problem. In Proceedings of the 26th International Conference on Machine Learning, pages 1201–1208, 2009

    2009

  30. [38]

    Y . Yue, J. Broder, R. Kleinberg, and T. Joachims. Thek-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538–1556, 2012

    2012

  31. [39]

    Y . Zhou, J. Li, and J. Zhu. Identify the Nash equilibrium in static games with random payoffs. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 4160–4169, 2017

    2017

  32. [40]

    Zoghi, S

    M. Zoghi, S. Whiteson, R. Munos, and M. Rijke. Relative upper confidence bound for the k-armed dueling bandit problem. In Proceedings of the 31st International Conference on Machine Learning, volume 32, pages 10–18, 2014

    2014

  33. [41]

    Zoghi, Z

    M. Zoghi, Z. S. Karnin, S. Whiteson, and M. de Rijke. Copeland dueling bandits. InProceedings of the 29th International Conference on Neural Information Processing Systems, volume 28, pages 307–315, 2015. 12 A Supplemental Proofs of Section 2 A.1 Proof of Proposition 4 Proof o...

    2015

  34. [42]

    A is non-redundant

    (8) and by Theorem 3 of Carlitz [6] (cf [9]), the number of matrices of rank 2r is given by S(q,n, 2r) =qr(r−1) Q2r−1 i=0 (qn−i− 1)Qr i=1(q2i− 1) . (9) In particular, whenn is odd, the maximal possible rank isn− 1, and asymptotically (asq→∞ ), the probability that a random ske...

  35. [43]

    = det(Qo n) = (n− 4)s κ + 4 and det(Qo n+1 2 ) = (n− 4) s κ 2 + 2(n− 6)s κ + 8. On condition that |s| κ ≤ 1 n, it is not difficult to see that| det(Qo 1)| = | det(Qo n)|≥|− 1 + 4| = 3 and| det(Qo n+1 2 )|≥| 0− 2 + 8| = 6, which implies the claim for k = 1, n+1 2 andn. Consider...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.