# US 11,077,368 B2 · Determining action selection policies of an execution device

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,077,368 B2
- Document ID: US11077368B2
- Status: Granted
- Kind: B2
- Application number: 17/084,363
- Filed: 2020-10-29
- Published: 2021-06-17
- Granted: 2021-08-03
- Earliest claimed: 2019-12-12
- Assignees: Alipay (Hangzhou) Information Technology Co., Ltd.
- Applicants: Alipay (Hangzhou) Information Technology Co., Ltd.
- Inventors: Hui Li; Le Song
- Web page: https://patentgrep.com/patent/US11077368B2

## CPC

- A63F 13/47: involving branching, e.g. choosing one of several possible scenarios at a given point in time
- G06Q 20/405: {Establishing or using transaction specific rules}
- G06F 9/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)}
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06N 3/006: based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
- A63F: CARD, BOARD, OR ROULETTE GAMES; INDOOR GAMES USING SMALL MOVING PLAYING BODIES; VIDEO GAMES; GAMES NOT OTHERWISE PROVIDED FOR
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## 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.

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

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.

### Claim 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 CFVs of the execution device in the child states of the non-terminal state;
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;
computing 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 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.

### Claim 9 (depends on 8)

The non-transitory, computer-readable medium of claim 8, 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.

### Claim 10 (depends on 8)

The non-transitory, computer-readable medium of claim 8, 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.

### Claim 11 (depends on 8)

The non-transitory, computer-readable medium of claim 8, 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.

### Claim 12 (depends on 8)

The non-transitory, computer-readable medium of claim 8, 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.

### Claim 13 (depends on 8)

The non-transitory, computer-readable medium of claim 8, 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.

### Claim 14 (depends on 8)

The non-transitory, computer-readable medium of claim 8, 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.

### Claim 15

A computer-implemented system, comprising:
one or more computers; and
one or more computer memory devices interoperably coupled with the one or more computers and having tangible, non-transitory, machine-readable media storing one or more instructions that, when executed by the one or more computers, perform one or more 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 CFVs of the execution device in the child states of the non-terminal state;
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;
computing 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 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.

### Claim 16 (depends on 15)

The computer-implemented system of claim 15, 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.

### Claim 17 (depends on 15)

The computer-implemented system of claim 15, 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.

### Claim 18 (depends on 15)

The computer-implemented system of claim 15, 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.

### Claim 19 (depends on 15)

The computer-implemented system of claim 15, 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.

### Claim 20 (depends on 15)

The computer-implemented system of claim 15, 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.