A POMDP Dialogue Policy with 3-way Grounding and Adaptive S ensing for Learning through Communication (2022)

Abstract: Agents to assist with rescue, surgery, and similar activities could collaborate better with humans if they could learn new strategic behaviors through communication. We introduce a novel POMDP dialogue policy for learning from people. The policy has 3-way grounding of language in the shared physical context, the dialogue context, and persistent knowledge. It can learn distinct but related games, and can continue learning across dialogues for complex games. A novel sensing component supports adaptation to information-sharing differences across people. The single policy performs better than oracle policies customized to specific games and information behavior.

## introduction agents that drive cars, assist in surgery, or support elder care could more easily collaborate with us if they could ask us questions to learn to operate a new type of vehicle, perform a related type of surgery, or help with a different daily life activity @xcite . we present a novel pomdp policy with the following distinctive communicative abilities. it can apply general communicative skills to similar but different learning goals, pursue more complex learning objectives across multiple dialogues, and adapt to human variation in information sharing. to motivate the latter, we also show that human subjects vary in the information they share, with corresponding differences in the optimal questioning strategy. we build on previous work in statistical pomdp policies for dialogue management in several ways @xcite . as in most such systems, natural language utterances are mapped to a domain-dependent semantic representation. similarly, we train offline using a simulator instead of a human dialogue partner, common since @xcite , and we update pepper: where else can i put these pieces and still come out with a win? -informative answer: you can lay those pieces in any of the three remaining empty rows and still win. the following section is an extended example that illustrates 1) through 4). here we illustrate 5) and give full explanation in section 4. grice proposed that co-operative conversationalists are as informative as possible @xcite . we find, however, that people vary in informativeness, and the 3ga policy adapts its questioning strategy accordingly. figure 1 illustrates different answers to the same question from the 3ga policy, given a demonstrated way to win the board game quarto. 1 the first answer is highly informative while the second is less so. the policy generates more open-ended questions, more yes-no questions, or more requests for board demonstrations, in proportion to the informativeness of respondents. we train the pomdp on three n-in-a-row games, and assess performance by how much game knowledge the agent acquires. first, we measure knowledge acquisition in dialogues with a simulator, where we control for information quantity in the simulator's answers to questions. 3ga performs better than oracle policies trained for each specific condition of game and information quantity, and generalizes to unseen games. second, an exploratory study confirms that people vary in informativeness, and shows that 3ga continues to learn a complex game in a succession of dialogues. ## example dialogue games are a common test bed for agents that learn through communication @xcite @xcite . as in @xcite ; @xcite , we adopt a formal meaning representation (mr) to express the agent's communicative intentions, and its interpretations of utterances. further, we use extensive-form game trees to represent the agent's game knowledge, cf. @xcite . in a game tree, nodes are game states, and edges at a given level of the tree are the actions available to the player (odd levels) or the opponent (even levels). leaves represent terminal states of a win, loss or draw for the player. game search algorithms can then be applied to the declarative knowledge in the agent's game tree, for the agent to choose moves while playing the game (cf. @xcite ). to support the ability to learn different games, we create a generic representation for two-person zero-sum games. some of the questions 3ga generates aim to specialize this generic knowledge for a specific game like quarto. in contrast to previous work on learning through communication, we use a statistical pomdp for dialogue management. the trained policy chooses what question to ask in each dialogue state, and context-specific questions are generated on the fly. figure 2 illustrates how responses to the agent's questions are added to an evolving game tree. 1 an n-in-a-row game, it is played on a 4 × 4 grid with pieces differentiated by height, shape, color and hollowness. q1 nl can you show me a way of starting the game? mr req_move_dem() a1 dem mr inform(turn(@xmath0,put(@xmath1, @xmath2,3))) ∧ turn(@xmath3, put(@xmath4, @xmath5,3)))) q2 nl here, where else can i put this piece? mr continue(d 0 ), req(location()) a2 nl any of the columns to the left. mr inform(@xmath6,1,2})) ⇒ agent learns red can go in {(0,0), . . . , (0,3)} q3 nl what's another example of turn taking? mr req_move_dem() a3 img mr inform(turn(@xmath7,5) turn(@xmath8,4))) q4 nl can you show me a way to win? mr req_win_dem() a4 img mr inform(@xmath9, where else can i put the pieces and still win? mr continue(d 3 ), req(translate()) a6 nl they can go in any column on the board. mr inform(@xmath10, to abstract game knowledge, and to the discourse context itself, figure 2 shows part of a dialogue to learn connect four. 2 text-based, multi-modal dialogues take place in a graphical user interface. natural language questions and responses are shown here with corresponding meaning representations (mrs). utterances are grounded in the physical world of game boards, pieces and moves via elements of the mr, as in put(@xmath11,@xmath12,3)) from a1. they are also grounded by initializing a new game tree at the beginning of a dialogue, as in the tree labeled after a1, or by adding to it. finally, each utterance is in reference to a specific game board demonstration, or local context. in q1, the agent asks how the game starts, and the response is a visual demonstration. the game tree labeled after a1 shows a root node representing an empty board state, an edge (move) to a successor game state where the player (red) has put a piece in column 3 (numbering starts in 0), and a subsequent edge to a state where the opponent (blue) added another piece to column 3. as the dialogue progresses, the agent grounds new ways to make moves or to win. if it has sufficient grounding (knowledge about moves), the agent adds paths to the tree that terminate in wins. in q4, the agent asks for a way to win, and is shown a board with four discs in the last column. because the individual moves have not been grounded as game knowledge, the agent's belief state (not shown) is updated, but not its game tree knowledge. in contrast, after a different win demonstration in a5, the agent can add a complete path to a win state (green box in tree), because in a1-a2 each move in that path was grounded. at the dialogue's end, the size of the game tree is a measure of the knowledge gained. ## learning and remembering games for the agent to learn different n-in-a-row games, we formalized generic properties of two-person zero-sum games. game trees for different games have different game states and actions from each state. in connect four, for example, a player has 7 opening moves, while in our modified version of gobblet, with 4 game piece sizes and a 4 × 4 grid, there are 64 opening moves. to learn a new game from scratch, the agent must learn the new state space, action set and successor function, or it will not be able to retain persistent knowledge. the agent's initial game knowledge consists of an unspecified start state g 0 , a place-holder for the set of game states γ, a place-holder for the set of actions (game moves) m , and a procedure to build a successor function that defines the successor states γ i+1 given a move µ @xmath13. during a dialogue, the agent's choice to ask about a new move versus about a new win path is determined by the trained dialogue policy. for a given game, after the agent has learned at least one game state and some actions available in that state, it can start constructing a game tree for that game. we use the term information for facts presented to the agent through demonstration or language, and knowledge for incorporation of information into a persistent knowledge representation that can be used for reasoning. persistent knowledge store is useful for learning games that are too complex to learn in one short dialogue. it is also useful to be able to turn to a new dialogue partner if the current one is uninformative. the difference in an update to the agent's beliefs versus its knowledge is explained in section 4. ## 3ga pomdp with adaptive sensing a markov decision process (mdp) formalizes an agent's step-by-step decision making to reach a goal in an uncertain environment as a @xmath14, a, t, r, s 0 >, where s is the set of states, a is the set of the agent's actions, t is the transition model consisting of a probability distribution over successor states s i+1 given an action a i taken in s i , r is a reward function for each action, and s 0 is the initial state. an mdp dialogue agent's communicative actions are chosen by a policy π that maps dialogue states to the actions that maximize the discounted, cumulative reward over time. in a partially observable mdp (pomdp), states are not fully observed. here, as in previous statistical pomdp dialogue management, s consists of the agent's belief states that represent the agent's uncertain interpretations of the interlocutor's utterances, a is the agent's communicative actions, and the reward r is a trade-off between a small cost per turn and metrics that encourage the agent to achieve its dialogue goal. the remainder of this section describes the following features in turn foot_1 : 1. a hierarchical policy for context switching; 2. compositional communicative actions that mirror the policy structure; 3. three-way grounding; 4. distinct updates to beliefs versus knowledge; 5. information dynamics to support an adaptive dialogue strategy. the hierarchical policy creates nested communicative actions consisting of a parent action followed by a child action. the parent action, determined by a parent policy π p , is a decision to continue the local context initiated with demonstration d j , to resume a previous context associated to d i , (@xmath15; or to request a new demonstration d j+1 . figure 2 illustrated requests for demonstrations of new moves in q1 and q3, and for new ways to win in q4 and q5. new demonstrations are selected to be more or less informative, depending on the simulator setting, or the sensed informativeness of the human interlocutor (more below). questions q2 and q6 continue the current demonstration (continue(d i )). as noted in the description of three-way grounding, belief states are co-indexed with the demonstrations that spawn each local context. game board images are saved in a database, so when π g chooses resume(d i ), the image for d i can be re-displayed in the gui. the child policy π c chooses a question type, which completes the compound decision to ask a specific question about the selected context. compositional communicative actions are expressed using an mr that is a variant of first order logic, with predicate-argument structure, quantifiers, and question operators that are functions from contexts to specific questions (see complete specification in appendix b). the previous paragraph illustrated the parent predicates that choose the context, which is passed as an implicit argument of question operators chosen by the child policy. for example, in q2 the full mr first specifies the context as d 0 , to be an argument of the entire question function, such that the embedded predicate req(location()) constitutes a contextspecific request for a new location on d 0 . the local context-specific mr elements fall into two categories: open-ended (wh-) questions, and yes/no questions. there are five wh-question types (e.g., about locations of game pieces, or their properties, such as shape and color): three about moves and two about win conditions. eleven yes/no question types consist of two about moves and nine about win conditions. the yes/no question types are more numerous because they are more specific. the mrs are converted to english text using a natural language generation (nlg) sequence-tosequence rnn with two hidden layers and bahdanau attention @xcite . a similar model converts english responses to mrs. the rnns were trained for 15 epochs on the dialogue corpus from @xcite ) (13k turn exchanges). 4 to ensure the agent never receives in-valid answers due to inaccurate nlu, we perform automated verification on nlu output. invalid answers to yes/no questions are converted to unknown(), and inconsistent information from answers to wh-questions is removed (e.g., nonexistent board locations). replacing this step with clarification questions is left for future work. three-way grounding builds on two kinds of grounding previously utilized in human-machine interaction. symbol grounding is the relation between symbols and a representation of the physical world of objects and actions, e.g., @xcite . communicative grounding involves how information is presented and tracked during dialogue @xcite . we include grounding of symbols in a knowledge store for representing and reasoning about knowledge, as in dialogue for learning board games @xcite . what distinguishes our three-way grounding is that the 3ga mr serves as an interface to connect all communicative actions produced and generated by the agent concurrently to the real world, to an abstract knowledge store and reasoner, and to the evolving but temporary dialogue context. belief and knowledge updates take place after each turn exchange. in pomdp dialogue policies, belief state updates track the information that has been communicated to the system or agent @xcite . in 3ga, a distinct belief vector b i is updated for each local context d i with information given in answers to questions that reference the current context. each b i has j subvectors v ij representing the current state of belief about the jth predicate of the mr subset that denotes properties of game pieces or boards. for example, after a2 in figure 2 , the belief subvector for the location predicate, which is length 42 for the connect four 6 × 7 rack, is updated to represent the belief that pieces can go in locations {0, 1, 2}. each subvector v ij of the corresponding belief state b i is updated after interpreting a verbal response or new demonstration using the method from @xcite . with positive answers to yes/no questions or answers with new information, updates use equation (1), and use equation (2) for negative responses: to all our games. training used the adam optimizer (kingma and ba, 2015), with embedding size 256, 127 rnn cells, and batch size 128. the game tree update is very similar to that used in @xcite : new edges or win paths in the belief state are added to the game tree. the game tree updates determine the reward function r for calculation of the cumulative reward as the discounted sum of rewards over time (bellman equation). r is a weighted sum of the number of new moves, new win conditions, the strategic value (sv) of the new game knowledge, and a turn cost: information dynamics senses the information synergy of the dialogue by monitoring what types of question the agent chooses, and how much information the interlocutor provides. as a result, the agent can adapt its strategy at each turn exchange. previous work on mdp dialogue policies for learning games found that policies differed when trained under different fixed conditions of the amount of information a simulator provided in response to questions @xcite . given a simulator that answered all questions completely, the trained mdp produced relatively more wh-questions. training with a moderately informative simulator led to relatively more yes/no questions. at test time, the agent learned more in a dialogue if the policy matched the informativeness of the interlocutor. mdp policies, however, are not realistic given imperfect nlu, and it is not practical to depend upon an expectation of the interlocutor's informativeness. information dynamics leads to a single adaptive policy. information dynamics consists of two measures updated after each turn exchange: self information dynamics (sid) and partner information dynamics (pid). sid stores frequency counts for the 16 categories of questions, and the number of times the agent switches between different dialogue contexts. for responses to yes/no questions, pid increments the counts for the three types of responses (affirmative, negative, and non-answers), and updates the probability of getting a non-answer (e.g., i don't know). for "wh-" questions, pid updates a list of the number of different win paths provided by the dialogue partner, along with the standard deviation of the list. this gives the agent an expectation of the informativeness and consistency of answers. ## training 3ga to train 3ga, we expose it to different games and different information dynamics, using the gaussian process, q-learning from @xcite . their model had relatively few hyperparameters, converged quickly to a local optimum (< 20k epochs), and produced good results. we trained for 30k epochs, with hyper-parameters σ (noise residual) = 2, η = 3, @xmath16.15, and a polynomial kernel function. each training epoch (one dialogue) randomly selected a game and simulator informativeness. three games of increasing complexity were used: connect four, gobblet and quarto. simulator informativeness had five levels: 20%, 40%, 50%, 60%, 80% or 100%. the simulator picks answers to questions from a database that matches questions to response mrs, which the nlg module converts to english. there are different sets of mr responses for each of the 16 question categories (see appendix b). we systematically control the simulator to have informativeness 0% ≤ @xmath17. for yes/no questions, the simulator responds unknown with a probability (100x)%. for wh-questions, it provides x% of a complete answer. for example, a2 of figure 2 provides all other locations to the left of column 3 where a first disc could be placed, but omits the columns to the right, thus provides only 50% of a complete answer to the question in q2. for questions that request a new board demonstration, the simulator uses a database that pairs images with a formal representation. demonstrations of win conditions are chosen from the top (100-x)% of an ascending sort of all win paths by the number of times it has already been presented in a board demonstration. to compare how the policy converges across the three games, we sort the training epochs by game. the policy converges quickly for connect four, less quickly for gobblet, and incompletely for quarto. we tried weighting the random game selection by game complexity, but this degraded performance. average dialogue length ranged from about a dozen turn exchanges for connect four @xmath18. we capped quarto dialogues at 25, for more reasonable dialogues with humans. ## simulation experiments to test the 3ga policy in controlled conditions of informativeness, we used the simulator. in experiment 1, we examined how well the agent learned a game seen in training, under different conditions of informativeness. in experiment 2, we tested 3ga on unseen games, with no change in the training or policy. we measure the agent's game knowledge after a dialogue as the proportion of learned win paths to total win paths in a given game. note that minimax search on zero-sum game trees is known to lead to optimal play. previous work has shown that an agent that learns a game tree by asking questions can play against humans, and plays better when it acquired a more complete game tree @xcite . we compare the behavior of 3ga with a baseline, and with an oracle for each condition of game and informativeness. the baseline is identical to 3ga but omits sid_pid; the training is the same. each of the 18 oracle policies is the baseline policy, trained only a single game and informativeness level, and tested for that condition. we also report two ablations of 3ga: nosid, and nopid. ## exploratory human study our exploratory human study posed three questions: how well does 3ga communicate with people, do people vary in informativeness, and can 3ga acquire knowledge across dialogues. we used quarto, given that less of its game tree is learned in one dialogue. we tested a variant of 3ga trained specifically for quarto, omitting the generic game knowledge. participants communicated easily with the agent, had different informativeness from each other and themselves, and 3ga could continue to learn in a second dialogue. twenty-three college students (15 native speakers of english, 8 fluent non-native) participated in a two-part dialogue collection. in part one, eight native speakers had two dialogues each where the agent started out with no game tree (@xmath19. in part two, all twenty-three subjects each had two dialogues where the agent's knowledge state was a randomly selected end state of one of the part one dialogues (@xmath20. participants communicated with the agent via text through a graphical user interface (gui) that displayed the agent's questions, with a text box for subjects to enter responses. the gui displayed a visual representation of the current game board. instead of allowing subjects to select demonstrations, they were selected as in simulated dialogues, using the current estimate of the subject's informativeness. participants were asked seven questions about whether the language seemed natural or artificial, whether they could answer better if they knew the game better, what aspects of the dialogue they found interesting, and how willing they would be to have another dialogue with this agent (details in appendix d). all participants said most of the questions were like those a human would ask. six said they might have provided incorrect answers most subjects volunteered positive comments on the agent's ability to resume discussion of a previous demonstration within a dialogue, and to pick up on its knowledge from previous conversations. some of their comments appear in figure 3 . to assess human informativeness, we computed an informativeness score for each question-answer pair in a dialogue. the score for "wh-" questions measures the percentage of win conditions in the subject's response, compared to a fully informative answer. for "yes/no" questions, a non-response is uninformative (e.g., "i don't know"). the informativeness score is ratio of the positive or negative answers to the total number of "yes/no" questions in the dialogue. a subject's informativeness in a dialogue is average informativeness for all questions. based on average informativeness as calculated above, part one dialogues were binned into three groups of low (0% -33%; @xmath21, medium (33% -66%; @xmath22, @xmath23. part two dialogues had 1 low, 16 medium, and 29 high. individuals' informativeness varied. for example, the one subject with an uninformative dialogue in part one had a part two dialogue in the medium group and one in the high group. the combinations of part one and part two di-alogues yielded the seven conditions in ## related work hierarchical pomdp dialogue policies have been applied to switching between domains @xcite , or between different belief states for communicative actions versus slot values @xcite . entities versus relations among them are represented independently in the belief state in @xcite . in our work, the hierarchical policy is for context switching, and mirrored in the belief state. work on learning through communication has often addressed natural language instructions for procedural tasks such as "forwarding an email" @xcite , "grabbing an object from the desk" @xcite , or "folding cloth" @xcite . our work is for learning gametheoretic decision making, rather than procedures. extensive work has been done on learning to ground language, including words for objects or actions @xcite @xcite . our work grounds not only has 3-way grounding,it grounds generic knowledge to specific games. ## limitations the 3ga policy presented here addresses the question of whether reinforcement learning can be applied to learn a single policy for learning a variety of two-person zero-sum games through dialogues with different individuals who differ in how much information they provide. the specific limitations of this work include the difficulty of generalizing to games not seen in training, the restriction to agent initiative dialogue strategies, and the lack of communicative actions to handle poorly understood responses from the human interlocutor. we speculate the agent is unable to learn much about the structure of the game tree for unseen games. for the agent to do so this might require an ability to reason about similarities among different games. we found that in unseen games, 3ga is more sensitive to informativeness of the dialogue partner, and to game complexity, in comparison to the games seen in training. the 3ga policy is agent-initiative, which is a natural starting point for developing dialogue strategies to learn through communication: the agent learns to request information it does not already have. the three existing components that would need the most development to support mixed initiative are the natural language understanding (nlu) capabilities, the reward function, and the calculation of information dynamics. regarding the lack of clarification actions, our early probes indicated this would not greatly improve the user experience, and the questionnaire results confirmed that subjects found the agent easy to communicate with. to add this capability, communicative actions to request a restatement, or to state a lack of understanding, should be added to the agent's repertoire. as the nlu confidence is already part of the belief state, it is likely the policy could learn to execute clarification requests. a final limitation is that we have not yet looked at extending this work to learning other kinds of real-world activities. extending this work for new domains would require the means to store and reason over knowledge, extensions to the mr, and training data for the natural language models. ## conclusion the 3ga policy applies to different games, supports sustained knowledge acquisition across multiple dialogues, and accommodates differences in informativeness of interlocutors. we have shown that people do vary in their informativeness. information dynamics, which is inspired by interpersonal synergy @xcite , supports seamless transfer of a policy trained in simulation for immediate use with people, similar to use of sensing in robotics to close the so-called reality gap @xcite @xcite . it also leads to more semantic diversity of questions for the most complex game. finally, the agent can learn in a limited way about a game not seen during training.