Safe learning for near-optimal scheduling

DOI10.1007/978-3-030-85172-9_13MaRDI QIDQ832074zbMATH OpenOpenAlexFDO

Authors Damien Busatto-Gaston, Debraj Chakraborty, Shibashis Guha, G. A. Pérez, Jean-François Raskin

Publication date 24 March 2022

Full work available at URL https://arxiv.org/abs/2005.09253

zbMATH Keywords

Monte-Carlo tree searchtask schedulingmodel-based learning

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Markov and semi-Markov decision processes (90C40)

Abstract: In this paper, we investigate the combination of synthesis, model-based learning, and online sampling techniques to obtain safe and near-optimal schedulers for a preemptible task scheduling problem. Our algorithms can handle Markov decision processes (MDPs) that have 1020 states and beyond which cannot be handled with state-of-the art probabilistic model-checkers. We provide probably approximately correct (PAC) guarantees for learning the model. Additionally, we extend Monte-Carlo tree search with advice, computed using safety games or obtained using the earliest-deadline-first scheduler, to safely explore the learned model online. Finally, we implemented and compared our algorithms empirically against shielded deep Q-learning on large task systems.

Recommendations

• As soon as probable: optimal scheduling under stochastic uncertainty
• scientific article; zbMATH DE number 1956584
• Scheduling with timed automata
• Verification of Markov decision processes using learning algorithms
• Synthesising succinct strategies in safety games with an application to real-time scheduling

Cites work

• scientific article; zbMATH DE number 1134975 (Why is no real title available?)
• scientific article; zbMATH DE number 7559496 (Why is no real title available?)
• scientific article; zbMATH DE number 7561341 (Why is no real title available?)
• A sparse sampling algorithm for near-optimal planning in large Markov decision processes
• A theory of the learnable
• Continuity of the value of competitive Markov decision processes
• Hard real-time computing systems. Predictable scheduling algorithms and applications.
• Learning-based mean-payoff optimization in an unknown MDP under omega-regular constraints
• On the synthesis of strategies in infinite games
• Robustness of structurally equivalent concurrent parity games
• Stochastic games
• Supervisory Control of a Class of Discrete Event Processes
• \({\mathcal Q}\)-learning

Describes a project that uses

Uses Software

• Storm
• Adam
• Baselines
• GitHub

This page was built for publication: Safe learning for near-optimal scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q832074)