acceptodds
Withdrawn from ICLR 2027

Best Arm Identification in Generalized Linear Bandits with 1-Bit Feedback

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

In many real-world applications such as IoT sensor networks, digital marketing, and clinical trials, decision-making often operates under strict 1-bit communication constraints and binary feedback (e.g., success/failure, click/no-click). Generalized Linear Models (GLMs) have been shown to be more efficient than linear models for binary data and are used effectively in contextual settings where decisions are driven by a multitude of high-dimensional variables. However, the existing literature on Best Arm Identification (BAI) in GLMs has focused almost exclusively on full-precision rewards, leaving a critical gap in communication-constrained settings. In this paper, we study Best Arm Identification in Generalized Linear Models with 1-bit observations, where the latent reward follows an exponential-family distribution but the learner observes only thresholded binary feedback. To the best of our knowledge, this is the first work to formulate and solve BAI in the 1-bit GLM setting. Our algorithm constructs confidence sets directly for the pairwise reward gaps between arms, formulated in terms of the feature matrices and an -dimensional parameter vector . Under standard regularity assumptions, we prove that the proposed algorithm is -PAC.

Primary area:
learning theory
Keywords:
generalized linear bandits, best-arm identification, 1-bit feedback, Fisher Information Matrix, exponential family

Reviews

Among:
Shape:
1234this paper, Bottom 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.00 over 3 reviews, above 0% of the others.
Reviewer_hKnnOpenReview ↗
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
  1. The main theoretical guarantees have substantial correctness problems. Proposition 5 is false as stated. Consider the scalar Gaussian model with θ∈[−1,1]\theta\in[-1,1], features V1=1V_1=1, V2=−1V_2=-1, unit variance, and thresholds γ1=γ2=0\gamma_1=\gamma_2=0. The arm means are θ\theta and −θ-\theta. Fix ϵ∈(0,1)\epsilon \in (0,1) and δ∈(0,0.15)\delta \in (0, 0.15), sample only arm 1 for n=⌈log⁡(1/δ)2(Φ(ϵ/2)−1/2)2⌉n=\left\lceil \frac{\log(1/\delta)} {2\bigl(\Phi(\epsilon/2)-1/2\bigr)^2} \right\rceil pulls, where Φ\Phi is the standard Gaussian CDF. Recommend arm 1 if the empirical fraction of bits equal to 1 is at most 1/21/2, and arm 2 otherwise. When ∣θ∣<ϵ/2|\theta|<\epsilon/2, either arm is acceptable; otherwise, Hoeffding’s inequality bounds the error probability by δ\delta. This gives a uniformly (ϵ,δ)(\epsilon,\delta)-PAC procedure. Now take θ=(ϵ+u)/2\theta=(\epsilon+u)/2, with u↓0u\downarrow 0. Then Δ2−ϵ=u\Delta_2-\epsilon=u, while C2=J2/4C_2=J_2/4 stays bounded away from zero and infinity. The claimed lower bound diverges as u−2u^{-2}, although the procedure above uses a number of samples independent of uu. 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 θ\theta.

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 λmin⁡(Jj)≤vj⊤Jjvj∥∣vj∥∣22\lambda_{\min}(J_j) \leq \frac{v_j^\top J_jv_j}{\||v_j\||_2^2}. The subsequent information-growth argument therefore does not follow.

  1. The algorithm and analysis do not match. Algorithm 3 determines sampling proportions through an ℓ1\ell_1 feature-representation program. The appendix instead analyzes an allocation proportional to 1/[(Δj−ϵ)2Cj]1/[(\Delta_j-\epsilon)^2C_j], 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

Proposition 5 and lower bound. You are right. Two errors caused this: an alternative where a competitor becomes ϵ\epsilon-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 θ\theta 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 Θ\Theta with 0<δ<1/20 < \delta < 1/2 and a unique acceptable arm Aϵ(θ)={a∗}\mathcal{A} _ {\epsilon}(\theta) = \{a^*\},

Eθ[τ]≥kl(1−δ,δ)sup⁡w∈ΔKinf⁡λ∈Altϵ(θ)∑k=1Kwkdk(θ,λ),\mathbb{E} _ {\theta}[\tau] \ge \frac{\mathrm{kl}(1-\delta, \delta)}{\sup _ {w \in \Delta _ K} \inf _ {\lambda \in \mathrm{Alt} _ {\epsilon}(\theta)} \sum _ {k=1}^K w _ k d _ k(\theta,\lambda)},

where Altϵ(θ)={λ∈Θ:a∗∉Aϵ(λ)}\mathrm{Alt} _ {\epsilon}(\theta) = \{\lambda \in \Theta : a^* \notin \mathcal{A} _ {\epsilon}(\lambda)\} and dk(θ,λ)=kl(pk(θ),pk(λ))d _ k(\theta,\lambda) = \mathrm{kl}(p _ k(\theta), p _ k(\lambda)) (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>1d > 1 errors: treating ∇2ϕ\nabla^2\phi as a scalar rather than a matrix (Vi⊤Hie−Vj⊤HjeV _ i^{\top} H _ i e - V _ j^{\top} H _ j e), 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 SS (s=∣S∣s=|S|) and constant Lid<∞L _ {\mathrm{id}} < \infty satisfy ∣[ri−rj](θ)−[ri−rj](θ′)∣≤Lidmax⁡k∈S∣pk(θ)−pk(θ′)∣\lvert \lbrack r _ i - r _ j \rbrack(\theta) - \lbrack r _ i - r _ j \rbrack(\theta^{\prime}) \rvert \le L _ {\mathrm{id}} \max _ {k \in S} \lvert p _ k(\theta) - p _ k(\theta^{\prime}) \rvert (full rank of feature matrices alone is insufficient; we provide a sufficient Gaussian variance condition). Using time-uniform Bernoulli confidence sets CtC_t, forced exploration over SS, and a deterministic cap τ≤T0=(s+1)n0\tau \le T_0 = (s+1)n_0, the modified procedure is (ϵ,δ)(\epsilon,\delta)-PAC with finite unconditional expectation E[τ]≤(s+1)n0\mathbb{E}[\tau] \le (s+1)n_0, bypassing both d>1d > 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⁡θ∈Ctmax⁡j[rj(θ)−ra(θ)]<ϵ\sup _ {\theta \in C _ t} \max _ j [r _ j(\theta) - r _ a(\theta)] < \epsilon and consistent proof signs. We also include the missing expectation in Ik(θ)=−Eθ[∇2ℓk(θ;Gk)]=Eθ[∇ℓk(θ;Gk)∇ℓk(θ;Gk)⊤]I _ k(\theta) = -\mathbb{E} _ {\theta}[\nabla^2 \ell _ k(\theta; G _ k)] = \mathbb{E} _ {\theta}[\nabla \ell _ k(\theta; G _ k)\nabla \ell _ k(\theta; G _ k)^{\top}], 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⊤Jjvj∥vj∥22≤λmax⁡(Jj)\lambda _ {\min}(J _ j) \le \frac{v _ j^{\top} J _ j v _ j}{\|v _ j\| _ 2^2} \le \lambda _ {\max}(J _ j) for vj≠0v _ j \ne 0). We also agree that Algorithm 3's ℓ1\ell _ 1 representation program is not equivalent to the appendix's "water-filling" proportions, and for d>1d > 1 its constraint (∑kwkVk⊤∈Rm×d\sum _ k w _ k V _ k^{\top} \in \mathbb{R}^{m \times d} vs. zt∈Rmz _ t \in \mathbb{R}^m) 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.

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.

Reviewer_LSr4OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies best-arm identification in generalized linear bandits under 1-bit feedback, where the latent reward follows an exponential-family distribution but the learner observes only thresholded binary feedback. The proposed algorithm, 1BIT-GLGAPE, constructs confidence sets for pairwise reward gaps and uses a tracking-based sampling strategy informed by the censored Fisher information matrix. While the problem is relevant, the methodological novelty relative to existing work on gap-based best-arm identification in generalized linear bandits, particularly Kazerouni etal 2021, needs to be more clearly established. The lower-bound analysis explicitly builds on the change-of-measure framework of Kaufmann et al. 2016, and it would be helpful to clarify which aspects of the algorithm and theoretical analysis constitute substantive advances beyond these established techniques.

