Anti-Overestimation Dialogue Policy Learning for Task-Completion Dialogue System

Chang Tian, Wenpeng Yin, Marie-Francine Moens

TL;DR

This paper introduces the Dynamic Partial Average (DPAV) estimator to tackle the notorious overestimation bias in reinforcement learning-based dialogue systems. By dynamically balancing predicted maximum and minimum action values, DPAV DQN achieves state-of-the-art task completion performance across multiple domains while completely avoiding the heavy computational overhead of ensemble methods.

What Problem Does This Paper Address?

Task-completion dialogue systems (such as automated systems for booking movie tickets or reserving tables at restaurants) typically rely on a pipeline framework. This pipeline consists of Natural Language Understanding (NLU), Dialogue State Tracking (DST), Dialogue Policy Learning (DPL), and Natural Language Generation (NLG).

Figure 1: Task-completion dialogue system

The DPL module decides which action the system should take next based on the current dialogue state. Increasingly, researchers use Reinforcement Learning (RL)—specifically Q-learning—to train this module. However, standard Q-learning suffers from a fundamental flaw: overestimation bias. Because the standard maximum estimator selects the maximum expected value over noisy, approximated actions, it systematically overestimates the true action values.

In a dialogue system, this bias causes the agent to become overly confident in incorrect actions. For example, the system might get stuck in a loop, repeatedly asking a user "How many tickets do you need?" even after the user has already answered. This leads to broken conversations and failed tasks. Existing solutions either introduce underestimation bias (like Double DQN) or require computationally expensive ensemble models that are too heavy for practical deployment.

Figure 2: Wrong and correct dialogue actions

Methods

The authors propose the Dynamic Partial Average (DPAV) estimator to mitigate overestimation without veering into underestimation or inflating computational costs.

Instead of relying solely on the maximum predicted Q-value, DPAV calculates a weighted average between the maximum and minimum predicted action values from the target network:

$$Q_*(s_{t+1}) \approx (1 - \lambda_t) * \max_{a'} Q(s_{t+1}, a') + \lambda_t * \min_{a''} Q(s_{t+1}, a'')$$

Here, $\lambda_t$ is a dynamic, problem-dependent float between 0 and 1. To ensure the model relies more on its maximum predictions as it becomes better trained, $\lambda_t$ decays over time according to a predefined rate $d$:

$$\lambda_{t+1} = \lambda_t * d$$

By integrating this estimator into a Deep Q-Network (DPAV DQN), the system effectively uses the minimum predicted value to "pull down" the overestimated maximum. Crucially, because it operates on a single value function rather than an ensemble of multiple networks, DPAV DQN maintains a low time complexity of $O(N)$, identical to standard DQN.

Datasets

The authors evaluated their approach on three public task-completion dialogue benchmarks:

  • Movie-ticket booking: Contains 11 intents, 16 slots, and 128 user goals across 280 dialogues.
  • Restaurant reservation: Contains 11 intents, 30 slots, and 3,525 user goals across 4,103 dialogues.
  • Taxi ordering: Contains 11 intents, 29 slots, and 2,830 user goals across 3,094 dialogues.

Key Insights and Ideas

  • The Minimum as an Anchor: The core "aha" moment is realizing that the minimum predicted action value can serve as a regularizer against the maximum estimator's upward bias.
  • Dynamic Weighting is Essential: Early in training, Q-value estimates are highly inaccurate and noisy, meaning overestimation is severe. A higher $\lambda$ leverages the minimum value to aggressively counteract this bias. As training progresses and predictions stabilize, decaying $\lambda$ prevents the model from underestimating true optimal values.
  • Efficiency Over Ensembles: Traditional state-of-the-art methods against overestimation (like SUNRISE or Maxmin DQN) rely on ensembles of $K$ networks, scaling time complexity to $O(K \cdot N)$. This paper proves that mathematically bounding and regularizing a single network can achieve comparable or superior results.

Key Results

  • Superior Performance: DPAV DQN consistently outperformed standard DQN and achieved better or comparable success rates and average rewards compared to top baselines (including Double DQN, Duel DQN, and ensemble methods) across the movie and restaurant domains.
  • Computational Efficiency: As shown in the paper's complexity analysis, DPAV DQN achieves its performance with a fraction of the computational load required by ensemble methods ($O(N)$ vs $O(K \cdot N)$).
  • Optimal Hyperparameters: Empirical testing demonstrated that an initial weight of $\lambda_0 \approx 0.5$ consistently yielded the best performance across all three distinct dialogue domains.

Limitations and Future Work

  • Confusing States: In the taxi domain, Duel DQN slightly outperformed DPAV DQN in final success rate. The authors note that when a state lacks an explicitly preferable action, the action values become highly similar, reducing DPAV's ability to effectively mitigate bias through max-min averaging.
  • Heuristic Dependency: The initial value $\lambda_0$ and decay rate $d$ currently require manual, heuristic searching. The authors attempted to train a neural network (LambdaNet) to automatically learn $\lambda_t$ dynamically, but it failed to converge. Automating this trade-off remains an open challenge for future research.

Summary updated

Abstract

A dialogue policy module is an essential part of task-completion dialogue systems. Recently, increasing interest has focused on reinforcement learning (RL)-based dialogue policy. Its favorable performance and wise action decisions rely on an accurate estimation of action values. The overestimation problem is a widely known issue of RL since its estimate of the maximum action value is larger than the ground truth, which results in an unstable learning process and suboptimal policy. This problem is detrimental to RL-based dialogue policy learning. To mitigate this problem, this paper proposes a dynamic partial average estimator (DPAV) of the ground truth maximum action value. DPAV calculates the partial average between the predicted maximum action value and minimum action value, where the weights are dynamically adaptive and problem-dependent. We incorporate DPAV into a deep Q-network as the dialogue policy and show that our method can achieve better or comparable results compared to top baselines on three dialogue datasets of different domains with a lower computational load. In addition, we also theoretically prove the convergence and derive the upper and lower bounds of the bias compared with those of other methods.
BibTeX
@inproceedings{tian2022anti,
  author = {Chang Tian and Wenpeng Yin and Marie-Francine Moens},
  title = {{Anti-Overestimation Dialogue Policy Learning for Task-Completion Dialogue System}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2022},
  doi = {10.18653/v1/2022.findings-naacl.43},
}
Figure