Gradient boosting reinforcement learning

Abstract

Reinforcement learning, which is a machine learning technique where a model learns to make decisions that maximize a reward, has shown great promise in various domains that involve sequential decision making, including for many real-world tasks, such as inventory management, traffic signal optimization, network optimization, resource allocation, and robotics. However, current neural network (NN) based solutions for reinforcement learning struggle with interpretability, handling categorical data, and supporting light implementations suitable for low-compute devices. The present disclosure provides a gradient boosting trees (GBT) framework that is tailored for reinforcement learning, which may enable interpretability, may be well suited for real-world tasks with structured data, and may be capable of deployment on low-compute devices.

What is claimed is: 
     
         1 . A method, comprising:
 at a device, for each iteration of a plurality of iterations used to train a model comprised of an ensemble of decision trees:   using the ensemble of decision trees to generate parameters for a policy;   generating a trajectory of state and action pairs, by the policy parameterized with the parameters; and   updating the ensemble of decision trees by:
 sampling a batch of the state and action pairs, 
 computing gradients for the batch according to a reinforcement learning objective, 
 constructing a new decision tree fitted to the gradients, and 
 adding the new decision tree to the ensemble of decision trees to form an updated ensemble of decision trees. 
   
     
     
         2 . The method of  claim 1 , wherein for an initial iteration of the plurality of iterations, the ensemble of decision trees is comprised of an initialized decision tree. 
     
     
         3 . The method of  claim 1 , wherein a number of the plurality of iterations is predefined. 
     
     
         4 . The method of  claim 3 , wherein the number of the plurality of iterations is two or more. 
     
     
         5 . The method of  claim 1 , wherein at each iteration the parameters for the policy are generated by summing outputs of decision trees included in the ensemble of decision trees. 
     
     
         6 . The method of  claim 1 , wherein each decision tree in the ensemble of decision trees includes a plurality of leaves each constructed to predict the parameters for the policy. 
     
     
         7 . The method of  claim 1 , wherein the policy is a Gaussian policy. 
     
     
         8 . The method of  claim 1 , wherein the reinforcement learning objective is defined by an actor critic algorithm. 
     
     
         9 . The method of  claim 8 , wherein the actor critic algorithm utilizes a shared approximation for an actor generating the actions and a critic generating rewards. 
     
     
         10 . The method of  claim 1 , further comprising, at the device:
 using the ensemble of decision trees to generate a value function;   computing rewards for the state and action pairs, using the value function.   
     
     
         11 . The method of  claim 10 , wherein the state and action pairs are stored with their rewards. 
     
     
         12 . The method of  claim 11 , wherein sampling the batch of state and action pairs includes sampling the batch of state and action pairs with their corresponding rewards. 
     
     
         13 . The method of  claim 10 , wherein tree-sharing provides differentiated learning rates for the policy and the value function. 
     
     
         14 . The method of  claim 1 , wherein the new decision tree is constructed to minimize an error of a prior tree added to the ensemble of decision trees. 
     
     
         15 . The method of  claim 1 , wherein the new decision tree is constructed from multi-dimensional data that includes the gradients computed for the batch and a state for which each gradient was computed. 
     
     
         16 . The method of  claim 15 , wherein for each dimension of the multi-dimensional data up until a last dimension of the multi-dimensional data, the gradient of the dimension is used for training policy parameters. 
     
     
         17 . The method of  claim 1 , wherein the state and action pairs are randomly sampled. 
     
     
         18 . The method of  claim 1 , wherein for each iteration of the plurality of iterations used to train the model comprised of the ensemble of decision trees, the updating of the ensemble of decision trees is performed a predefined number of times. 
     
     
         19 . The method of  claim 18 , wherein the predefined number of times is one. 
     
     
         20 . The method of  claim 18 , wherein the predefined number of times is two or more. 
     
     
         21 . The method of  claim 1 , further comprising, at the device:
 deploying the trained model.   
     
     
         22 . The method of  claim 21 , wherein the trained model is deployed on a graphics processing unit (GPU). 
     
     
         23 . The method of  claim 21 , wherein the trained model is deployed for use by a downstream application. 
     
     
         24 . The method of  claim 23 , wherein the downstream application is configured to use the trained for model for sequential decision making. 
     
     
         25 . The method of  claim 23 , wherein the downstream application streams input data to the model for obtaining from the model in return an output stream of actions. 
     
     
         26 . The method of  claim 25 , wherein the input data is structured. 
     
     
         27 . The method of  claim 25 , wherein the input data has categorical features. 
     
     
         28 . The method of  claim 23 , wherein the downstream application is a robotics application. 
     
     
         29 . The method of  claim 23 , wherein the downstream application is an autonomous driving application. 
     
     
         30 . The method of  claim 23 , wherein the downstream application is a network congestion control application. 
     
     
         31 . The method of  claim 21 , wherein the trained model is deployed to an edge device. 
     
     
         32 . The method of  claim 31 , wherein the edge device is a network interface card. 
     
     
         33 . The method of  claim 31 , wherein the edge device is a mobile phone. 
     
     
         34 . A system, comprising:
 a non-transitory memory storage comprising instructions; and   one or more processors in communication with the memory, wherein the one or more processors execute the instructions to train a model comprised of an ensemble of decision trees over a plurality of iterations including for each iteration:   using the ensemble of decision trees to generate parameters for a policy;   generating a trajectory of state and action pairs, by the policy parameterized with the parameters; and   updating the ensemble of decision trees by:
 sampling a batch of the state and action pairs, 
 computing gradients for the batch according to a reinforcement learning objective, 
 constructing a new decision tree fitted to the gradients, and 
 adding the new decision tree to the ensemble of decision trees to form an updated ensemble of decision trees. 
   
     
     
         35 . The system of  claim 34 , wherein at each iteration the parameters for the policy are generated by summing outputs of decision trees included in the ensemble of decision trees. 
     
     
         36 . The system of  claim 34 , wherein the reinforcement learning objective is defined by an actor critic algorithm that utilizes a shared approximation for an actor generating the actions and a critic generating rewards. 
     
     
         37 . The system of  claim 34 , wherein the new decision tree is constructed to minimize an error of a prior tree added to the ensemble of decision trees. 
     
     
         38 . The system of  claim 34 , wherein the one or more processors further execute the instructions to:
 deploy the trained model for use by a downstream application in sequential decision making.   
     
     
         39 . The system of  claim 38 , wherein the downstream application is one of:
 a robotics application,   an autonomous driving application, or   a network congestion control application.   
     
     
         40 . A non-transitory computer-readable media storing computer instructions which when executed by one or more processors of a device cause the device to train a model comprised of an ensemble of decision trees over a plurality of iterations including for each iteration:
 using the ensemble of decision trees to generate parameters for a policy;   generating a trajectory of state and action pairs, by the policy parameterized with the parameters; and   updating the ensemble of decision trees by:
 sampling a batch of the state and action pairs, 
 computing gradients for the batch according to a reinforcement learning objective, 
 constructing a new decision tree fitted to the gradients, and 
 adding the new decision tree to the ensemble of decision trees to form an updated ensemble of decision trees. 
   
     
     
         41 . The non-transitory computer-readable media of  claim 40 , wherein the reinforcement learning objective is defined by an actor critic algorithm that utilizes a shared approximation for an actor generating the actions and a critic generating rewards. 
     
     
         42 . The non-transitory computer-readable media of  claim 40 , wherein the one or more processors further execute the instructions to:
 deploy the trained model for use by a downstream application in sequential decision making;   wherein the downstream application is one of:
 a robotics application, 
 an autonomous driving application, or 
 a network congestion control application. 
   
     
     
         43 . A method, comprising:
 at a device:   growing an ensemble of decision trees over a plurality of iterations to continuously learn from an input stream of data; and   outputting the ensemble of decision trees as a model configured to provide sequential decision making.   
     
     
         44 . The method of  claim 43 , wherein the ensemble of decision trees are grown using a reinforcement learning objective. 
     
     
         45 . The method of  claim 44 , wherein the ensemble of decision trees are grown over one or more iterations including for each iteration of the one or more iterations:
 using a current ensemble of decision trees to generate parameters for a policy;   generating a trajectory of state and action pairs, by the policy parameterized with the parameters; and   updating the ensemble of decision trees by:
 sampling a batch of state and action pairs, 
 computing gradients for the batch according to the reinforcement learning objective, 
 constructing a new decision tree fitted to the gradients, and 
   adding the new decision tree to the ensemble of decision trees to form an updated ensemble of decision trees.   
     
     
         46 . The method of  claim 44 , wherein the reinforcement learning objective is defined by an actor critic algorithm. 
     
     
         47 . The method of  claim 46 , wherein the actor critic algorithm utilizes a shared approximation for an actor generating actions and a critic generating rewards. 
     
     
         48 . The method of  claim 43 , wherein the sequential decision making involves streaming input data to the model for obtaining from the model in return an output stream of actions. 
     
     
         49 . The method of  claim 43 , further comprising, at the device:
 deploying the model.   
     
     
         50 . The method of  claim 49 , wherein the model is deployed for use by a downstream application that uses the model for the sequential decision making. 
     
     
         51 . The method of  claim 50 , wherein the downstream application streams input data to the model for obtaining from the model in return an output stream of actions. 
     
     
         52 . The method of  claim 51 , wherein the downstream application is one of:
 a robotics application,   an autonomous driving application, or   a network congestion control application.