Level: M2
Contact: Laurent Doyen
Keywords: automata theory, probability, algorithms.
Read the internship proposal in pdf.
Description
Finite-state stochastic games combine the stochastic aspects of Markov chains and the interactive aspects of two-player games. In a traditional view, Markov chains generate a probability measure over sequences of states (called paths), and questions such as “What is the probability that a path reaches a given state?” can be solved. In a more recent view, Markov chains generate a sequence of probability distributions {$d_i:Q \to [0,1]$} over their state space {$Q$} , where {$d_i(q)$} is the probability that the Markov chain is in state {$q \in Q$} after {$i$} execution steps. This distribution-based view has been considered recently in works on Markov chains and Markov decision processes (MDPs) [3, 1, 2], as a model of large- population systems consisting of several copies of the same process (molecules, sensors, bacteria, etc.). The dynamics of the system is described by a finite-state stochastic process, and a distribution {$d_i(q)$} is interpreted as the percentage of the population that is in state {$q$} at step {$i$}.
In this context, synchronization properties require that the sequence of probability distributions tends to accumulate all the probability mass in a given set {$T \subseteq Q$} of target states, that is all process instances synchronize in {$T$} . They generalize synchronizing properties of finite automata [4]. Different modes of synchronization can be defined, which require for instance the synchronization to occur once, or infinitely often. The synchronization modes are reminiscent of the traditional reachability, safety, Büchi, and coBüchi objectives [2].
In this internship (with possible continuation as a phd thesis), we consider stochastic games in the distribution-based view. We are looking for algorithmic solutions and structural properties of stochastic games where the objective of one of the player is given by a synchronization property. Several theoretical questions can be investigated and the solutions and heuristics can possibly lead to prototype implementations.
References
[1] S. Akshay, B. Genest, and N. Vyas. Distribution-based objectives for Markov decision processes. In Proc. of LICS: Logic in Computer Science, pages 36–45. ACM, 2018.
[2] L. Doyen, T. Massart, and M. Shirmohammadi. The complexity of synchronizing Markov decision processes. Journal of Computer and System Sciences, 100:96–129, 2019.
[3] V. A. Korthikanti, M. Viswanathan, G. Agha, and Y. Kwon. Reasoning about MDPs as transformers of probability distributions. In Proc. of QEST: Quantitative Evaluation of Systems, pages 199–208. IEEE Computer Society, 2010.
[4] M. V. Volkov. Synchronizing automata and the ˇCern ́y conjecture. In Proc. of LATA: Language and Automata Theory and Applications, LNCS 5196, pages 11–27. Springer, 2008.
Profile
- Knowledge in automata theory, combinatorics, probabilities, and algorithms.
- Language: French or English.
Where:
Laboratoire Méthodes Formelles (LMF)
École Normale Supérieure Paris-Saclay
4, avenue des sciences
91190 Gif-sur-Yvette
FRANCE