🤖 machine learning

CC-AOS: Cost- and Horizon-Conditioned Amortized Backward Induction for Finite-Horizon Optimal Stopping

The paper proposes CC-AOS, a structured amortized solver that learns a shared continuation-value model conditioned on state, time, horizon, and cost to efficiently solve finite-horizon optimal stopping problems across varying operating conditions, achieving superior performance and adaptability compared to traditional separate optimization methods.

Original authors: Tianwei Yu

Published 2026-07-28

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Tianwei Yu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but you have a strict budget for how many clues you can buy. Every time you ask for a new piece of evidence, it costs you a little bit of money. If you stop too early, you might guess the wrong culprit and fail. If you wait too long, you might catch the right person, but you'll have spent all your money on useless clues. This is the heart of a problem called "optimal stopping." It's the mathematical art of deciding exactly when to say, "I have enough information, let's make a decision."

Now, imagine this detective doesn't just work in one city with one price tag on clues. Sometimes the clues are cheap, sometimes they are expensive. Sometimes the detective has a whole day to solve the case, and other times they only have an hour. In the past, if a detective wanted to know the best time to stop, they had to hire a different expert for every single combination of price and time limit. It was like having to relearn how to ride a bicycle every time you changed the size of your shoes or the type of road you were on. This paper, written by Tianwei Yu, introduces a new kind of "super-detective" brain that learns the rules for all these different situations at once, so it can instantly tell you when to stop, no matter how much the clues cost or how much time you have left.

The Problem: Too Many Detectors, Not Enough Time

In the world of artificial intelligence, systems often have to look at a stream of data—like a recording of an engine noise or a sequence of stock prices—and decide when to stop listening and make a prediction. The goal is to be right, but also to be fast and cheap. If you stop too soon, your prediction might be wrong. If you keep listening, you pay a "cost" (in time, battery, or money) for every extra second of data.

The tricky part is that the "right" moment to stop changes depending on the situation. If the cost of listening is high, you should stop sooner. If you have a long deadline, you can afford to wait. Traditionally, scientists built a separate computer model for every single scenario. If you wanted to know what to do when a clue costs $0.01 and you have 30 seconds left, you trained one model. If you wanted to know what to do when a clue costs $0.02 and you have 40 seconds left, you had to train a completely different model from scratch. This is slow, expensive, and inefficient. It's like baking a fresh cake for every single guest at a party instead of making one big cake and slicing it.

The Solution: The "All-in-One" Detective Brain

The paper proposes a new method called CC-AOS (Cost- and Horizon-Conditioned Amortized Optimal Stopping). Think of CC-AOS not as a single detective, but as a detective who has memorized the entire library of "stop-or-go" rules for every possible price tag and time limit.

Instead of training a new model for every situation, CC-AOS trains one giant, flexible model that understands the relationship between the current evidence, the time remaining, and the cost of the next clue. The authors call this "amortized optimization." In simple terms, it's like paying a small fee upfront to learn a skill that saves you a massive amount of time later. Once this model is trained, you can ask it, "What should I do if the cost is X and the time left is Y?" and it gives you an answer instantly, even if it has never seen that exact combination before.

How It Works: The Shape of Smart Decisions

The magic of CC-AOS isn't just that it learns faster; it's that it learns correctly. The authors realized that the math behind these decisions has a specific shape. For example, if the cost of a clue goes up, the value of waiting should never go down—it should either stay the same or go up. Also, the "smoothness" of this decision curve depends on how much time is left.

To make sure their AI doesn't learn weird, impossible rules, the researchers built special "guardrails" into the model's architecture. They forced the computer to follow these mathematical laws (like being "concave" or "Lipschitz," which are fancy ways of saying the decision curve bends in a predictable, logical way). This ensures that even when the AI guesses for a situation it hasn't seen, it guesses in a way that makes sense physically and logically.

What They Found: One Brain Beats Many

The researchers tested this new method on several challenges, including a real-world dataset of engine noises called FordA. They compared their "super-detective" (CC-AOS) against the old method of training separate models for each scenario (called CFL) and against simple, static rules.

The results were impressive. On the FordA engine-noise data, the CC-AOS model was tested on six different combinations of cost and time that it had never seen during training. In all six cases, it performed better than the method that trained a separate model for each specific situation.

On average, CC-AOS reduced the total "risk plus cost" by 15.75% compared to the separate models.
In some specific cases, the improvement was as high as 31.29%.
It also matched the performance of a very strong, pre-tuned static rule, proving it didn't sacrifice accuracy for speed.

Furthermore, the new method was incredibly efficient. Training the single CC-AOS model took only 18.04 seconds. In contrast, training the six separate models required about 53 minutes. This means the new method is not only smarter but also thousands of times faster to set up.

The Takeaway

This paper suggests that we don't need to build a new brain for every new set of rules. By teaching one AI to understand the underlying geometry of "when to stop," we can create a system that adapts instantly to changing costs and deadlines. While the paper focuses on specific simulations and a real-world engine noise dataset, the results show that a single, well-structured model can outperform a collection of specialized ones, saving both time and computational power. It's a step toward making AI systems that are not just smart, but also flexible and efficient enough to handle the messy, changing reality of the real world.

Technical Summary: CC-AOS

1. Problem Formulation

The paper addresses finite-horizon optimal stopping, a central challenge in early time-series classification. In this setting, a system must decide at each sequence prefix whether to stop and make a terminal decision or to acquire another observation. This decision involves a trade-off: stopping early saves acquisition costs (time, energy, computation) but risks higher terminal decision error, while waiting improves prediction accuracy but incurs additional costs and delay.

The core difficulty arises when operating conditions are not fixed. In many applications, the sampling cost ( $\lambda$ ) and the maximum horizon ( $H$ ) vary dynamically due to changing resource availability or latency budgets. Existing data-driven backward-induction methods typically solve for a single cost–horizon pair at a time. Consequently, adapting to a new operating point requires re-optimization and the construction of separate model stacks, making continuous cost adaptation and multi-horizon deployment inefficient. The paper seeks a unified model that learns a family of stopping problems indexed by continuous costs and multiple horizons, enabling direct querying at unseen cost–horizon pairs.

2. Methodology: CC-AOS

The authors propose CC-AOS (Cost- and Horizon-Conditioned Amortized Optimal Stopping), a structured amortized solver. The methodology consists of three interconnected components:

2.1 Shared Cost–Horizon Continuation Model

Instead of fitting separate models for each operating point, CC-AOS learns a single shared continuation model $C_\theta(s, t, h, \lambda)$ .

Inputs: The model is conditioned on the current state $s$ , absolute time $t$ , remaining horizon $h$ , and sampling cost $\lambda$ .
Output: It approximates the continuation value $C_h(s; \lambda)$ , representing the expected future optimal risk after acquiring one more observation.
Policy Derivation: The stopping decision is made by comparing the terminal risk $g(s)$ with the complete continuation risk $\lambda + C_\theta(s, t, h, \lambda)$ .

2.2 Joint Amortized Fitted Backward Induction

The model is trained using a joint amortized fitted backward-induction procedure.

Training Process: The algorithm iterates from small remaining horizons to large ones. At each layer, it uses a frozen snapshot of the current model to generate recursive Bellman targets.
Data Generation: Targets are constructed over continuously sampled costs (drawn from a distribution $q$ ) and transitions drawn from multiple training horizons.
Optimization: A replay buffer accumulates tuples $(s, t, h, \lambda, y_h)$ , where $y_h$ is the target value. The shared model parameters $\theta$ are updated to minimize the regression loss against these targets across all accumulated layers and operating points simultaneously.

2.3 Structure-Preserving Architecture

To ensure the learned continuation surface behaves correctly with respect to cost, the authors encode theoretical properties of the exact value function into the model architecture.

