Life is Random, Time is Not: Markov Decision Processes with Window Objectives

2019-01-11 · Thomas Brihaye, Florent Delgrange, Youssouf Oualhadj, Mickael Randour

The window mechanism was introduced by Chatterjee et al. to strengthen classical game objectives with time bounds. It permits to synthesize system controllers that exhibit acceptable behaviors within a configurable time frame, all along their infinite execution, in contrast to the traditional objectives that only require correctness of behaviors in the limit. The window concept has proved its interest in a variety of two-player zero-sum games because it enables reasoning about such time bounds in system specifications, but also thanks to the increased tractability that it usually yields. In this work, we extend the window framework to stochastic environments by considering Markov decision processes. A fundamental problem in this context is the threshold probability problem: given an objective it aims to synthesize strategies that guarantee satisfying runs with a given probability. We solve it for the usual variants of window objectives, where either the time frame is set as a parameter, or we ask if such a time frame exists. We develop a generic approach for window-based objectives and instantiate it for the classical mean-payoff and parity objectives, already considered in games. Our work paves the way to a wide use of the window mechanism in stochastic models.

📄 PDF Abstract BibTeX arXiv:1901.03571

Code (0)

등록된 구현이 없습니다.

Experimenting on Markov Decision Processes with Local Treatments

2024-07-29 · Shuze Chen, David Simchi-Levi, Chonghuan Wang

Utilizing randomized experiments to evaluate the effect of short-term treatments on the short-term outcomes has been well understood and become the golden standard in industrial practice. However, as service systems beco…

Attention-Enhanced Prioritized Proximal Policy Optimization for Adaptive Edge Caching

2024-02-08 · Farnaz Niknia, Ping Wang, Zixu Wang, Aakash Agarwal 외

This paper tackles the growing issue of excessive data transmission in networks. With increasing traffic, backhaul links and core networks are under significant traffic, leading to the investigation of caching solutions …

Deep Reinforcement Learning Q-Learning reinforcement-learning Reinforcement Learning+1

ChronosPerseus: Randomized Point-based Value Iteration with Importance Sampling for POSMDPs

2022-07-16 · Richard Kohar, François Rivest, Alain Gosselin

In reinforcement learning, agents have successfully used environments modeled with Markov decision processes (MDPs). However, in many problem domains, an agent may suffer from noisy observations or random times until its…

Decision Making

Logarithmic regret bounds for continuous-time average-reward Markov decision processes

2022-05-23 · Xuefeng Gao, Xun Yu Zhou

We consider reinforcement learning for continuous-time Markov decision processes (MDPs) in the infinite-horizon, average-reward setting. In contrast to discrete-time MDPs, a continuous-time process moves to a state and s…

Point Processes reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Constrained Active Classification Using Partially Observable Markov Decision Processes

2020-08-10 · Bo Wu, Niklas Lauffer, Mohamadreza Ahmadi, Suda Bharadwaj 외

In this work, we study the problem of actively classifying the attributes of dynamical systems characterized as a finite set of Markov decision process (MDP) models. We are interested in finding strategies that actively …

Attribute Classification Medical Diagnosis