# Percentile Queries in Multi-Dimensional Markov Decision Processes

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Oct 2014.

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

- [Reinforcement Learning Methods for Wordle: A POMDP/Adaptive Control Approach](https://mlsanity.com/paper/2211.10298/) (2022)
- [Mixing Any Cocktail with Limited Ingredients: On the Structure of Payoff Sets in Multi-Objective POMDPs and its Impact on Randomised Strategies](https://mlsanity.com/paper/2502.18296/) (2025)
- [Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs](https://mlsanity.com/paper/2503.00788/) (2025)
- [Polynomial-Time Algorithms for Multi-Agent Minimal-Capacity Planning](https://mlsanity.com/paper/2105.01225/) (2021)
- [Simplicity Lies in the Eye of the Beholder: A Strategic Perspective on Controllers in Reactive Synthesis](https://mlsanity.com/paper/2509.04129/) (2025)
- [Categorizer Automata for Discounted-Sum Payoffs](https://mlsanity.com/paper/2608.26763/) (2026)

## Abstract (arXiv)

Markov decision processes (MDPs) with multi-dimensional weights are useful to analyze systems with multiple objectives that may be conflicting and require the analysis of trade-offs. We study the complexity of percentile queries in such MDPs and give algorithms to synthesize strategies that enforce such constraints. Given a multi-dimensional weighted MDP and a quantitative payoff function f, thresholds vi (one per dimension), and probability thresholds αi, we show how to compute a single strategy to enforce that for all dimensions i, the probability of outcomes ρ satisfying fi(ρ) ≥ vi is at least αi. We consider classical quantitative payoffs from the literature (sup, inf, lim sup, lim inf, mean-payoff, truncated sum, discounted sum). Our work extends to the quantitative case the multi-objective model checking problem studied by Etessami et al. in unweighted MDPs.