# Learning from Demonstration without Demonstrations

Tom Blau∗,†,⋄, Philippe Morere†, Gilad Francis† * Correspondence to: Tom Blau,
<EMAIL_ADDRESS>School of Computer Science, The University of
Sydney, Australia⋄ CSIRO, Australia

###### Abstract

State-of-the-art reinforcement learning (RL) algorithms suffer from high
sample complexity, particularly in the sparse reward case. A popular strategy
for mitigating this problem is to learn control policies by imitating a set of
expert demonstrations. The drawback of such approaches is that an expert needs
to produce demonstrations, which may be costly in practice. To address this
shortcoming, we propose Probabilistic Planning for Demonstration Discovery
(P2D2), a technique for automatically discovering demonstrations without
access to an expert. We formulate discovering demonstrations as a search
problem and leverage widely-used planning algorithms such as Rapidly-exploring
Random Tree to find demonstration trajectories. These demonstrations are used
to initialize a policy, then refined by a generic RL algorithm. We provide
theoretical guarantees of P2D2 finding successful trajectories, as well as
bounds for its sampling complexity. We experimentally demonstrate the method
outperforms classic and intrinsic exploration RL techniques in a range of
classic control and robotics tasks, requiring only a fraction of exploration
samples and achieving better asymptotic performance.

##  I Introduction

Reinforcement Learning (RL) studies how agents can learn a desired behaviour
by simply using interactions with an environment and a return signal. While RL
algorithms have enjoyed many recent successes in fields ranging from game
playing to robotic control [1, 2], a high computational cost is needed to find
efficient control policies. This issue is particularly severe when rewards are
sparse, indicating only binary success ($1$) or failure ($0$ or $-1$). Since
most rewards are identical, there is little gradient information to guide
policy learning. Figure 1(a) offers some insight into this phenomenon:
exploration in regions where the return surface is flat leads to a random walk
type search. This inefficient search continues until non-zero gradients are
found, which can then be followed to a local optimum.

However, if the policy can be initialized to a region of parameter space where
the gradient is informative (i.e. not flat), reinforcement learning can
optimize the policy efficiently, as shown in Figure 1(b). Learning from
demonstration (LfD) is a popular class of algorithms that can achieve such
initialization. In LfD, the training data is a set of demonstrations from an
expert policy that exhibits the desired agent behaviour. Control policies can
be learned from this data either by pure supervised learning [3], supervised
learning followed by RL refinement [4], or interleaving RL and supervision
[5]. The drawback of LfD approaches is that they require expert
demonstrations. The availability of such demonstrations is taken for granted
in much of the LfD literature, and there is an implicit assumption that the
cost of acquiring demonstrations is negligible. However, for many problems
this acquisition is difficult and costly, possibly defeating the purpose of
using LfD in the first place.

To address this issue, we propose to formulate the acquisition of
demonstrations as a search problem in state space. The demonstration finding
problem is then solved by planning algorithms, yielding a method for acquiring
demonstrations automatically (without an external expert). Planning algorithms
can achieve much better exploration performance than the random walk of Figure
1(a) by taking search history into account [6]. These techniques are also
often guaranteed to find a solution in finite time if one exists [7].
Demonstrations found by planning algorithms are then used to pre-train RL
policies, initializing them in regions of parameter space where the return
gradient is informative.

(a)

(b)

Figure 1: Expected returns for linear policy with $2$ parameters
$\theta_{0},\theta_{1}$ on Sparse MountainCar domain (background). Gradient is
$0$ in the dark blue area. Trajectories show the evolution of policy
parameters over $1000$ iterations of TRPO, with $5$ random seeds. Same colors
indicate the same random seeds. (a) Random-walk type behaviour observed when
parameters are initialized near the origin, following [8]. (b) Convergence
observed when parameters are initialized in a region with gradients ($1,40$).

This paper brings the following contributions:

  1. 1.

We relax the implicit assumptions—common in the LfD literature—that
demonstrations are readily available and that the cost of acquiring them is
negligible.

  2. 2.

We propose a method, called Probabilistic Planning for Demonstration Discovery
(P2D2), which automatically acquires demonstrations without the need for an
external expert111Code is available at https://gitlab.com/tomblau/p2d2. The
demonstrations are then used in an LfD algorithm.

  3. 3.

We provide theoretical guarantees for finding successful demonstration
trajectories and derive bounds for the sampling complexity of P2D2.

  4. 4.

Experimentally, we show LfD with P2D2 outperforms both classic and intrinsic
exploration techniques in RL, even when accounting for the cost of acquiring
demonstrations.

  5. 5.

Results demonstrate that P2D2 lowers the variance of policy gradient methods
such as TRPO, and verify that initializing policies in regions with rich
gradient information makes them less sensitive to initial conditions and
random seed.

The paper is structured as follows: Section II discusses related work. The
P2D2 algorithm and theoretical exploration guarantees are described in Section
III, followed by experimental results and analysis in Section IV. Finally,
Section V concludes and gives directions for future work.

##  II Related work

Techniques for learning policies from demonstration have been extensively
studied [9]. The most basic form of LfD is pure supervised learning to imitate
the actions of an expert [3, 10]. Policies learned in this way generalize
poorly to new states not seen during training, giving rise to approaches with
an RL fine-tuning phase [11]. Other methods couple LfD and RL more tightly:
reinforcement learning from demonstration [12] shapes the reward function
based on the demonstrated trajectories, whereas Q-learning from demonstration
[13] seeks to learn the state-action value function of the expert.

Yet another class of LfD algorithms interleaves supervision and RL. Generative
adversarial reinforcement learning [5] applies an adversarial approach, where
a discriminator model learns to distinguish between expert demonstrations and
policy actions, while the policy learns to fool the discriminator. The BCO
algorithm [14] uses only observations of the system state, learning to infer
actions and improving the policy simultaneously. All of these LfD techniques
rely on user-generated demonstrations or a-priori knowledge of environment
parameters. In contrast, P2D2 _automatically_ discovers demonstrations, with
no need of an external expert. To the best of our knowledge, it is the first
method with this capability.

Exploration has long been an important topic in RL. Classic techniques
typically rely on adding noise to actions [1, 15], and perform very poorly in
settings with sparse rewards. Intrinsic motivation tackles this problem by
defining a new reward to direct exploration. Many intrinsic reward definitions
were proposed, based on information theory [16], state visitation count [17,
18, 19, 20], value function posterior variance [21, 22], or model prediction
error [23, 24]. In the setting of continuous state and action spaces none of
these approaches offer guarantees for the exploration of the state space,
unlike P2D2. Recent works try to offer exploration guarantees by adapting
Bayesian optimization to RL [25, 26], but results are still limited to toy
problems and specific policy model classes.

Motion planning in robotics is predominantly addressed with sampling-based
methods. This type of approach offers a variety of methodologies for
exploration and solution space representation (e.g., Probabilistic roadmaps
(PRM) [27], Expansive space trees (EST) [28] and Rapidly-exploring random tree
(RRT) [29]), which have shown excellent performance in path planning in high-
dimensional spaces under dynamic constraints [30, 31, 27].

RL was previously combined with sampling-based planning to replace core
elements of planning algorithms, such as PRM’s point-to-point connection [32],
local RRT steering function [33] or RRT expansion policy [34], and even entire
motion planners [35]. In contrast, the proposed method bridges the gap in the
opposite direction, employing a sampling-based planner to discover
demonstrations that kick-start RL algorithms and enhance their performance.

##  III Probabilistic Planning for Demonstration Discovery (P2D2)

This work formulates finding demonstrations as a planning problem in the state
space. Unlike random walk RL exploration, planning algorithms such as Rapidly-
exploring Random Tree (RRT) encourage uniform coverage of the search space and
are probabilistically complete, i.e. guaranteed to find a solution [36]. The
presented algorithm, called P2D2, generates a collection of successful
trajectories, which can be used instead of expert demonstrations in LfD
algorithms. We first provide preliminaries in Section III-A, then present the
RRT algorithm in Section III-B and adapt it to the RL setting in order to
achieve automatic demonstration discovery. Finally, theoretical guarantees for
the proposed method are provided in Section III-C.

###  III-A Preliminaries

This work is based on the Markov Decision Process (MDP) framework, defined as
a tuple ${<\mathcal{S},\mathcal{A},T,R,\gamma>}$. $\mathcal{S}$ and
$\mathcal{A}$ are spaces of states $s$ and actions $a$ respectively.
$T:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$ is a
transition probability distribution so that
$T(s_{t},a_{t},s_{t+1})=p(s_{t+1}|s_{t},a_{t})$, where subscript $t$ indicates
the $t^{th}$ discrete timestep.
$R:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow\mathbb{R}$ is a
reward function defining rewards $r_{t}$ associated with transitions
$(s_{t},a_{t},s_{t+1})$. $\gamma\in[0,1)$ is a discount factor, and we denote
the space of initial states $\mathcal{S}_{0}$. Solving a MDP amounts to
finding the optimal policy $\pi^{*}$ maximizing the expected return
$J(\pi^{*})=\mathbb{E}_{T,\pi^{*}}[\sum^{\infty}_{t=0}\gamma^{t}R(s_{t},a_{t},s_{t+1})]$,
where actions are chosen according to $a_{t}=\pi^{*}(s_{t})$.

We add the following definitions to the MDP framework:

######  Definition 1.

A transition $(s_{t},a_{t},s_{t+1})$ is _valid_ if and only if
$T(s_{t},a_{t},s_{t+1})>0$. That is, the transition is in the support of
transition dynamics $T$.

######  Definition 2.

A valid trajectory is a sequence
$\tau=\left[s_{0},a_{0},s_{1},\ldots,s_{t_{\tau}-1},a_{t_{\tau}-1},s_{t_{\tau}}\right]$
such that $(s_{t},a_{t},s_{t+1})$ is a valid transition $\forall
t\in\\{0,1,\ldots,t_{\tau}-1\\}$, and $s_{0}\in\mathcal{S}_{0}$.

Additionally, whenever a goal space $\mathcal{S}_{goal}\subseteq\mathcal{S}$
is defined for the MDP, we say a trajectory is _successful_ if its end state
is within the goal space, i.e. $s_{t_{\tau}}\in\mathcal{S}_{goal}$.

###  III-B Planning in MDPs with RRT

The RRT algorithm [30] provides a principled approach for planning in problems
that cannot be solved directly (e.g. using inverse kinematics), but where it
is possible to sample transitions. Ordinarily, a planning problem given to an
RRT is defined by a configuration space $\mathcal{C}$, a set of configurations
that result in collision $\mathcal{C}_{obs}$, and the set of collision-free
configurations $\mathcal{C}_{free}=\mathcal{C}\setminus\mathcal{C}_{obs}$. RRT
and variant algorithms commonly assume that it is possible to travel in a
straight line in $\mathcal{C}_{free}$, or that there is access to a steering
function that can move an agent between the end-points of such a line segment.
In each iteration of the algorithm, RRT randomly samples a candidate point
$c_{rand}\in\mathcal{C}_{free}$ and tries to connect it to the nearest node in
the tree $c_{near}\in\mathbb{T}$ via a straight line (typically what ends up
being added to the tree is a point $c_{new}$ on the line
$\overline{c_{near}c_{rand}}$).

In the MDP setting, the state space $\mathcal{S}$ replaces the configuration
space $\mathcal{C}$, and obstacles are only defined implicitly by the
transition dynamics $T$. In general it is not possible to travel along a
straight line, and a steering function is usually not available. For these
reasons, an RRT planning in MDPs can’t connect nodes in a straight line.
Instead, after sampling candidate state $s_{rand}\in\mathcal{S}$, the RRT will
add a new node $s_{new}$ connected to $s_{near}$ by executing a random action
$a_{rand}\in\mathcal{A}$ at the state $s_{near}$. The edge
$(s_{near},s_{new})$ will store this action. If the newly added state
satisfies $s_{new}\in\mathcal{S}_{goal}$, the algorithm is finished, and a
successful trajectory can be generated by traversing up the tree from
$s_{new}$ to $s_{root}$. A typical instance of this procedure is illustrated
in Figure 2.

The ability to execute this modified RRT algorithm in MDPs relies on two
assumptions:

######  Assumption 1.

States can be sampled uniformly from the MDP state space $\mathcal{S}$.

Since $\mathcal{S}$ is typically a hyper-rectangle, sampling from it uniformly
is trivial. Note that the sampled states don’t have to be valid (i.e.
collision-free). Even if $s_{rand}$ isn’t valid, $s_{new}$ and
$(s_{near},s_{new})$ will be valid because they are produced by the transition
dynamics.

######  Assumption 2.

The environment state can be set to a previously visited state
$s\in\mathbb{T}$ (e.g. by means of a simulator).

Although this assumption may seem limiting at first glance, it is already in
use in the RL literature [37, 38, 39]. Further, it lines up nicely with
existing research on sim-to-real transfer [40]: a policy can be trained in
simulation, where the assumption is easily satisfied, then transferred to
physical environments using sim-to-real techniques.

The proposed P2D2 algorithm, as summarized in Algorithm 1, discovers a set of
$N$ demonstrations ${\bm{\tau}=\\{\tau_{i}\\}_{1}^{N}}$ by repeatedly
executing the above modified RRT with different initial states. LfD techniques
can then be leveraged to learn an imitation policy $\pi_{0}$, which may be
further refined using traditional RL algorithms such as TRPO [15].

2

Input: $\mathcal{S}_{goal},N,\mathcal{M}$: MDP, $k$: sampling budget

Input(optional): $p_{g}$: goal sampling prob.

Output: ${\bm{\tau}=\\{\tau_{i}\\}_{1}^{N}}$: successful trajectories

$\bm{\tau}\leftarrow\emptyset$

while $\lvert\bm{\tau}\rvert<N$ do

$s_{0}\leftarrow\text{sample initial state
}s_{0}\sim\mathbb{U}(\mathcal{S}_{0})$

Initialise tree $\mathbb{T}$ with root $s_{0}$

for $i=1:k$ do

$s_{rand}\leftarrow\text{sample random state
}s_{rand}\sim\mathbb{U}(\mathcal{S})$

if $u\sim\mathbb{U}(\left[0,1\right])\leq p_{g}$ then

$s_{rand}\leftarrow\text{sample }s_{rand}\sim\mathbb{U}(\mathcal{S}_{goal})$

end if

$s_{near}\leftarrow\text{find nearest node to $s_{rand}$ in $\mathbb{T}$}$

$a\leftarrow\text{sample random action }a\sim\mathbb{U}(\mathcal{A})$

$s_{new}\leftarrow\text{execute $a$ in state $s_{near}$}$

Add $a$, node $s_{new}$ and edge ($s_{near},s_{new}$) to $\mathbb{T}$

end for

$\tau\leftarrow\text{trajectory in $\mathbb{T}$ with max. cumulated reward}$

if $\tau$ is a successful trajectory then

$\bm{\tau}\leftarrow\bm{\tau}\cup\tau$

end if

1 end while

Algorithm 1 Probabilistic Planning for Demonstration Discovery Figure 2:
Example of P2D2 on sparse MountainCar. Green segments are sampled transitions,
executed in simulation. A successful solution found by P2D2 is displayed in
red. State dimensions are normalized to $\left[-1,1\right]$.

###  III-C Exploration guarantees

The RL planning environment defines differential constraints of the form:

$\dot{s}=f(s(t),a(t)),\quad s(t)\in\mathcal{S},\quad a(t)\in\mathcal{A}.$ (1)

Therefore, starting at $s_{0}$, the trajectory $\tau$ can be computed by
forward integrating equation (1) with the applied actions. As with many RL
problems, $a(t)$ is time-discretized resulting in a piecewise constant control
function. This means $\tau$ is constructed of $n_{\tau}$ segments of fixed
time duration $\Delta t$ such that the overall trajectory duration
$t_{\tau}=n_{\tau}\cdot\Delta t$. Thus, $a(t)$ is defined as
$a(t)=a_{i}\in\mathcal{A}$ where $t\in[(i-1)\cdot\Delta t,i\cdot\Delta t)$ and
$1\leq i\leq n_{\tau}$. Furthermore, as all transitions between states in
$\tau$ are known, the trajectory return can be defined as
$R_{\tau}=\sum^{n_{\tau}}_{t=0}\gamma^{t}R(s_{t},a_{t},s_{t+1})$.

P2D2 explores in state-action space instead of policy parameter space.
Furthermore, it is an effective exploration framework which provides
probabilistic completeness (PC):

######  Definition 3.

A probabilistically complete planner finds a feasible solution (if one exists)
with a probability approaching 1 in the limit of infinite samples.

With the aforementioned dynamic characteristics, we prove that P2D2 under the
RL setting is PC. This is in stark contrast to the random walk-like RL
exploration, discussed in section I, which is _not_ PC. We begin with the
following theorem, a modification of Theorem 2 from [36], which is applied to
kinodynamic RRT where a goal set $\mathcal{S}_{goal}$ is defined.

######  Theorem 1.

Suppose that there exists a valid trajectory $\tau$ from $s_{0}$ to
$\mathcal{S}_{goal}$ as defined in definition 2, with a corresponding
piecewise constant control. The probability that P2D2 fails to reach
$\mathcal{S}_{goal}$ from $s_{0}$ after $k$ iterations is bounded by
$ae^{-bk}$, for some constants $a,b>0$.

The proof, which is a modification of Theorem 2 from [36], can be found in
Appendix S2. It should be noted that P2D2 does not require an explicit
definition for $\mathcal{S}_{goal}$ in order to explore the space. While in
some path planning variants of RRT, $\mathcal{S}_{goal}$ is used to bias
sampling, the main purpose of $\mathcal{S}_{goal}$ is to indicate that a
solution has been found. Therefore, $\mathcal{S}_{goal}$ can be replaced by
another implicit success criterion. In the RL setting, this can be replaced by
a return-related criterion.

######  Theorem 2.

Suppose there exists a trajectory with a return
$R_{\tau}\geq\hat{R},\hat{R}\in\mathbb{R}$. The probability that P2D2 fails to
find a valid trajectory from $s_{0}$ with $R_{\tau}\geq\hat{R}$ after $k$
iterations is bounded by $\hat{a}e^{-\hat{b}k}$, for some constants
$\hat{a},\hat{b}>0$.

###### Proof.

The proof is straightforward. We augment each state in $\tau$ with the return
for reaching it from $s_{0}$:

$\displaystyle s^{\prime}_{n}$ $\displaystyle=\begin{bmatrix}s_{n}\\\
R_{s_{n}}\end{bmatrix},\qquad\forall n=1:n_{\tau},$ (2)

where $R_{s_{n}}=\sum^{n}_{t=0}\gamma^{t}R(s_{t},a_{t},s_{t+1})$. For
consistency we modify the distance metric by simply adding a reward distance
metric. With the above change in notation, we modify the goal set to
$\mathcal{S}^{RL}_{goal}=\\{(s,R_{s})|s\in\mathcal{S}_{goal},R_{s}\geq\hat{R}\\}$,
such that there is an explicit criterion for minimal return as a goal.
Consequently, the exploration problem can be written for the augmented
representation as $(\mathcal{S},s^{RL}_{0},\mathcal{S}^{RL}_{goal})$, where
$s^{RL}_{0}=[s_{0},0]^{\top}$. Theorem 1 satisfies that P2D2 can find a
feasible solution to this problem within finite time, i.e. PC, and therefore
the probability of not reaching $\mathcal{S}^{RL}_{goal}$ after $k$ iterations
is upper-bounded by the exponential term $\hat{a}e^{-\hat{b}k}$, for some
constants $\hat{a},\hat{b}>0$ ∎

We can now state our main result on the sampling complexity of the exploration
process.

######  Theorem 3.

If trajectory exploration is probabilistically complete and satisfies an
exponential convergence bound, the expected sampling complexity is finite and
bounded s.t.

$\mathbb{E}[k]\leq\frac{\hat{a}}{4\sinh^{2}{\frac{\hat{b}}{2}}},$ (3)

where $\hat{a},\hat{b}>0$.

###### Proof.

Theorem 2 provides an exponential bound for the probability the planner fails
in finding a feasible path. Hence, we can bound the expected number of
iterations needed to find a solution, i.e. sampling complexity:

$\displaystyle\mathbb{E}[k]\leq\sum^{\infty}_{k=1}k\hat{a}e^{-\hat{b}k}$
$\displaystyle=\sum^{\infty}_{k=1}-\hat{a}\frac{de^{-\hat{b}k}}{d\hat{b}}$ (4)
$\displaystyle=-\hat{a}\frac{d}{d\hat{b}}\sum^{\infty}_{k=1}e^{-\hat{b}k}$ (5)
$\displaystyle=-\hat{a}\frac{d}{d\hat{b}}\frac{1}{e^{\hat{b}}-1}$ (6)
$\displaystyle=\frac{\hat{a}}{4\sinh^{2}{\frac{\hat{b}}{2}}},$ (7)

where we used the relation
$\sum^{\infty}_{k=1}e^{-\hat{b}k}=\frac{1}{e^{\hat{b}}-1}$. ∎

It is worth noting that while the sample complexity is bounded, the above
result implies that the bound varies according to problem-specific properties,
which are encapsulated in the value of $\hat{a}$ and $\hat{b}$. Intuitively,
$\hat{a}$ depends on the scale of the problem. It grows as
$\lvert\mathcal{S}^{RL}_{goal}\rvert$ becomes smaller or as the length of the
solution trajectory becomes longer. $\hat{b}$ depends on the probability of
sampling states that will expand the tree in the right direction. It therefore
shrinks as the dimensionality of $\mathcal{S}$ increases. We refer the reader
to Appendix S2 for more details on the meaning of $\hat{a},\hat{b}$ and the
derivation of the tail bound in Theorem 1.

Figure 3: Results for classic control tasks, comparing our proposed method
(P2D2-TRPO/DDPG), vanilla TRPO/DDPG, and VIME-TRPO. Trendlines are the medians
and shaded areas are the interquartile range, taken over $10$ randomly chosen
seeds. Also shown is the average undiscounted return of successful
trajectories discovered by P2D2. The dashed offset at the start of
P2D2-TRPO/DDPG reflects the number of timesteps spent on P2D2.

##  IV Experiments

In this section, we investigate (i) whether P2D2 reduces the number of
exploration samples needed to find good policies, compared with methods using
classic and intrinsic exploration, (ii) how P2D2 can reduce the variance
associated with policy gradient methods, and (iii) how P2D2 compares with
standard LfD. All experiments make use of the Garage [41] and Gym [42]
frameworks. The experiments feature sparse-reward versions of the following
tasks: _MountainCar_
($\mathcal{S}\subseteq\mathbb{R}^{2},\mathcal{A}\subseteq\mathbb{R}$),
_Pendulum_
($\mathcal{S}\subseteq\mathbb{R}^{2},\mathcal{A}\subseteq\mathbb{R}$),
_Cartpole Swingup_
($\mathcal{S}\subseteq\mathbb{R}^{4},\mathcal{A}\subseteq\mathbb{R}$),
_Acrobot_
($\mathcal{S}\subseteq\mathbb{R}^{4},\mathcal{A}\subseteq\mathbb{R}$).
Experiments also include the following robotics tasks: _Reacher_
($\mathcal{S}\subseteq\mathbb{R}^{6},\mathcal{A}\subseteq\mathbb{R}^{2}$)
_Fetch Reach_
($\mathcal{S}\subseteq\mathbb{R}^{13},\mathcal{A}\subseteq\mathbb{R}^{4}$),
and _Hand Reach_
($\mathcal{S}\subseteq\mathbb{R}^{78},\mathcal{A}\subseteq\mathbb{R}^{20}$).

Figure 4: Comparison of RL initialized with automatically discovered
demonstrations (P2D2) and expert demonstrations (Theoretical Solver).
Trendlines are medians and shaded areas are interquartile ranges aggregated
over $10$ random seeds. Results show that degradation due to P2D2
demonstrations is small, and the P2D2-initialized agents catch up to the
baseline agents before convergence occurs.

Comparison to classic and intrinsic exploration on RL benchmarks. We compare
P2D2 with state-of-the-art RL algorithms on several RL benchmarks. Performance
is measured in terms of undiscounted returns and aggregated over 10 random
seeds, sampled at random for each environment. We focus on domains with sparse
rewards, which are notoriously difficult to explore for traditional RL methods
(cf. Appendix S3-A). Note that in all of the following experiments, P2D2
utilises basic RRT to discover demonstrations, and a simple LfD technique
(supervised learning) is used. However, P2D2 is compatible with more
sophisticated versions of RRT and LfD, which would most likely increase
performance if used. Our experiments focus on the widely-used methods TRPO
[15] and DDPG [43]. P2D2-TRPO and P2D2-DDPG are compared to the baseline
algorithms with Gaussian action noise. As an additional baseline we include
VIME-TRPO [44]. VIME is an exploration strategy based on maximizing
information gain about the agent’s belief of the environment dynamics. It is
included to show that P2D2 can improve on state-of-the-art exploration methods
as well as naive ones, even though the return surface for VIME-TRPO is no
longer flat, unlike Figure 1. The exact experimental setup is described in
Appendix S3.

P2D2 is first run to compute training trajectories for all environments. The
number of environment interactions during this phase is accounted for in the
results, displayed as an offset with a vertical dashed black line. The average
performance achieved by these trajectories is also reported as a guideline,
with the exception of _Cartpole Swingup_ where doing so does not make sense.
RL is then used to refine a policy pretrained with these trajectories.

Figure 3 shows the median and interquartile range for all methods. P2D2
outdoes both vanilla and VIME baselines. It converges faster and achieves
higher performance at the end of the experiment. In most cases, the upper
quartile for our method begins well above the minimum return, indicating that
P2D2 and pre-training are able to produce successful though not optimal
policies. For the majority of problems, P2D2-DDPG performance starts
significantly above the minimum return, plunges due to the inherent
instability of DDPG, but eventually recovers, indicating that P2D2 pre-
training can help mitigate the instability.

It is worth noting that P2D2’s lower quartile is considerably higher than that
of baselines. Indeed, for many of the baselines the lower quartile takes a
long time to improve on the minimum return, and in some cases it never manages
to do so at all. This is a common problem in sparse reward RL, where there is
no alternative but to search the state space randomly until the first
successful trajectory is found, and only then is an informative reward signal
received. While a few random seeds will by chance find a successful trajectory
quickly (represented by the quickly rising upper quartile), others take a long
time (represented by the much slower rise of the median and lower quartile).
In other words, P2D2-TRPO/DDPG is much more robust to random policy
initialization and to random seeds than standard RL methods. This is because
P2D2 is able to use automatically discovered demonstrations to initialize
policy parameters to a region with informative return gradients.

Comparison to learning from expert demonstrations. Since the demonstrations
produced by P2D2 have no guarantee of optimality, it is reasonable to expect
that a policy learned from them will be worse than a policy learned from
expert demonstrations. This degradation is assessed in Figure 4. Experiments
were conducted on the _MountainCar_ , _Pendulum_ and _Acrobot_ tasks for which
a theoretical solver is readily available (described in Appendix S3-B). The RL
algorithm used was TRPO in all cases. As the figure shows, the P2D2 agent has
worse initial performance than the baseline agent, but quickly catches up. The
performance difference becomes statistically insignificant _before_ either
agent converges. This contrasts with the previous set of experiments, where
P2D2 agents converge long before other agents learning without demonstrations.
The difference between learning from P2D2 demonstrations and learning from
expert demonstrations is therefore very small when compared to the difference
between learning from P2D2 and learning from scratch. These results suggest
that in a LfD context, the quality of P2D2 demonstrations is relatively close
to that of expert demonstrations.

##  V Conclusion

We proposed Probabilistic Planning for Demonstration Discovery (P2D2), a
paradigm for leveraging planing algorithms to automatically discover
demonstrations, which can be converted to policies then refined by classic RL
methods. This is a relaxation of the common assumption made in the LfD
literature, which presupposes that either demonstrations or an expert are
available. We provided theoretical guarantees of P2D2 finding solutions, as
well as sampling complexity bounds. Empirical results show that P2D2
outperforms classic and intrinsic exploration techniques, requiring only a
fraction of exploration samples and achieving better asymptotic performance.
This holds true even when accounting for the cost of acquiring demonstrations.
Finally, experiments indicate that the degradation caused by using
demonstrations from P2D2 rather than from an expert is mild, especially in
comparison to the discrepancy between P2D2 and RL from scratch.

In future work P2D2 could be extended to real-world problems by using sim-to-
real methods, as mentioned in Section III-B. Exploration in high-dimensional
tasks is also challenging, as stated in Theorem 3 and confirmed experimentally
by increased P2D2 timesteps. Exploiting external prior knowledge and/or the
structure of the problem can benefit exploration in high-dimensional tasks,
and help make P2D2 practical for problems such as Atari games. Lastly, all the
results in this paper were achieved using basic RRT and supervised LfD. Recent
advances in RRT [33] and LfD [14] could therefore be applied to significantly
improve P2D2.

## References

  * [1] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, _et al._ , “Human-level control through deep reinforcement learning,” _Nature_ , 2015\.
  * [2] J. Tan, T. Zhang, E. Coumans, _et al._ , “Sim-to-real: Learning agile locomotion for quadruped robots,” _Robotics: Science and Systems_ , 2018\.
  * [3] D. A. Pomerleau, “Efficient training of artificial neural networks for autonomous navigation,” _Neural Computation_ , vol. 3, 1991.
  * [4] S. Schaal, “Learning from demonstration,” in _Advances in Neural Information Processing Systems_ , 1997.
  * [5] J. Ho and S. Ermon, “Generative adversarial imitation learning,” in _Advances in Neural Information Processing Systems_ , 2016.
  * [6] S. M. Lavalle, “Rapidly-exploring random trees: A new tool for path planning,” Department of Computer Science. Iowa State University., Tech. Rep., 1998.
  * [7] S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” _The International Journal of Robotics Research_ , 2011.
  * [8] X. Glorot and Y. Bengio, “Understanding the difficulty of training deep feedforward neural networks,” in _International Conference on Artificial Intelligence and Statistics_ , 2010.
  * [9] B. D. Argall, S. Chernova, M. Veloso, and B. Browning, “A survey of robot learning from demonstration,” _Robotics and Autonomous Systems_ , vol. 57, 2009.
  * [10] M. Bojarski, D. Del Testa, D. Dworakowski, B. Firner, B. Flepp, P. Goyal, L. D. Jackel, M. Monfort, U. Muller, J. Zhang, X. Zhang, J. Zhao, and K. Ziebaand, “End to end learning for self-driving cars,” _NIPS Deep Learning Symposium_ , 2016.
  * [11] H. Benbrahim and J. A. Franklin, “Biped dynamic walking using reinforcement learning,” _Robotics and Autonomous Systems_ , vol. 22, 1997.
  * [12] T. Brys, A. Harutyunyan, H. B. Suay, _et al._ , “Reinforcement learning from demonstration through shaping,” in _AAAI Conference on Artificial Intelligence_ , 2015.
  * [13] T. Hester, M. Vecerik, O. Pietquin, _et al._ , “Deep q-learning from demonstrations,” in _AAAI Conference on Artificial Intelligence_ , 2018.
  * [14] F. Torabi, G. Warnell, and P. Stone, “Behavioral cloning from observation,” in _International Joint Conference on Artificial Intelligence_ , 2018.
  * [15] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz, “Trust region policy optimization,” in _International Conference on Machine Learning_ , 2015.
  * [16] P. Y. Oudeyer and F. Kaplan, “How can we define intrinsic motivation?” in _International Conference on Epigenetic Robotics: Modeling Cognitive Development in Robotic Systems_ , 2008.
  * [17] M. Lopes, T. Lang, M. Toussaint, and P. Oudeyer, “Exploration in model-based reinforcement learning by empirically estimating learning progress,” in _Advances in Neural Information Processing Systems_ , 2012.
  * [18] M. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton, and R. Munos, “Unifying count-based exploration and intrinsic motivation,” in _Advances in Neural Information Processing Systems_ , 2016.
  * [19] I. Szita and A. Lőrincz, “The many faces of optimism: a unifying approach,” in _International Conference on Machine learning_ , 2008.
  * [20] L. Fox, L. Choshen, and Y. Loewenstein, “DORA the explorer: Directed outreaching reinforcement action-selection,” in _International Conference on Learning Representations_ , 2018.
  * [21] I. Osband, C. Blundell, A. Pritzel, and B. Van Roy, “Deep exploration via bootstrapped DQN,” in _Advances in Neural Information Processing Systems_ , 2016.
  * [22] P. Morere and F. Ramos, “Bayesian RL for goal-only rewards,” in _Conference on Robot Learning_ , 2018.
  * [23] B. C. Stadie, S. Levine, and P. Abbeel, “Incentivizing exploration in reinforcement learning with deep predictive models,” _arXiv:1507.00814_ , 2015.
  * [24] D. Pathak, P. Agrawal, A. A. Efros, and T. Darrell, “Curiosity-driven exploration by self-supervised prediction,” in _International Conference on Machine Learning_ , 2017.
  * [25] A. Wilson, A. Fern, and P. Tadepalli, “Using trajectory data to improve bayesian optimization for reinforcement learning,” _The Journal of Machine Learning Research_ , 2014.
  * [26] N. A. Vien, H. Zimmermann, and M. Toussaint, “Bayesian functional optimization,” in _AAAI Conference on Artificial Intelligence_ , 2018.
  * [27] L. E. Kavraki, P. Svestka, J. C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” _Transactions on Robotics and Automation_ , 1996.
  * [28] D. Hsu, J. Latombe, and R. Motwani, “Path planning in expansive configuration spaces,” in _International Conference on Robotics and Automation_ , 1997\.
  * [29] J. J. Kuffner and S. M. LaValle, “RRT-connect: An efficient approach to single-query path planning,” in _International Conference on Robotics and Automation_ , 2000.
  * [30] S. M. LaValle and J. J. Kuffner, “Randomized kinodynamic planning,” _The International Journal of Robotics Research_ , 2001.
  * [31] D. Hsu, R. Kindel, J. Latombe, and S. Rock, “Randomized kinodynamic motion planning with moving obstacles,” _The International Journal of Robotics Research_ , 2002.
  * [32] A. Faust, K. Oslund, O. Ramirez, A. Francis, L. Tapia, M. Fiser, and J. Davidson, “PRM-RL: Long-range robotic navigation tasks by combining reinforcement learning and sampling-based planning,” in _International Conference on Robotics and Automation_ , 2018.
  * [33] H. L. Chiang, J. Hsu, M. Fiser, L. Tapia, and A. Faust, “RL-RRT: Kinodynamic motion planning via learning reachability estimators from RL policies,” _Robotics and Automation Letters_ , vol. 4, 2019.
  * [34] B. Chen, B. Dai, and L. Song, “Learning to plan via neural exploration-exploitation trees,” _arXiv:1903.00070_ , 2019.
  * [35] T. Jurgenson and A. Tamar, “Harnessing reinforcement learning for neural motion planning,” _Robotics: Science and Systems_ , 2019.
  * [36] M. Kleinbort, K. Solovey, Z. Littlefield, K. E. Bekris, and D. Halperin, “Probabilistic completeness of RRT for geometric and kinodynamic planning with forward propagation,” _Robotics and Automation Letters_ , 2019.
  * [37] C. Florensa, D. Held, M. Wulfmeier, M. Zhang, and P. Abbeel, “Reverse curriculum generation for reinforcement learning,” in _Conference on Robot Learning_ , 2017.
  * [38] A. Nair, B. McGrew, M. Andrychowicz, W. Zaremba, and P. Abbeel, “Overcoming exploration in reinforcement learning with demonstrations,” in _International Conference on Robotics and Automation_ , 2018.
  * [39] A. Ecoffet, J. Huizinga, J. Lehman, K. O. Stanley, and J. Clune, “Go-explore: a new approach for hard-exploration problems,” _arXiv:1901.10995_ , 2019\.
  * [40] X. B. Peng, M. Andrychowicz, W. Zaremba, and P. Abbeel, “Sim-to-real transfer of robotic control with dynamics randomization,” in _International Conference on Robotics and Automation_ , 2018.
  * [41] T. garage contributors, “Garage: A toolkit for reproducible reinforcement learning research,” https://github.com/rlworkgroup/garage, 2019.
  * [42] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba, “OpenAI Gym,” 2016.
  * [43] T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, _et al._ , “Continuous control with deep reinforcement learning,” _arXiv:1509.02971_ , 2015.
  * [44] R. Houthooft, X. Chen, Y. Duan, J. Schulman, F. De Turck, and P. Abbeel, “Vime: Variational information maximizing exploration,” in _Advances in Neural Information Processing Systems_ , 2016.
  * [45] R. Arratia and L. Gordon, “Tutorial on large deviations for the binomial distribution,” _Bulletin of Mathematical Biology_ , 1989.
  * [46] M. W. Spong, “Swing up control of the acrobot,” in _International Conference on Robotics and Automation_ , 1994.
  * [47] C. Urmson and R. Simmons, “Approaches for heuristically biasing RRT growth,” in _International Conference on Intelligent Robots and Systems_ , 2003.
  * [48] A. Rahimi and B. Recht, “Random features for large-scale kernel machines,” in _Advances in Neural Information Processing Systems_ , 2008.

Learning from Demonstration without Demonstrations: Supplementary Material

##  S1 RRT algorithm psuedo-code

In this section, we provide pseudo-code of the classic RRT algorithm.

The basic form of RRT, used for path planning, attempts at every iteration to
extend its tree $\mathbb{T}$ by adding a new vertex, which is biased by a
randomly-selected state $s_{rand}$. The tree is expanded by selecting the
nearest vertex of the tree, $s_{near}$, to the newly sampled state RRT then
attempts to add a new vertex $s_{new}$ to the tree by applying an input $a$.
This process biases the RRT to rapidly explore, which results in a uniform
coverage of the state space [6].

Note that all trajectories represented by $\mathbb{T}$ are valid, as they are
grown from valid transitions between states in $\mathcal{S}$. The robotics
path planning community often adds explicit collision validity checks for
$s_{rand}$ and $s_{new}$. However, the basic form of RRT [6], does not require
these checks, as expansion of the tree toward $s_{new}$ is inherently valid
given transition dynamics. In RL problems, validity might extend beyond
collision checks (e.g. not all random images are valid states of an Atari
game), but the transition dynamics still guarantee $s_{new}$ will be valid.

2

Input: $s_{init}$, $k$: sampling budget

1 Output: $\delta t$: Euler integration time interval

$\mathbb{T}$.init($s_{init}$)

for $i=1:k$ do

$s_{rand}\leftarrow\text{RANDOM\\_UNIFORM}(S)$

$s_{near}\leftarrow\operatorname*{arg\,min}_{s\in\mathbb{T}}\lVert
s_{rand}-s_{near}\rVert$ {Find nearest vertex}

$a\leftarrow\Upsilon(s_{near},s_{rand})$ {Sample action}

$s_{new}\leftarrow s_{near}+\Delta t\cdot f(s_{near},a)$ {Propagate to new
state, Equation (1)}

$\mathbb{T}$.add_vertex($s_{new}$)

$\mathbb{T}$.add_edge($s_{near},s_{new}$)

end for

Algorithm 2 Rapidly-exploring Random Trees (RRT)

##  S2 Proof of Theorem 1

This appendix proves Theorem 1, which shows that planning using RRT under
differential constraints is probabilistically complete. The following proof is
a modification of Theorem 2 from [36], where completeness of RRT in the RL
setting is maintained without the need to explicitly sample a duration for
every action.

Equation 1 defines the environment’s differential constraints. In practice,
the equation is approximated by an Euler integration step, with the interval
$[0,t_{\tau}]$ divided into $l>>n_{\tau}$ equal time intervals of duration $h$
with $t_{\tau}=l\cdot h$. The valid transition between consecutive time steps
is given by:

$\displaystyle s_{n+1}=s_{n}+f(s_{n},a_{n})\cdot h,\qquad
s_{n},s_{n+1}\in\tau,$ (S1) $\displaystyle
s.t.\lim\limits_{l\rightarrow\infty,h\rightarrow 0}\lVert s_{n}-\tau(n\cdot
h)\rVert=0.$

Furthermore, we define $\mathcal{B}_{r}(s)$ as a ball with a radius $r$
centered at $s$ for any given state $s\in\mathcal{S}$.

We assume that the planning environment is Lipschitz continuous in both state
and action, constraining the rate of change of Equation (S1). Formally, there
exist positive constants $K_{s},K_{a}>0$, such that $\forall
s_{0},s_{1}\in\mathcal{S},a_{0},a_{1}\in\mathcal{A}:$

$\displaystyle\lVert f(s_{0},a_{0})-f(s_{0},a_{1})\rVert$ $\displaystyle\leq
K_{a}\lVert a_{0}-a_{1}\rVert,$ (S2) $\displaystyle\lVert
f(s_{0},a_{0})-f(s_{1},a_{0})\rVert$ $\displaystyle\leq K_{s}\lVert
s_{0}-s_{1}\rVert.$ (S3)

######  Lemma 1.

Let $\tau$, $\tau^{\prime}$ be trajectories where $s_{0}=\tau(0)$ and
$s^{\prime}_{0}=\tau^{\prime}(0)$ such that $\lVert
s_{0}-s^{\prime}_{0}\rVert\leq\delta_{s}$, with $\delta_{s}$ a positive
constant. Suppose that for each trajectory a piecewise constant action is
applied, so that $\Upsilon(t)=a$ and $\Upsilon^{\prime}(t)=a^{\prime}$ is
fixed during a time period $T\geq 0$. Then
$\lVert\tau(T)-\tau^{\prime}(T)\rVert\leq
e^{K_{s}T}\delta_{s}+TK_{a}e^{K_{s}T}\lVert a-a^{\prime}\rVert$.

The proof for Lemma 1 is given in Lemma 2 of [36]. Intuitively, this bound is
derived from compounding worst-case divergence between $\tau$ and
$\tau^{\prime}$ at every Euler step along $T$ which leads to an overall
exponential dependence.

Using Lemma 1, we want to provide a lower bound on the probability of choosing
an action that will expand the tree successfully. We note that this scenario
assumes that actions are drawn uniformly from $\mathcal{A}$, i.e. there is no
steering function 222The function
$steer:\mathcal{S}\times\mathcal{S}\rightarrow\mathcal{A}$ returns an action
$a_{steer}$ given two states $s{rand}$ and $s_{near}$ such that
$a_{steer}=\operatorname*{arg\,min}_{a\in\mathcal{A}}\lVert
s_{rand}-(s_{near}+\Delta t\cdot f(s_{near},a))\rVert\>s.t.\>\lVert\Delta
t\cdot f(s_{near},a)\rVert<\eta$, for a pre-specified $\eta>0$ [7].. When
better estimations of the steering function are available, the performance of
RRT significantly improves.

######  Definition 4.

A trajectory $\tau$ is defined as $\delta$-clear if $\exists\delta_{clear}>0$
such that $\mathcal{B}_{\delta_{clear}}(\tau(t))\in\mathcal{S}$ $\quad\forall
t\in[0,t_{\tau}]$.

######  Lemma 2.

Suppose that $\tau$ is a valid trajectory from $\tau(0)=s_{0}$ to
$\tau(t_{\tau})=s_{goal}$ with a duration of $t_{\tau}$ and a clearance of
$\delta$. Without loss of generality, we assume that actions are fixed for all
$t\in[0,t_{\tau}]$, such that $\Upsilon(t)=a\in\mathcal{A}$.

Suppose that RRT expands the tree from a state
$s^{\prime}_{0}\in\mathcal{B}_{(\kappa\delta-\epsilon)}(s_{0})$ to a state
$s^{\prime}_{goal}$, for any $\kappa\in(0,1]$ and
$\epsilon\in(0,\kappa\delta)$ we can define the following bound:

$\Pr[s^{\prime}_{goal}\in\mathcal{B}_{\kappa\delta}(s_{goal}))]\geq\frac{\zeta_{\lvert\mathcal{S}\rvert}\cdot\frac{\kappa\delta-e^{K_{s}t_{\tau}}(\kappa\delta-\epsilon)}{K_{a}t_{\tau}e^{K_{s}t_{\tau}}}}{\lvert\mathcal{A}\rvert}.$

Here, $\zeta_{\lvert\mathcal{S}\rvert}=\lvert\mathcal{B}_{1}(\cdot)\rvert$ is
the Lebesgue measure for a unit circle in $\mathcal{S}$.

###### Proof.

We denote $\tau^{\prime}$ a trajectory that starts from $s^{\prime}_{0}$ and
is expanded with an applied random action $a_{rand}$. According to Lemma 1,

$\displaystyle\lVert\tau(t)-\tau^{\prime}(t)\rVert$ $\displaystyle\leq
e^{K_{s}t}\delta_{s}+tK_{a}e^{K_{s}t}\lVert a-a_{rand}\rVert$
$\displaystyle\leq e^{K_{s}t}(\kappa\delta-\epsilon)+tK_{a}e^{K_{s}t}\lVert
a-a_{rand}\rVert,$

for all $t\in[0,t_{\tau}]$, where $\delta_{s}\leq\kappa\delta-\epsilon$ since
$s^{\prime}_{0}\in\mathcal{B}_{\kappa\delta-\epsilon}(s_{0})$. Now, we want to
find $\lVert a-a_{rand}\rVert$ such that the distance between the goal points
of these trajectories, i.e. in the worst-case scenario, is bounded:

$e^{K_{s}t_{\tau}}(\kappa\delta-\epsilon)+t_{\tau}K_{a}e^{K_{s}t_{\tau}}\lVert
a-a_{rand}\rVert<\kappa\delta.$

After rearranging this formula, we can obtain a bound for $\lVert
a-a_{rand}\rVert$:

$\Delta a=\lVert
a-a_{rand}\rVert<\frac{\kappa\delta-e^{K_{s}t_{\tau}}(\kappa\delta-\epsilon)}{t_{\tau}K_{a}e^{K_{s}t_{\tau}}}.$

Assuming that $a_{rand}$ is drawn out of a uniform distribution, the
probability of choosing the proper action is

$p_{a}=\frac{\zeta_{\lvert\mathcal{S}\rvert}\cdot\frac{\kappa\delta-e^{K_{s}t_{\tau}}(\kappa\delta-\epsilon)}{t_{\tau}K_{a}e^{K_{s}t_{\tau}}}}{\lvert\mathcal{A}\rvert},$
(S4)

where $\zeta_{\lvert\mathcal{S}\rvert}$ is used to account for the degeneracy
in action selection due to the dimensionality of $\mathcal{S}$. We note that
$\epsilon\in(0,\kappa\delta)$ guarantees $p_{a}\geq 0$, thus the probability
is valid. ∎

Equation S4 provides a lower bound for the probability of choosing the
suitable action. The following lemma provides a bound on the probability of
randomly drawing a state that will expand the tree toward the goal.

######  Lemma 3.

Let $s\in\mathcal{S}$ be a state with clearance $\delta$, i.e.
$\mathcal{B}_{\delta}(s)\in\mathcal{S}$. Suppose that for an RRT $\mathbb{T}$
there exists a vertex $v\in\mathbb{T}$ such that
$v\in\mathcal{B}_{2\delta/5}(s)$. Following the definition in Section III-B,
we denote $s_{near}\in\mathbb{T}$ as the closest vertex to $s_{rand}$. The
probability that $s_{near}\in\mathcal{B}_{\delta}(s)$ is at least
$\lvert\mathcal{B}_{\delta/5}(s)\rvert/\lvert S\rvert$.

###### Proof.

Let $s_{rand}\in\mathcal{B}_{\delta/5}(s)$. Therefore the distance between
$s_{rand}$ and $v$ is upper-bounded by $\lVert s_{rand}-v\rVert\leq
3\delta/5$. If there exists a vertex $s_{near}$ such that $s_{near}\neq v$ and
$\lVert s_{rand}-s_{near}\rVert\leq\lVert s_{rand}-v\rVert$, then
$s_{near}\in\mathcal{B}_{3\delta/5}(s_{rand})\subset\mathcal{B}_{\delta}(s)$.
Hence, by choosing $s_{rand}\in\mathcal{B}_{\delta/5}(s)$, we are guaranteed
$s_{near}\in\mathcal{B}_{\delta}(s)$. As $s_{rand}$ is drawn uniformly, the
probability for $s_{rand}\in\mathcal{B}_{\delta/5}(s)$ is at least
$\lvert\mathcal{B}_{\delta/5}(s)\rvert/\lvert S\rvert$. ∎

We can now prove the main theorem.

######  Theorem 1.

Suppose that there exists a valid trajectory $\tau$ from $s_{0}$ to
$\mathcal{S}_{goal}$ as defined in definition 2, with a corresponding
piecewise constant control. The probability that RRT fails to reach
$\mathcal{S}_{goal}$ from $s_{0}$ after $k$ iterations is bounded by
$ae^{-bk}$, for some constants $a,b>0$.

###### Proof.

Lemma 2 puts a bound on the probability to find actions that expand the tree
from one state to another in a given time. As we assume that a valid
trajectory exists, we can assume that the probability defined in Lemma 2 is
non-zero, i.e. $p_{a}>0$, hence:

$\kappa\delta-e^{K_{s}\Delta t}(\kappa\delta-\epsilon)>0,$ (S5)

where we set $\kappa=2/5$ and $\epsilon=5^{-2}$ as was also done in [36]. We
additionally require that $\Delta t$, which is typically defined as an RL
environment parameter, is chosen accordingly so to ensure that Equation (S5)
holds, i.e. $K_{s}\Delta
t<\log\left(\frac{\kappa\delta}{\kappa\delta-\epsilon}\right)$.

We cover $\tau$ with balls of radius
$\delta=\min\\{\delta_{goal},\delta_{clear}\\}$, where
$\mathcal{B}_{\delta_{goal}}\subseteq\mathcal{S}_{goal}$. The balls are spaced
equally in time with the center of the $i^{th}$ ball is in $c_{i}=\tau(\Delta
t\cdot i),\forall i=0:m$, where $m=t_{\tau}/\Delta t$. Therefore,
$c_{0}=s_{0}$ and $c_{m}=s_{goal}$. We now examine the probability of RRT
propagating along $\tau$. Suppose that there exists a vertex
$v\in\mathcal{B}_{2\delta/5}(c_{i})$. We need to bound the probability $p$
that, by taking a random sample $s_{rand}$, there will be a vertex
$s_{near}\in\mathcal{B}_{\delta}(c_{i})$ such that
$s_{new}\in\mathcal{B}_{2\delta/5}(c_{i+1})$. Lemma 3 provides a lower bound
for the probability that $s_{near}\in\mathcal{B}_{\delta}(c_{i})$, given that
there exists a vertex $v\in\mathcal{B}_{2\delta/5}(c_{i})$. The bound is
$\lvert\mathcal{B}_{\delta/5}(s)\rvert/\lvert S\rvert$. Lemma 2 provide a
lower bound for the probability of choosing an an action from $s_{near}$ to
$s_{new}$. This bound is
$\rho\equiv\frac{\zeta_{\lvert\mathcal{S}\rvert}\cdot\frac{\kappa\delta-e^{K_{s}\Delta
t}(\kappa\delta-\epsilon)}{\Delta tK_{a}e^{K_{s}\Delta
t}}}{\lvert\mathcal{A}\rvert}>0$, where we have substituted $t_{\tau}$ with
$\Delta t$. Consequently,
$p\geq(\lvert\mathcal{B}_{\delta/5}(s)\rvert\cdot\rho)/\lvert S\rvert$.

For RRT to recover $\tau$, the transition between consecutive circles must be
repeated $m$ times. This stochastic process can be described as a binomial
distribution, where we perform $k$ trials (randomly choosing $s_{rand}$), with
$m$ successes (transition between circles) and a transition success
probability $p$. The probability mass function of a binomial distribution is
$\Pr(X=m)=\Pr(m;k,p)=\binom{k}{m}p^{m}(1-p)^{k-m}$. We use the cumulative
distribution function (CDF) to represent the upper bound for failure, i.e. the
process was unable to perform $m$ steps, which can be expressed as:

$\Pr(X<m)=\sum_{i=0}^{m-1}\binom{k}{i}p^{i}(1-p)^{k-i}.$ (S6)

Using Chernoff’s inequality we derive the tail bounds of the CDF when $m\leq
p\cdot k$:

$\displaystyle\Pr(X<m)$
$\displaystyle\leq\exp\left(-\frac{1}{2p}\frac{(kp-m)^{2}}{k}\right)$ (S7)
$\displaystyle=\exp\left(-\frac{1}{2}kp+m-\frac{m^{2}}{kp}\right)$ (S8)
$\displaystyle\leq e^{m}e^{-\frac{1}{2}pk}=ae^{-bk}.$ (S9)

In the other case, where $p<m/k<1$, the upper bound is given by [45]:

$\displaystyle\Pr(X<m)$
$\displaystyle\leq\exp\left(-k\mathcal{D}\left({\frac{m}{k}}\parallel
p\right)\right),$ (S10)

where $\mathcal{D}$ is the relative entropy such that

$D\left({\frac{m}{k}}\parallel
p\right)=\frac{m}{k}\log{\frac{\frac{m}{k}}{p}}+(1-\frac{m}{k})\log{\frac{1-\frac{m}{k}}{1-p}}.$

Rearranging $\mathcal{D}$, we can rewrite S10 as follows:

