{"id":"40058094-db17-48d3-8c50-0843bc6f2a88","arxiv_id":"2501.07761","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A Thompson sampling bandit with a Bayesian filter over progressively revealed engagement signals improves cold-start recommendation before long-term rewards are observed, with regret bounded by the Value of Progressive Feedback.","lead":"Recommender systems that optimize for long-term user satisfaction usually have to wait weeks for feedback. This paper proposes a bandit algorithm that learns from progressive engagement signals before long-term rewards appear, proves a regret bound tied to how informative those signals are, and reports a large Spotify A/B test supporting the approach.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The regret guarantee is only as good as the empirical-Bayes prior: Section 9 disclaims any prior-learning guarantee, and Section 7.4 shows the progressive-feedback advantage collapses with an uninformative prior, so prior misspecification is the load-bearing gap.","rationale":"I independently read the proof of Theorem 1 and Corollary 1. The argument is self-contained under the stated Gaussian assumptions: Lemma 2 reduces regret to posterior variance, Lemma 3 transfers bandit-feedback covariance to full-information covariance via inverse propensity weights, and Lemma 5 identifies the variance ratio with exp(-2 VoPF). I checked the algebra around Eq (26). The displayed equality is not true for arbitrary V_z when the conditioning set is the full vector {Y_u(a)} rather than only the scalar rewards R(Y_u); the correct statement is an inequality (full-vector posterior variance is no larger than scalar-reward posterior variance), which preserves the upper bound, so this is a repairable typo rather than a fatal gap. No machine-checked proof is provided, but the analytical structure is plausible. The genuinely load-bearing assumption is that the empirical-Bayes prior is correctly specified and learned; the paper explicitly disclaims guarantees, and Section 7.4 demonstrates that the algorithm's advantage depends on the fitted prior. The A/B test validates a deterministic ranking variant and does not report significance, but the paper is transparent about the variant; this weakens the empirical generalization, not the regret theorem. Because the central theoretical claim holds under explicitly stated assumptions and the main gap is an acknowledged limitation, I agree with the reader's CONDITIONAL verdict and recommend no change.","tokens_in":42749,"tokens_out":21443,"duration_ms":225522,"concrete_test":"Use the two temporal splits in Section 6.1 to perform a prior-calibration check and a regret comparison. Fit the prior on the September-December 2021 shows; on the January-March 2022 validation shows, (i) compute standardized residuals (Y_u minus the posterior mean) and test whether they match the assumed N(0, V_z) noise and whether the fitted between-show covariance Sigma_1,z equals the empirical covariance of validation show means, and (ii) run the Section 7.3 simulator under three priors: the fitted prior, an oracle prior estimated directly from the validation shows, and the fitted prior with hyperparameters perturbed by their empirical-Bayes standard errors. If the regret with the fitted prior is not close to the oracle prior, or if the residuals show systematic miscalibration, the concern lands and the claim should be stated as conditional on prior validity.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central regret bound (Theorem 1, Corollary 1) is derived under Assumptions 1-4, which include a correctly specified Gaussian prior (mu_1,z, Sigma_1,z) and noise covariance V_z. The posterior update (Proposition 2) is exact only under this Gaussian model, and Lemma 3 bounds the bandit posterior covariance using the full-information covariance CFull computed from that model. If the prior fitted by the Section 6 empirical-Bayes procedure is misspecified for newly released items, the posterior used by Thompson sampling is not the true conditional distribution, the quantities p*_{t,a} and sigma^2_{t,a} in Lemma 2 no longer correspond to true Bayesian beliefs, and the exp(-VoPF(t)) improvement is not guaranteed. The paper explicitly acknowledges this in Section 9: 'The Impatient Bandit algorithm assumes that the prior distribution is learned correctly. A limitation of this work is that we did not provide any guarantees regarding under what settings one would expect to learn an accurate prior from previously collected data.' The empirical evidence makes the concern concrete: Section 7.4 shows that replacing the fitted prior with an isotropic uninformative prior makes Progressive perform no better than the Delayed baseline, so the practical benefit attributed to progressive feedback is largely mediated by the prior. In the real podcast data the Gaussian assumption is also an approximation to binary engagement traces, and the A/B test uses a deterministic ranking variant rather than the Thompson-sampling algorithm, so the theoretical guarantee does not directly cover the deployed system. These are limitations rather than internal inconsistencies; the mathematical proof appears coherent under its stated assumptions.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper formalizes a multi-armed bandit setting with progressive feedback and delayed rewards, proposes an Impatient Thompson Sampling algorithm built on a Gaussian Bayesian filter, and proves a per-batch regret bound whose improvement over delayed-reward Thompson sampling is governed by an information-theoretic quantity called the Value of Progressive Feedback (VoPF). The authors fit the Gaussian prior by empirical Bayes, validate the method on synthetic and Spotify podcast data, and report a large-scale Spotify A/B test in which a deterministic ranking variant with progressive stickiness estimates improves long-term engagement metrics, especially for recently released shows.","tokens_in":43071,"tokens_out":7622,"duration_ms":76257,"significance":"If the main results hold, this is a valuable contribution: VoPF is an environment-dependent, algorithm-independent quantity, and the regret bound interpolates cleanly between delayed and immediate feedback. The proof machinery, which builds on inverse-propensity weighting and lemmas from Qin and Russo, is substantive and mostly carefully presented. The synthetic experiments qualitatively match the theoretical prediction, and the large-scale A/B test is rare and valuable industrial evidence for the practical value of progressive feedback. The main limitations are that the theoretical guarantees require a correctly specified Gaussian prior and that the A/B test evaluates a deterministic ranking variant rather than the proposed bandit algorithm itself; the manuscript's broadest claims are stronger than what the evidence supports in these two respects.","major_comments":[{"comment":"The central regret guarantee is derived under Assumptions 1–4, which include a Gaussian outcome model and a prior distribution for theta_a that is known to the algorithm. Section 9 explicitly disclaims any guarantee about learning an accurate prior from previous data. Section 7.4 (Figure 7) then shows that replacing the fitted prior with an isotropic uninformative prior makes Progressive essentially match Delayed, so the exp(-2·VoPF) improvement is not a property of progressive feedback alone; it is jointly mediated by the quality of the empirical-Bayes prior. Because Proposition 2 and Lemmas 2–5 are exact only under this correctly specified Gaussian model, the paper's practical claim that the algorithm 'significantly outperforms' delayed-reward methods is not established under prior misspecification. Please add a misspecification or robustness analysis, or an empirical-Bayes consistency result with explicit rates, and qualify the abstract and Section 1 claims accordingly.","section":"Theorem 1; §7.4; §9"},{"comment":"The A/B test does not evaluate Algorithm 1 or Algorithm 2. Section 8 states that all tested variants use deterministic ranking strategies, and Section 8.4 specifies that the treatment policy replaces the delayed stickiness estimate with the posterior mean from the Gaussian filter, with no Thompson-sampling exploration. The reported gains therefore validate the progressive-feedback filtering model in a ranking system, but not the bandit exploration or the regret guarantees that constitute the paper's theoretical contribution. The abstract's statement that the approach is 'demonstrated by an A/B test' should either be scoped to this deterministic ranking variant or be accompanied by an online experiment that actually runs the bandit algorithm.","section":"§8.4 and Section 8 introduction"},{"comment":"The headline empirical claims—over 50% increases on three recent-show metrics and 7–10% increases on all-show metrics—are supported only by point estimates with standard errors. The manuscript does not report the sample sizes behind recent-show impressions, confidence intervals for the reported ratios, or any multiple-comparison control across the four primary metrics. Since these numbers are central to the paper's applied significance, please provide formal interval estimates or a pre-specified analysis plan; if the standard errors shown are meant to be sufficient, the authors should explain why they support the stated conclusions.","section":"§8.5, Figure 11, Table 1"},{"comment":"The formal model assumes Gaussian engagement outcomes (Assumption 3), but the Spotify data used in Sections 6.1, 7.3–7.5, and 8 consist of binary daily indicators Y_u^(j) = 1{user engaged on day j}. This is a model misspecification in the main empirical application, so the exact Gaussian posterior and the regret bound do not directly cover the data-generating process used in the real-data experiments. The paper should state this mismatch as a limitation and provide calibration or robustness evidence, such as posterior predictive checks or a comparison to a non-Gaussian filter, rather than presenting the Gaussian filter as the model for the real data.","section":"Assumption 3; §6.1"}],"minor_comments":[{"comment":"In the paragraph following Algorithm 1, the phrase 'the posterior update rule used in line 11 of Algorithm 1 is can be derived' contains a grammatical typo; please revise.","section":"§4, Algorithm 1 description"},{"comment":"In the proof of Lemma 5, the second entropy term uses \\tilde Y_{u,t-1}(a) in one display, while the statement and the rest of the proof use \\tilde Y_{u,t}(a); this should be corrected to be internally consistent.","section":"Appendix D.2, Lemma 5 proof"},{"comment":"The text says 'reduce the number of actions per round dramatically from m = 1000 to m = 10,' but m is the batch size, not the number of actions per round; please rephrase to avoid confusion.","section":"§7.2"},{"comment":"The y-axis label 'Information entropy [Nats]' is misleading because the plotted quantity is the Value of Progressive Feedback measured in nats, not an entropy; please relabel the axis accordingly.","section":"Figure 3"},{"comment":"The phrase 'huge increases' is informal for a refereed paper; please replace it with precise effect sizes and confidence intervals, and reserve magnitude language for the discussion section.","section":"§8.5"}],"recommendation":"major_revision","confidential_remarks":"To the editor: The authors are transparent about the prior-learning limitation in Section 9 and about the differences between the A/B implementation and the theoretical algorithm in Section 8, so my concerns are about the scope of the claims rather than about integrity. The VoPF quantity is not circular: it is defined as a property of the environment and is not fitted from the algorithm's behavior. The overlap with the authors' KDD 2023 paper is disclosed, and the regret analysis and A/B test are the substantial new contributions. I see no reason to doubt fit with the journal's scope, but the empirical inference details should be strengthened before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The real news here is the formal model and the regret analysis. The algorithm itself is the KDD 2023 Impatient Bandit, but this paper adds a clean problem formulation, a regret bound that depends on the Value of Progressive Feedback, and a large-scale Spotify A/B test. The VoPF quantity is genuinely useful: it is an environment property, not a fitted constant, and the bound interpolates between delayed and immediate feedback in a way that matches intuition. The proof seems internally coherent under Assumptions 1–4, building on Qin and Russo, and the semi-synthetic experiments track the theory well, including the predicted exp(−VoPF) shrinkage in regret. That is solid work.\n\nThe soft spots are real but not fatal. The load-bearing one is prior misspecification. The regret bound assumes a correctly specified Gaussian prior, and Section 9 explicitly disclaims any guarantee about learning that prior from historical data. Figure 7 makes the concern concrete: with an isotropic uninformative prior, Progressive performs no better than Delayed. So the practical benefit is mediated by the quality of the empirical-Bayes prior. This does not break the theory—the theorem is conditional on its assumptions—but it means the title's 'without delay' is contingent on a good prior. A referee should push on this gap rather than treat it as a contradiction.\n\nThe A/B test is a case study, not a tight experiment. It validates a deterministic ranking variant, not the Thompson-sampling algorithm, and the headline percentages come without confidence intervals. Still, the effect sizes are large, the direction is consistent with the simulations, and the fact that it changed production at Spotify is evidence of practical relevance. I don't read the heavy reliance on the authors' own prior papers as a flaw here; those results are disclosed and independently published.\n\nWho is this for? People working on bandits with delayed or surrogate feedback, and recommender systems folks facing cold start. It deserves a serious referee, and with revisions addressing the prior-learning caveat and the A/B uncertainty it could be a useful reference. I would not desk-reject it.","headline":"Formal progressive-feedback bandits with a genuinely novel VoPF-dependent regret bound and a production-scale A/B test; the main soft spot is the correctly-specified-prior requirement, which the authors openly acknowledge.","tokens_in":43645,"tokens_out":1282,"would_cite":true,"duration_ms":15800,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"A Thompson-sampling Bayesian filter learns 60-day rewards from early engagement; a large podcast A/B test saw recent-show 60-day metrics rise over 50%.","keywords":["multi-armed bandits","delayed rewards","progressive feedback","Thompson sampling","Bayesian filtering","regret bounds","cold-start recommendation","recommender systems"],"falsifier":"Run the fitted-prior algorithm on a held-out domain where early engagement is uncorrelated with the 60-day reward (estimated VoPF near zero), and compare the log-ratio of delayed versus progressive regret to the predicted $\\exp(-\\mathrm{VoPF}(t))$ curve; if regret does not improve before day 60, or if the measured ratio trails the prediction, the central pre-reward learning claim is contradicted.","tokens_in":42550,"feed_emoji":"🎧","tokens_out":10831,"duration_ms":97481,"temperature":0.7,"pith_summary":"This paper takes on the cold-start problem in recommender systems, where the reward of interest—say, engagement over 60 days—arrives long after the recommendation decision. The authors model the setting as a bandit with progressive feedback: short-term engagement outcomes arrive day by day and are imperfectly correlated with the eventual long-term reward. Their algorithm, the Impatient Bandit, combines Thompson sampling with a Bayesian filter that updates a posterior over each item's latent quality as partial trajectories arrive. The paper's central theoretical claim is that the expected regret in every batch is at most the regret of delayed-reward Thompson sampling scaled by $\\exp(-\\mathrm{VoPF}(t))$, where $\\mathrm{VoPF}(t)$ is the mutual information between progressive feedback and the mean reward. If correct, this means informative early signals can drive good decisions well before any long-term reward is ever observed, and the reported podcast A/B test supports that conclusion with over 50% improvements in 60-day engagement metrics for recently released shows.","feed_headline":"Early engagement signals beat waiting for 60-day rewards","feed_subtitle":"A Bayesian-filter bandit shows early signals cut regret before long-term rewards appear; a large podcast A/B test confirms.","key_machinery":"The load-bearing object is the Value of Progressive Feedback, $\\mathrm{VoPF}(t) = I(\\bar R_a; \\{\\tilde Y_{u,t}(a)\\}_{u\\in\\mathcal{U}_{<t}} \\mid \\{\\tilde Y_{u,t}(a)\\}_{u\\in\\mathcal{U}_{<(t-d_{\\max})}})$, an environment-defined conditional mutual information that measures how much of the uncertainty in an item's mean long-term reward is resolved by early engagement beyond what the fully delayed rewards would resolve. It enters the bound directly as $\\exp(-\\mathrm{VoPF}(t))$. The second engine is the Bayesian filter: a Cholesky whitening of the noise covariance converts each partial engagement trajectory into linear measurements of $\\theta_a$, so the posterior over latent quality updates in closed form as censored outcomes arrive. Thompson sampling draws from that posterior to choose items, and the regret analysis uses inverse-propensity-weighted posterior covariances to show that the variance at the optimal arm is controlled by the full-feedback covariance multiplied by $\\exp(-2\\,\\mathrm{VoPF}(t,Z_a))$.","core_discovery":"The paper's central claim is that with delayed long-term rewards and progressive feedback, a Thompson-sampling algorithm driven by a Bayesian filter can achieve low expected regret before any long-term reward is observed, at a rate governed by the Value of Progressive Feedback. Formally, under a Gaussian model in which each item has a latent quality vector $\\theta_a$ and user trajectories are i.i.d. noise around it, the expected instantaneous regret at batch $t$ of the lower-variance Impatient Bandit is bounded by $\\exp(-\\mathrm{VoPF}(t))\\cdot \\sigma_R\\sqrt{2|A|\\log(|A|)/(\\sigma_R^2(r_1^\\top \\Sigma_1 r_1)^{-1}+|U_{<(t-d_{\\max})}|)} + O(\\epsilon_{\\mathrm{rnd}})$; the square-root factor is the regret of Thompson sampling that waits for delayed rewards, and $\\mathrm{VoPF}(t)$ is the conditional mutual information between the mean reward and the progressive observations given only the fully delayed observations. The paper further claims that in a large podcast-recommendation A/B test, the progressive-feedback treatment raised discovery rate by roughly 30% and 60-day active days, minutes, and return days per impression by over 50% for recently released shows relative to the delayed-reward control, and that the method was subsequently used in production.","pith_inferences":["Editorial inference: a natural logged-data test of the theory is to estimate $\\mathrm{VoPF}(t)$ from the fitted prior and compare it with the measured log-ratio of delayed versus progressive regret; a mismatch would diagnose prior misspecification or non-stationarity.","Editorial inference: the mechanism transfers to other delayed-outcome decisions with intermediate signals—clinical trials with biomarker surrogates, marketing with early click signals, or content moderation with early user reports—wherever a Gaussian filter can be fit from historical trajectories.","Editorial inference: the acknowledged reliance on a correctly learned prior means the pre-reward gains may shrink for genuinely novel content categories with no historical analogues, and the A/B-test gains should not be assumed to persist when the item distribution shifts.","Editorial inference: because VoPF is algorithm-independent and computable from data, it could be used prospectively to screen which surrogate signals justify an expensive online experiment before committing to deployment."],"forward_implications":["Before any long-term reward is fully observed, the algorithm can already achieve low expected regret in every batch when early engagement is informative, because the regret bound shrinks as $\\exp(-\\mathrm{VoPF}(t))$.","With uninformative progressive feedback the bound reduces to standard delayed-reward Thompson sampling; with perfect leading indicators it matches no-delay Thompson sampling, so the result interpolates between those extremes.","In the podcast simulations, the progressive-feedback policy accumulated far less regret than the delayed-reward policy during the first 60 days, and in a continuously changing action set the delayed policy never improved while the progressive policy kept cumulative regret under half.","In the reported A/B test, recently released shows recommended by the treatment policy had roughly 30% higher discovery rate and over 50% higher 60-day active days, minutes, and return days per impression compared with the delayed-reward control.","Since $\\mathrm{VoPF}$ is a property of the data-generating environment, it can be estimated from historical data before deployment and used to compare candidate progressive feedback signals."],"supporting_citations":[{"why":"Supplies the underlying Thompson sampling exploration strategy that the algorithm builds on.","marker":"[Thompson, 1933]"},{"why":"Provides the inverse-propensity-weighted analysis and Lemma 8 used to bound posterior variance under bandit feedback in the regret proof.","marker":"Qin and Russo [2023]"},{"why":"Defines the long-term stickiness model used as the delayed-reward control policy and demonstrates the value of long-term outcomes that this paper extends with progressive feedback.","marker":"Maystre et al. [2023]"},{"why":"De Finetti's representation justifies the latent item-quality parameter $\\theta_a$ that the Bayesian filter targets.","marker":"[Heath and Sudderth, 1976, De Finetti, 1937]"},{"why":"Supplies the standard Thompson sampling regret benchmark that the perfect-progressive-feedback extreme of the bound is compared against.","marker":"Russo and Van Roy [2016]"},{"why":"Supplies the original Impatient Bandit algorithm that this paper formalizes and extends with the regret analysis and A/B test.","marker":"McDonald et al. [2023]"}],"fun_headline_variants":["Short-term signals cut regret before long-term rewards","Bayesian filter uses early engagement to beat 60-day wait","Progressive feedback theory validates podcast recommender gains","Impatient bandit learns from proxies before long-term rewards","Value of Progressive Feedback drives early-regret reduction"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The posterior updates and the regret bound are only valid if the Gaussian prior learned from historical data correctly describes newly released items; the paper states in Section 9 that it provides no guarantee for when such a prior can be accurately learned.","fun_headline_variants_meta":{"raw":{"variants":["Short-term signals cut regret before long-term rewards","Bayesian filter uses early engagement to beat 60-day wait","Progressive feedback theory validates podcast recommender gains","Impatient bandit learns from proxies before long-term rewards","Value of Progressive Feedback drives early-regret reduction"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000934,"raw_usage":{"total_tokens":4053,"prompt_tokens":1056,"completion_tokens":2997,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":672,"completion_tokens_details":{"reasoning_tokens":2921}},"tokens_in":672,"tokens_out":2997,"duration_ms":20358,"temperature":1.0,"reasoning_tokens":2921,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T20:36:02.876206+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the fitted-prior algorithm on a held-out domain where early engagement is uncorrelated with the 60-day reward (estimated VoPF near zero), and compare the log-ratio of delayed versus progressive regret to the predicted $\\exp(-\\mathrm{VoPF}(t))$ curve; if regret does not improve before day 60, or if the measured ratio trails the prediction, the central pre-reward learning claim is contradicted.","supporting_citations":[],"review_version":1}