Online temporal difference learning from incomplete customer interaction histories

• US 8,914,314 B2
• Filed: 10/18/2012
• Issued: 12/16/2014
• Est. Priority Date: 09/28/2011
• Status: Active Grant

• Current Assignee: NICE Systems Technologies UK Limited (Nice Ltd)
• Original Assignee: NICE Systems Technologies UK Limited (Nice Ltd)
• Inventors: Newnham, Leonard Michael, McFall, Jason Derek, Barker, David J, Silver, David
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Misir, Dave
• Application Number:
  US13/655,298
• Publication Number:
  US 20130110750A1
• Time in Patent Office: 789 Days
• Field of Search: 706/12, 706/52
• US Class Current: 706/12
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/04 Inference or reasoning models

Abstract

In one embodiment, an indication that a decision has been requested, selected, or applied with respect to one or more users may be obtained. After the indication that a decision that has been requested, selected, or applied is obtained, a value function may be updated, where the value function approximates an expected reward associated with the one or more users over time since the decision has been requested, selected, or applied with respect to the one or more users. The value function may be updated by performing or providing one or more updates to the value function, where a time at which each of the one or more updates is performed or provided is independent of activity of the one or more users.

Claims

1. A computer implemented method, comprising:

obtaining an indication that a decision has been requested, selected, or applied with respect to one or more users; and

after obtaining the indication that a decision that has been requested, selected, or applied, updating a time dependent value function, including performing or providing one or more updates to the time dependent value function, wherein a time at which each of the one or more updates is performed or provided is independent of activity of the one or more users;

wherein the time dependent value function approximates an expected reward as a function of one or more time based variables corresponding to one or more time based values, the expected reward being associated with the one or more users, at least one of the time based variables indicates an elapsed time since a prior or last user event pertaining to at least one of the one or more users, the one or more updates to the value function indicate update(s) to one or more weights associated with one or more parameters of the time dependent value function, and the update(s) to the one or more weights include a modification or replacement value for each of the one or more weights.

2. The computer implemented method of claim 1, wherein a time at which each of the one or more updates is performed or provided is independent of activity of any of a plurality of users.

3. The method of claim 1, wherein performing or providing one or more updates to the value function comprises:

performing a temporal difference update.

4. The computer-implemented method of claim 1, wherein performing or providing one or more updates to the time dependent value function comprises performing or providing one or more updates prior to obtaining an indication that a subsequent decision has been requested, selected, or applied with respect to the one or more users.

5. The computer-implemented method of claim 1, wherein performing or providing one or more updates comprises performing or providing an update to the time dependent value function at a predetermined time, or after expiration of a predetermined period of time, after a particular event.

6. The computer-implemented method of claim 5, wherein the particular event comprises selection of an action in response to the indication that a decision has been requested.

7. The computer-implemented method of claim 1, wherein updating the time dependent value function is performed via one or more update functions derived from the time dependent value function.

8. The method of claim 1, wherein performing or providing one or more updates to the value function comprises:

performing a product based temporal difference update.

9. The method of claim 1, wherein the time dependent value function is defined as a product of two terms.

10. The computer-implemented method of claim 1, wherein performing or providing one or more updates to the time dependent value function is performed based, at least in part, upon one or more time based values.

11. The computer-implemented method of claim 10, wherein the one or more time based values indicate a time since the decision was requested, selected, or applied and/or a time since a prior or last user event pertaining to at least one of the one or more users.

12. The computer-implemented method of claim 1, wherein performing or providing one or more updates to the time dependent value function comprises performing or providing one or more updates at time(s) that are determined based, at least in part, upon one or more time based values.

13. The computer-implemented method of claim 12, wherein the one or more time based values indicate a time since the decision was requested, selected, or applied and/or a time since a prior or last user event pertaining to at least one of the one or more users.

14. The computer-implemented method of claim 1, further comprising:

generating a schedule for performing or providing the one or more updates based, at least in part, upon one or more time based values.

15. The computer-implemented method of claim 1, wherein performing or providing one or more updates to the time dependent value function comprises performing or providing one or more updates at times or according to intervals determined according to an exponential distribution.

16. The computer-implemented method of claim 15, wherein the exponential distribution comprises a random component.

17. The computer-implemented method of claim 1, further comprising:

selecting at least one of a plurality of actions as a decision with respect to the one or more users, wherein selecting at least one of the plurality of actions as the decision with respect to the one or more users is performed, at least in part, by applying the time dependent value function to a user state pertaining to the one or more users.

18. The computer-implemented method of claim 1, further comprising:

obtaining an indication of a decision request pertaining to the one or more users;

receiving, obtaining, accessing or constructing a user state pertaining to the one or more users;

scoring a plurality of actions according to the time dependent value function based, at least in part, upon the user state;

applying a policy to identify one of the scored actions as a decision; and

providing an indication of the decision or applying the decision to the one or more users.

19. The computer-implemented method of claim 18, the decision request being activated independent of activity of the at least one user.

20. The computer-implemented method of claim 1, further comprising:

scheduling one or more updates to the time dependent value function.

21. The computer-implemented method of claim 1, wherein performing or providing one or more updates to the time dependent value function comprises:

performing or providing a terminal update to the value function, the terminal update being associated with a timeout condition.

22. The computer-implemented method of claim 1, wherein performing or providing the one or more updates comprises:

performing or providing a plurality of updates according to a fixed interval.

23. The computer-implemented method of claim 1, wherein performing or providing the one or more updates comprises:

performing or providing a plurality of updates according to a varying interval.

24. The computer-implemented method of claim 1, wherein the time dependent value function is associated with a computing device, and wherein performing or providing the one or more updates comprises:

