Recent advances in Deep Neural Networks (DNNs) have demonstrated outstanding performance across various domains. However, their large size is a challenge for deployment on resource-constrained devices such as mobile, edge, and IoT platforms. To overcome this, a distributed inference setup can be used where a small-sized DNN (initial few layers) can be deployed on mobile, a bigger version on the edge, and the full-fledged DNN on the cloud. A sample that has less complexity (easy) could be then inferred on mobile, that has moderate complexity (medium) on edge, and higher complexity (hard) on the cloud. As the complexity of each sample is not known beforehand, the following question arises in distributed inference: how to decide complexity so that it is processed by enough layers of DNNs. We develop a novel approach named DIMEE that utilizes Early Exit (EE) strategies developed to minimize inference latency in DNNs. DIMEE aims to improve the accuracy, taking into account the offloading cost from mobile to edge/cloud. Experimental validation on GLUE datasets, encompassing various NLP tasks, shows that our method significantly reduces the inference cost ($>43 \%$) while maintaining a minimal drop in accuracy ($<0.3 \%$) compared to the case where all the inference is made in the cloud.11The source code is available at https://github.com/Div290/DIMEE

Early Exit (EE) techniques have emerged as a means to reduce inference latency in Deep Neural Networks (DNNs). The latency improvement and accuracy in these techniques crucially depend on the criteria used to make exit decisions. We propose a new decision criterion BEEM where exit classifiers are treated as experts and aggregate their confidence scores. The confidence scores are aggregated only if neighbouring experts are consistent in prediction as the samples pass through them, thus capturing their ensemble effect. A sample exits when the aggregated confidence value exceeds a threshold. The threshold is set using the error rates of the intermediate exits aiming to surpass the performance of conventional DNN inference. Experimental results on the COCO dataset for Image captioning and GLUE datasets for various language tasks demonstrate that our method enhances the performance of state-of-the-art EE methods, achieving improvements in speed-up by a factor $1.5\times$ to $2.1\times$. When compared to the final layer, its accuracy is comparable in harder Image Captioning and improves in the easier language tasks. The source code is available at https://github.com/Div290/BEEM1/tree/main.

Early-Exit Deep Neural Networks enable adaptive inference by allowing prediction at intermediary layers, significantly reducing computational costs and latency. Most of the early exit strategies greedily exit a sample at an intermediary layer if the confidence in class prediction exceeds a predefined threshold that is set using a static validation set. This is problematic as the model might be overconfident in a wrong class. Also, they are not robust to distribution shifts encountered in deployment, which can undermine model trustworthiness and accuracy. To address these challenges, we propose UAT that adapts the threshold for exit decisions using a Multi-Armed Bandit framework, enabling online, unsupervised adjustment of exit decisions. UAT makes decisions based on a new reward function that assesses predictive certainty and its reliability to balance computational efficiency and prediction quality while penalizing unnecessary late exits. We provide guarantees on risk achieved by UAT and validate its performance on diverse tasks spanning vision-language understanding, text generation, and classification. Our framework demonstrates consistent improvements in speedup $(1.70-2.10\times)$ with a minimal performance drop $(<2)$\% as compared to full model performance.

Deep Neural Networks (DNNs) have demonstrated exceptional performance in diverse tasks. However, deploying DNNs on resource-constrained devices presents challenges due to energy consumption and delay overheads. To mitigate these issues, early-exit DNNs (EE-DNNs) incorporate exit branches within intermediate layers to enable early inferences. These branches estimate prediction confidence and employ a fixed threshold to determine early termination. Nonetheless, fixed thresholds yield suboptimal performance in dynamic contexts, where context refers to distortions caused by environmental conditions, in image classification, or variations in input distribution due to concept drift, in NLP. In this article, we introduce Upper Confidence Bound in EE-DNNs (UCBEE), an online algorithm that dynamically adjusts early exit thresholds based on context. UCBEE leverages confidence levels at intermediate layers and learns without the need for true labels. Through extensive experiments in image classification and NLP, we demonstrate that UCBEE achieves logarithmic regret, converging after just a few thousand observations across multiple contexts. We evaluate UCBEE for image classification and text mining. In the latter, we show that UCBEE can reduce cumulative regret and lower latency by approximately 10%–20% without compromising accuracy when compared to fixed threshold alternatives. Our findings highlight UCBEE as an effective method for enhancing EE-DNN efficiency.

Divya Jyoti Bajpai, Ayush Maheshwari, Manjesh Hanawal, Ganesh Ramakrishnan. Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers). 2024.

The recent advances in Deep Neural Networks (DNNs) stem from their exceptional performance across various domains. However, deploying these networks on resource-constrained devices-like edge, mobile, and IoT platforms-is hindered by their inherent large size. Strategies have emerged, from partial cloud computation offloading (split computing) to integrating early exits within DNN layers. Our work presents an innovative unified approach merging early exits and split computing. We determine the ‘splitting layer’, the optimal depth in the DNN for edge device computations, and whether to infer on edge device or be offloaded to the cloud for inference considering accuracy, computational efficiency, and communication costs. Also, Image classification faces diverse environmental distortions, influenced by factors like time of day, lighting, and weather. To adapt to these distortions, we introduce I-SplitEE, an online unsupervised algorithm ideal for scenarios lacking ground truths and with sequential data. Experimental validation using Caltech-256 and Cifar-10 datasets subjected to varied distortions showcases I-SplitEE's ability to reduce costs by a minimum of 55% with marginal performance degradation of at most 5%.1

