Thompson strategy based online reinforcement learning system for action selection
First Claim
1. An online reinforcement learning system comprising components embodied on a computer readable storage medium, the components when executed by one or more processors, update a model based upon reinforcement learning, the components comprising:
- a model comprising an influence diagram with at least one chance node, the model receiving an input and providing a probability distribution associated with uncertainty regarding parameters of the model;
a decision engine that selects an action based, at least in part, upon the probability distribution, the decision engine employing a Thompson strategy heuristic technique to maximize long term expected utility when selecting the action, wherein the decision engine decreases a variance of a distribution of the parameters as a last decision instance is approached; and
a computer-implemented reinforcement learning component that modifies at least one of the parameters of the model based upon feedback associated with the selected action, the parameters defining distributions over discrete variables and continuous variables, uncertainty of the parameters expressed using Dirichlet priors for conditional distributions of discrete variables of the model, and, Normal-Wishart priors for distributions of continuous variables of the model, wherein the modified model is stored.
2 Assignments
0 Petitions
Accused Products
Abstract
A system and method for online reinforcement learning is provided. In particular, a method for performing the explore-vs.-exploit tradeoff is provided. Although the method is heuristic, it can be applied in a principled manner while simultaneously learning the parameters and/or structure of the model (e.g., Bayesian network model).
The system includes a model which receives an input (e.g., from a user) and provides a probability distribution associated with uncertainty regarding parameters of the model to a decision engine. The decision engine can determine whether to exploit the information known to it or to explore to obtain additional information based, at least in part, upon the explore-vs.-exploit tradeoff (e.g., Thompson strategy). A reinforcement learning component can obtain additional information (e.g., feedback from a user) and update parameter(s) and/or the structure of the model. The system can be employed in scenarios in which an influence diagram is used to make repeated decisions and maximization of long-term expected utility is desired.
137 Citations
17 Claims
-
1. An online reinforcement learning system comprising components embodied on a computer readable storage medium, the components when executed by one or more processors, update a model based upon reinforcement learning, the components comprising:
-
a model comprising an influence diagram with at least one chance node, the model receiving an input and providing a probability distribution associated with uncertainty regarding parameters of the model; a decision engine that selects an action based, at least in part, upon the probability distribution, the decision engine employing a Thompson strategy heuristic technique to maximize long term expected utility when selecting the action, wherein the decision engine decreases a variance of a distribution of the parameters as a last decision instance is approached; and a computer-implemented reinforcement learning component that modifies at least one of the parameters of the model based upon feedback associated with the selected action, the parameters defining distributions over discrete variables and continuous variables, uncertainty of the parameters expressed using Dirichlet priors for conditional distributions of discrete variables of the model, and, Normal-Wishart priors for distributions of continuous variables of the model, wherein the modified model is stored. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
-
-
15. An online reinforcement learning method comprising:
-
determining a probability distribution associated with uncertainty regarding parameters of a model, the model comprising an influence diagram with at least one chance node; employing a computer-implemented Thompson strategy heuristic technique to select an action based, at least in part, upon the probability distribution, wherein a variance of a distribution of the parameters is artificially increased to be large enough that the model continues to adapt; updating at least one parameter of the model based, at least in part, upon feedback associated with the selected action, the parameters defining distributions over discrete variables and continuous variables, uncertainty of the parameters expressed using Dirichlet priors for conditional distributions of discrete variables of the model, and, Normal-Wishart priors for distributions of continuous variables of the model; and storing the updated model on a computer readable storage medium. - View Dependent Claims (16, 17)
-
Specification