transmitting the one or more updates to one or more other computing devices.

25. The computer-implemented method of claim 1, wherein the time dependent value function is associated with a computing device, the method further comprising:

receiving a second set of one or more updates pertaining to the time dependent value function, the second set of one or more updates comprising modifications to or replacement values for one or more weights associated with one or more parameters of the time dependent value function.

26. A computer-implemented method comprising:

obtaining an indication that a decision has been requested, selected, or applied with respect to one or more users; and

after obtaining the indication that a decision that has been requested, selected, or applied, updating a time dependent value function, including performing or providing one or more updates to the time dependent value function, wherein a time at which each of the one or more updates is performed or provided is independent of activity of the one or more users, wherein the time dependent value function is defined as a product of two terms;

wherein the one or more updates to the value function indicate update(s) to one or more weights associated with one or more parameters of the time dependent value function, and the update(s) to the one or more weights include a modification or replacement value for each of the one or more weights,

wherein each of the two terms operates on at least a subset of a set of weights, the set of weights corresponding to parameters of the time dependent value function.

27. A computer-implemented method comprising:

obtaining an indication that a decision has been requested, selected, or applied with respect to one or more users; and

after obtaining the indication that a decision that has been requested, selected, or applied, updating a time dependent value function, including performing or providing one or more updates to the time dependent value function, wherein a time at which each of the one or more updates is performed or provided is independent of activity of the one or more users, wherein the time dependent value function is defined as a product of two terms, wherein one of the two terms is a time-varying function,

wherein the one or more updates to the value function indicate update(s) to one or more weights associated with one or more parameters of the time dependent value function, and the update(s) to the one or more weights include a modification or replacement value for each of the one or more weights.

28. The computer-implemented method of claim 27, wherein the time-varying function is a decaying exponential or decreasing sigmoid.

29. A computer-implemented method comprising:

obtaining an indication that a decision has been requested, selected, or applied with respect to one or more users; and

after obtaining the indication that a decision that has been requested, selected, or applied, updating a time dependent value function, including performing or providing one or more updates to the time dependent value function, wherein a time, at which each of the one or more updates is performed or provided is independent of activity of the one or more users;

wherein the one or more updates to the value function indicate update(s) to one or more weights associated with one or more parameters of the time dependent value function, and the update(s) to the one or more weights include a modification or replacement value for each of the one or more weights,

wherein the time dependent value function is defined as a product of a first function and a second function, the first function operating on at least a first subset of a set of weights, the second function operating on at least a second subset of the set of weights, the set of weights corresponding to parameters of the time dependent value function.

30. The computer-implemented method of claim 29, wherein performing or providing one or more updates to the time dependent value function comprises:

applying a first update function to perform or provide one or more updates to the first subset of the set of weights; and

applying a second update function to perform or provide one or more updates to the second subset of the set of weights.

31. The computer-implemented method of claim 29, wherein the first subset of the set of weights corresponds to a first subset of the parameters, and wherein the second subset of the set of weights corresponds to a second subset of the parameters, wherein the first subset of the parameters and the second subset of the parameters are mutually exclusive.

32. The computer-implemented method of claim 29, wherein the first function is a time-varying function, and wherein the first subset of the set of weights corresponds to a first subset of the parameters, each of the first subset of the parameters being a parameter that is likely to change over time after the decision was requested, selected, or applied.

33. The computer-implemented method of claim 29, wherein the first function is a time-varying function and wherein the second function is a linear function.

34. The computer-implemented method of claim 29, wherein the first function is a time-varying function, and wherein the first subset of the set of weights corresponds to a first subset of the parameters, at least one of the first subset of the parameters being a parameter that corresponds to and/or represents an elapsed time since the decision was requested, selected, or applied.

35. The computer-implemented method of claim 29, wherein the first function is a time-varying function, and wherein the first subset of the set of weights corresponds to a first subset of the parameters, at least one of the first subset of the parameters being a parameter that corresponds to and/or represents a time since a prior or last user event pertaining to at least one of the one or more users.

36. A computer-implemented method comprising:

obtaining an indication that a decision has been requested, selected, or applied with respect to one or more users;

after obtaining the indication that a decision that has been requested, selected, or applied, updating a time dependent value function, including performing or providing one or more updates to the time dependent value function, wherein a time at which each of the one or more updates is performed or provided is independent of activity of the one or more users, wherein the one or more updates to the value function indicate update(s) to one or more weights associated with one or more parameters of the time dependent value function, and the update(s) to the one or more weights include a modification or replacement value for each of the one or more weights,

scheduling one or more updates to the time dependent value function,

obtaining an indication that a subsequent decision pertaining to the at least one user is requested, selected, or applied; and

after obtaining the indication that the subsequent decision pertaining to the at least one user is requested, selected, or applied, cancelling scheduled updates to the time dependent value function that have not yet been performed.

37. A computer implemented method comprising:

obtaining an indication that a decision has been requested, selected, or applied with respect to one or more users; and

after obtaining the indication that a decision that has been requested, selected, or applied, updating a time dependent value function, including performing or providing one or more updates to the time dependent value function, wherein a time at which each of the one or more updates is performed or provided is independent of activity of the one or more users;

wherein the time dependent value function approximates an expected reward as a function of one or more time based variables corresponding to one or more time based values, the expected reward being associated with the one or more users, wherein at least one of the time based variables indicates an elapsed time since a prior or last user event pertaining to at least one of the one or more users,

wherein the one or more updates to the value function indicate update(s) to one or more weights associated with one or more parameters of the time dependent value function, and the updates to the one or more weights include a modification or replacement value for each of the one or more weights.