Holographic Metasurface Transceivers (HMTs) are emerging as cost-effective substitutes to large antenna arrays for beamforming in Millimeter and TeraHertz wave communication. However, to achieve desired channel gains through beamforming in HMT, phase-shifts of a large number of elements need to be appropriately set, which is challenging. Also, these optimal phase-shifts depend on the location of the receivers, which could be unknown. In this work, we develop a learning algorithm using a fixed-budget multi-armed bandit framework to beamform and maximize received signal strength at the receiver for far-field regions. Our algorithm, named Holographic Beam (HoloBeam) exploits the parametric form of channel gains of the beams, which can be expressed in terms of two phase-shifting parameters. Even after parameterization, the problem is still challenging as phase-shifting parameters take continuous values. To overcome this, HoloBeam works with the discrete values of phase-shifting parameters and exploits their unimodal relations with channel gains to learn the optimal values faster. We upper bound the probability of HoloBeam incorrectly identifying the (discrete) optimal phase-shift parameters in terms of the number of pilots used in learning. We show that this probability decays exponentially with the number of pilot signals. We demonstrate that HoloBeam outperforms state-of-the-art algorithms through extensive simulations.

Security and Privacy have become fundamental requirements of modern Internet services. Over the years, both Hypertext Transfer Protocol (HTTP) and Transport Layer Security (TLS) have evolved significantly to meet the performance, privacy and security demands of the web services. However, the usage of Service Name Identity (SNI) in TLS carry service-related information in plain-text, which potentially reveal the user’s activity and compromise the privacy. In this work, we analyse the performance, security and privacy trade-offs offered by the recent developments in HTTP and TLS protocols namely HTTP/3 and TLS1.3. Our results indicate the end-to-end performance of HTTP/3 and HTTP/2 to be very similar, but HTTP/3 offers better security and privacy. Further, we quantify the overheads associated with HTTP/3 and find that the computational complexity with HTTP/3 for SNI obfuscation and extraction from ‘ClientHello’ packets is nearly 10 times more than HTTP/2. Further, we find that the user-space implementations of QUIC in HTTP/3 are more compute-intensive and prone to be unstable. We conclude that a leaner alternative would be the adoption of "Encrypted ClientHello" (ECH), that proposes to overcome this privacy issue by extending TLS 1.3, where all the information that could potentially reveal the service type is encrypted using a public key. The widespread adoption of TLS 1.3 with ECH is imperative to enable complete privacy in web services.

Holographic metasurface transceivers (HMT) are an emerging technology for enhancing the coverage and rate of wireless communication systems. However, acquiring accurate channel state information in HMT-assisted wireless communication systems is critical for achieving these goals. In this paper, we propose an algorithm for learning the optimal phase-shifts at an HMT for the far-field channel model. Our proposed algorithm exploits the structure of the channel gains in the far-field regions and learns the optimal phase-shifts in the presence of noise in the received signals. We prove that the probability that the optimal phase-shifts estimated by our proposed algorithm deviate from the true values decays exponentially in the number of pilot signals. Extensive numerical simulations validate the theoretical guarantees and also demonstrate significant gains as compared to the state-of-the-art policies.

One of the core problems in millimeter wave (mmWave) massive multiple-input-single-output (MISO) communication systems, which significantly affects the data rate, is the misalignment of the beam direction of the transmitter towards the receiver. In this paper, we investigate strategies that identify the best beam within a fixed duration of time. To this end, we develop an algorithm, namedUnimodal Bandit for Best Beam (UB3), that exploits the unimodal structure of the mean received signal strength as a function of the available beams and identifies the best beam within a fixed time duration using pure exploration strategies. We derive an upper bound on the probability of misidentifying the best beam, and we prove that the upper bound is of the orderO(log2Kexp {-αnA}), whereKis the number of beams,Ais a problem-dependent constant, and αnis the number of pilots used in the channel estimation phase. In contrast, when the unimodal structure is not exploited, the error probability is of orderO(log2Kexp {-αnA/(KlogK)}). Thus, by exploiting the unimodal structure, we achieve a much better error probability, which depends only logarithmically onK. We demonstrate thatUB3outperforms the state-of-the-art algorithms through extensive simulations.

In wireless networks, the transmitter adapts its parameters based on the receiver’s feedback to achieve a high throughput. The throughput also depends on factors like interference level and channel gain, which can be measured at the transmitter. They provide useful information about the instantaneous throughput as well. For example, higher interference implies a lower throughput. This work treats any measurable quality with a non-zero correlation with the throughput as side information (SI). We also study how it can be exploited to quickly learn the channel that offers higher throughput (reward). When the mean value of the SI is known, using control variate theory, we develop online learning algorithms that require fewer samples to learn and can improve the learning rate compared to cases where SI is ignored. Specifically, we incorporated SI in the Upper Confidence Bound (UCB) algorithm and proposed the UCBwSI algorithm. We quantify the gain achieved in terms of the regret and show that the improvement in regret over state-of-the-art UCB is proportional to the correlation between the reward and SI. Simulations demonstrate a 5-10% improvement in the bit-error rate. Even when the mean of the SI is unknown, we demonstrate the superiority of the UCBwSI over UCB.

Deep Neural Networks (DNNs) are widely used to solve a growing number of tasks, such as image classification. However, their deployment at resource-constrained devices still poses challenges related to energy consumption and delay over-heads. Early-Exit DNNs (EE-DNNs) address the challenges by adding side branches through their architecture. Under an edge-cloud co-inference, if the confidence at a side branch is larger than a fixed confidence threshold, the inference is performed completely at the edge device, saving computation for more difficult observations. Otherwise, the edge device offloads the inference task to the cloud, incurring overhead. Despite its success, EE-DNNs for image classification have to cope with distorted images. The baseline distortion level depends on the environmental context, e.g., time of the day, lighting, and weather conditions. To cope with varying distortion, we propose Adaptive Early-Exit in Deep Neural Networks (AdaEE), a novel algorithm to dynamically adjust the confidence threshold based on context, leveraging the Upper Confidence Bound (UCB) for that matter. AdaEE provably achieves logarithmic regret under mild conditions. We experimentally verify that 1) convergence occurs after collecting a few thousand observations for images with different distortion levels and overhead values, and 2) AdaEE obtains a lower cumulative regret when compared against alternatives using the Caltech-256 dataset subject to varying distortion.

We study the problem of best-arm identification in a distributed variant of the multi-armed bandit setting, with a central learner and multiple agents. Each agent is associated with an arm of the bandit, generating stochastic rewards following a distribution that is a priori unknown to the learner. Further, each agent can communicate the observed rewards with the learner over a bit-constrained channel. We propose a novel quantization scheme called ICQ that can be applied to existing confidence-bound based learning algorithms such as Successive Elimination and requires only an exponentially sparse frequency of communication between the learner and the agents. We analyze the performance of ICQ applied to Successive Elimination, and show that the overall algorithm, which we call ICQ-SE, has order-optimal sample complexity and uses considerably fewer bits than existing quantization schemes to successfully identify the best arm. We are also able to verify our findings via numerical experiments.

We consider a continuous time multi-arm bandit problem (CTMAB), where the learner can sample arms any number of times in a given interval and obtain a random reward from each sample, however, increasing the frequency of sampling incurs an additive penalty/cost. Thus, there is a tradeoff between obtaining large reward and incurring sampling cost as a function of the sampling frequency. The goal is to design a learning algorithm that minimizes the regret. We establish lower bounds on the regret achievable with any algorithm, and propose algorithms that achieve the lower bound up to logarithmic factors. For the single arm case, we show that the lower bound on the regret is$\Omega(1/\mu)$, and an upper bound with regret$O((\log(T/\lambda))^{2}/\mu)$, where$\mu$is the mean of the arm,$T$is the time horizon, and$\lambda$is the tradeoff parameter between the reward and the sampling cost. With$K$arms, we show that the lower bound on the regret is$\Omega(K\mu[1]/\Delta^{2})$, and an upper bound$O(K(\log(T/\lambda))^{2}\mu[1]/\Delta^{2})$where$\mu$[1] now represents the mean of the best arm, and$\Delta$is the difference of the mean of the best and the second-best arm.

Network neutrality is related to the non-discriminatory treatment of packets on the Internet. Any deliberate discrimination of traffic of one application while favoring others violates the principle of neutrality. Many countries have enforced laws against such discrimination. One requires tools to detect any net neutrality violations to enforce such laws. However, detecting such violations is challenging as it is hard to separate any degradation in quality due to natural network effects and selective degradation. Also, legitimate traffic management and deliberate discrimination methods can be technically the same, making it challenging to distinguish them further. We developed an end-to-end measurement framework named FairNet to detect discrimination of traffic. It compares the performance of similar services. Our focus is on HTTPS streaming services which constitute a predominant portion of the Internet traffic. The effect of confounding factors (congestion, traffic management policy, dynamic rate adaptation) is made ‘similar’ on the test services to ensure a fair comparison. FairNet framework uses a ‘replay server’ and user-client that exchanges correctly identifiable traffic streams over the Internet. The Server Name Indication (SNI) field in the TLS handshake, which goes in plain text, ensures that the traffic from the replay server appears to network middle-boxes as that coming from its actual server. We validated that appropriate SNIs result in the correct classification of services using a commercial traffic shaper. FairNet uses two novel algorithms based on application-level throughput and connection status to detect traffic discrimination. We also validated the methodology’s effectiveness by collecting network logs through mobile apps over the live Internet and analyzing them.

We consider a system with a single source that measures/tracks a time-varying quantity and periodically attempts to report these measurements to a monitoring station. Each update from the source has to be scheduled on one of$K$available communication channels. The probability of success of each attempted communication is a function of the channel used. This function is unknown to the scheduler. The metric of interest is the Age-of-Information (AoI), formally defined as the time elapsed since the destination received the recent most update from the source. We model our scheduling problem as a variant of the multi-arm bandit problem with communication channels as arms. We characterize a lower bound on the AoI regret achievable by any policy and characterize the performance of UCB, Thompson Sampling, and their variants. Our analytical results show that UCB and Thompson sampling are order-optimal for AoI bandits. In addition, we propose novel policies which, unlike UCB and Thompson Sampling, use the current AoI to make scheduling decisions. Via simulations, we show the proposed AoI-aware policies outperform existing AoI-agnostic policies.

