Multiple Mean-Payoff Optimization Under Local Stability Constraints
| Authors | |
|---|---|
| Year of publication | 2025 |
| Type | Article in Proceedings |
| Conference | Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39 No. 25: AAAI-25 Technical Tracks 25 |
| MU Faculty or unit | |
| Citation | |
| web | http://dx.doi.org/10.1609/aaai.v39i25.34856 |
| Doi | https://doi.org/10.1609/aaai.v39i25.34856 |
| Keywords | Multiple Mean-Payoff Optimization |
| Description | 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. |