Information-directed sampling for bandits: a primer
Annika Hirling, Giorgio Nicoletti, Antonio Celani · 2025
Read Information-directed sampling for bandits: a primer by Annika Hirling, Giorgio Nicoletti, Antonio Celani (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-20096.txt.
Introduction
Annika Hirling, Giorgio Nicoletti, and Antonio Celani wrote a primer on information-directed sampling. The stage is the multi-armed bandit problem. It is the classic clash of exploration and exploitation. Information-directed policies pick arms by weighing regret now against information gain. Their theory can be forbidding. The primer steps back to a tractable arena. Two-state Bernoulli bandits serve as the minimal model. There, heuristics can be compared with the true optimal policy in strict form.
The frame is extended to discounted, infinite-horizon problems. A modified information measure and a tuning knob shape the choices. In symmetric bandits, the method holds cumulative regret bounded. In the one-fair-coin case, its regret grows only with the log of the horizon. That matches classic lower bounds. The piece is aimed at statistical physicists. It bridges reinforcement learning and information theory.
Catalog record
| CREATOR | Annika Hirling, Giorgio Nicoletti, Antonio Celani |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-20096
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Information-directed sampling for bandits: a primer Preprint: APS/123-QED Annika Hirling, Giorgio Nicoletti, Antonio Celani Abstract The Multi-Armed Bandit problem provides a fundamental framework for analyzing the tension between exploration and exploitation in sequential learning. This paper explores Information Directed Sampling (IDS) policies, a class of heuristics that balance immediate regret against information gain. We focus on the tractable environment of two-state Bernoulli bandits as a minimal model to rigorously compare heuristic strategies against the optimal policy. We extend the IDS framework to the discounted infinite-horizon setting by introducing a modified information measure and a tuning parameter to modulate the decision-making behavior. We examine two specific problem classes: symmetric bandits and the scenario involving one fair coin. In the symmetric case we show that IDS achieves bounded cumulative regret, whereas in the one-fair-coin scenario the IDS policy yields a regret that scales logarithmically with the horizon, in agreement with classical asymptotic lower bounds. This work serves as a pedagogical synthesis, aiming to bridge concepts from reinforcement learning and information theory for an audience of statistical physicists. I Introduction “Knowing ignorance is strength. Ignoring knowledge is sickness.” ―Lao Tsu, Tao Te Ching Understanding how to make good decisions in uncertain and partially observable environments is the key to success for humans, animals and machine alike. How can we make a profitable use of the limited knowledge we have about the world? How can we increase our knowledge without indulging in idle curiosity? How can we maximize our gain without being greedy and close-minded? The Multi-Armed Bandit (MAB) problem – which describes situations where a decision-maker must choose repeatedly among different options, each giving uncertain rewards – serves as the canonical mathematical framework for studying this kind of dilemmas 11 ; 7 . Although bandit problems are often characterized as a simplified model of the broader Reinforcement Learning (RL) landscape, they effectively encapsulate the central tension of sequential learning: the trade-off between exploration and exploitation 15 . The agent must continuously decide whether to adhere to the option currently believed to be the best (exploitation) or to sacrifice immediate returns to gather data on less-tested options (exploration). While the problem formulation is simple, the optimal resolution of this tension is mathematically profound and often computationally intractable. Despite the intuitive appeal of the exploration-exploitation trade-off, the question of how to make this notion operational still stands. We know that balancing information acquisition and regret (the shortfall with respect to the best choice in hindsight) is key, but the precise, optimal weighting function for general settings is not known in general. Information Directed Sampling (IDS) policies represent a class of heuristic algorithms that make this trade-off explicit 12 ; 13 ; 8 ; 3 . IDS strategies are defined by an optimization objective that balances immediate regret against information gain. At each step of the task, the policy evaluates the “cost” of exploration in terms of forgone reward against the “value” of the resulting reduction in uncertainty. Comparing the performance of interpretable IDS strategies against a theoretically optimal policy can offer significant insight into the nature of efficient learning. Unfortunately, in general bandit problems – despite their deceptive simplicity – rarely allow for closed-form solutions. The calculation of Gittins indices 2 or the solution of the Bellman equation for continuous belief spaces 4 is often feasible only through approximation. Consequently, we must look to the simplest non-trivial cases. To this end, we treat the two-state Bernoulli armed bandit problem as the ”hydrogen atom” of decision-making under uncertainty. Just as the hydrogen atom provides a tractable quantum mechanical system that guides our understanding of the physics of more complex elements, the two-state Bernoulli bandit is simple enough to allow for the computation of the optimal strategy, yet complex enough to exhibit the non-trivial dynamics of belief updates and information value. The primary goal of this work is to study a specific sub-class of IDS strategies and compare them directly to the optimal policy within this controlled setting. By restricting our analysis to a problem simple enough to solve, we can rigorously quantify how closely the explicit information-regret ratios of IDS approximate the optimal decision path. This comparison allows us to probe the efficacy of Information Directed Sampling, validating its design principles while highlighting the gaps between heuristic efficiency and theoretical optimality. This is a largely a pedagogical article. It would be a daunting task to even provide a cursory overview of the work done in this field. The reader interested in delving deeper in the algorithmic approaches to bandit problems should definitely read the comprehensive and beautiful book by Lattimore and Szepesvari 7 . Many of the theoretical concepts discussed herein have been introduced in prior literature. Our aim is to synthesize and scrutinize them in a language that can be accessible to statistical physicists who are interested in problems that involve decision-making, stochastic control and information theory. II Partially Observable Markov Decision Processes with two states In this section, we introduce the general framework of a partially observable Markov decision process, where an agent takes actions in an unknown environment and receives partial observations in response. We focus on the simple scenario where the environment can be described by two discrete states, which has important applications in the class of problems known as “bandit problems”. Figure 1: (a-b) Classes of two-armed Bernoulli bandit problems. The outer square contains all two-armed bandit problems where the reward distributions are Bernoulli. The outer circle contains all the two-state problems, which in general are described by four different parameters. The inner circle contains the problems parametrized by \theta_{+},\theta_{-} – table 1 of panel (b). The special symmetric and one fair coin cases are shown in the (\theta_{+},\theta_{-})- space and in tables 2 and 3 of panel (b), respectively. (c) Schematic sketch of a belief update for our two-state problem, where the belief is defined on a one-dimensional space, and of the evolution of a POMDP in time, showing the belief b , state s , observations y , and actions a for two steps of the process. II.1 Two-armed Bernoulli Bandits Consider the problem of a gambling agent who has to choose between two biased coins and wants to maximize their total gain. Each coin has a fixed but a priori unknown probability of landing on the “winning” face, which yields a reward. The gambler faces the following dilemma. On one hand, it should gather information about both coins so as to identify the best one with reasonable certainty and then be able to act optimally. On the other hand, they want to avoid accumulating too much loss during this exploration. This decision process is part of a larger class of problems where an agent repeatedly chooses between two actions and collects rewards, which can be thought of as either “win” or “lose”, and they are described by a random variable that follows a Bernoulli distribution for each action. The rewards effectively represent the observations that the agent receives from an unknown environment – i.e., the agent does not have access to the pair of Bernoulli parameters of the coins. In other words, the agent cannot directly observe the state variable that specifies the environment, and this partial observability