To bring large-scale artificial intelligence of things (AIoT) to reality, wireless networks need intelligence to identify resources in a limited shared noncontiguous spectrum. In this article, we address this challenge via a sub-Nyquist sampling-based wideband spectrum analyzer deployed in the AIoT gateway. The noncontiguous nature demands learning the channel occupancy. However, the identification of channel status can fail when the number of busy channels in a selected subset is higher than the number of analog-to-digital converters,$K$. We model this subset selection problem as multiplay multiarmed bandit. First, we demonstrate the learnability of such a problem via a learning algorithm with a subset size of$K$(no sensing failure). For wideband sparse spectrum, we extend this algorithm using a novel subset size estimation approach to identify the optimal subset that gives the best possible throughput and could have a size potentially larger than$K$. These algorithms are mapped on the system-on-chip, and in-depth performance analysis demonstrates their superiority over state-of-the-art approaches.

It has been a long demand of Internet Service Providers (ISPs) that the Content Providers (CPs) share their profits for investments in network infrastructure. In this paper, we study profit sharing contracts between a CP with multiple ISPs. Each ISP commits to improving the Quality of Service (QoS) for the end-users through higher investments efforts. The CP agrees to share the profits due to the resulting higher demand for its content. We first model non-cooperative interaction between the CP and the ISPs as a two-stage Stackelberg game. CP is the leader that decides what fraction of its profits will be shared with the ISPs. Each ISP then simultaneously decides the amount of effort (investment) to enhance network quality. Here, CP cannot observe individual effort by the ISPs, which poses a challenge for the CP to decide how to share the profits with each ISP. Therefore, we also investigate a cooperative scenario, where the CP only decides the total share it gives to the ISPs, and each ISP then cooperatively shares the profit among themselves. We study the effect of such cooperation between the ISPs by building a Nash Bargaining based model. We show that the collaboration improves total effort by the ISPs and the payoff of the CP.

Recursive neural networks (RvNN) have been shown useful for learning sentence representations and helped achieve competitive performance on several natural language inference tasks. However, recent RvNN-based models fail to learn simple grammar and meaningful semantics in their intermediate tree representation. In this work, we propose an attention mechanism over Tree-LSTMs to learn more meaningful and explainable parse tree structures. We also demonstrate the superior performance of our proposed model on natural language inference, semantic relatedness, and sentiment analysis tasks and compare them with other state-of-the-art RvNN based methods. Further, we present a detailed qualitative and quantitative analysis of the learned parse trees and show that the discovered linguistic structures are more explainable, semantically meaningful, and grammatically correct than recent approaches. The source code of the paper is available here.

This paper studies a new variant of the stochastic multi-armed bandits problem where auxiliary information about the arm rewards is available in the form of control variates. In many applications like queuing and wireless networks, the arm rewards are functions of some exogenous variables. The mean values of these variables are known a priori from historical data and can be used as control variates. Leveraging the theory of control variates, we obtain mean estimates with smaller variance and tighter confidence bounds. We develop an upper confidence bound based algorithm named UCB-CV and characterize the regret bounds in terms of the correlation between rewards and control variates when they follow a multivariate normal distribution. We also extend UCB-CV to other distributions using resampling methods like Jackknifing and Splitting. Experiments on synthetic problem instances validate performance guarantees of the proposed algorithms.

Thompson Sampling has generated significant interest due to its better empirical performance than upper confidence bound based algorithms. In this paper, we study Thompson Sampling based algorithm for Unsupervised Sequential Selection (USS) problem. The USS problem is a variant of the stochastic multi-armed bandits problem, where the loss of an arm can not be inferred from the observed feedback. In the USS setup, arms are associated with fixed costs and are ordered, forming a cascade. In each round, the learner selects an arm and observes the feedback from arms up to the selected arm. The learner’s goal is to find the arm that minimizes the expected total loss. The total loss is the sum of the cost incurred for selecting the arm and the stochastic loss associated with the selected arm. The problem is challenging because, without knowing the mean loss, one cannot compute the total loss for the selected arm. Clearly, learning is feasible only if the optimal arm can be inferred from the problem structure. As shown in the prior work, learning is possible when the problem instance satisfies the so-called ‘Weak Dominance’ (WD) property. Under WD, we show that our Thompson Sampling based algorithm for the USS problem achieves near optimal regret and has better numerical performance than existing algorithms.

The opportunistic spectrum access (OSA) algorithms allow secondary users (SUs) to exploit vacant channels with an aim to maximize overall spectrum utilization/throughput. The design of OSA algorithm is challenging for ad hoc networks due to lack of coordination among SUs and unknown channel statistics. It becomes even more challenging for the dynamic networks where the SUs can enter or leave the network any time without prior agreement. Most of the existing algorithms assume either prior knowledge of the number of SUs or need wideband sensing to sense all channels simultaneously to guarantee optimal channel allocation among SUs. Our goal in this paper is to develop distributed OSA algorithm for dynamic ad hoc networks that offers higher throughput without compromising on the number of SUs collisions. The proposed distributed algorithm is based on multi-player multi-arm bandit framework and they allow SUs to independently estimate the number of other SUs and channel statistics. We derive the upper bounds on the throughput loss (regret) and number of collisions. Exhaustive synthetic results and experimental results on universal software radio peripherals (USRP) based testbed validate our claims and superiority of the proposed algorithm.

