Solving MDPs with Skew Symmetric Bilinear Utility Functions

Hugo Gilbert, Olivier Spanjaard, Paolo Viappiani, Paul Weng

TL;DR

This paper introduces a novel framework for solving Markov Decision Processes (MDPs) using Skew Symmetric Bilinear (SSB) utility functions, which can capture a wider range of rational decision-making behaviors than traditional Expected Utility (EU) models. They propose a game-theoretic approach and a double oracle algorithm to find SSB-optimal policies, demonstrating its effectiveness on a popular TV game show.

What Problem Does This Paper Address?

Decision-theoretic planning, particularly within the framework of Markov Decision Processes (MDPs), is a cornerstone of artificial intelligence for modeling and solving complex decision problems. Standard MDP approaches typically assume an agent aims to maximize expected rewards, often represented by an Expected Utility (EU) function. However, the EU model, while intuitive, fails to account for certain rational decision behaviors, such as the paradox of nontransitive dice. This limitation means that EU-based planning might not always yield the most appropriate or desirable policies in real-world scenarios. The paper addresses this gap by proposing a more general decision model, Skew Symmetric Bilinear (SSB) utility theory, which can accommodate a broader spectrum of rational preferences, including intransitive ones, and then developing methods to solve MDPs under these more general utility functions.

Methods

The core of the paper lies in extending MDP planning to SSB utility functions and developing an algorithm to find optimal policies.

  • SSB Utility Theory: The paper leverages Skew Symmetric Bilinear (SSB) utility theory, which generalizes the EU model. Instead of a single utility function, SSB utility uses a binary functional $\phi(p, q)$ to compare probability distributions $p$ and $q$. A policy is preferred if its resulting distribution yields a higher value under this functional. This allows for more complex preference structures, including cyclic ones.
  • Augmented MDP: To handle the complexities of SSB utility, the authors transform the original MDP into an "augmented MDP." This augmented MDP's states include not only the original state but also the accumulated wealth, allowing the planning process to consider the full outcome of a history.
  • Game-Theoretic Approach: Identifying an SSB-optimal policy is framed as finding a Nash Equilibrium (NE) in a zero-sum two-player symmetric game played on the set of policies. The payoff function for this game is derived from the SSB utility function. The existence of a symmetric NE is guaranteed by game theory.
  • Double Oracle Algorithm: Due to the combinatorial explosion of possible policies (pure strategies in the game), a direct enumeration is infeasible. The paper adapts the double oracle algorithm, a technique for solving large-sum games. This algorithm iteratively builds a set of relevant pure strategies and finds the NE within this restricted set. A key component is a "best response oracle" that, given a mixed strategy of the opponent, finds the optimal pure strategy for the current player.

Datasets

Not discussed in the paper. The paper uses a simulated "Who Wants to Be a Millionaire?" game and a grid world domain for experimental evaluation.

Key Insights and Ideas

  • Beyond Expected Utility: The most significant insight is that standard EU models are insufficient for capturing all rational decision-making behaviors. SSB utility provides a more expressive framework that can account for phenomena like intransitive preferences, which are observed in real-world decision-making.
  • Game Theory as a Solution: Reframing the problem of finding an SSB-optimal policy as a game-theoretic problem (finding a Nash Equilibrium) provides a robust theoretical foundation for existence and a path towards computation.
  • Augmented MDPs for Richer States: The concept of an augmented MDP, where states incorporate accumulated wealth, is crucial for correctly evaluating policies under utility functions that depend on the entire outcome distribution, not just expected values.
  • Scalability through Double Oracle: The double oracle algorithm is a critical methodological contribution, enabling the practical solution of these complex games by avoiding the explicit enumeration of all possible policies.

Key Results

The paper demonstrates the operationality of their approach through experiments on a simulated "Who Wants to Be a Millionaire?" game and other domains.

  • "Who Wants to Be a Millionaire?" Game:
    • The SSB framework allows for policies that exhibit different risk attitudes (risk-averse, risk-seeking, threshold-based) compared to a purely expectation-maximizing policy.
  • For instance, risk-averse and probabilistic dominance-optimal policies tend to use lifelines earlier to secure gains, while expectation-optimal policies might hold them for later, more difficult questions.
  • The computational times for solving the game were reported to be in the order of seconds to minutes, demonstrating the efficiency of the double oracle approach.
  • Other Domains: Preliminary experiments on grid world and cancer clinical trials domains using the probabilistic dominance criterion showed that the method can handle MDPs with thousands of states, with computation times varying from seconds to half an hour.

Limitations and Future Work

  • Theoretical Guarantees: The authors acknowledge the need for theoretical guarantees on the number of iterations for the double oracle algorithm.
  • Factored MDPs: Extending the approach to factored MDPs would be beneficial for tackling even larger-scale problems.
  • Reinforcement Learning: Investigating the use of SSB utility functions in reinforcement learning settings is suggested as a promising future direction.
  • Scalability: While the method shows promise for scalability, the authors note that the increase in state space size during augmentation can vary significantly, and further study on scalability is underway.

Summary updated

Abstract

International audience
BibTeX
@inproceedings{gilbert2015solving,
  author = {Hugo Gilbert and Olivier Spanjaard and Paolo Viappiani and Paul Weng},
  title = {{Solving MDPs with Skew Symmetric Bilinear Utility Functions}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
  url = {https://openreview.net/forum?id=rkbwAXzO-B},
}
Figure