IP Library › Granted Patent US 12,566,801

Granted Patent B2

US 12,566,801 · App. 17/824,680 · Granted Mar 3, 2026

Method for fast and better tree search for reinforcement learning

Inventors: Shie Mannor (Haifa, IL); Assaf Joseph Hallak (Tel Aviv, IL); Gal Dalal (Haifa, IL); Steven Tarence Dalton (Cary, NC); Iuri Frosio (Bergamo, IT); Gal Chechik (Ramat Hasharon, IL)

Assignee: NVIDIA Corporation

G06F16/90335 G06F16/9027

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,566,801
App. No.: 17/824,680
Granted: Mar 3, 2026
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

A method for performing a Tree-Search (TS) on an environment is provided. The method comprises generating a tree for a current state of the environment based on a TS policy, determining a corrected TS policy, and determining an action to apply to the environment based on the corrected TS policy. The tree comprises a plurality of nodes including a root node among the plurality of nodes corresponding to the current state of the environment. Each node other than the root node among the plurality of nodes corresponding to an estimated future state of the environment. The plurality of nodes in the tree are connected by a plurality of edges. Each edge among the plurality of edges is associated with an action causing a transition from a first state to a different sate of the environment.

Claims (79)

1 . A method, applied by an agent device on an environment, the method comprising:

generating, as a data structure in a processor-readable memory of the agent device, a tree for a current state of the environment based on a tree search (TS) policy, wherein the tree comprises a plurality of nodes including a root node among the plurality of nodes corresponding to the current state of the environment, each node other than the root node among the plurality of nodes corresponding to an estimated future state of the environment, the plurality of nodes in the tree are connected by a plurality of edges, and each edge among the plurality of edges is associated with an action causing a transition from a first state to a different state of the environment;

determining, by one or more processors of the agent device, a corrected TS policy by applying an off-policy correction term to an estimated value function associated with the TS policy to obtain a corrected estimated value function associated with the corrected TS policy, wherein the corrected estimated value function is configured to compensate for a distribution shift of the estimated value function associated with the TS policy by rewarding training states and/or applying a bound to off-policy states;

determining, by the one or more processors of the agent device based on the corrected TS policy, an action to apply to the environment; and

applying, by the agent device, the action to the environment to transition to a new state.

2 . The method of claim 1 , wherein the determining the corrected TS policy comprises:

estimating, based on a calculated Bellman error, the correction term for each of a plurality of child nodes of the root node.

3 . The method of claim 1 , wherein the tree is expanded to a final depth, and wherein the determining, based on the corrected TS policy, the action to apply to the environment comprises:

evaluating, using the corrected estimated value function associated with the corrected TS policy, a value for each node in the final depth of the tree;

determining, for all nodes in the final depth of the tree, a node associated with a highest value computed using the corrected estimated value function; and

determining the action for the state of the environment to be a first action in a trajectory of the tree including the node associated with the highest value in the final depth of the tree, wherein the first action in the trajectory is associated with an edge between the root node and a child node of the root node in an adjacent depth of the tree.

4 . The method of claim 1 , wherein the tree is generated by expanding the tree using one or more parallel processing units (PPUs).

5 . The method of claim 4 , wherein the one or more PPUs expand the tree by adding edges and nodes associated with a next depth of the tree in each iteration of the expansion.

6 . The method of claim 5 , wherein the one or more PPUs process a number of state-action pairs in each iteration of the expansion, and wherein each state-action pair includes an action and a state associated with a node of the tree at a depth prior to the depth to be added to the tree in the expansion.

7 . The method of claim 6 , wherein the environment is associated with an action space comprising a plurality of actions.

8 . The method of claim 1 , wherein the TS policy comprises a machine learning algorithm that is pre-trained in the environment.

9 . The method of claim 1 , wherein the TS policy is based on Breadth-First-Search.

10 . The method of claim 1 , wherein the determining the corrected TS policy is based on one or more parameters related to the TS policy, and wherein the one or more parameters related to the TS policy comprise at least one of a performance parameter, a count parameter, or an error parameter of the TS policy.

11 . The method according to claim 1 , wherein the applying, by the agent device, the action to the environment to transition to a new state comprises executing a movement, by a robot or an autonomous vehicle, in the environment.

12 . An agent device for performing a Tree-Search (TS) on an environment, the agent device comprising:

a processor-readable memory storing a TS policy; and

one or more processors coupled to the memory and configured to:

generate, as a data structure in the processor-readable memory of the agent device, a tree for a current state of the environment based on the TS policy, wherein the tree comprises a plurality of nodes including a root node among the plurality of nodes corresponding to the current state of the environment, each node other than the root node among the plurality of nodes corresponding to an estimated future state of the environment, the plurality of nodes in the tree are connected by a plurality of edges, and each edge among the plurality of edges is associated with an action causing a transition from a first state to a different state of the environment,

determine a corrected TS policy by applying an off-policy correction term to an estimated value function associated with the TS policy to obtain a corrected estimated value function, wherein the corrected estimated value function is configured to compensate for a distribution shift of the estimated value function associated with the TS policy by rewarding training states and/or applying a bound to off-policy states,

determine, based on the corrected TS policy, an action to apply to the environment, and

apply, by the agent device, the action to the environment to transition to a new state.

13 . The agent device of claim 12 , wherein the determining the corrected TS policy comprises:

estimating, based on a calculated Bellman error, the correction term for each of a plurality of child nodes of the root node.

14 . The agent device of claim 12 , wherein the tree is expanded to a final depth, and wherein the determining, based on the corrected TS policy, the action to apply to the environment comprises:

evaluating, using the corrected estimated value function associated with the corrected TS policy, a value for each node in the final depth of the tree;

determining, for all nodes in the final depth of the tree, a node associated with a highest value computed using the corrected estimated value function; and

15 . The agent device of claim 12 , further comprising one or more parallel processing units (PPUs), and wherein the tree is generated by expanding the tree using the one or more PPUs.

16 . The agent device of claim 15 , wherein the one or more PPUs expand the tree by adding edges and nodes associated with a next depth of the tree in each iteration of the expansion.

17 . The agent device of claim 16 , wherein the one or more PPUs process a number of state-action pairs in each iteration of the expansion, and wherein each state-action pair includes an action and a state associated with a node of the tree at a depth prior to the depth to be added to the tree in the expansion.

18 . The agent device of claim 17 , wherein the environment is associated with an action space comprising a plurality of actions.

19 . The agent device of claim 12 , wherein the TS policy comprises a reinforcement learning algorithm that is pre-trained in the environment.

20 . The agent device of claim 12 , further comprising one or more sensors configured to measure the current state of the environment.

21 . The agent device of claim 20 , wherein the one or more sensors comprise a camera.

22 . A non-transitory computer readable medium comprising instructions that, responsive to being executed by one or more processors, cause an agent device to perform a Tree-Search (TS) on an environment by:

generating, as a data structure in a processor-readable memory of the agent device, a tree for a current state of the environment based on a TS policy, wherein the tree comprises a plurality of nodes including a root node among the plurality of nodes corresponding to the current state of the environment, each node other than the root node among the plurality of nodes corresponding to an estimated future state of the environment, the plurality of nodes in the tree are connected by the edges, and each edge among the plurality of edges is associated with an action causing a transition from a first state to a different state of the environment;

determining, by the one or more processors, a corrected TS policy by applying an off-policy correction term to an estimated value function associated with the TS policy to obtain a corrected estimated value function associated with the corrected TS policy, wherein the corrected estimated value function is configured to compensate for a distribution shift of the estimated value function associated with the TS policy by rewarding training states and/or applying a bound to off-policy states;

determining, by the one or more processors based on the corrected TS policy, an action to apply to the environment; and

applying, by the agent device, the action to the environment to transition to a new state.

23 . A method, applied by an agent device on an environment, the method comprising:

determining, by one or more processors of the agent device, a corrected TS policy by applying a correction term to an estimated value function associated with the TS policy to obtain a corrected estimated value function associated with the corrected TS policy;

determining, by the one or more processors of the agent device based on the corrected TS policy, an action to apply to the environment; and

applying, by the agent device, the action to the environment to transition to a new state,

wherein the determining the corrected TS policy comprises estimating, based on a calculated Bellman error, the correction term for each of a plurality of child nodes of the root node.

24 . The method of claim 23 , wherein the tree is expanded to a final depth, and wherein the determining, based on the corrected TS policy, the action to apply to the environment comprises:

evaluating, using the corrected estimated value function associated with the corrected TS policy, a value for each node in the final depth of the tree;

determining, for all nodes in the final depth of the tree, a node associated with a highest value computed using the corrected estimated value function; and

25 . The method of claim 23 , wherein the tree is generated by expanding the tree using one or more parallel processing units (PPUs).

26 . The method of claim 25 , wherein the one or more PPUs expand the tree by adding edges and nodes associated with a next depth of the tree in each iteration of the expansion.

27 . The method of claim 26 , wherein the one or more PPUs process a number of state-action pairs in each iteration of the expansion, and wherein each state-action pair includes an action and a state associated with a node of the tree at a depth prior to the depth to be added to the tree in the expansion.

28 . The method of claim 27 , wherein the environment is associated with an action space comprising a plurality of actions.

29 . The method of claim 23 , wherein the TS policy comprises a machine learning algorithm that is pre-trained in the environment.

30 . The method of claim 23 , wherein the TS policy is based on Breadth-First-Search.

31 . The method of claim 23 , wherein the determining the corrected TS policy is based on one or more parameters related to the TS policy, and wherein the one or more parameters related to the TS policy comprise at least one of a performance parameter, a count parameter, or an error parameter of the TS policy.

32 . An agent device for performing a Tree-Search (TS) on an environment, the agent device comprising:

a processor-readable memory storing a TS policy; and

one or more processors coupled to the memory and configured to:

determine, based on the corrected TS policy, an action to apply to the environment, and

apply, by the agent device, the action to the environment to transition to a new state,

wherein the determining the corrected TS policy comprises estimating, based on a calculated Bellman error, the correction term for each of a plurality of child nodes of the root node.

33 . The agent device of claim 32 , wherein the tree is expanded to a final depth, and wherein the determining, based on the corrected TS policy, the action to apply to the environment comprises:

evaluating, using the corrected estimated value function associated with the corrected TS policy, a value for each node in the final depth of the tree;

determining, for all nodes in the final depth of the tree, a node associated with a highest value computed using the corrected estimated value function; and

34 . The agent device of claim 32 , further comprising one or more parallel processing units (PPUs), and wherein the tree is generated by expanding the tree using the one or more PPUs.

35 . The agent device of claim 34 , wherein the one or more PPUs expand the tree by adding edges and nodes associated with a next depth of the tree in each iteration of the expansion.

36 . The agent device of claim 35 , wherein the one or more PPUs process a number of state-action pairs in each iteration of the expansion, and wherein each state-action pair includes an action and a state associated with a node of the tree at a depth prior to the depth to be added to the tree in the expansion.

37 . The agent device of claim 36 , wherein the environment is associated with an action space comprising a plurality of actions.

38 . The agent device of claim 32 , wherein the TS policy comprises a reinforcement learning algorithm that is pre-trained in the environment.

39 . The agent device of claim 32 , further comprising one or more sensors configured to measure the current state of the environment.

40 . The agent device of claim 39 , wherein the one or more sensors comprise a camera.

Assignments (1)

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded May 26, 2022

From: MANNOR, SHIE; HALLAK, ASSAF JOSEPH; DALAL, GAL; DALTON, STEVEN TARENCE; FROSIO, IURI; CHECHIK, GAL

To: NVIDIA CORPORATION

Reel/Frame 060023/0466 →

Continuity (2)

Provisional Application 63193035 · May 25, 2021

Related Publication 20220398283A1 · Dec 15, 2022

References Cited (48)

US 8429097B1 · Sivasubramanian · 2013 [cited by examiner]

US 8527366B2 · Jacob Sushil · 2013 [cited by examiner]

US 20030135485A1 · Leslie · 2003 [cited by examiner]

US 20150062353A1 · Dalal · 2015 [cited by examiner]

US 20180075105A1 · Chavan · 2018 [cited by examiner]

US 20180253837A1 · Ghesu · 2018 [cited by examiner]

US 20180341989A1 · Reim · 2018 [cited by examiner]

US 20200150672A1 · Naghshvar · 2020 [cited by examiner]

US 20210097445A1 · Devlin · 2021 [cited by examiner]

US 20220318206A1 · Prahlad · 2022 [cited by examiner]

CN 108429259B · 2019 [cited by examiner]

CN 111062373A · 2020 [cited by examiner]

WO WO2019149949A1 · 2019 [cited by examiner]

Blair, J.M., et al., “Rational chebyshev approximations for the inverse of the error function,” Mathematics of Computation, 30(136):827-830, 1976. [cited by applicant]

Brockman, G., et al., “OpenAI Gym,” arXiv preprint arXiv:1606.01540, 2016. [cited by applicant]

Browne, C.B., et al., “A survey of monte carlo tree search methods,” IEEE Transactions on Computational Intelligence and AI in games, 4(1):1-43, 2012. [cited by applicant]

Buckman, J., et al., “Sample-efficient reinforcement learning with stochastic ensemble value expansion,” arXiv preprint arXiv:1807.01675, 2018. [cited by applicant]

Coulom, R. et al., “Efficient selectivity and backup operators in monte-carlo tree search,” In International conference on computers and games, pp. 72-83, Springer 2006. [cited by applicant]

Dalton, S., et al., “Accelerating reinforcement learning through gpu atari emulation,” arXiv preprint arXiv:1907.08467, 2019. [cited by applicant]

Efroni, Y., et al., “Beyond the one-step greedy approach in reinforcement learning,” In International Conference on Machine Learning, pp. 1387-1396, PMLR, 2018. [cited by applicant]

Efroni, Y., et al., “How to combine tree-search methods in reinforcement learning,” Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 2019). [cited by applicant]

Farebrother, J., et al., “Generalization and Regularization in DQN,” arXiv preprint arXiv:1810.00123, 2018. [cited by applicant]

Feinberg, V., et al., “Model-based value estimation for efficient model-free reinforcement learning,” arXiv preprint arXiv:1803.00101, 2018. [cited by applicant]

Ha, D., et al., “World Models,” arXiv preprint arXiv:1803.10122, 2018. [cited by applicant]

Jessel, M., et al., “Rainbow: Combining improvements in deep reinforcement learning,” In Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32, 2018. [cited by applicant]

Jiang, D., et al., “Feedback-based tree search for reinforcement learning,” In International conference on machine earning, pp. 2284-2293, PMLR, 2018. [cited by applicant]

Kaiser, L., et al., “Model-based reinforcement learning for atari,” arXiv preprint arXiv:1903.00374, 2019. [cited by applicant]

Kalweit, G., et al., “Uncertainty-driven imagination for continuous deep reinforcement learning,” In Conference on Robot Learning, pp. 195-206, PMLR, 2017. [cited by applicant]

Kim, S.W., et al., “Learning to simulate dynamic environments with gameGAN,” In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1231-1240, 2020. [cited by applicant]

Krishnan, R., et al., “Deep kalman filters,” arXiv preprint arXiv:1511.05121, 2015. [cited by applicant]

Liang, J., et al., “GPU-accelerated robotic simulation for distributed reinforcement learning,” In Conference on Robot earning, pp. 270-282, PMLR, 2018. [cited by applicant]

Mnih, V., et al., “Playing atari with deep reinforcement learning,” arXiv preprint arXiv:1312.5602, 2013. [cited by applicant]

Moerland, T., et al., “Think too fast nor too slow: the computational trade-off between planning and reinforcement learning,” arXiv preprint arXiv:2005.07404, 2020. [cited by applicant]

Munos, R., et al., “Safe and efficient off-policy reinforcement learning,” Advances in Neural Information Processing Systems, vol. 29, Curran Associates, Inc., 2016. [cited by applicant]

Nagabandi, A., et al., “Neural network dynamics for model-based deep reinforcement learning with model-free fine tuning,” In 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 7559-7566, IEEE, 201… [cited by applicant]

Noreen, I., et al., “Optimal path planning using RRT* based approaches: a survey and future directions,” Int.J.Adv. Comput.Sci.Appl., 7(11):97-101, 2016. [cited by applicant]

Oh, J., et al., “Action-conditional video prediction using deep networks in atari games,” arXiv preprint arXiv:1507:08750, 2015. [cited by applicant]

Weber, T., et al., “Imagination-augmented agents for deep reinforcement learning,” In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 5694-5705, 2017. [cited by applicant]

Schrittwieser, J., et al., “Mastering atari, go, chess and shogi by planning with a learned model,” Nature, 588 (7839):604-609, 2020. [cited by applicant]

Schrittwieser, J., et al., “Online and offline reinforcement learning by planning with a learned model,” arXiv preprint arXiv:2104.06294, 2021. [cited by applicant]

Silver, D., et al., “Mastering the game of go with deep neural networks and tree search,” Nature, 529(7587):484-489, 2016. [cited by applicant]

Silver, D., et al., “Mastering chess and shogi by self-play with a general reinforcement learning algorithm,” arXiv preprint arXiv:1712.01815, 2017. [cited by applicant]

Todorov, E., et al., “Mujoco: a physics engine for model-based control,” In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033, IEEE, 2012. [cited by applicant]

Williams, G., et al., “Information theoretic mpc for model-based reinforcement learning,” In 2017 IEEE International Conference on Robotics and Automation (ICRA), pp. 1714-1721, IEEE, 2017. [cited by applicant]

Zanon, M., et al., “Safe reinforcement learning using robust MPC,” IEEE Transactions on Automatic Control, 2020. [cited by applicant]

“How much did alphago zero cost?” https://www.yuzeh.com/data/agz-cost.html; accessed:May 20, 2021. [cited by applicant]

Mokovlychuk, V., et al., “Isaac Gym: High Performance GPU-Based Physics Simulation For Robot Learning,” arXiv:2108.10470v2, Aug. 25, 2021. [cited by applicant]

Lavalle, S., et al., “Rapidly-Exploring Random Trees: A New Tool for Path Planning,” Iowa State University, Ames, IA. [cited by applicant]