# Aargh! End-to-end Retrieve & Generate for Task-oriented Dialog Systems

Tomáš Nekvinda and Ondřej Dušek
Charles University, Faculty of Mathematics and Physics
Institute of Formal and Applied Linguistics
Prague, Czech Republic
<EMAIL_ADDRESS>

# AARGH! End-to-end, Action-Aware Retrieval-Generation Hybrid for Task-
oriented Dialog

Tomáš Nekvinda and Ondřej Dušek
Charles University, Faculty of Mathematics and Physics
Institute of Formal and Applied Linguistics
Prague, Czech Republic
<EMAIL_ADDRESS>

# AARGH! End-to-end, Action-Aware Retrieval-Generation Hybrid Model for Task-
Oriented Dialog

Tomáš Nekvinda and Ondřej Dušek
Charles University, Faculty of Mathematics and Physics
Institute of Formal and Applied Linguistics
Prague, Czech Republic
<EMAIL_ADDRESS>

# AARGH! End-to-end Retrieve & Generate for Task-Oriented Dialog

Tomáš Nekvinda and Ondřej Dušek
Charles University, Faculty of Mathematics and Physics
Institute of Formal and Applied Linguistics
Prague, Czech Republic
<EMAIL_ADDRESS>

# AARGH! End-to-end Retrieval-Generation for Task-Oriented Dialog

Tomáš Nekvinda and Ondřej Dušek
Charles University, Faculty of Mathematics and Physics
Institute of Formal and Applied Linguistics
Prague, Czech Republic
<EMAIL_ADDRESS>

###### Abstract

We introduce AARGH, an end-to-end task-oriented dialog system combining
retrieval and generative approaches in a single model, aiming at improving
dialog management and lexical diversity of outputs. The model features a new
response selection method based on an action-aware training objective and a
simplified single-encoder retrieval architecture which allow us to build an
end-to-end retrieval-enhanced generation model where retrieval and generation
share most of the parameters.

On the MultiWOZ dataset, we show that our approach produces more diverse
outputs while maintaining or improving state tracking and context-to-response
generation performance, compared to state-of-the-art baselines.

##  1 Introduction

Most research task-oriented dialog models nowadays focus on end-to-end
modeling, i.e., the whole dialog system is integrated into a single neural
network Wen et al. (2017); Ham et al. (2020). Although recent end-to-end
_generative_ approaches based on pre-trained language models produce fluent
and natural responses, they suffer from two major problems: (1) hallucinations
and lack of grounding (Dziri et al., 2021), which result in faulty dialog
management or responses inconsistent with the dialog state or database
results, and (2) blandness and low lexical diversity of outputs (Zhang et al.,
2020b). On the other hand, _retrieval-based_ dialog systems (Chaudhuri et al.,
2018) select the most appropriate response candidate from a human-generated
training set, thus producing varied outputs. However, their responses might
not fit the context and can lead to disfluent conversations, especially when
the set of candidates is sparse. This limits their usage to very large
datasets which do not support dialog state tracking or database access (Lowe
et al., 2015; Al-Rfou et al., 2016).

Several recent works focus on combining the retrieval and generative dialog
systems via response selection and subsequent refinement, i.e., _retrieval-
augmented generation_ (Pandey et al., 2018; Weston et al., 2018; Cai et al.,
2019b; Thulke et al., 2021). These models are used for open-domain
conversations or to incorporate external knowledge into task-oriented systems
and do not consider an explicit dialog state.

Our work follows the retrieve-and-refine approach, but we adapt it for
database-aware task-oriented dialog. We aim at improving diversity of produced
responses while preserving their appropriateness. In other words, we do not
retrieve any new information from an external knowledge base, instead, we
retrieve relevant training data responses to support the decoder in producing
varied outputs. To the best of our knowledge, we are the first to use
retrieval-augmented models in this context. Unlike previous works, we merge
the retrieval and generative components into a single neural network and train
both tasks jointly, instead of using two separately trained models. Our
contributions are summarized as follows:111Code:
https://github.com/Tomiinek/Aargh

Figure 1: Our retrieval-based generative task-oriented system (AARGH, see
Section 3.5). Numbers in module boxes mark the order of processing during
inference: (1) inputs are pushed through the shared context encoder and (2)
state encoder; (3) the state decoder produces the update to the current dialog
state. The new state is used to query the database whose outputs are
discretized, embedded, and (4) used in the retrieval encoder whose output is
reduced to a single vector via average pooling. The context embedding is used
to get the best response candidate (hint). Finally, (5) the response decoder,
which can attend to the state encoder outputs via cross-attention and is
conditioned on the database results and the hint, generates the final system
response to be shown to the user.

  * •

We propose a single-encoder retrieval model utilizing dialog action annotation
during training, and we show its superior retrieval capabilities in the task-
oriented setting compared to two-encoder baseline models Humeau et al. (2020).

  * •

We propose an end-to-end _task-oriented_ generative system with an
_integrated_ minimalistic retrieval module. We compare it to strong baselines
that model response selection and generation separately.

  * •

On the MultiWOZ benchmark (Budzianowski et al., 2018), our approaches
outperform previous methods in terms of lexical diversity and achieve
competitive or better results in automatic metrics and human evaluation.

##  2 Related Work

#### Task-Oriented Response Generation

Most current works focus on building multi-domain database-grounded systems.
The breeding ground for this research is the large-scale conversational
dataset MultiWOZ (Budzianowski et al., 2018; Eric et al., 2020; Zang et al.,
2020).

Recent models often benefit from _action annotation_. Zhang et al. (2020a) use
action-based data augmentation and a three-stage architecture, decoding the
dialog state, action, and response. Chen et al. (2019) generate responses
without state tracking, exploiting a hierarchical structure of the action
annotation. On the other hand, reinforcement learning models (Wang et al.,
2021) learn latent actions from data without using annotation.

Recent works focus on _end-to-end_ systems based on pre-trained language
models. Budzianowski and Vulic (2019) fine-tune GPT-2 (Radford et al., 2019)
to model task-oriented dialogs, Hosseini-Asl et al. (2020) enhance this
approach with explicitly decoded system actions. Peng et al. (2021b) use
auxiliary training objectives and machine teaching for GPT-2 fine-tuning. Lin
et al. (2020) introduced the encoder-decoder-based framework MinTL with BART
(Devlin et al., 2019a) or T5 (Kale and Rastogi, 2020) backbones (see Section
3.1).

#### Response Selection

can be viewed as scoring response candidates given a dialog context. A popular
approach is the dual encoder architecture (Lowe et al., 2015; Henderson et
al., 2019b) where the response and context encoders model a joint embedding
space. The encoders can take various forms: Henderson et al. (2019a) compare
encoders based on BERT (Devlin et al., 2019b) and custom encoders pre-trained
on Reddit; Wu et al. (2020) pre-train encoders specifically for task-oriented
conversations. Humeau et al. (2020) introduce poly-encoders, which produce
multiple context encodings and add an attention layer to allow rich
interaction with the candidate encoding (cf. Section 3.3).

#### Retrieval-Augmented Generation

To benefit from both retrieval and generative models, Weston et al. (2018)
proposed an open-domain dialog system utilizing a retrieval network and a
decoder to refine retrieved responses. Roller et al. (2021) further developed
this approach, using poly-encoders with a large pre-trained decoder. They
found that their decoder tends to ignore the retrieved response hints. To
combat this, they propose the $\alpha$-blending method (replacing retrieval
output with ground truth, see Section 3.2). Similarly, Gupta et al. (2021) and
Cai et al. (2019a, b) focus on retrieval-augmented open-domain dialog, but to
prevent the inflow of erroneous information into the generative part of their
models, they use semantic frames or reduced forms of retrieved responses
instead of raw response texts.

Thulke et al. (2021) aim at knowledge retrieval from external documents for
resolution of out-of-domain questions on MultiWOZ (Kim et al., 2020).
Shalyminov et al. (2020) present the only work using generation and retrieval
in a single model. They finetune GPT-2 (Radford et al., 2019) for response
generation in a low-resource task-oriented setup, retrieve alternative
responses based on the model’s embedding similarity, and choose between
generated and retrieved responses on-the-fly. However, their model is not
trained for retrieval, cannot alter retrieved responses, and does not take a
dialog state or database into account.

##  3 Method

We aim at end-to-end modeling of database-aware task-oriented systems, i.e.,
systems supporting both dialog state tracking and response generation tasks
Young et al. (2013). We combine retrieval and generative models to reduce
hallucinations and boost output diversity. We first describe our purely
generative baseline (Section 3.1), then explain baseline generation based on
retrieved hints (Section 3.2). We then introduce baseline retrieval models
(Section 3.3) and our action-aware retrieval (Section 3.4). Finally, we
describe AARGH, our single-model retrieval generation hybrid, in Section 3.5.
AARGH is shown in Figure 1; other setups are depicted in Appendix A.

###  3.1 Generative Baseline

Our purely-generative baseline model (Gen) follows MinTL (Lin et al., 2020).
It is based on an encoder-decoder backbone with a context encoder, shared
among two decoders: one for modeling the dialog state updates, the other for
producing the final system response. Both decoders attend to the encoded input
tokens via an attention mechanism.

The encoder input sequence consists of a concatenation of two parts: (1) past
dialog utterances prepended with _< |system|>_ or _< |user|>_ tokens, and (2)
the initial dialog state converted to a string, e.g., _hotel [area: center]
restaurant [food: African, pricerange: expensive]_. The first decoder is
conditioned only on the start-of-sequence token and predicts the dialog state
update as a difference between the current state and the initial state. The
second decoder is conditioned on the number of database results for each
queried domain, e.g. _train: 6_ if there are six matching results for a train
search, and generates the final response.

During inference, the input is passed through the encoder, then the state
update is predicted, merged with the initial dialog state, and this new state
is used to query the database (see Section 4 for details). The final system
response is predicted based on the context, state, and database results.

###  3.2 Retrieval-Augmented Response Generation

To combine the retrieval and generative approaches, we follow Weston et al.
(2018) and incorporate response _hints_ , i.e., the outputs of a retrieval
module (Sections 3.3, 3.4), into the generative module in their original form
as raw sub-word tokens. Specifically, we add the retrieved response prepended
with _< |hint|>_ to the input of Gen’s response decoder (Section 3.1),
alongside the database results.

Gupta et al. (2021) state that this straightforward token-based retrieve &
refine setup might lead to generating incoherent responses due to over-copying
of contextually irrelevant tokens. However, using more abstract outputs of the
retrieval module, e.g. semantic frames or salient words would go against our
goal of reducing blandness and increasing responses lexical diversity. To
smoothly control the amount of token copying, we follow Roller et al. (2021)
and use the so-called $\alpha$-blending. During training, we replace the
retrieved utterance with the ground-truth final response with probability
$\alpha$. This method also ensures that the decoder learns to attend to the
retrieval part of its input successfully.

###  3.3 Baseline Response Selection

