# Learning-Based Mean-Payoff Optimization in an Unknown MDP under Omega-Regular Constraints

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2018.

## Built on by (most cited first, 8 of 8)

- [Learning Non-Markovian Reward Models in MDPs](https://mlsanity.com/paper/2001.09293/) (2020)
- [Online Learning of Non-Markovian Reward Models](https://mlsanity.com/paper/2009.12600/) (2020)
- [Model-Free Learning of Safe yet Effective Controllers](https://mlsanity.com/paper/2103.14600/) (2021)
- [What Are the Odds? Improving the foundations of Statistical Model Checking](https://mlsanity.com/paper/2404.05424/) (2024)
- [PAC Statistical Model Checking of Mean Payoff in Discrete- and Continuous-Time MDP](https://mlsanity.com/paper/2206.01465/) (2022)
- [Follow the STARs: Dynamic ω-Regular Shielding of Learned Policies](https://mlsanity.com/paper/2505.14689/) (2025)
- [Lecture Notes on Partially Known MDPs](https://mlsanity.com/paper/2112.02976/) (2021)
- [Value Functions as Supermartingale Certificates](https://mlsanity.com/paper/2605.31524/) (2026)

## Abstract (arXiv)

We formalize the problem of maximizing the mean-payoff value with high probability while satisfying a parity objective in a Markov decision process (MDP) with unknown probabilistic transition function and unknown reward function. Assuming the support of the unknown transition function and a lower bound on the minimal transition probability are known in advance, we show that in MDPs consisting of a single end component, two combinations of guarantees on the parity and mean-payoff objectives can be achieved depending on how much memory one is willing to use. (i) For all ε and γ we can construct an online-learning finite-memory strategy that almost-surely satisfies the parity objective and which achieves an ε-optimal mean payoff with probability at least 1 - γ. (ii) Alternatively, for all ε and γ there exists an online-learning infinite-memory strategy that satisfies the parity objective surely and which achieves an ε-optimal mean payoff with probability at least 1 - γ. We extend the above results to MDPs consisting of more than one end component in a natural way. Finally, we show that the aforementioned guarantees are tight, i.e. there are MDPs for which stronger combinations of the guarantees cannot be ensured.