# US 10,765,949 B1 · 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 10,765,949 B1
- Document ID: US10765949B1
- Status: Granted
- Kind: B1
- Application number: 16/712,509
- Filed: 2019-12-12
- Granted: 2020-09-08
- Earliest claimed: 2019-05-15
- Assignees: Alibaba Group Holding Limited
- Applicants: Alibaba Group Holding Limited
- Inventors: Hui Li; Le Song
- Web page: https://patentgrep.com/patent/US10765949B1

## CPC

- A63F 13/67: adaptively or by learning from player actions, e.g. skill level adjustment or by storing successful combat sequences for re-use
- G06Q 10/04: Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202)
- A63F 13/35: Details of game servers
- A63F 13/47: involving branching, e.g. choosing one of several possible scenarios at a given point in time
- A63F 13/49: Saving the game status; Pausing or ending the game
- A63F 13/69: by enabling or updating specific game elements, e.g. unlocking hidden features, items, levels or versions
- A63F 13/79: involving player-related data, e.g. identities, accounts, preferences or play histories
- A63F 13/822: Strategy games; Role-playing games (A63F13/825, A63F13/828 take precedence)
- A63F 13/847: Cooperative playing, e.g. requiring coordinated actions from several players to achieve a common goal
- A63F 13/85: Providing additional services to players
- A63F 13/803: Driving vehicles or craft, e.g. cars, airplanes, ships, robots or tanks
- 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

## Abstract

Disclosed herein are methods, systems, and apparatus for generating an action selection policy (ASP) for an execution device. One method includes obtaining an ASP in a current iteration; obtaining a respective first reward for each action in a current state; computing a first reward of the current state based on the respective first rewards for the actions and the ASP; computing a respective regret value of each action based on a difference between the respective first reward for the action and the first reward for the current state; computing an incremental ASP based on the respective regret value of the each action in the current iteration; computing a second reward for the current state based on the incremental ASP; determining an ASP in a next iteration based on the second reward of the current state; and controlling actions of the execution device according to the ASP.

## Claims

### Claim 1

A computer-implemented method for generating an action selection policy for causing an execution device to complete a task in an environment that includes the execution device and one or more other devices, the method comprising:
at a current iteration of a plurality of iterations,
obtaining, by a computer system, an action selection policy in the current iteration, wherein the action selection policy specifies a respective probability of selecting an action among a plurality of possible actions in a current state of the execution device, wherein the current state results from a previous action taken by the execution device in a previous state, and each action of the plurality of possible actions leads to a respective next state if performed by the execution device when the execution device is in the current state;
obtaining, by the computer system, a respective first reward for each action of the plurality of possible actions in the current state, wherein the respective first reward for the action represents a gain attributed to the action towards completing the task;
computing, by the computer system, a first reward for the current state based on respective first rewards for the plurality of possible actions and the action selection policy in the current iteration, wherein the first reward for the current state represents a gain attributed to the current state towards completing the task;
computing, by the computer system, a respective regret value of each action of the plurality of possible actions based on a difference between the respective first reward for the action and the first reward for the current state;
computing, by the computer system, an incremental action selection policy based on the respective regret value of the action in the current iteration but not any regret value of the action in any iteration prior to the current iteration, wherein the incremental action selection policy is used for determining an action selection policy in a next iteration;
computing, by the computer system, a second reward for the current state based on the respective first rewards for the plurality of possible actions and the incremental action selection policy, wherein the second reward for the current state includes partial information of the action selection policy in the next iteration; and
determining, by the computer system, the action selection policy in the next iteration based on the second reward of the current state; and
controlling actions of the execution device according to the action selection policy.

### Claim 2 (depends on 1)

The method of claim 1, wherein obtaining a respective first reward for each action comprises obtaining a respective first reward for the action by traversing a game tree that represents the environment based on an action selection policy in a previous iteration.

### Claim 3 (depends on 1)

The method of claim 1, wherein computing a first reward for the current state based on respective first rewards for the plurality of possible actions and the action selection policy in the current iteration comprises computing the first reward for the current state based on a sum of the respective first rewards for the plurality of possible actions weighted by corresponding probabilities of selecting the plurality of possible actions in the current iteration.

