Information-directed sampling for bandits: a primer
This work provides a pedagogical synthesis for statistical physicists, bridging reinforcement learning and information theory, but it is incremental as it extends IDS to a discounted infinite-horizon setting with minimal models.
The paper tackles the Multi-Armed Bandit problem by exploring Information Directed Sampling (IDS) policies to balance exploration and exploitation, showing that in symmetric bandits, IDS achieves bounded cumulative regret, and in a one-fair-coin scenario, regret scales logarithmically with the horizon.
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.