IP Library › Granted Patent US 12,189,688
Granted Patent B2
US 12,189,688 · App. 18/373,870 · Granted Jan 7, 2025

Fast exploration and learning of latent graph models

Inventors: Sivaramakrishnan Swaminathan (Mountain View, CA); Meet Kirankumar Dave (Santa Clara, CA); Miguel Lazaro-Gredilla (Union City, CA); Dileep George (Sunnyvale, CA)
Assignee: DeepMind Technologies Limited
G06F16/9024G06F17/12
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,189,688
App. No.
18/373,870
Granted
Jan 7, 2025
Kind
B2
Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for generating a graph model representing an environment being interacted with by an agent. In one aspect, one of the methods include: obtaining experience data; using the experience data to update a visitation count for each of one or more state-action pairs represented by the graph model; and at each of multiple environment exploration steps: computing a utility measure for each of the one or more state-action pairs represented by the graph model; 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.

Claims (57)

1. A method of generating a graph model representing an environment being interacted with by an agent, wherein the graph model comprises nodes that represent states of the environment and edges connecting the nodes, wherein an edge between a first node and a second node in the graph model represents a corresponding action performed by the agent which caused the environment to transition from a state represented by the first node into a state represented by the second node, wherein the method comprises:

obtaining experience data generated as a result of controlling the agent 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 represented by the graph model, wherein each state-action pair corresponds to a node and an outgoing edge of the node included in the graph model; and

at each of multiple environment exploration steps:

computing a utility measure for each of the one or more state-action pairs represented by the graph model, 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 evaluating the closed form utility function comprises:

determining a parameter vector from the updated visitation counts and a Dirichlet prior parameter; and

determining a Dirichlet distribution parameterized by the parameter vector over an action-conditioned transition distribution of the graph model, wherein the action-conditioned transition distribution defines a probability of the environment transitioning from the state represented by the first node into the state represented by the second node given that the corresponding action represented by the edge is performed by the agent.

3. The method of claim 2 , wherein evaluating the closed form utility function comprises evaluating an entropy function using the parameter vector.

4. The method of claim 2 , wherein evaluating the closed form utility function comprises:

evaluating a polygamma function using the parameter vector to determine a polygamma function output; and

determining an elementwise product between the parameter vector and the polygamma function output.

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

selecting, from all state-action pairs represented by the graph model that includes a node representing the state characterized by the 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.

6. 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 the node representing the state characterized by the last observation; and

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

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

8. 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 represented by the graph model.

9. 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.

10. The method of claim 1 , wherein two or more nodes in the graph model represent a same observation of the environment.

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

using the experience data to update the graph model to include (i) a plurality of nodes that represent the respective states of the environment and (ii) one or more edges between the plurality of nodes that represent the one or more actions performed by the agent which caused the environment to transition between the respective states.

12. The method of claim 11 , wherein updating the graph model comprises updating the graph model based on using one of Expectation-Maximization (EM) algorithm, online EM algorithm, or Memorize-Generalize algorithm.

13. The method of claim 11 , wherein the graph model comprises a clone structured cognitive graph (CSCG) model.

14. The method of claim 11 , further comprising using a Viterbi algorithm to remove redundant clones of the graph model based on the experience data.

15. 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.

16. The method of claim 1 , further comprising using the graph model to select, from a possible set of actions, actions to be performed by an agent interacting with an environment to cause the agent to perform a task, the selecting comprising:

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

performing a plurality of planning iterations to generate plan data by using the graph model, the plan data indicative of an estimated total reward to be received by the agent in response to performing each of multiple actions from the possible set of actions in the environment and starting from the current state; and

selecting an action to be performed by the agent in response to the current observation using the plan data.

17. The method of claim 1 , further comprising using the graph model to control an agent interacting with an environment to perform a sequence of one or more actions to cause the environment to transition from an origin state to a destination state, the controlling comprising:

obtaining a query that characterizes the origin state and the destination state;

determining an origin node in the graph model that represents the origin state of the environment and a destination node in the graph model that represents the destination state;

determining a respective outgoing edge of the origin node and each intermediate node between the origin node and the destination node; and

causing the agent to perform actions represented by the respective outgoing edges starting from the origin state.

18. The method of claim 17 , wherein the query identifies recent experience data generated as a result of controlling the agent to interact with the environment, and wherein determining the origin node in the graph model that represents the origin state of the environment and the destination node in the graph model that represents the destination state comprises:

identifying the origin node based on the graph model and the recent experience data.

19. A system comprising one or more data processing apparatuses and one or more storage devices storing instructions that are operable, when executed by the one or more data processing apparatuses, to cause the one or more data processing apparatuses to perform operations for generating a graph model representing an environment being interacted with by an agent, wherein the graph model comprises nodes that represent states of the environment and edges connecting the nodes, wherein an edge between a first node and a second node in the graph model represents a corresponding action performed by the agent which caused the environment to transition from a state represented by the first node into a state represented by the second node, wherein the operations comprise:

obtaining experience data generated as a result of controlling the agent 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 represented by the graph model, wherein each state-action pair corresponds to a node and an outgoing edge of the node included in the graph model; and

at each of multiple environment exploration steps:

computing a utility measure for each of the one or more state-action pairs represented by the graph model, 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.

20. One or more non-transitory computer-readable media storing instructions that, when executed by one or more computers, cause the one or more computers to perform operations for generating a graph model representing an environment being interacted with by an agent, wherein the graph model comprises nodes that represent states of the environment and edges connecting the nodes, wherein an edge between a first node and a second node in the graph model represents a corresponding action performed by the agent which caused the environment to transition from a state represented by the first node into a state represented by the second node, wherein the operations comprise:

obtaining experience data generated as a result of controlling the agent 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 represented by the graph model, wherein each state-action pair corresponds to a node and an outgoing edge of the node included in the graph model; and

at each of multiple environment exploration steps:

computing a utility measure for each of the one or more state-action pairs represented by the graph model, 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.

Assignments (2)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 29, 2025
From: DEEPMIND TECHNOLOGIES LIMITED
To: GDM HOLDING LLC
Reel/Frame 071109/0414 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Mar 18, 2024
From: SWAMINATHAN, SIVARAMAKRISHNAN; DAVE, MEET KIRANKUMAR; LAZARO-GREDILLA, MIGUEL; GEORGE, DILEEP
To: DEEPMIND TECHNOLOGIES LIMITED
Reel/Frame 066810/0809 →
Continuity (3)
Provisional Application 63436845 · Jan 3, 2023
Provisional Application 63411031 · Sep 28, 2022
Related Publication 20240126812A1 · Apr 18, 2024
References Cited (46)
US 20220366246A1 · Danihelka · 2022 [cited by examiner]
US 20230073326A1 · Schrittwieser · 2023 [cited by examiner]
Amin et al., “A survey of exploration methods in reinforcement learning,” CoRR, submitted on Sep. 2, 2021, arXiv:2109.00157v2, 79 pages. [cited by applicant]
Battaglia et al., “Relational inductive biases, deep learning, and graph networks,” CoRR, submitted on Oct. 17, 2018, arXiv:1806.01261v3, 40 pages. [cited by applicant]
Beattie et al., “DeepMind lab,” CoRR, submitted on Dec. 13, 2016, arXiv:1612.03801v2, 11 pages. [cited by applicant]
Bellemare et al., “Unifying Count-Based exploration and intrinsic motivation,” CoRR, submitted on Nov. 7, 2016, arXiv:1606.01868v2, 20 pages. [cited by applicant]
Brafman et al., “Resolving perceptual aliasing in the presence of noisy sensors,” Advances in neural information processing systems, 2004, 8 pages. [cited by applicant]
Buhai et al., “Empirical study of the benefits of overparameterization in learning latent variable models” In International Conference on Machine Learning, Nov. 21, 2020, p. 1211-1219. [cited by applicant]
Cassandra et al., “Acting optimally in partially observable stochastic domains,” in AAAI 94, Jul. 31, 1994, p. 1023-1028. [cited by applicant]
Chandra et al., “The electrical resistance of a graph captures its commute and cover times,” In Proceedings of the twenty-first annual ACM symposium on Theory of computing, Feb. 1, 1989, p. 574-586. [cited by applicant]
Chrisman, “Reinforcement learning with perceptual aliasing: The perceptual distinctions approach,” in AAAI, Jul. 12, 1992, p. 183-188. [cited by applicant]
Dai et al., “Learning transferable graph exploration,” Advances in Neural Information Processing Systems, Oct. 2019, 12 pages. [cited by applicant]
Dechter et al., “Bootstrap learning via modular concept discovery,” In Proceedings of the international joint conference on artificial intelligence 2013, AAAI Press/International Joint Conferences on Artificial Intellig… [cited by applicant]
Dong et al., “ Learning graphs from data: A signal representation perspective,” CoRR, submitted on May 20, 2019, arXiv:1806.00848v3, 38 pages. [cited by applicant]
Ecoffet et al., “First return, then explore,” Nature, Feb. 24, 2021, 590(7847):580-586. [cited by applicant]
Forney et al., “Counterfactual data-fusion for online reinforcement learners,” In International Conference on Machine Learning, Jul. 17, 2017, p. 1156-1164. [cited by applicant]
From Animals to Animats, Schmidhuber(ed)., 1991, A possibility for implementing curiosity and boredom in model-building neural controllers, 1 page (abstract only). [cited by applicant]
George et al., “Clone-structured graph representations enable flexible learning and vicarious evaluation of cognitive maps,” Nature Communications, Apr. 2021, 12(1):2392, 17 pages. [cited by applicant]
Ghosh et al., “Why generalization in RL is difficult: Epistemic POMDPs and implicit partial observability,” CoRR, submitted on Jul. 13, 2021, arXiv:2107.06277v1, 23 pages. [cited by applicant]
Groth et al., “Is curiosity all you need? on the utility of emergent behaviours from curious exploration,” CoRR, submitted on Sep. 17, 2021, arXiv:2109.08603v1, 14 pages. [cited by applicant]
Guestrin et al., “Efficient solution algorithms for factored MDPs,” Journal of Artificial Intelligence Research, Oct. 1, 2003, p. 399-468. [cited by applicant]
Kearns et al., “Near-Optimal reinforcement learning in polynomial time,” Machine Learning, Nov. 2002, 49(2/3):209-232. [cited by applicant]
Kolter et al., “Near-Bayesian exploration in polynomial time,” In Proceedings of the 26th Annual International Conference on Machine Learning, Jun. 14, 2009, p. 513-520. [cited by applicant]
Lajoie et al., “Modeling perceptual aliasing in SLAM via discrete-continuous graphical models,” CoRR, submitted on Jan. 24, 2019, arXiv:1810.11692v3, 13 pages. [cited by applicant]
Lambiotte et al., “From networks to optimal higherorder models of complex systems,” Nature Physics, 2019, 15(4):313-320 (abstract only). [cited by applicant]
Lehman et al., “Abandoning objectives: evolution through the search for novelty alone,” Evolutionary Computation, Feb. 2011, 19(2): 189-223. [cited by applicant]
Meuleau et al., “Solving POMDPs by searching the space of finite policies,” CoRR, Jan. 23, 2013, arXiv:1301.6720, 10 pages. [cited by applicant]
Motwani et al., “Randomized algorithms,” ACM Compututer Surveys, Mar. 1, 1996, 28(1): 33-37. [cited by applicant]
Osband et al., “Deep exploration via bootstrapped DQN,” CoRR, submitted on Jul. 4, 2016, arXiv:1602.04621v3, 18 pages. [cited by applicant]
Oudeyer et al., “What is intrinsic motivation? a typology of computational approaches,” Frontiers in Neurorobotics, Nov. 2, 2007, 1:6, 14 pages. [cited by applicant]
Rabiner, “A tutorial on hidden markov models and selected applications in speech recognition,” Proceedings of the IEEE, Feb. 1989, 77(2):257-286. [cited by applicant]
Rikhye et al., “Memorize-Generalize: An online algorithm for learning higher-order sequential structure with cloned hidden markov models,” BioRxiv, Sep. 10, 2019, 4 pages. [cited by applicant]
Ritter et al., “Rapid task-solving in novel environments,” CoRR, submitted on Apr. 19, 2021, arXiv:2006.03662v3, 15 pages. [cited by applicant]
Rosvall et al., “Maps of random walks on complex networks reveal community structure,” Proceedings of the National Academy of Sciences of the United States of America, Jan. 2008, 105(4): 1118-1123. [cited by applicant]
Sharan et al., “Learning overcomplete HMMs,” Advances in Neural Information Processing Systems, 2017, 10 pages. [cited by applicant]
Sharma et al., “Map induction: Compositional spatial submap learning for efficient exploration in novel environments,” CoRR, submitted on Mar. 17, 2022, arXiv:2110.12301v2, 22 pages. [cited by applicant]
Shyam et al., “Model-based active exploration,” In International conference on machine learning, May 24, 2019, p. 5779-5788. [cited by applicant]
Strehl et al., “A theoretical analysis of Model-Based interval estimation,” In Proceedings of the 22nd international conference on Machine learning—ICML, Aug. 7, 2005, p. 856-863. [cited by applicant]
Strehl et al., “An analysis of model-based interval estimation for markov decision processes,” Journal of Computer and System Sciences, Dec. 1, 2008, 74(8):1309-1331. [cited by applicant]
Tang et al., “#exploration: A study of Count-Based exploration for deep reinforcement learning,” Advances in neural information processing systems, 2017, 10 pages. [cited by applicant]
Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE transactions on information theory I Professional Technical Group on Information Theory, Apr. 1967, 13(2):260-269. [cited by applicant]
Whitehead et al., “Learning to perceive and act by trial and error,” Machine Learning, Jul. 1991, 7(1):45-83. [cited by applicant]
Wilf, “The white screen problem,” The American mathematical monthly: the official journal of the Mathematical Association of America, Oct. 1, 1989, 96(8):704-707 (abstract only). [cited by applicant]
Xu et al., “Benefits of over-parameterization with EM,” Advances in Neural Information Processing Systems, 2018, 11 pages. [cited by applicant]
Xu et al., “Representing higher-order dependencies in networks,” Network Science, May 20, 2016, 2(5):e1600028. [cited by applicant]
Yang et al., “Exploration in deep reinforcement learning: a comprehensive survey,” CoRR, submitted on Jan. 26, 2022, arXiv:2109.06668v3, 24 pages. [cited by applicant]