# Multi-Armed Bandits with Self-Information Rewards

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 68 references that are in the map.
- First posted on arXiv 6 Sep 2022.

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

- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Learning to Optimize via Information-Directed Sampling](https://mlsanity.com/paper/1403.5556/) (2014)
- [Information Directed Sampling and Bandits with Heteroscedastic Noise](https://mlsanity.com/paper/1801.09667/) (2018)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [Thompson Sampling for Complex Bandit Problems](https://mlsanity.com/paper/1311.0466/) (2013)
- [Asymptotically Optimal Information-Directed Sampling](https://mlsanity.com/paper/2011.05944/) (2020)
- [Regret Minimization in Heavy-Tailed Bandits](https://mlsanity.com/paper/2102.03734/) (2021)
- [Fast Frontier-based Information-driven Autonomous Exploration with an MAV](https://mlsanity.com/paper/2002.04440/) (2020)
- [Distribution oblivious, risk-aware algorithms for multi-armed bandits with unbounded rewards](https://mlsanity.com/paper/1906.00569/) (2019)
- [Near Optimal Exploration-Exploitation in Non-Communicating Markov Decision Processes](https://mlsanity.com/paper/1807.02373/) (2018)
- [Restless Multi-Armed Bandits under Exogenous Global Markov Process](https://mlsanity.com/paper/2202.13665/) (2022)

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

- [Be More Diverse than the Most Diverse: Optimal Mixtures of Generative Models via Mixture-UCB Bandit Algorithms](https://mlsanity.com/paper/2412.17622/) (2024)
- [A Multi-Armed Bandit Approach to Online Selection and Evaluation of Generative Models](https://mlsanity.com/paper/2406.07451/) (2024)
- [DAK-UCB: Diversity-Aware Prompt Routing for LLMs and Generative Models](https://mlsanity.com/paper/2603.23140/) (2026)
- [Maximal-Capacity Discrete Memoryless Channel Identification](https://mlsanity.com/paper/2401.10204/) (2024)
- [Exploration-Exploitation Tradeoff in Universal Lossy Compression](https://mlsanity.com/paper/2506.20261/) (2025)

## Abstract (arXiv)

This paper introduces the informational multi-armed bandit (IMAB) model in which at each round, a player chooses an arm, observes a symbol, and receives an unobserved reward in the form of the symbol's self-information. Thus, the expected reward of an arm is the Shannon entropy of the probability mass function of the source that generates its symbols. The player aims to maximize the expected total reward associated with the entropy values of the arms played. Under the assumption that the alphabet size is known, two UCB-based algorithms are proposed for the IMAB model which consider the biases of the plug-in entropy estimator. The first algorithm optimistically corrects the bias term in the entropy estimation. The second algorithm relies on data-dependent confidence intervals that adapt to sources with small entropy values. Performance guarantees are provided by upper bounding the expected regret of each of the algorithms. Furthermore, in the Bernoulli case, the asymptotic behavior of these algorithms is compared to the Lai-Robbins lower bound for the pseudo regret. Additionally, under the assumption that the textitexact alphabet size is unknown, and instead the player only knows a loose upper bound on it, a UCB-based algorithm is proposed, in which the player aims to reduce the regret caused by the unknown alphabet size in a finite time regime. Numerical results illustrating the expected regret of the algorithms presented in the paper are provided.