$\displaystyle\Pr(X<m)\leq$ (S11)
$\displaystyle\exp\left(-k\left({\frac{m}{k}}\log\left(\frac{m}{kp}\right)+\frac{k-m}{k}\log\left({\frac{1-\frac{m}{k}}{1-p}}\right)\right)\right)$
(S12)
$\displaystyle=\exp\left(-m\log\left(\frac{m}{kp}\right)\right)\exp\left(-k\log\left(\frac{1-\frac{m}{k}}{1-p}\right)\right)$
(S13)
$\displaystyle\qquad*\exp\left(m\log\left(\frac{1-\frac{m}{k}}{1-p}\right)\right)$
(S14)
$\displaystyle=\exp\left(-m\log\left(\frac{m(1-p)}{kp(1-\frac{m}{k})}\right)\right)$
(S15)
$\displaystyle\qquad*\exp\left(-k\log\left(\frac{1-\frac{m}{k}}{1-p}\right)\right)$
(S16)
$\displaystyle\leq\exp\left(-k\log\left(\frac{1-\frac{m}{k}}{1-p}\right)\right)$
(S17) $\displaystyle\leq\exp\left(-k\log\left(\frac{0.5}{1-p}\right)\right)$
(S18) $\displaystyle\leq e^{-kp}=ae^{-bk},$ (S19)

where (S17) is justified for worst-case scenario where $p=m/k$, (S18) uses the
fact that $p<m/k<0.5$, hence $1-m/k>0.5$. The last step, (S19) is derived from
the first term of the Taylor expansion of
$\log\left(\frac{1}{1-p}\right)=\sum_{j=1}^{\infty}\frac{p^{j}}{j}$.

As $p$ and $m$ are fixed and independent of $k$, we show that the expression
for $\Pr(X<m)$ decays to zero exponentially with $k$, therefore RRT is
probabilistically complete. ∎

It is worth noting that the failure probability $\Pr(X<m)$ depends on problem-
specific properties, which give rise to the values of $a$ and $b$.
Intuitively, $a$ depends on the scale of the problem such as volume of the
goal set $\lvert\mathcal{S}^{RL}_{goal}\rvert$ and how complex and long the
solution needs to be, as evident in Equation (S9). More importantly, $b$
depends on the probability $p$. Therefore, it is a function of the
dimensionality of $\mathcal{S}$ (through the probability of sampling
$s_{rand}$) and other environment parameters such as clearance (defined by
$\delta$) and dynamics (via $K_{s}$, $K_{a}$), as specified in Equation (S4).

##  S3 Experimental setup

All experiments were run using a single $2.2$GHz core and a GeForce GTX 1080
Ti GPU.

###  S3-A Environments

All environments are made available in supplementary code. Environments are
based on Gym [42], with modified sparse reward functions and state spaces. All
environments emit a $-1$ reward per timestep unless noted otherwise. The
environments have been further changed from Gym as follows:

  * •

_Cartpole Swingup_ \- The state space $\mathcal{S}\subseteq\mathbb{R}^{4}$
consists of states $s=\left[x,\theta,\dot{x},\dot{\theta}\right]$ where $x$ is
cart position, $\dot{x}$ is cart linear velocity, $\theta$ is pole angle
(measuring from the $y$-axis) and $\dot{\theta}$ pole angular velocity.
Actions $\mathcal{A}\subseteq\mathbb{R}$ are force applied on the cart along
the $x$-axis. The goal space $\mathcal{S}_{goal}$ is
$\\{s\in\mathcal{S}\mid\cos{\theta}>0.9\\}$. Note that reaching the goal space
does not terminate an episode, but yields a reward of $\cos{\theta}$. Time
horizon is $H=500$. Reaching the bounds of the rail does not cause failure but
arrests the linear movement of the cart.

  * •

_MountainCar_ \- The state space $\mathcal{S}\subseteq\mathbb{R}^{2}$ consists
of states $s=\left[x,\dot{x}\right]$ where $x$ is car position and $\dot{x}$
is car velocity. Actions $\mathcal{A}\subseteq\mathbb{R}$ are force applied by
the car engine. The goal space $\mathcal{S}_{goal}$ is $\\{s\in\mathcal{S}\mid
x\geq 0.45\\}$. Time horizon is $H=200$.

  * •

_Acrobot_ \- The state space $\mathcal{S}\subseteq\mathbb{R}^{4}$ consists of
states
$s=\left[\theta_{0},\theta_{1},\dot{\theta_{0}},\dot{\theta_{1}}\right]$ where
$\theta_{0},\theta_{1}$ are the angles of the joints (measuring from the
$y$-axis and from the vector parallel to the $1^{st}$ link, respectively) and
$\dot{\theta_{0}},\dot{\theta_{1}}$ are their angular velocities. Actions
$\mathcal{A}\subseteq\mathbb{R}$ are torque applied on the $2^{nd}$ joint. The
goal space $\mathcal{S}_{goal}$ is
$\\{s\in\mathcal{S}\mid-\cos{\theta_{0}}-\cos{(\theta_{0}+\theta_{1})}>1.9\\}$.
In other words, the set of states where the end of the second link is at a
height $y>1.9$. Time horizon is $H=500$.

  * •

_Pendulum_ \- The state space $\mathcal{S}\subseteq\mathbb{R}^{2}$ consists of
states $s=\left[\theta,\dot{\theta}\right]$ where $\theta$ is the joint angle
(measured from the $y$-axis) and $\dot{\theta}$ is the joint angular velocity.
Actions $\mathcal{A}\subseteq\mathbb{R}$ are torque applied on the joint. The
goal space $\mathcal{S}_{goal}$ is
$\\{s\in\mathcal{S}\mid\cos{\theta}>0.99\\}$. Note that reaching the goal
space does not terminate an episode, but yields a reward of $\cos{\theta}$.
Time horizon is $H=100$.

  * •

_Reacher_ \- The state space $\mathcal{S}\subseteq\mathbb{R}^{6}$ consists of
states
$s=\left[\theta_{0},\theta_{1},x,y\dot{\theta_{0}},\dot{\theta_{1}}\right]$
where $\theta_{0},\theta_{1}$ are the angles of the joints, $(x,y)$ are the
coordinates of the target and $\dot{\theta_{0}},\dot{\theta_{1}}$ are the
joint angular velocities. Actions $\mathcal{A}\subseteq\mathbb{R}^{2}$ are
torques applied at the $2$ joints. The goal space $\mathcal{S}_{goal}$ is the
set of states where the end-effector is within a distance of $0.01$ from the
target. Time horizon is $H=50$.

  * •

_Fetch Reach_ \- A high-dimensional robotic task where the state space
$\mathcal{S}\subseteq\mathbb{R}^{13}$ consists of states
$s=[gripper\\_pos,finger\\_pos,gripper\\_state,$ $finger\\_state,goal\\_pos]$
where the Cartesian coordinates and velocities of the Fetch robot’s gripper
are $gripper\\_pos$ and $gripper\\_vel$, and $finger\\_state$ and
$finger\\_vel$ are the two-dimensional position and velocity of the gripper
fingers, and $goal\\_pos$ are the Cartesian coordinates of the goal. Actions
$\mathcal{A}\subseteq\mathbb{R}^{4}$ are relative target positions of the
gripper and fingers, which the MuJoCo controller will try to achieve. The goal
space $\mathcal{S}_{goal}$ is the set of states where the end-effector is
within a distance of $0.05$ from $goal\\_pos$. Time horizon is $H=50$. Note
that this problem is harder than the original version in OpenAI Gym, as we
only sample $goal\\_pos$ that are far from the gripper’s initial position.

  * •

_Hand Reach_ \- A high-dimensional robotic task where the state space
$\mathcal{S}\subseteq\mathbb{R}^{78}$ consists of states
$s=\left[joint\\_pos,joint\\_vel,fingertip\\_pos,goal\\_pos\right]$ where
$joint\\_pos,joint\\_vel$ are the angles and angular velocities of the Shadow
hand’s $24$ joints, $fingertip\\_pos$ are the Cartesian coordinates of the $5$
fingertips, and $goal\\_pos$ are the Cartesian coordinates of the goal
positions for each fingertip. Actions $\mathcal{A}\subseteq\mathbb{R}^{20}$
are absolute target angles of the $20$ controllable joints, which the MuJoCo
controller will try to achieve. The goal space $\mathcal{S}_{goal}$ is the set
of states where all fingertips are simultaneously within a distance of $0.02$
from their respective goals. Time horizon is $H=50$.

###  S3-B Theoretical solvers

LfD algorithms typically use demonstrations from a human demonstrator, a
previously learned policy, or a theoretical solver. In order to generate
expert demonstrations of this type for Figure 4, we used the following
solvers:

  * •

_MountainCar_ \- The solver is simply the policy

$a=\text{sgn}(\dot{x}).$ (S20)

This will pump the maximum possible energy into the system at every time step.
Although this solver overshoots slightly, it is guaranteed to solve the
problem and is in practice very close to optimal.

  * •

_Pendulum_ \- The solver is the policy

$a=\text{sgn}(\dot{\theta})\cdot e_{goal}(s)-e_{total}(s),$ (S21)

where $e_{total}$ is the total energy of the system in state $s$ and
$e_{goal}$ is the total energy of the system in the goal state $(0,0)$. This
policy is able to arrive at the upright position with low velocity. Note that
the P2D2 algorithm does not have velocity information in its goal space, so
this comparison unfairly favours the theoretical solver.

  * •

_Acrobot_ \- We used the solver described by [46].

###  S3-C Experimental setup and hyper-parameter choices

All experiments feature a policy with $2$ fully-connected hidden layers of
$32$ units each with tanh activation, with the exception of _Reacher_ , for
which a policy network of $4$ fully-connected hidden layers of $128$ units
each with relu activation is used. For all environments we use a linear
feature baseline for TRPO.

Default values are used for most hyperparameters. A discount factor of
$\gamma=0.99$ is used in all environments. For VIME, hyperparameters values
reported in the original paper are used, and the implementation published by
the authors was used.

For TRPO, default hyperparameter values and implementation from Garage are
used: KL divergence constraint $\delta=10^{-2}$, and Gaussian action noise
$\mathcal{N}(0,0.3^{2})$.

In comparisons with VIME-TRPO and vanilla TRPO, the P2D2 goal sampling
probability $p_{g}$ is set to $0.05$, as proposed in [47]. Goal sets
$\mathcal{S}_{goal}$ are defined in Appendix S3-A for each environment. In all
experiments, the local policy $\pi_{l}$ learned by P2D2 is an approximate
Gaussian process, combining Bayesian linear regression with prior precision
$0.1$ and noise precision $1.0$, with $300$ random Fourier features [48]
approximating a square exponential kernel with lengthscale $0.3$.


11institutetext: Leiden University, Leiden, the Netherlands 11email:
<EMAIL_ADDRESS>11email<EMAIL_ADDRESS>11email:
<EMAIL_ADDRESS>11email<EMAIL_ADDRESS>
# Answer Retrieval in
Legal Community Question Answering

Arian Askari  0000-0003-4712-832X Zihui Yang  Zhaochun Ren
0000-0002-9076-6565 Suzan Verberne  0000-0002-9609-9505

###### Abstract

The task of answer retrieval in the legal domain aims to help users to seek
relevant legal advice from massive amounts of professional responses. Two main
challenges hinder applying existing answer retrieval approaches in other
domains to the legal domain: (1) a huge knowledge gap between lawyers and non-
professionals; and (2) a mix of informal and formal content on legal QA
websites. To tackle these challenges, we propose CEFS, a novel cross-encoder
(CE) re-ranker based on the fine-grained structured inputs. CEFS uses
additional structured information in the CQA data to improve the effectiveness
of cross-encoder re-rankers. Furthermore, we propose LegalQA: a real-world
benchmark dataset for evaluating answer retrieval in the legal domain.
Experiments conducted on LegalQA show that our proposed method significantly
outperforms strong cross-encoder re-rankers fine-tuned on MS MARCO. Our novel
finding is that adding the question tags of each question besides the question
description and title into the input of cross-encoder re-rankers structurally
boosts the rankers’ effectiveness. While we study our proposed method in the
legal domain, we believe that our method can be applied in similar
applications in other domains.

###### Keywords:

Legal Answer Retrieval Legal IR Data collection Fine-grained structured cross-
encoder

##  1 Introduction

As an established problem in information retrieval, answer111We
interchangeably use the word answer and response to refer to the content
written by the professional lawyer. retrieval [6] has been studied in a
variety of domains, including healthcare [8], social media [6, 30], and
programming [32]. Community question answering (CQA) platforms provide common
sources for answer retrieval [23, 5, 24], e.g.,
Stackoverflow222https://stackoverflow.com/ for finding answers of programming
questions [5]. In the legal domain, users333We refer to the person who posts a
question as a user or questioner throughout this paper. seek legal advice from
professionals, and timely access to accurate answers is important. Legal
language, often considered a sub-language due to its distinct characteristics,
emphasizes the importance of answer retrieval in the legal domain [10, 28,
26]. However, answer retrieval has not been addressed in the legal domain yet.

In this paper, we propose the task of legal answer retrieval. We start by
analyzing the effectiveness of the widely used two-stage ranking pipeline [3],
which consists of an efficient retriever, e.g., BM25 [21], to retrieve a
shortlist of documents from the collection, and a re-ranker [18] to increase
the effectiveness of the initial ranking. On this premise, we propose cross-
encoderCAT (CECAT), which uses cross-encoders for optimizing the re-ranking
stage by concatenating the query and the candidate document in the input [3].
Given a new question and the corresponding initial ranked list produced by
BM25, the CECAT aims to effectively reorder the candidate documents from the
initial ranked list to locate the most relevant responses on top of the ranked
list. We fine-tune a cross-encoder re-ranker, called CEFS, based on our novel
fine-grained structured inputs to learn the relevance between a pair of a
question and its best answer based on structured information from the data;
such a model would be able to effectively re-rank prior existing relevant
responses where the best answer is not provided [31].

Our proposed method is inspired by recent studies that have shown task-level
input modification could improve the effectiveness of cross-encoder re-
rankers. For instance, BERT-FP [11] has shown that adding splitter tokens
between each utterance of a dialogue can improve the effectiveness of BERT-
based re-rankers. We are also motivated by the fact that, in legal CQA,
question tags consist of important legal terms related to the legal question
and using them can potentially bridge the knowledge gap between lawyer content
and questioner content. It is noteworthy to mention that question tags are
dynamically generated by the online platform that we have used in this paper.

For the first attempt, we release a new benchmark dataset, namely LegalQA, in
this paper. Each question in LegalQA has a corresponding best answer selected
by the questioner 444https://github.com/arian-askari/AnswerRetrieval-Legal. It
consists of 9,846 questions and 33,670 answers responses by identified
lawyers, organized in train, validation, and test splits. Our experiments on
LegalQA show that CEFS significantly outperforms regular and strong fine-tuned
cross-encoder re-rankers such as MiniLM-MSMARCO [25] which is a highly
effective cross-encoder re-ranker trained on MS MARCO [17].

Our contributions are as follows: (1) We formulate the task of answer
retrieval in the legal domain and release LegalQA. As far as we know, this is
the first benchmark test collection for legal answer retrieval. (2) We
evaluate the applicability of both probabilistic and existing effective fine-
tuned cross-encoder re-rankers on legal answer retrieval. (3) We propose CEFS
taking into account the different elements of a legal question with a fine-
grained structured input that significantly outperforms regular fine-tuning
cross-encoder re-rankers and the strong cross-encoder re-ranker trained on MS
MARCO.

##  2 Related work

The objective of answer retrieval is to find the most relevant response given
a question, which aligns with the core retrieval objective [31, 23, 5, 24, 6,
30, 32]. Therefore, the effective CECAT re-rankers are suitable to be invested
in this task as they have shown high effectiveness in addressing various core
retrieval tasks [18, 1, 12, 20]. Several studies have shown the impact of
modifying the regular input of CECAT could improve their effectiveness such as
[11, 2, 3, 7]. However, there are no studies that investigated the usage of
question tags to improve cross-encoder re-rankers in community question-
answering systems. The most relevant work to this study is the recent work by
[15] that investigates the effectiveness of existing methods on legal CQA
data. However, the responses in that work are written by legal forum users
rather than identified lawyers, and they do not improve the effectiveness of
existing methods for this particular domain. They also included the fine-tuned
MiniLM on MS Marco [25] in their study and showed its poor performance in the
legal domain. Furthermore, Martinez-Gil et al. [16] explore potential future
directions for legal answering systems in a survey on legal systems designed
for lawyers or law students including statute law retrieval and task legal
textual entailment tasks. In contrast, our focus is on answer retrieval in a
legal community question-answering system with a combination of legal language
by lawyers and everyday language by questioners who ask questions.

Figure 1: Fine-grained structured input of CEFS

##  3 Methods

We present our method, CEFS, as an effective cross-encoder based re-ranker for
the question answering retrieval in the legal domain. Our retrieval pipeline
consists of first-stage retrieval and re-ranking. For a user’s questions, the
first-stage retrieval returns a set of initial responses from the dataset.
These results are then re-ranked in the second step to improve the
effectiveness of retrieval.

Collected dataset for the task. We create the LegalQA dataset by using the
question URLs shared by [4] to investigate expert finding in the legal domain.
In the context of the expert finding task, the input consists solely of
specific question tags, and the output is a list of experts about that
specific question tag. In contrast, in answer retrieval, the standard input is
the question’s content, and the desired output is the most suitable answer to
that question. We therefore create a new dataset, LegalQA based on the expert
finding data. The LegalQA dataset is derived from a subset of the ‘bankruptcy’
related forum on Avvo555https://www.avvo.com/topics/bankruptcy in California,
spanning from January 2008 to July 2021, and comprises 9,846 questions by
regular users and 33,670 answers by certified lawyers. Notably, lawyers’
profiles on Avvo are associated with their real names, distinguishing them
from regular users. The questions are categorized, and each category, such as
‘bankruptcy,’ includes questions with different category tags, for instance,
‘bankruptcy homestead exemption’. Following [4], we determine a question’s
best answer based on whether it is selected as the most helpful by the
questioner or if it receives “lawyer agree” votes from at least three
certified lawyers, which is distinct from the “helpful” upvotes provided by
other users. To facilitate model training and evaluation, we split the dataset
into three subsets: 70% for training, 10% for validation, and 20% for testing,
based on the chronological order of questions. To ensure the dataset’s
integrity and eliminate duplicates, we perform a lexical similarity analysis
using Levenshtein distance [14] on all the questions666We use the
implementation available at https://github.com/seatgeek/thefuzz. This analysis
identified 50 pairs of questions with more than a 90% overlap. In cases of
high overlap between question pairs, we retain the longer question and discard
the shorter one. Additionally, we reassign the responses from the removed
question to the retained one.

Baselines. For the first-stage retrieval, we employ BM25 as the baseline
method. Additionally, we compare BM25 to a lexical-based probabilistic first-
stage retriever named LMD[19] to assess the effectiveness of BM25 compared to
another lexical-based retrieval. We leave out investigating the effectiveness
of Transformer-based first-stage retrievers, e.g., dense retrievers, since we
focus on improving the effectiveness of the re-ranking stage of answer
retrieval in the legal domain. We leave further analysis on Transformer-based
first-stage retrievers to future work. For the re-ranking, we use cross-
encoder re-rankers (CECAT) in different settings: (1) a fine-tuned cross-
encoder on MS MARCO; (2) a fine-tuned cross-encoder on the LegalQA training
set; (3) a pre-trained cross-encoder as the zero-shot baseline.

BM25 and LMD. We use BM25 as first stage retriever, a commonly used ranking
function that efficiently retrieves a set of documents from the full document
collection based on word overlap [22, 9].

CECAT. We use CECAT as a strong re-ranker. The query q1:m and answer content
a1:n sequences are concatenated with the [SEP] token, and the [CLS] token
representation computed by CE is scored with a single linear layer W in the
CECAT ranking model:
$CE_{CAT}(q_{1:m},a_{1:n})=CE([CLS]\,q\,[SEP]\,a\,[SEP])*W$. We evaluate fine-
tuned both MS MARCO-trained CECAT, MiniLM-MSMARCO[25], and LegalQA-trained
CECAT following by the above design. We use MiniLM [27] as the cross-encoder
model thorough all of the experiments.

Proposed method: Cross-encoderFS (CEFS). We propose CEFS in order to capture
the relevance within the question and best answer based on a fine-grained
structural-based input representation tailored for cross-encoder re-rankers.
In Figure 1, we present the input representation of CEFS, which is formally
explained as follows:

$CE_{FS}(q_{1:m},a_{1:n})=CE([CLS]\,q_{Subject}\,[S]\,q_{Description}\,[D]\,q_{Tags}\,[T]\,[SEP]\,a\,[SEP])*W$

(1)

Here, the [S], [D], and [T] tokens serve as separators, i.e., splitter tokens,
for different parts of the question, namely Subject, Description, and Category
tags, respectively. The input representation of CEFS is designed to take into
account different aspects of the retrieval context. The novelties brought by
CEFS can be summarized in two key aspects:

  * •

Structured Input. CEFS employs structured input by dividing the question into
distinct sections – the subject, description, and tags. These sections are
separated by splitter tokens. Such structuring not only facilitates a more
comprehensive representation of the query but also emphasizes the importance
of individual sections to the re-ranker since the cross-encoder in CEFS can
comprehend different aspects of the information and assign varying levels of
importance to each section of the question.

  * •

Question Tags. CEFS takes the question tags into account in a straightforward
yet effective manner by incorporating them into the cross-encoder re-ranker’s
input. Each question tag is separated by a semicolon. The motivation behind
these additions is to equip the re-ranker with more comprehensive knowledge
about the query, enabling it to grasp both an overview of the legal question’s
topic and its detailed category tags.

##  4 Experiments and results

Table 1: Effectiveness results. $\dagger$ denotes a statistically significant
improvement of CEFS over the second most effective re-ranker, CECAT fine-tuned
on the LegalQA training set. Statistical significance was measured with a
paired t-test ($p<0.001$) with Bonferroni correction for multiple testing. All
re-rankers used top-1000 retrieved answers by BM25 as the initial ranking.

