Provably Feedback-Efficient Reinforcement Learning via Active Reward Learning
Authors: Dingwen Kong
Lin Yang
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement Learning
Human-in-the-loop
Active Learning
Theory

Abstract: 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 \emph{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 \emph{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 $\tilde{O}(H{\dim_{R}^2})$ queries on the reward function to provide an $\epsilon$-optimal policy for any $\epsilon > 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 $\Omega(\operatorname{poly}(d, 1/\epsilon))$ state-action pairs where $d$ depends on the complexity of the environmental transition.

Provably Feedback-Efficient Reinforcement Learning via Active Reward Learning
Dingwen Kong
Lin F. Yang Department of Electrical and Computer Engineering University of California, Los Angeles linyanggee www.gggeeeullll.....e .ul...clle edu
School of Mathematical Sciences
Peking University dingwenk@pku. edu.
Abstract
An appropriate reward function is of paramount importance in specifying a task in reinforcement learning (RI.). Yet, it known to extremely challenging practice to design correct reward function for even simple tasks. Human-in-the- loop (Hil.) RI. allows humans to communicate complex goals to the RI. 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 beedback-efficienn algorithmic frameworks that take human-in-the in-the-loop specify rewards of given tasks. We provide an active- learreeleaninn--eee based RL algorithm that first explores the environment without specifying 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 provide 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 O(Hiim) queries on the reward function to provide an s-optimal policy for any & O. Here H the horizon of the RI. environment, and dim specifies the complexity of the function class representing the reward function. In contrast, standard RI. algorithms require query the reward function for at least ((poly 1/E)) state-action pairs where d depends on the complexity of the environmental transition.
Introduction
A suitable reward function is essential for specifying a reinforcement learning (RL) agent to perform a complex task. Yet obvious approaches such as hand-designed reward is not scalable for large number of tasks, especially in the multitask settings [Wilson al., 2007, Brunskill and Li, 2013, Yu et al., 2020, Sodhani et al., 2021]. and can also be extremely challenging (e.g.. [Ng et al., 1999, Marthi, 2007] shows even intuitive reward shaping can lead undesired side effects). Recently, popular framework called Human-in-the-loow (HiL. RL [Knox and Stone, 2009, Christiano et al., 2017. MaeGlashan al., 2017, Ibarz al., 2018, Lee al., 2021, Wang al., 2022] gains more interests as it allows humans to communicate complex goals to the RL agent directly by providing various types of feedback. In this sense, a reward function can be learned automatically and can also be corrected at proper times if unwanted behavior is happening. Despite its promising empirical performance, HiL. algorithms still suffer from insufficient theoretical understanding and possess drawbacks Arakawa et al. [2018], e.g., it assumes humans can give precise numerical rewards and do so without delay and at every time step, which are usually not true. Moreover, these approaches usually train on every new task separately and cannot incorporate exiting experiences.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

In this paper, we attempt to address the above issues of incorporating humans' feedback in RL from a theoretical perspective. In particular, we would like address (I) the feedback complexity issue i.e., the algorithms in practice usually require large amount feedback from humans to be accurate; (2) feedback from humans can be noisy and non-numerical; (3) in need for support of multiple tasks. In particular we consider a fixed unknown RI environment, and formulate a task as an unknown but fixed reward function. A human who wants the agent to accomplish the task needs to communicate the reward to the agent. It is not possible to directly specify the parameters of the reward function as the human may not know it exactly as well, but is able to specify good actions at any given state. To capture the non-numerical feedback issue, we assume that the feedback we can get for an action is only binary- whether an action is "good" or "bad". We further assume that the feedback is noisy in the sense that the feedback is only correct with certain probability. Lastly, require that the algorithm, after some initial exploration phase, should be able to accomplish multiple tasks by only querying the reward rather than the environment again.
In the supervised learning setting, if we only aim to learn a reward function, the feedback complexity can be well-addressed by the active learning framework Settles [2009], Hanneke et al. [2014] an algorithm only queries a few samples of the reward entries and then provide a good estimator. Yet this become challenging in the RL setting as it is sequential decision making problem state-action pairs that are important in the supervised learning setting may not be accessible in the RL setting. Therefore, apply similar ideas in RL, need way to explore the environment and collect samples that are important for reward learning. Fortunately, there were a number of recent works focusing "reward-free" exploration Jin et al. [2020a]. Wang et al. [2020a] on the environment. Hence, applying such an algorithm would not affect the feedback complexity. Additionally it is possible for us to reuse the collected data for multiple tasks.
Our proposed theoretical framework is a non-trivial integration of reward-free reinforcement learning and active learning. The algorithm possesses two phases: in phase I, it performs reward-free RL to explore the environment and collect the small but necessary amount of the information about the environment; in phase II, the algorithm performs active learning to query the human for the reward at only a few state-action pairs and then provide a near optimal policy for the tasks with high probability. The algorithm is guaranteed to work even the feedback is noisy and binary and can solve multiple tasks in phase II. Below we summarize our contributions:
1. We propose a theoretical framework for incorporating humans' feedback in RL. The frame- work contains two phases: an unsupervised exploration and an active reward learning phase. Since the two phases are separated, our framework is suitable for multi-task RL.
2. Our framework deals with a general and realistic case where the human feedback is stochastic and binary-i.e., we only ask the human teacher to specify whether an action is "good" or "bad". We design an efficient active learning algorithm for learning the reward function from this kind of feedback.
3. Our query complexity is minimal because it is independent of both the environmental complexity d and target policy accuracy e. In contrast, standard RL algorithms require query the reward function for at least (pp 1/e)) state-action pairs. Thus our work provides a theoretical validation for the recent empirical HiL RL works where the number of queries is significantly smaller than the number of environmental steps.
4. Moreover, we shows the efficacy of our framework in the offline RL setting, where the environmental transition dataset is given beforchand.
1.1 Related Work
Sample Complexity of Tabular and Linear MDP. There is long line of theoretical work on the sample complexity and regret bound for tabular MDP. See, e.g., [Kearns and Singh, 2002, Jaksch al., 2010, Azar et al., 2017, Jin et al., 2018, Zanette and Brunskill, 2019, Agarwal et al., 2020b, Wang et al., 2020b, Li et al., 2022]. The linear MDP is first studied in Yang and Wang [2019]. See, e.g., [Yang and Wang, 2020, Jin et al., 2020b, Zanette et al., 2020a, Ayoub et al., 2020, Zhou et al., 2021a,b] for sample complexity and regret bound for linear MDP.
Unsupervised Exploration for RI. The reward-free exploration setting is first studied in Jin et al. [2020a]. This setting is later studied under different function approximation scheme: tabular [Kauf-

---

mann et al., 2021, Ménard et al., 2021, Wu et al., 2022], linear function approximation [Wang et al., 2020a, Zanette et al., 2020b, Zhang al., 2021, Huang et al., 2022, Wagenmaker al., 2022, Agarwal et al., 2020a, Modi et al., 2021], and general function approximation [Qiu et al., 2021, Kong et al., 2021, Chen et al., 2022]. Besides, Zhang al. [2020]. Yin and Wang [2021] study task-agnostic RI,, which is variety of reward-free RL. Wu et al. [2021] studies multi-objective RL in the reward-free setting. Bai and Jin [2020], Liu et al. [2021] studies reward-free exploration in Markov games.
Active Learning. Active learning is relatively well-studied in the context of unsupervised learning. See, e.g., Dasgupta et al. [2007], Balcan et al. [2009], Settles [2009], Hanneke et al. [2014] 4] and the references therein. Our active reward learning algorithm is inspired by line of works et al., 2009, Dekel et al., 2010, Agarwal, 2013] considering online classification problem where they assume the response model P(y ()) is linear parameterized. However, their works can not directly apply to the RL setting and also the non-linear case. There are also many empirical study-focuse paper on active reward learning. See, e.g., [Daniel et al., 2015, Christiano et al., 2017, Sadigh et al., 2017, Bιyлk et al., 2019, 2020, Wilde et al., 2020, Lindner et al., 2021, Lee et al., 2021]. Many of them share similar algorithmic components with ours, like information gain-based active query and unsupervised pre- wre-training. But they do not provide finite query complexity bounds.
2 Preliminaries
2.1 Episodic Markov Decision Process
In this paper, we consider the finite-horizon Markov decision process (MDP) M = (S, H, s1). where S is the state space, A is the action space, P {Pr 1 where Pv. 8 x A (S8) are the transition operators,
{r, } where T₁ S x A - {0, 1} are the deterministic binary reward functions, and is the planning horizon. Without loss of generality, we assume that the initial state 81 is fixed. In RL, agent interacts with the environment episodically. Each episode consists of H time steps. A deterministic policy π chooses an action a E AA based on the current state E S at each time { / where for each
step h E [M]. Formally, action. In each episode, the policy induces a trajectory 81, 01, F1, 82, a22 r2,...; 8H, aH TH, 8H+1 where 81 is fixed, a (s1), ri ri (81, $2 Pi (-1 a1) d2 = 7T2 (2())). etc.
[4]. Th. S A maps given state an
We use Q-function and V-function to evaluate the long-term. expected cumulative reward in terms of the current state (state-action pair), and the policy deployed. Concretely, the Q-function and V-function are defined as: Q7,s,, a) EE| E (sw, ahr))ss s, ag 0, ग and (TT(s) E E#= The (sk,, one [sA 8, x=] We denote the optimal policy as n" = { hE)H) optimal values as Q2 (s, a) and (s). Sometimes it is convenient to consider the Q-function and V-function where the true reward function is replaced by a estimated one f {fr hej We denote them as (8, a, and V (s. We also denote the corresponding optimal policy and value π (f)). (s, a, f) and Vž ().
Additional Notations. We define the infinity- norm of function f S A - suP(s.a)ES A lf(ss For a set of state-action pairs Z C S x A and a function f ::S x A 1-3 R
- R as If
we define | = E(in))z2(ss,8)) 1/2
3 Technical Overview
In this section we give overview of our learning scenario and notations, well as the main techniques. The learning process divides into two phases.
3.1 Phase 1: Unsupervised Exploration
The first step is to explore the environment without reward signals. Then we can query the human teacher about the reward function in the explored region. We adopt the reward-free exploration technique developed in Jin et al. [2020a], Wang et al. [2020a]. The agent is encouraged to do
For general initial distribution p. we treat it the first stage transition probability. Pi.
3

