Consider$n$random variables forming a Markov random field (MRF). The true model of the MRF is unknown, and it is assumed to belong to a binary set. The objective is to sequentially sample the random variables (one-at-a-time) such that the true MRF model can be detected with the fewest number of samples, while in parallel, the decision reliability is controlled. The core element of an optimal decision process is a rule for selecting and sampling the random variables over time. Such a process, at every time instant and adaptively to the collected data, selects the random variable that is expected to be most informative about the model, rendering an overall minimized number of samples required for reaching a reliable decision. The existing studies on detecting MRF structures generally sample the entire network at the same time and focus on designing optimal detection rules without regard to the data-acquisition process. This paper characterizes the sampling process for general MRFs, which is shown to be optimal in the asymptote of large$n$. The critical insight in designing the sampling process is devising an information measure that captures the decisions’ inherent statistical dependence over time. Furthermore, when the MRFs can be modeled by acyclic probabilistic graphical models, the sampling rule is shown to take a computationally simple form. Performance analysis for the general case is provided, and the results are interpreted in several special cases: Gaussian MRFs, non-asymptotic regimes, Chernoff’s rule for controlled (active) sensing, and the problem of cluster detection.

Mobile edge computing allows resource-constrained mobile devices to offload their computationally-intensive tasks to powerful devices at the edge of the network. Designing an optimal offloading strategy for deciding whether to execute a task locally or at an edge device has attracted much attention recently. The existing literature focuses mostly on settings with a single mobile device or a single edge device, making the results unsuitable for real-world situations. This paper considers a setting consisting of multiple non-cooperative mobile devices and multiple edge devices, and aims to design offloading policies that minimize the task drop rate as well as the execution delay without requiring information about the dynamics of the environment such as channel models and task arrival rates at mobile devices. This non-cooperative resource allocation problem is only partially observable to each mobile device. We propose a method to mitigate the partial observability and then apply a deep reinforcement learning-based policy that progressively learns the dynamics of the environment as well as the long-term consequences of decisions. Numerical results demonstrate that the proposed algorithm significantly reduces the task drop rate compared to existing offloading policies, while minimizing energy and computation cost of each mobile device.

This paper considers a sequence of random variables that undergo periods of transient changes at an unknown set of time instants, referred to as transient change-points. The objective is to constantly monitor the sequence in order to detect one of the change-points subject to a hard constraint on the detection delay, while in parallel, the rate of false alarms is controlled. This setting is fundamentally different from the conventional change-point detection problems, in which there exists at most one change-point that can be either persistent or transient. In this paper, the exact optimal decision rules are characterized. Furthermore, it is shown that in the special case that the objective is detecting a transient change-point at exactly the instant that a change occurs (i.e., no detection delay), the test reduces to the well-known Shewhart test. Numerical evaluations are also provided to assess the performance of the decision rules.

Multi-hypothesis testing, which is widely used in many domains for discerning the true model governing the data, is often studied in a fixed sample-size setting. In such settings, the data-acquisition and decision-making processes are decoupled and the data-acquisition policies are pre-specified. Motivated by the advantages of sequential sampling, this paper treats the inherently coupled problems of data-acquisition and decision-making for multi-hypothesis testing, where data-acquisition can be abstracted as selecting one possible sensing action from a finite set. It aims to devise the quickest detection strategy by characterizing the minimum number of samples required to make a reliable decision as well as designing the dynamic attendant decision rules for selecting the best actions. The setting in which the available control actions are co-dependent is considered, which is a major distinction from the existing literature. Specifically, the existing data-adaptive approaches lose their optimality guarantees for this problem as they fail to account for such dependence. A novel sampling strategy that incorporates the dependence of the control actions into its decision rules is proposed, and its optimality properties are established.

This paper considers a network of agents generating correlated data according to a known kernel. The correlation structure might undergo a change at an unknown time instant, where the post-change kernel is not fully known. Moreover, due to the data processing and communication costs, only a subset of agents can be observed at any time instant. The objective is to detect the change-point with minimum average delay, while the rate of false alarms is controlled. This paper proposes a coupled data acquisition and decision-making process for change detection and establishes its optimality properties.

Consider a set of random sequences, each consisting of independent and identically distributed random variables. Each sequence is generated according to one of the two possible distributions F0or F1with unknown prior probabilities (1 - ϵ) and ϵ, respectively. The objective is to design a sequential decision-making procedure that identifies a sequence generated according to F1with the fewest number of measurements. Earlier analyses of this search problem have demonstrated that the optimal design of the sequential rules strongly hinge on the exact value of ϵ. Such information, however, might not be available in certain applications, especially in anomaly detection where the anomalous sequences occur with unpredicted patterns. Motivated by this premise, this paper designs a sequential inference mechanism that forms two coupled decisions for identifying a sequence of interest, and also learning the value of ϵ. The paper devises three strategies that place different levels of emphasis on each of these inference goals.

An ordered set of data sequences is given where, broadly, the data sequences are categorized into normal and abnormal ones. The normal sequences consist of random variables generated according to a known distribution, while there exist uncertainties about the distributions of the abnormal sequences. Moreover, the generations of different sequences are correlated, induced by an underlying physical coupling, where a sequence being normal or abnormal depends on the status of the rest of the sequences according to a known dependency kernel. The objective is to design the quickest sequential and data-adaptive sampling procedure for identifying one abnormal sequence. This quickest search strategy strikes a balance between the quality and agility of the search process, as two opposing figures of merit. This paper characterizes the sampling and search strategy. Motivated by the fact that full characterization of such strategies can become computationally prohibitive, this paper also proposes asymptotically optimal sampling and search strategies that are computationally efficient.

Detecting correlation structures in large networks arises in many domains. Such detection problems are often studied independently of the underlying data acquisition process, rendering settings in which data acquisition policies and the associated sample size are pre-specified. Motivated by the advantages of data-adaptive sampling in data dimensionality reduction, especially in large networks, as well as enhancing the agility of the sampling process, this paper treats the inherently problems of data acquisition and correlation detection. Specifically, this paper considers a network of nodes generating random variables and designs the quickest sequential sampling strategy for collecting data and reliably deciding whether the network is a Markov network with a known correlation structure. By abstracting the Markov network as an undirected graph, in which the vertices represent the random variables and their connectivities model the correlation structure of interest, designing the quickest sampling strategy becomes equivalent to sequentially and data-adaptively identifying and sampling a sequence of vertices in the graph. Optimal sampling strategies are proposed and their associated optimality guarantees are established. Performance evaluations are provided to demonstrate the gains of the proposed sequential approaches.

Consider a set of random sequences, each consisting of independent and identically distributed random variables drawn from one of the two known distributions$F_{0}$and$F_{1}$. The underlying distributions of different sequences are correlated, induced by an inherent physical coupling in the mechanisms generating these sequences. The objective is to design the quickest data-adaptive and sequential search procedure for identifying one sequence generated according to$F_{1}$. The optimal design involves striking a balance between the average delay in reaching a decision and the rate of false alarms, as two opposing figures of merit. Optimal and asymptotically optimal decision rules are derived, which can take radically different forms depending on the correlation structure. Performance and sampling complexity analyses are provided to delineate the tradeoff between decision delay and quality. The generalization to parallel sampling, in which multiple sequences are sampled at the same time, is also investigated.

Quickest spectrum sensing seeks to optimize a balance between two opposing performance measures in spectrum sensing, one being the delay in identifying spectrum opportunities, and the other being the quality of the decision. The existing spectrum sensing approaches formed based on quickest detection theory rely on the assumption that the occupancy states of different spectrum bands over a wideband spectrum are statistically independent. This is an assumption that cannot be met in practice, especially in broadband communication schemes in which radio channels are dynamically grouped in bundles and allocated to different users based on the users' traffic needs. As a result of such channel grouping and allocation the occupancy states of the channels, especially the adjacent ones, are correlated. This paper, in contrast to the existing literature on quickest spectrum sensing, considers a wideband spectrum in which the occupancy states of different channels follow a pre-specified dependency kernel. The objective is to design the quickest spectrum sensing approach for identifying spectrum holes, which aims to minimize the average delay in identifying spectrum opportunities while assuring, in parallel, certain guarantees on the quality of the decision. The closed-form expression of the optimal sensing scheme are delineated and are shown to have low computational complexity.

Linear search arises in many application domains. The problem of linear search over multiple sequences in order to identify one sequence with a desired statistical feature is considered. The quickest linear search optimizes a balance between two opposing performance measures, one being the delay in detecting a desirable sequence, and the other one being the quality of the decision. The existing approaches in the quickest search literature rely on the assumption that the sequences are statistically independent. In many applications, however, due to the underlying physical couplings, generations of available sequences are not necessarily independent. Driven by such underlying couplings, this paper considers searching over correlated sequences, in which the distribution of each sequence depends on the distribution of its preceding one. The closed-form characterization of the sampling process for the optimal search is delineated. The analysis reveals that depending on the correlation structure, the optimal search strategy can be similar to (in spirit) or dramatically different from the optimal search strategy over independent sequences.

Quickest spectrum sensing seeks to optimize a balance between two opposing performance measures, one being the delay in identifying spectrum opportunities, and the other being the quality of the decision. The existing spectrum sensing approaches formed based on quickest detection theory rely on the assumption that the occupancy states of different spectrum bands over a wideband spectrum are statistically independent. This is an assumption that cannot be met in practice, especially in broadband communication schemes in which radio channels are dynamically grouped in bundles and allocated to different users based on the users' traffic needs. As a result of such channel grouping and allocation, the occupancy states of the channels, especially the adjacent ones, are correlated. This paper, in contrast to the existing literature on quickest spectrum sensing, considers a wideband spectrum in which the occupancy states of different channels follow a pre-specified dependency kernel. The objective is to design the quickest spectrum sensing approach for identifying spectrum holes, which aims to minimize the average delay in identifying spectrum opportunities while assuring, in parallel, certain guarantees on the quality of the decision. The closed-form characterization of the optimal sensing scheme is delineated and it is shown that this optimal scheme has low computational complexity.