Towards End-to-End Learning for Dialog State Tracking and Management using Deep Reinforcement Learning

In plain words

A task-oriented chatbot has to figure out what the user wants, keep track of what has been said, and then act, for example by asking a question or looking something up. Usually these steps are separate modules that are built and debugged one at a time. This paper trains one model to do the whole job, with the only signal being whether the conversation reached its goal.

The test is a game of 20 Questions. The agent asks yes/no questions about a hidden person and makes guesses. It is rewarded for a correct guess and penalised for wrong ones and for running out of turns. The agent keeps a running memory of the conversation, and it also fills in a small form of what it has learned about the answers so far, which it then uses to choose its next move.

Learning from the final win or loss alone is slow. When the agent is also told the true answer to each question, it learns faster. The paper calls this variant Hybrid-RL. The reported results favour the end-to-end models over a conventional pipeline. These results come from a simulated user, not from real people.

TL;DR

• Replaces the separate language-understanding, state-tracking and policy modules of a task-oriented dialog system with one recurrent deep Q-network trained by reinforcement learning §4.
• The agent takes two kinds of action: verbal actions (a question or a guess) and slot-filling actions that set the value of the latest question in a database query hypothesis §4.2.
• Hybrid-RL adds a state-tracking label term to the reward and generates synthetic database transitions, which the paper says speed up learning §4.3.
• Evaluated only in a 20-questions simulator with 100 people and 31 questions; author-reported win rates are 90.5% (Hybrid-RL), 85.6% (RL) and 68.5% (modular baseline) tab. 3.

Problem

Conventional spoken dialog systems chain NLU, dialog state tracking (DST), dialog policy and NLG §1, fig. 1. The paper names two problems with this pipeline: errors from upstream modules are hard to attribute (credit assignment), and retraining one module can make the others sub-optimal (process interdependence) §1. Dialog state tracking is usually trained as a supervised labelling task, and the policy that consumes the tracker's output is trained separately, so the two distributions can mismatch §2.

The paper assumes that a reward signal (dialog success) is available from users and from the database, and that state-tracking labels may or may not exist §4.1, §4.3. It does not claim a general solution; the evaluation covers one simulated domain §5.1.

Method

Overview §4.1 fig. 2

The agent acts in a POMDP-style setting. Its environment has a user and a database §4.2. At each turn it selects a verbal action (a question about one attribute, or a guess) or a slot-filling action that changes the query hypothesis, then receives either a user reply or a database result §4.2.

Observation and belief §4.2 eq. 3 fig. 3

The observation at turn t concatenates the action, the user observation and the database observation eq. 3. An LSTM aggregates observations over turns into a state vector that the paper treats as an approximation of the belief state §4.2 §3.2.

o^t = \begin{bmatrix} a_t \\ o^u_t \\ o^{db}_t \end{bmatrix} \qquad [\text{eq. 3}]

The recurrent state feeds Q-value heads. The text describes one verbal-action head Q(b_t, a^v) and S+1 heads, one per slot, Q(b_t, a^h) §4.2 fig. 3. §5.3 says the 20Q experiments use only one slot-filling head with three outputs (yes, no, unknown), reused for every question §5.3. The two descriptions differ in the number of slot heads; §5.3 is the one the experiments use.

Learning §3.1 §3.2 eq. 1 eq. 2

The base learner is a DRQN: a DQN whose convolutional front end is followed by an LSTM §3.2. The DQN loss uses a target network, experience replay and the Bellman target eq. 1 eq. 2. The paper states that double DQN and prioritised experience replay were "found useful" and included, but gives no parameters for either §3.1.

