Information Directed Sampling for Sequential Decision Making

142 concepts84 papers1 proposal

In sequential decision-making, agents face a fundamental dilemma: should they exploit the action that currently looks best, or explore an uncertain action to learn more? Traditional approaches like Upper Confidence Bound (UCB) and Thompson Sampling rely on heuristics like optimism under uncertainty or probability matching. While effective in simple environments, these methods can fail or scale poorly when the environment possesses complex structural dependencies, hidden feedback loops, or unevenly distributed noise.

The core insight of Information-Directed Sampling (IDS), introduced by Russo et al., is to treat exploration as an explicit economic transaction. Instead of exploring blindly to reduce general uncertainty, an agent evaluates actions based on their "cost-per-bit" of information regarding the optimal action.

The Core Mechanism: The Information Ratio

To formalize this cost-per-bit trade-off, IDS minimizes a metric known as the information ratio. For a given action (or a probability distribution over actions), the information ratio $\Psi$ is defined as:

$$\Psi = \frac{\Delta^2}{g}$$

where $\Delta$ is the expected immediate regret of taking that action, and $g$ is the expected information gain (typically measured as mutual information) about the identity or properties of the optimal action.

Why squared regret? As shown by Russo et al. and further analyzed by Shufaro et al. using information-theoretic tools like Fano's Inequality, squaring the regret aligns its scale with mutual information. This establishes a direct mathematical exchange rate between performance loss and uncertainty reduction.

By minimizing this ratio, the agent ensures a highly targeted exploration strategy:

  • An action with high immediate regret ($\Delta$) is only selected if it provides a massive amount of information ($g$) that significantly narrows down the search for the optimal policy.
  • If an action is highly uncertain but reveals nothing about which choice is truly best, its information gain $g$ is low, and the ratio penalizes it.

Adapting to Complex Geometries and Feedback Structures

A major advantage of the information ratio framework is its ability to automatically adapt to the underlying geometry of a problem without manual tuning.

Heteroscedastic Noise

In many real-world settings, some choices yield far noisier observations than others. Kirschner et al. demonstrated that frequentist formulations of IDS naturally steer agents toward less noisy, more informative actions, preventing them from being misled by high-variance distractions that offer little structural insight.

Graph Feedback and Side Observations

When taking one action provides "free" side observations about other related actions, standard algorithms struggle to exploit this extra data efficiently. Liu et al. showed that IDS naturally leverages graph feedback to minimize regret. By evaluating the collective information gain across the graph, the agent strategically selects actions that act as informational hubs. Furthermore, Degenne et al. demonstrated that actively choosing which actions to observe for free can transition a system from standard logarithmic regret to uniformly bounded regret, meaning total expected loss eventually stops growing entirely.

Partial Monitoring and Dueling Feedback

In settings where absolute rewards are hidden and only relative or partial feedback is available, the information ratio provides a unified lens. Kirschner et al. applied IDS to linear partial monitoring, proving it achieves optimal minimax regret across different observability regimes by automatically adapting to the problem's geometry. For scenarios combining absolute scores and pairwise comparisons, Wang et al. partitioned actions based on which feedback channel offered the highest information gain at the lowest cost.

Contextual and High-Dimensional Scaling

As we move to contextual bandits and reinforcement learning, myopic exploration becomes a major pitfall. An action might be highly informative for the current context but useless for future ones. To resolve this, Hao et al. introduced the marginal information ratio, which minimizes the ratio between expected regret and information gain by taking an expectation over the entire context distribution. This prevents myopic choices by accounting for the probability of future context arrivals.

In high-dimensional sparse settings—where thousands of features exist but only a handful drive the outcome—Hao et al. showed that minimizing the information ratio naturally guides the agent to perform targeted feature elimination. This concept is extended to frequentist settings by the authors of Sparse Optimistic Information Directed Sampling, who utilize an optimistic posterior and a time-dependent learning rate to achieve optimal worst-case regret bounds in both data-rich and data-poor regimes simultaneously.

Overcoming Computational Bottlenecks: From Ratios to Regularization

While minimizing a ratio is elegant in theory, it presents severe computational challenges in multi-state environments like Markov Decision Processes (MDPs). Fractional action allocations cannot be easily solved via standard dynamic programming bellman equations.

To make information-directed exploration computationally tractable, Hao et al. proposed transforming the fractional ratio objective into an additive regularized objective:

$$\min \left( \text{Expected Regret} - \lambda \cdot \text{Information Gain} \right)$$

This additive formulation allows the exploration objective to be integrated directly into standard dynamic programming solvers like value iteration. A similar regularization approach was extended to multi-agent reinforcement learning by Zhang et al., enabling order-optimal Bayesian regret bounds in complex Markov games while bypassing the need to solve complex ratio-based optimization problems at every step.

Deciding What to Learn via Rate-Distortion Theory

In massive or infinitely complex environments, learning everything perfectly is impossible. How does an agent decide what is actually worth learning?

Arumugam et al. bridged IDS with rate-distortion theory to introduce "satisficing" targets. Instead of calculating the information ratio relative to the absolute optimal action, the agent can optimize information gain relative to a sub-optimal but significantly easier-to-learn target policy. This allows the agent to trade off absolute optimality for rapid learnability, focusing its information-gathering resources only on the details that matter for practical success.

Key Foundational Work

An Information-Theoretic Analysis of Thompson Sampling (2014) — contributed 2 concept elements to this direction.
Learning to Optimize via Information-Directed Sampling (2014) — contributed 2 concept elements to this direction.
Learning to optimize via information-directed sampling (2014) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_information_directed_sampling_f351443b,
  title = {information-directed sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/information-directed-sampling/rdr_f351443b096943108e454b0231d6fb3b},
  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_sampling_f351443b_v1,
  title = {information-directed sampling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/information-directed-sampling/rdr_f351443b096943108e454b0231d6fb3b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake