acceptodds
Under review as a conference paper at ICLR 2027

Exploration under Heterogeneous Feedback:Exact Geometry of Ordered Admission Bandits

Abstract

Efficient exploration depends on where informative feedback is available, not just which actions offer high utility. We study ordered admission bandits with increasing known utility scales, decreasing unknown survival probabilities, and a strictly unimodal product. Under heterogeneous feedback, the optimum's neighbors need not be the best exploration sources. We reduce the structured-bandit allocation program exactly to a left-prefix constraint and a right-neighbor constraint. The resulting closed form selects the left source by its regret-to-information ratio, recovering neighbor exploration under homogeneous releases and proving an unbounded penalty for enforcing locality under heterogeneous releases. For regular single-candidate count/randomized-response feedback, we develop Certified Oracle Tracking (COT) and prove that suitable fixed tunings approach the lower-bound constant arbitrarily closely. Experiments with 10, 20, and 50 arms demonstrate source migration and competition. On frozen real-data gates, changing only the release channel isolates the value of information location: COT reduces weak-feedback regret by 73.5% against a matched neighbor-oracle ablation, while their full-count trajectories coincide. These results characterize when exploration should move beyond neighbors and provide a certified policy for using that information.

Primary area:
learning theory
Keywords:
unimodal bandits, survival feedback, score-based sanitization, black-box attacks, information-theoretic regret bounds, feedback coarsening

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_5yHyOpenReview ↗
Rating
1
Confidence
2(+1)
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper works on K-armed bandits with extra knowledge in the reward structure. The mean reward μi\mu_i of arm ii is determined by μi=ripi\mu_i=r_ip_i, where 0<r1<r2<⋯<rK0<r_1<r_2<\cdots< r_K is known, 1>p1≥⋯≥pK>01>p_1\geq \cdots \geq p_K >0 is unknown, but the non-increasing order of pii∈[K]\\{p_i\\}_{i\in [K]} is assumed to be known. Targeted on the reward structure, this paper proposes a new algorithm COT with performance guarantee on the asymptotic regret, which is consistent with the asymptotic lower bound.

Critical strengths
  1. The problem formulation is interesting and meaningful, regarding how to utilize extra structure information in K-armed bandits
  2. The paper has provided sufficient numeric experiments to validate the performance of their proposed COT, which seems to be convincing.
Critical weaknesses

I am unfamiliar with the topic, and I find it hard to follow some of the notations and descriptions in the paper. Please rectify me if my understanding is incorrect.

  1. I believe the paper should improve the presentation, regarding motivation, problem formulation, definition of notations and summary of result. See the subsection "Questions For Authors."
  2. I am worried whether the theoretical contribution is sufficient. It seems the main theorems proved in the paper is asymptotic. And the tightness of Corollary 2 is unclear.
  3. It seems the numeric experiments mainly care about the performance of COT under different settings. I wonder whether it is possible to conduct more comparison between COT and other benchmark algorithms.
Questions for authors

Please forgive my stupidity if some of the questions are naive.

  1. Could you provide a real-world example of the problem setting? It is hard for me to follow the motivation of the problem setting. For example, why do we consider arm-dependent channel HkH_k and τ\tau candidates in one decision? Do they model some real-world challenges? What does Qk,pkHQ^H_{k,p_k} stand for? Could you explain the meaning of RR releases?
  2. Same as the question 1, could you provide the interaction dynamics between the agent and the environment, through a piece of pseudo-code? I think it will be helpful to clarify the problem formulation.
  3. I have some questions regarding some words in the paper
    1. At the line line 137, what is "allocation constraints"? I think there shouldn't be any constraint on the action that an general algorithm take. Do you mean for an algorithm with some performance guarantee, its action must fulfill some constraints? Or is there any requirement in the problem formulation?
    2. The sentence starts at line 142 contain three words, whose meaning is unclear to me. They are "full counts" "binary randomized response" "survivor bit". I am not sure what they refer to... I believe they should occur when presenting the interaction between the agent and the environment.
    3. At the line 214, I want to confirm how to use Theorem 1 to calculate c(p^)c(\hat{p})? I think Theorem 1 only gives the formula of CH(p)C_H(p), do you mean CHC_H​ and c are the same?
    4. In the algorithm 1, it is unclear on how to specify λ\lambda. In addition, algorithm specifies τ=1\tau=1 in the caption, does it mean there are different version of algorithms to handle the case τ≠1\tau\neq 1?
