Method and system for configuring form filling application to minimize form filling effort

1. A method for generating an optimal policy for configuring a form filling application that assists a user to fill one or more slots of a form, the method comprising:

defining a plurality of actions of an agent, wherein each agent action specifies one or more slots of the form for the user to fill and specifies one or more user interfaces for the user to use to fill the one or more slots specified by the agent action;

defining a state model of a process to fill one or more slots of the form, wherein each state of the state model includes information that is accessible to the agent at a certain point in time during the form filling process;

defining a q-function as a mapping from state-agent action pairs to values, wherein each of the values is defined as an average return for the state-agent action pair;

initializing the q-function;

simulating an episode of filling out the form, wherein simulating the episode comprises:

simulating, at time index i, an agent action that is performed from a state at time index i, the state and simulated agent action forming a state-agent action pair;

simulating, at time index i, a user action that is performed in response to the simulated agent action, the simulated agent action and the user action causing a transition from the state at time index i to a state at time index i+1;

simulating, at time index i+1, a reward that reflects a measure of user effort that is associated with the user performing the simulated user action on the user interface specified by the simulated agent action; and

if the state at time index i+1 is not a terminal state, repeating the simulation of the agent action, the user action and the reward from the state at time index i+1, otherwise if the state at time index i+1 is a terminal state, concluding the simulation of the episode;

for each state-agent action pair that is simulated in the episode, calculating a return of the state-agent action pair based on the rewards recorded from the simulation of the episode;

updating the q-function based on one or more of the returns calculated during the simulation of the episode; and

repeating the process of simulating an episode, calculating returns, and updating the q-function until values of the q-function sufficiently converge,

wherein the optimal policy for configuring the form filling application that assists the user to fill one or more slots of the form comprises a greedy policy, in which, for a given state, an agent action is selected that maximizes the q-function for the given state.

2. The method of claim 1 , wherein at least one of the states specifies one or more of information regarding a client device of the user or an interface type preferred by the user, wherein the interface type includes one or more of chat interface or a web-based interface.

3. The method of claim 1 , wherein the agent action that is simulated, at time index i, during the simulation of the episode is chosen in accordance with an ε-greedy policy, wherein, with a probability of ε, the ε-greedy policy randomly selects an agent action from a plurality of possible agent actions, and with a probability of 1−ε, the ε-greedy policy selects an agent action in accordance with the greedy policy.

4. The method of claim 1 , wherein simulating the one or more user actions, at time index i, comprises drawing a user action from a probability distribution.

5. The method of claim 4 , wherein the conditional probability distribution is defined as the probability of a user action, conditioned upon at least (i) the one or more slots selected by the simulated agent action, and (ii) the user interface selected by the simulated agent action.

6. The method of claim 1 , wherein simulating the reward, at time index i+1, comprises drawing a reward from a conditional probability distribution.

7. The method of claim 6 , wherein the conditional probability distribution is defined as the probability of a reward, conditioned upon at least (i) the one or more slots selected by the simulated agent action and (ii) the user interface selected by the simulated agent action.

8. A method for generating an optimal policy for configuring a form filling application that assists a user to fill one or more slots of a form, the method comprising:

defining a plurality of actions of an agent, wherein each agent action specifies one or more slots of the form for the user to fill and specifies one or more user interfaces for the user to use to fill the one or more slots specified by the agent action;

defining a state model of a process to fill one or more slots of the form, wherein each state of the state model includes information that is accessible to the agent at a certain point in time during the form filling process;

defining a q-function as a mapping from state-agent action pairs to values, wherein each of the values is defined as an average return for a corresponding state-agent action pair;

initializing the q-function;

simulating an episode of filling out the form, wherein simulating the episode comprises:

simulating, at time index i, an agent action that is performed from a state, the state and simulated agent action forming a state-agent action pair;

simulating, at time index i, a slot value for a slot selected by the agent action;

simulating, at time index i, one or more user actions that are performed so as to transition from the simulated agent action at time index i to a state at time index i+1 that is specified by the simulated slot value;

simulating, at time index i+1, a reward that reflects a measure of user effort that is associated with a user performing the one or more simulated user actions; and

if the state at time index i+1 is not a terminal state, incrementing the time index i, and repeating the simulation of the agent action, the slot value, the user action and the reward from the state at time index i+1, otherwise if the state at time index i+1 is a terminal state, concluding the simulation of the episode;

