Overcoming the Unique Optimal Arm Constraint in Bandits

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 261 papers75 conceptsfrozen 2026-10-04

In the mathematical theory of Multi-Armed Bandits (MAB), there is a silent assumption that does much of the heavy lifting: the existence of a unique optimal arm.

Most classic regret bounds—the measure of how much reward a learner loses by not knowing the best action from the start—are "gap-dependent." They rely on a parameter $\Delta$, representing the difference in expected reward between the best arm and the second-best arm. When a unique winner exists, the learner eventually gathers enough data to "see" this gap, allowing regret to grow only logarithmically over time.

However, as Tiancheng Jin, Junyan Liu, and Haipeng Luo argue in Improved Best-of-Both-Worlds Guarantees for Multi-Armed Bandits: FTRL with General Regularizers and Multiple Optimal Arms, this uniqueness is often an "artifact of analytical methods" rather than a reality of the world. In complex systems, multiple strategies may yield identical maximum rewards. When the gap $\Delta$ disappears because two arms are tied for first place, the traditional mathematical machinery often breaks, leading to theoretical guarantees that vanish or become trivial.

The Mathematical Hurdle of Ties

Why do ties cause such trouble? In stochastic environments, algorithms like UCB (Upper Confidence Bound) work by being optimistic; they pick the arm that might be the best. If there is only one best arm, the algorithm eventually stops picking the sub-optimal ones. But if two arms are equally optimal, the algorithm may oscillate between them indefinitely.

While this doesn't hurt the learner's reward (since both arms are "best"), it wreaks havoc on proofs for specific types of problems:

  1. Switching Costs: As Chloé Rouyer, Yevgeny Seldin, and Nicolò Cesa-Bianchi show in An Algorithm for Stochastic and Adversarial Bandits with Switching Costs, if a learner constantly switches between two tied optimal arms, they may incur massive "switching costs" that wouldn't exist if they just stuck to one.
  2. Best-Arm Identification (BAI): In pure exploration, the goal is to identify the best arm and stop. If two arms are tied, a learner looking for a "unique" winner will never find one, potentially sampling forever. Marc Jourdan, Rémy Degenne, and Emilie Kaufmann address this in An $\varepsilon$-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond by relaxing the goal to finding an arm that is "good enough" (within $\varepsilon$ of the best).
  3. Combinatorial Settings: In problems like online ranking or network routing, the number of possible "super-arms" is exponential. Sougata Chaudhuri and Ambuj Tewari note in Phased Exploration with Greedy Exploitation in Stochastic Combinatorial Partial Monitoring Games that multiple configurations often result in identical rewards, making "optimism-based" approaches unstable.

From Unique Arms to Optimal Mixtures

A surprising insight from recent research is that the "single best arm" might not even be the goal. In Preference-centric Bandits: Optimality of Mixtures and Regret-efficient Algorithms, Meltem Tatlı, Ali Tajer, and colleagues demonstrate that when we care about risk or tail behavior (rather than just the average reward), the optimal strategy is often a randomized mixture of arms.

This shifts the problem from "finding the needle in the haystack" to "finding the right distribution over the hay." This perspective naturally handles ties: if two arms are equally good, any mixture of them is also optimal.

Robustness Through Self-Bounding and Adaptive Grids

To move past the unique arm assumption, researchers are developing more flexible analytical frameworks.

One approach involves self-bounding techniques. In Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptions, Saeed Masoudian and Yevgeny Seldin use refined mathematical proofs that don't collapse when the gap $\Delta$ is zero. These proofs essentially bound the regret by the algorithm's own internal variance or stability, rather than external gaps in the environment.

Another approach is the use of adaptive grids and phased exploration. Instead of trying to identify the single best arm at every step, algorithms like those proposed by Tianyuan Jin and Quanquan Gu in Almost Optimal Anytime Algorithm for Batched Multi-Armed Bandits eliminate sets of arms in batches. By focusing on eliminating "clearly bad" arms rather than identifying the "uniquely best" one, these algorithms remain robust even when the remaining pool contains multiple identical winners.

Why It Works: Intuition

The shift away from the unique optimal arm assumption is essentially a shift toward coarse-grained identification.

If you assume there is only one best arm, you are forced to zoom in infinitely close to distinguish it from a "near-tie." If you allow for multiple optimal arms, you only need to zoom in far enough to distinguish the "optimal group" from the "sub-optimal group." This makes the algorithms more stable, more parallelizable, and ultimately more applicable to real-world scenarios where the difference between two choices might be non-existent or too small to matter.

Papers in this version

Showing 60 of 61 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_unique_optimal_action_assumption_b2bbdcbe,
  title = {unique optimal action assumption},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/unique-optimal-action-assumption/rdr_b2bbdcbe47954be3a2b620f2690b2c84},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_overcoming_the_unique_optimal_arm_constr_b2bbdcbe_v1,
  title = {Overcoming the Unique Optimal Arm Constraint in Bandits},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/overcoming-the-unique-optimal-arm-constraint-in-bandits/rdr_b2bbdcbe47954be3a2b620f2690b2c84/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}