# k-Means Maximum Entropy Exploration

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 29 references that are in the map.
- First posted on arXiv 31 May 2022.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [dm_control: Software and Tasks for Continuous Control](https://mlsanity.com/paper/2006.12983/) (2020)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Self-Supervised Exploration via Disagreement](https://mlsanity.com/paper/1906.04161/) (2019)
- [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)
- [Behavior From the Void: Unsupervised Active Pre-Training](https://mlsanity.com/paper/2103.04551/) (2021)
- [URLB: Unsupervised Reinforcement Learning Benchmark](https://mlsanity.com/paper/2110.15191/) (2021)
- [APS: Active Pretraining with Successor Features](https://mlsanity.com/paper/2108.13956/) (2021)
- [State Entropy Maximization with Random Encoders for Efficient Exploration](https://mlsanity.com/paper/2102.09430/) (2021)
- [Geometric Entropic Exploration](https://mlsanity.com/paper/2101.02055/) (2021)
- [Task-Agnostic Exploration via Policy Gradient of a Non-Parametric State Entropy Estimate](https://mlsanity.com/paper/2007.04640/) (2020)
- [VIME: Variational Information Maximizing Exploration](https://mlsanity.com/paper/1605.09674/) (2016)

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

- [Correlated Proxies: A New Definition and Improved Mitigation for Reward Hacking](https://mlsanity.com/paper/2403.03185/) (2024)
- [Accelerating Reinforcement Learning with Value-Conditional State Entropy Exploration](https://mlsanity.com/paper/2305.19476/) (2023)
- [How to Explore with Belief: State Entropy Maximization in POMDPs](https://mlsanity.com/paper/2406.02295/) (2024)
- [The Limits of Pure Exploration in POMDPs: When the Observation Entropy is Enough](https://mlsanity.com/paper/2406.12795/) (2024)
- [State Entropy Regularization for Robust Reinforcement Learning](https://mlsanity.com/paper/2506.07085/) (2025)
- [Towards Principled Unsupervised Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2502.08365/) (2025)
- [Enhancing Diversity in Parallel Agents: A Maximum State Entropy Exploration Story](https://mlsanity.com/paper/2505.01336/) (2025)
- [ELEMENT: Episodic and Lifelong Exploration via Maximum Entropy](https://mlsanity.com/paper/2412.03800/) (2024)
- [Inference with K-means](https://mlsanity.com/paper/2410.17256/) (2024)
- [An Information-Geometric Approach to Artificial Curiosity](https://mlsanity.com/paper/2504.06355/) (2025)
- [K-Myriad: Jump-starting reinforcement learning with unsupervised parallel agents](https://mlsanity.com/paper/2601.18580/) (2026)

## Abstract (arXiv)

Exploration in high-dimensional, continuous spaces with sparse rewards is an open problem in reinforcement learning. Artificial curiosity algorithms address this by creating rewards that lead to exploration. Given a reinforcement learning algorithm capable of maximizing rewards, the problem reduces to finding an optimization objective consistent with exploration. Maximum entropy exploration uses the entropy of the state visitation distribution as such an objective. However, efficiently estimating the entropy of the state visitation distribution is challenging in high-dimensional, continuous spaces. We introduce an artificial curiosity algorithm based on lower bounding an approximation to the entropy of the state visitation distribution. The bound relies on a result we prove for non-parametric density estimation in arbitrary dimensions using k-means. We show that our approach is both computationally efficient and competitive on benchmarks for exploration in high-dimensional, continuous spaces, especially on tasks where reinforcement learning algorithms are unable to find rewards.