Training source |  Model |  MAP@1k |  R@1k |  R@100 |  R@10 |  R@2 |  R@1
---|---|---|---|---|---|---|---
First-stage retrievers
— |  BM25 | .120 | .542 | .354 | .192 | .113 | .069
— |  LMD | .080 | .540 | .321 | .153 | .840 | .050
Cross-encoder re-rankers
MS MARCO |  CECAT | .109 | .542 | .341 | .173 | .101 | .087
LegalQA (ours) |  CECAT | .236 | .542 | .495 | .381 | .204 | .181
LegalQA (ours) |  CEFS (ours) | .270$\dagger$ | .542 | .524$\dagger$ | .428$\dagger$ | .261$\dagger$ | .209$\dagger$

Experimental setup. We use the Huggingface library [29] for the cross-encoder
re-ranking training and inference. We add the splitter tokens into the
tokenizer of the cross-encoder. Following prior work [12] we use Cross-Entropy
loss [33], training batch size of 32, and Adam [13] optimizer with a learning
rate of $7*10^{-6}$ for all cross-encoder layers, regardless of the number of
layers trained.

Ranking quality. Table 1 illustrates the effectiveness of lexical-based first-
stage retrievers and cross-encoder re-rankers. For re-ranking, our proposed
method, CEFS, demonstrates significant improvements over both CECAT fine-tuned
on the LegalQA dataset and CECAT trained on MS MARCO, referred to as MiniLM-
MSMARCO [25]. E.g., in terms of MAP@1k, CEFS achieves 0.270 vs. 0.236 for
CECAT and 0.109 for MiniLM-MSMARCO. The higher effectiveness of CEFS over the
CECAT confirms the effectiveness of the proposed method, and the low
performance of MiniLM-MSMARCO on LegalQA confirms the challenges of the legal
domain since MiniLM-MSMARCO achieves a three times higher effectiveness on MS
MARCO dataset in terms of MAP@1k. Among the first-stage retrievers, BM25
outperforms LMD in terms of initial ranking effectiveness. The relatively low
effectiveness of BM25 reveals a noticeable difference in lexical word overlap
between the question and the best answer. This difference serves as an
indicator of a knowledge gap between the questioner and the lawyer, resulting
in a higher occurrence of lexical mismatches between the question and the
relevant answer. Achieving a higher overall effectiveness in this task is a
potential area for improvement in future works.

Table 2: Results of the ablation study on CEFS.

Model | MAP@1k | R@100 | R@10 | R@1
---|---|---|---|---
CEFS w/o [T] splitter and query tags | .252 | .510 | .405 | .163
CEFS w/o [S] splitter and question subject | .239 | .498 | .379 | .154
CEFS w/o [D] splitter and question description | .191 | .461 | .315 | .119
CEFS | .270 | .524 | .428 | .209

Ablation study. We do an ablation study on the CEFS to analyze to what extent
each section of the fine-grained structured input of CEFS has an impact on the
effectiveness of CEFS. As shown in Table 2, the effectiveness of CEFS is
highest when we use all of the splitter and corresponding contents. We see
that query tags and [T] splittor have less impact on the effectiveness and
question description and [D] has the highest impact. Question subject and [S]
have the second-highest impact. This suggests that although the query tags
have a role in improved effectiveness, question subject and description have
still a large impact on the effectiveness.

##  5 Conclusion

For investigating answer retrieval in legal community question answering, we
created a dedicated dataset, called LegelQA, which we divide into training,
validation, and test sets. We use this dataset to train neural retrieval
models, introducing a novel and highly effective re-ranker called CEFS, and
take a fine-grained structured approach to leverage the information available
in the legal domain, demonstrating significantly higher effectiveness over
common strong cross-encoder re-rankers. We investigate the impact of each part
of the fine-grained structured input within our method and highlight the
significant role played by question tags in improving retrieval effectiveness
besides the most important part of the question which is question description.
While our method is initially proposed for answer retrieval within the legal
domain, we foresee its potential application in answer retrieval for community
question-answering systems across various domains where question tags are
provided alongside each question post. For future work, our data, LegalQA,
facilitates other tasks such as legal response generation.

## ACKNOWLEDGMENTS

This work was supported by the EU Horizon 2020 ITN/ETN on Domain Specific
Systems for Information Extraction and Retrieval (H2020-EU.1.3.1., ID:
860721).

## References

  * [1] Abolghasemi, A., Verberne, S., Azzopardi, L.: Improving bert-based query-by-document retrieval with multi-task optimization. In: Advances in Information Retrieval: 44th European Conference on IR Research, ECIR 2022, Stavanger, Norway, April 10–14, 2022, Proceedings, Part II. pp. 3–12. Springer (2022)
  * [2] Askari, A., Abolghasemi, A., Aliannejadi, M., Kanoulas, E., Verberne, S.: Closer: Conversational legal longformer with expertise-aware passage response ranker for long contexts. In: The 32nd ACM International Conference on Information and Knowledge Management (CIKM 2023). ACM (2023)
  * [3] Askari, A., Abolghasemi, A., Pasi, G., Kraaij, W., Verberne, S.: Injecting the BM25 score as text improves BERT-based re-rankers. In: Advances in Information Retrieval. pp. 66–83. Springer Nature Switzerland, Cham (2023)
  * [4] Askari, A., Verberne, S., Pasi, G.: Expert finding in legal community question answering. In: Hagen, M., Verberne, S., Macdonald, C., Seifert, C., Balog, K., Nørvåg, K., Setty, V. (eds.) Advances in Information Retrieval. pp. 22–30. Springer International Publishing, Cham (2022)
  * [5] Atkinson, J., Figueroa, A., Andrade, C.: Evolutionary optimization for ranking how-to questions based on user-generated contents. Expert Systems with Applications 40(17), 7060–7068 (2013)
  * [6] Bian, J., Liu, Y., Agichtein, E., Zha, H.: Finding the right facts in the crowd: factoid question answering over social media. In: Proceedings of the 17th international conference on World Wide Web. pp. 467–476 (2008)
  * [7] Boualili, L., Moreno, J.G., Boughanem, M.: Markedbert: Integrating traditional ir cues in pre-trained language models for passage retrieval. In: Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval. pp. 1977–1980 (2020)
  * [8] Budler, L.C., Gosak, L., Stiglic, G.: Review of artificial intelligence-based question-answering systems in healthcare. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 13(2), e1487 (2023)
  * [9] Chen, T., Zhang, M., Lu, J., Bendersky, M., Najork, M.: Out-of-domain semantics to the rescue! zero-shot hybrid retrieval models. In: Advances in Information Retrieval. pp. 95–110. Springer International Publishing, Cham (2022)
  * [10] Haigh, R.: Legal English. Routledge (2018)
  * [11] Han, J., Hong, T., Kim, B., Ko, Y., Seo, J.: Fine-grained post-training for improving retrieval-based dialogue systems. In: Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. pp. 1549–1558 (2021)
  * [12] Hofstätter, S., Althammer, S., Schröder, M., Sertkan, M., Hanbury, A.: Improving efficient neural ranking models with cross-architecture knowledge distillation. arXiv preprint arXiv:2010.02666 (2020)
  * [13] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
  * [14] Levenshtein, V.: Binary codes capable of correcting deletions, insertions and reversals. In: Soviet Physics-Doklady. vol. 10, pp. 707–710 (1966)
  * [15] Mansouri, B., Campos, R.: Falqu: Finding answers to legal questions. arXiv preprint arXiv:2304.05611 (2023)
  * [16] Martinez-Gil, J.: A survey on legal question–answering systems. Computer Science Review 48, 100552 (2023)
  * [17] Nguyen, T., Rosenberg, M., Song, X., Gao, J., Tiwary, S., Majumder, R., Deng, L.: Ms marco: A human generated machine reading comprehension dataset. In: CoCo@ NIPs (2016)
  * [18] Nogueira, R., Cho, K.: Passage re-ranking with bert. arXiv preprint arXiv:1901.04085 (2019)
  * [19] Ponte, J.M., Croft, W.B.: A language modeling approach to information retrieval. In: ACM SIGIR Forum. vol. 51, pp. 202–208. ACM New York, NY, USA (2017)
  * [20] Rau, D., Kamps, J.: The role of complex nlp in transformers for text ranking. In: Proceedings of the 2022 ACM SIGIR International Conference on Theory of Information Retrieval. pp. 153–160 (2022)
  * [21] Robertson, S.E., Walker, S.: Some simple effective approximations to the 2-poisson model for probabilistic weighted retrieval. In: SIGIR’94. pp. 232–241. Springer (1994)
  * [22] Robertson, S.E., Walker, S.: Some simple effective approximations to the 2-poisson model for probabilistic weighted retrieval. In: SIGIR’94. pp. 232–241. Springer (1994)
  * [23] Roy, P.K., Ahmad, Z., Singh, J.P., Alryalat, M.A.A., Rana, N.P., Dwivedi, Y.K.: Finding and ranking high-quality answers in community question answering sites. Global Journal of Flexible Systems Management 19, 53–68 (2018)
  * [24] Roy, P.K., Saumya, S., Singh, J.P., Banerjee, S., Gutub, A.: Analysis of community question-answering issues via machine learning and deep learning: State-of-the-art review. CAAI Transactions on Intelligence Technology 8(1), 95–117 (2023)
  * [25] Sentence-BERT: Cross-encoder for ms marco: ms-marco-minilm-l-12-v2 (October 2023), https://huggingface.co/cross-encoder/ms-marco-MiniLM-L-12-v2
  * [26] Tiersma, P.M.: Legal language. University of Chicago Press (1999)
  * [27] Wang, W., Wei, F., Dong, L., Bao, H., Yang, N., Zhou, M.: Minilm: Deep self-attention distillation for task-agnostic compression of pre-trained transformers. Advances in Neural Information Processing Systems 33, 5776–5788 (2020)
  * [28] Williams, C.: Tradition and change in legal English: Verbal constructions in prescriptive texts, vol. 20. Peter Lang (2007)
  * [29] Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, A., Cistac, P., Rault, T., Louf, R., Funtowicz, M., et al.: Huggingface’s transformers: State-of-the-art natural language processing. arXiv preprint arXiv:1910.03771 (2019)
  * [30] Xiong, W., Wu, J., Wang, H., Kulkarni, V., Yu, M., Chang, S., Guo, X., Wang, W.Y.: Tweetqa: A social media focused question answering dataset. arXiv preprint arXiv:1907.06292 (2019)
  * [31] Yang, W., Xie, Y., Lin, A., Li, X., Tan, L., Xiong, K., Li, M., Lin, J.: End-to-end open-domain question answering with bertserini. arXiv preprint arXiv:1902.01718 (2019)
  * [32] Yen, S.J., Wu, Y.C., Yang, J.C., Lee, Y.S., Lee, C.J., Liu, J.J.: A support vector machine-based context-ranking model for question answering. Information Sciences 224, 77–87 (2013)
  * [33] Zhang, Z., Sabuncu, M.: Generalized cross entropy loss for training deep neural networks with noisy labels. Advances in neural information processing systems 31 (2018)