Theoretical Properties: The exact value function $V_h(s; \lambda)$ is proven to be nondecreasing, concave, and $h$ -Lipschitz in $\lambda$ . The continuation value $C_h(s; \lambda)$ is nondecreasing, concave, and $(h-1)$ -Lipschitz.
Normalized Soft-Min Affine Head: The model outputs logits that are transformed into intercepts ( $a_j$ ) and slopes ( $b_j$ ). The final continuation estimate is computed via a normalized soft-minimum of affine functions:
$\tilde{C}_\theta = -\rho \log \left[ \frac{1}{J} \sum_{j=1}^J \exp \left( \frac{-a_j + b_j \lambda}{\rho} \right) \right]$
The slopes $b_j$ are constrained to $[0, h-1]$ via a sigmoid transformation. This architecture guarantees that the learned function preserves monotonicity, concavity, and the horizon-dependent Lipschitz constant by construction.

3. Theoretical Analysis

The paper provides a rigorous theoretical framework linking the approximation error to policy performance:

Geometry Preservation: The structured head is proven to maintain the exact monotonicity, concavity, and Lipschitz properties of the true value functions.
Error Bounds: The authors derive residual-based bounds showing that the Bellman approximation error accumulates linearly over the horizon. Specifically, the difference between the learned value and the true optimal value is bounded by the sum of layerwise Bellman residuals.
Policy Performance: The suboptimality of the induced greedy stopping policy is bounded by twice the sum of the continuation residuals, providing a direct link between the quality of the fitted continuation function and the performance of the deployed policy.

4. Experimental Results

Experiments were conducted on three settings: controlled Gaussian processes, time-varying non-Gaussian mixtures, and the FordA engine-noise time-series benchmark.

4.1 Generalization to Unseen Operating Points

On the FordA dataset, a single CC-AOS checkpoint was trained on horizons $H \in \{20, 30, 40, 50\}$ and costs $\lambda \in [0.0005, 0.008]$ . It was then evaluated at six unseen cost–horizon pairs (interleaved horizons and costs).

Comparison with Per-Setting Solvers: CC-AOS achieved a lower terminal-risk-plus-sampling-cost objective than independently fitted Convex Function Learning (CFL) at all six unseen pairs.
Performance Gain: The average reduction in the objective was 15.75%, with relative reductions ranging from 0.95% to 31.29%. Five of the six paired bootstrap confidence intervals were entirely below zero.
Comparison with Static Thresholds: CC-AOS performed essentially on par with a strong, validation-tuned static stopping threshold on average, though it offers a dynamic, state-dependent boundary rather than a static rule.

4.2 Ablation and Efficiency

Structure Preservation: An ablation study replacing the structured head with a parameter-matched unstructured head showed that the unstructured head had slightly lower task objective in one controlled setting but violated monotonicity and concavity constraints (up to 7.10% violation rate). The structured head eliminated all such violations.
Computational Efficiency: CC-AOS trained a single shared model in 18.04 seconds. In contrast, fitting independent CFL solvers for six operating points took approximately 53 minutes, and fitting per-horizon references took 33.48 seconds.

5. Significance and Claims

The paper claims that CC-AOS represents a shift from solving isolated stopping problems to learning a coherent family of solutions.

Unified Representation: It replaces the need for multiple, independently fitted model stacks with a single checkpoint that can be queried directly at any cost–horizon pair within the modeled range.
Geometric Consistency: By encoding the exact cost geometry (monotonicity, concavity, Lipschitz continuity) into the architecture, the method ensures reliable behavior along the continuous cost axis, which unconstrained shared networks fail to guarantee.
Practical Deployment: The approach enables efficient multi-operating-point deployment, allowing systems to adapt to changing latency budgets or acquisition costs without retraining.

The authors maintain a modest tone regarding their claims, noting that while CC-AOS outperforms per-setting solvers significantly, it remains competitive with (but not strictly superior to) strong static thresholds on average. The primary contribution is the provision of a dynamic, state-dependent stopping boundary and a shared continuation surface that supports direct multi-operating-point deployment, rather than claiming universal superiority in every metric. The work is limited to binary classification with fixed upstream state estimators and constant per-observation costs, with future work suggested for multiclass settings and time-dependent costs.