# Multiple Mean-Payoff Optimization under Local Stability Constraints

arXiv: https://arxiv.org/abs/2412.13369 · HTML: https://mlsanity.com/paper/2412.13369/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 16 references that are in the map.
- First posted on arXiv 17 Dec 2024.

## Builds on (most cited first, 6 of 6)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Looking at Mean-Payoff and Total-Payoff through Windows](https://mlsanity.com/paper/1302.4248/) (2013)
- [MultiGain: A controller synthesis tool for MDPs with multiple mean-payoff objectives](https://mlsanity.com/paper/1501.03093/) (2015)
- [Life is Random, Time is Not: Markov Decision Processes with Window Objectives](https://mlsanity.com/paper/1901.03571/) (2019)
- [Trading Performance for Stability in Markov Decision Processes](https://mlsanity.com/paper/1305.4103/) (2013)

## Abstract (arXiv)

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.