Fast exploration and learning of latent graph models

1 . A method performed by one or more computers, wherein the method comprises:

obtaining experience data generated as a result of controlling an agent in an environment to perform a sequence of one or more actions from a possible set of actions, each action being performed in response to receiving a respective observation characterizing a respective state of the environment;

using the experience data to update a visitation count for each of one or more state-action pairs, wherein each state-action pair represents a respective state of the environment and a respective action performed by the agent; and

performing an environment exploration step to explore the environment, the performing comprising:

computing a utility measure for each of the one or more state-action pairs, wherein computing the utility measure comprises evaluating a closed form utility function using at least the updated visitation counts;

determining, based on the utility measures, a sequence of one or more planned actions that have an information gain that satisfies a threshold; and

controlling the agent to perform the sequence of one or more planned actions to cause the environment to transition from a state characterized by a last observation received after a last action in the experience data into a different state.

2 . The method of claim 1 , wherein determining the sequence of one or more planned actions comprises:

selecting, from all state-action pairs that includes a first node representing a first state characterized by a first last observation, a selected state-action pair that has a highest utility measure; and

using an action included in the selected state-action pair as one single planned action.

3 . The method of claim 1 , wherein determining the sequence of one or more planned actions comprises:

using a reinforcement learning technique to generate an action selection policy for a second node representing a second state characterized by a second last observation; and

using the action selection policy to select a sequence of multiple planned actions.

4 . The method of claim 3 , wherein the reinforcement learning technique comprises a value iteration technique that maximizes a total utility measure of actions selected by the action selection policy.

5 . The method of claim 1 , further comprising, at each of multiple environment exploration steps:

obtaining updated experience data generated as a result of controlling the agent to perform the sequence of one or more planned actions; and

using the updated experience data to update the visitation count for each of one or more state-action pairs.

6 . The method of claim 1 , wherein the information gain of the sequence of one or more planned actions comprises a combination of utility measures of the planned actions included in the sequence.

7 . The method of claim 1 , wherein the sequence of one or more actions comprise one or more randomly selected actions from the possible set of actions.

8 . The method of claim 1 , wherein the agent comprises a mechanical agent and the environment is a real-world environment.

9 . The method of claim 1 , wherein the agent comprises a computer program and the environment is a simulated environment.

10 . A method performed by one or more computers for exploring an environment being interacted with by an agent, wherein the method comprises:

computing a utility measure for each of one or more state-action pairs in a representation of the environment based on evaluating a closed form utility function, wherein each state-action pair represents a respective state of the environment and a respective action performed by the agent;

determining, based on the utility measures, a sequence of one or more planned actions that have an information gain that satisfies a threshold;

controlling the agent to perform the sequence of one or more planned actions to cause the environment to transition into one or more different states;

obtaining updated experience data generated as a result of controlling the agent to perform the sequence of one or more planned actions; and

using the updated experience data to update the representation of the environment.

11 . The method of claim 10 , wherein determining the sequence of one or more planned actions comprises:

selecting, from all state-action pairs that includes a first node representing a first state characterized by a first last observation, a selected state-action pair that has a highest utility measure; and

using an action included in the selected state-action pair as one single planned action.

12 . The method of claim 10 , wherein determining the sequence of one or more planned actions comprises:

using a reinforcement learning technique to generate an action selection policy for a second node representing a second state characterized by a second last observation; and

using the action selection policy to select a sequence of multiple planned actions.

13 . The method of claim 12 , wherein the reinforcement learning technique comprises a value iteration technique that maximizes a total utility measure of actions selected by the action selection policy.

14 . The method of claim 10 , further comprising, at each of multiple environment exploration steps:

obtaining updated experience data generated as a result of controlling the agent to perform the sequence of one or more planned actions; and

using the updated experience data to update a visitation count for each of one or more state-action pairs.

15 . The method of claim 10 , wherein the information gain of the sequence of one or more planned actions comprises a combination of utility measures of the planned actions included in the sequence.

16 . The method of claim 10 , wherein the sequence of one or more actions comprise one or more randomly selected actions from a possible set of actions.

17 . A method performed by one or more computers, wherein the method comprises:

performing one or more environment exploration steps to update a representation of an environment being interacted with by an agent, comprising, at each of the one or more environment exploration steps:

computing a utility measure for each of one or more state-action pairs in the representation of an environment based on evaluating a closed form utility function, wherein each state-action pair represents a respective state of the environment and a respective action performed by the agent;

determining, based on the utility measures, a sequence of one or more planned actions that have an information gain that satisfies a threshold;

controlling the agent to perform the sequence of one or more planned actions to cause the environment to transition into one or more different states;

obtaining updated experience data generated as a result of controlling the agent to perform the sequence of one or more planned actions; and

using the updated experience data to update the representation of the environment; and

controlling the agent to perform a task by causing the agent to perform actions selected from a possible set of actions by using the updated representation of the environment.

18 . The method of claim 17 , wherein the agent comprises a mechanical agent and the environment is a real-world environment.

19 . The method of claim 17 , wherein the agent comprises a computer program and the environment is a simulated environment.

20 . The method of claim 17 , wherein determining the sequence of one or more planned actions comprises:

selecting, from all state-action pairs that includes a node representing a state characterized by a last observation, a selected state-action pair that has a highest utility measure; and

using an action included in the selected state-action pair as one single planned action.