# An Analysis of the Value of Information when Exploring Stochastic, Discrete Multi-Armed Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2017.

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

- [An Information-Theoretic Approach for Automatically Determining the Number of States when Aggregating Markov Chains](https://mlsanity.com/paper/2107.01799/) (2021)

## Abstract (arXiv)

In this paper, we propose an information-theoretic exploration strategy for stochastic, discrete multi-armed bandits that achieves optimal regret. Our strategy is based on the value of information criterion. This criterion measures the trade-off between policy information and obtainable rewards. High amounts of policy information are associated with exploration-dominant searches of the space and yield high rewards. Low amounts of policy information favor the exploitation of existing knowledge. Information, in this criterion, is quantified by a parameter that can be varied during search. We demonstrate that a simulated-annealing-like update of this parameter, with a sufficiently fast cooling schedule, leads to an optimal regret that is logarithmic with respect to the number of episodes.