Decision-Oriented Dialogue for Human- AI Collaboration (2024)

Abstract: We describe a class of tasks called decision-oriented dialogues, in which AI assistants such as large language models (LMs) must collaborate with one or more humans via natural language to help them make complex decisions. We formalize three domains in which users face everyday decisions: (1) choosing an assignment of reviewers to conference papers, (2) planning a multi-step itinerary in a city, and (3) negotiating travel plans for a group of friends. In each of these settings, AI assistants and users have disparate abilities that they must combine to arrive at the best decision: Assistants can access and process large amounts of information, while users have preferences and constraints external to the system. For each task, we build a dialogue environment where agents receive a reward based on the quality of the final decision they reach. We evaluate LMs in self-play and in collaboration with humans and find that they fall short compared to human assistants, achieving much lower rewards despite engaging in longer dialogues. We highlight a number of challenges models face in decision-oriented dialogues, ranging from goal-directed behavior to reasoning and optimization, and release our environments as a testbed for future work.

## introduction imagine that you are trying to book conference travel with the help of a digital assistant. your choice of airline is flexible, but you'd rather avoid layovers, want to arrive a day or two before the conference begins, and would like to be able to check in to your hotel as soon as you arrive. additionally, you're in charge of booking travel for a few of your colleagues, each of whom has their own preferences and budgets, some of whom will be flying in from different cities, but all of whom would like to arrive at roughly the same time and similar optimization problems occur in many everyday situations. consider consulting a friend about what computer they'd recommend with the best tradeoff of features for your use cases. or trying to allocate funding from multiple grants to determine which students should work on which projects, while juggling student preferences. or making strategic decisions with your colleagues about which projects your company will take on and who to hire to manage those projects. all these situations share an underlying decision problem in the face of uncertainty, where collaborating with others is often critical to arrive at the best solution. difficult decision problems like these are precisely where ai assistants could shine. automated systems can handle large amounts of information and complex computations much better than humans. for example, in cases like travel booking, they can quickly search over a large number of possible itineraries and compute total costs in a way that the average user cannot. they may also be able to efficiently reason under uncertainty about the expected value of decision-relevant information, helping them determine what information may be important to share with or request from the user. on the other hand, these decisions cannot be fully automated either. ai assistants complement humans' knowledge and capabilities: people know their preferences and may have other knowledge external to the system, including knowledge about fuzzy real-world constraints that are difficult to formalize in a computer-readable format. to solve these problems, systems need to communicate with users, ideally with a flexible interface such as natural language. however, there is limited existing work evaluating model performance in these types of conversational settings. in this paper, we develop a challenging suite of decision problems in which multiple agents must collaborate with each other and make decisions via natural language. we then benchmark the abilities of language models on these tasks and release datasets and environments to encourage future modeling work in this area. we begin by formalizing the setting of decision-oriented dialogue, a class of tasks in which multiple agents must communicate in order to arrive at a joint decision, perhaps from a combinatorially large space of options. agents in these tasks are jointly rewarded according to the quality of the decision. each agent starts out with different information: for example, the user knows their own travel preferences, while the ai assistant has a database of flight and hotel prices. sharing their information allows them to better assess different travel plans. critically, however, the large amount of information makes it unnatural and inefficient for assistants to communicate all of their knowledge to users, or vice versa. instead, agents must determine what their partners already know and what information is likely to be decision-relevant, asking clarification questions and making inferences as needed. within this class of tasks, we present three everyday domains where humans and agents must collaborate in order to make complicated decisions. (1) in assignment, two agents take on the role of conference area chairs, assigning reviewers to conference papers when each agent has only has partial information about reviewerpaper fit. (2) in planning, an assistant with knowledge of a city must assist a human with building an itinerary based on their preferences. we use these environments to benchmark the relative performance of gpt-3 @xcite in collaboration with humans, along with additional experiments in self-play and in a novel evaluation procedure known as prompted selfplay, in which ai agents complete partial human dialogues. we then identify several common failure modes of gpt-3 and provide analyses of self-play dialogues. we release all dialogues, environments, and interfaces for human data collection in order to encourage future work on these challenges. foot_0 2 task formulation we formalize a decision-oriented dialogue (dod) task as a multi-agent problem consisting of a set of agents, an underlying world state w , each agent's partial and possibly noisy observation o i , a set of legal messages @xmath0, a reward function r with parameters θ that evaluates decisions, and a communication cost function c. the goal of a decision-oriented dialogue is to find a decision that maximizes r while minimizing the communication cost function c. w remains fixed throughout the dialogue. our problem can be thought of as a decentralized partially observable markov decision process @xcite in which actions are messages and formal decisions. an agent i's policy π i maps its known information o i and the dialogue history {m 1 , . . . m t-1 } to a new message m t : π i (m t | o i , {m 1 , . . . m t-1 }). agents send messages by sampling from their policy. messages may specify a recipient if the number of @xmath1, and are expressed in natural language except for three special formal messages: a proposed decision, a formal acceptance of a decision, and a formal rejection. if an agent sends a proposed decision message and all other agents respond with formal acceptances, the dialogue ends. to illustrate the information in a dod, consider the task of planning a travel itinerary that satisfies a user's preferences (planning, as shown in figure 1 , middle). we represent the underlying world state as a weighted graph @xmath2, e, w) whose vertices are potential destinations. a decision is a path w in w , representing the itinerary. higher-weighted paths are better and the agents must communicate to improve their knowledge of the edge weights. figure 1 : overview of the three collaborative dialogue tasks that we consider. in assignment, two agents with symmetric access to information play the role of area co-chairs assigning reviewers to conference papers. in planning, an assistant collaborates with a user to help them plan an itinerary. in mediation, an assistant must chat with multiple separate users to help them resolve a group scheduling problem. in general, we represent the world state w as a weighted graph and the possible decisions as subgraphs w that satisfy task-specific constraints. 2 edges and vertices in w have weights w(e ij ), w(v i ) that represent rewards (which may be negative) for including them in w . the optimal decision for this world state is a subgraph w ⊆ w that maximizes the reward in principle, the reward function could be any function of w , but we focus on the linear objective (1). for most practical tasks, the constrained optimization problem could then be expressed as an integer linear programming problem and solved using standard algorithms. we assume edge and vertex weights are determined by their features, represented by feature vectors φ(•) ∈ r k , so that: the hard constraints on w and the form of the objective are treated as common knowledge. however, the world state w -in particular the feature vectors and the preferences θ-is only partially observed by each agent. therefore, crucially, agents must exchange messages in order to reduce their respective uncertainties about the optimization problem. however, there is a cost to communicating (e.g., time or effort), which agents must trade off with their desire to achieve a good decision. thus, the overall objective function for a dod is: ## the dialop environments we introduce three everyday collaborative decision-making domains formalized as dod tasks. to instantiate them, we release dialop, an open-source suite of decision-oriented dialogue environments. for each task, we implement a graphical ui to build human user interfaces for data collection (as in §4), a text environment to evaluate models in self-play (as in §6.2), and a unified interface between the two to evaluate models in collaboration with humans (as in §6.1). here, we describe how we formalize each everyday scenario as a dod problem and implement the environments. in contrast to other dialogue tasks where evaluation is based on supervised datasets, we procedurally generate each game by sampling the parameters of the underlying decision problem (e.g., the reward parameters θ) to instantiate new dialogue contexts. 4 to account for the variance in the difficulty of randomized optimization instances (i.e., for ease of comparison and optimization in future modeling approaches), we normalize rewards to @xcite . this generation process enables future work to study how models generalize: for example, to larger optimization problems (by changing the parameter dimensions) or new domains (by changing the ''theme'' while keeping the underlying parameters fixed). we provide more details on environment generation in appendix a. ai agents interact with the text environments through an openai gym-like interface @xcite , which is designed to provide text-only language models like gpt-3 with the same affordances that humans have in the gui. agents send messages to the environment, prefixing each with a message type ([message], [propose], @xcite , or [reject]), which the environment parses to determine how to interpret the message. messages are forwarded to other agents. proposals can be partial (e.g., a subset of the itinerary) or full, and may optionally be accompanied by another message such as a clarifying question. proposals are parsed and scored; if full, the only valid actions for the other agents are [accept] and @xcite . formal rejections clear the current proposal, and formal acceptances terminate the game. below, we describe how the environments implement each of the decision domains we introduce. ## dataset in order to study the communication strategies used by humans and establish baseline performance numbers, we collected a set of humanhuman dialogues. for each task, we built a multi-player online interface (figure 2 , left) and collected high-quality human-human dialogues in randomized games using a mixture of workers hired directly and through amazon mechanical turk, resulting in a total of 409 dialogues, consisting of 5253 messages and over 58k words across domains. pairs of human players take a median time of 8min 19sec across tasks, showing that these tasks are nontrivial. they achieve an average of roughly 90% of the maximum possible range-normalized reward on both the assignment and planning domains, and close to 100% performance in the mediation domain. we provide additional data statistics and example dialogues for each task in appendix b. in each task, each worker played the role of an assistant or user. for ease of play, players were not required to take turns, but used a chat interface where they could send a message at any time. consecutive messages from the same player were then concatenated into a ''turn.'' real-world users would know their own preferences, but our workers are emulating users that we have generated programmatically, so we must tell them what their preferences are. this setup gives us full knowledge of user preferences so that we can objectively evaluate the quality of the decision. ## baseline models future ai agents for decision-oriented dialogue may benefit from incorporating explicit reasoning over possible world states and possible decisions. however, as a baseline approach, this paper evaluates few-shot prompted lms as the ai agents. these have the benefit that they can attempt a wide variety of dialogue interactions figure 2 : data collection and evaluation frameworks. in order to collect human-human dialogues, we built web interfaces that allow humans to play either the user or assistant role for each task. when evaluating how well an ai language model plays one of these roles, we linearize information from the web interface into a text prompt and provide additional tools that let the language model access information that cannot fit within its context window. this figure shows just the assistant role, for one task. if a model generates an invalid message (e.g., if the user in planning or mediation sends a proposal), we append the message to the prompt, along with any error message from the game, and continue generating, allowing the model to revise its previous generation. generally, we simply prompt models with player information in context, with some exceptions we note here. for planning, we noted that models needed particularly complex reasoning to search based on the dialogue (on the assistant side) and to decide whether to accept an itinerary based on the scores (on the user side), so we implemented a react-style prompting approach @xcite . to do so, we augment the few-shot example dialogues in the user and assistant prompts with [think] steps (''[think] i am losing the most points from the travel time between events. i should reject the proposal...''), which demonstrate how the agent can reason. for mediation, to handle the multi-party dialogue, we adopt a simple turn-taking strategy where we iterate round-robin through all agents; on the assistant's turn, it is prompted with ''you to'' and chooses which user to send the message to by generating either 0 or 1. ## evaluation in this section, we evaluate the baseline models to determine how well prompted present-day lms can collaborate with humans. first, we directly compare the performance of lm assistants with human assistants at assisting human users. second, although helping actual humans is the ultimate goal, human-lm evaluation is expensive and frustrating for human users, given the quality of current models, so we add two automatic evaluation settings for our benchmark to ease future evaluation and provide additional insights into model behavior: self-play and prompted self-play. figure 3 : for the planning task, an annotated example of a human-human dialogue (left) and an annotated example of an lm self-play dialogue using gpt-3 (right). while humans generally exhibit diverse and flexible strategies and reach good solutions, self-play dialogues tend to be repetitive, and the assistant makes mediocre proposals and often hallucinates. we discuss further in §7. figure 4 : human-lm and self-play scores compared to human dialogues, plotted against dialogue lengths in words. lm assistants achieve lower scores than human assistants on average, and also tend to have longer dialogues. models in self-play have even lower scores and longer dialogues since they must also play the role of a cooperative user. the histograms show the marginal distributions of the scores and dialogue lengths. the dashed line shows the average score of a random proposal. ## discussion & conclusion in this paper, we presented data, environments, and model baselines for a class of tasks we call decision-oriented dialogues. across all task settings, current lms did not perform as well as humans, suggesting failures in their ability to communicate efficiently and reason in structured real-world optimization problems. future work in this domain may seek to integrate tools and inference techniques which would allow language models to compute optimal decisions while maintaining their flexible communication and collaboration skills. these tasks are also useful for studying how models optimize for longer-term dialogue objectives rather than single responses. for instance, information seeking should be an emergent behavior of a model that utilizes the underlying pomdp structure of the problem to reason about how to communicate. the ultimate goal of this line of work is to build general collaborative agents rather than agents specialized to particular settings. as we develop more generally capable models, future work should evaluate whether models can generalize their collaborative capabilities to harder task instances and transfer them to related tasks. people often use strategies that depend on the visual presentation of information @xcite , suggesting that multimodal agents that can use or generate visuals may improve collaboration (e.g., using maps in itinerary planning). additionally, people often construct their preferences over time rather than beginning with all the relevant knowledge @xcite . agents could help the user consider salient decision points. finally, we presented a particular graph-based formalism for decision-making dialogues that focuses on structured decisions and discrete optimization problems. many real-world problems may lack this formal structure but involve complex decision-making nonetheless, ranging from choosing a gift to designing a website layout to making a life decision. we hope that our work is a step toward assistants that can help us deliberate and make the best decisions in the range of problems we face every day.