Non-Myopic Exploration in Contextual Bandits

This direction is merged into another direction: myopic acquisition functions. Its last version stays readable and citable here.

Version 1 of 15 papers21 conceptsfrozen 2026-10-04

In a standard contextual bandit problem, an agent receives a "hint" (the context), chooses an action, and receives a reward. Most classic algorithms, like Upper Confidence Bound (UCB) or Thompson Sampling, approach this problem myopically: they ask, "Given the context I see right now, which action helps me maximize my immediate reward or learn the most about this specific situation?"

However, a growing body of research suggests that this local focus is inefficient. By considering the global structure of the problem—how information gained in one context helps in others—agents can explore far more strategically.

The Value of Waiting for Clarity

The intuition for non-myopic exploration begins with the realization that not all contexts are equally useful for learning. In their foundational work, Chih-Chun Wang, Sanjeev Kulkarni, and H. Vincent Poor demonstrated that "side information" (context) changes the fundamental limits of regret.

Imagine you are trying to determine which of two medications is more effective, but their effects are very similar in most patients. If you test them on a random patient, the "noise" of their biology might drown out the signal of which drug is better. However, if you know that the drugs behave very differently in patients with a specific rare genetic marker, it is strategically optimal to "postpone" intense exploration until you encounter a patient with that marker.

Wang et al. showed that by concentrating exploration on these "high-information" states—where reward distributions are most distinct—an agent can distinguish between competing hypotheses much faster, significantly reducing the cumulative regret.

From Local Actions to Global Policies

While early work focused on timing, recent advancements shift the focus toward what we are trying to learn. Traditional strategies try to find the best action for the current context. In contrast, Botao Hao, Tor Lattimore, and Chao Qin propose Contextual Information-Directed Sampling (Contextual IDS).

The core shift in Contextual IDS is the pursuit of a global optimal policy rather than a point-wise optimal action. Instead of asking "What do I need to know now?", the agent asks:

  1. What is the distribution of contexts I am likely to see in the future?
  2. Which action, if taken now, provides the most information about the best possible mapping of actions to all those future contexts?

This approach resolves a major pitfall of myopic exploration: the "information spillover" problem. In many real-world settings, rewards are governed by an underlying structure (like a linear model or a graph). An action taken in Context A might yield zero reward and zero information about Context A, but it might perfectly reveal the reward structure for Context B, which appears 90% of the time. A myopic agent would never pick that action; a global agent would.

Why Global Exploration Works

The effectiveness of this direction stems from two main mechanisms:

  1. Information Efficiency: By accounting for the distribution of future contexts, the agent prioritizes resolving uncertainty for the most frequent or critical states. It treats exploration as a budget to be spent where the "return on information" is highest for the entire lifetime of the agent.
  2. Structural Leveraging: In complex settings like sparse linear bandits or graph feedback, the relationship between actions and rewards is interconnected. Hao, Lattimore, and Qin demonstrate that by optimizing the full policy mapping, the agent can identify "bridge" actions that resolve global uncertainty, even if those actions look sub-optimal when viewed through the lens of the current context alone.

By moving from "What is best now?" to "What helps me learn the most about the future?", this research direction transforms contextual bandits from a series of isolated decisions into a cohesive, strategic search for the optimal behavior.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_non_myopic_exploration_in_contextual_ban_ee5655b1,
  title = {Non-Myopic Exploration in Contextual Bandits},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-myopic-exploration-in-contextual-bandits/rdr_ee5655b1cec341e4ab3379b8eb15c74b},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_non_myopic_exploration_in_contextual_ban_ee5655b1_v1,
  title = {Non-Myopic Exploration in Contextual Bandits},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-myopic-exploration-in-contextual-bandits/rdr_ee5655b1cec341e4ab3379b8eb15c74b/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}