MDPs with Non-Deterministic Policies

Mahdi Milani Fard, Joelle Pineau

In the realm of automated decision-making, Markov Decision Processes (MDPs) are the gold standard for finding the "optimal" path through a sequence of choices. Traditionally, solving an MDP yields either a deterministic policy (a strict rule to "do action A") or a stochastic policy (a rule to "do action A with 70% probability").

However, in high-stakes fields like medicine, these rigid, "black box" recommendations often face resistance. Doctors rarely want a machine to dictate their exact actions; instead, they prefer a decision support system that respects their clinical expertise, patient preferences, and the subtle nuances of real-world care.

The central challenge addressed by this research is: How can we provide a menu of "good enough" options to a human expert while guaranteeing that even their worst choice from that menu won't lead to a disastrous outcome?

The Shift to Non-Deterministic Policies

To solve this, the authors introduce the concept of a non-deterministic policy. Instead of mapping each state to a single action, a non-deterministic policy maps each state to a set of viable actions.

Example of a standard Markov Decision Process (MDP) with states, actions, and rewards.

To ensure the quality of these recommendations, the framework relies on an $\epsilon$-optimal constraint. This constraint guarantees that the worst-case expected return of any action in the provided set must fall within a defined margin ($(1-\epsilon)$) of the theoretical optimal value. Unlike stochastic policies, which assume a fixed probability distribution over actions, non-deterministic policies assume the human agent might pick the absolute worst available option in the set—and still guarantees that the outcome remains near-optimal.

A traditional optimal policy provides a single, rigid path, whereas a non-deterministic policy offers a menu of near-optimal choices.

Finding the Best Menu of Options

The researchers propose two primary methods to compute these non-deterministic policies:

  1. Mixed Integer Program (MIP): A formal optimization approach designed to maximize the "size" of the policy—giving the human as many choices as possible—while strictly satisfying the $\epsilon$-optimal performance guarantees. While mathematically precise, this method is computationally heavy.
  2. Search Algorithm: A recursive depth-first search that exploits a "monotonic" property of the problem. The core insight is that if a set of actions is already sub-optimal, adding more actions to that set will never magically make it optimal. This monotonicity allows the algorithm to aggressively prune large branches of the search tree, making it significantly faster than the MIP for certain problem structures.

Real-World Application: The STAR*D Study

To validate their approach, the authors evaluated the framework on both randomly generated MDPs and real-world data from the STAR*D Study, a large-scale clinical trial involving over 4,000 patients suffering from depression. The MDP was constructed to optimize sequential treatment steps based on patient symptom scores.

The results demonstrated a clear benefit for medical flexibility. As the error tolerance ($\epsilon$) increased, the system successfully expanded the available treatment options. For instance, at a strict $\epsilon=0$, the system might recommend only a single optimal drug. But by slightly relaxing the tolerance to $\epsilon=0.02$, the system could safely offer the doctor a choice between three different, highly effective treatments, empowering the physician to make the final call based on side effects or patient history.

Furthermore, the search algorithm proved highly efficient, scaling significantly better than the MIP as the number of possible state-action pairs increased. The non-deterministic policies also remained remarkably stable when Gaussian noise was introduced to the reward functions, indicating robust performance even with the "messiness" of real-world clinical data.

Limitations and Future Directions

While promising, the current algorithms are primarily suited for relatively small or structured domains, such as Directed Acyclic Graphs (DAGs). Scaling these methods to massive, highly complex state spaces remains an ongoing challenge.

Future work will focus on developing better heuristics to further prune the search space, exploring alternative optimization criteria (like minimizing uncertainty or maximizing the margin between good and bad actions), and adapting the framework for environments where the underlying MDP model is imperfectly learned from data. Ultimately, this research marks a vital step toward AI systems that act as true advisors rather than rigid dictators.

Summary updated

Abstract

Markov Decision Processes (MDPs) have been extensively studied and used in the context of planning and decision-making, and many methods exist to find the optimal policy for problems modelled as MDPs. Although finding the optimal policy is sufficient in many domains, in certain applications such as decision support systems where the policy is executed by a human (rather than a machine), finding all possible near-optimal policies might be useful as it provides more flexibility to the person executing the policy. In this paper we introduce the new concept of non-deterministic MDP policies, and address the question of finding near-optimal non-deterministic policies. We propose two solutions to this problem, one based on a Mixed Integer Program and the other one based on a search algorithm. We include experimental results obtained from applying this framework to optimize treatment choices in the context of a medical decision support system.
BibTeX
@inproceedings{fard2008mdps,
  author = {Mahdi Milani Fard and Joelle Pineau},
  title = {{MDPs with Non-Deterministic Policies}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2008},
  url = {https://openreview.net/forum?id=S1ZwJuWubr},
}

Loading related content...

Figure