11 Making Simple Decisions Flashcards
Uncertainty and utility
Agents and decision theory
Uncertainty and utility
Agents and decision theory
Agents need to make decisions in situations of uncertainty and conflicting goals. Basic principle of decision theory: Maximization of expected utility. Decision-theoretic agents are based decision theory, and need knowledge of probability and utility. Here, we are concerned with “simple” (one-shot) decisions, can be extended to sequential decisions.
Maximum expected utility
Maximum expected utility (MEU)
Principle
Let
• U(s) - Utility of state s
• RESULT(a) - Random variable whose values are possible outcome states of action a in current state
• P(RESULT(a) = s’ | a,e) - Probability of outcome s0, as a result of doing action a in current state, and given agent’s available evidence e of the world
Then the expected utility EU of a, given e is
EU(a | e) = Sum_s’{ P(RESULT(a) = s’ | a,e)U(s0) }
MEU: Agent should select a that maximizes EU
Preference and utility
MEU appears to be a rational basis for decision making, but is not the only possible
• Why maximize average utility, instead of e.g. minimize losses?
• Can preferences between states really be compared by comparing two numbers?
• Etc.
We can state constraints on preference structures for a rational agent, and show that MEU is compatible with the constraints
Problems with applying MEU
Problems with applying MEU
Often difficult to formulate problem completely, and required computation can be prohibitive. Knowing state of the world requires perception, learning, representation and inference. Computing P(RESULT(a)|a,e) requires complete causal model and NP-complete belief net updating. Computing utility U(s0) may require search or planning since agent needs to know how to get to a state before its utility can be assessed.
Preference structures
Preference structures
Preferences
• A > B - A is preferred over B
• A ~= B - Agent is indifferent between A and B
• A >= B - Prefers A over B or is indifferent
Constraints on preferences include orderability, transitivity, etc.
Utility follows from preferences
The constraints on preferences are the axioms of utility, from which utility principles follow. Utility principle:
If the agent’s preferences obey axioms of utility, there exists a real-valued utility function U such that:
U(A) > U(B), A > B
U(A) = U(B), A ~= B
MEU principle: Utility of a lottery can be derived from outcome utilities U([p1,S1;…;pn,Sn]) = Sum_i{ pi U(Si)}
Human decision making
Decision theory is normative, but not descriptive: People violate axioms of utility in practice. Example: A: 80% chance of $4000
B: 100% chance of $3000
C: 20% chance of $4000
D: 25% chance of $3000
Most people choose B over A, and C over D. Since only the scale is different, there does not seem to be a utility function that is consistent with the choices.
Possible descriptive theory. People are risk-aversive with high-probability events (A-B). People take more risks with unlikely payoffs (C-D).
Decision networks
Decision networks (also called influence diagrams) are a general mechanism for making rational decisions. Decision networks combine belief networks with nodes for actions and utilities, and can represent:
- Information about agent’s current state • Agent’s possible actions
- States that will follow from actions
- Utilities of these states
Therefore, decision networks provide a substrate for implementing rational, utility-based agents
Node types in decision networks
Chance nodes (ovals)
Represent random variables (as in belief networks), with associated conditional probability table (CPT) indexed by states of parent nodes (decisions or other chance nodes)
Decision nodes (rectangles)
Represent points where the decision maker has choice of actions to make
Utility nodes (diamonds)
Represent the agent’s utility function, with parents all nodes that directly influence utility
Evaluating decision networks
Set the evidence variables (chance nodes with known values) for the current state. For each possible value of the decision node:
Set decision node to that value (from now on, it behaves like a chance node that has been set as an evidence variable)
Calculate posterior probabilities for parent nodes of the utility node, using standard probabilistic inference methods
Calculate resulting utility for the action Return the action with the highest utility
Value of information
The agent will normally not have all required information available before making a decision. Important to know which information to seek, by performing tests that may be expensive and/or hazardous. The importance of tests depend on:
- Will different outcomes make significant difference to the optimal action
- What is the probability of different outcomes
Information value theory helps agents decide which information to seek, by using sensing actions
Considerations for information gathering
Information has value if it is likely to cause a change of plan, and if the new plan will be significantly better than the old. An information-gathering agent should:
- Ask questions in a reasonable sequence
- Avoid asking irrelevant questions
- Take into account importance of information vs. cost
- Stop asking questions when appropriate
Requirements met by using VPI(E) - Value of Perfect Information of evidence E. Properties:
• Always non-negative
• Depends on current state and is non-additive
• Order-independent (simplifies sensing actions)
An information gathering agent
Information-gathering agent is myopic, i.e. it just considers one evidence variable at a time. It may hastily select an action where a better decision would be based on two or more information gathering actions. “Greedy” search heuristic - often works well in practice. A perfectly rational agent would consider all possible sequences of sensing action that terminate in an external action. May disregard permutations due to order-independence.
[image: *non-information seeking action]
Decision analysis vs. expert systems
Decision analysis (application of decision theory)
- Focus on making decisions
- Defines possible actions and outcomes with preferences
- Roles
- Decision maker states preferences
- Decision analyst specifies problem
Expert systems (“classical” rule-based systems)
- Focus on answering questions
- Defines heuristic associations between evidence & answers
- Roles
- Domain expert provides heuristic knowledge
- Knowledge engineer elicits & encodes knowledge in rules
Decision-theoretic expert systems
Decision-theoretic expert systems.
• Inclusion of decision networks in expert system frameworks
Advantages:
• Make expert preferences explicit
• Automate action selection in addition to inference
• Avoid confusing likelihood with importance (Common pitfall in expert systems: Conclusions are ranked in terms of likelihood, disregarding rare, but dangerous conclusion)
• Availability of utility information helps in knowledge engineering process
Knowledge engineering for decision-theoretic expert systems
- *Knowledge engineering for decision-theoretic expert systems**
1. Create causal model
2. Simplify to qualitative decision model
3. Assign probabilities
4. Assign utilities
5. Verify and refine model
6. Perform sensitivity analysis
