An Anytime Algorithm for Decision Making under Uncertainty

Michael C. Horsch, David L. PooleUAI 1998

TL;DR

This paper introduces a novel "anytime" algorithm for making decisions under uncertainty in complex, multi-stage scenarios represented by influence diagrams. The algorithm incrementally builds decision policies, providing increasingly valuable (though not necessarily optimal) solutions quickly, making it suitable for situations where computing the absolute best decision is computationally infeasible.

What Problem Does This Paper Address?

Decision-making under uncertainty is a critical problem in artificial intelligence and operations research. Influence diagrams (IDs) are powerful tools for modeling these problems, allowing for the representation of beliefs, preferences, and sequential decisions. For simpler problems, dynamic programming can find optimal policies. However, as the complexity of the influence diagram grows (e.g., with many decision stages and variables), the computational cost of finding an optimal policy becomes prohibitive. This paper addresses the challenge of finding good enough policies in a timely manner for these large, complex decision problems, where a perfect solution is out of reach due to computational constraints. The goal is to provide a useful policy that can be used by a decision-maker even if it's not the absolute best possible.

Methods

The core of the paper is the Random Access Refinement algorithm. This algorithm constructs policies incrementally, starting with a very basic policy (essentially making decisions without using any information) and progressively refining it.

Here's a breakdown of the key methodological aspects:

  • Influence Diagrams (IDs): The problem is framed using influence diagrams, which are directed acyclic graphs (DAGs) representing sequential decision problems. They consist of chance nodes (random variables), decision nodes (actions), and a value node (representing preferences).
  • Decision Trees: Policies are represented as a collection of decision trees, one for each decision node. These trees map information states (outcomes of previous decisions or observations) to specific actions.
  • Incremental Refinement: The algorithm iteratively improves a policy by selecting a "leaf" in one of the decision trees and "splitting" it. This split introduces new decision points or information considerations, thereby making the policy more informed.
  • Stochastic Decision Functions: During the refinement process, decision functions are treated as stochastic. This means that at any given information state, there's a probability distribution over actions, reflecting the uncertainty about which action will ultimately be endorsed as best after further refinement. This is a departure from deterministic decision trees used in single-stage problems.
  • Random Access: Unlike traditional dynamic programming which processes decision nodes in a fixed sequence, this algorithm refines decision trees in a "random access" manner. It uses heuristics to prioritize which decision node or leaf to refine next, aiming for the most impactful improvement.
  • Global Effects: A crucial aspect is that refining one part of the policy can have ripple effects on other parts. The algorithm accounts for these global effects by updating probabilities and expected values across the entire policy after each refinement step.
  • Bayesian Network Conversion: To efficiently compute expected values and probabilities, the influence diagram is converted into a Bayesian network. This allows for standard probabilistic inference queries to guide the refinement process.

Datasets

The paper evaluates its algorithm on a set of problems based on an agent navigating a maze. These mazes are represented as influence diagrams, and the agent has actions (move N, S, E, W, stay) and sensors (detecting walls).

The experiments use four variations of the agent model:

  • Sensor Models: Perfect vs. Noisy sensors.
  • Actuator Models: Perfect vs. Noisy actuators.

These variations are applied to several maze configurations (Maze 1, 2, 3, 4). The paper notes that for some mazes and agent models, optimal policies are not known, highlighting the difficulty of these problems.

Key Insights and Ideas

  • "Anytime" Nature is Key: The most significant insight is the development of an algorithm that provides a useful policy at any point during its execution. This is invaluable when computational resources are limited or time is critical.
  • Stochasticity as a Bridge: Treating decision functions as stochastic during refinement is a clever way to handle the ongoing nature of the process and the global dependencies between decision stages. It allows for more flexible exploration of the decision space.
  • Heuristics Drive Efficiency: The "random access" refinement, guided by heuristics (like the "second best action" heuristic), is crucial for making progress on large problems. It prioritizes refinements that are likely to yield the most significant improvements, rather than exhaustively exploring all possibilities.
  • Global Updates are Necessary: Simply refining a local part of the policy isn't enough. The algorithm's ability to propagate the effects of a refinement globally ensures that the overall policy remains coherent and that improvements are realized.
  • Real-world applicability: The maze navigation problems, while simplified, demonstrate the algorithm's ability to handle complex, multi-stage decision-making scenarios with uncertainty, which are common in robotics and AI planning.

Key Results

  • The algorithm successfully constructs "reasonably valuable" policies for large decision problems that are too complex for traditional exhaustive methods.
  • For the "perfect agent" in Maze 1, the algorithm achieved an expected value of 0.869565 after 2280 Bayesian network computations, which is a 13% error from the optimal policy. This was achieved with significantly fewer computations than would be required for exhaustive enumeration (estimated at over 2^60 queries).
  • In some cases, the algorithm was able to find policies that exceeded the value of the best policy for a "perfect agent" when using imperfect sensors/actuators, attributed to the heuristic choices made.
  • The performance curves show that for "sharp" probability distributions (perfect agent), the expected value increases steeply and plateaus. For more distributed probabilities (noisy sensors/actuators), the increases are less steep.
  • Table 1 summarizes the best policies found for various agent models and mazes, showing expected values and the number of steps (computations) taken. The error from optimal for perfect agents ranged from 13% to 30%.

Limitations and Future Work

  • Asymptotic Cost: The paper acknowledges that the procedure is "very expensive asymptotically." While it provides valuable policies quickly, constructing a complete optimal policy can still be computationally intensive.
  • Sub-optimal Policies: The algorithm is designed to produce sub-optimal policies when computational limits are reached. The paper doesn't guarantee optimality within a fixed resource budget.
  • Heuristic Choice: The performance is dependent on the chosen heuristics for selecting which leaf to refine and how to extend it. The paper suggests that exploring different heuristic and extension strategies is an avenue for future research.
  • Generalization: The empirical results are based on a specific subclass of influence diagrams (maze navigation). Further work is needed to demonstrate the algorithm's performance on a broader range of problem types.
  • Fine-tuning p: The parameter p (probability of no further refinement) is mentioned as requiring fine-tuning, suggesting that its optimal setting might be problem-dependent.

Summary updated

BibTeX
@inproceedings{horsch1998anytime,
  author = {Michael C. Horsch and David L. Poole},
  title = {{An Anytime Algorithm for Decision Making under Uncertainty}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1998},
}
Figure