# US 2022/0044110 A1 · Controlling agents using reinforcement learning with mixed-integer programming

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

- Number: US 2022/0044110 A1
- Document ID: US20220044110A1
- Status: Published application
- Kind: A1
- Application number: 16/987,246
- Filed: 2020-08-06
- Published: 2022-02-10
- Earliest claimed: 2020-08-06
- Applicants: Google LLC
- Inventors: Mungyung Ryu; Yinlam Chow; Ross Michael Anderson; Christian Tjandraatmadja; Craig Edgar Boutilier
- Web page: https://patentgrep.com/patent/US20220044110A1

## CPC

- G06N 3/08: Learning methods
- G06N 3/045: Combinations of networks
- G06N 3/0464: Convolutional networks [CNN, ConvNet]
- G06N 3/09: Supervised learning
- G06N 3/092: Reinforcement learning
- G06N 3/006: based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
- G06N 3/048: Activation functions
- G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
- G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for training a neural network system used to control an agent interacting with an environment. One of the methods includes obtaining a plurality of transitions that are each generated as a result of an agent interacting with an environment, and training a Q neural network having a mixed-integer programming (MIP) formulation on the transitions. The Q neural network is configured to process an observation and initial action constraints in accordance with the Q network parameters to generate a MIP problem based on a Q value objective and the initial action constraints. The initial action constraints specify a set of possible actions that can be performed by the agent to interact with the environment.

## Claims

### Claim 1

A method comprising:
obtaining a plurality of transitions that are each generated as a result of an agent interacting with an environment, each transition comprising:
a current observation characterizing a current state of the environment,
a current action performed by the agent in response to the current observation,
a reward received in response to the agent performing the current action, and
a next observation characterizing a next state of the environment;
training a Q neural network having a plurality of Q network parameters on the transitions, wherein the Q neural network is configured to process an observation and initial action constraints in accordance with the Q network parameters to generate a mixed-integer programming (MIP) problem based on a Q value objective and the initial action constraints, the initial action constraints specifying a set of possible actions that can be performed by the agent to interact with the environment,
the training comprising, for each of one or more of the plurality of transitions:
processing the next observation and initial action constraints specifying a set of possible next actions to perform in response to the next observation using the Q neural network in accordance with current values of the Q network parameters to generate the mixed-integer programming (MIP) problem including defining a Q value objective function and a set of action constraints;
evaluating the MIP problem to identify a next action that achieves the Q value objective and meets the set of action constraints;
determining, based on the next observation and the next action, a temporal difference learning target for the transition;
determining, based on processing the current observation and initial action constraints specifying the current action using the Q neural network in accordance with current values of the Q network parameters, a current Q value for the transition;
determining a temporal difference learning error for the transition by computing a difference between the current Q value and the temporal difference learning target; and
using the temporal difference learning error in determining an update to the current values of the Q network parameters.

### Claim 2 (depends on 1)

The method of claim 1, wherein generate the mixed-integer programming (MIP) problem including defining the Q value objective function and the set of action constraints comprises:
generating the Q value objective function that specifies the Q value objective and that includes variables that can be adjusted to achieve the objective based on the observation and the set of action constraints, wherein the variables include a plurality of outputs at an output layer of the Q neural network.

### Claim 3 (depends on 2)

The method of claim 2, wherein generate the mixed-integer programming (MIP) problem including defining the Q value objective function and the set of action constraints further comprises:
generating the set of action constraints based on a respective plurality of outputs at one or more piece-wise linear activation layers of the Q neural network.

### Claim 4 (depends on 1)

The method of claim 1, wherein evaluating the MIP problem to identify an action that achieves the Q value objective and meets the initial action constraints comprises:
adjusting, using a dynamic tolerance technique, stopping conditions for a MIP solver that is used to evaluate the MIP problem.

### Claim 5 (depends on 1)

The method of claim 1, wherein determining the temporal difference learning target comprises:
determining, using a dual filtering technique or a clustering technique, an approximate temporal difference learning target that is an estimate of the temporal difference learning target for the transition.

### Claim 6 (depends on 1)

