Determining action selection policies of an execution device

1. A computer-implemented method of an execution device for generating an action selection policy for completing a task in an environment that includes the execution device and one or more other devices, the method comprising:

at each of a plurality of iterations and for each action among a plurality of possible actions in a state of the execution device in a current iteration, wherein the state of the execution device results from a history of actions taken by the execution device,

obtaining a regret value of the action in the state of the execution device in a previous iteration, wherein the regret value of the action in the state of the execution device represents a difference between a gain of the execution device after taking the action in the state and a gain of the execution device in the state; and

computing a parameterized regret value of the action in the state of the execution device in the previous iteration comprising:

determining a maximum of a nonnegative flooring cutoff regret value and the regret value of the action in the state of the execution device in the previous iteration, and

computing the parameterized regret value by raising the determined maximum to the power of β, where β is a fixed value that is larger than 1;

determining a respective normalized regret value for each of the plurality of possible actions in the previous iteration from parameterized regret values for the plurality of possible actions in the state of the execution device in the previous iteration;

determining, from the normalized regret values, a parameterized action selection policy of the action in the state of the execution device;

determining, from the parameterized action selection policy of the action in the state of the execution device, an action selection policy of the action in the state of the execution device, wherein the action selection policy specifies a probability of selecting the state of the plurality of possible actions; and

controlling operations of the execution device according to the action selection policy.

2. The method of claim 1 , wherein the nonnegative flooring cutoff regret value is less than 10 −1 .

3. The method of claim 1 , wherein β is less than 2.

4. The method of claim 1 , further comprising determining whether a convergence condition is met based on the action selection policy of the action in the state of the execution device in the current iteration.

5. The method of claim 1 , wherein the regret value of the action in the state of the execution device in the previous iteration is an iterative cumulative regret computed based on a difference between a first counterfactual value (CFV) of the action in the state of the execution device in a previous iteration and a second CFV in the state of the execution device in the previous iteration, wherein the first CFV and the second CFV are computed by recursively traversing a game tree that represents the environment based on an action selection policy of the action in the state of the execution device in the previous iteration.

6. The method of claim 1 , wherein the regret value of the action in the state of the execution device in the previous iteration is a cumulative regret computed based on a regret value of the action in the state of the execution device after an iteration prior to the previous iteration and an iterative cumulative regret computed based on a difference between a first counterfactual value (CFV) of the action in the state of the execution device in a previous iteration and a second CFV in the state of the execution device in the previous iteration, wherein the first CFV and the second CFV are computed by recursively traversing a game tree that represents the environment based on an action selection policy of the action in the state of the execution device in the previous iteration.

7. The method of claim 1 , wherein the action selection policy of the action in the state of the execution device in the current iteration is an average action selection policy from a first iteration to the current iteration, wherein the average action selection policy of the action in the state of the execution device in the current iteration is determined based on the parameterized action selection policy of the action in the state of the execution device weighted by a respective reach probability of the state of the execution device in the current iteration.

8. The method of claim 1 , wherein the action selection policy of the action in the state of the execution device in the current iteration is an iterative action selection policy of the action in the state of the execution device in the current iteration, wherein the iterative action selection policy of the action in the state of the execution device in the current iteration is determined based on a weighted sum of the parameterized action selection policy of the action in the state of the execution device in the current iteration and an iterative action selection policy of the action in the state of the execution device in the previous iteration.

9. A system for performing a software-implemented application for generating an action selection policy for completing a task in an environment that includes an execution device and one or more other devices, the system comprising:

one or more processors; and

one or more computer-readable memories coupled to the one or more processors and having instructions stored thereon that are executable by the one or more processors to perform operations comprising:

at each of a plurality of iterations and for each action among a plurality of possible actions in a state of the execution device in a current iteration, wherein the state of the execution device results from a history of actions taken by the execution device,

obtaining a regret value of the action in the state of the execution device in a previous iteration, wherein the regret value of the action in the state of the execution device represents a difference between a gain of the execution device after taking the action in the state and a gain of the execution device in the state; and

computing a parameterized regret value of the action in the state of the execution device in the previous iteration comprising:

determining a maximum of a nonnegative flooring cutoff regret value and the regret value of the action in the state of the execution device in the previous iteration, and

computing the parameterized regret value by raising the determined maximum to the power of β, where β is a fixed value that is larger than 1;

determining a respective normalized regret value for each of the plurality of possible actions in the previous iteration from parameterized regret values for the plurality of possible actions in the state of the execution device in the previous iteration;

determining, from the normalized regret values, a parameterized action selection policy of the action in the state of the execution device;

determining, from the parameterized action selection policy of the action in the state of the execution device, an action selection policy of the action in the state of the execution device, wherein the action selection policy specifies a probability of selecting the state of the plurality of possible actions; and

controlling operations of the execution device according to the action selection policy.

10. The system of claim 9 , wherein the nonnegative flooring cutoff regret value is less than 10 −1 .

11. The system of claim 9 , wherein β is less than 2.

12. The system of claim 9 , the operations further comprising determining whether a convergence condition is met based on the action selection policy of the action in the state of the execution device in the current iteration.

13. The system of claim 9 , wherein the regret value of the action in the state of the execution device in the previous iteration is an iterative cumulative regret computed based on a difference between a first counterfactual value (CFV) of the action in the state of the execution device in a previous iteration and a second CFV in the state of the execution device in the previous iteration, wherein the first CFV and the second CFV are computed by recursively traversing a game tree that represents the environment based on an action selection policy of the action in the state of the execution device in the previous iteration.

14. The system of claim 9 , wherein the regret value of the action in the state of the execution device in the previous iteration is a cumulative regret computed based on a regret value of the action in the state of the execution device after an iteration prior to the previous iteration and an iterative cumulative regret computed based on a difference between a first counterfactual value (CFV) of the action in the state of the execution device in a previous iteration and a second CFV in the state of the execution device in the previous iteration, wherein the first CFV and the second CFV are computed by recursively traversing a game tree that represents the environment based on an action selection policy of the action in the state of the execution device in the previous iteration.

15. The system of claim 9 , wherein the action selection policy of the action in the state of the execution device in the current iteration is an average action selection policy from a first iteration to the current iteration, wherein the average action selection policy of the action in the state of the execution device in the current iteration is determined based on the parameterized action selection policy of the action in the state of the execution device weighted by a respective reach probability of the state of the execution device in the current iteration.

16. The system of claim 9 , wherein the action selection policy of the action in the state of the execution device in the current iteration is an iterative action selection policy of the action in the state of the execution device in the current iteration, wherein the iterative action selection policy of the action in the state of the execution device in the current iteration is determined based on a weighted sum of the parameterized action selection policy of the action in the state of the execution device in the current iteration and an iterative action selection policy of the action in the state of the execution device in the previous iteration.

17. A non-transitory, computer-readable storage medium storing one or more instructions executable by a computer system to perform operations for generating an action selection policy for completing a task in an environment that includes an execution device and one or more other devices, the operations comprising:

at each of a plurality of iterations and for each action among a plurality of possible actions in a state of the execution device in a current iteration, wherein the state of the execution device results from a history of actions taken by the execution device,

obtaining a regret value of the action in the state of the execution device in a previous iteration, wherein the regret value of the action in the state of the execution device represents a difference between a gain of the execution device after taking the action in the state and a gain of the execution device in the state; and

computing a parameterized regret value of the action in the state of the execution device in the previous iteration comprising:

determining a maximum of a nonnegative flooring cutoff regret value and the regret value of the action in the state of the execution device in the previous iteration, and

computing the parameterized regret value by raising the determined maximum to the power of β, where β is a fixed value that is larger than 1;

determining a respective normalized regret value for each of the plurality of possible actions in the previous iteration from parameterized regret values for the plurality of possible actions in the state of the execution device in the previous iteration;

determining, from the normalized regret values, a parameterized action selection policy of the action in the state of the execution device;

determining, from the parameterized action selection policy of the action in the state of the execution device, an action selection policy of the action in the state of the execution device, wherein the action selection policy specifies a probability of selecting the state of the plurality of possible actions; and

controlling operations of the execution device according to the action selection policy.

18. The non-transitory, computer-readable storage medium of claim 17 , wherein the nonnegative flooring cutoff regret value is less than 10 −1 .

19. The non-transitory, computer-readable storage medium of claim 17 , wherein β is less than 2.

20. The non-transitory, computer-readable storage medium of claim 17 , the operations further comprising determining whether a convergence condition is met based on the action selection policy of the action in the state of the execution device in the current iteration.

21. The non-transitory, computer-readable storage medium of claim 17 , wherein the regret value of the action in the state of the execution device in the previous iteration is an iterative cumulative regret computed based on a difference between a first counterfactual value (CFV) of the action in the state of the execution device in a previous iteration and a second CFV in the state of the execution device in the previous iteration, wherein the first CFV and the second CFV are computed by recursively traversing a game tree that represents the environment based on an action selection policy of the action in the state of the execution device in the previous iteration.

22. The non-transitory, computer-readable storage medium of claim 17 , wherein the regret value of the action in the state of the execution device in the previous iteration is a cumulative regret computed based on a regret value of the action in the state of the execution device after an iteration prior to the previous iteration and an iterative cumulative regret computed based on a difference between a first counterfactual value (CFV) of the action in the state of the execution device in a previous iteration and a second CFV in the state of the execution device in the previous iteration, wherein the first CFV and the second CFV are computed by recursively traversing a game tree that represents the environment based on an action selection policy of the action in the state of the execution device in the previous iteration.

23. The non-transitory, computer-readable storage medium of claim 17 , wherein the action selection policy of the action in the state of the execution device in the current iteration is an average action selection policy from a first iteration to the current iteration, wherein the average action selection policy of the action in the state of the execution device in the current iteration is determined based on the parameterized action selection policy of the action in the state of the execution device weighted by a respective reach probability of the state of the execution device in the current iteration.

24. The non-transitory, computer-readable storage medium of claim 17 , wherein the action selection policy of the action in the state of the execution device in the current iteration is an iterative action selection policy of the action in the state of the execution device in the current iteration, wherein the iterative action selection policy of the action in the state of the execution device in the current iteration is determined based on a weighted sum of the parameterized action selection policy of the action in the state of the execution device in the current iteration and an iterative action selection policy of the action in the state of the execution device in the previous iteration.