Multiple Mean-Payoff Optimization Under Local Stability Constraints
David Klaška, Antonín Kučera, Vojtěch Kůr, Vít Musil, Vojtěch Řehák
Abstract
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.
BibTeX
@article{Klaška_Kučera_Kůr_Musil_Řehák_2025, title={Multiple Mean-Payoff Optimization Under Local Stability Constraints}, volume={39}, url={https://ojs.aaai.org/index.php/AAAI/article/view/34856}, DOI={10.1609/aaai.v39i25.34856}, abstractNote={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.}, number={25}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Klaška, David and Kučera, Antonín and Kůr, Vojtěch and Musil, Vít and Řehák, Vojtěch}, year={2025}, month={Apr.}, pages={26551-26558} }