# Exploration-Exploitation Tradeoff in Universal Lossy Compression

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

## Key facts

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

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [Multi-Armed Bandits with Self-Information Rewards](https://mlsanity.com/paper/2209.02211/) (2022)
- [Improved Offline Contextual Bandits with Second-Order Bounds: Betting and Freezing](https://mlsanity.com/paper/2502.10826/) (2025)
- [Reinforcement Learning for Near-Optimal Design of Zero-Delay Codes for Markov Sources](https://mlsanity.com/paper/2311.12609/) (2023)

## Abstract (arXiv)

Universal compression can learn the source and adapt to it either in a batch mode (forward adaptation), or in a sequential mode (backward adaptation). We recast the sequential mode as a multi-armed bandit problem, a fundamental model in reinforcement-learning, and study the trade-off between exploration and exploitation in the lossy compression case. We show that a previously proposed "natural type selection" scheme can be cast as a reconstruction-directed MAB algorithm, for sequential lossy compression, and explain its limitations in terms of robustness and short-block performance. We then derive and analyze robust cost-directed MAB algorithms, which work at any block length.