- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies how deploying a mixture over candidate policies affects the expert feedback available for subsequent learning. It compares frozen per-step mixing (PS), sampling once per episode (PE), and updating after each label (WU), for finite realizable classes with clean expert labels.
For two stochastic policies with a uniform prior, worst-case cumulative squared trajectory Hellinger loss is under PS, versus under PE and WU. Likelihood tempering by gives , while refreshing every steps gives .
For deterministic classes, matching offline return-gap rates are for PS and for PE. Corresponding hybrid bounds hold for the averaged iterate. A rare-context construction refutes the proposed class-size improvement for WARM-STAGGER as specified, while plurality voting achieves the proposed rates in expectation under single-state queries. The experiments are synthetic and mainly validate the theoretical calculations.
Critical strengths
-
Sharp results for a clear question. The main result goes beyond showing that one deployment can fail: it provides matching upper and lower bounds in the stated two-policy model. The tower potential connects information collected along the learner's trajectory to future loss. I find the distinction between bounded and unbounded cumulative discrepancy meaningful, even though the iterated logarithm grows very slowly.
-
A concrete resolution of an algorithmic conjecture. The deterministic characterization is another valuable contribution. It quantifies the extra cost of per-step resampling, and the WARM-STAGGER counterexample addresses a specific proposed improvement. The positive plurality result makes this more useful than a negative result alone, although its guarantee is in expectation rather than high probability.
Critical weaknesses
-
The scope limits the broader takeaway. I see this primarily as a theoretical contribution. The sharpest stochastic characterization concerns two policies under clean-label Bayesian updates and measures trajectory Hellinger loss rather than general cumulative return gaps. Larger-class bounds are provided, but the uniform order around remains unresolved. The authors acknowledge these limitations, so I do not view them as correctness issues, but they limit the broader applicability of the results.
-
The experiments offer limited evidence beyond the constructions, and the presentation is dense. The stochastic experiments use informative labels that consistently reduce the wrong policy's posterior odds by a fixed factor. They do not test cases where labels can temporarily increase a wrong policy's weight. A small variation would help establish how robust the mechanism is. I would also move the two-state recurrence and a short explanation of the tower potential into the main text.
Overall, I lean toward acceptance because the matching bounds and the concrete conjecture refutation are worthwhile contributions. The limited experimental coverage and the scope of the stochastic results keep my recommendation at weak acceptance.
Questions for authors
-
How sensitive is the finite-horizon separation to the uninformative absorbing state? For example, what happens when post-failure states provide some distinguishing labels, or there is a chance of returning to informative states? A small sensitivity analysis would help clarify the mechanism's scope.
-
Proposition 8 is explicitly an expectation guarantee. Does its argument extend to high probability with logarithmic dependence on , or is there a particular obstacle? I regard this as a possible extension rather than a missing step in the stated result.
2 comments
Thank you for the detailed response. The sensitivity analysis clarifies the role of lost feedback, and the experiment with fluctuating posterior odds addresses my concern about the original label model. The high-probability extension of Proposition 8 is also a welcome addition. Please include these results in the revision, particularly the finding that continued informative feedback can remove the asymptotic separation, along with the proposed presentation improvements. My concerns about the narrow stochastic setting and broader applicability remain, but I still find the theoretical contributions worthwhile and will maintain my weak acceptance.
Response to Reviewer 3
Thank you for suggesting tests of feedback sensitivity and posterior fluctuations.
Feedback after failure and returns to informative states
We evaluated two feedback perturbations while keeping per-step deployment frozen throughout each episode.
In the first, the failure state remains absorbing, but each label there has likelihood ratio
2^(−λ)in favor of the wrong policy relative to the expert. This is realized by keeping the expert distribution(1/2, 1/2, 0)and setting the wrong policy at the absorbing state to(2^(−λ)/2, 2^(−λ)/2, 1 − 2^(−λ)). IfK_tcounts active visits, the negative base-two log odds satisfyIn the second, labels at the failure state remain uninformative, but each step there returns to the active state with probability
ρ. The update then uses all active visits, including revisits. To keep the return criterion fixed, reward is one only if no failure action occurred; a failure flag in the state records this event.Summing the count recursions gives these cumulative expected terminal-success return gaps over all learning rounds:
H = 128H = 1024λ = 1/128λ = 1/16ρ = 0.01ρ = 0.1Hactive-state labels after every episodeThe recursions have omitted-tail bounds below
10^(−15); the displayed values use ordinary floating-point evaluation. Recovery kernels were checked against exhaustive enumeration at small horizons, and zero recovery reproduces the original recursion.For the first perturbation, we can also characterize the asymptotic change. Fix
λ > 0and writea = min{1, λ}. Every episode adds at leastaHtob_t, henceThis is bounded uniformly in
Hfor fixedλand converges to one asH → ∞. Thus, a fixed positive amount of distinguishing information per post-failure step removes the asymptotic iterated-logarithm growth in this perturbed construction. Small amounts of feedback can still leave excess loss at finite horizons, as the table shows. The construction demonstrates the cost of losing informative visits; its asymptotic separation need not persist with continued feedback.Labels that temporarily favor the wrong policy
Theorem 1 also permits such labels. Its proof uses conditional likelihood-ratio moments and the expected decrease of the tower potential, without assuming that posterior odds decrease on every update.
We also ran a variation with expert probabilities
(1/2, 1/2, 0)and wrong-policy probabilities(0.6, 0.15, 0.25)at the active state. An expert label multiplies the wrong-policy odds by either1.2or0.3, each with probability1/2. The failure state remains absorbing and uninformative. Over 128 learning rounds and 100,000 independent histories per setting, the cumulative expected terminal-success return gaps were:1281.8251 ± 0.00480.6419 ± 0.001710242.0710 ± 0.00510.6434 ± 0.0017Intervals are pointwise approximate 95% Monte Carlo confidence intervals across independent histories. We integrate conditional expected returns and sample the histories determining subsequent posteriors. For frozen per-step mixing, the first complete episode increased the wrong-policy odds in 11.46% and 11.23% of runs, respectively. The deployment gap persists with posterior fluctuations; these finite-round results establish neither a new asymptotic rate nor broad environmental coverage.
High probability and presentation
Proposition 8 extends to high probability under its existing assumptions. Each queried plurality mistake halves the version space, giving a deterministic bound on the number of observed mistakes. An exponential supermartingale converts this into a bound on their conditional probabilities. Combined with the offline finite-class bound, the result is
with probability at least
1 − δ. Omit the offline term without offline data. Reviewer 1's response gives constants and proof. No additional round logarithm is needed.We will move the recurrence and a short explanation of the tower potential into the main text. We will also state the unresolved
M ≈ Hregime there and preserve the distinction between the general Hellinger theorem, the deterministic return guarantees, and the return separation for the terminal-success construction.