We formulate dialogue generation as a partially observable Markov decision process (POMDP) [1]}, with a state that consists of known and unknown context information about the task.
Let \(c_h\in \mathcal {C}^{(h)}\)  denote the hidden context for the task, and let \(c_o\in \mathcal {C}^{(o)}\)  denote the observed context. For instance, in a flight booking task, a table of available flights might correspond to \(c_o\) , while the particular flight that the human wants to book, which is unknown to the agent, corresponds to \(c_h\) .
Note that the reward, which requires booking the right flight, depends on both hidden and observed contexts. We can define such an environment as a POMDP \(\mathcal {M} = (\mathcal {S}, \mathcal {A}, \mathcal {O}, \mathcal {T}, \mathcal {Z}, \mu _0, \mathcal {R}, \gamma )\) . We denote a conversation \(\tau \)  as \(\tau :=\lbrace a_0,e_0,...,a_{T}\rbrace \) , where \(T\)  denotes the number of turns in a conversation and \(a_t\)  and \(e_t\)  represent utterances (strings of tokens) from the dialogue agent (\(a_t\) ) and the human (\(e_t\) ) at the \(t\) -th turn, respectively. We additionally use \(\tau _{<t}\)  to denote conversation history up to the \(t\) -th turn.
We can represent the underlying POMDP state \(s_t \in \mathcal {S}\)  as the concatenation of both of the contexts and the previous conversation history \(s_t := \lbrace c_h, c_o, \tau _{<t}\rbrace  = \lbrace c_h, c_o, a_0, e_0,..., a_{t-1}, e_{t-1}\rbrace \) . However, we only observe the last two elements of the state tuple, such that our observation \(o_t\in \mathcal {O}\)  at the \(t\) -th conversation turn is \(o_t= \lbrace c_o, \tau _{<t}\rbrace \) .
An action \(a_t \in \mathcal {A}\)  is the agent's response to the current state \(s_t\) . Given our definition of the state, the full conversation in a dialogue can be conveniently represented by the last observation and action, \(\lbrace o_T,a_T\rbrace \) . An agent \(\pi : \mathcal {O}\rightarrow \mathcal {P}(\mathcal {A})\)  maps observations to sets of probability measures over the action space \(\mathcal {P}(\cdot )\) . A transition function \(\mathcal {T}(\cdot |s_t, a_t)\) , represents a distribution over the human's utterances, returning \(s_{t+1}\)  as the state at turn \(t+1\) .
We only consider the sparse reward setting with \(r_T=R(s_T,a_T)\in \lbrace 0, 1\rbrace \)  denoting task completion, and \(r_t=0\) , \(\forall t<T\) . Our final reward is therefore dependent on both the context and the dialogue: \(R(s_T,a_T)=R(\tau , c_h, c_o)\) , where the context \(\lbrace c_o, c_h\rbrace \)  is randomly sampled for each dialogue from some initial distribution \(\mu _0\) .
