- Rating
- 3
- Confidence
- 1
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper asks whether randomization actually helps when a learner makes a guess and receives a counterexample if it is wrong. The authors show that it can help when compared to a deterministic learner. They provide a few different settings in this paper.
When the answer can change in between rounds, they give an example where the feedback rule picks a new random starting point on a circle for each guess and reports the first error it finds. With this rule, it forces every deterministic learner use about queries , and another symmetric rule forces queries. On the other hand, for both examples, a randomized learner needs about 3 queries on average.
When the answer stays fixed, the worst-case deterministic querey cost is , even for a class with Littlestone dimension 1 and again randomized learners need at most 3.
The paper also shows that if feedback follows a fixed, known order, then a deterministic learner can finish in at most queries (where is Littlestone dimension).
Critical strengths
The COLT 2026 work asked two things: a) Is randomness needed against arbitrary symmetric adversaries, and b) is randomness needed for the case of order-induced adversaries. This paper answers the first part. Even for a very simple class (Littlestone dimension 1) and a fixed target, there is a symmetric feedback adversary that forces any deterministic learner to use queries, while a randomized learner needs at most 3. I followed this argument and it seems correct. I am not an expert in this area, but this seems like a meaningful contribution.
Critical weaknesses
For order-induced adversaries, the paper's query bound holds only when the target can change in between rounds. The fixed-target case, which is the main setting of the COLT paper (to my understanding at least), is left open, as the authors state. There are hints the answer there could be positive: with a fixed target, the cyclic rule needs at most 4 deterministic queries (Prop 4.5.), and random counterexamples which is a special case of order-induced adversaries (taken from the COLT paper), already have deterministic learners. So while the paper shows randomization is necessary for some symmetric adversaries, it remains unclear whether it is needed for the order-induced adversaries.
The main negative result for symmetric adversaries follows quickly from known results on tournament domination (Thm 4.3.). Most of the paper is spent on introducing many protocol variants and exact constants and not on this main question. The main text is dense, it uses many similar notations, and it gives little intuition, which made the claims hard for me to verify beyond the main arguments. For an ICLR audience, this limits both the accessibility and the perceived significance of the contribution.
Questions for authors
-
Do you have any evidence on if a deterministic learner can achieve constant queries for order-induced adversaries with a fixed target? This is the part of the COLT question left open.
-
The answer for symmetric adversaries follows quickly from known tournament results. Which results do you consider the main technical contribution of the paper, and what makes them difficult?
4 comments
A brief note before the discussion closes
Dear Reviewer Jkpu:
We are grateful for your review, and especially for the hints you pointed out on the fixed-target case.
The answer there is indeed positive, as your hints suggested. Both the cyclic rule and random counterexamples are special cases of Theorem 4.1 in the revised version we have uploaded: for every known order-induced adversary, a deterministic learner facing a fixed target needs an expected number of queries that grows only linearly with the Littlestone dimension. With this result, the open problem of Braverman et al. (COLT 2026) is now completely resolved. It also answers your first question in the affirmative: on every finite class of Littlestone dimension one, a constant expected number of queries suffices. We also tried to answer your second question, on the main technical contribution, as clearly as we could in our response.
If anything is unclear, or if other questions come up, we would be glad to hear from you.
With many thanks, and best regards.
Thank you for your response! Theorem 4.1 addresses my fixed-target concern. Although my second question is only partly addressed, I maintain my positive rating.
Thank you so much!
Dear Reviewer Jkpu:
Thank you very much for reading our response and the revised version, and for your continued support. The hints in your review on the fixed-target case encouraged us to develop our techniques further, check every proof line by line, and improve the writing.
Thank you for your time and support.
The fixed-target case and the complete resolution of the open problem
Thank you very much for the careful review, and for pointing to the fixed-target case, which is indeed the main setting of the COLT paper.
The revised version, now uploaded, completely resolves the open problem posed by Braverman et al. at COLT 2026.
It settles the fixed-target case left open in the submitted version, carries over all theorems of the submitted version with their proofs, and improves the presentation. The paper is now titled "Randomization in Learning from Symmetric Equivalence Queries"; the general response gives a result-by-result correspondence. Theorem and section numbers refer to the revised version unless we say otherwise.
1. Order-induced adversaries with a fixed target
As the review anticipated, the answer is positive. Theorem 4.1 gives a deterministic learner that uses at most 15128Ldim(H)+1 queries in expectation against every known order-induced generator, for every finite class and every fixed target; up to the constant this is optimal. It extends the deterministic learner for random counterexamples (Braverman et al., Section 3.1.1) to every known distribution of checking orders. On singleton classes it needs at most 143/15<10 queries for every n, not only for the cyclic rule mentioned in the review but for every known order mixture.
How the proof closes the question, in four steps:
The argument needs the target to stay fixed; under reselection, order mixtures behave differently (Section 5).
2. The presentation
We also agree that the main text of the submitted version was dense and gave too much space to protocol variants and exact constants. The revised main text follows the main question: an opening example (Figure 1), a phase diagram of all main results (Table 1), then the negative answer (Section 3), the positive answer (Section 4) and target reselection (Section 5). Exact constants and specialized variants are in the appendices, with a proof index and dependency diagrams in Appendix A.
Thank you again for this valuable feedback. We hope the revised version gives a much clearer picture, and we would be glad to clarify anything further.