Learning with Non-Unique Optimal Actions

97 concepts67 papers1 proposal

In sequential decision-making, multi-armed bandits, and reinforcement learning (RL), theoretical guarantees often rely on a comforting mathematical luxury: the unique optimal action assumption. This assumption posits that there is exactly one best choice available to the agent at any given state, separated from all suboptimal choices by a distinct performance margin known as the "suboptimality gap" ($\Delta > 0$).

While mathematically convenient, real-world environments rarely conform to this ideal. Symmetries, redundant constraints, and multi-objective goals frequently create scenarios where multiple distinct actions or policies yield the exact same optimal reward. When these ties occur, the foundational mathematics of exploration, convergence, and regret minimization begin to fracture.

Understanding why this assumption is so pervasive—and how algorithms break when it is violated—reveals a major frontier in modern learning theory.


The Comfort of the Suboptimality Gap

To understand why non-unique optima cause trouble, we must first look at why theorists love a unique optimum. In a standard stochastic multi-armed bandit or Markov Decision Process (MDP), an algorithm's goal is to minimize regret—the difference between the reward earned by the optimal strategy and the reward earned by the agent.

When a unique optimal action exists, the suboptimality gap $\Delta$ acts as a safety margin. As an agent gathers data, its confidence intervals around the estimated values of each action shrink. Once these intervals become smaller than $\Delta$, the agent can statistically differentiate the single best action from the rest and stop exploring suboptimal choices. This mechanism underpins the classic "logarithmic regret" bounds ($O(\frac{\log T}{\Delta})$) that define efficient online learning.

As noted by Tian Lin et al. in Combinatorial Partial Monitoring Game with Linear Feedback and Its Applications, achieving this logarithmic regret heavily depends on the existence of a single unique optimal action. Shinji Ito argues in On Optimal Robustness to Adversarial Corruption in Online Decision Problems that assuming a single optimal action separated by a distinct gap is far too restrictive for practical applications where environments are complex and less clearly defined.


What Breaks When Optima Are Tied?

When multiple actions are perfectly optimal, the suboptimality gap vanishes ($\Delta = 0$). If you plug $\Delta = 0$ into standard gap-dependent regret formulas, the denominator goes to zero, and the bounds blow up. This mathematical artifact reflects several deep structural failures that occur in the underlying optimization process.

1. The Loss of Constant and Logarithmic Regret

Without a positive gap to exploit, algorithms can no longer cleanly eliminate options. In Revisiting Online Learning Approach to Inverse Linear Optimization: A Fenchel-Young Loss Perspective and Gap-Dependent Regret Analysis, Shinsaku Sakaue et al. demonstrate that when multiple optimal actions exist, the margin between choices vanishes, causing the regret bound to degrade from a stable constant to a square-root ($\sqrt{T}$) growth relative to time.

2. The Non-Smoothness of the Bellman Operator

In reinforcement learning, algorithms like Q-learning rely on Stochastic Approximation (SA) to solve the Bellman optimality equation. This equation inherently uses a maximization operator ($\max_a Q(s,a)$) to evaluate the value of the next state.

If one action is strictly better than the others, the $\max$ function behaves smoothly around that optimal value, making it differentiable. This allows theorists to use Taylor expansions to linearize the operator and prove convergence.

Unique Optimum (Smooth at Max)         Non-Unique Optima (Kink/Nonsmooth)
          Value                                  Value
            ^                                      ^
            |     .---.                            |     /\
            |    /     \                           |    /  \
            |   /       \                          |   /    \
            +------------->                        +------------->
                Actions                                Actions

However, when multiple actions achieve the exact same maximum reward, the objective function develops a sharp "kink" or non-differentiable point at the optimum. Dongyan Lucy Huo et al. in Prelimit Coupling and Steady-State Convergence of Constant-stepsize Nonsmooth Contractive SA show that this degeneracy introduces non-smooth behavior into the error dynamics, making it incredibly difficult to predict asymptotic behavior.

Furthermore, Qiaomin Xie et al. in Constant Stepsize Q-learning: Distributional Convergence, Bias and Extrapolation establish that this non-smoothness invalidates standard bias expansion models, because the linearization of the Bellman operator breaks down entirely when ties occur.


Algorithmic Consequences in the Wild

The breakdown of the unique optimality assumption manifests as concrete failures in algorithmic behavior, particularly in identification tasks and environments with action-dependent costs.

Statistical Indecision in Pure Exploration

In Best-Arm Identification (BAI) or Best-Policy Identification (BPI), an agent's explicit goal is to find the optimal strategy using the fewest samples possible and then stop. Most statistical stopping criteria monitor the confidence bounds between the top candidate and its competitors.

If two policies are equally valid, the algorithm will find itself unable to declare one a definitive winner. As Alessio Russo et al. explain in Multi-Reward Best Policy Identification, when multiple policies achieve the same maximum reward, the statistical stopping criteria become significantly more complex to implement.

Emil Carlsson et al. echo this in Pure Exploration in Bandits with Linear Constraints, noting that standard sample allocation strategies fail to provide the same theoretical guarantees when multiple policies are nearly indistinguishable or tied. This makes the problem of navigating to the best policy structurally ill-posed under traditional frameworks, an issue detailed by Aymen Al Marjani et al. in Navigating to the Best Policy in Markov Decision Processes.

The Cost of Oscillation

In practical applications, changing your mind costs something. In bandits with switching costs, an agent incurs a penalty every time it selects a different action from the previous step.

If Arm A and Arm B are both perfectly optimal, a standard optimistic algorithm might suffer from minor statistical fluctuations in its empirical estimates. It will pull Arm A, see its estimate drop slightly due to noise, switch to Arm B, see Arm B's estimate drop, and switch back.

Empirical Mean
    ^
    |   Arm A   Arm B   Arm A   Arm B
    |    _       _       _       _
    |   / \     / \     / \     / \
    |--/---\---/---\---/---\---/---\---> Time
    |       \_/     \_/     \_/     \_/
    +------------------------------------> High Switching Cost Accumulated!

While the cumulative reward remains optimal, this endless flip-flopping creates a hidden catastrophe. Chloé Rouyer et al. in An Algorithm for Stochastic and Adversarial Bandits with Switching Costs demonstrate that frequent switching between tied optimal actions inflates the switching cost in the analysis, destroying the algorithm's efficiency. Cem Tekin et al. confirm this behavioral failure in Online Learning of Rested and Restless Bandits, observing that when multiple arms provide identical expected rewards, the selection mechanism fails to stabilize, leading to highly inefficient switching behavior.


The Fundamental Separation Between Bandits and RL

The challenge of non-unique optima exposes a deep theoretical divide between simple multi-armed bandits and full Markov Decision Processes.

In a bandit setting, picking between two tied optimal arms is harmless to future iterations because each pull is independent. In reinforcement learning, however, your current action dictates your next state. If a state contains multiple actions that are equally optimal but lead to entirely different parts of the state space, the transition dynamics couple with the optimization process in dangerous ways.

Haike Xu et al. expose this phenomenon in Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive Multi-Step Bootstrap. They prove that when optimal actions are not unique, the transition operator can create hard instances that necessitate higher exploration costs. This introduces an unavoidable regret penalty proportional to the number of states with multiple optimal actions—a fundamental theoretical separation that does not exist in simpler bandit settings.


Designing for Non-Unique Optima

To build algorithms capable of operating in real-world environments, researchers have developed techniques that explicitly accommodate or smooth out non-unique optima.

Top-Two Sampling

Instead of greedily picking the single empirical best arm, top-two sampling strategies dynamically allocate a portion of their exploration budget to a "challenger" arm. Marc Jourdan et al. demonstrate in An $\varepsilon$-Best-Arm Identification Algorithm for Fixed-Confidence and Beyond and Top Two Algorithms Revisited that these strategies achieve asymptotic optimality even when the optimal arm is not unique or when dealing with zero-gap distributions, providing robust performance without needing a strictly positive gap.

Entropic and Regularized Mirror Descent

Another way to bypass the non-smoothness of the $\max$ operator is to add regularization, which rounds out the sharp kinks in the optimization landscape. Shinji Ito shows in Parameter-Free Multi-Armed Bandit Algorithms with Hybrid Data-Dependent Regret Bounds that certain online mirror descent variants, such as the Tsallis-INF algorithm, naturally handle multiple optimal arms efficiently by utilizing data-dependent regularization parameters that do not collapse under ties.

Shifting Focus to Policy-Space Convergence

Finally, some researchers argue that we should care about converging to the maximum possible reward, rather than converging to a single behavior.

In REINFORCE Converges to Optimal Policies with Any Learning Rate, Samuel McLaughlin Robertson proves that for policy gradient methods operating in environments with multiple equally optimal actions, the cumulative probability of the optimal action set cleanly converges to one. Even if individual action probabilities continue to oscillate indefinitely because they are tied, the agent's expected reward remains perfectly maximized.

By shifting the analytical lens from tracking individual actions to tracking optimal subspaces, modern learning theory is successfully moving past the restrictive crutch of the unique optimal action.

Key Foundational Work

Adaptive Learning of Uncontrolled Restless Bandits with Logarithmic Regret (2011) — contributed 1 concept elements to this direction.
Combinatorial Partial Monitoring Game with Linear Feedback and Its Applications (2014) — contributed 1 concept elements to this direction.
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 2, frozen text):

@misc{lacuna_unique_optimal_action_assumption_b2bbdcbe_v2,
  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/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake