mlsanityData to 7 Oct 2026

Provably Feedback-Efficient Reinforcement Learning via Active Reward Learning

arXiv 2304.08944 ↗First posted 18 Apr 2023cs.LG cs.AI math.OCcited by 15

Not on the map. Why?

Abstract (arXiv)

An appropriate reward function is of paramount importance in specifying a task in reinforcement learning (RL). Yet, it is known to be extremely challenging in practice to design a correct reward function for even simple tasks. Human-in-the-loop (HiL) RL allows humans to communicate complex goals to the RL agent by providing various types of feedback. However, despite achieving great empirical successes, HiL RL usually requires too much feedback from a human teacher and also suffers from insufficient theoretical understanding. In this paper, we focus on addressing this issue from a theoretical perspective, aiming to provide provably feedback-efficient algorithmic frameworks that take human-in-the-loop to specify rewards of given tasks. We provide an active-learning-based RL algorithm that first explores the environment without specifying a reward function and then asks a human teacher for only a few queries about the rewards of a task at some state-action pairs. After that, the algorithm guarantees to provide a nearly optimal policy for the task with high probability. We show that, even with the presence of random noise in the feedback, the algorithm only takes widetildeO(HdimR2) queries on the reward function to provide an ε-optimal policy for any ε > 0. Here H is the horizon of the RL environment, and dimR specifies the complexity of the function class representing the reward function. In contrast, standard RL algorithms require to query the reward function for at least Omega(operatornamepoly(d, 1/ε)) state-action pairs where d depends on the complexity of the environmental transition.

Key facts. Cited by 15 papers in the map (data through 7 Oct 2026). Builds on 52 of its 108 references that are in the map. First posted on arXiv 18 Apr 2023.

Builds on

52 of 108 references.

References · 52

  1. 2017Deep reinforcement learning from human preferencescited by 3,846
  2. 2020Gradient Surgery for Multi-Task Learningcited by 1,210
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  5. 2018Is Q-learning Provably Efficient?cited by 485
  6. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  7. 2018Reward learning from human preferences and demonstrations in Ataricited by 314
  8. 2019Dynamics-Aware Unsupervised Discovery of Skillscited by 308
  9. 2016#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learningcited by 307
  10. 2021PEBBLE: Feedback-Efficient Interactive Reinforcement Learning via Relabeling Experience and Unsupervised Pre-trainingcited by 298
  11. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 285
  12. 2013Learning to Optimize Via Posterior Samplingcited by 253
38 more
  1. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 233
  2. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 232
  3. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 222
  4. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  5. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 199
  6. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 194
  7. 2020Learning Near Optimal Policies with Low Inherent Bellman Errorcited by 180
  8. 2020Reward-Free Exploration for Reinforcement Learningcited by 177
  9. 2021Behavior From the Void: Unsupervised Active Pre-Trainingcited by 173
  10. 2021Multi-Task Reinforcement Learning with Context-based Representationscited by 169
  11. 2017Interactive Learning from Policy-Dependent Human Feedbackcited by 155
  12. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 124
  13. 2014Model-based Reinforcement Learning and the Eluder Dimensioncited by 116
  14. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
  15. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
  16. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  17. 2020Fast active learning for pure exploration in reinforcement learningcited by 92
  18. 2020On Reward-Free Reinforcement Learning with Linear Function Approximationcited by 89
  19. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  20. 2020Adaptive Reward-Free Explorationcited by 77
  21. 2020Active Preference-Based Gaussian Process Regression for Reward Learningcited by 70
  22. 2019Asking Easy Questions: A User-Friendly Approach to Active Reward Learningcited by 67
  23. 2013Sample Complexity of Multi-task Reinforcement Learningcited by 58
  24. 2020Provably Efficient Reward-Agnostic Navigation with Linear Value Iterationcited by 56
  25. 2022Reward-Free RL is No Harder Than Reward-Aware RL in Linear Markov Decision Processescited by 49
  26. 2018DQN-TAMER: Human-in-the-Loop Reinforcement Learning with Intractable Feedbackcited by 39
  27. 2020Task-agnostic Exploration in Reinforcement Learningcited by 37
  28. 2020Is Long Horizon Reinforcement Learning More Difficult Than Short Horizon Reinforcement Learning?cited by 34
  29. 2021Skill Preferences: Learning to Extract and Execute Robotic Skills from Human Feedbackcited by 34
  30. 2021Reward-Free Model-Based Reinforcement Learning with Linear Function Approximationcited by 29
  31. 2022On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RLcited by 27
  32. 2021Information Directed Reward Learning for Reinforcement Learningcited by 24
  33. 2022Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimalitycited by 24
  34. 2020Active Preference Learning using Maximum Regretcited by 21
  35. 2018State Aggregation Learning from Markov Transition Datacited by 20
  36. 2021On Reward-Free RL with Kernel and Neural Function Approximations: Single-Agent MDP and Markov Gamecited by 20
  37. 2021Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learningcited by 17
  38. 2021Optimal Uniform OPE and Model-based Offline Reinforcement Learning in Time-Homogeneous, Reward-Free and Task-Agnostic Settingscited by 14

50 most cited of 52 All 52 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

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

15 papers.

Sort:

By area:

  1. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraintcited by 346
  2. 2023Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimismcited by 69
  3. 2024Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inferencecited by 12
  4. 2025ReDit: Reward Dithering for Improved LLM Policy Optimizationcited by 8
  5. 2024Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysiscited by 4
  6. 2024RL-STaR: Theoretical Analysis of Reinforcement Learning Frameworks for Self-Taught Reasonercited by 4
  7. 2025Sign-SZPO: Provable Preference-based Reinforcement Learning with an Unknown Link Functioncited by 4
  8. 2023Conditions on Preference Relations that Guarantee the Existence of Optimal Policiescited by 3
  9. 2025KL-regularization Itself is Differentially Private in Bandits and RLHFcited by 2
  10. 2025SharedRep-RLHF: A Shared Representation Approach to RLHF with Diverse Preferencescited by 1
  11. 2025Active Measuring in Reinforcement Learning With Delayed Negative Effectscited by 1
  12. 2026Differentially Private Preference Data Synthesis for Large Language Model Alignmentcited by 1
3 more
  1. 2025Reducing Reward Dependence in RL Through Adaptive Confidence Discountingcited by 0
  2. 2025Optimizing Algorithms for Mobile Health Interventions with Active Querying Optimizationcited by 0
  3. 2026Offline Constrained RLHF with Multiple Preference Oraclescited by 0