# Simplicity Lies in the Eye of the Beholder: A Strategic Perspective on Controllers in Reactive Synthesis

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 54 references that are in the map.
- First posted on arXiv 4 Sep 2025.

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

- [Qualitative Controller Synthesis for Consumption Markov Decision Processes](https://mlsanity.com/paper/2005.07227/) (2020)
- [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)
- [Strategy Representation by Decision Trees in Reactive Synthesis](https://mlsanity.com/paper/1802.00758/) (2018)
- [Looking at Mean-Payoff and Total-Payoff through Windows](https://mlsanity.com/paper/1302.4248/) (2013)
- [Variations on the Stochastic Shortest Path Problem](https://mlsanity.com/paper/1411.0835/) (2014)
- [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)
- [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)
- [Characterizing Omega-Regularity through Finite-Memory Determinacy of Games on Infinite Graphs](https://mlsanity.com/paper/2110.01276/) (2021)
- [Characterising memory in infinite games](https://mlsanity.com/paper/2209.12044/) (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)
- [Extending Finite Memory Determinacy to Multiplayer Games](https://mlsanity.com/paper/1602.08912/) (2016)
- [Window Parity Games: An Alternative Approach Toward Parity Games with Time Bounds](https://mlsanity.com/paper/1606.01831/) (2016)
- [Playing Stochastically in Weighted Timed Games to Emulate Memory](https://mlsanity.com/paper/2105.00984/) (2021)
- [Half-Positional Objectives Recognized by Deterministic B"uchi Automata](https://mlsanity.com/paper/2205.01365/) (2022)
- [How to Play Optimally for Regular Objectives?](https://mlsanity.com/paper/2210.09703/) (2022)
- [Positional ω-regular languages](https://mlsanity.com/paper/2401.15384/) (2024)
- [Programmatic Reinforcement Learning: Navigating Gridworlds](https://mlsanity.com/paper/2402.11650/) (2024)
- [Taming Infinity one Chunk at a Time: Concisely Represented Strategies in One-Counter MDPs](https://mlsanity.com/paper/2503.00788/) (2025)

## Abstract (arXiv)

In the game-theoretic approach to controller synthesis, we model the interaction between a system to be controlled and its environment as a game between these entities, and we seek an appropriate (e.g., winning or optimal) strategy for the system. This strategy then serves as a formal blueprint for a real-world controller. A common belief is that simple (e.g., using limited memory) strategies are better: corresponding controllers are easier to conceive and understand, and cheaper to produce and maintain. This invited contribution focuses on the complexity of strategies in a variety of synthesis contexts. We discuss recent results concerning memory and randomness, and take a brief look at what lies beyond our traditional notions of complexity for strategies.