mlsanityData to 14 Oct 2026

Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedback

arXiv 2405.07637 ↗First posted 13 May 2024cs.LGcited by 10

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

In many real-world applications, it is hard to provide a reward signal in each step of a Reinforcement Learning (RL) process and more natural to give feedback when an episode ends. To this end, we study the recently proposed model of RL with Aggregate Bandit Feedback (RL-ABF), where the agent only observes the sum of rewards at the end of an episode instead of each reward individually. Prior work studied RL-ABF only in tabular settings, where the number of states is assumed to be small. In this paper, we extend ABF to linear function approximation and develop two efficient algorithms with near-optimal regret guarantees: a value-based optimistic algorithm built on a new randomization technique with a Q-functions ensemble, and a policy optimization algorithm that uses a novel hedging scheme over the ensemble.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 32 of its 42 references that are in the map. First posted on arXiv 13 May 2024.

Builds on

32 of 42 references.

References · 32

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2017Proximal Policy Optimization Algorithmscited by 15,215
  3. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,885
  4. 2020Learning to summarize from human feedbackcited by 2,588
  5. 2015Trust Region Policy Optimizationcited by 2,580
  6. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  7. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  8. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
  9. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 181
  10. 2014Generalization and Exploration via Randomized Value Functionscited by 112
  11. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 106
  12. 2023Is RLHF More Difficult than Standard RL?cited by 96
20 more
  1. 2019Learning Adversarial MDPs with Bandit Feedback and Unknown Transitioncited by 85
  2. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 81
  3. 2019Online Convex Optimization in Adversarial Markov Decision Processescited by 79
  4. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  5. 2019Learning Linear-Quadratic Regulators Efficiently with only √T Regretcited by 70
  6. 2021Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonusescited by 52
  7. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  8. 2023Making RL with Preference-based Feedback Efficient via Randomizationcited by 46
  9. 2020Reinforcement Learning with Trajectory Feedbackcited by 40
  10. 2020Learning Adversarial Markov Decision Processes with Delayed Feedbackcited by 33
  11. 2021On the Theory of Reinforcement Learning with Once-per-Episode Feedbackcited by 32
  12. 2013Learning Trajectory Preferences for Manipulators via Iterative Improvementcited by 31
  13. 2022Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 22
  14. 2021Near-Optimal Randomized Exploration for Tabular Markov Decision Processescited by 15
  15. 2023Rate-Optimal Policy Optimization for Linear Markov Decision Processescited by 14
  16. 2022Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Rewardcited by 13
  17. 2021Online Markov Decision Processes with Aggregate Bandit Feedbackcited by 10
  18. 2023Delay-Adapted Policy Optimization and Improved Regret for Adversarial MDP with Delayed Bandit Feedbackcited by 6
  19. 2023Model-free Posterior Sampling via Learning Rate Randomizationcited by 6
  20. 2021Optimism and Delays in Episodic Reinforcement Learningcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 3; 2026: 5.

10 papers.

  1. 2024Multi-turn Reinforcement Learning from Preference Human Feedbackcited by 67
  2. 2025Do We Need to Verify Step by Step? Rethinking Process Supervision from a Theoretical Perspectivecited by 17
  3. 2025Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limitscited by 7
  4. 2024Warm-up Free Policy Optimization: Improved Regret in Linear Markov Decision Processescited by 5
  5. 2025Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedbackcited by 2
  6. 2026Near-Optimal Regret for Policy Optimization in Contextual MDPs with General Offline Function Approximationcited by 2
  7. 2026Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Lossescited by 0
  8. 2026Learning Kernel-Based MDPs from Episodic Preferential Feedbackcited by 0
  9. 2026When Does Trajectory-Level Supervision Permit Efficient Offline Reinforcement Learning?cited by 0
  10. 2026Provably Efficient Reinforcement Learning in Continuous-Time Episodic MDPs with Poisson Decision Epochscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs
  2. 2026Learning Markov Decision Processes under Fully Bandit Feedback
  3. 2024Provably Efficient Infinite-Horizon Average-Reward Reinforcement Learning with Linear Function Approximation
  4. 2025Optimistically Optimistic Exploration for Provably Efficient Infinite-Horizon Reinforcement and Imitation Learning
  5. 2021Fast Rates for the Regret of Offline Reinforcement Learning
  6. 2024Prior-dependent analysis of posterior sampling reinforcement learning with function approximation
  7. 2024Optimistic Q-learning for average reward and episodic reinforcement learning
  8. 2025Provably Efficient RL under Episode-Wise Safety in Constrained MDPs with Linear Function Approximation