- Rating
- 1
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
The paper studies best-arm identification with latent exponential-family rewards and fixed-threshold 1-bit observations. It combines estimation from the censored likelihood with gap-based exploration, and claims PAC correctness and upper and lower sample-complexity bounds involving a common instance-dependent hardness
Critical strengths
None. However I think the problem formulation, i.e., best-arm identification in generalized linear bandits with threshold binary feedback, is a worthwhile problem and a natural continuation of work on 1-bit estimation and bandits.
Critical weaknesses
- The main theoretical guarantees have substantial correctness problems. Proposition 5 is false as stated. Consider the scalar Gaussian model with , features , , unit variance, and thresholds . The arm means are and . Fix and , sample only arm 1 for pulls, where is the standard Gaussian CDF. Recommend arm 1 if the empirical fraction of bits equal to 1 is at most , and arm 2 otherwise. When , either arm is acceptable; otherwise, Hoeffding’s inequality bounds the error probability by . This gives a uniformly -PAC procedure. Now take , with . Then , while stays bounded away from zero and infinity. The claimed lower bound diverges as , although the procedure above uses a number of samples independent of . The proof also makes an invalid inference at Eq. (44): a lower bound on the total KL divergence does not imply the same lower bound on an individual arm’s contribution. Observations from different arms share information about .
The upper guarantees have separate problems. Lemma 8 uses asymptotic normality to assert finite-sample confidence probabilities and then takes a union bound over time. This does not establish the uniform confidence event needed for adaptive sampling and stopping. Eq. (57) also reverses the Rayleigh-quotient inequality: the correct direction is . The subsequent information-growth argument therefore does not follow.
- The algorithm and analysis do not match. Algorithm 3 determines sampling proportions through an feature-representation program. The appendix instead analyzes an allocation proportional to , calling it a “water-filling” allocation. No equivalence is established, so it is unclear why this analysis applies to Algorithm 3. These inconsistencies make the technical arguments difficult to follow.
Questions for authors
Can you reconcile Proposition 5 with the counterexample above, and explain how the PAC and upper-bound arguments can be repaired for the algorithm specified?
2 comments
Thank you for the response and for acknowledging the issues. The proposed changes withdraw the main complexity and optimality claims and replace the PAC analysis with a modified procedure under an additional observability assumption. I have not rigorously checked the replacement analysis, but even assuming it is correct, this substantially changes the central contribution. I do not find the remaining contribution sufficient for acceptance at ICLR, and I maintain my scores.
Proposition 5 and lower bound. You are right. Two errors caused this: an alternative where a competitor becomes ϵ-optimal need not invalidate the true best arm, and total KL divergence cannot be reduced to a single arm's contribution (Eq. 44) because the shared parameter θ links information across arms. We retract Proposition 5 and replace it with the standard observed-data change-of-measure lower bound: for any uniformly PAC algorithm on Θ with 0<δ<1/2 and a unique acceptable arm Aϵ(θ)={a∗},
Eθ[τ]≥supw∈ΔKinfλ∈Altϵ(θ)∑k=1Kwkdk(θ,λ)kl(1−δ,δ),
where Altϵ(θ)={λ∈Θ:a∗∈/Aϵ(λ)} and dk(θ,λ)=kl(pk(θ),pk(λ)) (with a weaker finite-confidence bound for multiple acceptable answers). This does not imply our submitted hardness expression or a matching upper bound.
Finite-sample PAC and multidimensional fixes. We agree asymptotic normality (even with a union bound) cannot justify Lemma 8, and our audit also found two d>1 errors: treating ∇2ϕ as a scalar rather than a matrix (Vi⊤Hie−Vj⊤Hje), and assuming a strictly positive minimum eigenvalue for each arm's rank-one censored covariance. We replace this analysis with a conservative guarantee under an explicit observability assumption: a known set S (s=∣S∣) and constant Lid<∞ satisfy ∣[ri−rj](θ)−[ri−rj](θ′)∣≤Lidmaxk∈S∣pk(θ)−pk(θ′)∣ (full rank of feature matrices alone is insufficient; we provide a sufficient Gaussian variance condition). Using time-uniform Bernoulli confidence sets Ct, forced exploration over S, and a deterministic cap τ≤T0=(s+1)n0, the modified procedure is (ϵ,δ)-PAC with finite unconditional expectation E[τ]≤(s+1)n0, bypassing both d>1 reductions.
Stopping-sign and information-matrix conventions. We replace
SelectGap's leader-minus-challenger expression (which tended toward the best-to-worst gap and prevented finite termination) with the direct challenger-minus-leader stopping certificate supθ∈Ctmaxj[rj(θ)−ra(θ)]<ϵ and consistent proof signs. We also include the missing expectation in Ik(θ)=−Eθ[∇2ℓk(θ;Gk)]=Eθ[∇ℓk(θ;Gk)∇ℓk(θ;Gk)⊤], and clarify that using expected Fisher information defines Fisher scoring rather than an exact Newton step in our estimator and optimization analysis.Spectral inequality and allocation mismatch. We retract the invalid reversed Rayleigh-quotient step in Eq. (57) (the valid inequality is λmin(Jj)≤∥vj∥22vj⊤Jjvj≤λmax(Jj) for vj=0). We also agree that Algorithm 3's ℓ1 representation program is not equivalent to the appendix's "water-filling" proportions, and for d>1 its constraint (∑kwkVk⊤∈Rm×d vs. zt∈Rm) requires reformulation. Consequently, we remove the unsupported bound and optimality claims for unchanged Algorithm 3, retaining only the conservative sample-complexity bound for our explicitly modified procedure.