Beyond the Independent Arm Assumption in Bandit Learning

520 concepts301 papers2 proposals

In the classic multi-armed bandit framework, every choice is an island. If you pull an arm and receive a reward, that observation tells you everything about that specific arm, but absolutely nothing about any other option. This is known as the independent arm assumption.

While mathematically convenient, this assumption creates a massive bottleneck in real-world applications. If a recommendation engine treats thousands of products as completely independent, it must test every single product individually to learn its value. In complex, high-dimensional spaces, this brute-force exploration is catastrophically slow.

To build faster, more practical decision-making systems, a major thread of research focuses on breaking this assumption. By modeling the underlying correlations between arms, algorithms can achieve information spillover: a single action can simultaneously reduce uncertainty across a wide array of unselected alternatives.

The Geometry of Shared Information

The most direct way arms share information is through a shared parameter space. In linear stochastic bandits, the reward of each arm is not an isolated distribution, but the inner product of that arm's known features and a hidden, global parameter vector.

As noted by Kong et al., this structural coupling means that an observation from one action fundamentally alters our belief about the global parameter, and consequently, about all other actions. This geometric correlation changes the fundamental nature of the problem. For instance, Wang et al. demonstrated that this geometric link makes linear bandits intrinsically resilient against adversarial reward-poisoning attacks. An attacker cannot maliciously manipulate the perceived reward of a single target arm without distorting the rewards of geometrically correlated arms, making the manipulation mathematically transparent to the learner.

To quantify how efficiently an agent can navigate these dependent spaces, Russo et al. introduced the eluder dimension. This metric characterizes the sample complexity of structured action spaces by measuring how many sequential actions can be chosen such that their rewards remain uninformative about one another. When the eluder dimension is small, information generalizes rapidly across the action space, allowing both Upper Confidence Bound (UCB) and Thompson Sampling algorithms to find optimal policies without exhaustive search.

Graph Feedback and Neighborhood Spillover

In many modern applications, such as viral marketing or social network recommendations, the relationships between options are explicitly mapped as a network. This structure can be leveraged using graph feedback, where choosing one option reveals direct or indirect information about its neighbors.

Caron et al. formalized this by allowing an agent to receive "side observations" from adjacent nodes in a feedback graph. Instead of a single data point, one pull updates an entire neighborhood. The efficiency of this approach depends heavily on the topology of the network. Tossou et al. proved that when utilizing Thompson Sampling in graphical bandits, the regret scales not with the total number of arms, but with the graph's clique cover number—effectively treating tightly knit clusters of arms as a single informational unit.

Even when explicit side observations are missing, we can exploit the assumption that the reward function changes smoothly across the graph. Valko et al. introduced spectral bandits, which utilize the graph Laplacian to model smooth reward functions. By analyzing the graph's spectral properties, the authors showed that exploration can be restricted to a low-dimensional subspace. The algorithm's performance scales with a small effective dimension rather than the total number of nodes, enabling accurate recommendations across thousands of items after only a handful of interactions.

Combinatorial Interdependence and Kernelized Similarities

The independent arm assumption becomes particularly problematic in Combinatorial Multi-Armed Bandits (CMAB), where an agent selects a subset of base arms simultaneously (e.g., choosing a portfolio of assets or a set of routing paths).

Traditional combinatorial frameworks often assume that the outcomes of individual base arms are independent. However, as argued by Chen et al., real-world environments like financial markets or communication networks feature highly correlated base actions. Ignoring these dependencies causes standard algorithms to miscalculate the joint distribution of the subset, leading to poor risk management and suboptimal choices. For example, in financial portfolios, assets exhibit strong co-movements; Wang et al. addressed this by using Principal Component Analysis (PCA) to decouple correlated assets into independent, orthogonal portfolios, allowing standard bandit exploration to function safely.

Alternatively, rather than trying to decouple correlations, learners can actively model them using non-parametric methods like Gaussian Processes (GPs). Accabi et al. integrated GPs into combinatorial bandits to capture complex, non-linear relationships between arm payoffs. By utilizing kernel-based similarity measures, as further developed by Nika, the system can update its beliefs about multiple related actions simultaneously. When the outcomes of different items are linked, leveraging these dependencies allows the system to compress massive combinatorial action spaces into a few highly correlated groups, drastically accelerating convergence.

Why It Works: The Intuition of Variance Reduction

Ultimately, moving beyond the independent arm assumption works because it changes how the algorithm manages uncertainty. In an independent bandit, the variance (or uncertainty) of an unplayed arm remains constant until it is explicitly pulled.

In a structured or correlated bandit, every observation acts as a projection onto a shared underlying space. When you sample an arm, you don't just update a single scalar mean; you update a shared parameter vector, a graph spectrum, or a Gaussian Process covariance matrix. This update shrinks the confidence intervals of all correlated arms simultaneously. By actively exploiting these relationships, the learner can mathematically rule out large sub-optimal regions of the action space without ever having to play them.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 330 papers
  2. Version 1 · 2026-10-04 · 405 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_independent_arm_assumption_b9c48b80,
  title = {independent arm assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/independent-arm-assumption/rdr_b9c48b800f434b1dae9b3a6ab655e3b0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_independent_arm_assumption_b9c48b80_v2,
  title = {independent arm assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/independent-arm-assumption/rdr_b9c48b800f434b1dae9b3a6ab655e3b0/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake