# Entropy Objectives in Markov Decision Processes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 45 references that are in the map.
- First posted on arXiv 19 Jun 2026.

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

- [Entropy Maximization for Markov Decision Processes Under Temporal Logic Constraints](https://mlsanity.com/paper/1807.03223/) (2018)
- [Stochastic Omega-Regular Verification and Control with Supermartingales](https://mlsanity.com/paper/2405.17304/) (2024)
- [Termination Analysis of Probabilistic Programs through Positivstellensatz's](https://mlsanity.com/paper/1604.07169/) (2016)
- [Stochastic Invariants for Probabilistic Termination](https://mlsanity.com/paper/1611.01063/) (2016)
- [Polynomial Invariant Generation for Non-deterministic Recursive Programs](https://mlsanity.com/paper/1902.04373/) (2019)
- [MDPs as Distribution Transformers: Affine Invariant Synthesis for Safety Objectives](https://mlsanity.com/paper/2305.16796/) (2023)
- [PolyQEnt: A Polynomial Quantified Entailment Solver](https://mlsanity.com/paper/2408.03796/) (2024)
- [Limit Synchronization in Markov Decision Processes](https://mlsanity.com/paper/1310.2935/) (2013)
- [The Complexity of Synchronizing Markov Decision Processes](https://mlsanity.com/paper/1604.01942/) (2016)
- [Distribution-based objectives for Markov Decision Processes](https://mlsanity.com/paper/1804.09341/) (2018)
- [Probabilistic Program Verification via Inductive Synthesis of Inductive Invariants](https://mlsanity.com/paper/2205.06152/) (2022)
- [Certified Policy Verification and Synthesis for MDPs under Distributional Reach-avoidance Properties](https://mlsanity.com/paper/2405.04015/) (2024)

## Abstract (arXiv)

We consider the problem of synthesizing control policies that enforce a concentration property on the state distributions of a stochastic system. We present a formalization of this problem in terms of synthesizing strategies for maintaining an entropy-based objective in Markov Decision Processes (MDPs). We first show that even relaxed versions of this problem are complexity-theoretically hard. We then present a sound and (conditionally) relatively complete method to verify and synthesize strategies for such entropy objectives. The main challenge is the non-linear nature of such objectives, and our approach addresses this by exploiting and combining ideas from convex duality and invariant synthesis. We also investigate the role of memory and randomization in ensuring entropy objectives. Finally, we implement our ideas to evaluate our approach empirically on a few illustrative benchmarks.