Determining action selection policies of an execution device

Patent metadata

Field	Value
Publication number	US-11077368-B2
Application number	US-202017084363-A
Country	US
Kind code	B2
Filing date	Oct 29, 2020
Priority date	Dec 12, 2019
Publication date	Aug 3, 2021
Grant date	Aug 3, 2021

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, are described, for generating an action selection policy of an execution device for completing a task in an environment. The method includes, in a current iteration, computing a counterfactual value (CFV) of the execution device in a terminal state based on a payoff of the execution device and a reach probability of other devices reaching the terminal state; computing a baseline-corrected CFV of the execution device in the terminal state; for each non-terminal state having child states, computing a CFV of the execution device in the non-terminal state based on a weighted sum of the baseline-corrected CFVs of the execution device in the child states; computing a baseline-corrected CFV and a CFV baseline of the execution device in the non-terminal state; and determining an action selection policy in the non-terminal state for the next iteration.

First claim

The invention claimed is:

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:
in a current iteration of a plurality of iterations,
computing, by the execution device, a counterfactual value (CFV) of the execution device in a terminal state of completing a task based on a payoff of the execution device at the terminal state and a reach probability of the one or more other devices reaching the terminal state, wherein the terminal state results from a sequence of actions taken at a plurality of non-terminal states by the execution device and by the one or more other devices, wherein each of the plurality of non-terminal states has one or more child states;
computing, by the execution device, a baseline-corrected CFV of the execution device in the terminal state based on the CFV of the execution device in the terminal state, a CFV baseline of the execution device in the terminal state of a previous iteration, or the CFV of the execution device in the terminal state and the CFV baseline of the execution device in the terminal state of the previous iteration;
for each of the non-terminal states and starting from a non-terminal state that has the terminal state and one or more other terminal states as child states:
computing, by the execution device, a CFV of the execution device in the non-terminal state based on a weighted sum of baseline-corrected CFVs of the execution device in the child states of the non-terminal state;
computing, by the execution device, a baseline-corrected CFV of the execution device in the non-terminal state based on the CFV of the execution device in the non-terminal state, a CFV baseline of the execution device in the non-terminal state of a previous iteration, or the CFV of the execution device in the non-terminal state and the CFV baseline of the execution device in the non-terminal state of the previous iteration;
computing, by the execution device, a CFV baseline of the execution device in the non-terminal state of the current iteration based on a weighted sum of the CFV baseline of the execution device in the non-terminal state of the previous iteration and the CFV of the execution device in the non-terminal state or the baseline-corrected CFV of the execution device in the non-terminal state; and
determining, by the execution device, an action selection policy in the non-terminal state for the next iteration based on the baseline-corrected CFV of the execution device in the non-terminal state of the current iteration.

2. The computer-implemented method of claim 1 , further comprising, in response to determining that a convergence condition is met, controlling operations of the execution device in the non-terminal state based on the action selection policy in the non-terminal state for the next iteration.

3. The computer-implemented method of claim 1 , wherein
determining the action selection policy in the non-terminal state for the next iteration based on the baseline-corrected CFV of the execution device in the non-terminal state of the current iteration comprises:
calculating a regret value based on the baseline-corrected CFV of the execution device in the non-terminal state of the current iteration; and
determining the action selection policy in the non-terminal state for the next iteration based on the regret value according to regret matching.

4. The computer-implemented method of claim 1 , wherein the reach probability of the one or more other devices reaching the terminal state comprises a product of probabilities of actions taken by the one or more other devices reach the terminal state.

5. The computer-implemented method of claim 1 , wherein computing a baseline-corrected CFV of the execution device in the non-terminal state based on the CFV of the execution device in the non-terminal state, a CFV baseline of the execution device in the non-terminal state of a previous iteration, or the CFV of the execution device in the non-terminal state and the CFV baseline of the execution device in the non-terminal state of the previous iteration comprises:
computing a sampled CFV baseline of the execution device that takes an action in the terminal state of the previous iteration based on the CFV baseline of the execution device in the terminal state of the previous iteration, a sampling policy of the execution device that takes the action in the terminal state of the previous iteration, and a probability of reaching the terminal state that results from the sequence of actions taken by the execution device;
in response to determining that the action is sampled, computing a baseline-corrected CFV of the execution device that takes the action in the non-terminal state based on the CFV of the execution device in the non-terminal state and the sampled CFV baseline of the execution device that takes the action in the terminal state of the previous iteration; and
in response to determining that the action is not sampled, using the sampled CFV baseline of the execution device that takes the action in the terminal state of the previous iteration as the baseline-corrected CFV of the execution device in the non-terminal state.

6. The computer-implemented method of claim 1 , wherein the weighted sum of the baseline-corrected CFV of the execution device in the terminal state and corresponding baseline-corrected CFVs of the execution device in the one or more other terminal states is computed based on the baseline-corrected CFV of the execution device in the terminal state and corresponding baseline-corrected CFVs of the execution device in the one or more other terminal states weighted by an action selection policy in the non-terminal state in the current iteration.

7. The computer-implemented method of claim 1 , wherein the weighted sum of the CFV baseline of the execution device in the non-terminal state of the previous iteration and the CFV or the baseline-corrected CFV of the execution device in the non-terminal state comprises a sum of:
the CFV baseline of the execution device in the non-terminal state of the previous iteration weighted by a scalar; and
the CFV or the baseline-corrected CFV of the execution device in the non-terminal state weighted by a second scalar and a probability of considering the non-terminal state.

8. A non-transitory, computer-readable medium storing one or more instructions executable by a computer system to perform operations comprising:
in a current iteration of a plurality of iterations,
computing a counterfactual value (CFV) of an execution device in a terminal state of completing a task based on a payoff of the execution device at the terminal state and a reach probability of one or more other devices reaching the terminal state, wherein the terminal state results from a sequence of actions taken at a plurality of non-terminal states by the execution device and by the one or more other devices, wherein each of the plurality of non-terminal states has one or more child states;
computing a baseline-corrected CFV of the execution device in the terminal state based on the CFV of the execution device in the terminal state, a CFV baseline of the execution device in the terminal state of a previous iteration, or the CFV of the execution device in the terminal state and the CFV baseline of the execution device in the terminal state of the previous iteration;
for each of the non-terminal states and starting from a non-terminal state that has the terminal state and one or more other terminal states as child states:
computing a CFV of the execution device in the non-terminal state based on a weighted sum of baseline-corrected

Assignees

• Alipay Hangzhou Inf Tech Co Ltd

Inventors

• Li Hui
• Song Le

Classifications

• G06N5/01

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

• G06N7/01

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

• G06N3/006

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

• G06F9/5038

  considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups) · CPC title

• G06Q20/405 Primary

  Establishing or using transaction specific rules · CPC title