PaperlayerView exact revision on arXiv

Source-linked AI summary

Reinforcement Learning with Segment Reward Feedback under Linear Function Approximation

Fengxu Liu, Siwei Wang, Gal Dalal, Shie Mannor, Yihan Du

arXiv:2610.08271v1cs.LG

TL;DR

Fine-grained rewards can be costly to collect, while episode-level rewards may be too aggregated, leaving open how segment granularity and partition choice affect learning in large state spaces. The paper develops regret-guaranteed algorithms for segment feedback in linear MDPs across feedback types, transition settings, and segmentation schemes. Its results show that finer segmentation substantially reduces regret under binary feedback, but not much under sum feedback; for variable binary segments, equal segmentation performs best under the stated analysis.

  • Problem

    It remains unclear how efficiently segment rewards can be exploited in linear MDPs, how segment granularity affects learning, and whether feature-dependent partitions improve learning, despite the need to handle large state spaces and sparse feedback.

    Source: §1 · p. 2

  • Method

    The paper develops regret-analyzed algorithms for binary and sum segment feedback in linear MDPs, covering equal segments with known or unknown transitions and variable segments with binary feedback.

    Source: §1 · pp. 3–4

  • Results

    Under binary feedback, increasing the number of segments significantly reduces regret, while under sum feedback it does not improve learning much; for variable binary segments, equal segmentation minimizes regret under the common elliptical potential analysis.

    Source: §1 · p. 4, §8 · p. 25

  • Takeaways & Limitations

    Segment feedback provides an intermediate feedback model between state-action-wise and trajectory-level signals, and the reported results distinguish how segmentation granularity affects binary versus sum feedback.

    Source: §8 · p. 25

    Whether equal segmentation is intrinsically preferable or favored by the current elliptical-potential analysis remains unresolved; the authors call for stronger tools and a lower bound.

    Source: §8 · pp. 25–26

Abstract

from arXiv · show

Classical reinforcement learning (RL) assumes that a reward is observed for every visited state-action pair. However, in real-world applications such as autonomous driving, such fine-grained feedback can be costly or difficult to collect, whereas trajectory-level feedback may be too sparse for efficient learning. To provide a general feedback model bridging these two extremes and handle large state spaces, we study RL with segment reward feedback under linear function approximation. Our work answers how the granularity of segment feedback and the choice of segmentation influence learning. For equal-length segments with known transitions, we design algorithms $\bitssegd$ and $\edlinucbsegd$ for binary and sum feedback types, respectively. They adopt posterior sampling with planning to achieve computational efficiency and the E-optimal experimental design to attain near-optimality. Nearly matching lower bounds are established. For equal-length segments with unknown transitions, we develop a unified $\seglsvits$ framework with two instantiations for binary and sum feedback, which carefully integrates the posterior estimated reward parameters into least-squares value iteration. These results reveal a fundamental insight: under binary feedback, increasing the number of segments significantly reduces the regret through an exponential factor, while surprisingly, under sum feedback, the granularity of segments does not affect learning much. Finally, to investigate whether segmenting according to state-action features can further expedite learning, we design an algorithm $\uneqsegbitsd$ that allows arbitrary segmentations. The resulting regret bound shows that under the usual elliptical potential analysis, the influence of state-action features on the regret appears only through logarithmic factors, and equal segmentation achieves the best performance.

1 Introduction

The paper studies segment reward feedback in linear MDPs to understand how feedback type, segment granularity, transition knowledge, and segmentation affect regret. It develops algorithms and regret guarantees for equal and variable segments, with binary feedback benefiting from finer segmentation while sum feedback does not improve much.

1 Introduction

  • Segment feedback addresses a trade-off: per-state-action rewards can be costly to obtain, while a trajectory-level signal aggregates an entire episode and may obscure which behavior helped or hurt.The paper asks how segment granularity and segmentation choice influence learning in linear MDPs, extending beyond tabular segment-feedback results and whole-trajectory feedback with function approximation.Source: §1 · pp. 2–3
  • The work frames segment feedback as an intermediate model between state-action-wise rewards and a single trajectory-level signal, studying binary and sum feedback with known and unknown transitions.Binary feedback is a Bernoulli outcome generated by a segment’s cumulative reward; sum feedback is a noisy observation of that cumulative reward.Source: §1 · p. 3
  • Unknown transitions create a scale mismatch between aggregate-segment reward uncertainty and state-action-wise transition uncertainty, complicating efficient optimism-based learning.Per-step bonuses can be incompatible with the reward covariance, segment-level bonuses are history dependent, and omitting reward bonuses can break optimism.Source: §1 · p. 3
  • For equal-length segments with known transitions, SegBiTS-d uses posterior sampling with efficient linear MDP planning, while E-LinUCB-d uses E-optimal design for sum feedback.The paper also establishes dimension-dependent lower bounds for both feedback types, with the binary lower bound showing the exponential dependence is unavoidable and the sum-feedback bound validating near-optimality.Source: §1 · p. 4
  • For equal-length segments with unknown transitions, Seg-LSVI-TS integrates posterior reward-parameter sampling with optimistic least-squares value iteration for binary and sum feedback.The framework addresses the mismatch between segment-level reward uncertainty and state-action-wise value iteration; transition learning adds polynomial terms while preserving the feedback-type insights.Source: §1 · p. 4
  • Under binary feedback, increasing the number of segments reduces regret significantly; under sum feedback, increasing segments does not improve learning much, and equal segmentation performs best in the variable-segment analysis.The variable-segment regret bound places the influence of realized state-action features only in logarithmic factors under the common elliptical potential analysis.Source: §1 · p. 4
  • The paper extends equal-length segments to adaptive, episode-dependent partitions with binary feedback through Uneq-SegBiTS-d, accounting for each segment’s sigmoid curvature.Its guarantee indicates that feature-dependent segmentation does not substantially benefit learning under the common elliptical potential analysis.Source: §1 · p. 4

2 Related Work

Prior sparse-feedback RL studied trajectory-level signals and segment feedback, but results were divided between tabular models and function approximation. This paper addresses segment feedback in linear MDPs, where sparse observations can be combined with generalization across large state spaces.

2.1 RL with Sparse Feedback

  • Trajectory-level feedback replaces per-step rewards with one episode-level signal; prior work studied sum feedback, binary feedback, and aggregate losses in episodic tabular RL.The cited trajectory-feedback work includes Efroni et al. (2021), Zhang et al. (2025), and Chatterji et al. (2021); other work considers adversarial aggregate losses and fully bandit feedback.Source: §2.1 · pp. 4–5
  • Prior segment or bagged-feedback work includes empirical methods without regret guarantees, transition-structure modeling, and tabular equal-length segments with regret guarantees.Du et al. (2025) studied equal-length segments with both sum and binary feedback under known and unknown transitions.Source: §2.1 · p. 6
  • Earlier segment-feedback guarantees primarily addressed tabular MDPs, while function-approximation work focused on whole-trajectory signals; a general segment-level treatment under function approximation remained unresolved.The paper positions its contribution as bridging these research lines with binary and sum feedback in linear MDPs, lower bounds, and variable binary segments.Source: §2.1 · p. 6, §2.2 · p. 6

2.2 RL with Linear Function Approximation

  • Linear MDPs represent transitions using known state-action features and support optimism-based and randomized exploration methods for large or continuous state spaces.The literature includes LSVI-UCB and subsequent work with improved dimension and horizon dependence; linear mixture MDPs are a related but distinct model.Source: §2.2 · p. 6
  • Linear-function-approximation work typically assumes individually observed rewards, leaving sparse segment observations unaddressed; this paper studies binary and sum segment feedback in linear MDPs.The contribution also includes dimension-dependent lower bounds and an extension to variable segments with binary feedback.Source: §2.2 · p. 6

3 Problem Formulation

The formulation studies episodic linear MDPs where segment-end rewards replace per-step observations, covering equal-length binary and sum feedback and variable binary segments. Learning is evaluated by cumulative regret, and binary feedback is used to infer rewards while optimizing expected cumulative reward.

3 Problem Formulation

  • The framework replaces per-step reward observations with segment-level feedback, covering equal-length binary and sum feedback and variable binary segments.It studies episodic reinforcement learning under linear function approximation.Source: §3 · p. 7

3.1 Episodic Linear MDPs

  • The linear MDP setup uses a known feature map, an unknown reward parameter, and either known or unknown transitions.State-action pairs in the realized trajectory are observable, while reward information arrives through segment feedback.Source: §3.1 · pp. 7–8

3.2 Equal-length Segment Feedback

  • Equal-length feedback divides each episode into m segments of length H/m, with binary outcomes depending on each segment’s cumulative reward.The formulation assumes m divides H.Source: §3.2 · p. 8
  • Under sum feedback, the agent observes each segment’s aggregate random reward rather than the unobserved instantaneous rewards.The instantaneous reward noise is zero-mean, 1-sub-Gaussian, and independent of the transition distribution.Source: §3.2 · pp. 8–9

3.3 Variable and Binary Segment Feedback

  • Variable binary segmentation lets the algorithm choose each episode’s segment count and partition after observing its trajectory.The environment reveals one binary outcome for each segment after the partition is set.Source: §3.3 · p. 9

3.4 Learning Objective

  • The learning objective is to minimize cumulative regret over K episodes.The same objective applies across the feedback models considered.Source: §3.4 · p. 9
  • Rather than maximizing the probability of binary feedback one, the paper uses binary feedback to infer reward and maximize expected cumulative reward.This distinction permits restricting attention to Markovian policies and designing computationally efficient algorithms.Source: §3.4 · p. 9

4 Equal-length Segment Feedback with Known Transitions

With known transitions, this section studies equal-length binary and sum segment feedback, using algorithms and regret bounds to characterize how segmentation affects learning.

4 Equal-length Segment Feedback with Known Transitions

  • The known-transition setting isolates the statistical challenge of learning the reward parameter from the difficulty of learning transition dynamics.The section studies equal-length segments with both binary and sum feedback.Source: §4 · p. 10

4.1.1 Algorithm SegBiTS-d and Regret Upper Bound

  • SegBiTS-d perturbs logistic reward estimates with segment-uncertainty-calibrated Gaussian noise, then plans under sampled rewards.At each episode, it estimates the reward parameter from past binary feedback, samples a posterior parameter, and plans in the linear MDP.Source: §4.1 · p. 10, §4.1.1 · pp. 10–11

4.1 Binary Feedback

  • Increasing m rapidly lowers binary-feedback regret through sigmoid curvature, while a lower bound makes the exponential segment-length dependence unavoidable.Long segments place sigmoid outputs near 0 or 1, where the curve is nearly flat and feedback is less informative.Source: §4.1.1 · pp. 11–12, §4.1.2 · p. 12

4.1.2 Regret Lower Bound

  • The binary-feedback lower bound establishes that the exponential dependence on segment length in the regret guarantee is intrinsic.The proof uses hard instances where segment rewards fall in the sigmoid's nearly flat region, making neighboring reward parameters difficult to distinguish.Source: §4.1.2 · p. 12

4.2.1 Algorithm E-LinUCB-d and Regret Upper Bound

  • For sum feedback, E-LinUCB-d uses E-optimal experimental design to condition the segment covariance matrix and achieves a near-optimal regret guarantee.Its initial exploration phase secures a well-conditioned covariance matrix before regularized least squares and optimistic policy selection.Source: §4.2 · p. 14, §4.2.1 · pp. 14–15

4.2 Sum Feedback

  • Under sum feedback, increasing m does not substantially reduce regret because more observations are offset by smaller segment features.The resulting dependence on m is only logarithmic, and the lower bound confirms that essential regret is independent of m.Source: §4.2.1 · p. 15, §4.2.2 · p. 16

4.2.2 Regret Lower Bound

  • The sum-feedback lower bound nearly matches E-LinUCB-d's upper bound and confirms that essential regret is independent of m.Thus, unlike binary feedback, finer segmentation does not substantially reduce regret under sum feedback.Source: §4.2.2 · p. 16

5 Equal-length Segment Feedback with Unknown Transitions