The method of claim 1, further comprising training an actor neural network having a plurality of actor network parameters on the transitions, the training comprising, for each of the one or more of the plurality of transitions:
processing the next observation using the actor neural network in accordance with current values of the actor network parameters to generate an actor network output specifying an estimated next action that is an estimate of the next action identified based on evaluating the MIP problem generated by the Q neural network;
determining a gradient of an actor network loss function with respect to the actor network parameters, wherein the actor network loss function measures a difference between (i) a Q value for the estimated next action specified by the actor network output and (ii) a Q value for the next action identified based on evaluating the MIP problem generated by the Q neural network; and
determining, based on the gradient of the actor network loss function, an update to the current values of the actor network parameters.

### Claim 7 (depends on 6)

The method of claim 6, wherein the Q value for the estimated next action specified by the actor network output is generated based on processing the next observation and initial action constraints specifying the estimated next action using the Q neural network in accordance with current values of the Q network parameters.

### Claim 8 (depends on 6)

The method of claim 6, further comprising:
receiving a new observation characterizing a new state of the environment being interacted with by the agent;
processing the new observation using the actor neural network having the plurality of actor network parameters to generate an actor network output specifying an estimated action that is an estimate of the action that would be identified by evaluating the MIP problem generated by the Q neural network based on processing the new observation and initial action constraints; and
causing the agent to perform the estimated action.

### Claim 9 (depends on 8)

The method of claim 8, wherein generating the actor network output specifying the estimated action comprises:
adding exploration noise to the actor network output.

### Claim 10 (depends on 1)

The method of claim 1, wherein the possible set of actions is a continuous set of actions.

### Claim 11 (depends on 1)

The method of claim 1, further comprising:
receiving the new observation characterizing the new state of the environment being interacted with by the agent;
processing the new observation and the initial action constraints using the Q neural network to generate the mixed-integer programming (MIP) problem including defining a Q value objective function and a set of action constraints;
evaluating the MIP problem to identify an action that achieves the Q value objective and meets the set of action constraints; and
causing the agent to perform the identified action.

### Claim 12

A system comprising one or more computers and one or more storage devices storing instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
obtaining a plurality of transitions that are each generated as a result of an agent interacting with an environment, each transition comprising:
a current observation characterizing a current state of the environment,
a current action performed by the agent in response to the current observation,
a reward received in response to the agent performing the current action, and
a next observation characterizing a next state of the environment;
training a Q neural network having a plurality of Q network parameters on the transitions, wherein the Q neural network is configured to process an observation and initial action constraints in accordance with the Q network parameters to generate a mixed-integer programming (MIP) problem based on a Q value objective and the initial action constraints, the initial action constraints specifying a set of possible actions that can be performed by the agent to interact with the environment,
the training comprising, for each of one or more of the plurality of transitions:
processing the next observation and initial action constraints specifying a set of possible next actions to perform in response to the next observation using the Q neural network in accordance with current values of the Q network parameters to generate the mixed-integer programming (MIP) problem including defining a Q value objective function and a set of action constraints;
evaluating the MIP problem to identify a next action that achieves the Q value objective and meets the set of action constraints;
determining, based on the next observation and the next action, a temporal difference learning target for the transition;
determining, based on processing the current observation and initial action constraints specifying the current action using the Q neural network in accordance with current values of the Q network parameters, a current Q value for the transition;
determining a temporal difference learning error for the transition by computing a difference between the current Q value and the temporal difference learning target; and
using the temporal difference learning error in determining an update to the current values of the Q network parameters.

### Claim 13 (depends on 12)

The system of claim 12, wherein generate the mixed-integer programming (MIP) problem including defining the Q value objective function and the set of action constraints comprises:
generating the Q value objective function that specifies the Q value objective and that includes variables that can be adjusted to achieve the objective based on the observation and the set of action constraints, wherein the variables include a plurality of outputs at an output layer of the Q neural network.

### Claim 14 (depends on 13)

The system of claim 13, wherein generate the mixed-integer programming (MIP) problem including defining the Q value objective function and the set of action constraints further comprises:
generating the set of action constraints based on a respective plurality of outputs at one or more piece-wise linear activation layers of the Q neural network.

