acceptodds
Under review as a conference paper at ICLR 2027

Counterfactual Updates for Conformal Retrieval with Semi-Bandit Feedback

Abstract

Conformal retrieval constructs document sets at a prescribed coverage rate. Under semi-bandit feedback, a successful retrieval reveals the correct document, while a miss reveals only its absence. Existing conservative threshold methods provide guarantees for smooth coverage objectives, leaving the discrete number of returned documents unresolved. Coverage protection also changes the feedback used to learn the threshold. We propose counterfactual updates that recover whether the original proposed set would have contained the correct document. Whenever another miss would exceed the cumulative miss budget, the method returns the full candidate pool and uses the revealed document to evaluate the original proposal. Assuming every candidate pool contains the correct document, this preserves the unprotected learner's threshold trajectory and guarantees cumulative coverage after every query. For i.i.d. queries with fixed scores, a unique continuous target quantile and continuity of expected document cost at that quantile, average returned-set size converges to the best feasible fixed-threshold cost. In contrast, updating from protected hits keeps the threshold at or below its initial value and requires full-pool returns on a positive fraction of queries when initialized below the target quantile. The decreasing-step-size learner tracks that quantile directly, while conservative estimation certifies a threshold through a distributional bound. In the initial ten-order SQuAD comparison, our method returns 2.64 documents per query versus 9.44 for conservative threshold estimation. Protection adds about 0.09 documents per query relative to the same unprotected learner with identical step sizes, while maintaining at least 90% cumulative coverage after every query. With unchanged parameters, evaluation on Natural Questions also produces smaller sets than the compared conservative and constant-step methods. These results show that learning from the original proposal supports efficient retrieval with cumulative coverage protection.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
online conformal prediction, semi-bandit feedback, partial feedback, document retrieval, prediction sets, adaptive conformal inference, coverage guarantee

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_mtMrOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies online conformal retrieval in a semi-bandit setting. Specifically, for the returned retrieval candidate set, the learner can get the ground truth if the downstream hits the truth, which can be used to update the threshold.

To maintain the coverage guarantee at each step, this paper proposes a counterfactual update: the returned set overrides the proposed set entirely while continuing to monitor historical coverage.

The paper also provides related theorems and provides empirical evaluations on some real datasets, e.g., SQuAD and Natural Questions

Critical strengths
  • The idea is straightforward and easy to follow.
  • The authors provide many sensitivity analyses on the parameters.
Critical weaknesses
  • The theorems are presented in a simple almost-sure way, without a finite bound to show the convergence rate.
  • The setting is pretty ideal (line 43): this simplification is too naive because the retrieval task may miss the ground truth, so CP in practice cannot provide the guarantee. This setting paves the way for your Proposition 1.
  • The authors cue the notion, i.e., protected(ion) or unprotected, multiple times at the beginning but defer the explanation. This makes the reading confusing.
Questions for authors
  • Now that this is online conformal work and the author claims the per-step accumulative coverage guarantee, can you provide the online coverage trajectory for all experiments?
  • Line 012: Does the retrieval return the feedback, or does the downstream work on the retrieved doc reveal the feedback?
  • Lines 150-151: What kind of mechanism provides the assumed hit/miss feedback and identifies the correct document before the next update? For example, does this require a user annotation or a downstream verification system? When protection returns the entire set, the inclusion guarantees that the correct document is present, but what mechanism identifies it?
3 comments
AuthorsOpenReview ↗

Response to Reviewer mtMr

Thank you for your review. We have added protection and cost bounds that include initial adaptation, plus a coverage bound with an explicit pool-miss term. In a new Quora experiment without inserted positives, we obtain 90.9% overall coverage at 18.04 documents/query. We also clarify how external verification supplies relevance feedback.

W1. Finite-time convergence beyond almost-sure guarantees

Under the iid conditions below, expected protection frequency and absolute average-cost error are O(T−β/2)O(T^{-\beta/2}). The cost comparator is the best feasible fixed threshold, and the bounds include initial adaptation. Let α\alpha be the target miss rate, NTN_T the number of protection triggers, and ptp_t the proposal-miss probability conditional on the pre-query history. Define DT=∑t=1TE∣pt−α∣D_T=\sum_{t=1}^T\mathbb E|p_t-\alpha|. With positive-containing pools and accurate, immediate feedback, we prove, without iid, ENT≤[4(1+T)+2DT]/α.\mathbb E N_T\le[4(1+\sqrt T)+2D_T]/\alpha. The bound separates fluctuations from adaptation through DTD_T. For pool size at most KK, expected protection cost is at most KENT/TK\mathbb E N_T/T documents/query above the learner's own proposals.

The O(T−β/2)O(T^{-\beta/2}) rate assumes iid queries, fixed scores, a unique target quantile, positive local coverage slope and local Lipschitz coverage/cost. Steps satisfy ηt=ct−β\eta_t=ct^{-\beta}, c>0c>0, 1/2<β<11/2<\beta<1, with initialization included in the constants. The threshold second-moment rate follows the form of Angelopoulos et al. (2024), Proposition 2. Our added step transfers that rate to protection and returned cost.

W2. Coverage when candidate pools miss the relevant document

With imperfect recall, excess prefix misses are bounded by protected full-pool misses: Mt≤⌊αt⌋+EtM_t\le\lfloor\alpha t\rfloor+E_t. Here MtM_t counts actual misses and EtE_t protected full-pool misses. A full-pool miss still identifies a nested proposal miss.

The natural-pool experiment uses Quora BM25 top-51 pools, with a relevant document present for 95.0% of 10,000 queries, across 20 fixed orders. The 90% target holds at every prefix in 12/20 orders. The other eight have 161 violating prefixes, last at query 79, with at most two excess misses. Six first violations occur in queries 1–9, and two at 14 and 23. Full-pool returns fail at the same prefixes, identifying candidate availability as the constraint at those prefixes.

Furthermore, expected protection and misses remain controlled when the conditional pool-miss probability satisfies ρt≤ρˉ<α\rho_t\le\bar\rho<\alpha on protected rounds. Here ρt\rho_t uses the same pre-query history as ptp_t. The W1 trigger bound then uses denominator α−ρˉ\alpha-\bar\rho and retains DTD_T, and EMT≤⌊αT⌋+ρˉENT\mathbb E M_T\le\lfloor\alpha T\rfloor+\bar\rho\mathbb E N_T. This applies, for example, to iid queries with a fixed retriever whose population miss rate is below α\alpha.

W3. Define protection before using the term

We now define the proposal as the threshold-selected set returned by the unprotected learner. Protection returns the full pool when another miss would exceed the budget. Returned outcomes control coverage. Proposal outcomes drive learning.

Q1. Coverage trajectories for every online experiment

Counterfactual updates meet the target at every prefix in all original positive-pool settings. We computed per-query cumulative coverage and first-100-query views for every Table 4 batch. Coverage after switches uses the original sequence start. Table 3 replays cover both rules, 20 seeds and three nested horizons and exactly reproduce its endpoints. We also replayed five coefficients at seed 12345. Natural-pool trajectories show the early departures quantified in W2.

Q2. Is feedback supplied by retrieval or downstream verification?

External annotation or downstream verification supplies feedback. Retrieval selects documents, while the external mechanism checks relevance. Our learning analysis uses accurate, immediate feedback.

For delayed feedback, we added a conservative coverage guard: count every pending return as a miss, and return the proposal only if that count plus one fits the miss budget. With accurate feedback on arrival, arbitrary delays and out-of-order arrivals preserve Mt≤⌊αt⌋+EtM_t\le\lfloor\alpha t\rfloor+E_t. Perfect pool recall gives Et=0E_t=0 and every-prefix coverage.

Q3. How is the relevant document identified after protection?

External annotation or verification identifies relevance. Our experiments use reference labels. A verified first relevant position or miss determines every nested proposal's outcome, including with multiple relevant documents. Every query needs returned hit/miss feedback. Only protected rounds can need an extra proposal-hit judgment. On natural pools this requires 3.52 document checks/query versus 5.68 for full-pool returns, showing that smaller returned sets also reduce label-inspection cost.

Thanks for the response. Could authors provide the revision to support all your claims?

Thank you for asking to see the revision. The accompanying manuscript brings the proofs, experimental results and coverage curves into one PDF. The following locations correspond to the six points in your review.