In this paper, we study a novel Stochastic Network Utility Maximization (NUM) problem where the utilities of agents are unknown. The utility of each agent depends on the amount of resource it receives from a network operator/controller. The operator desires to do a resource allocation that maximizes the expected total utility of the network. We consider threshold type utility functions where each agent gets non-zero utility if the amount of resource it receives is higher than a certain threshold. Otherwise, its utility is zero (hard real-time). We pose this NUM setup with unknown utilities as a regret minimization problem. Our goal is to identify a policy that performs as `good' as an oracle policy that knows the utilities of agents. We model this problem setting as a bandit setting where feedback obtained in each round depends on the resource allocated to the agents. We propose algorithms for this novel setting using ideas from Multiple-Play Multi-Armed Bandits and Combinatorial Semi-Bandits. We show that the proposed algorithm is optimal when all agents have the same utility. We validate the performance guarantees of our proposed algorithms through numerical experiments.

In this paper, we study Contextual Unsupervised Sequential Selection (USS), a new variant of the stochastic contextual bandits problem where the loss of an arm cannot be inferred from the observed feedback. In our setup, arms are associated with fixed costs and are ordered, forming a cascade. In each round, a context is presented, and the learner selects the arms sequentially till some depth. The total cost incurred by stopping at an arm is the sum of fixed costs of arms selected and the stochastic loss associated with the arm. The learner's goal is to learn a decision rule that maps contexts to arms with the goal of minimizing the total expected loss. The problem is challenging as we are faced with an unsupervised setting as the total loss cannot be estimated. Clearly, learning is feasible only if the optimal arm can be inferred (explicitly or implicitly) from the problem structure. We observe that learning is still possible when the problem instance satisfies the so-called 'Contextual Weak Dominance' (CWD) property. Under CWD, we propose an algorithm for the contextual USS problem and demonstrate that it has sub-linear regret. Experiments on synthetic and real datasets validate our algorithm.

Efficient utilization of licensed spectrum in the cognitive radio network is challenging due to lack of coordination among the Secondary Users (SUs). Distributed algorithms proposed in the literature aim to maximize the network throughput by ensuring orthogonal channel allocation for the SUs. However, these algorithms work under the assumption that all the SUs faithfully follow the algorithms which may not always hold due to the decentralized nature of the network. In this paper, we study distributed algorithms that are robust against malicious behavior (jamming attack). We consider both the cases of jammers launching coordinated and uncoordinated attacks. In the coordinated attack, the jammers select non-overlapping channels to attack in each time slot and can significantly increase the number of collisions for SUs. We setup the problem in each scenario as a multi-player bandit and develop algorithms. The analysis shows that when the SUs faithfully implement proposed algorithms, the regret is constant with high probability. We validate our claims through exhaustive synthetic experiments and also through a realistic USRP based experiment.

The ongoing net neutrality debate has generated a lot of heated discussions on whether or not monetary interactions should be regulated between content and access providers. Among the several topics discussed, `differential pricing' has recently received attention due to `zero-rating' platforms proposed by some service providers. In the differential pricing scheme, Internet Service Providers (ISPs) can exempt data access charges for on content from certain CPs (zero-rated) while no exemption is on content from other CPs. This allows the possibility for Content Providers (CPs) to make `sponsorship' agreements to zero-rate their content and attract more user traffic. In this article, we study the effect of differential pricing on various players in the Internet. We first consider a model with a monopolistic ISP and multiple CPs where users select CPs based on the quality of service (QoS) and data access charges. We show that in a differential pricing regime 1) it is possible for a CP to obtain higher utility than a CP offering better QoS through higher subsidy at user equilibrium 2) Overall QoS (mean delay) for end users can degrade under differential pricing schemes. In the oligopolistic market with multiple ISPs, ISPs tend to set equal access prices at equilibrium and similar conclusions are derived as in the monopolistic market.

In many security and healthcare systems, the detection and diagnosis systems use a sequence of sensors/tests. Each test outputs a prediction of the latent state and carries an inherent cost. However, the correctness of the predictions cannot be evaluated due to unavailability of the ground-truth annotations. Our objective is to learn strategies for selecting a test that gives the best trade-off between accuracy and costs in such unsupervised sensor selection (USS) problems. Clearly, learning is feasible only if ground truth can be inferred (explicitly or implicitly) from the problem structure. It is observed that this happens if the problem satisfies the ’Weak Dominance’ (WD) property. We set up the USS problem as a stochastic partial monitoring problem and develop an algorithm with sub-linear regret under the WD property. We argue that our algorithm is optimal and evaluate its performance on problem instances generated from synthetic and real-world datasets.

We consider an ad hoc network where multiple users access the same set of channels. The channel characteristics are unknown and could be different for each user (heterogeneous). No controller is available to coordinate channel selections by the users, and if multiple users select the same channel, they collide and none of them receive any rate (or reward). For such a completely decentralized network we develop algorithms that aim to achieve optimal network throughput. Due to lack of any direct communication between the users, we allow each user to exchange information by transmitting in a specific pattern and sense such transmissions from others. However, such transmissions and sensing for information exchange do not add to network throughput. For the wideband sensing and narrowband sensing scenarios, we first develop explore-and-commit algorithms that converge to near-optimal allocation with high probability in a small number of rounds. Building on this, we develop an algorithm that gives logarithmic regret. We validate our claims through extensive experiments and show that our algorithms perform significantly better than the state-of-the-art CSM-MAB, dE3and dE3-TS algorithms.

In this paper, we study Censored Semi-Bandits, a novel variant of the semi-bandits problem. The learner is assumed to have a fixed amount of resources, which it allocates to the arms at each time step. The loss observed from an arm is random and depends on the amount of resources allocated to it. More specifically, the loss equals zero if the allocation for the arm exceeds a constant (but unknown) threshold that can be dependent on the arm. Our goal is to learn a feasible allocation that minimizes the expected loss. The problem is challenging because the loss distribution and threshold value of each arm are unknown. We study this novel setting by establishing its `equivalence' to Multiple-Play Multi-Armed Bandits (MP-MAB) and Combinatorial Semi-Bandits. Exploiting these equivalences, we derive optimal algorithms for our setting using existing algorithms for MP-MAB and Combinatorial Semi-Bandits. Experiments on synthetically generated data validate performance guarantees of the proposed algorithms.

