Sequential Testing

Suppose that we wish to learn a state

Z \in Z = {0, 1}^{n}

. At each time step

t

, we can choose

X^{t} \in X = {0, 1}^{n}

, and observe

\begin{matrix} (1) & Y^{t} = 1 (X^{t} \cdot Z > 0) \end{matrix}

(??)

A history is a sequence of $(X^{t}, Y^{t})$ pairs. A policy $π$ is a map from histories to $X$ . Given history $H$ , let $F (H)$ be the set of $Z$ that are consistent with $H$ . Define $T (π, Z)$ to be the number of tests run under policy $π$ when the state is $Z$ .

Extensions

Feedback -- for example, could be $X^{t} \cdot Z$ itself.
Decision space -- for example, could choose weights to apply.
Error tolerance -- cost of incorrect label.
Noise -- could incorporate false positives or negatives.

Sequential Testing

Nick Arnosti

2021/03/01

Extensions