Contextual Bandits via Regression Oracles

This direction is merged into another direction: Bellman completeness. Its last version stays readable and citable here.

Version 1 of 120 papers21 conceptsfrozen 2026-10-04

In the theoretical world of contextual bandits, we often assume realizability: the idea that the true relationship between a context and a reward is perfectly captured by our chosen model class. If you use a linear model, you assume the world is linear. If you use a neural network, you assume the "ground truth" function lives somewhere in that network's weight space.

In practice, this assumption is almost always false. Real-world rewards are messy, and models are merely approximations. When this gap—known as model misspecification—appears, traditional bandit algorithms often collapse, failing to converge or providing suboptimal recommendations.

A growing body of research addresses this by shifting the focus from bespoke bandit strategies to regression oracles. By reducing the bandit problem to a series of standard regression tasks, researchers have developed frameworks that are both computationally efficient and robust to the realities of imperfect modeling.

The Power of Reduction

The core intuition behind this research direction is a "reduction." Instead of inventing a new exploration strategy for every possible model type (like Gradient Boosted Trees or Deep Learning), we treat the underlying machine learning model as a "black box" regression oracle.

In Practical Contextual Bandits with Regression Oracles, Dylan J Foster, Alekh Agarwal, and Miroslav Dudík introduced RegCB. This algorithm bridges the gap between flexible, agnostic methods and efficient, model-based approaches. By reducing the bandit's decision-making process to a sequence of standard least-squares regression problems, RegCB allows practitioners to use complex, non-linear models while maintaining strong theoretical guarantees on performance (regret).

Surviving Model Misspecification

If the "true" reward function lies outside your model's hypothesis class, a standard algorithm might become overconfident in a wrong prediction. To solve this, researchers have focused on making these reductions "misspecification-robust."

Sanath Kumar Krishnamurthy, Susan Athey, and Vitor Hadad developed Epsilon-FALCON in Tractable contextual bandits beyond realizability. Their approach provides regret guarantees that "scale gracefully" with the degree of misspecification. If the model is slightly wrong, the performance degrades slightly, rather than failing entirely.

Later, in Adapting to misspecification in contextual bandits with offline regression oracles, the same authors introduced Safe-FALCON. This algorithm acts as a fail-safe: it detects when model errors are causing performance to dip and can automatically revert to a "safe" historical policy, ensuring the learner doesn't perform worse than a known baseline even when the model is fundamentally flawed.

Square Loss and Policy Space Optimism

A recurring mechanism in these papers is the use of square-loss regression as the primary engine for exploration. By minimizing the square error between predicted and observed rewards, algorithms can estimate the uncertainty of their predictions.

Generalizing the Framework

The "regression oracle" philosophy is now being applied to increasingly complex bandit variants:

  1. Dueling Bandits: Aadirupa Saha and Robert E. Schapire have applied these reductions to preference-based learning. In Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability, they use square-loss regression to solve a long-standing problem of how to make dueling bandits computationally efficient.
  2. Resource Constraints: In Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oracles, Yuxuan Han and colleagues introduced SquareCBwK, which handles "knapsack" constraints (like limited budget or time) by reducing both reward and cost estimation to online regression.
  3. Submodular Rewards: Alexander Rakhlin and Dean P. Foster explored how these oracles can handle Submodular Contextual Bandits, where the goal is to select a subset of items with diminishing returns.

By decoupling the exploration logic from the function approximation, this research direction provides a universal toolkit. It allows the field to move away from "toy" linear models and toward robust, real-world systems that can leverage any regression model while remaining resilient to the inevitable gaps between our models and reality.

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_contextual_bandits_via_regression_oracle_0a74d357,
  title = {Contextual Bandits via Regression Oracles},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/contextual-bandits-via-regression-oracles/rdr_0a74d357cbed4d4696f235b9a3bedfab},
  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_contextual_bandits_via_regression_oracle_0a74d357_v1,
  title = {Contextual Bandits via Regression Oracles},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/contextual-bandits-via-regression-oracles/rdr_0a74d357cbed4d4696f235b9a3bedfab/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}