Critical strengths

The paper studies best-arm identification under 1-bit feedback in generalized linear bandits, where the learner must identify the best arm based on latent rewards despite observing only thresholded binary outcomes. This is a meaningful problem because quantization limits the information available for decision-making, and the paper explicitly connects this limitation to the information retained in the censored Fisher information matrix which may also be independently important.

Critical weaknesses

The proposed algorithm builds on established ideas in best-arm identification, particularly gap-based exploration in generalized linear bandits (Kazerouni and Wein, 2021), while its lower-bound analysis explicitly adopts the change-of-measure framework of Kaufmann et al. (2016). Although the paper incorporates censored Fisher information to account for 1-bit feedback, it does not sufficiently establish how its algorithmic and theoretical contributions advance beyond these existing techniques. This makes the significance of the claimed contributions difficult to assess.

Questions for authors
  1. See weaknesses part, could the authors elaborate on the significant technical challenges faced during the analysis.

  2. Theorem 4 establishes finite-time termination only on the high-probability good event (\mathcal E), with (\Pr(\mathcal E)\ge 1-\delta), but does not establish almost-sure termination on the complementary event. This distinction appears consequential for Theorem 6, which claims an upper bound on the unconditional expected stopping time (\mathbb E[\tau]). Could the authors clarify whether the algorithm terminates almost surely and, if so, provide a proof that also accounts for trajectories on (\mathcal E^c)? If termination is established only on the good event, how is the unconditional expected sample-complexity bound in Theorem 6 justified?

  3. More experiments on real world scenarios are essential.

  4. The experiments report the standalone performance of 1BIT-GLGAPE without comparisons to existing methods. Could the authors compare against suitable baselines, such as adapted gap-based sampling or alternative arm-allocation strategies under the same 1-bit feedback setting, to demonstrate the benefits of the proposed method?

1 comment

Q1: Technical contribution and novelty. We agree that gap-based exploration, tracking, and change of measure are established tools. The observed one-bit Fisher information also follows from the standard conditional-score identity, so that identity alone is not a new theoretical contribution. The model-specific issue is that the information retained by censoring must resolve latent reward-gap directions. The proposed revised emphasis is therefore the relationship between latent gap identification, fixed-threshold information loss, and admissible experimental designs. The present proof problems prevent us from claiming the originally stated theoretical advance. The conservative replacement provides a narrower guarantee, not an instance-optimality result or a new general design principle.

Q2: Almost-sure termination and unconditional expectation. You are right that bounding τ\tau on a high-probability event E\mathcal{E} does not control E[τ1Ec]\mathbb{E}[\tau \mathbf{1}_{\mathcal{E}^c}]. To fix this, our modified procedure enforces an explicit deterministic budget cap τ≤T0=(s+1)n0\tau \le T_0 = (s+1)n_0 across all trajectories (including when confidence sets are empty). On the simultaneous confidence event, θ∗\theta^* remains in every confidence set and the PAC guarantee holds. This repairs the unconditional bound E[τ]≤T0\mathbb{E}[\tau] \le T_0 for the modified procedure, rather than salvaging the original uncapped algorithm.

Q3: Real-world evaluation. We agree that real-world claims require empirical validation, which could not be completed for this draft (and would require continuous responses, a known censoring mechanism, latent mean ground truth, and misspecification analysis). We will revise the text to present sensor networks, marketing, and clinical trials strictly as motivating scenarios rather than demonstrated applications.

Q4: Baselines and current experiments. We agree that omitting baselines is unjustified—controlled comparisons under a fixed observation model and valid stopping certificate should evaluate uniform, ℓ1\ell_1, and censored-information allocations alongside a full-feedback baseline.

The current Bernoulli experiments are a special case: thresholding can merely relabel the original binary reward, so suitable direct-feedback GLM or logistic BAI baselines may apply. They do not demonstrate the loss incurred by censoring a continuous reward. A focused additional experiment would use Gaussian latent rewards and vary threshold offsets and feature conditioning, reporting both sample counts and empirical error rates, including any capped runs. No such new results are claimed here. Consequently, the current experiments do not establish empirical superiority of the proposed allocation.

Reviewer_foXMOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

