NON-STATIONARY DELAYED BANDITS WITH INTERMEDIATE SIGNALS

1 . A method of selecting actions from a set of actions to be performed in an environment, the method comprising, at each time step in a sequence of a plurality of time steps:

maintaining count data, the count data specifying:

(i) for each action and for each intermediate signal in a discrete set of intermediate signals, a count of how many times the intermediate signal has been observed in response to the action being performed, and

(ii) for each intermediate signal, a count of rewards that have been received for time steps for which the intermediate signal has been observed in response to the action performed at the time step,

wherein each intermediate signal in the discrete set describes a corresponding state of the environment after an action has been performed but before the reward for the performed action has been received, and

wherein each reward is a numeric value that measures a quality of the action in response to which the intermediate signal was observed;

determining, from the count data and for each action, a respective current transition probability distribution that includes a respective current transition probability for each of the intermediate signals that represents an estimate of a current likelihood that the intermediate signal will be observed if the action is performed;

determining, from the count data and for each intermediate signal, a respective reward estimate that is an estimate of a reward that will be received as a result of the intermediate signal being observed;

determining, from the respective current transition probability distributions and the respective reward estimates, a respective action score for each action; and

selecting an action to be performed in the environment based on the respective action scores.

2 . The method of claim 1 , wherein the environment is a content item recommendation setting, wherein the actions correspond to content items, and wherein content items corresponding to selected actions are recommended to a user in the content item recommendation setting.

3 . The method of claim 1 , wherein selecting an action comprises:

selecting the action with the highest action score.

4 . The method of claim 1 , further comprising:

receiving an indication that an intermediate signal was observed in response to the selected action being performed; and

in response, updating the count data.

5 . The method of claim 1 , further comprising:

receiving a reward as a result of a previous intermediate signal that was observed at an earlier time step; and

in response, updating the count data.

6 . The method of claim 1 , wherein, for each action and for each intermediate signal in a discrete set of intermediate signals, the count of how many times the intermediate signal has been observed in response to the action being performed is:

a windowed count that counts how many times the intermediate signal has been observed in response to the action being performed during a recent time window that includes a fixed number of most recent time steps.

7 . The method of claim 6 , wherein determining, from the count data and for each action, a respective current transition probability distribution that includes a respective current transition probability for each of the intermediate signals comprises:

determining the respective current transition probability for each of the intermediate signals based on a ratio of (i) the windowed count that counts how many times the intermediate signal has been observed in response to the action being performed during the recent time window to (ii) a windowed count that counts how many times the action has been performed during the recent time window.

8 . The method of claim 1 , wherein, for each intermediate signal, the count of rewards that have been received as a result of the intermediate signal being observed is:

a reward count that counts the rewards received for the time steps the intermediate signal has been observed in response to the action being performed during a longer time window that does not include some or all of the most recent time steps in the recent time window.

9 . The method of claim 8 , wherein the count data further specifies:

for each intermediate signal, a delayed count of times that the intermediate signal has been observed during the longer time window that does not include some or all of the most recent time steps in the recent time window.

10 . The method of claim 9 , wherein determining, from the count data and for each intermediate signal, a respective reward estimate that is an estimate of a reward that will be received as a result of the intermediate signal being observed comprises:

determining the respective reward estimate based on a ratio of (i) the reward count for the intermediate signal to (ii) the delayed count for the intermediate signal.

11 . The method of claim 1 , wherein determining, from the respective current transition probability distributions and the respective reward estimates, a respective action score for each action comprises:

determining the respective action scores from the respective current transition probability distributions and the respective reward estimates using a stochastic bandit technique.

12 . A system comprising one or more computers and one or more storage devices storing instructions that when executed by the one or more computers cause the one or more computers to perform operations for selecting actions from a set of actions to be performed in an environment, the operations comprising, at each time step in a sequence of a plurality of time steps:

maintaining count data, the count data specifying:

(i) for each action and for each intermediate signal in a discrete set of intermediate signals, a count of how many times the intermediate signal has been observed in response to the action being performed, and

(ii) for each intermediate signal, a count of rewards that have been received for time steps for which the intermediate signal has been observed in response to the action performed at the time step,

wherein each intermediate signal in the discrete set describes a corresponding state of the environment after an action has been performed but before the reward for the performed action has been received, and

wherein each reward is a numeric value that measures a quality of the action in response to which the intermediate signal was observed;

determining, from the count data and for each action, a respective current transition probability distribution that includes a respective current transition probability for each of the intermediate signals that represents an estimate of a current likelihood that the intermediate signal will be observed if the action is performed;

determining, from the count data and for each intermediate signal, a respective reward estimate that is an estimate of a reward that will be received as a result of the intermediate signal being observed;

determining, from the respective current transition probability distributions and the respective reward estimates, a respective action score for each action; and

selecting an action to be performed in the environment based on the respective action scores.

13 . The system of claim 12 , wherein the environment is a content item recommendation setting, wherein the actions correspond to content items, and wherein content items corresponding to selected actions are recommended to a user in the content item recommendation setting.

14 . The system of claim 12 , wherein selecting an action comprises:

selecting the action with the highest action score.

15 . The system of claim 12 , the operations further comprising:

receiving an indication that an intermediate signal was observed in response to the selected action being performed; and

in response, updating the count data.

16 . The system of claim 12 , the operations further comprising:

receiving a reward that is associated with a previous intermediate signal that was observed at an earlier time step; and

in response, updating the count data.

17 . The system of claim 12 , wherein, for each action and for each intermediate signal in a discrete set of intermediate signals, the count of how many times the intermediate signal has been observed in response to the action being performed is:

a windowed count that counts how many times the intermediate signal has been observed in response to the action being performed during a recent time window that includes a fixed number of most recent time steps.

18 . The system of claim 17 , wherein determining, from the count data and for each action, a respective current transition probability distribution that includes a respective current transition probability for each of the intermediate signals comprises:

determining the respective current transition probability for each of the intermediate signals based on a ratio of (i) the windowed count that counts how many times the intermediate signal has been observed in response to the action being performed during the recent time window to (ii) a windowed count that counts how many times the action has been performed during the recent time window.

19 . The system of claim 12 , wherein, for each intermediate signal, the count of rewards that have been received as a result of the intermediate signal being observed is:

a reward count that counts the rewards received for the time steps the intermediate signal has been observed in response to the action being performed during a longer time window that does not include some or all of the most recent time steps in the recent time window.

20 . One or more non-transitory computer-readable storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations for selecting actions from a set of actions to be performed in an environment, the operations comprising, at each time step in a sequence of a plurality of time steps:

maintaining count data, the count data specifying:

(i) for each action and for each intermediate signal in a discrete set of intermediate signals, a count of how many times the intermediate signal has been observed in response to the action being performed, and

(ii) for each intermediate signal, a count of rewards that have been received for time steps for which the intermediate signal has been observed in response to the action performed at the time step,

wherein each intermediate signal in the discrete set describes a corresponding state of the environment after an action has been performed but before the reward for the performed action has been received, and

wherein each reward is a numeric value that measures a quality of the action in response to which the intermediate signal was observed;

determining, from the count data and for each action, a respective current transition probability distribution that includes a respective current transition probability for each of the intermediate signals that represents an estimate of a current likelihood that the intermediate signal will be observed if the action is performed;

determining, from the count data and for each intermediate signal, a respective reward estimate that is an estimate of a reward that will be received as a result of the intermediate signal being observed;

determining, from the respective current transition probability distributions and the respective reward estimates, a respective action score for each action; and

selecting an action to be performed in the environment based on the respective action scores.