# Provably Feedback-Efficient Reinforcement Learning via Active Reward Learning

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

## Key facts

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

## Builds on (most cited first, 30 of 52)

- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Gradient Surgery for Multi-Task Learning](https://mlsanity.com/paper/2001.06782/) (2020)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Reward learning from human preferences and demonstrations in Atari](https://mlsanity.com/paper/1811.06521/) (2018)
- [Dynamics-Aware Unsupervised Discovery of Skills](https://mlsanity.com/paper/1907.01657/) (2019)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [PEBBLE: Feedback-Efficient Interactive Reinforcement Learning via Relabeling Experience and Unsupervised Pre-training](https://mlsanity.com/paper/2106.05091/) (2021)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Learning to Optimize Via Posterior Sampling](https://mlsanity.com/paper/1301.2609/) (2013)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs](https://mlsanity.com/paper/2006.10814/) (2020)
- [Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms](https://mlsanity.com/paper/2102.00815/) (2021)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Learning Near Optimal Policies with Low Inherent Bellman Error](https://mlsanity.com/paper/2003.00153/) (2020)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Multi-Task Reinforcement Learning with Context-based Representations](https://mlsanity.com/paper/2102.06177/) (2021)
- [Behavior From the Void: Unsupervised Active Pre-Training](https://mlsanity.com/paper/2103.04551/) (2021)
- [Interactive Learning from Policy-Dependent Human Feedback](https://mlsanity.com/paper/1701.06049/) (2017)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Model-based Reinforcement Learning and the Eluder Dimension](https://mlsanity.com/paper/1406.1853/) (2014)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [On Reward-Free Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2006.11274/) (2020)

## Built on by (most cited first, 15 of 15)

- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Reinforcement Learning with Human Feedback: Learning Dynamic Choices via Pessimism](https://mlsanity.com/paper/2305.18438/) (2023)
- [Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference](https://mlsanity.com/paper/2409.17401/) (2024)
- [ReDit: Reward Dithering for Improved LLM Policy Optimization](https://mlsanity.com/paper/2506.18631/) (2025)
- [Reinforcement Learning from Human Feedback without Reward Inference: Model-Free Algorithm and Instance-Dependent Analysis](https://mlsanity.com/paper/2406.07455/) (2024)
- [RL-STaR: Theoretical Analysis of Reinforcement Learning Frameworks for Self-Taught Reasoner](https://mlsanity.com/paper/2410.23912/) (2024)
- [Sign-SZPO: Provable Preference-based Reinforcement Learning with an Unknown Link Function](https://mlsanity.com/paper/2506.03066/) (2025)
- [Conditions on Preference Relations that Guarantee the Existence of Optimal Policies](https://mlsanity.com/paper/2311.01990/) (2023)
- [KL-regularization Itself is Differentially Private in Bandits and RLHF](https://mlsanity.com/paper/2505.18407/) (2025)
- [SharedRep-RLHF: A Shared Representation Approach to RLHF with Diverse Preferences](https://mlsanity.com/paper/2509.03672/) (2025)
- [Active Measuring in Reinforcement Learning With Delayed Negative Effects](https://mlsanity.com/paper/2510.14315/) (2025)
- [Offline Constrained RLHF with Multiple Preference Oracles](https://mlsanity.com/paper/2604.00200/) (2026)
- [Differentially Private Preference Data Synthesis for Large Language Model Alignment](https://mlsanity.com/paper/2605.30808/) (2026)
- [Reducing Reward Dependence in RL Through Adaptive Confidence Discounting](https://mlsanity.com/paper/2502.21181/) (2025)
- [Optimizing Algorithms for Mobile Health Interventions with Active Querying Optimization](https://mlsanity.com/paper/2512.08950/) (2025)

## 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.