Online Algorithm for Unsupervised Sensor Selection
  In many security and healthcare systems, the detection and diagnosis systems
use a sequence of sensors/tests. Each test outputs a prediction of the latent
state and carries an inherent cost. However, the correctness of the predictions
cannot be evaluated since the ground truth annotations may not be available.
Our objective is to learn strategies for selecting a test that gives the best
trade-off between accuracy and costs in such Unsupervised Sensor Selection
(USS) problems. Clearly, learning is feasible only if ground truth can be
inferred (explicitly or implicitly) from the problem structure. It is observed
that this happens if the problem satisfies the 'Weak Dominance' (WD) property.
We set up the USS problem as a stochastic partial monitoring problem and
develop an algorithm with sub-linear regret under the WD property. We argue
that our algorithm is optimal and evaluate its performance on problem instances
generated from synthetic and real-world datasets.