W1. How fast do protection and document cost converge? Both the expected fraction of protected queries and the expected absolute error in average returned-set size decay as O(T−β/2)O(T^{-\beta/2}) under the stated i.i.d. conditions. The comparator is the best feasible fixed threshold. Proposition 3 (p. 30) first bounds the expected number of protected queries over any horizon by separating random fluctuations from the learner's initial and subsequent deviations from the target. This step does not require independent queries. Theorem 2 (p. 31) then gives the rate for fixed scores, a unique target quantile with positive local slope, locally Lipschitz coverage and cost, and steps ct−βct^{-\beta} with 1/2<β<11/2<\beta<1. The proofs are in Appendices C.1–C.2 (pp. 30–32). The initialization enters explicitly in Eq. (22) on p. 32.

W2. What if retrieval misses every relevant document? At any prefix, the number of misses above budget is at most the number of protected returns whose entire pool lacks a relevant document. Appendix C.3 (pp. 32–34) proves this pathwise result. Proposition 4 also bounds expected protection and misses when the conditional pool-miss probability on protected rounds stays below the target miss rate by a fixed margin. On 10,000 natural Quora queries, top-51 recall was 95.04%. We reached 90.91% mean coverage at 18.04 documents/query. Twelve of 20 orders met the 90% target at every prefix. In the other eight, even returning all 51 documents missed the target at exactly the same 161 prefixes. The last was at query 79 and the largest excess was two misses (Tables 30–31 and Fig. 5, pp. 35–36).

W3. What does protection change? The opening paragraph of Section 1 (p. 1) now distinguishes the set selected by the threshold from the set actually returned. If one more miss could exceed the budget, protection returns the full pool. The returned outcome counts toward coverage, while the original proposal's outcome updates the threshold (Eqs. (3)–(4), p. 4).

Q1. Where can I see coverage throughout each experiment? Table 4 (p. 19) links each batch to its full-sequence and first-100-query curves (Figs. 7–35, pp. 37–65). Counterfactual updates meet the target at every prefix in the original positive-containing pools. For distribution switches, Fig. 30 (p. 60) measures coverage from the original start. Figure 31 (p. 61) restarts the count at the switch to show local adaptation. The prefix guarantee applies to the full sequence. Figure 36 (p. 66) shows both Table 3 update rules for all 20 seeds and all three nested horizons. These replays reproduce the Table 3 endpoints exactly. Figure 37 (p. 67) shows the five coefficients replayed on development order 12345.

Q2. Who supplies feedback, and when? An external annotator or downstream verifier judges relevance. The abstract (p. 1) names the verifier, and our experiments use reference labels. The learning-rate result assumes accurate feedback before the next update (Section 3.1, p. 3). When feedback is delayed, Proposition 5 (p. 34) proves that counting every pending return as a possible miss preserves the prefix bound even with out-of-order arrivals. With perfect pool recall, this gives the original coverage target at every prefix.

Q3. How is a relevant document identified after a full-pool return? In the designated-label setting the annotator identifies the relevant document. In the natural-pool experiment we use reference labels to check the returned ranking until its first relevant document, or exhaust the set on a miss. Because the proposal is a prefix, that result determines whether the proposal hit even if several documents are relevant (Section 4.3, pp. 4–5). Every query needs a returned hit or miss. Only a protected query can require distinguishing a hit inside the proposal from a hit elsewhere in the pool. On the same natural Quora orders this rule required 3.52 ranked document checks/query, compared with 5.68 for full-pool returns (Table 30, p. 36).

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

This paper studies online retrieval with semi-bandit feedback, aiming to minimize returned documents while guaranteeing per-prefix cumulative coverage. Conventional threshold methods may return the full candidate pool to preserve coverage, but this protection changes hit outcomes and can prevent timely threshold updates, causing repeated full-pool returns. The authors propose a counterfactual update mechanism: it returns the full pool only when the next miss would violate the coverage budget, recovers the original proposed set’s hit/miss outcome from the observable correct document, and updates the threshold using this counterfactual feedback, so the protected learner follows the same threshold trajectory as an unprotected decreasing-step-size learner. The paper proves per-prefix coverage guarantees, trajectory consistency, and convergence of average returned documents to the optimal feasible fixed-threshold cost under stochasticity and continuity assumptions, and analyzes direct actual-feedback updates. Experiments on SQuAD, Natural Questions, and Quora against SPS, OCP-Unlock+, Primal-ACI, and an unprotected learner show that the method meets per-prefix coverage requirements and, in some settings, significantly reduces returned documents.

