# From Relative Entropy to Minimax: A Unified Framework for Coverage in MDPs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 30 references that are in the map.
- First posted on arXiv 17 Jan 2026.

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

- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Generative Adversarial Imitation Learning](https://mlsanity.com/paper/1606.03476/) (2016)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Efficient Exploration via State Marginal Matching](https://mlsanity.com/paper/1906.05274/) (2019)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [On Learning Intrinsic Rewards for Policy Gradient Methods](https://mlsanity.com/paper/1804.06459/) (2018)
- [Fast active learning for pure exploration in reinforcement learning](https://mlsanity.com/paper/2007.13442/) (2020)
- [The Role of Coverage in Online Reinforcement Learning](https://mlsanity.com/paper/2210.04157/) (2022)
- [Adaptive Reward-Free Exploration](https://mlsanity.com/paper/2006.06294/) (2020)
- [When to Trust Your Simulator: Dynamics-Aware Hybrid Offline-and-Online Reinforcement Learning](https://mlsanity.com/paper/2206.13464/) (2022)
- [Fast Rates for Maximum Entropy Exploration](https://mlsanity.com/paper/2303.08059/) (2023)
- [Active Exploration in Markov Decision Processes](https://mlsanity.com/paper/1902.11199/) (2019)
- [Adaptive Sampling for Minimax Fair Classification](https://mlsanity.com/paper/2103.00755/) (2021)
- [Active Model Estimation in Markov Decision Processes](https://mlsanity.com/paper/2003.03297/) (2020)
- [Global Reinforcement Learning: Beyond Linear and Convex Rewards via Submodular Semi-gradient Methods](https://mlsanity.com/paper/2407.09905/) (2024)
- [Active Coverage for PAC Reinforcement Learning](https://mlsanity.com/paper/2306.13601/) (2023)
- [Fixed-horizon Active Hypothesis Testing](https://mlsanity.com/paper/1911.06912/) (2019)
- [What can online reinforcement learning with function approximation benefit from general coverage conditions?](https://mlsanity.com/paper/2304.12886/) (2023)

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

- [kappa-Explorer: A Unified Framework for Active Model Estimation in MDPs](https://mlsanity.com/paper/2602.20404/) (2026)

## Abstract (arXiv)

Targeted and deliberate exploration of state--action pairs is essential in reward-free Markov Decision Problems (MDPs). More precisely, different state-action pairs exhibit different degree of importance or difficulty which must be actively and explicitly built into a controlled exploration strategy. To this end, we propose a weighted and parameterized family of concave coverage objectives, denoted by Uρ, defined directly over state--action occupancy measures. This family unifies several widely studied objectives within a single framework, including divergence-based marginal matching, weighted average coverage, and worst-case (minimax) coverage. While the concavity of Uρ captures the diminishing return associated with over-exploration, the simple closed form of the gradient of Uρ enables an explicit control to prioritize under-explored state--action pairs. Leveraging this structure, we develop a gradient-based algorithm that actively steers the induced occupancy toward a desired coverage pattern. Moreover, we show that as ρ increases, the resulting exploration strategy increasingly emphasizes the least-explored state--action pairs, recovering worst-case coverage behavior in the limit.