Sequential Learning without Feedback
This addresses a critical challenge in security and healthcare systems where sensor selection must be optimized without feedback, though it is incremental as it builds on existing partial monitoring and bandit frameworks.
The paper tackles the problem of unsupervised sensor selection (USS) in sequential learning without feedback, aiming to optimize accuracy and costs when ground truth annotations are unavailable. They propose the weak-dominance condition, verify it on real datasets, and develop polynomial-time algorithms that achieve sublinear regret.
In many security and healthcare systems a sequence of features/sensors/tests are used for detection and diagnosis. Each test outputs a prediction of the latent state, and carries with it inherent costs. Our objective is to {\it learn} strategies for selecting tests to optimize accuracy \& costs. Unfortunately it is often impossible to acquire in-situ ground truth annotations and we are left with the problem of unsupervised sensor selection (USS). We pose USS as a version of stochastic partial monitoring problem with an {\it unusual} reward structure (even noisy annotations are unavailable). Unsurprisingly no learner can achieve sublinear regret without further assumptions. To this end we propose the notion of weak-dominance. This is a condition on the joint probability distribution of test outputs and latent state and says that whenever a test is accurate on an example, a later test in the sequence is likely to be accurate as well. We empirically verify that weak dominance holds on real datasets and prove that it is a maximal condition for achieving sublinear regret. We reduce USS to a special case of multi-armed bandit problem with side information and develop polynomial time algorithms that achieve sublinear regret.