Critical strengths
  1. The problem is clearly defined and has practical value. The paper focuses not on coverage control alone, but on simultaneously satisfying per-prefix coverage constraints and optimizing document cost under semi-bandit feedback. This setting is practically meaningful, because in systems such as retrieval-augmented generation (RAG), the number of returned documents directly affects the computational overhead of downstream models. The authors explicitly distinguish the original proposed set from the final returned set and incorporate their differences in feedback information and document cost into a unified framework, making the problem formulation relatively clear.
Critical weaknesses
  1. The paper's novelty is not clearly articulated. The threshold update rule directly adopts an existing decreasing-step-size online conformal learning method, and the cumulative coverage protection rule is closely related to the budget-protection idea in conservative bandits. Relative to existing counterfactual feedback inference, online conformal prediction, and conservative bandit methods, what new theoretical or algorithmic properties does this paper establish that cannot be directly derived from existing results?

  2. The assumption that the candidate pool contains the correct document limits practical applicability. The algorithm relies on every candidate pool containing the correct document: when protection is triggered, returning the full pool enables exact recovery of the original proposal’s feedback. However, if the correct document is absent, this mechanism fails, limiting the method to retrieval settings with guaranteed candidate recall rather than end-to-end coverage control. The paper should discuss this limitation and clarify what guarantees remain under candidate-recall failures.

Questions for authors
  1. The paper adopts semi-bandit feedback, but neither the problem formulation nor the theoretical analysis includes bandit-related regret analysis. Should regret bounds and worst-case scenarios be considered?
2 comments
AuthorsOpenReview ↗

Response to Reviewer HEN9

Thank you for your comments. We clarify exact preservation of the unprotected threshold path and add finite-time protection and cost bounds. Matched-feedback experiments show lower cost than actual-hit updates at every tested below-target start on SQuAD and NQ. We also derive an imperfect-recall coverage bound and test it on natural Quora pools.

W1. Novelty beyond conformal updates, conservative bandits and feedback inference

Counterfactual (CF) updates preserve threshold learning under prefix protection. With positive-containing pools and accurate, immediate feedback, they recover proposal outcomes and exactly match the unprotected threshold path. Under Theorem 1's iid/continuity conditions, vanishing protection frequency transfers threshold convergence to average returned cost at the best feasible fixed threshold.

In contrast, actual-hit updates from a positive start below the target quantile stay at or below that start and require positive asymptotic protection frequency under Proposition 2's stochastic conditions. Thus the same protection can produce different learning paths and costs.

We build on the decreasing-step update of Angelopoulos et al. (2024), budget protection of Wu et al. (2016), and unchosen-outcome inference of Yang et al. (2026).

A matched-feedback experiment complements SPS, OCP-Unlock+ and Primal-ACI by isolating the feedback mechanism. CF reduces cost at every tested start below the empirical target quantile: SQuAD's four starts cost 2.78–2.88 documents/query versus 45.66–45.90 for actual-hit, and NQ's three cost 1.60–1.61 versus 45.90. Both rules meet 90% coverage at every prefix in all 20 orders/setting. Across 320 runs, CF also exactly matches the unprotected threshold path while preserving protected coverage.

Quora shows the role of initialization. With eight starts and 20 shared orders on the original positive-containing pools, both rules maintain 90% prefix coverage. Six starts favor actual-hit, 0.05 favors CF, and the paired-order 95% interval at 0.10 spans zero: [−0.15,1.79] documents/query for CF minus actual-hit. These intervals measure order variation within the fixed collection.

At start 0.20, actual-hit costs 25.33 documents/query versus 32.43 for CF and the empirical fixed-threshold reference of 33. This follows from its mixture of full-pool returns on 26.6% of queries and smaller proposals otherwise. It is therefore consistent with Theorem 1, whose comparator is the best feasible fixed threshold.

W2. Coverage guarantees with imperfect candidate recall