5 comments
AuthorsOpenReview ↗

Response to Reviewer 5yHy : weaknesses.

Thank you for the detailed reading and for the specific questions. One note on notation, since the line numbers you cite are those of the submitted version. To make Section 3.1 readable we restructured the exposition almost entirely, presenting the model in the order a reader meets it, and we aligned the symbols with the new text: the released statistic previously written ZZ is now OO, and the admitted count previously written CC is now SS. Both keep their meaning, and Table 1 (p.4) collects the notation of Sections 3-4.

Weakness 1 (presentation). The paper now opens with a concrete example (p.1-2) before any formalism. Section 3.1 (p.3) defines the model in the order a reader needs it: rkr_k is a known utility scale, pkp_k the unknown probability that a candidate from arm kk is admitted, μk=rkpk\mu_k=r_kp_k the expected reward, HkH_k the release channel of arm kk, OO what is actually released. The auxiliary objects you asked about, t±t_\pm, aia_i, b+b_+ and ηk\eta_k, are now defined where they first appear (p.4-5), and Equation (2) now names its constraint: it is what we call the allocation constraint.

Weakness 2 (theory and Corollary 2). The guarantee is asymptotic, as in most instance-dependent regret results. Beyond the guarantee, our exact two-constraint reduction identifies when non-neighbor exploration is preferable, and enforcing locality can incur an unbounded penalty. Corollary 2 (p.7) shows that COT can approach the lower-bound constant arbitrarily closely. Equation (2) gives lim inf⁡B→∞Reg(B)/log⁡B≥CH(p)\liminf_{B\to\infty}\mathrm{Reg}(B)/\log B\ge C_H(p) for every uniformly efficient policy, and Appendix A.4 shows that COT satisfies

lim sup⁡B→∞RegCOT(B)log⁡B ≤ (1+γ) CH(p)+λAγ(p)1−Kλ.\limsup_{B\to\infty}\frac{\mathrm{Reg}_{\mathrm{COT}}(B)}{\log B}\ \le\ (1+\gamma)\,C_H(p)+\frac{\lambda A_\gamma(p)}{1-K\lambda}.

Taking γ\gamma and then λ\lambda small gives CH(p)+δC_H(p)+\delta for any δ>0\delta>0. This holds under the conditions stated in Corollary 2: 1<s<K1<s<K, t−<ut_-<u, a unique minimizing left ratio, and known strict feasible points in the modes of P\mathcal P for fixed 0<ℓ<u<10<\ell<u<1. One qualification is now stated explicitly: the tuning is existential. The B→∞B\to\infty recipe uses CH(p)C_H(p) and Aγ(p)A_\gamma(p), which are not known to the learner, so it is not an implementable rule; the experiments therefore use one fixed (Kλ,γ)=(.10,.25)(K\lambda,\gamma)=(.10,.25) for every condition and do not tune per instance.

Weakness 3 (benchmarks). In the single-candidate experiments at B=100,000B=100{,}000 under weak RR (ϵ2=.1\epsilon_2=.1), the mean regret is 1690.3±1073.51690.3\pm1073.5 for COT, 5405.8±1539.55405.8\pm1539.5 for Prefix-KL and 8729.2±225.58729.2\pm225.5 for OSUB-KL, with 5403.1±422.85403.1\pm422.8 for COT-Local, the ablation that changes only the oracle's left source. In the batched setting at 100,000 candidates, Table 3 (p.22) adds two further baselines: at p1=.80,ϵ2=.1p_1=.80,\epsilon_2=.1, Prefix-KL ends at 105.0±6.6105.0\pm6.6 against 9332.8±473.79332.8\pm473.7 for Global KL, 8032.1±341.78032.1\pm341.7 for OSUB-KL and 9401.6±491.99401.6\pm491.9 for Ordered-KL. Here Prefix-KL follows the predicted source; this batched comparison evaluates routing, not an extension of COT's τ=1\tau=1 asymptotic guarantee.

AuthorsOpenReview ↗

Response to Reviewer 5yHy : questions 1 and 2

Question 1 (real-world example, channels, batches, RR)

The example is the one in the introduction (p.1-2), spelled out. A platform prepares a submission, and it can draw the candidates for that submission from several generators; one generator is one arm. A more ambitious generator produces a more valuable result, so one of its candidates is worth more when it passes the platform's hidden quality check, but it passes less often. The platform knows the arm order, the utility scale rkr_k of each arm and the batch size τ\tau; it does not know the survival probability pkp_k, the chance that one candidate passes. One decision is one submission: the learner selects one arm, and the batch is τ\tau candidates, with τ\tau fixed by the application rather than chosen by the learner.

Only the released statistic comes back. A full-count channel releases the admitted count SS. An RR channel flips each admission bit with probability βk\beta_k and then releases the count. An any-survivor channel releases only 1{S>0}\mathbf{1}\{S>0\}, and a sampled-bit channel releases one admission bit chosen at random. The learner knows which channel each arm uses and its privacy level, and it never sees the bits themselves. Channels may differ across arms, which is what Section 3.1 calls heterogeneous feedback; when all arms share one channel the feedback is homogeneous. In the example the generators sit with different parties, so the channel differs: an in-house generator reports the full count, a generator whose data sits with a partner can only be queried through RR at that partner's ϵk\epsilon_k, and a third reports only whether any candidate passed.

Qk,pHQ^H_{k,p} is the distribution of OO when arm kk is selected and has survival probability pp (Section 3.1, Table 1 p.4). It is the law of the only thing the learner ever sees, which is why the model is stated through it, and every divergence in the lower bound is a divergence between two such laws.

Randomized response is the standard mechanism for ϵk\epsilon_k-local differential privacy, and it is deployed practice rather than a toy: browsers and phone operating systems report this way. Each admission bit is flipped independently with probability βk=(1+eϵk)−1\beta_k=(1+e^{\epsilon_k})^{-1}, and the released statistic is the resulting count. A large ϵk\epsilon_k means almost no flipping, and ϵk→∞\epsilon_k\to\infty recovers the full count; ϵk→0\epsilon_k\to0 gives βk→1/2\beta_k\to1/2, where the release is independent of the truth. The flipping can be undone, at a price: if a batch of τ\tau releases the count S^\hat S, the unbiased estimate of pp is (S^/τ−βk)/(1−2βk)(\hat S/\tau-\beta_k)/(1-2\beta_k), so an error in the release is amplified by 1/(1−2βk)1/(1-2\beta_k). At ϵk=0.1\epsilon_k=0.1 we get βk≈0.475\beta_k\approx0.475 and an amplification of 2020. Concretely, one batch of τ=100\tau=100 with p=.3p=.3 gives a standard error of about 1.01.0 on the estimate of pp, so the release carries essentially no information, while a full count over the same batch pins pp down to ±.05\pm.05; reaching that precision through RR takes about 40,00040{,}000 candidates, four hundred times the batch. The resulting information loss is reflected in dk(p,q)=KL(Qk,pH ∥ Qk,qH)d_k(p,q)=\mathrm{KL}(Q^H_{k,p}\,\|\,Q^H_{k,q}), the divergence between released laws.

Arms therefore differ in the regret paid per sample and channels in the evidence returned per sample, so the arm worth probing next need not be the neighbor of the peak. Theorem 1 (p.5) makes the split explicit: the left source is the arm with the smallest regret-to-information ratio, and Qk,pHQ^H_{k,p} enters it through dkd_k.

Question 2 (interaction). At each decision:

for t = 1, 2, ...:
    k        <- policy(history)                # learner chooses a generator
    Y_{1:tau} ~ Bernoulli(p_k), i.i.d.         # the gate admits each candidate
    O        <- H_k(Y_{1:tau})                 # known channel, may differ by arm
    history  <- history + (k, O)               # learner never sees Y itself

Algorithm 1 (p.7) implements this loop for τ=1\tau=1, with the policy being the estimation, allocation and certification rule described in Section 3.3, and Figure 14 (p.26) depicts the interface. The "τ=1\tau=1" in Algorithm 1's caption marks the case the theorem covers; there is only one version of COT.

AuthorsOpenReview ↗

Response to Reviewer 5yHy : question 3

Question 3(1) ("allocation constraint"). Your second reading is the right one. The problem puts no restriction on the learner's actions. The constraint is a necessary condition that every uniformly efficient policy must meet in the long run: if ηk\eta_k is the number of selections of arm kk per log⁡B\log B, then inf⁡q∈Alt(p)∑k≠sηkdk(pk,qk)≥1\inf_{q\in\mathrm{Alt}(p)}\sum_{k\ne s}\eta_k d_k(p_k,q_k)\ge 1, that is, the sampling rates must collect enough information to rule out every alternative with a different optimal arm. The revised text says this explicitly at p.4: the constraint "does not restrict which arm the learner may choose at any single decision".

Question 3(2) ("full counts", "randomized response", "survivor bit"). These are release channels, now defined in Section 3.1 (p.3) before they are used. A full-count channel releases O=SO=S, the number of admitted candidates. RR flips each admission bit and releases the resulting count, which is a single bit when τ=1\tau=1. An any-survivor channel releases 1{S>0}\mathbf{1}\{S>0\}. A sampled-bit channel releases one randomly chosen admission bit.

Question 3(3) (computing cc from Theorem 1). cc and CHC_H are different. c(p)c(p) is the optimal allocation, how often each arm should be selected per log⁡B\log B, and CH(p)C_H(p) is the regret that this allocation costs. Theorem 1 gives ci⋆(p)=1/ai⋆c_{i^\star}(p)=1/a_{i^\star} for the left arm i⋆i^\star with the smallest regret-to-information ratio, cs+1(p)=1/b+c_{s+1}(p)=1/b_+, and ck(p)=0c_k(p)=0 otherwise; then CH(p)=τ∑kΔkck(p)C_H(p)=\tau\sum_k\Delta_k c_k(p). The two boundary cases follow the same rule with an absent side contributing zero: if s=Ks=K there is no right term, and if s=1s=1 or t−≥1t_-\ge 1 there is no left term. This is now stated right after Theorem 1 (p.5).

Question 3(4) (specifying λ\lambda, and the τ=1\tau=1 caption). λ∈(0,1/K)\lambda\in(0,1/K) and γ>0\gamma>0 are fixed in advance, not learned. For a target δ\delta, the proof of Corollary 2 gives a recipe: pick γ\gamma with γCH(p)<δ/2\gamma C_H(p)<\delta/2, then λ<1/K\lambda<1/K with λAγ(p)/(1−Kλ)<δ/2\lambda A_\gamma(p)/(1-K\lambda)<\delta/2. This is an existence statement rather than a practical rule, since CH(p)C_H(p) and Aγ(p)A_\gamma(p) are unknown; the four-arm experiments use one fixed λ=.025\lambda=.025 and γ=.25\gamma=.25, that is (Kλ,γ)=(.10,.25)(K\lambda,\gamma)=(.10,.25). COT is defined for single-candidate count and RR releases, which is what τ=1\tau=1 refers to; for τ>1\tau>1 the experiments use Prefix-KL, a finite-budget routing policy that carries no asymptotic claim. The geometry itself is unchanged by the batch: Section 4.2 checks it through 1,584 exact allocation computations, and Figure 2b shows COT's realised left-prefix share tracking the oracle's, so the batched experiments test the allocation rather than the τ=1\tau=1 guarantee.

Reviewer_jj9AOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This is an interesting bandit papers wherein the authors considered heterogeneous feedback. In particular, the authors studied ordered admission bandits with increasing known utility scales, decreasing unknown survival probabilities, and a strictly unimodal product.

The authors showed how to reduce the structured-bandit allocation program to a left-prefix constraint and a right-neighbor constraint.

The authors proposed an algorithm to select the left source by its regret-to-information ratio, as well as showing how to recover neighbor exploration under homogeneous releases, and proving an unbounded penalty for enforcing locality under heterogeneous releases.

For a special case of randomized feedback, authors proposed a Certified Oracle Tracking (COT), and proved that suitable fixed tunings approach the lower-bound constant arbitrarily close.

Critical strengths

Overall, this is a strong paper and I like the new information heterogeneous setting. I believe it will be interesting to the bandit community.

The analysis was elegant and even for the special case of randomized feedback, the derived results are useful.

Critical weaknesses

I think it will be interesting (and important) for the authors to show what are some practical scenarios for the heterogeneous feedback models are used.

Questions for authors

I think it will be interesting (and important) for the authors to show what are some practical scenarios for the heterogeneous feedback models are used.'

2 comments

Thank you for the positive review. The revision answers the practical-scenario question in three places.

First, the introduction (p.1-2) now opens with a concrete example. A platform can prepare a submission with several generators. A more ambitious generator gives a more valuable result but passes the platform's hidden quality check less often. What a test returns depends on the generator: an exact pass count, a count perturbed for privacy, or only whether anything passed. The channel therefore differs across arms, which is exactly the heterogeneous feedback we study, and it does so for an institutional rather than an artificial reason: each generator's data sits with a different holder, so each carries its own privacy budget ϵk\epsilon_k, and randomized response at ϵk\epsilon_k is what that holder is allowed to return.

Second, the same structure appears elsewhere: inspection lines report censored defect counts, so a monitor may see an exact count from one line and only a pass/fail flag from another; instruments measure the same quantity with different precision; and under ϵ\epsilon-local differential privacy, randomized response is the standard mechanism, so arms drawing on sources with different privacy budgets ϵk\epsilon_k have different channels.

Third, Section 4.3 (p.8) makes it concrete rather than illustrative. We build 60 frozen gates from four public datasets (Adult, Bank Marketing, Spambase, Phishing Websites), keep the candidate laws, utilities and gate fixed, and change only the release channel of one arm. Any difference in regret or in the oracle's source is then attributable to where the information sits.

Section 2 and the new Table 2 (p.20) also position the setting against the closest bandit models (OSSB and structure-adaptive bandits, corrupt bandits, threshold bandits, side observations).

Reviewer_jj9AOpenReview ↗

feedback on authors' rebuttal

Hi: i am ok with the authors' reply. I will keep my score.

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

Sadly the paper was impossible to read. It also had many undefined terms before they were used. It seems the authors thought that the setting is already known to the reader without introducing it. For example in equation (1) the Q terms are not introduced and they are also not typically defined in the literature. Terms like these need to be defined to make the work readable.

Critical strengths

Sadly the paper was impossible to read. It also had many undefined terms before they were used. It seems the authors thought that the setting is already known to the reader without introducing it. For example in equation (1) the Q terms are not introduced and they are also not typically defined in the literature. Terms like these need to be defined to make the work readable.

Critical weaknesses

Sadly the paper was impossible to read. It also had many undefined terms before they were used. It seems the authors thought that the setting is already known to the reader without introducing it. For example in equation (1) the Q terms are not introduced and they are also not typically defined in the literature. Terms like these need to be defined to make the work readable.

Questions for authors

Sadly the paper was impossible to read. It also had many undefined terms before they were used. It seems the authors thought that the setting is already known to the reader without introducing it. For example in equation (1) the Q terms are not introduced and they are also not typically defined in the literature. Terms like these need to be defined to make the work readable.

2 comments

Thank you for the careful reading. The revision restructures the presentation so that every symbol is defined before it is used, and the four changes listed below carry that through.

What the paper shows, in three sentences. In an ordered admission bandit, utility scales are known, survival probabilities are unknown, and each arm has a known release channel that may differ across arms. We reduce the allocation program exactly to a left-prefix and a right-neighbour constraint, which yields a closed form for where exploration should go: under homogeneous releases it sends budget to the neighbour, as in the classical picture, and under heterogeneous releases it need not, with a penalty that grows without bound when locality is enforced. For regular single-candidate count and randomized-response channels, COT with fixed tunings approaches the lower-bound constant.

The law of OO is stated in Section 3.1, in the sentence saying that a known, possibly arm-dependent channel HkH_k "releases O∼Qk,pkHO\sim Q^H_{k,p_k}". The revision states explicitly that the same object is also needed at a second value of the survival probability: dk(p,q)=KL(Qk,pH ∥ Qk,qH)d_k(p,q)=\mathrm{KL}(Q^H_{k,p}\,\|\,Q^H_{k,q}) is how much one selection of arm kk tells you when pp has to be told apart from another survival vector qq, and Alt(p)\mathrm{Alt}(p) collects the confusing alternatives, the survival vectors that change the optimal arm while producing the same release distribution at arm ss. It also defines four release mechanisms for OO, some of which coincide when τ=1\tau=1.

Changes in the revision (page and line numbers refer to the revised PDF):

  1. Section 3.1 (p.3, lines 129-160) now builds the model in reading order: arms and scales rkr_k, survival probabilities pkp_k, expected reward μk=rkpk\mu_k=r_kp_k, the admission bits Y1:τY_{1:\tau} and count SS, the release channel HkH_k, the released statistic OO, then Qk,pHQ^H_{k,p}, defined as "the distribution of OO when arm kk is selected and has survival probability pp", then the four channels before any of them is used.
  2. Equation (1) on p.3 now carries the regret, dk(p,q)d_k(p,q) and one sentence on what the divergence measures.
  3. Table 1 (p.4) now follows the sentence that explains Equation (1) rather than floating above it, and it collects the notation of Sections 3-4, including Qk,pHQ^H_{k,p}, dkd_k, t±t_\pm, aia_i, b+b_+, c(p)c(p), CH(p)C_H(p), λ\lambda and γ\gamma.
  4. The introduction now opens with a concrete example, a platform testing several generators behind one hidden quality gate, before any formalism.

On soundness, here is what can be checked directly. The released-law lower bound is Equation (2) with Appendix A.1. The exact two-constraint reduction is Theorem 1 with Appendix A.2. Near-attainment is Corollary 2 with Appendix A.4. Beyond the proofs, Appendix H (p.26) adds two numerical checks of the closed form: on each of four feedback conditions, a finite-grid LP over 50,684 competing instances returns an objective within 1.62% of the closed-form CH(p)C_H(p), and in 4.8 million paired decisions the closed form and a numerical LP selected the same arm at every step. If a specific step still looks unsupported after the revision, we will address it directly.

AuthorsOpenReview ↗

Follow-up on the revised presentation and soundness concerns.

We would appreciate your feedback on whether the revised PDF addresses your presentation concerns. In particular, Section 3.1 now introduces the model and release distributions before their use, and Table 1 collects the notation.

Since your review also raises soundness concerns, could you point us to any specific claim, assumption, or proof step that you still find technically problematic? We would like to distinguish any remaining exposition issues from substantive technical concerns and address both directly.

With the discussion period nearing its end, any specific points you could share would be particularly helpful while we still have time to respond. Thank you for your time and consideration.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.