PaperlayerView exact revision on arXiv

Source-linked AI summary

Controlled Sensing for Multihypothesis Testing

Sirin Nitinawarat, George Atia, Venugopal V. Veeravalli

arXiv:1205.0858v6cs.IT

TL;DR

The paper asks how observation-control policies should be designed for multihypothesis testing in fixed-sample and sequential settings. It analyzes open-loop and causal policies, develops Chernoff-based tests and bounds, and shows binary stationary open-loop optimality, possible causal gains for multiple hypotheses, and strong sequential asymptotic optimality. The results also distinguish when past information and randomization matter.

  • Problem

    The paper studies how to jointly design observation-control, decision, and sequential stopping rules for multihypothesis testing across fixed-sample and sequential settings.

  • Method

    The paper analyzes open-loop and causal control policies and develops Chernoff-information- and KL-distance-based tests, including modified sequential Chernoff procedures.

  • Results

    The paper shows stationary open-loop control is asymptotically optimal for binary fixed-sample testing, causal control can outperform open-loop control for multiple hypotheses, and modified Chernoff tests are strongly asymptotically optimal sequentially.

  • Takeaways & Limitations

    Past information is crucial for binary sequential performance but superfluous for binary fixed-sample performance, while randomization is unnecessary in fixed-sample control and can facilitate sequential policy structure.

Abstract

from arXiv · show

The problem of multiple hypothesis testing with observation control is considered in both fixed sample size and sequential settings. In the fixed sample size setting, for binary hypothesis testing, the optimal exponent for the maximal error probability corresponds to the maximum Chernoff information over the choice of controls, and a pure stationary open-loop control policy is asymptotically optimal within the larger class of all causal control policies. For multihypothesis testing in the fixed sample size setting, lower and upper bounds on the optimal error exponent are derived. It is also shown through an example with three hypotheses that the optimal causal control policy can be strictly better than the optimal open-loop control policy. In the sequential setting, a test based on earlier work by Chernoff for binary hypothesis testing, is shown to be first-order asymptotically optimal for multihypothesis testing in a strong sense, using the notion of decision making risk in place of the overall probability of error. Another test is also designed to meet hard risk constrains while retaining asymptotic optimality. The role of past information and randomization in designing optimal control policies is discussed.

I. INTRODUCTION

The paper studies controlled sensing for multihypothesis testing, where controls shape observations, in both fixed-sample and sequential settings. It develops asymptotically optimal joint designs of control, decision, and, sequentially, stopping rules, extending prior work across information structures and risk criteria.

  • Problem formulation: Controlled sensing differs from traditional control because the control affects observations rather than the evolution of the underlying state.The goal is accurate inference through shaping observation quality.
  • Problem formulation: The paper formulates hypothesis testing with observation control as jointly designing a control policy and decision rule, with a stopping rule added in the sequential setting.The controller chooses actions that shape observation quality before the hypothesis decision; sequential control can also determine when to stop.
  • Problem formulation: The paper analyzes both fixed sample size and sequential settings for multiple hypotheses under a Markovian observation-control model.In the sequential setting, the controller adaptively chooses whether to continue collecting observations.
  • Contributions: For fixed sample size, the paper characterizes open-loop performance, derives causal-control bounds, and shows with three hypotheses that causal control can strictly outperform open-loop control.The causal policy may depend on past measurements and controls, whereas open-loop control does not.
  • Relationship to prior work: The paper distinguishes controlled sensing from related problems where the controller knows the hypothesis or has only finitely many past outputs available.Its causal policies can depend on the entire past observation history, and the controller is not assumed to know the true hypothesis.
  • Contributions: For sequential testing, the paper establishes strong asymptotic optimality for a modified Chernoff test using decision-making or frequentist risks and constructs a hard-risk-constrained asymptotically optimal variant.These results extend earlier sequential controlled-sensing work beyond its assumptions and risk formulation.

III. FIXED SAMPLE SIZE SETTING

The fixed-sample analysis compares open-loop and causal control policies through maximal-error exponents. For binary testing, stationary open-loop control is asymptotically optimal, while the multihypothesis results characterize open-loop performance and provide causal-control bounds and constructions.

  • Control policies: Open-loop controls are independent of observations, whereas causal controls may be randomized functions of past observations and past controls.The causal information pattern is more informative, so its optimal exponent is at least the open-loop exponent.
  • Problem setup: The fixed-sample problem uses a decision rule after n observations and evaluates the maximal error probability over hypotheses.Pure policies reduce the decision rule to a function of observations because controls are then determined by fixed sequences or observed histories.
  • Multiple hypothesis testing: For general multiple hypothesis testing, the paper characterizes the optimal open-loop error exponent and shows it is achievable by pure non-randomized control.The characterization optimizes over control distributions and pairs of distinct hypotheses.
  • Multiple hypothesis testing: The paper proposes a causal policy based on a suitable Chernoff information and derives lower and upper bounds on the optimal causal exponent.The bounds apply to any number of hypotheses, while the lower-bound result has a finite-observation-alphabet condition.
  • Binary hypothesis testing: For binary testing, the optimal error exponent equals the maximum Chernoff information over controls.A pure stationary open-loop sequence using a maximizing control achieves this exponent.

B. The Case of Multiple Hypothesis Testing (M > 2)

For more than two hypotheses, the paper develops open-loop and causal-control analyses beyond the binary case. It proposes a Chernoff-information-based causal policy, proves general exponent bounds, and identifies conditions under which causal control can improve on open-loop control.

  • Open-loop control: For M > 2, the open-loop exponent is characterized by optimization over control distributions and pairs of distinct hypotheses.The result applies beyond finite observation alphabets under the paper’s general assumptions.
  • Causal control: The paper frames causal-control performance for M > 2 as a harder characterization problem than open-loop performance.Causal controls may depend on past measurements and controls, creating a richer information pattern.
  • Performance comparison: Causal control can outperform open-loop control even with M = 3, and the paper’s causal exponent lower bound can be strictly larger than the open-loop exponent in an example.The paper also shows that pure control without randomization achieves the causal exponent bounds.
  • Causal control: The proposed causal policy estimates the maximum-likelihood hypothesis and selects the next control using a Chernoff-information criterion against the most competitive alternative.The policy follows a separation principle: online estimation is paired with a stationary deterministic mapping from posterior distributions to controls.
  • Scope conditions: The causal lower-bound theorem requires finite observation alphabets, whereas the upper bound and earlier results apply to arbitrary observation alphabets subject to the stated assumptions.For finite alphabets, the distributions under each hypothesis are assumed to have common support for each control.

IV. SEQUENTIAL SETTING

The sequential setting adaptively controls whether to continue sampling or stop and decide. The paper establishes strong asymptotic optimality for Chernoff-type tests, removes a technical assumption, and develops a hard-risk variant.

  • Sequential formulation: Sequential tests adaptively choose controls and stopping times from past observations and controls before making a final hypothesis decision.The test combines a causal control policy, a stopping time, and a decision rule.
  • Chernoff test: Under the technical distributional assumption, the Chernoff test is strongly asymptotically optimal when performance is measured by decision-making risk.This replaces overall error probability with a risk-based criterion.
  • Modified test: The modified Chernoff test removes the technical assumption required by the original test while retaining asymptotic optimality.Its control policy occasionally samples uniformly rather than always using the ML-index-based policy.
  • Control policy: Randomization in the causal control policy supports simultaneous minimization of expected stopping time under all hypotheses as error probabilities vanish.The policy samples the next control from a distribution determined by the current ML estimate.
  • Optimality criterion: Maximal-risk asymptotic optimality is stronger than the corresponding maximal-error-probability result.The paper states that the converse in terms of maximal risk implies the one in terms of maximal error probability, but not vice versa.

C. Asymptotically Optimal Test Meeting Hard Constraints on the Risks

The paper modifies the sequential Chernoff test to satisfy hard per-hypothesis risk constraints while preserving asymptotic optimality. An example then contrasts open-loop and causal fixed-sample control and shows the benefit of adaptive stopping sequentially.

  • Hard-risk test: The hard-risk test uses prior knowledge and hypothesis-dependent posterior thresholds instead of a single stopping threshold.The resulting test is shown to remain asymptotically optimal as all risks vanish.
  • Hard-risk test: For any positive risk bounds and any full-support prior, the modified test with the new stopping rule satisfies the stated risk constraints and remains asymptotically optimal.The theorem establishes the result for every hypothesis and concludes asymptotic optimality.
  • Fixed-sample example: In the three-hypothesis example, a causal control policy can achieve a larger error exponent than the best open-loop control.The example uses three hypotheses, binary observations, and three controls corresponding to three sensor locations.
  • Fixed-sample example: The example’s causal lower bound matches the achievable error exponent obtained by the proposed policy.The matching result follows after selecting the control as a function of the posterior ordering.
  • Sequential comparison: Sequential performance exceeds the fixed-sample causal exponent because adaptive stopping adds the ability to stop based on past observations.The paper identifies the sequential quantities governing asymptotically optimal performance and notes the resulting numerical comparison.

VI. DISCUSSION

Past information is central to sequential optimal control because it forms the ML estimate used to select maximizing distributions and controls.

  • Discussion: Sequential control uses past observations to form the ML estimate, which selects the maximizing distribution and control value.The relevant maximizers can depend on the accumulated information.

VII. CONCLUSIONS

The paper characterizes asymptotically optimal control for multihypothesis testing in fixed-sample and sequential settings. It shows that causal control can improve fixed-sample performance, while sequential control exploits decision-making risk and can satisfy hard risk constraints.

  • For binary fixed-sample testing, the optimal error exponent equals the maximum Chernoff information over controls.
  • For binary fixed-sample testing, a pure stationary open-loop policy is asymptotically optimal even among causal policies.
  • For multiple fixed-sample hypotheses, the paper derives open-loop characterizations and causal-control lower and upper bounds.
  • An example shows that the proposed causal policy strictly outperforms the best open-loop policy.
  • In sequential testing, a modified Chernoff test is strongly asymptotically optimal under decision-making risk, and another test satisfies hard risk constraints while retaining asymptotic optimality.
  • Past information is crucial sequentially but superfluous for binary fixed-sample asymptotic performance, while randomization is unnecessary fixed-sample and can facilitate sequential policy structure.

