# Machine Learning-Based Path Loss Modeling with Simplified Features

Jonathan Ethier and Mathieu Châteauvert J. Ethier and M. Chateauvert are with
the Communications Research Centre, Kanata, Ontario, Canada, e-mail:
<EMAIL_ADDRESS>
###### Abstract

Propagation modeling is a crucial tool for successful wireless deployments and
spectrum planning with the demand for high modeling accuracy continuing to
grow. Recognizing that detailed knowledge of the physical environment (terrain
and clutter) is essential, we propose a novel approach that uses environmental
information for predictions. Instead of relying on complex, detail-intensive
models, we explore the use of simplified scalar features involving the total
obstruction depth along the direct path from transmitter to receiver. Obstacle
depth offers a streamlined, yet surprisingly accurate, method for predicting
wireless signal propagation, providing a practical solution for efficient and
effective wireless network planning.

###### Index Terms:

Machine Learning, Path Loss Modeling, Feature Selection, Drive Test
Measurements

##  I Introduction

Propagation modeling is used to make predictions of wireless signal power
levels in aid of radio deployments including coverage and interference
analysis. Path loss modeling is a popular approach to this end, allowing for a
generic prediction of loss along a wireless link, thereby providing network
planners with the ability to consider a range of physical layer attributes
(antenna gains, system technology, and the like). In mid-band communications
scenarios with mostly line-of-sight (LOS) conditions, propagation modeling can
be covered by models such as Longley-Rice [1] and even the commonly used free
space path loss (FSPL) model.

However, in non-LOS conditions, these models provide degraded prediction
accuracy by failing to account for the signal attenuation and interference
caused by electromagnetic interactions with terrain and clutter [2]. Various
propagation models explicitly account for clutter, including ITU-R P.1812-6
[3] (hereafter known as P.1812), which is appropriate for mid-band
frequencies. These models require knowledge of the entire path profile between
transmit and receive, including the complete spatial variation of the terrain
(DTM) and surface (DSM) as separate entities (effectively a 1D problem). Other
models exist that use thousands of features in 2D [4] and 3D [5]
representations of terrain and clutter and perform point-to-multi-point type
predictions.

The question addressed in this paper is as follows: can simple features
derived from path profiles be used as the sole input to a predictor of path
loss along a wireless link and still provide sufficient accuracy for
predicting radio coverage? In particular, we will (1) use machine learning
(ML)-based modeling, comparing against traditional approaches and (2)
emphasize the use of measurement data for training to provide us with reliable
ground truth. Similar work has been done [6], but did not use features that
describe the physical environment, which we will use gainfully here.

In Section II, we will discuss the data sources and processing techniques that
can be used to sculpt data to train our models. Following this, in Section
III, we will consider the models used in our analysis, along with feature
selection and their possible configurations. Section IV will outline our
training and testing approaches and provide the results of the study, followed
by Section V where we dive deeper into the influence of the key model feature
of obstacle depth. Finally, Section VI will provide conclusions and propose
future work.

##  II Data Preparation

###  II-A Drive Test Measurement Data

Measurement data is critical when developing new propagation models, namely
for model testing. This requirement is exacerbated when training ML-based
models, with measurement data taking on double duty: both training and
testing. Not only must the data be high quality, but numerous and varied as
well. To this end, we use the openly available ITU-R UK Ofcom drive test
dataset [7]. This drive test was conducted across the United Kingdom from 2015
to 2018, consisting of six frequencies in mid-band (449, 915, 1802, 2695,
3602, and 5850 MHz) at seven geographically and morphologically distinct
sites. The dataset consists of 8.2 million measurements, with more than seven
million measurements above the measurement noise floor. The distribution of
path loss over link distance for the Ofcom data is shown in Fig. 1. The reader
is encouraged to refer to [7] for drive test path details.

Figure 1: Measured Path Loss vs. Distance for the Ofcom [7] Data (FSPL shown
for the two frequency extremes)

The minimum, median, and maximum path loss and link distance in the dataset
are 50.64, 160.28, and 183.59 dB, and 18, 8093, and 78613 meters, respectively
(only measurements above the noise floor). Transmitter height varies from 17
to 25 meters, while the receiver has a constant height of 1.5 meters. Both
transmit and receive use omnidirectional antennas. The majority (98.5%) of the
samples have NLOS conditions. Every sample has a measured path loss in dB,
frequency in MHz and the associated latitude, longitude and antenna height
above terrain for the receiver and transmitter. A propagation model can be
constructed using these parameters but such a model would lack information
about the environment. The acquisition of environmental information will be
discussed next.

###  II-B Terrain and Surface Databases

Online databases of DTM and DSM have increased in both detail and coverage in
recent years, providing a treasure trove of information for many scientific
and engineering disciplines. These databases are made publicly available by
governments worldwide, including Canadian [8], USA [9], and UK [10]
governments. Fortunately, the latter database provides the resources one needs
to extract path profiles for six of the seven sites in the Ofcom drive test
data (Scar Hill GIS data not being publicly available). The DTM and DSM data
are available in geotiff format, making direct path calculations and
assessment of terrain and clutter a straightforward task.

###  II-C The SAFE Tool for Path Profile Extraction and Analysis

The propagation model known as the Signal Attenuation through Foliage
Estimator (SAFE) tool [11] contains several sub-routines that can be used to
process geotiff files to extract the DTM and DSM path profiles, given only the
transmit and receive antenna heights and their (lat, lon) coordinates. With
path profiles in hand, numerous features can be derived including quantities
such as total obstacle depth along the direct path. The source code for the
SAFE tool is available on GitHub [12] and is used extensively in this paper
for path profile and feature extraction.

Figure 2: Example path profile extracted using the SAFE tool. Total depth
through terrain (724 meters) and total depth through clutter (67 meters + 314
meters = 381 meters) are as shown with total obstacle depth as the sum of the
two (724 meters + 381 meters = 1105 meters). Any number of non-contiguous
blocks can contribute to the total terrain, clutter and obstacle depths.

##  III Feature and Model Selection

The goal of our feature selection is to use as few features as possible while
still sufficiently describing the physical properties of a radio link. The
default features in any propagation model are frequency and link distance
(distance along the direct path from transmitter to receiver). We consider two
additional environmental features: terrain and clutter depth, where depth is
calculated as the total obstruction (in meters) in either terrain or clutter
along the direct path. Note that the total depth is computed from any number
of non-contiguous obstructions, and clutter that appears above obstructing
terrain does not contribute to the total clutter depth.

Three configurations of these features will be considered as shown in Table I.
Note that Obstacle Depth is equal to Terrain Depth + Clutter Depth, i.e.
$o=t+c$, and was selected as a simple feature that can be derived from
datasets that only contain surface data (DSM) and no separate terrain data
(DTM). A visualization of the path profile and feature extraction is shown in
Figure 2. The three model architectures will be discussed next.

TABLE I: Feature Configurations Features |  Feature List
---|---
2 |  Link Distance (d), Frequency (f)
3 |  Dist. (d), Freq. (f), Obstacle Depth (o)
4 |  Dist. (d), Freq. (f), Terrain Depth (t), Clutter Depth (c)

####  III-1 Curve-fit Log Regression (Log-Reg) Model

The modeling approach we begin with is a traditional curve fit using the
scaled logarithms shown in Equations 1-3 for the feature configurations 1-3.
Using the $curve\\_fit$ method from the Python package $scipy$, we optimize
the scalar parameters A-E, depending on the configuration used.

$PL=\mathrm{A}\log_{10}(f)+\mathrm{B}\log_{10}(d)+\mathrm{C}$ (1)
$PL=\mathrm{A}\log_{10}(f)+\mathrm{B}\log_{10}(d)+\mathrm{C}\log_{10}(o)+\mathrm{D}$
(2)
$PL=\mathrm{A}\log_{10}(f)+\mathrm{B}\log_{10}(d)+\mathrm{C}\log_{10}(t)+\mathrm{D}\log_{10}(c)+\mathrm{E}$
(3)

For brevity’s sake, the ideal ML architectures were determined with grid
search and the results will be stated here. The model architectures were
determined to yield lower prediction errors while not overfitting.

####  III-2 Boosted Trees (XGBoost) Model

For boosted trees, the XGBoost Python package was used with the ideal model:

  * •

100 regression trees with a depth of 2, with all other parameters left as
default.

####  III-3 Fully-Connected Network (FCN) Model

Lastly, we consider a fully connected network (FCN) using Tensorflow & Keras
Python packages. The ideal fully connected network has the following
hyperparameters (obtained through grid search):

  * •

One layer of 256 neurons, ReLU activation, a dropout of 20% after the single
layer, ADAM optimization, MSE loss function, batch size of 8,192, an 80/20
random train/validate split and a max of 20 training epochs.

Note that XGBoost and FCNs are both known to perform well with tabular data
[13], which makes them ideal for our scalar feature-based modeling approach.

##  IV Training and Results

###  IV-A Train and Test Approach

With a large collection of training samples, it is important to carefully
select the training and test scenarios to avoid overfitting and data leakage,
thus allowing proper assessment of model generalization [14]. Various test
scenarios were considered, including splitting test sites geographically (e.g.
training on 80% of the samples in a city and testing on the remaining non-
overlapping 20%). However, such a scenario allows too much of a drive test to
be present in the training data and it would be difficult to judge to what
extent the geographic adjacency of measurements influences scores.
Alternatively, we take a more stringent route and perform a round-robin of
city holdouts, training on five cities and testing on the sixth (repeating
this six times). This minimizes both geographic adjacency and data leakage.

###  IV-B Test Results

A summary of the prediction errors for the three modeling techniques, three
feature configurations and six city holdouts is shown in Table III. Root mean
squared error (RMSE) is used to judge the models as it penalizes large errors
more so than mean absolute error (MAE). Additionally, a column listing the
RMSE for the FSPL and P.1812-6 models, with the latter quoted from [3], are
included as baselines. The P.1812 model performs well on the data, which is to
be expected since it was developed using the Ofcom drive test data for model
validation. Conversely, an FSPL model performs poorly on this data since the
datasets are heavily dominated by NLOS measurements. The coefficients of the
Log-Reg London holdout models (Eq. 1-3) are shown in Table II.

TABLE II: Log-Reg Model Coefficients (London Holdout) No. of Features | Coefficient | Optimized Values
---|---|---
2 features | A, B, C | 30.52, 31.08, -253.24
3 features | A, B, C, D | 18.32, 31.77, 11.03, -242.34
4 features | A, B, C, D, E | 20.93, 31.76, 3.96, 8.50, -247.91

For the FCN model, we perform 20 optimization runs for each city/feature
combination (18 in total) with random starting weights and train/validation
splits. Consequently, the RMSE shown in the table for FCN is the median RMSE
among 20 runs, with the largest standard deviation among the six city holdouts
and three different feature configurations never exceeding 2% of the median
RMSE. This indicates the modeling is largely insensitive to the starting
weights and random train/validate split. This is at least in part due to the
very large number of samples that help reduce the variation from run to run.
Note that running any single model has a similar maximum RMSE difference of 2%
relative to a 20-model median ensemble, making the ensemble approach not
necessarily worth the additional computational costs.

TABLE III: City Holdout Model Test Results (RMSE in dB) |  |  | Log-Regression | Boosted Trees (XGBoost) | Fully-Connected Network (FCN)
---|---|---|---|---|---
| FSPL | P.1812 | 2 features | 3 features | 4 features | 2 features | 3 features | 4 features | 2 features | 3 features | 4 features
London | 45.7 | 8.8 | 11.65 | 7.44 | 7.59 | 11.04 | 7.75 | 7.60 | 10.66 | 7.44 | 7.58
Merthyr | 43.5 | 13.4 | 10.88 | 9.17 | 8.97 | 12.34 | 6.91 | 6.89 | 12.28 | 7.22 | 7.02
Nottingham | 40.5 | 12.6 | 11.94 | 7.38 | 7.82 | 12.06 | 7.15 | 6.93 | 12.06 | 7.07 | 6.68
Southampton | 47.1 | 9.5 | 11.37 | 7.13 | 6.71 | 10.90 | 6.38 | 6.06 | 10.95 | 6.64 | 6.12
Stevenage | 45.7 | 12.3 | 11.46 | 9.13 | 9.24 | 11.17 | 8.63 | 8.49 | 11.14 | 8.81 | 8.63
Boston | 31.9 | 11.4 | 17.68 | 7.64 | 8.08 | 17.15 | 8.21 | 7.78 | 17.51 | 7.56 | 7.52
Median | 44.6 | 11.85 | 12.50 | 7.98 | 8.07 | 12.44 | 7.51 | 7.29 | 12.43 | 7.46 | 7.26

The FCN has a lower median RMSE than boosted trees and log regression, though
the advantage of the FCN models over XGBoost is not very significant. In all
cases, the more features present in the model, the lower the RMSE. For the FCN
model, we observed 4.97 and 5.17 dB improvements for three and four features
over the simplest two-feature model, respectively. Introducing obstacle depth
as a third feature has a very significant impact on reducing RMSE.

Separating obstacle depth into two features (terrain & clutter) does not
provide a significant reduction in error. For the FCN model, we only see a 0.2
dB improvement. This is possibly due to a temporal mismatch between
measurements (2015-2018) and geospatial information (2022), which degrades the
efficacy of clutter information since it changes over time.

The majority of measurements reside in high-clutter urban and suburban
environments (98.5% of measurements are NLOS), with a small number of rural
measurements residing at the periphery of the drive test areas. This allows
models to generalize well between city holdouts due to the similarity in
clutter types and hence the similar RMS errors. One exception is the Stevenage
holdout city model which has a higher RMSE relative to the other holdouts.
This is likely due to the city having significantly newer construction [7]
than other drive test sites, thus being more difficult to generalize using
training data from cities with older infrastructure. Scar Hill is the only
majority rural drive test in the Ofcom measurements, and detailed DTM/DSM data
for this region is not currently available in open source and was therefore
not included in this study.

A histogram plot of the prediction errors for the fully connected network
models (London holdout) is shown in Figure 3 for two, three and four feature
inputs (with -7.70, -0.97 and +0.74 dB median error, respectively). Without
environmental information, the predictions under-predict path loss, but as one
includes additional features describing the environment, the median error is
closer to zero. Similar results can be observed for the other five city
holdout test scenarios.

Figure 3: Histogram of Prediction Errors (London Holdout, FCN)

The RMSE obtained for the path loss model in [4] is in the range of 3-5 dB
whereas our models are in the range of 6-8 dB. In the former, the authors used
high-resolution imagery and detailed path profiles (equivalent to many
thousands of features), whereas our work relied on 3-4 scalar feature inputs.
This comparison emphasizes the engineering balance of increasing model
accuracy at the cost of increasing model complexity. Our work shows that on
the low end of model complexity, accurate modeling is still feasible.

##  V Analysis of Obstacle Depth Modeling

Given the significant improvement offered by the total obstacle depth feature
(5 dB reduction in RMSE), it is worthwhile exploring how this feature is
accounted for in the ML models, and the FCN model in particular. We can
compute the obstacle loss by subtracting the FSPL from the PL predicted by the
ML model, as shown in Equation 4:

$Obstacle\hskip 2.84526ptLoss=PL_{ML}-FSPL$ (4)

In Figure 4, we plot the obstacle loss as a function of total obstacle depth,
for a few pairs of frequency & distance. This effectively turns the
propagation model into an obstacle loss model. The loss curves shown in Fig. 4
are reminiscent of the clutter loss model used in SAFE [11], namely the P.833
model [15]. This implies that the ML-FCN model is learning behaviours that are
grounded in physics. Additionally, the expected trend of increasing loss with
increasing frequency is evident in the plots.

A limitation of the ML modeling is evident by considering that obstacle loss
should be insensitive to link distance (identically coloured plots should
perfectly overlap in Fig. 4) but we observe that shorter links (5 km) provide
slightly higher obstacle loss than longer links (10 km). This is a limitation
of the modeling that could be addressed by additional, relevant features (or
additional training samples) that would help the models learn the correct
influence of link distance. Another limitation of the modeling is the non-zero
obstacle loss when the total obstacle depth is zero. This is likely to be in
part due to LOS links still having interactions with clutter and terrain via
Fresnel zone effects and NLOS paths. Both of these limitations will be
addressed in future work.

Figure 4: Predicted Obstacle Loss for Various Frequencies and Link Distances
(London Holdout FCN-ML model)

##  VI Conclusion

Propagation modeling has always been integral to wireless deployments and
spectrum planning with ever-increasing demands on improving modeling accuracy.
Accounting for the physical environment in greater detail is key to improving
prediction accuracy. In this paper, we showed that simple scalar features
describing terrain and clutter can be used to train very accurate machine
learning-based propagation models. When combined with link distance and
frequency, simple features such as total obstacle depth along the direct path
provide enough predictive ability to yield well-generalized models with RMSE
in the range of 6-8 dB. Future work will address some of the limitations
discussed in Section V as well as incorporate clutter classification and
seasonal information as inputs to the machine learning models.

## Acknowledgments

The authors would like to thank Dr. Pierre Bouchard and Dr. Yvo de Jong for
sharing their expertise in propagation theory and measurements, and Dr. Paul
Guinand for sharing his knowledge in optimization and machine learning.

## References

  * [1] “Prediction of tropospheric radio transmission over irregular terrain, a computer method-1968.” in _ESSA Tech. Rep. ERL 79-ITS 67, U.S. Gov. Printing Office, Washington, DC_ , July 1968.
  * [2] M. Hata, “Empirical formula for propagation loss in land mobile radio services,” _IEEE Transactions on Vehicular Technology_ , vol. 29, no. 3, pp. 317–325, 1980.
  * [3] P.1812: A path-specific propagation prediction method for point-to-area terrestrial services in the frequency range 30 MHz to 6000 MHz. International Telecommunications Union (ITU). [Online]. Available: https://www.itu.int/rec/R-REC-P.1812-6-202109-I/en, Accessed December 2023
  * [4] T. Hayashi and K. Ichige, “A deep-learning method for path loss prediction using geospatial information and path profiles,” _IEEE Transactions on Antennas and Propagation_ , vol. 71, no. 9, pp. 7523–7537, 2023.
  * [5] M. Chen, M. Châteauvert, and J. Ethier, “Extending machine learning based rf coverage predictions to 3d,” in _2022 IEEE International Symposium on Antennas and Propagation and USNC-URSI Radio Science Meeting (AP-S/URSI)_ , 2022, pp. 205–206.
  * [6] H.-S. Jo, C. Park, E. Lee, H. Choi, and J. Park, “Path loss prediction based on machine learning techniques: PCA, artificial neural network, and gaussian process,” _Sensors_ , vol. 20, p. 1927, 03 2020.
  * [7] UK mobile measurement data for frequencies below 6 GHz. Office of Communications (OFCom), UK. [Online]. Available: https://www.itu.int/md/R15-WP3K-C-0294, Accessed December 2023
  * [8] High-resolution digital elevation model (hrdem). Natural Resources Canada (NRCan). [Online]. Available: https://open.canada.ca/data/en/dataset/957782bf-847c-4644- a757-e383c0057995, Accessed December 2023
  * [9] The national map-data delivery. United States Geological Service. [Online]. Available: https://www.usgs.gov/the-national-map-data-delivery/gis-data-download, Accessed December 2023
  * [10] Open Data data.gov.uk. Government of the United Kingdom. [Online]. Available: https://www.data.gov.uk/, Accessed December 2023
  * [11] M. Châteauvert, J. Ethier, and P. Bouchard, “Signal attenuation through foliage estimator,” in _IEEE 14th Annual Ubiquitous Computing, Electronics & Mobile Communication Conf. (UEMCON)_, 2023, pp. 38–41.
  * [12] Signal attenuation through foliage estimator (source code). Communications Research Center (CRC) Canada. [Online]. Available: https://github.com/ic-crc/SAFE-Tool, Accessed December 2023
  * [13] I. Goodfellow, Y. Bengio, and A. Courville, _Deep Learning_ , 2016.
  * [14] C. Bishop, _Pattern Recognition and Machine Learning_ , 2006.
  * [15] P.833 : Attenuation in vegetation. International Telecommunications Union (ITU). [Online]. Available: https://www.itu.int/rec/R-REC-P.833-10-202109-I/en, Accessed March 2024


# Learning Soft Constraints From Constrained Expert Demonstrations

Ashish Gaurav
Cheriton School of Computer Science
University of Waterloo
Vector Institute
<EMAIL_ADDRESS>
&Kasra Rezaee
Huawei Technologies Canada
<EMAIL_ADDRESS>
Guiliang Liu
Cheriton School of Computer Science
University of Waterloo
Vector Institute
<EMAIL_ADDRESS>
&Pascal Poupart
Cheriton School of Computer Science
University of Waterloo
Vector Institute
<EMAIL_ADDRESS>

###### Abstract

Inverse reinforcement learning (IRL) methods assume that the expert data is
generated by an agent optimizing some reward function. However, in many
settings, the agent may optimize a reward function subject to some
constraints, where the constraints induce behaviors that may be otherwise
difficult to express with just a reward function. We consider the setting
where the reward function is given, and the constraints are unknown, and
propose a method that is able to recover these constraints satisfactorily from
the expert data. While previous work has focused on recovering hard
constraints, our method can recover cumulative soft constraints that the agent
satisfies on average per episode. In IRL fashion, our method solves this
problem by adjusting the constraint function iteratively through a constrained
optimization procedure, until the agent behavior matches the expert behavior.
Despite the simplicity of the formulation, our method is able to obtain good
results. We demonstrate our approach on synthetic environments and real world
highway driving data.

##  1 Introduction

Inverse reinforcement learning (IRL) [1, 2] refers to the problem of learning
a reward function given observed optimal or near optimal behavior. However, in
many setups, expert actions may result from a policy that inherently optimizes
a reward function subject to certain constraints. While IRL methods are able
to learn a reward function that explains the expert demonstrations well, many
tasks also require knowing constraints. Constraints can often provide a more
interpretable representation of behavior than just the reward function [3]. In
fact, constraints can represent safety requirements more strictly than reward
functions, and are therefore are especially useful in safety-critical
applications [4, 5].

Inverse constraint learning (ICL) may therefore be defined as the process of
extracting the constraint function(s) associated with the given optimal (or
near optimal) expert data, where we assume that the reward function is
available. Notably, some prior work [3, 6, 4, 5, 7] has tackled this problem
by learning hard constraints (i.e., functions that indicate which state
action-pairs are allowed).

We propose a novel method for ICL that learns cumulative soft constraints from
expert demonstrations while assuming that the reward function is known. More
precisely, we adopt the framework of constrained Markov decision processes,
where an agent seeks to maximize expected cumulative rewards subject to
constraints on the expected cumulative value of constraint functions. While
previous work in constrained RL focuses on finding an optimal policy that
respects known constraints, we seek to learn the constraints based on expert
demonstrations. We adopt an approach similar to IRL, but the goal is to learn
the constraint functions instead of the the reward function. To our knowledge,
this is the first work that learns soft cumulative constraint functions
bounded in expectations. In practice, soft constraints can take into account
noise in sensor measurements and possible violations in expert demonstrations.
Our contributions can be summarized as follows:

  * •

We propose a novel formulation and method for ICL. Our approach works with
continuous state-action spaces and can learn arbitrary Markovian constraint
functions represented by flexible neural networks. To the best of our
knowledge, our method is the first to learn cumulative soft constraints
bounded in expectation as in constrained MDPs.

  * •

We demonstrate our approach by learning constraint functions in various
synthetic environments, and a driving environment based on real world highway
driving data.

The paper is structured as follows. Section 2 provides some background about
IRL and ICL. Section 3 summarizes previous work about ICL. Section 4 describes
our new technique to learn cumulative soft constraints from expert
demonstrations. Section 5 demonstrates the approach in synthetic environments
as well as real data from human highway driving. Finally, Section 6 concludes
by discussing limitations and future work.

##  2 Background

Markov Decision Process (MDP). An MDP is defined as a tuple
$(\mathcal{S},\mathcal{A},p,\mu,r,\gamma)$, where $\mathcal{S}$ is the state
space, $\mathcal{A}$ is the action space, $p(\cdot|s,a)$ are the transition
probabilities over the next states given the current state $s$ and current
action $a$, $r:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ is the
reward function, $\mu:\mathcal{S}\rightarrow[0,1]$ is the initial state
distribution and $\gamma$ is the discount factor. The behavior of an agent in
this MDP can be represented by a stochastic policy
$\pi:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$, which is a mapping from a
state to a probability distribution over actions. A constrained MDP (CMDP) [8]
augments the MDP structure to contain a constraint function
$c:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ and an episodic
constraint threshold $\beta$.

Reinforcement learning. The objective of any standard RL procedure is to
obtain a policy that maximizes the (infinite horizon) expected long term
discounted reward [9]:

$\pi^{*}=\arg\max_{\pi}\mathbb{E}_{s_{0}\sim\mu(\cdot),a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim
p(\cdot|s_{t},a_{t})}\bigg{[}\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\bigg{]}=:J_{\mu}^{\pi}(r)$
(1)

Constrained reinforcement learning. Similarly, the objective of a standard
Constrained RL procedure is to obtain a policy that maximizes the (infinite
horizon) expected long term discounted reward while ensuring that the
expectation of cumulative constraint functions $c_{i}$ does not exceed
associated thresholds $\beta_{i}$:

$\pi^{*}=\arg\max_{\pi}J_{\mu}^{\pi}(r)\mbox{ such that
}J_{\mu}^{\pi}(c_{i})\leq\beta_{i}\forall i$ (2)

Inverse reinforcement learning. IRL performs the inverse operation of
reinforcement learning, that is, given access to a dataset
$\mathcal{D}=\\{\tau_{j}\\}_{j=1}^{N}=\\{\\{(s_{t},a_{t})\\}_{t=1}^{M_{j}}\\}_{j=1}^{N}$
sampled using an optimal or near optimal policy $\pi^{*}$, the goal is to
obtain a reward function $r$ that best explains the dataset. By “best
explanation”, we mean that if we perform the RL procedure using $r$, then the
obtained policy captures the behavior demonstrated in $\mathcal{D}$ as closely
as possible.

Inverse constraint learning. Given access to a dataset $\mathcal{D}$ (just
like in IRL), which is sampled using an optimal or near optimal policy
$\pi^{*}$ (respecting some constraints $c_{i}$ and maximizing some known
reward $r$), the goal is to obtain the constraint functions $c_{i}$ that best
explain the dataset, that is, if we perform the constrained RL procedure using
$r,c_{i}\forall i$, then the obtained policy captures the behaviour
demonstrated in $\mathcal{D}$. Similar to prior work [6], we learn only the
constraints, but not the reward function. Essentially, it is difficult to say
whether a demonstrated behaviour is obeying a constraint, or maximizing a
reward, or doing both. So, for simplicity, we assume the (nominal) reward is
given, and we just need to learn a constraint function. Without loss of
generality, we fix the threshold $\beta$ to a predetermined value and learn
only a constraint function $c$.111Mathematically equivalent constraints can be
obtained by multiplying the constraint function and the threshold by the same
value. Therefore there is no loss in fixing $\beta$ to learn a canonical
constraint within the set of equivalent constraints, assuming that the learned
constraint function can take arbitrary values. In this work however, we use a
constraint network with a sigmoid output, so that we can also interpret the
outputs as safeness values. Simultaneously learning multiple constraint
functions and the reward function is subject to future work.

##  3 Related Work

Several works in the inverse RL literature consider the framework of
constrained MDPs [10, 11, 12]. However, those works focus on learning the
reward function while assuming that the constraints are known. In contrast, we
focus on learning constraints while assuming that the reward function is
known.

Initial work in constraint learning focused on learning instantaneous
constraints with respect to states and actions. When states and actions are
discrete, constraint sets can be learned to distinguish feasible state-action
pairs from infeasible ones [3, 5, 13, 14]. In continuous domains, various
types of constraint functions are learned to infer the boundaries of
infeasible state-action pairs. This includes geometric state-space constraints
[15, 16], task space equality constraints [17, 18], convex constraints [19]
and parametric non-convex constraint functions [6, 7]. Several other works
learn local trajectory-based constraints with respect to a single trajectory
[20, 21, 22, 23, 24].

The vast majority of previous work considers hard constraints, which is fine
in deterministic domains. However, in stochastic domains, the probability of
violating a constraint can rarely be reduced to zero, making hard constraints
inadequate. To that effect, Glazier et al. [25] learns probabilistic
constraints that hold with high probability in expert demonstrations. This
approach extends the framework of maximum entropy inverse reinforcement
learning to learn a constraint value that is treated as a negative reward
added to the given reward function. Since the probability of a trajectory is
proportional to the exponential of the rewards, this has the effect of
reducing the probability of trajectories with high constraint values. Several
other works also extend the inverse entropy RL framework to learn constraints
that reduce some transition probabilities to 0 when a constraint is violated,
but this amounts to hard constraints again [5, 14, 13, 7]. In an other line of
work, Bayesian approaches [4, 26] have also been proposed to learn a
distribution over constraints due to the unidentifiability and uncertainty of
the true underlying constraints. With the exception of [26], existing
techniques that learn probabilistic constraints are restricted to discrete
states and actions. Furthermore, the probabilistic constraints that are
learned do not correspond to the soft constraints of constrained MDPs. Hence,
we fill this gap by proposing a first technique that learns soft cumulative
constraint functions bounded in expectations (as in constrained MDPs) for
stochastic domains with continuous states and actions.

##  4 Approach

###  4.1 Inverse Constraint Learning: Two Phases

Formulation. We propose a simple strategy to do ICL, that is, given a reward
$r$ and demonstrations $\mathcal{D}$, this strategy obtains a constraint
function $c$ such that when $r,c$ are used in the constrained RL procedure,
the obtained policy $\pi^{*}$ explains the behavior in $\mathcal{D}$. We first
describe a theoretical procedure that captures the essence of the approach and
then adapt it to a practical algorithm. The theoretical approach starts with
an empty set of policies (i.e., $\Pi=\emptyset$) and then alternates between
two optimization procedures until convergence (i.e., when the set $\Pi$ of
policies remains unchanged):

$\displaystyle\mbox{{Policy optimization}:
}\pi^{*}:=\arg\max_{\pi}J_{\mu}^{\pi}(r)\mbox{ such that
}J_{\mu}^{\pi}(c)\leq\beta\mbox{ and }\Pi\leftarrow\Pi\cup\\{\pi^{*}\\}$ (3)
$\displaystyle\mbox{{Constraint adjustment}:
}c^{*}:=\arg\max_{c}\min_{\pi\in\Pi}J_{\mu}^{\pi}(c)\mbox{ such that
}J_{\mu}^{\pi_{E}}(c)\leq\beta$ (4)

The optimization procedure in 3 is performing forward constrained RL to find
an optimal policy $\pi^{*}$ given a reward function $r$ and a constraint
function $c$. This optimal policy is added to $\Pi$. Then, the optimization
procedure in (4) is adjusting the constraint function $c$ to increase the
constraint values of the policies in $\Pi$ while keeping the constraint value
of the expert policy $\pi_{E}$ bounded by $\beta$. Hence at each iteration of
those two optimization procedures a new policy is found but its constraint
value will be increased past $\beta$ unless it corresponds to the expert
policy. By doing so, this approach will converge to the expert policy (or an
equivalent policy when multiple policies can generate the same trajectories).

###### Theorem 1

Assuming there is a unique policy $\pi^{E}$ that achieves
$J^{\pi^{E}}_{\mu}(r)$, the alternation of optimization procedures in (3) and
(4) converges to a set of policies $\Pi$ such that the last policy $\pi^{*}$
added to $\Pi$ is equivalent to the expert policy $\pi^{E}$ in the sense that
$\pi^{*}$ and $\pi^{E}$ generate the same trajectories.

The proof of Theorem 1 is provided in the supplementary material. In practice,
there are several challenges to implement the optimization procedures in (3)
and (4). First, we do not have the expert policy $\pi_{E}$, but rather
trajectories generated based on the expert policy. Also, the set $\Pi$ of
policies can grow to become very large before convergence is achieved.
Furthermore, convergence may not occur or may occur prematurely due to
numerical issues and whether the policy space contains the expert policy. The
optimization procedures include constraints and one of them requires min-max
optimization. We now describe various strategies to approximate the
theoretical approach in (3) and (4) into the practical approach described in
Algorithm 1.

As a first step, we replace the optimization procedure in (4) by a simpler
optimization described in (5). More precisely, we replace the max min
optimization of the constraint values of the policies in $\Pi$ by a
maximization of the constraint value of the mixture $\pi_{mix}$ of policies in
$\Pi$. This avoids a challenging max-min optimization, but we lose the
guarantee of convergence to a policy equivalent to the expert policy.
Nevertheless, maximizing the constraint values of a mixture of policies tends
to increase the constraint values for all policies most of the time, and when
a policy’s constraint value is not increased beyond $\beta$ it will usually be
a policy close to the expert policy. Hence, as we will demonstrate in the
experiments, the algorithm finds policies that are close to the expert policy
in terms of generated trajectories.

$c^{*}:=\arg\max J_{\mu}^{\pi_{mix}}(c)\mbox{ such that
}J_{\mu}^{\pi_{E}}(c)\leq\beta$ (5)

###  4.2 Deep Constraint Correction

Solving the constrained optimizations. The constrained optimization problems
(3), (4), (5), described in the preceding subsection belong to the following
general class of optimization problems ($f,g$ are potentially non-linear and
non-convex):

$\min_{y}f(y)\mbox{ such that }g(y)\leq 0$ (6)

While we could tackle them by turning the constraints into penalties
corresponding to the Lagrangian, the Lagrangian would introduce a challenging
min max optimization. Instead, Donti et al. [27] proposed to solve such
problems using a technique called DC3: deep constraint correction and
completion. We solve our constrained optimization formulation in a similar
way. In our case, we don’t need the completion step of the algorithm (see
[27]), since we do not have a constraint $h(y)=0$ associated with the
optimization. Hence, we use a simplified procedure that may be called deep
constraint correction (DC2). DC2 starts by instantiating $y=y_{0}$, and then
repeating two steps until convergence: (a) first a feasible solution is found
by repeatedly modifying $y$ in the direction of $-\nabla g(y)$ until $g(y)\leq
0$ (note that this is equivalent to $-\nabla ReLU(g(y)$), also called
correction, then (b) a soft loss is optimized that simultaneously minimizes
$f(y)$ while trying to keep $y$ within the feasible region. In this work, we
use a soft loss (this soft loss differs from the soft loss mentioned in Donti
et al. [27]), which yields the following objective for the second step
($\lambda$ is a hyperparameter):

$\min_{y}L_{\mbox{soft}}(y):=f(y)+\lambda\mbox{{ReLU}}(g(y))$ (7)

Choice of $\lambda$. The choice of $\lambda$ is crucial here. A small
$\lambda$ means that in the second step, the gradient of $\mbox{ReLU}(g(y))$
does not interfere with the optimization of $f(y)$, however, $y$ may not stay
feasible during the soft loss optimization, which is why the correction step
is even more important to ensure some notion of feasibility. Conversely, a
large $\lambda$ means that minimizing the soft loss is more likely to ensure
feasibility, and the correction step may be omitted. This is precisely what we
do for the proposed optimizations. Namely, we perform approximate forward
constrained RL ((3)) using $\lambda=0$ with the correction step, and
constraint adjustment ((4)/(5)) using a high $\lambda$ and without the
correction step.

###  4.3 Improving Constraint Adjustment

Out of distribution boundary. It can be argued that constraint adjustment
(equations (4), (5)) is essentially finding the decision boundary between
expert and non-expert trajectories. We can look at the soft loss objective
(considering (5)):

$\min_{c}L_{\mbox{soft}}(c):=-J_{\mu}^{\pi_{mix}}(c)+\lambda\mbox{{ReLU}}(J_{\mu}^{\pi_{E}}(c)-\beta)$

It is quite likely that during training, some of the agent behavior overlaps
with expert behavior. This means that some expert trajectories appear in the
first term $-J_{\mu}^{\pi_{mix}}(c)$. This is problematic if we wish to learn
the decision boundary between expert and non-expert trajectories, as we will
now argue.

Depending on whether $J_{\mu}^{\pi_{E}}(c)-\beta\leq 0$ or not, the ReLU term
vanishes in $L_{\mbox{soft}}(c)$.

Case I. If $J_{\mu}^{\pi_{E}}(c)-\beta\leq 0$, then $c$ is already feasible,
that is, for this value of $c$, the average constraint value across expert
trajectories is less than or equal to $\beta$. If there are expert (or expert-
like) trajectories in $-J_{\mu}^{\pi_{mix}}(c)$, then we will end up
increasing the constraint value across these expert trajectories, which is not
desirable since it will lead to $c$ becoming more infeasible.

Case II. If $J_{\mu}^{\pi_{E}}(c)-\beta>0$, then there is a nonzero ReLU term
in $L_{\mbox{soft}}(c)$. Given that there are some expert trajectories in
$-J_{\mu}^{\pi_{mix}}(c)$, if we take the gradient of $L_{\mbox{soft}}(c)$, we
will get two contrasting gradient terms trying to increase and decrease the
constraint value across these expert trajectories. The gradient update
associated with the ReLU term is more necessary since we want $c$ to become
feasible, but having expert trajectories in $-J_{\mu}^{\pi_{mix}}(c)$
diminishes the effect of the ReLU term and it takes more iterations to get a
feasible $c$.

In both cases, it is not a good idea to have expert or expert-like
trajectories in $-J_{\mu}^{\pi_{mix}}(c)$. To mitigate this, we propose two
reweightings: (a) we reweight the policies in $\pi_{mix}$ so that policies
dissimilar to the expert policy are favoured more in the calculation of
$-J_{\mu}^{\pi_{mix}}(c)$, and (b) we reweight the individual trajectories in
the expectation $-J_{\mu}^{\pi_{mix}}(c)$ to ensure that there is less or
negligible weight associated with the expert or expert-like trajectories. We
can perform both these reweightings using a density estimator. In this work,
we use a normalizing flow for this purpose, more specifically, we use the
RealNVP flow [28]. Our complete algorithm is provided in Algorithm 1.

Algorithm 1 Inverse Constraint Learning with Trajectory & Policy Reweighting

1:hyper-parameters: learning rates $\eta_{1},\eta_{2},\eta_{3}$, tolerance
$\epsilon$, penalty wt. $\lambda$, constraint threshold $\beta$

2:input: number of iterations $n$, constrained RL epochs $m$, constraint
adjustment epochs $e$,

3: expert dataset
$\mathcal{D}=\\{\tau\\}_{\tau\in\mathcal{D}}:=\\{\\{(s_{t},a_{t})\\}_{1\leq
t\leq|\tau|}\\}_{\tau\in\mathcal{D}}$

4:given: Sum$(\cdot)$, Mean$(\cdot)$, Std-Dev$(\cdot)$, ReLU$(\cdot)$, PPO-
Loss$(\cdot)$,

5: $c^{\gamma}(\tau):=\textsc{Sum}_{1\leq
t\leq|\tau|}(\gamma^{t-1}c(s_{t},a_{t}))$,

6: $\mbox{{Sample}}_{\tau}(\Pi,p)$ which generates $|\mathcal{D}|$
trajectories $\tau=\\{(s_{t},a_{t})\\}_{1\leq t\leq|\tau|}$, where for each

7: $\tau$, we choose $\pi\in\Pi$ with prob. $p(\pi)$, then,
$s_{1}\sim\mu(\cdot),a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim
p(\cdot|s_{t},a_{t})$

8:initialize normalizing flow $f$

9:optimize likelihood of $f$ on expert state action data:
$\max_{f}\mbox{{Sum}}_{(s,a)\in\tau,\tau\in\mathcal{D}}(\log p_{f}(s,a))$

10:$\mu_{E}:=\mbox{{Mean}}_{(s,a)\in\tau,\tau\in\mathcal{D}}(-\log
p_{f}(s,a))$

11:$\sigma_{E}:=\mbox{{Std-Dev}}_{(s,a)\in\tau,\tau\in\mathcal{D}}(-\log
p_{f}(s,a))$

12:$w(\tau):=\mbox{{Mean}}_{(s,a)\in\tau}(\mathbf{1}(-\log
p_{f}(s,a)>\mu_{E}+\sigma_{E}))$ $\triangleright$ trajectory dissimilarity
w.r.t. expert

13:initialize constraint function $c$ (parameterized by $\boldsymbol{\phi}$)

14:for $1\leq i\leq n$ do

15: initialize policy $\pi_{i}$ (parameterized by $\boldsymbol{\theta}_{i}$)

16: for $1\leq j\leq m$ do $\triangleright$ constrained reinforcement learning

17: correct $\pi_{i}$ to be feasible: (iterate)
$\boldsymbol{\theta}_{i}\leftarrow\boldsymbol{\theta}_{i}-\eta_{1}\nabla_{\boldsymbol{\theta}_{i}}\mbox{{ReLU}}(J_{\mu}^{\pi_{i}}(c)-\beta)$

18: optimize expected discounted reward:
$\boldsymbol{\theta}_{i}\leftarrow\boldsymbol{\theta}_{i}-\eta_{2}\nabla_{\boldsymbol{\theta}_{i}}\mbox{{PPO-
Loss}}(\pi_{i})$ $\triangleright$ PPO [29]

19: end for

20: construct policy dataset
$\mathcal{D}_{\pi_{i}}=\mbox{{Sample}}_{\tau}(\Pi=\\{\pi_{i}\\},p=\\{1\\})$

21: $\tilde{w}_{i}:=\mbox{{Mean}}_{\tau\in\mathcal{D}_{\pi_{i}}}w(\tau)$
$\triangleright$ unnormalized policy weights

22: construct agent dataset
$\mathcal{D}_{A}=\mbox{{Sample}}_{\tau}(\Pi=\pi_{1:i},p(\pi_{i})\propto\tilde{w}_{i})$
$\triangleright$ policy reweighting

23: for $1\leq j\leq e$ do $\triangleright$ constraint function adjustment

24: compute
$J_{\mu}^{\pi_{mix}}(c):=\mbox{{sum}}_{\tau\in\mathcal{D}_{A}}\frac{w(\tau)c^{\gamma}(\tau)}{\mbox{{Sum}}_{\tau\in\mathcal{D}_{A}}w(\tau)}$
$\triangleright$ trajectory reweighting

25: compute
$J_{\mu}^{\pi_{E}}(c):=\mbox{{Mean}}_{\tau\in\mathcal{D}}(c^{\gamma}(\tau))$

26: compute soft loss
$L_{\mbox{soft}}(c):=-J_{\mu}^{\pi_{mix}}(c)+\lambda\mbox{{ReLU}}(J_{\mu}^{\pi_{E}}(c)-\beta)$

27: optimize constraint function $c$:
$\boldsymbol{\phi}\leftarrow\boldsymbol{\phi}-\eta_{3}\nabla_{\boldsymbol{\phi}}L_{\mbox{soft}}(c)$

28: end for

29: if $\mbox{{Normalized-Accrual-
Dissimilarity}}(\mathcal{D},\mathcal{D}_{\pi_{i}})\leq\epsilon$ then

30: convergence: may exit early

31: end if

32:end for

33:output: learned constrained function $c$, learned most recent policy
$\pi_{i}$

##  5 Experiments

We conduct several experiments to assess the constraint function recovered by
our algorithm. We conduct the experiments on the following environments:

  * •

Gridworld (A, B) are 7x7 gridworld environments (adapted from yrlu’s
repository [30]). The start states, true constraint function and the goal
state are indicated in Figure 1. The action space consists of 8 discrete
actions including 4 nominal directions and 4 diagonal directions.

  * •

CartPole (MR, Mid) (MR means Move Right) are variants of CartPole environment
from OpenAI Gym [31] where the objective is to balance a pole for as long as
possible (maximum episode length is 200). The start regions and the true
constraint function are indicated in Figure 1. Both variants may start in a
region of high constraint value, and the objective is to move to a region of
low constraint value and balance the pole there, while the constraint function
is being learned.

  * •

HighD dataset: We construct an environment using $\approx 100$ trajectories of
length $\leq 1000$ from the HighD highway driving dataset [32] (see Figure 2).
The environment is adapted from the Wise-Move framework [33]. For each
trajectory, the agent starts on a straight road on the left side of the
highway, and the objective is to reach the right side of the highway without
colliding into any longitudinally moving cars. The action space consists of a
single continuous action, i.e. the acceleration. Note that for this
environment, we do not have the true constraint function. Instead, we aim to
learn a constraint function that is able to capture the relationship between
agent’s velocity and the distance to car in the front.

We use the following two baselines to compare against our method:

  * •

GAIL-Constraint: Generative adversarial imitation learning [34] is an
imitation learning method that can be used to learn a policy that mimics the
expert policy. The discriminator can be considered as a local reward function
that incentivizes the agent to mimic the expert. We assume that the agent is
maximizing the reward $r(s,a):=r_{0}(s,a)+\log(1-c(s,a))$ where $r_{0}$ is the
given true reward, and then the log term corresponds to the GAIL’s
discriminator. Note that when $c(s,a)=0$, the discriminator reward is $0$, and
when $c(s,a)=1$, the discriminator reward tends to $-\infty$.

  * •

Inverse constrained reinforcement learning (ICRL) [7] is a recent method that
is able to learn arbitrary Markovian neural network constraint functions,
however, it can only handle hard constraints.

For both these methods, we use a similar training regime as adopted by Malik
et. al [7], however, we try to keep the constraint function architecture fixed
across all experiments (baselines and our method). The hyperparameter
configuration can be found in the appendix.

Note that we did not include the method in Scobee and Sastry [5] as it is
unable to handle continuous state spaces. Similarly, we did not include the
binary constraint (BC) method described in Malik et al. [7] as GC and ICRL
empirically perform better than BC, according to their experiments.

Next, we define two metrics for our experiments.

  * •

Constraint Mean Squared Error (CMSE) is computed as the mean squared error
between the true constraint function and the recovered constraint function on
a uniformly discretized state-action space for the respective environment.

  * •

Normalized Accrual Dissimilarity (NAD) is computed as follows. Given the
policy learned by the method, we compute an agent dataset of trajectories.
Then, the accrual (state-action visitation frequency) is computed for both the
agent dataset and the expert dataset over a uniformly discretized state-action
space, which is the same as the one used for CMSE. Finally, the accruals are
normalized to sum to $1$, and the Wasserstein distance (using the Python
Optimal Transport library [35]) is computed between the accruals.

Gridworld (A)

Gridworld (B)

CartPole (MR)

CartPole (Mid)

Figure 1: Environments used in the experiments. White regions indicate
constraint value of 1. Yellow regions correspond to start states. Green
regions correspond to the goal state.

Figure 2: HighD driving dataset environment. Leftmost white region indicates
start region and rightmost white region indicates end region. Ego car is in
blue, other cars are in red.

Our results are reported in Table 2 and 2. The average recovered constraint
functions and accruals are provided in the appendix. For the highway dataset,
our results are reported in Figure 3. The hyperparameter configuration and
training strategy is elaborated in the appendix.

Table 1: Constraint Mean Squared Error

Algorithm$\downarrow$, Environment$\rightarrow$ | Gridworld (A) | Gridworld (B) | CartPole (MR) | CartPole (Mid)
---|---|---|---|---
GAIL-Constraint | 0.31 ± 0.01 | 0.25 ± 0.01 | 0.12 ± 0.03 | 0.25 ± 0.02
ICRL | 0.11 ± 0.02 | 0.21 ± 0.04 | 0.21 ± 0.16 | 0.27 ± 0.03
ICL (ours) | 0.08 ± 0.01 | 0.04 ± 0.01 | 0.02 ± 0.00 | 0.08 ± 0.05

Table 2: Normalized Accrual Dissimilarity

Algorithm$\downarrow$, Environment$\rightarrow$ | Gridworld (A) | Gridworld (B) | CartPole (MR) | CartPole (Mid)
---|---|---|---|---
GAIL-Constraint | 1.76 ± 0.25 | 1.29 ± 0.07 | 1.80 ± 0.24 | 7.23 ± 3.88
ICRL | 1.73 ± 0.47 | 2.15 ± 0.92 | 12.32 ± 0.48 | 13.21 ± 1.81
ICL (ours) | 0.36 ± 0.10 | 1.26 ± 0.62 | 1.63 ± 0.89 | 3.04 ± 1.93

Reported metrics (Mean $\pm$ Std. Deviation across 5 seeds) for the conducted
experiments.

GAIL-Constraint

ICRL

ICL ($\beta=0.1$) (ours)

Figure 3: Constraint functions (averaged across 5 seeds) recovered for the
HighD highway driving dataset. X-axis is the agent velocity $v$ (m/s), Y-axis
is the gap to the vehicle (center-to-center distance) in front $g$ (m). Red
points are (discretized) binary expert accruals.

###  5.1 Discussion

Lowest CMSE. While our method is not guaranteed to produce the true constraint
function (constraints are typically unidentifiable), we find that in our
experiments, our method is able to learn constraint functions that strongly
resemble the true constraint function, as can be seen by our low CMSE scores.
GAIL-Constraint method is able to find the correct constraint function for all
environments except CartPole-Mid, however, the recovered constraint is more
diffused throughout the state action space (see appendix). In contrast, our
recovered constraint is pretty sharp, even without a regularizer. Since
CartPole-Mid is a difficult constraint in comparison to the other constraints,
this result seems acceptable. On the other hand, the ICRL method is able to
find the correct constraint function only for CartPole-MR and to a less
acceptable degree for Gridworld A. This is surprising as ICRL should be able
to theoretically learn any arbitrary constraint function (note that we used
the settings in Malik et al. [7] as much as possible), and we expect it to
perform better than GAIL-Constraint. Our justification for this is two-fold.
One, the authors of ICRL have only considered simple constraints in their work
to demonstrate ICRL, and for more complex settings (constraints or
environments), ICRL may not be able to perform as well. Second, ICRL may
require more careful hyperparameter tuning for each constraint function
setting, even with the same environment, depending on the constraint. This is
ascertained by the fact that with the same hyperparameter settings, ICRL works
for CartPole-MR, but not for CartPole-Mid. For the interested reader, we
provide plots of the actual constraint function learned for all the methods,
for the 4 environments (averaged across 5 seeds) in the appendix.

Lowest NAD. Similarly, we find a strong resemblance between the accruals
recovered by our method and the expert, as can be seen by our low NAD scores.
As expected, our accruals are pretty similar to the expert accruals, which is
due to the fact that we are able to learn the true constraint function to a
better degree than other methods. GAIL-Constraint accruals are similar to the
expert accruals except for CartPole-Mid environment, where it is also unable
to learn the correct constraint function. Overall, this indicates that GAIL is
able to correctly imitate the constrained expert across most environments, as
one would expect. On the other hand, ICRL accruals are even worse than GAIL,
indicating that it is unable to satisfactorily imitate the constrained expert,
even on the environments for which it is able to generate a somewhat
satisfactory constraint function. Again, this may indicate that we need more
careful hyperparameter tuning, unlike our method, where we only tuned $\beta$.
For the interested reader, we provide plots of the accruals for the 4
environments (averaged across 5 seeds) in the appendix.

HighD driving dataset results. We report the results for the HighD driving
dataset [32] in Figure 3.Overall, all the methods are able to find the lower
boundary that corresponds to a 3-4.5 second gap. Ideally, we expect this gap
to be 2-3 seconds, but since the distances are computed center-to-center,
hence the gap time is larger. More specifically, at $v=20m/s=72km/h$, the gap
is roughly between 60-80 m (equivalently, 3-4 seconds) for all methods, while
close to $v=40m/s=144km/h$, the gap is between 125-150 m (equivalently
$\approx$3-4 seconds) for our method, and 160-180 m (equivalently 4-4.5
seconds) for GAIL-Constraint/ICRL. However, our method is the only one which
doesn’t assign high constraint value to large gaps. The possible justification
for this is that the other methods are unable to explicitly ensure that expert
trajectories are assigned low constraint value, while our method is able to do
so through the constraint value adjustment step. Moreover, our method has
fewer accrual points in the white (high constraint value) region compared to
the baselines.

##  6 Conclusion

This paper introduces a new technique to learn constraints from expert
demonstrations. While several techniques have been proposed to learn
constraints in stochastic domains, they adapt the maximum entropy inverse RL
framework to constraint learning [5, 14, 13, 25, 7]. We propose the first
approach that can recover soft cumulative constraints common in constrained
MDPs with continuous states and actions. We discuss the limitations of our
work below and provide some directions for future work.

Known reward function and single constraint function. The proposed technique
assumes that the reward function is known and can learn a single constraint
function. The challenge with simultaneously learning the reward function as
well as multiple constraints is that there will likely be many equivalent
configurations of reward and constraint functions that can generate the same
trajectories. Nevertheless, this is already a problem in traditional inverse
RL [1] since multiple reward functions can explain the expert demonstrations.
We would now need a way to give preference to specific combinations of reward
and constraint functions.

Training time. While the approach empirically produces a constraint function
that closely resembles the true constraint function, it requires multiple
iterations (empirically, this is typically $\leq 10$) of forward CRL and
constraint adjustment, and as a result, it needs overall more training time
than the existing baselines. The training time is simply due to the nature of
our algorithm, and its structure which involves repeating and completing two
alternating constrained optimization procedures. Trajectory and policy
reweighting are able to somewhat improve the convergence speed as discussed in
Section 4.3.

Probabilistic constraints. It may be more desirable to express constraints not
through expectations, but through probabilistic notions, eg. a cumulative soft
constraint which holds (i.e., is $\leq\beta$) with probability $p$. A possible
way to incorporate such constraints would be to learn a distributional value
for the constraint function and change the constraint adjustment step to
ensure that the probability that the constraint holds is within $p$. We leave
this for future work.

###  6.1 Societal Impact

Positive impact. This approach learns constraints from a given set of
demonstrations, which can then be used to deploy RL systems that perform CRL
using these constraints. This will reduce the guesswork needed to design
complex utility functions and accelerate the real world deployment of RL based
systems (eg. for autonomous driving).

Negative impact. If we deploy a safety-critical real world system using
constraints learned from this method, and the constraints learned are not
accurate enough (in fact, we may learn a different constraint function than
the true constraint function), we might see undesirable behaviors for edge
cases. Further, since this approach produces neural network based constraints,
it may be hard to inspect such constraints and therefore it may reduce
interpretability of the entire system. This might reduce public confidence in
AI systems.

###  6.2 Acknowledgements

Resources used in preparing this research at the University of Waterloo were
provided by Huawei Canada, the province of Ontario and the government of
Canada through CIFAR and companies sponsoring the Vector Institute.

## References

  * [1] Andrew Y Ng, Stuart J Russell, et al.  Algorithms for inverse reinforcement learning.  In Icml, volume 1, page 2, 2000.
  * [2] Stuart Russell.  Learning agents for uncertain environments.  In Proceedings of the eleventh annual conference on Computational learning theory, pages 101–103, 1998.
  * [3] Glen Chou, Dmitry Berenson, and Necmiye Ozay.  Learning constraints from demonstrations.  In International Workshop on the Algorithmic Foundations of Robotics, pages 228–245. Springer, 2018.
  * [4] Glen Chou, Dmitry Berenson, and Necmiye Ozay.  Uncertainty-aware constraint learning for adaptive safe motion planning from demonstrations.  In Conference on Robot Learning, pages 1612–1639. PMLR, 2021.
  * [5] Dexter RR Scobee and S Shankar Sastry.  Maximum likelihood constraint inference for inverse reinforcement learning.  In International Conference on Learning Representations, 2019.
  * [6] Glen Chou, Necmiye Ozay, and Dmitry Berenson.  Learning parametric constraints in high dimensions from demonstrations.  In Conference on Robot Learning, pages 1211–1230. PMLR, 2020.
  * [7] Shehryar Malik, Usman Anwar, Alireza Aghasi, and Ali Ahmed.  Inverse constrained reinforcement learning.  In International Conference on Machine Learning, pages 7390–7399. PMLR, 2021.
  * [8] Eitan Altman.  Constrained Markov decision processes: stochastic modeling.  Routledge, 1999.
  * [9] Richard S Sutton and Andrew G Barto.  Reinforcement learning: An introduction.  MIT press, 2018.
  * [10] Gabriel Kalweit, Maria Huegle, Moritz Werling, and Joschka Boedecker.  Deep inverse q-learning with constraints.  Advances in Neural Information Processing Systems, 33, 2020.
  * [11] Johannes Fischer, Christoph Eyberg, Moritz Werling, and Martin Lauer.  Sampling-based inverse reinforcement learning algorithms with safety constraints.  In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 791–798, 2021.
  * [12] Fan Ding and Yeiang Xue.  X-men: Guaranteed xor-maximum entropy constrained inverse reinforcement learning, 2022.
  * [13] David L McPherson, Kaylene C Stocking, and S Shankar Sastry.  Maximum likelihood constraint inference from stochastic demonstrations.  In 2021 IEEE Conference on Control Technology and Applications (CCTA), pages 1208–1213. IEEE, 2021.
  * [14] Daehyung Park, Michael Noseworthy, Rohan Paul, Subhro Roy, and Nicholas Roy.  Inferring task goals and constraints using bayesian nonparametric inverse reinforcement learning.  In Leslie Pack Kaelbling, Danica Kragic, and Komei Sugiura, editors, Proceedings of the Conference on Robot Learning, volume 100 of Proceedings of Machine Learning Research, pages 1005–1014. PMLR, 30 Oct–01 Nov 2020.
  * [15] Leopoldo Armesto, Jorren Bosga, Vladimir Ivan, and Sethu Vijayakumar.  Efficient learning of constraints and generic null space policies.  In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 1520–1526. IEEE, 2017.
  * [16] Claudia Pérez-D’Arpino and Julie A Shah.  C-learn: Learning geometric constraints from demonstrations for multi-step manipulation in shared autonomy.  In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 4058–4065. IEEE, 2017.
  * [17] Hsiu-Chin Lin, Matthew Howard, and Sethu Vijayakumar.  Learning null space projections.  In 2015 IEEE International Conference on Robotics and Automation (ICRA), pages 2613–2619. IEEE, 2015.
  * [18] Hsiu-Chin Lin, Prabhakar Ray, and Matthew Howard.  Learning task constraints in operational space formulation.  In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 309–315. IEEE, 2017.
  * [19] Marcel Menner, Peter Worsnop, and Melanie N. Zeilinger.  Constrained inverse optimal control with application to a human manipulation task.  IEEE Transactions on Control Systems Technology, 29(2):826–834, 2021.
  * [20] Sylvain Calinon and Aude Billard.  A probabilistic programming by demonstration framework handling constraints in joint space and task space.  In 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 367–372, 2008.
  * [21] Lucia Pais, Keisuke Umezawa, Yoshihiko Nakamura, and Aude Billard.  Learning robot skills through motion segmentation and constraints extraction.  In HRI Workshop on Collaborative Manipulation, page 5. Citeseer, 2013.
  * [22] Changshuo Li and Dmitry Berenson.  Learning object orientation constraints and guiding constraints for narrow passages from one demonstration.  In International symposium on experimental robotics, pages 197–210. Springer, 2016.
  * [23] Negar Mehr, Roberto Horowitz, and Anca D Dragan.  Inferring and assisting with constraints in shared autonomy.  In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 6689–6696. IEEE, 2016.
  * [24] Gu Ye and Ron Alterovitz.  Demonstration-Guided Motion Planning, pages 291–307.  Springer International Publishing, Cham, 2017.
  * [25] Arie Glazier, Andrea Loreggia, Nicholas Mattei, Taher Rahgooy, Francesca Rossi, and K Brent Venable.  Making human-like trade-offs in constrained environments by learning from demonstrations.  arXiv preprint arXiv:2109.11018, 2021.
  * [26] Dimitris Papadimitriou, Usman Anwar, and Daniel S Brown.  Bayesian inverse constrained reinforcement learning.  In Workshop on Safe and Robust Control of Uncertain Systems (NeurIPS), 2021.
  * [27] Priya L Donti, David Rolnick, and J Zico Kolter.  Dc3: A learning method for optimization with hard constraints.  In International Conference on Learning Representations, 2020.
  * [28] Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio.  Density estimation using real nvp.  arXiv preprint arXiv:1605.08803, 2016.
  * [29] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  arXiv preprint arXiv:1707.06347, 2017.
  * [30] Yiren Lu.  Irl-imitation.  https://github.com/yrlu/irl-imitation, 2019.
  * [31] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  Openai gym, 2016.
  * [32] Robert Krajewski, Julian Bock, Laurent Kloeker, and Lutz Eckstein.  The highd dataset: A drone dataset of naturalistic vehicle trajectories on german highways for validation of highly automated driving systems.  In 2018 21st International Conference on Intelligent Transportation Systems (ITSC), pages 2118–2125, 2018.
  * [33] Jaeyoung Lee, Aravind Balakrishnan, Ashish Gaurav, Krzysztof Czarnecki, and Sean Sedwards.  W ise m ove: A framework to investigate safe deep reinforcement learning for autonomous driving.  In International Conference on Quantitative Evaluation of Systems, pages 350–354. Springer, 2019.
  * [34] Jonathan Ho and Stefano Ermon.  Generative adversarial imitation learning.  Advances in neural information processing systems, 29, 2016.
  * [35] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer.  Pot: Python optimal transport.  Journal of Machine Learning Research, 22(78):1–8, 2021.

## Appendix

##  1 Proof of Theorem 1

We give a proof by contradiction under 3 assumptions. The 3 assumptions are:

  1. (i)

The reward function is non-negative.

  2. (ii)

The space of policies is finite.

  3. (iii)

There is a unique policy $\pi^{E}$ that achieves $J^{\pi^{E}}_{\mu}(r)$. In
other words no other policy achieves the same expected cumulative reward as
$\pi^{E}$.

Note that the first assumption is not restrictive since we can always shift a
reward function by adding a sufficiently positive constant to the reward of
all state-action pairs such that the new reward function is always non-
negative. This new reward function is equivalent to the original one since it
does not change the value ordering of policies.

We argue that the second assumption is reasonable in practice. Even if we
consider what appears to be a continuous policy space because the
parameterization of the policy space is continuous, in practice, parameters
have a finite precision and therefore the space of policies is necessarily
finite (albeit possibly very large).

Based on assumption (ii), it should be clear that the alternation of the
optimization procedures in (3) and (4) will converge to a fixed point. Since
there are finitely many policies, and we add a new policy to $\Pi$ at each
iteration (until we reach the fixed point), in the worst case, the alternation
will terminate once all policies have been added to $\Pi$.

When the algorithm converges to a fixed point, let $\pi^{*}$ be the optimal
policy found by policy optimization in (3) and $c^{*}$ be the optimal
constraint function found by constraint adjustment in (4). According to (3),
we know that $J^{\pi^{*}}_{\mu}(c^{*})\leq\beta$. Similarly, we show that the
objective in (4) is less than or equal to $\beta$:

$\displaystyle\max_{c}\min_{\pi\in\Pi}J^{\pi}_{\mu}(c)\mbox{ subject to
}J^{\pi^{E}}_{\mu}(c)\leq\beta$ (8)
$\displaystyle=\min_{\pi\in\Pi}J^{\pi}_{\mu}(c^{*})$ since $c^{*}$ is the
optimal solution of (4) (9) $\displaystyle\leq\beta$ since $\pi^{*}\in\Pi$ and
$J^{\pi^{*}}_{\mu}(c^{*})\leq\beta$ (10)

Next, if we assume that $\pi^{*}$ is not equivalent to $\pi^{E}$, then we can
show that the objective in (4) is greater than $\beta$.

$\displaystyle\max_{c}\min_{\pi\in\Pi}J^{\pi}_{\mu}(c)\mbox{ such that
}J^{\pi^{E}}_{\mu}(c)\leq\beta$ (11)
$\displaystyle\geq\min_{\pi\in\Pi}J^{\pi}_{\mu}(\hat{c})$
$\displaystyle\mbox{where we choose
}\hat{c}(s,a)=\frac{r(s,a)\beta}{J^{\pi^{E}}_{\mu}(r)}$ (12)
$\displaystyle=\min_{\pi\in\Pi}J^{\pi}_{\mu}(r)\beta/J^{\pi^{E}}_{\mu}(r)$ by
substituting $\hat{c}$ by its definition (13)
$\displaystyle>J^{\pi^{E}}_{\mu}(r)\beta/J^{\pi^{E}}_{\mu}(r)=\beta$ since
$J^{\pi}_{\mu}(r)\geq J^{\pi^{E}}_{\mu}(r)\;\forall\pi\in\Pi$ according to (3)
and $J^{\pi}_{\mu}(r)\neq J^{\pi^{E}}_{\mu}(r)$ by assumption (iii) (14)

The key step in the above derivation is Equation 12, where we choose a
specific constraint function $\hat{c}$. Intuitively, this constraint function
is selected to be parallel to the reward function while making sure that
$J^{\pi^{E}}_{\mu}(c)\leq\beta$. We know that all policies in $\Pi$ achieve
higher expected cumulative rewards than $\pi^{E}$. This follows from the fact
that the optimization procedure in (3) finds an optimal policy $\pi^{*}$ at
each iteration and this optimal policy is not equivalent to $\pi^{E}$ based on
our earlier assumption. So the policies in $\Pi$ must earn higher expected
cumulative rewards than $\pi^{E}$. So if we select a constraint function
parallel to the reward function then the policies in $\Pi$ will have
constraint values greater than the constraint value of $\pi^{E}$ and therefore
they should be ruled out in the constrained policy optimization (3).

Since the inequalities 8-10 contradict the inequalities 11-14, we conclude
that $\pi^{*}$ must be equivalent to $\pi^{E}$.

##  2 Additional Discussion

###  2.1 Constrained PPO

For our forward constrained RL step, we use a modification of the PPO
algorithm [29] that approximately ensures constraint feasibility. This
modification is based on the DC2 algorithm mentioned in Section 4.2. This
modified PPO works in two steps. First, we change the policy to ensure
constraint feasibility. Then, we change the policy to optimize the PPO
objective. If the policy $\pi$ is parameterized by $\boldsymbol{\theta}$, then
these two steps are:

$\displaystyle\mbox{{Correction}:}\,\,\,\boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\eta_{1}\nabla_{\boldsymbol{\theta}}\mbox{{ReLU}}(J_{\mu}^{\pi}(c)-\beta)$
$\displaystyle\mbox{{PPO
Update}:}\,\,\,\boldsymbol{\theta}\leftarrow\boldsymbol{\theta}-\eta_{2}\nabla_{\boldsymbol{\theta}}\mbox{{PPO-
Loss}}(\pi)$

The gradient for the correction step can be computed just like policy
gradient:

$\displaystyle
G_{t_{0}}(c):=\sum_{t=t_{0}}^{\infty}\gamma^{t-t_{0}}c(s_{t},a_{t})$ (15)
$\displaystyle\nabla_{\boldsymbol{\theta}}J_{\mu}^{\pi}(c)=E_{s_{0}\sim\mu,a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim
p(\cdot|s_{t},a_{t})}\bigg{[}\sum_{t=0}^{\infty}G_{t}(c)\nabla_{\boldsymbol{\theta}}\log\pi(a_{t}|s_{t})\bigg{]}$
(16)
$\displaystyle\nabla_{\boldsymbol{\theta}}\mbox{{ReLU}}(J_{\mu}^{\pi}(c)-\beta)=\mathbf{I}(J_{\mu}^{\pi}(c)>\beta)\nabla_{\boldsymbol{\theta}}J_{\mu}^{\pi}(c)$
(17)

The PPO-Loss($\pi$) term is computed over a minibatch as follows (note that
$A(s_{t},a_{t})$ is an advantage estimate). This is the same as the original
paper [29], except for an entropy term.

$\displaystyle
r_{t}:=\frac{\pi(a_{t}|s_{t};{\boldsymbol{\theta}})}{\pi(a_{t}|s_{t};{\boldsymbol{\theta}_{old}})}$
(18) $\displaystyle\mbox{{PPO-
Loss}}(\pi):=-\mathbb{E}_{t}\bigg{[}\min(r_{t},\mbox{clip}(r_{t},1-\epsilon_{PPO},1+\epsilon_{PPO}))A(s_{t},a_{t})\bigg{]}-\lambda_{ent}H(\pi)$
(19)

This gradient can be computed through automatic differentiation.

Overall, we do not have a ReLU term in the PPO update, since its gradient
would interfere with the PPO update and cause difficulty in learning. Instead,
the correction step tries to ensure feasibility of the solution before every
PPO update. While this doesn’t guarantee that feasibility will hold during and
after the PPO update, we see empirically that feasibility approximately holds.

The correction step is comparable to a projection step, since it projects the
solution into the feasibility region, although not necessarily the closest
feasible point.

Our results are reported in Figures 4, 5.

Gridworld (A)
($\beta=0.99$)

Gridworld (B)
($\beta=0.99$)

CartPole (MR)
($\beta=50$)

CartPole (Mid)
($\beta=30$)

Figure 4: Avg reward per PPO epoch for the expert (1 seed). As seen, the
modified PPO is able to learn a good policy that achieves a high reward.

Gridworld (A)
($\beta=0.99$)

Gridworld (B)
($\beta=0.99$)

CartPole (MR)
($\beta=50$)

CartPole (Mid)
($\beta=30$)

Figure 5: Avg constraint violations per PPO epoch for the expert (1 seed). As
seen, the modified PPO is able to learn a good policy that reduces the
constraint violations as the training progresses.

###  2.2 Ablation: Effect of Policy Mixture and Reweighting

To assess the effect of having a policy mixture and reweighting, we conduct
experiments with two more variants of ICL on all the synthetic environments:

  * •

ICL wihout a mixture policy or reweighting (use the policy learned in
constrained RL step instead of $\pi_{mix}$ to do constraint adjustment step)

  * •

ICL with a mixture policy but with no reweighting (use uniform weights)

Our results are reported in Figure 6. We find that ICL without a mixture
policy or reweighting is unable to perform as well as other methods with
Gridworld (A) environment. Empirically, it is prone to divergence and cyclic
behavior. This divergent behavior can be observed in the Gridworld (A) case.
ICL with a mixture policy but with no reweighting is unable to converge as
fast as ICL with mixture policy and reweighting in the Gridworld (B) and
CartPole (Mid) environments. For the CartPole (MR) environment, all the
methods converge fairly quickly and have almost the same performance. We also
note that there is significant variance in the result for ICL on the CartPole
(Mid) environment. Despite this, overall, ICL with a mixture policy and
reweighting performs better than the other variants (or close to the best).
Thus, we report this variant (with mixture policy and reweighting) in our
tables 2 and 2.

Gridworld (A)
($\beta=0.99$)

Gridworld (B)
($\beta=0.99$)

CartPole (MR)
($\beta=50$)

CartPole (Mid)
($\beta=30$)

Figure 6: CMSE (Y-axis) vs ICL Iteration $i$ (X-axis). In each iteration, we
do one complete procedure of constrained RL and one complete procedure of
constraint function adjustment.

###  2.3 Effect of Constraint Threshold $\beta$

We also assess the effect of $\beta$ with the Gridworld (A, B) environments.
We do not assess the effect of $\beta$ on the CartPole (MR, Mid) environments
since our claim can be easily verified by just observing the learned costs for
the Gridworld (A, B) environments. Our claim is as follows. With a higher
$\beta$, the learned constraint function should have a higher CMSE and more
state-action pairs with higher constraint values. This is because since
$\beta$ is higher, the agent is allowed to visit more high constraint value
state-action pairs, as the constraint threshold is more relaxed. To verify
this claim, we run experiments on the Gridworld (A, B) environments.
Specifically, in addition to $\beta=0.99$ (which corresponds to the results in
Tables 2 and 2), we also run experiments with $\beta=2.99,5.99$. Our results
are reported in Figures 7, 8. From the figures, it is apparent that our claim
is correct.

True constraint
function

ICL
($\beta=0.99$)

ICL
($\beta=2.99$)

ICL
($\beta=5.99$)

Figure 7: Average constraint function value (averaged across 5 training seeds)
for Gridworld (A) environment, demonstrating the effect of changing $\beta$.

True constraint
function

ICL
($\beta=0.99$)

ICL
($\beta=2.99$)

ICL
($\beta=5.99$)

Figure 8: Average constraint function value (averaged across 5 training seeds)
for Gridworld (B) environment, demonstrating the effect of changing $\beta$.

##  3 Training Setup

All PPO variants mentioned in this paper are single-process for simplicity.
For the tables, we abbreviate the Gridworld (A, B), CartPole (MR, Mid)
environments as GA, GB, CMR, CMid.

###  3.1 Common Hyperparameters

Hyperparameters common to all the experiments are listed in Table 3.

Table 3: Common Hyperparameters

Hyperparameter | Value(s)
---|---
PPO learning rate ($\eta_{2}$) | $5\times 10^{-4}$
Constraint function learning rate ($\eta_{3}$) | $5\times 10^{-4}$
Constraint function hidden layers | 64+ReLU, 64+ReLU
Constraint function final activation | Sigmoid
PPO policy layers | 64+ReLU, 64+ReLU
PPO value fn. layers | 64+ReLU, 64+ReLU
Minibatch size | 64
PPO clip parameter ($\epsilon_{PPO}$) | 0.1
PPO entropy coefficient ($\lambda_{ent}$) | 0.01
PPO updates per epoch | 25
No. of trajectories for any dataset | 50
Training seeds | 1, 2, 3, 4, 5

Since HighD is a continuous action space environment, we use Tanh activation
for the policy, which outputs the mean and std. deviation of a learned
Gaussian action distribution.

The inputs to the constraint functions are as follows:

  * •

Gridworld (A, B): $x,y$ coordinates of the agent’s position in the 7x7 grid

  * •

CartPole (MR, Mid): $x$ position of the cart, and the discrete action (0/1
corresponding to left or right)

  * •

HighD: velocity ($m/s$) of the ego, and the distance of the ego to the front
vehicle in pixels (1 pixel $\approx$ 2.5 $m$)

The environment maximum horizons (episodes are terminated after these many
steps) are as follows:

  * •

Gridworld (A, B): 50 steps

  * •

CartPole (MR, Mid): 200 steps

  * •

HighD: 1000 steps

###  3.2 GAIL-Constraint

Hyperparameters specific to the GAIL-Constraint method are listed in Table 4.
This method was adapted from Malik et al. [7] and they performed 1M timesteps
of training on all environments. To be sure that this method performs as
expected, we did 2M timesteps of training (except for the HighD environment
where we do 0.4M timesteps of training, since it was computationally expensive
to simulate).

Table 4: GAIL-Constraint Hyperparameters

Hyperparameter | Value(s)
---|---
GA | GB | CMR | CMid | HighD
Discount factor ($\gamma$) | 1.0 | 1.0 | 0.99 | 0.99 | 0.99
PPO steps per epoch | 2000 | 2000 | 2000 | 2000 | 2000
PPO value fn. loss coefficient | 0.5 | 0.5 | 0.5 | 0.5 | 0.5
PPO gradient clip value | 0.5 | 0.5 | 0.5 | 0.5 | 0.5
PPO total steps | 2M | 2M | 2M | 2M | 0.4M

###  3.3 ICRL

Similar to GAIL-Constraint, we performed 2M timesteps of training on all
environments except HighD, where we performed 0.4M timesteps of training.
Hyperparameters are listed in Table 5. ICRL did not perform as expected on two
out of the four environments, that is, Gridworld (B) and the CartPole (Mid)
environments, and may require further environment specific hyperparameter
tuning. Nevertheless, we use these parameters since they (somewhat) worked on
Gridworld (A) and CartPole (MR) environments. Note that for a fair comparison,
we tried to ensure that for some of the parameters, we use the same value as
our method, ICL (these parameters are number of rollouts, batch size, learning
rate, $\gamma$, constraint function architecture etc.).

Table 5: ICRL Hyperparameters

Hyperparameter | Value(s)
---|---
GA | GB | CMR | CMid | HighD
Discount factor ($\gamma$) | 1.0 | 1.0 | 0.99 | 0.99 | 0.99
PPO steps per epoch | 2000 | 2000 | 2000 | 2000 | 2000
PPO value fn. loss coefficient | 0.5 | 0.5 | 0.5 | 0.5 | 0.5
Cost value fn. loss coefficient | 0.5 | 0.5 | 0.5 | 0.5 | 0.5
PPO gradient clip value | 0.5 | 0.5 | 0.5 | 0.5 | 0.5
Eval episodes | 100 | 100 | 100 | 100 | 100
ICRL Iterations | 200 | 200 | 200 | 200 | 40
Forward PPO timesteps | 10000 | 10000 | 10000 | 10000 | 10000
PPO Budget | 0 | 0 | 0 | 0 | 0
Penalty initial value ($\nu$) | 0.1 | 0.1 | 0.1 | 0.1 | 0.1
Penalty learning rate | 0.01 | 0.01 | 0.01 | 0.01 | 0.01
Per step importance sampling | Yes | Yes | Yes | Yes | Yes
Forward KL (Old/New) | 10 | 10 | 10 | 10 | 10
Backward KL (New/Old) | 2.5 | 2.5 | 2.5 | 2.5 | 2.5
Backward iterations | 5 | 5 | 5 | 5 | 5
Constraint network reg. coefficient | 0.6 | 0.6 | 0.6 | 0.6 | 0.6

###  3.4 ICL (Our method)

The hyperparameters for our method are listed in Table 6. Our PPO
implementation differs from the baselines (the baseline code was adapted from
Malik et al. [7] official repository) as it does a fixed number of episodes
per epoch rather than doing a fixed number of environment steps per epoch. We
adjusted the number of PPO epochs in ICL so that each PPO procedure is roughly
the same length (or less) as the ICRL/GAIL PPO procedure. Even then, the
entire ICL training process requires a lot more steps than the GAIL-
Constraint/ICRL baselines, since every iteration requires a complete PPO
procedure. We have mentioned this in our conclusions section.

For the Gridworld (A, B) environments, we chose $\beta=0.99$ to disallow any
state of constraint value 1. For the CartPole (MR, Mid) environments, the
cartpole may start in a high constraint value region. To allow it to navigate
to a low constraint value region, we chose a high $\beta$. We chose $\beta$ by
doing a hyperparameter search on $\beta\in\\{30,50\\}$ for the CartPole
environments.

Table 6: ICL Hyperparameters

Hyperparameter | Value(s)
---|---
GA | GB | CMR | CMid | HighD
Discount factor ($\gamma$) | 1.0 | 1.0 | 0.99 | 0.99 | 0.99
ICL Iterations ($n$) | 10 | 10 | 10 | 10 | 3
Correction learning rate $(\eta_{1})$ | $2.5\times 10^{-5}$ | $2.5\times 10^{-5}$ | $2.5\times 10^{-5}$ | $2.5\times 10^{-5}$ | $2.5\times 10^{-5}$
PPO episodes per epoch | 20 | 20 | 20 | 20 | 20
$\beta$ | 0.99 | 0.99 | 50 | 30 | 0.1
Constraint update epochs ($e$) | 20 | 20 | 20 | 20 | 25
PPO epochs ($m$) | 500 | 500 | 300 | 300 | 50
Soft loss coefficient $\lambda$ | 15 | 15 | 15 | 15 | 15

##  4 Training Plots

For completeness, we provide the training plots for the recovered cost
functions (Figures 9, 11, 13, 15) and their respective accruals (Figures 10,
12, 14, 16, 17). Note that we have reported the costs for the HighD
environment in the main paper (Figure 3).

True constraint fn.

GAIL-Constraint

ICRL

ICL ($\beta=0.99$)

Figure 9: Average constraint function value (averaged across 5 training seeds)
for Gridworld (A) environment.

Expert accruals

GAIL-Constraint

ICRL

ICL ($\beta=0.99$)

Figure 10: Average normalized accruals (averaged across 5 training seeds) for
Gridworld (A) environment.

True constraint fn.

GAIL-Constraint

ICRL

ICL ($\beta=0.99$)

Figure 11: Average constraint function value (averaged across 5 training
seeds) for Gridworld (B) environment.

Expert accruals

GAIL-Constraint

ICRL

ICL ($\beta=0.99$)

Figure 12: Average normalized accruals (averaged across 5 training seeds) for
Gridworld (B) environment.

True constraint fn.

GAIL-Constraint

ICRL

ICL ($\beta=50$)

Figure 13: Average constraint function value (averaged across 5 training
seeds) for CartPole (MR) environment. Blue line represents the constraint
value for $a=0$ (going left) and the orange line represents the constraint
value for $a=1$ (going right).

Expert accruals

GAIL-Constraint

ICRL

ICL ($\beta=50$)

Figure 14: Average normalized accruals (averaged across 5 training seeds) for
CartPole (MR) environment.

True constraint fn.

GAIL-Constraint

ICRL

ICL ($\beta=30$)

Figure 15: Average constraint function value (averaged across 5 training
seeds) for CartPole (Mid) environment. Blue line represents the constraint
value for $a=0$ (going left) and the orange line represents the constraint
value for $a=1$ (going right).

Expert accruals

GAIL-Constraint

ICRL

ICL ($\beta=30$)

Figure 16: Average normalized accruals (averaged across 5 training seeds) for
CartPole (Mid) environment.

Expert accruals

GAIL-Constraint

ICRL

ICL ($\beta=0.1$)

Figure 17: Average normalized accruals (averaged across 5 training seeds) for
HighD environment. The X-axis and Y-axis are ego velocity in $m/s$ and gap to
the front vehicle $g$ in $m$ respectively.

##  5 Miscellaneous

###  5.1 Normalized Accrual Dissimilarity (NAD)

Here, we define the NAD metric more concretely. Given the policy $\pi$ learned
by any method (ICL or a baseline), we sample a dataset $\mathcal{D}_{\pi}$ of
agent trajectories (note that $|\mathcal{D}_{\pi}|=|\mathcal{D}|$, where
$\mathcal{D}$ is the expert dataset):

$\mathcal{D}_{\pi}:=\mbox{{Sample}}_{\tau}(\Pi=\\{\pi\\},p=\\{1\\}),\mbox{
{Sample} is defined in Algorithm \ref{alg:icl}}$

Then, the accrual (state-action visitation frequency) is computed for both the
agent dataset and the expert dataset over a uniformly discretized state-action
space (this depends on the constraint function inputs). For the various
environments, these are:

  * •

Gridworld (A, B): $\\{(x,y)|x,y\in\\{0,1,...,6\\}\\}$

  * •

CartPole (MR, Mid): $\\{(x,a)|x\in\\{-2.4,-2.3,\cdots,2.4\\},a\in\\{0,1\\}\\}$

  * •

HighD: $\\{(v,g)|v\in\\{0,1,\cdots,40\\},g\in\\{0,1,\cdots,80\\}\\}$ (here,
$v$ is in $m/s$ and $g$ is in pixels, where 1 pixel = 2.5m)

Finally, the accruals are normalized to sum to $1$, and the Wasserstein
distance is computed between the accruals. If the environment is CartPole, the
1D distance is computed and summed across actions. Otherwise, the 2D distance
is computed. We use the Python Optimal Transport library [35], specifically
the emd2 function to achieve this.