A distributed sampling strategy for multiple (N) agents is considered that minimizes the sample complexity and regret of acquiring the best subset of size N among total K ≥ N channels in a cognitive radio access setup. Agents cannot directly communicate with each other, and no central coordination is possible. Each agent can transmit on one channel at a time, and if multiple agents transmit on the same channel at the same time, a collision occurs, and no agent gets any information about the channel gain or how many other agents transmitted on the same channel. If no collision occurs, the agent observes a reward (or gain) sample drawn from an underlying distribution associated with the channel. An algorithm to minimize the sample complexity and regret is proposed. One important property of our algorithm that distinguishes it from the prior work (that do not assume knowledge of N) is that it requires no information about the difference of the means of the channel gains of the K channels. Our approach results in fewer collisions with improved regret performance compared to the state-of-the-art algorithms. We validate our theoretical guarantees with experiments.

Next generation networks are expected to be ultra-dense and aim to explore spectrum sharing paradigm that allows users to communicate in licensed, shared as well as unlicensed spectrum. Such ultra-dense networks will incur significant signaling load at base stations leading to a negative effect on spectrum and energy efficiency. To minimize signaling overhead, an ad-hoc approach is being considered for users communicating in the unlicensed and shared spectrums. For such users, decisions need to be completely decentralized as: 1) No communication between users and signaling from the base station is possible which necessitates independent channel selection at each user. A collision occurs when multiple users transmit simultaneously on the same channel, 2) Channel qualities may be heterogeneous, i.e., they are not same across all users, and moreover, are unknown, and 3) The network could be dynamic where users can enter or leave anytime. We develop a multi-armed bandit based distributed algorithm for static networks and extend it for the dynamic networks. The algorithms aim to achieve stable orthogonal allocation (SOC) in finite time and meet the above three constraints with two novel characteristics: 1) Low complexity narrowband radio compared to wideband radio in existing works, and 2) Epoch-less approach for dynamic networks. We establish convergence of our algorithms to SOC and validate via extensive simulation experiments.

The ongoing net neutrality debate has generated a lot of heated discussions on whether or not monetary interactions should be regulated between content and access providers. Among the several topics discussed, `differential pricing' has recently received attention due to `zero-rating' platforms proposed by some service providers. In the differential pricing scheme, Internet Service Providers (ISPs) can exempt data traffic charges for accessing content from certain Content Providers (CPs) or applications (zero-rated) and apply regular charges for accessing content from other CPs. This allows the possibility for CPs to make `sponsorship' agreements to zero-rate their content and attract more user traffic. In this paper, we study the effect of differential pricing on various players in the Internet. We consider a model with a single ISP and multiple CPs where users select CPs based on the quality of service (QoS) and applicable traffic charges. We show that in a differential pricing regime 1) a CP offering low QoS can make more revenues than a CP offering better QoS through sponsorships. 2) QoS (mean delay) for end users can degrade compared to the case where no differential pricing is allowed.

An opportunistic spectrum access (OSA) in the infrastructure-less network has received significant attention in last few years due to their ability to improve spectrum utilization as well as usefulness in the infrastructure-less networks established for disaster relief and military applications. The main research problem for feasible implementation of such network is to achieve coordination among secondary users (SUs) (i.e. unlicensed users). Existing algorithms incur a significant number of collisions which in turn require retransmissions and hence, lead to inefficient use of battery power, spectrum and time. In this paper, we set-up the problem as a multi-player Bandit and develop a new distributed algorithm which allows SUs to select one of the top channels with a significantly fewer number of collisions. We show that the proposed algorithm has constant regret with high confidence. We validate our claims and the superiority of the proposed algorithm over existing state-of-the-art algorithms through the exhaustive simulated experiments as well as a realistic USRP based experiments in the real radio environment.

Efficient utilization of licensed spectrum in the cognitive radio network is challenging due to lack of coordination among the Secondary Users (SUs). Distributed algorithms proposed in the literature aim to maximize the network throughput by ensuring orthogonal channel allocation for the SUs. However, these algorithms work under the assumption that all the SUs faithfully follow the algorithms which may not always hold due to the decentralized nature of the network. Moreover, they are vulnerable to Denial of Service attacks. In this paper, we study distributed algorithms that are robust against malicious behavior (jamming attack). We consider jammers launching coordinated attack where they select non-overlapping channels in each time slot and can lead to significantly higher number of collisions for SUs than uncoordinated attack. We setup the problem as a multiplayer bandit and develop distributed learning algorithms. The analysis shows that when the SUs faithfully implement proposed algorithms, the regret is constant with high probability. We validate our claims through exhaustive synthetic experiments and also through a realistic USRP based experiments.

In many security and healthcare systems a sequence of sensors/tests are used for detection and diagnosis. Each test outputs a prediction of the latent state, and carries with it inherent costs. Our objective is to learn strategies for selecting tests to optimize accuracy and costs. Unfortunately it is often impossible to acquire in-situ ground truth annotations and we are left with the problem of unsupervised sensor selection (USS). We pose USS as a version of stochastic partial monitoring problem with an unusual reward structure (even noisy annotations are unavailable). Unsurprisingly no learner can achieve sublinear regret without further assumptions. To this end we propose the notion of weak-dominance. This is a condition on the joint probability distribution of test outputs and latent state and says that whenever a test is accurate on an example, a later test in the sequence is likely to be accurate as well.

