- 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 of arm is determined by , where is known, is unknown, but the non-increasing order of 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
- The problem formulation is interesting and meaningful, regarding how to utilize extra structure information in K-armed bandits
- 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.
- 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."
- 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.
- 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.
- 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 and candidates in one decision? Do they model some real-world challenges? What does stand for? Could you explain the meaning of RR releases?
- 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.
- I have some questions regarding some words in the paper
- 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?
- 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.
- At the line 214, I want to confirm how to use Theorem 1 to calculate ? I think Theorem 1 only gives the formula of , do you mean and c are the same?
- In the algorithm 1, it is unclear on how to specify . In addition, algorithm specifies in the caption, does it mean there are different version of algorithms to handle the case ?
5 comments
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 of each arm and the batch size ; it does not know the survival probability , the chance that one candidate passes. One decision is one submission: the learner selects one arm, and the batch is candidates, with fixed by the application rather than chosen by the learner.
Only the released statistic comes back. A full-count channel releases the admitted count . An RR channel flips each admission bit with probability and then releases the count. An any-survivor channel releases only , 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 , and a third reports only whether any candidate passed.
is the distribution of when arm is selected and has survival probability (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 -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 , and the released statistic is the resulting count. A large means almost no flipping, and recovers the full count; gives , where the release is independent of the truth. The flipping can be undone, at a price: if a batch of releases the count , the unbiased estimate of is , so an error in the release is amplified by . At we get and an amplification of . Concretely, one batch of with gives a standard error of about on the estimate of , so the release carries essentially no information, while a full count over the same batch pins down to ; reaching that precision through RR takes about candidates, four hundred times the batch. The resulting information loss is reflected in , 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 enters it through .
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 , with the policy being the estimation, allocation and certification rule described in Section 3.3, and Figure 14 (p.26) depicts the interface. The "" in Algorithm 1's caption marks the case the theorem covers; there is only one version of COT.
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 is the number of selections of arm per , then , 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 , the number of admitted candidates. RR flips each admission bit and releases the resulting count, which is a single bit when . An any-survivor channel releases . A sampled-bit channel releases one randomly chosen admission bit.
Question 3(3) (computing from Theorem 1). and are different. is the optimal allocation, how often each arm should be selected per , and is the regret that this allocation costs. Theorem 1 gives for the left arm with the smallest regret-to-information ratio, , and otherwise; then . The two boundary cases follow the same rule with an absent side contributing zero: if there is no right term, and if or there is no left term. This is now stated right after Theorem 1 (p.5).
Question 3(4) (specifying , and the caption). and are fixed in advance, not learned. For a target , the proof of Corollary 2 gives a recipe: pick with , then with . This is an existence statement rather than a practical rule, since and are unknown; the four-arm experiments use one fixed and , that is . COT is defined for single-candidate count and RR releases, which is what refers to; for 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 guarantee.
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 Z is now O, and the admitted count previously written C is now S. 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: rk is a known utility scale, pk the unknown probability that a candidate from arm k is admitted, μk=rkpk the expected reward, Hk the release channel of arm k, O what is actually released. The auxiliary objects you asked about, t±, ai, b+ and η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 liminfB→∞Reg(B)/logB≥CH(p) for every uniformly efficient policy, and Appendix A.4 shows that COT satisfies
limsupB→∞logBRegCOT(B) ≤ (1+γ)CH(p)+1−KλλAγ(p).
Taking γ and then λ small gives CH(p)+δ for any δ>0. This holds under the conditions stated in Corollary 2: 1<s<K, t−<u, a unique minimizing left ratio, and known strict feasible points in the modes of P for fixed 0<ℓ<u<1. One qualification is now stated explicitly: the tuning is existential. The B→∞ recipe uses CH(p) and Aγ(p), which are not known to the learner, so it is not an implementable rule; the experiments therefore use one fixed (Kλ,γ)=(.10,.25) for every condition and do not tune per instance.
Weakness 3 (benchmarks). In the single-candidate experiments at B=100,000 under weak RR (ϵ2=.1), the mean regret is 1690.3±1073.5 for COT, 5405.8±1539.5 for Prefix-KL and 8729.2±225.5 for OSUB-KL, with 5403.1±422.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=.1, Prefix-KL ends at 105.0±6.6 against 9332.8±473.7 for Global KL, 8032.1±341.7 for OSUB-KL and 9401.6±491.9 for Ordered-KL. Here Prefix-KL follows the predicted source; this batched comparison evaluates routing, not an extension of COT's τ=1 asymptotic guarantee.