Satisficing Exploration in Sequential Decision Making

43 concepts23 papers1 proposal

In sequential decision-making under uncertainty, the traditional paradigm centers on optimization: finding the absolute best action, arm, or configuration. However, this relentless pursuit of the global optimum often encounters severe diminishing returns. In many real-world scenarios, an agent does not need the absolute best option; it simply needs an option that is "good enough."

This concept, known as satisficing, shifts the goal from continuous maximization to meeting a predefined performance threshold or aspiration level. As noted by Sugiyama et al. in the context of the 10th Asian Conference on Machine Learning, searching for the absolute optimal choice can be computationally and temporally wasteful for resource-constrained systems. By focusing on threshold-based satisfaction, algorithms can drastically reduce sample complexity and avoid unnecessary exploration.

Redefining Regret: From Absolute to Lenient

Traditional multi-armed bandit (MAB) frameworks evaluate performance using cumulative regret, which measures the gap between the chosen actions and the single best action over time. Because the agent must continuously refine its estimate of the optimum to ensure it isn't missing a marginally better choice, cumulative regret typically grows indefinitely.

To address this inefficiency, Merlis et al. introduced the concept of lenient regret in Lenient Regret for Multi-Armed Bandits. This metric ignores suboptimality gaps smaller than a predefined threshold $\epsilon$, treating all near-optimal actions as equivalent to the absolute best. By relaxing the objective, their $\epsilon$-Thompson Sampling algorithm allows for a distinct phase transition where the regret curve flattens out entirely, achieving constant rather than logarithmic cumulative regret.

Standard Regret:  Penalizes any gap from the absolute maximum. Continues exploring forever.
Lenient Regret:   Ignores gaps below ε. Flattens out once a "good enough" arm is found.

Similarly, Feng et al. proposed a meta-algorithmic framework in Satisficing Regret Minimization in Bandits that wraps around standard bandit algorithms. Instead of forcing the underlying algorithm to optimize indefinitely, the framework treats it as a candidate generator and terminates exploration the moment an arm's reward confidently exceeds the desired threshold.

Algorithmic Mechanisms: Threshold-Aware Acquisition

How do exploration strategies change when they no longer seek the absolute maximum? Traditional acquisition functions choose actions based on relative improvement or upper confidence bounds (UCB) aimed at the peak. Satisficing algorithms, by contrast, calculate the probability that an option exceeds a specific target value.

In Gaussian Process (GP) bandits, Cai et al. demonstrate in Lenient Regret and Good-Action Identification in Gaussian Process Bandits that incorporating a known success threshold directly into the acquisition function prevents the algorithm from wasting samples distinguishing between multiple supra-threshold actions. Target-value-based acquisition functions prioritize exploration purely based on the likelihood of crossing the 'good enough' boundary, ignoring the exact value of the peak.

For contextual environments subject to unpredictable shifts, Saday et al. developed RoBOS (Robust Bayesian Satisficing). Instead of requiring a predefined uncertainty set to handle distributional shifts, RoBOS leverages a user-defined utility threshold to minimize a metric called "fragility," ensuring the system achieves acceptable performance across varying contexts without over-engineering for the worst-case scenario.

Collapsing Sample Complexity

The mathematical advantage of satisficing is most apparent in its sample complexity. In standard Good Arm Identification (GAI), traditional methods often try to classify every single available option as either above or below a threshold. However, as Kano et al. argue in Good arm identification via bandit feedback, if the objective is simply to isolate a specific number of satisfactory options, comprehensively labeling the entire set is highly inefficient.

When acceptable solutions are plentiful, a threshold-based search can terminate much faster than a global optimization search. Katz-Samuels et al. formalize this in The True Sample Complexity of Identifying Good Arms by introducing unverifiable sample complexity, proving that satisficing avoids the need to compare candidates against one another.

Further refinements by Li et al. in Near Optimal Non-asymptotic Sample Complexity of 1-Identification provide near-optimal non-asymptotic bounds for binary classification tasks under uncertainty, optimizing the framework for finite-time engineering applications. To accelerate this process even further, Thaker et al. demonstrate in Maximizing and Satisficing in Multi-armed Bandits with Graph Information that overlaying graph-structured similarity relationships allows algorithms to discard entire clusters of suboptimal arms without ever pulling them.

Beyond Bandits: Stopping Rules and Equilibria

The principle of satisficing extends beyond simple bandit settings into game theory, optimal stopping, and system routing:

  • Optimal Stopping: In web search result evaluation, Huang et al. show in Optimal Strategies for Reviewing Search Results that a rational agent's optimal strategy is a fixed stopping rule dictated by a quality threshold. This minimizes the cognitive effort of scanning snippets once a satisfying answer is found.
  • Game Theory: In self-configuring wireless networks, Perlaza et al. introduce the Satisfaction Equilibrium (SE) in Satisfaction Equilibrium: A General Framework for QoS Provisioning in Self-Configuring Networks. Instead of selfishly maximizing utility (as in a Nash Equilibrium), devices aim only to meet a minimum Quality of Service (QoS) threshold, reducing interference and saving significant energy across the network.
  • Mortal Environments: When options have a finite lifespan, Chakrabarti et al. demonstrate in Mortal Multi-Armed Bandits that a reward threshold can act as an immediate trigger to exploit an arm before it expires, bypassing the need for exhaustive global optimization.

Handling Practical Constraints and Multi-Objective Trade-offs

Satisficing is uniquely suited for complex environments with strict operational constraints where absolute maximization is mathematically or physically impossible:

  • Recommendation Systems: Under "no-repetition" constraints where items cannot be recommended twice, Ariu et al. show in Regret in Online Recommendation Systems that targeting a top-tier quality percentile provides a mathematically feasible and practical benchmark when absolute maximization fails.
  • Multi-Objective Optimization: When objectives conflict, Maus et al. introduce MOCOBO in Covering Multiple Objectives with a Small Set of Solutions Using Bayesian Optimization. Instead of continuously maximizing objective values, it focuses on achieving a 'good enough' threshold across multiple dimensions to find a collaborative set of solutions, preventing wasted computational resources.
  • LLM Alignment: For large language models, Chehade introduces SITAlign in Bounded Rationality for LLMs: Satisficing Alignment at Inference-Time. By ensuring secondary goals (like safety) merely meet a strict threshold, the model can maximize its primary objective (helpfulness), outperforming traditional multi-objective optimization methods.
  • Edge Computing: In ECVL-ROUTER: Scenario-Aware Routing for Vision-Language Models, Han et al. apply this to route VLM queries. By evaluating whether a local edge model's response is "good enough" rather than chasing the cloud's absolute best answer, they route over 80% of tasks to the edge, drastically reducing latency and cost.
  • Privacy: Even under Local Differential Privacy (LDP), Barbara et al. show in Locally Differentially Private Thresholding Bandits how to identify all arms above a performance threshold, providing a framework crucial for domains like medicine where finding all viable dosages safely is paramount.

Key Foundational Work

Mortal Multi-Armed Bandits (2008) — contributed 1 concept elements to this direction.
Optimal Strategies for Reviewing Search Results (2010) — contributed 1 concept elements to this direction.
Satisfaction Equilibrium: A General Framework for QoS Provisioning in Self-Configuring Networks (2010) — 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_threshold_based_arm_identification_893a176e,
  title = {threshold-based arm identification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/threshold-based-arm-identification/rdr_893a176e9b9541279c181e8ee6d180b2},
  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_threshold_based_arm_identification_893a176e_v1,
  title = {threshold-based arm identification},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/threshold-based-arm-identification/rdr_893a176e9b9541279c181e8ee6d180b2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake