We consider the problem of contextual kernel bandits with stochastic contexts, where the underlying reward function belongs to a known Reproducing Kernel Hilbert Space (RKHS). We study this problem under the additional constraint of joint differential privacy, where the agents needs to ensure that the sequence of query points is differentially private with respect to both the sequence of contexts and rewards. We propose a novel algorithm that improves upon the state of the art and achieves an error rate of $\mathcal{O}\left(\sqrt{\dfrac{\gamma_T}{T}} + \dfrac{\gamma_T}{T \varepsilon}\right)$ after $T$ queries for a large class of kernel families, where $\gamma_T$ represents the effective dimensionality of the kernel and $\varepsilon > 0$ is the privacy parameter. Our results are based on novel estimator for the reward function that simultaneously enjoys high utility along with a low-sensitivity to observed rewards and contexts, which is crucial to obtain an improved performance.

We consider distributed kernel bandits where $N$ agents aim to collaboratively maximize an unknown reward function that lies in a reproducing kernel Hilbert space. Each agent sequentially queries the function to obtain noisy observations at the query points. Agents can share information through a central server, with the objective of minimizing regret that is accumulating over time $T$ and aggregating over agents. We develop the first algorithm that achieves the optimal regret order (as defined by centralized learning) with a communication cost that is sublinear in both $N$ and $T$. The key features of the proposed algorithm are the uniform exploration at the local agents and shared randomness with the central server. Working together with the sparse approximation of the GP model, these two key components make it possible to preserve the learning rate of the centralized setting at a diminishing rate of communication.

We consider the problem of differentially private stochastic convex optimization (DP-SCO) in a distributed setting with $M$ clients, where each of them has a local dataset of $N$ i.i.d. data samples from an underlying data distribution. The objective is to design an algorithm to minimize a convex population loss using a collaborative effort across $M$ clients, while ensuring the privacy of the local datasets. In this work, we investigate the accuracy-communication-privacy trade-off for this problem. We establish matching converse and achievability results using a novel lower bound and a new algorithm for distributed DP-SCO based on Vaidya’s plane cutting method. Thus, our results provide a complete characterization of the accuracy-communication-privacy trade-off for DP-SCO in the distributed setting.

We consider Bayesian optimization using Gaussian Process models, also referred to as kernel-based bandit optimization. We study the methodology of exploring the domain using random samples drawn from a distribution. We show that this random exploration approach achieves the optimal error rates. Our analysis is based on novel concentration bounds in an infinite dimensional Hilbert space established in this work, which may be of independent interest. We further develop an algorithm based on random exploration with domain shrinking and establish its order-optimal regret guarantees under both noise-free and noisy settings. In the noise-free setting, our analysis closes the existing gap in regret performance under a mild assumption on the underlying function and thereby *partially resolves a COLT open problem*. The proposed algorithm also enjoys a computational advantage over prevailing methods due to the random exploration that obviates the expensive optimization of a non-convex acquisition function for choosing the query points at each iteration.

We address the problem of detecting an anomalous process among a large number of processes. At each time t, normal processes are in state zero (normal state), whereas the abnormal process may exist in either state zero (normal state) or state one (abnormal state), with these states remaining hidden. The transitions between states for the abnormal process follow a Markov chain over time. During each time step, observations can be drawn from a selected subset of processes. Each probed process generates an observation based on its hidden state, following a typical distribution under state zero or an abnormal distribution under state one. The objective is to design a sequential search strategy that minimizes the expected detection time, subject to an error probability constraint. In contrast to prior studies on related models that focused on i.i.d. observations, the new model leads to the detection of a hidden Markov model (HMM) of anomaly, introducing significant challenges in both algorithm design and theoretical analysis. We introduce a novel sequential search strat-egy, referred to as the Anomaly Detection under Hidden Markov (ADHM) algorithm, and show that ADHM is asymptotically optimal as the error probability approaches zero. Simulation results demonstrate the superior performance of ADHM over existing methods within a finite regime.

Federated learning (FL) is an emerging machine learning (ML) paradigm used to train models across multiple nodes (i.e., clients) holding local data sets, without explicitly exchanging the data. It has attracted a growing interest in recent years due to its advantages in terms of privacy considerations, and communication resources. In FL, selected clients train their local models and send a function of the models to the server, which consumes a random processing and transmission time. The server updates the global model and broadcasts it back to the clients. The client selection (CS) problem in FL is to schedule a subset of the clients for training and transmission at each given time so as to optimize the learning performance. In this paper, we present a novel multi-armed bandit (MAB)-based approach for CS to minimize the training latency without harming the ability of the model to generalize, i.e., to give reliable predictions for new observations. We develop a novel algorithm to achieve this goal, dubbed Bandit Scheduling for FL (BSFL). We analyze BSFL theoretically, and show that it achieves a logarithmic regret, defined as the loss of BSFL as compared to a genie that has complete knowledge about the latency means of all clients. Furthermore, simulation results using synthetic and real datasets demonstrate that BSFL is superior to existing methods.

We consider distributed linear bandits where $M$ agents learn collaboratively to minimize the overall cumulative regret incurred by all agents. Information exchange is facilitated by a central server, and both the uplink and downlink communications are carried over channels with fixed capacity, which limits the amount of information that can be transmitted in each use of the channels. We investigate the regret-communication trade-off by (i) establishing information-theoretic lower bounds on the required communications (in terms of bits) for achieving a sublinear regret order; (ii) developing an efficient algorithm that achieves the minimum sublinear regret order offered by centralized learning using the minimum order of communications dictated by the information-theoretic lower bounds. For sparse linear bandits, we show a variant of the proposed algorithm offers better regret-communication trade-off by leveraging the sparsity of the problem.

We consider the problem of noisy group testing where the test results are corrupted by noise with an unknown distribution. We propose an adaptive test plan consisting of a hierarchy of biased random walks guided by a local sequential test which together lend adaptivity and agnosticism to the unknown noise model. We show that the proposed test plan is order optimal in both the population size and the error rate.

We consider sequential optimization of an unknown function in a reproducing kernel Hilbert space. We propose a Gaussian process-based algorithm and establish its order-optimal regret performance (up to a poly-logarithmic factor). This is the first GP-based algorithm with an order-optimal regret guarantee. The proposed algorithm is rooted in the methodology of domain shrinking realized through a sequence of tree-based region pruning and refining to concentrate queries in increasingly smaller high-performing regions of the function domain. The search for high-performing regions is localized and guided by an iterative estimation of the optimal function value to ensure both learning efficiency and computational efficiency. Compared with the prevailing GP-UCB family of algorithms, the proposed algorithm reduces computational complexity by a factor of $O(T^{2d-1})$ (where $T$ is the time horizon and $d$ the dimension of the function domain).

We consider the problem of anomaly detection among a large number of processes, where the probabilistic models of anomalies are unknown. At each time, aggregated noisy observations can be taken from a chosen subset of processes, where the chosen subset conforms to a tree structure. The observation distribution depends on the chosen subset and the absence/presence of anomalies. We develop a sequential search strategy using a hierarchical Kolmogorov-Smirnov (KS) statistics. Referred to as Tree-based Anomaly Search using KS statistics (TASKS), the proposed strategy is order-optimal with respect to the size of the search space and the detection accuracy.

The problem of detecting a few anomalous processes among a large number of data streams is considered. At each time, aggregated observations can be taken from a chosen subset of the processes, where the chosen subset conforms to a given tree structure. The random observations are drawn from a general distribution that may depend on the size of the chosen subset and the number of anomalous processes in the subset. We propose a sequential search strategy by devising an information-directed random walk on the tree-structured observation hierarchy. The proposed policy is shown to be asymptotically optimal with respect to the detection accuracy and order-optimal with respect to the size of the search space. Effectively localizing the data processing to small subsets of the search space, the proposed strategy is also efficient in terms of computation and memory requirement.

A framework based on iterative coordinate minimization (CM) is developed for stochastic convex optimization. Given that exact coordinate minimization is impossible due to the unknown stochastic nature of the objective function, the crux of the proposed optimization algorithm is an optimal control of the minimization precision in each iteration. We establish the optimal precision control and the resulting order-optimal regret performance for strongly convex and separably nonsmooth functions. An interesting finding is that the optimal progression of precision across iterations is independent of the low-dimension CM routine employed, suggesting a general framework for extending low-dimensional optimization routines to high-dimensional problems. The proposed algorithm is amenable to online implementation and inherits the scalability and parallelizability properties of CM for large-scale optimization. Requiring only a sublinear order of message exchanges, it also lends itself well to distributed computing as compared with the alternative approach of coordinate gradient descent.

Online minimization of an unknown convex function over a convex and compact set is considered under first-order stochastic bandit feedback, which returns a random realization of the gradient of the function at each query point. Without knowing the distribution of the random gradients, a learning algorithm sequentially chooses query points with the objective of minimizing regret defined as the expected cumulative loss of the function values at the query points in excess to the minimum value of the function. An active search strategy based on devising a biased random walk on an infinite-depth tree constructed through successive partitioning of the domain of the function is developed. It is shown that the biased random walk moves toward the optimal point in a geometric rate, leading to an order-optimal regret performance of O(√T). The structural properties of this random-walk based strategy admits detailed finite-time regret analysis. By localizing data processing to small subsets of the input domain based on the tree structure, it enjoys O(1) computation and memory complexity per query and allows dynamic allocation of limited data storage.

An active inference problem of detecting anomalies among heterogeneous processes is considered. At each time, a subset of processes can be probed. The objective is to design a sequential probing strategy that dynamically determines which processes to observe at each time and when to terminate the search so that the expected detection time is minimized under a constraint on the probability of misclassifying any process. This problem falls into the general setting of sequential design of experiments pioneered by Chernoff in 1959, in which a randomized strategy, referred to as the Chernoff test, was proposed and shown to be asymptotically optimal as the error probability approaches zero. For the problem considered in this paper, a low-complexity deterministic test is shown to enjoy the same asymptotic optimality while offering significantly better performance in the finite regime and faster convergence to the optimal rate function, especially when the number of processes is large. Furthermore, the proposed test offers considerable reduction in computation complexity.

An active inference problem of detecting an anomalous process among M heterogeneous processes is considered. At each time, a subset of processes can be probed. The objective is to design a sequential probing strategy that dynamically determines which processes to observe at each time and when to terminate the search so that the expected detection time is minimized under a constraint on the probability of misclassifying any process. This problem falls into the general setting of sequential design of experiments pioneered by Chernoff in 1959, in which a randomized strategy, referred to as the Chernoff test, was proposed and shown to be asymptotically optimal as the error probability approaches zero. For the problem considered in this paper, a low-complexity deterministic test is shown to enjoy the same asymptotic optimality while offering significantly better performance in the finite regime and faster convergence to the optimal rate function, especially when the number of processes is large. Furthermore, the proposed test offers considerable reduction in implementation complexity.

We consider the problem of detecting heavy hitters and hierarchical heavy hitters among a large number of traffic flows modeled as random processes with unknown and potentially heavy-tailed distributions. The objective is an active inference strategy that determines, sequentially, which aggregated flow on the IP-prefix tree to probe in order to minimize the sample complexity under a reliability constraint. We propose an active inference strategy that induces a biased random walk on the flow aggregation tree based on confidence bounds of sample statistics. We then establish its order optimality in terms of both the size of the search space (i.e., the number of traffic flows) and the reliability requirement. The result also finds applications in noisy group testing and adaptive sampling with noisy response.

The problem of detecting a few anomalous processes among a large number of M processes is considered. At each time, aggregated observations can be taken from a chosen subset of processes, where the chosen subset conforms to a given binary tree structure. The random observations are i.i.d. over time with a general distribution that may depend on the size of the chosen subset and the number of anomalous processes in the subset. The objective is a sequential search strategy that minimizes the sample complexity (i.e., the expected number of observations which represents detection delay) subject to a reliability constraint. A sequential test that results in a biased random walk on the tree is developed and is shown to be asymptotically optimal in terms of detection accuracy. Furthermore, it achieves the optimal logarithmic-order sample complexity in M provided that the Kullback-Liebler divergence between aggregated observations in the presence and the absence of anomalous processes are bounded away from zero at all levels of the tree structure as M approaches infinity. Sufficient conditions on the decaying rate of the aggregated observations to pure noise under which a sublinear scaling in M is preserved are also identified for the Bernoulli case.

We study the online learning problem of a bidder who participates in repeated auctions. With the goal of maximizing his T-period payoff, the bidder determines the optimal allocation of his budget among his bids for $K$ goods at each period. As a bidding strategy, we propose a polynomial-time algorithm, inspired by the dynamic programming approach to the knapsack problem. The proposed algorithm, referred to as dynamic programming on discrete set (DPDS), achieves a regret order of $O(\sqrt{T\log{T}})$. By showing that the regret is lower bounded by $\Omega(\sqrt{T})$ for any strategy, we conclude that DPDS is order optimal up to a $\sqrt{\log{T}}$ term. We evaluate the performance of DPDS empirically in the context of virtual trading in wholesale electricity markets by using historical data from the New York market. Empirical results show that DPDS consistently outperforms benchmark heuristic methods that are derived from machine learning and online learning approaches.

The problem of online learning and optimization of unknown Markov jump linear models is considered. A new online learning algorithm, referred to as Markovian simultaneous perturbations stochastic approximation (MSPSA), is proposed. It is shown that ν/ MSPSA achieves the minimax regret order of Θ(√T). Using the Van Trees inequality (stochastic Cramér-Rao bound), it is shown ν/ that Θ(√T) is the lowest regret order achievable. Simulation results show scenarios that MSPSA offers significant gain over the greedy certainty equivalent approaches.

We consider the problem of sampling a node-weighted graph. The objective is to infer the values of all nodes from that of a minimum subset of nodes by exploiting correlations in node values. We first introduce the concept of information dominating set (IDS). A subset of nodes in a given graph is an IDS if the value of these nodes is sufficient to infer the information state of the entire graph. We focus on two fundamental algorithmic problems: (i) how to determine whether a given subset of vertices is an IDS; (ii) how to construct a minimum IDS. Assuming binary node values and the local majority rule, we show that the first problem is co-NP-complete and the second problem is NP-hard in a general network. We then show that in acyclic graphs, both problems admit linear-complexity solutions by establishing a connection between the IDS problems and the vertex cover problem. For general graphs, we develop algorithms for solving both problems based on the concept of essential differential set. These results find applications in opinion sampling such as political polling and market survey in social-economic networks, and inferring epidemics and cascading failures in communication and infrastructure networks.

We study risk-averse multi-armed bandit problems under mean-variance measures. We consider two risk mitigation models. In the first model, the variations in the reward values obtained at different times are considered as risk and the objective is to minimize the mean-variance of the observed rewards. In the second model, the quantity of interest is the total reward at the end of the time horizon and the objective is to minimize the mean-variance of the total reward. Under both models, we establish asymptotic as well as finite-time lower bounds on regret and develop online learning a time horizon algorithms that achieve the lower bounds.

The quickest detection of short-term voltage instability in a smart grid is considered. The problem is formulated as a binary sequential composite hypothesis testing where the null hypothesis is a non-stationary process with an unknown exponentially decaying mean and the alternative is a nonstationary process with an unknown exponentially increasing mean. A sequential generalized likelihood ratio test (SGLRT) is proposed and analyzed. It is shown that the proposed SGLRT is asymptotically optimal.

The problem of detecting a single anomalous process among a finite number M of processes is considered. At each time, a subset of the processes can be observed, and the observations from each chosen process follow two different distributions, depending on whether the process is normal or abnormal. The objective is a sequential search strategy that minimizes the expected detection time subject to an error probability constraint. This problem can be considered as a special case of active hypothesis testing first considered by Chernoff where a randomized strategy, referred to as the Chernoff test, was proposed and shown to be asymptotically (as the error probability approaches zero) optimal. For the special case considered in this paper, we show that a simple deterministic test achieves asymptotic optimality and offers better performance in the finite regime. We further extend the problem to the case where multiple anomalous processes are present. In particular, we examine the case where only an upper bound on the number of anomalous processes is known.

A hypergraph is a set V of vertices and a set of nonempty subsets of V, called hyperedges. Unlike graphs, hypergraphs can capture higher-order interactions in social and communication networks that go beyond a simple union of pairwise relationships. In this paper, we consider the shortest path problem in hypergraphs. We develop two algorithms for finding and maintaining the shortest hyperpaths in a dynamic network with both weight and topological changes. These two algorithms are the first to address the fully dynamic shortest path problem in a general hypergraph. They complement each other by partitioning the application space based on the nature of the change dynamics and the type of the hypergraph. We analyze the time complexity of the proposed algorithms and perform simulation experiments for random geometric hypergraphs, energy efficient routing in multichannel multiradio networks, and the Enron email data set. The experiment with the Enron email data set illustrates the application of the proposed algorithms in social networks for identifying the most important actor and the latent social relationship based on the closeness centrality metric.

We formulate and study the thinnest path problem for secure communication in wireless ad hoc networks. The objective is to find a path from a source to its destination that results in the minimum number of nodes overhearing the message by a judicious choice of relaying nodes and their corresponding transmission powers. We adopt a directed hypergraph model of the problem and establish the NP-completeness of the problem in 2-D networks. We then develop two polynomial-time approximation algorithms that offer √(n/2) and n/2√(n-1) approximation ratios for general directed hypergraphs (which can model nonisotropic signal propagation in space) and constant approximation ratios for ring hypergraphs (which result from isotropic signal propagation). We also consider the thinnest path problem in 1-D networks and 1-D networks embedded in a 2-D field of eavesdroppers with arbitrary unknown locations (the so-called 1.5-D networks). We propose a linear-complexity algorithm based on nested backward induction that obtains the optimal solution for both 1-D and 1.5-D networks. This algorithm does not require the knowledge of eavesdropper locations and achieves the best performance offered by any algorithm that assumes complete location information of the eavesdroppers.

In an ad hoc cognitive radio network, secondary users access channels temporarily unused by primary users, and the existence of a communication link between two secondary users depends on the transmitting and receiving activities of nearby primary users. Using theories and techniques from continuum percolation and ergodicity, we analytically characterize the connectivity of the secondary network defined in terms of the almost sure finiteness of the multihop delay, and show the occurrence of a phase transition phenomenon while studying the impact of the temporal dynamics of the primary traffic on the connectivity of the secondary network. Specifically, as long as the primary traffic has some temporal dynamics caused by either mobility and/or changes in traffic load and pattern, the connectivity of the secondary network depends solely on its own density and is independent of the primary traffic; otherwise, the connectivity of the secondary network requires putting a density-dependent cap on the primary traffic load. We show that the scaling behavior of the multihop delay depends critically on whether or not the secondary network is instantaneously connected. In particular, we establish the scaling law of the minimum multihop delay with respect to the source-destination distance when the propagation delay is negligible.

We consider a large-scale cyber network with N components. Each component is either in a healthy state or an abnormal state. To model scenarios where attacks to the network may not follow a stochastic process and the attackers may adapt to the actions of the intrusion detection system (IDS) in an arbitrary and unknown way, we adopt a non-stochastic model in which the attack process at each component can be any unknown deterministic sequence. Due to resource constraints, the IDS can only choose K (K <; N) components to probe at each time. An abnormal component incurs a cost per unit time (depending on the criticality of the component) until it is probed and fixed. The objective is a dynamic probing strategy under the performance measure of regret, defined as the performance loss compared to that of a genie who knows the entire attack processes a priori and probes optimally (under certain constraints) based on this knowledge. We propose a policy that achieves sublinear regret order, thus offers the same time averaged performance as that of the omniscient genie.

We consider a variation of the Deffuant-Weisbuch model introduced by Deffuant et al. in 2000, to provide new analytical insights on the opinion dynamics in a social group. We model the trust that may exist between like-minded agents through a trust function, which is a discontinuous (hard-interaction) non-increasing function of the opinion distance. In this model, agents exchange their opinions with their neighbors and move their opinions closer to each other if they are like-minded (that is, the distance between opinions is smaller than a threshold). We first study the dynamics of opinion formation under random interactions with a fixed rate of communication between pairs of agents. Our goal is to analyze the convergence properties of the opinion dynamics and explore the underlying characteristics that mark the phase transition from opinion polarization to consensus. Furthermore, we extend the hard-interaction model to a strategic interaction model by considering a time-varying rate of interaction. In this model, social agents themselves decide the time and energy that should be expended on interacting each of their neighbors, based on their utility functions. The aim is to understand how and under what conditions clustering patterns emerge in opinion space. Extensive simulations are provided to validate the analytical results of both the hard-interaction model and the strategic interaction model. We also offer evidence that suggests the validity of the proposed model, using the location and monthly survey data collected in the Social Evolution experiment over a period of nine months.

We consider the restless multiarmed bandit problem with unknown dynamics in which a player chooses one out ofNarms to play at each time. The reward state of each arm transits according to an unknown Markovian rule when it is played and evolves according to an arbitrary unknown random process when it is passive. The performance of an arm selection policy is measured by regret, defined as the reward loss with respect to the case where the player knows which arm is the most rewarding and always plays the best arm. We construct a policy with an interleaving exploration and exploitation epoch structure that achieves a regret with logarithmic order. We further extend the problem to a decentralized setting where multiple distributed players share the arms without information exchange. Under both an exogenous restless model and an endogenous restless model, we show that a decentralized extension of the proposed policy preserves the logarithmic regret order as in the centralized setting. The results apply to adaptive learning in various dynamic systems and communication networks, as well as financial investment.

Gossiping models have been increasingly applied to study social network phenomena, in particular, to model the dynamics of social behavior or belief through local interactions. In this context, this paper investigates how the opinions of social agents diffuse in a network under a so-called hard-interaction model, in which the agents interact more strongly with neighbors that share their beliefs and have no influence on the neighbors whose opinions differ by more than a threshold. We analyze the convergence properties of the opinion dynamics and provide analytical insights to characterize the phase transition from a society of radicalized opinions to one of convergent behavior.

The problem of minimizing queueing delay of opportunistic access of multiple continuous time Markov channels is considered. A new access policy based on myopic sensing and adaptive transmission (MS-AT) is proposed. Under the framework of risk sensitive constrained Markov decision process with effective bandwidth as a measure of queueing delay, it is shown that MS-AT achieves simultaneously throughput and delay optimality. It is shown further that both the effective bandwidth and the throughput of MS-AT are two-segment piece-wise linear functions of the collision constraint (maximum allowable conditional collision probability) with the effective bandwidth and throughput coinciding in the regime of tight collision constraints. Analytical and simulation comparisons are conducted with the myopic sensing and memoryless transmission (MS-MT) policy which is throughput optimal but delay suboptimal in the regime of tight collision constraints.

We consider a large-scale cyber network with N components. Each component is either in a healthy state (0) or an abnormal state (1). Due to intrusions, the state of each component transits from 0 to 1 over time according to an arbitrary stochastic process. At each time, a subset of K (K <; N) components are probed and those observed in abnormal states are fixed. The objective is to design a dynamic probing strategy that minimizes the long-term network cost incurred at all abnormal components. We formulate the problem as a Restless Multi-Armed Bandit (RMAB) process. We show that this class of RMAB is indexable and Whittle index can be obtained in closed-form. For homogeneous networks, we show that Whittle index policy achieves the optimal performance with a simple structure that does not require any prior knowledge on the intrusion processes.

We consider dynamic spectrum access where distributed secondary users search for spectrum opportunities without knowing the primary traffic statistics. In each slot, a secondary transmitter chooses one channel to sense and subsequently transmit if the channel is sensed as idle. Sensing is imperfect, i.e., an idle channel may be sensed as busy and vice versa. Without centralized control, each secondary user needs to independently identify the channels that offer the most opportunities while avoiding collisions with both primary and other secondary users. We address the problem within a cooperative game framework, where the objective is to maximize the throughput of the secondary network under a constraint on the collision with the primary system. The performance of a decentralized channel access policy is measured by the system regret, defined as the expected total performance loss with respect to the optimal performance in the ideal scenario where the traffic load of the primary system on each channel is known to all secondary users and collisions among secondary users are eliminated through centralized scheduling. By exploring the rich communication structure of the problem, we show that the optimal system regret has the same logarithmic order as in the centralized counterpart with perfect sensing. A decentralized policy is constructed to achieve the logarithmic order of the system regret. In a broader context, this work addresses imperfect reward observation in decentralized multi-armed bandit problems.

In the classic Bayesian restless multi-armed bandit (RMAB) problem, there are N arms, with rewards on all arms evolving at each time as Markov chains with known parameters. A player seeks to activate K ≥ 1 arms at each time in order to maximize the expected total reward obtained over multiple plays. RMAB is a challenging problem that is known to be PSPACE-hard in general. We consider in this work the even harder non-Bayesian RMAB, in which the parameters of the Markov chain are assumed to be unknown a priori. We develop an original approach to this problem that is applicable when the corresponding Bayesian problem has the structure that, de pending on the known parameter values, the optimal solution is one of a prescribed finite set of policies. In such settings, we propose to learn the optimal policy for the non-Bayesian RMAB by employing a suitable meta-policy which treats each policy from this finite set as an arm in a different non-Bayesian multi-armed bandit problem for which a single-arm selection policy is optimal. We demonstrate this approach by developing a novel sensing policy for opportunistic spectrum access over unknown dynamic channels. We prove that our policy achieves near-logarithmic regret (the difference in expected reward compared to a model-aware genie), which leads to the same average reward that can be achieved by the optimal policy under a known model. This is the first such result in the literature for a non Bayesian RMAB.

We consider the restless multi-armed bandit (RMAB) problem with unknown dynamics. At each time, a player chooses K out of N (N >; K) arms to play The state of each arm determines the reward when the arm is played and transits according to Markovian rules no matter the arm is engaged or passive. The Markovian dynamics of the arms are unknown to the player. The objective is to maximize the long-term expected reward by designing an optimal arm selection policy. The performance of a policy is measured by regret, defined as the reward loss with respect to the case where the player knows which K arms are the most rewarding and always plays these K best arms. We construct a policy, referred to as Restless Upper Confidence Bound (RUCB), that achieves a regret with logarithmic order of time when an arbitrary nontrivial bound on certain system parameters is known. When no knowledge about the system is available, we extend the RUCB policy to achieve a regret arbitrarily close to the logarithmic order. In both cases, the system achieves the maximum average reward offered by the K best arms. Potential applications of these results include cognitive radio networks, opportunistic communications in unknown fading environments, and financial investment.

We consider the broadcasting problem in multi-radio multi-channel ad hoc networks. The objective is to minimize the total broadcast cost, where the cost can be of any form that is summable over all the transmissions (e.g., the transmission and reception energy, the price for accessing a specific channel). Our technical approach is based on a simplicial complex model that allows us to capture the broadcast nature of the wireless medium and the heterogeneity across radios and channels. Specifically, we show that broadcasting in multi-radio multi-channel ad hoc networks can be formulated as a minimum spanning problem in simplicial complexes. We establish the NP-completeness of the minimum spanning problem and propose two approximation algorithms with order-optimal performance guarantee. These two algorithms offer tradeoffs between performance and time complexity. In a broader context, this work appears to be the first that studies the minimum spanning problem in simplicial complexes and weighted minimum connected set cover problem.

We analyze the multihop delay of ad hoc cognitive radio networks, where the transmission delay of each hop consists of the propagation delay and the waiting time for the availability of the communication channel (i.e. the occurrence of a spectrum opportunity at this hop). Using theories and techniques from continuum percolation and ergodicity, we establish the scaling law of the minimum multihop delay with respect to the source-destination distance in cognitive radio networks. When the propagation delay is negligible, we show the starkly different scaling behavior of the minimum multihop delay in instantaneously connected networks as compared to networks that are only intermittently connected due to scarcity of spectrum opportunities. Specifically, if the network is instantaneously connected, the minimum multihop delay is asymptotically independent of the distance; if the network is only intermittently connected, the minimum multihop delay scales linearly with the distance. When the propagation delay is nonnegligible but small, we show that although the scaling order is always linear, the scaling rate for an instantaneously connected network can be orders of magnitude smaller than the one for an intermittently connected network.

We address the percolation-based connectivity of large-scale ad hoc heterogeneous wireless networks, where secondary users exploit channels temporarily unused by primary users and the existence of a communication link between two secondary users depends on not only the distance between them but also the transmitting and receiving activities of nearby primary users. We introduce the concept of connectivity region defined as the set of density pairs-the density of secondary users and the density of primary transmitters - under which the secondary network is connected. Using theories and techniques from continuum percolation, we analytically characterize the connectivity region of the secondary network and reveal the tradeoff between proximity (the number of neighbors) and the occurrence of spectrum opportunities. Specifically, we establish three basic properties of the connectivity region-contiguity, monotonicity of the boundary and uniqueness of the infinite connected component, where the uniqueness implies the occurrence of a phase transition phenomenon in terms of the almost sure existence of either zero or one infinite connected component; we identify and analyze two critical densities which jointly specify the profile as well as an outer bound on the connectivity region; we study the impacts of secondary users' transmission power on the connectivity region and the conditional average degree of a secondary user and demonstrate that matching the interference ranges of the primary and the secondary networks maximizes the tolerance of the secondary network to the primary traffic load. Furthermore, we establish a necessary condition and a sufficient condition for connectivity, which lead to an outer bound and an inner bound on the connectivity region.

We consider a cognitive radio network with distributed multiple secondary users, where each user independently searches for spectrum opportunities in multiple channels without exchanging information with others. The occupancy of each channel is modeled as an i.i.d. Bernoulli process with unknown mean. Users choosing the same channel collide, and none or only one receives reward depending on the collision model. This problem can be formulated as a decentralized multi-armed bandit problem. We measure the performance of a decentralized policy by the system regret, defined as the total reward loss with respect to the optimal performance under the perfect scenario where all channel parameters are known to all users and collisions among secondary users are eliminated through perfect scheduling. We show that the minimum system regret grows with time at the same logarithmic order as in the centralized counterpart, where users exchange observations and make decisions jointly. We propose a basic policy structure that ensures a Time Division Fair Sharing (TDFS) of the channels. Based on this basic TDFS structure, decentralized policies can be constructed to achieve this optimal order while ensuring fairness among users. Furthermore, we show that the proposed TDFS policy belongs to a general class of decentralized polices, for which a uniform performance benchmark is established. All results hold for general stochastic processes beyond Bernoulli and thus find a wide area of potential applications including multi-channel communication systems, multi-agent systems, web search and advertising, and social networks.

We analyze the multihop delay of ad hoc cognitive radio networks, where the transmission delay of each hop consists of the propagation delay and the waiting time for the availability of the communication channel (i.e., the occurrence of a spectrum opportunity at that hop). Using theories and techniques from continuum percolation and ergodicity, we establish the scaling law of the minimum multihop delay with respect to the source-destination distance. We show the starkly different scaling behavior of the multihop delay in instantaneously connected networks as compared to networks that are only intermittently connected due to the scarcity of spectrum opportunities.

Mobile device based human-centric sensing and user state recognition provide rich contextual information for various mobile applications and services. However, continuously capturing this contextual information consumes significant amount of energy and drains mobile device battery quickly. In this paper, we propose a computationally efficient algorithm to obtain the optimal sensor sampling policy under the assumption that the user state transition is Markovian. This Markov-optimal policy minimizes user state estimation error while satisfying a given energy consumption budget. We first compare the Markov-optimal policy with uniform periodic sensing for Markovian user state transitions and show that the improvements obtained depend upon the underlying state transition probabilities. We then apply the algorithm to two different sets of real experimental traces pertaining to user motion change and inter-user contacts and show that the Markov-optimal policy leads to an approximately 20% improvement over the naive uniform sensing policy.

In this paper, we consider a class of restless multiarmed bandit processes (RMABs) that arises in dynamic multichannel access, user/server scheduling, and optimal activation in multiagent systems. For this class of RMABs, we establish the indexability and obtain Whittle index in closed form for both discounted and average reward criteria. These results lead to a direct implementation of Whittle index policy with remarkably low complexity. When arms are stochastically identical, we show that Whittle index policy is optimal under certain conditions. Furthermore, it has a semiuniversal structure that obviates the need to know the Markov transition probabilities. The optimality and the semiuniversal structure result from the equivalence between Whittle index policy and the myopic policy established in this work. For nonidentical arms, we develop efficient algorithms for computing a performance upper bound given by Lagrangian relaxation. The tightness of the upper bound and the near-optimal performance of Whittle index policy are illustrated with simulation examples.

We consider power control in cognitive radio networks where secondary users identify and exploit instantaneous and local spectrum opportunities without causing unacceptable interference to primary users. We qualitatively characterize the impacts of the transmission power of secondary users on the occurrence of spectrum opportunities and the reliability of opportunity detection. Based on a Poisson model of the primary network, we quantify these impacts by showing that (i) the probability of spectrum opportunity decreases exponentially with the transmission power of secondary users, where the exponential decay constant is given by the traffic load of primary users; (ii) reliable opportunity detection is achieved in the two extreme regimes in terms of the ratio between the transmission power of secondary users and that of primary users. Such analytical characterizations allow us to study power control for optimal transport throughput under constraints on the interference to primary users. Furthermore, we reveal the difference between detecting primary signals and detecting spectrum opportunities, and demonstrate the complex relationship between physical layer spectrum sensing and MAC layer throughput. The dependency of this PHY-MAC interaction on the application type and the use of handshake signaling such as RTS/CTS is also illustrated.

This paper considers opportunistic communication over multiple channels where the state (ldquogoodrdquo or ldquobadrdquo) of each channel evolves as independent and identically distributed (i.i.d.) Markov processes. A user, with limited channel sensing capability, chooses one channel to sense and decides whether to use the channel (based on the sensing result) in each time slot. A reward is obtained whenever the user senses and accesses a ldquogoodrdquo channel. The objective is to design a channel selection policy that maximizes the expected total (discounted or average) reward accrued over a finite or infinite horizon. This problem can be cast as a partially observed Markov decision process (POMDP) or a restless multiarmed bandit process, to which optimal solutions are often intractable. This paper shows that a myopic policy that maximizes the immediate one-step reward is optimal when the state transitions are positively correlated over time. When the state transitions are negatively correlated, we show that the same policy is optimal when the number of channels is limited to two or three, while presenting a counterexample for the case of four channels. This result finds applications in opportunistic transmission scheduling in a fading environment, cognitive radio networks for spectrum overlay, and resource-constrained jamming and antijamming.

We aim to characterize the maximum link throughput of a multi-channel opportunistic communication system. The states of these channels evolve as independent and identically distributed Markov processes (the Gilbert-Elliot channel model). A user, with limited sensing and access capability, chooses one channel to sense and access in each slot and collects a reward determined by the state of the chosen channel. Such a problem arises in cognitive radio networks for spectrum overlay, opportunistic transmissions in fading environments, and resource-constrained jamming and anti-jamming. The objective of this paper is to characterize the optimal performance of such systems. The problem can be generally formulated as obtaining the maximum expected long-term reward of a partially observable Markov decision process or a restless multi-armed bandit process, for which analytical characterizations are rare. Exploiting the structure and optimality of the myopic channel selection policy established recently, we obtain a closed-form expression of the maximum link throughput for two-channel systems and lower and upper bounds when there are more than two channels. These results allow us to study the rate at which the optimal performance of an opportunistic system increases with the number of channels and to obtain the limiting performance as the number of channels approaches to infinity.

We consider opportunistic communications over multiple channels where the state ("good" or "bad") of each channel evolves as independent and identically distributed Markov processes. A user, with limited sensing and access capability, chooses one channel to sense and subsequently access (based on the sensed channel state) in each time slot. A reward is obtained when the user senses and accesses a "good" channel. The objective is to design the optimal channel selection policy that maximizes the expected reward accrued over time. This problem can be generally formulated as a Partially Observable Markov Decision Process (POMDP) or a restless multi-armed bandit process, to which optimal solutions are often intractable. We show in this paper that the myopic policy, with a simple and robust structure, achieves optimality under certain conditions. This result finds applications in opportunistic communications in fading environment, cognitive radio networks for spectrum overlay, and resource-constrained jamming and anti-jamming.

Opportunistic spectrum access (OSA) that allows secondary users to independently search for and exploit instantaneous spectrum availability is considered. The design objective is to maximize the throughput of a secondary user while limiting the probability of colliding with primary users. Integrated in the joint design are three basic components: a spectrum sensor that identifies spectrum opportunities, a sensing strategy that determines which channels in the spectrum to sense, and an access strategy that decides whether to access based on potentially erroneous sensing outcomes. This joint design is formulated as a constrained partially observable Markov decision process (POMDP), and a separation principle is established. The separation principle reveals the optimality of myopic policies for the design of the spectrum sensor and the access strategy, leading to closed-form optimal solutions. Furthermore, it decouples the design of the sensing strategy from that of the spectrum sensor and the access strategy, and reduces the constrained POMDP to an unconstrained one. Numerical examples are provided to study the tradeoff between sensing time and transmission time, the interaction between the physical layer spectrum sensor and the MAC layer sensing and access strategies, and the robustness of the ensuing design to model mismatch.

We consider a multi-channel opportunistic communication system where the states of these channels evolve as independent and statistically identical Markov chains (the Gilbert- Elliot channel model). A user chooses one channel to sense and access in each slot and collects a reward determined by the state of the chosen channel. The problem is to design a sensing policy for channel selection to maximize the average reward, which can be formulated as a multi-arm restless bandit process. In this paper, we study the structure, optimality, and performance of the myopic sensing policy. We show that the myopic sensing policy has a simple robust structure that reduces channel selection to a round-robin procedure and obviates the need for knowing the channel transition probabilities. The optimality of this simple policy is established for the two-channel case and conjectured for the general case based on numerical results. The performance of the myopic sensing policy is analyzed, which, based on the optimality of myopic sensing, characterizes the maximum throughput of a multi-channel opportunistic communication system and its scaling behavior with respect to the number of channels. These results apply to cognitive radio networks, opportunistic transmission in fading environments, downlink scheduling in centralized networks, and resource-constrained jamming and anti-jamming.

We design opportunistic spectrum access strategies for improving spectrum efficiency. In each slot, a secondary user chooses a subset of channels to sense and decides whether to access based on the sensing outcomes. Incorporating the secondary user's residual energy and buffer state, we formulate this sequential decision-making problem as a partially observable Markov decision process (POMDP). Within the POMDP framework, we obtain stationary optimal sensing and access policies. By exploiting the rich structure of the underlying problem, we develop monotonicity results for the optimal policies, which accelerate the computations. Numerical results are provided to study the impact of the secondary user's packet arrival rate and residual energy on the optimal sensing and access decisions.

In this paper, we provide a survey of dynamic spectrum access techniques. Various approaches envisioned for dynamic spectrum access are broadly categorized under three models: dynamic exclusive use model, open sharing model, and hierarchical access model. Based on this taxonomy, we provide an overview of the technical challenges and recent advances under each model.

We consider opportunistic spectrum access for secondary users over multiple channels whose occupancy by primary users is modeled as discrete-time Markov processes. Due to hardware limitations and energy constraints, a secondary user can choose, in each slot, one channel to sense and decide whether to access based on the sensing outcome. The design of sensing strategies that govern channel selections in each slot for optimal throughput performance of the secondary user can be formulated as a partially observable Markov decision process (POMDP). We exploit the structure of this problem when channels are independently and identically distributed. We reveal that the myopic sensing policy has a simple structure: channel selection is reduced to a counting process with little complexity. Further, for the two-channel case, we prove that the myopic sensing policy is in fact the optimal policy. Numerical results have also demonstrated the optimality of the myopic sensing policy when there are more than two channels.

We propose decentralized cognitive MAC protocols that allow secondary users to independently search for spectrum opportunities without a central coordinator or a dedicated communication channel. Recognizing hardware and energy constraints, we assume that a secondary user may not be able to perform full-spectrum sensing or may not be willing to monitor the spectrum when it has no data to transmit. We develop an analytical framework for opportunistic spectrum access based on the theory of partially observable Markov decision process (POMDP). This decision-theoretic approach integrates the design of spectrum access protocols at the MAC layer with spectrum sensing at the physical layer and traffic statistics determined by the application layer of the primary network. It also allows easy incorporation of spectrum sensing error and constraint on the probability of colliding with the primary users. Under this POMDP framework, we propose cognitive MAC protocols that optimize the performance of secondary users while limiting the interference perceived by primary users. A suboptimal strategy with reduced complexity yet comparable performance is developed. Without additional control message exchange between the secondary transmitter and receiver, the proposed decentralized protocols ensure synchronous hopping in the spectrum between the transmitter and the receiver in the presence of collisions and spectrum sensing errors

We propose and analyze an energy-aware traffic-adaptive routing strategy for large-scale mobile ad hoc networks. Referred to as Energy-Aware GEolocation-aided Routing (EAGER), this protocol optimally blends proactive and reactive strategies for energy efficiency. Specifically, EAGER partitions the network into cells and performs intra-cell proactive routing and inter-cell reactive routing. The cell size and transmission range are optimized analytically. By adjoining cells around hot spots and hot routes in the network, EAGER is capable of handling time-varying and spatially heterogeneous traffic conditions.

We consider information retrieval in a wireless sensor network deployed for the reconstruction of a spatially correlated signal field. Referred to as quality-of-service specific information retrieval (QUIRE), the proposed protocol optimizes the network performance under the metric of information rate per Joule while ensuring a given QoS. Based on the density of sensor deployment and the QoS specified by the maximum distortion for reconstructing the signal field, QUIRE partitions the sensor network into disjoint and equal-sized cells. The cell size is chosen to minimize the number of transmissions required for a given QoS by exploiting the spatial correlation of the signal field. Adopting the cross-layer design methodology that integrates opportunistic carrier sensing and optimal cell activation, QUIRE eliminates redundant transmissions and fully utilizes the channel reception capability in a fading environment

