Bayesian Methods for Constraint Inference in Reinforcement Learning
Authors: Dimitris Papadimitriou
Usman Anwar
Daniel S. Brown
Venue: Accepted by TMLR ()

Abstract: Learning constraints from demonstrations provides a natural and efficient way to improve the safety of AI systems; however, prior work only considers learning a single, point-estimate of the constraints. By contrast, we consider the problem of inferring constraints from demonstrations using a Bayesian perspective. We propose Bayesian Inverse Constraint Reinforcement Learning (BICRL), a novel approach that infers a posterior probability distribution over constraints from demonstrated trajectories. The main advantages of BICRL, compared to prior constraint inference algorithms, are (1) the freedom to infer constraints from partial trajectories and even from disjoint state-action pairs,  (2) the ability to infer constraints from suboptimal demonstrations and in stochastic environments, and (3) the opportunity to use the posterior distribution over constraints in order to implement active learning and robust policy optimization techniques. We show that BICRL outperforms pre-existing constraint learning approaches, leading to more accurate constraint inference and consequently safer policies. We further propose Hierarchical BICRL that infers constraints locally in sub-spaces of the entire domain and then composes global constraint estimates leading to accurate and computationally efficient constraint estimation.  

Published in Transactions on Machine Learning Research (10/2022)
Bayesian Methods for Constraint Inference in Reinforcement Learning
Dimitris Papadimitriou UC Berkeley
dimitri@berkeley.com edu
Usman Anwar University of Cambridge
ua2370ccmmmmmm uk
Daniel S. Brown University of Utah
edu
Reviewed on OpenReview: https: // optpevveew....ew....mo. net/ forum? id= ott5r
Abstract
Learning constraints from demonstrations provides a natural and efficient way to improve the safety of Al systems; however, prior work only considers learning a single, point-estimate of the constraints. By contrast, we consider the problem of inferring constraints from demonstrations using a Bayesian perspective. We propose Bayesian Inverse Constraint Reinforcement Learning (BICRL), a novel approach that infers a posterior probability distribution over constraints from demonstrated trajectories. The main advantages of BICRL, compared to prior constraint inference algorithms, are (1) the freedom to infer constraints from partial trajectories and even from disjoint state-action pairs, (2) the ability to infer constraints from suboptimal demonstrations and in stochastic environments, and (3) the opportunity to use the posterior distribution over constraints in order to implereent active learning and robust policy optimization techniques. We show that BICRL outperforms pre-cxisting constraint learning approaches, leading to more accurate constraint inference and consequently safer policies. We further propose Hicrarchical BICRL that infers constraints locally in sub-spaces of the entire domain and then composes global constraint estimates leading to accurate and computationally efficient constraint estimation.
1 Introduction
Reinforcement Learning (RL) algorithms have proven effective in providing policies for a wide range of dynamic decision making tasks (Muih et al., 2013 Polydoros Nalpantidis) 2017 Charpentier et al. 2021] However, manually specifying reward function in environment to encourage agent to perform specific task is a nontrivial process. To alleviate this issue, Inverse Reinforcement Learning (TRL.) aims at inferring a reward function by observing the behavior of an expert agent performing a specified task (Russell) 1998). While many different IRL approaches have been proposed to infer non-degenerate reward functions from finite set of expert. trajectories (Arora & Doshi 2021), , in many cases may not be necessary infer the entire reward function, since partial information regarding the reward function might be available. For example, in safety critical applications such as robotic surgery (Lanfranco al.) 2004) and autonomous driving (Shafaei et al. 2018), the basic goal of task may be known (e.g. move the robot end effector to particular position using minimal energy minimize travel time while avoiding collisions), but there may be user-specific constraints that are unknown (e.g. constraints on the amount of pressure applied during surgery or the proximity to people or other cars when driving). In these cases, we desire algorithms that can infer the unknown constraints by observing demonstrations from an expert in the environment.
Prior work has considered constraint learning from demonstrations in mazimum likelihood setting, without considering utilizing representation of uncertainty of the constraints. Chou et al. (018) reason that

---

Published in Transactions on Machine Learning Research (10/2022)
trajectories that result in lower cumulative costs than the demonstrated ones must be associated with constraints. Based on the same notion, (Scobee & Sastry (019)) propose greedy method to add constraints in MDP so that the expert demonstrated trajectories are more likely under that choice of constraints. Finally, Anwar et al. (2020) extend the aforementioned method to contimuous state spaces with unknown transition models. Park et al. (2020) use a Bayesian non-parametric approach to estimate a sequence of subgoals and corresponding constraints from demonstrations; however, they only obtaín the MAP solution and assume the demonstrator never violates constraints. By contrast, we infer full Bayesian posterior distribution over constraints while considering demonstrators that are imperfect and may sometimes accidentally violate constraints. Maintaining a belief distribution over the location and likelihood of constraints is important for many downstream tasks such as active query synthesis (Settles 2009), Bayesian robust optimization (Brown et al. 2020a Javed el al. 2021) and safe exploration (Garcia & Fernández 2015
In this work, we formulate the constraint inference problem using a Bayesian perspective and demonstrate that our approach has a number of advantages over prior work. For example, as opposed to the maximum likelihood counterpart (Scobee & Sastry 2019) which requires full expert trajectory demonstrations, our approach works with partial trajectories (even disjoint state-action pairs) as well as full trajectories. Our proposed Bayesian approach also allows us to estimate uncertainty over the true constraints, enabling active constraint learning where the agent can query the expert for specific state actions or partial demonstrations. One benefit of learning constraints is that they are naturally disentangled from the task reward. Building on this idea, we demonstrate the ability to learn constraints a hierarchical manner: learning constraints from local demonstrations to accelerate and improve global constraint inference via a divide and conquer approach. Finally, by extending and generalizing prior work by Ramachandran & Amir 2007a), we prove that our Bayesian constraint inference approach has desirable rapid mixing guarantces.
2 Related Work
Constraint Inference: Constraint inference has generally been studied (Chou et al.
2018
2020) with
focus on inferring unknown constraints of specific types e.g. geometric (D'Arpino & Shah 2017 Subramani
et al. 2018 ; sequential (Pardowitz et al. 2005) or convex (Miryoosefi et al. 2019). As an important
innovation, Scobee & Sastry| (2019) formulated the problem of inferring general constraints in the framework of inverse reinforcement learning and provided a greedy algorithm to infer constraints in deterministic tabular environments. Their proposed approach has since been extended to work with stochastic demonstrations McPPerson et al. 2021) and continuous state spaces (Stocking al., 2022 Anwar et al. (2020) developed alternative approach, with focus on scaling to high dimensional continuous stale space environments. Chou et al. (2022) in parallel have developed an approach to learn Chance-constrand using Gaussian processes for motion planning.
Preference Learning and Inverse RL: Constraint inference can also be viewed as a special case of preference learning (Christiano et al.] (0017). Preference learning focuses on learning the preference order over outcomes through means of ratings (Daniel et al.) 2014), comparisons (Christiano et al. 2017 Sadigh et al., 2017), human interventions MMcGGlahaan et al. 2017 Hadfield-Menell et al.)
2017a] other forms of human Teedback (Jeon et al., 2020). Demonstrations (Ziebart et al. 2008) Finn et al.
2016 Brown et al. 2020c) are a particularly popular form of feedback. In imitation learning (Ross et al. 2011), provided demonstrations are considered optimal and the AI agent is trained to reproduce the demonstrated behavior. However, imitation learning is known to suffer from issues such as lack of robustness to noisy observations (Reddy et al. 2020
distribution shift (Ross et al. 2011) and fragile lcarning (Zolna et al., 2019). Inverse reinforcement lcarning [Russel] 1998 Ng et al.] 22000] Abbeel & Ng) (2004) avoids some of the issues of imitation learning by learning
explicit reward function from demonstrations first and using regularizers (Finn et al. 2016 Fu et al. 2018
priors [Raachhnnrrnn & Amir 2007b Michini & How 2012 Jeon et al.] 2018) or robust optimization (Javed
et al.
2021) to generalize faithfully. Bayesian IRL (Ramachandran & Amir 2007b Brown et al.
2020a
Chan & van der Schaar 2020), in particular, attempts to learn a distribution over possible reward functions.
Reward Function Design: Our work also connocts with the wider litcrature on safe reward function design which focuses on minimizing or avoiding side effects [Turner et al.] 2020) due to reward misspecification. The approaches in this area either manually design a reward function regularizer that inhibits the tendency of RL.
2

---

Published in Transactions on Machine Learning Research (10/2022)
agent to act destructively in the environment or learn such regularizer from information leaked provided by humans. Turner et al. (2020) use attainable utility preservation regularizer which is closely linked to the idea of reachability (Krakovna& et al. 2018). Shah et al. (2019) learn the regularizer term by ensuring that the world state in the final state of a demonstration trajectory is maintained. [Hadfeld-Menell et al. (2017b) consider the given reward function as true reward function only on the given enviromment and then use Bayesian inference to infer the correct reward function when the environment undergoos any change.
Safe Reinforcement Learning: In safe reinforcement learning (Garcia & Fernández 2015), the objective is to learn a policy that maximizes the given reward while ensuring minimal constraint violations. In most of the prior works |Garcia & Fernández 2015 Achiam et al. 2017 Tessler ct al. 2018 Calian ct al. 2020; Srinivasan et al., 2020), it has been assumed that the constraint set is known and the focus has been on improving algorithms to learn improved constraint abiding policies efficiently. (Yng et al. (2021) is a notable exception to this trend which assumes that constraints are specified through natural language.
3 Bayesian Constraint Inference
3.1 Preliminaries
Constrained Reinforcement Learning (CRL) Garcia & Fernández 2015), is generally studied in the context of Constrained Markov Decision Processes (CMDP). A CMDP, Mc, is a tuple (S, A, P. R, ?), where S denotes the state space and A the action space, We denote the transition probability : 5 state s following action a with P(s' s. a). The transition dynamics are considered known throughout this paper. We denote with R: S x + E the reward function, with C the set of constraints and with y (0, the discount factor. If the state space is discrete with |S| n, then the constraint set C 10, can be modeled as an n-ary binary product where Clj] = 11 means that the state (l,....,,) nu is constraint state. Further, we use the indicator function Ic to denote membership over the constraint set. Denoting the action policy with n, the CRL objective can be written as follows
+ S from a
T
T EnNT Σ IIc(s.a)) 0.
max
E
BANT
Σ yf RRs Ex((ss,a)
s.t.
(1)
One way to solve Eq. ① is by formulating the Lagrangian of the optimization problem and solving the resulting min-max problem
min max 50
Bass
Σ Ex'R(s,a))
tr
Bann
Σ To(s, (0)
(2)
where rp E (-o0, 0| denotes the Lagrange multiplier. Intuitively, the Lagrange multiplier Tp can be interpreted as the penalty an agent will incur in terms of reward for violating a constraint. Prior work by Paternain et al. (2019), shows that the problem has zero duality gap and hence the solutions of the aforementioned two problems are equivalent. We leverage this fact to pose the constraint inference problem as the inverse of Problem 2 This novel perspective helps us utilize off-the-shelf efficient RL solvers to obtain an optimal policy from Problem (2) for fixed values of rp- That allows us to formulate the constraint inference task as a Bayesian optimization problem over the unknown parameters, without solving a min-max problem. In contrast, prior works (Scobee & Sastry] 2019 Anwar et al.] 2020) which formulate the constraint inference problem as the inverse of Problem
1 require the use of constrained RL solvers which are generally much
less stable and efficient.
3.2 Problem Statement
Bayesian constraint inference is the problem of inferring a distribution over possible constraint sets given Mc \ C, which denotes the nominal MDP with unknown constraints, and set of demonstrations. Denote the set of demonstrations with D, where (Ei, .2....) is composed of a number of trajectories, with each individual trajectory being denoted with & [(ff. af), af), Furthermore, opposed to prior works
3

---

Published in Transactions on Machine Learning Research (10/2022)
[Scobee & Sastry 2019: Anwar et al. 2020 we leverage the fact that problems 1 and 2 are equivalent and hence we use the formulation in 2 for constraint inference. This novel perspective, has multiple benefits: (1) learning constraints does not require making any modifications to the model of the environment (for example there is no need in modifying the action space in particular states as done in (Scobee & Sastry (2019)) )): (2) it allows for learning demonstrator's "risk tolerance" level through learning of rpi and (3) this in turn allows the use of standard, and more stable, RL algorithms to solve for the CMDP in the place of CRL algorithms, which are often difficult to tune (Anwar et al. 2020
3.3 Bayesian Constraint Inference Algorithm
In our formulation, an agent can take an action that leads to constraint state in which case the agent incurs penalty reward of rp O, which is incorporated in the reward function. More specifically, when the agent takes action a and transitions to state C the observed reward is Tpp For a transition in state & C the accrued nominal reward is R(s, a). We will be referring to the nominal MDP that is augmented with a constraint set C' and a penalty reward Tp as Mcsr, which is defined by (S, A, P, R, C,rp, 7). In this formulation, the entries of the nominal reward vector specified by C' have been modified to take the value of Tp. With this modifiod reward function, we can use a MDP solver and obtain an optimal policy for any choice of constraint configuration and penalty reward. Inspired by the classic Bayesian IRL (BIRL) framework (Ramachandran & Amir 2007a); ; we propose modification of the Grid Walk algorithm (Vempala 2005) to jointly perform Markov Chain Monte Carlo (MCMC) sampling over the constraint set C and the penalty reward Tp. as detailed in the next section.
In what follows, we detail our Bayesian constraint inference method called Bayesian Inverse Constraint Reinforcement Learning (BICRL). The basic concept behind our Bayesian method follows the approach proposed in Ramachandran Amir (2007a) and can be summarized in the following steps: (1) we sample a candidate solution, in this case candidate constraint and a penalty reward, from the neighborhood of the current solution; (2) we compare the likelihood functions of the demonstrations under this proposal and the current solution and probabilistically accept the candidate solution based on that comparison. As in the HastopolisHHastings
Metropolis- Hastings algorithm for Markov Chain Monte Carlo methods, we also allow for randomly accepting proposals even if they are not associated with a higher likelihood to enhance exploration in the Markov Chain. In our implementation, at each iteration we either sample a candidate constraint or a penalty reward, which is an approach reminiscent of alternating optimization algorithms. This choice can is controlled by the user specified sampling frequency fr. For instance, if f. = 20 then we sample constraints 20 times more often than penalty rewards. When sampling constraints, the constraint status of state j: C'(i] -Cbi, C*[i] from Gaussian proposal distribution. The main computational burden of the algorithm, lies in the value iteration method that is called in each of the K iterations to evaluate the likelihood given the proposal.
select a random index j from {1....,P) n) and only change
Cli], Vi $j. For the penalty reward we sample Tp
We compute the likelihood of a sample by assuming a Boltzmann type choice model (Ziebart et al. 2008
Under this model, the likelihood of a trajectory & of length m is given by
0Q' (s),a))
[(C,r,) P(ECC
II
(3)
Z
where Z; is the partition function and 8 E [0, oo) is the inverse of the temperature parameter. Assuming a prior distribution over constraints and penaltics rp), the posterior distribution is given by
P(C,r,1E) P(E P(C(Cr,)P(C,r)) P(E)
(4)
We choose an uninformative prior in our experiments, but given some domain knowledge informative priors can also be incorporated. The detailed process of sampling from the posterior distribution using BICRL can be seen in Algorithm i
The Maximum a Posteriori (MAP) estimates for the constraints and the penalty reward can be obtained as
CMAP, TpMAP arg Mgmxx(CC,rpp5 C,rp
(5)
4

---

Published in Transactions on Machine Learning Research (10/2022)
Algorithm BICRL
1: Parameters: Number of iterations K, penalty reward sampling frequency fr. standard deviation d
2: Randomly sample C' E {0,
3: Randomly sample Tp E
4: chaing 0 C
chain,, [0] = Tg
Compute Q" on Mc,,
for = K do
8:
if (i mod f-)!=0 then Randomll sample state j from fl....,n} Set = - r =
9:
10:
11: else
12:
Set r rp + NN(0,)) σ), C²=
13:
Compute Q" on Mc
14:
if log [(C", ry) ) 2 log (() then
15:
Set C = C², Tp r
16:
else
17:
Set C = C² rp = r w.p. L(C" (C)C.r))
18:
chainc C
19:
chain,, [1] = Tp
20:
Return chaine, chainr,
and the Expected a Posteriori (FAP) estimates as
CEAP,TPEAP = P(cr,eerc)))))
(6)
The MAP and EAP estimates will be used to evaluate the performance of BICRL. Although the MAP estimates provide the required information to evaluate the classification and possibly obtain new policies, the EAP estimates complement them by quantifying the estimation uncertainty.
3.4 Theoretical Properties
One common concern of MCMC algorithms is the speed of convergence. In Appendix D we prove that in the special case of a uniform prior, the Markov chain induced by BICRL mixes rapidly within c of the equilibrium distribution in number of steps equal to O log 1/e). Our proof follows closely the work of Applegate & Kannan (997). Our proof is similar that of Ramachandran Amir (007a);; however, as we show in the Appendix, the proof in Ramachandran & Amir (2007a) relies simplified likelihood function that can lead to pathologically trivial maximum a postcriori reward functions. By contrast, we extend the work of Ramachandran & Amir (2007a) by proving rapid mixing for both Bayesian IRL and BICRL when using the true Boltzmann likelihood function.
3.5 Active Constraint Learning
One of the benefits of using Bayesian approach to infer constraints is the quantification of the uncertainty, confidence, in the estimation. Safety critical applications require safety guarantees during the deployment of agent. In that direction, regarding constraint inference. We examine the utility of simple active learning acquisition function which is based on the variance of the constraint estimates. One of the benefits of BICRL lies in that it does not require entire trajectory demonstrations but specific state action demonstrations suffice. We propose an active learning method in which the agent can query the demonstrator K2 times for Kp specific state demonstrations associated with high uncertainty in the current estimation. Between queries BICRL run for KA iterations. The outline of this process is summarized in Algorithm 2
interested in mechanisms that can improve the agent's confidence
5

---

Published in Transactions on Machine Learning Research (10/2022)
At every iteration of the active learning algorithm, the BICRL Algorithm is called to provide a estimate of the constraints. To expedite the process, initialization in BICRL can be set using warm start. More specifically, after the first iteration, each of the subsequent calls to BICRL uses the MAP solution of the previous itcration as the constraint and penalty reward initialization (lines 2 and 3 in Algorithm 1
Despite its simplicity, this active learning approach yields significant improvement and highlights the active learning benefits that can be gained due to the Bayesian nature of the approach. As active learning of constraints is not the primary focus of this work, we leave the investigation of more sophisticated approaches, such seeking expert samples states in backward reachable sets of highly uncertain states, to future work.
Algorithm Active Constraint Learning
Parameters: Number of iterations Kq, KD; KA
for i 1,..., Kę do
Run BICRL for KA iterations
4: Compute var(C(i)), Vi
5: Select state i* = argmax, var(C(())
6: Query demonstrator for Kn state i" demonstrations
7: Add demonstrations to D
Return chaing, chain.,
4 Deterministic Environments
Most recent work in constraint inference in IRL is based on Maximum Likelihood framework (Scobee & Sastry 2019 Stocking et al.] 2022). Before introducing the main body of our results, we carry out simulations in deterministic state space grid world environments to compare our method to the Greody Iterative Constraint Inference (GICT) method proposed by Sooobe Sastry (2019). GICI iteratively learns constraints by computing the most likely state, amoug the ones not appearing in the expert demonstrations, to appear in trajectories obtained by optimizing the current set of learned constraints. This state is then added to the set of learned constraints. GICI, like our method, assumes knowledge of the nominal reward function which refers to the rewards of the constraint free states. One of the restrictions of GTCT is that it assumes deterministic transition dynamics and hence in this section we restrict BICRL in deterministic MDPs for a fair comparison.
4.1 Classification Performance and Convergence Rate
We first demonstrate the performance of our method in the discrete grid world environment shown in Figure La The goal state, which is marked with a green flag at the top left, is associated with a known reward of 2 while each other constraint-frec state associated with known reward of -1. The environment includes 12 constraint states that can be seen in Figure Ia] colored in red. Each constraint state is associated with an unknown penalty reward of rp 100. We synthesize expert trajectories using Boltzmann policy
<(ls)) (Q"((e.))
(7)
with 8 1. We provide to our learning algorithm 100 trajectories from the demonstrator, each having as a starting state the bottom left corner, designated with a blue flag. Figure la shows the state visitation frequencies of those trajectories. We run BICRL for K = 2000 iterations and we sample constraints using a penalty reward sampling frequency fr of 50. Our Bayesian method correctly identifies the majority of the actual constraints. Figure Lb shows the mean predictions for the constraints with values approaching 1.0 corresponding to high belief of that state being constrained. Mcan values close to 0.5 designate states with high uncertainty regarding their constraint status. Given the modeling in BICRL, these values are essentially the parameters of Bernoulli random variables that model the likelihood of constraint existence. The algorithm further manages infer the penalty reward rp returning an estimated mean value of -9.96. As expected, the agent demonstrates high uncertainty in areas that are far away from the expert demonstrations, like the bottom right section of the grid.

---

Published in Transactions on Machine Learning Research (10/2022)
FPR
ENR
Fne
1.0
200
05
250
0.5
300
0.4
Namber lievations
(a)
(b)
Figure 1:
1a True constraints (red) along with expert state visitation frequencies.
1bj
EAP constraint
estimates obtained from BICRL. [cl Classification rates of MAP constraint. estimates. Results averaged over 10 independent experiments.
To quantify the convergence rate and the performance of BICRL, we further provide plot in Figure Ic of the False Positive Rate (FPR), the False Negative Rate (FNR) and the Precision (Prec) of the MAP estimates at each BICRL iteration. We average the rates over 10 independent runs of BICRL, each using 100 new expert demonstrations. The true constraints are the ones specified in Figure Ia] The rates are not necessarily monotonic, as at each iteration BICRL, we allow sub-optimal propositions to be accepted to enhance exploration in the Markov Chain. As the number of iterations increases, the MAP estimates tend towards the truc constraints.
4.2 Bayesian vs Maximum Likelihood Estimation
To further quantify the benefits our method, we also compare it with GICL For the same environment as in Figure la. we compare the classification performance of both methods in Table I
Table 1: False Positive, False Negalive and Precision classification rales for GICT and BICRL for varying levels of transition dynamics noise. Results averaged over 10 runs.
GICI
BICRL
FPR
FNR
Precision
FPR
FNR
Precision
0.02
0.08
0.89
0.02
0.0
0.88
0.01
0.01
0.46
0.88
0.02
0.0
0.92
0.05
0.0
0.83
0.90
0.0
0.0
0.99
For these simulations, utilized 100 expert trajectories obtained using Boltzmann policy with 1. The detailed parameters of the simulation can be found in Appendix A.1 GTCT utilizes KT-divergence based stopping criterion with which it terminates when the distribution of the trajectories under the inferred constraints is within a threshold of the distribution of the expert trajectories. We tuned this criterion accordingly to improve classification results. In the Appendix we include the classification performance of GICI for a grid of KT, divergence stopping criterion choices. We average the classification results over simulations. For deterministic transition dynamics, for which is 0.0, BICRL and GICI show comparable performance, with BICRL returning fewer false negatives. A low False Negative Rate in the estimation lead to the acquisition of significantly safer policies. Furthermore, it must be noted that properly tuning the KL criterion requires knowledge of the number of constraints which in reality is not available. In addition, BICRL estimates the entire posterior distribution that can be utilized in aclive learning tasks. Although this section is focused on deterministic dynamics, we further perform simulations for stochastic environments with low levels of noise, namely for < 0.01 and 0.05. It is evident that even with little noise, BICRL outperforms GICI, which can be attributed the fact that noise in demonstrations enhances exploration and periodically leads to constraint violation.

---

Published in Transactions on Machine Learning Research (10/2022)
PPR
(A]
Prse (A)
0.6
30
0.5
0.4
33
0.3
0.0
Number Derations
(b)
Figure 2:
2a
True constraints (red) along with expert state visitation frequencies.
2b
Classification rates
for Active A
and Random (R) learning methods. Results averaged over 10 independent experiments.
4.3 Active Learning
Another advantage of BICRL over GICI, is having access to a posterior distribution of the constraints which inherently allows for active learning. Querying the expert for specific state-action pair demonstrations can allow for faster and more accurate inference. To obtain intuition about the significance of active learning, we compare the active learning method outlined in Algorithm 2 with a random approach that cach time randomly selects state to query the expert for demonstrations. The MDP environment used is shown in have set D of 20 initial expert demonstrations and we the active and
Figure 2a In each experiment, the random method to query the expert KQ = 20 times for KD 20 state-action pair demonstrations at a particular state each time with Ka = 100. After each iteration i = I,... Kg of the active and random learning methods, we compute the FPR, FNR and Precision.
We deliberately restricted to few expert demonstrations and imposed smaller constraint set in this MDP order to increase uncertainty especially on the states on the right side of the grid, as very few trajectories now pass through that region. Figure 2b contains the classification ion rates averaged over 10 independent experiments. The active learning method outperforms the random one especially in the case of false positives and precision. In these simulations, we assumed there was budget of 20 iterations for the active learning algorithm. As the number of active learning ilerations increases, classification accuracy naturally further improves.
5
BICRL Motivation
5.1
Comparison With Other Approaches
In this section, motivate BICRL by showing that the decoupling of constraints and the corresponding penalty rewards is indeed needed for accurate constraint inference. In that direction, compare BICRL to three alternative methods. The simplest approach in inferring constraint states associated with low rewards is via Bayesian Inverse Reinforcement Learning (BIRL) (Ramachandran Amir 2007a). In this case however, we do not assume knowledge of a nominal reward function but infer the entire reward vector instead. Tn the other two methods, we assume knowledge of the nominal reward function and on top of that we infer the penalty rewards rp E R", that are now state dependent, without including in the MCMC sampling the indicator variable set C to designate constraint states. These approaches implementation of BIRL with knowledge of the nominal rewards. In the first variation, called Bayesian Continuous Penalty Reward (BCPR), we assume that rp takes on continuous values while in Bayesian Discrete Penalty Reward (BDPR) we assume they are discrete. The detailed algorithms for these two methods, as well the details of the experiments, can be seen in the Appendix.
essentially be considered
To compare the above alternatives with BICRL, we use four different MDP environments as seen in Figure 3
Each MDP;, 1,2,3,4 is associated with h; constraints, kn 14, ka 16, ka 10, ha = 6, depicted in

---

Published in Transactions on Machine Learning Research (10/2022)
The four grid world environments (from left to right iDP,, = I,.... 4) used to evaluate BICRL. Red squares denote constraint states while the colormap quantifies the state visitation frequencies of the expert trajectories. Start states are denoted with a blue flag and goal states with a green.
Figure 3:
red. In each case, an expert provides noisy demonstrations from a start to a goal state which are designated with blue and green flags, respectively. The dynamics are considered to be stochastic in the MDPs. More specifically, when the agent tries to move in a particular direction there an probability that the agent will move neighboring state instead. Stochastic dynamics, in addition to providing a more general framework to the deterministic ones, not always perfect due to sensor errors, actuator errors or interference from the surrounding environment. For the remainder of this paper we will assume that the transition dynamics are stochastic.
be seen
accurate depiction of real world robot transitions that are
We first compare the False Positive, False Negative and Precision classification rates that we obtain from the MAP estimates of the four methods as shown in Figure la For BIRL, BDPR and BCPR we classify the k states with the lowest r,s (from the vector of rys) as constraint states, where & is the number of constraints in the original MDP. It should be noted that assuming knowledge of the actual number of constraint states gives significant advantage to the three comparison methods. Furthermore, in Figure 4b report the average number of constraint violations per trajectory for each method. These trajectories are acquired from an optimal policy that is obtained for the MDPs with the inferred constraints and penalty rewards and evaluated on the true MDPs. For each MDP we carry out 10 independent constraint inference estimations using the four ams and for each of those we obtain 100 optimal trajectories to evaluate the average constraint violation.
ECPR
BICRL
BIRL
BCPS
BD0R
SOCRE
0.8
Vinlation Vinlatin Rate
0.6
Rato
1.00
0.4
Comstriit
0.75
0.50
0.25
0.0
FPR
FNR
Precision
MDN
MDD'
Mbr'
MDP,
(b)
Figure& 4: (a) Classification results of BIRL, BCPR, BDPR and BICRL. Results averaged over the four MDPs and 10 independent simulations. (b) Average constraint violation for the four MDPs. Results averaged over 10 independent simulations.

---

Published in Transactions on Machine Learning Research (10/2022)
FPR
FNR
0.6
Precision
0.5
1.0
0.5
0.4
Pr
0.4
0.5
Rates
0.3
Rales
0.3
Rates
0.6
2
0.2
0.9
10
0.1
0.1-
0.2
0.0
1000
1500
2000
2000
500
1:00
1500
2000
Number of Iterations
Number of Iterations
Number of Iterations
(a)
(b)
(c)
Figure 5: FPR (5a].
15c classification rates using BICRL in the grid world environment of Figure la under deterministic transition dynamics. Results averaged over 10 independent
FNR 5b
and Precision
experiments.
Both the classification results, as well as the average constraint violation metric, showcase that a decomposition of inferring constraint indicator functions and the associated penalty reward leads to more accurate inference and safer policies. Constraint inference via BIRL leads to significantly higher constraint violation. BDPR and BCPR also underperform and some times lead to inferred penalty rewards that can alter the reward in a way that changes the actual goal state.
5.2 Demonstrator-Leame Discrepancy in Rationality
BICRL, an inverse RL method, requires demonstrators from an expert in order to infer constraints. In general, it might be unrealistic to assume knowledge of the exact rationality levels of the demonstrator. In this section, we investigate the effect on inference when the rationality of the demonstrator captured, by the temperature $D, is different from the rationality of the learner trying to infer the constraints, captured by 3y. For the environment and task depicted in Figure Ta we gather 100 demonstrations from an expert with temperature parameter $D We use BICRL infer the constraints in that environment for a range of B, values.
We performed two sets of experiments, one assuming deterministic transition dynamics and another assuming stochastic dynamics with = 0.05. We report the classification rates for each choice of B3 in Figures 5 and 6 It should be noted that, as the value of 3 increases the agent's 's behavior converges towards the optimal one. As expected the larger the discrepancy between 3D and Br the higher the misclassification. Interestingly, this discrepancy further attenuated by the stochasticity the transition dynamics. One possible explanation for this phenomenon the following. When By has high value, like 100, the inferring agent behaves almost optimally. However, the demonstrating agent is suboptimal and the additional noise exacerbates this. As result, the inferring agent assumes that the demonstrating agent would rarely violate constraint, and perhaps rarely move close to one, and hence ends up inferring significantly fewer constraints. To quantify the discrepancy between rationality levels more, in Section g we present inference results on a continuous state space environment obtained by using human demonstrations.
6 Hierarchical BICRL
For large number of environments and tasks, safety constraints are compositional. In this section, we take advantage of that fact, and we propose learning local constraints by observing agents perform sub-tasks. These local estimates can then be synthesized to obtain an estimate of the constraints in the entire space. Concretely, if the state space 5 made of distinct sub-domains S2....... ., Sn, each with constraint sets C₁, C2..... C., then the constraint set associated with the full state space is C₁ UC, U... UC,, By observing experts interact in those distinct. domains, we can infer constraints that, when composed together, provide
10

---

Published in Transactions on Machine Learning Research (10/2022)
FPR
FNR
Precision
0.8
0.5
0.7
1.0
P1
0.0
0.5
Rattes
0.3
Rates
0.5
0.4
Rates
0.6
0.2
10
011
0.0
0.0
500
1000
1500
2000
500
10:0
1500
2000
Number of Iterations
Number of Iterations
Number
(a)
(c)
Figure 6: FPR. 66 environment of Figure la under stochastic transition dynamics with noise level c= 0.05. Results averaged over 10 independent experiments.
FNR 6b
and Precision
(bb
classification rates using BICRL in the grid world
accurate constraint cstimation compared to global inference approach, in which agent tries to complete one task on S. Learning constraints from tab-tasks has also the benefit of mitigating the high dimensionality of the original problem. BICRL can be run in parallel for each sub-domain increasing the computational efficiency of our approach.
To showcase the benefits of learning from tasks, we design an experiment on a 24 x 24 state grid world environment with constraints as seen Figure Ta We compare the case of Global inference in which the agent tries traverse from the bottom right the top left cell with the Hierarchioal case in which the domain is split into four non-overlapping 12 x 12 sub-domains in which agents complete specific sub-tasks. Figure 7a shows the original grid world, along with the constraints and state visitation frequencies of the demonstrations, while Figure 8 shows the sub-domains extracted from the main environment and the associated sub-tasks.
200
30
(a)
(b)
Figure 7: Even given 10000 samples, performing global constraint inference results in much more uncertainty than when using Hicrarchical BICRL (Figures and 9 (a) Original constraints along with state occupancies from 10000 samples from expert trajectories. (b) Global EAP constraint estimates.
In each of the four sub-domains, the experts have to complete different task shown by the blue (start state) and green (target state) flags respectively. The posterior mean estimates of the constraints are shown in Figure g In comparison, the posterior mean estimates the Global inference case shown in Figure 76 are considerably more uncertain.
To further motivate Hierorchical BICRL, we compare the classification performance of the MAP estimates of the two methods. Given that trajectories, and hence the total number of state-action demonstration pairs,
11

---

Published in Transactions on Machine Learning Research (10/2022)
(b)
(c)
(d)
Figure 8: Original sub-task constraints and state occupancies for 2500 samples (for each sub-domain) from
expert trajectories. The sub-tasks were obtained by splitting the original 24 x 24 grid into four equally sized quadrants.
(a)
(b)
(c)
(d)
Figure 9: Hierarchical BICRL learns more accurate and less uncertain constraints than using global inference. Shown are the EAP constraint estimates for the four sub-domains of Figure
be of varying length due to the grid size differences, for fairness we compare the methods by varying the total number of actenn transition pairs used during inference. Table 2 clearly showcases that Hierarchical BICRL achieves significantly higher classification accuracy while providing more computationally efficient. alternative.
Table 2: False Positive, False Negative and Precision classification rates for Global and Hierarchical BICRL over varying number of state-action demonstration sample sizes. Results averaged over 10 experiments.
BICRL (Global)
BICRL (Hierarchical)
Samples
FPR
FNR
Precision
FPR
FNR
Precision
1000
0.34
0.38
0.12
0.26
0.35
0.15
5000
0.25
0.13
0.23
0.08
0.2
0.46
10000
0.12
0.08
0.43
0.03
0.11
0.67
The main goal of Hierarchical BICRL, except for the possible computational gains, is to show that constraint inference in the entire state space is still possible even if only sub-domain demonstrations are available. If only global task demonstrations are available, then Hierarchical BICRL would require further information about sub-tasks, which night not always be straightforward to obtain. It should be noted that, if diverse sub-task demonssuratonss are provided then classification might be more accurale as opposed to the case in which only demonstrations from global task are available. That is expected, as higher diversity in the demonstrations leads to more accurate constraint inference due to better exploration of the state space.
6.1 Home Navigation Task
In this section, we present more realistic constraint inference scenario for Hicrarchical BICRL in which agent. infers obstacles in home environment. An example of such agent could be home appliance
12

---

Published in Transactions on Machine Learning Research (10/2022)
robot trying to map the rooms of house. Figure 10 shows the floor plan of single bedroom apartment obtained from the iGibson dataset (Li et al. 2021 A natural way to divide the entire apartment domain into sub-domains is to consider each room individually. The four room spaces are discretized and for each room we provide a number of expert demonstrations for two navigation sub-tasks. The details regarding the sub-lasks, associated rewards and the demonstration can be seen in Appendix B.1
Collect sub-task trajectories
Sub-domain inference
Global inference
BICRL
BICRL
BICRL
BICRL
Figure 10: Hierarchical BICRL in a home navigation environment with posterior mean results.
we show the mean constraint estimates of the posterior distribution for each sub-domain and ultimately for the entire space. BICRL manages identify with high certainty most of the constraints in the rooms. As expected, sections of the domain with few no demonstrations, like the bed area in the bottom left room, have higher uncertainty. Occasionally, false positives appear in the classification and they can be altributed to the stochastic nature of our Bayesian method. In practice, a large number of expert demonstrations that span the entire domain will drastically decrease the false positives in the classification. This example showcases, that given the dccomposability of constraints, they can be efficiently inferred from independent sub-tasks. Having access that information, agent can then design policies and safely complete any task, possibly involving subset of the sub-domains.
In Figure 10]
7 Feature-Based BICRL
This section introduces feature- based version of BICRL. Estimating Reature-based constraints allows for better generalization to different environments and tasks. In the feature- based case, the walk takes place the feature weight vector and given that this is usually of smaller dimension than for instance the number of stales in Section 5 BICRL may require fewer iterations for the posterior distribution to converge. Feature-based BICRL, detailed in Algorithm 5 in the Appendix, follows the same logic as the original version of the algorithm. The main difference that this time the features and not the states are considered to be constrained or not. At each iteration, the algorithm either switches the label of feature between constraint and free samples a value for the feature weight associated with constraint features.
13

---

Published in Transactions on Machine Learning Research (10/2022)
BURL.
BCPR
BDPR
BICRL
Constmintt Vialation Rate
Figure 13: Average constraint violation in the test highway environment
pictured in Figure 11b Results averaged over 10 independent simulations.
(a) Train Environment
(b) Test Environment
Figure 11: BICRL learns constraints from demonstrations in (a) that better transfer to new settings (b).
00
10
10
(a) Ground Truth
(b) BICRL
Figure 12: BICRL able to learn the correct constraint function from driving demonstrations.
We study highway environment in which the reward in each state is given linear function over features R(s) wT (fs). The nine binary features Φ E IR9 and the corresponding weights E RR9 are shown in Table
g in the Appendix. The dimensions of the original highway environment shown in Figure IIa are 3 x 11. The goal of the driver of the blue car is to overtake the rest of the vehicles and the cyclists. For tailgating a car, overtaking from the right side of another car, passing close to the cyclists or any collision the driver incurs a penalty of 10. The driver obtains reward of for completing the task while being penalized for driving slowly. For 20 expert demonstrations and K 2000 iterations, Figures 12a and 12b show the original reward and the recovered from BICRL. The latter results are average 10 independent simulations.
Finally, we compare how the inferred feature weights from BIRL, BCPR, BDPR and BICRL generalize to new unseen environment shown in Figure [1b The new environment models a longer highway stretch with more lanes and vehicles. For each method, we run 10 independent inference simulations using each time new expert demonstrations and for each of those we obtain 100 optimal trajectorics using the inferred features. Figure 13 shows the average constraint violation in the test environment, providing evidence that BICRL leads to safer policies.
14

---

Published in Transactions on Machine Learning Research (10/2022)
8 Continuous State Spaces
Finally, we investigate the performance of BICRL in continuous state spaces with human provided demonstra- tions. We utilize two dimensional navigation task depicted in Figure 14a in which the goal is to navigate from starting state in the set Ss to a state in Sg while avoiding the constraint states in Se. We collect a dataset of 20 human demonstrations by selecting way points from the start to the goal state that complete the task. The state space is comprised (x, y) coordinate tuples while the control inputs are the orientation Φ E [0] and the travel distance along the direction the orientation r [0, 0.25]. After the way points have been created, the actions are computed by inverting the dynamics between each pair of adjacent way points.
%
(a)
(b)
(c)
Figure 14: Continuous two dimensional navigation task along with human demonstrations
14a
MAP
14b
and EAP (1c] constraint estimates.
As BICRL applies to discrete state spaces, we proceed to discretize both the state and action spaces, in a similar way to Stockinn et al.] (2022). The state space is discretized into a 12 x 12 grid, while the action space is discretized into 8 actions for the orientation and 5 actions for the distance, We assume that the target states are associated with a reward 5, while the living reward is -2. We fix the value of B 10, the demonstrations are noisy but close to optimal. Figures [4b] and 14c show the MAP and EAP estimates obtained from BICRL. While one of the constraint states is missclassified, the other three are identified correctly. As expected, in the unexplored areas of the state space uncertainty is high which is evident in the corresponding EAP estimates.
(a)
(b)
Figure 15: MAP
15a and EAP (15b) constraint estimates under sparsity priors.
In the entirety of this paper, we assumed that there is no prior information regarding constraints. Given that in certain applications some information regarding constraints could be available, we also examine the classification performance of BICRL in the case where we assume that constraints sparse. More
15

---

Published in Transactions on Machine Learning Research (10/2022)
specificallyy, each state is assumed to have prior probability of being constraint that follows Bernoulli distribution with parameter 0.05. For the same trajectories and hyperparameters as the ones used in the results in Figure [4] the MAP and EAP estimates for the sparse prior case are shown in Figure 15 The inclusion sparsity prior removes the noisy MAP estimates on the unexplored domain of the environment while keeping the constraint estimates around the actual constraint unaffected.
9 Conclusion
In this work we proposed BICRL, a Bayesian approach to infer the unknown constraints discrete MDPs. BICRL can be utilized in both deterministic and stochastic environments as well as under complete or partial demonstrations. We showed that BICRL outperforms in constraint classification established approaches in both types of environments. The posterior dist.ribution obtained allows for active learning tools to be utilized to further improve classification, especially in infrequently visited by the expert sections of the state space. We further proposed hierarchical version of BICRL that allows for independent constraint inference in distinet sub-domains of the entire state space. Furthermore, we extended BICRL to feature-basee environments and we showed that the estimated feature vectors can be used to obtain safe policies in new environments. Finally, we implemented BICRL a continuous state space environment and we showed its effectiveness in inferring constraints from human demonstrations.
10 Limitations and Future Directions
Constraint learning is a relatively new research area, hence, there is significant room for improvement. In this work, we only consider constraint lcarning in low dimensional, and in most cases, discrete state spaces. An important avenue of future research, will be to adapt the principles introduced in this paper, to work with preference learning in order to enable scalable inference of constraints in high-dimensional continuous euvironments. Additionally, our active learning approach could be further improved through using more informative acquisition functions which could potentially incorporate information from the environment and corresponding task.
Another direction of future work is to leverage the fact that our constraint estimates are associated with confidence levels obtained from the posterior distribution. These confidence levels could be used design policies that satisfy certain safety criteria, agents can utilize this information to keep, for example, certain distance from arcas where the cxistence of constraints is highly uncertain.
Hierarchical BICRL requires experts to provide demonstrations under various different reward functions. In many enviromments, such as the home navigation enviromment studied in this work, design of these reward functions may be straightforward; however, in other environments of interest, design of these different reward functions may be quite challenging. This may meril use of Global BICRL, over Hierarchical BICRL environments where there sufficiently diverse data available naturally. Finally, this work and other prior art in constraint learning has mainly focused on simulated studies. Application papers focused on utilizing constraint learning for real world applications is another exciting area of future research.
References
Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the twenty-first international conference on Machine learning, pp. 1, 2004.
Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International conference on machine learning, pp. 22 31. PMLR, 2017.
Usman Anwar, Shehryar Malik, Alireza Aghasi, and Ali Ahmed. Inverse constrained reinforcement learning. arXiv preprint arXix:2011.0990 2020.
David Applegate and Ravi Kannan. Sampling and integration of near log-concave functions. In Proceedings of the twenly-thine third annual ACM symposium Theory of compuling, pp. 156 156-163, 1991.
16

---

Published in Transactions on Machine Learning Research (10/2022)
Saurabh Arora and Prashant Doshi. A survey of inverse reinforcement learning: Challenges, methods and progress. Artificial Intelligence, 297:103500, 2021.
André Barreto, Will Dabney, Rémi Munos, Jonathan Hunt, Tom Schaul, Hado P van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. Advances in neural information processing systems, 30, 2017.
D Brown, S Niekum, and M Petrik. Bayesian robust optimization for imitation learning. In Newral Information Processing Systems, 2020a.
Daniel Brown, Russell Coleman, Ravi Srinivasan, and Scott Nickum. Safe imitation learning via fast Bayesian reward inference from preferences. International Conference on Machine Learning, pp. 1165-1177. PMLR, 2020b.
Danicl S Brown, Wonjoon Goo, and Scott Nickum. Bette-thaa-ddmmonstator imitation learning via automatically-rankeed demonstrations. In Conference on robot learning, pp. 330-359. PMLR, 2020c.
Dan A Calian, Daniel J Mankowilz, Tom Zahavy, Zhongwen Xu, Junhyuk Oh, Nir Levine, and Timothy Mann. Balancing constraints and rewards with meta- meta-gradien titadggraientt d4pg. arXiv preprint arXiv:2010. (X.::2010.063%4, 2020.
Alex James Chan and Mihacla van der Schaar. Scalable Bayesian inverse reinforcement learning. In International Conference on Learning Represenlations, 2020.
Arthur Charpentier, Romuald Elie, and Carl Remlinger. Reinforcement learning in economics and finance.
Computational Economics, pp. 1-38, 2021.
Glen Chou, Dmitry Berenson, and Necmiye Ozay. Learning constraints from demonstrations. arXiv preprinl arXiv:1812.07084 2018.
Glen Chou, Necmiye Ozay, and Dmitry Berenson. Learning constraints from locally-optimal demonstrations under cost function uncertainty. IEEE Robotics Autom. Lett., 5()):3682-3690 2020.
Glen Chou, Hao Wang, and Dmitry Berenson. Gaussian process constraint learning for scalable chance- constrained motion planning from demonstrations, IEEE Robotics and Automation Letters, 7(2):3827-3844 2022.
Paul F. Christiano, Jan Leike, Tom B. Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems, 2017.
Christian Daniel, Malte Viering, Jan Metz, Oliver Kroemer, and Jan Peters. Active reward learning. In Proceedings of Robotics: Science and Systems, 2014.
Claudia Pérez D' Arpino and Julie A. Shah. C-learn: Learning geometric constraints from demonstrations for multi-step manipulation in shared autonomy. In IEEE International Conference Robotics and Automation (ICRA), 2017.
Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International Conference on Machine Learning, 2016.
Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adverserial inverse reinforcement learning. In International Conference Learning Representations, 2018.
Javier Garcia and Fernando Fermández. A comprehensive survey on safe reinforcement learning. Journal of Machine Learning Research, 16(1):1487-1480, 2015.
Dylan Hadfield- Hadnllld-Menell, Anca Dragan, Pieter Abbeel, and Stuart Russell. The off-switch game. In Workshops at the Thirby-Fiee First. AAAT Conference Artificial Intelligence, 2017a.
17

---

Published in Transactions on Machine Learning Research (10/2022)
Dylan Hadfield-Menell, Smitha Milli, Pieter Abbeel, Stuart J Russell, and Anca Dragan. Inverse reward design. Advances in neural information processing systems, 30, 2017b.
Zaynah Javed, Daniel Brown, Satvik Sharma, Jerry Zhu, Ashwin Balakrishna, Marek Petrik, Anca Dragan, and Ken Goldberg. Policy gradient bayesian robust optimization for imitation learning. In International Conference on Machine Learning, 2021.
Hong Jun Jeon, Smitha Milli, and Anca Dragan. Roward-rational (implicit) choice: A unifying formalism for reward learning. Advances in Neural Information Processing Systems, 33:4415-44222 2020.
Wonseok Jeon, Scokin Sco, and Keo-Eung Kim. bayesian approach to generative adversarial imitation learning. In Advances in Neural Information Processing Systems, 2018.
Victoria Krakovna, Laurent Orseau, Ramana Kumar, Miljan Martic, and Shane Legg. Penalizing side effects using stepwise relative reachability. arXi preprint 1rXiv:1806.01188 2018.
Authony Lanfranco, Andres E Castellanos, Jaydev P Desai, and William C Meyers. Robotic surgery: a current perspective. Annals of surgery, 239(1):14, 2004.
Chengshu Li, Fei Xia, Roberto Martín-Martín, Michael Lingelbach, Sanjana Srivastava, Bokui Shen, Kent Elliott Vaimio, Cem Gokmen, Gokul Dharan, Tanish Jain, Andrey Kurenkov, Karen Liu, Hy- owon Gweon, Jiajun Wu, Li Fei-Fei, and Silvio Savarese. igibson 2.0: Object-centric simulation for robot learning of everyday household tasks. In 5th Annual Conference on Robot Learning, 2021. URL https://openrreieew met//forumiid=2uN66]]
James MacGlashan, Mark K. Ho, Robert Loftin, Bei Peng, Guan Wang, David L. Roberts, Matthew E. Taylor, and Michael T.. Littman. Interactive learning from poliey-dependens human feedback. Tn International Conference on Machine Learning, 2017.
David L McPherson, Kaylene C Stocking, and S Shankar Sastry. Maximum likelihood constraint inference from stochastic demonstrations. In 2021 IEEE Conference Control Technology and Applications (CCTA), pp. 1208-1220 1213. IEEE, 2021.
Bernard Michini and Jonathan How. Bayesian nonparametric inverse reinforcement. learning. In Machine Learning and Knowledge Discovery in Databases, 2012.
Sobhan Miryoosefi, Kianté Brantley, Hal Daume III, Miro Dudik, and Robert E Schapire. Reinforcement learning with convex constraints. In Advances in Neural Information Processing Systems, 2019.
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and
Martin Riedmiller. Playing atari with deep reinforcement learning. ar preprinl orXim:1312.5000 2013.
Andrew Y Ng. Stuart J Russell, et al. Algorithms for inverse reinforcement learning, In Icml, volume 1, pp. 2, 2000.
Michael Pardowitz, Raoul Zöllner, and Rüdiger Dillmann. Learning sequential constraints of tasks from user demonstrations. In 5th IEFE-RAS International Conference on Humanoid Robots, 2005.
Daehyung Park, Michael Noseworthy, Rohan Paul, Subhro Roy, and Nicholas Roy. Inferring task goals and constraints using Bayesian nonparametric inverse reinforcement learning. In Conference on Robot Learning, pp. 1005 1014. PMLR, 2020.
Santiago Paternain, Luiz Chamon, Miguel Calvo Calvo-Fullana, and Alejandro Ribeiro. Constrained reinforcement. learning has zero duality gap. In Advances in Newral Information Process- ing Systems, volume 32, 2019. URL claebSSTTatr773355444444810111 Papeeeeeeapppppppppp .dff.
neun http://diiin..eiir.ps..paaappppp
Athanasios S Polydoros and Lazaros Nalpantidis. Survey of model-based reinforcement learning: Applications robotics. Journal of Intelligent & Robotic Systems, 86(2):153 173, 2017.
18

---

Published in Transactions on Machine Learning Research (10/2022)
Deepak Ramachandran and Eyal Amir. Bayesian inverse reinforcement learning. In IJCAI, volume 7, pp. 2586-2591, 2007a.
Deepak Ramachandran and Eyal Amir. Bayesian inverse reinforcement learning. In 20th International Joint Conference on Artifical Intelligence, 2007b.
Siddharth Reddy, Anea D. Dragan, and Sergey Levine. SQIL: with sparse rewards. In International Conference on Learning Regresentations, 2020.
imitation learning via reinforcement learning
Stéphane Ross, Geoffrey J. Gordon, and Drew Bagnell. A reduction of imitation learning and structured prediction to no-rogret online learning. In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, 2011.
Stuart Russell. Learning agents for uncertain environments. In Proceedings of the eleventh annual conference on Compulational learning theory, pp. 101-103, 1998.
Dorsa Sadigh, Anca D. Dragan, Shankar Sastry, and Sanjit A. Seshia. Active preference-based learning of reward functions. In Robolics: Science and Systems XIII, 2017.
Dexter RR Scobee and S Shankar Sastry. Maximum likelihood constraint inference for inverse reinforcement learning. In International Conference on Learning Representations, 2019.
Burr Settles. Active learning literature survey. 2009.
Sina Shafaci, Stefan Kugele, Mohd Hafeez Osman, and Alois Knoll. Uncertainty in machine learning: A safety perspective on autonomous driving. In International Conference on Computer Safety, Reliability, and Security, pp. 458 464. Springer, 2018.
Rohin Shah, Dmitrii Krasheninnikov, Jordan Alexander, Pieter Abbeel, and Anca Dragan. Preferences 2019.
implicit in the state of the world. arXiv preprint
Krishnan Srinivasan, Benjamin Eysenbach, Sehoon Ha, Jie Tan, and Chelsea Finn. Learning to be safe: Deep rl with safety critic. arXiv preprint Xiv::200 14603, 2020.
Kaylene Stocking, David L McPherson, Robert P Matthew, and Claire J Tomlin. Maximum likelihood constraint inference on continuous state spaces. In IEEE International Conference on Robotics and Automation (ICRA), 2022.
Guru Subramani, Michael Zimn, and Michael Gleicher. Inferring geometric constraints in human demonstra- tions. In 2nd Conference on Robot Learning (CoRL), 2018
Chen Tessler, Daniel J Mankowilz, and Shie Mannor. Reward constrained policy optimization. ar preprinl 17Xiv:1805.11074, 2018.
Alex Turner, Neale Ratzlaff, and Prasad Tadepalli. Avoiding side effects in complex environments. Advances in Neural Information Processing Systems, 33:21406 21415, 2020.
Santosh Vempala. Geometric random walks: survey. Combinatorial and compulational geometry, 52 (573-612):2, 2005.
Tsung- Yen Yang, Michael Y Hu, Yinlam Chow, Peter J Ramadge, and Karthik Narasimhan. Safe reinforcement learning with natural language constraints. Advances in Neural Information Processing Systems, 34:13794 13808, 2021.
Brian Ziebart, Andrew Maas, J Andrew Bagnell, Anind Dey, et al. Maximum entropy inverse reinforcement learning. In Aaai, volume 8, pp. 1433-1444 1433-1488. Chicago, IL, USA, 2008
Konrad Zolna, Scott Reed, Alexander Novikov, Sergio Gomez Colmenarejo, David Budden, Serkan Cabi, Misha Denil, Nando de Freitas, and Ziyu Wang. Task-relevant adversarial imitation learning. arXiv preprint 1rXiv:1910. 010001777 2019.
19

---

Published in Transactions on Machine Learning Research (10/2022)
A Appendix
A.1 Details for Simulations in Section 4
This section contains the details for the deterministic transition dynamics environment simulations, as well as the two stochastic scenaria of Section 4.2] The MDP has 8 x 10 number of states. The possible actions are up, down, left and right. The discount factor is ? 0.95. Starting and goal states are depicted with a blue and green flag respectively. The expert trajectorics are obtained with Boltzmann policy model with & = For this example, and all the rest of the simulations in this paper, we gather demonstrated trajectories by letting the expert agent follow Boltzmann policy (7) from the start state until the goal state is reached or predetermined number of steps has been made.
Table 3: Hyperparameters of Sections
4.1
4.3
simulations.
Hyperparameters
Sec. 4.1
Sec. 4.2
Sec.
4.3
Expert trajectories
100
100
20
80
80
80
0.95
0.95
0.95
c
0.0
0.0, 0.05
0.0
B
K
2000
4000
200
fr
50
50
50
tune the KL divergence stopping criterion by using grid search over its values. The classification results for these values for the deterministic and stochastic transition models can be seen in Table 4 The high levels of false negatives for > 0.0 are attributed to the infrequent violation of constraints due to transition dynamics noise.
In Section 4.2
Table 4: False Positive, False Negative and Precision classification rates for GICI over varying KL divergence stopping criteria for environment in Figure la Results averaged over 10 runs.
0.0
0.01
0.05
KL
FPR
FNR
Precision
FPR
FNR
Precision
FPR
FNR
Precision
0.5
0.0
0.91
1.0
0.0
0.95
0.5
0.0
1.0
0.0
10
0.0
0.41
1.0
0.0
0.63
1.0
0.0
0.86
0.90
10
0.0
0.33
0.94
0.0
0.55
0.96
0.0
0.83
0.90
10
0.02
0.08
0.89
0.01
0.46
0.88
0.0
0.83
0.90
10
0.02
0.0
0.89
0.01
0.45
0.85
0.0
0.83
0.85
We also report the mean prediction for the constraints learned in Section 4.3
As expected, uncertainly is now significantly higher before running active learning. Applying Algorithm from Section 3.5 with K2 = 20, KA = 100 and Kp = 20 we obtain mean estimates that are significantly more accurate as seen in Figure 16c This feature of BICRL makes it appropriate for tasks where demonstrations are scarce and there is a limitation on the number of queries. In the active learning case, we first obtained initial constraint. estimates by running BICRL on the initial 20 trajectories for 200 iterations and then used the active learning algorithm to further refine the classification.
P
A.2 Details for Simulations in Section 5
This section contains the details on the simulations we run compare our method with three other Bayesian approaches. The four MDP environments have 8 10 number of states. The possible actions up, down,
20

---

Published in Transactions on Machine Learning Research (10/2022)
36
(a)
(c)
Figure 16: (16a) Original 20 trajectories and true constraint allocation. (6bb) EAP constraint estimation
without active learning querying. 16e EAP constraint estimation after 10 active learning queries.
left and right. There is uncertainty in the transition model with certain probability the agent moves to neighboring state instead of the target state. For instance for noise level when the agent takes the action up then the agent will end up laking the action up with probability 1 + and the act ions left and right each with probability If the agent tries to transition outside the grid boundaries then the agent remains in the same state as shown in Figure 17
0.9
0.9
0.0
0.05
0.0
0.05
0.0
0.05
0.05
0.0
0.95
0.05
Stochastic dynamics with e = 0.05 for taking action up. Red squares represent grid walls. The rest of the actions are analogous.
Figure 17:
The discount factor is y 0.95. Starting and goal states are depicted with blue and green flag respectively. For each of the MDPs we used 20 expert trajectories which we assume are noisy. We model this noise by using a Boltzmann policy for the expert with 3 =
Table 5: Hyperparameters of Section
5.1
simulations.
Hyperparamoters
Values
Expert trajectories
20
80
0.95
0.1
4000
fr
50
The algorithms for BDPR and BCPR are given below. We demote the reward penalty rp E R" with bold letter as now it is a vector since we infer a state-dependent penalty. Both BCPR and BDPR assume knowledge of the nominal reward and sample a stato-dependent penalty reward that added on top of the nominal reward. The MDP notation Mr, refers to the MDP that has the penalty reward term added its nominal reward function.
21

---

Published in Transactions on Machine Learning Research (10/2022)
Algorithm BDPR
1: Parameters: Number of iterations K
2: Randomly sample reward vector rp E n"
3: chainr, [0] = Fp
4: Compute Q* on Mr, for l......, do Randomly sample state j from {1.-..,A K}
Set ry,[]] = rrp[]] + ryl5] with equal probability Compute Q" on Mr;
8:
9:
if log [(r,) 2 log ((pp) then
10:
Set rp = p
11: else
12:
Set Fp = r w.p. L(r,)/ ((r,) chainr, rp
13:
14:
Return chainr,
Algorithm BCPR
1: Parameters: Number of ilerations K, standard deviation a Randomly sample penalty reward vector rp R
chain,, [0] Fp
Compute Q* on Mr 5: for == 1. K do
6: Randomly sample state j from nI.
7: Set ry[s] ~ ~N(rpp(),)
Compute Q" on Mr;
if log [(rr)) 2 log ((r,) then
10:
Set rp r
11:
else
12:
Set rp = r w.p. [(r))// ((rp) chainr, [1] Ip
13:
14:
Return chainr,
Table 6 contains the hyperparameters regarding the sensitivity in the temperature parameter (3) of Section 5.2
Table 6: Hyperparameters of Scction
5.2
simulations.
Hyperparameters
Values
# Expert trajectories
100
n
80
0.95
0.0, 0.05 1
Bp
B
0.5, 1, 2, 5, 10, 100 2000
K
fr
50
22

---

Published in Transactions on Machine Learning Research (10/2022)
B Hierarchical BICRL
For the Hierarchical BICRL in Section 6 we compare the methods using the varying number of state- action tuples obtained from the expert and not the number of trajectories. The reason for that, is that the heterogencity in the constraints and grid sizes lead to imbalanced numbers of total state-action demonstrations for the same number of expert trajectories. In practice, we keep gathering trajectories until the certain limit of state-action tuples is reached.
Table 7: Hyperparameters of grid world Hierarchical BICRL.
Hyperparameters
Values
# Expert samples
1000, 5000, 10000
n (Global, Hierarchical)
576, 4 144
0.95
c
0.1
8
K
4000
1
fr
50
B.1 Home Navigation with Hierarchical BICRL
For the home navigation task, we use one of the apartments in the iGibson dataset Li (2021). Each
room is discretized, counting from the top left clockwise, into 16 15, 12 x 24, 23 17 and 29 15 states
respectively. In this set of experiments, the reward associated with the goal state is now 10 while the penalty reward and the living reward are 100 and -1 respectively.
(18a)
(18b)
Figure 18: Original four room layout 18a and mean constraint estimates 18b) on the four rooms.
Figure 18 contains the original apartment layout and the posterior mean constraint estimates. The brightness of each grid point in the Figure 18 on the right proportional to the likelihood of that state being constrained. Colorless grid points designate states that are estimated to be free of obstacles. The parameters used infer the constraints in each room be seen in Table S
23

---

Published in Transactions on Machine Learning Research (10/2022)
Table 8: Hyperparameters home navigation simulations.
Hyperparameters
Values
# Expert trajectories (for each room)
100
240, 288, 391, 435
0.95
0.1
B
K
4000
a
f+
The expert trajectorics gatherod for the subtasks in the individual rooms can be seen in Figure 19 Each room has two individual subtasks that start from the blue flags and both end in the green flag. Figure [0] although more conceptual in nature, also shows the subtasks for each room with green arrows. For each of the rooms, gather 50 expert trajectories for each subtask by using a Boltzmann policy with temperature parameter B 1.
(a)
(b)
(d)
Figure 19: Home navigation expert trajectories. With reference to Figure bottom left (19cb and bottom right [9d rooms.
18a top left. 19a top right
19b).
24

---

Published in Transactions on Machine Learning Research (10/2022)
C Peature-Based BICRL and Continuous State Space Navigation
C.1 Feature- Based BICRL
Figure 20 shows the highway environment used for the Seature-based simulations. The original environment is discrctized in 3 x 11 states. The feature weights are shown in Table The blue car pays a "living" reward penalty of -1, which penalizes driving slowly, while obtaining a small positive reward for overtaking a car from the left lane (car on the right). Overtaking car from the right lane (car on the left), along with proximity to cyclist, tailgating and collisions considered constraints and are hcavily penalized with penalty reward of 100. The ceaturebbaed version of BICRL can be seen in Algorithm
5 BICRL, BCPR and BDPR assume knowledge of the "nominal" feature weights (features 4, 5, 6, 7 and 9), and they sample feature weights on top of these. In lines 5 an 12 in Algorithm 5 the Q values are computed on the MDP that has its nominal feature weights along with the inferred constraint ones that are associated with a penalty reward (weight) of rp- For instance, if the current weight sample w' = [0, 1, O, 0, 0, O, O, 0, and ry = 225 then the weight vector Mw.rg .f w' [0. 2.5, 0, 1, -1, 1,, 11 0, 10]. In this particular MDP, the goal state is reaching the top right cell by overtaking all the vehicles and eyclists according to the rules.
Figure 20: Highway environment.
The hyperparameters the simulations can be seen Table 10
Table 9: Features and weights of highway environment.
Feature ID
Feature
Weight
Tailgating
10.00
2
Close to cyclist
-00.0
3
Car on the left
-0.00
Car on the right Driving left lane Driving middle lane
1.0
5
-1.0
6
-1.0
7
Driving right lane
-10
8
Collision Goal State
10.0
9
10.0
25

---

Published in Transactions on Machine Learning Research (10/2022)
Table 10: Hyperparameters of highway environment.
Hyperparametens
Values
Expert trajectories
20
33
n
9
0.95
0.1
B
2000
0.2
fr
20
Algorithm Feature-Based BICRI.
1: Parameters: Number of iterations K, penalty reward sampling frequency fr. standard deviation o Randomly sample w E R
chainw (0)
chainr, = Tp
Compute Q? on Mw.rp
6: for = l. K do
if (i mod f+)!=0 then 8: Randomly sample feature j from Set w' -w(l,, T = Tp
7:
10: else
11:
Set r rp +0(00 o), w'
12:
Compute Q on Mw
13:
if log L(w', r//)) 2 log ((w, then
14:
Set w', rp r
15:
else
16:
Set w w', = The w.p. L(w)/[(())
17:
chain [1] w
18:
chain,, Tp
19:
Return chainw: chain,,
C.2
Continuous State Space Navigation
The hyperparamcters used in Soction can be seen table
Table 11: Hyperparameters of continuous state space navigation environment.
Hyperparameters
Values
# Expert trajectories
20
n
144
# actions
5
0.95
0.05
B
10
K
6000
fr
50
26

---

Published in Transactions on Machine Learning Research (10/2022)
To collect the trajectorics, graphical user interface is used on which way points created on the environment. The continuous environment state space is a [0, 1] [0, 1] box which is then discretized into 12 x 12 grid. Each continuous state is then assigned to each closest discrete state following a nearest neighbor rule. The discretization of actions follows similar rule. The original continuous actions along a trajectory are obtained by inverting the dynamics belween two adjacent way points.
Theoretical Analysis and Proof of Rapid MCMC Mixing
D.1 Preliminaries
Below, we provide a rigorous proof of rapid mixing for the Policy Walk algorithm found in Ramachandran & Amir (2007a). Note that while our proof follows theirs, there some important differences. First, we note that the likelihood for Bayesian IRL (and the one used in our paper for BICRL) is of the form
(Qg(),a)
P(D]R) = II
(8)
(e,0)DD EBEA (QT
Note that Ramachandran & Amir 2007a) assume the following likelihood function
P(DRR) II
(Q2(s,a)
(9)
(s,0ED
To see why this might not be accurate, consider Equation (3) in Ramachandran & Amir 2007a The
posterior probability of reward function R by applying Bayes' theorem is given as
P(R[D) P(DIR)P(R)
(10)
P(D)
Eowee Vils,a) P(R).
= z'
(11)
Ramachandran & Amir (2007a) then claim that computing the normalization Z' is hard, which is true, but that the term can be ignored since MCMC only requires sampling probability density ratios. However, Z' does not actually cancel when performing probability density ratios since Z' is dependent on R. To see this we unpack the above posterior distribution
P(RD) = P(D
(12)
P(D)
80% ( P(R)
Il(S,)eD
(13)
P(D)
8 E. P(R) P(R).
(14)
II(s,)) EBEA (Q P(D)
Thus, there is clear dependence of Z' R and when take ratio of probability densities for the posterior probability of two reward functions R and R', we cannot fully cancel Z' as claimed by Ramachandran & Amir 2007a). Instead we have
exp(8 >, (2(3:))))P(M) P(R)
D) P(RDD
(r.a) EnEA (XP()Q
(15)
cxp(
(p(()))))))((
Dhea (x.(())),. P(R')
exp(3)
(x(en.a)))P()
P(R)
II
exp()(22
(16)
exp(s
(pr( P(R)
2bea exp(s12 (a.b))
(s.b))
(n.a)
27

---

Published in Transactions on Machine Learning Research (10/2022)
Thus, while P(D) cancels, the rest does not. The reason this is important is because the proof of rapid mixing in RRaaachandran & Amir (007a)) assumes that the log of the posterior probability for a reward sample in MCMC is
((R) 3
Σ @s(s,a).
(17)
(s.a)ED
This makes the proofs incorrect, since the counterfactual Q-value terms in the likelihood function are ignored, namely the Q-values of alternative actions
It is easy show that using the likelihood function presented in the proofs of rapid mixing by Ramachandran & Amir (2007a) can lead to trivial and non-sensical reward. For simplicity assume uniform prior can focus on the likelihood function. If we choose the likelihood function to be
P(D exp(3
Σ Qk(s,a)),
(18)
(x.A)DD
then setting R(s) Rmax, Vs maximizes the likelihood function; however, noted by Ng et al. (2000) constant reward function makes every policy optimal, and gives no insight into the reward function of optimal policy of the demonstrator. Thus, if we want to find a reward function that, when optimized, leads to behavior similar to the demonstrator, we need a likelihood function that maximizes the probability of the demonstrations. This calculation, by necessity, must then include the Q-values of the actions not taken by the demonstrator, leading us the likelihood function used in our paper and shown in Equation (8). In the next. section, we first seek to remedy this flaw in the proof of rapid mixing for Bayesian IRL. Then in the following section we show that this analysis also applies to BICRL.
D.2 Rapid Mixing Theorem for Bayesian IRL
We make use of the following Lemma from Applegate Kannan (1911) and Ramachandran & Amir (200a
Lemma D.1. Let F()) be a positive real valued function defined on the cube {e IR" : -d S x, S d} and f(x) log F(x). If there exist real numbers and i. such that
1f(z) - f()) s L||x yllco:
(19)
and
f()x + (1- 2 2f(x) + (1 X)f(8) - K,
(20)
for all E [0, then the Markov chain induced by Grid Walk and Policy Walk on F rapidly mizes to within of R T2 log !) steps.
Proof. See Applegate & Kannan 1991
We will also need the following Lemma relating the Lipschitz-smoothness of value functions and reward functions. Here, we use the vectorized notation of value functions and reward functions for notational simplicity, but note that the same analysis applics to continuous MDPs. Lemma D.2.
V (s) (s) -
1 - R1 -Rella
(21)
Proof.
[ - V2 5 R1 + +P Vř, R2 - P Vř, 1l.0
(22)
< Rí - RRllox + >1 Vš, - -?Pr; V2 |loc
(23)
S Rí B2llx + > PIl (V,, -VR
(24)
Rí Relloc > Pa; |0x0 IV -V 12x
(25)
28

---

Published in Transactions on Machine Learning Research (10/2022)
RR R2lloc + > - VRolloo
(26)
Thus, have
VV (VR S 1-
11-1111- 1| R2lloo
(27)
and this gives us the final desired result
VV (8) Vūg (s) S max VR, (s)
Vig (s) [V (s.a) (s. S 1 1-9 1R, Relloo
(28)
Theorem D.3. Given an MDP, M (S..S.TTT)) with |S|= N, and a distribution over rewards P(R)
P(R)D D) defined by Equation 14) with uniform prior P(R) over the cube C = {R E R - Rmax R S Rmax), if Rmax = O(1/N) and A O(),, then P(R) can be efficiently sampled within enror in O(2 log 1/e) steps by Bayesian IRL (Ramachandran & Amir 2007a).
As stated in the theorem, assume uniform prior and that |A| = 0(1). Note that it is common that the number of actions is constant so this is not constraining. We will also assume that Rmax = O(1NN). As noted by RRaachandran & Amir (2007a], this is not restrictive since we can rescale the rewards (and hence the value functions and Q-value functions) by a constant factor h after computing the posterior without changing the optimal policy.
To show rapid mixing, we need to prove that there exist L and as prescribed in Lemma D.1 Assuming uniform prior, can ignore the prior. We now focus on the likelihood function for BICRL. The likelihood function is
(Qp(s,a)
P(DI))
II
(29)
(S.OED EdEA e (T(())))
( we let F(R) = II Eoca 3 and f(R) = log F(R)
Thus,
= BE, (8)
E, log EvEr (k(()))) We first consider the Lipschitz property. We have
BQR, (s,a) - -log
8Q2, (s.b)
(0n + log
Σ
QRg (x:b)
5
(30)
DeA
BEA
B Qn (s, a) - Un (s, (s, +
log
9Qnn
(s.b)
log
ARn (x.b)
(31)
beA
DEA
We now consider each term individually. Starting with the first term, have
28
$ QlQin (s, - Qig (s, a)) < I-2 RR R2loor
(32)
by Lemma in the Appendix of Barreto et al. 2017). We now consider the second term. Recall that
max maxf21,................ Fnd S log Σ exp S max max(x1,..... r. + log n.
(33)
We thus have
log
e A2kn (8.b)
log
80R (x.b)
< max 3Q (s.b) + log [A] max BQ (s.
(34)
PEA
be A
1BV (s) log |A| BVR, (s)
(35)
log A + 3 V (s) VR, (s)
(36)
29

---

Published in Transactions on Machine Learning Research (10/2022)
B [R] R2g
S log A +
(37)
1 7
3
0
[R - R2lloo);
(38)
where the second to last line follows from Lemma D.2 and the last line follows from our assumption that A = O(1). The above analysis shows that we have
(S()) - s( = 8 Σ QR. (81, uz) - Σ log
Ri, (st.b) - B E Qk. (6s,aa))))))))) + Σ log
Binr (s,,b)
bEA
BEA
(39)
S 33 Σ 12.. 0s) - BQQ (8i ai) + Σ log Σ
(Rny (si.h) - -log
Ang (s)
(40)
DEA
DeA
2
NB || R1 R2lla0
[R R2lloo +
(41)
1-7
1 1-9
3
[R] R2lloo.
(42)
7
We now turn to showing approximate log-concavity. For any arbitrary policy ır let
(m) 8 Σ Th(s: ai R)
Σ log (Q((e,))
(43)
We have that
f(R) = 3 3 (i((s,))) - Σ log Σ
(44)
b
S B Σ PR(s),)) a.) - - max 3QR(s..
(45)
b
< 8 Σ Pi(siaai)
-E 3VH(ss)
(46)
< 0,
(47)
where we have again used the fact that
max(#1 ... mn S log Σ expo S (1ax(x1,...,.44 + log n,
(48)
and also that v*(s)= = max, (*(s, a). Thus, we also have
[=( 3 E0 (5) ai It)
Σ log
e (Q(().
(49)
Rmax
2 -13 Σ 1-7
Σ log
(50)
b
-B Σ Rimax
3 RRmax
Σ
+ log [A)
(51)
1-7
1-7
R N
3Rmax
N(
1-7 + log O(1))
(52)
?
2,3 2.3 N
(53)
1-7
23 23Rmax N
2 S(R)
(54)
1 ?
30

---

Published in Transactions on Machine Learning Research (10/2022)
where we have used the fact that Q-values are upper bounded by Rmax/ -7 and where the last line comes from the fact that (R) is non-positive.
We can now prove approximate log-concavity. Let Rt = AR1 + (1 R), then we have
S(R + (1 - 2) = B E 2Te (si, - Σ log
e
3Q
n (s;
"
(55)
BEA
= 3
E
RR'S(ss,, a4) = si, a0 azl
(56)
R
t=
B. x
IEmo 7 (( 00=0)00=0))
log
(57)
Pe
3
R (s2, az) + (1 R) = 00
= ail
(58)
R
1=0
3. ; Im
log
(59)
bEA
3
E
(8t, = 81, = a:) + 7 2) [R2 at)l = 81, ag = a;}
(60)
s.. Er
(a00)//000000000((0--000-a)))0)0 (1 ma.]
log
(61)
B
1Q Th (8i, a:) + (1 - -2)Q (si,
(62)
BrQtn (1:b)+(1->10)) (xx.)) (e..b)
Σ log Elog>
(63)
DEA
Th' (s; 3 1Q (Si, az) +B (1-A))
(64)
R2
E Alog
BQ I (sr.b)
Σ( A)
Ony
Th' (sr,b)
(65)
DEA
= NFz (R1) + (1
2)5 Rr
(R2)
(66)
2.3 N
2.3RmaxN N
2 A(((R))) 1 1-7
+ (1-A)(((RR)
(67)
1 7
2,3 N
=S((R)) + (1 - (Ra)
(68)
1-?
where Line 665) follows from the convexity of the log-sum Thus, have
bog-ssum-exponee exponential and Line 67 follows from Equation 54
3N3 1-7'
L
(69)
and
23 N
(70)
1-7 7
Thus, by Lemma D.I the Markov chain induced by Bayesian IRL mixes rapidly to within of P in number of steps equal to O(N2
R2 R2 1!2 (2exp(2k) log !) = 0 222
1 3ND
(28 N 1-7 log ! = =ON22 log 1/6).
N
exp
31

---

Published in Transactions on Machine Learning Research (10/2022)
D.3 Extension to BICRL
We now show that the above proof also exlends to the Bayesian Inverse Constrained RL (BICRL) algorithm that we have proposed in this paper.
Corollary D.3.1. BICRL has the same rapid mixing properties Bayesian IRL.
Proof. Note first that in BICRL sample over the binary hypercube {0, 10, where N is the mumber of states. We also sample over the constraint penalty scalar Tp- In practice we have -Tp in the range [0, Rymax], so BICRL samples are just a special case of sampling over the cuber {i E IR=+1, : 0 S I; S Rmax). BICRL assumes access to a known task reward and then computes a posterior probability using Q-values over the augmented reward function given by
rp R(s,a)
if Ic(s,a) is otherwise.
as,
(71)
Thus, BICRL satisfies the same conditions Bayesian IRL and by Lemma D.1 the Markov chain induced by BICRL mixes rapidly to within of P in number of steps equal to OoN 1/c).
32


Reviews:
[{"review_id": "JJcGjbK1t2", "reviewer": "Reviewer_a2ZC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\n* I like that the paper considers not only constraint inference, but also active learning and feature-based and hierarchical versions of the approach. Altogether, they comprise a thorough contribution.\n* The engagement with previous work is very good throughout the paper, both in terms of the writing and in terms of well selected baselines in experiments.\n* Using the Paternain et al. (2019) zero duality gap result as motivation makes sense and provides a good theoretical foundation for the work.\n* The writing is overall very clear and well organized.\n* The experimental environments are relatively simple and gridworld-y overall, but seems as-good-as or better than previous work in this line (IRL is hard!).\n\n\n### Weaknesses\n\n* In contrast to previous work, this paper allows demonstrators to sometimes violate constraints. On one hand, this is perhaps more realistic, since demonstrations are often imperfect. On the other hand, if constraints can be violated, it calls into question whether “constraints” are really the appropriate framing. It may be more accurate to describe the setting as one where there is a strong prior over the reward function (each transition either elicits the known nominal reward or an unknown other constant reward). In fact, I think that nothing would change in the approach if rather than the unknown “constraint” states being uniformly bad, they were actually uniformly good, or just uniformly somewhere in between.\n* Relatedly, my understanding is that the only difference between BICRL and the ​​baselines BCPR and BCDR is that the former assumes a state-independent reward prior and the latter have state-dependent reward priors.\n* As far as I can tell, the demonstrations used throughout this work are collected synthetically by running a policy that conforms to the Boltzmann-type model. It would be much more compelling to show results with human demonstrations, or at least demonstrations that do not directly conform to the model assumed in this work.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper considers the problem of inferring unknown constraint states in a constrained MDP with known transition model, nominal reward function, and finite state and action spaces. The dual formulation of the constrained RL objective leads to an MCMC algorithm where both the constraint states and the Lagrange multiplier (reward for violating the constraint states) are sampled. The resulting posterior can also be used for active learning. The paper also proposes feature-based and hierarchical extensions of the main approach. Experiments are in a variety of grid-like domains, including robotic home and highway environments, with comparisons against several baselines.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "* I am curious about the time complexity of the proposed BICRL vs the GICI baseline. My understanding is that GICI does not have to run value iteration in an inner loop, so I imagine it could be significantly faster than BICRL. The comparisons in Section 4.2 are against GICI using constant threshold on KL divergence as a stopping criterion. Could we instead see a graph with wall-clock time on the x axis and performance (either FNR, FPR, or Precision) on the y axis, and one line for each of BICRL and GICI? Or instead, could we see additional results for smaller thresholds for the stopping criterion of GICI, to rule out the possibility that the constant 0.1 was just a poor choice in this domain?\n* Can you clarify whether all of the baselines assume a known transition model?\n* The second paragraph of Section 3.2 “Problem Statement” contains information about the approach, rather than the problem statement. I would suggest moving this information elsewhere, to let the problem statement stand alone.\n* What is the motivation for including results with Expected a Posteriori (EAP)? In a practical application, would EAP ever be a better choice than MAP?\n* A consistent grammatical issue is missing commas, especially following introductory clauses. For example:\n   * For these simulations we utilized 100 expert trajectories. (There should be a comma after “simulations”)\n   * In this section we motivate BICRL… (There should be a comma after “section”)\n   * For a large number of environments and tasks safety constraints are compositional. (There should be a comma after “tasks”)\n   * There are many others -- please check the first sentence of every paragraph and apply this change everywhere.\n\n## Minor\n\n* “in a Hierarchical manner” → “in a hierarchical manner”\n* “an Hierarchical version” → “a hierarchical version”\n* My understanding is that “constraint allocation” and “constraint” are used interchangeably. If there is a distinction, please clarify, otherwise, it would be clearer to stick with one (probably just “constraint”).\n* The Scobee & Sastry reference should be updated from arXiv 2019 to ICLR 2020.\n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "v7v9ChLZfH", "reviewer": "Reviewer_Cajr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well written and generally well organized, and situated the work well in the literature.\n- The proposed algorithm is clean and well justified, and performs well on the proposed experiments.\n- The proposed modeling framework yields a simple and easy to implement algorithm.\n- The authors do well to highlight the benefits of the uncertainty quantification provided by a Bayesian approach by including an active learning example.\n\nWeaknesses:\n- The paper is posed as a method for learning MDPs with hard constraints (having an expected constraint violation equal to 0, as stated in equation (1), but the algorithm is designed only for soft constraints which add a fixed penalty for constraint violation. The authors argue that this is justified, as the penalty formulation arises in the Lagrangian of the original problem. However, while it is true that there exists a value of the penalty $r_p$ such that the solutions to the penalized formulation and the original problem are the same, the specific value of $r_p$ will depend on the nominal reward function, and not necessarily be the same across different tasks in the same environment. For all of the experiments, expert trajectories were drawn by using a Botlzmann exploration policy with a reward function with soft constraints encoded by some true value of $r_p$ (except perhaps the home navigation example, for which details were not given). However, realistically, we cannot know that the experts are acting with this type of constraint model. While assuming this soft constraint model may be a useful modeling assumption, the authors should demonstrate how this approach generalizes to expert trajectories which follow a different model of constraints (such as hard constraints which are never violated in the demonstrations?)\n\n- More generally, I found the experimental comparisons to be limited. As mentioned, the experiments all used expert trajectories that were drawn from the exact model assumed by the algorithm: soft constraints which share an equal penalty, and actions executed via a Boltzmann policy with $\\beta = 1$. Within this setup, it is not surprising to me that BICRL outperforms the BIRL, BCPR, and BDPR baselines, as the latter algorithms make fewer assumptions on the reward structure. The paper would be greatly strengthened by experimental evaluation under settings which do not exactly meet the modeling assumptions chosen by BICRL, including real-world data collected from human expert behavior, or data where the “optimality” of the expert data isn’t known to the algorithm, i.e. the $\\beta$ that is used to collect data is different from that used in the inference step.\n\n- The active learning approach feels suboptimal: As after each iteration, the expert is only queried on a single state, rather than a collection of the most uncertain states. Furthermore, as the experts aim to avoid constraint states, their behavior when in a constraint state would not necessarily be informative. It seems that sampling states that are in the backward reachable set to states with high uncertainty would provide the most information. The authors should better motivate their approach to the active learning problem, and at the very least highlight this potential limitations of their approach.\n\n- Finally, the paper lacks some important details and discussion in the experimental results:\n\n    - The section on Hierarchical BICRL compares the original BICRL algorithm argues that the hierarchical version yields better constraint estimation and also improved computational efficiency. However, this is not necessarily a fair comparison (even with more demonstrations given to the Global version) — the hierarchical version sees a more diverse set of task demonstrations which give better coverage of the state space. Thus, the two algorithms cannot work on the same dataset — one needs to collect separate subtask data to use the hierarchical version. This distinction should be emphasized, as in real world settings, expert demonstrations may be a scarce resource. \n\n    - The section on the home navigation task is quite short and does not provide enough details about how the experiment was set up. The discussion in the appendix still leaves important details missing: How are the trajectories generated? How were the subtasks defined?", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a Bayesian method for inferring state-space constraints from expert state-action trajectories in an MDP whose (nominal) reward and transition function is known. Specifically, the authors assumes that expert act according to a Boltzmann stochastic policy following an optimal Q-function given an augmented reward function consisting of the nominal reward plus a constant penalty term if the current state is in the true constraint set. Given this model, the authors propose a Markov-chain Monte-Carlo approach to perform Bayesian inference on the constraint set as well as the value of the penalty. Furthermore, the authors propose a hierarchical approach to scale the algorithm to larger state spaces, if the larger problem can be broken down into distinct subspaces with independent subtasks which share the same constraints. Finally, the authors also extend the approach to learning constraints which are defined in terms of known features, rather than on the state-space itself. The authors demonstrate the approach through a set of numerical experiments on a set of grid navigation tasks, including grid-world problems, as well as home navigation and a lane change scenario, comparing their approach to alternative Bayesian inverse reinforcement learning algorithms which make fewer assumptions of the reward structure, as well as a non-Bayesian constraint inference algorithm in GICI.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Major changes:\n- More experiments on demonstrations that don’t exactly follow the modeling assumptions made by BICRL\n    - Synthetic data generated with different parameters (e.g. different value of $\\beta$, or noisy expert model which respects constraints) *(critical)*\n    - Real world demonstrations, e.g. human controlled navigation in the apartment navigation task. *(strengthen)*\n- Amended active learning discussion to include what sorts of demonstrations would be most informative in reducing ambiguity about constraints. *(strengthen)*\n- Added discussion highlighting the limitations of Hierarchical BICRL, namely that it requires different demonstrates, and discussion of how diversity in data may contribute to the better performance of BICRL. *(critical)*\n- Potentially add experiments comparing against Global BICRL with demonstrations from multiple tasks to distinguish the benefits of the small subproblems from the benefits from more diverse data. *(strengthen)*\n- Details on how demonstration data in the home navigation task was collected, and what the subtasks were. *(critical)*\n\nMinor changes:\n\n- Section 3.1: “Prior work by Paternain et al. (2019) shows that the problem has zero duality gap and hence the solutions of the aforementioned two problems are equivalent.” What are the two problems? As written, equation (2) is just an objective function, not an optimization problem. *(critical)*\n- Section 3.3: “We further allow for randomly accepting proposals even if they are not associated with a higher likelihood to enhance exploration in the Markov Chain.” As far as I can tell, this is standard practice in the Metropolis-Hastings algorithm for MCMC, while the language in the paper suggests it is a unique choice in BICRL. If it is novel, the authors should provide more motivation for this choice, while if it is not, then the authors should make clear that the implementation is the standard Metropolis-Hastings algorithm for MCMC. *(critical)*\n- Algorithm 1: “if sample constraints” is unclear, amend to make more explicit that this if clause is a form of scheduling *(strengthen)*\n- Figure 2: Subfigure (a) is unrelated to subfigures (b) and (c), perhaps (a) should move to be part of Figure 1. *(strengthen)*\n- Section 5: “Stochastic dynamics, except for providing a more general framework to the deterministic ones, can be seen as…” Using “except” in this case is confusing,  reword, perhaps to “beyond providing…” *(strengthen)*\n- Figure 8 and Figure 14 are inconsistent - 14 shows false constraints identified near the doorways. These should be made consistent and the potential cause of the false positives should be discussed. *(critical)*\n- Add a discussion of future work *(strengthen)*", "broader_impact_concerns": "I do not think the lack of a Broader Impact statement here is an egregious limitation, but the authors could consider adding a discussion of the implications of both false-positive and false-negative constraint identification.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bTtxOtHwvU", "reviewer": "Reviewer_8ZEH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths. \n\nThis is a work of possible interest to the community. Writing and presentation are clear and, for the most part, concepts and statements are clearly introduced. The main idea introduced in the paper, Bayesian Inverse Constrained Reinforcement Learning, is simple yet appears to work well in practice. This behavior is supported by extensive numerical evaluations.\n\nWeaknesses. \n\n- It feels like the paper is missing some more theoretical support for the proposed algorithm. It would increase the value of the manuscript to provide a more thorough analysis of the methodology leading to the algorithm and to evaluate some of its properties. As it currently stands, the manuscript is just a very simple idea applied to a large number of numerical scenarios.\n\n- Isn't setting =0 in the constraint in (1)-(2) very restrictive? This is asking to satisfy the constraint with probability 1 (zero constraint violation), which is unfeasible in practice for most stochastic policies. Would it not be better to allow for some epsilon-probability (in (1), a constant epsilon instead of 0)?\n\n- In section 4.1, \"As expected, the agent demonstrates high uncertainty in areas that are far away from the expert demonstrations, like the bottom right section of the grid.\" Out of curiosity, could you go into more detail about why this behavior occurs (e.g., only on the bottom-right and not on the top-right corner)?\n\n- While numerical extensive, they are all in discrete or grid world domains. It would be very interesting to evaluate the proposed methodology in continuous spaces rather than only grid world environments.", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors study the problem of inferring constraints from demonstrations in a reinforcement learning setting. To this end, they propose Bayesian Inverse Constrained Reinforcement Learning (BICRL), a method that acquires the posterior probability over constraints given expert demonstrations. Extensive numerical evaluations are provided to support the method.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "Addressing the previously mentioned weaknesses should be sufficient.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers the problem of inferring state-space constraints in a known MDP from demonstrations. Contemporary methods primarily focus on maximum likelihood inference of constraints, and thus do not model or utilize the uncertainty in the resulting constraint estimates. In contrast, the paper proposes a Bayesian approach to inferring state-space constraints for an MDP with known transition and nominal reward functions based upon expert state-action trajectories. These trajectories are assumed to correspond to a Boltzmann policy, where the nominal reward is augmented with a fixed reward penalty when a state lies in the constraint set. The proposed algorithm uses MCMC to perform Bayesian inference over the constraint set and the reward penalty. The paper then describe feature-based and hierarchical variations of their algorithm that extend this approach to larger state spaces. As a demonstration of the usefulness of uncertainty estimates for the inferred constraints, the authors present a simple approach to active learning that utilizes the resulting posterior. The paper compares the performance of the proposed constraint inference algorithm to recent Bayesian and non-Bayesian baselines in a series of discrete or grid-like domains, as well as a continuous-state environment.

The paper was thoroughly reviewed by three knowledgeable reviewers, who read the authors' responses and updated their reviews accordingly. The reviewers agree that the final manuscript provides a valuable contribution to RL constraint inference---the proposed Bayesian inference algorithm is novel and theoretically sound, and its effectiveness is experimentally demonstrated on a variety of domains. The reviewers also agree that the paper is well written and clearly organized, and that it provides a solid discussion of and comparison to existing work on constraint inference. The reviewers raised several key concerns about the initial submission, notably: the fact that the experiments involved synthetically generated demonstrations that conform to the modeling assumptions by construction; questions about the comparisons to the GICI baseline; and limitations of the hierarchical variation of the approach and its use for active learning. The authors clearly put considerable effort into addressing the reviewers' questions and concerns, which includes carrying out additional experiments with non-conforming demonstrations and updated implementations of GICI, and revisions the text to speak to limitations. All three reviewers appreciate these changes and agree that the final manuscript warrants acceptance.
Decision: Accept (poster)