# Solving Royal Game of Ur Using Reinforcement Learning

Sidharth Malhotra Girik Malik
College of Computer and Information Sciences
Northeastern University
Boston, MA 02115

###### Abstract

> Reinforcement Learning has recently surfaced as a very powerful tool to
> solve complex problems in the domain of board games, wherein an agent is
> generally required to learn complex strategies and moves based on its own
> experiences and rewards received. While RL has outperformed existing state-
> of-the-art methods used for playing simple video games and popular board
> games, it is yet to demonstrate its capability on ancient games. Here, we
> solve one such problem, where we train our agents using different methods
> namely Monte Carlo, Q-learning and Expected Sarsa to learn optimal policy to
> play the strategic Royal Game of Ur. The state space for our game is complex
> and large, but our agents show promising results at playing the game and
> learning important strategic moves. Although it is hard to conclude that
> when trained with limited resources which algorithm performs better overall,
> but Expected Sarsa shows promising results when it comes to fastest
> learning.

##  1 Introduction

Reinforcement Learning (RL) (?) is a powerful optimisation method used for
complex problems. In RL, an agent learns to perform a (set of) task(s) on the
basis of how it has performed on the previous steps. The agent typically gets
a reward for moving closer to the goal or the optimised value, and in some
cases a punishment for deviating from its intended learning task.
Reinforcement learning, in a lot of ways, is inspired by biological learning
that generally happens in mammals; for e.g.: children learn a language by
observing their environment and if they are able to mimic it well, they are
rewarded with something in appreciation. Similar behaviour is also observed in
animals, like dogs, which are given treats on successful completion of a task,
say fetching a stick. Mammalian brain then tries and rewire itself so that it
can perform certain actions which lead to successful completion of tasks and
gives it some sort of short/long term rewards.

A few algorithms in RL are also directly inspired by neuroscience and
behavioural psychology. Temporal Difference learning (TD), for example, is one
such example which has been rigorously studied in the mammalian brain, and the
loss function in TD is known to perform in a way the brain spikes, in case of
dopamine neurons, when given a reward (?) (?) (?) (?) (?). Schultz et al. (?)
reported that in case of a monkey rewarded with juice, the dopamine level shot
up, when the reward was not expected, showing a difference in expected and
actual rewards, as in the TD loss function. Overtime, this firing activity
back propagated to the earliest reliable stimuli, and once the monkey was
fully trained, the firing activity disappeared, and started resulting in a
decline on when the expected reward was not produced. The field has not just
benefitted unidirectionally, results from TD have also been used in the study
of schizophrenia, and the effects of dopamine manipulation on learning (?).

The community has always been interested in development of more sophisticated
algorithms and applying them to real-life tasks. RL is not far-behind in this.
With the practical viability of deep leaning, there have been significant
progresses in training RL algorithms with deep learning and then applying them
to solve problems with human-level accuracy. This has been lately demonstrated
by the use of RL algorithms to train agents for playing atari games, where
they have surpassed human accuracy on a wide array of games, without
significant changes in the strategy (?). Board games are also not left behind
in this feat. Shortly after atari games, RL has been used to solve one of the
most complex board games, and beat the world champion (?).

Traditional approaches on board games have failed on larger boards, given
large state spaces, complex optimal value functions making it infeasible for
the to learn using self-play, and underdeveloped algorithms, that have
slower/skewed learning curves. The problem starts to become even more complex
as soon as multi-agent strategies come into play. Cooperative v/s independent
multi agent strategies have their own advantages and disadvantages (?).
Cooperative agents have shown improvements in scores at the cost of speed.
Independent agents, on the other hand, have shown the reverse to be true.
While the idea of having both agents have access to the other’s state and
action space is an acceptable workaround, such a setting is not possible to
have in a few cases, like card games and certain kind of board games.

