{'fraction_non_alphanumeric': 0.052305214415139925, 'fraction_numerical': 0.0075699617475337225, 'mean_word_length': 4.038750253601136, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Active Search with a Cost for Switching Actions

Active Sequential Hypothesis Testing (ASHT) is an extension of the classical sequential hypothesis testing problem with controls. Chernoff (Ann. Math. Statist., 1959) proposed a policy called Procedure A and showed its asymptotic optimality as the cost of sampling was driven to zero. In this paper we study a further extension where we introduce costs for switching of actions. We show that a modification of Chernoff's Procedure A, one that we call Sluggish Procedure A, is asymptotically optimal even with switching costs. The growth rate of the total cost, as the probability of false detection is driven to zero, and as a switching parameter of the Sluggish Procedure A is driven down to zero, is the same as that without switching costs.


I. INTRODUCTION
Active Sequential Hypothesis Testing (ASHT) is a generalization of the classical sequential hypothesis testing problem where, at each observation instant, the decision maker has a choice that controls the type or quality of the observation. For example, in a cognitive radio setting, at each observation instant, the decision maker must select exactly one frequency band, of the several available, for observation. Another example is visual search where, at each time instant, one can focus only on a small subset of the entire visual field, and one must choose this subset for information gathering. ASHT can be used as a modeling tool for many other applications apart from visual search and cognitive radio, such as anomaly detection, medical diagnostics, etc.
Chernoff [1] studied ASHT in the context of designing optimal experiments. His performance metric was the total cost of sampling, which is propotional to delay, plus a penalty for false detection. Chernoff proposed a policy, the so-called Procedure A, and showed its asymptotic optimality as the cost of sampling went to zero. Procedure A maintains a posterior distribution on the set of hypotheses and, at each instant, selects actions according to the hypothesis with the highest posterior probability.
In this paper we study a further extension of ASHT where, in addition to the average decision delay, we also penalize switching of actions. The current extension is motivated by visual search where a switch in action implies a change in the location of one's focus and a fast movement of the eyes (a saccade), which has an associated biological cost that translates to a delay cost.
We propose a modified Procedure A where the next action depends on the current posterior and the previous action, whereas in Procedure A the next action depends only on the current posterior. The modification is simple: at a given decision instant, if an independently generated Bernoulli random variable turns up "1", then the next action is taken as per Procedure A, else the current action is continued. We call this the Sluggish Procedure A.
There has been a flurry of recent activity extending Chernoff's work in other directions. In a series of works, Naghshvar and Javidi [2], [3], [4], [5], [6] studied ASHT from a Bayesian cost minimization perspective. The total cost was the sum of decision delay and a penalty for false detection. They proposed policies, similar to Chernoff's Procedure A, identified bounds on the total cost, and established their proposed policies' asymptotic optimality in the same asymptotic regime as Chernoff's 1 . Nitinawarat et al. [7] studied active hypothesis testing in fixed sample size and in sequential settings. They also minimize decision delay subject to a constraint on the conditional probability of false detection. When these conditional probabilities of false detection are driven to zero, the resulting asymptotic regime is the same as Chernoff's. In this asymptotic regime, they obtained results similar to those of Chernoff's but under milder assumptions. They also prove a stronger asymptotic result based on the "risk associated with a decision". Nitinawarat and Veeravalli [8] extended ASHT to Markovian observations and non-uniform costs on actions. Recently Cohen and Zhao [9] studied ASHT from an anomaly detection perspective. They showed that, in their setting, a simple deterministic policy was optimal. This is in contrast to random policies advocated in the other works. None of the above works consider costs associated with a change in action.
Our contribution: We show that the aforementioned modification of Chernoff's Procedure A, the Sluggish Procedure A, is asymptotically optimal even with switching costs. Further, we show that the growth rate of the total cost, as the probability of false detection is driven to zero, and as a switching parameter of the Sluggish Procedure A is driven to zero, is the same as that without switching costs.

II. THE ASHT ABSTRACTION
In this section, we describe our mathematical model for ASHT and collect all the relevant theoretical results.
A. The ASHT Model 1) The model description: Let us begin by setting up some notation.
Let H i , i = 1, 2, . . . , M denote the M hypotheses of which exactly one, denoted H, holds true. We do not assume a prior on the hypotheses. Let A be the set of all possible actions which we take as finite: |A| = K < ∞. Let X be the observation space. Let (X n ) n≥1 and (A n ) n≥1 denote the observation process and the control process respectively. We write X n for (X 1 , . . . , X n ) and similarly A n for (A 1 , . . . , A n ). We also write P(A) for the set of probability distributions on A.
A policy π is a sequence of action plans that at time n looks at the history X n−1 , A n−1 and prescribes a composite action that is either (stop, δ) or (continue, λ) as explained next. If the composite action is (stop, δ), then the controller stops taking further samples (or retires) and indicates δ as its decision on the hypothesis; δ ∈ {1, 2, . . . , M }. If the composite action is (continue, λ), the controller picks the next action A n according to the distribution λ ∈ P(A). Let τ (π) be the stopping time Consider a policy π. Conditioned on action A n and the true hypothesis H, we assume that X n is conditionally independent of previous actions A n−1 = (A 1 , A 2 , . . . , A n−1 ), previous observations X n−1 = (X 1 , X 2 , . . . , X n−1 ), and the policy. Let q a i be the conditional probability density function, with respect to some reference measure µ, of the observation X n under action a when H = H i . Let D(q a i q a j ) denote the relative entropy 2 between the conditional probability measures associated with the observations under hypothesis H i and under hypothesis H j , upon action a. Denote by unif(A) the uniform distribution on A. Let q π i (x n , a n ) be the probability density function of observations and actions (x n , a n ) till time n, with respect to the common reference measure µ ⊗n ×unif(A) ⊗n . Let Z π i (n) denote the log-likelihood process of hypothesis H i , i.e., Going forward, for ease of notation, we drop the superscript π while describing q π i , Z π i , and other variables, but their dependence on the underlying policy should be kept in mind, and the policy under consideration will be clear from the context. Define Z(n) = (Z 1 (n), Z 2 (n), . . . , Z M (n)). Let Z ij (n) denote the log-likelihood ratio (LLR) process of H i with respect to H j , i.e., .
2 By an abuse of notation, we use the densities of the probability measures as the arguments of the relative entropy function.
Let E i denote the conditional expectation and let P i denote the conditional probability measure under H = H i . (More formally, these should be represented E π i and P π i . But as done above, we omit the superscript π.) Given an error tolerance vector α = (α 1 , α 2 , . . . , α M ) with 0 < α i < 1, let Π(α) be the set of policies These are policies that meet a specified tolerance for the conditional probability of false detection. We define α := max i α i .
We define λ i to be the best mixed action that guards H i against its nearest alternative, i.e., λ i ∈ P(A) such that If there are several maximizers, pick one arbitrarily. Further, define Let A ij = {a ∈ A : D(q a i q a j ) > 0}, the set of all actions that can differentiate hypothesis H i from hypothesis H j . From well known properties of relative entropy, we obtain A ij = A ji .
2) Assumptions: Throughout, we make the following assumptions.
Assumption (I) implies that D(q a i ||q a j ) < ∞, which in turn ensures that no single observation can result in a reliable decision. Assumption (I) is used in proving the lower bound on the expected number of samples needed to satisfy the tolerance criterion. This is also assumed by Chernoff [1] and Nitinawarat et al. [7].
Assumption (IIa) ensures that for any distinct i and j, there is at least one control that can help distinguish the hypotheses H i from H j . If A ij = ∅ for some i and j, it will be impossible to distinguish them from each other. Assumption (IIb) is a stronger assumption than, and implies, Assumption (IIa). Assumption (IIb) ensures that if actions are taken according to any of the λ k in (2) then, for any two hypotheses H i and H j , there is a positive probability of choosing an action that can discriminate them. We shall use Assumption (IIb) in the achievability proofs of our policies. It allows for easier proofs for our policies, and makes the presentation simpler. However one can work with Assumption (IIa) as well, and construct asymptotically optimal policies, with minor modifications to our policies. We will describe the modifications later in this section.
3) Switching cost and total cost: The costs are as follows.
Switching Cost: Let g(a, a ) denote the cost of switching from action a to action a . We assume g(a, a ) ≥ 0 ∀a, a ∈ A and g(a, a) = 0.
Define g max = max a,a g(a, a ). We also assume g max < ∞.
Total cost: For a policy π ∈ Π(α), the total cost C(π) is taken to be the sum of the stopping time (delay) and the net switching cost, i.e.,

4) Asymptotics:
We shall be interested in the asymptotics of the minimum expected total cost E i [C(π)], minimized over policies in Π(α), as ||α|| → 0. Note that there are M such conditional expected total costs, one for each hypothesis.

B. Results on the ASHT Model
We collect all the main results in this section. We first identify a lower bound.
1) The converse -Lower bound: The following proposition gives a lower bound for the expected conditional stopping time, given hypothesis H = H i , for all policies belonging to Π(α).
where D i is given in (3).
Proof: Since only expected time to stop is considered, proof of [1, Th. 2, p. 766] applies.
We then have the following corollary.
2) Achievability -A modification to Chernoff's Procedure A: Chernoff [1] proposed a policy termed Procedure A and showed that it has asymptotically optimal expected decision delay. We now describe Procedure A.
Policy Procedure A: π P A (L) Fix L > 0. At time n: • Let θ(n) = arg max i Z i (n). Ties are resolved uniformly at random. i.e., • If Z θ(n),j (n) ≥ log ((M − 1)L) for all j = θ(n) then the test retires and declares H θ(n) as the true hypothesis.
We now describe a modified policy that can be made as close as one wishes to being asymptotically optimal in the presence of switching costs. We introduce a switching parameter η, 0 < η ≤ 1, which determines the maximum transition rate out of a given action. When η = 1, we will have the original Procedure A. When η approaches zero, the rate of jumping out of the current action approaches zero.
At time n: • Let θ(n) = arg max i Z i (n). Ties are resolved uniformly at random.
, then the test retires and declares H θ(n) as the true hypothesis.
We also consider two variants of π SA (L, η) which are useful in the analysis.
• Policy π i SA (L, η): This is the same as π SA (L, η), but stops only at decision i when min j =i Z ij (n) ≥ log(L(M − 1)). • Policyπ SA (η): This is the same as π SA (L, η), but never stops, and hence L is irrelevant.
Under a fixed hypothesis H = H i , and the triplet of policies (π SA (L, η), π i SA (L, η),π SA (η)), it is easily seen that there is a common underlying probability measure with respect to which the processes (X n , A n ) n≥1 associated with the three policies are naturally coupled, with only the stopping times being different. Under this coupling, the following are true: Policy π SA (L, η) is designed to stop only when the posteriors suggest a reliable decision. This is formalized now.
See Appendix IV-A for a proof. As a consequence we have π SA (L, η) ∈ Π(α) if α i ≥ 1 L ∀i. We now state the timedelay performance of the policy π SA (L, η). Theorem 4. Assume (I) and (IIb). Consider the policy π SA (L, η). The expected time to make a decision, for each i, satisfies See Appendix IV-B for a detailed proof. This result will be crucial because the policy π SA (L, η), despite its sluggishness induced by η, remains asymptotically optimal when only the stopping time τ (π SA (L, η)) is considered as cost. We now leverage this to show that, if η is sufficiently small, π SA (L, η) is near optimal when switching costs are also taken into account.
Proposition 5. Assume (I) and (IIb). Consider the policy π SA (L, η). We then have, for each i, Proof: We can write the following chain of inequalities.
In the above chain, the penultimate equality holds because of Wald's equation [10]. Dividing by log L, letting L → ∞, and using Theorem 4, we see that (9) holds.
3) Asymptotic optimality: Proposition 1 and Proposition 5 show that, when the conditional probability of false detection is driven to zero, the proposed policy π SA (L, η) has nearly the same growth rate for cost as an asymptotically optimal policy without switching costs. We now make the above statement precise. The parameter η should be suitably chosen to get sufficiently close to asymptotic optimality. Theorem 6. Assume (I) and (IIb). Consider a sequence of vectors (α (n) ) n≥1 , where α (n) is the n th tolerance vector, such that lim n→∞ α (n) = 0 and for some B. Then, the sequence of policies π SA (L n , η) with log L n = − log min k α (n) k belongs to Π(α (n) ). Furthermore, for each i, Proof: The fact that π SA (L n , η) ∈ Π(α (n) ) is evident from Proposition 3, and 1 Ln ≤ α n k , k = 1, 2, · · · , n. We then have the following chain of inequalities: The first inequality follows from Proposition 1. The next equality follows from the fact that lim n→∞ | log α (n) | log Ln = 1, which in turn is true due to the assumption (11). The third inequality follows because π SA (L n , η) is one specific policy in Π(α n ). The last inequality follows from Proposition 5 after letting η ↓ 0. Consequently, all inequalities must be equalities.

C. Discussion on Assumption (IIb)
Chernoff's proof of the asymptotic optimality of Procedure A was proved under a stronger assumption than Assumption (IIb), namely, Chernoff required D(q a i q a j ) > 0 ∀a and for all pairs i = j.
Assumption (IIb) ensures that, at all times, and for any pair of hypotheses i and j, i = j, there is a positive probability of choosing an action that can distinguish the two hypotheses. This suffices for Chernoff's proofs to go through. Specifically, we shall use Assumption (IIb) to prove the exponential decay result in Proposition 11. Nitinawarat et al. [7] proposed a modified Procedure A that sampled actions randomly at intervals ν l l≥1 , ν > 1, and showed that their proposed policy is asymptotically optimal under the weaker Assumption (IIa). The random sampling enabled them to obtain a polynomial decay counterpart of Proposition 11 of Appendix. Recently, Cohen and Zhao [9] claimed the asymptotic optimality of Procedure A under the weaker Assumption (IIa) for an active anomaly detection problem, which is a specific ASHT problem. We conjecture that Chernoff's Procedure A is asymptotically optimal under the weaker Assumption (IIa) for all ASHT problems. A proof of this claim has remained elusive. Nevertheless, policies whose performances are provably arbitrarily close to the optimum can be designed. We make the above claim precise in the next proposition. lim We omit the proof because the needed modifications to the proof of Theorem 4 are straightforward. Policy {π (L)} can be constructed as a variant of Procedure A that, at each instant n, chooses an action according to unif(A) with probability or as per (6) with probability (1 − ). Thus, at the cost of a small penalty, we can design nearly asymptotically optimal policies under the weaker Assumption (IIa). A similar argument holds true with switching costs, just as Theorem 4 is extended in Theorem 6, albeit with a corresponding but arbitrarily small increase in the total cost. Again, we omit the proof of this claim. Hence Assumption (IIa) suffices for the asymptotic growth rate to be 1 Di .

III. CONCLUSION
We studied active sequential hypothesis testing (ASHT) with switching costs. We proposed a modification to Chernoff's Procedure A that can be made to approach the asymptotic performance of Procedure A. The proposed algorithm merely slows down the switching of actions via an i.i.d. Bernoulli modulation process. The growth rate of total cost, as the probability of false detection is driven to zero, and as the switching parameter η is driven to zero, is the same as that without switching costs. We will now show some desirable properties of the loglikelihood ratio processes under the policy π SA (L, η). These properties are analogous to those of classical sequential hypothesis testing, but their analyses are more involved because actions introduce 1) dependency in the log-likelihood ratio increments, and 2) the increments are no longer identically distributed. The properties we will establish will be useful in forthcoming proofs.
Define ∆Z ji (n) = Z ji (n) − Z ji (n − 1). We then have ∆Z ji (n) = −∆Z ij (n). Here, ∆Z ji (n) is the increment in the process associated with the log-likelihood ratio of H j with respect to H i at time n. We now show that under Assumptions (I) and (IIb), and under policy π SA (L, η), the log-likelihood ratio processes are well behaved in the following sense: the log-likelihood ratio of the true hypothesis H i with respect to any other hypothesis H j has a positive drift. This will be made precise in Proposition 11. Towards that, we first establish the following lemmas.
Proof: The following sequence of inequalities hold: The strict inequality in (16) follows from Hölder's inequality and the fact that a ∈ A ij implies q a i and q a j are not linearly related.
The above result was obtained by conditioning on the action A n to lie in the desirable set A ij . The result is independent of the underlying policy, because when conditioned on the current action A n , the observation is independent of the policy.