The authors consider generalized linear bandit models with a twist; the rewards are only observed through arm-specific threshold channels. More specifically, the observation is binary either 1 or 0 based on wether the reward of the selected arm kk is above a threshold γk\gamma_k. This is referred to as the 1 Bit constraint. They focus on the pure exploration task where the objective is to identify an ϵ\epsilon-optimal arm with respect to the true mean with probability 1−δ1-\delta where δ\delta is a confidence level. First they derive a lower bound on the expected sample complexity which exhibits a scaling in a hardness constant Hϵ(θ⋆,γ)\mathcal{H}_{\epsilon}(\theta^\star, \gamma) (See Proposition 5). Then they propose a gap-elimination style algorithm, which does not exactly match this lower bound but exhibits a dependence on this constant (See Theorem 6). They further complement their finding with numerical results.

Critical strengths
  1. The setting seems to be interesting with what appears to be a useful and new structure.

  2. The authors do provide a sample complexity lower bound under this structure characterizing the hardness of the problem.

  3. The authors propose an elimination style algorithm with a provable instance-dependent guarantee. This guarantee does not show optimality in view of the provided lower bound.

Critical weaknesses
  1. The literature review is a bit weak and could benefit from an exhaustive survey.

  2. In theorem 6, the authors present an upper bound exhibiting a dependence on the hardness constant Hϵ(θ⋆,γ)\mathcal{H}_{\epsilon}(\theta^\star, \gamma) and a dependence on log⁡(1/δ)2\log(1/\delta)^2 as well as other problem dependent constants.

  3. I suspect the lower bound might have some mistakes, eq (31) is not justified. See my questions below.

  4. The authors do not discuss how sub-optimal their result with regards to their lower bound. For instance how bad is the dependence in λ1\lambda_1, one should not expect this in the upper bound first term, but only in the second order term (terms not involving log⁡(1/δ)\log(1/\delta)). This may be due to a loose analysis or perhaps a fundamental challenge. The authors should carefully discuss this. Worst case dependencies on KK, dd, mm and spectral properties of the design matrix constructed from VkV_k, must be discussed.

  5. The upper and lower bounds are not matching.

  6. The idea of using elimination as a design principle is not completely novel. The design principle is well understood. It is not clear what are the key challenges or new insights uncovered when applying this principle in this bandit setting.