We consider two baseline retrieval model variants:

#### Dual-encoder (DE)

follows the very popular retrieval architecture (Lowe et al., 2015; Humeau et
al., 2020) which makes use of context and response encoders. Both produce a
single vector in a joint embedding space. During training, the context
embedding and the corresponding response embedding are pushed towards each
other, while other responses in the training batch are used as negative
examples, i.e., cross-entropy loss is used:

$\mathcal{L}(S)=\frac{1}{N}\sum_{j}{\left(-S_{j,j}+\log{\sum_{i}{e^{S_{j,i}}}}\right)}$

where $S\in\mathbb{R}^{N\times N}$ is the similarity matrix between
_normalized_ encoded responses $\mathbf{e}^{r}$ and contexts $\mathbf{e}^{c}$
in the batch, specifically
$S_{i,j}=w\cdot(\mathbf{e}^{c}_{i}\cdot\mathbf{e}^{r}_{j})$, where $w>0$ is a
trainable scaling factor.

Inference-time retrieval is as simple as finding the nearest candidate
embedding given a context embedding. The context input is similar to Gen’s
(see Section 3.1): a concatenation of the current updated dialog state, the
number of matching database results and past user and system utterances.
Encoders are followed by average pooling and a fully-connected layer for
dimensionality reduction.

#### Poly-encoder (PE)

an extension of DE, aiming at richer interaction between the candidate and the
context. The candidate encoder is unchanged. In the context encoder, the
average pooling is replaced with two levels of dot-product attention (Vaswani
et al., 2017; Humeau et al., 2020). The first level summarizes the encoded
context tokens into $m$ vectors. The context tokens act as attention keys and
values; queries to this attention are $m$ learned embeddings (query codes).
The second attention level provides the candidate-context interaction: it
takes the $m$ context summary vectors as keys and values, and the candidate
encoder output acts as the query. The parameter $m$ provides trade-off between
inference complexity and richness of the context encoding. The loss term
remains the same.

###  3.4 Action-aware Response Selection

We argue that the dual- or poly-encoder models are not practical for the task-
oriented settings as their performance depends on the way negative examples
are sampled during training (Nugmanova et al., 2019). Choosing appropriate
negative examples is difficult in task-oriented datasets as system responses
are often very similar to each other (with the conversations being in a narrow
domain and following similar patterns). Therefore, we propose a method for
candidate selection based on system action annotation, which is usually
available in task-oriented datasets. We designed the method to be usable with
a single encoder only, but we also include a dual-encoder version for
comparison.

#### Action-aware-encoder (AAE)

Using two separate encoders to encode the response and the context might be
impractical due to large model size. Some recent works (e.g., Wu et al.
(2020); Roller et al. (2021)) use a single shared encoder instead, and
Henderson et al. (2020) discuss parameter sharing between the two encoders. In
view of that, we propose a single-encoder action-aware retrieval model. We
train it to produce embeddings of dialog contexts which are close to each
other if the corresponding responses in the training data have similar action
annotation. More precisely, we adapt Wan et al. (2018)’s generalized end-to-
end loss, originally developed for batch-wise training of speaker
classification from audio: To form training mini-batches, we first sample $M$
random dialog actions, and for each of those actions, we sample $N$ examples
that include the particular action in their system action annotation. We then
encode dialog contexts corresponding to the sampled examples into normalized
embeddings $\mathbf{e}_{m,n}$, and compute the similarity matrix as follows:

$S_{ji,k}=\begin{cases}w\cdot(\mathbf{e}_{j,i}\cdot\mathbf{c}^{\\{i\\}}_{j})&\text{if
k = j}\\\
w\cdot(\mathbf{e}_{j,i}\cdot\mathbf{c}^{\varnothing}_{k})&\text{otherwise}\end{cases}$
$\mathbf{c}^{A}_{j}=\frac{1}{N-|A|}\sum_{i\in[N]-A}\mathbf{e}_{j,i}$

where $S\in\mathbb{R}^{N\cdot M\times M}$, $i\in[N]$, $j,k\in[M]$, and
$A\subseteq[N]$ is a set of indices. Same as for DE, $w>0$ is a trainable
scaling factor of the similarity matrix. In other words, the similarity matrix
describes the similarity between embeddings of each example and centroids,
i.e., the means of $N$ embeddings that correspond to the same particular
action. For stability reasons and to avoid trivial solutions, we follow Wan et
al. (2018) and exclude $\mathbf{e}_{j,i}$ from the centroid calculation when
computing $S_{ji,j}$.

We then maximize the similarity between the examples and their corresponding
centroids while using other centroids as negative examples:

$\mathcal{L}(S)=\frac{1}{N\cdot
M}\sum_{j,i}{\left(-S_{ji,j}+\log{\sum_{k}{e^{S_{ji,k}}}}\right)}$

During inference, we rank the responses from the training set according to the
cosine similarity of their corresponding contexts and the query context.
Again, the contexts consist of the current updated dialog state, the number of
matching database results and past utterances.

#### Action-aware-dual-encoder (AADE)

This setup follows the DE architecture (see Section 3.3), but it is trained in
a similar way as AAE, i.e., we form training mini-batches identically and for
each of $M$ distinct actions in the batch, we treat all $N$ examples as
positive examples.

###  3.5 Hybrid End-to-end Model

To further simplify the retrieval-augmented setup, reduce the number of
trainable parameters and gain back computational efficiency, we introduce an
end-to-end Action-Aware Retrieval-Generative Hybrid model (AARGH), which
jointly models both response selection and context-to-response generation (see
Figure 1). It is a natural extension of the Gen generative model (Section
3.1), enabled by our new single-encoder action-aware response retrieval (AAE,
Section 3.4).

A new retrieval encoder, which produces normalized context embeddings, shares
most parameters with the original encoder, which is followed by the two
decoders and is partially responsible for state tracking and response
generation. To build the retrieval encoder, we fork the last $L$ layers of the
original encoder and condition them on the outputs of the shared preceding
layers, concatenated with an embedding of the number of current database
results. To obtain this embedding, we convert the number of database results
into a small set of bins, which are then embedded via a learnt embedding layer
of size $E$.222This conversion is dataset-specific and not used in other
compared models such as Gen. We use the label 0 if there are no results, 1 for
0 matching results, 2, 3, 4 if there are 1, 2 or 3 results, respectively, 5, 6
if there are less than 6 or 11 results, and 7 if there are 11 or more results.
The new retrieval encoder is followed by average pooling and trained using the
same objective as AAE (see Section 3.4).

During inference, we pass the input through the partially shared context
encoder and decode and update the dialog state. The new state is used to query
the database. Database results are embedded and added to the output of the
last encoder shared layer to form the input to the retrieval encoder, which
produces the context embedding and a retrieved response. Based on state,
database results, and retrieved response, the response decoder produces the
final (delexicalized) response.

##  4 Experimental Setup

#### Models

Our models are based on pre-trained models from HuggingFace (Wolf et al.,
2020): We implement Gen and the generative parts in our retrieval-based models
using T5-base (Kale and Rastogi, 2020). Retrieval encoders in DE, AADE, PE and
AAE are implemented as fine-tuned BERT-base (Devlin et al., 2019a). AARGH is
built upon T5-base, same as Gen; we fork the last $L=2$ out of $K=12$ encoder
layers. The choice of $L$ is a trade-off between model performance and
size.333We noticed a performance drop when using $L=1$, and $L=3$ did not
bring any large gain. The database embedding has size $E=4$. For simplicity,
we do not use specialized backbones pre-trained on dialogs such as ToD-BERT
(Wu et al., 2020). PE uses $m=16$ query codes (see Section 3.3) and single-
headed attention mechanisms.

Figure 2: Part of a short conversation from MultiWOZ. It has  user and  system
turns, and annotated  slot spans. Both, user and system affect the  dialog
state. Actions are shown below system texts.  Figure 3: t-SNE projection of
test set context embeddings (colored by domains) of retrieval modules of our
models. The colors indicate the different MultiWOZ domains that are associated
with the corresponding dialog turns.

#### Data and database

We experiment on the MultiWOZ 2.2 dataset (Budzianowski et al., 2018; Zang et
al., 2020) which is a popular dataset with around 10k task-oriented
conversations in 7 different domains such as trains, restaurants, or hotels
(see Figure 2). A single conversation can touch multiple domains. The dataset
has an associated database, dialog state annotation, dialog action annotation
of system turns, and slot value span annotation for easy delexicalization (Wen
et al., 2015), thus enabling development of realistic end-to-end dialog
systems.444Unlike the similar-sized Taskmaster (Byrne et al., 2019) and SGD
(Rastogi et al., 2020) datasets, which lack databases and annotation detail.
To query the database using the belief state, we use the fuzzy matching
implementation by Nekvinda and Dušek (2021). To filter out inactive domains
from database results during inference, we follow previous work and estimate
the currently active domain from dialog state updates.

#### Input and output format

We use the same formats for all models. Target responses are delexicalized
using MultiWOZ 2.2 span annotation, and we limit the context to 5 utterances.
MultiWOZ action labels include domain, action, and slot name, e.g., _train-
inform-price_. We remove domains from the labels to limit data sparsity.

#### Training procedure

DE, AADE, PE and AAE are trained in two stages. The retrieval part is trained
first and provides response hints to the generative model during the second
phase. Modules in AARGH are trained jointly, but we alternate parameter
updates for the retrieval encoder and the rest of the network. To do so, we
use two separate optimizers. AARGH’s hints used in the response decoder during
training are refreshed after every epoch. All models are optimized using Adam
(Kingma and Ba, 2015) and cosine learning rate decay with warmup. With respect
to memory limits of our hardware, we set $N=6$, $M=8$ for batch sampling
during training of retrieval parts of AAE and AARGH.

####  $\mathbf{\alpha}$-blending

We experiment with two $\alpha$-blending values: a conservative one
($\alpha=0.05$, marked “$\downarrow$ ”) and a greedy one ($\alpha=0.4$, marked
“$\uparrow$ ”), targeting a mostly generation-focused and a mostly retrieval-
focused setting.555The values were chosen empirically, based on preliminary
experiments on development data.

#### Decoding

We use greedy decoding for dialog state update generation. For response
generation, we report results with greedy decoding in Section 5 and with beam
search in Appendix B.

##  5 Evaluation and Results

We focus on end-to-end modeling, which includes dialog state tracking and
response generation. All reported results are on MultiWOZ test set with 1000
dialogs, averaged over 8 different random seeds. We generated responses given
ground truth contexts. We follow MinTL and predict the dialog state
cumulatively for each conversation turn, which means that state tracking
errors may compound. See Appendix C for an example end-to-end conversation
without any ground-truth information.

Setting | BLEU | Action IoU |  % full match |  % no match |  % uniq. hints
---|---|---|---|---|---
Random |  02.1 |  05.1 ± 0.2 |  01.1 |  85.0 |  93.5
DE |  08.9 | 34.7 ± 0.5 |  11.0 |  29.7 |  54.1
AADE |  07.9 | 30.9 ± 1.7 |  08.9 |  33.4 |  24.2
PE |  08.8 | 35.0 ± 0.8 |  11.4 |  28.9 |  44.1
AAE | 12.8 |  37.1 ± 0.2 |  14.5 |  28.6 |  88.6
AARGH | 12.6 | 36.6 ± 0.2 |  14.2 |  29.0 |  89.6
Table 1: Evaluation of retrieval components of our models (Section 3.3, 3.5).
See Section 5.1 for details.

###  5.1 Response selection

Setting | BLEU |  Inform |  Success | Unique trigrams | BCE | Hint-BLEU | Hint-copy | Joint acc.
---|---|---|---|---|---|---|---|---
Corpus | - |  93.7 |  90.9 | 25,212 | 3.37 | - | - | -
SOLOIST (Peng et al., 2021a) | 13.6 |  82.3 |  72.4 |  07,923 | 2.41 | - | - | -
PPTOD (Su et al., 2022) | 18.2 |  83.1 |  72.7 |  02,538 | 1.88 | - | - | -
MTTOD (Lee, 2021) | 19.0 |  85.9 |  76.5 |  04,066 | 1.93 | - | - | -
MinTL (Lin et al., 2020) | 19.4 |  73.7 |  65.4 |  02,525 | 1.81 | - | - | -
Gen (equiv. to MinTL) | 18.6 ± 0.3 |  77.0 ± 1.2 |  66.4 ± 1.0 |  03,209 | 1.94 | - | - | 54.1 ± 0.2
AAE (retrieval only) | 12.8 ± 0.1 |  79.9 ± 0.6 |  58.3 ± 0.7 | 22,457 | 3.34 | 100.0 | 100.0 % | -
_$\alpha$ =0.05_ | DE +Gen $\downarrow$ |  17.6 ± 0.3 |  80.9 ± 0.5 |  68.8 ± 0.6 |  08,190 | 2.36 | 32.5 | 15.2 % | 54.2 ± 0.1
AADE +Gen $\downarrow$ | 17.3 ± 0.3 |  81.2 ± 0.9 |  69.1 ± 1.0 |  06,613 | 2.29 | 26.7 | 12.8 % | 54.3 ± 0.1
PE +Gen $\downarrow$ | 17.4 ± 0.3 |  79.9 ± 0.9 |  66.8 ± 1.0 |  07,736 | 2.35 | 31.3 | 14.5 % |  54.4 ± 0.2
AAE +Gen $\downarrow$ | 17.5 ± 0.6 |  82.0 ± 1.0 |  70.3 ± 0.8 |  08,152 | 2.32 | 32.0 | 16.2 % | 54.2 ± 0.2
AARGH $\downarrow$ | 17.3 ± 0.3 |  81.2 ± 0.6 |  69.5 ± 0.5 |  08,200 | 2.33 | 28.4 | 14.2 % | 53.8 ± 0.2
_$\alpha$ =0.4_ | DE +Gen $\uparrow$ | 12.3 ± 0.3 |  87.8 ± 0.3 |  69.1 ± 0.5 | 18,800 | 3.20 | 80.4 | 76.5 % | 54.2 ± 0.2
AADE +Gen $\uparrow$ |  14.6 ± 0.4 |  81.0 ± 0.8 |  66.7 ± 0.4 | 10,723 | 2.72 | 51.7 | 44.8 % | 54.2 ± 0.1
PE +Gen $\uparrow$ | 12.9 ± 0.4 |  86.0 ± 0.8 |  67.1 ± 0.6 | 16,632 | 3.13 | 74.0 | 69.1% |  54.4 ± 0.1
AAE +Gen $\uparrow$ | 11.9 ± 0.2 |  90.5 ± 0.3 |  71.3 ± 0.3 | 19,436 | 3.23 | 91.1 | 89.3 % | 54.3 ± 0.2
AARGH $\uparrow$ | 12.1 ± 0.2 |  89.6 ± 0.2 |  70.7 ± 0.5 | 19,813 | 3.21 | 87.6 | 85.0 % | 53.6 ± 0.2
Table 2: Response generation and state tracking evaluation on MultiWOZ using
automatic metrics, including the bi-gram conditional entropy (BCE) and number
of unique trigrams. We compare previous work, the baseline and retrieval-based
generative models. See Section 5.2 for details about the metrics; Section 3, 4
for model descriptions.

First, we assess the performance of retrieval components of DE, AADE, PE, AAE
and AARGH. We cannot use the popular R@k metric (Chaudhuri et al., 2018) as
AAE and AARGH use embeddings of dialog contexts (not responses) of candidates
as the search criterion and would always score 100%. Instead, we use the
action annotation and measure the intersection over union (IoU), full-match
and no-match rates on sets of actions associated with top-1 retrieved and
ground-truth responses. We add BLEU (Papineni et al., 2002; Liu et al., 2016a)
between ground-truth and retrieved responses and the proportion of distinct
retrieval outputs to assess their lexical similarity to references and
diversity.

Table 1 shows that AAE and AARGH significantly outperform other setups on all
measures except for the no-match rate,666According to a paired t-test with 95%
confidence level. where PE has comparable results. This is expected as they
use the additional action annotation during training, unlike DE and PE. AADE
performs surprisingly bad. According to the unique hints rate, AAE and AARGH
retrieve a much wider range of outputs, which could improve lexical diversity
of final responses. The higher BLEU, Action IoU and full match rates suggest
that the models retrieve responses more similar to the ground truth.

Silhouette coefficient | DE | AADE | AAE | AARGH
---|---|---|---|---
per Domain | 0.098 | 0.179 | 0.151 | 0.159
per Action | 0.147 | 0.316 | 0.312 | 0.320
Table 3: Evaluation of domain and action separation (Section 5.1). We show
averages over 8 random seeds.

To further compare the approaches to response selection, we computed the
Silhouette coefficient (Rousseeuw, 1987) based on the active domain and action
annotation (see Table 3).777In the case of action-based clustering, we treat
each action as a separate cluster; each example can belong to multiple
clusters. The clustering measure is calculated for each cluster and averaged
over all actions which are weighted by the size of the corresponding clusters.
We omit PE because its context embeddings depend on queries, i.e., the
candidate embeddings (other models output the same context regardless of
candidates). DE has the worst results; other systems perform similarly, but
AARGH is the best on action separation while AADE has the best scores for
domains.

We see that AADE’s context encoder is successful in clustering, but it lags
behind in terms of correct action selection. Unlike AARGH and AAE, AADE
retrieves candidates based on response embeddings. We hypothesize that lower
response variability (compared to context variability) leads the model to
prefer responses seen more frequently during training. AARGH and AAE are not
affected by this as they use purely context-based retrieval.

Figure 3 provides a visualisation of the domain clusters projected using t-SNE
(van der Maaten and Hinton, 2008). It supports the findings of our evaluation
based on the Silhouette coefficient: We see that visualisations of AARGH and
AADE embedding spaces look similarly whereas DE’s clusters appear more noisy.

###  5.2 Response generation

System |  Response
---|---
Context |  User: I need a taxi to take me to Yippee Noodle Bar by 9:45.
Corpus |  Absolutely, where will the taxi be picking you up from today?
Gen |  I can help with that. Where are you departing from?
DE +Gen $\downarrow$ |  Where will you be departing from?
AARGH $\downarrow$ |  Okay, I can help with that. Where are you coming from?
AARGH $\uparrow$ |  Of course, I just need to know your destination so I can book that for you.
Context |  […] User: It does, thanks. Can you tell me about a hotel called the Warkworth House? System: I sure can. They are a guesthouse in the east. They are moderately priced and 4-star rated. They also offer free internet and free parking. Can I help book a room? User: Yes I would like to book it for 3 nights starting on Wednesday for 4.
Corpus |  I have made the reservation for you. The confirmation number is [ref]. They will expect you on [bookday]. Is there anything else I can get for you?
Gen |  I have made those reservations and your reference number is [ref].
DE +Gen $\downarrow$ |  I’d be happy to make that booking for you. For how many people?
AARGH $\downarrow$ |  I have successfully booked a room for you at [name] for [bookpeople] starting on [bookday] for [bookstay] nights. Your reference number is [ref]. Would that be all for you?
AARGH $\uparrow$ |  You are all set! Reference number [ref]. Is there anything else I can help you with?
Context |  User: I am planning a trip in Cambridge
Corpus |  Great! Is there a certain restaurant you’re looking for?
Gen |  I can help you with that. What type of food are you interested in?
DE +Gen $\downarrow$ |  I can help you with that. What type of food are you looking for?
AARGH $\downarrow$ |  Great! Do you need assistance with transportation arrangements?
AARGH $\uparrow$ |  Great! Would you like to book a train to take you there?
Table 4: Side-by-side system output comparison (see Sections 3 and 4 for model
details, see Section 5.2 for example description). The responses are
continuations of conversations SNG0016, MUL1091, and PMUL4542 from MultiWOZ.

We evaluate the response generation abilities of our models using automatic
metrics and human assessment of delexicalized texts (see Table 4 for
examples).

#### Evaluation with automatic metrics

We use the corpus-based evaluator by Nekvinda and Dušek (2021) to measure
commonly used metrics on MultiWOZ (Inform & Success rates, BLEU) as well as
lexical diversity measures, namely the number of distinct trigrams in the
outputs and bigram conditional entropy Li et al. (2016); Novikova et al.
(2019). State tracking joint accuracy is calculated with scripts adapted from
TRADE (Wu et al., 2019). To better understand the effect of using retrieved
hints and to quantify the amount of copying, we calculate BLEU between
retrieved hints and final generated responses (Hint-BLEU) and the proportion
of generated responses exactly matching the corresponding retrieved hints
(Hint-copy).

We include comparisons with recent strong end-to-end models on MultiWOZ:
SOLOIST (Peng et al., 2021a), MTTOD (Lee, 2021), PPTOD (Su et al., 2022), and
MinTL (Lin et al., 2020), which has the same architecture as Gen. To show the
importance of the generative parts of our models, we also include AAE without
the refining decoder.

Table 2 shows scores obtained with greedy decoding (see Appendix B for beam
search results). All models have similar state tracking performance. AARGH has
slightly lower numbers, which is not surprising as it shares a substantial
part of the encoder with its retrieval component. As expected, we notice a
huge difference in Hint-BLEU and Hint-copy of versions with different
$\alpha$-blending probabilities ($\downarrow$ vs. $\uparrow$).888Hint-copy of
15% roughly means one turn per dialog. The performance boost over Gen and
retrieval-only AAE is, for $\downarrow$ variants, mainly in terms of Success.
In $\uparrow$, more frequent hint copying reduces BLEU and improves lexical
diversity; we also see higher Inform. AAE +Gen and AARGH (both $\downarrow$
and $\uparrow$) perform better than corresponding DE +Gen or PE +Gen on Inform
and Success rates.999According to a paired t-test with 95% confidence level.
Differences between AAE +Gen and AARGH are not statistically significant and
their Success scores are better than MinTL, competitive with PPTOD and SOLOIST
but lower than MTTOD. In terms of lexical diversity, all models are better
than most generative baselines.101010The $\downarrow$ variants are similar to
SOLOIST, which, however, reaches diversity by employng sampling (Holtzman et
al., 2020) instead of greedy decoding.

