AI Glossary / Graphs and symbolic AI / Intermediate
Stopping rule
Definition
A stopping rule specifies when a sequential process should end or switch to another option, using information available at the time of the decision. In AI decision-making, it can determine when to stop exploring an uncertain option and commit to an alternative. A rule describes the decision policy; the stopping time is the time at which that policy actually triggers on a particular run.
What it means
The important question is often not whether an option is currently attractive, but whether trying it again is worth the cost and possible information gained. Continuing can produce rewards, reveal useful evidence, or consume resources that could have been used elsewhere.
A sequential rule cannot rely on observations that have not yet occurred. An optimal stopping rule also needs an objective and a model of consequences. The best rule depends on rewards, remaining time, information, and alternatives.
How it works
Specify what can be observed, when decisions are made, what stopping means, and what happens if the process continues. Compare the value of stopping now with the expected value of continuing, including later decisions that will use newly available information.
For a finite-horizon model, backward reasoning can evaluate the final decision first and then work toward the present. A threshold rule may result, depending on the problem. Document whether the rule is mathematically optimal under a stated model or simply a chosen operating policy.
Three practical examples
- A bandit-style learning exercise can decide when to leave an uncertain reward process for a known alternative.
- A search system can stop gathering candidate solutions when its stated budget or quality condition is reached.
- A sequential inspection simulation can stop once observed evidence meets a defined decision criterion, provided the analysis respects that monitoring design.
Think of it this way
Think of trying an unfamiliar route while retaining the option to return to a known route. Each trial can teach you something, but it also uses time. The analogy is limited because a formal stopping problem must specify exactly what is learned, whether switching is reversible, and how current and future outcomes are valued.
Worked example
Consider an original two-round decision problem. A known option provides reward three each round. An experimental option has a fixed but initially unknown type: with probability one half it is good and always gives six; with probability one half it is bad and always gives zero. One experimental observation reveals its type perfectly. Rewards are added without discounting.
The decision maker can choose the known option permanently, or try the experimental option and then decide whether to continue with it. If the known option is chosen immediately for both rounds, total reward is 3 + 3 = 6.
Work backward from the second and final round. If a first-round experiment revealed a good option, continuing gives six, which is better than switching for three. If it revealed a bad option, switching gives three, which is better than continuing for zero.
Therefore, the adaptive rule is: try the experiment in round one; continue in round two after reward six; stop using it and switch after reward zero. With probability one half, the total is 6 + 6 = 12. With probability one half, the total is 0 + 3 = 3. Expected total reward is one half of twelve plus one half of three, or 7.5.
Compare this with committing to the experimental option for both rounds. Its total is twelve or zero with equal probability, giving expectation six. The benefit of 7.5 comes from using the first observation to change the second decision, not from a higher initial expected experimental reward: that reward is three, equal to the known option.
If only one round remained, there would be no future opportunity to use the information, and the expected rewards of trying and choosing the known option would both be three. The remaining horizon therefore changes the value of exploration.
The example assumes perfect revelation, a fixed type, no switching cost, and no ability to recover a missed round. Changing those assumptions changes the decision problem and may change the rule.
Illustrative case study
In a fictional simulation project, a team compares a fixed trial limit with a rule that can switch after observing results. It defines the reward model, the information revealed by each trial, and the available fallback before running comparisons.
The team records total reward and trials used, checking whether differences reflect useful information or changed budgets. This fictional evaluation does not describe a deployed service.
Common misconceptions and mistakes
A stopping rule is not necessarily a fixed deadline. It can depend on observed history. Conversely, a history-dependent rule is not automatically optimal; optimality is relative to a specified model and objective.
Do not use future outcomes to decide retrospectively when a system should have stopped and then describe that as an implementable rule. Do not ignore the value of information when comparing current expected rewards. Finally, repeatedly monitoring a statistical result can affect the validity of an analysis designed for a fixed sample size; the monitoring procedure must be considered explicitly.
Business use
Stopping rules help make resource-allocation decisions consistent and explainable. They can determine when more information is unnecessary or an alternative becomes preferable.
Write the rule before evaluating it, specify the information available at each decision, and log the reason for stopping. Compare its outcomes with meaningful baselines under the same constraints. If the model uses estimated probabilities or rewards, examine how sensitive the selected rule is to those estimates rather than presenting the decision as assumption-free.
People also ask
Is a stopping rule the same as its stopping time?
The rule is the policy; the stopping time is when it triggers on a run.
Must stopping mean doing nothing afterward?
No. It can mean switching permanently to a fallback or ending one phase of a larger process.
Does a rule need future information to be optimal?
No. It uses a model of possible futures while acting only on information currently available.
Check your understanding
Why is trying the experiment worthwhile with two rounds but not strictly better with only one?
Answer: With two rounds, the first result guides a later choice. With one round, there is no later decision that can use the information.
Related terms
- Stopping time
- Exploration
- Exploitation
- Finite horizon
- Dynamic programming
- Optimal stopping
- Multi-armed bandit
- Value of information
Learn next
Next, charge one unit only for the initial experimental trial. The adaptive expected total becomes 6.5, still above the known option's six. Raise that trial charge to two: the expected total becomes 5.5. Explain how an information-gathering cost can reverse the decision.
More in Graphs and symbolic AI
- Stochastic games - Stochastic games are models of sequential interaction in which several players choose actions, receive rewards, and influence probabilistic transitions...
- Stochastic hill climbing - Stochastic hill climbing is a local-search method that randomly selects among improving moves instead of always choosing the best immediate neighbor.
- Stoer-Wagner minimum cut - The Stoer - Wagner minimum-cut algorithm finds a global minimum edge cut in an undirected graph with nonnegative edge weights.
- Strategic form - Strategic form, also called normal form, represents a game by specifying its players, each player's available strategies, and the payoff each player...
- Strategy - A strategy is a player's complete plan for choosing actions in a game or other model of strategic interaction.
- Strategy profile - A strategy profile is a collection containing one strategy for every player in a game.
Sources
Primary sources: Russell and Norvig's AIMA source sentences, one-armed-bandit stopping-rule context: https://raw.githubusercontent.com/aimacode/aima-glossary/master/sentences.txt ; Scott Sheffield, MIT probability lecture, stopping-time information condition: https://math.mit.edu/~sheffield/2016175/Lecture15.pdf . The two-round model and calculations are original.
Previous: Stop word Next: Stopping time