\mathcal{L}(\theta_i) = \mathbb{E}_{(s,a,r,s')}\left[\left(y^{DQN} - Q(s,a;\theta_i)\right)^2\right] \qquad [\text{eq. 1}]

y^{DQN} = r + \gamma \max_{a'} Q(s', a';\theta_i^-) \qquad [\text{eq. 2}]

Hybrid-RL: state-tracking labels §4.3 eq. 4 eq. 5

The paper splits the reward for slot actions into a database-driven part and a label part eq. 4 eq. 5. The label part P(a^h|b) is replaced by an indicator 1(y = a^h), where y is the state-tracking label §4.3. The paper says this avoids training a separate model for P(a^h|b).

Q^{\pi}(b,a^h) = \bar{R}(b,a) + \gamma \sum_{b'} P(b'|b,a^h)\, V^{\pi}(b') \qquad [\text{eq. 4}]

\bar{R}(b,a,b') = R(b,a^h) + P(a^h|b) \qquad [\text{eq. 5}]

Because the database dynamics P(b'|b,a^h) are known, the agent can create synthetic experience tuples (b, a^h, r, b') for every slot action and add them to the replay buffer §4.3. The paper ties this to Dyna-Q but notes that Dyna-Q learns a model, whereas this method uses only the known database transition §4.3.

Constrained action mask §4.4 eq. 6 eq. 7

The available actions depend on whether the user has just given new input: slot-filling actions are allowed only then, and otherwise the agent must act verbally §4.4.

A_{mask}(s) = A_h \quad \text{if new input from the user} \qquad [\text{eq. 6}]

A_{mask}(s) = A_v \quad \text{otherwise} \qquad [\text{eq. 7}]

# Action masking  [§4.4] [eq. 6] [eq. 7]
def available_actions(new_user_input):
    # Slot-filling actions only right after new user input  [§4.4]
    if new_user_input:
        return slot_actions      # A_h  [eq. 6]
    # Otherwise the agent must act verbally  [§4.4] [eq. 7]
    return verbal_actions        # A_v

Potential-based reward shaping from the database §4.4 eq. 8–eq. 11

The user gives sparse end-of-dialog rewards, while the database gives frequent signals §4.4. The paper adds a potential-based shaping term F(s,a,s') = γφ(s') − φ(s) eq. 8 eq. 9. The potential depends on d_t, the number of database entities consistent with the current hypothesis, out of D entities in total, with a maximum potential P_max §4.4 eq. 10 eq. 11.

\bar{R}(s,a,s') = R(s,a,s') + F(s,a,s') \qquad [\text{eq. 8}]

F(s,a,s') = \gamma\,\phi(s') - \phi(s) \qquad [\text{eq. 9}]

\phi(s_t) = P_{max}\left(1 - \frac{d_t}{D}\right) \quad \text{if } d_t > 0 \qquad [\text{eq. 10}]

\phi(s_t) = 0 \quad \text{if } d_t = 0 \qquad [\text{eq. 11}]

# Database potential  [§4.4] [eq. 10] [eq. 11]
def potential(consistent_count, total_entities, p_max):
    # Zero when no entity is consistent with the hypothesis  [§4.4]
    if consistent_count == 0:
        return 0.0
    # Narrowing the candidate set raises the potential  [§4.4] [eq. 10]
    return p_max * (1.0 - consistent_count / total_entities)

# Shaped reward  [§4.4] [eq. 8] [eq. 9]
def shaped_reward(reward, phi_prev, phi_next, gamma):
    # The shaping term changes learning speed, not the optimal policy  [§4.4]
    return reward + (gamma * phi_next - phi_prev)

Shared slot-filling policy §4.4 §5.3

Because every 20Q question has the same three-value slot, the paper shares one slot-filling network across questions, with the question index given as input §4.4 §5.3. The "index as input" detail is stated for shared policies in general §4.4; §5.3 does not describe how the index is encoded.

Simulator and task §5.1 §5.2

• Game. The agent asks yes/no questions and guesses a famous person. The user answers yes, no or "I don't know". The game ends on a correct guess, when no person in the database matches the hypothesis, after 100 steps, or after 10 guesses §5.2.
• Database. 100 famous people from Freebase, each with attributes from which 31 yes/no questions are built §5.2 tab. 1.
• User simulator. Uniform sampling of the target person §5.2. With probability 5% the simulator treats an attribute as unknown and answers "unknown" for it §5.2. Natural-language answers are sampled from the Switchboard Dialog Act corpus, mapped to yes, no and unknown tab. 2 §5.2.
• Rewards. Win +30, loss −30, wrong guess −5 §5.2. The paper gives no per-turn reward for ordinary questions.

Simulator tables

Q_a is the number of questions per attribute; they sum to 31 tab. 1.

The paper reports 508, 445 and 251 unique utterances for yes, no and unknown after filtering, and keeps their corpus frequencies so the simulator samples in the corpus proportions §5.2.

Hyperparameters

Stated in the paper unless marked otherwise.

Results

Author-reported. Setup: 20Q simulator with 100 people and 31 questions §5.2. Baseline: an LSTM slot tracker plus a DRQN policy trained separately §5.4. The paper notes that Hybrid-RL changes the reward, so average cumulative reward is not comparable and the paper reports win rate and average game length instead §5.4.

State-tracking precision / recall on 10,000 greedy trajectories §5.5:

tab. 4. Each cell is precision / recall.

Belief-state probes §5.6:

• Learning curves fig. 4: the win rate over training for the three systems. The paper says the baseline learns fastest early but plateaus, RL starts slowly, and Hybrid-RL converges faster than RL. No numeric values are given in the text.
• Retrieval fig. 5: for each learned state vector, the 5 nearest neighbours by cosine distance are retrieved, and the mismatch rate of their true latent states is measured per slot §5.6 eq. 12. The text says this error falls for better-trained models; no numeric values are given.

p_{\text{diff}}(s[k]) = E_{s_i}\!\left[\frac{\sum_{n=0}^{4} \mathbb{1}\big(N(b_i)[n][k] \neq s_i[k]\big)}{5}\right] \qquad [\text{eq. 12}]

Paper vs code

Code: NeuralDialog-DM by snakeztc (the first author), commit 80fd54f5b198b2c05ff5879850311dc3fc81afcd. The repository has no LICENSE file. Paths below are relative to the repository root. The commit does not contain the paper's main model: a search of all files, including notebooks, finds no LSTM, recurrent layer, hybrid or state-tracking term.

• Architecture. Paper: DRQN with an LSTM of size 256 §5.3 §3.2. Code: a feed-forward Keras network with two 128-unit ReLU layers and a linear output head DNNfqi.py.
• Dropout. Paper: 0.3 §5.3. Code: 0.2 DNNfqi.py.
• Hybrid labels. Paper: indicator reward and synthetic database transitions §4.3. Code: no label-based reward or term found; the reward comes from the simulator only BinarySimulator20q.py.
• Potential shaping. Paper: φ with P_max = 2 §4.4 §5.3. Code: no potential function found; the per-turn reward is a constant step penalty of −0.5 BinarySimulator20q.py BinarySimulator20q.py.
• Rewards. Paper: win +30, loss −30, wrong guess −5 §5.2. Code: win +10 and loss −10 BinarySimulator20q.py; wrong guess is scaled by the number of consistent people as (−10 − 10) / N × matches, where N = 100 BinarySimulator20q.py.
• Episode limit. Paper: 100 steps §5.2. Code: episode_cap = 30 BinarySimulator20q.py.
• Guess limit. Paper: 10 guesses §5.2. Code: no guess counter; an episode ends only on a correct guess or the turn cap BinarySimulator20q.py.
• Exploration. Paper: ε linear from 1 to 0.1 §5.3. Code: ε multiplied by 0.99 per episode, floor 0.2 binary_dqn.py binary_dqn.py.
• Update schedule. Paper: behavior network every 4 steps, target update C = 1000 §5.3. Code: one update every 32 environment steps with mini-batch 64 binary_dqn.py ExpQlearning.py. No separate target network is created: the bootstrap target is computed with the current network DNNfqi.py.
• Replay priority. Paper: prioritised replay (Schaul et al.) §3.1. Code: priority = min(|r|, 5) + 1 from the reward, sampled proportionally ExpQlearning.py ExpQlearning.py. This is reward-based, not TD-error-based.
• Double DQN. Paper: included §3.1. Code: the target takes the max over the same network, which is not double DQN DNNfqi.py.
• Optimizer. Paper: RMSProp §5.3. Code: RMSProp with gradient clipping at 1.0 and the library default learning rate DNNfqi.py.
• Training length and evaluation. Paper: 120,000 steps, evaluation every 5000 steps §5.3. Code: sample sizes go up to 15,000 steps, evaluation every 1000 binary_dqn.py. The 200-episode evaluation matches binary_dqn.py.
• Simulator data. Paper: 100 Freebase people and 31 questions §5.2. Code: data paths point to a local directory of the author config.py; the data files are not in the repository. The uniform sampling matches BinarySimulator20q.py. No 5% unknown-attribute rule was found.
• Experiment scripts. The repository has binary_dqn.py, wh_dqn.py, binary_online_fqi.py and online_fqi.py . None implements the DRQN in the paper.
• Language and API. The code is Python 2 (print statements) on the Keras 1 API (nb_epoch, init=) DNNfqi.py DNNfqi.py.

Conclusion: the released code is an earlier feed-forward DQN experiment on a similar simulator. It cannot reproduce Table 3 or Table 4. The paper's DRQN and Hybrid-RL results have no matching code in this repository.

Pitfalls

• The official code does not implement the paper's model. Any implementation should follow the paper's text, not the repository. Several numbers in §5.2–5.3 are not in the code, and the code's game rules differ (see Paper vs code).
• Equation 4 notation. It writes R̄(b,a) on the right-hand side, while eq. 5 defines the reward with a^h eq. 4 eq. 5. The mixture of a and a^h, and of A_h and A^h (eq. 6 vs §4.2), suggests a typo; read a as a^h.
• Potential shaping has a jump. With D = 100 entities and P_max = 2 (D is derived from §5.2), φ = 1.98 when one entity is consistent and φ = 0 when none are eq. 10 eq. 11. Moving to an inconsistent hypothesis therefore loses about 2 units of potential. This is intended as a penalty for mistakes §4.4, but it is a large, non-smooth term.
• Per-turn reward is missing. The paper gives the win, loss and wrong-guess rewards but no reward for ordinary turns §5.2. The code uses −0.5 per turn BinarySimulator20q.py. Choose this value deliberately.
• Hybrid reward scale. Eq. 5 adds the indicator 1(y = a^h) to the database reward. The relative scale and any weighting are not stated.
• Synthetic transitions cost database queries. For each real step the paper creates a tuple for every slot value in A^h, which has three values §4.3 §5.3. The number of queries per step is therefore three extra database calls.
• Missing optimisation details. Learning rate, mini-batch size, replay size, the length of the ε decay, prioritisation parameters, and the units of C are not stated §3.1 §5.3.
• Turn embedding. The mapping from the observation vector to the 30-dimensional turn embedding is not described §5.3.
• Bag-of-bigrams vocabulary. The vocabulary size and tokenisation are not stated §5.3.
• Single-domain evaluation. Only the 20Q simulator is used §5.1. The paper's own conclusion calls poor scalability and sample efficiency the main limitations, and says the models need many samples to converge §6.
• Simulator realism. The user answers come from SWDA dialog acts and a 5% unknown rule §5.2. Results depend on this simulator and say nothing about real users.
• Table 4 wording. The text says RL "aims for high precision" when it predicts unknown §5.5. The table shows RL unknown precision 0.21, while its yes and no precision is 1.00 and 0.95. The claim holds for yes and no, not for unknown.
• Baseline wins on learning speed. The text says the baseline learns fastest early §5.4 fig. 4. Its plateau is the paper's explanation for the end-to-end gains.
• Statistical reporting. No number of runs, seeds or variance is reported for Table 3 or Table 4 tab. 3 tab. 4. Treat the win-rate differences as single-run results.
• Table 3 setup. The table does not name its evaluation protocol. §5.3 describes 200 greedy episodes for the periodic evaluations §5.3; the paper does not confirm that Table 3 uses the same protocol.
• Regression under-specified. The l2 strength for the r² probe is not stated §5.6.
• Figure values. The learning-curve and retrieval-error figures have no numeric values in the text fig. 4 fig. 5. Read them from the figures only if needed.
• Source version. This card uses the arXiv v2 LaTeX source (updated 2016-09-15). Equation, table and figure numbers were counted from that source.

Lineage

• Builds on: DQN §3.1 (Mnih et al., 2015), double DQN and prioritised replay §3.1, DRQN §3.2 (Hausknecht and Stone, 2015), and Dyna-Q §4.3 (Sutton, 1990), which the paper contrasts with its own synthetic transitions. Reward shaping follows Ng et al. (1999) §4.4. The paper's related-work section cites these by author and year; arXiv ids are not in this wiki.
• Compared against: a modular baseline with an LSTM state tracker and a separately trained DRQN policy §5.4; the end-to-end network of Wen et al. (2016) is discussed in related work §2.
• Superseded by: not stated in this card.