In many real-world decision-making scenarios, we face a fundamental tension between accuracy and cost. A doctor must decide whether to stop at a cheap blood test or order an expensive MRI; a security system must decide whether to trigger a simple heuristic or run a computationally heavy deep learning model.
The standard way to optimize these "cascades" is through supervised learning: we look at historical data where the "ground truth" (the actual disease or the actual security threat) is known. But what if we never see the ground truth? What if we have to learn the optimal sequence of sensors or tests while the system is running, without ever receiving feedback on whether our final classification was correct?
This is the problem of Unsupervised Sequential Selection (USS). Research by Manjesh Kumar Hanawal, Csaba Szepesvari, and Venkatesh Saligrama has shown that, under specific structural conditions, it is mathematically possible to achieve near-optimal performance even in total darkness.
The Problem of Hidden Rewards
In a typical Multi-Armed Bandit problem, you pull a lever and see a reward. In USS, the "arms" are sensors arranged in a sequence. You can choose to stop at sensor $k$ and pay a low cost, or proceed to sensor $k+1$ for a higher cost but potentially better accuracy.
The difficulty, as explored in Sequential Learning without Feedback, is that the reward—the correctness of the prediction—is never revealed. If you never know when you are wrong, you cannot easily identify which sensors are reliable. Without some underlying structure, the learner cannot distinguish between a cheap, accurate sensor and a cheap, noisy one.
The Key Intuition: Weak Dominance
The breakthrough that makes USS solvable is a property called Weak Dominance. Introduced in Unsupervised Sequential Sensor Acquisition, this property assumes a reliability hierarchy: more expensive sensors are generally more accurate than cheaper ones.
Specifically, weak dominance implies that if a cheap sensor is correct, a more expensive sensor later in the cascade is also likely to be correct. This creates a mathematical "anchor." While we don't know the ground truth, we can observe the disagreement rate between sensors.
If a cheap sensor and an expensive sensor frequently disagree, and we assume the expensive one is a "gold standard" (or at least better), the disagreement acts as a proxy for the cheap sensor's error rate. By minimizing these proxy errors relative to cost, we can converge on an optimal stopping policy.
Learning from Disagreement
To turn this intuition into an algorithm, researchers have adapted classic online learning strategies:
- Upper Confidence Bounds (UCB): In Online Algorithm for Unsupervised Sensor Selection, the authors use disagreement rates to build confidence intervals around the estimated error of each sensor. They prove that this approach achieves "sublinear regret," meaning the algorithm's performance eventually catches up to a strategy that knew the true error rates from the start.
- Thompson Sampling: Arun Verma and colleagues developed USS-TS in Thompson Sampling for Unsupervised Sequential Selection. By maintaining a posterior distribution over the sensors' performance based on observed disagreements, this method often converges faster than UCB-based approaches in practice.
- Contextual Information: Real-world decisions often depend on the specific case at hand (e.g., a patient's age or symptoms). Online Algorithm for Unsupervised Sequential Selection with Contextual Information extends the framework to handle these "contexts," allowing the system to learn different optimal sequences for different types of inputs.
The Boundaries of Learnability
The feasibility of this entire research direction hinges on the structural relationship between sensors. As Arun Verma notes in Sequential Decision Problems with Weak Feedback, there is a fundamental "boundary" for unsupervised learning.
If the dominance property is violated—for example, if a more expensive medical test is actually less reliable for certain patients, or if sensors have independent, non-overlapping failure modes—the learner can no longer use disagreement as a reliable signal. In these cases, it becomes mathematically impossible to minimize regret without external labels.
This framework has significant implications for Cost-Sensitive Medical Diagnosis (CSMD). As demonstrated in Unsupervised Online Feature Selection for Cost-Sensitive Medical Diagnosis, these algorithms can help hospitals automatically refine diagnostic protocols, ensuring that expensive tests are only used when the cheaper, "dominated" tests are likely to be insufficient.