For unknown transitions, Seg-LSVI-TS combines segment-level reward estimation with step-wise value iteration for binary and sum feedback. Its regret bounds show that segment granularity matters differently across the two feedback types.

5.1 A Unified Seg-LSVI-TS Framework

  • Seg-LSVI-TS couples segment-level reward sampling with step-wise least-squares value iteration to handle reward and transition uncertainty together.The framework uses feedback-specific logistic or linear regression for reward estimation, then integrates estimated reward parameters into optimistic value iteration.Source: §5 · p. 16, §5.1 · p. 18
  • The framework addresses the mismatch between segment-level reward uncertainty and step-wise value iteration by handling reward uncertainty at the segment level and transition uncertainty at the step level.This coupling avoids an explicit within-segment-transition-dependent reward bonus in the Bellman recursion.Source: §5.1 · pp. 16–18

5.2 Binary Feedback

  • When binary-feedback reward learning dominates, increasing the number of segments reduces regret because its reward-learning term depends exponentially on segment length.Learning unknown transitions contributes an additional polynomial term.Source: §5.2 · p. 19

5.3 Sum Feedback

  • Under sum feedback, the regret bound has no explicit dependence on the number of segments, so finer segmentation does not substantially reduce regret.The reward-learning error is polynomial in problem parameters, while the higher-order term comes from learning unknown transitions.Source: §5.3 · pp. 20–21

6 Variable and Binary Segment Feedback with Known Transitions

Uneq-SegBiTS-d supports arbitrary episode-dependent partitions for binary feedback by adapting sigmoid-curvature weights to segment lengths. Its regret analysis makes long segments costly and finds no significant benefit from unequal segmentation under the usual elliptical-potential analysis.

6 Variable and Binary Segment Feedback with Known Transitions

  • Uneq-SegBiTS-d adapts sigmoid-curvature weights to individual segment lengths when constructing its covariance matrix for variable-length binary feedback.The algorithm builds on SegBiTS-d and samples a reward parameter using the resulting confidence geometry.Source: §6 · p. 21
  • A small number of long segments can substantially enlarge the regret bound because each segment incurs an exponential cost determined by its own length.Under the usual elliptical-potential argument, state-action feature effects enter only through logarithmic factors when the feature decomposition aligns with the realized partition.Source: §6 · pp. 22–23
  • When the exponential curvature term dominates, equal segmentation minimizes the dominant segment-dependent regret term for a fixed number of segments.The conclusion is established under standard logistic-regression-based algorithm design and elliptical-potential analysis.Source: §6 · p. 23
  • Whether more advanced algorithms or analyses can exploit state-action features to improve on equal segmentation remains open.The analysis must keep the feature decomposition aligned with the episode-dependent partition used to form the covariance matrix.Source: §6 · p. 23

7 Experiments

Across the reported experiments, finer segments substantially reduce regret for binary feedback, whereas regret changes only mildly with segment count for sum feedback. For variable binary partitions, equal segmentation has the smallest reported regret.

7 Experiments

  • Regret decreases substantially as the number of equal-length segments increases under binary feedback.The reported pattern holds for SegBiTS-d and Bi-Seg-LSVI-TS and matches the exponential dependence on H/m in the theorems.Source: §7 · p. 25
  • Regret varies only mildly with the number of equal-length segments under sum feedback.The reported pattern holds for E-LinUCB-d and Sum-Seg-LSVI-TS.Source: §7 · p. 25
  • Equal segmentation achieves the smallest regret in the variable binary-feedback experiments, while regret generally increases as partitions become more uneven, particularly with a very long segment.The experiments use four or six segments and keep the segment count and partition fixed across episodes.Source: §7 · p. 25

8 Conclusion and Future Work

The paper studies segment reward feedback under linear function approximation and reports different effects of segmentation granularity for binary and sum feedback. For variable binary segments, equal segmentation minimizes regret under the common elliptical-potential analysis; whether that preference is intrinsic or analysis-dependent remains open.

8 Conclusion and Future Work

  • The paper develops algorithms and regret guarantees for equal-length segments with known and unknown transitions, and establishes lower bounds for known transitions.Its main granularity finding is that more segments accelerate learning under binary feedback but do not substantially expedite learning under sum feedback.Source: §8 · p. 25
  • For variable binary segments, the regret bound favors equal segmentation under the common elliptical-potential analysis.The conclusion does not establish whether this preference is intrinsic to the problem or due to limitations of the analysis.Source: §8 · pp. 25–26
  • Determining whether feature-based partitioning can improve learning remains open and calls for methods beyond elliptical-potential analysis and a lower bound.The paper identifies this as future work.Source: §8 · p. 26

Appendix A Experimental Details

The experiments use a 30-state linear MDP for several settings, with a separate two-state instance for known-transition sum feedback. The instances specify their rewards and transitions to compare optimal and suboptimal actions.

Appendix A Experimental Details

  • The main instance has 30 states and 6 actions arranged in five cyclic layers, with six states per layer and a uniformly chosen start in the first layer.The two optimal actions yield rmax; the four suboptimal actions yield zero, and transitions are uniform across the six states in the next layer.Source: Appendix A · p. 27, Figure A1 · p. 27
  • The known-transition sum-feedback experiment uses a separate instance with two states, s+ and s−, and two actions, a+ and a−.The initial state is uniform over the two states; a+ transitions to s+ with probability 0.75, while a− transitions to s− with probability 0.75.Source: Appendix A · pp. 27–28, Figure A2 · p. 28

B.1 Proof for the Regret Upper Bound

The upper-bound proof develops concentration and posterior-sampling arguments for binary feedback, while the lower-bound proof constructs a linear MDP to establish regret hardness under fixed segment feedback.

B.1 Proof for the Regret Upper Bound

  • The binary-feedback upper-bound proof establishes concentration controls for the noise and estimated reward parameter, including a Gaussian anti-concentration result.These controls are stated under event E and are used within the regret-bound argument.Source: §B.1 · pp. 29, 33, 34
  • The upper-bound argument applies the preceding lemmas to control the posterior-sampling analysis and complete the regret proof.The proof identifies its final step as using Lemma B.1.Source: §B.1 · pp. 29–30

B.2 Proof for the Regret Lower Bound

  • The lower-bound proof constructs a linear MDP and analyzes the algorithm’s average action within each fixed-length segment.It defines H/m as the segment length and uses the resulting segment-level actions to derive regret for the constructed instance.Source: §B.2 · pp. 41, 43

C.1 Proof for the Regret Upper Bound

For known transitions with fixed equal-length sum feedback, the upper-bound proof uses E-optimal design and concentration arguments. The lower-bound proof treats a segment reward as a linear-bandit observation and constructs a linear MDP.

C.1 Proof for the Regret Upper Bound

  • The upper-bound proof uses E-optimal design and initial-sampling concentration to control the empirical design matrix, then applies an elliptical-potential argument.The proof also establishes concentration for the parameter estimate under sum feedback and invokes matrix Bernstein.Source: §C.1 · pp. 44, 46, 47

C.2 Proof for the Regret Lower Bound

  • The lower-bound proof views each segment reward as one linear-bandit pull and constructs a linear MDP satisfying the stated assumption.The proof is for known transitions under fixed segment sum feedback.Source: §C.2 · pp. 49–51

D.1 Proof for the Regret Upper Bound of Binary Feedback

This appendix proves the binary-feedback regret upper bound by establishing optimism for sampled-reward auxiliary MDPs and Algorithm 3, then controlling stochastic deviations, reward and transition estimation errors, and cumulative design-matrix terms.

Proof strategy

  • Value estimates are first shown optimistic for auxiliary MDPs built from sampled rewards; Thompson sampling transfers optimism when a sample is optimistic along the optimal policy.The passage states this occurs with high probability.Source: §D.1 · pp. 51–52
  • The regret proof decomposes loss into one-step estimation errors along realized trajectories and controls reward and transition errors through their covariance matrices.The argument yields the desired regret upper bound.Source: §D.1 · p. 52

Technical bounds

  • Under the stated assumptions and events, the proof establishes linear value-function representations and uniform weight bounds for the original and auxiliary MDPs and algorithm estimates.These bounds support the subsequent estimation-error analysis.Source: §D.1 · pp. 53–56

Estimation-error bounds

  • The proof establishes self-normalized concentration for binary-feedback value estimation and upper bounds on estimator error in both the original and auxiliary MDPs.The estimator-error bounds require the specified concentration events and a sufficiently large bonus coefficient.Source: §D.1 · pp. 56, 58, 60

D.1 Proof for the Regret Upper Bound of Binary Feedback

  • Algorithm 3’s selected policy is optimistic: on the stated event, its value at the realized initial state is at least the optimal value.The proof uses the maximum-valued candidate policy and a backward-induction argument.Source: §D.1 · pp. 63–64
  • Azuma–Hoeffding bounds and union bounds control both martingale-difference terms and deviations caused by random initial states across episodes.Each bound holds for all episodes with probability at least 1 − δ′; the proof combines the two concentration events.Source: §D.1 · pp. 65–66
  • The proof bounds cumulative design-matrix terms using the matrix determinant lemma, AM–GM, and Cauchy–Schwarz, then combines three terms in the regret bound.The final probability step uses a union bound.Source: §D.1 · pp. 67–69

D.2 Proof for the Regret Upper Bound of Sum Feedback

This part proves the unknown-transition sum-feedback regret upper bound by combining concentration and estimation-error and optimism arguments, yielding a bound that holds with probability at least 1 − δ.

D.2 Proof for the Regret Upper Bound of Sum Feedback

  • The proof follows essentially the same arguments as Appendix D.1, with notation adjusted for sum feedback and unknown transitions.Source: §D.2 · p. 69
  • Normalizing segment-sum noise by H/m gives 1-sub-Gaussian noise for the concentration argument on sampled reward parameters.The proof applies Lemma 2 of Abbasi-Yadkori et al. (2011) to the normalized features and observations.Source: §D.2 · pp. 69–70
  • On the stated concentration events, the analysis bounds value-function weights and the Algorithm 4 regression weights, with regression targets bounded by 2HBsum.The weight and target bounds are established under ETS and KNorm.Source: §D.2 · p. 71
  • A high-probability least-squares event yields estimator-error bounds for both the original MDP and the auxiliary MDP M(j).These bounds assume ETS, KNorm, and ELS; the proof chooses the bonus coefficient sufficiently large.Source: §D.2 · pp. 72, 73, 75
  • Under the stated event intersection, Lemma D.25 gives a bound for all listed tuples; the supplied inequality fragment includes ≥V ∗ 1 (sk 1).Source: §D.2 · p. 78
  • The proof combines concentration events for trajectory randomness and initial-state randomness using a union bound.For each source of randomness, Azuma–Hoeffding and a union bound yield an event holding for all episodes with probability at least 1 − δ′.Source: §D.2 · p. 81
  • The proof bounds three terms separately: Eq. (D39) for the first, Cauchy–Schwarz with Lemma D.16 for the second, and Cauchy–Schwarz with Lemma D.29 for the third, then combines the bounds.Source: §D.2 · p. 82
  • Setting δ′ = δ/6, the regret bound holds with probability at least 1 −δ.Source: §D.2 · p. 83

Appendix E Proof for Variable Binary Feedback with Known Transitions

The appendix adapts an earlier proof argument to variable binary-feedback segmentations and establishes concentration results under that setting. It also states technical tools for controlling function classes and covering numbers.

Appendix E Proof for Variable Binary Feedback with Known Transitions

  • The proof adapts the Appendix B.1 argument to accommodate different segmentation schemes for variable binary feedback with known transitions.The algorithm chooses the number of segments and their partition after observing the trajectory, but before segment-level feedback is revealed.Source: Appendix E · pp. 83–84
  • Lemma E.2 gives a high-probability concentration result for noises under binary feedback with unequal segments.The stated probability is at least 1 − δ′; the supplied passage does not show the bound itself.Source: Appendix E · p. 84

Appendix F Some Technical Tools

  • The technical tools include a uniform inequality over bounded value functions, expressed using their ε-covering number.The passage states that the inequality holds simultaneously for all T ≥ 0 and all functions in the class.Source: Appendix F · p. 96

Related papers

Loading 2610.08271v1…