MODEL-FREE CONTROL FOR REINFORCEMENT LEARNING AGENTS

1 . A method for selecting an action from a predetermined set of actions to be performed by an agent interacting with an environment, the method comprising:

maintaining return data that maps each of a plurality observation-action pairs to a respective return,

wherein the action in each observation-action pair is an action that was performed by the agent in response to the observation in the observation-action pair, and

wherein the respective return mapped to by each of the observation-action pairs is a return that resulted from the agent performing the action in the observation-action pair in response to the observation in the observation-action pair;

receiving a current observation characterizing a current state of the environment;

determining whether the current observation matches any of the observations identified in the return data; and

in response to determining that the current observation matches a first observation identified in the return data, selecting an action to be performed by the agent in response to the current observation using the returns mapped to by observation-action pairs in the return data that include the first observation.

2 . The method of claim 1 , wherein selecting the action to be performed by the agent comprises:

selecting an action that, according to the return data, resulted in a highest return of any action when performed by the agent in response to the first observation.

3 . The method of claim 1 , wherein selecting the action to be performed by the agent comprises:

selecting an action that, according to the return data, resulted in a highest return of any action when performed by the agent in response to the first observation with probability 1-ϵ; and

selecting an action randomly from the predetermined set of actions with probability ϵ.

4 . The method of claim 1 , further comprising:

in response to determining that the current observation does not match any of the observations identified in the return data:

determining a feature representation of the current observation;

determining the k observations identified in the return data that have feature representations that are closest to the feature representation of the current observation, wherein k is an integer greater than one;

determining a respective estimated return for each of a plurality of actions in the predetermined set of actions from returns mapped to by observation-action pairs in the return data that include the action and any one of the k observations; and

selecting the action to be performed by the agent in response to the current observation using the estimated returns.

5 . The method of claim 4 , wherein determining a respective estimated return comprises, for each of the plurality of actions:

determining an average of the returns mapped to by observation-action pairs in the return data that include the action and any one of the k observations.

6 . The method of claim 4 , wherein selecting the action to be performed by the agent comprises:

selecting an action from the plurality of actions that has the highest estimated return.

7 . The method of claim 4 , wherein selecting the action to be performed by the agent comprises:

selecting an action from the plurality of actions that has the highest estimated return with probability 1-ϵ; and

selecting an action randomly from the predetermined set of actions with probability ϵ.

8 . The method of claim 4 , wherein determining the k observations identified in the return data that have feature representations that are closest to the feature representation of the current observation comprises:

determining the k observations identified in the return data that have feature representations that have a smallest Euclidian distance to the feature representation of the current observation.

9 . The method of claim 4 , wherein the feature representation of the current observation is the current observation.

10 . The method of claim 4 , wherein determining the feature representation of the current observation comprises:

projecting the current observation into a smaller-dimensional space.

11 . The method of claim 10 , wherein projecting the current observation into the smaller-dimensional space comprises applying a random projection matrix to the current observation.

12 . The method of claim 4 , wherein determining the feature representation of the current observation comprises:

processing the current observation using a variational auto-encoder model to generate a latent representation of the current observation; and

using the latent representation of the current observation as the feature representation of the current observation.

13 . The method of claim 1 , further comprising:

receiving a new return resulting from the agent performing the selected action in response to the current observation; and

updating the return data using the new return.

14 . The method of claim 13 , wherein, when the current observation matches a first observation identified in the return data, updating the return data using the new return comprises:

determining whether the new return is larger than an existing return resulting from performing the selected action in response to the first observation according to the return data; and

when the new return is larger than the existing return, replacing the existing return with the new return in the return data.

15 . The method of claim 13 , wherein, when the current observation does not match a first observation identified in the return data, updating the return data using the new return comprises:

updating the return data to map a current observation—selected action pair to the new return.

16 . The method of claim 1 , further comprising:

determining that a number of mappings in the return data has reached a maximum size and, in response, removing a least recently updated mapping from the return data.

17 . The method of claim 1 , further comprising:

initializing the return data with initial mappings by randomly selecting actions to be performed by the agent until each action in the predetermined set of actions has been performed more than a threshold number of times.

18 . The method of claim 1 , wherein the returns are discounted sums of rewards received by the agent in response to performing actions.

19 . 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 an action from a predetermined set of actions to be performed by an agent interacting with an environment, the operations comprising:

maintaining return data that maps each of a plurality observation-action pairs to a respective return,

wherein the action in each observation-action pair is an action that was performed by the agent in response to the observation in the observation-action pair, and

wherein the respective return mapped to by each of the observation-action pairs is a return that resulted from the agent performing the action in the observation-action pair in response to the observation in the observation-action pair;

receiving a current observation characterizing a current state of the environment;

determining whether the current observation matches any of the observations identified in the return data; and

in response to determining that the current observation matches a first observation identified in the return data, selecting an action to be performed by the agent in response to the current observation using the returns mapped to by observation-action pairs in the return data that include the first observation.

20 . A computer storage medium encoded with instructions that, when executed by one or more computers, cause the one or more computers to perform operations for selecting an action from a predetermined set of actions to be performed by an agent interacting with an environment, the operations comprising:

maintaining return data that maps each of a plurality observation-action pairs to a respective return,

wherein the action in each observation-action pair is an action that was performed by the agent in response to the observation in the observation-action pair, and

wherein the respective return mapped to by each of the observation-action pairs is a return that resulted from the agent performing the action in the observation-action pair in response to the observation in the observation-action pair;

receiving a current observation characterizing a current state of the environment;

determining whether the current observation matches any of the observations identified in the return data; and

in response to determining that the current observation matches a first observation identified in the return data, selecting an action to be performed by the agent in response to the current observation using the returns mapped to by observation-action pairs in the return data that include the first observation.