📄 Agenda-Based User Simulation for Bootstrapping a POMDP Dialogue System

Summary

The paper tackles a chicken-and-egg problem in building statistical dialogue managers (DMs). Learning a policy needs many dialogues, typically around 10^4, but without a working system you cannot collect them. Wizard-of-Oz or handcrafted-prototype corpora are also usually an order of magnitude too small. The authors propose a probabilistic user simulator that needs no training data. The simulated user's state is split into two parts:

• a goal, made of constraints the venue must satisfy plus pieces of information the user wants;
• a stack-like agenda of pending dialogue acts.

The model factorises the user's behaviour into act selection, agenda updates and goal updates. These are reduced to so few parameters that hand-set values become workable. The simulator was used to train the HIS dialogue manager, a POMDP-based system, on a tourist-information task. A policy learned entirely from simulated users was then tested with 40 human subjects and completed over 90% of tasks. This shows that a carefully structured simulator with handcrafted parameters can bootstrap a statistical DM before any real data exists.

Key points

• The user state is S = (A, G), with goal G = (C, R): constraints (e.g., type, drinks, area) and requests (e.g., name, addr, phone). Each new dialogue starts from a goal sampled from the system database.
• At the start, the agenda holds one inform act per constraint and one request act per request slot, with a bye() act at the bottom. Each user turn pops the top n acts, where n reflects user initiative and is drawn from a distribution favouring small values.
• The HIS dialogue manager uses a grid-based discretisation of the belief space and online ε-greedy policy iteration. The reward is +20 for success and −1 per turn. Training over 60,000 simulated dialogues converged after about 25,000 and levelled off near 14 points.
• In the human evaluation, 40 subjects (a mix of native and non-native speakers) took part. 145 of 160 dialogues (90.6%) ended with a correct venue, averaging 5.59 turns.
• Planned future work is to train the simulator itself on the collected real dialogues and then retrain the policy.

Interesting ideas

• I1. Stack as dialogue memory. A priority stack of pending acts tracks what the user still wants to say. It also lets lower-priority acts wait while urgent ones, such as corrections, are issued first. This is a cheap, interpretable way to encode history in any goal-driven agent simulator.
• I2. One push per system-act item. Each item in the machine's act triggers exactly one push onto the agenda (possibly a null act removed later). This makes the update a product of small per-item distributions conditioned on the goal, so a huge transition space becomes something you can set by hand.
• I3. Conditioning on boolean flags. Goal changes depend only on a few yes/no features, such as whether the system asked about a constraint slot or reported no matching item. Summarising complex inputs into a handful of flags is a general way to keep handcrafted probabilistic models tractable.
• I4. Deterministic clean-up. The stochastic push step is separated from a rule-based step that drops duplicates and requests that are already satisfied. Keeping randomness where it matters and rules elsewhere simplifies both the maths and the implementation.
• I5. Evaluate with real users. The handcrafted simulator was not judged only against itself; the policy it produced was checked with real users. Measuring task success with humans is a sound check for any synthetic-data or simulation-trained system.