Active Sequential Hypothesis Testing
Preprint
Abstract
Consider a decision maker who is responsible to dynamically collect observations so as to enhance his information in a speedy manner about an underlying phenomena of interest while accounting for the penalty of wrong declaration. The special cases of the problem are shown to be that of noisy dynamic search and variable-length coding with feedback. Due to the sequential nature of the problem, the decision maker relies on his current information state to adaptively select the most "informative" action among the available ones. In this paper, using results in dynamic programming, lower bounds for the optimal total cost is established. The lower bounds characterize the fundamental limits on the maximum achievable information acquisition rate and the optimal reliability. Moreover, upper bounds are obtained via an analysis of two heuristic policies for dynamic selection of actions. It is shown that the first proposed heuristic achieves asymptotic optimality; where the notion of asymptotic optimality, due to Chernoff, implies that the relative difference between the total cost achieved by the proposed policy and the optimal total cost approaches zero as the penalty of wrong declaration (hence the number of collected samples) increases. The second heuristic is shown to achieve asymptotic optimality only in a limited setting such as the problem of variable-length coding with feedback. However, by considering the asymptotic where the number of hypotheses is also growing, this second heuristic is shown to achieve non-zero information acquisition rate, establishing a lower bound for the maximum achievable rate. In case of variable-length coding with feedback, this non-zero rate is shown to be maximum and the proposed heuristic is proved to achieve Burnashev's optimal reliability. This result extends the notions of capacity and optimal reliability to the context of sequential hypothesis testing.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Controlled Sensing for Multihypothesis TestingIEEE Transactions on Automatic Control, 2013
- Sensor Management: Past, Present, and FutureIEEE Sensors Journal, 2011
- Feedback in the Non-Asymptotic RegimeIEEE Transactions on Information Theory, 2011
- Discrimination of Two Channels by Adaptive Methods and Its Application to Quantum SystemIEEE Transactions on Information Theory, 2009
- A Simple Converse of Burnashev's Reliability FunctionIEEE Transactions on Information Theory, 2009
- Multihypothesis sequential probability ratio tests .I. Asymptotic optimalityIEEE Transactions on Information Theory, 1999
- Optimal search strategies in dynamic hypothesis testingIEEE Transactions on Systems, Man, and Cybernetics, 1995
- Hypothesis testing and information theoryIEEE Transactions on Information Theory, 1974
- Sequential transmission using noiseless feedbackIEEE Transactions on Information Theory, 1963
- The zero error capacity of a noisy channelIEEE Transactions on Information Theory, 1956