---

exploration by maximizing the cumulative exploration bonus. Concretely, we gather K trajectories D = =( [ [ by interacting with the environment. We can strategically choose which policy to use. At the beginning of the k-th episode, we calculate policy based on the history of the first k episodes and use zy to induce a trajectory {(5%, af)) ne(H)-
A similar approach called unsupervised pre-training [Sharma et al., 2020, Liu and Abbeel, 2021] has been successfully used in practice. Concretely, in unsupervised pre-training agents are encouraged to do exploration by maximizing various intrinsic rewards, such as prediction errors [Houthooft et al., 2016] and count-based statennovely [Tang et al., 2017].
3.2 Phase 2: Active Reward Learning
The second step is to learn proper reward function from human feedback. Our work assumes that the underlying valid reward is 1-0 binary, which is interpreted as good action and bad action. We remark that RL problems with binary rewards represent large group of RL problems that are suitable and relatively easy for having human-in-thin -ntaa-----e--ooo.... A representative group problems the binary judgments: For example, suppose we want a robot to learn to do a backflip. A human teacher will judge whether a flip successful and assign a reward our framework can also be generalized to RL problems with n-uniffrm discrete rewards. The detailed discussion is defered to Appendix E.2 due to space limit.
for success and O for failure. Furthermore,
Concretely, consider a fixed stage h E [H]. and we are trying to learn from the human response.
Each time we can query datum (s, a) and receive an independent random response Y {0. 1} from the human expert, with distribution:
P(Y = 1|2) = P(Y 0|2) = (x)...
Here f% is the human response model and needs to be learned from data. We assume that the underlying valid reward of can be determined by (z) in the following manner:
1, (1) > 1/2
(2)2
[0, f2(2) S 1/2.
Note that the query returns 1 with a probability greater than if and only if the underlying valid reward is 1. To make the number of queries as small as possible, we choose small subset of informative data to query the human. We adopt ideas in the pool-based active learning literature and select informative queries greedily. We show that only ((Hdimg) queries need to be answered by the human teacher. The active query method is widely used in human-involved reward learning in practice and shows superior performance than uniform sampling Christiano et al. [2017], Ibarz et al. [2018], Lee al. [2021].
After we learn a proper reward function f. we use past experience D and f to plan for good policy. Note that in this phase we are not allowed for further interaction with the environment. In the multi-task RL setting, we can run Phase 2 for multiple times and reuse the data collected in Phase 1.
Now we diseuss the efficacy of our framework. A naive approach for reward learning via human feedback is asking the human teacher to evaluate the reward function in each round. This approach results in equal environmental steps and number of queries. This high query frequency is unacceptable for large-scale problems. For example, in Lee et al. [2021] the agent learns complex tasks with very few queries (~ 102 to 10 queries) to the human compared to the number of environmental steps (~ 10th steps) by utilizing active query technique. From the theoretical perspective, usual RL sample complexity bound scales with x poly(d, 2). where d is the complexity measure of the environmental transition and E is the target policy accuracy. This quantity can be huge when the environment is complex (i.e., d is large) or with small target accuracy. Our query complexity is desirable since it is independent of both d and 1/c.
Pool-Based Active Reward Learning
In this section we formally introduce our algorithm for active reward learning. We consider fixed stage h and learn Ty. by querying small subset of Z,, = { a hejK)) We omit the subscript h in this section, i.c., use Z, 2k, r, to denote Zn, 2 The ft in this section. Since Z is given

---

before the learning process starts, we refer to this learning scenario as pool-based active learning. Our purpose is to learn a reward function f(-) such that r(2) f(2) for most of 2 in Z. At the same time, we hope the number of queries can be as small as possible.
We assume F is a pre-specified function class to learn f* from, and F is known prior. We assume that F has enough expressive power to represent the human response. Concretely, we assume the following realizabiliity
Assumption (Realizability). f" F.
The learning problem can be arbitrarily difficult, especially when (=) is close to 1. in which case will be difficult to determine the true value of r(2). To give the following bounded noise assumption. In the literature on statistical learning, this assumption is also referred to as Massart noise [Massart and Nédélec, 2006, Giné and Koltchinskii, 2006, Hanneke et al., 2. Our framework can also work under the low noise assumption due to space limit, we defer the discussion to Appendix E.3.
bound, assume
Assumption 2 (Bounded Noise). There exists
> 0, such that for all 2 E 8 A. (f
The value of the margin A depends on the intrinsic difficulty of the reward learning problem and the capacity of the human teacher. For example, if the reward is rather easy to specify and the human teacher is a field expert, and can always give the right answer with a probability of at least 80%, then A will be 0.3. But if the learning problem is hard or the human teacher is unfamiliar with the problem and can only give near-random answers, then A will be very small. But that case, we won't hope the human teacher can help us in the first place. So typical good value for A should be constant.
Examples
We give two examples of JF that frequently studied in the active learning literature. In the linear model, the function class F consists of f in the following form: f(z)
(d(=),=)++ In the
logistic model, the function class JF consists of in the following form: f(z) 1+exp (P(3).))
exp (0(=) Here
S x A I is a fixed and known feature extractor, and w E IR4.
The complexity of F essentially depends on the learning complexity of the human response model. We use the following Eluder dimension [Russo and Van Roy, 2014] to characterize the complexity of F. The eluder dimension serves as a common complexity measure of general non- non-linear function class in both reinforcement learning literature [Osband and Van Roy, 2014, Ayoub et al., 2020, Wang et al., 2020c, Jin al., 2021a] and active learning literature [Chen al., 2021].
Definition 1 (Eluder Dimension). Let & 2 0 and 2 = {(8; F S S x A be a sequence of state-action pairs.
(I) A state-action pair (s,a) a) E x A is e e-dependent on Z with respect to F if any f.g' E F satisfying | I' 2 S also satisfies (s(s,a) f'(s, a) S E.
(2) An (s, a) is s-independent of Z with respect to F if (s, a) is not s-dependent on Z.
(3) The E-eluder dimension (Jing(F,e, E) of function class F is the length of the longest sequence of elements in S x A such that, for some E' 2 E, every element is e' e'-independent of its predecessors. (4) The eluder dimension of function class F is defined as dim == lim supa50 Tog(1/a)
(F,
We remark that a wide range of function classes, including linear functions, generalized linear functions and bounded degree polynomials, have bounded eluder dimension.
Definition 2 (Covering Number and Kolmogorov Dimension). For any E > 0, there exists an E-cover C(F,E) C F with size |C(F, < (FF such that for any f F, there exists I' E C(FF5) with [If f'lloo S E. The Kolmogorov dimension of F is defined as: dim == lim suP.40 [/x(1/a)
([F.)((F.)))
The Kolmogorov dimension is also bounded by (d) for linear/generalized linear function class. Throughout this paper, of F. When F is the class of d-dimensional linear/generalized linear functions, dim(F) is bounded by Od)).
we denote dJm := max dimm dim (F)) as the complexity measure
4.1 Algorithm
We describe our algorithm for learning the human response model and the underlying reward function. We sequentially choose which data points to query. Denote Z the first k points that we decide to
5

---

query and initial Zu to be an empty set. For each & E 2, we use the following bonus function to measure the information gain of querying 2, i.e. how much new information contains compared to -
by(+) + S'
sa If()) --))
We then simply choose 2 to be arg max by (z). After the query points are determined, we query their labels from human. The human response model is then learned by solving least-squares regression:
minger E.ez,, ((=))-
The human response model is used for estimating the underlying reward function. We round f to the cover CFF, A/2) to ensure that there are a finite number of possibilities of such functions - this gives us the convenience of applying union bound in our analysis. Indeed, believe more refined analysis would remove the requirement of rounding but will make the analysis much more involved. The whole algorithm presented in Algorithm 1. Note that such an interactive mode with the human teacher is non-adaprive since all queries are given to the human teacher in one batch. This property makes our algorithm desirable in practice. Here we assume the value of A is known as prior. We can extend our results to the case where A is unknown. Due to space limit, we defer the discussion to Appendix E.
Algorithm Active Reward Learning(2 2, A, 6)
Input: Data Pool 2 (=)))) margin A, failure probability E (0, 1)
Zo <- {} //Query Dataset
Set N <- C [dim" + log(l (8)) (log
A
for 1..,.... N do
3 C Vlo((1/) log N dim(F)
Set the bonus function: (-(-) 4- -
2k arg m bz(2)
Zg 4 Zk-1 (za)
end for
for E NN do
Ask the human expert for a label ((:) E {0.1} end for
Estimate the human model as = arg min ExEEy (f(2) - (()))²
Let f C(F, A/2) such that || - Flloo S A/2
1, f(.) > 1/2
Estimate the underlying true reward: f(-)
0, f() < 1/2
return: The estimated reward function A:
4.2 Theoretical Guarantee
Theorem 1.
With probability at least 1 - 6, for all 2 E 2, we have, f(z) = r(2)) The total number (10)))((1))))))))))))))))))))) (dim(())
of queries is bounded by O (F)
A2
Proof Sketch The first step is to show that the sum of bonus functions EK_ (=x) is bounded by O(dvK) using ideas Russo and Van Roy [2014]. Note that the bonus function bx(-) is non- increasing. Thus we can show that after selecting N = Ō (())) points, for all E 2, the bonus function of does not exceed A. By the bounded-noise assumption, know that the reward label for 2 is correct for all z.
Online RL with Active Reward Learning
In this section we consider how to apply active reward learning method in the online RL setting. In this setting the agent is allowed actively explore the environment without reward signal in the exploration phase. We consider both tabular MDP and linear MDP cases.

---

5.1 Linear MDP with Positive Features
The linear MDP assumption was first studied in Yang and Wang [2019] and then applied in the online setting Jin et al. [2020b]. It is assumed that the agent is given feature extractor Φ S x A - R and the transition model can be predicted by linear functions of the give feature extractor. In our work, we additionally assume that the coordinates of & are all positive. This assumption essentially reduce the linear MDP model to the soft state aggregation model [Singh et al., 1994, Duan al., 2019]. As will be seen later, the latent state structure helps the learned reward function to generalize.
Assumption 3 (Linear MDP with Non-Negative Features). For all h E [H] we assume that there exists a function pr S + Rd such that Pa(s'|s, a) = (un(s'), ő(s a)). Moreover, for all (s, a) E S A, the coordinates of Φ(8.00 a) and Pa (s,5,a) a) all non-negative.
5.2 Exploration Phase
In the exploration phase, inspired by former works on reward-free RI., we use optimistic least-squares value iteration (LSVI) based algorithm with zero reward. In the linear case, for any V S + R, estimate PA V in the following manner
VV(())) + w (),,),, where w <- arg min WER* [ (6 (( 1|
(1)
For the tabular case, we simply use the empirical estimation of PA:
(=,
(s'(s,
(x,a)
(2)
NW (8, a) =0
and define VVV in the conventional manner. Here (5, a.) Σ A[(5%) oh s
(s, s')} and (s, Σ==l 1[(s), añ)) as are the numbers of visit time.
The following optimism bonus (.,)) is sufficient to guarantee optimism in standard regret mini- mization RL algorithms. (The choices of S and BIn specified in the appendix)
min (AA,)) "/ ()2/2, H):
(Linear Case)
min (N.) H}.
(Tabular Case).
In our setting we enlarge the optimism bonus to the following exploration bonus.
(3,)), H's + ( N.G.)
(Linear Case)
(4)
(Tabular Case).
We then set the optimistic Q-function
2h()))) [(HH- ( + (.(:))
and define the exploration policy as the greedy policy with respect to Q,x
5.3 Reward Learning & Planning Phase
After the exploration phase, we run the active reward learning algorithm introduced before on the collected dataset. In the linear setting, we replace the original action with uniform random action. We then use the learned reward function to plan for a near-optimal policy. We still add optimism bonus to guarantee optimism. The whole algorithm is presented in Algorithm 3
5.4 Theoretical Guarantee
Theorem 2. In the linear case, our algorithm can find an e-optimal policy with probability at least 1 8, with at most
o
[Al2d dim dim (F) 1. log( 262
22
7

---

Algorithm 2 UCBVI-Explooationn for k 1r,k=1,,.... K do
1,2,.... V H f- -0.0 +
for h H, 117-111 do
Estimate P (+1(+>)) using (1) or (2)
Set the optimism bonus r (.,)) using (3)
Set the exploration bonus by (+:-) using (4).
Set the optimistic Q-function (n(:))) t 10 HO. PAV
(hi (+ bK(-))
f arg mIxxEEA (7(aaa)
(.) t m Q% (),a)
end for
Execute policy n. = [T to induce a trajectory sf, at o a si+ end for return: Dataset D = =( ((AA)E((M))11
Algorithm 3 UCBVI-Planning
Input: Dataset D = {sh (A.))(((xx)
for 1,2,.... H do if' Linear Case then
2, ((s) where [a(K] are sampled i.i.d. from Unif(AA)
fn < Active Reward Learning( 2n, A, (/HH))
else if Tabular Case then
Zn {s ke]k]
in < Active Reward Learning( 2n, (2)2H)
end if end for for
1,2, K do
V - <- 0, Q
H+1 0
for = H, -,, do
Estimate P/ (..)) using (1) or (2)
Set the optimism bonus (:,-) using (3)
Set the optimistic Q-function ()(3)) 11 (o. + V A+1 + (3)
++(+) < arg magma ())aa))
V. + maxagA Qh(,a))
end for end for return: drawn uniformly from {
Jk=1 where * [
episodes. In the tabular case, our algorithu can find an e-optimal policy with probability at least 1 8, with most
H'S 22
A²
== log(
HSA
episodes. In both cases, the total number of queries to the reward is bounded by Ö(H O(H-dim dim((F)/A?)
Remark Theorem 2 readily extends to multi-task RL setting by replacing with 8/N and applying union bound all tasks, where N is the number of tasks. The corresponding sample complexity bound only increase by a factor of poly (N).
Remark 2. Standard RL algorithms require to query the reward function for at least D maxx/diun dim times, where dimn and dimp stand for the complexity of the reward/transition function. See, e.g., Jin et al. [2020b], Zanette et al. [2020u], Wang et al. [2020c] for the deriva- tion of this bound. Compared to this bound, our feedback complexity bound has two merits: 1) In practice the transition function is generally more complex than the reward function, thus

---

max dimp) > dimg: 2) Our bound is independent of note that e can be arbitrarity small, whereas A a constant.
Proof Sketch
The suboptimality of the policy á can be decomposed into two parts:
V
1 (f) (i" (f)
VT
VI (f) I (F)
(6)
(6))
where (i) correspond the planning error in the planning phase (Algorithm 3) and (ii) correspond to the estimation error of the reward f. By standard techniques from the reward-free RL, (i) can be upper bounded by the expected summation of the exploration bonuses in the exploration phase. In order to bound (ii), we need the learned reward function to be universally correct, not just on the explored region. We show that the dataset collected in the exploration phase essentially cover the state space (tabular case) or the latent state space. Since the reward function class has bounded complexity (log [R] bounded due to the bounded covering number of F), the reward function learned from the exploratory dataset can generalized to distribution induced by any policy.
Offline RL with Active Reward Learning
In this section consider the offline RL setting, where the dataset 2 is provided beforchand. We show that our active reward learning algorithm can still work well this setting. In order to give meaningful result, we assume the following compliance property of D with respect to the underlying MDP. This assumption is firstly introduced in Jin et al. [2021b]. Unlike many literature for offline RL, we do not require strong coverage assumptions, e.g., concentratability [Szepesvári and Munos, 2005, Antos et al., 2008, Chen and Jiang, 2019].
Definition 3 (Compliance). For dataset D [( a (x1 let PD be the joint dis- tribution of the data collecting process. We say 'D is compliant with the underlying MDP if Pp(s l h+1 = [ [ (8) (1
18-1) = (s(s sh a holds for all h E [H],k k E [K]
6.1
Algorithm and Theoretical Guarantee
At the beginning of the algorithm call the active reward learning algorithm estimate the reward function. Inspired by Jin et al. [2021b], we estimated the optimal Q-value Q* using pessimistic value iteration with empirical transition and learned reward function. The policy is defined the greedy policy with respect to Q* The full algorithm and theoretical guarantee is stated below.
Algorithm 4 T.CBVV--Tabula--Off
Input: Dataset D = {sh (A.))()()x
for 1,2,.... H do
Zn. + { af)
n < Active Reward Learning A, (/HH))))..
end for
VH+I + 0.
for
H, H - 1,....1 do
Tx(-,)) :) + Pbi (N + 1)-11/2
Qx(,) ) +- -I, [F,(.)) PA 2rx(.-)]
4x < arg max Qu(:a)
(.).) + max Qu(;a))
end for
return: = (
Theorem 3. With probability least 6, the sub-optimal gap of āt is bounded by
2 (H/S E,,- EN an) + 1)-1/2])
And the total number of queries is bounded by Ö(H -im2 (F)/A)))
The proof of Theorem 3 is deferred to the appendix.

---

7 Numerical Simulations
We run a few experiments to lest the efficacy of our algorithmic framework and verify our theory. We consider tabular MDP with linear reward. The details of the experiments are deferred to Appendix A. Here we highlight three main points derived from the experiment.
Active learning helps reduce feedback complexity compared to passive learning. For instance, to learn a 0.02-optimal policy, the active learning- learning-based algorithm only needs ~ 70 queries the human teacher, while the passive learning- based algorithm requires 200 queries. (Figure 1, left panel)
The noise parameter A plays essential role in the feedback complexity, which is consistent with our bound. For instance, with fixed number of queries, the average error of the learned policy is 0.05, 0.02, 0.005 for A = 0.02, 0.05, 0.1. (Figure 1, right panel)
When A is relatively large (which indicates that the reward learning problem is not inherently difficult for the human teacher), we can learn an accurate policy with much fewer queries the human teacher compared to the number of environmental steps. For instance, for A 0.05, to learn a 0.01-optimal policy, our algorithm requires ~ 2000 environmental steps but only requires 150 queries. (Figure left panel)
active
active
passive
passive
average CRTOR
average error
3,12
100
1.0
1.20
022
number queries
noise margin A
Figure 1: Left: average error v.s. number of queries. Right: the effect of the noise margin A.
8 Conclusions and Discussions
In this work, we provide a provably feedback-efffcient algorithmic framework that takes human-in-the- loop to specify rewards of given tasks. Our proposed framework theoretically addresses several issues of incorporating humans' feedback in RL, such as noisy, non-numerical feedback and high feedback complexity. Technically, our work integrates reward-free RL and active learning in a non non-trive ooiiiiliall way. The current framework is limited to information gain-based active learning, and an interesting future direction is incorporating different active learning methods, such as disagreement based active learning, into our framework.
From broad perspective, work is theoretical validation of recent empirical successes in Hil. RL. Our results also brings new ideas to practice: it provides a new type of selection criterion that can be used in active queries; suggests that one can use recently developed reward-free RL algorithms for unsupervised pre-training. These ideas can be combined with existing deep RL frameworks to be scalable. limitation of the current work that mainly focus on theory, and we leave the empirical test of these ideas in real-world deep RL as future work.
Acknowledgement
DK is partially supported by the elite undergraduate training program of School of Mathematical Sciences in Peking University. L. supported in part by DARPA grant HR001 12190130, NSF Award 2221871.
10

