Multiple Mean-Payoff Optimization Under Local Stability Constraints

Varování

Publikace nespadá pod Ústav výpočetní techniky, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.

Autoři	KLAŠKA David KUČERA Antonín KŮR Vojtěch MUSIL Vít ŘEHÁK Vojtěch
Rok publikování	2025
Druh	Článek ve sborníku
Konference	Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39 No. 25: AAAI-25 Technical Tracks 25
Fakulta / Pracoviště MU	Fakulta informatiky
Citace
www	http://dx.doi.org/10.1609/aaai.v39i25.34856
Doi	https://doi.org/10.1609/aaai.v39i25.34856
Klíčová slova	Multiple Mean-Payoff Optimization
Popis	The long-run average payoff per transition (mean payoff) is the main tool for specifying the performance and dependability properties of discrete systems. The problem of constructing a controller (strategy) simultaneously optimizing several mean payoffs has been deeply studied for stochastic and game-theoretic models. One common issue of the constructed controllers is the instability of the mean payoffs, measured by the deviations of the average rewards per transition computed in a finite "window" sliding along a run. Unfortunately, the problem of simultaneously optimizing the mean payoffs under local stability constraints is computationally hard, and the existing works do not provide a practically usable algorithm even for non-stochastic models such as two-player games. In this paper, we design and evaluate the first efficient and scalable solution to this problem applicable to Markov decision processes.