Research map / Reinforcement learning / MDPs and planning
Reinforcement Learning with Segment Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies episodic RL where each episode is split into m segments and the agent gets only binary or sum reward feedback per segment, proving that regret decays exponentially in m under binary feedback but is essentially independent of m under sum feedback.
Problem
Reinforcement learning when reward feedback is given only once per segment of an episode (between per-step and per-trajectory feedback), and how the number of segments m affects regret under binary and sum feedback.
Approach
Unifies per-step and trajectory feedback into segment feedback; uses Thompson-sampling style MLE for binary feedback (exponential dependence on Hr_max/m via sigmoid derivative) and E-optimal experimental design with LinUCB for sum feedback, yielding near-optimal regret independent of m.
Key results
- Under binary feedback, regret of SegBiTS scales as exp(Hr_max/(2m)) times sqrt(K), so regret decays exponentially in m; a matching-form lower bound Omega(exp((1/2-c0)Hr_max/m) sqrt(|S||A|mK)) is proved.
- Under sum feedback, E-optimal-design LinUCB (EDLinUCBSeg) achieves O(|S||A| sqrt(HK)) regret independent of m (up to log terms), improving the trajectory-feedback result by sqrt(H).
- Sum-feedback lower bound Omega(sqrt(|S||A|HK)) matches the upper bound in H and m, showing m does not reduce regret in essence.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the number of segments m | RL with binary segment feedback · Binary segment feedback | regret: a dependency on \exp(\frac{Hr_{\max}}{2m}) | Helped |
| Increase the number of segments m | RL with sum segment feedback · Sum segment feedback | regret | No clear effect |
| Use E-optimal design with initial exploration | edlinucbseg versus prior trajectory-feedback algorithm · Sum trajectory feedback (m=1) | regret: by a factor of \sqrt{H} | Helped |
| Increase the length of each segment H/m | edlinucbseg and linucbtranseg · Sum segment feedback | regret | Hurt |
Surprising findings
- Under sum feedback, increasing the number of segments m does not meaningfully reduce regret, contrary to the intuition that more feedback helps.
Limitations
- Analysis restricted to equal-length segments and tabular settings.
- Sum-feedback algorithms with known/unknown transitions are computationally inefficient.
- Experiments use small synthetic MDPs only.
Experimental setup
Benchmarks: custom tabular MDP instances
Metrics: cumulative regret
Baselines: RL with binary trajectory feedback algorithms RL with sum trajectory feedback algorithms
Builds on: Thompson sampling LinUCB E-optimal experimental design RL with trajectory feedback
Closest papers by meaning
- Minimax Optimal Regret Bound for Reinforcement Learning with Trajectory Feedback (ICML 2025 · similarity 0.90)
- Towards Theoretical Understanding of Sequential Decision Making with Preference Feedback (ICML 2025 · similarity 0.88)
- Efficient Preference-Based Reinforcement Learning: Randomized Exploration meets Experimental Design (NeurIPS 2025 · similarity 0.88)
- A Theoretical Framework for Partially-Observed Reward States in RLHF (ICLR 2025 · similarity 0.87)
- Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback (NeurIPS 2025 · similarity 0.86)
- Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.