Provably Feedback-Efficient Reinforcement Learning via Active Reward Learning
This work addresses the problem of reducing human feedback burden in human-in-the-loop reinforcement learning for AI practitioners, offering a theoretical framework with provable efficiency gains, though it is incremental in advancing theoretical understanding.
The paper tackles the challenge of designing correct reward functions in reinforcement learning by proposing a provably feedback-efficient algorithm that uses active learning to query human teachers for only a few reward feedbacks, achieving an ε-optimal policy with high probability using only Õ(H dim_R^2) queries, compared to standard methods requiring Ω(poly(d, 1/ε)) queries.
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 $\widetilde{O}(H{{\dim_{R}^2}})$ queries on the reward function to provide an $ε$-optimal policy for any $ε> 0$. Here $H$ is the horizon of the RL environment, and $\dim_{R}$ 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 $Ω(\operatorname{poly}(d, 1/ε))$ state-action pairs where $d$ depends on the complexity of the environmental transition.