The Informational Value of Suboptimal Actions

19 concepts13 papers1 proposal

In sequential decision-making, the standard recipe for balancing exploration and exploitation relies on a celebrated principle: Optimism in the Face of Uncertainty. Algorithms like Upper Confidence Bound (UCB) and Thompson Sampling (TS) operate by tracking the potential of each action. If an action's true value is highly uncertain, the algorithm optimistically overestimates its reward, forcing the agent to try it.

This strategy works beautifully when actions are independent. However, a growing body of research reveals that when the environment possesses underlying structure—such as linear correlations, side observations, or task constraints—optimism breaks down. In these settings, standard algorithms can be asymptotically sub-optimal because they stop playing suboptimal actions too quickly.

The core insight of this research direction is a paradox: to find the optimal action as efficiently as possible, an agent must frequently and intentionally choose actions that it knows are suboptimal.

To understand why optimism fails, we must look at how information is distributed across a structured environment. In a standard multi-armed bandit, pulling Arm A tells you absolutely nothing about Arm B. In structured environments, however, actions are mathematically linked.

Consider a linear bandit where each action is a vector, and the reward is the inner product of that vector and an unknown parameter $\theta^*$. Here, pulling a single arm yields information about $\theta^*$, which in turn updates our knowledge about every single arm in the system.

As Tor Lattimore et al. demonstrated, this structure creates a fundamental flaw in optimistic exploration. An optimistic algorithm only selects an arm if its upper confidence bound is higher than the current best estimate. If an arm is quickly revealed to have a low immediate reward, its upper bound drops, and an optimistic agent will abandon it forever.

But what if that low-reward arm happens to be pointing in a geometric direction that perfectly isolates and identifies $\theta^*$? By abandoning it, the agent deprives itself of cheap, high-fidelity information. As a result, the agent is forced to learn about $\theta^*$ through highly repetitive, expensive pulls of near-optimal arms, leading to long-term regret that can be arbitrarily worse than the theoretical limit.

Optimistic Strategy (UCB / Thompson Sampling):
[Action Selection] ---> Tied to Reward Potential ---> Ignores Low-Reward, High-Information Arms

Information-Directed Strategy:
[Action Selection] ---> Evaluates Information Gain per Unit of Regret ---> Leverages Suboptimal Arms

This failure mode is not unique to frequentist optimism. In their comprehensive tutorial, Daniel Russo et al. note that Thompson Sampling suffers from the exact same limitation. Because posterior sampling ties an action's selection probability directly to its probability of being the optimal choice, it fundamentally under-explores actions that offer massive epistemic value but have zero chance of being the highest-reward option.

Decoupling Reward from Information

To resolve this suboptimality, we must entirely decouple an action's informational value from its immediate reward value. This necessity manifests clearly across several distinct problem structures:

1. Feedback Graphs and Side Observations

In many practical settings, choosing an action provides "side observations" about neighboring actions. For example, testing a drug on one patient profile might reveal data about its efficacy on a related profile.

Alexia Atsidakou et al. and Alessio Russo et al. show that in systems governed by these feedback graphs, the most efficient path to identifying the best overall option often requires pulling an arm with a terrible immediate reward. If that low-reward arm acts as a central "hub" in the feedback graph, pulling it provides high-quality data about a vast number of competitive alternatives simultaneously, accelerating global convergence.

2. Distinguishing Near-Identical Alternatives

Imagine a scenario where the true optimal action and a runner-up action are nearly identical in reward, making them incredibly difficult to tell apart. Johannes Kirschner et al. highlight that in such configurations, the fastest way to break the tie is often to play a highly suboptimal action that is structurally sensitive to the subtle differences between the two leaders. Optimistic algorithms completely miss this opportunity because they refuse to look at arms that are clearly losing the race.

3. Contextual and Global Parameter Mapping

In contextual environments, the optimal action changes depending on the situation. To perform well over time, an agent must map out the global parameter space. Andrea Tirinzoni et al. and Alessandro Lazaric et al. demonstrate that allocating exploration explicitly to suboptimal arms allows an agent to narrow down the set of possible reward models much faster than standard methods like LinUCB. Similarly, Chao Du et al. show that prioritizing actions that maximize information gain or reduce posterior variance between competing candidate sets allows contextual bandits to identify optimal subsets with significantly fewer samples.

Quantifying the Information-Regret Trade-off

If standard optimism fails because it ignores informative suboptimal actions, how do we design algorithms that correctly value them?

The answer lies in explicitly optimizing the trade-off between the cost of an action (its immediate regret) and the benefit of an action (the information it provides about the global optimum). This is often operationalized through frameworks like Information-Directed Sampling (IDS) or custom primal-dual linear programs.

Instead of asking "Could this action be the best?", an information-directed algorithm asks: $$\text{Selection Metric} = \frac{\text{Information Gained by Playing Action } a}{\text{Expected Regret Incurred by Playing Action } a}$$

By framing exploration this way, the algorithm treats the exploration phase not as random noise or a necessary evil, but as a structured data-gathering process. This perspective is validated by Kumar Krishna Agrawal et al., who proved that the exploration phase of a learning agent contains highly structured, valuable data that allows observers to reverse-engineer true rewards far better than watching a perfect expert.

Pure Exploration vs. Regret Minimization

The value of suboptimal actions becomes even more pronounced when we shift from minimizing regret during learning to pure exploration (such as Best Arm Identification).

In pure exploration, the agent does not pay a penalty for pulling bad arms during the training phase; it only cares about outputting the correct optimal arm at the end. Andrew J. Wagenmaker et al. demonstrate this in linear dynamical systems, showing that task-optimal exploration requires visiting high-cost, suboptimal states that contain critical information about system boundaries.

However, even when the goal is to minimize regret over time, the long-term mathematical benefits of rapid uncertainty reduction outweigh the short-term cost of playing a suboptimal arm. As Mirco Mutti et al. point out, when the actions providing the most information are different from those yielding the highest immediate rewards, greedy or purely optimistic behavior causes the agent to fail to identify the underlying task structure entirely.

Ultimately, this research direction forces a paradigm shift in how we think about machine learning exploration. True efficiency requires moving past simple optimism and embracing the fact that sometimes, the fastest way to learn how to succeed is to strategically choose to fail.

Key Foundational Work

The End of Optimism? An Asymptotic Analysis of Finite-Armed Linear Bandits (2017) — contributed 5 concept elements to this direction.
A Tutorial on Thompson Sampling (2018) — 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_informative_suboptimal_actions_4d8db029,
  title = {informative suboptimal actions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/informative-suboptimal-actions/rdr_4d8db02986994284bb32fd290290c039},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_informative_suboptimal_actions_4d8db029_v1,
  title = {informative suboptimal actions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/informative-suboptimal-actions/rdr_4d8db02986994284bb32fd290290c039/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake