Algebraic Markov Decision Processes

Patrice Perny, Olivier Spanjaard, Paul Weng

TL;DR

This paper introduces an "algebraic" framework for Markov Decision Processes (AMDPs) that unifies various existing models (qualitative, multicriteria, etc.) under a single, general structure. By leveraging semiring theory, they provide a principled way to handle diverse reward systems, uncertainty representations, and decision criteria, leading to a generalized Jacobi algorithm for finding optimal policies.

What Problem Does This Paper Address?

Markov Decision Processes (MDPs) are a powerful tool for sequential decision-making under uncertainty. However, the standard MDP formulation, which relies on scalar additive rewards and probabilistic uncertainty with expected utility maximization, is often too restrictive for real-world scenarios. Many extensions exist, such as those dealing with non-additive rewards (e.g., multicriteria decision-making), non-probabilistic uncertainty (e.g., possibility theory), or alternative decision criteria beyond expected utility. The challenge has been to unify these diverse approaches and develop general algorithms that can handle them. Existing attempts to combine non-expected utility criteria with dynamic decision-making often lead to violations of the Bellman principle, making backward induction (a standard solution method) inapplicable.

Methods

The core contribution is the development of an Algebraic Markov Decision Process (AMDP) framework. This framework generalizes standard MDPs by:

  • Rewards in a Semiring: Rewards are not restricted to scalars but can take values in a set $V$ endowed with two operations, $\oplus_v$ (addition) and $\otimes_v$ (multiplication), forming a semiring. This allows for various reward structures, including those that are not additive (e.g., using max for addition).
  • Uncertainty in a Semiring: Plausibility measures over events are used to represent uncertainty, taking values in a set $P$ with semiring operations $\oplus_p$ and $\otimes_p$. This accommodates non-probabilistic uncertainty representations.
  • Generalized Expectation: A generalized expectation operator is used to combine plausibilities and rewards, based on the work of Chu and Halpern.
  • Decision Rule Graph: The problem of finding an optimal policy is recast as finding an optimal path in a "decision rule graph."
  • Generalized Jacobi Algorithm: The authors adapt the Jacobi algorithm (originally for solving systems of linear equations) to solve the algebraic Bellman equations that arise in AMDPs. This algorithm leverages the structure of the decision rule graph and the properties of the semirings.

The paper also establishes conditions (C1-C5) on the semiring operations and the update functions that guarantee dynamic consistency and allow the generalized Jacobi algorithm to work.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unification through Algebra: The power of semiring theory is demonstrated as a unifying mathematical tool for diverse decision-making models. By abstracting reward and uncertainty structures into semirings, a single algorithmic framework can address a wide range of problems.
  • Dynamic Consistency for Non-EU Criteria: The paper shows that certain non-expected utility (non-EU) decision criteria can be made dynamically consistent within the AMDP framework, overcoming a major hurdle in applying them to sequential decision problems. This is achieved by carefully selecting semiring structures and ensuring specific properties of the update functions.
  • Algorithmic Generality: The generalized Jacobi algorithm provides a single, efficient method for solving AMDPs, regardless of the specific semiring structures or decision criteria employed, as long as the necessary conditions are met.
  • New AMDP Variants: The framework naturally leads to new variants of MDPs, such as those with qualitative uncertainty or multicriteria rewards, which are explored in the examples.

Key Results

  • The paper formally defines the Algebraic Markov Decision Process (AMDP) framework.
  • It proves that under certain conditions (C1-C5), the update functions in AMDPs are non-decreasing, which is crucial for dynamic programming.
  • It shows that the generalized Jacobi algorithm can be used to solve the algebraic Bellman equations for AMDPs.
  • The paper demonstrates how standard MDPs, qualitative MDPs, and multicriteria MDPs can be represented as instances of AMDPs.

Limitations and Future Work

  • Dynamic Consistency Limitations: The authors acknowledge that their framework does not encompass all decision theories, specifically mentioning the Rank-Dependent Expected Utility (RDEU) model and Choquet integrals, which are known to be dynamically inconsistent and thus not directly amenable to backward induction-style algorithms.
  • Infinite Horizon: The paper focuses on finite horizon problems. The authors suggest that the result might generalize to the infinite horizon case, provided a suitable topology is defined on the policy valuation space.
  • Computational Complexity: While the generalized Jacobi algorithm is presented as efficient, the paper notes that specific implementations might require careful consideration of the complexity of semiring operations. The presented algorithm is polynomial when semiring operations are O(1).
  • Exploration of New AMDP Variants: The paper opens the door for further research into the properties and applications of the newly defined AMDP variants, particularly in areas like qualitative decision-making and multicriteria planning.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{perny2005algebraic,
  author = {Patrice Perny and Olivier Spanjaard and Paul Weng},
  title = {{Algebraic Markov Decision Processes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
  url = {https://openreview.net/forum?id=rJV_kQMO-S},
}
Figure