### Claim 4 (depends on 1)

The method of claim 1, wherein determining the action selection policy in the next iteration comprises determining the action selection policy in the next iteration based on a weighted sum of the action selection policy in the current iteration and the incremental action selection policy.

### Claim 5 (depends on 1)

The method of claim 1, further comprising replacing the first reward for the current state with the second reward for the current state.

### Claim 6 (depends on 1)

The method of claim 1, wherein determining the action selection policy in the next iteration based on the second reward of the current state comprises computing a probability of selecting the previous action among a plurality of possible actions in the previous state in the next iteration based on the second reward for the current state.

### Claim 7 (depends on 6)

The method of claim 6, wherein computing a probability of selecting the previous action among the plurality of possible actions in the previous state in the next iteration based on the second reward for the current state comprises:
computing a first reward for the previous state based on the second reward for the current state;
computing a regret value of the previous action based on a difference between the first reward for the previous action in the previous state and the first reward for the previous state; and
computing the probability of selecting the previous action among the plurality of possible actions in the previous state in the next iteration based on the regret value of the previous action.

### Claim 8 (depends on 1)

The method of claim 1, wherein:
the environment comprises a traffic routing environment,
the execution device comprises a computer-assisted vehicle,
the action selection policy comprises a route selection policy for controlling directions of the computer-assisted vehicle, and
controlling operations of the execution device according to the action selection policy comprises controlling directions of the computer-assisted vehicle according to the route selection policy.

### Claim 9

A system 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 a current iteration of a plurality of iterations,
obtaining an action selection policy in the current iteration, wherein the action selection policy specifies a respective probability of selecting an action among a plurality of possible actions in a current state of the execution device, wherein the current state results from a previous action taken by the execution device in a previous state, and each action of the plurality of possible actions leads to a respective next state if performed by the execution device when the execution device is in the current state;
obtaining a respective first reward for each action of the plurality of possible actions in the current state, wherein the respective first reward for the action represents a gain attributed to the action towards completing the task;
computing a first reward for the current state based on respective first rewards for the plurality of possible actions and the action selection policy in the current iteration, wherein the first reward for the current state represents a gain attributed to the current state towards completing the task;
computing a respective regret value of each action of the plurality of possible actions based on a difference between the respective first reward for the action and the first reward for the current state;
computing an incremental action selection policy based on the respective regret value of the action in the current iteration but not any regret value of the action in any iteration prior to the current iteration, wherein the incremental action selection policy is used for determining an action selection policy in a next iteration;
computing a second reward for the current state based on the respective first rewards for the plurality of possible actions and the incremental action selection policy, wherein the second reward for the current state includes partial information of the action selection policy in the next iteration; and
determining the action selection policy in the next iteration based on the second reward of the current state; and
controlling actions of the execution device according to the action selection policy.

### Claim 10 (depends on 9)

The system of claim 9, wherein obtaining a respective first reward for each action comprises obtaining a respective first reward for the action by traversing a game tree that represents the environment based on an action selection policy in a previous iteration.

### Claim 11 (depends on 9)

The system of claim 9, wherein computing a first reward for the current state based on respective first rewards for the plurality of possible actions and the action selection policy in the current iteration comprises computing the first reward for the current state based on a sum of the respective first rewards for the plurality of possible actions weighted by corresponding probabilities of selecting the plurality of possible actions in the current iteration.

### Claim 12 (depends on 9)

The system of claim 9, wherein determining the action selection policy in the next iteration comprises determining the action selection policy in the next iteration based on a weighted sum of the action selection policy in the current iteration and the incremental action selection policy.

### Claim 13 (depends on 9)

The system of claim 9, the operations further comprising replacing the first reward for the current state with the second reward for the current state.

### Claim 14 (depends on 9)

The system of claim 9, wherein determining the action selection policy in the next iteration based on the second reward of the current state comprises computing a probability of selecting the previous action among a plurality of possible actions in the previous state in the next iteration based on the second reward for the current state.

### Claim 15 (depends on 14)

The system of claim 14, wherein computing a probability of selecting the previous action among the plurality of possible actions in the previous state in the next iteration based on the second reward for the current state comprises:
computing a first reward for the previous state based on the second reward for the current state;
computing a regret value of the previous action based on a difference between the first reward for the previous action in the previous state and the first reward for the previous state; and
computing the probability of selecting the previous action among the plurality of possible actions in the previous state in the next iteration based on the regret value of the previous action.

### Claim 16 (depends on 9)

The system of claim 9, wherein:
the environment comprises a traffic routing environment,
the execution device comprises a computer-assisted vehicle,
the action selection policy comprises a route selection policy for controlling directions of the computer-assisted vehicle, and
controlling operations of the execution device according to the action selection policy comprises controlling directions of the computer-assisted vehicle according to the route selection policy.

### Claim 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 a current iteration of a plurality of iterations,
obtaining an action selection policy in the current iteration, wherein the action selection policy specifies a respective probability of selecting an action among a plurality of possible actions in a current state of the execution device, wherein the current state results from a previous action taken by the execution device in a previous state, and each action of the plurality of possible actions leads to a respective next state if performed by the execution device when the execution device is in the current state;
obtaining a respective first reward for each action of the plurality of possible actions in the current state, wherein the respective first reward for the action represents a gain attributed to the action towards completing the task;
computing a first reward for the current state based on respective first rewards for the plurality of possible actions and the action selection policy in the current iteration, wherein the first reward for the current state represents a gain attributed to the current state towards completing the task;
computing a respective regret value of each action of the plurality of possible actions based on a difference between the respective first reward for the action and the first reward for the current state;
computing an incremental action selection policy based on the respective regret value of the action in the current iteration but not any regret value of the action in any iteration prior to the current iteration, wherein the incremental action selection policy is used for determining an action selection policy in a next iteration;
computing a second reward for the current state based on the respective first rewards for the plurality of possible actions and the incremental action selection policy, wherein the second reward for the current state includes partial information of the action selection policy in the next iteration; and
determining the action selection policy in the next iteration based on the second reward of the current state; and
controlling actions of the execution device according to the action selection policy.

### Claim 18 (depends on 17)

The non-transitory, computer-readable storage medium of claim 17, wherein obtaining a respective first reward for each action comprises obtaining a respective first reward for the action by traversing a game tree that represents the environment based on an action selection policy in a previous iteration.

### Claim 19 (depends on 17)

The non-transitory, computer-readable storage medium of claim 17, wherein computing a first reward for the current state based on respective first rewards for the plurality of possible actions and the action selection policy in the current iteration comprises computing the first reward for the current state based on a sum of the respective first rewards for the plurality of possible actions weighted by corresponding probabilities of selecting the plurality of possible actions in the current iteration.

### Claim 20 (depends on 17)

The non-transitory, computer-readable storage medium of claim 17, wherein determining the action selection policy in the next iteration comprises determining the action selection policy in the next iteration based on a weighted sum of the action selection policy in the current iteration and the incremental action selection policy.

### Claim 21 (depends on 17)

The non-transitory, computer-readable storage medium of claim 17, the operations further comprising replacing the first reward for the current state with the second reward for the current state.

### Claim 22 (depends on 17)

The non-transitory, computer-readable storage medium of claim 17, wherein determining the action selection policy in the next iteration based on the second reward of the current state comprises computing a probability of selecting the previous action among a plurality of possible actions in the previous state in the next iteration based on the second reward for the current state.

### Claim 23 (depends on 22)

The non-transitory, computer-readable storage medium of claim 22, wherein computing a probability of selecting the previous action among the plurality of possible actions in the previous state in the next iteration based on the second reward for the current state comprises:
computing a first reward for the previous state based on the second reward for the current state;
computing a regret value of the previous action based on a difference between the first reward for the previous action in the previous state and the first reward for the previous state; and
computing the probability of selecting the previous action among the plurality of possible actions in the previous state in the next iteration based on the regret value of the previous action.

### Claim 24 (depends on 17)

The non-transitory, computer-readable storage medium of claim 17, wherein:
the environment comprises a traffic routing environment,
the execution device comprises a computer-assisted vehicle,
the action selection policy comprises a route selection policy for controlling directions of the computer-assisted vehicle, and
controlling operations of the execution device according to the action selection policy comprises controlling directions of the computer-assisted vehicle according to the route selection policy.