---

References
Alckh Agarwal. Selective sampling algorithms for cost-sensitive multiclass prediction. In Interna- fional Conference on Machine Learning, pages 1220- 1228. PMLR, 2013.
Alekh Agarwal, Sham Kakade, Akshay Krishnamurthy, and Wen Sun. Flambe: Structural complexity and representation learning of low rank MDPs, Advances in neural information processing systems, 33:20095-2001 2020a.
Alckh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pages 67-83. PMLR, 2020b.
András Antos, Csaba Szepesvári, and Rémi Munos. Learning near-optimal policies with Bellman- residual minimization based fitted policy iteration and single sample path. Machine Learning, 71 (1):89-129, 2008.
Riku Arakawa, Sosuke Kobayashi, Yuya Unno, Yuta Tsuboi, and Shin-ichi Maeda. Dqn- tamer: Human-in-the-lowg reinforcement learning with intractable feedback. arXiv preprint 10X1:1811011148. 2018.
Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, and Lin Yang. Model-based reinforcement learning with value-targeted regression. In International Conference Machine Learning, pages 463-474 PMLR, 2020.
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for rein- forcement learning. In International Conference on Machine Learning, pages 263-272. PMLR, 2017.
Yu Bai and Chi Jin. Provable self-play algorithms for competitive reinforcement learning. In International conference on machine learning, pages 551-560. PMLR, 2020.
Maria-Florina Balcan, Alina Beygelzimer, and John Langford. Agnostic active learning. Journal of Computer and System Sciences, 75(1):78-88) 1778-89,17 2009.
Erdem BIyik, Malayandi Palan, Nicholas C Landolfi, Dylan P Losey, and Dorsa Sadigh. Asking easy questions: A user-friendly approach active reward learning. arXiv preprint arXiv: 1910.04355. 2019.
Erdem Biyik, Nicolas Huynh, Mykel J Kochenderfer, and Dorsa Sadigh. Active preference-based Gaussian process regression for reward learning. arXiv preprint arXi::2005.02575. 2020.
Emma Brunskill and Lihong Li. Sample complexity of multi-task reinforcement learning. arXiv preprint arXiv: 1309:::330..2222 6821, 2013.
Nicolo Cesa-Bianche Bianchi, Claudio Gentile, and Francesco Orabona. Robust bounds for classification via selective sampling. In Proceedings of the 26th annual international conference on machine learning, pages 121-128, 2009.
Jinglin Chen and Nan Jiang. Information-theonee considerations batch reinforcement learning. In International Conference Machine Learning, pages 1042-1051. PMLR, 2019.
Jinglin Chen, Aditya Modi, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. On the statistical efficiency of reward-free exploration in non-linear RL. arXiv preprint arXiv:2206. 10770, 2022.
Yining Chen, Haipeng Luo, Tengyu Ma, and Chicheng Zhang. Active online learning with hidden shifting domains. In International Conference on Artificial Intelligence and Statistics, pages 2053-2061. PMLR. 2021.
Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
Christian Daniel, Oliver Kroemer, Malte Viering, Jan Metz, and Jan Peters. Active reward learning with novel acquisition function. Autonomous Robots, 39(3):389 405, 2015.
11

---

Sanjoy Dasgupta, Daniel Hsu, and Claire Monteleoni. A general agnostic active learning algorithm. Advances in neural information processing systems, 20, 2007.
Ofer Dekel, Claudio Gentile, and Karthik Sridharan. Robust selective sampling from single and multiple teachers. In COLT, pages 346-358, 2010.
Yaqi Duan, Tracy Ke, and Mengdi Wang. State aggregation learning from Markov transition data. Advances in Neural Information Processing Systems, 32, 2019.
Evarist Giné and Vladimir Koltchinskii. Concentration inequalities and asymptotic results for ratio type empirical processes. The Annals of Probability. 34(3):1143-1216 2006.
Steve Hanneke et al. Theory of disagreement-busee active learning, Foundations and Trends@ in Machine Learning, 7(2-3):131-300 2014.
Rein Houthooft, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. Vime: Variational information maximizing exploration. Advances in neural information processing systems, 29, 2016.
Jiawei Huang, Jinglin Chen, Li Zhao, Tao Qin, Nan Jiang, and Tie- Liu. Towards deployment- efficient reinforcement learning: Lower bound and optimality. arXiv preprint arXiv:2202.06450, 2022.
Borja Ibarz, Jan Leike, Tobias Pohlen, Geoffrey Irving, Shane Legg, and Dario Amodei. Reward learning from human preferences and demonstrations in atari. Advances in neural information processing systems, 31, 2018.
Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1660 1600, 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learning provably efficient? Advances in neural information processing systems, 31, 2018
Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870-4879, PMLR, 2020a.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020b.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34, 2021a.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference Machine Learning, pages 5084-5096. PMLR, 2021b.
Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pages PMLR, 2021.
Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 49(2):209 232, 2002.
W Bradley Knox and Peter Stone. Interactively shaping agents via human reinforeement: The TAMER framework. In Proceedings of the fifth international conference on Knowledge capture, pages 9-16, 2009.
Dingwen Kong, Ruslan Salakhutdinov, Ruosong Wang, and Lin F Yang. Online sub-sampling for reinforcement learning with general function approximation, arXiv preprint arXiv:2106.07200 2021.
12

---

Kimin Lee, Laura Smith, and Pieter Abbeel. Pebble: Feedback-efficiem interactive reinforcement learning via relabeling experience and unsupervised pre-training. arXiv preprint (rXiv:206600501,, 2021.
Yuanzhi Li, Ruosong Wang. and Lin F Yang. Setting the horizon-dependencee of sample complexity in reinforcement learning. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 965-976. IEEE, 2022.
David Lindner, Matteo Turchetta, Sebastian Tschiatschek, Kamil Ciosek, and Andreas Krause. Information directed reward learning for reinforcement learning. Advances in Neural Information Processing Systems, 34:3850-3862, 2021.
Hao Liu and Pieter Abbeel. Behavior from the void: Unsupervised active pre-training. Advances in Neural Information Processing Systems, 34, 2021.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of moodel-based reinforcement learning with self-play. International Conference on Machine Learning, pages 7001-7010. PMLR, R, 2021.
James MacGlashan, Mark Ho, Robert Loftin, Bei Peng, Guan Wang, David L Roberts, Matthew Taylor, and Michael L Littman. Interactive learning from dolicy-dependent human feedback. In International Conference Machine Learning, pages
PMLR, 2017.
Enno Mammen and Alexandre B Tsybakov. Smooth discrimination analysis. The Annals of Statistics, 27(6):1808-188) 1999.
Bhaskara Marthi. Automatic shaping and decomposition reward functions. In Proceedings of the 24th International Conference on Machine learning, pages 601-608, 2007.
Pascal Massart and Élodie Nédélec. Risk bounds for statistical learning. The Annals of Statistics, 34 59:2226-23666 2006.
Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In Interna- tional Conference on Machine Learning, pages 7599-7608. PMLR, 2021.
Aditya Modi, Jinglin Chen, Akshay Krishnamurthy, Nan Jiang, and Alekh Agarwal. Model-free representation learning and exploration in low-rank MDPs. arXiv preprint arXiv:2102.07035, 2021.
Andrew Y Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In Ieml, volume 99, pages 278-287, 1999.
Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
Shuang Qiu, Jieping Ye, Zhaoran Wang, and Zhuoran Yang. On reward-free RL with kernel and neural function approximations: Single-agent MDP and Markov game. In International Conference on Machine Learning, pages 8737-8747, PMLR, 2021.
Daniel Russo and Benjamin Van Roy. Learning to optimize via posterior sampling. Mathematics of Operations Research, 322411121111243, 2014.
Dorsa Sadigh, Anca Dragan, Shankar Sastry, and Sanjit A Seshia, Active preference-based learning of reward functions. 2017.
Burr Settles. Active learning literature survey. 2009.
Archit Sharma, Shixiang Gu, Sergey Levine, Vikash Kumar, and Karol Hausman. Dynamics- aware unsupervised discovery of skills. In ICLR, 2020.
Satinder Singh, Tommi Jaakkola, and Michael Jordan. Reinforcement learning with soft state aggregation. Advances in neural information processing systems, 1994.
13

---

Shagun Sodhani, Amy Zhang, and Joelle Pineau. Multi-tas task reinforcement learning with context- based representations. In International Conference on Machine Learning, pages 9767-9779. PMLR, 2021.
Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference on Machine learning, pages 880-887, 2005.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, OpenAl Xi Chen, Yan Duan, John Schulman, Filip DeTurck, and Pieter Abbeel. exploration: A study of count-based exploration for deep reinforcement learning. Advances in neural information processing systems, 30, 2017.
Alexander B Tsybakov. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32(1):135-166 2004.
Andrew J Wagenmaker, Yifang Chen, Max Simchowitz, Simon Du, and Kevin Jamieson. Reward- freerd-free RL is no harder than reward-aware RL in linear Markov decision processes. In International Conference Machine Learning, pages 22430-22456. PMLR, 2022.
Ruosong Wang. Simon $ Du, Lin Yang, and Russ R Salakhutdinov. On reward-free reinforcement learning with linear function approximation. Advances in neural information processing systems, 13:17816-17826, 2020a.
Ruosong Wang, Simon S Du, Lin F Yang, and Sham M Kakade. Is long horizon reinforcement learning more difficult than short horizon reinforcement learning? arXiv preprint arXiv:2005.00527, 2020b,
Ruosong Wang. Russ Salakhutdinov, and Lin Yang. Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension. Advances in Neural Information Processing Systems, 33:6123-6135 2020c.
Xiaofei Wang, Kimin Lee, Kourosh Hakhamaneshi, Pieter Abbeel, and Michael Laskin. Skill preferences: Learning to extract and execute robotic skills from human feedback. In Conference on Robot Learming, pages 2259-1268 PMLR, 2022.
Nils Wilde, Dana Kulić, and Stephen L. Smith. Active preference learning using maximum regret. In 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 10952-10959. IEEE, 2020.
Aaron Wilson, Alan Fern, Soumya Ray, and Prasad Tadepalli. Multi-task reinforcement learning: a hierarchical bayesian approach. In Proceedings of the 24th international conference Machine learning, pages 1015-1022, 2007.
Jingfeng Wu, Vladimir Braverman, and Lin Yang. Accommodating picky customers: Regret bound and exploration complexity for multi-objective reinforcement learning. Advances in Neural Information Processing Systems, 34:13112-1311 2021.
Jingfeng Wu, Vladimir Braverman, and Lin Yang. Gap-dependent unsupervised exploration for reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 4109-4131. PMLR, 2022.
Lin Yang and Mengdi Wang. Samplc-optimal parametric Q-lcarning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
Lin Yang and Mengdi Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR, 2020.
Ming Yin and Yu- Yu-Xiang Wang. Optimal uniform OPE and model- in homoeeooogensuus, reward-free and task-agnostic settings. Advances in neural information processing systems, 18900-12992,, 2021.
model-based based offline reinforcement learning
Tianhe Yu, Saurabh Kumar, Abhishek Gupta, Sergey Levine, Karol Hausman, and Chelsea Finn. Gradient surgery for multi-task learning. Advances Neural Information Processing Systems, 33: 5824-5836, 2020.
14

---

Andrea Zanette and Emma Brunskill. Tighter learning without domain knowledge using value function bounds, In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
regret bounds in reinforcement
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near optimal policies with low inherent Bellman error. In International Conference on Machine Learning, pages 10978-10989. PMLR, 2020a.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Provably efficient reward-agnostic navigation with linear value iteration. Advances in Neural Information Processing Systems, 33:1 1756-1111111 11766, 2020b.
Weitong Zhang, Dongruo Zhou, and Quanquan Gu. Reward-free model-based reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems, 34: 1582-1593, 2021.
Xuezhou Zhang, Yuzhe Ma, and Adish Singla. Task-agnostic exploration in reinforcement learning. Advances in Neural Information Processing Systems, 33:11734-11743 2020.
Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes. In Conference on Learning Theory, pages 4532-4576. PMLR, 202
Dongruo Zhou, Jiafan He, and Quanquan Gu. Provably efficient reinforcement learning for discounted MDPs with feature mapping. International Conference on Machine Learning, pages 12793- 12802. PMLR, 2021b.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations your work? [Yes] See Section for future directions.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work is theoretical in nature and does not have immediate social impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump- tions 1,2,3
(b) Did you include complete proofs of all theoretical results? [Yes] Proof of all theorems and lemmas are included the Supplementary Material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (cither in the supplemental material or as URL)? [Yes] The source code is included in the supplementary material. One may run Figure I.m and Figure2.m to reproduce the results in Figure and Figure 2, respectively.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] Please refer Appendix A.
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [No] The figure is averaged over 100 trials and is enough to validate our theory.
(d) Did you include the total amount compute and the type of resources used (e.g.. type of GPUs, internal cluster, cloud provider)? [N/A] The amount of compute is negligible since the environment is very small. Our results can be easily reproduced in personal laptop.
4. If you using cxisting assets (c.g., code, data, models) or curating/releasing assets...
15

---

(a) If your work uses existing assets, did you cite the creators? [Yes] Please refer to Appendix A.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "cIAAvNPosM", "reviewer": "Reviewer_GgBc", "summary": "This paper studies the problem of active reward learning in reinforcement learning. The objective is to design an algorithm that  allows the user, after limited access to a few reward queries, to not only reconstruct the reward function but also use it to produce an $\\epsilon$-optimal policy. The authors assume the rewards are in $\\{ 0,1\\}$ and that the human feedback is random such that for any state action pair and episode step  $s,a,h$  the observed human feedback $Y$ satisfies, \n\n$$\\mathbb{P}(Y | s,a,h) = f_h^*(s,a,h)$$\n\nSuch that $f_h^* \\in \\mathcal{F}$ for some known function class $\\mathcal{F}$. It is further assumed that the true rewards are a thresholded version of the human feedback so that the reward of $s,a,h$ equals $1$ if $f_h^*(s,a,h) > 1/2$ and $0$ otherwise. They make use of a Massart noise assumption to ensure the learnability of this threshold function. It is possible to show that sufficient samples from the human labeler are enough to learn the thresholded reward even over all state actions in a data pool. The number of labels needed depends only on the gap $\\Delta$ (from the Massart noise assumption), and the complexity of the function class $\\mathcal{F}$. In short even if the dataset is large, a dataset size independent number of samples are needed to learn the reward function over all of it.\n\nThe authors then combine this result with a reward free exploration scheme to first collect sufficient data from either a tabular or a linear MDP and use it for the purpose of reward labeling. The reward labeling results described above imply that in order to learn the reward function over all the datapoints in the data batch generated by free exploration it is enough to query the rewards over a number of state action pairs only dependent on the noise condition and the size of the function class. \n\nThey complement their discussion with some commentary on how to extend their results to the setting of offline RL.\n", "questions": "I think there should be some citations in the reward free section that are missing. For example \"Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation\" by Weitong Zhang, Dongruo Zhou, Quanquan Gu discusses the reward free setting for linear MDPs. \n\nQs\na) The margin $\\Delta$ is assumed to be known. What happens if this quantity is unknown? Have the authors thought how to bypass this issue?\nb) In Algorithm 1 the underlying true reward is produced by thresholding $\\hat{f}$. This is a member of the covering. Is there a reason why $\\tilde{F}$ is not enough? This could be better explained in the main. [ I didn't look at the appendix]\n", "limitations": "This work poses no negative societal impact.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1) Strengths. The setting studied by the paper seems novel, and the discussion that these results may bring about would represent a welcome addition to the reinforcement learning literature. Developing theoretical understanding of HiL algorithms and how it is that in practice these algorithms do not require massive amounts of data is very important. Thus, the assumptions used in this work are not to be thought as limiting but instead as ways of developing understanding of these issues.\n\n2) Weaknesses. The technical contribution of this work is limited. The algorithms presented and their analysis in my understanding is mainly lifted from the existing literature. The Active Reward Learning guarantees are not really novel or surprising. The reward free section lacks citations but these results are already present in the literature. \n\nDespite 2) I think the paper has merit because of the introduction of this setup. \n\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WY28uaHd8F4", "reviewer": "Reviewer_oq5m", "summary": "Summary\n-------\n\nTo better understand human-in-the-loop RL, this paper aims to provide a\ntheoretical understanding of the feedback required from a human to learn\na reward function. The authors proposes a provable active-learning RL\nalgorithm, which queries a human on feedback for its actions. The\nproposed algorithm needs to query the reward function for feedback\n$O(H dim_R)$ times, in contrast to standard RL algorithm which require\nat least $\\Omega(\\text{poly}(d,\n\\frac{1}{\\epsilon}))$. This is a purely theoretical paper, and there are\nno experiments.\n\n\n", "questions": "\nDetailed Comments\n-----------------\n\n-   Simple synthetic experiments with a programmatic reward function\n    that can be queried would help elucidate the main points, and also\n    enable comparisons against simple baselines.\n-   The order of the number of queries needed for your algorithm depends\n    on the complexity of the function class representing the reward,\n    whereas the bound on \\\"typical\\\" RL algorithms dpeends on the\n    complexity of the environment transition. How do these bounds\n    compare for different classes of problems? I can imagine some MDPs\n    with very simple transitions and complicated reward function (and\n    vice-versa). How should these differences be reconciled?\n\nMinor Comments\n--------------\n\n-   Line 122: Mistakenly refers to three phases, when it seems there are\n    only two.", "limitations": "The conclusion section, which the authors point to, only discusses future work and not the limitations of the algorithm nor negative societal impact. As a theory paper, societal impact is difficult to ascertain. Limitations in the theoretical analysis are somewhat discussed throughout the paper, but it would be nice to see candid discussion in the conclusion on the overall limitations of this approach.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\nDecision\n--------\n\nOverall, I think this paper is interesting in the problem that it\nstudies and the theoretical results seem important. I am not an expert\nin this area, however, and will tentatively rate the paper at slightly\nbelow the acceptance threshold. The submission is held back by some open\nquestions, namely the comparison of the bound derived versus the bound\nof standard RL algorithms. Experiments in a toy environment, with an\nunknown but programmatic reward function that can be queried, would also\nbe nice and strengthen confidence in the importance of the derived\nalgorithm.\n\nStrengths\n---------\n\n-   The problem studied, that of optimally querying a human on feedback\n    for reward, is an interesting line of study that deserves a\n    theoretical analysis.\n-   The bound derived is surprisingly elegant, and the presentation of\n    the theory is mostly readable.\n\nWeaknesses\n----------\n\n-   Experiments in a toy environment, with some programmatic reward\n    function that can be queried, would help contextualize the proposed\n    algorithm and the tightness of the bound.\n-   The biggest open question is how to contextualize the bound derived,\n    which depends on a measure of complexity of the reward function,\n    with the standard bound that depends on the complexity of of the\n    transition.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "DITXGfqyth", "reviewer": "Reviewer_MpPD", "summary": "This paper aims to solve the RL problem in a setting where the rewards are initially unknown. The algorithms proceeds in two stages. First, in the exploration phase, the algorithm collects samples form the environment to learn about the transitions from state to state. Then, the algorithm queries the user about rewards for specific state-action pairs and comes up with an approximation to the optimal policy. The paper shows a bound on the sub-optimality gap on the resulting policy. The analysis is restricted to the case where the true reward is binary.\n\nMinor points: \n - in line 119, the definition of the norm of a function wrt. to the set does not use the set Z on the right hand side. You have to change the definition so that the summation is over the elements of Z.  \n- it may make sense to briefly contrast your approach to [1] in the Active Learning paragraph of the \"Related Work\" section. They solve a related reward active learning problem, although in a slightly different setting (known transition model, unknown reward function). \n\n[1] Lindner, D., Turchetta, M., Tschiatschek, S., Ciosek, K., Krause, A. (2021) Information Directed Reward Learning for Reinforcement Learning NeurIPS 2021.", "questions": "1. Your analysis is restricted to RL problems where the reward is binary (1 or 0 for every state-action pair). Can you offer any intuitions about how restricted a class of problems this is? In other words, how does the set of RL problems with binary rewards compare to the set of RL problems with rewards bounded in [0,1]?\n2. Can you offer any intuitions about how well your method will scale to deep RL / larger-scale benchmarks?\n3. The noise margin \\Delta plays a huge role when determining the required number of queries. Can you give any insights about what the values of \\Delta will be for realistically large MDPs?", "limitations": "The authors briefly mention limitations of the approach in the conclusion, but do not discuss them at length. In my view, the biggest limitations are: (1) it is unclear how the method scales and (2) it is unclear what the noise margin will be for realistic problems (a small margin makes the required number of queries in Theorem 3 very large).\n\nI do not see any ethical problems with this paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The problem of finding out enough information about the reward function of an MDP to be able to come up with a close-enough idea of what the optimal policy is is a major challenge and crucial to unlock many applications of RL. This paper makes a good attempt directed towards solving this problem. \n- The theoretical results paint a complete picture of the performance of the agent trained using this method.\n\nWeaknesses:\n- There is no empirical evaluation in the main paper and evaluation in the supplementary material is very limited. This is not a deal-breaker since good theoretical papers can by viable contributions to NeurIPS even without experiments, but including them would make the submission stronger. \n- Presentation of the material is dry and dense at times. It could be improved by providing more intuitions about what the practical significance of each result is. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-FyVBLG7HfM", "reviewer": "Reviewer_L6qb", "summary": "The authors propose a theoretical framework for studying human-in-the-loop RL which splits the problem into a reward-free exploration phase and an active reward learning phase. The agent has no knowledge of the reward function and has to learn about the reward from a human expert. In the first phase the agent explores the environment using standard RFE methods. In the second phase the agent then queries the human about states it has encountered during exploration in order to learn about the reward. The authors study the sample complexity of this problem, comparing the sample complexity of exploration with the sample complexity of learning the reward. They propose an active reward learning algorithm and bound it's sample complexity as a function of the complexity of the reward function class. They then apply this algorithm to linear MDPs and offline RL deriving tighter sample complexity results for these special cases.", "questions": "Would it be possible to extend the proposed framework to rewards that are not binary, and noise models that are not bounded (e.g., sub-Gaussian noise)?\n\n\n \n**Minor**\n\n- The abstract on OpenReview has an error in the Latex syntax. Also, it should be a single paragraph.\n- There are some capitalization issues and inconsistencies in the references (\"bellman\" -> \"Bellman\", \"markov\" -> \"Markov\", \"q-learning\" -> \"Q-learning\", etc.)\n- The paper should probably cite other work on active reward learning such as Sadigh et al. 2017", "limitations": "The paper would benefit from a discussion of the assumptions made for the theoretical results, in particular, binary rewards and bounded noise. It should also discuss if the approach could be extended to nonlinear rewards.\n\nI did not find a discussion of potential broader impact of the paper.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n- The paper provides a nice theoretical framework to think about human-in-the-loop RL.\n- The theoretical results support the empirical observation that we need much less information about the reward than interactions with the environment, which is encouraging for work on RL that relies on human feedback.\n- The theoretical analysis seems strong and the results all seem sound to me (I did not check the proofs)\n- The application of the theoretical analysis to offline RL is particularly nice, and supports the generality of the proposed framework.\n- The paper is well-written overall and well-structured.\n \n**Weaknesses**\n- The setup makes some strong and impractical assumptions, such as assuming binary rewards and bounded noise.\n- The proposed framework of separating an exploration and an active learning phase is not novel and implicitly assumed in a lot of prior work on active reward learning. Practical work often finds that iterating between exploration and active learning is beneficial, which the theoretical framework does not capture.\n- The paper could be clearer about how the theoretical framework connects to practical applications.\n- The paper lacks any empirical evaluation. Having at least a small empirical evaluation of the proposed method, to see if the sample complexity results match empirical performance at least in simple experiments, would make the paper much stronger in my opinion.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept