Non-Deterministic Policies in Markovian Decision Processes

Mahdi Milani Fard, Joelle Pineau

Introduction

Standard Reinforcement Learning (RL) is traditionally designed for full autonomy. In this paradigm, an agent calculates an optimal policy and executes the single best action at every step. While effective for closed systems like games or robotics, this "prescriptive" approach often fails in high-stakes, human-in-the-loop domains such as clinical medicine or flight control. In these environments, a human expert may possess "extrinsic" knowledge—contextual nuances or patient-specific factors—that the underlying Markov Decision Process (MDP) model does not capture.

This paper introduces Non-Deterministic Policies (NDPs), a framework that shifts the role of AI from a solo driver to a sophisticated guardrail. Rather than commanding a single action, an NDP suggests a set of near-optimal actions, allowing the human user to exercise discretion while maintaining rigorous mathematical guarantees on the final outcome.

The NDP Framework

The authors transition from traditional deterministic policies ($\pi(s) = a$) and stochastic policies (probability distributions) to Non-Deterministic Policies ($\Pi(s) = \{a_1, a_2, ...\}$).

The defining characteristic of an NDP is its worst-case value analysis. A policy is considered $\epsilon$-optimal if, even in the event that a user consistently selects the worst possible action from the suggested set at every time step, the total expected reward remains at least $(1-\epsilon)$ of the true optimal value. This ensures that the AI provides a menu of "good enough" options without risking a catastrophic divergence from the optimal path.

Algorithmic Solutions

Finding the largest possible set of actions that satisfy the safety constraint is computationally intensive. The paper proposes three primary methods to address this:

  1. Mixed Integer Programming (MIP): An exact mathematical optimization approach designed to find the maximal sets of actions. While precise, it faces scalability challenges in larger state spaces.
  2. Heuristic Search: A more efficient algorithm that exploits the monotonicity of the safety constraint. The authors observe that adding an action to a set can only decrease (never increase) the worst-case value. This allows the algorithm to prune "risky" branches of the search tree early, significantly speeding up the computation.
  3. DAG Heuristic: A specialized version of the search algorithm optimized for Directed Acyclic Graphs, which are common in medical treatment protocols with fixed, sequential stages.

Experimental Evaluation

The researchers evaluated the NDP framework across three distinct environments to test both computational efficiency and human-AI synergy:

  • Random MDPs: Synthetic benchmarks used to compare the runtime and scaling of the MIP approach against the Heuristic Search.
  • STAR*D Medical Data: A real-world application using data from a large-scale clinical trial for depression treatment (4,000+ patients). Here, the NDP provided clinicians with a range of viable medication and therapy combinations based on patient QIDS scores.
  • Schools-Wikipedia: A web navigation task where users find pages containing target words. This served as the primary testbed for measuring human interaction with NDP "hints."

Key Results and Human-AI Synergy

The experimental results highlight a significant performance boost when humans and AI work in tandem. In the Wikipedia navigation task, humans assisted by NDP-generated hints achieved 2.63 hits, significantly outperforming both unassisted humans (1.94 hits) and the computer-only optimal agent (1.88 hits).

This suggests that humans can use their intuition to select the best option from a filtered list of "probably good" choices, effectively outperforming the model's own optimal path. Furthermore, the NDP framework reduced cognitive load; by narrowing the field of choice, the system actually sped up human decision-making in the majority of test categories.

Limitations and Future Work

Despite the promising results, the authors identify several avenues for future research:

  • Model Uncertainty: The current framework assumes the MDP model is a perfect representation of reality. Future iterations must account for "extrinsic uncertainty" where the model itself may be noisy or incomplete.
  • Parameter Tuning: Selecting the appropriate "slack" ($\epsilon$) remains a manual process. If $\epsilon$ is too restrictive, the user has no choice; if it is too permissive, the safety guarantee loses its utility.
  • Complexity: Searching for the maximal NDP remains NP-hard. Continued work is required to develop faster approximation methods for massive, real-world state spaces.

Conclusion

By moving from prescriptive autonomy to flexible decision support, Non-Deterministic Policies offer a path toward safer and more collaborative AI. By mathematically guaranteeing a floor for performance, NDPs empower human experts to apply their unique context and intuition without sacrificing the optimization power of Reinforcement Learning.

Summary updated

Abstract

Markovian processes have long been used to model stochastic environments. Reinforcement learning has emerged as a framework to solve sequential planning and decision-making problems in such environments. In recent years, attempts were made to apply methods from reinforcement learning to construct decision support systems for action selection in Markovian environments. Although conventional methods in reinforcement learning have proved to be useful in problems concerning sequential decision-making, they cannot be applied in their current form to decision support systems, such as those in medical domains, as they suggest policies that are often highly prescriptive and leave little room for the users input. Without the ability to provide flexible guidelines, it is unlikely that these methods can gain ground with users of such systems. This paper introduces the new concept of non-deterministic policies to allow more flexibility in the users decision-making process, while constraining decisions to remain near optimal solutions. We provide two algorithms to compute non-deterministic policies in discrete domains. We study the output and running time of these method on a set of synthetic and real-world problems. In an experiment with human subjects, we show that humans assisted by hints based on non-deterministic policies outperform both human-only and computer-only agents in a web navigation task.
BibTeX
@article{fard2011non,
  author = {Mahdi Milani Fard and Joelle Pineau},
  title = {{Non-Deterministic Policies in Markovian Decision Processes}},
  journal = {J. Artif. Intell. Res.},
  year = {2011},
  doi = {10.1613/jair.3175},
}
Figure