# Mixing Any Cocktail with Limited Ingredients: On the Structure of Payoff Sets in Multi-Objective POMDPs and its Impact on Randomised Strategies

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 57 references that are in the map.
- First posted on arXiv 25 Feb 2025.

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

- [Pareto Conditioned Networks](https://mlsanity.com/paper/2204.05036/) (2022)
- [Optimizing Expectation with Guarantees in POMDPs (Technical Report)](https://mlsanity.com/paper/1611.08696/) (2016)
- [Simple Strategies in Multi-Objective MDPs (Technical Report)](https://mlsanity.com/paper/1910.11024/) (2019)
- [Percentile Queries in Multi-Dimensional Markov Decision Processes](https://mlsanity.com/paper/1410.4801/) (2014)
- [Expectation Optimization with Probabilistic Guarantees in POMDPs with Discounted-sum Objectives](https://mlsanity.com/paper/1804.10601/) (2018)
- [Unifying Two Views on Multiple Mean-Payoff Objectives in Markov Decision Processes](https://mlsanity.com/paper/1502.00611/) (2015)
- [Life is Random, Time is Not: Markov Decision Processes with Window Objectives](https://mlsanity.com/paper/1901.03571/) (2019)
- [Games Where You Can Play Optimally with Arena-Independent Finite Memory](https://mlsanity.com/paper/2001.03894/) (2020)
- [Strategy Complexity of Parity Objectives in Countable MDPs](https://mlsanity.com/paper/2007.05065/) (2020)
- [Arena-Independent Finite-Memory Determinacy in Stochastic Games](https://mlsanity.com/paper/2102.10104/) (2021)
- [Different Strokes in Randomised Strategies: Revisiting Kuhn's Theorem under Finite-Memory Assumptions](https://mlsanity.com/paper/2201.10825/) (2022)
- [Games on Graphs: From Logic and Automata to Algorithms](https://mlsanity.com/paper/2305.10546/) (2023)
- [Meet Your Expectations With Guarantees: Beyond Worst-Case Synthesis in Quantitative Games](https://mlsanity.com/paper/1309.5439/) (2013)
- [Submixing and Shift-invariant Stochastic Games](https://mlsanity.com/paper/1401.6575/) (2014)
- [Average-energy games (full version)](https://mlsanity.com/paper/1512.08106/) (2015)
- [Extending finite-memory determinacy by Boolean combination of winning conditions](https://mlsanity.com/paper/1808.05791/) (2018)
- [Energy mean-payoff games](https://mlsanity.com/paper/1907.01359/) (2019)
- [Multi-objective Optimization of Long-run Average and Total Rewards](https://mlsanity.com/paper/2010.13566/) (2020)
- [Characterizing Omega-Regularity through Finite-Memory Determinacy of Games on Infinite Graphs](https://mlsanity.com/paper/2110.01276/) (2021)
- [Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs](https://mlsanity.com/paper/2203.07079/) (2022)
- [Characterising memory in infinite games](https://mlsanity.com/paper/2209.12044/) (2022)
- [Bi-Objective Lexicographic Optimization in Markov Decision Processes with Related Objectives](https://mlsanity.com/paper/2305.09634/) (2023)
- [Reaching Your Goal Optimally by Playing at Random](https://mlsanity.com/paper/2005.04985/) (2020)

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

- [Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs](https://mlsanity.com/paper/2503.00788/) (2025)
- [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 multi-dimensional payoff functions in partially observable Markov decision processes. We study the structure of the set of expected payoff vectors of all strategies (policies) and study what kind are needed to achieve a given expected payoff vector. In general, pure strategies (i.e., not resorting to randomisation) do not suffice for this problem. We prove that for any payoff for which the expectation is well-defined under all strategies, it is sufficient to mix (i.e., randomly select a pure strategy at the start of a play and committing to it for the rest of the play) finitely many pure strategies to approximate any expected payoff vector up to any precision. Furthermore, for any payoff for which the expected payoff is finite under all strategies, any expected payoff can be obtained exactly by mixing finitely many strategies.