APPENDIX

The appendix develops achievability and converse arguments for fixed-sample error exponents under open-loop and causal control. The proof uses maximum-likelihood decisions, empirical control distributions, pairwise hypothesis comparisons, and finite-horizon dynamic programming.

  • A maximum-likelihood decision rule is used to establish achievable error exponents for fixed control sequences.
  • Empirical distributions of deterministic open-loop control sequences approximate arbitrary control distributions and support the achievability argument.
  • The converse analyzes every hypothesis pair using likelihood-based inequalities and martingale stability under causal policies.
  • For open-loop policies, the empirical control distribution is independent of the hypothesis pair, while the optimizing Chernoff parameter may depend on that pair.
  • For fixed sample size, deterministic causal control suffices because the finite-horizon optimization can be formulated using the posterior as a sufficient statistic and solved by dynamic programming.

2) Proof of Theorem 2:

The proof of Theorem 2 establishes a causal-control exponent bound by reducing multihypothesis testing to binary pairwise tests and separately proving upper and lower bounds.

  • A multihypothesis test induces a binary test for any pair of hypotheses using the same control policy.
  • The upper bound follows by applying the binary converse argument to every ordered pair of hypotheses and minimizing over pairs.
  • The lower-bound proof relies on a lemma involving non-point-mass distributions and then takes a limit as the auxiliary parameter tends to zero.
  • The achievability construction uses a control selected from a mismatched posterior model.

3) Proof of Lemma 1:

The lemma proof constructs a posterior-based mismatched model, specifies likelihood and posterior updates, and analyzes maximum-likelihood error probabilities under the resulting control policy.

  • The construction begins with posterior probabilities over hypotheses under a uniform prior and defines a mismatched observation model.
  • The proof tracks likelihood ratios and uses the maximum-posterior hypothesis as the maximum-likelihood decision at the terminal time.
  • The error analysis bounds the real-model error probability using the mismatched model and a negative auxiliary exponent parameter.
  • The control is selected as u_k = u*(ν_k−1), making the action a function of the preceding posterior.
  • Full support of the constructed model ensures posterior distributions retain full support throughout the argument.

B. Proofs of Results in Section IV

The proofs establish asymptotic guarantees for the proposed tests by controlling likelihood-ratio concentration, ML-estimate convergence, and risk decay. Without Condition (12), sparse uniform-control sampling preserves asymptotic optimality despite weakening exponential to polynomial decay in key probabilities.

  • Proof of supporting lemmas: The proof of Lemma 2 uses Lemma 3 and Markov's inequality to establish the required risk bound for tests with vanishing maximal risk.The argument applies for every 0 < ρ < 1.
  • Achievability without Condition (12): Condition (12) prevents poor controls under an incorrect ML estimate and accelerates convergence of the ML estimate to the true hypothesis.Without it, convergence may fail or may be too slow.
  • Achievability without Condition (12): Sparse uniform-control sampling guards against incorrect ML estimation by forcing uniformly distributed controls at times k = ⌈a^l⌉.At other times, the policy remains based on the ML hypothesis.
  • Achievability without Condition (12): The modified policy achieves the target asymptotic bound because likelihood ratios concentrate around the denominator in (18), whose minimum corresponds to the closest alternative hypothesis.The proof decomposes the likelihood ratio and controls the probability of non-concentration.
  • Achievability without Condition (12): The proof obtains exponential decay for one probability sequence and polynomial decay for another, with arbitrarily high polynomial degree γ when a is sufficiently close to 1.This decay is sufficient to complete the asymptotic expected-sample-size bound in (18).

3) Proof of Theorem 4:

The proof of Theorem 4 bounds the proposed test's risks and compares its stopping rule with a single-threshold alternative. The alternative is asymptotically optimal, while its stopping time dominates the proposed test's stopping time.

  • Proof of Theorem 4: The risks satisfy R_j ≤ R̄_j for every hypothesis j.This follows directly from the definition of R_j in (15).
  • Proof of Theorem 4: A second test replaces the proposed stopping rule with a single threshold while retaining the same control and decision rules.Its stopping time N′ is always at least as large as the proposed test's stopping time N.
  • Proof of Theorem 4: The single-threshold test is asymptotically optimal for every hypothesis as the risk bounds converge to zero.The full-support assumption makes the single threshold diverge as max R̄_i → 0.
  • Proof of Theorem 4: The proof derives a uniform risk bound for every hypothesis using the dominance N ≤ N′ almost surely and inequality (72).The bound holds for a suitable constant K′.
Loading 1205.0858v6…