With accurate, timely external feedback, proposal outcomes remain recoverable despite pool misses. Coverage incurs an additional miss term: Mt≤⌊αt⌋+Et,M_t\le\lfloor\alpha t\rfloor+E_t, where α\alpha is the target miss rate, MtM_t counts actual misses and EtE_t counts protected full-pool misses. A full-pool miss identifies a nested proposal miss. After a hit, the designated correct label or first relevant position recovers proposal feedback.

Expected protection and misses are also controlled if the conditional pool-miss probability satisfies ρt≤ρˉ<α\rho_t\le\bar\rho<\alpha on protected rounds. Let NTN_T count triggers and ptp_t be the proposal-miss probability, with both probabilities conditioned on the same pre-query history. For δ=α−ρˉ\delta=\alpha-\bar\rho and DT=∑t=1TE∣pt−α∣D_T=\sum_{t=1}^T\mathbb E|p_t-\alpha|, we obtain

\mathbb E M_T\le\lfloor\alpha T\rfloor+\bar\rho\mathbb E N_T.$$ These bounds retain adaptation and apply, for example, to iid queries with a fixed retriever whose population miss rate is below $\alpha$. Testing this setting on natural Quora BM25 top-51 pools yields 90.9% coverage at 18.04 documents/query. Without inserted positives, the pools contain a relevant document for 95.0% of 10,000 queries. The 90% prefix target holds in 12/20 orders. Eight have at most two excess misses, with six first violations in queries 1–9 and two at 14 and 23. Full-pool returns fail at the same prefixes, identifying candidate availability as the constraint at those prefixes. **Q1. Cost regret and worst-case sequences** We obtain vanishing average cost regret under Theorem 1's iid/continuity conditions and an adaptation-dependent protection bound for arbitrary sequences. For returned sets $R_t$ and best feasible fixed-threshold cost $J^{\ast}$, define $$\mathrm{Reg}_T=\sum_t\lvert R_t\rvert-TJ^{\ast}.$$ Under those stochastic conditions, $\mathrm{Reg}_T/T\to0$ almost surely. With fixed scores, a unique target quantile, positive local slope and locally Lipschitz coverage/cost, steps $ct^{-\beta}$ ($c>0$, $1/2<\beta<1$) also give expected absolute average-cost error $O(T^{-\beta/2})$. Sequence-wise prefix feasibility uses the pool/feedback conditions. For arbitrary adapted proposals, $D_T$ can grow linearly, so the trigger bound does not establish general sublinear cost regret.

Thank you for the authors’ response. I have no further questions and will keep my original score.

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

This paper introduces a cumulative miss-budget safeguard for threshold learning udner semi-bandit feedback, while the threshold is learned with a decreasing step size. Whenever an additional miss could violate the prefix coverage, the proposed method falls back and return the full candidate pool. The correct document is still revealed, which determines whether the original proposal would have succeeded and keeps the threshold trajectory of the learner. Retrieval experiments and ablations with matched feedback demonstrate that the mechanism works, especially when the threshold is initialized below the target quantile.

Critical strengths
  • The paper cleanly separates path-wise coverage protection from threshold learning, and it proves an asymptotic cost guarantee. The theoretical results presented seem to be solid.
  • Experiments appear to be thorough. The matched ablations isolate the effect of the feedback and measure the protection overhead.
Critical weaknesses
  • I am not sure how easy this mechanism can be deployed in reality, given the guaranteed-positive pools and the need for immediate correct-document identification, and the lack of general finite-time rates.
Questions for authors
  • Can you provide general finite-time bounds on protection frequency and excess document cost, with the threshold learner's convergence rate in consideration. Your current O(T)O(\sqrt{T}) trigger bound assumes that the proposal miss prob already equals α\alpha, which doesn't incorporate the initial adaptation period in reality.
2 comments
AuthorsOpenReview ↗

Response to Reviewer Y8cT

Thank you for your review. We have added a trigger bound with accumulated adaptation error and combined it with threshold convergence. Under the stated iid regularity conditions, expected protection frequency and absolute average-cost error are O(T−β/2)O(T^{-\beta/2}). We also evaluate natural candidate pools and prove coverage bounds for imperfect recall and delayed feedback.

Q1. Finite-time protection and excess cost during initial adaptation

