Algebraic Markov Decision Processes

Patrice Perny, Olivier Spanjaard, Paul Weng

Abstract

In this paper, we provide an algebraic approach to Markov Decision Processes (MDPs), which allows a unified treatment of MDPs and includes many existing models (quantitative or qualitative) as particular cases. In algebraic MDPs, rewards are expressed in a semiring structure, uncertainty is represented by a decomposable plausibility measure valued on a second semiring structure, and preferences over policies are represented by Generalized Expected Utility. We recast the problem of finding an optimal policy at a finite horizon as an algebraic path problem in a decision rule graph where arcs are valued by functions, which justifies the use of the Jacobi algorithm to solve algebraic Bellman equations. In order to show the potential of this general approach, we exhibit new variations of MDPs, admitting complete or partial preference structures, as well as probabilistic or possibilistic representation of uncertainty.

Introduction

Markov Decision Processes (MDPs) are the gold standard for modeling sequential decision-making under uncertainty. However, the standard MDP framework is quite rigid: it assumes that rewards are scalar and additive, that uncertainty is strictly probabilistic, and that policies should be evaluated using standard Expected Utility (EU).

In the real world, these assumptions often fail. Rewards might be multi-dimensional (e.g., balancing time, cost, and safety), uncertainty might be qualitative (e.g., "highly plausible" vs. "unlikely" rather than strict percentages), and human preferences often violate standard EU. While alternative decision theories exist, applying them to dynamic, multi-step problems usually breaks dynamic consistency—meaning the famous Bellman principle is violated, and standard dynamic programming algorithms fail to find optimal policies. This paper seeks a mathematically sound way to swap out standard probabilities and rewards for alternative models without breaking the algorithms used to solve them.

Methodology: The Algebraic Framework

The authors tackle this by generalizing the underlying math of MDPs using semirings—algebraic structures equipped with two operators that generalize addition and multiplication.

  1. Algebraic Abstraction:
    • Rewards take values in an idempotent semiring (using operators $\oplus_V$ and $\otimes_V$).
  2. Uncertainty is modeled as "plausibility measures" living in a second semiring (using $\oplus_P$ and $\otimes_P$).
  3. Policy Evaluation uses a Generalized Expected Utility (GEU) model, combining plausibilities and rewards using generalized operators ($\boxplus$ and $\boxtimes$).
  4. The Decision Rule Graph: The authors recast the MDP as a specialized graph where nodes are decision rules and edges are transitions. Finding the optimal policy becomes equivalent to finding an optimal algebraic path through this graph.
The decision rule graph representing the sequential decision process as an algebraic path problem.
  1. Algebraic Jacobi Algorithm: To solve the generalized Bellman equations, the authors adapt the Jacobi algorithm. They establish five specific algebraic conditions ($C_1$ through $C_5$, mostly distributivity and monotonicity rules) that guarantee dynamic consistency and allow the algorithm to work.

Key Insights and Ideas

  • A Grand Unification: Standard MDPs, qualitative MDPs, and multicriteria MDPs are shown to be special cases of the exact same algebraic structure. By changing the definitions of addition and multiplication, the same logic solves them all.
  • The Secret to Dynamic Consistency: The paper isolates exactly why the Bellman equation works. It boils down to specific distributivity properties between how rewards are combined and how uncertainty is measured. If custom math satisfies conditions $C_1$-$C_5$, dynamic programming remains valid.
  • Graph Theory Bridge: Recasting sequential decision-making as a generalized path-finding problem on a "decision rule graph" elegantly bridges reinforcement learning with classic graph theory.

Key Results

The authors mathematically proved that their Algebraic Jacobi Algorithm correctly solves the algebraic Bellman equations, provided the semiring conditions are met. This algebraic backward induction runs in polynomial time when the reward scale is completely ordered.

To prove the framework's utility, the authors successfully formulated two new types of MDPs:

  • Possibilistic MDPs: Using a qualitative decision model to handle weak information about uncertainty.
  • Multicriteria MDPs: Handling environments where rewards are vectors compared using Pareto dominance or lexicographic ordering.
Evaluation of decision rules in a multicriteria setting, showing vector-valued rewards over time.

Limitations and Future Work

While highly general, the framework cannot capture all decision theories. For example, Rank Dependent Expected Utility (RDEU) is inherently dynamically inconsistent and cannot be expressed using these generalized expectation operators. Additionally, the current work focuses on finite-horizon problems. Extending this to infinite-horizon AMDPs is a promising future direction, though it will require defining suitable mathematical topologies to handle convergence.

Summary updated

Abstract

In this paper, we provide an algebraic approach to Markov Decision Processes (MDPs), which allows a unified treatment of MDPs and includes many existing models (quantitative or qualitative) as particular cases. In algebraic MDPs, rewards are expressed in a semiring structure, uncertainty is represented by a decomposable plausibility measure valued on a second semiring structure, and preferences over policies are represented by Generalized Expected Utility. We recast the problem of finding an optimal policy at a finite horizon as an algebraic path problem in a decision rule graph where arcs are valued by functions, which justifies the use of the Jacobi algorithm to solve algebraic Bellman equations. In order to show the potential of this general approach, we exhibit new variations of MDPs, admitting complete or partial preference structures, as well as probabilistic or possibilistic representation of uncertainty.
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