Active sequential hypothesis testing

Abstract

Consider a decision maker who is responsible to dynamically collect observations so as to enhance his information about an underlying phenomena of interest in a speedy manner while accounting for the penalty of wrong declaration. Due to the sequential nature of the problem, the decision maker relies on his current information state to adaptively select the most ``informative'' sensing action among the available ones. In this paper, using results in dynamic programming, lower bounds for the optimal total cost are 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 a noisy dynamic search. However, by considering the dependency on the number of hypotheses, under a technical condition, this second heuristic is shown to achieve a nonzero information acquisition rate, establishing a lower bound for the maximum achievable rate and error exponent. In the case of a noisy dynamic search with size-independent noise, the obtained nonzero rate and error exponent are shown to be maximum.

Published in at http://dx.doi.org/10.1214/13-AOS1144 the Annals of Statistics (http://www.imstat.org/aos/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (2)

• Asymptotically optimal multistage tests of simple hypotheses
• Controlled Sensing for Multihypothesis Testing

Cited by in corpus (54)

• Active Learning and CSI Acquisition for mmWave Initial Alignment
• Sequentiality and Adaptivity Gains in Active Hypothesis Testing
• Asymptotically Optimal Anomaly Detection via Sequential Testing
• Extrinsic Jensen-Shannon Divergence: Applications to Variable-Length Coding
• Optimal Index Policies for Anomaly Localization in Resource-Constrained Cyber Systems
• Rate and Detection-Error Exponent Tradeoff for Joint Communication and Sensing of Fixed Channel States
• Active Classification for POMDPs: a Kalman-like State Estimator
• Searching for Anomalies over Composite Hypotheses
• Collaborative Distributed Hypothesis Testing
• Noisy Bayesian Active Learning
• Covariance Matrix Estimation with Non Uniform and Data Dependent Missing Observations
• Feedback Communication Systems with Limitations on Incremental Redundancy
• Asynchronous Online Testing of Multiple Hypotheses
• Optimal Adaptive Strategies for Sequential Quantum Hypothesis Testing
• Anomaly Search with Multiple Plays under Delay and Switching Costs
• Utility Maximizing Sequential Sensing Over a Finite Horizon
• Active Sampling of Multiple Sources for Sequential Estimation
• Active inference and deep generative modeling for cognitive ultrasound
• Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration
• Nonmyopic View Planning for Active Object Detection
• Active Hypothesis Testing for Quickest Anomaly Detection
• A General Framework for Clustering and Distribution Matching with Bandit Feedback
• Optimal Stopping and Worker Selection in Crowdsourcing: an Adaptive Sequential Probability Ratio Test Framework
• Active Sampling for the Quickest Detection of Markov Networks
• Active Search with a Cost for Switching Actions
• Improving quantum state detection with adaptive sequential observations
• Myopic Policy Bounds for Information Acquisition POMDPs
• Sequential Hypothesis Test with Online Usage-Constrained Sensor Selection
• Greedy Approximation Algorithms for Active Sequential Hypothesis Testing
• Policy Design for Active Sequential Hypothesis Testing using Deep Learning
• Active Anomaly Detection in Heterogeneous Processes
• Information-Directed Random Walk for Rare Event Detection in Hierarchical Processes
• Construction and Analysis of Posterior Matching in Arbitrary Dimensions via Optimal Transport
• Joint source-channel coding with feedback
• Anomaly Detection in Hierarchical Data Streams under Unknown Models
• Adaptive Sensing Resource Allocation Over Multiple Hypothesis Tests
• Universal Scheme for Optimal Search and Stop
• Discriminative Learning via Adaptive Questioning
• Second-Order Asymptotics of Sequential Hypothesis Testing
• Seeing into Darkness: Scotopic Visual Recognition
• Partially Observed Markov Decision Processes. Problem Sets and Internet Supplement
• Cross-layer estimation and control for Cognitive Radio: Exploiting Sparse Network Dynamics
• Sequential Relevance Maximization with Binary Feedback
• Learning and Optimization with Submodular Functions
• Chernoff Sampling for Active Testing and Extension to Active Regression
• Controlled Sensing: A Myopic Fisher Information Sensor Selection Algorithm
• Anomaly Detection via Controlled Sensing and Deep Active Inference
• Learning to Detect an Odd Markov Arm
• Sequential anomaly detection with sampling constraints
• A label-efficient two-sample test
• Nonlinear POMDPs for Active State Tracking with Sensing Costs
• Active Anomaly Detection with Switching Cost
• Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees
• Change Acceleration and Detection