# Simple Strategies in Multi-Objective MDPs (Technical Report)

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

## Key facts

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

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

- [Composing Reinforcement Learning Policies, with Formal Guarantees](https://mlsanity.com/paper/2402.13785/) (2024)
- [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)
- [Multi-Objective Controller Synthesis with Uncertain Human Preferences](https://mlsanity.com/paper/2105.04662/) (2021)
- [Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs](https://mlsanity.com/paper/2503.00788/) (2025)
- [Best-Effort Policies for Robust Markov Decision Processes](https://mlsanity.com/paper/2508.07790/) (2025)
- [Level Assembly as a Markov Decision Process](https://mlsanity.com/paper/2304.13922/) (2023)
- [Simplicity Lies in the Eye of the Beholder: A Strategic Perspective on Controllers in Reactive Synthesis](https://mlsanity.com/paper/2509.04129/) (2025)

## Abstract (arXiv)

We consider the verification of multiple expected reward objectives at once on Markov decision processes (MDPs). This enables a trade-off analysis among multiple objectives by obtaining the Pareto front. We focus on strategies that are easy to employ and implement. That is, strategies that are pure (no randomization) and have bounded memory. We show that checking whether a point is achievable by a pure stationary strategy is NP-complete, even for two objectives, and we provide an MILP encoding to solve the corresponding problem. The bounded memory case can be reduced to the stationary one by a product construction. Experimental results using Storm and Gurobi show the feasibility of our algorithms.