Monte-Carlo approach to computing value of information
AssigneeMicrosoft Technology Licensing, LLC
InventorsEric J. Horvitz, Semiha E. Kamar Eden
Life of this patent
Estimating the term…
Abstract
The subject disclosure is directed towards the use of Monte Carlo (MC) procedures for computing the value of information (VOI), including with long evidential sequences. An MC-VOI algorithm is used to output a decision as to balancing the value and costs of collecting information in advance of taking action by running prediction model-based simulations to determine execution paths through possible states, and processing the results of the simulations/paths taken into a final decision.
Claims20
A method comprising:
- receiving a request to evaluate a long evidential sequence task, the long evidential sequence task comprising a plurality of belief states that formulate paths, the plurality of belief states comprising a first belief state and a terminal belief state;
- building a search tree by executing a plurality of samples through corresponding paths until the corresponding paths are completed;
- identifying values for all belief states traversed during execution of the plurality of samples;
- and
- using the identified values to evaluate a reward for taking an action at any of the plurality of belief states, wherein the action is one of the following:
- collecting more evidence or a terminating action.
A system comprising:
- a processor;
- and
- a memory area having logic stored therein, the logic, when executed by the processor, causes the processor to perform operations comprising:
- receiving a request to evaluate a long evidential sequence task, the long evidential sequence task comprising a plurality of belief states that formulate paths, the plurality of belief states comprising a first belief state and a terminal belief state;
- building a search tree by executing a plurality of samples through corresponding paths until the corresponding paths are completed;
- identifying values for all belief states traversed during execution of the plurality of samples;
- and
- using the identified values to evaluate a reward for taking an action at any of the plurality of belief states, wherein the action is one of the following:
- collecting more evidence or a terminating action.
One or more computer-readable storage mediums having computer-executable instructions that cause a processor to perform operations comprising:
- receiving a request to evaluate a long evidential sequence task, the long evidential sequence task comprising a plurality of belief states that formulate paths, the plurality of belief states comprising a first belief state and a terminal belief state;
- building a search tree by executing a plurality of samples through corresponding paths until the corresponding paths are completed;
- identifying values for all belief states traversed during execution of the plurality of samples;
- and
- using the identified values to evaluate a reward for taking an action at any of the plurality of belief states, wherein the action is one of the following:
- collecting more evidence or a terminating action.
Dependencies are inferred from the claim text.