IP Library › Granted Patent US 12,705,485
Granted Patent B2
US 12,705,485 · App. 18/919,108 · Granted Aug 11, 2026

Training action selection neural networks using look-ahead search

Inventors: Karen Simonyan (London, GB); David Silver (Hitchin, GB); Julian Schrittwieser (London, GB)
Assignee: GDM Holding LLC
G06N3/08G06N7/01
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,705,485
App. No.
18/919,108
Filed
Oct 17, 2024
Granted
Aug 11, 2026
Kind
B2
Art Unit
2632
USPC
706/25
Abstract

Methods, systems and apparatus, including computer programs encoded on computer storage media, for training an action selection neural network. One of the methods includes receiving an observation characterizing a current state of the environment; determining a target network output for the observation by performing a look ahead search of possible future states of the environment starting from the current state until the environment reaches a possible future state that satisfies one or more termination criteria, wherein the look ahead search is guided by the neural network in accordance with current values of the network parameters; selecting an action to be performed by the agent in response to the observation using the target network output generated by performing the look ahead search; and storing, in an exploration history data store, the target network output in association with the observation for use in updating the current values of the network parameters.

Claims (43)

1 . A method performed by one or more computers and of selecting, using a neural network, actions to be performed in an attempt to achieve a specified result,

wherein the neural network has a plurality of network parameters and is configured to receive an input observation characterizing a state of an environment and to process the input observation in accordance with the network parameters to generate a network output that comprises an action selection output that defines an action selection policy for selecting an action to be performed in response to the input observation, and

wherein the method comprises:

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

determining a target action selection output for the current observation by performing, using the neural network and in accordance with values of the network parameters, a look ahead search of possible future states of the environment starting from the current state until the environment reaches a possible future state that satisfies one or more termination criteria, wherein the look ahead search is a tree search of a state tree having nodes representing states of the environment starting from a root node that represents the current state; and

selecting an action to be performed in response to the current observation using the target action selection output generated by performing the look ahead search.

2 . The method of claim 1 , wherein performing the look ahead search comprises evaluating leaf nodes of the state tree encountered during the look ahead search using the neural network and in accordance with the values of the network parameters.

3 . The method of claim 2 , wherein evaluating leaf nodes of the state tree encountered during the look ahead search using the trained neural network and in accordance with the values of the network parameters comprises, for each leaf node:

adding one or more new edges from the leaf node of the state tree;

processing a new observation characterizing a new state of the environment that is characterized by the leaf node using the neural network and in accordance with the values of the network parameters to generate a new action selection output; and

generating, using the new action selection output, a respective prior probability for each of the one or more new edges.

4 . The method of claim 1 , wherein the values of the network parameters have been determined by training the neural network using target network outputs determined by performing look ahead searches using the neural network.

5 . The method of claim 1 , wherein performing the look ahead search comprises determining a respective visit count for each of a plurality of outgoing edges from the root node, each outgoing edge representing a respective action to be performed by the agent.

6 . The method of claim 5 , wherein the target action selection output comprises a respective probability for each action that is represented by an outgoing edge from the root node, and wherein determining the target action selection output comprises determining the target action selection output from the respective visit counts for the outgoing edges.

7 . The method of claim 6 , wherein performing the look ahead search comprises traversing the state tree starting from the root node until encountering a leaf node by selecting edges to be traversed using adjusted action scores for edges in the state tree.

8 . The method of claim 6 , wherein selecting an action to be performed in response to the current observation using the target action selection output generated by performing the look ahead search comprises:

sampling an action using the respective probabilities for the actions.

9 . The method of claim 6 , wherein determining the target action selection output from the respective visit counts for the outgoing edges comprises applying a softmax over the respective visit counts for the outgoing edges.

10 . The method of claim 1 , further comprising: storing the current observation and the target action selection output for use in training the neural network.

11 . A method performed by one or more computers and of selecting, using a neural network, actions to be performed by an agent interacting with an environment to perform a task in an attempt to achieve a specified result,

wherein the neural network has a plurality of network parameters and is configured to receive an input characterizing a state of the environment and to process the input in accordance with the network parameters to generate a network output, and

wherein the method comprises:

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

determining a target action selection output for the current observation by performing, using the neural network and in accordance with values of the network parameters, a look ahead search of possible future states of the environment starting from the current state until the environment reaches a possible future state that satisfies one or more termination criteria, wherein the look ahead search is a tree search of a state tree having nodes representing states of the environment starting from a root node that represents the current state; and

selecting an action to be performed by the agent in response to the current observation using the target action selection output generated by performing the look ahead search.

12 . The method of claim 11 , wherein performing the look ahead search comprises evaluating leaf nodes of the state tree encountered during the look ahead search using the neural network and in accordance with the values of the network parameters.

13 . The method of claim 12 , wherein evaluating leaf nodes of the state tree encountered during the look ahead search using the trained neural network and in accordance with the values of the network parameters comprises, for each leaf node:

adding one or more new edges from the leaf node of the state tree;

processing a new observation characterizing a new state of the environment that is characterized by the leaf node using the neural network and in accordance with the values of the network parameters to generate a new action selection output; and

generating, using the new action selection output, a respective prior probability for each of the one or more new edges.

14 . The method of claim 11 , wherein the values of the network parameters have been determined by training the neural network using target network outputs determined by performing look ahead searches using the neural network.

15 . The method of claim 11 , wherein performing the look ahead search comprises determining a respective visit count for each of a plurality of outgoing edges from the root node, each outgoing edge representing a respective action to be performed by the agent.

16 . The method of claim 15 , wherein the target action selection output comprises a respective probability for each action that is represented by an outgoing edge from the root node, and wherein determining the target action selection output comprises determining the target action selection output from the respective visit counts for the outgoing edges.

17 . The method of claim 16 , wherein performing the look ahead search comprises traversing the state tree starting from the root node until encountering a leaf node by selecting edges to be traversed using adjusted action scores for edges in the state tree.

18 . The method of claim 16 , wherein selecting an action to be performed in response to the current observation using the target action selection output generated by performing the look ahead search comprises:

sampling an action using the respective probabilities for the actions.

19 . The method of claim 16 , wherein determining the target action selection output from the respective visit counts for the outgoing edges comprises applying a softmax over the respective visit counts for the outgoing edges.

20 . 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 comprising selecting, using a neural network, actions to be performed in an attempt to achieve a specified result,

wherein the neural network has a plurality of network parameters and is configured to receive an input observation characterizing a state of an environment and to process the input observation in accordance with the network parameters to generate a network output that comprises an action selection output that defines an action selection policy for selecting an action to be performed in response to the input observation, and

wherein the method comprises:

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

determining a target action selection output for the current observation by performing, using the neural network and in accordance with values of the network parameters, a look ahead search of possible future states of the environment starting from the current state until the environment reaches a possible future state that satisfies one or more termination criteria, wherein the look ahead search is a tree search of a state tree having nodes representing states of the environment starting from a root node that represents the current state; and

selecting an action to be performed in response to the current observation using the target action selection output generated by performing the look ahead search.

Assignments (2)
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 6, 2025
From: DEEPMIND TECHNOLOGIES LIMITED
To: GDM HOLDING LLC
Reel/Frame 071498/0210 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Apr 4, 2025
From: SIMONYAN, KAREN; SILVER, DAVID; SCHRITTWIESER, JULIAN
To: DEEPMIND TECHNOLOGIES LIMITED
Reel/Frame 070745/0985 →
Continuity (5)
Continuation 18528640 · Dec 4, 2023
Continuation 17948016 · Sep 19, 2022
Continuation 16617478 · May 28, 2018
Provisional Application 62511945 · May 26, 2017
Related Publication 20250148282A1 · May 8, 2025
References Cited (75)
US 9008840B1 · Ponulak et al. · 2015 [cited by applicant]
US 11449750B2 · Simonyan et al. · 2022 [cited by applicant]
US 12147899B2 · Simonyan · 2024 [cited by examiner]
US 20140277718A1 · Izhikevich · 2014 [cited by applicant]
US 20150106315A1 · Birdwell · 2015 [cited by examiner]
US 20150106316A1 · Birdwell et al. · 2015 [cited by applicant]
US 20150127149A1 · Sinyavskiy · 2015 [cited by applicant]
Abe et al., “Empirical Comparison of Various Reinforcement Learning Strategies for Sequential Targeted Marketing,” IEEE International Conference on Data Mining, Dec. 2002, 8 pages. [cited by applicant]
Anthony et al., “Thinking Fast and Slow with Deep Learning and Tree Search,” https://arxiv.org/abs/1705.08439v1, May 2017, 17 pages. [cited by applicant]
Barto et al., “Monte Carlo Matrix Inversion and Reinforcement Learning,” retrieved from URL <https://pdfs.semanticscholar.org/4315/56f0e52d620689579d8145607e4410f06994.pdf>, 1994, 687-694. [cited by applicant]
Baxter et al., “Learning to Play Chess Using Temporal Differences,” Machine Learning, Sep. 2000, 40:243-263. [cited by applicant]
Bertsekas, “Approximate policy iteration: a survey and some new methods,” Journal of Control Theory and Applications, Jul. 2011, 9:310-335. [cited by applicant]
Browne et al., “A Survey of Monte Carlo Tree Search Methods,” IEEE Transactions on Computational Intelligence and AI in Games, Mar. 2012, 43 pages. [cited by applicant]
Buro, “From Simple Features to Sophisticated Evaluation Functions,” International Conference on Computers and Games, Mar. 1999, 20 pages. [cited by applicant]
Cazenave et al., “Using a Monte-Carlo approach for bus regulation,” 2009 12th International IEEE Conference on Intelligent Transportation Systems, Oct. 2009, 340-345. [cited by applicant]
Cazenave, “Residual Networks for Computer Go,” IEEE Transactions on Games , Mar. 2017, 4 pages. [cited by applicant]
Clark et al., “Training Deep Convolutional Neural Networks to Play Go,” Proceedings of the 32nd International Conference on Machine Learning, Jul. 2015, 9 pages. [cited by applicant]
Coulom, “Computing Elo Ratings of Move Patterns in the Game of Go,” Int. Comput. Games Assoc. J., Jan. 2007, 30:11 pages. [cited by applicant]
Coulom, “Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search,” Proceedings of the 5th International Conference on Computers and Games, retrieved from URL <https://refs.devinmcgloin.com/artificial_intel… [cited by applicant]
Coulom, R. “Whole-History Rating: A Bayesian Rating System for Players of Time-Varying Strength,” Int. Conf. Comput. Games, 2008, vol. 5131:113-124. [cited by applicant]
Dosovitskiy et al., “Learning to Act by Predicting the Future,” https://arxiv.org/abs/1611.01779v2, last revised Feb. 2017, 14 pages. [cited by applicant]
Enzenberger, “Evaluation in Go by a Neural Network Using Soft Segmentation,” Advances in Computer Games, 2003, 97-108. [cited by applicant]
Enzenberger, “The Integration of a Prior Knowledge into a Go Playing Neural Network,” retrieved from URL <http://www.cgl.ucsf.edu/go/Programs/NeuroGo.pdf>, Sep. 1996, 8 pages. [cited by applicant]
EP Office Action in European Appln. No. 18727294.3, dated Jun. 9, 2021, 9 pages. [cited by applicant]
Evans et al., “DeepMind AI Reduces Google Data Centre Cooling Bill by 40%,” retrieved from URL <https://deepmind.com/blog/article/deepmind-ai-reduces-google-data-centre-cooling-bill-40>, Jul. 2016, retrieved on Mar. 9, … [cited by applicant]
Foerster et al., “Stabilizing Experience Replay for Deep Multi-Agent Reinforcement Learning,” https://arxiv.org/abs/1702.08887v2, Jun. 2017, 10 pages. [cited by applicant]
Fukushima et al., “Neocognitron: A Self-organizing Neural Network Model for a Mechanism of Pattern Recognition Unaffected by Shift in Position,” Biological Cybernetics, Apr. 1980, 36:193-202. [cited by applicant]
Gelly et al., “Modification of UCT with Patterns in Monte-Carlo Go,” INRIA, retrieved from URL <https://hal.inria.fr/inria-00117266v3/document>, Nov. 2006, 6062:25 pages. [cited by applicant]
Gelly et al., “Monte-Carlo tree search and rapid action value estimation in computer Go,” Artificial Intelligence, Jul. 2011, 175(11):1856-1875. [cited by applicant]
Guo et al., “Deep learning for real-time Atari game play using offline Monte-Carlo tree search planning,” retrieved from URL<http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.859.328&rep-rep1&type=pdf>, Dec. 2014… [cited by applicant]
Hahnloser et al., “Digital selection and analogue amplification coexist in a cortex-inspired silicon circuit,” Nature, Jun. 2000, 405:947-951. [cited by applicant]
He et al., “Deep Residual Learning for Image Recognition,” 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), Jun. 2016, 770-778. [cited by applicant]
Heinrich et al., “Deep Reinforcement Learning from Self-Play in Imperfect-Information Games,” https://arxiv.org/abs/1603.01121v2, last revised Jun. 2016, 10 pages. [cited by applicant]
Ioffe et al., “Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift,” https://arxiv.org/abs/1502.03167v3, last revised Mar. 2015, 11 pages. [cited by applicant]
Jaderberg et al., “Reinforcement Learning with Unsupervised Auxiliary Tasks,” https://arxiv.org/abs/1611.05397, Nov. 2016, 14 pages. [cited by applicant]
Jouppi et al., “In-Datacenter Performance Analysis of a Tensor Processing Unit,” Proceedings of the 44th Annual International Symposium on Computer Architecture, Jun. 2017, 12 pages. [cited by applicant]
Kober et al., “Reinforcement Learning in Robotics: A Survey,” Int. J. Robot. Res., 2013, 32:1238-1274. [cited by applicant]
Kocsis et al., “Bandit Based Monte-Carlo Planning,” European Conference on Machine Learning, Sep. 2006, 282-293. [cited by applicant]
Krizhevsky et al., “ImageNet Classification with Deep Convolutional Neural Networks,” retrieved from URL <http://vision.cse.psu.edu/people/chrisF/deep-learning/Papers/KrizhevskyNIPS12Imagenet.pdf>, 2012, 9 pages. [cited by applicant]
Lagoudakis et al., “Reinforcement Learning as Classification: Leveraging Modern Classifiers,” Proceedings of the Twentieth International Conference on International Conference on Machine Learning, Aug. 2003, 8 pages. [cited by applicant]
Lai, “Giraffe: Using Deep Reinforcement Learning to Play Chess,” Dissertation for MSc degree, retrieved from URL <https://arxiv.org/pdf/1509.01549v2.pdf>, Imperial College London, Sep. 2015, 39 pages. [cited by applicant]
Laurent et al., “The world of independent learners is not markovian,” International Journal of Knowledge-based and Intelligent Engineering Systems, Mar. 2011, 15:55-64. [cited by applicant]
LeCun et al., “Convolutional Networks for Images, Speech, and Time Series,” The Handbook of Brain Theory and Neural Networks, 1995, 255-258. [cited by applicant]
LeCun et al., “Deep learning,” Nature, May 2015, 521:436-444. [cited by applicant]
Littman, “Markov games as a framework for multi-agent reinforcement learning,” Machine Learning Proceedings of the Eleventh International Conference, Jul. 1994, 157-163. [cited by applicant]
Maddison et al., “Move Evaluation in Go Using Deep Convolutional Neural Networks,” https://arxiv.org/abs/1412.6564v2, last revised Apr. 2015, 8 pages. [cited by applicant]
Mandziuk, “Computational Intelligence in Mind Games,” Challenges for Computational Intelligence, Jun. 2007, 407-442. [cited by applicant]
Mechner, “All Systems Go,” The Sciences, Jan. 1998, 32-37. [cited by applicant]
Mnih et al., “Asynchronous Methods for Deep Reinforcement Learning,” Proceedings of the 33rd International Conference on Machine Learning, Jun. 2016, 10 pages. [cited by applicant]
Mnih et al., “Human-level control through deep reinforcement learning,” Nature, Feb. 2015, 518:529-533. [cited by applicant]
Moravcik et al., “DeepStack: Expert-level artificial intelligence in heads-up no-limit poker,” Science, retrieved from URL <https://arxiv.org/abs/1701.01724v3>, Mar. 2017, 37 pages. [cited by applicant]
Müller, “Computer Go,” Artificial Intelligence, Jan. 2002, 134:145-179. [cited by applicant]
PCT International Preliminary Report on Patentability in International Appln. No. PCT/EP2018/063869, mailed Dec. 5, 2019, 11 pages. [cited by applicant]
PCT International Search Report and Written Opinion in International Appln. No. PCT/EP2018/063869, mailed Sep. 3, 2018, 17 pages. [cited by applicant]
Rosin, “Multi-armed bandits with episode context,” Annals of Mathematics and Artificial Intelligence, Aug. 2011, 61:203-230. [cited by applicant]
Samuel, “Some Studies in Machine Learning Using the Game of Checkers II—Recent Progress,” IBM J. Res. Develop., Nov. 1967, 11:601-617. [cited by applicant]
Schaeffer et al., “Temporal difference learning applied to a high-performance game-playing program,” Proceedings of the 17th international joint conference on Artificial intelligence, Aug. 2001, 1:529-534. [cited by applicant]
Scherrer et al., “Approximate Modified Policy Iteration and its Application to the Game of Tetris,” Journal of Machine Learning Research, Aug. 2015, 16:1629-1676. [cited by applicant]
Scherrer, “Approximate Policy Iteration Schemes: A Comparison,” Proceedings of the 31st International Conference on Machine Learning, Jan. 2014, 9 pages. [cited by applicant]
Schraudolph et al., “Temporal Difference Learning of Position Evaluation in the Game of Go,” Advances in Neural Information Processing, 1994, 8 pages. [cited by applicant]
Segal, “On the Scalability of Parallel UCT,” Comput. Games, 2011, 6515:36-47. [cited by applicant]
Shahriari et al., “Taking the Human Out of the Loop: A Review of Bayesian Optimization,” Proceedings of the IEEE, Jan. 2016, 104:148-175. [cited by applicant]
Sheppard, “World-championship-caliber Scrabble,” Artificial Intelligence, Jan. 2002, 134:241-275. [cited by applicant]
Silver et al., “Concurrent Reinforcement Learning from Customer Interactions,” In Proc. 30th Int. Conf. Mach. Learn., Feb. 2013, 9 pages. [cited by applicant]
Silver et al., “Mastering the game of Go with deep neural networks and tree search,” Nature, Jan. 2016, 529:20 pages. [cited by applicant]
Silver et al., “Temporal-difference search in computer Go,” Machine Learning, Feb. 2012, 87:183-219. [cited by applicant]
Silver, “Reinforcement Learning and Simulation-Based Search in Computer Go,” Thesis for the degree of Doctor of Philosophy, University of Alberta, 2009, 170 pages. [cited by applicant]
Singh et al., “Reinforcement Learning with Replacing Eligibility Traces,” Machine Learning, Jan. 1996, 22:123-158. [cited by applicant]
Sutton, “Learning to Predict by the Methods of Temporal Differences,” Machine Learning, Aug. 1988, 3:9-44. [cited by applicant]
Tesauro et al., “On-line Policy Improvement using Monte-Carlo Search,” In Adv. Neural Inf. Process. Syst., retrieved from URL <https://pdfs.semanticscholar.org/3552/fba431aa866bf9de293bebf7eff168e9e19c.pdf>, Dec. 1996, … [cited by applicant]
Tesauro, “Neurogammon: a neural-network backgammon program,” 1990 IJCNN International Joint Conference on Neural Networks, Jun. 1990, 3:33-39. [cited by applicant]
Tesauro, “TD-Gammon, a Self-Teaching Backgammon Program, Achieves Master-Level Play,” Neural Computation, Mar. 1994, 6:215-219. [cited by applicant]
Tian et al., “Better Computer Go Player with Neural Network and Long-term Prediction,” https://arxiv.org/abs/1511.06410v3, last revised Feb. 2016, 10 pages. [cited by applicant]
Veness et al., “Bootstrapping from Game Tree Search,” In Adv. Neural Inf. Process. Syst., retrieved from URL <http://blair.web.cse.unsw.edu.au/pubs/2009VenessSilverUtherBlairNIPS.pdf>, 2009, 9 pages. [cited by applicant]
Zhang et al., “A Reinforcement Learning Approach to Job-shop Scheduling,” Proceedings of the 14th international joint conference on Artificial intelligence, Aug. 1995, 1114-1120. [cited by applicant]