Throughput of a mobile ad hoc network (MANET) operating on an unlicensed spectrum can increase if nodes can also transmit on a (shared) licensed spectrum. However, the transmissions on the licensed spectrum has to be limited to avoid degradation of quality of service (QoS) to primary users (PUs). We address the problem of how the nodes of a MANET or secondary users (SUs) should spread their transmissions on both licensed and unlicensed spectra to maximize network throughput, and characterize ‘throughput gain’ achieved in such spectrum sharing systems. We show that the gain can be significant and is increasing in the density of the SUs. The primary and secondary users are modeled as two independent Poisson point processes and their performance is evaluated using techniques from stochastic geometry.

We study stochastic linear optimization problem with bandit feedback. The set of arms take values in an N-dimensional space and belongs to a bounded polyhedron described by finitely many linear inequalities. We present an algorithm that has O(Nlog1+ε(T)) expected regret for any ε > 0 in T rounds. The algorithm alternates between exploration and exploitation phases where it plays a deterministic set of arms in the exploration phases and a greedily selected arm in the exploitation phases. The regret bound of SEE compares well to the lower bounds of Ω(N log T) that can be derived by a direct adaptation of Lai-Robbin's lower bound proof [1]. Our key insight is that for a polyhedron the optimal arm is robust to small perturbations in the reward function. Consequently, a greedily selected arm is guaranteed to be optimal when the estimation error falls below a suitable threshold. Our solution resolves a question posed by [2] that left open the possibility of efficient algorithms with logarithmic regret bounds. The simplicity of our approach allows us to derive probability one bounds on the regret, in contrast to the weak convergence results of other papers. This ensures that with probability one only finitely many errors occur in the exploitation phase. Numerical investigations show that while theoretical results are asymptotic the performance of our algorithms compares favorably to state-of-the-art algorithms in finite time as well.

Recent advances in the design of in-band full-duplex (IBFD) radios promise to double the throughput of a wireless link. However, IBFD-capable nodes are more vulnerable to jamming attacks than their out-of-band full-duplex (OBFD) counterparts, and any advantages offered by them over the OBFD nodes can be jeopardized by such attacks. A jammer needs to attack both the uplink and the downlink channels to completely break the communication link between two OBFD nodes. In contrast, he only needs to jam one channel (used for both uplink and downlink) in the case of two IBFD nodes. Even worse, a jammer with the IBFD capability can learn the transmitters' activity while injecting interference, allowing it to react instantly with the transmitter's strategies. In this paper, we investigate frequency hopping (FH) technique for countering jamming attacks in the context of IBFD wireless radios. Specifically, we develop an optimal strategy for IBFD radios to combat an “IBFD reactive sweep jammer”. First, we introduce two operational modes for IBFD radios: transmission reception and transmission-detection. These modes are intended to boost the anti-jamming capability of IBFD radios. We then jointly optimize the decision of when to switch between the modes and when to hop to a new channel using Markov decision processes. Numerical investigations show that our policy significantly improves the throughput of IBFD nodes under jamming attacks.

Wireless transmissions are inherently vulnerable to jamming attacks. Frequency hopping (FH) and transmission rate adaptation (RA) have been separately used to mitigate jamming. When RA is used alone, it has been shown that a jammer who randomizes its power levels can force the transmitter toalwaysoperate at the lowest rate, by maintaining the average jamming power above a certain threshold. On the other hand, when only FH is used, a high throughput overhead is incurred due to frequent channel switching. In this paper, we propose to mitigate jamming by jointly optimizing the FH and RA techniques. This way, the transmitter can escape the jammer by changing its channel, adjusting its rate, or both. We consider a power-constrained “reactive-sweep” jammer who aims at degrading the throughput of the wireless link. The jammer sweeps through the set of channels, jamming a subset of them at a time, using the optimal jamming power. We model the interactions between the legitimate transmitter and jammer as a constrained zero-sum Markov game. The transmitter’s optimal defense strategy is derived by obtaining the equilibria of the constrained Markov game. This policy informs the transmitter when to hop to another channel and when to stay on the current channel. Furthermore, it gives the best transmission rate to use in both cases (hop or stay). The structure of the transmitter’s optimal policy is shown to be threshold type, whereby the transmitter stays on the same channel up to a certain number of time slots after which it hops. We analyze the “constrained Nash equilibrium” of the Markov game and show that the equilibrium defense strategy of the transmitter is deterministic. Numerical investigations show that the new scheme improves the average throughput and provides better jamming resiliency.

The problem of efficiently identifying regions of interest arises in the context of surveillance, monitoring and exploration of a large area or network involving social, sensor, communication network data. We formulate these problems in terms of locating optimum values of signals on graphs. In this perspective we associate features with nodes/edges of a graph where the maxima/minima of these features correspond to interest points. We develop an algorithm that adaptively probes local sub-collection of nodes (local regions) on the graph and sequentially refines the search space from noisy averaged returns from each probed region. The size of the region determines the cost of the probe with larger regions corresponding to lower cost. Our goal is to minimize regret after T rounds with minimal budget/cost. Under suitable smoothness conditions on the signal we show that after T rounds the cumulative regret scales optimally as O(equation) with significant cost gain over other state-of-art techniques.

