Neighborhood Restricted Exploration in Unimodal Bandits

38 concepts22 papers1 proposal

In standard multi-armed bandit (MAB) problems or black-box optimization, a fundamental challenge is scalability. If an agent must choose between $K$ independent options (or "arms"), the cost of finding the best option—measured in cumulative regret or sample complexity—inherently scales with the total number of choices. As the action space grows massive, continuous, or combinatorial, unstructured exploration becomes completely intractable.

To bypass this curse of dimensionality, researchers look for structural properties in the reward landscape. While convexity is a powerful assumption, it is frequently too restrictive for real-world empirical surfaces. A broader, highly elegant alternative is unimodality: the assumption that the reward landscape possesses a single global "peak." As Cutkosky et al. note, many empirical hyperparameter surfaces exhibit a single peak, meaning that failing to exploit this unimodal structure leads to highly inefficient search strategies.

Defining Graphical Unimodality

How do we formalize a "single peak" when the action space isn't a simple continuous line? The breakthrough lies in mapping the action space to an underlying graph structure.

In this framework, actions are represented as nodes, and edges define a neighborhood relationship. A reward function is considered graphically unimodal if there are no local maxima other than the global maximum. More precisely, from any sub-optimal node, there exists a path of strictly increasing rewards leading directly to the global optimum.

This graph-based representation allows us to structure highly complex spaces:

  • Continuous or Discrete Parameters: In wireless systems, parameters like transmission rates, channels, or angular beam alignments naturally form graphs where adjacent settings are neighbors (Combes et al.; Hashemi et al.).
  • Combinatorial Permutations: In online ranking problems, the space of item arrangements can be structured as a graph where two rankings are neighbors if they differ by a single item swap or replacement. As Gauthier et al. demonstrate, user click behaviors under the Position-Based Model exhibit an inherent relaxed unimodality over these permutation graphs.
  • Matrices: In rank-one bandit problems, arms can be modeled as a graph where nodes are connected if they share a row or column, creating a unimodal topology (Trinh et al.).

Why It Works: The Power of Local Neighborhoods

The core intuition behind why unimodal optimization is so efficient can be summarized in a single principle: a local maximum is a global maximum.

Because the reward landscape lacks deceptive local peaks, an agent does not need to survey the entire action space to know which direction to move. If the current empirical leader is sub-optimal, at least one of its immediate neighbors must yield a higher expected reward.

Consequently, exploration can be strictly restricted to the immediate neighborhood of the current empirical leader. As pioneered by Proutiere et al. with the OSUB (Optimal Sampling for Unimodal Bandits) algorithm, the search complexity collapses from the size of the entire action space down to the local degree of the underlying graph.

This neighborhood-restricted exploration changes the sampling dynamics entirely:

  1. Sub-logarithmic Distant Sampling: Options that are far away from the current peak do not need to be sampled heavily. Saber et al. show that leveraging local graph structures allows for sub-logarithmic sampling of distant options, concentrating almost all exploration effort on immediate neighbors and effectively pruning irrelevant regions of the search space.
  2. Local Stopping Criteria: In best-arm identification tasks, algorithms can terminate much earlier than standard methods. Poiani et al. prove that a local stopping criterion—checking an arm's performance purely relative to its immediate neighbors—is sufficient to guarantee global optimality.

Breaking the Dependence on Action Space Size

The mathematical payoff of this localized exploration is profound. In standard bandits, regret scales with the total number of arms $K$. In unimodal bandits, the performance bounds become decoupled from the total size of the action space.

Proutiere et al. proved that OSUB achieves an optimal regret that does not depend on the total number of arms. Similarly, in fixed-budget settings, Ghosh et al. show that the probability of error becomes independent of $K$ in the exponent. This allows algorithms to scale seamlessly to massive or even continuous action spaces.

Furthermore, this structure enables safe, directional exploration. In scenarios where an agent cannot backtrack and must commit to a monotone sequence of actions, Chen demonstrates that a quasiconcave (unimodal) reward landscape allows the agent to infer global properties from local trends and safely terminate exploration without getting trapped in local optima.

From Theory to Physical Systems

This theoretical framework translates directly into massive efficiency gains across practical engineering domains:

  • Wireless Communications: In Wi-Fi Rate Adaptation, Proutiere et al. exploit the unimodal nature of throughput curves to restrict exploration, avoiding the costly overhead of probing the entire space of transmission modes. For Reconfigurable Intelligent Surfaces (RIS), Zappone et al. prove that energy efficiency is unimodal with respect to the number of reflecting elements, preventing local searches from getting trapped in suboptimal configurations.
  • Adaptive Clinical Trials: In dose allocation, Shen et al. incorporate structural assumptions (like a monotonic increase followed by a plateau) to share information between adjacent doses, drastically reducing the patient sample size needed to find the optimal biological dose safely.
  • Data Mining: For submatrix localization, Liu et al. utilize the unimodality of the objective function to replace exhaustive grid searches with highly efficient variants like Golden Section Search.

By shifting the optimization paradigm from global surveillance to graph-based local verification, neighborhood-restricted exploration turns intractable search spaces into highly efficient, path-based journeys to the global optimum.

Key Foundational Work

Unimodal Bandits: Regret Lower Bounds and Optimal Algorithms (2014) — contributed 3 concept elements to this direction.
Dynamic Rate and Channel Selection in Cognitive Radio Systems (2014) — contributed 2 concept elements to this direction.
Unimodal Bandits (2011) — 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_unimodal_reward_structure_ce350d48,
  title = {unimodal reward structure},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unimodal-reward-structure/rdr_ce350d48dcfe4c07bbb7fdd001e974f7},
  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_unimodal_reward_structure_ce350d48_v1,
  title = {unimodal reward structure},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unimodal-reward-structure/rdr_ce350d48dcfe4c07bbb7fdd001e974f7/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