Non-Deterministic Policies in Markovian Decision Processes

2014-01-16 · Mahdi Milani Fard, Joelle Pineau

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.

📄 PDF Abstract BibTeX arXiv:1401.3871

Code (0)

등록된 구현이 없습니다.

Tasks

Decision Making reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)Sequential Decision Making

Model-Based Reinforcement Learning in Discrete-Action Non-Markovian Reward Decision Processes

2025-12-16 · Alessandro Trapasso, Luca Iocchi, Fabio Patrizi arxiv

Many practical decision-making problems involve tasks whose success depends on the entire system history, rather than on achieving a state with desired properties. Markovian Reinforcement Learning (RL) approaches are not…

Reinforcement Learning

Trajectory representation learning for Multi-Task NMRDPs planning

2019-09-25 · Firas Jarboui, Vianney Perchet, Roman EGGER

Expanding Non Markovian Reward Decision Processes (NMRDP) into Markov Decision Processes (MDP) enables the use of state of the art Reinforcement Learning (RL) techniques to identify optimal policies. In this paper an app…

Reinforcement Learning (RL)Representation Learning Triplet

Inferring Probabilistic Reward Machines from Non-Markovian Reward Processes for Reinforcement Learning

2021-07-09 · Taylor Dohmen, Noah Topper, George Atia, Andre Beckus 외

The success of reinforcement learning in typical settings is predicated on Markovian assumptions on the reward signal by which an agent learns optimal policies. In recent years, the use of reward machines has relaxed thi…

Decision Making reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Policy Dispersion in Non-Markovian Environment

2023-02-28 · Bohao Qu, Xiaofeng Cao, Jielong Yang, Hechang Chen 외

Markov Decision Process (MDP) presents a mathematical framework to formulate the learning processes of agents in reinforcement learning. MDP is limited by the Markovian assumption that a reward only depends on the immedi…

Anytime-Constrained Reinforcement Learning

2023-11-09 · Jeremy McMahan, Xiaojin Zhu

We introduce and study constrained Markov Decision Processes (cMDPs) with anytime constraints. An anytime constraint requires the agent to never violate its budget at any point in time, almost surely. Although Markovian …

reinforcement-learning Reinforcement Learning