The new trigger bound accounts for initial adaptation through DTD_T. Let α\alpha be the target miss rate, ptp_t the proposal-miss probability conditional on the pre-query history, NTN_T the protection-trigger count, and DT=∑t=1TE∣pt−α∣D_T=\sum_{t=1}^T\mathbb E|p_t-\alpha|. With positive-containing pools and accurate, immediate feedback, we prove for any adapted proposal sequence, ENT≤[4(1+T)+2DT]/α.\mathbb E N_T\le[4(1+\sqrt T)+2D_T]/\alpha. This bound separates budget fluctuations from accumulated adaptation error through DTD_T. When pt=αp_t=\alpha, it recovers the O(T)O(\sqrt T) bound in your question. For pool size at most KK, expected average cost added by protection is at most KENT/TK\mathbb E N_T/T relative to the learner's own proposals.

The rate assumes iid queries, fixed scores, a unique target quantile τ∗\tau^{\ast}, positive local coverage slope and local Lipschitz coverage/cost around τ∗\tau^{\ast}. For ηt=ct−β\eta_t=ct^{-\beta}, c>0c>0, 1/2<β<11/2<\beta<1, we prove E(τt−τ∗)2≤Ct−β\mathbb E(\tau_t-\tau^{\ast})^2\le Ct^{-\beta}, with initialization and the finite transient included in CC.

The threshold rate has the form of Angelopoulos et al. (2024), Proposition 2. Our added step transfers it to protection frequency and returned-document cost, including empty/full boundary actions. Specifically, for average returned cost J^T\widehat J_T and best feasible fixed-threshold cost J∗J^{\ast},

\le \frac K{2\sqrt T} +\frac{L_g\sqrt C}{1-\beta/2}T^{-\beta/2} +\frac K T\mathbb E N_T.$$ The three terms respectively quantify sampling fluctuations, threshold-learning error and protection cost. Here $L_g$ bounds expected cost's deviation from its value at $\tau^{\ast}$ per unit threshold distance on the bounded iterate interval. The continuous example in original Appendix A.5 satisfies these conditions: its iid uniform positive-document nonconformity score has local coverage slope 5 and locally Lipschitz cost at the target quantile. **W1. Deployment with imperfect recall and delayed relevance feedback** Deployment uses a retriever to form candidate pools and an external annotator or verifier to provide relevance feedback. Each query needs returned hit/miss feedback. Only protected rounds may require an additional judgment of whether the original proposal contains a relevant document. A verified first relevant position or miss determines every nested proposal's outcome, including with multiple relevant documents. Our experiments use accurate, immediate reference labels. On natural pools, the mechanism requires 3.52 document checks/query versus 5.68 for full-pool returns. We added an experiment with natural Quora BM25 top-51 pools, without inserting positives. The pools contain a relevant document for 95.0% of 10,000 queries. Across 20 fixed orders, we obtain 90.9% overall coverage at 18.04 documents/query. Every-prefix 90% coverage holds in 12/20 orders. The other eight have 161 violating prefixes, last at query 79, with at most two excess misses. Six first violations occur in queries 1–9 and two at 14 and 23. Full-pool returns fail at the same prefixes, identifying candidate availability as the constraint at those prefixes. We quantify candidate failures through the bound $M_t\le\lfloor\alpha t\rfloor+E_t$, where $M_t$ counts actual misses and $E_t$ counts protected full-pool misses. A full-pool miss still reveals a proposal miss because the proposal is nested inside the pool. The expected guarantees also account for imperfect recall. Let $\rho_t$ be the pool-miss probability given the same pre-query history as $p_t$. If $\rho_t\le\bar\rho<\alpha$ on protected rounds, the expected-trigger bound uses Q1's numerator with denominator $\alpha-\bar\rho$, retaining $D_T$, and $\mathbb E M_T\le\lfloor\alpha T\rfloor+\bar\rho\mathbb E N_T$. This applies, for example, to iid queries with a fixed retriever whose population miss rate is below $\alpha$. For delayed or out-of-order feedback, we add a conservative guard: count every pending return as a miss and return the proposal only if that count plus one fits the miss budget. With accurate feedback on arrival, $M_t\le\lfloor\alpha t\rfloor+E_t$ still holds. Perfect pool recall gives $E_t=0$ and every-prefix coverage. This extends coverage protection to delayed feedback, while Q1's learning and cost analysis uses immediate feedback.

Thanks for the effort put into the rebuttal. I'd like to keep my positive rating.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.