# US 9,870,532 B2 · Monte-Carlo approach to computing value of information > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 9,870,532 B2 - Document ID: US9870532B2 - Status: Granted - Kind: B2 - Application number: 15/156,307 - Filed: 2016-05-16 - Published: 2016-12-01 - Granted: 2018-01-16 - Earliest claimed: 2013-03-15 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Eric J. Horvitz; Semiha E. Kamar Eden - Web page: https://patentgrep.com/patent/US9870532B2 ## CPC - G06N 5/04: Inference or reasoning models - G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} - G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound - G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks - G06N 20/00: Machine learning - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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. ## Claims ### Claim 1 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. ### Claim 2 (depends on 1) The method of claim 1, further comprising: calculating an expected value of information based on the identified values for all of the belief states. ### Claim 3 (depends on 2) The method of claim 2, wherein the identified values represent one or more of the following: an expected cost for taking an action associated with a corresponding belief state, an expected value for taking the action associated with the corresponding belief state, and an expected value for taking a terminating action associated with the corresponding belief state. ### Claim 4 (depends on 2) The method of claim 2, wherein evaluating a reward for taking an action at any of the plurality of belief states comprises comparing the calculated expected value of the information with a value at a particular belief state. ### Claim 5 (depends on 2) The method of claim 2, wherein the expected value of information is calculated as the difference of an expected value for a first action at a belief state and an expected value for a second action at the belief state, wherein the first action is collecting more evidence and the second action is the terminating action. ### Claim 6 (depends on 1) The method of claim 1, wherein a reward for taking an action at any of the plurality of belief states is based on a number of identified values. ### Claim 7 (depends on 1) The method of claim 1, further comprising using the identified values to evaluate an additional reward for taking a separate action at any of the plurality of belief states. ### Claim 8 (depends on 1) The method of claim 1, wherein a belief state has a particular action associated therewith, the particular action being taken as the belief state is traversed. ### Claim 9 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. ### Claim 10 (depends on 9) The system of claim 9, wherein the logic causes the processor to perform further operations comprising: calculating an expected value of information based on the identified values for all of the belief states. ### Claim 11 (depends on 10) The system of claim 10, wherein the identified values represent one or more of the following: an expected cost for taking an action associated with a corresponding belief state, an expected value for taking the action associated with the corresponding belief state, and an expected value for taking a terminating action associated with the corresponding belief state. ### Claim 12 (depends on 10) The system of claim 10, wherein evaluating a reward for taking an action at any of the plurality of belief states comprises comparing the calculated expected value of the information with a value at a particular belief state. ### Claim 13 (depends on 10) The system of claim 10, wherein the expected value of information is calculated as the difference of an expected value for a first action at a belief state and an expected value for a second action at the belief state, wherein the first action is collecting more evidence and the second action is the terminating action. ### Claim 14 (depends on 9) The system of claim 9, wherein a reward for taking an action at any of the plurality of belief states is based on a number of identified values. ### Claim 15 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. ### Claim 16 (depends on 15) The computer-readable storage medium of claim 15, wherein the logic causes the processor to perform further operations comprising: calculating an expected value of information based on the identified values for all of the belief states. ### Claim 17 (depends on 16) The computer-readable storage medium of claim 16, wherein the identified values represent one or more of the following: an expected cost for taking an action associated with a corresponding belief state, an expected value for taking the action associated with the corresponding belief state, and an expected value for taking a terminating action associated with the corresponding belief state. ### Claim 18 (depends on 16) The computer-readable storage medium of claim 16, wherein evaluating a reward for taking an action at any of the plurality of belief states comprises comparing the calculated expected value of the information with a value at a particular belief state. ### Claim 19 (depends on 16) The computer-readable storage medium of claim 16, wherein the expected value of information is calculated as the difference of an expected value for a first action at a belief state and an expected value for a second action at the belief state, wherein the first action is collecting more evidence and the second action is the terminating action. ### Claim 20 (depends on 15) The computer-readable storage medium of claim 15, wherein a reward for taking an action at any of the plurality of belief states is based on a number of the identified values.