Adaptive Active Hypothesis Testing under Limited Information
We consider the problem of active sequential hypothesis testing where a Bayesian decision maker must infer the true hypothesis from a set of hypotheses. The decision maker may choose for a set of actions, where the outcome of an action is corrupted by independent noise. In this paper we consider a special case where the decision maker has limited knowledge about the distribution of observations for each action, in that only a binary value is observed. Our objective is to infer the true hypothesis with low error, while minimizing the number of action sampled. Our main results include the derivation of a lower bound on sample size for our system under limited knowledge and the design of an active learning policy that matches this lower bound and outperforms similar known algorithms.
The paper studies the problem of active hypothesis testing with limited information. More specifically, denoting the probability of ‘correct indication’ by q(j,w) if the true hypothesis is j and the chosen action is w, they assume that q(j,w) is bounded below by \alpha(w) for all j, and this quantity is available to the controller. They first study the incomplete-bayesian update rule, where all q’s are replaced with alpha’s, hence approximate, and show that with this IB update rule, one needs at least O(log(1/\delta)) to achieve (1-\delta) posterior error probability. Then, they show that their gradient-based policy achieves the order-wise optimal sample complexity. 
I have a few technical questions. 
On the upper bound: The authors claim that the upper bound is obtained by considering the worst case scenario where q(w,j) = \alpha(w) for every w if j is the true hypothesis. If that’s the case, how is different the analysis given in this paper from that for Bayesian update case? (If my understanding is correct, q(w,j) = \alpha(w) implies IB update rule = Bayesian update rule.) Further, what can happen in reality is that q(w,j) is arbitrarily close to 1, and alpha(w) is arbitrarily close to 1/2. In this case, can the upper bound provide any guarantee? 
On the lower bound: Can this bound recover the existing lower bounds for the case of complete information? 
On simulation results: It will be great if the authors can present the lower & upper bounds on E[T] and compare them with the simulation results.