Rating tasks and policies using conditional probability distributions derived from equilibrium-based solutions of games

Patent metadata

Field	Value
Publication number	US-12151171-B2
Application number	US-202217963113-A
Country	US
Kind code	B2
Filing date	Oct 10, 2022
Priority date	Oct 8, 2021
Publication date	Nov 26, 2024
Grant date	Nov 26, 2024

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for rating tasks and policies using conditional probability distributions derived from equilibrium-based solutions of games. One of the methods includes: determining, for each action selection policy in a pool of action selection policies, a respective performance measure of the action selection policy on each task in a pool of tasks, processing the performance measures of the action selection policies on the tasks to generate data defining a joint probability distribution over a set of action selection policy-task pairs, and processing the joint probability distribution over the set of action selection policy-task pairs to generate a respective rating for each action selection policy in the pool of action selection policies, where the respective rating for each action selection policy characterizes a utility of the action selection policy in performing tasks from the pool of tasks.

First claim

What is claimed is:

1. A method performed by one or more computers, the method comprising:
determining, for each action selection policy in a pool of action selection policies, a respective performance measure of the action selection policy on each task in a pool of tasks, wherein each action selection policy defines a policy for selecting actions to be performed by an agent in an environment;
processing the performance measures of the action selection policies on the tasks to generate data defining a joint probability distribution over a set of action selection policy-task pairs,
wherein each action selection policy-task pair comprises a respective action selection policy from the pool of action selection policies and a respective task from the pool of tasks; and

processing the joint probability distribution over the set of action selection policy-task pairs to generate a respective rating for each action selection policy in the pool of action selection policies, wherein the respective rating for each action selection policy characterizes a utility of the action selection policy in performing tasks from the pool of tasks.

2. The method of claim 1 , further comprising:
selecting an action selection policy from the pool of action selection policies in accordance with the ratings for the action selection policies; and
selecting actions to be performed by an agent to interact with an environment using the selected action selection policy.

3. The method of claim 1 , further comprising:
updating the pool of action selection policies based on the ratings of the action selection policies.

4. The method of claim 3 , wherein updating the pool of action selection policies based on the ratings of the action selection policies comprises:
selecting one or more action selection policies for removal from the pool of action selection policies based on the ratings of the action selection policies; and
removing the selected action selection policies from the pool of action selection policies.

5. The method of claim 4 , wherein selecting one or more action selection policies for removal from the pool of action selection policies based on the ratings of the action selection policies comprises:
selecting one or more action selection policies associated with the lowest ratings from among the pool of action selection policies for removal from the pool of action selection policies.

6. The method of claim 3 , wherein updating the pool of action selection policies based on the ratings of the action selection policies comprises:
selecting one or more action selection policies for reproduction in the pool of action selection policies based on the ratings of the action selection policies; and
adding one or more new action selection policies to the pool of action selection policies based on the action selection policies selected for reproduction.

7. The method of claim 6 , wherein selecting one or more action selection policies for reproduction in the pool of action selection policies based on the ratings of the action selection policies comprises:
selecting one or more action selection policies associated with the highest ratings from among the pool of action selection policies for reproduction in the pool of action selection policies.

8. The method of claim 1 , wherein the joint probability distribution over the set of action selection policy-task pairs is an equilibrium-based solution of a game,
wherein the game is defined by performance measures of the action selection policies on the tasks.

9. The method of claim 8 , wherein the game includes a first player that selects an action selection policy from the pool of action selection policies and a second player that selects a task from the pool of tasks, and wherein a respective payoff received by each player is based on a performance of an agent controlled by the action selection policy selected by the first player on the task selected by the second player.

10. The method of claim 8 , wherein the equilibrium-based solution of the game is a Nash equilibrium solution of the game.

11. The method of claim 8 , wherein the equilibrium-based solution of the game is a correlated equilibrium solution of the game.

12. The method of claim 8 , wherein the equilibrium-based solution of the game is a coarse-correlated equilibrium solution of the game.

13. The method of claim 1 , wherein processing the joint probability distribution over the set of action selection policy-task pairs to generate a respective rating for each action selection policy in the pool of action selection policies comprises, for each given action selection policy:
determining the rating for the given action selection policy based on a conditional probability distribution over the pool of tasks, wherein the conditional probability distribution over the pool of tasks is defined by conditioning the joint probability distribution over the set of action selection policy-task pairs on the given action selection policy.

14. The method of claim 13 , wherein for each given action selection policy, determining the rating for the given action selection policy based on the conditional probability distribution over the pool of tasks comprises:
determining an expected value of a performance measure of the given action selection policy on the pool of tasks when the tasks are selected in accordance with the conditional probability distribution over the pool of tasks.

15. The method of claim 1 , wherein the environment is a real-world environment.

16. The method of claim 15 , wherein each action selection policy in the pool of action selection policies defines a policy for selecting actions to be performed by a mechanical agent to interact with the real-world environment.

17. The method of claim 1 , wherein one or more of the action selection policies in the pool of action selection policies is defined by a respective action selection neural network that is configured to process an input comprising an observation of the environment to generate a policy output for selecting an action to be performed by an agent to interact with the environment.

18. A system comprising:
one or more computers; and
one or more storage devices communicatively coupled to the one or more computers, wherein the one or more storage devices store instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising:
determining, for each action selection policy in a pool of action selection policies, a respective performance measure of the action selection policy on each task in a pool of tasks, wherein each action selection policy defines a policy for selecting actions to be performed by an agent in an environment;
processing the performance measures of the action selection policies on the tasks to generate data defining a joint probability distribution over a set of action selection policy-task pairs,
wherein each action selection policy-task pair comprises a respective action selection policy from the pool of action selection policies and a respective task from the pool of tasks; and

processing the joint probability distribution over the set of action selection policy-task pairs to generate a respective rating for each action selection policy in the pool of action selection policies, wherein the respective rating for each action selection policy characterizes a utility of the action selection policy in performing tasks from the pool of tasks.

19. One or more non-transitory computer storage media storing instruct

Assignees

• Deepmind Tech Ltd

Inventors

• Marris Luke Christopher

Classifications

• G06F17/18

  for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} · CPC title

• A63F13/822

  Strategy games; Role-playing games (A63F13/825, A63F13/828 take precedence) · CPC title

• G06N7/01

  Probabilistic graphical models, e.g. probabilistic networks · CPC title

• G06N5/01

  Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound · CPC title

• G06N3/006

  based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO] · CPC title