mlsanityData to 14 Oct 2026

On the Theory of Reinforcement Learning with Once-per-Episode Feedback

arXiv 2105.14363 ↗First posted 29 May 2021cs.LG cs.AI stat.MLcited by 32

Not on the map. Why?

Abstract (arXiv)

We study a theory of reinforcement learning (RL) in which the learner receives binary feedback only once at the end of an episode. While this is an extreme test case for theory, it is also arguably more representative of real-world applications than the traditional requirement in RL practice that the learner receive feedback at every time step. Indeed, in many real-world applications of reinforcement learning, such as self-driving cars and robotics, it is easier to evaluate whether a learner's complete trajectory was either "good" or "bad," but harder to provide a reward signal at each step. To show that learning is possible in this more challenging setting, we study the case where trajectory labels are generated by an unknown parametric model, and provide a statistically and computationally efficient algorithm that achieves sublinear regret.

Key facts. Cited by 32 papers in the map (data through 14 Oct 2026). Builds on 23 of its 55 references that are in the map. First posted on arXiv 29 May 2021.

Builds on

23 of 55 references.

References · 23

  1. 2014Adam: A Method for Stochastic Optimizationcited by 37,240
  2. 2017Deep reinforcement learning from human preferencescited by 3,912
  3. 2015End-to-End Training of Deep Visuomotor Policiescited by 875
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  7. 2018Time-uniform, nonparametric, nonasymptotic confidence sequencescited by 229
  8. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  9. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  10. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  11. 2020Improved Optimistic Algorithms for Logistic Banditscited by 118
  12. 2016Why is Posterior Sampling Better than Optimism for Reinforcement Learning?cited by 117
11 more
  1. 2019Non-Asymptotic Gap-Dependent Regret Bounds for Tabular MDPscited by 105
  2. 2020Preference-based Reinforcement Learning with Finite-Time Guaranteescited by 65
  3. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learningcited by 56
  4. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  5. 2016On Lower Bounds for Regret in Reinforcement Learningcited by 40
  6. 2020Reinforcement Learning with Trajectory Feedbackcited by 40
  7. 2019Tight Regret Bounds for Model-Based Reinforcement Learning with Greedy Policiescited by 39
  8. 2019On the Performance of Thompson Sampling on Logistic Banditscited by 32
  9. 2020Self-Concordant Analysis of Generalized Linear Bandits with Forgettingcited by 29
  10. 2021Confidence-Budget Matching for Sequential Budgeted Learningcited by 12
  11. 2021Online Markov Decision Processes with Aggregate Bandit Feedbackcited by 10

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 3; 2022: 5; 2023: 5; 2024: 9; 2025: 5; 2026: 5.

32 papers.

Sort:

By area:

  1. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisonscited by 247
  2. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 106
  3. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 81
  4. 2024Multi-turn Reinforcement Learning from Preference Human Feedbackcited by 67
  5. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
  6. 2021Learning Long-Term Reward Redistribution via Randomized Return Decompositioncited by 33
  7. 2022Challenging Common Assumptions in Convex Reinforcement Learningcited by 30
  8. 2024Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferencescited by 27
  9. 2023Submodular Reinforcement Learningcited by 23
  10. 2026SOP: A Scalable Online Post-Training System for Vision-Language-Action Modelscited by 21
  11. 2024Corruption Robust Offline Reinforcement Learning with Human Feedbackcited by 20
  12. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
20 more
  1. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  2. 2025ReDit: Reward Dithering for Improved LLM Policy Optimizationcited by 8
  3. 2025Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limitscited by 7
  4. 2026Coverage Improvement and Fast Convergence of On-policy Preference Learningcited by 6
  5. 2022Integrating Reward Maximization and Population Estimation: Sequential Decision-Making for Internal Revenue Service Audit Selectioncited by 5
  6. 2024Test-Time Regret Minimization in Meta Reinforcement Learningcited by 5
  7. 2022Reinforcement Learning with a Terminatorcited by 4
  8. 2023Hindsight-DICE: Stable Credit Assignment for Deep Reinforcement Learningcited by 4
  9. 2024Stop Relying on No-Choice and Do not Repeat the Moves: Optimal, Efficient and Practical Algorithms for Assortment Optimizationcited by 4
  10. 2024Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysiscited by 4
  11. 2025Reinforcement Learning with Segment Feedbackcited by 4
  12. 2021Neural Pseudo-Label Optimism for the Bank Loan Problemcited by 3
  13. 2023Conditions on Preference Relations that Guarantee the Existence of Optimal Policiescited by 3
  14. 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
  15. 2026Policy Gradient Primal-Dual Method for Safe Reinforcement Learning from Human Feedbackcited by 2
  16. 2024A Theoretical Framework for Partially Observed Reward-States in RLHFcited by 1
  17. 2026Learning Markov Decision Processes under Fully Bandit Feedbackcited by 1
  18. 2026Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferencescited by 1
  19. 2024Preference-Guided Reinforcement Learning for Efficient Explorationcited by 0
  20. 2025Reinforcement Learning from Multi-level and Episodic Human Feedbackcited by 0