We consider stochastic sequential learning problems where the learner can observe the average reward of several actions. Such a setting is interesting in many applications involving monitoring and surveillance, where the set of the actions to observe represent some (geographical) area. The importance of this setting is that in these applications, it is actually cheaper to observe average reward of a group of actions rather than the reward of a single action. We show that when the reward is smooth over a given graph representing the neighboring actions, we can maximize the cumulative reward of learning while minimizing the sensing cost. In this paper we propose CheapUCB, an algorithm that matches the regret guarantees of the known algorithms for this setting and at the same time guarantees a linear cost again over them. As a by-product of our analysis, we establish a Ω(\sqrt(dT)) lower bound on the cumulative regret of spectral bandits for a class of graphs with effective dimension d.

Wireless transmissions are inherently broadcast and are vulnerable to jamming attacks. Frequency hopping (FH) and transmission rate adaptation (RA) have been used to mitigate jamming. However, recent works have shown that using either FH or RA (but not both) is inefficient against smart jamming. In this paper, we propose mitigating jamming by jointly optimizing the FH and RA techniques. We consider a power constrained “reactive-sweep” jammer who aims at degrading the goodput of a wireless link. We model the interaction between the legitimate transmitter and jammer as a zero-sum Markov game, and derive the optimal defense strategy. Numerical investigations show that the new scheme improves the average goodput and provides better jamming resiliency.

Representatives of several Internet service providers (ISPs) have expressed their wish to see a substantial change in the pricing policies of the Internet. In particular, they would like to see content providers (CPs) pay for use of the network, given the large amount of resources they use. This would be in clear violation of the “network neutrality” principle that had characterized the development of the wireline Internet. Our first goal in this article is to propose and study possible ways of implementing such payments and of regulating their amount. We introduce a model that includes the users' behavior, the utilities of the ISP and of the CPs, and, the monetary flow that involves the content users, the ISP and CP, and, in particular, the CP's revenues from advertisements. We consider various game models and study the resulting equilibria; they are all combinations of a noncooperative game (in which the ISPs and CPs determine how much they will charge the users) with a “cooperative” one on how the CP and the ISP share the payments. We include in our model a possible asymmetric weighting parameter (that varies between zero to one). We also study equilibria that arise when one of the CPs colludes with the ISP. We also study two dynamic game models as well as the convergence of prices to the equilibrium values.

This paper studies the performance of Mobile Ad hoc Networks (MANETs) when the nodes, that form a Poisson point process, selfishly choose their Medium Access Probability (MAP). We consider goodput and delay as the performance metric that each node is interested in optimizing taking into account the transmission energy costs. We introduce a pricing scheme based on the transmission energy requirements and compute the symmetric Nash equilibria of the game in closed form. It is shown that by appropriately pricing the nodes, the selfish behavior of the nodes can be used to achieve the social optimum at equilibrium. The price of anarchy is then analyzed for these games. For the game with delay based utility, we bound the price of anarchy and study the effect of the price factor. For the game with goodput based utility, it is shown that price of anarchy is infinite at the price factor that achieves the global optima.

This paper studies the performance of a wireless network when the nodes, that form a Poisson point process, selfishly choose their Medium Access Probability (MAP). We define the utility of each node as a weighted difference between a performance metric and some transmission costs. We consider expected goodput and expected delay as the performance metrics. The relative preference of nodes for their performance metrics and the transmission costs is represented by a tradeoff factor. We first consider a scenario in which nodes can be priced for the channel access. We relate the tradeoff factor to some pricing mechanism and compute the symmetric Nash equilibria of the game in closed form as a function of the price factor. We show that simple pricing mechanisms can be used to maximize system efficiency. In particular, we show that for a specific value of price factor, the selfish behavior of the nodes can be used to achieve the same performance as social optima at equilibrium. In the case without pricing where the dis-utility coincides with the transmission energy costs, we analyze the Price of Anarchy for these games. For the game with goodput based utility, we show that the Price of Anarchy is infinite at the tradeoff factor that achieves the global optimal goodput. For the game with delay based utility, we bound the Price of Anarchy and study the effect of the tradeoff factor.

The problem of guessing a random string is revisited. A close relation between guessing and compression is first established. Then it is shown that if the sequence of distributions of the information spectrum satisfies the large deviation property with a certain rate function, then the limiting guessing exponent exists and is a scalar multiple of the Legendre-Fenchel dual of the rate function. Other sufficient conditions related to certain continuity properties of the information spectrum are briefly discussed. This approach highlights the importance of the information spectrum in determining the limiting guessing exponent. All known prior results are then re-derived as example applications of our unifying approach.

The Shannon cipher system is studied in the context of general sources using a notion of computational secrecy introduced by Merhav and Arikan. Bounds are derived on limiting exponents of guessing moments for general sources. The bounds are shown to be tight for i.i.d., Markov, and unifilar sources, thus recovering some known results. A close relationship between error exponents and correct decoding exponents for fixed rate source compression on the one hand and exponents for guessing moments on the other hand is established.

The Shannon cipher system is studied in the context of general sources using a notion of computational secrecy introduced by Merhav & Arikan. Bounds are derived on limiting exponents of guessing moments for general sources. The bounds are shown to be tight for iid, Markov, and unifilar sources, thus recovering some known results. A close relationship between error exponents and correct decoding exponents for fixed rate source compression on the one hand and exponents for guessing moments on the other hand is established.