for each state-agent action pair that is simulated in the episode, computing a return of the state-agent action pair based on the rewards simulated during the episode;

updating the q-function based on one or more of the computed returns; and

repeating the process of simulating an episode, computing returns, and updating the q-function until values of the q-function sufficiently converge,

wherein the optimal policy for configuring the form filling application that assists the user to fill one or more slots of the form comprises a greedy policy, in which, for a given state, an agent action is selected that maximizes the q-function for the given state.

9. The method of claim 8 , wherein at least one of the states specifies one or more of information regarding a client device of the user or an interface type preferred by the user, wherein the interface type includes one or more of chat interface or a web-based interface.

10. The method of claim 8 , wherein the agent action that is simulated, at time index i, during the simulation of the episode is chosen in accordance with an ε-greedy policy, wherein, with a probability of ε, the agent randomly selects an agent action from a plurality of possible agent actions, and with a probability of 1−ε, the agent selects an agent action in accordance with the greedy policy.

11. The method of claim 8 , wherein simulating the slot value, at time index i, comprises drawing a slot value from a conditional probability distribution.

12. The method of claim 11 , wherein the conditional probability distribution is defined as the probability of a slot value, conditioned upon at least the slot selected by the simulated agent action.

13. The method of claim 8 , wherein simulating the one or more user actions, at time index i, comprises inferring a user action that, if performed on the user interface selected by the simulated agent action at time index i, would result in the slot value drawn at time index i.

14. The method of claim 8 , wherein simulating the one or more user actions, at time index i, comprises drawing a user action from a probability distribution that, if performed on the user interface selected by the simulated agent action at time index i, would result in the slot value drawn at time index i.

15. The method of claim 14 , wherein the conditional probability distribution is defined as the probability of a user action, conditioned upon at least (i) the one or more slots selected by the simulated agent action, (ii) the user interface selected by the simulated agent action, and (iii) the slot value drawn at time index i.

16. The method of claim 8 , wherein simulating the reward, at time index i+1, comprises drawing a reward from a conditional probability distribution.

17. The method of claim 16 , wherein the conditional probability distribution is defined as the probability of a reward, conditioned upon at least (i) the one or more slots selected by the simulated agent action and (ii) the user interface selected by the simulated agent action.

18. A system for generating an optimal policy for configuring a form filling application that assists a user to fill one or more slots of a form, the system comprising a processor configured to perform the steps of:

defining a plurality of actions of an agent, wherein each agent action specifies one or more slots of the form for the user to fill and specifies one or more user interfaces for the user to use to fill the one or more slots specified by the agent action;

defining a state model of a process to fill one or more slots of the form, wherein each state of the state model includes information that is accessible to the agent at a certain point in time during the form filling process;

defining a q-function as a mapping from state-agent action pairs to values, wherein each of the values is defined as an average return for a corresponding state-agent action pair;

initializing the q-function;

simulating an episode of filling out the form, wherein simulating the episode comprises:

simulating, at time index i, an agent action that is performed from a state, the state and simulated agent action forming a state-agent action pair;

simulating, at time index i, a slot value for a slot selected by the agent action;

simulating, at time index i, one or more user actions that are performed so as to transition from the simulated agent action at time index i to a state at time index i+1 that is specified by the simulated slot value;

simulating, at time index i+1, a reward that reflects a measure of user effort that is associated with the user performing the one or more simulated user actions; and

if the state at time index i+1 is not a terminal state, incrementing the time index i, and repeating the simulation of the agent action, the slot value, the user action and the reward from the state at time index i+1;

for each state-agent action pair that is simulated in the episode, computing a return of the state-agent action pair based on the rewards simulated during the episode;

updating the q-function based on one or more of the computed returns; and

repeating the process of simulating an episode, computing returns, and updating the q-function until values of the q-function sufficiently converge,

wherein the optimal policy for configuring the form filling application that assists the user to fill one or more slots of the form comprises a greedy policy, in which, for a given state, an agent action is selected that maximizes the q-function for the given state.

19. The system of claim 18 , wherein simulating the slot value, at time index i, comprises drawing a slot value from a conditional probability distribution.

20. The system of claim 19 , wherein the conditional probability distribution is defined as the probability of a slot value, conditioned upon at least the slot selected by the simulated agent action.