Exploration-Exploitation Tradeoff in Universal Lossy Compression
This addresses a fundamental problem in compression theory for improving sequential adaptation methods, though it appears incremental as it builds on existing bandit frameworks.
The paper tackles the exploration-exploitation tradeoff in universal lossy compression by recasting sequential adaptation as a multi-armed bandit problem, showing that a prior scheme has limitations and deriving robust algorithms that work at any block length.
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.