Abstract
We present a new algorithm that significantly improves the efficiency of exploration for deep Q-learning agents in dialogue systems. Our agents explore via Thompson sampling, drawing Monte Carlo samples from a Bayes-by-Backprop neural network. Our algorithm learns much faster than common exploration strategies such as $\epsilon$-greedy, Boltzmann, bootstrapping, and intrinsic-reward-based ones. Additionally, we show that spiking the replay buffer with experiences from just a few successful episodes can make Q-learning feasible when it might otherwise fail.
The Challenge of Sparse Rewards in Dialogue
Training an AI agent to conduct multi-turn, task-oriented dialogues—such as booking a movie ticket—is a complex reinforcement learning (RL) problem. While Deep Reinforcement Learning (DRL) offers a path toward flexible policies, dialogue systems suffer from extreme reward sparsity. An agent typically receives a positive reward only at the end of a conversation if the task is successfully completed.
Standard DRL agents, like Deep Q-Networks (DQNs), typically rely on $\epsilon$-greedy exploration. In environments with large action spaces and sparse rewards, random exploration rarely encounters successful outcomes. In initial tests, a randomly exploring Q-learner achieved zero successes over thousands of episodes, highlighting the need for more efficient exploration strategies.
Methods: BBQ-Networks and Replay Buffer Spiking
To address these challenges, we introduce two primary techniques: Deep BBQ-Networks (BBQN) and Replay Buffer Spiking (RBS).
Deep BBQ-Networks (BBQN)
Instead of learning fixed weights, BBQN (Bayes-by-Backprop Q-networks) learns a probability distribution (Gaussian) over the network's weights. This allows the model to quantify its own uncertainty.
- Thompson Sampling: The agent explores by sampling weights from this distribution and acting greedily. This drives the agent toward state-action pairs where it is uncertain, a more principled approach than random noise.
- MAP Target Generation: For stability and speed, Maximum A Posteriori (MAP) weight estimates are used to generate temporal difference targets.
Replay Buffer Spiking (RBS)
To "jumpstart" learning in a sparse reward environment, the experience replay buffer is pre-filled with a small number of successful dialogues generated by a simple, rule-based agent. Even though this rule-based agent is sub-optimal (18.3% success rate), providing just 100 successful examples allows the RL agent to discover that rewards are possible and begin the learning process.
Experimental Evaluation
Agents were evaluated on a movie-booking task in both stationary ("Full Domain") and non-stationary ("Domain Extension") simulated environments, as well as in a human user study.
Simulation Performance
In the Full Domain setting, BBQN-MAP achieved a 50.3% success rate, nearly doubling the standard DQN's 26.9%. In the Domain Extension setting, where new slots are introduced over time, the combination of BBQN and VIME (Variational Information Maximizing Exploration) reached a 71.2% success rate, compared to 35.0% for the DQN baseline.
Human Evaluation
A study with 398 real-user dialogue sessions confirmed these findings. The BBQN agent achieved a 59% success rate (vs. 29% for DQN) and an average user rating of 3.42/5 (vs. 2.6/5 for DQN).
Conclusion
Explicitly quantifying uncertainty via Bayesian neural networks significantly outperforms traditional exploration methods in dialogue tasks. Furthermore, Replay Buffer Spiking proves to be a critical practical technique for overcoming the "zero-success" hurdle in sparse reward environments. The synergy between parameter uncertainty (BBQN) and environment dynamics uncertainty (VIME) suggests that these methods are highly complementary for complex, non-stationary tasks.
Summary updated