# Unsupervised Distractor Generation via Large Language Model Distilling and
Counterfactual Contrastive Decoding

Fanyi Qu Hao Sun Yunfang Wu
National Key Laboratory for Multimedia Information Processing, Peking
University
MOE Key Laboratory of Computational Linguistics, Peking University
School of Computer Science, Peking University
<EMAIL_ADDRESS>Corresponding author.

###### Abstract

Within the context of reading comprehension, the task of Distractor Generation
(DG) aims to generate several incorrect options to confuse readers.
Traditional supervised methods for DG rely heavily on expensive human-
annotated distractor labels. In this paper, we propose an unsupervised DG
framework, leveraging Large Language Models (LLMs) as cost-effective
annotators to enhance the DG capability of smaller student models. Specially,
to perform knowledge distilling, we propose a dual task training strategy that
integrates pseudo distractors from LLMs and the original answer information as
the objective targets with a two-stage training process. Moreover, we devise a
counterfactual contrastive decoding mechanism for increasing the distracting
capability of the DG model. Experiments show that our unsupervised generation
method with Bart-base greatly surpasses GPT-3.5-turbo performance with only
200$\times$ fewer model parameters. Our proposed unsupervised DG method offers
a cost-effective framework for practical reading comprehension applications,
without the need of laborious distractor annotation and costly large-size
models.

Unsupervised Distractor Generation via Large Language Model Distilling and
Counterfactual Contrastive Decoding

Fanyi Qu Hao Sun Yunfang Wu††thanks:  Corresponding author. National Key
Laboratory for Multimedia Information Processing, Peking University MOE Key
Laboratory of Computational Linguistics, Peking University School of Computer
Science, Peking University<EMAIL_ADDRESS>

##  1 Introduction

Reading comprehension assessment holds significant importance in the
educational field. Typically, a reading comprehension sample consists of four
components: passage, question, answer and multiple distractors. In recent
years, while the cloze-style Distractor Generation (DG) task has received wide
interest Ren and Zhu (2021); Chiang et al. (2022); Wang et al. (2023), the DG
task with complete long sentences is less addressed, primarily due to a
scarcity of available supervised data.

Limited by the expensive annotation cost, there are just a few reading
comprehension datasets for DG from examination scene Lai et al. (2017); Sun et
al. (2019). Methods on these single-sourcing datasets Gao et al. (2019); Zhou
et al. (2020) all face challenges of insufficient generalization in real-world
applications. On the other hand, unsupervised generation methods remain
inaccessible considering the difficulty brought by the reading comprehension
context.

Figure 1: Performance of different unsupervised methods generating 3
distractors on two datasets. We also display results with the supervised Bart-
base model for comparison.

Recently, LLMs like GPT OpenAI (2023) and LLaMa Touvron et al. (2023) have
demonstrated powerful ability as automatic annotators to label training data
Arora et al. (2022); Gilardi et al. (2023). LLMs have been successfully
applied in various fields of NLP, including multi-choice question-answering
task Bitew et al. (2023); Nasution (2023); Doughty et al. (2024). However,
compared to previous fine-tuned methods, mainstream LLMs often fail to achieve
a satisfactory performance on DG, as illustrated in Figure 1. Additionally,
deploying LLMs in real world applications is challenging due to their
substantial computational resource requirements and the closed-source model
parameters.

To meet the high need of DG for real applications, where there are no
distractor labelling data and only limited computational resource, we propose
an unsupervised DG framework with a small model. We adopt the distilling
paradigm to enhance the smaller student model’s generation capability with
pseudo labels from LLMs Smith et al. (2022); Arora et al. (2022), regarding
LLMs as data annotators to assist the training of the smaller model Wang et
al. (2021). Recognizing the suboptimal performance of LLMs on DG, we propose a
dual task training strategy by integrating both pseudo distractors and golden
answers as training targets. Furthermore, we devise a two-stage training
framework to reduce the negative impact caused by the conflict semantics
presented in answers and distractors. Note that we do not use the reference
distractors for the unsupervised setting.

The utilization of answer information as training target, although improves
the model’s performance in generation quality, makes harm to the
counterfactual capability of the generative model. To address this issue, we
introduce contrastive decoding Li et al. (2023) into the inference process of
DG. Specifically, we penalize factual text patterns favored by the answer
generation module while encourage counterfactual results generated by the
distractor generation agent. Additionally, we apply plausibility constraint to
restrict the effect of contrastive decoding for more stable generation
results. Note that we do not leverage LLMs during inference to ensure an easy
deployment in real applications.

We conduct experiments on RACE Lai et al. (2017) and Dream Sun et al. (2019).
As illustrated in Figure 1, our unsupervised method with Bart-base
significantly outperforms zero-shot LLMs with 200$\times$ fewer model
parameters. Experimental results also show that our proposed counterfactual
contrastive decoding method greatly improves the distracting capability of the
generation model. Moreover, we leverage GPT-4 OpenAI (2023) to evaluate the
generated distractors, demonstrating that our method obtains a better
performance than GPT-3.5-turbo both in generation quality and distracting
level.

To sum up, our contributions are as follows:

  * •

We propose an unsupervised DG framework with dual task training, integrating
the original answer information and pseudo distractors generated by LLMs.

  * •

We devise a new counterfactual contrastive decoding method to improve the
distracting level of generated outputs. The proposed optimization can be
transferred to other counterfactual generation tasks.

  * •

Our method greatly outperforms teacher LLMs across various evaluation metrics.
Our method provides a valuable approach for constructing reading comprehension
data in diverse real-world applications, eliminating the need for costly
human-annotated data and large-size models.

##  2 Related Work

###  2.1 Distractor Generation

Previous researches on distractor generation in reading comprehension mostly
concentrate on designing attention framework based on end-to-end models Gao et
al. (2019). Co-attention Zhou et al. (2020) and reforming modules Qiu et al.
(2020) among passage, question and answer are proposed to extract key
information about question-related and counterfactual details. Besides,
Mixture of Expert is utilized in some works to ensure the quality and
diversity of the generation results Qiu et al. (2020); Qu et al. (2023).

Recently, DG studies with LLMs mostly focus on knowledge-based distractor
generation in education field. Bitew et al. (2023) explores question-
similarity based example selection method to enhance LLMs’ DG performance in
in-context learning. Doughty et al. (2024) designs complex prompt to generate
multi-choice question answering data for Python programming learning. Nasution
(2023) asks ChatGPT to construct multi-choice data with the input of biology
subject for biology learning.

Figure 2: Overview of our proposed unsupervised distractor generation
framework, which can be divided into two parts: pseudo distractor generation
and dual task training.

###  2.2 LLM Knowledge Distillation

LLMs have been widely applied to generate pseudo labels to reduce the labeling
cost in unsupervised situation. Recent works have proved the effectiveness of
LLMs in annotating accuracy compared to human-annotated results in various NLP
tasks Gilardi et al. (2023); He et al. (2023). Related works have already been
applied in question answering Saad-Falcon et al. (2023), information retrieval
Bonifacio et al. (2022), text summarization Wang et al. (2021) and common
sense reasoning Whitehouse et al. (2023) , covering both NLU and NLG fields.

Similar unsupervised methods are still under-explored in DG task, though
previous works suffer from the expensive labeling cost. Addressing this gap is
the main target of our paper.

##  3 Method

###  3.1 Task Definition

The reading comprehension data generally consists of four components: passage,
question, answer and multiple distractors. In this context, the DG model
regards the triplet of passage($p$), question($q$) and answer($a$) as input
and generates results with a probability of $p_{d}$:

$p_{d}=p(d_{i}|p,q,a,d_{<i})$ (1)

In this work, we propose an unsupervised framework for DG task, where the
reference distractors in the training data are unseen but only the
passage($p$), question($q$) and answer($a$) are provided. In this way, we
would liberate experts from the laborious work of distractor annotation.

An overview of our unsupervised framework is displayed in Figure 2. We first
apply LLM as a teacher model to generation pseudo distractors. Next, we train
a smaller student model with both pseudo labels and answers as generating
targets through a two-stage training process.

###  3.2 Generating Distractors with LLMs

Previous works on DG task Gao et al. (2019); Zhou et al. (2020) mostly depend
on human-annotated data. The common-used dataset like RACE Lai et al. (2017)
is sourced from the educational domain and annotated by professional teachers,
exhibiting a high quality but expensive cost. The powerful generation
capability of LLMs presents a chance for DG task in reading comprehension to
overcome the problem of limited data.

Instead of utilizing human-annotated distractors, we obtain pseudo distractors
from a LLM teacher with the input passage, question and answer. To save space,
we display the prompts in Appendix A.1.

To guarantee the distracting level of the generated pseudo distractors, we
filter out results that exhibit high similarity to the answer by calculating
the BLEU-4 score. All pseudo outputs with a BLEU-4 score greater than 30 are
dropped, along with their associated question-answer pairs.

###  3.3 Dual Task Training with Student Models

The pseudo distractors from LLMs (denoted as $d^{\prime}$) can be directly
distilled to a student model as supervised signals during training. However,
employing this straightforward augmentation method may not lead to
satisfactory results because of the suboptimal performance of LLM in DG task.

As a pair of dual tasks, the answer generation task exhibits similarities with
the DG task. Both tasks require a comprehensive understanding on the input
passage and deep analysis on question-related contexts. To this end, we
introduce answer generation into our unsupervised distractor training process
as an auxiliary task.

To take advantage of both pseudo distractor generation and answer generation,
we devise a two-stage training procedure for the smaller student model.
Firstly, the model treats [$p,q,d^{\prime}$] as input and generates $a$,
addressing answer generation:

$p_{a}=p(a_{i}|p,q,d^{\prime},a_{<i})$ (2)

Secondly, we just interchange answers and pseudo distractors, applying
[$p,q,a$] as input and $d^{\prime}$ as output, serving as distractor
generation:

$p_{d}=p(d^{\prime}_{i}|p,q,a,d^{\prime}_{<i})$ (3)

In the experiment, we prepend task-specific tokens to distinguish these two
tasks. For distractor generation, we replace the decoder start token (often
eos token) with the special token [DIS] and [ANS] for answer generation.

We denote the model training in answer generation as $M_{a}$, and distractor
generation as $M_{d}$. In the two-stage training procedure, $M_{d}$ is
initialized with the parameters of $M_{a}$. Both models apply the cross-
entropy (CE) loss for training.

###  3.4 Contrastive Decoding

The introduction of answer generation in dual task training raises up a
challenge on the distracting level of the generated result, as the model may
generate correct content. Inspired by the contrastive decoding method Li et
al. (2023), we propose a novel decoding strategy called counterfactual
contrastive decoding (CCD) to solve this issue.

####  3.4.1 Counterfactual Contrastive Decoding

Generally speaking, CCD rewards counterfactual text patterns favoured by the
distractor generation model while penalizes factual text patterns generated by
the answer generation model. To obtain the output probabilities of both
models, we propose a two-stage inference process:

##### Stage 1