Sensor network with mobile access (SENMA) is an architecture in which randomly deployed low-power sensors are orchestrated by a few powerful mobile access points. This paper considers SENMA from energy-efficiency and information-theoretic perspectives. By allowing sensors to propagate data directly to mobile access points over multiaccess channels and relieving sensors from energy-consuming network functions, SENMA has the potential of offering orders of magnitude of improvement in energy efficiency over the multihop ad hoc architecture, as demonstrated by our analysis on scalability. Optimization configurations of SENMA such as the altitude, the trajectory, and the coverage of access points are considered next, using the sum-rate as the performance metric. Optimal strategies for single and multiple access points are determined. For multiple access points, the possibility of and the gain due to cooperation (i.e., joint decoding of signals received at different access points) are investigated.

Sensor network with mobile access (SENMA) is an architecture in which randomly deployed low-power sensors are orchestrated by a few powerful mobile access points (APs). This paper considers SENMA from energy-efficiency and information-theoretic perspectives. By allowing sensors to propagate data directly to mobile APs over multiaccess channels, and relieving sensors from energy-consuming network functions, SENMA has the potential of offering orders of magnitude of improvement in energy efficiency over the multihop ad hoc architecture, as demonstrated by our analysis on scalability. Optimization configurations of SENMA such as the altitude, the trajectory, and the coverage of APs are considered next, using the sum-rate as the performance metric. Optimal strategies for single and multiple APs are determined. For multiple APs, the possibility of and the gain due to cooperation (i.e., joint decoding of signals received at different APs) are investigated

We propose a hybrid networking strategy for large-scale energy constrained ad hoc networks. Referred to as energy-aware geolocation aided routing (EAGER), this protocol optimally blends proactive and reactive routing strategies for energy efficiency. Specifically, EAGER partitions the network into cells and performs intracell proactive routing and inter-cell reactive routing. The cell size and transmission range are optimized analytically for energy efficiency. Furthermore, by gluing cells around the hot spots in the network, EAGER is capable of adapting to time-varying heterogenous traffic patterns.

An analytical approach to the characterization of energy consumption of large-scale wireless networks is presented. The radio model includes energy consumption of nodes at various operating states. We analyze the total energy consumption of the proactive and the reactive networking strategies, taking into account transmitting, listening, and sleeping energy. Scaling laws with respect to the increase of node density and geographical size are derived. Energy efficiency and overhead at the physical and the network layers are evaluated against message duty cycle, channel fading rate, and node mobility. The crossover point in message duty cycle below which reactive network has assured advantages is obtained. The analysis is then applied to large-scale sensor networks for applications involving data-centric and location-centric queries. The ad hoc sensor network architecture is compared with sensor networks with mobile access points.

We consider protocol design for extracting information from sensors by a mobile access point. Energy efficiency, defined as the expected number of bits reliably received for each unit of energy consumed, is used as the performance measure. A distributed opportunistic information retrieval protocol which exploits channel state information (CSI) is proposed. Referred to as the CSI-based carrier sensing, this protocol encodes the channel state into the backoff strategy of carrier sensing. When the propagation delay is negligible, CSI-based carrier sensing achieves the highest energy efficiency of the opportunistic strategy. For significant propagation, we construct the backoff function which maps the channel state to backoff time to minimize the performance loss. The CSI-based carrier sensing with the constructed backoff strategy is shown to be robust to propagation delay.

A dynamic medium access control (MAC) protocol is proposed for a finite-user slotted channel with multipacket reception (MPR). This protocol divides the time axis into transmission periods (TPs) where the ith TP is dedicated to the transmission of the packets generated in the (i-1)th TP. At the beginning of each TP, the state (active or idle) of each user is estimated based on the length of the previous TP and the incoming traffic load. By exploiting the information on the state of users and the channel MPR capability, the number of users who can simultaneously access the channel in the current TP is chosen so that the expected length of this TP is minimized. As a result, the MPR capability is more efficiently utilized by the proposed protocol as compared to, for example, the slotted ALOHA with optimal retransmission probability. Furthermore, the proposed protocol requires little online computation. Its simplicity is comparable to that of slotted ALOHA. It can be applied to random access networks with spread spectrum and/or antenna array.

An adaptive medium-access control (MAC) protocol for heterogeneous networks with finite populations is proposed. Referred to as the multiqueue service room (MQSR) protocol, this scheme is capable of handling users with different quality-of-service (QoS) constraints. By exploiting the multipacket reception (MPR) capability, the MQSR protocol adaptively grants access to the MPR channel to a number of users such that the expected number of successfully received packets is maximized in each slot. The optimal access protocol avoids unnecessary empty slots for light traffic and excessive collisions for heavy traffic. It has superior throughput and delay performance as compared to, for example, the slotted ALOHA with optimal retransmission probability. This protocol can be applied to random-access networks with multimedia traffic.

A decision feedback blind symbol estimation algorithm based on the least squares smoothing approach is proposed for single-input multiple-output finite impulse response systems. With the finite alphabet property, the input signal is estimated based on the past detected symbols and the least squares smoothing error of the observation. Implemented both time and order recursively, the proposed algorithm is adaptive to channel variation and has low complexity both in computation and in VLSI implementation. Based on a deterministic model, this algorithm has the finite sample convergence property, i.e., the input signal can be perfectly detected with a small set of data samples in the absence of noise.

A linear least squares smoothing approach is proposed for the blind channel estimation. It is shown that the single-input multiple-output moving average process has the property that the error sequence of the least squares smoother, under certain conditions, uniquely determines the channel impulse response. The relationship among the dimension of the observation space, channel order and smoothing delay is presented. A new algorithm for channel estimation based on the least squares smoothing is developed. The proposed approach has the finite-sample convergence property in the absence of the channel noise. It also has a structure suitable for recursive implementations.