Gated linear contextual bandits

A method of selecting an action from a set of actions to be performed in response to each context in a sequence of contexts, the method comprising:

• maintaining data specifying a respective tree of gated linear networks corresponding to each action of the set of actions, wherein each tree of gated linear networks is collectively configured to predict a respective probability for each of a plurality of bins of a range of reward values, wherein the respective probability for each bin represents a likelihood that a reward that falls in the bin will be received if the corresponding action is performed in response to an input context, and wherein each gated linear network comprises a plurality of layers, each layer comprising one or more neurons, wherein each neuron in each layer after the first layer is configured to receive (i) the input context and (ii) predictions from neurons in a previous layer and to (iii) apply a gating function to the input context to select a weight vector and (iv) generate as output a geometric mixture of the predictions from the neurons in the previous layer based on the selected weight vector;
• for each context in the sequence of contexts:
• for each action, processing the context using the tree of gated linear networks corresponding to the action to generate a respective probability for each of the plurality of bins of the range of reward values;
• for each action, generating an action score for the action from at least the respective probabilities, comprising:
• computing a pseudo-count for the action, the computing the pseudo-count comprises determining an overlap between (i) a signature of the context across the gating functions of the neurons in the gated linear networks in the tree of gated linear networks for the action and (ii) signatures of the context across the gating functions of the neurons in the gated linear networks in the tree of gated linear networks for any earlier contexts in the sequence for which the action was selected as the action to be performed in response to the earlier context, wherein the signature of a context refers to the outputs of the gating functions of the neurons in the gated linear networks in the tree of gated linear networks for the action generated by processing the context;
• and
• selecting the action to be performed in response to the context based on the action scores.

A system comprising one or more computers and one or more storage devices storing instructions that when executed by one or more computers cause the one or more computers to perform operations for selecting an action from a set of actions to be performed in response to each context in a sequence of contexts, the operations comprising:

• maintaining data specifying a respective gated linear network corresponding to each action of the set of actions, wherein each gated linear network is configured to predict a probability that a reward will be received if the corresponding action is performed in response to an input context, and wherein each gated linear network comprises a plurality of layers, each layer comprising one or more neurons, wherein each neuron in each layer after the first layer is configured to receive (i) the input context and (ii) predictions from neurons in a previous layer and to (iii) apply a gating function to the input context to select a weight vector and (iv) generate as output a geometric mixture of the predictions from the neurons in the previous layer based on the selected weight vector;
• for each context in the sequence of contexts:
• for each action, processing the context using the gated linear network corresponding to the action to generate a predicted probability;
• for each action, generating an action score for the action from at least the predicted probability, comprising:
• computing a pseudo-count for the action, wherein computing the pseudo-count comprises determining an overlap between (i) a signature of the context across the gating functions of the neurons in the gated linear network for the action and (ii) signatures of any earlier contexts in the sequence for which the action was selected as the action to be performed in response to the earlier context, wherein the signature of the context characterizes outputs of the gating functions of the neurons in the gated linear network corresponding to the action generated by processing the context;
• and
• generating the action score from the predicted probability for the action and the pseudo-count for the action;
• and
• selecting the action to be performed in response to the context based on the action scores.