Information Directed Exploration for Stochastic Bandits

This direction is split into other directions: informative suboptimal actions, information-directed sampling. Its last version stays readable and citable here.

Version 1 of 1188 papers300 conceptsfrozen 2026-10-04

In sequential decision-making, the "exploration-exploitation trade-off" is usually described as a tug-of-war: do you pull the arm you think is best (exploitation), or do you pull a random arm to learn more (exploration)? Traditional algorithms like Upper Confidence Bounds (UCB) and Thompson Sampling (TS) navigate this by being "optimistic"—they treat uncertainty as potential reward.

However, as Benjamin Van Roy and Daniel Russo argue in A Tutorial on Thompson Sampling, these methods can be "information-blind." They prioritize actions that might be the best, but they ignore actions that could provide crucial information about the environment at a low cost.

Information Directed Sampling (IDS) reframes exploration not as a gamble, but as a purchase. Every action has a price (expected regret) and a value (information gain). IDS simply looks for the best "price per bit."

The Information Ratio

The core mechanism of this research direction is the Information Ratio. Introduced to unify various bandit problems, the ratio $\Psi_t$ quantifies the efficiency of an action:

$$\Psi_t = \frac{(\text{Expected Regret})^2}{\text{Expected Information Gain}}$$

By minimizing this ratio, an agent selects actions that either have very low immediate regret (exploitation) or provide massive amounts of information about which action is truly optimal (exploration).

As Johannes Kirschner and Andreas Krause demonstrate in Information Directed Sampling and Bandits with Heteroscedastic Noise, this approach is particularly powerful when noise is not uniform. If one action is very noisy and another is clean, IDS naturally gravitates toward the cleaner signal to learn faster, whereas "information-blind" algorithms might waste time in the noise.

Why Squaring Regret Matters

A recurring theme across these papers is the mathematical necessity of the squared term in the numerator. In Information Directed Sampling for Linear Partial Monitoring, Johannes Kirschner and Tor Lattimore explain that this ensures the agent achieves optimal minimax regret rates.

In "easy" games, this mechanism leads to the standard $\sqrt{T}$ regret. In "hard" games—specifically Partial Monitoring, where you might never see the actual reward but only a related signal—it automatically adapts to achieve $T^{2/3}$ regret. This adaptation happens without manual tuning because the ratio captures the underlying geometry of the information-reward space.

Beyond Simple Rewards: Graphs and Contexts

The power of the IDS framework is its ability to incorporate complex feedback structures:

The Price of Alignment

Perhaps the most modern application of this idea is in AI Alignment. In Aligning AI Agents via Information-Directed Sampling, Benjamin Van Roy models the challenge of an agent that doesn't know what a human wants.

Querying a human for feedback is "expensive" (it incurs regret because the agent isn't acting autonomously). An information-blind agent might never ask for help because asking isn't "optimally rewarding" in the short term. IDS, however, recognizes that a single expensive query might provide enough "bits" of information about human preferences to drastically reduce regret for all future steps.

Learning to be "Good Enough"

In high-dimensional problems, searching for the absolute best action can be counterproductive. Daniel Russo explored this in Satisficing in Time-Sensitive Bandit Learning, proposing that agents should minimize information gain relative to a "satisficing" target rather than an optimal one.

This was further formalized by Dilip Arumugam and Benjamin Van Roy in Deciding What to Learn: A Rate-Distortion Approach. By treating learning as a communication problem with a limited "bit rate," they show that agents can converge faster by strategically deciding which parts of the environment are worth learning and which are irrelevant to the task at hand.

Papers in this version

Showing 60 of 188 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_information_directed_exploration_for_sto_aa0a773e,
  title = {Information Directed Exploration for Stochastic Bandits},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/information-directed-exploration-for-stochastic-bandits/rdr_aa0a773e5649402eac2ceee03194bb30},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_information_directed_exploration_for_sto_aa0a773e_v1,
  title = {Information Directed Exploration for Stochastic Bandits},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/information-directed-exploration-for-stochastic-bandits/rdr_aa0a773e5649402eac2ceee03194bb30/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}