### Claim 15 (depends on 12)

The system of claim 12, wherein the operations further comprise training an actor neural network having a plurality of actor network parameters on the transitions, the training comprising, for each of the one or more of the plurality of transitions:
processing the next observation using the actor neural network in accordance with current values of the actor network parameters to generate an actor network output specifying an estimated next action that is an estimate of the next action identified based on evaluating the MIP problem generated by the Q neural network;
determining a gradient of an actor network loss function with respect to the actor network parameters, wherein the actor network loss function measures a difference between (i) a Q value for the estimated next action specified by the actor network output and (ii) a Q value for the next action identified based on evaluating the MIP problem generated by the Q neural network; and
determining, based on the gradient of the actor network loss function, an update to the current values of the actor network parameters.

### Claim 16 (depends on 15)

The system of claim 15, wherein the Q value for the estimated next action specified by the actor network output is generated based on processing the next observation and initial action constraints specifying the estimated next action using the Q neural network in accordance with current values of the Q network parameters.

### Claim 17 (depends on 15)

The system of claim 15, wherein the operations further comprise:
receiving a new observation characterizing a new state of the environment being interacted with by the agent;
processing the new observation using the actor neural network having the plurality of actor network parameters to generate an actor network output specifying an estimated action that is an estimate of the action that would be identified by evaluating the MIP problem generated by the Q neural network based on processing the new observation and initial action constraints; and
causing the agent to perform the estimated action.

### Claim 18 (depends on 12)

The system of claim 12, wherein the operations further comprise:
receiving the new observation characterizing the new state of the environment being interacted with by the agent;
processing the new observation and the initial action constraints using the Q neural network to generate the mixed-integer programming (MIP) problem including defining a Q value objective function and a set of action constraints;
evaluating the MIP problem to identify an action that achieves the Q value objective and meets the set of action constraints; and
causing the agent to perform the identified action.

### Claim 19

One or more computer-readable storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:
obtaining a plurality of transitions that are each generated as a result of an agent interacting with an environment, each transition comprising:
a current observation characterizing a current state of the environment,
a current action performed by the agent in response to the current observation,
a reward received in response to the agent performing the current action, and
a next observation characterizing a next state of the environment;
training a Q neural network having a plurality of Q network parameters on the transitions, wherein the Q neural network is configured to process an observation and initial action constraints in accordance with the Q network parameters to generate a mixed-integer programming (MIP) problem based on a Q value objective and the initial action constraints, the initial action constraints specifying a set of possible actions that can be performed by the agent to interact with the environment,
the training comprising, for each of one or more of the plurality of transitions:
processing the next observation and initial action constraints specifying a set of possible next actions to perform in response to the next observation using the Q neural network in accordance with current values of the Q network parameters to generate the mixed-integer programming (MIP) problem including defining a Q value objective function and a set of action constraints;
evaluating the MIP problem to identify a next action that achieves the Q value objective and meets the set of action constraints;
determining, based on the next observation and the next action, a temporal difference learning target for the transition;
determining, based on processing the current observation and initial action constraints specifying the current action using the Q neural network in accordance with current values of the Q network parameters, a current Q value for the transition;
determining a temporal difference learning error for the transition by computing a difference between the current Q value and the temporal difference learning target; and
using the temporal difference learning error in determining an update to the current values of the Q network parameters.

### Claim 20 (depends on 19)

The computer-readable storage media of claim 19, wherein the operations further comprise training an actor neural network having a plurality of actor network parameters on the transitions, the training comprising, for each of the one or more of the plurality of transitions:
processing the next observation using the actor neural network in accordance with current values of the actor network parameters to generate an actor network output specifying an estimated next action that is an estimate of the next action identified based on evaluating the MIP problem generated by the Q neural network;
determining a gradient of an actor network loss function with respect to the actor network parameters, wherein the actor network loss function measures a difference between (i) a Q value for the estimated next action specified by the actor network output and (ii) a Q value for the next action identified based on evaluating the MIP problem generated by the Q neural network; and
determining, based on the gradient of the actor network loss function, an update to the current values of the actor network parameters.