Overcoming Parametric Assumptions in Multi Armed Bandits

40 concepts35 papers1 proposal

Multi-armed bandit algorithms are built on a simple promise: by balancing exploration and exploitation, an agent can maximize its cumulative reward in an unknown environment. However, to achieve the theoretical gold standard of performance, classic algorithms rely on a crucial piece of hidden assistance: they assume they know the mathematical shape, scale, or boundaries of the rewards beforehand.

In the real world, this reliance creates a profound vulnerability. If an environment's rewards deviate even slightly from these rigid assumptions, traditional algorithms can fail catastrophically. To build truly autonomous systems, researchers are shifting toward non-parametric, parameter-free, and distribution-oblivious bandit frameworks.

The Hidden Fragility of Bounded Confidence

To understand why parametric assumptions are problematic, consider how a standard Upper Confidence Bound (UCB) algorithm works. To decide whether to pull an arm, the algorithm calculates an optimistic estimate of that arm's value:

$$\text{UCB}(a) = \hat{\mu}_a + c \cdot \sqrt{\frac{\log t}{N_a}}$$

The exploration bonus—the second term—depends entirely on a scale parameter $c$. This parameter represents a strict assumption about the reward distribution, such as a known upper bound or a specific variance. As Lattimore points out in A Scale Free Algorithm for Stochastic Bandits with Bounded Kurtosis, if this scale is unknown or incorrectly specified, the algorithm cannot properly balance exploration and exploitation. If $c$ is chosen too small, the agent under-explores and misses the optimal choice; if it is too large, the agent wastes samples on sub-optimal actions.

This reliance creates what can be called statistical fragility. Ashutosh et al. demonstrate in Bandit algorithms: Letting go of logarithmic regret for statistical robustness that any algorithm designed to achieve optimal logarithmic regret under strict parametric assumptions is inherently fragile. If the underlying distribution parameters are even slightly misestimated, the algorithm's efficiency guarantees completely vanish, leading to significantly higher regret than expected.

The Catch-22 of Instance Complexity

The problem runs deeper than just guessing the variance or scale of the rewards. Many optimal bandit frameworks require prior knowledge of the environment's instance complexity to function.

For example, to guarantee the exact identification of the best arm or to minimize regret under constraints, algorithms often require the user to input the "sub-optimality gap" ($\Delta$)—the exact difference in expected reward between the best arm and the second-best arm. This requirement introduces a logical paradox: finding the best arm is the entire purpose of running the algorithm, yet the algorithm needs to know how hard it is to distinguish the best arm from the others before it even begins.

As noted by Liu et al. in Combinatorial Bandits with Linear Constraints: Beyond Knapsacks and Fairness and Shi et al. in Efficient Pure Exploration in Adaptive Round model, this dependency severely limits practical deployment. If an algorithm requires prior knowledge of the reward gap to trigger state-revisiting mechanisms—as seen in the reinforcement learning models analyzed by Li et al. in Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting—it cannot operate autonomously in dynamic settings where these gaps are entirely unknown.

Similarly, the authors of An optimal algorithm for the Thresholding Bandit Problem highlight that traditional pure-exploration methods require the total sampling budget or instance complexity in advance to tune their elimination strategies, creating a barrier for real-world optimization problems.

When Real-World Data Breaks the Model

In practice, rewards rarely conform to neat, single-parameter exponential families like Gaussian or Bernoulli distributions. Real-world data is messy, often exhibiting heavy tails, multi-modal structures, or adversarial contamination.

When an algorithm forces a simple parametric model onto complex data, it suffers from severe model misspecification:

Data-Driven and Parameter-Free Solutions

To bypass these limitations, recent research focuses on designing algorithms that adapt organically to the observed data without requiring manual tuning or structural assumptions.

Non-Parametric Resampling

Instead of drawing exploration bonuses from a theoretical distribution tail, algorithms can use the empirical history of past rewards. Baudry et al. introduce this intuition via Dirichlet Sampling in From Optimality to Robustness: Adaptive Re-Sampling Strategies in Stochastic Bandits, using weights derived directly from observed data to maintain robustness across complex distributions.

To achieve asymptotic efficiency without knowing the underlying mathematical family, Baudry et al. propose a random-block sub-sampling strategy in Sub-sampling for Efficient Non-Parametric Bandit Exploration. By conducting pairwise duels between arms using subsets of history, the algorithm matches the theoretical limits of specialized parametric models while naturally accommodating unbounded rewards.

Robust, Scale-Free Estimation

Instead of relying on standard empirical means—which are highly sensitive to heavy tails—modern algorithms leverage robust statistics that do not require prior moment bounds. In Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits, Tamás et al. utilize a resampled median-of-means estimator to achieve near-optimal regret in heavy-tailed settings without needing prior knowledge of the distribution's tail parameters.

Alternatively, Cassel et al. demonstrate in Batch Ensemble for Variance Dependent Regret in Stochastic Bandits that taking the minimum of empirical means from non-overlapping batches creates an optimistic estimator. This simple architectural tweak allows the algorithm to adapt automatically to the underlying distribution's concentration properties without pre-defined variance parameters.

Structural and Horizon Adaptation

The push toward parameter-free learning also extends to complex structural settings. For instance, Russo demonstrates in Learning to Stop with Surprisingly Few Samples that for discounted optimal stopping problems, sample complexity can scale logarithmically with the effective horizon even in non-parametric settings.

By moving away from rigid parametric constraints, these diverse approaches allow online decision-making systems to handle the structural complexities of the real world—from infinite-armed spaces (Chaudhuri et al. in Quantile-Regret Minimisation in Infinitely Many-Armed Bandits) to non-stationary, shifting environments (Suk et al. in Tracking Most Significant Shifts in Nonparametric Contextual Bandits)—without requiring the designer to guess the underlying physics of the environment beforehand.

Key Foundational Work

An Asymptotically Optimal Algorithm for the Max k-Armed Bandit Problem (2006) — contributed 1 concept elements to this direction.
Bayesian Mixture Modelling and Inference based Thompson Sampling in Monte-Carlo Tree Search (2013) — 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_parametric_distribution_constraints_prio_5d80c4cb,
  title = {parametric distribution constraints (prior knowledge requirement)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parametric-distribution-constraints-prior-knowledge-requirement/rdr_5d80c4cb06c74981af66324ca514b3a7},
  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_parametric_distribution_constraints_prio_5d80c4cb_v1,
  title = {parametric distribution constraints (prior knowledge requirement)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/parametric-distribution-constraints-prior-knowledge-requirement/rdr_5d80c4cb06c74981af66324ca514b3a7/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