Task-Completion Dialogue Policy Learning via M onte C arlo Tree Search with Dueling Network (2020)

Abstract: We introduce a framework of Monte Carlo Tree Search with Double-q Dueling network (MCTS-DDU) for task-completion dialogue policy learning. Different from the previous deep model-based reinforcement learning methods, which uses background planning and may suffer from low-quality simulated experiences, MCTS-DDU performs decision-time planning based on dialogue state search trees built by Monte Carlo simulations and is robust to the simulation errors. Such idea arises naturally in human behaviors, e.g. predicting others’ responses and then deciding our own actions. In the simulated movie-ticket booking task, our method outperforms the background planning approaches significantly. We demonstrate the effectiveness of MCTS and the dueling network in detailed ablation studies, and also compare the performance upper bounds of these two planning methods.

## introduction designing a task-completion dialogue system has become an important task due to its huge commercial values. the dialogue agent aims to help users to complete a single or multi-domain task, e.g. booking a flight and making a hotel reservation. the core of such a system is the dialogue policy module, which enables the agent to respond properly and provide users with the desired information. early work has shown that dialogue policy learning can be designed as a markov decision process (mdp) @xcite @xcite . reinforcement learning (rl) is a common framework to solve mdp but it requires huge amounts of interactions with real users, which is generally infeasible in the real world. one way to work around this problem * corresponding author is by designing a user simulator using the real human conversation data @xcite . recently, following these ideas, many researchers have applied deep model-based rl methods to task-completion dialogue policy learning @xcite @xcite . in a model-based method, the agent not only updates its action value or policy function through real experiences but also learns how the environment produces the next states and rewards. the learned environment is called a model, which can be further used to generate simulated experiences. using both real and simulated experiences is referred to as background planning and can substantially improve the learning efficiency @xcite . @xcite extend dyna-q @xcite to deep dyna-q (ddq) for dialogue policy learning and achieve appealing results. however, since model learning cannot be perfect, some simulated experiences with large errors may hinder policy learning @xcite . @xcite propose to train a discriminator to filter low-quality simulated experiences. @xcite design a switcher-based mechanism to automatically balance the use of real and simulated experiences. nevertheless, the overall improvement is still limited. in this paper, we first upgrade the common baseline model of the task-completion dialogue policy learning problem, deep q-network (dqn) @xcite by adopting its two variants: deep double q-networks (ddqn) @xcite and dueling network @xcite . the purpose is to fully exploit the advanced valuebased methods that are orthogonal to planning. we show that the new baseline can achieve comparable performance with ddq. to further boost the performance, we propose to use monte carlo tree search (mcts) @xcite as decision-time planning @xcite . the differences between background and decision-time planning are illustrated in figure 1 and 2. decisiontime planning doesn't use the model to generate simulated experiences. in the testing stage or a real decision time, rather than directly picking actions based on action values, a rollout algorithm like mcts uses the model to build a search tree by running simulations. performing policy evaluation on the search tree generally yields more accurate estimations of action values assuming that the model is correct. due to this property, mcts has achieved huge success in the game of go @xcite . however, its applications in the non-gaming settings, such as dialogue systems, are still rare and little studied. one difficulty is that the model now has to learn the more complex dynamics of state transitions than the deterministic game rules. consequently, mcts may grow a erroneous search tree and the resulting estimated action values may be wrong. to alleviate simulation errors, we design a new mcts method incorporating the ddqn object and the dueling architecture. the main idea is to focus on the more promising parts of the state-action space and reduce the rollout depths. the dueling network can be used as heuristic or scoring functions in this case. given dialogue states, it outputs two streams of data: action advantages and state values. action advantages can be viewed as the prior knowledge to differentiate actions. state values can be used as the approximated rollout results. we denote an agent under this design as mcts-ddu. experiments show that mcts-ddu agent outperforms previous methods by a wide margin in both task success rate and learning efficiency. briefly, the main contributions of our work are in the following aspects: reinforcement learning is a framework to solve sequential decision problems. the problem can be formalized as a markov decision process s, a, p, r, γ , where s is a finite state space, a is a finite action space, p is a state transition function, r is a reward function, and γ is a discount factor. a value-based agent aims to learn an action value function as its implicit policy, so that its expected long-term rewards are maximized. next, we show how to formalize a task-completion dialogue session as a mdp. state s t is defined as the dialogue history of previous t turns, containing user intents, associated slots, and agent responses. action a t is defined as dialog act, (intent, slot), representing the agent's intent on a specific slot. take movie-ticket booking as an example, (request, #tickets) means that the agent asks the user how many tickets are needed. transition p represents the dialogue state updates according to stochastic responses from the user to the agent. in the case of a user simulator, the handcrafted rules define the state transitions implicitly. reward r is the immediate feedback signal after the agent takes an action to the user, which generally depends on the dialogue status, such as in-process, success, or failure. ## methodology for a dialogue process involving complex state dynamics, applying planning directly is problematic, since the model learning cannot be perfect. this may result in low-quality simulated experiences for dyna-q and an erroneous search tree for mcts. in the former case, it is inevitable that parameter updates would be made in some wrong directions for the action value network. while for mcts, it is possible to reduce the incorrect portions by trimming the depths based on value function that summarize the subtrees, and preferring the actions with higher advantages for branch exploration. since a value-based agent picks actions based on the action advantages, the state transitions induced by the higher advantages are more likely to be generalized well. thus, branch exploration with the higher action advantages contains fewer errors by focusing more on the neighborhood of those well learned state space. our framework for task-completion dialogue policy learning is presented in figure 3 and algorithm 1. in the training stage, the action value network or q-network @xmath0, v ) is optimized via direct reinforcement learning and the model @xmath1, r) is optimized via model learning respectively. in the testing stage, the agent take actions in a more thoughtful way by performing mcts with the action advantage head a and the state value head v . ## experiments in this section, we first introduce the experimental setup and baseline models. we also propose a new model-free baseline based on the recent extensions of dqn. the effectiveness of mcts, advantage function, and ddqn objective are demonstrated via thorough ablation studies. we also explore the tradeoff between exploitation and exploration in mcts. lastly, we compare the performance upper bounds of background and decision-time planning with a perfect model. ## conclusions our work introduces a novel way to apply deep model-based rl to task-completion dialogue policy learning. we combine the advanced valuebased methods with mcts as decision-time planning. in the movie-ticket booking task, mcts-ddu agent exceeds recent background planning approaches by a wide margin with extraordinary data efficiency. in this paper, one main focus is to demonstrate the differences between background and decisiontime planning. however, it is reasonable and straightforward to combine them together. this might be an interesting topic for future work.