Proof:
The following sequence of inequalities hold as described after the last inequality.
Equality (18) holds because conditioned on A n = a, ∆Z ij (n) is independent of the remaining history. Inequality (19) holds because, when a / ∈ A ij , we have ∆Z ij (n) ≡ 0. The penultimate inequality is a consequence of the fact that, under π SA (L, η), one will choose an action a ∈ A ij with probability at least ηβ.
We now proceed to show an inequality analogous to the Chernoff bound for the log-likelihood ratio. In classical sequential hypothesis testing, due to independence of samples across time, the expectation of the likelihood ratio can be split as the product of the expectation of the likelihood ratio increments, as follows: The same decomposition is not valid in ASHT because actions introduce dependency in the likelihood ratio increments across time. However, we can obtain an upper bound of the product form.
Proof: Once again, we proceed through the chain of inequalities all of which are now self-evident: where the last inequality follows by induction.
We now show an exponential decay property of the loglikelihood process which primarily stems from the anticipated negative drift in Z ji (n) for j = i. Let us alert the reader that in the following Proposition we deal with Z ij (n) = −Z ji (n).
Proposition 11. Assume (I) and (IIb). Consider policỹ π SA (η). Fix i. There exist constants C K > 0 and γ > 0 such that C K is independent of i, but γ may depend on i.
Proof: This follows from the previous lemmas via the following : where max j =i ρ ij (s) = e −γ , and C K = M e sK . The inequality in (22) is due to the union bound, the inequality in (23) is due to Chernoff's bound with 0 < s < 1, and the inequality in (24) is due to Lemma 10. We now show that under the hypothesis H = H i , the θ(n) process eventually settles at i. Indeed we show something stronger. Let us define the time at which θ(n) meets its eventuality of settlement at i. This random variable has a tail that decays exponentially fast, as shown next.
Lemma 12. Assume (I) and (IIb). Consider policyπ SA (η). Fix i. Then there exist C > 0 and b > 0, both finite and possibly dependent on i, such that Proof: By the union bound The assertion now follows from Proposition 11. Thus far we have considered the policyπ SA (η) which never stops. We now show that the policy π SA (L, η) stops in finite time.
Proof: We consider π i SA (L, η) for analysis. Recall that τ (π SA (L, η)) ≤ τ (π i SA (L, η)), and hence it is sufficient to show that From Proposition 11, we know that, for a suitable constantC, Since this bound is summable, by the Borel-Cantelli lemma, which is stronger than the assertion (27). Propositions 11 and 13 are the ones that will be used in the sequel.

A. Proof of Proposition 3
The proof relies on a standard change of measure argument. Let ∆ j denote the event that the policy π SA (L, η) declares H j as the true hypothesis.
The equality in the second step is valid as we have shown in Proposition 13 that the stopping time is finite with probability 1. The inequality (28) follows because under

B. Proof of Theorem 4: Achievability
We assume (I) and (IIb). All statements in this proof are under H = H i and under Sluggish Procedure A. We follow the proof technique of Chernoff [1, Lem. 2]. Chernoff's proof technique does not go through completely because unlike in Procedure A, the next action in Sluggish Procedure A is not conditionally independent of the previous action, given the current likelihood values. A similar issue was addressed by Nitinawarat and Veeravalli in [8], and we will adapt their proof technique to our setting.
Let us first setup some notation. Fix > 0. Define where λ i is as defined in (2). Let D i be as defined by (3), i.e., D i = min j =i D ij . Under the Sluggish Procedure A, the transition probability matrix T P (θ(n)) of the action process A n at time n is given by It is easy to verify that the stationary distribution associated with T P (θ(n)) is λ θ(n) . Define F k−1 := σ(X k−1 , A k−1 ), the σ-field generated by the random variables (X k−1 , A k−1 ).
We now upper bound the expected time to make a decision under Sluggish Procedure A as follows: To complete the proof, we will now show that for any > 0, the second term on the right-hand side of (30) goes to zero as L → ∞. Let us first analyse a term in the summation. We claim that each term decays exponentially with n. So the tail sum vanishes as L → ∞, becauseñ → ∞. This suffices to complete the proof of Theorem 4. We now proceed to prove the claim. Observe that Fix one j = i. (The same analysis holds for other j.) Then The third probability term is 0 if we choose an small enough such that n(D ij −2 ) > log(L(M −1)), for all n >ñ. We now proceed to show that the second term also decays exponentially to zero. Let T i be as defined in (25). For a suitably chosen , and we will soon indicate how to choose it, we have From Lemma 12, the second probability term on the righthand side decays exponentially with n. To show that the first probability term on the right-hand side decays exponentially with n, we use a technique of Nitinawarat and Veeravalli [8, (6.23)].
First, we indicate how to choose . Definẽ Since D ij is the λ i -weighted average of D(q a i q a j ), we havẽ C ≤ 0. Choose small enough so that˜ := + C > 0. We then have for some C > 0 and someb(˜ ) > 0. The second inequality follows from the fact thatC ≤ E i [∆Z ij (k)|F k−1 ] − D ij , for all k. The third inequality follows from the choice of˜ and the fact that n (C + ) + (n − n ) ≥ (n − n )˜ . P i is a new measure under which actions are taken according to Sluggish Procedure A but assuming θ(n) = i ∀n, and the observations are conditionally independent of past observations and actions, given the current action. Consequently, underP i , the action process A n is a stationary Markov Chain with transition probability matrix T P (i). By the ergodic theorem and concentration inequalities for Markov Chains [11], this term also decays exponentially with n, which is (32).