Dialogue Policies for Learning Board Games through Multimodal Communication (2020)

Abstract: This paper presents MDP policy learning for agents to learn strategic behavior–how to play board games–during multimodal dialogues. Policies are trained offline in simulation, with dialogues carried out in a formal language. The agent has a temporary belief state for the dialogue, and a persistent knowledge store represented as an extensive-form game tree. How well the agent learns a new game from a dialogue with a simulated partner is evaluated by how well it plays the game, given its dialogue-final knowledge state. During policy training, we control for the simulated dialogue partner’s level of informativeness in responding to questions. The agent learns best when its trained policy matches the current dialogue partner’s informativeness. We also present a novel data collection for training natural language modules. Human subjects who engaged in dialogues with a baseline system rated the system’s language skills as above average. Further, results confirm that human dialogue partners also vary in their informativeness.

## introduction agents that can learn by communicating with human have many potential benefits for human-agent interaction in real world situations, including making it easier for ordinary people to integrate agents into their daily activities. agents that can communicate to learn games could help us understand how to design agents that can communicate to learn how to make strategic decisions, meaning to pursue a goal when the state of the world changes. games are a useful testbed, given our reliance on extensive-form game trees, which supports generalization across games. games model a space of interactions from very simple two-player settings (e.g., tic-tac-toe) to highly complex multi-party interactions (e.g., bridge). our agent learns markov decision process (mdp) dialogue policies to learn in-a-row board games by asking questions of diathe original dialogues were between an agent learning quarto and a simulated dialogue partner, using a meaning representation language (mrl). for 960 dialogues, experts translated each mrl into english. (best viewed in color.) logue partners, with policy differences that derive from differences in game complexity, and differences in dialogue partners. our mdp policies are trained offline through simulation. agent dialogues are carried out in a general meaning representation language (mrl) we developed for communicating about games. the agent can request a visual demonstration, or can formulate context-specific verbal questions, including "yes/no" questions, as illustrated in figure 1 , and open-ended "wh-" questions. because different humans can have different knowledge, or different dispositions for how much information to give when answering questions, we investigated the impact of policy learning that is sensitive to the informativeness of the dialogue partner. we show that an agent acquires better game knowledge from dialogues when its trained policy matches the dialogue partner. we also add elementary natural language capability, and show that human dialogue partners vary in their informativeness. learning through communication @xcite is related to learning from demonstration (lfd) @xcite , where the goal is for agents to learn through immediate and direct experience rather than through offline processing of large datasets. previous work on learning through communication has focused on joint grounding of perception and language in task learning @xcite , complex concept grounding @xcite , or collaborative action @xcite , rather than dialogue management. our work investigates reinforcement learning of dialogue policies, which makes it easy to produce and compare many policies. we exploit the ability to control the behavior of simulated dialogue partners to investigate policy training when dialogue partners vary in informativeness. we develop a policy with hierarchical structure based on a global policy for context-switching, and a local policy for formulating specific questions given a context. we present two kinds of experiments. first, we compare the mdp policies for different games and different levels of informativeness of simulated dialogue partners. results show how policies differ across games, and for different dialogue partners. for example, the agent asks more "wh-" questions when the dialogue partner is more forthcoming, and more "yes/no" questions when the dialogue partner is withholding. second, we conduct an experiment with human dialogue partners to show that the agent can have successful dialogues with people, and that people vary in informativeness. to add natural language capability, we developed a novel data collection method and used it to collect a dataset of 960 dialogues (12,885 turn exchanges) for quarto, one of three in-a-row games that our agent can learn. @xmath0, @xmath1. the mrl has communicative action types that are functions from contexts to specific questions about that context. thus the mrl combines utterance meaning with action type (similar to dialogue act type). figure 1 illustrates one turn exchange in a graphical user interface developed for the data collection. trained annotators presented with dialogues in mrl translated the mrl to colloquial english. we present initial results where we trained baseline natural language understanding and generation modules from this dataset to show that the agent can learn games in dialogues with people. no other work we know of addresses the general problem of agents learning through communication with respect to strategic knowledge, meaning knowledge about how to act when the state of the world can change through other agents' actions or natural events. our first main contribution is development of mdp dialogue policies for learning games through communication, based on our characterization of the learning goal in relative rather than absolute terms: to learn more and better about how to play a game. specifically, policy training addresses the tradeoff between quality of knowledge acquired from the dialogue partner and length of the dialogue, so that the agent learns how to formulate advantageous questions. our second main contribution is experimental evidence of the benefits of dialogue policies that are customized to the informativeness of the dialogue partner. sensitivity to the informativeness of the dialogue partner is particularly important when the role of the dialogue partner is to provide knowledge, given that different dialogue partners can have different levels of expertise, and different communication skills. ## related work recent work on deep reinforcement learning has made great progress in developing systems capable of learning atari games and other games such as chess, poker, and even go @xcite @xcite . although the agent does learn how to play the game with considerable accuracy, the process requires large amounts of data, time, and accurate perception. in contrast to this prior work, we seek an approach where an agent learns as much as it can by engaging in short, situated dialogues with human partners. most previous work that addresses agent learning through interaction with people, including games, involves agents learning by observing the world (learning from demonstration, or lfd). there can be some verbal input, but without significant knowledge of language or communication strategies. virtual agents have learned games like connect four and tic-tac-toe from demonstration videos, mapping observations to a fragment of first-order logic @xcite , or from sketches combined with natural language @xcite . the soar cognitive architecture has been applied to learning tic-tac-toe and tower of hanoi @xcite . in lfd, agents can also learn actions, such as how to hit a ping pong ball @xcite or open a drawer @xcite . active learning has been used for agents to ask clarification questions of a human who gives a fetching request @xcite , to use pre-defined queries while learning task sequences @xcite , or to pose a specific question to learn a particular skill @xcite . previous work on learning through communication has addressed concept grounding or task learning, rather than learning how to act when the state changes due to other agents' actions. in (matuszek, 2018), machine-learned classifiers ground words and phrases provided by a human in an agent's perception of the world. language can also be grounded more directly in perception, by machine learning the relevant perceptual categories from data, rather than pre-specifying them in a formal semantics @xcite . in @xcite , an agent learns cloth folding through rich verbal communication, based on and-or graphs. it can understand utterances with context dependencies common to human language but challenging for machines (e.g., descriptions of objects that evolve over several utterances). language interaction via semantic parsing combined with deep reasoning is used in agents that explain their actions @xcite , using existing nlp tools for parsing into a logical form (steedman and baldridge, 2011), and a rule-based, broadcoverage toolkit for generating english from structured input @xcite . other work that relies on rich, situated reasoning through multimodal communication is based on an architecture for collaborative problem-solving @xcite , with plan-based dialogue management @xcite . these works either do not have distinct dialogue management modules, or rely on manually-engineered dialogue management rather than machine-learning. our work presents machine-learned mdp policies using a method that generalizes across different games, and across differences in dialogue partners' informativeness. ## game-learning dialogues: overview three games our agent learns through communication, in order of complexity, are connect four, gobblet, and quarto. in all three, players take turns placing pieces on a grid game board. the first player with four pieces in a row wins. there are different sets of possible actions per game due to different board sizes, numbers of game pieces, and properties that distinguish game pieces. this paper focuses mostly on quarto. quarto has a 4×4 board and 16 game pieces, distinguished into two colors, two heights, two shapes, and whether they are solid or hollow. at each turn n of the game, there are (4 2 -n) × (4 2 -n) possible moves. in each turn, the opponent identifies a piece for the current player to place on the board. four in a row wins if there is a property shared by all four pieces. to engage in a game-learning dialogue, a markov decision process (mdp) policy π chooses the agent's dialogue actions, meaning an action a t at time t depends on the current state s t , which is fully observable. reinforcement learning finds an optimal policy π to choose communicative actions that will maximize the expected total reward over time, r @xmath2. here we give a brief sketch of the hierarchical policy π, dialogue actions a t , states s t , and reward r t . the multi-modal dialogues are structured as sequences of sub-dialogues, where each sub-dialogue starts with a visual demonstration of a game board showing a new way to win. the use of demonstrations of win conditions is based on observations from our previous work of how people start asking questions to learn a new game @xcite . as indicated below, each win condition corresponds to a path to a win state in an extensiveform game tree, where the opponent's game actions are left unspecified. a global policy π g chooses whether to continue the current subdialogue context, or initiate a new one, while a local policy π l generates questions to prompt for additional win conditions based on the current demonstration, or additional information about what makes it a win. for example, the agent can ask whether the current configuration of pieces counts as a win due to the color of the pieces (see figure 1 ). the use of game trees for knowledge representation is presented in section 4. we developed a meaning representation language (mrl) to represent specific communica-tive actions a t that are grounded in the actions and action properties of game trees (see section 5). game trees are a well-studied abstraction for representing game knowledge, and for executing play based on tree search. game trees represent game states as nodes, actions as edges, with payoffs at relevant nodes @xcite . each visual demonstration of a win condition presented to the agent updates the agent's belief state s t , as described in section 6. the belief state is also updated after a simulated or human dialogue partner (dp) responds to a question. in turn, the belief state is used to update the agent's knowledge, represented as a game tree. for example, each visual demonstration of a win condition is interpreted as a path in a game tree from the game start to a finish in which the agent wins, and where the other player's actions are unspecified. the agent receives a greater reward r t when the questions it asks lead to more and better game knowledge, and receives a small penalty on each next turn to encourage efficiency. dialogues vary in length, depending on the game and the informativeness of the dp, but most dialogues are around a dozen turn exchanges. the reward function and policy training are presented in section 7. an excerpt of a quarto dialogue from our data collection appears in appendix a. ## game trees as knowledge game theory has been used to represent, reason about, and implement games (goeree and holt, 1999; @xcite . our innovation is to use the game tree abstraction as a vehicle for 1) storing the agent's persistent knowledge about a game, 2) reasoning about that knowledge for dialogue, and 3) providing a measurement of the quality of the game knowledge that the agent acquires in the dialogue. we developed a game knowledge reasoner (gkr) shown in figure 2 as an interface between the agent's belief state during a dialogue, and its long-term knowledge store. the gkr assesses the strategic value of new win conditions that a dp has confirmed, and draws inferences about new ways to win that are added to the agent's belief state as unconfirmed beliefs, as discussed further below. after a dialogue, the agent's final game tree, can be used to engage in play. in an extensive form game tree, each next depth in the tree represents action choices of alternate players. the well-known minimax algorithm (osborne and ru-binstein, 1994) computes a player's optimal action from a given node at depth d i , on the assumption that at depth d i+1 the opponent always chooses its best action. the challenge of learning a new extensive form game is thereby reduced to learning enough of a game tree to engage in play. the quality of what the agent learned is reflected in how often it can win. at the start of a dialogue, an empty extensive form game tree is initialized, and incrementally extended based on answers to the agent's questions. game-specific constraints specify how the game tree can grow, e.g. how many actions are available at each node. we use mapping functions from abstract actions in a game tree to physical actions, based on pre-defined information about the gameboard and pieces. the gkr computes a strategic value for a new win condition at a given dialog state as a function of the number of overlapping actions with existing win paths in the tree. given a game tree with n win paths at a given depth in the game tree, sibling nodes represent the actions available to the corresponding player. in an incomplete game tree, some of these siblings are part of a set of win paths and some of them are not. if some of the actions at a given depth lead to win conditions, the agent infers that siblings of these actions might lead to similar win conditions. the gkr thus infers unseen board configurations based on the current game tree, and passes them to the dialogue manager as hypothesized win conditions. formally, given a known win path w @xmath3, a i2 , ..., a im } and a sibling list of an action a il of the win condition w i (sibling(a il ) = {a 1 , a 2 , ..., a k }) the gkr infers a maximum of k new win branches, for k remaining actions in the game, based on a sibling distance metric siblingdistance(a il , a j ) = d , @xmath4, ..., k}: for connect four and gobblet we use a depth two game tree to make inferences about possible win conditions. for quarto, we don't set a depth limit. we also use the board positions of inferred win condition w j to find any known win condition w i at the same board positions, so as to infer that any feature f shared by all actions in w j is the game piece feature that contributes to this win condition. the gkr returns this information to the dialog manager. in sum, if the agent sees a new win condition in a row where it has previously seen a win condition, and the color is what distinguishes this new win, it infers that the color is a win feature. ## meaning representation the communicative action generator takes as input the current context and the communicative action type selected by the dialogue policy, and generates a specific communicative action for the agent in an mrl we describe here. the meaning representation language is described in detail in our previous work @xcite . here we explain the communicative action types of the agent and dialogue partner. the action types at the top of ## belief state the global belief space is a set of belief vectors b that represent beliefs acquired during a dialogue (see figure 2 ). each new demonstration d i instantiates a new local belief vector b i to represent confirmed information observed in d i or acquired from responses to questions about d i . inferences the gkr makes about possible win conditions are also represented. a game board is represented as a vector representing each board position (e.g., 0 to 15 for quarto), with a belief value in [0,1] for each vector position. confirmed beliefs (b c ) and inferred beliefs (b i ) about ways to reconfigure a win condition are similar vectors with an additional position none. formally, the game belief vector b is defined as concatenated vectors that each pertain to an observed property of game pieces (e.g., color) or a type of physical rearrangement of a configuration of pieces (e.g., rotate): figure 1 illustrates a board demonstration d 3 for quarto with a vertical sequence of four game pieces starting in position 2. the board d 3 is the implicit argument in the question. b i is updated at the end of each turn with inferences derived by the gkr. for updating b c , we rely on the baseline belief tracking method proposed in @xcite . given a response to a particular question, the component belief vector vect t gets updated if the turn exchange is a question and answer about a function (e.g. translate) or a property (e.g. game piece shape). when the response from the dp is positive or contains new information, the corresponding belief vectors get updated according to equation ( 4 ). when the dp response is negative, the relevant sub-belief vectors are updated according to equation ( 5 ). currently, the confidence score p ut over the dp utterance is always 1.0, because there is no uncertainty in the interpretation of the mrl. (in future work, we plan to train partially observable mdp policies to accommodate the uncertainty in natural language interactions with humans.) ## policy learning and reward through simulation, we can control the informativeness of the dp's responses, and thus investigate the impact of informativeness on policy learning. we train multiple policies, setting the dp informativeness to a value between 0 and 1. a 100% informative dp responds to all questions completely. for lower informativeness, we keep a list of all the possible winning conditions sorted by the number of times they have been presented by the dp in ascending order. when the agent asks a newwinc() question, a dp with x% informativeness randomly chooses a win condition from the top (100-x)% of the sorted list. a x% informative dp responds with unknown() to confirm() queries with 100 -x% probability, and provides only x% of a complete answer to request() queries. gašić and young (2014) achieved good results with less training for a gaussian process approach to policy learning. the model has few hyperparameters and converges quickly to a local optimum (< 20k epochs). we adopted their model and trained dialogue polices for 10k epochs. the policy gets updated at the end of each interaction. the reward is designed to encourage the agent to acquire as many new win condition paths as possible, to prefer paths with higher strategic value, and to end the dialogue when the turn costs outweigh the gains in knowledge. equation 6 shows the reward r for a turn exchange t as a function of the number of new win conditions in the dp's response to a question, the strategic value sv of the response, and a turn cost c (through tuning, we found good performance from α = 0.2, β = 3, and @xmath5.): @xmath6. our first question is how dialogue policy learning differs across levels of dp informativeness. figure 3 shows a sensitivity analysis of the training process over 10k epochs, using change in total reward, for six informativeness levels ranging from 100% to 20%. the informativeness conditions clearly differ, with lower reward for lower informativeness. we achieved similar results for connect four and gobblet with much faster convergence for connect four, the simplest game. using the fully trained policies from figure 3 , we ask how communicative actions differ during learning dialogues. in each informativeness level, the agent engages in 100 dialogues. we next ask how the policy affects what is learned in a given dialogue from a given dp type, and what happens if the agent's learned policy for a dp level x is used when interacting with a dp of level y . we next ask how well can the agent play after a learning dialogue. for connect four and gobblet, we recruited 16 students to play with the agent, using the same conditions and knowledge states from our final question was whether the agent could use the same policy to continue learning over a sequence of dialogues. here we looked at three conditions: where the learned policy matched the dp informativeness of 100%, 50% and 20%. in each condition, the agent had four dialogues, starting with no knowledge. the agent began each next dialogue with the knowledge it had gained from its previous dialogue. we averaged the final reward at the end of each dialogue. results show that the agent continues to learn more and more about the game, especially from the 100% informative dp. results for gobblet were very similar to quarto. however for connect four, there is usually little reward (knowledge) left to gain after the first or second dialogue in higher informativeness levels, so the reward plateaus after two or three dialogues. ## dialogue data collection to add natural language capability for the agent, we developed a novel data collection method to produce a corpus consisting @xmath7,mrl,@xmath8. the quarto dialogue corpus is distinctive in that it is agent-agent situated, multi-modal dialogue where agents' utterances are in an mrl, then all dialogues translated by experts into english. to our knowledge, this is the first corpus of its kind. most previous dialogue corpora we know of fall into one of three other categories: human-wizard-of-oz, human-agent, or human-human. corpora for human-wizard-of-oz are used either to inform manually engineered dialogue management or as training data for machine learned dialogue managers. these corpora are collected for the purpose of restaurant reservation @xcite , finding available vacation accommodations @xcite , or even open-domain information retrieval systems @xcite . humanagent corpora are often annotated with dialogue acts for applications such as travel booking systems @xcite . human-human corpora are either collected under constrained settings where humans are instructed to follow a series of instructions @xcite , or are naturally occurring conversations between humans @xcite @xcite . distinctive characteristics of the quarto corpus are that every utterance has an mrl and a natural language version where the mrl is a communicative act. the dialogues involve a shared multi-modal context, leading to deictic reference to the game board and with a known structure into sub-dialogues. to collect our corpus, we developed two graphical user interfaces (guis) to display a schematic representation of the current board demontration (cf. figure 1 ), and to allow annotators to page through each turn exchange. one gui was for the translation task, and a second was to collect ratings on the translations. thirteen undergraduate students from a course in artificial intelligence participated as part of their course work. students were first trained in the mrl, including comparisons with the first order logic translations of english that students had learned in class. their instructions were to translate into colloquial english. meetings were held where students discussed examples and asked questions. all translations were rated for correctness and naturalness on a five-point scale where 5 was the top. on average, correctness was 4.79 and naturalness was 4.72. the 960 dialogues contain 12,885 turn exchanges. the english translations contain 229,641 word tokens, and 1,498 word types. the nlg data has 146,055 tokens and 1,102 types. the nlu data is somewhat less rich, with 83,586 tokens and 952 types. the 960 dialogues consist of 535 from a 60% informative simulator, 255 from a 100% informative simulator, and 170 from a 50% simulator. we are currently augmenting the data to synthesize new examples for quarto, and to synthesize connect four and gobblet data. because all turn exchanges are tied to a physical board, the corpus is rich in spatial references. the students referred to the pieces by specific attributes (e.g. next to that green circular piece), exact location on the board (e.g. top corner piece), relation with other pieces (e.g. to the right of the square piece), or deictic reference (e.g. this piece here). there are also many anaphoric references (e.g. about that win you showed, the second win). ## human-agent dialogues the dataset described above provides training data for nlu and nlg modules to enable the agent to engage in dialogue with humans. two other changes needed to support future human-agent dialogues are clarification sub-dialogues to handle misunderstandings or confusions, and modification of the policy training and belief updates to address uncertainty in the nlu. to preview our future challenges, we developed baseline nlu and nlg modules, and asked the 18 subjects who played quarto with our agent to engage in text-based dialogues. here we describe the dialogue interface, the baseline nlu and nlg modules, the dialogue outcomes, and the subjects' informativeness. we developed a text-based gui for subjects to engage in dialogues with an agent, similar to the gui used for translating mrl into english. for nlg and nlu, we trained two sequence-tosequence rnn models with two hidden layers and a bahdanau attention layer @xcite . the adam optimizer was used for training (kingma and ba, 2014) (20 epochs for nlg, and 15 for nlu). the mdp policy for 100% informativeness was used, and belief updating remained the same. the comparison of baseline human-agent learning dialogues with those between an agent and simulated dp shows promise for reinforcement learning of policies that are trained offline in simulation. subjects provided less than 100% informative answers, and the agent's final knowledge states were similar to those where the agent interacted with a 50% informative simulator, using a matching policy. even without the ability to engage in clarification sub-dialogues with a human to clear up confusions, the dialogues were all completed. the agent was completely understandable two thirds of the time. the agent learned as much about quarto as in the 50%-50% simulator condition. a question raised by these results is how an agent could benefit from having access to multiple dialogue policies. in robotics, a very similar question has been addressed for agents learning motor skills through simulation and deploying the learned policies in real-world environments with unknown dynamics. approaches include learning to linearly combine a family of policies @xcite , learning a classifier for environment parameters to choose the correct policy @xcite , or searching directly within a family of policies using the current accumulated reward @xcite . similar methods could be applied to exploit a family of dialogue policies to adapt questioning strategies in different ways, depending on the observed behavior of the dialogue partner. ## conclusion our results show that agents can learn mdp policies to learn board games through multi-modal dialogues using a relative knowledge goal, namely to increase the agent's game knowledge as much as possible during a short dialogue. we also show that the agent learns different dialogue policies depending on the dialogue partner's informativeness. this work exploits the benefits of a knowledge domain that has a very abstract representation in the form of game trees, where a novel meaning representation language is grounded in the game tree abstraction. this approach can generalize to a wide range of two-person board games, and provides a foundation for communication learning about other strategic activities. in addition, an agent that can learn new games and then engage in play has potential benefits in socially assistive robotics @xcite . board games have been used to delay the onset of dementia @xcite , and have been shown to help children learn computational concepts @xcite . additionally, we have demonstrated that mdp policies trained offline in simulation can lead to fairly effective human-robot learning dialogues, based on training data for natural language modules we collected through a novel procedure. our future work will expand the communicative actions to include clarifications, will train pomdp policies, and will borrow ideas from reinforcement learning of robotic motor skills to close the reality gap between offline training of dialogue policies and engaging in real-world dialogues with humans.