| Gen | DE +Gen $\downarrow$ | AARGH $\downarrow$ | AARGH $\uparrow$
---|---|---|---|---
Mean Ranking | 2.03 | 1.99 | 1.91 | 2.3
Ranked #1 | 36.1% | 35.5% | 40.8% | 37.9%
Ranked #2 | 34.7% | 36.7% | 33.5% | 18.8%
Ranked #3 | 18.8% | 20.5% | 19.7% | 18.8%
Ranked #4 | 10.4% |  07.2% |  06.1% | 24.6%
Table 5: Human evaluation results – mean ranks (1-4) established from 50
evaluated conversations.

#### Human evaluation

We arranged an in-house human evaluation on the delexicalized outputs of Gen
(i.e., MinTL’s architecture), DE +Gen $\downarrow$, AARGH $\downarrow$ and
AARGH $\uparrow$. We used side-by-side relative ranking evaluation, which has
been repeatedly found to increase consistency compared to rating isolated
examples (Callison-Burch et al., 2007; Belz and Kow, 2010; Kiritchenko and
Mohammad, 2017). Participants were given full dialog context and current
database results, and we asked them to rank responses of the compared models
from the best-fitting to the worst, where multiple responses could be ranked
the same (see Appendix D for details). We collected rankings for 346 turns of
50 conversations from 5 linguists with experience in natural language
generation. All of them were given a different set of dialogs and they were
instructed to focus on consistency with the context and database results,
naturalness, and attractiveness of the responses. See Table 5 for results.

Although AARGH $\uparrow$ scored the best on automatic metrics, it has worse
mean ranks than other models, which all have similar mean
ranks.111111According to Friedman test with 95% confidence level and Nemenyi
post-hoc test; only the difference between AARGH $\uparrow$ and other models
is statistically significant. This confirms previous findings of low
correlation between automatic metrics and human assessments Liu et al.
(2016b); Novikova et al. (2017). Upon detailed manual error analysis, we found
that AARGH $\uparrow$ often copies whole hints including words that do not fit
the context (see the top example in Table 4), i.e., contradictions to earlier
statements or noisy non-delexicalized values from the training set. AARGH
$\downarrow$ performs slightly better than the baselines and is more often
ranked best and least often ranked worst. The bottom two examples in Table 4
demonstrate that AARGH $\downarrow$ is often able to provide more detailed
responses and uses more varied vocabulary, compared to the baseline.

##  6 Conclusion

We present AARGH, an end-to-end task-oriented dialog system, combining
retrieval and generative approaches. It uses an embedded single-encoder
retrieval component which extends a purely generative model without the need
for a large number of new parameters. AARGH features an action-aware response
selection training objective. Our experiments on the MultiWOZ dataset show
that AARGH outperforms baselines in terms of automatic metrics and human
evaluation and it is competitive with state-of-the-art models such as SOLOIST
or MTTOD. We showed that our proposed action-aware retrieval training
objective supports retrieval of a larger variety of unique and relevant
responses in the task-oriented setting and makes efficient use of the
available system action annotation. Further, using the retrieval module
improves dialog management in terms of the Success rate. A limitation of our
approach is the need for careful hyper-parameter setting, coupled with the
risk of overuse of retrieved responses that match the dialogue state but are
not appropriate for the context.

In future work, we would like to confirm our results on more datasets and
explore more complex ways of usage of the retrieved responses to encourage the
model to copy interesting language structures while ignoring inappropriate
tokens or relics of faulty delexicalization.

## Acknowledgements

This research was supported by Charles University projects GAUK 373921, SVV
260575 and PRIMUS/19/SCI/10, and by the European Research Council (Grant
agreement No. 101039303 NG-NLG). It used resources provided by the
LINDAT/CLARIAH-CZ Research Infrastructure (Czech Ministry of Education, Youth
and Sports project No. LM2018101).

## References

  * Al-Rfou et al. (2016) Rami Al-Rfou, Marc Pickett, Javier Snaider, Yun hsuan Sung, Brian Strope, and Ray Kurzweil. 2016.  Conversational Contextual Cues: The Case of Personalization and History for Response Ranking.  _arXiv:1606.00372_.
  * Belz and Kow (2010) Anja Belz and Eric Kow. 2010.  Comparing Rating Scales and Preference Judgements in Language Evaluation.  In _INLG 2010 - Proceedings of the Sixth International Natural Language Generation Conference_ , Trim, Co. Meath, Ireland.
  * Budzianowski and Vulic (2019) Pawel Budzianowski and Ivan Vulic. 2019.  Hello, It’s GPT-2 \- How Can I Help You? Towards the Use of Pretrained Language Models for Task-Oriented Dialogue Systems.  In _Proceedings of the 3rd Workshop on Neural Generation and Translation@EMNLP-IJCNLP 2019_ , pages 15–22, Hong Kong.
  * Budzianowski et al. (2018) Paweł Budzianowski, Tsung-Hsien Wen, Bo-Hsiang Tseng, Iñigo Casanueva, Stefan Ultes, Osman Ramadan, and Milica Gašić. 2018.  MultiWOZ - A Large-Scale Multi-Domain Wizard-of-Oz Dataset for Task-Oriented Dialogue Modelling.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 5016–5026, Brussels, Belgium.
  * Byrne et al. (2019) Bill Byrne, Karthik Krishnamoorthi, Chinnadhurai Sankar, Arvind Neelakantan, Ben Goodrich, Daniel Duckworth, Semih Yavuz, Amit Dubey, Kyu-Young Kim, and Andy Cedilnik. 2019.  Taskmaster-1: Toward a Realistic and Diverse Dialog Dataset.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019_ , pages 4515–4524, Hong Kong, China.
  * Cai et al. (2019a) Deng Cai, Yan Wang, Wei Bi, Zhaopeng Tu, Xiaojiang Liu, Wai Lam, and Shuming Shi. 2019a.  Skeleton-to-Response: Dialogue Generation Guided by Retrieval Memory.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Volume 1 (Long and Short Papers)_ , pages 1219–1228, Minneapolis, MN, USA.
  * Cai et al. (2019b) Deng Cai, Yan Wang, Wei Bi, Zhaopeng Tu, Xiaojiang Liu, and Shuming Shi. 2019b.  Retrieval-guided Dialogue Response Generation via a Matching-to-Generation Framework.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing, EMNLP-IJCNLP 2019_ , pages 1866–1875, Hong Kong, China.
  * Callison-Burch et al. (2007) Chris Callison-Burch, Cameron S. Fordyce, Philipp Koehn, Christof Monz, and Josh Schroeder. 2007.  (meta-) Evaluation of Machine Translation.  In _Proceedings of the Second Workshop on Statistical Machine Translation, WMT@ACL 2007_ , pages 136–158, Prague, Czech Republic.
  * Chaudhuri et al. (2018) Debanjan Chaudhuri, Agustinus Kristiadi, Jens Lehmann, and Asja Fischer. 2018.  Improving Response Selection in Multi-Turn Dialogue Systems by Incorporating Domain Knowledge.  In _Proceedings of the 22nd Conference on Computational Natural Language Learning, CoNLL 2018_ , pages 497–507, Brussels, Belgium.
  * Chen et al. (2019) Wenhu Chen, Jianshu Chen, Pengda Qin, Xifeng Yan, and William Yang Wang. 2019.  Semantically Conditioned Dialog Response Generation via Hierarchical Disentangled Self-Attention.  In _Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28-, Volume 1: Long Papers_ , pages 3696–3709.
  * Devlin et al. (2019a) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019a.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, MN, USA.
  * Devlin et al. (2019b) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019b.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, MN, USA.
  * Dziri et al. (2021) Nouha Dziri, Andrea Madotto, Osmar Zaïane, and Avishek Joey Bose. 2021.  Neural Path Hunter: Reducing Hallucination in Dialogue Systems via Path Grounding.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, EMNLP 2021_ , pages 2197–2214, Virtual Event / Punta Cana, Dominican Republic.
  * Eric et al. (2020) Mihail Eric, Rahul Goel, Shachi Paul, Abhishek Sethi, Sanchit Agarwal, Shuyang Gao, Adarsh Kumar, Anuj Goyal, Peter Ku, and Dilek Hakkani-Tur. 2020.  MultiWOZ 2.1: A Consolidated Multi-Domain Dialogue Dataset With State Corrections and State Tracking Baselines.  In _Proceedings of the 12th Language Resources and Evaluation Conference_ , pages 422–428, Marseille, France.
  * Gupta et al. (2021) Prakhar Gupta, Jeffrey P. Bigham, Yulia Tsvetkov, and Amy Pavel. 2021.  Controlling Dialogue Generation with Semantic Exemplars.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2021_ , pages 3018–3029, Online.
  * Ham et al. (2020) DongHoon Ham, Jeong-Gwan Lee, Youngsoo Jang, and Kee-Eung Kim. 2020.  End-to-End Neural Pipeline for Goal-Oriented Dialogue Systems using GPT-2.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020_ , pages 583–592, Online.
  * Henderson et al. (2019a) Matthew Henderson, Paweł Budzianowski, Iñigo Casanueva, Sam Coope, Daniela Gerz, Girish Kumar, Nikola Mrkšić, Georgios Spithourakis, Pei-Hao Su, Ivan Vulić, and Tsung-Hsien Wen. 2019a.  A Repository of Conversational Datasets.  In _Proceedings of the First Workshop on NLP for Conversational AI_ , pages 1–10, Florence, Italy.
  * Henderson et al. (2020) Matthew Henderson, Iñigo Casanueva, Nikola Mrkšić, Pei-Hao Su, Tsung-Hsien Wen, and Ivan Vulić. 2020.  ConveRT: Efficient and Accurate Conversational Representations From Transformers.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 2161–2174, Online.
  * Henderson et al. (2019b) Matthew Henderson, Ivan Vulic, Daniela Gerz, Iñigo Casanueva, Pawel Budzianowski, Sam Coope, Georgios Spithourakis, Tsung-Hsien Wen, Nikola Mrksic, and Pei-Hao Su. 2019b.  Training Neural Response Selection for Task-Oriented Dialogue Systems.  In _Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28-, Volume 1: Long Papers_ , pages 5392–5404.
  * Holtzman et al. (2020) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020.  The Curious Case of Neural Text Degeneration.  In _8th International Conference on Learning Representations, ICLR 2020_ , Addis Ababa, Ethiopia.
  * Hosseini-Asl et al. (2020) Ehsan Hosseini-Asl, Bryan McCann, Chien-Sheng Wu, Semih Yavuz, and Richard Socher. 2020.  A Simple Language Model for Task-Oriented Dialogue.  In _Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS_.
  * Humeau et al. (2020) Samuel Humeau, Kurt Shuster, Marie-Anne Lachaux, and Jason Weston. 2020.  Poly-encoders: Architectures and Pre-training Strategies for Fast and Accurate Multi-sentence Scoring.  In _8th International Conference on Learning Representations, ICLR 2020_ , Addis Ababa, Ethiopia.
  * Kale and Rastogi (2020) Mihir Kale and Abhinav Rastogi. 2020.  Text-to-Text Pre-Training for Data-to-Text Tasks.  In _Proceedings of the 13th International Conference on Natural Language Generation, INLG 2020_ , pages 97–102, Dublin, Ireland.
  * Kim et al. (2020) Seokhwan Kim, Mihail Eric, Karthik Gopalakrishnan, Behnam Hedayatnia, Yang Liu, and Dilek Hakkani-Tür. 2020.  Beyond Domain APIs: Task-oriented Conversational Modeling with Unstructured Knowledge Access.  In _Proceedings of the 21th Annual Meeting of the Special Interest Group on Discourse and Dialogue, SIGdial 2020_ , pages 278–289, Online.
  * Kingma and Ba (2015) Diederik P. Kingma and Jimmy Ba. 2015.  Adam: A Method for Stochastic Optimization.  In _3rd International Conference on Learning Representations, ICLR 2015Proceedings_ , San Diego, CA, USA.
  * Kiritchenko and Mohammad (2017) Svetlana Kiritchenko and Saif M. Mohammad. 2017.  Best-Worst Scaling More Reliable than Rating Scales: A Case Study on Sentiment Intensity Annotation.  In _Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics, ACL 2017 4, Volume 2: Short Papers_ , pages 465–470, Vancouver, Canada.
  * Lee (2021) Yohan Lee. 2021.  Improving End-to-End Task-Oriented Dialog System with A Simple Auxiliary Task.  In _Findings of the Association for Computational Linguistics: EMNLP 2021_ , pages 1296–1303, Virtual Event / Punta Cana, Dominican Republic.
  * 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 _NAACL HLT 2016, The 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 110–119, San Diego California, USA.
  * Lin et al. (2020) Andrea Lin, Zhaojiang andMadotto, Genta Indra Winata, and Pascale Fung. 2020.  MinTL: Minimalist Transfer Learning for Task-Oriented Dialogue Systems.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 3391–3405, Online.
  * Liu et al. (2016a) Chia-Wei Liu, Ryan Lowe, Iulian Serban, Michael Noseworthy, Laurent Charlin, and Joelle Pineau. 2016a.  How NOT To Evaluate Your Dialogue System: An Empirical Study of Unsupervised Evaluation Metrics for Dialogue Response Generation.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016_ , pages 2122–2132, Austin, Texas, USA.
  * Liu et al. (2016b) Chia-Wei Liu, Ryan Lowe, Iulian Serban, Michael Noseworthy, Laurent Charlin, and Joelle Pineau. 2016b.  How NOT To Evaluate Your Dialogue System: An Empirical Study of Unsupervised Evaluation Metrics for Dialogue Response Generation.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016_ , pages 2122–2132, Austin, Texas, USA.
  * Lowe et al. (2015) Ryan Lowe, Nissan Pow, Iulian Serban, and Joelle Pineau. 2015.  The Ubuntu Dialogue Corpus: A Large Dataset for Research in Unstructured Multi-Turn Dialogue Systems.  In _Proceedings of the 16th Annual Meeting of the Special Interest Group on Discourse and Dialogue_ , pages 285–294, Prague, Czech Republic.
  * van der Maaten and Hinton (2008) Laurens van der Maaten and Geoffrey Hinton. 2008.  Visualizing Data Using T-Sne.  _Journal of Machine Learning Research_ , 9(86):2579–2605.
  * Nekvinda and Dušek (2021) Tomáš Nekvinda and Ondřej Dušek. 2021.  Shades of BLEU, Flavours of Success: The Case of MultiWOZ.  In _Proceedings of the 1st Workshop on Natural Language Generation, Evaluation, and Metrics (GEM 2021)_ , pages 34–46, Online.
  * Novikova et al. (2019) Jekaterina Novikova, Aparna Balagopalan, Ksenia Shkaruta, and Frank Rudzicz. 2019\.  Lexical Features Are More Vulnerable, Syntactic Features Have More Predictive Power.  In _Proceedings of the 5th Workshop on Noisy User-generated Text, W-NUT@EMNLP 2019_ , pages 431–443, Hong Kong, China.
  * Novikova et al. (2017) Jekaterina Novikova, Ondrej Dusek, Amanda Cercas Curry, and Verena Rieser. 2017\.  Why We Need New Evaluation Metrics for NLG.  In _Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, EMNLP 2017_ , pages 2241–2252, Copenhagen, Denmark.
  * Nugmanova et al. (2019) Aigul Nugmanova, Andrei Smirnov, Galina Lavrentyeva, and Irina Chernykh. 2019.  Strategy of the Negative Sampling for Training Retrieval-Based Dialogue Systems.  In _IEEE International Conference on Pervasive Computing and Communications Workshops, PerCom Workshops 2019_ , pages 844–848, Kyoto, Japan.
  * Pandey et al. (2018) Gaurav Pandey, Danish Contractor, Vineet Kumar, and Sachindra Joshi. 2018.  Exemplar Encoder-Decoder for Neural Conversation Generation.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics, ACL 2018, Volume 1: Long Papers_ , pages 1329–1338, Melbourne, Australia.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a Method for Automatic Evaluation of Machine Translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics, July 6-12, 2002_ , pages 311–318, Philadelphia, PA.
  * Peng et al. (2021a) Baolin Peng, Chunyuan Li, Jinchao Li, Shahin Shayandeh, Lars Liden, and Jianfeng Gao. 2021a.  SOLOIST: Building Task Bots at Scale with Transfer Learning and Machine Teaching.  _Trans. Assoc. Comput. Linguistics_ , 9:907–824.
  * Peng et al. (2021b) Baolin Peng, Chunyuan Li, Zhu Zhang, Chenguang Zhu, Jinchao Li, and Jianfeng Gao. 2021b.  RADDLE: An Evaluation Benchmark and Analysis Platform for Robust Task-oriented Dialog Systems.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, ACL/IJCNLP 2021, (Volume 1: Long Papers)_ , pages 4418–4429, Virtual Event.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language Models Are Unsupervised Multitask Learners.  Technical report, Open AI.
  * Rastogi et al. (2020) Abhinav Rastogi, Xiaoxue Zang, Srinivas Sunkara, Raghav Gupta, and Pranav Khaitan. 2020.  Towards Scalable Multi-Domain Conversational Agents: The Schema-Guided Dialogue Dataset.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020_ , pages 8689–8696, New York, NY, USA.
  * Roller et al. (2021) Stephen Roller, Emily Dinan, Naman Goyal, Da Ju, Mary Williamson, Yinhan Liu, Jing Xu, Myle Ott, Eric Michael Smith, Y-Lan Boureau, and Jason Weston. 2021\.  Recipes for Building an Open-Domain Chatbot.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume, EACL 2021_ , pages 300–325, Online.
  * Rousseeuw (1987) Peter J. Rousseeuw. 1987.  Silhouettes: A Graphical Aid to the Interpretation and Validation of Cluster Analysis.  _Journal of Computational and Applied Mathematics_ , 20:53–65.
  * Shalyminov et al. (2020) Igor Shalyminov, Alessandro Sordoni, Adam Atkinson, and Hannes Schulz. 2020.  Hybrid Generative-Retrieval Transformers for Dialogue Domain Adaptation.  In _DSTC8@AAAI_ , New York, NY, USA.
  * Su et al. (2022) Yixuan Su, Lei Shu, Elman Mansimov, Arshit Gupta, Deng Cai, Yi-An Lai, and Yi Zhang. 2022.  Multi-Task Pre-Training for Plug-and-Play Task-Oriented Dialogue System.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), ACL 2022_ , pages 4661–4676, Dublin, Ireland.
  * Thulke et al. (2021) David Thulke, Nico Daheim, Christian Dugast, and Hermann Ney. 2021.  Efficient Retrieval Augmented Generation From Unstructured Knowledge for Task-Oriented Dialog.  In _DSTC9@AAAI_ , Online.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017.  Attention Is All You Need.  In _Advances in Neural Information Processing Systems_ , volume 30.
  * Wan et al. (2018) Li Wan, Quan Wang, Alan Papir, and Ignacio Lopez-Moreno. 2018.  Generalized End-to-End Loss for Speaker Verification.  In _2018 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2018_ , pages 4879–4883, Calgary, AB, Canada.
  * Wang et al. (2021) Jianhong Wang, Yuan Zhang, Tae-Kyun Kim, and Yunjie Gu. 2021.  Modelling Hierarchical Structure between Dialogue Policy and Natural Language Generator with Option Framework for Task-oriented Dialogue System.  In _9th International Conference on Learning Representations, ICLR 2021_ , Virtual Event, Austria.
  * Wen et al. (2015) Tsung-Hsien Wen, Milica Gasic, Nikola Mrksic, Pei-hao Su, David Vandyke, and Steve J. Young. 2015.  Semantically Conditioned LSTM-based Natural Language Generation for Spoken Dialogue Systems.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, EMNLP 2015_ , pages 1711–1721, Lisbon, Portugal.
  * Wen et al. (2017) Tsung-Hsien Wen, David Vandyke, Nikola Mrksic, Milica Gasic, Lina Maria Rojas-Barahona, Pei-Hao Su, Stefan Ultes, and Steve J. Young. 2017.  A Network-based End-to-End Trainable Task-oriented Dialogue System.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics, EACL 2017, Volume 1: Long Papers_ , pages 438–449, Valencia, Spain.
  * Weston et al. (2018) Jason Weston, Emily Dinan, and Alexander H. Miller. 2018.  Retrieve and Refine: Improved Sequence Generation Models For Dialogue.  In _Proceedings of the 2nd International Workshop on Search-Oriented Conversational AI, SCAI@EMNLP 2018_ , pages 87–92, Brussels, Belgium.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020.  Transformers: State-of-the-Art Natural Language Processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, EMNLP 2020 - Demos_ , pages 38–45, Online.
  * Wu et al. (2020) Chien-Sheng Wu, Steven C. H. Hoi, Richard Socher, and Caiming Xiong. 2020.  TOD-BERT: Pre-trained Natural Language Understanding for Task-Oriented Dialogue.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, EMNLP 2020_ , pages 917–929, Online.
  * Wu et al. (2019) Chien-Sheng Wu, Andrea Madotto, Ehsan Hosseini-Asl, Caiming Xiong, Richard Socher, and Pascale Fung. 2019.  Transferable Multi-Domain State Generator for Task-Oriented Dialogue Systems.  In _Proceedings of the 57th Conference of the Association for Computational Linguistics, ACL 2019, Florence, Italy, July 28-, Volume 1: Long Papers_ , pages 808–819.
  * Young et al. (2013) Steve J. Young, Milica Gasic, Blaise Thomson, and Jason D. Williams. 2013.  POMDP-Based Statistical Spoken Dialog Systems: A Review.  _Proc. IEEE_ , 101(5):1160–1179.
  * Zang et al. (2020) Xiaoxue Zang, Abhinav Rastogi, Srinivas Sunkara, Raghav Gupta, Jianguo Zhang, and Jindong Chen. 2020.  MultiWOZ 2.2 : A Dialogue Dataset With Additional Annotation Corrections and State Tracking Baselines.  In _Proceedings of the 2nd Workshop on Natural Language Processing for Conversational AI_ , pages 109–117, Online.
  * Zhang et al. (2020a) Yichi Zhang, Zhijian Ou, and Zhou Yu. 2020a.  Task-Oriented Dialog Systems That Consider Multiple Appropriate Responses under the Same Context.  In _The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020_ , pages 9604–9611, New York, NY, USA.
  * Zhang et al. (2020b) Yizhe Zhang, Siqi Sun, Michel Galley, Yen-Chun Chen, Chris Brockett, Xiang Gao, Jianfeng Gao, Jingjing Liu, and Bill Dolan. 2020b.  DIALOGPT : Large-Scale Generative Pre-training for Conversational Response Generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations, ACL 2020_ , pages 270–278, Online.

##  Appendix A Model Architectures

Figure 4 shows architectures of the baseline (Gen), dual-encoder-based model
(DE), and single-encoder action-aware model (AAE). See Figure 1 for details
about AARGH and Section 3 for description of the models.

Figure 4: Architecture of the baseline (Gen, _top_), dual-encoder-based model
(DE, _middle_) and single-encoder action-aware model (AAE, _bottom_). Numbers
in module boxes mark the order of processing during inference.

##  Appendix B Beam Search Results

See Table 6 for the results of beam search-based response generation
evaluation, and compare the results with greedy decoding evaluation (see
Section 5.1 and Table 2). For all models, we used beams of size 8 during the
decoding

In the case of conservative $\alpha$-blending, beam search decoding results in
higher lexical diversity for all retrieval-augmented systems. However, the
gains with respect to Inform and Success rates are mostly very small or not
present at all in the case of AADE and AARGH. All BLEU scores are slightly
lower which corresponds with the higher output diversity. We notice that the
numbers for the baseline without a retrieval component have an opposite trend.
Beam search decoding causes lower lexical diversity and higher BLEU. We
attribute this to the fact that beam search decoding prefers safer responses
with a higher overall probability.

When using higher $\alpha$-blending, the differences become small even in the
case of lexical diversity. We hypothesize that all the retrieval-based models
are not substantially influenced by the particular response decoding strategy
because they strongly rely on the retrieved hints and their copying.

Setting | BLEU | Inform | Success | Num. trigrams | Bi-gram entropy | Hint-BLEU | Hint-copy
---|---|---|---|---|---|---|---
Gen | $19.1\pm 0.3$ | $73.1\pm 1.8$ | $63.0\pm 1.7$ | 2683 | 1.81 | - | -
_$\alpha=0.05$_ | DE | $16.1\pm 0.3$ | $81.1\pm 0.5$ | $68.3\pm 0.8$ | 10098 | 2.49 | $41.9$ | 25.2 %
AADE | $16.0\pm 0.4$ | $78.0\pm 1.1$ | $65.9\pm 1.0$ | 7378 | 2.33 | $32.6$ | 19.2 %
PE | $15.9\pm 0.4$ | $80.6\pm 0.9$ | $66.9\pm 1.0$ | 9470 | 2.48 | $40.7$ | 24.4 %
AAE | $\mathbf{16.4}\pm 0.4$ | $\mathbf{82.5}\pm 0.8$ | $\mathbf{69.8}\pm 0.6$ | 10457 | 2.46 | $44.2$ | 29.0 %
| AARGH | $16.2\pm 0.3$ | $79.5\pm 0.5$ | $68.0\pm 0.3$ | 9072 | 2.36 | $36.2$ | 22.2 %
_$\alpha=0.4$_ | DE | $12.3\pm 0.3$ | $87.7\pm 0.3$ | $68.7\pm 0.6$ | 19103 | 3.28 | $83.1$ | 79.6 %
AADE | $13.7\pm 0.4$ | $77.8\pm 0.9$ | $63.2\pm 0.4$ | 10997 | 2.76 | $55.8$ | 50.2 %
PE | $\mathbf{12.7}\pm 0.3$ | $85.9\pm 0.9$ | $66.3\pm 0.7$ | 17178 | 3.19 | $78.3$ | 74.2 %
AAE | $12.0\pm 0.2$ | $\mathbf{90.3}\pm 0.5$ | $\mathbf{71.2}\pm 0.4$ | 19448 | 3.21 | $92.6$ | 90.1 %
| AARGH | $12.2\pm 0.2$ | $89.3\pm 0.3$ | $70.0\pm 0.6$ | 19763 | 3.22 | $88.6$ | 86.0 %
Table 6: Beam search-based response generation on MultiWOZ using automatic
metrics. For each model setup, We use beams of size 8 during response decoding
and report results averaged over 8 random seeds. We compare the baseline (Gen)
and retrieval-based generative models (See Section 3 and 4). See Section 5.2
for details about the metrics. Cf. Table 2 showing results obtained using
greedy decoding.

##  Appendix C End-to-end Conversation

Figure 5 shows a multi-domain (restaurant and taxi) end-to-end conversation
between our end-to-end retrieval-based model AARGH (See Section 3.5).

Figure 5: End-to-end conversation between  the user and  our retrieval-based
AARGH model with conservative $\alpha$-blending (see Section 3). For the
system turns, we show delexicalized hints proposed by the retrieval module
(left boxes in italics) and the corresponding lexicalized final responses
(right boxes). We highlighted  the parts of hints present in the final texts
and  the parts of final responses newly-introduced by the model during
refining.

##  Appendix D Human Evaluation Interface

We used the graphical user interface depicted in Figure 6 for human
evaluation. A full dialog context, i.e., all past utterances corresponding to
the particular turn, and the number of database results were shown to
participants. We asked participants to rank provided responses from the best
to the worst. They evaluated only two conversations in a single run and we
sampled the conversations from the test set so that all participants receive
roughly the same number of turns to assess. Evaluated responses were shown
side-by-side; each of them had a dedicated discrete scale from 1 to 4 where 1
was labeled as the best and 4 as the worst. More responses could receive the
same ranking. Participants could move forward and backward in the
conversations and they could switch to another conversation anytime.

Figure 6: Our graphical user interface used for human evaluation.


# Implicit Sensing in Traffic Optimization: Advanced Deep Reinforcement
Learning Techniques

Emanuel Figetakis1, Yahuza Bello 1, Ahmed Refaey 12, Lei Lei 1, and Medhat
Moussa 1

1 University of Guelph, Guelph, Ontario, Canada.  2 Western University,
London, Ontario, Canada.

###### Abstract

A sudden roadblock on highways due to many reasons such as road maintenance,
accidents, and car repair is a common situation we encounter almost daily.
Autonomous Vehicles (AVs) equipped with sensors that can acquire vehicle
dynamics such as speed, acceleration, and location can make intelligent
decisions to change lanes before reaching a roadblock. A number of literature
studies have examined car-following models and lane-changing models. However,
only a few studies proposed an integrated car-following and lane-changing
model, which has the potential to model practical driving maneuvers. Hence, in
this paper, we present an integrated car-following and lane-changing decision-
control system based on Deep Reinforcement Learning (DRL) to address this
issue. Specifically, we consider a scenario where sudden construction work
will be carried out along a highway. We model the scenario as a Markov
Decision Process (MDP) and employ the well-known DQN algorithm to train the RL
agent to make the appropriate decision accordingly (i.e., either stay in the
same lane or change lanes). To overcome the delay and computational
requirement of DRL algorithms, we adopt an MEC-assisted architecture where the
RL agents are trained on MEC servers. We utilize the highly reputable SUMO
simulator and OPENAI GYM to evaluate the performance of the proposed model
under two policies; $\epsilon$-greedy policy and Boltzmann policy. The results
unequivocally demonstrate that the DQN agent trained using the
$\epsilon$-greedy policy significantly outperforms the one trained with the
Boltzmann policy.

###### Index Terms:

Lane-changing, car-following, MDPs, DQN, Autonomous vehicles, Intelligent
transportation systems

##  I Introduction

In the past two decades, researchers have been working on innovative ways to
make significant improvements in security and comfort in Intelligent
Transportation Systems (ITS) [1]. Safety is one of the major design goals for
autonomous driving as it allows autonomous vehicles to navigate roads
independently with fewer human interventions. This will eventually lead to
fewer accidents compared to human drivers who are mostly impaired due to many
reasons such as sickness and fatigue after a long drive to name a few. A
multitude of onboard sensors is used in most current autonomous driving
systems to gather relevant data [2] [3]. Sharing these relevant data among
multiple autonomous cars will be beneficial to have an efficient ITS. The
advent of advanced communication technologies such as Vehicle-to-Vehicle
(V2V), Vehicle-to-Infrastructure (V2I), and Vehicle-to-everything (V2X) allows
for highly efficient wireless communication within the ITS domain [4]. This is
very important for autonomous vehicles to communicate with one another,
central servers, and off-board Road Side Units (RSUs).

An essential aspect of autonomous vehicle operation in complex driving
scenarios is having a decision-making control module that is accurate and that
can be executed almost instantly. This module is responsible for sending
instructions to the vehicle’s action execution module to perform numerous
actions like following cars, avoiding obstacles, changing lanes, and
overtaking [5]. Driving maneuvers such as following a car in front and
changing lanes are the two most important driving situations that occur most
frequently. Consequently, multiple research works have emerged with various
car-following models and lane-changing models [6, 7, 8, 9, 10, 11]. However,
most of these research works studied and proposed car-following models and
lane-changing models individually. The effects of lane-changing behavior on
vehicles in the opposite lane have been pointed out by many scholars. To this
end, the importance of joint research on vehicle driving systems that
considers both lane-changing behavior and car-following behavior cannot be
overstated.

Recently, Machine Learning (ML) based car-following models have yielded
outstanding performance as reported in the literature. Specifically,
Reinforcement Learning (RL) and Deep Reinforcement Learning (DRL) stand out
among other ML approaches adopted [6, 7, 8]. Similarly, lane-changing models
are seeing similar research trends in the literature (i.e., researchers are
adopting RL and DRL such as Deep Deterministic Policy Gradient (DDPG) and Deep
Q-Network (DQN) algorithms to solve the lane-changing maneuver problem) [9,
10, 11]. However, only a few research works have been reported in the
literature [12].

For any ITS to be effective, vehicle-to-everything (V2X) applications must be
deployed to enable vehicles to exchange information with nearby vehicles and
infrastructure to coordinate maneuvers. It is very common to execute several
intensive computational operations in a very short period of time in the ITS
domain to have safe and effective coordination among vehicles. This
necessitates the deployment of servers with high computational resources along
the road. As part of the V2X infrastructure deployment, operators install RSUs
to reduce communication delays between vehicles and central servers, which
improves the coverage range.

In response to concurrent delay and computational requirements, the European
Telecommunications Standards Institute (ETSI) introduced the multi-access edge
computing (MEC) concept [13]. With MEC, computational resources are moved
closer to the vehicles. MEC-assisted ITS applications are being heavily
investigated in the literature.

The contributions of this paper are summarized as follows:

  * •

Develop a cohesive decision control framework for car-following and lane-
changing operations, utilizing DRL techniques. This is specifically tailored
for scenarios involving abrupt highway construction work.

  * •

Formulate the given scenario as an MDP and employ the Deep Q-Network (DQN)
algorithm during the experimentation phase to train an RL agent in making
optimal decisions.

  * •

Integrate a MEC-assisted architecture to address latency and computational
demands associated with DRL algorithms.

  * •

Evaluate and contrast two distinct decision-making policies, namely Boltzmann
and Epsilon Greedy, to ascertain the superior approach in enhancing traffic
flow efficiency within the simulation environment.

The structure of the rest of the paper is as follows: Section II presents the
background knowledge and the relevant related works in the literature. Section
III presents the proposed system model and its description. Section IV
presents the description of the implementation of the environment and model
used for training the agent. The section concludes with results and a
discussion of the performance analysis of the proposed model. Section V gives
conclusion remarks and highlights the intended future work.

Figure 1: Proposed integrated car-following and lane-changing model running on
MEC server

##  II Background and Related Works

The purpose of this section is to discuss the necessary background knowledge
required and the related works from the literature. The first part discusses
the concept of RL and DRL in general. The second part dive into the car-
following models, and lane-changing models.

###  II-A RL and DRL

Generally, RL describes an autonomous agent learning by interacting with its
surroundings to improve its performance. A reward function $R$ determines
whether an agent performs well or not in a typical RL environment. A decision
is made for every state experienced and an occasional reward, $R$, is received
as a result based on the usefulness of that decision by the agent. In order to
maximize cumulative rewards over a specified period of time, the agent must
maximize each reward received during the specified period, which is the
ultimate goal of the agent. As the agent learns more about the expected
utility of different state-action pairs (i.e. discounted sum of future
rewards), it can gradually increase its long-term reward.

When formalizing sequential decision problems with an RL agent, Markov
decision processes (MDPs) seem to be the standard that is widely adopted [14].
A typical MDP is characterized as a tuple $<S,A,P,R,\gamma>$ where $S$ is the
set of state space, $A$ is the set of action space, $P$ is the probability
transition function, $R$ is the reward function, and $\gamma$ is a discount
factor used to adjust immediate and future rewards.

In short, when an agent in a state $s\in S$ chooses an action $a\in A$, the
agent will transition to the next state $s^{\prime}\in S$ according to the
transition probability $P\in[0,1]$ and gain a reward $R(s,a)$. Note that the
end goal of an agent is to find the optimal policy $\pi^{*}$ (which is a
mapping of the environment states to actions) that will result in the maximum
expected sum of discounted rewards [14]. The agent uses this policy to
determine how to behave at every step of the way. A policy can either be
deterministic or stochastic in nature. A deterministic policy typically
returns the action to be taken in each state whereas as a stochastic policy
returns a probability distribution over the actions (usually donated as
$\pi(a|s)$). Based on a given policy, a value-function or a Q-function can be
defined to measure the expected rewards starting from any given state $s\in S$
or any state-action pair $(s,a)$. For more details on the different RL methods
for finding the optimal value-function, Q-function, and policy, refer to [15].

Despite the fact that learning in RL is a convergent process, it takes a long
time to come up with the best policy because it requires a lot of exploration
and knowledge, so it is not suitable and inapplicable for large-scale
networks. This limits the wide adoption of RL in many applications. The
advancement of deep learning paves the way for a new RL approach called DRL,
which solves some of the limitations of the traditional RL. By utilizing Deep
Neural Networks (DNNs) as a learning tool, DRL is able to increase the
learning speed and performance of RL algorithms. Consequently, DRL is being
adopted in many applications such as ITS, healthcare, robotics, trading and
finance, news recommendation platforms, and networking. Several algorithms
such as DQN, DDPG, and Double Deep Q Network (DDQN) emerged as a result of the
advancement in the DRL paradigm [16].

###  II-B Car-following models and lane-changing models

Several studies emerged in the domain of ITS tackling the problem of car-
following and lane-changing decisions. A car-following framework for
Autonomous Vehicles (AVs) is developed in [6] using a navigation decision
module and an automatic object detection module. The authors explore
Q-learning and DQN algorithms against the proposed car-following framework. In
[7], the authors explored the characteristics of demand for AVs in mixed
traffic flow and proposed a car-following model with a warning module. An
automated entropy adjustment algorithm using Tsallis actor-critic (ATAC) is
established in [8] to propose a car-following model. The authors explore Twin
Delayed DDPG (TD3), Soft Actor-critic (SAC) and DDPG algorithms to test the
performance of the proposed car-following model.

Similarly, numerous research works have emerged in the domain of lane-changing
maneuvers. The authors in [9] proposed a lane-changing decision module for AVs
using a game theoretical approach. The authors demonstrated that during the
course of the lane-changing decision, the objective quantification of lane-
changing intention must be used in order to determine the lane-changing
intentions of AVs. The authors in [10] proposed an improved method for
planning the trajectory of changing lanes for AVs on closed highways based on
segmented data. For predicting target vehicles’ driving intentions, a Bayesian
Network-based model using Long Short-Term Memory and the maximum entropy
Inverse Reinforcement Learning (IRL) algorithm is used.

Some research works that explore the integration of car-following and lane-
changing models for better decision options are starting to trend in the
literature. For example, the authors in [12] proposed a two-layered framework
that utilizes DRL algorithms to handle large-scale mixed-state spaces and
produces lane-changing and car-following decisions as a composite output. A
Duelling Double Deep Q-Network (D3QN) algorithm is used to distinguish the
value of selected lane-changing actions and the potential value of the
environment in the upper layer model. A DDPG algorithm is used in the second
layer of the model to control vehicle speed continuously based on car-
following decisions. This paper differs from the work in [12] in the sense
that we use a single RL algorithm (i.e., DQN algorithm) to make decisions on
car-following or lane-changing actions. Moreover, the work in [12] did not
adopt a MEC-assisted architecture, rather assuming the vehicle is equipped
with the required processing resources to run the RL agents.

##  III System Model

The proposed integrated car-following and lane-changing model is presented in
Figure 1. We consider a scenario where a sudden construction or roadblock is
up ahead on a highway. To model the scenario properly, we assume the
autonomous vehicle is equipped with multiple sensors and appropriate wireless
communication systems such as V2V or V2I systems, which can be depicted in
Figure 1 as the vehicle dynamic module. This means that the target vehicle can
be able to gather information such as its own speed, acceleration, position,
distance to the roadblock, and the same information about neighboring
vehicles. We also assume to have off-board Road Side Units (RSUs) that the
vehicles can exchange data. The vehicles’ data/information is passed through a
DQN algorithm to train the agent to make appropriate decisions regarding lane-
changing or car-following. The DQN algorithm is implemented on a central MEC
edge server. This central edge server handles the computational calculations
of the MDP problem and then communicates the decision to the vehicles
accordingly through V2I technology using the nearby RSU.

Mathematically, we model the scenario as an MDP as follows:

  * •

State space definition: We model each state $s\in S$ as tuple
$<d_{c},d_{f},v_{EH},x_{p},y_{p}>$ where $d_{c}$ represents the distance of
the target car from the roadblock, $d_{f}$ represents the distance of the
target car to the next car in its path, $v_{EH}$ represents the speed of the
target car, $x_{p}$ and $y_{p}$ represents the location of the target car
along the x-axis and y-axis respectively.

  * •

Action space definition: The action space $a\in A$ is given as $<M,C>$ where
$M$ represents the decision of merging to the other lane (i.e., lane-changing
decision) and avoiding reaching the roadblock and $C$ represents the decision
of staying on the same lane (i.e., a car-following decision for the cars on
the right lane or cars that are far away from the roadblock). Note that this
action space is represented by 12 discrete action spaces, which correlate to
the positions in the lane with the roadblock where lane-changing action can be
initiated. This will be explained in more detail in section IV.

  * •

Reward definition: The reward definition is given as a tuple
$<R_{M}^{+},R_{M}^{-},-R_{M}^{+}>$ where $R_{M}^{+}$ represents a positive
reward when the target car successfully changes lane and merge with average
speed before reaching the roadblock, $R_{M}^{-}$ represents a negative reward
when the target car fails to change lane after reaching the roadblock (i.e.,
the end of the lane in this case) and $-R_{M}^{+}$ represents negative
positive reward when the target car change lane and merge with minimum speed
before reaching the roadblock. The last reward will deal with the situation
where the target car eventually merges but at the end of the lane (which will
cause high traffic jams).

To solve the above modeled MDP problem, we utilize the well-known DQN
algorithm because it achieves good performance in related decision control
problems [6]. We employ two policies; $\epsilon$-greedy policy and Boltzmann
policy as explained in the DQN algorithm’s pseudocode in algorithm 1. The
vehicles gather information about the state space as defined in the state
space definition and send it to the nearest off-board RSUs. The off-board RSUs
forward the state space to the central MEC edge server, which uses the DQN
algorithm to determine the correct actions to execute. The current action is
then sent to the corresponding vehicle via the nearby RSU. It is worth
mentioning that we adopt the two policies (i.e., $\epsilon$-greedy and
Boltzmann) for the sake of performance evaluation as shown in algorithm 1.

Algorithm 1 DQN algorithm on the MEC server

1:Initial w set randomly, Initial replay buffer $D$ set to $N$, Initial policy
$\pi(s)$ as either $\epsilon$-greedy policy or Boltzmann policy, Initial
$S_{0}$

2:for $t=0$ to $T$ do

3: Execute action $A_{t}=\pi(S_{t})$ according to either $\epsilon$-greedy
policy or Boltzmann policy

4: Observe state $S_{t+1}$ and reward $R_{t+1}$

5: Store the transition parameters $S_{t},A_{t},R_{t+1},S{t+1})$ in $D$

6: Sample minibatch transitions randomly from $D$ as
$(S_{j},A_{j},R_{j+1},S{j+1})$

7: for $j$ in minibatch do

8: Set $y_{j}=\biggl{\\{}\begin{array}[]{cl}R_{j+1},S_{j+1}\\!\\\
R_{j+1}+\gamma max_{a^{^{\prime}}}Q(S_{j+1},a^{^{\prime}};w)\end{array}$

9: Update w using stochastic descent to minimize
$(y_{j}-Q(S_{j},Aj;\textbf{w}))^{2}$

10: end for

11: Improve policy $\pi(s)$ as either $\epsilon$-greedy or Boltzmann with the
new w

12:end for

##  IV Implementation and Experiment

The implementation of the system model is a multi-layer problem with the end
goal for the extermination to include two RL agents with different policies to
take action in the system model. The following tasks are defined in order to
achieve the goal of our experimentation:

  * •

Model the MDP from the System Model into a Python OpenAi GYM environment

  * •

Create the simulation space in Simulation of Urban Mobility(SUMO)

  * •

Create the model and add the agent and policy to the Model

  * •

Interface the OpenAI GYM environment with the simulation space in SUMO

  * •

Interface the Agent with the environment

###  IV-A GYM Environment

The GYM environment was modeled after our MDP formulation. The GYM environment
allows us to define the parameters of our problem such as state space, action
space, observation space, reward function, and simulation length. The library
is also not limited to these parameters and can include more complex functions
and parameters however, since the GYM environment is being interfaced with
SUMO there are fewer parameters needed. The definition of our parameters is as
follows, for the state space it is determined by the observation space which
is the range that is determined by each lane’s average speed. Our action space
is a discrete 12-action space that correlates to positions in the lane of
construction where a lane change will be initiated.

Figure 2: Sumo environment and model representation

###  IV-B SUMO Environment

The SUMO environment is a 300-unit, three-lane highway with a blocked lane at
280 units, causing vehicles to slow down and make lane-changing decisions. A
vehicle can change lanes every 20 units in the lane leading up to the
roadblock. The RL agent must determine when to start changing lanes to avoid a
negative reward if the average speed of the lanes falls below a certain
threshold. The work features seamless integration between the two libraries,
and more scenarios will be added in future work. Figure 2 depicts the
environment with yellow boxes representing positions for lane changes,
including one at the construction site and the topmost detectors used to
gather information about average speed.

###  IV-C Model

A shallow network with 948 parameters was used to support a DQN model
(depicted in Figure 2) for the GYM environment. It consisted of an input layer
based on possible states, followed by a 24-dense layer with ReLu activation,
another 24-dense layers, and a model for 12 discrete actions. Testing showed
that the program completed one step per second, although this was due to the
SUMO simulation rather than the network. The DQN implemented two policies -
the Boltzmann Q-Policy and the Greedy Q-Policy - with all other
hyperparameters kept consistent. In future works, an actor-critic network
could be used to evaluate actions as they occur, which would benefit multi-
agent testing.

###  IV-D Interfacing Agent, GYM, and SUMO

At this point in the implementation all modules have been created so comes the
time for all modules to work together to create the simulation. The agent that
utilizes Tensorflow and Keras interface works with OpenAI GYM without any
problems, however, the challenges began when trying to implement SUMO with the
agent and the environment. There was no standard way found to implement the
two together; the only use factor that was found during research was that SUMO
had a Python library integration tool called TraCI. From this Python library
the SUMO application can be called from Python, this is what was needed for
the implementation. A function was created that took a number between 1 and
12, which corresponds to the point at which the lane change was supposed to
take place, and then launched the SUMO simulation with those parameters.

##  V Simulation Results and Analysis

This section presents the performance evaluation of the proposed model. For
each model, the system was trained for 400 episodes which correlate to 20,000
steps. Several different metrics were recorded and a small noise factor was
included in each simulation to simulate randomness. Along with this
randomness, the vehicles starting positions were not always the same. With all
of this included each policy was able to perform and find optimal solutions.

###  V-A DQN Boltzmann Q-Policy and Epsilon Greedy Q-Policy

The DQN model with the Boltzmann Q-Policy is intended to take a more
exploratory approach. It tries different actions and learns random actions
based on a scale of the Q function. The Greedy Q-Policy will quickly find
which actions correlate to the highest rewards and based on the state take
different actions.

Figure 3: Action and Reward Data

Figure 3 shows that for this environment the Greedy policy is actually taking
more diverse actions whereas Boltzmann is taking the more consistent actions.
However, the rewards for the Greedy Policy are greater than the Boltzmann,
this is because they are working in a dynamic environment where the optimal
actions change per step. The Greedy policy is able to learn this and adapt
whereas Boltzmann is stuck evaluating random actions for every scenario on its
scale. The problem that the Boltzmann policy is facing is analogous to an
optimization problem where gradient descent is getting stuck in local minima.

Figure 4(a) helps us understand why the Boltzmann policy is operating poorly
compared to the Greedy policy. The Q-Values of Boltzmann are converging with
the Greedy policy however, figure 3 shows that this is not the case otherwise
the rewards would be similar. The Boltzmann Policy is evaluating its actions
Q-Values as good but since the environment is dynamic and is changing after
every step this is not the case. This is due to the limited memory of the
algorithm and is shown by Figures 4(a) and 3.

Figure 4: (Q-Value Function at each episode and Rewards of Both Models

After both models were trained they were saved and used to play in the
environment. Before running both models, based on the results that were
received during testing, we predicted that the Greedy policy would outperform
the Boltzmann policy. Looking at figure 4(b), shows that our prediction was
correct. The Boltzmann policy takes more consistent actions that result in the
same rewards, while the Greedy Q starts taking different actions to increase
rewards as the simulation runs. This is because the Boltzmann Q operates on a
range of actions that it determines based on Q values, while the Greedy Q
takes actions with the intention of increasing rewards and therefore Q Value.
Another reason the Greedy Q outperforms the Boltzmann later in the simulation
is the discount factor in the equation as it focuses on gathering rewards over
a longer period of time.

Figure 5 shows the program created for this implementation has a reasonable
run time. It also shows that Greedy policy is taking a little more time and
this can be because the algorithm includes memory for its previous steps
before making a new action whereas Boltzmann is making different actions every
step.

Figure 5: Run time of Training both DQN Agents

##  VI Conclusion and Future Work

In this paper, the task of modeling traffic and optimal merge patterns was
accomplished through the use of Deep Reinforcement Learning. This task
presented many challenges that required creativity when creating the training
and testing programs. The problem had to be modeled into a game environment,
and then the RL algorithm had to be trained and tested to gather results. It
features a unique and novel implementation with Python, OpenAI GYM, and SUMO.
With the use of this novel program, two different RL policies were able to be
tested. From the experiment, it can be determined for the application of merge
patterns the Epsilon Greedy Q-Policy performs better than the exploratory
Boltzmann Q-Policy. Also, due to the dynamic nature of the environment that
was created, the conclusion is that Greedy Q performs better in a random
environment. Since the framework for the problem has been created this
presents opportunities for different algorithms and policies to be tested. The
framework can be scaled to almost any RL or ML framework. We hope to further
contribute by evaluating different algorithms to test performance against one
another, as well as perform tweaks to the environment to add several different
scenarios.

## References

  * [1] M. Veres and M. Moussa, “Deep learning for intelligent transportation systems: A survey of emerging trends,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 21, no. 8, pp. 3152–3168, 2020.
  * [2] S. Verma, S. Zeadally, S. Kaur, and A. K. Sharma, “Intelligent and secure clustering in wireless sensor network (wsn)-based intelligent transportation systems,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 8, pp. 13 473–13 481, 2022.
  * [3] A. S. El-Wakeel, A. Osman, N. Zorba, H. S. Hassanein, and A. Noureldin, “Robust positioning for road information services in challenging environments,” _IEEE Sensors Journal_ , vol. 20, no. 6, pp. 3182–3195, 2020\.
  * [4] M. Ouaissa, M. Ouaissa, M. Houmer, S. El Hamdani, and Z. Boulouard, “A secure vehicle to everything (v2x) communication model for intelligent transportation system,” in _Computational Intelligence in Recent Communication Networks_. Springer, 2022, pp. 83–102.
  * [5] J. Rosenzweig and M. Bartl, “A review and analysis of literature on autonomous driving,” _E-Journal Making-of Innovation_ , pp. 1–57, 2015.
  * [6] M. Masmoudi, H. Friji, H. Ghazzai, and Y. Massoud, “A reinforcement learning framework for video frame-based autonomous car-following,” _IEEE Open Journal of Intelligent Transportation Systems_ , vol. 2, pp. 111–127, 2021.
  * [7] C. Zhao, S. Jiang, Y. Lei, and C. Wang, “A study on an anthropomorphic car-following strategy framework of the autonomous coach in mixed traffic flow,” _IEEE Access_ , vol. 8, pp. 64 653–64 665, 2020.
  * [8] T.-Q. Tang, Y. Gui, and J. Zhang, “Atac-based car-following model for level 3 autonomous driving considering driver’s acceptance,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 8, pp. 10 309–10 321, 2022.
  * [9] D. Qu, K. Zhang, H. Song, Y. Jia, and S. Dai, “Analysis and modeling of lane-changing game strategy for autonomous driving vehicles,” _IEEE Access_ , vol. 10, pp. 69 531–69 542, 2022.
  * [10] Y. Sun, Y. Chu, T. Xu, J. Li, and X. Ji, “Inverse reinforcement learning based: Segmented lane-change trajectory planning with consideration of interactive driving intention,” _IEEE Transactions on Vehicular Technology_ , vol. 71, no. 11, pp. 11 395–11 407, 2022.
  * [11] J. Peng, S. Zhang, Y. Zhou, and Z. Li, “An integrated model for autonomous speed and lane change decision-making based on deep reinforcement learning,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 11, pp. 21 848–21 860, 2022.
  * [12] ——, “An integrated model for autonomous speed and lane change decision-making based on deep reinforcement learning,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 11, pp. 21 848–21 860, 2022.
  * [13] M. E. ISG, “‘multi-access edge computing (mec); study on mec support for v2x use cases,” _ETSI, Sophia-Antipolis, France, Tech. Rep. GR MEC_ , vol. 22, 2018.
  * [14] X. Wang, S. Wang, X. Liang, D. Zhao, J. Huang, X. Xu, B. Dai, and Q. Miao, “Deep reinforcement learning: a survey,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2022.
  * [15] B. R. Kiran, I. Sobh, V. Talpaert, P. Mannion, A. A. A. Sallab, S. Yogamani, and P. Pérez, “Deep reinforcement learning for autonomous driving: A survey,” _IEEE Transactions on Intelligent Transportation Systems_ , vol. 23, no. 6, pp. 4909–4926, 2022.
  * [16] X. Wang, S. Wang, X. Liang, D. Zhao, J. Huang, X. Xu, B. Dai, and Q. Miao, “Deep reinforcement learning: A survey,” _IEEE Transactions on Neural Networks and Learning Systems_ , pp. 1–15, 2022.