Perform the inference process with $p$, $q$, $a$ as input on DG model $M_{d}$
to generate one distractor result, referring as $d_{inter}$.

##### Stage 2

Regard $M_{d}$ as the expert model and $M_{a}$ as the amateur model, and apply
contrastive decoding as Equation 4:

$\text{CCD-
score}_{i}=\text{log}\frac{p_{d}(y_{i}|p,q,a,y_{<i})}{p_{a}(y_{i}|p,q,d_{inter},y_{<i})}$
(4)

where $y$ is the output sequence of $M_{d}$.

Please note that different from the training process, $d_{inter}$ replaces the
pseudo distractor $d^{\prime}$ in the input sequence of $M_{a}$, thereby
avoiding the dependence on LLM during inference.

Taking into account the high similarity between $M_{d}$ and $M_{a}$ models,
some common text patterns with high probability in both models will become
hard to be generated while the generation probability of some implausible
tokens will greatly improve. To address this issue, we optimize the
counterfactual contrastive decoding as:

CCD-score $\displaystyle=\text{log-softmax}(\text{logit}^{\prime}_{d})$ (5)
$\displaystyle\text{logit}^{\prime}_{d}$
$\displaystyle=\text{logit}_{d}*f(\text{logit}_{d},\text{logit}_{a})$
$\displaystyle\text{logit}_{a}$ $\displaystyle=M_{a}(p,q,d_{inter},y_{<i})$
$\displaystyle\text{logit}_{d}$ $\displaystyle=M_{d}(p,q,a,y_{<i})$

The scaling function $f$ is calculated as:

$f(x,y)=\text{exp}(\text{sgn}(x)*(\sigma(\frac{x-y}{t})-0.5))$ (6)

where $\sigma$ is the Sigmoid function, $\text{sgn}(*)$ is the Signum
function. $t$ is a hyper-parameter to control the scaling degree and avoid the
saturation of the sigmoid function.

As the final value of CCD-score mostly depends on the absolute value of
$\text{logit}_{d}$, the implausible tokens with low generation probability are
still hard to be generated after the logit scaling. On the other hand, the
scaling factor is determined by the difference between $\text{logit}_{d}$ and
$\text{logit}_{a}$. Notably, it will be close to 1 when the $\text{logit}_{d}$
is approximately equal to $\text{logit}_{a}$, maintaining the high probability
of tokens that both models exhibit high confidence on.

####  3.4.2 Plausibility Constraint

To improve the stability of the decoding results, we introduce a plausibility
constraint method to restrict the effect of counterfactual contrastive
decoding. For distractor generation, we propose a rank-based plausibility
constraint:

$\text{CCD-score}=\left\\{\begin{aligned}
&\text{Equation~{}\ref{eq:ccd_scale}}&\text{if}\ x_{i}\in\mathcal{V}_{adj}\\\
&\text{log-softmax}(\text{logit}_{d})&\text{otherwise}\end{aligned}\right.$
(7)

$\displaystyle\mathcal{V}_{adj}=\\{y_{i}\in\mathcal{V}:\
\text{rank}(p_{d}(y_{i}|y_{<i}))>r\\}$ (8)

We rank the probability across the vocabulary. For tokens with extremely high
probability, we will fix their logits and only adjust tokens ranked after
$r$-th, where $r$ is a hyper-parameter. Compared to the value-based
plausibility constraint method proposed in Li et al. (2023), our rank-based
method is more stable and controllable.

##  4 Experimental Setup

###  4.1 Student Model Training

We choose Bart-base as the student model , which has only 139M parameters and
can be easily deployed in real applications. We train the student model with
5-epoch answer generation and 10-epoch distractor generation in the two-stage
training process. In both stages we set the maximum learning rate, batch size
and warmup ratio to $10^{-5}$, 48 and 0.1. During inference, we adopt Jaccard
Distance for generating 3 different results with the beam size as 20, and
other detail settings can be referred to Zhou et al. (2020). $r$ and $t$ are
set to 15 and 2 in experiment.

###  4.2 Applying LLMs

We conduct experiments on two mainstream series LLMs: LLaMa-2 and GPT-3.5. For
LLaMa-2, we apply LLaMa-2-13B-chat implemented by HuggingFace. For GPT-3.5, we
apply GPT-3.5-turbo with the official API.

##### LLM distractor generation for distilling

We apply the prompt shown in Appendix A.1 to generate one pseudo distractor
for each input $p$, $q$ and $a$. For the sake of reproductivity, we turn off
the sampling and set the temperature to zero.

##### LLM zero-shot inference

To explore the performance of LLM, we apply LLMs to generate three distractors
with the prompt displayed in Appendix A.2. Due to the high cost of applying
LLMs with a large beam size, we do not ask LLMs to return 20 results for
filtering like student model does.

###  4.3 Datasets

We conduct extensive experiments on RACE Lai et al. (2017) and Dream Sun et
al. (2019), which are collected from the English exams of middle and high
schools in China. The detailed statistics of the cleaned dataset are shown in
Table 1.

| Dataset | # q-a pair | # passage | # d(pseudo)
---|---|---|---|---
Train | RACE | 45120 | 20028 | 35452
Dream | 6116 | 3862 | 4721
Test | RACE | 5787 | 2519 | -
Dream | 2041 | 1283 | -
Table 1: The statistics of RACE and Dream dataset, where $q$, $a$ refers to
the question and answer respectively. d(pseudo) is the pseudo distractor
generated by GPT-3.5-turbo.

We drop the human-annotated distractors in training set and utilize these
datasets as unsupervised data. LLMs are applied to generate one pseudo
distractor for each question-answer pair in the training set for student model
training. The generated results will be filtered with BLEU score as mentioned
in Section 3.2.

###  4.4 Automatic Evaluation Metrics

We apply BLEU111https://pypi.org/project/sacrebleu/,
Rouge222https://pypi.org/project/pyrouge/ and
BertScore333https://github.com/huggingface/evaluate to evaluate the generation
quality, and Distinct Li et al. (2016) to evaluate the generation diversity.

As an important evaluation aspect, the distracting level of generated
distractors has not received sufficient attention in previous works.
Therefore, we propose a new automatic evaluation metric called Faithful Score
to measure the distracting level of the generated results.

| Dataset | Faithful Score
---|---|---
Answer | RACE | 78.34
Dream | 76.23
Distractor | RACE | 10.49
Dream | 10.81
Table 2: Faithful Score evaluation on the test set of RACE and Dream. Models | 1-st B4 | 2-nd B4 | 3-rd B4 | Avg B4 | Avg BS | Avg R-L | Distinct 1 | Distinct 2 |  Avg FS($\downarrow$)
---|---|---|---|---|---|---|---|---|---
Fully Fine-tuned
HSA | 6.43 | 5.17 | 4.59 | 5.40 | - | 14.67 | - | - | -
HCA | 7.01 | 5.51 | 4.88 | 5.80 | - | 15.12 | - | - | -
EDGE | 7.57 | 6.27 | 5.70 | 6.51 | - | 18.27 | - | - | -
HMD-Net | 7.66 | 6.37 | 5.33 | 6.45 | - | 24.99 | - | - | -
MSG-Net | 8.87 | 8.86 | 8.53 | 8.75 | - | 26.39 | - | - | -
DG-MoE | 9.52 | 9.12 | 9.59 | 9.41 | 89.78 | 26.80 | 69.61 | 82.40 | -
Bart-base | 11.22 | 9.83 | 9.15 | 10.07 | 88.83 | 26.45 | 71.39 | 85.24 | 24.66
Unsupervised
GPT-3.5-turbo | 6.82 | 5.75 | 5.07 | 5.88 | 86.73 | 26.13 | 75.46 | 87.68 | 33.39
LLaMa-2-13B-chat | 5.99 | 4.82 | 4.00 | 4.94 | 70.03 | 19.48 | 80.74 | 91.48 | 30.30
Our Full Model | 8.36 | 7.43 | 7.14 | 7.64 | 88.38 | 26.38 | 70.33 | 83.86 | 25.64
Table 3: Experimental results on RACE dataset with 3 distractors comparing with baselines. B4 refers to BLEU-4, BS refers to BertScore, R-L refers to Rouge-L and FS refers to Faithful Score. The pseudo labels for model training are from GPT-3.5-turbo. Models | 1-st B4 | 2-nd B4 | 3-rd B4 | Avg B4 | Avg BS | Avg R-L | Distinct 1 | Distinct 2 |  Avg FS($\downarrow$)
---|---|---|---|---|---|---|---|---|---
Fully Fine-tuned
Bart-base | 22.65 | 16.37 | 12.88 | 17.30 | 93.30 | 41.52 | 76.03 | 81.25 | 27.20
Unsupervised
GPT-3.5-turbo | 10.91 | 8.18 | 6.33 | 8.47 | 91.80 | 33.00 | 71.73 | 77.26 | 28.67
LLaMa-2-13B-chat | 11.81 | 7.63 | 5.92 | 8.12 | 87.13 | 31.01 | 80.61 | 82.91 | 24.22
Our Full Model | 15.83 | 11.09 | 9.93 | 12.29 | 92.07 | 38.44 | 77.64 | 81.71 | 23.83
Table 4: Experimental results on DREAM dataset with 3 distractors. The pseudo
labels are from GPT-3.5-turbo.

##### Faithful Score

Based on RACE and Dream, we follow Jiang et al. (2020) and train an Alberta
model on the machine reading comprehension task. This model aims to judge
whether a given candidate is a correct answer to the corresponding passage-
question pair and return a classification score ranging [0, 100]. The DG task
prefers models that generate distracting results with low Faithful Score.

We conduct evaluation on the test set of RACE and Dream, and results are shown
in Table 2. The Faithful Score values on reference answers are between 75 and
80 for both datasets and about 10 on distractors. The experiment results prove
the excellent discrimination ability of this metric.

(a) BLEU-4 Score

(b) Faithful Score

Figure 3: Low-resource experimental results on RACE.

##  5 Results and Analysis

###  5.1 Main Results

The experiment results on RACE and Dream are shown in Table 3 and Table 4. For
RACE, we display the results on previous works including HSA Gao et al.
(2019), HCA Zhou et al. (2020), EDGE Qiu et al. (2020), HMD-Net Maurya and
Desarkar (2020), MSG-Net Xie et al. (2022), DG-MoE Qu et al. (2023). The
results of fine-tuned Bart-base and LLMs are also displayed for comparison.
For our full model, we apply GPT-3.5-turbo to generate pseudo distractors. We
mainly evaluate the results from three aspects: quality, diversity and
distracting level.

##### Performance on the generation quality

Both GPT-3.5-turbo and LLaMa-2-13B-chat just manage to obtain half of the SOTA
BLEU-4 score on two datasets. Compared to GPT-3.5-turbo, LLaMa-2-13B-chat is
more unstable. On the more challenging dataset RACE, LLaMa-2-13B-chat achieves
far inferior performance on BertScore (70.03) and Rouge-L (19.48) than other
methods.

Our proposed unsupervised method greatly outperforms LLMs on the generation
quality. In terms of BLEU-4, we achieve 1.76 and 3.82 points improvements on
RACE and Dream compared to GPT-3.5-turbo. And our model has achieved an
approximate performance on BertScore and Rouge-L compared to the fully fine-
tuned SOTA result. As for BLEU-4, there still exists an obvious gap between
the unsupervised and fine-tuned results.

Models | Avg B4 | Avg BS | Avg R-L | Distinct 1 | Distinct 2 |  Avg FS($\downarrow$)
---|---|---|---|---|---|---
Two-stage training | 7.75 | 88.48 | 26.77 | 69.34 | 83.37 | 27.59
\+ Counterfactual Contrastive Decoding | 7.17 | 88.12 | 26.22 | 68.29 | 82.71 | 25.85
\+ Plausibility Constraint | 7.64 | 88.38 | 26.38 | 70.33 | 83.86 | 25.64
Table 5: Ablation studies on the contrastive decoding method. Models | Avg B4 | Distinct 1 |  Avg FS($\downarrow$)
---|---|---|---
Pseudo Label | 6.69 | 72.56 | 27.31
Answer Label | 6.81 | 70.07 | 45.31
Mixed Data | 8.02 | 69.16 | 32.68
Two Stage | 7.75 | 69.34 | 27.59
Table 6: Experimental results on dual task training.

##### Performance on the generation diversity

We apply Distinct-1 and Distinct-2 to measure the generation diversity. On
both RACE and Dream, our method achieves a close performance to SOTA. Among
all these methods, LLaMa-2-13B-chat achieves greatest diversity performance.
However, this may be due to the high randomness of its result that improves
the generation diversity while makes harm to the generation quality Fang and
Jiang (2022).

##### Performance on the distracting level

We apply Faithful Score to evaluate the distracting level of the generated
results. Our proposed method outperforms GPT-3.5 and LLaMa-2-13B-chat on both
datasets and performs closely to the fully fine-tuned method. On RACE, our
method is just 0.98 points lower than fine-tuned method, and on Dream our
method outperforms 3.37 points.

###  5.2 Effect of Dual Task Training

We conduct experiments on RACE to investigate the impact of the dual task
training based on GPT-3.5-turbo. We train the student model in four different
settings: with only pseudo distractors (Pseudo Label); with only answer
targets (Answer Label); with the mixed data of pseudo distractors and answers
(Mixed Data) and two-stage training process (Two Stage). In all these
settings, we do not apply our proposed counterfactual contrastive decoding
during inference.

The results are shown in Table 6. Compared to pseudo-distractor-only method,
results of answer-only method have a slight improvement on BLEU-4 and a tiny
decline on Distinct-1. However, the Faithful Score of pseudo-distractor-only
method outperforms that of answer-only method significantly, with a decline of
18.0 points. As for the dual task training with mixed data, the incorporation
of answer information brings significant improvement on the generation
quality. Nevertheless, it raises up a negative impact on the result’s
distracting level, as evidenced by the Faithful Score value.

The two-stage training process proves to be effective to address the above
limitation. We observe a decrease of 5.09 points in Faithful Score,
accompanied by only a slight 0.27 points reduction in BLEU-4.

###  5.3 Effect of Counterfactual Contrastive Decoding

Further, we explore the effect of counterfactual contrastive decoding based on
GPT-3.5-turbo. We apply the DG model with two-stage training as the base
model. The results on RACE dataset are shown in Table 5.

Despite a decline on the generation quality, CCD contributes to an improvement
on model’s counterfactual generation capability, with a 1.74 points decline on
Faithful Score. Besides, plausibility constraint successfully enhances the
stability of the generated results, further reducing Faithful Score by 0.21
points and achieving a great trade-off between the generation quality and
distracting level.

###  5.4 Performance with Low-Resource Setting

Our unsupervised method leverages answer information to enhance the generation
quality. However, obtaining a sufficient number of annotated answer labels
still requires investment, even if cheaper than distractors. In this section,
we simulate the low-resource scenario of real-world applications on RACE
dataset, and investigate the performance of both supervised and our
unsupervised methods. The results are shown in Figure 3. The experiments of
our unsupervised method are conducted based on GPT-3.5-turbo.

As the data ratio of the training set decreases, the generation quality of the
supervised method declines continuously. In contrast, our unsupervised method
maintains a stable BLEU-4 score until the data ratio decreases to 1% (about
400 samples) and demonstrates comparable performance to the supervised method
in low-resource situation.

With the decrease of the unannotated data number, the second stage training
for distractor generation becomes insufficient, resulting in a heightened
impact from the first stage answer generation training on the final results.
This leads to a faster increase in the Faithful Score of unsupervised method
compared to supervised one.

Besides, we conduct experiments to explore LLMs’ performance on few-shot
settings. The results in Table 7 indicate that adding 5 randomly selected
demonstrations to the prompt only increases the BLEU-4 score by 0.3 points for
LLaMa-2-13B-chat.

Model | Shots | Avg B4 |  Avg FS($\downarrow$)
---|---|---|---
Llama-2-13b-chat | 0 | 4.94 | 30.30
5 | 5.24 | 28.76
Table 7: Experimental results on few-shot setting.

###  5.5 Evaluation from GPT-4

N-gram based quality metrics like BLEU are not completely consistent with the
actual performance in generation task. Thereby we apply GPT-4 as a
professional evaluator to measure the performance of different methods from
two aspects: the quality and distracting level of the generated results.

Concretely, we apply GPT-4 to compare two distractors generated by different
methods. GPT-4 is asked to return "Win", "Lose" or "Tie" according to the
comparison result. The order of two input distractors will be randomly
shuffled in the input prompt for a fair comparison. We randomly select 1000
samples from the test set of RACE for evaluation. The prompt for GPT-4
evaluation is proposed in Section A.3. The results are shown in Table 8.

(%) | vs. Supervised | vs. GPT-3.5-turbo
---|---|---
Win | Tie | Lose | Win | Tie | Lose
Quality | 36.4 | 23.2 | 40.4 | 41.8 | 18.2 | 40.0
Distracting | 47.1 | 12.8 | 40.1 | 49.1 | 7.5 | 43.4
Table 8: Evaluation results from GPT-4 with respect to the quality and
distracting level of the generated distractors. We compare our unsupervised
model with the supervised Bart-base and GPT-3.5-turbo zero-shot inference
results.

For the generation quality, GPT-4 favors results from the supervised method
more, and our method’s performance is slightly better than GPT-3.5-turbo. As
for the distracting level, our method performs significantly better than the
other two methods, demonstrating the effectiveness of our counterfactual
contrastive decoding strategy.

###  5.6 Performance of Different LLMs

Teacher Models | Avg B4 | Distinct 1 |  Avg FS($\downarrow$)
---|---|---|---
GPT-3.5-turbo | 7.64 | 70.33 | 0.2564
LLaMA-2-13B | 5.84 | 71.27 | 0.2583
Table 9: Experimental results with different large language models as the
teacher models.

Further, to explore the impact of different LLMs on the performance, we adopt
GPT-3.5-turbo and LLaMa-2-13B as different teacher models, and the results are
shown in Table 9.

Generally, the generation diversity and distracting level of the generated
results are not significantly related to the selection of teacher model.
However, the unsupervised method based on GPT-3.5-turbo outperforms
LLaMa-2-13B by an average of 1.40 points in BLEU-4 score, which is positively
correlated with the zero-shot performance of LLMs.

Passage: Until late in the 20th century, most Americans spent time with people
of generations. Now mid-aged Americans may not keep in touch with old people
until they are old themselves …. The young, in turn, save the old. Once I was
in a rest home when a visitor showed up with a baby ….
---
Question: Now in an American family, people can find that
Answer: not all working people live with their parents
Reference distractors:
(1) children never live with their parents (2) aged people are supported by
their grandchildren (3) grandchildren are supported by their grandparents
Results of fully fine-tuned Bart-base:
(1) all working people live with their parents (2) parents don’t care about
their children (3) all the old people live with their children
Results of GPT-3.5-turbo:
(1) all working people live with their parents (2) working people live with
their parents (3) working people do not live with their parents
Results of proposed unsupervised method:
(1) only working people live with parents (2) parents don’t care about their
children (3) the young save the old in turn
Passage: ’Where Are We Going , Dad ?’ presents a new generation of men, in a
break from Chinese tradition, now take an active role in their children’s
lives …. Another one must survive with his son for three days in the desert ….
In traditional Chinese culture, the common conception of parenthood is that
the father is strict and the mother is kind ….
Question: In Where Are We Going , Dad , we can probably learn about
Answer: how the fathers look after and guide their children
Reference distractors:
(1) how the fathers do housework at home (2) how the children study in their
spare time (3) how the children help their father with their travel around
China
Results of fully fine-tuned Bart-base:
(1) how the children grow up at the same time (2) how the father is strict and
the mother is kind (3) how the fathers raise their children
Results of GPT-3.5-turbo:
(1) what kind of food the fathers and their children eat (2) whether the
fathers know how to do their daughters’ hair
(3) how the fathers survive in the desert without cooking skills
Results of proposed unsupervised method:
(1) the negative impact of fathers on children’s lives (2) the history of
Chinese culture (3) why the father is strict
Table 10: Case study for fully fine-tuned model, GPT-3.5-turbo and our
proposed unsupervised generation method.

###  5.7 Case Study

Table 10 illustrates two examples of the generated distractors by three
models. All three models produce fluent results without grammar errors.
However, in case 1, the results from GPT-3.5-turbo suffers a problem of low
diversity. And in case 2, both fine-tuned Bart-base and GPT-3.5-turbo generate
correct answers like ’how the fathers raise their children’, ’what kind of
food the fathers and their children eat’ and ’how the fathers survive in the
desert without cooking skills’. This mistake is not observed in our
unsupervised results with counterfactual contrastive decoding.

##  6 Conclusion

In this paper, we propose an unsupervised distractor generation method. We
apply Large Language Models as distractor labelers and construct dual task
training process to enhance the student model’s generation capability.
Moreover, we optimize contrastive generation method in counterfactual
generation context. Experiment results indicate that our method generally
outperforms LLM-based approaches and is comparable to fully fine-tuned results
in low-resource situations. Given the absence of human-annotated distractor
dataset, our work can make contribution to building solid reading
comprehension data in more future scenarios.

## Acknowledgements

This work is supported by the National Natural Science Foundation of China
(62076008) and the Key Project of Natural Science Foundation of China
(61936012).

## Limitations

First, there still remains an obvious gap between our proposed unsupervised
method and supervised method in DG task, especially for the quality of the
generated results. Second, we only experiment on two English dataset from
reading comprehension data due to the lack of high-quality testing data. The
performance of our method on other application scenarios requires further
exploration. Third, we utilize human-annotated answer labels in our
unsupervised method, which brings some cost of manual annotation. Fourth,
while recent works succeed to enhance student models with rationales generated
by LLMs in various NLU tasks, we fail to introduce these methods into DG task.
We analyze that for NLG tasks, the rationales generated by LLMs rather
complicate the generation process and put negative impact on the model’s
performance. Related work can be further explored in the future. Last, due to
limited time, we do not explore the performance on more LLMs and student
models with different parameter scales.

## References

  * Arora et al. (2022) Simran Arora, Avanika Narayan, Mayee F Chen, Laurel Orr, Neel Guha, Kush Bhatia, Ines Chami, Frederic Sala, and Christopher Ré. 2022.  Ask me anything: A simple strategy for prompting language models.  _ArXiv preprint_ , abs/2210.02441.
  * Bitew et al. (2023) Semere Kiros Bitew, Johannes Deleu, Chris Develder, and Thomas Demeester. 2023.  Distractor generation for multiple-choice questions with predictive prompting and large language models.  _ArXiv preprint_ , abs/2307.16338.
  * Bonifacio et al. (2022) Luiz Bonifacio, Hugo Abonizio, Marzieh Fadaee, and Rodrigo Nogueira. 2022.  Inpars: Data augmentation for information retrieval using large language models.  _ArXiv preprint_ , abs/2202.05144.
  * Chiang et al. (2022) Shang-Hsuan Chiang, Ssu-Cheng Wang, and Yao-Chung Fan. 2022.  CDGP: automatic cloze distractor generation based on pre-trained language model.  In _Findings of the Association for Computational Linguistics: EMNLP 2022, Abu Dhabi, United Arab Emirates, December 7-11, 2022_ , pages 5835–5840. Association for Computational Linguistics.
  * Doughty et al. (2024) Jacob Doughty, Zipiao Wan, Anishka Bompelli, Jubahed Qayum, Taozhi Wang, Juran Zhang, Yujia Zheng, Aidan Doyle, Pragnya Sridhar, Arav Agarwal, et al. 2024.  A comparative study of ai-generated (gpt-4) and human-crafted mcqs in programming education.  In _Proceedings of the 26th Australasian Computing Education Conference_ , pages 114–123.
  * Fang and Jiang (2022) Weike Fang and Meng Jiang. 2022.  Investigating relationships between accuracy and diversity in multi-reference text generation.
  * Gao et al. (2019) Yifan Gao, Lidong Bing, Piji Li, Irwin King, and Michael R. Lyu. 2019.  Generating distractors for reading comprehension questions from real examinations.  In _The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019_ , pages 6423–6430. AAAI Press.
  * Gilardi et al. (2023) F Gilardi, M Alizadeh, and M Kubli. 2023.  Chatgpt outperforms crowd-workers for textannotation tasks. _ArXiv preprint_ , abs/2303.15056.
  * He et al. (2023) Xingwei He, Zhenghao Lin, Yeyun Gong, Alex Jin, Hang Zhang, Chen Lin, Jian Jiao, Siu Ming Yiu, Nan Duan, Weizhu Chen, et al. 2023.  Annollm: Making large language models to be better crowdsourced annotators.  _ArXiv preprint_ , abs/2303.16854.
  * Jiang et al. (2020) Yufan Jiang, Shuangzhi Wu, Jing Gong, Yahui Cheng, Peng Meng, Weiliang Lin, Zhibo Chen, and Mu Li. 2020.  Improving machine reading comprehension with single-choice decision and transfer learning.  _ArXiv preprint_ , abs/2011.03292.
  * Lai et al. (2017) Guokun Lai, Qizhe Xie, Hanxiao Liu, Yiming Yang, and Eduard Hovy. 2017.  RACE: Large-scale ReAding comprehension dataset from examinations.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing_ , pages 785–794, Copenhagen, Denmark. Association for Computational Linguistics.
  * Li et al. (2016) Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and Bill Dolan. 2016.  A diversity-promoting objective function for neural conversation models.  In _Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 110–119, San Diego, California. Association for Computational Linguistics.
  * Li et al. (2023) Xiang Lisa Li, Ari Holtzman, Daniel Fried, Percy Liang, Jason Eisner, Tatsunori Hashimoto, Luke Zettlemoyer, and Mike Lewis. 2023.  Contrastive decoding: Open-ended text generation as optimization.  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2023, Toronto, Canada, July 9-14, 2023_ , pages 12286–12312. Association for Computational Linguistics.
  * Maurya and Desarkar (2020) Kaushal Kumar Maurya and Maunendra Sankar Desarkar. 2020.  Learning to distract: A hierarchical multi-decoder network for automated generation of long distractors for multiple-choice questions for reading comprehension.  In _CIKM ’20: The 29th ACM International Conference on Information and Knowledge Management, Virtual Event, Ireland, October 19-23, 2020_ , pages 1115–1124. ACM.
  * Nasution (2023) NEA Nasution. 2023.  Using artificial intelligence to create biology multiple choice questions for higher education.  _Agricultural and Environmental Education_ , 2(1).
  * OpenAI (2023) OpenAI. 2023.  GPT-4 technical report.  _CoRR_ , abs/2303.08774.
  * Qiu et al. (2020) Zhaopeng Qiu, Xian Wu, and Wei Fan. 2020.  Automatic distractor generation for multiple choice questions in standard tests.  In _Proceedings of the 28th International Conference on Computational Linguistics_ , pages 2096–2106, Barcelona, Spain (Online). International Committee on Computational Linguistics.
  * Qu et al. (2023) Fanyi Qu, Che Wang, and Yunfang Wu. 2023.  Accurate, diverse and multiple distractor generation with mixture of experts.  In _CCF International Conference on Natural Language Processing and Chinese Computing_ , pages 761–773. Springer.
  * Ren and Zhu (2021) Siyu Ren and Kenny Q. Zhu. 2021.  Knowledge-driven distractor generation for cloze-style multiple choice questions.  In _Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021_ , pages 4339–4347. AAAI Press.
  * Saad-Falcon et al. (2023) Jon Saad-Falcon, Omar Khattab, Keshav Santhanam, Radu Florian, Martin Franz, Salim Roukos, Avirup Sil, Md Arafat Sultan, and Christopher Potts. 2023.  Udapdr: Unsupervised domain adaptation via llm prompting and distillation of rerankers.  _ArXiv preprint_ , abs/2303.00807.
  * Smith et al. (2022) Ryan Smith, Jason A Fries, Braden Hancock, and Stephen H Bach. 2022.  Language models in the loop: Incorporating prompting into weak supervision.  _ArXiv preprint_ , abs/2205.02318.
  * Sun et al. (2019) Kai Sun, Dian Yu, Jianshu Chen, Dong Yu, Yejin Choi, and Claire Cardie. 2019.  DREAM: A challenge data set and models for dialogue-based reading comprehension.  _Transactions of the Association for Computational Linguistics_ , 7:217–231.
  * Touvron et al. (2023) Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaei, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. 2023.  Llama 2: Open foundation and fine-tuned chat models.  _ArXiv preprint_ , abs/2307.09288.
  * Wang et al. (2023) Hui-Juan Wang, Kai-Yu Hsieh, Han-Cheng Yu, Jui-Ching Tsou, Yu-An Shih, Chen-Hua Huang, and Yao-Chung Fan. 2023.  Distractor generation based on text2text language models with pseudo kullback-leibler divergence regulation.  In _Findings of the Association for Computational Linguistics: ACL 2023, Toronto, Canada, July 9-14, 2023_ , pages 12477–12491. Association for Computational Linguistics.
  * Wang et al. (2021) Shuohang Wang, Yang Liu, Yichong Xu, Chenguang Zhu, and Michael Zeng. 2021.  Want to reduce labeling cost? GPT-3 can help.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 4195–4205, Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Whitehouse et al. (2023) Chenxi Whitehouse, Monojit Choudhury, and Alham Fikri Aji. 2023.  Llm-powered data augmentation for enhanced crosslingual performance.  _ArXiv preprint_ , abs/2305.14288.
  * Xie et al. (2022) Jiayuan Xie, Ningxin Peng, Yi Cai, Tao Wang, and Qingbao Huang. 2022.  Diverse distractor generation for constructing high-quality multiple choice questions.  _IEEE ACM Trans. Audio Speech Lang. Process._ , 30:280–291.
  * Zhou et al. (2020) Xiaorui Zhou, Senlin Luo, and Yunfang Wu. 2020.  Co-attention hierarchical network: Generating coherent long distractors for reading comprehension.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020_ , pages 9725–9732. AAAI Press.

##  Appendix A Prompt for LLMs

In this section we display the prompts applied to different LLMs.

###  A.1 Prompt for generating pseudo distractors

We generate pseudo distractors by LLMs for the training of student model. The
instructions are shown in Table 11

###  A.2 Prompt for zero-shot inference

When applying LLMs for zero-shot inference in distractor generation, we ask
LLMs to generate three different results in one generation process. The prompt
are shown in Table 12

###  A.3 Prompt for GPT-4 evaluation

We compare the quality and distracting level of results from two different
models with GPT-4, and the prompts are shown in Table 13.

GPT-3.5-turbo | LLaMa-2-13B-chat
---|---
"system":
You are a helpful AI educational assistant to generate distractors (wrong
answers) to help reading comprehension. Please generate one distractor with
following requirement: 1. The generated distractor is a wrong answer to the
input question according to the given document. 2. Return the generated result
directly in one line that begin with ’<result>’ and end with ’</result>’.
"user":
Now I will provide you with a reading comprehension document, a question and
an answer.
<document> $p$ </document>
<question> $q$ </question>
<answer> $a$ </answer> |  You are a helpful AI educational assistant to generate distractors (wrong answers) for reading comprehension. You are required to generate one distractor with the given document, question and answer. There are some requirements for you: 1. The generated result should begin with ’<result>’ and end with ’</result>’. 2. If the input question is an incomplete sentence, the generated result should complete the syntax of the question. 3. You should not return any explanations except the distractors. There is the document, question and answer:
<document> $p$ </document>
<question> $q$ </question>
<answer> $a$ </answer>
<result>
Table 11: Prompt for GPT-3.5-turbo and LLaMa-2-13B-chat to generate pseudo distractors. GPT-3.5-turbo | LLaMa-2-13B-chat
---|---
"system":
You are a helpful AI educational assistant to generate distractors (wrong
answers) to help reading comprehension. Please generate three distractors with
following requirement: 1. The generated distractors are a wrong answer to the
input question according to the given document. 2. The generated results
should be returned in three lines and each result should begin with ’<result>’
and end with ’</result>’.
"user":
Now I will provide you with a reading comprehension document, a question and
an answer.
<document> $p$ </document>
<question> $q$ </question>
<answer> $a$ </answer> |  You are a helpful AI educational assistant to generate distractors (wrong answers) for reading comprehension. You are required to generate three distractors with the given document, question and answer. Now I will provide you with a document.
<document> $p$ </document>
There are some requirements for you: 1. The generated result should begin with
’<result>’ and end with ’</result>’. Between <result> and </result>, return
three results split by ’;’. 2. If the input question is an incomplete
sentence, the generated result should complete the syntax of the question. 3.
You should not return any explanations except the distractors. Then I will
give you a question-answer pair about the input document.
<question> $q$ </question>
<answer> $a$ </answer>
The three distractors can be: <result>
Table 12: Prompt for GPT-3.5-turbo and LLaMa-2-13B-chat to generate three
different distractors.

Prompt for GPT-4
---
"system":
You are a helpful AI educational assistant that can evaluate distractors
(wrong answers) and find the better one from two candidates.
"user":
Now I will provide you with a reading comprehension document, a question, an
answer and a reference distractor.
<document> $p$ </document>
<question> $q$ </question>
<answer> $a$ </answer>
<reference> $d$ </reference>
Then I will give you 2 distractor candidates and you should judge which one is
a better result. The detailed comparison requirements are as follow:
************
$requirement$
************
I will show you two candidate distractors. If the first candidate is obviously
greater than the second candidate, return ’Win’; If the first candidate is
obviously worse than the second candidate, return ’Lose’; If you think there
are not obvious gap between these two candidates, return ’Tie’. Do not return
any explanations about your result.
The candidates are: 1. $candidates\\_1$; 2. $candidates\\_2$.

Requirements for quality evaluation | Requirements for distracting level evaluation
---|---
1\. You should compare the candidates according to their quality.
2\. If the candidate is consist of fluent sentences without any grammar
errors, the candidate has high quality.
3\. If there are just some small errors like tense error and voice error, the
candidate has medium quality.
4\. If there are obvious syntactic or grammatical errors, the candidate has low quality. |  1\. You should compare the candidates according to their distracting level.
2\. If the candidate is correct to the input question, it has low distracting
level.
3\. If the candidate is wrong to the input question, it has high distracting
level.
4\. The given answer has low distracting level and the given reference has
high distracting level. These two sentences can serve as the reference for
your comparison.

Table 13: Prompt for GPT-4 to compare distractors generated by two different
models.


Inverse reinforcement learning (IRL) algorithms  often rely on (forward) reinforcement learning or  planning  over a given time horizon to compute an approximately optimal policy for a hypothesized reward function and then match this policy with expert demonstrations. The time horizon plays a critical role in determining both the accuracy of reward estimate and the computational efficiency of IRL algorithms. Interestingly, an effective time horizon shorter than  the ground-truth value often produces better results faster. This work formally analyzes this phenomenon and provides an explanation: the time horizon controls the complexity of an induced policy class and mitigates overfitting with limited data. This analysis
leads to a principled choice of the effective horizon for IRL. It
also prompts us to reexamine the classic IRL formulation: it is  more natural to learn jointly the reward and the effective horizon  together rather than the reward alone with a given horizon.
Our experimental results confirm the theoretical analysis.

[Abbeel & Ng, 2004]
Abbeel, P. and Ng, A.
Apprenticeship learning via inverse reinforcement learning.
In Proc. Int. Conf. on Machine Learning, 2004.

[Boularias et al., 2011]
Boularias, A., Kober, J., and Peters, J.
Relative entropy inverse reinforcement learning.
In Proc. Int. Conf. on Artificial Intelligence & Statistics,

[Finn et al., 2016]
Finn, C., Christiano, P., Abbeel, P., and Levine, S.
A connection between generative adversarial networks, inverse
reinforcement learning, and energy-based models.
In Advances in Neural Information Processing Systems,

[Finn et al., 2016]
Finn, C., Levine, S., and Abbeel, P.
Guided cost learning: Deep inverse optimal control via policy
In Proc. Int. Conf. on Machine Learning, 2016b.

[Fu et al., 2018]
Fu, J., Luo, K., and Levine, S.
Learning robust rewards with adversarial inverse reinforcement
In Proc. Int. Conf. on Learning Representations, 2018.

[Ghasemipour et al., 2019]
Ghasemipour, S. K. S., Zemel, R., and Gu, S.
A divergence minimization perspective on imitation learning methods.
In Proc. Conference on Robot Learning, 2019.

[Ho & Ermon, 2016]
Ho, J. and Ermon, S.
Generative adversarial imitation learning.
In Advances in Neural Information Processing Systems, 2016.

[Hoshino et al., 2022]
Hoshino, H., Ota, K., Kanezaki, A., and Yokota, R.
Opirl: Sample efficient off-policy inverse reinforcement learning via
distribution matching.
In Proc. IEEE Int. Conf. on Robotics & Automation, pp.  448–454, 2022.

[Jiang et al., 2015]
Jiang, N., Kulesza, A., Singh, S., and Lewis, R.
The dependence of effective planning horizon on model accuracy.
In Proc. Int. Conf. on Autonomous Agents & Multiagent
Systems, volume 2, pp.  1181–1189, 05 2015.

[Ke et al., 2020]
Ke, L., Choudhury, S., Barnes, M., Sun, W., Lee, G., and Srinivasa, S.
Imitation learning as f-divergence minimization.
In Algorithmic Foundations of Robotics XIV—Proc. Int.
Workshop on the Algorithmic Foundations of Robotics (WAFR), 2020.

[Lee et al., 2022]
Lee, K., Isele, D., Theodorou, E. A., and Bae, S.
Spatiotemporal costmap inference for MPC via deep inverse
reinforcement learning.
In IEEE Robotics & Automation Letters, 2022.
URL <https://arxiv.org/abs/2201.06539>.

[Levine et al., 2011]
Levine, S., Popovic, Z., and Koltun, V.
Nonlinear inverse reinforcement learning with gaussian processes.
In Advances in Neural Information Processing Systems, 12 2011.

[MacGlashan & Littman, 2015]
MacGlashan, J. and Littman, M. L.
Between imitation and intention learning.
In Proc. Int. Jnt. Conf. on Artificial Intelligence, 2015.

[Metelli et al., 2021]
Metelli, A. M., Ramponi, G., Concetti, A., and Restelli, M.
Provably efficient learning of transferable rewards.
In Proc. Int. Conf. on Machine Learning, 2021.

[Ng & Russell, 2000]
Ng, A. Y. and Russell, S. J.
Algorithms for inverse reinforcement learning.
In Proc. Int. Conf. on Machine Learning, San Francisco, CA,
USA, 2000. Morgan Kaufmann Publishers Inc.
ISBN 1558607072.

[Ni et al., 2020]
Ni, T., Sikchi, H., Wang, Y., Gupta, T., Lee, L., and Eysenbach, B.
f-irl: Inverse reinforcement learning via state marginal matching.
In Proc. Conference on Robot Learning, 11 2020.

[Osa et al., 2018]
Osa, T., Pajarinen, J., Neumann, G., Bagnell, J. A., Abbeel, P., Peters, J.,
et al.
An algorithmic perspective on imitation learning.
Foundations and Trends® in Robotics,
70 (1-2):0 1–179, 2018.

[Pirotta & Restelli, 2016]
Pirotta, M. and Restelli, M.
Inverse reinforcement learning through policy gradient minimization.
In Proc. AAAI Conf. on Artificial Intelligence, 2016.

[Ramachandran & Amir, 2007]
Ramachandran, D. and Amir, E.
Bayesian inverse reinforcement learning.
In Proc. Int. Jnt. Conf. on Artificial Intelligence, 2007.

[Ramponi et al., 2020]
Ramponi, G., Drappo, G., and Restelli, M.
Inverse reinforcement learning from a gradient-based learner.
Advances in Neural Information Processing Systems,
33:0 2458–2468, 2020.

[Ratliff et al., 2006]
Ratliff, N. D., Bagnell, J. A., and Zinkevich, M. A.
Maximum margin planning.
In Proc. Int. Conf. on Machine Learning, 2006.

[Spencer et al., 2021]
Spencer, J., Choudhury, S., Venkatraman, A., Ziebart, B. D., and Bagnell, J. A.
Feedback in imitation learning: The three regimes of covariate shift.
ArXiv, abs/2102.02872, 2021.

[Wulfmeier et al., 2016]
Wulfmeier, M., Ondruska, P., and Posner, I.
Maximum entropy deep inverse reinforcement learning.
In Advances in Neural Information Processing Systems, 2016.

[Xu et al., 2022]
Xu, Y., Gao, W., and Hsu, D.
Receding horizon inverse reinforcement learning.
In Advances in Neural Information Processing Systems, 2022.

[Ziebart et al., 2008]
Ziebart, B. D., Maas, A., Bagnell, J. A., and Dey, A. K.
Maximum entropy inverse reinforcement learning.
In Proc. AAAI Conf. on Artificial Intelligence, 2008.

§ PROOF FOR SECTION <REF>

§.§ Proof for Lemma <ref>

This proof is adapted from the proof of Lemma B.1 and Lemma 3.2 in Metelli et al., 2021. Recall that we use the advantage function to derive two conditions such that the expert policy $\expertPolicy$ is optimal under the reward function $\learnedR$ and $\learnedGamma$. Specifically,

\begin{align}
& \QFunction{\expertPolicy}{\learnedR}{\learnedGamma}(s, a) - \VFunction{\expertPolicy}{\learnedR}{\learnedGamma}(s)  = 0 \;\;\;\;\;\;\;\text{if}\; \expertPolicy(a|s) > 0, \label{equ:cond_1}\\
&\QFunction{\expertPolicy}{\learnedR}{\learnedGamma}(s, a) - \VFunction{\expertPolicy}{\learnedR}{\learnedGamma}(s) \leq 0 \;\;\;\;\;\;\;\text{if}\; \expertPolicy(a|s) = 0. \label{equ:cond_2}
\end{align}

Consider an IRL problem $\IRL = (\partialMDP, \expertPolicy)$. A Q-function satisfies the specified conditions if and only if there exist $\zeta \in \mathbb{R}^{\stateSpace \times \actionSpace}_{\geq 0}$ and $V \in \mathbb{R}^{|\stateSpace|}$ such that:

\begin{equation}\label{equ:Q-function}
Q_{\learnedR, \learnedGamma} = - \expertFilterC{\expertPolicy}\zeta +E V.
\end{equation}

Given that $\expertPolicy \expertFilterC{\expertPolicy} = \mathbf{0}_{\stateSpace}$ and $\expertPolicy E = I_S$, the corresponding value function is $V_{\learnedR, \learnedGamma} = \expertPolicy Q_{\learnedR, \learnedGamma} =V$. For any $s\in \stateSpace$ and $a \in \actionSpace$ with $\expertPolicy(a|s) > 0$, we obtain $Q_{\learnedR, \learnedGamma}(s, a) = V(s) = V_{\learnedR, \learnedGamma}(s)$. This establishes the first condition in equation <ref>. If $a \in \actionSpace$ has $\expertPolicy(a|s) = 0$, then $Q_{\learnedR, \learnedGamma}(s, a) = - \zeta(s, a) + V(s) = - \zeta(s, a) + V_{\learnedR, \learnedGamma}(s) \leq V_{\learnedR, \learnedGamma}(s)$. This verifies the second condition in equation <ref>. Conversely, if $Q_{\learnedR, \learnedGamma}$ fulfills the two conditions, we set $V = V_{\learnedR, \learnedGamma}$ and $\zeta = EV_{\learnedR, \learnedGamma}-Q_{\learnedR, \learnedGamma} \leq 0$.

Next, recall that $Q_{\learnedR, \learnedGamma} = \learnedR + \learnedGamma \transition \expertPolicy Q_{\learnedR, \learnedGamma}$. The Q-function can be written as the fixed point of the above Bellman equation: $Q_{\learnedR, \learnedGamma} = (I_{\stateSpace\times \actionSpace} - \learnedGamma \transition \expertPolicy )^{-1} \learnedR$, and for $\learnedGamma<1$, the matrix is invertible. In other words, with fixed $\expertPolicy$, $\transition$, and $\learnedGamma<1$, there is a one-to-one correspondence between Q-functions and rewards. From equation <ref>, we obtain:

\begin{align}
\learnedR & = (I_{\stateSpace\times \actionSpace} - \learnedGamma \transition \expertPolicy ) ( - \expertFilterC{\expertPolicy}\zeta +EV) \nonumber\\
& =  - \expertFilterC{\expertPolicy}\zeta + \learnedGamma \transition \expertPolicy \expertFilterC{\expertPolicy}\zeta + (E - \learnedGamma \transition \expertPolicy E)V\nonumber\\
& =  - \expertFilterC{\expertPolicy}\zeta + (E - \learnedGamma \transition)V,
\end{align}

since $\expertPolicy \expertFilterC{\expertPolicy} = \mathbf{0}_S$ and $\expertPolicy E = I_S$.

§.§ Proof for Theorem <ref>

This proof is adapted from Theorem 3.1 in Metelli et al., 2021. Note that $\gtR$ in Theorem <ref> is the ground-truth reward function and has the corresponding ground-truth discount factor $\gtGamma$. Using Lemma <ref>, we express reward functions $\gtR \in \feasibleSet{\IRL}$ and $\learnedR \in \feasibleSet{\approxIRL}$ as:

\begin{align}
\gtR & = -\expertFilterC{\expertPolicy}\zeta + (E - \gtGamma \transition)V, \\
\learnedR & = -\expertFilterC{\approxExpertPolicy}\hat{\zeta} + (E - \learnedGamma \transition)\hat{V},
\end{align}

where $V, \hat{V} \in \mathbb{R}^{\stateSpace}$ and $\zeta, \hat{\zeta} \in \mathbb{R}^{\stateSpace \times \actionSpace}_{\geq 0}$. To find the existence of $\learnedR \in \feasibleSet{\approxIRL}$, we choose $\hat{V} =(E - \learnedGamma \transition)^{-1} (E - \gtGamma \transition)V$ and $\hat{\zeta} = \expertFilterC{\expertPolicy}\zeta$. Then:

\begin{align}
\gtR - \learnedR  = & - (\expertFilterC{\expertPolicy}\zeta - \expertFilterC{\approxExpertPolicy}\expertFilterC{\expertPolicy}\zeta) + (E - \gtGamma \transition)V - (E - \learnedGamma \transition)(E - \learnedGamma \transition)^{-1} (E - \gtGamma \transition)V \nonumber \\
= & - (I_{\stateSpace \times \actionSpace} - \expertFilterC{\approxExpertPolicy})\expertFilterC{\expertPolicy}\zeta \nonumber \\
= & - \expertFilter{\approxExpertPolicy}\expertFilterC{\expertPolicy}\zeta
\end{align}

As the expert-filter-complement $\expertFilterC{\approxExpertPolicy}$ is linear and sums with the expert-filter to unity, i.e., $\expertFilter{\approxExpertPolicy} + \expertFilterC{\approxExpertPolicy} = I_{\stateSpace \times \actionSpace}$, we get:

\begin{equation}
\lvert \gtR - \learnedR \rvert \leq\expertFilter{\approxExpertPolicy}\expertFilterC{\expertPolicy}\zeta.
\end{equation}

Finally, we obtain $\left\lVert\zeta\right\rVert_{\infty} \leq \frac{R_{\max}}{1-\gtGamma}$ by using the condition $\left\lVert\gtR\right\rVert \leq R_{\max}$.

§.§ Proof of Theorem <ref>

To prove Theorem <ref>, we need three lemmas.

For any MDP $\MDP$ with rewards in $[0, R_{max}]$, $\forall \pi : \stateSpace \to \actionSpace$ and $\learnedGamma \leq \gtGamma$,

\begin{equation}
\VFunction{\pi}{\gtR}{\learnedGamma} \leq \VFunction{\pi}{\gtR}{\gtGamma} \leq   \VFunction{\pi}{\gtR}{\learnedGamma} + \frac{\gtGamma - \learnedGamma}{(1-\gtGamma)(1-\learnedGamma)}R_{max}
\end{equation}

Hence, we have the following upper bound:

\begin{equation}
\left\lVert\VFunction{\optimalPolicy{\gtR}{\gtGamma}}{\gtR}{\gtGamma}
- \VFunction{\optimalPolicy{\gtR}{\gtGamma}}{\gtR}{\learnedGamma}\right\rVert_{\infty} \leq \frac{\gtGamma - \learnedGamma}{(1-\gtGamma)(1-\learnedGamma)}R_{max}
\end{equation}

Intuitively, Lemma <ref> measures the performance discrepancy of a policy $\pi$ when evaluated under two different discount factors: $\learnedGamma$ and $\gtGamma$.

For any $\MDP = ( \stateSpace, \actionSpace, \transition, \learnedR, \learnedGamma )$ with $\learnedR$ bounded by $[0, R_{max}]$,

\begin{equation}
\left\lVert\VFunction{\optimalPolicy{\gtR}{\learnedGamma}}{\gtR}{\learnedGamma} - \VFunction{\optimalPolicy{\learnedR}{\learnedGamma}}{\gtR}{\learnedGamma}\right\rVert_{\infty} \leq 2 \underset{\pi \in \Pi_{\learnedGamma}}{\max} \left\lVert\VFunction{\pi}{\gtR}{\learnedGamma} - \VFunction{\pi}{\learnedR}{\learnedGamma}\right\rVert_{\infty}
\end{equation}

$\forall s \in \stateSpace,$

\begin{align}
&\VFunction{\optimalPolicy{\gtR}{\learnedGamma}}{\gtR}{\learnedGamma}(s) -
\VFunction{\optimalPolicy{\learnedR}{\learnedGamma}}{\gtR}{\learnedGamma}(s) \nonumber\\
= & (\VFunction{\optimalPolicy{\gtR}{\learnedGamma}}{\gtR}{\learnedGamma}(s) - \VFunction{\optimalPolicy{\gtR}{\learnedGamma}}{\learnedR}{\learnedGamma}(s) )
- (\VFunction{\optimalPolicy{\learnedR}{\learnedGamma}}{\gtR}{\learnedGamma}(s) - \VFunction{\optimalPolicy{\learnedR}{\learnedGamma}}{\learnedR}{\learnedGamma}(s) )
+ (\VFunction{\optimalPolicy{\gtR}{\learnedGamma}}{\learnedR}{\learnedGamma}(s) - \VFunction{\optimalPolicy{\learnedR}{\learnedGamma}}{\learnedR}{\learnedGamma}(s) ) \nonumber \\
\leq & (\VFunction{\optimalPolicy{\gtR}{\learnedGamma}}{\gtR}{\learnedGamma}(s) - \VFunction{\optimalPolicy{\gtR}{ \learnedGamma}}{\learnedR}{\learnedGamma}(s))
- (\VFunction{\optimalPolicy{\learnedR}{\learnedGamma}}{\gtR}{\learnedGamma}(s) - \VFunction{\optimalPolicy{\learnedR}{\learnedGamma}}{\learnedR}{\learnedGamma}(s))\nonumber\\
\leq &2\underset{\pi \in \Pi_{\learnedGamma}}{\max} \lvert\VFunction{\pi}{\gtR}{\learnedGamma}(s) - \VFunction{\pi}{\learnedR}{\learnedGamma}(s)\rvert.
\end{align}

Intuitively, Lemma <ref> measures the difference between V-functions of two policies: the optimal policy under the ground-truth reward function $\gtR$, and the one under the estimated reward function $\learnedR$. Both are evaluated using $\gtR$ and the effective discount factor $\learnedGamma$. Lemma <ref> shows that this difference is at most double the highest V-function difference among policies in $\Pi_{\learnedGamma}$, when evaluated with $\gtR$ and $\learnedR$. This connects the value difference between two optimal policies evaluated under the ground truth reward to the difference in the same policy evaluated using the ground truth and estimated rewards respectively.

Let $\partialMDP = ( \stateSpace, \actionSpace, \transition )$ be a partial MDP, and let $\gtR \in \mathbb{R}^{\stateSpace \times \actionSpace}_{\geq 0}$ be the ground-truth reward function and $\learnedR \in \mathbb{R}^{\stateSpace \times \actionSpace}_{\geq 0}$ be the estimated reward function with the discount factor $\learnedGamma$, and let $\pi$ be a policy. Then the following inequality holds:

\begin{equation}
\left\lVert\VFunction{\pi}{\gtR}{\learnedGamma} - \VFunction{\pi}{\learnedR}{\learnedGamma}\right\rVert_{\infty} \leq \frac{1}{1-\learnedGamma} \left\lVert\gtR - \learnedR\right\rVert_{\infty}
\end{equation}

From the bellman equation, we have:

\begin{equation}
\VFunction{\pi}{\gtR}{\learnedGamma} = \pi \gtR + \learnedGamma \pi \transition \VFunction{\pi}{\gtR}{\learnedGamma}.
\end{equation}

Rearrange this, we will have $\VFunction{\pi}{\gtR}{\learnedGamma} = (I_{\stateSpace} - \learnedGamma \pi \transition)^{-1}\pi \gtR$. Therefore,

\begin{align}
\VFunction{\pi}{\gtR}{\learnedGamma} - \VFunction{\pi}{\learnedR}{\learnedGamma} & = (I_{\stateSpace} - \learnedGamma \pi \transition)^{-1}\pi \gtR - (I_{\stateSpace} - \learnedGamma \pi \transition)^{-1}\pi \learnedR \nonumber \\
& = (I_{\stateSpace} - \learnedGamma \pi \transition)^{-1}\pi (\gtR - \learnedR)
\end{align}

For the $L_{\infty}$ inequality, we simply observe:

\begin{align}
\left\lVert\VFunction{\pi}{\gtR}{\learnedGamma} - \VFunction{\pi}{\learnedR}{\learnedGamma}\right\rVert_{\infty} & = \left\lVert(I_{\stateSpace} - \learnedGamma \pi \transition)^{-1}\pi (\gtR - \learnedR)\right\rVert_{\infty} \nonumber \\
& \leq \left\lVert(I_{\stateSpace} - \learnedGamma \pi \transition)^{-1}\right\rVert_{\infty} \left\lVert\pi\right\rVert_{\infty} \left\lVert\gtR - \learnedR\right\rVert_{\infty} \nonumber \\
& \leq \frac{1}{1-\learnedGamma}\left\lVert\gtR - \learnedR\right\rVert_{\infty}
\end{align}

where we exploited the fact that $\left\lVert(I_{\stateSpace} - \learnedGamma \pi \transition)^{-1}\right\rVert_{\infty} = \frac{1}{1-\learnedGamma}$ and that $\left\lVert\pi\right\rVert_{\infty} \leq 1$.

Using these three lemmas, we can now proceed to prove Theorem <ref>.

Proof of Theorem <ref>
$\forall s \in \stateSpace$

\begin{equation}
\VFunction{\optimalPolicy{\gtR}{\gtGamma}}{\gtR}{\gtGamma}(s) -\VFunction{\optimalPolicy{\learnedR}{\learnedGamma}}{\gtR}{ \gtGamma}(s) = (\VFunction{\optimalPolicy{\gtR}{\gtGamma}}{\gtR}{\gtGamma}(s) - \VFunction{\optimalPolicy{\gtR}{\gtGamma}}{\gtR}{ \learnedGamma}(s))  + ( \VFunction{\optimalPolicy{\gtR}{\gtGamma}}{\gtR}{ \learnedGamma}(s) - \VFunction{\optimalPolicy{\learnedR}{\learnedGamma}}{\gtR}{\gtGamma}(s)).
\end{equation}

Using Lemma <ref>, we obtain:

\begin{equation}
\left\lVert\VFunction{\optimalPolicy{\gtR}{\gtGamma}}{\gtR}{\gtGamma} - \VFunction{\optimalPolicy{\gtR}{\gtGamma}}{\gtR}{ \learnedGamma}\right\rVert_{\infty} \leq \frac{\gtGamma - \learnedGamma}{(1-\gtGamma)(1-\learnedGamma)}R_{max}.
\end{equation}

For the second term, we derive the following:

\begin{align}
\VFunction{\optimalPolicy{\gtR}{\gtGamma}}{\gtR}{\learnedGamma}(s) - \VFunction{\optimalPolicy{\learnedR}{\learnedGamma}}{\gtR}{ \gtGamma}(s) \leq & \VFunction{\optimalPolicy{\gtR}{ \gtGamma}}{\gtR}{\learnedGamma}(s) - \VFunction{\optimalPolicy{\learnedR}{ \learnedGamma}}{\gtR}{\learnedGamma}(s) \nonumber\\
\leq &  \VFunction{\optimalPolicy{\gtR}{\learnedGamma}}{\gtR}{\learnedGamma}(s) - \VFunction{\optimalPolicy{\learnedR}{\learnedGamma}}{\gtR}{\learnedGamma}(s) \nonumber\\
\leq &  2\underset{\pi \in \Pi_{\learnedGamma}}{\max} \lvert\VFunction{\pi}{\gtR}{\learnedGamma}(s) - \VFunction{\pi}{\learnedR}{\learnedGamma}(s)\rvert. \label{equ:V_bound}
\end{align}

The first line results from $\learnedGamma \leq \gtGamma$, the second line from $\VFunction{\optimalPolicy{\gtR}{ \learnedGamma}}{\gtR}{\learnedGamma}(s) \geq \VFunction{\optimalPolicy{\gtR}{ \gamma'}}{\gtR}{\learnedGamma}(s)$ for any $\gamma' \in [0, 1]$, and the last line utilizes Lemma <ref>.

Using Lemma <ref>, for any policy $\pi$, we get:

\begin{align} \label{equ:lemma3}
\left\lVert \VFunction{\pi}{\gtR}{\learnedGamma} - \VFunction{\pi}{\learnedR}{\learnedGamma}\right\rVert_{\infty} \leq \frac{1}{1-\learnedGamma} \left\lVert \gtR - \learnedR\right\rVert_{\infty}
\end{align}

By combining Equations <ref> and <ref>, we arrive at the inequality:

\begin{equation}
\left\lVert  \VFunction{\optimalPolicy{\gtR}{\gtGamma}}{\gtR}{\learnedGamma} - \VFunction{\optimalPolicy{\learnedR}{\learnedGamma}}{\gtR}{ \gtGamma}\right\rVert_{\infty}\leq \frac{2}{1-\learnedGamma} \left\lVert \gtR - \learnedR\right\rVert_{\infty}
\end{equation}

§.§ Proof of Theorem <ref>

Proof of Theorem <ref>
Recall from Theorem <ref> that the reward function estimation error, denoted by $\left\lVert\gtR - \learnedR\right\rVert$, is upper-bounded by $\expertFilterC{\expertPolicy} \expertFilter{\approxExpertPolicy}\zeta$. Here, $\expertFilter{\approxExpertPolicy}(.)$ represents the expert-filter that preserves function values only for actions taken by the approximate expert policy $\approxExpertPolicy(a|s)$, while $\expertFilterC{\expertPolicy}(.)$ is the expert-filter-complement that preserves values for actions not taken by the ground-truth expert policy $\expertPolicy(a|s)$. We use $\left\lVert\expertFilterC{\expertPolicy} \expertFilter{\approxExpertPolicy}\zeta\right\rVert_{\infty}$ to measure the global estimation error of the expert policy: as $\approxExpertPolicy$ approaches $\expertPolicy$, most entries of $\expertFilterC{\expertPolicy} \expertFilter{\approxExpertPolicy}\zeta$ become zero, resulting in $\left\lVert\expertFilterC{\expertPolicy} \expertFilter{\approxExpertPolicy}\zeta\right\rVert_{\infty}$ converging to zero.

We bound the global expert policy estimation error $\left\lVert\expertFilterC{\expertPolicy} \expertFilter{\approxExpertPolicy}\zeta\right\rVert_{\infty}$ using Hoeffding's inequality. Consider $N$ independent $(s_i, \pi^E(s_i))$ expert pairs, with each pair covering one state. For each sample $(s_i, \pi^E(s_i))$ from expert demonstrations, we let $a_i^j = \pi^E(s_i)$ represent the expert action, and its corresponding policy matrix $\widehat{\pi}^E_i$ be a $|S| \times |A|$ matrix with $[\widehat{\pi}^E_i]_{i, j} = 1$ and zeros elsewhere. The estimated expert policy matrix $\widehat{\pi}^{E}$ is obtained from $N$ such sampled matrices. As $N$ increases, our estimated expert policy converges to the ground-truth expert policy, i.e., $\widehat{\pi}^E \to \pi^E$. Note that $\expertFilterC{\expertPolicy} \expertFilter{\approxExpertPolicy}\zeta(s, a)$ is bounded in $[0, \frac{R_{\max}}{1-\learnedGamma}]$.
Applying Hoeffding's inequality, given expert samples covering $N$ states, we obtain

\begin{align}
\mathrm{Pr}\left(\left\lVert\expertFilterC{\expertPolicy} \expertFilter{\approxExpertPolicy}\zeta\right\rVert_{\infty} - 0 > t\right) \leq 2 \exp \{-\frac{2Nt^2}{(R_{\max}/(1-\learnedGamma))^2}\}. \label{equ:hoeffding}
\end{align}

In equation (<ref>), the error bound decreases with increasing $N$ and becomes $0$ when $N = \lvert \stateSpace \rvert$. This occurs because as $N$ approaches the size of the state space ($N \to \lvert \stateSpace \rvert$), the estimated expert policy converges to the ground-truth expert policy ($\approxExpertPolicy \to \expertPolicy$), rendering most entries of the expert filter term zero. When $\approxExpertPolicy = \expertPolicy$, all entries of the expert filter term become zero, making $\left\lVert \expertFilterC{\expertPolicy} \expertFilter{\approxExpertPolicy} \zeta\right\rVert_{\infty}$ exactly $0$. $\left\lVert \expertFilterC{\expertPolicy} \expertFilter{\approxExpertPolicy} \zeta\right\rVert_{\infty}$ approaching $0$ as $N \to \lvert \stateSpace \rvert$ is independent of Hoeffding’s inequality. In particular, it does not depend on the asymptotics of Hoeffding’s bound, which only tries to capture the sampling variance.

Next, we set the RHS of equation <ref> to $\frac{\delta}{|\stateSpace||\Pi_{\learnedGamma}|}$ and we solve for $t$:

\begin{align}
2 \exp \{-\frac{2Nt^2}{(R_{\max}/(1-\learnedGamma))^2}\} & =  \frac{\delta}{\lvert \stateSpace\rvert\lvert\Pi_{\learnedGamma}\rvert} \nonumber\\
\frac{2Nt^2}{(R_{\max}/(1-\learnedGamma))^2} &= \log \frac{\lvert\stateSpace\rvert\lvert\Pi_{\learnedGamma}\rvert}{2\delta} \nonumber\\
t &= \sqrt{\frac{(R_{\max}/(1-\learnedGamma))^2}{2N}\log \frac{\lvert\stateSpace\rvert\lvert\Pi_{\learnedGamma}\rvert}{2\delta}} \nonumber\\
t & = \frac{R_{\max}}{1-\learnedGamma}\sqrt{\frac{1}{2N}\log \frac{\lvert\stateSpace\rvert\lvert\Pi_{\learnedGamma}\rvert}{2\delta}}
\end{align}

Substitute $t$ into equation <ref>:

\begin{align}
& \left\lVert\VFunction{\optimalPolicy{\gtR}{\gtGamma}}{\gtR}{\gtGamma} -\VFunction{\optimalPolicy{\learnedR}{\learnedGamma}}{\gtR}{ \gtGamma}\right\rVert_{\infty} \nonumber \\
\leq & \frac{\gtGamma-  \learnedGamma}{(1-\gtGamma)(1-\learnedGamma)}R_{max} + \frac{2}{1- \learnedGamma} \left\lVert\gtR - \learnedR\right\rVert_{\infty} \nonumber \\
\leq &  \frac{\gtGamma -  \learnedGamma}{(1-\gtGamma)(1-\learnedGamma)}R_{max} + \frac{2}{1- \learnedGamma} \left\lVert\expertFilterC{\expertPolicy} \expertFilter{\approxExpertPolicy}\zeta\right\rVert_{\infty} \nonumber \\
\leq &  \frac{\gtGamma-  \learnedGamma}{(1-\gtGamma)(1-\learnedGamma)}R_{max} + \frac{2}{1- \learnedGamma} \frac{R_{\max}}{1-\learnedGamma}\sqrt{\frac{1}{2N}\log \frac{\lvert\stateSpace\rvert\lvert\Pi_{\learnedGamma}\rvert}{2\delta}}  \nonumber \\
= & \frac{\gtGamma-  \learnedGamma}{(1-\gtGamma)(1-\learnedGamma)}R_{max} + \frac{2R_{\max}}{(1-\learnedGamma)^2}\sqrt{\frac{1}{2N}\log \frac{\lvert\stateSpace\rvert\lvert\Pi_{\learnedGamma}\rvert}{2\delta}},
\end{align}

with probability $1-\delta$.

§ DETAILS OF THE TASKS

All tasks share a common action space, transition function with $9$ actions per state, and a $10\%$ chance of moving randomly.

Gridworld-simple. In each Gridworld-simple environment, there are $10 \times 10$ states with $4$ randomly selected goal states. The ground-truth reward function assigns $+1$ for goal states and $0$ for all others. The expert policy moves greedily towards the nearest goal.

Gridworld-hard. The Gridworld-hard environment consists of $15 \times 15$ states and $6$ random goal states. It has a larger state space and more goal states than Gridworld-simple, but shares the same reward function.

Objectworld-linear. Each Objectworld-linear environment has $10 \times 10$ states and $10$ randomly placed objects, each with a randomly assigned inner and outer color from the set $C = \{c_0, c_1\}$. Object states receive a reward of $+3$ for outer color $c_0$ and $+1$ for outer color $c_1$. All other states have a $0$ reward.

Objectworld-nonlinear. Objectworld-nonlinear differs from its linear counterpart only in the reward function. The reward depends on the outer colors of surrounding objects: $+1$ for states within 3 grids of $c_0$ and 2 grids of $c_1$, $-1$ for states within 3 grids of $c_1$, and $0$ otherwise.

§ MODIFICATIONS TO THE LINEAR PROGRAMMING IRL METHOD (LP-IRL)

The original objective function of LP-IRL [Ng & Russell, 2000] is formulated on the full state coverage of the expert policy and the ground-truth $\gtGamma$. We modified the objective function to extend it to our setting with varying partial state coverage and $\learnedGamma$. W.L.O.G, let $a_1$ be the uniquely optimal action for all states. The transition probability vector at state $s$ for the expert action is thus $\Pe(s) = P(.|s, a_1)$, while that for the rest of the actions $a \in \{a_2, ..., a_k\}$ be $\Pa(s) = P(.|s, a)$. Our modified objective function for LP-IRL is as follows:

Given expert demonstrations covering $N$ states,

\begin{align}
\underset{\learnedR}{\max}\sum_{i=1}^N \underset{a \in \{a_2, ..., a_k\}}{\min} &(\Pe(i)-\Pa(i))(I- \learnedGamma \approPe)^{-1} \learnedR  \nonumber \\
\text{subject to\;\;} & (\Pe(i)-\Pa(i))(I- \learnedGamma \approPe)^{-1}\learnedR \geq b \nonumber \\
& b>0, \forall a  \in \{a_2, ..., a_k\} \nonumber\\
& |\learnedR| \leq R_{max}, \text{for\;} i = 1, ..., N,
\label{equ:lp_objective}
\end{align}

whereas $\Pe$ is full expert policy transition matrix of size $|\stateSpace| \times |\stateSpace|$ such that $[\Pe](s, s') = \transition(s'| a_1, s)$, while $\approPe$ is an estimate of $\Pe$ from partial expert demonstrations covering only $N \leq |\stateSpace|$ states. Essentially, the transition matrix of the expert policy $\Pe$ is the combination of the transition function $\transition$ (known) and the expert policy $\pi^E$ (unknown). Therefore, estimating transition matrix of the expert policy $\approPe$ is equivalent to estimating the expert policy from expert demonstrations. Our modifications are highlighted below.

Estimate Expert Transition Matrix. We estimate $\approPe$ by setting the transitions of the undemonstrated states to 0. Using this estimation, the action choices at the undemonstrated states do not affect the constraints on the other states. In addition, the value of the undemonstrated state myopically reduced to the state reward function.

Use Different Discount Factors. Our objective function also allows $\learnedGamma$ to differ from the ground-truth $\gtGamma$. That is, with an estimated $\approPe$, we allow the mapping $\approFFunction{i}{\learnedGamma} = (\Pe(i)-\Pa(i))(I- \learnedGamma \approPe)^{-1}$ to take different $\learnedGamma$s to account the temporal effect of the policy at different horizons.

Remove L1 Regularization.
The original LP-IRL uses the $L_1$-regularization on the reward function, i.e., $|R|$, to resolve the ambiguity among the feasible reward functions. This assumption on the preferred reward function form can be a confounding factor to the performance of the induced policy, therefore we remove it to focus on the effect of horizons.

Enforce Uniquely Optimal Expert Policy. To enforce the induced policy to be uniquely optimal, we modified the constraints to be strictly positive, i.e., $b > 0$.

§ MODIFICATIONS TO THE MAXIMUM ENTROPY IRL METHOD (MAXENT-IRL)

Our theoretical analysis of the effective horizon stems from the error bound between two feasible reward function sets: the ground truth expert policy set and the approximated expert policy set derived from limited expert demonstrations. However, most IRL algorithms, such as Maximum Entropy IRL [Ziebart et al., 2008] and Maximum Margin IRL [Ratliff et al., 2006], obtain a single reward function from the feasible set using specific criteria. The error bound between the learned reward function and the ground-truth $\gtR$ may deviate from the bound between their corresponding feasible sets. In this section, we extend our theoretical insights to Maximum Entropy Inverse Reinforcement Learning [Ziebart et al., 2008] and demonstrate that our conclusions on the effective horizon are still applicable when choosing the reward function based on specific criteria.

§.§ Maximum Entropy IRL

MaxEnt-IRL is formulated for finite horizon MDPs with horizon $\gtHorizon$ and no discounting. The reward function is linear in the state feature, i.e., $r = \theta^{\gtHorizon}\phi(s)$. The reward of a trajectory $\tau = (s_0, ..., s_{\gtHorizon})$ is the undiscounted sum of all state rewards, where $f_{\gtHorizon}$ is the total feature count for the trajectory $\tau$. MaxEnt IRL aims to match the feature counts between the policy and the expert demonstrations while maximizing the entropy of the induced policy. This leads to a distribution over behaviors constrained to match feature expectations, as shown in Equation (<ref>).

\begin{equation}
p(\tau|\theta, \transition, \gtHorizon) \approx \frac{1}{Z(\theta, \transition, \gtHorizon)} \exp^{\theta^T f_{\gtHorizon}} \prod_{s_t, a_t, s_{t+1} \in \tau} \transition(s_{t+1}|s_t, a_t) \label{equ:maxent_dis}
\end{equation}

The MaxEnt IRL objective is to choose the reward parameter $\theta$ that maximizes the probability of expert demonstrations under the distribution in Equation (<ref>):

\begin{equation}
\theta^* := \underset{\theta}{\arg \max}\;\; L(\theta) = \underset{\theta}{\arg\max} \sum_{\tau_i \in demo} \log p(\tau_i|\theta, \transition, \gtHorizon) \label{equ:maxent_objective}
\end{equation}

The objective function in equation (<ref>) can be optimized using gradient-based methods, where the gradient is the difference between the empirical and learner's expected feature counts, expressed in terms of expected state visitation frequencies, $D_{s_i, \gtHorizon}$.

\begin{equation}
\nabla L(\theta) = \tilde{f} - \sum_{\tau \in demo} p(\tau|\theta, \transition)f_{\gtHorizon} = \tilde{f} - \sum_{s_i}D_{s_i, \gtHorizon}f_{s_i} \label{equ:maxent_gradient}
\end{equation}

§.§ Maximum Entropy IRL with varying Effective Horizon

To extend MaxEnt IRL to varying effective horizons, we optimize trajectories with horizon $\learnedHorizon \leq \gtHorizon$. The corresponding optimal trajectory distribution is given in Equation (<ref>), where $f_{\learnedHorizon}$ is the undiscounted sum of $\learnedHorizon$ consecutive states in trajectory $\tau = (s_0, ..., s_{\learnedHorizon})$.

\begin{equation}
p(\tau|\theta, \transition, \learnedHorizon) \approx \frac{1}{Z(\theta, \transition, \learnedHorizon)} \exp^{\theta^T f_{\learnedHorizon}} \prod_{t = 0}^{\learnedHorizon-1} \transition(s_{t+1}|s_t, a_t) \label{equ:maxent_dis_discounted}
\end{equation}

whereas the feature factor $f_{\learnedHorizon} = \sum_{t=0}^{\learnedHorizon} \phi(s_t)$ is the undiscounted sum of $\learnedHorizon$ consecutive states in trajectory $\tau = (s_0, ..., s_{\learnedHorizon})$.

To investigate the performance of varying effective horizons under the same data coverage, we adjust the expert trajectories' lengths to match the planning horizons $\learnedHorizon$, while maintaining the total number of demonstrated states constant. Given that the expert covers $N$ states, for each effective horizon $\learnedHorizon$, we collect $N//\learnedHorizon$ trajectories with random initial states. Consequently, the gradient of the objective function is modified as shown in Equation (<ref>):

\begin{align}
\nabla L(\theta, \learnedHorizon)  = \tilde{f}_{\learnedHorizon} - \sum_{\tau \in demo} p(\tau|\theta, \transition, \learnedHorizon)f_{\learnedHorizon}   = \tilde{f}_{\learnedHorizon} - \sum_{s_i}D_{s_i, \learnedHorizon}f_{s_i} \label{equ:maxent_gradient_discounted}
\end{align}

where the expert expected feature vector $\tilde{f}_{\learnedHorizon}$ and the induced state visitation frequency $D{s_i, \learnedHorizon}$ consider only trajectories with length $\learnedHorizon$.

Our method for collecting expert demonstrations differs from the standard IRL approaches, where expert demonstrations are fixed and given upfront. Instead, we generate expert trajectories independently for each horizon $\learnedHorizon$ by rolling out trajectories with random initial states using the expert policy.

An alternative approach is to augment the fixed set of expert trajectories with length $\gtHorizon$ by breaking them into $\gtHorizon-\learnedHorizon+1$ shorter segments each with length $\learnedHorizon$. However, this method can slightly underestimate the visitation frequency of the final states of the original trajectories due to uniform sampling over the first $\gtHorizon-\learnedHorizon+1$ states. Our data collection method eliminates the potential bias that may arise from the quality of the expert demonstrations. In addition, our initial state distribution $\rho_0$ is a uniform distribution over the entire state space, which ensures a good approximation of the true state visitation frequency of the expert policy.

§.§ Results

The performance trends of MaxEnt-IRL align with those of LP-IRL, further supporting our theoretical results. Table <ref> provides a summary of the performance. Figure <ref> demonstrates how the optimal horizon $\optimalHorizon$ changes with increasing expert coverage for MaxEnt-IRL.
Figure <ref> summarizes cross-validation results for MaxEnt-IRL.

Optimal horizons ($\optimalHorizon$) for MaxEnt-IRL at varying expert demonstration coverage. We obtain the top 3 $\optimalHorizon$s for each coverage using the algorithm in Section <ref>. Orange curves show how $\optimalHorizon$ changes with expert coverage, while green curves display corresponding error counts. The ground-truth $\gtHorizon = 20$ is depicted by a grey line, with corresponding error lines in blue. The trends are consistent with LP-IRL.

Cross-validation results for four tasks on MaxEnt-IRL. The $x$-axis represents expert demonstration coverage, while the $y$-axis shows error count differences in all states for various $\optimalHorizon$s: $\optimalHorizonCv$ learned via cross-validation, and $\optimalHorizonCvAll$ chosen optimally using the oracle. Orange dots depict error count differences between the induced policies of $\optimalHorizonCv$ and $\optimalHorizonCvAll$, while blue dots represent differences between the induced polices of $\gtHorizon$ and $\optimalHorizonCvAll$.