Estimating Rewards & Rare Events in Nondeterministic Systems

Axel Legay 1 Sean Sedwards 1 Louis-Marie Traonouez 1
1 ESTASYS - Efficient STAtistical methods in SYstems of systems
Inria Rennes – Bretagne Atlantique , IRISA-D4 - LANGAGE ET GÉNIE LOGICIEL
Abstract : Exhaustive verification can quantify critical behaviour arising from concurrency in nondeterministic models. Rare events typically entail no additional challenge, but complex systems are generally intractable. Recent work on Markov decision processes allows the extremal probabilities of a property to be estimated using Monte Carlo techniques, offering the potential to handle much larger models. Here we present algorithms to estimate extremal rewards and consider the challenges posed by rarity. We find that rewards require a different interpretation of confidence and that reachability rewards require the introduction of an auxiliary hypothesis test. We show how importance sampling can significantly improve estimation when probabilities are low, but find it is not a panacea for rare schedulers.
Type de document :
Communication dans un congrès
Proceedings of the 15th International Workshop on Automated Verification of Critical Systems (AVoCS 2015), Sep 2015, Edinburgh, United Kingdom. 72, 〈10.14279/tuj.eceasst.72.1023〉
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01239051
Contributeur : Sean Sedwards <>
Soumis le : lundi 7 décembre 2015 - 13:14:16
Dernière modification le : mardi 16 janvier 2018 - 15:54:23
Document(s) archivé(s) le : mardi 8 mars 2016 - 12:44:06

Fichier

AVoCS15_rewards.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Axel Legay, Sean Sedwards, Louis-Marie Traonouez. Estimating Rewards & Rare Events in Nondeterministic Systems. Proceedings of the 15th International Workshop on Automated Verification of Critical Systems (AVoCS 2015), Sep 2015, Edinburgh, United Kingdom. 72, 〈10.14279/tuj.eceasst.72.1023〉. 〈hal-01239051〉

Partager

Métriques

Consultations de la notice

377

Téléchargements de fichiers

85