{"id":"24135804-d322-481c-895b-9c8494493510","arxiv_id":"2502.01876","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Segmenting episodes helps exponentially when feedback is binary, but barely helps when feedback is the sum of rewards.","lead":"This paper studies how often a reinforcement learning agent should receive feedback, a middle ground between per-action rewards and one reward per episode. It finds that when feedback is a simple thumbs up or down, splitting the episode into more segments cuts regret exponentially, while when feedback is the sum of rewards, extra segments barely help.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 4.1 omits the full-rank coverage condition its E-optimal design requires; the m-independence result is proved only for MDPs where a policy mixture makes the segment-feature covariance invertible.","rationale":"I agree with the reader that the coverage/reachability condition is the key missing hypothesis in Theorem 4.1. The proof in Appendix D.1 depends on Lemma D.2, whose inequality requires the E-optimal design to have a finite optimum, which in turn requires the mixture covariance to be invertible. The main text states this assumption in the algorithm description but the theorem statement is unconditional. This is load-bearing because the sum-feedback m-independence claim is an upper-bound statement about a concrete algorithm; without the hypothesis, the algorithm is not well-defined for some MDPs. The issue does not overturn the overall verdict: the reader's CONDITIONAL already encompasses it, and the lower bound in Theorem 4.2 is constructed on an MDP satisfying the coverage condition, so the minimax claim that increasing m does not significantly reduce regret remains intact. I would keep the verdict at CONDITIONAL and ask the authors to state the reachability/coverage assumption explicitly in Theorem 4.1 (or restrict the feature space to the reachable sub-MDP) before publication.","tokens_in":52994,"tokens_out":20786,"duration_ms":212178,"concrete_test":"Construct a two-state episodic MDP with initial state s0 and an unreachable state s1, so that for every policy the segment-feature covariance has zero rows and columns for (s1, a) for all a. Compute Eq. (4): the inverse of the mixture covariance does not exist and z* = ∞, making K0 in Algorithm 2 undefined. This confirms that Theorem 4.1 cannot be applied without an explicit reachability hypothesis. As a complementary check, delete all unreachable coordinates and re-derive Lemma D.2 on the reduced feature space; if the lemma holds there, the issue is precisely a missing hypothesis rather than a faulty derivation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central sum-feedback upper bound (Theorem 4.1) relies on Algorithm 2's E-optimal design (Line 2, Eq. (4)). The optimization minimizes ||(Σπ w(π) Σi E[φ_{τ_i} φ_{τ_i}^T])^{-1}||; this objective is finite only if some mixture of policies yields a nonsingular |S||A| × |S||A| covariance. When a state-action pair is unreachable from ρ under every policy, the corresponding row/column vanishes, the matrix is singular, z* = ∞, and K0 (Line 3) is undefined. Lemma D.2, which uses this invertibility to prove the sampled initial covariance has minimum eigenvalue ≥ H^2, fails; consequently the proof that ||φ_π||_{Σ_{k-1}^{-1}} ≤ 1 for all k > K0 breaks. The theorem statement does not include the reachability/coverage assumption; it appears only as 'We assume...' in the algorithm description. The m-independence conclusion therefore applies only to MDPs satisfying this condition. This is a qualification rather than a fatal error: the lower bound (Theorem 4.2) is built on a covered instance, so the worst-case claim that increasing m does not substantially reduce regret still stands.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces RL with segment feedback, an episodic tabular setting in which each episode is split into m equal segments and the agent observes feedback only at the end of each segment. Two feedback models are studied: binary feedback, where each segment yields a Bernoulli observation with parameter the sigmoid of the segment reward, and sum feedback, where the segment reward sum is observed with sub-Gaussian noise. The paper proposes Thompson-sampling algorithms SegBiTS and SegBiTS-Tran for binary feedback with known and unknown transitions, and E-LinUCB and LinUCB-Tran for sum feedback with known and unknown transitions. The main results are: for binary feedback, regret scales as exp(H rmax/(2m)) times polynomial factors, with a matching lower bound exp((1/2-c0)H rmax/m) sqrt(mK); for sum feedback, the leading regret term is O(|S||A| sqrt(HK) log) and is independent of m, with lower bounds Omega(sqrt(|S||A|HK)) and Omega(rmax H sqrt(|S||A|K)). Small experiments support the binary exponential decay and the roughly flat m-dependence for sum feedback. The appendix contains complete proofs, including self-concordance arguments for logistic bandits, KL/Pinsker lower bounds, and E-optimal experimental design for the initialization phase.","tokens_in":88,"tokens_out":14184,"duration_ms":276490,"significance":"The segment-feedback model is a natural interpolation between per-step feedback and once-per-episode trajectory feedback, and the paper gives the first systematic theoretical treatment of how the number of segments affects regret. If the stated bounds are correct, the contrast between exponential improvement in m under binary feedback and essentially flat leading-order behaviour under sum feedback is an interesting and non-obvious message. The proofs are detailed and self-contained: the binary upper bound adapts logistic-bandit self-concordance and Thompson-sampling anti-concentration, the binary lower bound uses a clean KL/Pinsker construction, and the sum upper bound improves the prior trajectory-feedback result of Efroni et al. by a sqrt(H) factor through E-optimal design. The lower bounds are information-theoretic rather than algorithmic, and the constants are explicit analytic functions of the problem parameters rather than fitted values.","major_comments":[{"comment":"Theorem 4.1 is stated without the full-rank coverage condition that Algorithm 2's E-optimal design actually requires. In Eq. (4), z* is finite only if some distribution w over policies makes the expected segment-feature covariance matrix nonsingular; otherwise z*=infinity, K0 in Line 3 is undefined, and Lemma D.2, which is used to prove ||phi_pi||_{Sigma_{k-1}^{-1}} <= 1 for all k > K0, fails. The assumption appears only as 'We assume...' inside the algorithm description, not in the theorem statement. The m-independence conclusion for sum feedback is therefore established only for MDPs satisfying this coverage property, and the theorem statement as well as the discussion following it should say so explicitly.","section":"§4.1, Theorem 4.1, Algorithm 2, Eq. (4)"},{"comment":"The additive term (z*)^2 H^5 log(1/delta) in Theorem 4.1 is not m-independent. Here z* is the E-optimal value of the unnormalized segment-feature covariance, and for a one-state, one-action MDP one has z* = m/H^2, making this term of order m^2 H. Thus the text's claim that the upper bound 'does not depend on m when ignoring logarithmic factors' is not literally true: the leading term in K is m-independent, but the initialization term can grow with m and the finite-K regret bound can worsen as m grows. The authors should either state explicitly that the m-independence claim concerns only the leading term in K and for K sufficiently large, or provide an additional argument controlling the z* term if the claim is meant to hold for all K.","section":"§4.1, Eq. (4), Theorem 4.1"}],"minor_comments":[{"comment":"Algorithm 1 takes lambda as an input but no value or tuning rule is given; the regret bound in Theorem 3.1 depends on lambda through nu(K) and alpha lambda, so a specific choice (or a statement that the bound holds for any fixed lambda) should be included.","section":"Algorithm 1, §3.1"},{"comment":"In the union-bound arguments in Lemma C.11 and the parallel Lemmas D.6 and D.14, the text says 'with probability at least delta-prime' after taking the union bound; this should read 'with probability at least 1 - delta-prime'.","section":"Appendix C.2, proof of Lemma C.11"},{"comment":"In the lower-bound instance description, r(s_{n+2}, a) = (1 - eps) rmax appears in some places as '1 - eps rmax' without parentheses; this is a typographical issue in the display but should be corrected for clarity.","section":"Figure 5 and §C.2"}],"recommendation":"major_revision","confidential_remarks":"The paper is technically strong and the proofs are unusually complete, but the two issues in Theorem 4.1 are load-bearing for the paper's central qualitative message. Both are fixable by a clearer theorem statement and an explicit discussion of the asymptotic-in-K interpretation of the sum-feedback bound; after that I would be willing to support acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things. First, this paper gives the first regret bounds that quantify how the number of segments m affects learning under segment feedback, and the central contrast is credible: binary feedback regret scales like exp(H rmax / 2m), while sum feedback regret is essentially m-independent. Second, the sum-feedback upper bound in Theorem 4.1 is overstated as printed. The proof depends on Algorithm 2's E-optimal design, which requires some mixture of policies to make the segment-feature covariance invertible. That assumption appears only in the algorithm description, not in the theorem statement. So the m-independence result is proved only for MDPs with full reachability/coverage.\n\nWhat the paper does well: the binary lower bound is genuinely new and the KL/Pinsker argument is clean. The binary upper bound uses adapted logistic-bandit self-concordance tools and looks coherent. The sum-feedback analysis is standard linear bandit plus E-optimal design, and it improves the prior trajectory-feedback result by sqrt H. No parameters are fitted; all constants are explicit. The proof appendix is consistent with the stated theorems as far as I checked without machine verification. The experiments are small and no code or data are released, but they are clearly secondary to the theory.\n\nThe soft spot I want you to weigh is just the missing coverage condition in Theorem 4.1. This is a qualification, not a fatal error. The lower bound in Theorem 4.2 is built on a covered instance, so the worst-case claim that increasing m does not help much under sum feedback still stands. The fix is straightforward: state the reachability assumption in the theorem and, ideally, discuss how it relates to the empirical bagged-reward work. A secondary concern is that the E-LinUCB algorithm is computationally heavy; the paper even says the experiments use a small MDP because of that, so the \"practical\" message is weaker than the abstract suggests.\n\nWho gets value from this: RL theorists and anyone working on reward engineering with sparse or aggregated feedback. The binary lower bound alone is worth a serious referee. I would send it to review rather than desk-reject, with a request to fix the theorem statement and add a short discussion of coverage. I would not block publication on the missing condition, but it has to be written down.\n\nMy bottom line: the central result is likely correct; it needs an honest qualifier, not a rewrite.","headline":"The binary-vs-sum contrast is real and well supported, but Theorem 4.1 as stated omits the coverage condition its E-optimal design needs, so the m-independence claim needs qualification.","tokens_in":53752,"tokens_out":1136,"would_cite":true,"duration_ms":14920,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","90C40","62K05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Under binary segment feedback, RL regret decays exponentially with the number of segments, while under sum segment feedback the number of segments barely affects regret.","keywords":["segment feedback","binary segment feedback","sum segment feedback","episodic MDP","regret bounds","Thompson sampling","LinUCB","E-optimal design"],"falsifier":"On the binary side, run SegBiTS on the paper's experimental MDP with $H=100$, $r_{\\max}=0.5$ for $m=1$ and $m=2$; the claimed bound predicts the $m=1$ regret exceeds the $m=2$ regret by a factor on the order of $\\exp(H r_{\\max}/2)=\\exp(25)\\approx 7.2\\times 10^{10}$, so a measured ratio orders of magnitude smaller would falsify the exponential dependence. On the sum side, execute E-LinUCB on an MDP where the E-optimal design is singular, e.g., some state-action pair is unreachable under every policy; the theorem as stated promises the flat-in-$m$ bound but the algorithm has no defined $K_0$, revealing that the missing coverage assumption is load-bearing.","tokens_in":52757,"feed_emoji":"🤖","tokens_out":6743,"duration_ms":65364,"temperature":0.7,"pith_summary":"The paper introduces RL with segment feedback: an episode is split into $m$ segments and the agent receives a reward signal only at the end of each segment, interpolating between per-state-action reward and once-per-trajectory reward. It asks how the number of segments $m$ affects learning, and answers with matching upper and lower regret bounds. For binary feedback, where each segment yields a thumbs-up/down generated by a sigmoid of the segment reward, the regret carries a factor of order $\\exp(H r_{\\max}/(2m))$, so more segments shrink regret exponentially. For sum feedback, where the agent observes the total reward in each segment, the leading regret is $O(|S||A|\\sqrt{HK}\\log(\\cdot))$ and is essentially independent of $m$. The lower bounds show that both behaviors are unavoidable, not artifacts of the algorithms.","feed_headline":"Binary-feedback RL regret decays exponentially as segments grow","feed_subtitle":"More thumbs-up queries per trajectory accelerate learning, while summed segment rewards barely change the regret.","key_machinery":"For binary feedback, the machinery is maximum-likelihood estimation of the reward parameter from sigmoid observations, a Gaussian posterior perturbation scaled by the inverse sigmoid derivative, and the feature covariance matrix of past segments; the exponential factor enters through the quantity $\\alpha = \\exp(H r_{\\max}/m) + \\exp(-H r_{\\max}/m) + 2$, which bounds the inverse derivative. The lower bound uses a KL-divergence/Pinsker argument that turns the sigmoid derivative into the exponential factor. For sum feedback, the machinery treats segment rewards as linear in segment visitation counts and uses E-optimal experimental design: a distribution over policies is chosen to maximize the minimum eigenvalue of the expected segment-feature covariance, then rounded to a discrete initial exploration sequence with the ROUND procedure. This ensures the elliptical norm $\\|\\phi\\|_{(\\Sigma_{k-1})^{-1}}$ is bounded by $1$, which is what removes the $m$-dependence from the leading regret term.","core_discovery":"The central discovery is that the information content of a segment depends on the feedback type. Under binary segment feedback, the decisive quantity is the per-segment reward scale $H r_{\\max}/m$: when it is large, the sigmoid is flat, the observed binary outcomes are almost constant, and distinguishing good from bad actions is exponentially hard; when $m$ increases, the scale drops and learning accelerates. The paper proves this with a Thompson-sampling algorithm whose regret is $\\widetilde{O}(\\exp(H r_{\\max}/(2m)) \\cdot \\mathrm{poly}(|S|,|A|,H) \\cdot \\sqrt{K})$ and a lower bound $\\Omega(\\exp((1/2-c_0)H r_{\\max}/m)\\sqrt{|S||A|mK})$. Under sum feedback, by contrast, an E-optimal-design LinUCB algorithm achieves regret $O(|S||A|\\sqrt{HK}\\log(\\cdot) + (z^*)^2 H^5 \\log(\\cdot) + |S||A|H)$, with a matching $\\Omega(\\sqrt{|S||A|HK})$ lower bound: splitting the trajectory into segments neither helps nor hurts in leading order, because the smaller per-segment feature vectors shrink the covariance and offset the extra observations.","pith_inferences":["One extension the paper leaves implicit is unequal segment lengths; under sum feedback the noise variance per segment would vary, so the cancellation between more observations and smaller features may break, giving a testable departure from the flat-in-$m$ bound.","The exponential binary-feedback penalty is driven by the per-segment reward scale, so a practical design implication not drawn by the paper is to normalize or clip segment rewards so human queries fall in the steep part of the sigmoid.","The lower-bound constructions use bandit-like MDPs with absorbing states, suggesting the exponential factor should also appear in contextual or partially observable variants whenever per-segment reward scale is large; this is a conjecture an interested reader could test.","A natural next experiment would vary $H r_{\\max}/m$ directly while holding $m$ fixed to confirm that the binary-feedback regret tracks the exponential factor rather than $m$ alone."],"forward_implications":["Under binary feedback, doubling $m$ replaces $\\exp(-H r_{\\max}/(2m))$ with a much smaller factor, so even a modest number of segments per trajectory yields most of the statistical benefit of fine-grained feedback.","Under sum feedback, there is no leading-order statistical penalty for using fewer, longer segments, so algorithms can operate on trajectory-level totals without sacrificing regret order when $m$ is small.","At $m=1$, sum segment feedback reduces to trajectory feedback, and the E-optimal-design analysis improves the existing trajectory-feedback regret by a factor of $\\sqrt{H}$.","The binary lower bound applies to any algorithm, not just SegBiTS, so the exponential dependence on $H r_{\\max}/m$ is inherent to the information structure of binary segment feedback.","Together the two results give a practical rule-of-thumb: for binary human feedback, split trajectories into more segments; for numerical summed rewards, segment count is not a major lever."],"supporting_citations":[{"why":"Provides the trajectory sum-feedback baseline that segment feedback generalizes, and its martingale-based analysis cannot be applied to dependent segments.","marker":"Efroni et al., 2021"},{"why":"Sets the alternative binary trajectory-feedback formulation whose non-Markovian optimal policies and inefficient algorithms motivate the present Markovian, Thompson-sampling approach.","marker":"Chatterji et al., 2021"},{"why":"Supplies the linear-bandit confidence ellipsoid and LinUCB machinery on which E-LinUCB and the sum-feedback concentration bounds are built.","marker":"Abbasi-Yadkori et al., 2011"},{"why":"Provides the logistic-bandit MLE concentration and self-concordance lemmas used to bound the reward estimate under binary sigmoid feedback.","marker":"Faury et al., 2020"},{"why":"Defines E-optimal experimental design, the optimization over policy distributions that initializes exploration in E-LinUCB.","marker":"Pukelsheim, 2006"},{"why":"Supplies the ROUND procedure that converts the E-optimal policy distribution into a discrete sampling sequence with a $(1+\\gamma)$ approximation guarantee.","marker":"Allen-Zhu et al., 2021"},{"why":"Provides the bandit lower-bound lemma used to derive both the exponential binary-feedback lower bound and the $\\sqrt{|S||A|HK}$ sum-feedback lower bound.","marker":"Auer et al., 2002"},{"why":"Supplies variance-aware KL transition concentration and Bernstein-type bounds used to control visitation estimation error when transitions are unknown.","marker":"Ménard et al., 2021"},{"why":"Provides the matrix Bernstein inequality used to concentrate the initial sampling covariance in the E-optimal-design analysis.","marker":"Tropp et al., 2015"}],"fun_headline_variants":["Binary segment feedback cuts RL regret exponentially","Sum feedback segments don't speed up RL learning","Binary segments exponential win, sum segments no gain","Segment count: binary feedback helps, sum doesn't","Splitting rewards: binary accelerates, sums don't"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The sum-feedback result with known transitions requires at least one distribution over policies whose expected segment-feature covariance matrix is invertible, meaning every state-action pair must be reachable by some policy; the theorem statement itself does not explicitly include this coverage condition.","fun_headline_variants_meta":{"raw":{"variants":["Binary segment feedback cuts RL regret exponentially","Sum feedback segments don't speed up RL learning","Binary segments exponential win, sum segments no gain","Segment count: binary feedback helps, sum doesn't","Splitting rewards: binary accelerates, sums don't"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000237,"raw_usage":{"total_tokens":1546,"prompt_tokens":1023,"completion_tokens":523,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":639,"completion_tokens_details":{"reasoning_tokens":451}},"tokens_in":639,"tokens_out":523,"duration_ms":5550,"temperature":1.0,"reasoning_tokens":451,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T14:09:30.046671+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"On the binary side, run SegBiTS on the paper's experimental MDP with $H=100$, $r_{\\max}=0.5$ for $m=1$ and $m=2$; the claimed bound predicts the $m=1$ regret exceeds the $m=2$ regret by a factor on the order of $\\exp(H r_{\\max}/2)=\\exp(25)\\approx 7.2\\times 10^{10}$, so a measured ratio orders of magnitude smaller would falsify the exponential dependence. On the sum side, execute E-LinUCB on an MDP where the E-optimal design is singular, e.g., some state-action pair is unreachable under every policy; the theorem as stated promises the flat-in-$m$ bound but the algorithm has no defined $K_0$, revealing that the missing coverage assumption is load-bearing.","supporting_citations":[{"cited_title":"Reinforcement learning with trajectory feedback","cited_arxiv_id":null,"evidence_quote":"Provides the trajectory sum-feedback baseline that segment feedback generalizes, and its martingale-based analysis cannot be applied to dependent segments."},{"cited_title":"On the theory of reinforcement learning with once-per-episode feedback","cited_arxiv_id":null,"evidence_quote":"Sets the alternative binary trajectory-feedback formulation whose non-Markovian optimal policies and inefficient algorithms motivate the present Markovian, Thompson-sampling approach."},{"cited_title":"Improved algorithms for linear stochastic bandits","cited_arxiv_id":null,"evidence_quote":"Supplies the linear-bandit confidence ellipsoid and LinUCB machinery on which E-LinUCB and the sum-feedback concentration bounds are built."},{"cited_title":"Optimal design of experiments","cited_arxiv_id":null,"evidence_quote":"Defines E-optimal experimental design, the optimization over policy distributions that initializes exploration in E-LinUCB."},{"cited_title":"Near-optimal discrete optimization for experimental design: A regret minimization approach","cited_arxiv_id":null,"evidence_quote":"Supplies the ROUND procedure that converts the E-optimal policy distribution into a discrete sampling sequence with a $(1+\\gamma)$ approximation guarantee."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the bandit lower-bound lemma used to derive both the exponential binary-feedback lower bound and the $\\sqrt{|S||A|HK}$ sum-feedback lower bound."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the matrix Bernstein inequality used to concentrate the initial sampling covariance in the E-optimal-design analysis."}],"review_version":1}