Questions for authors
  1. Why is the proposed model better then a Bernoulli bandit model? There you also only observe either 1 or 0 per arm. You can also consider a Bernoulli model with some structure. Some discussion is needed to help clarify the existing gaps in the literature.

  2. The derived lower bound is a bit obscure. How does this depend on the problem dimension in the worst case? For instance in linear bandits with gaussian rewards, it is well know that the worst case bound depends on the dimension over gap. (see Lemma 2 in https://arxiv.org/abs/1409.6110)

  3. When deriving lower bounds for epsilon-best arm identification, there are usually overlapping hypothesis to consider, how do you handle this? The inequality (31) only applies if the chosen events are disjoint. I don't believe this is true in this setting. This needs careful derivations for overlapping hypothesis especially when dealing with epsilon-optimality. (see https://arxiv.org/abs/1905.03495 and https://arxiv.org/abs/2202.06280). In line 684 mentions "if δ<1.5\delta<1.5", I don't get this as it is always true that δ∈(0,1)\delta \in (0,1).

  4. Are γk\gamma_k known to the learner?

  5. Line 834 seem to have a broken reference to a Lemma. Which Lemma do you refer to here?

  6. How do the upper bounds scale in the worst case?

2 comments

Thank you for the insightful review. Following your feedback, we retract our optimality claims, restrict our lower bound to unique-answer instances, and replace the flawed upper-bound proof with a conservative finite-sample bound for a modified procedure.

Q1: Relation to structured Bernoulli bandits. The observed process is a structured Bernoulli model; our contribution rests neither on binary feedback alone (studied in logistic bandits, e.g., Kazerouni & Wein, 2021; Jun et al., 2021; E.Ochoa Rivera et al., 2025) nor on a new general BAI principle beyond existing frameworks (Degenne et al., 2019; Degenne & Koolen, 2019). The distinction is the decision criterion: maximizing the latent mean rk(θ)=xk⊤θr_k(\theta)=x_k^\top\theta rather than pk(θ)=Φ((γk−xk⊤θ)/σ)p_k(\theta)=\Phi((\gamma_k-x_k^\top\theta)/\sigma). With arm-dependent γk\gamma_k, ranking pk(θ)p_k(\theta) need not rank rk(θ)r_k(\theta) (and reverses it under a common threshold). Our revised scope focuses on analyzing this specific censoring mechanism and its observability restrictions.

Q2: Dimension dependence of the lower bound. Take K=mK=m, Yk∼N(θk,1)Y_k\sim\mathcal{N}(\theta_k,1), threshold 00, and θ=(Δ,0,…,0)\theta=(\Delta,0,\dots,0) (Δ>ϵ\Delta>\epsilon), so arm 11 is uniquely acceptable. Perturbing θj→Δ+ϵ+η\theta_j\to\Delta+\epsilon+\eta (η↓0\eta\downarrow 0) for each j≥2j\ge 2 makes arm 11 unacceptable. Change of measure yields Eθ[τ]≥(m−1) kl(1−δ,δ)kl(1/2,Φ(−Δ−ϵ)).\mathbb{E}_\theta[\tau]\ge \frac{(m-1)\,\mathrm{kl}(1-\delta,\delta)}{\mathrm{kl}(1/2,\Phi(-\Delta-\epsilon))}. Using kl(1/2,Φ(−x))=x2/π+O(x4)\mathrm{kl}(1/2,\Phi(-x))=x^2/\pi+O(x^4) and Δ=2ϵ\Delta=2\epsilon gives Ω(mϵ−2log⁡(1/δ))\Omega(m\epsilon^{-2}\log(1/\delta)) for small ϵ,δ\epsilon,\delta. This establishes dimension-linear hard instances (consistent with Soare et al., 2014) without claiming worst-case optimality.

Q3: Overlapping hypotheses and confidence range. We agree Eq. (31) requires an event with small probability under the alternative, which fails when alternatives have multiple acceptable answers. We now restrict the replacement lower bound to instances with a unique acceptable answer (noting general multiple-answer cases require tools like Garivier & Kaufmann, 2019; Degenne & Koolen, 2019, while Al Marjani et al., 2022 target identifying all ϵ\epsilon-optimal arms). Finally, "δ<1.5\delta<1.5" was a typo for (0,0.15)(0,0.15)—which does not save the original proposition—and our replacement bound holds for 0<δ<1/20<\delta<1/2.

Q4–Q5: Known thresholds and broken reference. Yes, each γk\gamma_k is fixed and known beforehand (adaptive thresholds are outside our scope). Line 834 intended to cite Lemma 9 (gap concentration). However, we agree an empirical gap involving the time-dependent leader iti_t cannot be equated with Δk\Delta_k unless it=a∗i_t=a^*, so fixing the reference alone does not repair the upper bound.

Q6: Worst-case upper bound and comparison to the lower bound. We do not claim λ1−1\lambda_1^{-1} or log⁡2(1/δ)\log^2(1/\delta) are fundamental. For an explicitly modified procedure, we prove a conservative bound E[τ]≤(s+1)n0\mathbb{E}[\tau]\le(s+1)n_0 (with n0=min⁡{n≥1:β(q,δ)≤ϵ4Lid for every integer q≥n}n_0 = \min\{n \ge 1 : \beta(q,\delta) \le \frac{\epsilon}{4 L_{\mathrm{id}}} \text{ for every integer } q \ge n\}; s=∣S∣s=|S|), scaling as O((s+1)(1+Id2ϵ2)[log⁡Kδ+log⁡(1+Lidϵ)]).O\left((s+1)\left(1+\frac{I_d^2}{\epsilon^2}\right)\left[\log\frac{K}{\delta}+\log\left(1+\frac{L_{id}}{\epsilon}\right)\right]\right). Dimension and design enter through SS and LidL_{id} (made explicit for a Gaussian example; a dimension-only bound requires controlling threshold saturation and design degeneracy).

Sorry, in Q6, the equal is:

\left[\log\frac K\delta+\log\left(1+\frac{L_{id}}{\epsilon}\right)\right]\right)$$.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.