System and method for evaluating decisions using multiple dimensions

• US 9,798,700 B2
• Filed: 08/12/2014
• Issued: 10/24/2017
• Est. Priority Date: 08/12/2014
• Status: Active Grant

• Current Assignee: Supported Intelligence LLC
• Original Assignee: Supported Intelligence
• Inventors: Anderson, Patrick L., Johnson, Jeffrey P.
• Primary Examiner(s): VINCENT, DAVID ROBERT
• Application Number:
  US14/458,209
• Publication Number:
  US 20160048765A1
• Time in Patent Office: 1,169 Days
• Field of Search: 706 12, 706 15, 706 45
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06N 5/045 Explanation of inference; Explainable artificial intelligence [XAI]; Interpretable artificial intelligence
• CPC Class Codes: G06N 7/00 Computing arrangements based on specific mathematical models
• CPC Class Codes: G06Q 10/00 Administration; Management
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data

Abstract

A system and method for evaluating sequential decision problems that have multidimensional states. The system and method maximizes the value, as defined by the value functional equation, received by the user, for both finite and infinite horizon decision problems and provides decision making advice to the user based upon input actions, states, rewards and transition probabilities.

Claims

1. A computer-aided decision making system, comprising:

(a) a user input device;

(b) a user output device; and

(c) a processor programmed to evaluate decision problems available to a user, the programmed processor;

(A) facilitating input of information from the user via the user input device, the information including

(i) the decision problem to be solved to maximize a reward received by the user,

(ii) an action set, the action set has elements representing actions available to the user, each element in the action set having a corresponding action cost, the corresponding action costs forming an action cost set,

(iii) at least two state dimensions, each state dimension has elements representing values of a condition relevant to the decision problem,

(iv) each state dimension having a corresponding reward vector, the corresponding reward vector has reward elements representing the reward to the user associated with each of the elements of the corresponding state dimension,

(v) each state dimension having a corresponding transition matrix, the corresponding transition matrix containing, for each element in the state dimension, a probability of moving from each state in the state dimension to each state in the state dimension for each action in the action set, and

(vi) a time index, the time index containing decision points available to the user, each decision point representing a point in time when the user selects from the action set;

(B) the programmed processor combining the reward vectors with the action cost set to form a reward matrix and the programmed processor combining the transition matrices with the action set to form a total transition matrix;

(C) the programmed processor forming a functional equation from the state dimensions, the reward matrix, the total transition matrix, and all remaining inputs;

(D) the programmed processor evaluating the functional equation; and

(E) the programmed processor presenting the user with decision-making advice.

2. A computer-aided decision making system according to claim 1, wherein the programmed processor additionally receives as input a discount rate, the discount rate representing a time preference for rewards.

3. A computer-aided decision making system according to claim 2;

wherein the programmed processor combines the reward vectors by multiplying each of the elements of the reward vectors with each of the elements of the other reward vectors and subtracts the action cost set to form the reward matrix.

4. A computer-aided decision making system according to claim 2;

wherein the programmed processor combines the reward vectors by adding each of the elements of the reward vectors to each of the elements of the other reward vectors and subtracts the action cost set to form the reward matrix.

5. A computer-aided decision making system according to claim 2;

wherein the programmed processor additionally receives as input a selected reward vector, the programmed processor combines the reward vectors by multiplying each of the elements of the reward vectors with each of the elements of the other reward vectors and subtracts the action cost set multiplied by the selected reward vector to form the reward matrix.

6. A computer-aided decision making system according to claim 2;

wherein the programmed processor additionally receives as input a user combination function, the user combination function defining a relationship between the action cost set and the reward vectors, the programmed processor uses the user combination function to combine the reward vectors and the action cost set to form the reward matrix.

7. A computer-aided decision making system according to claim 2;

wherein the programmed processor additionally receives as input an absorbing state, the absorbing state is a state that the user can only transition to one time.

8. A computer-aided decision making system according to claim 2, wherein the programmed processor receives two state dimensions as user input.

9. A computer-aided decision making system according to claim 8, wherein the decision-making advice includes a value function and a policy function, the value function consist of a map from each combination of states in the state dimensions to a reward, and the policy function consists of a map from each combination of state dimensions to a reward maximizing action.

10. A computer implemented method for assisting a user in making a decision comprising:

providing a computer system having a user input device, a user output device, and a processor programmed with instructions to evaluate a decision problem available to the user, the instructions programming the processor to;

(a) using the computer system to provide the user with an option for selecting the decision problem to be solved, the user inputs information via the user input device to define the decision problem, the information including

(i) the decision problem to be solved to maximize a reward received by the user,

(ii) an action set, the action set has elements representing actions available to the user, each element in the action set having a corresponding action cost, the corresponding action costs forming an action cost set,

(iii) at least two state dimensions, each state dimension has elements representing values of a condition relevant to the decision problem,

(iv) each state dimension having a corresponding reward vector, the corresponding reward vector has reward elements representing the reward to the user associated with each of the elements of the corresponding state dimension,

(v) each state dimension having a corresponding transition matrix, the corresponding transition matrix containing, for each element in the state dimension, a probability of moving from each state in the state dimension to each state in the state dimension for each action in the action set, and

(vi) a time index, the time index containing decision points available to the user, each decision point representing a point in time when the user selects from the action set;

(b) forming, by the computer system manipulating the reward vectors with the action cost set, a reward matrix, and by the computer system manipulating the transition matrices with the set of actions, a total transition matrix,

(d) forming, by the computer system manipulating the state dimensions, the reward matrix, the total transition matrix and all remaining inputs, a functional equation,

(e) solving, by the computer system, the functional equation; and

(f) providing, by the computer system, decision-making advice.

11. A method as set forth in claim 10, wherein the step of using the computer system to prompt the user input to input information further includes the user inputting a discount rate, the discount rate representing a time preference for rewards.

12. A method as set forth in claim 11, wherein the step of forming the reward matrix, by the computer, is performed by multiplying each of the elements of the reward vectors with each of the elements of the other reward vectors and subtracting the action cost set.

13. A method as set forth in claim 11, wherein the step of forming the reward matrix, by the computer, is performed by adding each of the elements of the reward vectors with each of the elements of all of the other reward vectors and subtracting the action cost set.

14. A method as set forth in claim 11, wherein the step of inputting information additionally includes a selected reward vector, and the step of forming the reward matrix, by the computer, is performed by multiplying each of the elements of the reward vectors with each of the elements of all of the other reward vectors and subtracting the action cost set multiplied by the selected reward vector.

15. A method as set forth in claim 11, wherein the step inputting information additionally includes a user combination function, the user combination function defining a relationship between the action cost set and the reward vectors;

and

wherein the step of forming the reward matrix further includes the combining, according to the user combination function, the action cost set and reward vectors.

16. A method as set forth in claim 11, wherein the step of inputting information additionally includes an absorbing state, the absorbing state is a state that the user can only transition to one time.

17. A method as set forth in claim 11, wherein the step of using the user input to input information receives two state dimensions as user input.

18. A method as set forth in claim 17, wherein the step of providing the decision-making advice, by the computer, includes providing a value function and a policy function, the value function consist of a map from each combination of states in the state dimensions to a reward, and the policy function consists of a map from each combination of state dimensions to a reward maximizing action.