Strategic Dialogue Management via Deep Reinforcement Learning

Introduction

Artificially intelligent agents can require strategic conversational skills to negotiate during their interactions with other natural or artificial agents, e.g. “A: I will give/tell you X if you give/tell me Y?, B: Okay”. While typical conversations of artificial agents assume cooperative behaviour from partner conversants, strategic conversation does not assume full cooperation during the interaction between agents . Throughout this paper, we will use a strategic card-trading board game to illustrate our approach. Board games with trading aspects aim not only at entertaining people, but also at training them with trading skills. Popular board games of this kind include Last Will, Settlers of Catan, and Power Grid, among others . While these games can be played between humans, they can also be played between computers and humans. The trading behaviours of AI agents in computer games are usually based on carefully tuned rules , search algorithms such as Monte-Carlo tree search , and reinforcement learning with tabular representations or linear function approximation . However, the application of reinforcement learning is not trivial due to the complexity of the problem, e.g. large state-action spaces exhibited in strategic conversations. On the one hand, unique situations in the interaction can be described by a large number of variables (e.g. game board and resources available) so that enumerating them would result in very large state spaces. On the other hand, the action space can also be large due to the wide range of unique negotiations (e.g. givable and receivable resources). While one can aim for optimising the interaction via compression of the search space, it is usually not clear what features to incorporate in the state representation. This is a strong motivation for applying deep reinforcement learning for dialogue management, as first proposed by (anon citation), so that the agent can simultaneously learn its feature representation and policy. In this paper, we present an application of deep reinforcement learning to learning trading dialogue for the game of Settlers of Catan.

Our scenario for strategic conversation is the game of Settlers of Catan, where players take the role of settlers on the fictitious island of Catan—see Figure 1(left). The board game consists of 19 hexes randomly connected: 3 hills, 3 mountains, 4 forests, 4 pastures, 4 fields and 1 desert. In this island, hills produce clay, mountains produce ore, pastures produce sheep, fields produce wheat, forests produce wood, and the desert produces nothing. In our setting, four players attempt to settle on the island by building settlements and cities connected by roads. To build, players need specific resource cards, for example: a road requires clay and wood; a settlement requires clay, sheep, wheat and wood; a city requires three clay cards and two wheat cards; and a development card requires clay, sheep and wheat. Each player gets points for example by building a settlement (1 point) or a city (2 points), or by obtaining victory point cards (1 point each). A game consists of a sequence of turns, and each game turn starts with the roll of a die that can make the players obtain resources (depending on the number rolled and resources on the board). The player in turn can trade resources with the bank or through dialogue with other players, and can make use of available resources to build roads, settlements or cities. This game is highly strategic because players often face decisions about when to trade, what resources to request, and what resources to give away—which are influenced by what they need to build. A player can extend build-ups on locations connected to existing pieces, i.e. road, settlement or city, and all settlements and cities must be separated by at least 2 roads. The first player to win 10 victory points wins and all others lose.www.catan.com/service/game-rules

In this paper, we extend previous work on strategic conversation that has applied supervised or reinforcement learning in that we simultaneously learn the feature representation and dialogue policy by using Deep Reinforcement Learning (DRL). We compare our learnt policies against random, rule-based and supervised baselines, and show that the DRL-based agents perform significantly better than the baselines.

Background

To induce the $Q$ function above we use Deep Reinforcement Learning as in , which approximates $Q^{*}$ using a multilayer convolutional neural network. The $Q$ function of a DRL agent is parameterised as $Q(s,a;\theta_{i})$, where $\theta_{i}$ are the parameters (weights) of the neural net at iteration $i$. More specifically, training a DRL agent requires a dataset of experiences $D=\{e_{1},...e_{N}\}$ (also referred to as ‘experience replay memory’), where every experience is described as a tuple $e_{t}=(s_{t},a_{t},r_{t},s_{t+1})$. Inducing the $Q$ function consists in applying Q-learning updates over minibatches of experience $MB=\{(s,a,r,s^{\prime})\sim U(D)\}$ drawn uniformly at random from the full dataset $D$.

Policy Learning for Strategic Interaction

Our approach for strategic interaction optimises two tasks jointly: learning to offer and learning to reply to offers. In addition, our approach learns from constrained search spaces rather than unconstrained ones, resulting in quicker learning and also in learning from only legal (allowed) decisions.

A strategic agent has to offer a trade to its opponent agents (or players). In the case of the game of Settlers of Catan, an example trading offer is I will give anyone sheep for clay. Several things can be observed from this simple example. First, note that this offer may include multiple givable and receivable resources. Second, note that the offer is addressed to all opponents (as opposed to one opponent in particular, which could also be possible). Third, note that not all offers are allowed at a particular point in the game – they depend on the particular state of the game and resources available to the player for trading. The goal of the agent is to learn to make legal offers that will yield the largest pay-off in the long run.

A strategic agent also has to reply to trading offers made by an opponent. In the case of the game of Settlers of Catan, the responses can be narrowed down to (a) accepting the offer, (b) rejecting it, or (c) replying with a counteroffer (e.g. I want two sheep for one clay). Note that this set of responses is available at any point in the game once there is an offer made by any agent (or player). Similarly to the task above, the goal of the agent is to learn to choose a response that will yield the largest pay-off in the long run.

While one can aim for optimising only one of the tasks above, a joint optimisation of the these two tasks equips an automatic trading agent with more completeness. To do that, given an environment state space $S=\{s_{i}\}$, trading negotiations $A^{o}$, and responses $A^{r}$, the goal of a strategic learning agent consists of inducing an optimal policy so that action selection can be defined as $\pi^{*}(s)=\arg\max Q^{*}_{a\in\{A^{o}\cup A^{r}\}}(s,a)$, where the $Q$ function is estimated as described in the previous section, $A^{o}$ is the set of trading negotiations in turn, and $A^{r}$ is the set of responses.

2 Deep Learning from constrained action sets

While the behaviour of a strategic agent can be trained as described above, using deep learning with large action sets can be prohibitively expensive in terms of computation time. Our solution to this limitation consists in learning from constrained action sets rather than whole and static action sets. We distinguish two action sets, an action set $A^{r}$ which contains responses to trading negotiations and remains static, and an action set $A^{o}$ which contains those trading negotiations that are valid at any given point in the game (i.e. which the player is able to make due to the resources that they hold). We refer to the latter action set as $\bar{A}^{o}$, which contains a dynamic set $|\bar{A}^{o}|\leq|A^{o}|$ of trading negotiations available according to the game state and available resources (e.g. the agent would not offer a particular resource if it does not have it). Thus, we reformulate the goal of a strategic learning agent as inducing an optimal policy so that action selection can be defined as $\pi^{*}(s)=\arg\max Q^{*}_{a\in{\bar{A}^{o}\cup A^{r}}}(s,a)$, where the $Q$ function is still estimated as described in Section 2, $\bar{A}^{o}$ is the constrained set of trading negotiations in turn (i.e. legal offers), and $A^{r}$ is the set of responses. Note that the size of $\bar{A}^{o}$ will vary depending on the game state.

Experiments and Results

In this section we apply the approach above to conversational agents that learn to offer and to reply in the game of Settlers of Catan.

Figure 1(left) shows our integrated learning environment. On the left-hand side, the JSettlers benchmark framework receives an action (trading offer or response) and outputs the next game state and numerical reward. On the right-hand side, a Deep Reinforcement Learning (DRL) agent receives the state and reward, updates its policy during learning, and outputs an action following its learnt policy. Our integrated system is based on a multi-threaded implementation, where each player makes use of a synchronised thread. In addition, this system runs under a client-server architecture, where the learning agent acts as the ‘server’ and the game acts as the ‘client’. They communicate by exchanging messages, where the server tells the client the action to execute, and the client tells the server the game state and reward observed. Our DRL agents are based on the ConvNetJS tool , which implements the algorithm ‘Deep Q-Learning with experience replay’ proposed by . We extended this tool to support multi-threaded and client-server processing with constrained search spaces.The code of this substantial extension with an illustrative dialogue system is available at the following link: https://github.com/cuayahuitl/SimpleDS

1.2 Characterisation of the learning agent

The state space $S=\{s_{i}\}$ of our learning agent includes 160 non-binary features that describe the game board and the available resources. Table 1 describes the state variables that represent the input nodes, which we normalise to the range [0..1]. These features represent a high-dimensional state space—only approachable via reinforcement learning with function approximation.

The action space $A=\{a_{i}\}$ of our learning agents includes 70 actions for offering trading negotiationsTrading negotiation actions, where $C$=clay, $O$=ore, $S$=sheep, $W$=wheat, and $D=wood$: C4D, C4O, C4S, C4W, CC4D, CC4O, CC4S, CC4W, CD4O, CD4S, CD4W, CO4D, CO4S, CO4W, CS4D, CS4O, CS4W, CW4D, CW4O, CW4S, D4C, D4O, D4S, D4W, DD4C, DD4O, DD4S, DD4W, O4C, O4D, O4S, O4W, OD4C, OD4S, OD4W, OO4C, OO4D, OO4S, OO4W, OS4C, OS4D, OS4W, OW4C, OW4D, OW4S, S4C, S4D, S4O, S4W, SD4C, SD4O, SD4W, SS4C, SS4D, SS4O, SS4W, SW4C, SW4D, SW4O, W4C, W4D, W4O, W4S, WD4C, WD4O, WD4S, WW4C, WW4D, WW4O, WW4S. Example trade: C4D=clay for wood. and 3 actionsReply actions: accept, reject and counteroffer for replying to offers from opponents. Notice that our offer actions only make use of up to two givable resources and only one receivable resource is considered.

The state transition function of our agents is based on the game itself using the JSettlers framework . In addition, our strategic interactions were carried out at the semantic level rather than at the word level, for example: S4C is a higher-level representation of “I will give you sheep for clay”. Furthermore, our trained agents were active only during the selection of trading offers and reply to offers, the functionality of the rest of the game was based on the JSettlers framework.

The reward function of our agent is based on the game points provided by the JSettlers framework, but we make a distinction between reply actions and offer actions. This is due to the fact that we consider reply actions as high-level actions, and offer actions as lower-level ones. Our reward function is defined as:

where $GainedPoints$=points at time $t$ minus the points at time $t-1$, and $TotalPoints$ refers to the accumulated number of points of the trained agent during the game. We used the following weights for reply actions: $\{w_{gp}=1,w_{tp}=0.1\}$, and the following for offer actions: $\{w_{gp}=0.1,w_{tp}=0.01\}$.

The model architecture consists of a fully-connected multilayer neural network with 160 nodes in the input layer (see Table 1), 50 nodes in the first hidden layer, 50 nodes in the second hidden layer, and 73 nodes (action set) in the output layer. The hidden layers use RELU (Rectified Linear Units) activation functions to normalise their weights, see for details. Finally, the learning parameters are as follows: experience replay size=30K, discount factor=0.7, minimum epsilon=0.05, learning rate=0.001, and batch size=64. A comprehensive analysis comparing multiple state representations, action sets, reward functions and learning parameters is left for future work.

2 Experimental Results

We use the following baselines to compare our trained strategic agents, where we only switch the trading offers and reply behaviours—the remaining behaviour of the game remains constant and is provided by the JSettlers framework:

Ran: This agent chooses trading negotiation offers randomly, and replies to offers from opponents also in a random fashion. Although this is a weak baseline, we use it to analyse the impact of policies trained (and tested) against random behaviour.

Heu: This agent chooses trading negotiation offers and replies to offers from opponents as dictated by the heuristic bots included in the JSettlers frameworkThe baseline trading agent referred to as ‘heuristic’ included the following parameters, see : TRY_N_BEST_BUILD_PLANS:0, FAVOUR_DEV_CARDS:-5., see for details.

Sup: This agent chooses trading negotiation offers using a random forest classifier , and replies to offers from opponents using the heuristic behaviour above. This agent was trained from 32 games played between 56 different human players—labelled by multiple annotators. We compute the probability distribution of a human-like trade as $P(givable|evidence)=\frac{1}{Z}\prod_{b\in B}P_{b}(givable|evidence)$, where $givable$ refers to the class prediction (in our case, the givable resource), $evidence$ refers to observed featuresEvidence: Number of resources available, number of builds (roads, settlements and cities), and the resource received., $P_{b}(.|.)$ is the posterior distribution of the $b$th tree, and $Z$ is a normalisation constant . This classifier used 100 decision trees. Assuming that $Y$ is a set of givables at a particular point in time in the game, extracting the most human-like trading offer (givable $y^{*}$) given collected evidence (context of the game), is defined as $y^{*}=\arg\max_{y\in Y}Pr(y|evidence)$. The classification accuracy of this statistical classifier was 65.7%—according to a 10-fold cross-validation evaluation .

We trained three DRL agents against random, heuristic and supervised opponents—see Figure 2, which used 500K training experiences (around 2000 games each learning curve). We evaluate the learnt policies according to a cross-evaluation using the following metrics in terms of averages per game (using 10 thousand test games per comparison): win-rate, victory points, (successful) offers, total trades, pieces built, cards bought, and number of turns. Our observations of the cross-evaluation, reported in Table 2, are as follows:

The DRL agents acquire very competitive strategic behaviour in comparison to the other types of agents—they simply win substantially more than their opponents. While random behaviour is easy to beat with over 98% win-rate, the DRL agents achieve over 50% of win-rate against heuristic opponents and over 40% against supervised opponents. These results substantially outperform the heuristic and supervised agents which achieve less than 30% of win-rate (at $p<0.05$ according to a two-tailed Wilcoxon-Signed Rank Test).

The DRL agents outperform the baselines not just in win-rates but also in other metrics such as average victory points, pieces built and total trades. The latter is more prominent, for example, while the heuristic and supervised agents achieve between 270 to 280 trades per game, the DRL agents compared against heuristic and supervised agents achieve between 340 and 360 trades. This means that the DRL agents tend to trade more than their opponents, i.e. they accept more offered trading negotiations. These differences suggest that knowing when to accept, reject or counter offer a trading negotiation is crucial for winning.

Training a DRL agent in the environment where it will be tested is better than training and testing across environments. For example, DRLheu versus heuristic behaviour is better (53.4% win-rate) than DRLsup versus heuristic behaviour (50.3% win-rate). However, our results report that DRL agents trained using randomly behaving opponents are almost as good as those trained with stronger opponents. This suggests that DRL agents for strategic interaction can be also be trained without highly skilled opponents, presumably by tracking their rewards over time.

The DRL agents find the supervised agent harder to beat. This is because the supervised agent is the strongest baseline, which achieves the best winning rate of the baseline agents. It can be noted that the DRL agents versus supervised behaviour make more offers and trade more than the DRL agents versus heuristic behaviour. We can infer from this result that knowing when to offer and when to trade seem crucial for better winning rates.

The fact that the agent with random behaviour hardly wins any games, suggests that sequential decision-making in this strategic game is far from trivial.

In summary, strategic dialogue agents trained with deep reinforcement learning have the potential to acquire highly competitive behaviour, not just from training against strong opponents but even from opponents with random behaviour. This result may help to reduce the resources (heuristics or labelled data) required for training future strategic agents.

Related Work

Reinforcement learning applied to strategic interaction includes the following. proposes reinforcement learning with multilayer neural networks for training an agent to play the game of Backgammon. He finds that agents trained with such an approach are able to match and even beat human performance. proposes hierarchical reinforcement learning for automatic decision making on object-placing and trading actions in the game of Settlers of Catan. He incorporates built-in knowledge for learning the behaviours of the game quicker, and finds that the combination of learned and built-in knowledge is able to beat human players. used reinforcement learning in non-cooperative dialogue, and focus on a small 2-player trading problem with 3 resource types, but without using any real human dialogue data. This work showed that explicit manipulation moves (e.g. “I really need sheep”) can be used to win when playing against adversaries who are gullible (i.e. they believe such statements) but also against adversaries who can detect manipulation and can punish the player for being manipulative . More recently, designed an MDP model for selecting trade offers, trained and evaluated within the full jSettlers environment (4 players, 5 resource types). In comparison to the DRL model, it had a much more restricted state-action space, leading to significant, but more modest improvements over supervised learning and hand-coded baselines.

Other related work has been carried out in the context of automated non-cooperative dialogue systems, where an agent may act to satisfy its own goals rather than those of other participants . The game-theoretic underpinnings of non-cooperative behaviour have also been investigated . Such automated agents are of interest when trying to persuade, argue, or debate, or in the area of believable characters in video games and educational simulations . Another arena in which strategic conversational behaviour has been investigated is negotiation , where hiding information (and even outright lying) can be advantageous.

Recent work on deep learning applied to games include the following. train a deep convolutional network for the game of Go, but it is trained in a supervised fashion rather than trained to maximise a long-term reward as in this work. A closely related work to ours is a DRL agent for text-based games . Their states are based on words, their policies are induced using game-based rewards, and their actions are based on directions such as ‘go east/west/south/north’. Another closely related work to ours is DRL agents trained to play ATARI games . Their states are based on pixels from down-sampled images, their policies make use of game-based rewards, and their actions are based on joystick movements. In contrast to these previous works which are based on navigation commands, our agents are use trading dialogue moves (e.g. ‘I will give you ore and sheep for clay’, or ‘I accept/decline your offer’), which are essential behaviours for strategic interaction.

This paper extends the recent work above on training strategic agents using reinforcement learning, which have either used small state-action spaces or focused on navigation commands rather than negotiation dialogue. The learning agents described in this paper use a high dimensional state representation (160 non-binary features) and a fairly large action space (73 actions) for learning strategic non-cooperative dialogue behaviour. To our knowledge, our results report the highest winning rates reported to date in the game of Settlers of Catan, see . The comprehensive evaluation reported in the previous section is evidence to argue that deep reinforcement learning is a promising framework for training strategic interactive agents.

Concluding Remarks

The contribution of this paper is the first application of Deep Reinforcement Learning (DRL) to optimising the behaviour of strategic conversational agents. Our learning agents are able to: (i) discover what trading negotiations to offer, (ii) discover when to accept, reject, or counteroffer; (iii) discover strategic behaviours based on constrained action sets—i.e. action selection from legal actions rather than from all of them; and (iv) learn highly competitive behaviour against different types of opponents. All of this is supported by a comprehensive evaluation of three DRL agents trained against three baselines (random, heuristic and supervised), which are analysed from a cross-evaluation perspective. Our experimental results report that all DRL agents substantially outperform all the baseline agents. Our results are evidence to argue that DRL is a promising framework for training the behaviour of complex strategic interactive agents.

Future work can for example carry out similar evaluations as above in other strategic environments, and can also extend the abilities of the agents with other strategic features and forms of learning . In addition, a comparison of different model architectures, training parameters and reward functions can be explored in future work. Last but not least, given that our learning agents trade at the semantic level, they can be extended with language understanding/generation abilities to communicate verbally .

Acknowledgments

Funding from the European Research Council (ERC) project “STAC: Strategic Conversation” no. 269427 is gratefully acknowledged, see http://www.irit.fr/STAC/. Funding from the ESPRC, project EP/M01553X/1 “BABBLE” is gratefully acknowledged, see https://sites.google.com/site/hwinteractionlab/babble.

References