# Reward-Free Policy Space Compression for Reinforcement Learning

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 41 references that are in the map.
- First posted on arXiv 22 Feb 2022.

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

- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Diversity is All You Need: Learning Skills without a Reward Function](https://mlsanity.com/paper/1802.06070/) (2018)
- [Variational Intrinsic Control](https://mlsanity.com/paper/1611.07507/) (2016)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reward-Free Exploration for Reinforcement Learning](https://mlsanity.com/paper/2002.02794/) (2020)
- [Fast Task Inference with Variational Intrinsic Successor Features](https://mlsanity.com/paper/1906.05030/) (2019)
- [Variational Option Discovery Algorithms](https://mlsanity.com/paper/1807.10299/) (2018)
- [Towards Optimal Off-Policy Evaluation for Reinforcement Learning with Marginalized Importance Sampling](https://mlsanity.com/paper/1906.03393/) (2019)
- [Policy Optimization via Importance Sampling](https://mlsanity.com/paper/1809.06098/) (2018)
- [The Information Geometry of Unsupervised Reinforcement Learning](https://mlsanity.com/paper/2110.02719/) (2021)
- [Discovering a set of policies for the worst case reward](https://mlsanity.com/paper/2102.04323/) (2021)
- [Generative predecessor models for sample-efficient imitation learning](https://mlsanity.com/paper/1904.01139/) (2019)
- [Gradient Descent-Ascent Provably Converges to Strict Local Minmax Equilibria with a Finite Timescale Separation](https://mlsanity.com/paper/2009.14820/) (2020)
- [Policy Optimization as Online Learning with Mediator Feedback](https://mlsanity.com/paper/2012.08225/) (2020)

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

- [From Parameters to Behaviors: Unsupervised Compression of the Policy Space](https://mlsanity.com/paper/2509.22566/) (2025)
- [Towards A Unified Policy Abstraction Theory and Representation Learning Approach in Markov Decision Processes](https://mlsanity.com/paper/2209.07696/) (2022)
- [Unsupervised Behavioral Compression: Learning Low-Dimensional Policy Manifolds through State-Occupancy Matching](https://mlsanity.com/paper/2603.27044/) (2026)
- [Representative Action Selection for Large Action Space: From Bandits to MDPs](https://mlsanity.com/paper/2511.22104/) (2025)
- [Learning in Low-Dimensional Subspaces: Orthogonal Bottlenecks for Reinforcement Learning](https://mlsanity.com/paper/2605.26012/) (2026)
- [Implicit Neural Representations of Individual Behavior](https://mlsanity.com/paper/2606.12200/) (2026)

## Abstract (arXiv)

In reinforcement learning, we encode the potential behaviors of an agent interacting with an environment into an infinite set of policies, the policy space, typically represented by a family of parametric functions. Dealing with such a policy space is a hefty challenge, which often causes sample and computation inefficiencies. However, we argue that a limited number of policies are actually relevant when we also account for the structure of the environment and of the policy parameterization, as many of them would induce very similar interactions, i.e., state-action distributions. In this paper, we seek for a reward-free compression of the policy space into a finite set of representative policies, such that, given any policy π, the minimum R'enyi divergence between the state-action distributions of the representative policies and the state-action distribution of π is bounded. We show that this compression of the policy space can be formulated as a set cover problem, and it is inherently NP-hard. Nonetheless, we propose a game-theoretic reformulation for which a locally optimal solution can be efficiently found by iteratively stretching the compressed space to cover an adversarial policy. Finally, we provide an empirical evaluation to illustrate the compression procedure in simple domains, and its ripple effects in reinforcement learning.