Approximation Algorithms for Solving Cost Observable Markov Decision Processes

AAAI 1999

TL;DR

This paper introduces Cost Observable Markov Decision Processes (COMDPs) as a new framework for problems with partial observability, where obtaining information incurs a cost. They propose an approximation algorithm that explicitly models these observation costs, allowing agents to strategically decide when to gather information, addressing a key limitation of prior methods.

What Problem Does This Paper Address?

Many real-world problems involve making decisions with incomplete information about the environment's true state. These are typically modeled as Partially Observable Markov Decision Processes (POMDPs). However, solving POMDPs optimally is computationally intractable (NP-hard), and existing approximation algorithms often struggle with the fundamental challenge of deciding when to acquire more information, focusing instead on how to act when already uncertain. This is particularly problematic in scenarios like active vision or diagnostics where sensing actions are plentiful but costly, and the agent needs to balance exploration with exploitation.

Methods

The authors introduce Cost Observable Markov Decision Processes (COMDPs) as a generalization of POMDPs. In COMDPs, actions are categorized into "world actions" that change the environment's state and "observation actions" that reveal information about the state without changing it, but at a cost. This framework allows for a more nuanced representation of information-gathering costs.

Their core contribution is an approximation algorithm that tackles both acting under uncertainty and the cost of reducing that uncertainty. The algorithm works by constructing a sequence of modified Markov Decision Processes (MDPs). Each MDP in the sequence incorporates the cost of observations into its reward function, effectively propagating the "cost of getting unlost" backward through action trajectories. This allows the agent to learn policies that strategically choose observation actions to avoid costly uncertainty. The method aims to converge to a stable policy, predicting when and how much observation is needed.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Cost of Information is Key: The paper highlights that a critical aspect of decision-making under uncertainty is not just acting despite it, but strategically acquiring information, and that this acquisition has a cost.
  • COMDPs as a Unified Framework: COMDPs offer a flexible way to model problems where information gathering is an explicit, costly decision, bridging the gap between fully observable MDPs and traditional POMDPs.
  • Propagating Observation Costs: The novel algorithmic approach of incorporating observation costs into MDP rewards and propagating them backward is a significant step towards solving the "when to observe" problem.
  • Addressing "Getting Lost": Unlike previous methods, this algorithm directly addresses the problem of an agent becoming "lost" (highly uncertain) and the cost associated with regaining certainty.

Key Results

The paper describes the proposed algorithm and its theoretical underpinnings. It mentions that the authors are currently comparing its performance to optimal policies computed by exact POMDP solvers and policies from policy-space search. The goal is to extend this off-line approximation algorithm to an on-line version. Specific quantitative results are not presented in this abstract.

Limitations and Future Work

The authors acknowledge that the current work is an off-line approximation algorithm and state their intention to extend it to an on-line version. They also express a long-term goal of applying these COMDP approximation algorithms to real-time problems like active visual perception and air traffic control, as well as exploring reinforcement learning for learning COMDPs.

Summary updated

BibTeX
@inproceedings{1999approximation,
  title = {{Approximation Algorithms for Solving Cost Observable Markov Decision Processes}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure