Active Exploration for Inverse Reinforcement Learning
Authors: David Lindner
Andreas Krause
Giorgia Ramponi
Venue: NeurIPS 2022 Accept (2022)
Keywords: inverse reinforcement learning
active learning
reward-free exploration

Abstract: Inverse Reinforcement Learning (IRL) is a powerful paradigm for inferring a reward function from expert demonstrations. Many IRL algorithms require a known transition model and sometimes even a known expert policy, or they at least require access to a generative model. However, these assumptions are too strong for many real-world applications, where the environment can be accessed only through sequential interaction. We propose a novel IRL algorithm: Active exploration for Inverse Reinforcement Learning (AceIRL), which actively explores an unknown environment and expert policy to quickly learn the expert’s reward function and identify a good policy. AceIRL uses previous observations to construct confidence intervals that capture plausible reward functions and find exploration policies that focus on the most informative regions of the environment. AceIRL is the first approach to active IRL with sample-complexity bounds that does not require a generative model of the environment. AceIRL matches the sample complexity of active IRL with a generative model in the worst case. Additionally, we establish a problem-dependent bound that relates the sample complexity of AceIRL to the suboptimality gap of a given IRL problem. We empirically evaluate AceIRL in simulations and find that it significantly outperforms more naive exploration strategies.

Active Exploration for Inverse Reinforcement Learning
David Lindner
Andreas Krause Department of Computer Science ETH Zurich krausea@ethz.ch
Department of Computer Science
ETH Zurich
david. wet.d.iinneeriiii ethz. ch
Giorgia Ramponi
ETH AI Center
gi rimpoia.ramponi @ai ethz. ch
Abstract
Inverse Reinforcement Learning (IRL) is powerful paradigm for inferring a re- ward function from expert demonstrations, Many IRL algorithms require known transition model and sometimes even a known expert policy, or they at least require access to a generative model. However, these assumptions are too strong for many real-world applications, where the environment can be accessed only through se- quential interaction. We propose a novel IRL. algorithm: Active exploration for Inverse Reinforcement Learning (AceIRL), which actively explores unknown environment and expert policy to quickly learn the expert's s reward function and identify good policy. AceIRL uses previous observations construct confidence intervals that capture plausible reward functions and find exploration policies that focus on the most informative regions of the environment. AceIRL is the first approach to active IRL with comple-coplyxxtty bounds that does not require a generative model of the environment. AceIRL matches the sample complexity of active IRI. with a generative model in the worst case. Additionally, we establish problem-dependent bound that relates the sample complexity of AceIRL to the suboptimality gap of given IRL problem. We empirically evaluate AceIRL in sim- ulations and find that it significantly outperforms more naive exploration strategies.
Introduction
Reinforcement Learning (RL; Sutton and Barto 2018) has achieved impressive results, from playing video games (Mnih et al. 2015) to solving robotic control problems (Haarnoja et al., 2019).. However, in many applications, is challenging to design reward function that robustly describes the desired task (Amodei et al. 2016) Hendrycks et al. 2021). Instead of using an explicit reward function, Inverse Reinforcement Learning (IRL; Ng al. 20000) seeks recover the reward by observing an experi, e.g., an human who already knows how to perform a task. However, most existing IRL algorithms assume that the transition model, and in some cases, the expert's policy, known. In many real-world applications, this is not given, and the agent needs to estimate the transition dynamics and the expert policy from samples. Figure [ an illustrative example where the agent can choose between different paths that have different properties, c.g., walking speeds, and lead to different goals. The agent has to explore the environment and query the expert policy in order infer the expert's 's reward function.
IRL with sample- based estimation was only recently analyzed formally by Metelli et al. (2021). They decompose the error on the reward into a contribution from estimating the transition model and
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Th (50)
OO
Figure I: An illustrative example of Active IRI. The agent can choose between four paths that lead to different objects. It can get action recommendations from expert but does not know about the properties the different paths (the transition dynamics) or the value of different items (the reward function). The agent's 's goal is to infer which reward functions explain the expert's recommendations. Only observing the expert actions is not enough to do that. Rather, the agent has to explore the environment and learn about the dynamics. The human might prefer find the treasure over the carrot but still recommend the yellow path because the treasure is very difficult to reach. To explore efficiently, the agent has combine uncertainty about the expert policy with its uncertainty about the environment to choose where to explore. AceIRL implements infer which reward functions are consistent with the expert's 's recommendations as quickly as possible. We present experiments version of this environment in Section 7
exploration strategy that aims to
estimating the expert policy. Based on this, Metelli et al. (2021) propose an efficient sampling strategy recover good reward function. However, they assume a generative model of the environment, i.e, the agent can query the transition dynamics for arbitrary states and actions. In practice, this assumption unrealistic. The agent in Figure [ starts in the middle and cannot learn about the properties of any path without actually exploring the environment.
In this work, we consider IRL with unknown transition dynamics and expert policy and focus on exploring the environment in order to recover the expert's 's reward function efficiently. To the best of our knowledge, present the first paper providing sample complexity guarantees for the active IRL problem without access to a generative model.
Our main contributions are:
We propose the active IRL problem in a finite-horizon, undiscounted Markov Decision Pro- cess (MDP) and characterize necessary and sufficient conditions for solving it (Section 4.1
We analyze how the estimation errors of the transition model and the expert policy contribute to the estimation етrоr of the reward function, extending prior work to the finite-horizon setting. We provide a novel analysis of how this error affects the performance the policy, which optimizes the recovered reward function (Section 4.2)
We propose novel algorithm, Active exploration for Inverse Reinforcement Learning (AceIRL), which actively explores the environment and the expert policy to infer good reward function. In each iteration, AceIRL constructs an exploratory policy based on the estimation error of the recovered reward function (Section
We consider two different exploration strategies for AceIRL. The first, more straightforward, strategy provides a sample complexity similar to the algorithm proposed by Metelli et al. (202T), which has access a generative model (Section 6. The second strategy takes the expected reduction in uncertainty into account (Section 6.2 This yields tighter, sample complexity bound at the cost of solving a convex optimization problem in each iteration (Section 6.3
We evaluate AceIRL empirically in simulated environments and demonstrate that it achieves significantly better performance than more naive exploration strategies (Section 77.. We provide code reproduce out experiments at http:///gghhh.b..oaaaggggrur////
The proofs of all results presented in the main paper be found in Appendix B

---

2
Related Work
Most IRL algorithms assume that the underlying transition model is known RRtliff et al. 2006 Ziebart et al. 2008 Ramachandran and Amir 2007] Levine et al. 2011). However, the transition model usually needs to be estimated from samples, which induces an error in the recovered reward function that most papers do not study. Metelli et al. (202T) analyze this error and the sample complexity of IRL in tabular setting with a generative model. They propose an algorithm focused on transferring the learned reward function to a fully known target environment. Dexter et al. (2021) provides a similar analysis sis in continuous state spaces and discrete action spaces, but they still require generative model of the environment. In contrast, we do not assume access to generative model and thus need to tackle the exploration problem in IRI..
Some prior work studies active learning algorithms for IRL in a Bayesian framework but without theoretical guarantees. Lopes al. (2009) propose an active learning algorithm for IRL that estimates a posterior distribution over reward functions from demonstrations, requiring a prior distribution and full knowledge of the environment dynamics. Relatedly, Cohn et al. al. (20TT) consider Bayesian IRL setting with autii-uutoooouus agent that asks an expert for advice if it is uncertain about the reward. Brown et al. (2018) empirically study active IRL in several safety-critical environments, selecting queries using value at risk. Kulick et al. (2013) consider active learning for robotic manipulation task, asking a human expert for advice in situations with the highest predictive uncertainty. Similarly, Losey and O' Malley (2018) propose a method to learn uncertainty estimates from human corrections in a roboties context. All of these papers assume Bayesian framework and do not provide theoretical guarantees. In contrast, our setup does not require prior over reward functions, and we provide theoretical sample complexity guarantees for our algorithm.
A separate line of work studies sample complexity in imitation learning where the goal is to imitate
an expert policy rather than infer a reward function (Rajaraman et al.) 2020; Xu al. (020). In particular, Abbeel and Ng (2005) also focus on exploration and propose to use the expert policy to explore relevant regions, whereas Shani et al. (2022) use an upper-confidence approach to exploration. Our setting is different because we focus on IRL. instead of imitation learning, and we aim to explore to infer reward function learn most effectively.
3 Preliminaries
Let us first introduce necessary background and notation that we throughout the paper.
Markov decision process. finite-horizon (or episodic) Markov Decision Process without reward function (MDP, R) is a tuple M == (S. A. P. P. su), where S is the finite state space of size S; A the finite action space of size A; P: S x As the transition model; H is the horizon and so is the initial state.
| In other words, finite-horize MDP,R is a finie-hhorizon MDP (Puterman 2014) without the reward function. We describe an agent's behaviour with a (possible stochastic)
policy т E S x [H] - AA.
Reward function. A reward function r : 8x Ax Ax[H] + [0, Rmax] maps catte-action-imm step triplets to reward. Given an MDP R M and a reward function r, we denote the resulting MDP by M U..
Value functions and optimality conditions. We define the Q-function Quiu (s, a) and value- function V (s))(ss) (s) of a policy π in the MDP M Ur at time step h, state s and action as:
(s, = =
Σ Tn=aldd())P(s a) Q 8'
mo (s',t (s',d'): vM). = Σ na (ala))
We define the advantage function A (s, a) A Mur (8, (s V (s). A policy ा is optimal if ATuu, (s, a) is < 0 for each time step h E [H], state s E S, action a E A. We denote the set of optimal policies for the MDP M M with Mu
A
We can model any initial state distribution single initial state by modifying the transitions.
3

---

State-visitation frequencies. We define TM, (s]su) as the probability of being in state time h' 2 h following policy in MDP R M starting in state so at time h. We can compute it recursively:
h.h'
h.h 1M,r (s'[s) == | and
+ (s'[s) = Σ P(s's"" ((s'|s",a)<w ()), (s"[s).
MM,5
s"
We can define the visitation frequencies for atate-action pairs analogously (see Appendix B.1.
4 Active Learning for Inverse Reinforcement Learning (Active IRL)
In this section, we first introduce the Active Inverse Reinforcement Learning problem with and without a generative model (Section Then, we define the feasible reward set for finite-horizon MDPs (Section 4.2) and characterize the error propagation on the reward function and the value function (Section 4.3 extending results by Metelli et al. (2021) to the finite horizon setting.
4.1 Problem Definition
Our goal is to design an exploration strategy to construct a dataset of demonstrations DD such that an arbitrary IRL algorithm can recover a good reward function from it. To be agnostic to the choice of IRL algorithm, we consider the set of all feasible reward functions for specific expert policy. Formally, we consider IRL problems (M. consisting of an MDP and an expert policy π " and we define the feasible reward set as follows.
Definition 1 (Feasible Reward Set). A reward function is feasible for IRL problem (M, if and only if the expert policy _ is optimal in M U r. We call the set of all feasible reward functions Mu the feasible reward set. If estimate the transition model and expert policy from samples, we refer to the recovered feasible set Rg = RRuuss in contrast to the exact feasible set Rg- MUTE.
Now, we can formalize the goal of Active IRL. as finding a exploration strategy that satisfies the following PAC optimality criterion.
Definition 2 (Optimality Criterion). Let Rag be the exact feasible set and Rgg be the feasible set recovered after observing 2 0 samples collected from M and R We say that algorithm for Active IRL is (c, 5, n) coo-cot if after n iterations with probability at least 1 it holds that:
inf F F E'lll
sup
max (Mur (8,a) - Qt (s, a))
each r E Ræ, Se foreach
s,a Mue
Mur (s, - Qu - (s, a) se for each i E R.g.
inf
sup
max s,a,h
rE
where x² is an optimal policy in MU and ft is an optimal policy in MU
The first condition states that for each reward in the exact feasible set, the best reward we could estimate in the recovered feasible set has low error everywhere. This condition is type of "recall": every possible true reward function needs to be captured by the recovered feasible set. The second condition ensures that there is possible true reward function with low error for every possible recovered reward function. This avoids an unnecessarily large recovered feasible set. This condition is type of "precision": if we recover reward function, it has be close to a possible true reward function. Note, that Metelli et al. (202I) consider similar optimality criterion in their Definition 5. However, they consider known target environment; hence, our Definition is stronger requirement.
4.2 Feasible Rewards in Finite-horizon MDPs
Ng et al. (2000) characterize the feasible reward set implicitly in the infinite horizon setting, whereas Metelli et al. (2021) characterize it explicitly. Here, provide similar results for a finite horizon.
Lemma 3 (Feasible Reward Set Implicit). A reward function is feasible if and only for all a, h it holds that: (s. 0 if oT (a]s) 2 O and A (s, a) I 0 if (a(ss) O. Moreover, if the second inequality is strict, nt is uniquely optimal, i.e., Miuur {n E].

---

Lemma 4 (Feasible Reward Set Explicit). A reward function r is feasible if and onty if there exists an {Ai E ISSAA hemm and {Vi E 1 heem such that for all s, S, h it holds that:
= A
+ Vi((s + Σ
Here, the first term ensures there is an advantage function for x² and it for actions the expert takes and (s, a) for actions the expert does not take. The second term corresponds to reward reward-shaping by the value function.
4.3 Error Propagation
Next, study the error propagation of estimating the transition model P with P and the expert policy TH with म In particular, we bound the estimation error on the reward as a function of the estimation errors of P and A extending a result by Metelli et al. (2021) to the finite horizon setting.
Theorem 5 (Error Propagation). Let (M, and (M, R) be two IRL problems. Then, for any r E RM there exists f R R(M such that:
(rn(s,a)= ()) S An( - (als)) V1t1(6')P(()) - (()
and we can bound Vn, S (H - Rmax and An S (H Rmax.
In IRL, we cannot hope recover the expert's reward function perfectly. Instead, we aim to estimate a reward function that leads to an optimal policy with performance close to the expert's 's policy under the (unknown) real reward function. For example, suppose a specific state is difficult to reach the environment. In that case, the error the reward function r(s, :) will not impact the performance of the induced policy much. Formally, we are interested in studying the error propagation to the optimal value function. The next lemma will be crucial for analyzing this.
Lemma 6. Let M be MDP'R, R, f two reward functions with optimal policies ,²,#" Then,
(s, Qu0 (8. S Σ5 Σ
(olle a'),"')s,)) "MM a'',a'ls,))) (rnc(s',d)) fw((s'aa) ,'))
By combining this lemma with Theorem 5 we can decompose the error in the value function and Q- function into the error estimating the transition model and the error in estimating the expert policy.
5 Recovering Feasible Rewards with a Generative Model
As warmup, let us first study the sample complexity of a simple uniform sampling strategy with access to the generative model M. We assume we can query a generative model about state-action pair (s, a) to receive next state s' P(-|ss, ((-|ss, a) and an expert action ag ~ π (-Is). This allows to introduce key ideas and serves as a baseline to compare later results to. We adapt the infinite-horizon results by Metelli et al. (202I) to the hhoteehorizzon setting, and our stronger PAC requirement in Definition 2] We first discuss how we can estimate the transition model and the policy (Section 5.1
before stating the sample complexity of the uniform sampling strategy (Section 5.2
5.1 Estimating Transition Model and Expert Policy
a, 8') ) be the number of times we observed the transitions (s, a, at time In each iteration k; let n as h up iteration k. Also, we define n (s, Σ, (s,, a, 8'), and n² (s) E. n (s, a). Then we can estimate the transition model and expert policy by
Σ n (s.
nt( a)
Pa(('ls,a)= =
F (a(s)))=
max(1, Σ
n (s.
max(1,nf(s)
5

---

Algorithm AcelRL algorithm for IRL in an unknown environment.
Input: significance 8 (0, target accuracy e, IRL algorithm s number of episodes NE
2: Initialize k +- 0, co +- H/10
3: while c > c/4 do
4: Solve (convex) optimization problem ACE to obtain
5: Explore with policy иe for NE episodes, observing transitions and expert actions
6: & <- k +11
7: Update Pk, #kg, C% and tR +- (R
8: Update accuracy + max, (s
9: end while
10: return Estimated reward function f*
In Appendix B.3 we derive Hoeffding's s confidence intervals for the transition model and the expert we can compute the uncertainty on the recovered reward as: policy. Combining these with Theorem 3
2e (s, Ch a) = (H Bmax min 1.2
n2 (s.
where (s, log (24SAH /6) We show that for any pair of reward functions E Ry and E R. the difference (s, a) fx, (s, s O (s, a). This uncertainty estimate will be a key component in all of our theoretical analysis.
5.2 Uniform Sampling Strategy
each iteration k, the uniform sampling strategy allocates mmmax samples uniformly over [H] x x A. estimates the reward uncertainty and stops as soon H maX Cs, characterizes the sample complexity of uniform sampling with generative model.
(s, a) S e. The next theorem
Theorem 7 (Sample Complexity of Uniform Sampling IRL). The uniform sampling strategy fulfills Definition with number of samples upper bounded by:
n S 0 H R2 R SAIē).
max
where O suppresses logarithmic terms.
This sample complexity bound appears slightly worse than the one in Metelli et al. (2021). who find (1- which would translate to H This is, however, due to the fact that we consider reward functions that can depend the timestep h. If we assume the reward function does not depend on h, we gain a factor of H, obtaining the same result as Metelli et al. (2021).
Active Exploration for Inverse Reinforcement Learning
Let us now turn to our original problem: recovering the expert's reward function in an unknown environment without generative model. This problem is harder since need create an exploration strategy to acquire the desired information about the environment. We now propose novel sample- efficient exploration algorithm for IRL that we call Active exploration for Inverse Reinforcement Learning (AceIRL). The algorithm takes inspiration from recent works on reward-free exploration (Kaufmann al. 202T) and exploration strategies RL (Auer of the algorithm into two parts. First, we introduce simplified version of the algorithm, which comes with a problem independent sample complexity result (Section 6.1 Next, we introduce the full algorithm, which considers the expected reduction of uncertainty in the next iteration to improve exploration and maintains a confidence set plausibly optimal policies to focus on the most relevant regions (Section 6.2). The full algorithm provides tighter, problem-dependent sample complexity bound (Section 6.3p. Algorithm[D contains pseudo-code of AcelRI, and Appendix contains the detailed theoretical analysis including proofs of all results discussed here.
2008). We divide the explanation

---

6.1 Uncertainty-basee Exploration for IRL
The first idea of AceIRL is similar reward-free UCRL (Kaufmann et al. (02I). Our goal fulfill the PAC requirement in Definition Hence, we start from an upper bound on the estimation error between the performance of the optimal policy R* for reward f E Rg in the recovered feasible set and the optimal policy x" for reward function E Ra in the true MDP M. We will then use this upper bound to drive the exploration. For each timestep h and iteration k, we define the error:
( a: T" #*) = MMi a) - (5,
(I)
We can define an upper bound on these enrors recursively with C (s, a) 0 and
(s, min ( Rmax (s, P(s'ss a) max d'EA
E E (d).
(EB1)
It is straightforward to show that ég (s. 0; " (s, (s, a) for any two policies x². f". Using this error bound, we can introduce a simplified version of AceIRL that explores greedily with respect to (s, a). We call this algorithm "AceIRI. Greedy". Note that this is equivalent to solving the RL problem defined by M U C: hence, we can use any RL solver to find the exploration policy in practice. If we explore with this greedy policy, we can stop if:
4 max F. (5o, a) <.
(SP1)
We can show that when this stopping condition holds, the solution fulfills the PAC requirement Furthermore, we show in Appendix /B.4 that AceIRL Greedy achieves a sample complexity on order Ô &H&R SAfee" which matches the sample complexity of uniform sampling with a generative model. This is already a strong result implying that we do not need generative model achieve a good sample complexity for IRI. However, it turns out we can improve the algorithm further.
6.2 Problem Dependent Exploration
AceIRL Greedy is limited in two ways: (i) explores states that have high uncertainty so far, whereas our goal is to reduce uncertainty in the next iteration, and (ii) it explores to reduce the uncertainty about all policies, whereas our goal is to reduce the uncertainty primarily about plausibly optimal policies. To address these limitations, we propose two modifications that yield the full AcelRI. algorithm.
Reducing future uncertainty. The greedy policy w.r.t. E explores states in which the estimation error on the Q-functions is large. However, note that this is not exactly what we want, namely, to reduce the uncertainty the most. In particular, if we explore for more than one episode before updating the exploration policy, we should choose an exploration policy that considers how the uncertainty will reduce during exploration. Ideally, we would explore with a policy that minimizes E However, we cannot compute this quantity exactly. Instead, we can approximate it using our current estimate of the transition model. Concretely, if we have an exploration policy म, we can estimate the reward uncertainty at the next iteration as:
(8) Sh (s, = (H h)) Rmnx min 1.2 ( a) + n (s,
where (s) NE 7 (s, a/so) is the expected number of times visits (s, a) time h and Ng is the number of episodes will explore with We can this estimate to find policy that minimizes our estimate of E While original approach was akin to "uncertainty sampling", we now have a better way to measure the "informativeness" of choosing an exploration policy. This a common pattern when designing query strategies in active learning (Setles) 2012). Note, that this argument does not rely on the IRL problem and can be used to independently improve algorithms for reward-free exploration (cf. Appendix (D).
0.4
Focusing on plausibly optimal policies. By exploring greedily w.r.t. E we reduce the estimation emror of all policies. However, we are primarily interested in estimating the distance between policies T" E Muu and ** E MuM with r E Ræ and f E Rg.- Of course, we do not know these sets, so we cannot use them directly to target the exploration. Instead, assume we can construct set of
7

---

plausibly optimal policies II, that contains all x² and #g with high probability. Then, we can redefine upper bounds recursively as FN (s, a) and:
(s. min ( Rmaxs (s. P(s(ss,,a) max *ellz-1
((t (EB2)
In contrast (EB1). we maximize over policies in II rather than all actions. Acting greedily with respect P (s, a) equivalent finding the optimal policy wa M. for the RI problem defined by MUC To construct the set of plausibly optimal policies,
arbitrary IRL algorithm d/ We only assume that s/ will return a reward function t& E Rg. Then, we can construct a set of plausibly optimal policies II {
MuA. (50) VT, (so) - 10cx). We show in Appendix B.5 that Il MuRy
contains both x² and के with high probability. This choice is based on ideas by Zanette et al. (019))
We can define a stopping condition analogously to (SPI)
max (x a) S.
(SP2)
Again, we can prove that if the algorithms stops due (P2 then R.g. respects Definition Implementing AceIRL. To implement the full algorithm, we need to solve an optimization problem:
E argmin max F ((8))
(ACE)
x #Efi.-
The solution this problem the exploration policy that minimizes the uncertainty the next iteration about plausibly optimal policies. This combines both modifications we just discussed. This problem might seem difficult to solve first, but, perhaps surprisingly, can be formulated convex optimization problem solvable with standard techniques (cf. Appendix B.6
6.3 Sample Complexity of AceIRL
In this section, we present our main result about the sample complexity of AceIRL. The result is problem-dependent, and, in particular, depends on the advantage function A Mu, a), where is the reward function in the exact feasible set R.g closest to the reward function n'. which belongs to the estimated feasible set R.g. The advantage function A A Mur (s, a) acts similarly to suboptimality
gap: the closer the value of the second best action is to the best action, the harder it to identify the best action and infer the correct reward function.
Theorem 8. [AceIRL Sample Complexity] AcelRL returns (e, 6, n)-correct solution with
H SA
SA
H H
n nSO
min
ming ( (x, (222
where -1 depends on the choice of NE, the number of episodes of exploration in each iteration. A Mur (8,a) is the advantage function of r E argmin, maxp,s,a (Fn (8, ,, a) - (8, the reward function from the feasible set Rog closest to the estimated reward function fx-
This result is the minimum of two terms. The first term is problem independent and it is achieved both by AceIRL Greedy and the full AceIRL. This bound matches the bound we saw previously with generative model. Hence, AceIRL achieves the same results without access to the generative model. Using (ACE) can yield better sample complexity, represented by the second term in the minimum. This bound depends on two main components: the ratio c--1/c and the advantage function
A Mur (s, a). The ratio depends the choice of Ng, the number of exploration episodes per iteration. NE is small, then the e-ratio will be also small. If Ng is large the algorithm will perform similarly to uniform sampling strategy. Appendix B.5 provides the full proof of this theorem.

---

Uniform sampling
TRAVEL (gener. model)
Random Exploration
AceIRL
AcelRL. (Full)
(gener. model)
Metelli al. 2021 2021
Gready
Four Paths (Figure
1900 + 71
17840 1896
.Rk 50
1560 76
24150 + 1747
10780 1369
.E 1000
2000
32760 + 2172
14080 + 1603
-NR = 200
1000 = 0
52000 = 4037
16160 + 2033
Double Chain
Kaufimann al. 2021
1980 + 66
236-10 2195
We 50
1120 1: 46
16240 842
11580 1 870
-ig
22200 1329
15440 1031
NN 200
1000 + 0
37200 + 1664
20400 + 1629
Metelli et 2021
Kandom MDI
22
22
4: 153
Chain (Np = 1)
78 =
76 +
161 + 8
142 1 9
Gridworld =Nx=1)
43 2
35 1 2
45 1::22
46 1 3
48
Table 1: Sample complexity of AceIRL compared to random exploration and methods that use a generative model. We show the number of samples necessary to find policy with normalized regret less than 0.4. We report means and standard errors computed over 50 random seeds each. For each environment, we highlight in bold the method that achieves the best performance without access to generative model. If multiple methods are within one standard error distance, we highlight all of them. Overall, AceIRL is the most sample efficient method without a generative model if Ng is chosen small enough. In Appendix C.3 we show learning curves for all individual experiments.
7 Experiments
We perform series of simulation experiments evaluate AcelRI. We simulate a (deterministic) ex- pert policy using an underlying true reward function, and compare it to the recovered reward functions, We provide code to reproduce all of our experiments https://ge wtw.ttooooooeoeetetttttttttttttt hatp///aagooo/aaee/aaaa aceirl
Four Patie
Double Chain
Normalned Regret
0.4
0.2
Our main evaluation metric is normalized regret:
(VMLL :0 (oo)))oviet VV (oo)) (VMuP (eo)-VVill (so)), where n" is the optimal policy for M U A* is the optimal policy for MUA, and n* is the worst possible policy for r, i.e., the optimal policy for M U (-r).
0.8
0.8
Samples
xau6
Samples
Unif. Expl.
AceIRL Groady
AccIRL (Full)
Figure 2: Normalized regret (lower is better) of the policy optimizing for the inferred re- ward in the estimated MDP as function of the number of samples. The plots show the mean and 95% confidence intervals computed using 50 random seeds. We use Ng = 50.
We introduce the Four Paths environment shown in Figure which consists of four chains of states that have different randomly sampled transition probabil- ities. One path has goal with reward 1; all other rewards are O. We also evaluate on Random MDPs with uniformly sampled transition dynamics and re- ward functions, the Double Chain environment proposed by Kaulmann et al. (021), and the Chain and Gridworld environments proposed by Metelli al. 2022 Appendix C.I provides details on the transition dynamics and rewards of all environments.
We compare AceIRL and AceIRL Greedy to uniformly random exploration policy, as a naive explo- ration strategy. Further, we consider uniform sampling with a generative model as well as TRAVEL (Metelli al. 2021), which can be more sample efficient because they do not need to explore the envi- ronment. Note that TRAVEL is designed to learn a reward to be transferred to a known target environ- ment. Instead, we use modified version that uses the estimated MDP as target. Appendix C.2 pro- vides more details on our implementations, and we provide source code in the supplemental material.
Table T shows the sample efficiency of all algorithms in all environments, measured the number of samples needed to achieve regret threshold of 0.4 (different thresholds yield similar conclusions; cf. Appendix C). AceIRL is the most sample efficient exploration strategy without access to a generative model; but the relative differences between the methods depend on the environment. In some cases, AceIRI even performs comparably to methods using a generative model, as the theory predicts.
In the Four Paths and Double Chain environments, we also vary the Nr parameter. AceIRI performs better for small values at the computational cost of updating the exploration policy more often, If

---

NE is too large, using AceIRL can be as bad as uniformly random exploration policy. Increasing Nr hurts the performance of AceIRL Greedy more severely, which does not consider NE explicitly, Figure shows the normalized regret function of the number of samples in Four Paths and Double Chain. In both cases AcelRI. performs best. However, AcelRI. Greedy worse than random exploration in the Four Paths environment. Hence, we find that the problem dependent exploration strategy of the full algorithm significantly improves the sample efficiency.
8 Conclusion
We considered active inverse reinforcement learning (IRL) with unknown transition dynamics and expert policy and introduced AceIRL, an efficient exploration strategy to learn about both the dynamic and the expert policy with the goal of inferring the reward function as efficiently as possible.
Our approach a crucial step towards IRL algorithms with theoretical guarantees, but future work is needed move to more practical settings. particular, it would be interesting to extend the approach to continuous state and action spaces (e.g. using function approximation), and to obtain an efficient algorithm that does not require solving convex optimization problems. From theoretical perspective. it would be useful to derive lower bound on the sample complexity of the IRL, problem, to understand the IRL problem inherently more difficult than usual RL. Beyond IRL, we believe that some of our methods could be useful for other settings, such as reward-free exploration (cf. Appendix (D)
Sample efficient IRL promising way apply RL in situations where there is well-specified reward function available. Of course, even robust IRL algorithms pose a risk of misuse. But, we are optimistic that these methods will overall lead safer RL systems that be used in real applications.
Acknowledgements
This project has received funding from the Microsoft Swiss Joint Research Center (Swiss JRC), Google Brain, and from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme grant agreement No 815943. We thank Bhavya Sukhija for valuable feedback on an earlier draft.
References
P. Abbeel and A. Y. Ng. Exploration and apprenticeship learning in reinforcement learning. In Proceedings of International Conference on Machine Learning (ICML), 2005.
D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané. Concrete problems in Al safety. a60iv: 06565, 2016.
P. Auer, T. Jaksch, and R. Ortner. Near-optimal regret bounds for reinforcement learning, Advances in Neural Information Processing Systems, 2008
D. S. Brown, Y. Cui, and S. Nickum. Risk-aware active inverse reinforcement learning. In Conference on Robot Learning (CoRL), 2018
R. Cohn, E. Durfee, and S. Singh. Comparing action-query strategies in semi-autonomous agents. In AAAI Conference Artificial Intelligence, 2011.
G. Dexter, K. Bello, and J. Honorio. Inverse reinforcement learning in a continuous state space with formal guarantees. In Advances in Neural Information Processing Systems, 2021.
Diamond and S. Boyd. CVXPY: A Python-embeddded modeling language for convex optimization. Journal of Machine Learning Research, 1,5
Haarojja, S. Ha, A. Zhou, Tan, G. Tucker, and Levine. Learning to walk via deep reinforcement learning. In Proceedings of Robotics: Science and Systems (RSS), 2019.
D. Hendrycks, N. Carlini, Schulman, and Steinhardr. Unsolved problems MI. safety. 11X1::2009.13916, 2021.
10

---

T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563-1600, 2010.
C. Jin, A. Krishnamurthy, M. Simchowitz, and T. Yu. Reward-frre exploration for reinforcement learning. Proceedings of International Conference on Machine Learning (ICML), 2020.
S. Kakade and J. Langford. Approximately optimal approximate reinforcement learning. In Proceed- ings of International Conference on Machine Learning (ICML), 2002.
E. Kaufmann, Ménard. O. D. Domingues, A. Jonsson, E. Leurent, and M. Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, 2021.
Kulick, M. Toussaint, T. Lang, and M. Lopes. Active learning for teaching a robot grounded relational symbols. In Proceedings of International Joini Conferences on Artificial Intelligence, 2013.
S. Levine, Z. Popovic, and V. Koltun. Nonlinear inverse reinforcement learning with Gaussian processes. Advances in Neural Information Processing Systems, 2011.
M. Lopes, F. Melo, and L. Montesano. Active learning for reward estimation in inverse reinforcement learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2009.
D. P. Losey and M. K. O'Malley. Including uncertainty when learning from human corrections. In Conference on Robot Learning (CoRL), 2018
A. M. Metelli, G. Ramponi, A. Concetti, and M. Restelli. Provably efficient learning of transferable rewards. In Proceedings of International Conference on Machine Learning (ICML), 2021.
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Ried- miller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep reinforcement learning, nature, 518(7540):529-533 2015.
A. Y. Ng. S. J. Russell, et al. Algorithms for inverse reinforcement learning, In Proceedings of International Conference on Machine Learning (ICMI), 2000.
B. O' Donoghue, E. Chu, N. Parikh, and S. Boyd. Conic optimization via operator splitting and homogeneous self-dual embedding. Journal of Optimization Theory and Applications, 169(3): 1042 1068, June 2016. URL http: / /ttf//taffordrrr/o edu//boyd/ Bastu//boo//ppppr/////eaa papprs/ sscpersssccs.o html
M. L. Puterman. Markov decision processex: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
N. Rajaraman, L. Yang, J. Jiao, and K. Ramchandran. Toward the fundamental limits of imitation learning. Advances in Neural Information Processing Systems, 2020.
D. Ramachandran and E. Amir. Bayesian inverse reinforcement learning. In Proceedings of Interna- fional Joint Conferences on Artificial Intelligence, 2007.
N. D. Ratliff, J. A. Bagnell, and M. A. Zinkevich. Maximum margin planning. In Proceedings of International Conference on Machine Learning (ICML), 2006.
B. Settles. Active Learning. Morgan & Claypool Publishers, 2012.
I. Shani, T. Zahavy, and S. Mannor. Online apprenticeship learning. In AAAI Conference on Artificial Intelligence, 2022.
R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
T. Xu, 7. Li, and Y. Yu. Error bounds of imitating policies and environments. In Advances in Neural Information Processing Systems, 2020.
A. Zanette, M. J. Kochenderfer, and E. Brunskill. Almost horizon-free structure-aware best policy identification with generative model. H. Wallach, H. Larochelle, Beygelzimer, F. d' d'Alché- Buc, E. Fox, and R. Gamett, editors, Advances in Neural Informaiinn Processing Systems, 2019.
B. D. Ziebart, L.. Maas, J. Bagnell, A. K. Dey, et al. Maximum entropy inverse reinforcement learning. In AAAI Conference Artificial Intelligence, 2008


Reviews:
[{"review_id": "RhcunMnS85f", "reviewer": "Reviewer_qWnj", "summary": "The paper explores the problem of active IRL, where the goal is to explore the environment to infer a good reward function. The paper addresses the Active IRL problem without assuming access to the transition model of the environment or the expert's policy. The paper proposes the Active Exploration for IRL (AceIRL) method and analyzes two sampling strategies. Finally, the paper evaluates AceIRL in 4 environments comparing normalized regret and sample efficiency to baselines.\n", "questions": "* Why is the sample complexity of AceIRL Greedy higher empirically than Uniform Sampling (gener. model) in the Four Paths and Double Chain environments in Table 1 when the theoretical sample complexity bounds are the same? In Four Paths and Double Chain environments, the sample complexity of AceIRL greedy is over an order of magnitude higher than that of Uniform Sampling (gener. model). \n* How does the Random Exploration baseline work? I do not see it described in the text.\n* Why does AceIRL Greedy underperform Random Exploration in the Four Paths environment? This is surprising since AceIRL Greedy tries to minimize the reward estimation error. \n* Why are the results on the environments from [1] so different from the first two in Table 1? The gap between AceIRL and baselines is much larger in the first two environments, and AceIRL greedy outperforms AceIRL Full in some of the settings from [1]. What is the reason for this difference?\n\n[1] A. M. Metelli et al. Provably efficient learning of transferable rewards. In Proceedings of International Conference on Machine Learning (ICML), 2021.", "limitations": "The paper discusses that the method is limited to discrete state and action spaces, and future work will extend it to continuous states and actions. The paper also states the efficiency limitations of iteratively solving convex optimization problems in the algorithm. Potential negative social impacts are also discussed.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* AceIRL tackles the important problem of Active IRL without any generative model. No assumption of a generative model is an important improvement over baselines like TRAVEL. In my understanding, AceIRL is the first method for Active IRL without a generative model.\n* Two versions of AceIRL are studied and theoretically analyzed with sample complexity bounds. \n* The paper characterizes the goals of Active IRL with Definitions 1 and 2. Furthermore, the paper studies the impact of using learned generative models for the expert and transition model on the recovered reward in the finite horizon setting.\n* The paper is the first to study Active IRL in the context of finite-horizon, undiscounted MDPs.\n\nWeaknesses:\n* In the related work, I would like to see more comparisons to how active IRL relates to the standard IRL problem. For example, what is the relationship between Active IRL methods and other IRL methods such as Apprenticeship IRL [4] or MaxEnt IRL [3]? Furthermore, in contrast to the claim on line 63, many recent IRL algorithms that use function approximation do not assume the underlying transition model is known, such as the f-IRL method [2]. Are these methods not applicable to the active IRL setting?\n* How does Theorem 1 differ from Theorem 3.1 of [1] since both characterize the impact of error propagation from learned generative models? \n\n[1] A. M. Metelli et al. Provably efficient learning of transferable rewards. In Proceedings of International Conference on Machine Learning (ICML), 2021.\n[2]  Ni, Tianwei, et al. \"f-irl: Inverse reinforcement learning via state marginal matching.\" arXiv preprint arXiv:2011.04709 (2020).\n[3] Ziebart, Brian D., et al. \"Maximum entropy inverse reinforcement learning.\" Aaai. Vol. 8. 2008.\n[4] Abbeel, Pieter, et al. \"Apprenticeship learning via inverse reinforcement learning.\" Proceedings of the twenty-first international conference on Machine learning. 2004.", "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": "FraCFVPvZss", "reviewer": "Reviewer_Jvjh", "summary": "this paper proposes AceIRL, which is an IRL algorithm with active explorations in unknown environments. Authors give some novel analysis on this newly proposed method and empirically, AceIRL outperfroms some naive exploration methods. ", "questions": "why not conduct experiments on some complex environment like MuJoCo?", "limitations": "No", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nnovle algorithm to explore the environment and the expert policy to infer a good reward signal.\n\nprovides two exploration strategies for AceIRL, and the algorithms are sound\n\n\nWeaknesses:\n\nthe experiments seem not enough for evaluation. why not conduct experiments on some complex environment like MuJoCo?", "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": "EpwMLPX1UO", "reviewer": "Reviewer_LBnb", "summary": "The idea is to drive exploration to build the ideal set of demonstrations so that any IRL algorithm can reconstruct a reward function that leads to a policy as close as the optimal one, with a fixed limited number of examples.\nThe authors first set up a PAC criteria that their algorithm must verify in order to converge.\nThen, they analyse three strategies\n- A (oracle) uniform sampling as baseline\n- A greedy exploration that picks transitions that reduce the IMMEDIATE uncertainty about the value associated with ANY policy.\n- A smarter exploration that picks transitions that reduce the FUTURE uncertainty about the value associated with THE OPTIMAL policy.\n\nThey compare theoretical complexities and empirical performances of these different strategies.", "questions": "Cf minor critics above.", "limitations": "Not applicable.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is nicely written, the methodology is well driven and brings a solid solution to the problem. \nI did not go through the proof, but the mathematical claims look intuitively correct. \nThe empirical results are reflecting the theoretical findings, and they are verified over 50 seeds. \n\nI would only have minor critics:\n\n1) The abbreviation PAC (Probability Approximately Correct) is never written without abbreviation (so I had to check the meaning in another paper).\n2) In Theo. 1, A and V  are associated with which MDP’s reward? (the ground truth or the approximation?)\n3) Detail: in lemma 3, “theorem 4” should be “theorem 1”.\n4) L209: if you use the word “straightforward”, you have to at least explain why it is straightforward (in this case, triangular inequality with bellman equations?)\n5) L256 Why is it “surprising”?\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": "760FjGu33Uz", "reviewer": "Reviewer_uWZB", "summary": "This paper considers the problem of active learning in explorations for inverse RL. And this paper provides necessary and sufficient conditions for solving such active learning problem.  They theoretical analyze the estimation error of the reward function caused by the error in transition function and expert policy. A novel algorithm AceIRL is proposed in this paper whose idea is to actively explore sample with large uncertainties for learning a better reward function. Some empirical experiment results are presented to support the theories. And the proposed method performs better than naive exploration strategies.  ", "questions": "I have a concern regarding the scalability of the proposed algorithm to large state and action spaces MDPs. The proposed transition model and expert policy model are calculated by using the frequency which is actually not sample efficient. And it may lead to a large variance estimation although they are unbiased. Can you provide some explanation for this problem?   \n\nAnd the idea of focusing on plausibly optimal policies is a good way to reduce sample complexity. But in the real experiments, there is no description for how you choose the optimal policy set. It will be great if you can present some details for your experiment. \n\nIn the experiments, only sample complexity is considered. It will be good if you can include the comparison of estimation errors. \n", "limitations": "Yes. The authors provides adequate information for this. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: Overall, this paper is well written. The theorems are presented in a clear way. Sufficient number of theoretical analysis are provided to support the main result. I like the idea of applying a similar technique in UCRL to the inverse RL problem for estimating a better reward function. The proposed algorithm makes a lot of sense to me. The problem considered in this paper is promising since it is important to select samples in a efficient way for estimating the reward function. When the reward function is hard to learn, the proposed method has significant advantage over other random sampling based algorithm. \nWeaknesses: The empirical result in this paper is not sufficient to show the benefits of active learning for IRL problems. ", "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