# Reinforcement Learning with Trajectory Feedback

arXiv: https://arxiv.org/abs/2008.06036 · HTML: https://mlsanity.com/paper/2008.06036/

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Aug 2020.

## Built on by (most cited first, 30 of 40)

- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Dueling RL: Reinforcement Learning with Trajectory Preferences](https://mlsanity.com/paper/2111.04850/) (2021)
- [Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximation](https://mlsanity.com/paper/2205.11140/) (2022)
- [Multi-turn Reinforcement Learning from Preference Human Feedback](https://mlsanity.com/paper/2405.14655/) (2024)
- [Learning Long-Term Reward Redistribution via Randomized Return Decomposition](https://mlsanity.com/paper/2111.13485/) (2021)
- [On the Theory of Reinforcement Learning with Once-per-Episode Feedback](https://mlsanity.com/paper/2105.14363/) (2021)
- [Minimax Regret for Stochastic Shortest Path](https://mlsanity.com/paper/2103.13056/) (2021)
- [Challenging Common Assumptions in Convex Reinforcement Learning](https://mlsanity.com/paper/2202.01511/) (2022)
- [Provable RL with Exogenous Distractors via Multistep Inverse Dynamics](https://mlsanity.com/paper/2110.08847/) (2021)
- [Learning Energy Decompositions for Partial Inference of GFlowNets](https://mlsanity.com/paper/2310.03301/) (2023)
- [Latent Reward: LLM-Empowered Credit Assignment in Episodic Reinforcement Learning](https://mlsanity.com/paper/2412.11120/) (2024)
- [Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward](https://mlsanity.com/paper/2206.06426/) (2022)
- [Would I have gotten that reward? Long-term credit assignment by counterfactual contribution analysis](https://mlsanity.com/paper/2306.16803/) (2023)
- [Confidence-Budget Matching for Sequential Budgeted Learning](https://mlsanity.com/paper/2102.03400/) (2021)
- [Reinforcement Learning with History-Dependent Dynamic Contexts](https://mlsanity.com/paper/2302.02061/) (2023)
- [Online Markov Decision Processes with Aggregate Bandit Feedback](https://mlsanity.com/paper/2102.00490/) (2021)
- [Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback](https://mlsanity.com/paper/2405.07637/) (2024)
- [Consistent Aggregation of Objectives with Diverse Time Preferences Requires Non-Markovian Rewards](https://mlsanity.com/paper/2310.00435/) (2023)
- [Assessing the Zero-Shot Capabilities of LLMs for Action Evaluation in RL](https://mlsanity.com/paper/2409.12798/) (2024)
- [Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits](https://mlsanity.com/paper/2505.20268/) (2025)
- [Towards Fairness in Personalized Ads Using Impression Variance Aware Reinforcement Learning](https://mlsanity.com/paper/2306.03293/) (2023)
- [Test-Time Regret Minimization in Meta Reinforcement Learning](https://mlsanity.com/paper/2406.02282/) (2024)
- [Reinforcement Learning with a Terminator](https://mlsanity.com/paper/2205.15376/) (2022)
- [Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysis](https://mlsanity.com/paper/2406.07455/) (2024)
- [Reinforcement Learning with Segment Feedback](https://mlsanity.com/paper/2502.01876/) (2025)
- [Zero-Shot LLMs in Human-in-the-Loop RL: Replacing Human Feedback for Reward Shaping](https://mlsanity.com/paper/2503.22723/) (2025)
- [Efficient Preference-Based Reinforcement Learning: Randomized Exploration Meets Experimental Design](https://mlsanity.com/paper/2506.09508/) (2025)
- [Iterative Reward Shaping using Human Feedback for Correcting Reward Misspecification](https://mlsanity.com/paper/2308.15969/) (2023)
- [Episodic Return Decomposition by Difference of Implicitly Assigned Sub-Trajectory Reward](https://mlsanity.com/paper/2312.10642/) (2023)
- [Beyond Simple Sum of Delayed Rewards: Non-Markovian Reward Modeling for Reinforcement Learning](https://mlsanity.com/paper/2410.20176/) (2024)

## Abstract (arXiv)

The standard feedback model of reinforcement learning requires revealing the reward of every visited state-action pair. However, in practice, it is often the case that such frequent feedback is not available. In this work, we take a first step towards relaxing this assumption and require a weaker form of feedback, which we refer to as trajectory feedback. Instead of observing the reward obtained after every action, we assume we only receive a score that represents the quality of the whole trajectory observed by the agent, namely, the sum of all rewards obtained over this trajectory. We extend reinforcement learning algorithms to this setting, based on least-squares estimation of the unknown reward, for both the known and unknown transition model cases, and study the performance of these algorithms by analyzing their regret. For cases where the transition model is unknown, we offer a hybrid optimistic-Thompson Sampling approach that results in a tractable algorithm.