In our paper we demonstrate the use of popular RL algorithms in playing the
Royal Game of Ur. The use of RL algorithms to solve popular board games is not
new (?) (?) (?) (?) (?), but the use of RL for solving Ur has not been
attempted yet. The Game of Ur is known to be a fairly complex, two-player
board game, with variable number of states and pawns. A complete background on
Ur is given in section 2.1. We have compared the performance of on-policy
Monte Carlo, Q-learning and Expected Sarsa on playing The Game of Ur, in an
independent multi-agent setting. We compare these RL algorithms’ application
to Ur, implemented in a simulator, similar to Open AI’s Gym (?). For the
implementation, we create our own simulator from scratch (see section 3.1,
with similar functions as implemented in (?). Our goal is to test the
performance of these algorithms on the simulator, and for the agents to be
able to achieve human level strategies. The algorithm is not provided any
game-specific information or hand-designed features, and are not privy to the
internal state of the simulator. Through the simulator, the algorithms are
just given the state space and the possible actions to take, as well as the
information that they already have from their previous actions.

##  2 Background

Figure 1: Board for The Royal Game of Ur, showing coordinates and safe
positions.

###  2.1 Game of Ur

The Royal Game of Ur is a two player strategy racing board game, claimed to be
first played in Mesopotamia in third century BC. However the exact origin of
the game is still a matter of debate among historians. The game was long
forgotten, except being rediscovered among the Jewish population in Indian
city of Kochi, who continued playing a variant of it until 1950s. The Game of
Ur is also believed to inspire/transformed into the early form of Backgammon
(?).

The board consists of 20 squares, a large block of 3x4 squares, a small block
of 3x2 squares, and a bridge of 1x2 blocks connecting the two. Each player
starts with seven pieces (pawns) in hand and an empty board. There are four
pyramidal dice with two marked and two unmarked corners. The number of marked
corners that show up decide the number of positions to be moved by the active
player. On a score of four, player can roll over the dice again. A pawn must
bear off by exact throw. On landing on opponent’s pawn, the piece is removed
from the board and must begin its journey again. A piece sitting on a special
star-marked square is safe; the opponent can neither land on it, nor remove
the other opponent’s piece from that position. The first four squares in the
beginning of the pawn’s journey are safe by default, since an opponent cannot
land there. The first player whose all seven pieces are all borne off the
board has won the game (?).

Figure 2: Board movements as happen during a normal gameplay. The circles in
green and red represent different players and arrows represent the movement of
respective pieces.

#### Gameplay

The general move for the game is to move forward by the number of positions as
shown up on the dice. The two players start on their respective start
positions, on the opposite sides of the board, generally marked off as start.
The rule for starting vary depending on the version and the place of game
being played. In some places any number that shows up on the dice could be
allowed to start the game, while in other places a particular number might be
required to start-off with a particular piece. In yet another variant, the
particular number on the dice might be used to just bring the piece on the
board, and then another dice roll decides the number of pieces to be moved,
whereas in some variants the second dice roll might not be allowed. The
general movement of pieces is divided into war zones and safe zones. In case
of a safe zone, the player has no risk of the piece being eliminated by the
opponent, since the opponent cannot enter those positions (marked as rows a
and c in the figure 1), while in case of a war zone (marked as row b in the
board, figure 1), the player’s piece might get eliminated by the opponent,
depending on the position of the piece and the number that shows up on the
dice during opponent’s turn to roll the dice. The positions in the broad
marked by a star are called safe positions, where the opponent cannot
eliminate the other player’s piece. If a player’s piece is sitting on the safe
position and the opponent’s piece lands on it, then the opponent has to move
to the next position. There can be only a single piece situation on a position
at any given time. In case if the colliding piece is that of the opponent, the
piece gets eliminated, while if the piece is that of the current player, the
move is not allowed.

###  2.2 Algorithms

We also use the derivatives of Temporal Difference (TD) Algorithms, therefore
it is important to give a background on TD algorithms (?).

###  2.3 The Temporal Difference (TD) Algorithm

The problem solved by reinforcement learning, which defines an error signal
$\delta_{t}$ for state $V(s_{t})$:

$\delta_{t}=r(s^{\prime})+\gamma V(s^{\prime})-V(s)$

The error signal vanishes if $V(s_{t})$ reaches the target
$r(s^{\prime})+\gamma V(s^{\prime})$. The algorithm waits for the next state
$s^{\prime}$ and looks if for that state the reward or the value function is
known. If so, it changes $V(s)$ in that direction. Parameter $\gamma$
(typically 0.9) is called the discount factor. It takes into account that a
state further away in future. say $V(s^{\prime})=1$, might be a possible
successor of state $s$ in the course of the game, but it is not guaranteed
that the game path for the entire game leads from $s$ to $s^{\prime}$. Thus,
the game states more distant in the future are discounted in their effect on
$V(s)$. This clarifies the name TD, since for most states the reward is zero,
and the error signal in most cases is the temporal difference in the value
function.

###  2.4 Q-learning

Q-learning (?) is a popular learning algorithm that can be applied to most
sequential tasks to learn the state-action value. It is an off-policy learning
algorithm, as the policy being learnt is not executed during training, instead
a behaviour policy is used which is exploratory in nature. But the target
action is the one predicted by the policy using the following update rule
iteratively at each time step $t$:

$Q(s,a)\leftarrow Q(s,a)+\alpha(r+\gamma Q(s^{\prime},a^{\prime})-Q(s,a))$

where $a$ is the action that the behaviour policy predicts in the state $s$,
whereas $A$ is the action that our current learnt policy predicts. The above
update rule can be derived from the Bellman optimality equation for MDPs.

###  2.5 Expected Sarsa

Expected Sarsa improves the on-policy nature of Sarsa. Since the update rule
of Sarsa is dependent on the next action $a^{\prime}$ it cannot converge
unless the learning rate is reduced $(a\rightarrow 0)$ or exploration is
annealed $(\epsilon\rightarrow 0)$, since $a^{\prime}$ always has some degree
of randomness. Expected Sarsa changes this with an update rule that takes the
expected action-value instead of the action-value of $s^{\prime},a^{\prime}$:

$Q_{t+1}(s,a)=Q_{t}(s,a)+\alpha(r+\gamma\sum_{a^{\prime}}\pi(a^{\prime}|s^{\prime})Q_{t}(s^{\prime},a^{\prime})-Q_{t}(s,a))$

Since the update rule is now independent of the next action taken, and rather
dependent on the expected action-value, Expected Sarsa can indeed converge
(?). In case of a greedy policy $\pi$, Expected Sarsa is the same as
Q-learning.

##  3 Experimental Setup

###  3.1 The Game of Ur Simulator

For the purpose of this paper, we implemented our own simulator for the game
of Ur, which serves as a testbed for our algorithms and their comparisons. The
simulator is open source and available at
https://github.com/sidharth0094/game-of-ur-reinforcement-learning

The theoretical details of the simulator are given below.

###  3.2 Game representation as MDP

###  3.3 State representation:

Each square of the board is given a coordinate, for e.g.: (a,1), (a, 2), etc.
(as shown in Figure 1). Each state is represented by a tuple
$(((num\\_p_{1}),(p_{1}\cdots n)),((num\\_p_{2}),(p_{2}\cdots
n)),dice):position\\_piece\\_to\\_move$, where $num\\_p_{1}$ represents the
number of pieces of player $p_{1}$ that are yet to start, $p_{1}\cdots n$
represents the coordinates of pieces of player $p_{1}$ that are on board, here
$n$ represents the total number of pieces of a player, dice represents the
number that shows up on the dice, and $position\\_piece\\_to\\_move$
represents the position of the piece of the current player to be moved by the
number of steps that shows up on the dice. Likewise for player $p_{2}$. An
example state for a game with $4$ pieces and player $1$’s turn would be like:
$((2,((a,3),(a,4))),(3,((c,3))),1):4$, here $2$ represents that player $1$ has
2 pieces that are yet to start, which is followed by two tuples of positions
of pieces that are already on board, the following $3$ represents the number
of pieces of player $2$ that are yet to start, followed by the position of
piece on board, while $1$ is the number that shows up on the dice, and $4$
represents the position of piece of player $1$ to be moved, which in this case
is the one currently at $(‘a’,4)$.

###  3.4 Rewards:

The reward function for our MDP representation works in the following way. The
agent is given a reward of $+10$ when it successfully replaces the opponent’s
piece, since the opponent has to start with that piece again and the path
clears for the current player. The safe positions in the safe zones do not
have a reward associated with them, since the agent is encouraged to be in war
zone, while landing on the single safe position inside war zone has a reward
of $+20$ associated with it, as the piece here is safe, and it is a strategic
position to capture opponent’s pieces that cross it; the agent might want to
keep its piece here as long as possible. We also associate a reward of $-1$
with any step inside war zone, other than the one to the safe position
described above, as the piece is vulnerable to attack by the opponent, and
should move out of war zone as soon as possible. Winning has a reward of
$+100$ associated with it, while loosing has a reward of $0$. All other
positions on the board, namely in safe zone, have a reward of $0$ as well.

Initially, we had set the reward to be $+1$ for winning, and $0$ for loosing,
but we had to change to such a discretised function because of problems when
the agent tries to learn. In the absence of such a function, the agent takes a
very large number of episodes in order to learn efficiently, which results in
more compute time. Also, the agent is unable to learn the strategic moves well
enough, given the strategy is only applicable to a few parts of the game,
while the rest are independent of how the agent plays. We found that this
approach of breaking the reward function for multiple smaller sub-tasks helps
the agent learn faster and saves compute time.

Figure 3: Encoding of board coordinates for faster training, used for
representing board positions for deciding which piece to move forward

###  3.5 Actions:

All board positions are assigned an integer number, from 1 through 24, as
shown in Figure 3, in order to decipher the piece that needs to move forward.
This representation of using board positions to decide which piece to move
forward is better than using individual piece IDs as it allows the agent to
train faster by classifying the states with same coordinates, but different
pieces, into a single state, as opposed to considering them as different
states. The agent has the option to either go forward, or to make a null move,
which happens in case there is no legal move. The situation of not having a
legal move occurs in case all next positions are already occupied by the
current player’s pieces, or the required number of steps to finish the game
for a particular piece is less than the number that shows up on the dice.

Figure 4: Strategic move when each player has $4$ pieces. Here, player
represented by green piece has to decide between eliminating the red piece in
$(‘b’,1)$ or to move to a safe position in war zone. The decision making gets
more complex with a full $7$ piece game, where green also has to avoid being
eliminated by red.  Figure 5: Safe move inside of a war zone. It is green’s
turn to move, which with a dice roll of $4$ has to move to $(‘b’,5)$. This
move takes it closer to the goal state, and towards the end of war zone, as
opposed to it starting with a new piece. Other pieces on board not shown in
the figure Figure 6: Unsafe move inside of a war zone. It is green’s turn to
move, which with a dice roll of $3$ has to move to $(‘b’,3)$. Here, red is
vulnerable to be eliminated by green. Other pieces on board not shown in the
figure

##  4 Experiments

We formulate the problem as a multiagent MDP, where both agents compete
against each other to learn (?). The reward function works as defined in
(3.4). For our experiments, we consider only two dice, since every board
position is reachable by this configuration of dice. We have considered 4
pieces per player in order to train the agent quickly using limited
computational resources at hand. Another reason to consider only 4 pieces per
player is that this is the minimum number of pieces required for testing a
popular strategic move, represented in figure 4. Our action space consists of
forward and null moves, as described in (3.5).

For our experiments, we used an $\epsilon$-greedy approach, with an epsilon
value of $0.1$, which signifies that the agent explores with a probability of
$0.1$, while takes greedy actions with a probability of $0.9$. We trained our
agent using Q-learning, Expected Sarsa, and on-policy Monte Carlo, since we
thought it would be interesting to compare the performance of agents trained
using episodic learning algorithms like on-policy Monte Carlo, against the
popular TD learning based algorithms like tabular Q-learning and Expected
Sarsa. Our agents are trained on $100$K episodes for each of the algorithm,
and then tested on 100 gameplays against an agent following a stochastic
policy with equiprobable actions.

Since the state space of our environment is very large, therefore to keep a
track of how the agent learns, we record the change in value function for
state ((3, ((’a’, 3),)), (3, ((’c’, 3),)), 1), given that this state would
occur frequently over the training period of all agents. We keep a track of
time steps to win for each agent during training to observe if the agent is
learning the strategic moves to finish early.

We also tested a special board position with 4 pieces (displayed in figure 4),
wherein we tried testing for what piece does agent decide to move based on the
strategy it should learn. We show both safe and unsafe moves when the green
piece enters the war zone in figures 5 and 6.

##  5 Results

Algorithms | Games won | Games lost
---|---|---
Q-learning | 60 | 40
Monte Carlo | 55 | 45
Expected Sarsa | 54 | 46
Table 1: Table summarizing the results of agent performances trained on all
three methods and then tested on $100$ gameplays.

We show the results of our testing for $100$ gameplays after training 3
separate agents using Monte Carlo, Q-learning and Expected Sarsa, summarized
in Table 1. For our algorithms, Q-learning wins $60$ out of $100$ games, while
Monte Carlo and Expected Sarsa win $55$ and $54$ games respectively. This
result is not completely random, and demonstrates an agent learning to play
using popular strategic moves, as described below and shown in plots.

Figure 7: Time to finish for agents trained using the three methods. Here
Q-learning, Monte Carlo and Expected Sarsa are represented by green, red and
blue curves respectively. Note that Expected Sarsa demonstrates faster
learning.

We demonstrate the learning of our agents using the metric time to finish, as
shown in figure 7. We observe that for all $3$ agents trained, our time to
finish decreases over $100$K episodes. The sharpest decrease is shown by
Expected Sarsa, while both Q-learning and Monte Carlo show similar competing
curves. The curves do show fluctuations, but trend seems to move towards
stabilization.

Figure 8: Value function for agent trained using Monte Carlo on state
$((3,((a,3),)),(3,((c,3),)),1)$. Note the sharp increase and fluctuating
behaviour demonstrated. Figure 9: Value function for agent trained using
Q-learning on state $((3,((a,3),)),(3,((c,3),)),1)$. Figure 10: Value function
for agent trained using Expected Sarsa on state
$((3,((a,3),)),(3,((c,3),)),1)$. Figure 11: Strategic move learnt by the agent
to save the piece from elimination, by taking it from $(‘b’,8)$ to $(‘a’,8)$,
and saving it from opponent’s piece at $(‘b’,5)$

Our value functions for Monte Carlo, Q-learning and Expected Sarsa, for state
$((3,((a,3),)),(3,((c,3),)),1)$ are shown in Figures 8, 9, and 10 . The value
function for the given state does seem to increase for all $3$ agents. In case
of Monte Carlo, it shows a sharp increase, followed by a trend towards
stabilization, while the plots for Q-learning and Expected Sarsa show a much
smoother trend. One should not be misled that one agent is performing better
over the other, it just shows that there is a difference in the way they
learn.

We also demonstrate the strategic move that our agents learn, as shown in
figure 11. Our agents are able to learn this strategic move, in which the
piece on coordinate $(‘b’,8)$ is moved to $(‘a’,8)$. This is an important move
given the agent’s gameplay when at the intersection of war and safe zones.

##  6 Discussions

The testing of our agents using different methods show promising results. The
outcome was not always the smoothest, but for a lot of things we cannot
conclude with certainty as to why an agent behaves in the given way. We can
attribute this problem to the limitation of computational resources required
for training our agents, with such complex and large state spaces. We believe
that our agents could perform much better when trained with more episodes and
better computational resources.

Figure 12: Combined value functions for agents trained using all three methods
on state $((3,((a,3),)),(3,((c,3),)),1)$. Q-learning, Monte Carlo and Expected
Sarsa are shown by green, red and blue curves respectively.

We chose to show the value function for the state
$((3,((a,3),)),(3,((c,3),)),1)$, given that it is a prime state and occurs
very frequently (comparison of all three methods together is shown in figure
12). The disparity in smoothness, and the difference in values of the value
functions for the given state, of our plots could be attributed to the fact
that Monte Carlo takes full episode to learn, while TD methods do not. The
step updates in case of TD methods are biased on the initial conditions of
learning parameters. The bootstrapping process typically updates a function or
lookup $Q(s,a)$ on a successor value $Q(s^{\prime},a^{\prime})$ using whatever
the current estimates are in the latter. Clearly, at the very start of
learning, these estimates contain no information from any real rewards or
state transitions. However, if the agent is learning as it should, then this
bias will reduce asymptotically over multiple iterations, but this bias is
known to cause problems, specially for off-policy methods. Monte Carlo
methods, on the other hand, do not suffer from this bias, as each update is
made after the entire episode, using the true sample of $Q(s,a)$. But, Monte
Carlo methods can suffer from high variance, which means more samples are
required to achieve the same degree of learning compared to TD methods. A
middle ground between these two problems could be achieved by using
TD($\lambda$).

Our agent learns to move the piece on $(‘b’,8)$ inside of the war zone, to
coordinate $(‘a’,8)$ inside the safe zone. We believe that this is an
important strategic move that it learns, since the piece at $(‘b’,8)$ will
reach the end position in two steps; while if the opponent’s piece at position
$(‘b’,5)$ eliminates it, then the piece at $(‘b’,8)$ would have to restart. So
agent by moving piece to $(‘a’,8)$ didn’t just move it closer to winning state
but also saved it from eliminating.

##  7 Conclusion

In this report, we compared the performance of $3$ agents, trained using
entirely different methods, namely Monte Carlo, Q-learning and Expected Sarsa,
to play the ancient strategic board game, Royal Game of Ur. The state space
for our game is complex and large, but our agents show promising results at
playing the game and learning important strategic moves. Although it is hard
to conclude that when trained with limited resources which algorithm performs
better overall than the others, but Expected Sarsa showed promising results in
case of fastest learning.

In future, we plan to run our agent on the given algorithms and their variants
for more than $1$ million episodes, as is the case in community when testing
on board games, as we speculate that this would allow our agent to experience
more states, and therefore learn better policies. We also plan to train our
agent using sophisticated deep RL methods like DQN and Double DQN, to see if
the agent shows significant differences in performance when trained on those.

## References

  * [Brockman et al., 2016] Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., and Zaremba, W. (2016).  Openai gym.  arXiv preprint arXiv:1606.01540.
  * [Finkel, 2007] Finkel, I. L. (2007).  On the rules for the royal game of ur.  Ancient Board Games in Perspective. British Museum Press, London, pages 16–32.
  * [Ghory, 2004] Ghory, I. (2004).  Reinforcement learning in board games.  Department of Computer Science, University of Bristol, Tech. Rep, page 105.
  * [He, 2018] He, S. (2018).  Deep reinforcement learning-of how to win at battleship.
  * [Konen, 2015] Konen, W. (2015).  Reinforcement learning for board games: The temporal difference algorithm.
  * [Mnih et al., 2015] Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., Graves, A., Riedmiller, M., Fidjeland, A. K., Ostrovski, G., et al. (2015).  Human-level control through deep reinforcement learning.  Nature, 518(7540):529.
  * [Montague et al., 1996] Montague, P., Dayan, P., and Sejnowski, T. (1996).  A framework for mesencephalic dopamine systems based on predictive hebbian learning.  The Journal of Neuroscience, 16(5):1936–1947.
  * [Montague et al., 1993] Montague, P. R., Dayan, P., Nowlan, S. J., Pouget, A., and Sejnowski, T. (1993).  Using aperiodic reinforcement for directed self-organization during development.  In Advances in neural information processing systems, pages 969–976.
  * [Montague and Sejnowski, 1994] Montague, P. R. and Sejnowski, T. J. (1994).  The predictive brain: temporal coincidence and temporal order in synaptic learning mechanisms.  Learning & Memory, 1(1):1–33.
  * [Schraudolph et al., 1994] Schraudolph, N. N., Dayan, P., and Sejnowski, T. J. (1994).  Temporal difference learning of position evaluation in the game of go.  In Advances in Neural Information Processing Systems, pages 817–824.
  * [Schultz, 1998] Schultz, W. (1998).  Predictive reward signal of dopamine neurons.  Journal of Neurophysiology, 80(1):1–27.
  * [Schultz et al., 1997] Schultz, W., Dayan, P., and Montague, P. R. (1997).  A neural substrate of prediction and reward.  Science, 275(5306):1593–1599.
  * [Seijen et al., 2009] Seijen, H. V., Hasselt, H. V., Whiteson, S., and Wiering, M. (2009).  A theoretical and empirical analysis of expected sarsa.  2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning.
  * [Sejnowski et al., 1995] Sejnowski, T. J., Dayan, P., and Montague, P. R. (1995).  Predictive hebbian learning.  Proceedings of the eighth annual conference on Computational learning theory - COLT 95.
  * [Silver et al., 2016] Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016).  Mastering the game of go with deep neural networks and tree search.  nature, 529(7587):484.
  * [Smith et al., 2006] Smith, A., Li, M., Becker, S., and Kapur, S. (2006).  Dopamine, prediction error and associative learning: A model-based account.  Network: Computation in Neural Systems, 17(1):61–84.
  * [Sturtevant, 1961] Sturtevant, W. C. (1961).  Board and table games from many civilizations . r. c. bell.  American Anthropologist, 63(6):1396–1396.
  * [Sutton and Barto, 2018] Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * [Tan, 1993] Tan, M. (1993).  Multi-agent reinforcement learning: Independent vs. cooperative agents.  Machine Learning Proceedings 1993, page 330–337.
  * [Tesauro, 1995a] Tesauro, G. (1995a).  Td-gammon: A self-teaching backgammon program.  In Applications of Neural Networks, pages 267–285. Springer.
  * [Tesauro, 1995b] Tesauro, G. (1995b).  Temporal difference learning and td-gammon.  Communications of the ACM, 38(3):58–68.
  * [Watkins and Dayan, 1992] Watkins, C. J. and Dayan, P. (1992).  Q-learning.  Machine learning, 8(3-4):279–292.


# Knowledge-Grounded Response Generation with
Deep Attentional Latent-Variable Model

Hao-Tong Ye Kai-Ling Lo Shang-Yu Su Yun-Nung Chen
National Taiwan University, Taiwan
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

End-to-end dialogue generation has achieved promising results without using
handcrafted features and attributes specific for each task and corpus.
However, one of the fatal drawbacks in such approaches is that they are unable
to generate informative utterances, so it limits their usage from some real-
world conversational applications. This paper attempts at generating diverse
and informative responses with a variational generation model, which contains
a joint attention mechanism conditioning on the information from both dialogue
contexts and extra knowledge.

## Introduction

Dialogue-related research can be mainly categorized into two branches: (1)
task-oriented: the system trying to help users complete a certain task (2)
chit-chat: the system that can handle casual conversations that do not belong
to any specific domain. Recently, how to bridge these two branches has become
a new research direction in conversation modeling, where the system can
generate useful and fact-grounded responses via external knowledge without
domain constraints (?; ?; ?).

Prior work showed that end-to-end neural models are capable of generating
sound responses for chit-chat dialogues in a data-driven way, without using
handcrafted features specific for each corpus or different task (?; ?; ?; ?).
However, such systems still highly rely on the information stored in training
corpora, which is constrained by time, space, and speakers during data
collection. Also, the systems lack the direct access to external information
and the knowledge-grounded mechanism; therefore they cannot effectively
retrieve real-world common senses and facts in order to respond properly. This
fundamental limitation makes the end-to-end systems difficult to complete
tasks (?; ?) or generate fact-grounded chit-chat (?).

On the other hand, for traditional dialogue systems, we can easily insert
external knowledge and facts into the model with the cost of detailed hand-
coding features, which requires a large amount of pre-processing and data
labeling. For those tasks or corpora related to complex information or
professional knowledge, pre-processing and annotations are difficult to
acquire, thus making this approach impractical.

In this work, we propose an end-to-end variational model with the attention
mechanism that models the interactions between dialogue contexts and external
knowledge. This model is capable of balancing between scalability and
generalization of neural models and provides more factual and knowledge-
grounded responses compared to the traditional systems. Such extension is
especially important for a conversational model deployed in systems requiring
more relevant and informative interactions (e.g. the recommendation system).

To test the ability of generating knowledge-grounded responses, the seventh
Dialog System Technology Challenge (DSTC7) proposed a benchmark Reddit
dataset, in which the conversations are accompanied with a link to an external
webpage that may contain related facts and knowledge. A dataset example is
shown in Table 1, where the last two responses share the same contexts, and
the fact retrieved by our model contains related knowledge given the
conversation.

Conversation:
---
til monty python member terry gilliam was author j . k rowling ’s first choice
to direct the first harry potter movie , but was rejected for chris columbus .
inan interview he said ” i was the perfect guy to do harry potter … i mean ,
chris columbus ’ versions are terrible . just dull . pedestrian ”
https://en.wikipedia.org/wiki/terry_gilliam
—- gilliam would have been great - but we ’d still be waiting on the second
movie .
——– he should do an animated version
———— harry potter & the giant soft gradient foot
—- they hired chris columbus due to his experience directing child actors .
——– i also think he ’s really good at seeing things from a kid ’s imagination
. those first 2 movies really seemed
like someone went into my head and said ” ok we ’re going to film a movie
here!”
——– came here to say this. iirc, he was hired specifically because he was good
with kids… which gilliam had
little experience with. i think they turned out very well, very true to the
books.
Retrieved top-1 fact:
j . k . rowling , the author of the harry potter series , is a fan of
gilliam’s work . consequently , he was rowling’s first choice to direct harry
potter and the philosopher’s stone in 2000 , but warner bros . ultimately
chose chris columbus for the job . [ 32 ] in response to this decision ,
gilliam said that ” i was the perfect guy to do harry potter . i remember
leaving the meeting , getting in my car , and driving for about two hours
along mulholland drive just so angry . i mean , chris columbus ’ versions are
terrible . just dull . pedestrian . ” [ 33 ] in 2006 , gilliam said that he
found alfonso cuarón ’ s harry potter and the prisoner of azkaban to be ”
really good … much closer to what i would’ve done . ” [ 34 ] in retrospect ,
however , gilliam has stated that he wouldn’t have liked to direct any potter
film . in a 2005 interview with total film , he said that he would not enjoy
working on such an expensive project because of interference from studio
executives . [ 35 ]
Table 1: Dataset example from subreddit todayilearned. The horizontal lines
indicate the tree-structure of the conversation; we can see that the last two
responses share the same contexts. The shown fact retrieved by our model is
considered the most relevant to the given conversation among all facts
extracted by the official script from the wikipedia page.

