Multi-Agent Task-Oriented Dialog Policy Learning with Role-Aware Reward Decomposition

The goal of RL is to discover the optimal strategy $\pi^{*}(a|s)$ of the Markov Decision Process, which can be extended into the $N$-agent setting, where each agent has its own set of states $\mathcal{S}_{i}$ and actions $\mathcal{A}_{i}$. In MARL, the state transition $s=(s_{1},\dots,s_{N})\rightarrow s^{\prime}=(s^{\prime}_{1},\dots,s^{\prime}_{N})$ depends on the actions taken by all agents $(a_{1},\dots,a_{N})$ according to each agent’s policy $\pi_{i}(a_{i}|s_{i})$ where $s_{i}\in\mathcal{S}_{i},a_{i}\in\mathcal{A}_{i}$, and similar to single RL, each agent aims to maximize its local total discounted return $R_{i}=\sum_{t}\gamma^{t}r_{i,t}$.

Since two or more agents learn simultaneously, the agents continuously change as the training proceeds, therefore the environment is no longer stationary. Many MARL algorithms Lowe et al. (2017); Foerster et al. (2018); Rashid et al. (2018) have been proposed to solve challenging problems. Most of them use the CTDE framework to address the non-stationarity of co-adapting agents. It allows the policies to use extra information to ease training, but the learned policies can only use local information (i.e. their own observations) at execution time.

Several studies have demonstrated that applying MARL delivers promising results in NLP tasks these years. While some methods use identical rewards for all agents Das et al. (2017); Kottur et al. (2017); Feng et al. (2018), other studies use completely separate rewards Georgila et al. (2014); Papangelis et al. (2019). MADPL integrates two types of rewards by role-aware reward decomposition to train a better dialog policy in task-oriented dialog.

User modeling is essential for training RL-based dialog models, because a large amount of dialog samples are required for RL policy learning, making it impractical to learn with real users directly from the beginning.

There are three main approaches for user modeling. The first approach is to build a rule-based user simulator. Among these methods, the most popular one is agenda-based simulator Schatzmann et al. (2007); Shah et al. (2018), which is built on hand-crafted rules with a stack-like agenda based on the user goal. The second approach is to build a user simulator from the dialog data Keizer et al. (2010); El Asri et al. (2016); Kreyssig et al. (2018). Recently, Gür et al. Gür et al. (2018) uses a variational hierarchical seq2seq framework to encode user goal and system turns, and then generate the user response. Shi et al. Shi et al. (2019) uses two decoders with a copy and attention mechanism to predict a belief span first and then decode user utterance. The third approach is to use model-based policy optimization that incorporates a differentiable model of the world dynamics and assumptions about the interactions between users and systems Su et al. (2018); Zhang et al. (2019), but this approach still requires real users or a user simulator for world model learning.

Instead of employing a user simulator, a few methods jointly learn two agents directly from the corpus. Liu and Lane Liu and Lane (2017) models the system and the user by iteratively training two policies. Papangelis et al. Papangelis et al. (2019) make the first attempt to apply MARL into the task-oriented dialog policy, whose algorithm is based on Q-learning for mixed policies. However, it is not well scalable to complex tasks such as multi-domain dialog. Therefore, MADPL uses the actor-critic framework instead to deal with the large discrete action space in dialog.

On the one hand, the roles between the user agent and the system agent are different. The user agent actively initiates a task and may change it during conversation, but the system agent passively responds to the user agent and returns the proper information, so the reward should be considered separately for each agent. On the other hand, two agents communicate and collaborate to accomplish the same task cooperatively, so the reward also involves a global target for both agents. Therefore, we decompose the mixed reward into three parts according to the characteristic of each component. The reward of each part is explained as follows:

The value function aims to estimate the expected return given the current state $V(s_{t})=\mathbb{E}[R_{t}]=\mathbb{E}[\sum_{t^{\prime}\geq t}\gamma^{t^{\prime}-t}r_{t^{\prime}}]$ so that the policy can directly use the estimated cumulative reward for optimization, without sampling the trajectories to obtain rewards which may cause high variance. Another advantage by applying actor-critic approaches in MARL is that it can integrate with the CTDE framework: the actor of each agent benefits from a critic that is augmented with additional information about the policies of other agents during training. However, a simple centralized critic conditioned on the global state and joint actions cannot well exploit the domain knowledge mentioned above since each part of the overall rewards only depends on a subset of features, e.g. the system reward only depends on the system agent’s behaviors.

Inspired by Hybrid Reward Architecture Van Seijen et al. (2017) that learns a separate Q function, we propose Hybrid Value Network to improve an estimate of the optimal role-aware value function. It first encodes the dialog state of each agent to learn a state representation

where $f(\cdot)$ can be any neural network unit. The value network $V$ is separated into three branches $V^{S}$, $V^{U}$ and $V^{G}$ for the value of system rewards, user rewards and global rewards, respectively.

The action space for the policies can be very large since we deal with multi-domain, complex dialog tasks, which makes it almost impossible for the RL policies to explore and learn from scratch. So the training process can be split into two stages Fatemi et al. (2016); Takanobu et al. (2019): pretraining the dialog policy with the conversational corpus first and then using RL to improve the pretrained policies. We use $\beta$-weighted logistic regression for policy pretraining here to alleviate data bias because each agent only generates several dialog acts in one dialog turn

where $X$ is the state and $Y$ is the action from the corpus in this task.

As for critic optimization, it aims to minimize the squared error between the temporal difference (TD) target $r_{t}+\gamma V(s_{t+1})$ and the estimated value $V(s_{t})=\mathbb{E}[r_{t}+\gamma V(s_{t+1})]$. Actor-critic algorithms have high variance since the critic is updated too frequently, which has contributed to severe changes in the estimated value, particularly in multi-agent tasks. So we introduce a target network Mnih et al. (2015) to make the training process more stable. In the context of HVN, it aims to minimize the following loss functions:

where HVN $V_{\theta}$ is parameterized by $\theta$, and $\theta^{-}$ is the weight of target network, and the overall loss $L_{V}$ is the sum of value estimation loss on each component reward.

Each dialog policy aims to maximize all the related returns, e.g. the system policy $\pi$ aims to maximize the cumulative system rewards and global rewards $\mathbb{E}[\sum_{t}\gamma^{t}(r_{t}^{S}+r_{t}^{G})]$. The advantage $A(s)=r+\gamma V(s^{\prime})-V(s)$ estimated by the critic can evaluate the new state $s^{\prime}$ and current state $s$ to determine whether the dialog has become better or worse than expected. With the aid of HVN, the sum of the related component advantages can be used to update different agents. By using the log-likelihood ratio trick, the gradients for the system policy and the user policy yield:

where the system policy $\pi_{\phi}$ is parameterized by $\phi$ and the user policy $\mu_{\omega}$ by $\omega$.

In summary, a brief script for MADPL is shown in Algorithm 1.

MultiWOZ Budzianowski et al. (2018) is a multi-domain, multi-intent task-oriented dialog corpus that contains 7 domains, 13 intents, 25 slot types, 10,483 dialog sessions, and 71,544 dialog turns. During the data collection process, a user is asked to follow a pre-specified user goal, and is allowed to change the goal during the session if necessary, so the collected dialogs are much closer to real-world conversations. The corpus also provides the domain knowledge that defines all the entities and attributes as the external database.

Evaluation of a task-oriented dialog system mainly consists of the cost and task success. We count the number of dialog turns to reflect the dialog cost. A user utterance and a subsequent system utterance are regarded as one dialog turn. We utilize two other metrics: inform F1 and match rate to estimate the task success. Both metrics are calculated at the dialog act level. Inform F1 evaluates whether all the requested information has been informed, and match rate checks whether the booked entities match all the indicated constraints given by the user. The overall task success is reached if and only if both inform recall and match rate are 1.

We compare MADPL with a series of baselines that involve both system policy learning and user policy learning. Note that we do not consider any other approaches that use a user simulator for policy training because our motivation is to avoid explicitly modeling a simulator.

A set of 1,000 user goals are used for automatic evaluation as shown in Table 1. When the dialog is launched, two agents interact with each other around a given user goal. The performance of interaction between the two trained policies are shown in Table 2. MADPL reaches the highest match rate and task success among all the methods. It manages to improve the success rate of the pretrained policies from 49.7% to 70.1%. Single RL policies (row 2 to 4) have limited improvement, and even decline in match rate since they assume a stationary environment. The comparison between CRL and IterDPL indicates the effectiveness of CTDE in the multi-agent task. The superiority of MADPL against CRL shows that two agents benefit from the role-aware reward decomposition in HVN. The learning curves in Fig. 3 illustrates that the success rate grows rapidly in MADPL, and it always improves the success rate as the training proceeds.

The average reward of each component reward is shown in 4. We run 10 different instances of MADPL with different random seeds. The solid curves correspond to the mean and the shaded region to the standard deviation of rewards over the 10 trials. We can observe that all the rewards increase steadily during the training process, which implies that HVN has estimated a proper return for policy training.

It is essential to evaluate a multi-agent dialog system whether all the agents understand the semantic interaction rather than invent an uninterpretable language Kottur et al. (2017); Lee et al. (2019a). To this end, we use two benchmark policies in the standardized task-oriented dialog system platform Convlab Lee et al. (2019b) to examine all the methods. Each benchmark is a strong rule-based system policy or user policy at the dialog act level, which is used as the simulated evaluation in the DSTC-8 Track 1 competition and show a high correlation with real user interaction Li et al. (2020). The trained system/user policy in each method is directly deployed to interact with the benchmark user/system policy during the test without any other finetuning, which can be regarded as a weakly zero-shot experiment. The same goal set in Table 1 is used here.

Table 3 and Fig. 5 show the results of the interaction between the benchmark user policy and the system agent of each model. The SOTA performance from GDPL Takanobu et al. (2019) that directly trains with benchmark user policy is also presented as the soft performance upper bound. Among all the methods, MADPL has achieved the highest task success and the second-highest match rate. All the methods experience a decline in inform F1 after the RL training. Fig. 5 also shows that the success rate is unstable during training. This is because the action space of the system policy is much larger, thus more challenging to learn. In spite of that, the success rate of MADPL shows a rising trend.

Table 4 and Fig. 6 show the results of the interaction between the user agent of each method and the benchmark system policy. Among all the methods, MADPL has achieved the highest inform F1 and task success. Though CRL improves the performance at the beginning, the success rate fails to increase further afterwards, while MADPL continues to improve all the time. This also indirectly indicates the advantage of using role-aware reward decomposition in HVN.

In summary, each policy trained from MADPL can interact well with the benchmark policy, which implies that MADPL learns a reasonable dialog strategy.

We also investigate the domains in the user goals to observe the scalability of each method in the complex tasks. 200 goals are randomly sampled under each setting. Fig. 7 presents the results of the interaction between two agents in different numbers or classes of domains. The success rate decreases substantially as the number of domains increases in the goal. When there are 3 domains in the goal, RL/RL gets a high inform F1 but a low match rate, IterDPL gets a high match rate but a low inform F1, while MADPL can still keep a high inform F1 and match rate, and obtains the highest task success. In terms of the class of domains, there are 7/10/6 informable slots that needs to be tracked in the Restaurant/Hotel/Train domain respectively. Among these, MADPL outperforms other baselines in the Restaurant and Hotel domains, and performs comparably in the Train domain. In brief, all the results indicate that MADPL has good scalability in multi-domain dialog.