# US 11,113,619 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,113,619 B2 - Document ID: US11113619B2 - Status: Granted - Kind: B2 - Application number: 17/084,268 - Filed: 2020-10-29 - Published: 2021-06-17 - Granted: 2021-09-07 - 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/US11113619B2 ## CPC - G06F 8/30: Creation or generation of source code - G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks - G07F 17/3227: {Configuring a gaming machine, e.g. downloading personal settings, selecting working parameters} - G07F 17/3293: {Card games, e.g. poker, canasta, black jack} - G06Q 10/067: Enterprise or organisation modelling - G06Q 10/08: Logistics, e.g. warehousing, loading or distribution; Inventory or stock management - G06Q 30/0631: {Recommending goods or services} - G06Q 50/40: Business processes related to the transportation industry (shipping G06Q10/083) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - G07F: COIN-FREED OR LIKE APPARATUS (coin sorting G07D3/00; coin testing G07D5/00; {handling coins or paper currencies apart from payment activated apparatus G07D; payment architectures, schemes or protocols G06Q20/00}) - 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, including computer programs encoded on computer storage media, for generating an action selection policy for completing a task in an environment. The method includes identifying multiple possible actions in a state, wherein the state corresponds to a vector of information sets; identifying a vector of current action selection policies in the state, wherein each current action selection policy in the vector of current action selection policies corresponds to an information set in the vector of information sets; computing a sampling policy based on the vector of current action selection policies in the state; sampling an action among the multiple possible actions in the state according to a sampling probability of the action specified in the sampling policy; and updating each current action selection policy of the execution device in the state based on the action. ## 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: identifying, by the execution device, a plurality of possible actions in a state, wherein the state corresponds to a vector of information sets, and each information set in the vector of information sets comprises a sequence of actions taken by the execution device that leads to the state; identifying, by the execution device, a vector of current action selection policies in the state, wherein each current action selection policy in the vector of current action selection policies corresponds to an information set in the vector of information sets, and the action selection policy specifies a respective probability of selecting an action among the plurality of possible actions in the state; computing, by the execution device, a sampling policy based on the vector of current action selection policies in the state, wherein the sampling policy specifies a respective sampling probability corresponding to each of the plurality of possible actions in the state; sampling, by the execution device, an action among the plurality of possible actions in the state according to a sampling probability of the action specified in the sampling policy; and updating, by the execution device, the each current action selection policy in the vector of current action selection policies of the execution device in the state based on the action. ### 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 based on the action selection policy. ### Claim 3 (depends on 1) The computer-implemented method of claim 1, wherein updating the each current action selection policy in the vector of current action selection policies of the execution device in the state based on the action comprises performing Monte Carlo counterfactual regret minimization (MCCFR) based on the action. ### Claim 4 (depends on 1) The computer-implemented method of claim 1, wherein updating the each current action selection policy in the vector of current action selection policies of the execution device in the state based on the action comprises: calculating a probability of a sampled terminal sequence of actions based on the sampling probability of the action, the sampled terminal sequence of actions including the action and a terminal state for completing a task; calculating a sampled counterfactual value of the action based on the probability of the sampled terminal sequence of actions; calculating a regret value of the action based on the sampled counterfactual value of the action; and updating the each of the vector of current action selection policies of the execution device in the state based on the regret value of the action. ### Claim 5 (depends on 1) The computer-implemented method of claim 1, wherein the state corresponds to a public sequence that comprises one or more actions publically known by the execution device and the one or more other devices; and the each information set in the vector of information sets comprises the public sequence. ### Claim 6 (depends on 1) The computer-implemented method of claim 1, wherein computing a sampling policy based on the vector of current action selection policies of the execution device in the state comprises: computing the sampling probability corresponding to each of the plurality of possible actions in the state as a mean value of current action selection policies of each of the plurality of possible actions in the state over the vector of information sets. ### Claim 7 (depends on 1) The computer-implemented method of claim 1, wherein computing a sampling policy based on the vector of current action selection policies of the execution device in the state comprises: computing the sampling probability corresponding to each of the plurality of possible actions in the state based on current action selection policies of each of the plurality of possible actions in the state and respective reach probabilities of the vector of information sets. ### Claim 8 (depends on 7) The computer-implemented method of claim 7, wherein computing the sampling probability corresponding to each of the plurality of possible actions in the state based on current action selection policies of each of the plurality of possible actions in the state and respective reach probabilities of the vector of information sets comprises: computing the sampling probability corresponding to each of the plurality of possible actions in the state based on a sum of the current action selection policies of each of the plurality of possible actions in the state weighted by the respective reach probabilities of the vector of information sets. ### Claim 9 (depends on 1) The computer-implemented method of claim 1, wherein computing a sampling policy based on the vector of current action selection policies of the execution device in the state comprises: computing the sampling probability corresponding to each of the plurality of possible actions in the state based on average action selection policies of each of the plurality of possible actions in the state and respective reach probabilities of the vector of information sets. ### Claim 10 (depends on 9) The computer-implemented method of claim 9, wherein computing the sampling probability corresponding to each of the plurality of possible actions in the state based on average action selection policies of each of the plurality of possible actions in the state and respective reach probabilities of the vector of information sets comprises: computing the sampling probability corresponding to each of the plurality of possible actions in the state based on a sum of the average action selection policies of each of the plurality of possible actions in the state weighted by the respective reach probabilities of the vector of information sets. ### Claim 11 A non-transitory, computer-readable medium storing one or more instructions executable by a computer system to perform operations comprising: identifying a plurality of possible actions in a state, wherein the state corresponds to a vector of information sets, and each information set in the vector of information sets comprises a sequence of actions taken by an execution device that leads to the state; identifying a vector of current action selection policies in the state, wherein each current action selection policy in the vector of current action selection policies corresponds to an information set in the vector of information sets, and an action selection policy specifies a respective probability of selecting an action among the plurality of possible actions in the state; computing a sampling policy based on the vector of current action selection policies in the state, wherein the sampling policy specifies a respective sampling probability corresponding to each of the plurality of possible actions in the state; sampling an action among the plurality of possible actions in the state according to a sampling probability of the action specified in the sampling policy; and updating the each current action selection policy in the vector of current action selection policies of the execution device in the state based on the action. ### Claim 12 (depends on 11) The non-transitory, computer-readable medium of claim 11, further comprising, in response to determining that a convergence condition is met, controlling operations of the execution device based on the action selection policy. ### Claim 13 (depends on 11) The non-transitory, computer-readable medium of claim 11, wherein updating the each current action selection policy in the vector of current action selection policies of the execution device in the state based on the action comprises performing Monte Carlo counterfactual regret minimization (MCCFR) based on the action. ### Claim 14 (depends on 11) The non-transitory, computer-readable medium of claim 11, wherein updating the each current action selection policy in the vector of current action selection policies of the execution device in the state based on the action comprises: calculating a probability of a sampled terminal sequence of actions based on the sampling probability of the action, the sampled terminal sequence of actions including the action and a terminal state for completing a task; calculating a sampled counterfactual value of the action based on the probability of the sampled terminal sequence of actions; calculating a regret value of the action based on the sampled counterfactual value of the action; and updating the each of the vector of current action selection policies of the execution device in the state based on the regret value of the action. ### Claim 15 (depends on 11) The non-transitory, computer-readable medium of claim 11, wherein the state corresponds to a public sequence that comprises one or more actions publically known by the execution device and one or more other devices; and the each information set in the vector of information sets comprises the public sequence. ### Claim 16 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: identifying a plurality of possible actions in a state, wherein the state corresponds to a vector of information sets, and each information set in the vector of information sets comprises a sequence of actions taken by an execution device that leads to the state; identifying a vector of current action selection policies in the state, wherein each current action selection policy in the vector of current action selection policies corresponds to an information set in the vector of information sets, and an action selection policy specifies a respective probability of selecting an action among the plurality of possible actions in the state; computing a sampling policy based on the vector of current action selection policies in the state, wherein the sampling policy specifies a respective sampling probability corresponding to each of the plurality of possible actions in the state; sampling an action among the plurality of possible actions in the state according to a sampling probability of the action specified in the sampling policy; and updating the each current action selection policy in the vector of current action selection policies of the execution device in the state based on the action. ### Claim 17 (depends on 16) The computer-implemented system of claim 16, further comprising, in response to determining that a convergence condition is met, controlling operations of the execution device based on the action selection policy. ### Claim 18 (depends on 16) The computer-implemented system of claim 16, wherein updating the each current action selection policy in the vector of current action selection policies of the execution device in the state based on the action comprises performing Monte Carlo counterfactual regret minimization (MCCFR) based on the action. ### Claim 19 (depends on 16) The computer-implemented system of claim 16, wherein updating the each current action selection policy in the vector of current action selection policies of the execution device in the state based on the action comprises: calculating a probability of a sampled terminal sequence of actions based on the sampling probability of the action, the sampled terminal sequence of actions including the action and a terminal state for completing a task; calculating a sampled counterfactual value of the action based on the probability of the sampled terminal sequence of actions; calculating a regret value of the action based on the sampled counterfactual value of the action; and updating the each of the vector of current action selection policies of the execution device in the state based on the regret value of the action. ### Claim 20 (depends on 16) The computer-implemented system of claim 16, wherein the state corresponds to a public sequence that comprises one or more actions publically known by the execution device and one or more other devices; and the each information set in the vector of information sets comprises the public sequence.