## Proposed Approach

The task is to generate a suitable response that contains grounded knowledge
or factual information given its conversation contexts.

### Model Framework

The main difference between this task and others is the context-relevant
facts, which are retrieved from the website links mentioned at the beginning
of conversations. This external knowledge provides our model cues about how to
ground the information in the response. Therefore, we first build a retrieval
model to effectively obtain the fact containing the relevant knowledge, and
then learn the conversation model to generate the knowledge-grounded response.
Below we describe the detail of the proposed conversation model, where given a
conversation con texts and its related facts, the goal is to generate the next
probable sentence with informative knowledge.

### Conversation Model

For each conversation, our model takes dialogue contexts $\mathbf{C}$ and
context-relevant facts $\mathbf{F}$ as the input, and outputs the fact-
grounded response $\mathbf{R}$. Specifically,
$\mathbf{C}=\\{c_{i}\\}_{i=1}^{N_{c}}$, where
$c_{n}=\\{c_{n,j}\\}_{j=1}^{T^{c}_{n}}$ is a sequence of word embeddings in
the $n$-th utterance of the conversation. For the fact,
$\mathbf{F}=\\{f_{i}\\}_{i=1}^{N_{f}}$, where
$f_{n}=\\{f_{n,j}\\}_{j=1}^{T^{f}_{n}}$ is a sequence of word embeddings of
$n$-th fact. The generated response is formulated as
$\mathbf{R}=\\{r_{i}\\}_{i=1}^{T^{r}}$. In our model, we treat the
conversation utterances and facts as two sequences, with a special token used
to separate utterances in a dialogue or a fact; that is, the contexts and
facts are turned into $\mathbf{C}=\\{c_{i}\\}_{i=1}^{N}$ and
$\mathbf{F}=\\{f_{j}\\}_{j=1}^{M}$ respectively, where $c_{i}$ and $f_{j}$ are
word embedding vectors.

First, we use two separate encoders, $\text{Enc}_{C}$ and $\text{Enc}_{H}$, to
encode the dialogue contexts and facts respectively. The encoded contexts and
facts $H_{C}=\\{h^{c}_{i}\\}_{i=1}^{N}$, $H_{F}=\\{h^{f}_{j}\\}_{j=1}^{M}$ are
fed into the attention module, and then the decoder generates the fact-
grounded response. In our model, with the encoded contexts and facts, the
decoder generates the response in an auto-regressive way, which is commonly
called as a sequence-to-sequence model. For each step, the output of the
decoder $o_{t}$ is calculated from previous output $o_{t-1}$ and the encoded
information $H_{C}$ and $H_{F}$:

$o_{t}=\text{Dec}(o_{t-1},\text{Attn}(o_{t-1},H_{C},H_{F})).$ (1)

The output of the decoder, $o_{t}$, is then projected to the vocabulary
through a linear layer followed by a softmax activation. The proposed model is
illustrated in Figure 1, where there are several encoders that focus on
different types of information. During generation, this model proposes 1) a
_fact-grounded attention_ mechanism that can explicitly consider the contexts
snd facts and 2) a _conditional variational generation_ model that can produce
diverse and informative responses. The detail of two module is described
below.

Figure 1: Illustration of the proposed model architecture.

### Fact-Grounded Attention

In order to capture the relations between these three types of information,
dialogue contexts, facts, and responses, we apply three attention variants to
model their interactions (?): _context-only attention_ , _parallel attention_
, and _context-guided fact attention_ detailed below.

#### Context-Only Attention

One simple attention baseline only uses the information from contexts to
generate the response. That is, with the last-step output $o_{t-1}$ and the
encoded information $H_{C},H_{F}$, the attention is calculated as:

Attn
$\displaystyle(o_{t-1},H_{C},H_{F})=\sum_{i=1}^{N}\alpha^{t}_{i}h^{c}_{i},$
(2) $\displaystyle e^{t}_{i}$
$\displaystyle=v_{c}^{T}\text{tanh}(W^{c}_{1}o_{t-1}+W^{c}_{2}h^{c}_{i})+b_{c},$
$\displaystyle\alpha^{t}$ $\displaystyle=\text{softmax}(e^{t}),$

where $v_{c}$, $W^{c}_{1}$, $W^{c}_{2}$, and $b_{c}$ are trainable parameters.

#### Parallel Attention

In order to well utilize the facts, one trivial solution is to consider facts
as the additional contexts; that is:

Attn
$\displaystyle(o_{t-1},H_{C},H_{F})=\Bigg{[}\sum_{i=1}^{N}\alpha^{t}_{i}h^{c}_{i};\sum_{j=1}^{M}\beta^{t}_{j}h^{f}_{j}\Bigg{]}$
(3) $\displaystyle m^{t}_{j}$
$\displaystyle=v_{f}^{T}\text{tanh}(W^{f}_{1}o_{t-1}+W^{f}_{2}h^{f}_{j})+b_{f},$
$\displaystyle\beta^{t}$ $\displaystyle=\text{softmax}(m^{t}),$

and $\alpha^{t}$ is the same as the context-only attention. $v_{f}$,
$W^{f}_{1}$, $W^{f}_{2}$, $b_{f}$ are trainable parameters.

#### Context-Guided Fact Attention

To better model the interaction between contexts and facts, we proposed to use
the information from contexts to guide the attention towards facts.
Specifically, we modify the attention on facts from the parallel attention as
below. We first calculate the attention distribution from contexts to facts,

$\displaystyle M_{i,j}$
$\displaystyle=v_{g}^{T}\text{tanh}(W^{g}_{1}h^{c}_{i}+W^{g}_{2}h^{f}_{j})+b_{g},$
(4) $\displaystyle m^{c}_{j}$ $\displaystyle=\sum_{i=1}^{N}M_{i,j},$
$\displaystyle\beta^{c}$ $\displaystyle=\text{softmax}(m^{c}).$

Then, for each step, we calculate the attention from the last-step output to
facts, and take the mean of two distributions as the final attention
distribution on facts:

$\displaystyle\hat{m}^{t}_{i}$
$\displaystyle=v_{o}^{T}\text{tanh}(W^{o}_{1}o_{t-1}+W^{o}_{2}h^{c}_{i})+b_{o},$
(5) $\displaystyle\hat{\beta}^{t}$
$\displaystyle=\text{softmax}(\hat{m}^{t}),$ $\displaystyle\beta^{t}$
$\displaystyle=\frac{\hat{\beta}^{t}+\beta^{c}}{2},$

where $v_{g}$, $v_{o}$, $W_{1}^{g}$, $W_{2}^{g}$, $W_{1}^{o}$, $W_{2}^{o}$,
$b_{g}$, and $b_{o}$ are trainable parameters. Hence, the obtained attention
is guided by the contextual information.

### Conditional Variational Generation

The conversations in the dataset for the DSTC7 challenge are tree-like
structures, where for each context, there may be more than one reference
responses. This is also an important perspective for the natural
conversations: for arbitrary dialogue contexts, there are usually not only one
unique way to respond to it.

With the above consideration, we take the benefit from the variational
autoencoder for this task, which has the better capability of capturing such
relation than a simple seq2seq model (?; ?). The detail of the variational
model is described below.

#### CVAE for Dialogue Generation

For each conversation, we represent it via four random variables: the desired
response $R$, the contexts and facts, $C$ and $F$, and a latent variable $z$.
The conditional probability $p(R,z\mid C,F)$ can be rewritten as:

$p(R,z\mid C,F)=p(R\mid C,F,z)p(z\mid C,F).$ (6)

We model the probability $p(R\mid C,F,z)$ and $p(z\mid C,F)$ using the
parameters $\theta$ and $\phi$ respectively. Under the variational autoencoder
(VAE) framework, we can interpret $\theta$ and $\phi$ as the decoder and the
encoder; by setting up a Bayesian prior $p(z\mid C,F)$, our optimization
target $p_{\theta}(R\mid C,F)$ becomes the variational lower bound (ELBO):

$\displaystyle\log p_{\theta}(R\mid C,F)\geq$
$\displaystyle-\text{KL}(q_{\phi}(z\mid R,C,F)\parallel p(z\mid C,F))$ (7)
$\displaystyle\ +\mathbb{E}_{q_{\phi}(z\mid R,C,F)}[\log p_{\theta}(R\mid
C,F,z)].$

In our model, the prior $p(z\mid C,F)$ is set as $\mathcal{N}(0,I)$.

#### Annealing Loss of KL Divergence

As mentioned above, the optimization target, which is the variational lower
bound of $\log p_{\theta}(R\mid C,F)$, is composed of two sub-goals: one is to
minimize the KL divergence between the prior and the conditional encoder
probability $q_{\phi}$; another is to maximize the reconstruction probability.

It is found that the model tends to minimize the KL divergence instead of
reducing the reconstruction error during early training, resulting in a KL
vanishing issue. In order to alleviate the strong bias on minimization of KL
divergence, we apply the annealing loss trick to scale down the effect of the
KL term at the beginning of training for improving the performance (?).

### Training

The proposed model is trained to generate the responses using the CVAE
objective, where the attention mechanisms enforce the responses to cover the
fact-related information for _knowledge-grounded response generation_.

## Experiments

To evaluate the proposed model, we conduct the experiments on the DSTC7
challenge. The used dataset and the experimental setting are described below.
Then the results are analyzed in terms of objective and subjective evaluation
metrics.

| Time Period | Before Filter | After Filter
---|---|---|---
Train | 2015-01$\sim$2016-12 | 1,101,684 | 142,750
Dev | 2017-01$\sim$2017-06 | 116,858 | 14,875
Table 2: Statistics of the used dataset.

### Dataset

The dataset used in DSTC7-Track2 is crawled from Reddit with the
scripts111https://github.com/DSTC-MSR-NLP/DSTC7-End-to-End-Conversation-
Modeling, which consists of discussions from subreddits like todayilearned,
worldnews, movies, etc. In the dataset, the posts include a link to an
external webpage, from which the facts for each conversation are then
extracted.

In order to encourage our conversation model to contain the factual
information, we process this dataset to make sure the conversations in which
the context and provided facts are relevant. The processing procedure is
described as:

  1. 1.

Fact relevance: Because the facts are extracted from the HTML source codes of
webpages, some of them lack the relevant information (e.g. metadata), we use
TF-IDF to rank all facts and keep the top-1 fact as the relevant knowledge for
ensuring better data quality.

  2. 2.

Knowledge-grounded response: Because the discussions in some conversations may
deviate from the original topic, making all facts being irrelevant to the
dialogue contexts, we thus filter out data samples where the response and the
retrieved fact have no common words without considering punctuations and
stopwords222We used stopwords defined in spaCy.. This procedure ensures the
training data to match our goal about knowledge-grounded responses.

Due to the limitation of computation resources (one GTX 1080), we use only a
subset of training data, and discard the data samples with the responses
longer than 20. Table 2 shows the detailed statistics of the dataset after our
processing.

Model | B-1 | B-2 | B-3 | B-4 | N-1 | N-2 | N-3 | N-4 | MET | Div-1 | Div-2 | Ent-1 | Ent-2 | Ent-3 | Ent-4
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Baseline | 2.861 | .566 | .143 | .041 | .007 | .007 | .007 | .007 | 2.439 | .004 | .012 | 3.937 | 4.958 | 5.504 | 5.996
CO | 2.634 | .513 | .130 | .038 | .006 | .006 | .006 | .006 | 2.417 | .013 | .028 | 4.137 | 5.392 | 6.148 | 6.734
+CVAE | 2.690 | .527 | .145 | .042 | .007 | .007 | .007 | .007 | 2.371 | .013 | .030 | 4.204 | 5.436 | 6.239 | 7.049
PA | 3.698 | .763 | .200 | .063 | .020 | .021 | .021 | .021 | 2.574 | .012 | .027 | 4.244 | 5.378 | 6.040 | 6.576
+CVAE | 2.449 | .538 | .129 | .033 | .009 | .009 | .009 | .009 | 2.301 | .011 | .027 | 4.120 | 5.338 | 6.125 | 6.775
CG | 2.142 | .443 | .124 | .040 | .004 | .004 | .004 | .004 | 2.258 | .011 | .026 | 4.131 | 5.300 | 6.082 | 6.820
+CVAE | 3.898 | .817 | .223 | .074 | .023 | .024 | .024 | .024 | 2.620 | .012 | .027 | 4.089 | 5.220 | 5.916 | 6.427
Table 3: The automatic evaluation results of the baselines and the proposed methods. Baseline is a context-to-response seq2seq model without attention. CO, PA, CG correspond to context-only attention, parallel attention and context-guided attention respectively. (B: BLEU; N: Nist; MET: METEOR) | Model | Context | Interest | Fluency | Knowledge | Average
---|---|---|---|---|---|---
| Relevance | Relatedness
Offline | PA | 2.47$\pm$0.86 | 2.37$\pm$0.75 | 4.13$\pm$0.85 | 2.19$\pm$0.87 | 2.79
PA+CVAE | 2.40$\pm$0.81 | 2.38$\pm$0.77 | 4.00$\pm$0.92 | 2.10$\pm$0.86 | 2.72
CG | 2.25$\pm$0.83 | 2.18$\pm$0.76 | 3.86$\pm$1.07 | 2.02$\pm$0.83 | 2.58
Official | Submitted (CG+CVAE) | 2.52$\pm$0.04 | 2.40$\pm$0.05 | - | - | 2.46
Best | 3.09$\pm$0.04 | 2.87$\pm$0.05 | - | - | 2.94
Human | 3.61$\pm$0.04 | 3.49$\pm$0.04 | - | - | 3.55
Table 4: Human evaluation results in our offline and the official evaluation.

### Training Details

Considering that the dataset contains a large amount of Internet slangs and
spoken English, we train a 100 dimension word embeddings via GLoVe from train
and development conversations and facts (?). We truncate the context to the
last $100$ tokens and the fact to the first $500$ tokens.

The context encoder $Enc_{C}$ is a 2-layer bidirectional GRU (?) with hidden
size 128; the fact encoder $Enc_{H}$ is a convolutional network with 1,2,3
width filters, and 128 feature maps per filter. The decoder $Dec$ is a 2-layer
unidirectional GRU with the hidden size 128. For the CVAE variants, another
2-layer bidirectional GRU with the hidden size 128 is used to encode the
responses.

Our models are trained using the teacher-forcing mechanism to maximize the
likelihood of generating $\mathbf{R}=\\{r_{i}\\}_{i=1}^{T^{r}}$. We used adam
(?) with the default setting as our optimizer. During testing, we apply the
beam search where the beam size is $8$.

### Results

In the experiments, we perform two sets of evaluation, automatic evaluation
and human evaluation, to better validate our generated results.

#### Automatic Evaluation

Our evaluation metrics include BLEU (?), METEOR (?), NIST (?), diversity (?)
and entropy (?) scores. We use the implementation in the Python package nlg-
eval333https://github.com/Maluuba/nlg-eval for BLEU and METEOR scores (?), and
the NLTK toolkit to calculate NIST scores. Our results are shown in Table 3.

It can be found that the context-guided attention model with CVAE (CG+CVAE)
achieves better performance for most metrics in terms of the similarity
between the generated responses and the ground truth responses. This justifies
the effectiveness of our context-guided attention, because its goal is to
generate responses containing more relevant knowledge, and the metrics
slightly measure the relatedness. However, the context-only attention with
CVAE (CO+VVAE) obtains the higher diversity, which is also important for this
generation task. The results show the small improvement achieved by the
proposed CVAE model in terms of the generation quality and the diversity.

#### Human Evaluation

In order to understand the effect of our fact-grounded attention and
variational generation, we conduct human evaluation on three proposed methods:
the parallel attention model as our baseline (PA), compared with the parallel
attention with variational generation (PA+CVAE), and the context-guided
attention (CG). First, we randomly sample 100 testing samples that fulfill the
following two conditions:

  1. 1.

Each response has at least 3 words, because some methods tend to produce very
short responses, which is hard to evaluate.

  2. 2.

Due to the goal about fact-grounded generation, we make sure that the contexts
and the retrieved fact have more than 3 common words for each sample, where
punctuations and stop-words are not considered.

Then we conduct human evaluation for our proposed methods in a similar way to
the official evaluation:

  1. 1.

In addition to relevance and interest, which are asked in official evaluation,
we ask the judges to evaluate two additional metrics: fluency and knowledge
relatedness (to the retrieved fact) of our response.

  2. 2.

Because we only pick one fact based on the contexts as our model input, we
directly provide this fact to judges as the extra information for them to
better evaluate knowledge relatedness of the response.

The results are shown in Table 4. The submitted system, the best achieved
results, and human performance are also included in Table 4 for better
comparison. Note that the numbers for two sets of evaluation may not be
directly compared but for reference.

In the offline human evaluation, it is found that the proposed models do not
achieve better performance and the difference between all models are small.
From the official evaluation, our submitted results are also between
_disagree_ (2) and _neutral_ (3) as in our evaluation, but the context-guided
attention achieves slightly better numbers than other proposed models shown in
the offline setting. Furthermore, the best achieved performance is about 2.94,
which is also lower than _neutral_ (3), implying the difficulty of this task.
It is clear that there is a huge gap between the currently machine-achieved
and human-achieved performance, so this task requires further investigation.

Retrieved top-1 fact:
---
in the united states , centenarians traditionally receive a letter from the
president , congratulating them for their longevity . nbc ’ s today show has
also named new centenarians on air since 1983 . centenarians born in ireland
receive a â‚¬ 2,540 ” centenarians ’ bounty ” and a letter from the president
of ireland , even if they are resident abroad . [ 63 ] japanese centenarians
receive a silver cup and a certificate from the prime minister of japan upon
their 100th birthday , honouring them for their longevity and prosperity in
their lives . swedish centenarians receive a telegram from the king and queen
of sweden . [ 64 ] centenarians born in italy receive a letter from the
president of italy . in japan , a ” national respect for the aged day ” has
been celebrated every september since 1966 .
Conversation:
– til in the united states , people who turn 100 years old receive a letter
from the president , congratulating them on their
longevity .
– same in canada but 90 instead of 100
Ground Truth: is that the canadian exchange rate these days ?
PA Response: they are the same thing .
PA+CVAE Response: you can have to be a .
CG Response: it’s not the same thing in the uk .
Table 5: Model response sample.

### Qualitative Analysis

The above results tell that there is no significant difference between our
proposed models and baselines. A sample model responses from the human
evaluation set is shown in Table 5 for our qualitative analysis. In this
example, adding CVAE generates a more diverse response than the parallel
attention result, but may not effectively ground the knowledge in the
sentence. Also, our context-guided result seems to focus more on the fact
compared to other models. However, the ground truth in the data is very
difficult to simulate for the current models, because it may need additional
knowledge or common sense. From the current results achieved by our model, we
conclude that this task still needs further investigation.

## Conclusion

We describe a variational knowledge-grounded conversation system, which
attempts at modeling the relations between dialogue contexts and external
facts in an end-to-end fashion. It guides a potential research direction about
how external information interacts with dialogues and how the machine can
capture such interaction for better knowledge-grounded response generation. In
the experiments on DSTC7, the results demonstrate the difficulty of this task,
because almost all current models fail to generate reasonable responses.
Therefore, the knowledge-grounded dialogue modeling requires further study in
order to advance the machine’s capacity of producing a informative and
knowledgable conversation.

## References

  * [Bahdanau, Cho, and Bengio 2014] Bahdanau, D.; Cho, K.; and Bengio, Y.  2014\.  Neural machine translation by jointly learning to align and translate.  arXiv preprint arXiv:1409.0473.
  * [Banerjee and Lavie 2005] Banerjee, S., and Lavie, A.  2005\.  Meteor: An automatic metric for mt evaluation with improved correlation with human judgments.  In Proceedings of the acl workshop on intrinsic and extrinsic evaluation measures for machine translation and/or summarization, 65–72.
  * [Bowman et al. 2016] Bowman, S. R.; Vilnis, L.; Vinyals, O.; Dai, A.; Jozefowicz, R.; and Bengio, S.  2016\.  Generating sentences from a continuous space.  In Proceedings of The 20th SIGNLL Conference on Computational Natural Language Learning, 10–21.
  * [Cho et al. 2014] Cho, K.; Van Merriënboer, B.; Gulcehre, C.; Bahdanau, D.; Bougares, F.; Schwenk, H.; and Bengio, Y.  2014\.  Learning phrase representations using rnn encoder-decoder for statistical machine translation.  arXiv preprint arXiv:1406.1078.
  * [Doddington 2002] Doddington, G.  2002\.  Automatic evaluation of machine translation quality using n-gram co-occurrence statistics.  In Proceedings of the second international conference on Human Language Technology Research, 138–145.  Morgan Kaufmann Publishers Inc.
  * [Gao, Galley, and Li 2018] Gao, J.; Galley, M.; and Li, L.  2018\.  Neural approaches to conversational ai.  1371–1374.
  * [Ghazvininejad et al. 2017] Ghazvininejad, M.; Brockett, C.; Chang, M.-W.; Dolan, B.; Gao, J.; Yih, W.-t.; and Galley, M.  2017\.  A knowledge-grounded neural conversation model.  arXiv preprint arXiv:1702.01932.
  * [Hori and Hori 2017] Hori, C., and Hori, T.  2017\.  End-to-end conversation modeling track in dstc6.  arXiv preprint arXiv:1706.07440.
  * [Kingma and Ba 2014] Kingma, D. P., and Ba, J.  2014\.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980.
  * [Kingma and Welling 2013] Kingma, D. P., and Welling, M.  2013\.  Auto-encoding variational bayes.  arXiv preprint arXiv:1312.6114.
  * [Li et al. 2016a] Li, J.; Galley, M.; Brockett, C.; Gao, J.; and Dolan, B.  2016a.  A diversity-promoting objective function for neural conversation models.  In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 110–119.
  * [Li et al. 2016b] Li, J.; Monroe, W.; Ritter, A.; Galley, M.; Gao, J.; and Jurafsky, D.  2016b.  Deep reinforcement learning for dialogue generation.  arXiv preprint arXiv:1606.01541.
  * [Li et al. 2017] Li, X.; Chen, Y.-N.; Li, L.; Gao, J.; and Celikyilmaz, A.  2017\.  End-to-end task-completion neural dialogue systems.  In Proceedings of the Eighth International Joint Conference on Natural Language Processing (Volume 1: Long Papers), volume 1, 733–743.
  * [Papineni et al. 2002] Papineni, K.; Roukos, S.; Ward, T.; and Zhu, W.-J.  2002\.  Bleu: a method for automatic evaluation of machine translation.  In Proceedings of the 40th annual meeting on association for computational linguistics, 311–318.  Association for Computational Linguistics.
  * [Peng et al. 2018] Peng, B.; Li, X.; Gao, J.; Liu, J.; Chen, Y.-N.; and Wong, K.-F.  2018\.  Adversarial advantage actor-critic model for task-completion dialogue policy learning.  In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 6149–6153.  IEEE.
  * [Pennington, Socher, and Manning 2014] Pennington, J.; Socher, R.; and Manning, C.  2014\.  Glove: Global vectors for word representation.  In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), 1532–1543.
  * [Sharma et al. 2017] Sharma, S.; El Asri, L.; Schulz, H.; and Zumer, J.  2017\.  Relevance of unsupervised metrics in task-oriented dialogue for evaluating natural language generation.  CoRR abs/1706.09799.
  * [Sohn, Lee, and Yan 2015] Sohn, K.; Lee, H.; and Yan, X.  2015\.  Learning structured output representation using deep conditional generative models.  In Advances in Neural Information Processing Systems, 3483–3491.
  * [Sordoni et al. 2015] Sordoni, A.; Galley, M.; Auli, M.; Brockett, C.; Ji, Y.; Mitchell, M.; Nie, J.-Y.; Gao, J.; and Dolan, B.  2015\.  A neural network approach to context-sensitive generation of conversational responses.  In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 196–205.
  * [Vinyals and Le 2015] Vinyals, O., and Le, Q.  2015\.  A neural conversational model.  ICML Deep Learning Workshop 2015.
  * [Yoshino et al. 2018] Yoshino, K.; Hori, C.; Perez, J.; D’Haro, L. F.; Polymenakos, L.; Gunasekara, C.; Lasecki, W. S.; Kummerfeld, J.; Galley, M.; Brockett, C.; Gao, J.; Dolan, B.; Gao, S.; Marks, T. K.; Parikh, D.; and Batra, D.  2018\.  The 7th dialog system technology challenge.  arXiv preprint.
  * [Zhang et al. 2018] Zhang, Y.; Galley, M.; Gao, J.; Gan, Z.; Li, X.; Brockett, C.; and Dolan, B.  2018\.  Generating informative and diverse conversational responses via adversarial information maximization.  arXiv preprint arXiv:1809.05972.