Given a vector of probability distributions, or arms, each of which can be sampled independently, we consider the problem of identifying the partition to which this vector belongs from a finitely partitioned universe of such vector of distributions. We study this as a pure exploration problem in multi-armed bandit settings and develop sample complexity bounds on the total mean number of samples required for identifying the correct partition with high probability. This framework subsumes well studied problems such as finding the best arm or the best few arms. We consider distributions belonging to the single parameter exponential family and primarily consider partitions where the vector of means of arms lie either in a given set or its complement. The sets considered correspond to distributions where there exists a mean above a specified threshold, where the set is a half space and where either the set or its complement is a polytope, or more generally, a convex set. In these settings, we characterize the lower bounds on mean number of samples for each arm highlighting their dependence on the problem geometry. Further, inspired by the lower bounds, we propose algorithms that can match these bounds asymptotically with decreasing probability of error. Applications of this framework may be diverse. We briefly discuss a few associated with simulation in finance.

In small-cell wireless networks where users are connected to multiple base stations (BSs), it is often advantageous to switch OFF dynamically a subset of BSs to minimize energy costs. We consider two types of energy cost: 1) the cost of maintaining a BS in the active state and 2) the cost of switching a BS from the active state to inactive state. The problem is to operate the network at the lowest possible energy cost (sum of activation and switching costs) subject to queue stability. In this setting, the traditional approach-a Max-Weight algorithm along with a Lyapunov-based stability argument-does not suffice to show queue stability, essentially due to the temporal co-evolution between channel scheduling and the BS activation decisions induced by the switching cost. Instead, we develop a learning and BS activation algorithm with slow temporal dynamics, and a Max-Weight-based channel scheduler that has fast temporal dynamics. We show that using convergence of time-inhomogeneous Markov chains, that the co-evolving dynamics of learning, BS activation and queue lengths lead to near optimal average energy costs along with queue stability.

In small-cell wireless networks where users are connected to multiple base stations (BSs), it is often advantageous to opportunistically switch off a subset of BSs to minimize energy costs. We consider two types of energy cost: (i) the cost of maintaining a BS in the active state, and (ii) the cost of switching a BS from the active state to inactive state. The problem is to operate the network at the lowest possible energy cost (sum of activation and switching costs) subject to queue stability. In this setting, the traditional approach - a Max-Weight algorithm along with a Lyapunov-based stability argument - does not suffice to show queue stability, essentially due to the temporal co-evolution between channel scheduling and the BS activation decisions induced by the switching cost. Instead, we develop a learning and BS activation algorithm with slow temporal dynamics, and a Max-Weight based channel scheduler that has fast temporal dynamics. We show using convergence of time-inhomogeneous Markov chains, that the co-evolving dynamics of learning, BS activation and queue lengths lead to near optimal average energy costs along with queue stability.

With increasing data demand, wireless networks are evolving to a hierarchical architecture where coverage is provided by both wide-area base stations (BS) and dense deployments of short-range access nodes (ANs) (e.g., small cells). The dense scale and mobility of users provide new challenges for scheduling: 1) high flux in mobile-to-AN associations, where mobile nodes quickly change associations with ANs (time scale of seconds) due to their small footprint and 2) multi-point connectivity, where mobile nodes are simultaneously connected to several ANs at any time. We study such a densified scenario with multi-channel wireless links (e.g., multi-channel OFDM) between nodes (BS/AN/mobile). We first show that traditional algorithms that forward each packet at most once, either to a single AN or a mobile user, do not have good delay performance. We argue that the fast association dynamics between ANs and mobile users necessitate a multi-point relaying strategy, where multiple ANs have duplicate copies of the data, and coordinate to deliver data to the mobile user. Surprisingly, despite data replication and no coordination between ANs, we show that our algorithm (a distributed scheduler-DIST) can approximately stabilize the system in large-scale instantiations of this setting, and further, performs well from a queue-length/delay perspective (shown via large deviation bounds).

We consider a variant of the multiarmed bandit problem where jobs queue for service, and service rates of different servers may be unknown. We study algorithms that minimize queue-regret: the (expected) difference between the queue-lengths obtained by the algorithm, and those obtained by a genie-aided matching algorithm that knows exact service rates. A naive view of this problem would suggest that queue-regret should grow logarithmically: since queue-regret cannot be larger than classical regret, results for the standard MAB problem give algorithms that ensure queue-regret increases no more than logarithmically in time. Our paper shows surprisingly more complex behavior. In particular, the naive intuition is correct as long as the bandit algorithm's queues have relatively long regenerative cycles: in this case queue-regret is similar to cumulative regret, and scales (essentially) logarithmically. However, we show that this "early stage" of the queueing bandit eventually gives way to a "late stage", where the optimal queue-regret scaling is O(1/t). We demonstrate an algorithm that (order-wise) achieves this asymptotic queue-regret, and also exhibits close to optimal switching time from the early stage to the late stage.

Future wireless standards such as 5G envision dense wireless networks with large number of simultaneously connected devices. In this context, interference management becomes critical in achieving high spectral efficiency. Orthogonal signaling, which limits the number of users utilizing the resource simultaneously, gives a sum-rate that remains constant with increasing number of users. An alternative approach called interference alignment promises a throughput that scales linearly with the number of users. However, this approach requires very high SNR or long time duration for sufficient channel variation, and therefore may not be feasible in real wireless systems. We explore ways to manage interference in large networks with delay and power constraints. Specifically, we devise an interference phase alignment strategy that combines precoding and scheduling without using power control to exploit the diversity inherent in a system with large number of users. We show that this scheme achieves a sum-rate that scales almost logarithmically with the number of users. We also show upper bounds on the sum-rate within the restricted class of single-symbol phase alignment schemes. Specifically, we prove that no scheme in this class can achieve better than logarithmic scaling of the sum-rate.

Personalized recommender systems provide great opportunities for targeted advertisements, by displaying ads alongside genuine recommendations. We consider a biased recommendation system where such ads are displayed without any tags (disguised as genuine recommendations), rendering them indistinguishable to users. We consider the problem of detecting such a bias and propose an algorithm that uses statistical analysis based on binary feedback data from a subset of users. We prove that the proposed algorithm detects bias with high probability for a broad class of recommendation systems with sufficient number of feedback samples.

We study device-to-device (D2D) enabled hierarchical cellular networks consisting of a macro base station (BS), a dense network of access nodes (ANs) and mobile users, where spectrum is shared between cellular traffic and D2D traffic. Further, (the receivers of) mobile users dynamically time-share between the cellular and D2D networks. We develop algorithms for channel allocation and mobile-user receiver mode selection (choosing which network to participate in) with the objectives of minimizing delay for cellular traffic, and capacity maximization for D2D traffic. Our proposed solution takes advantage of the unique features offered by large and densified cellular networks such as multi-point connectivity, channel diversity, spatial reuse and load distribution. Given a BS-to-mobile delay requirement of d + 1 time-slots, we show that by appropriately scheduling channels and receiver modes, we can (with exponentially high probability) guarantee that cellular traffic reaches its intended destination within d timeslots. By leveraging spatial channel reuse, we show that this is achieved by utilizing a vanishingly small fraction of the available spatial capacity. Further, in the presence of delay-constrained cellular traffic, our scheduling algorithm guarantees D2D traffic can achieve rates within a (1-1/d) factor of the corresponding achievable rates without cellular traffic.

We investigate the sensitivity of epidemic behavior to a bounded susceptibility constraint -- susceptible nodes are infected by their neighbors via the regular SI/SIS dynamics, but subject to a cap on the infection rate. Such a constraint is motivated by modern social networks, wherein messages are broadcast to all neighbors, but attention spans are limited. Bounded susceptibility also arises in distributed computing applications with download bandwidth constraints, and in human epidemics under quarantine policies.

There have been several studies on the performance of TCP controlled transfers over an infrastructure IEEE 802.11 WLAN, assuming perfect channel conditions. In this paper, we develop an analytical model for the throughput of TCP controlled file transfers over the IEEE 802.11 DCF with different packet error probabilities for the stations, accounting for the effect of packet drops on the TCP window. Our analysis proceeds by combining two models: one is an extension of the usual TCP-over-DCF model for an infrastructure WLAN, where the throughput of a station depends on the probability that the head-of-the-line packet at the Access Point belongs to that station; the second is a model for the TCP window process for connections with different drop probabilities. Iterative calculations between these models yields the head-of-the-line probabilities, and then, performance measures such as the throughputs and packet failure probabilities can be derived. We find that, due to MAC layer retransmissions, packet losses are rare even with high channel error probabilities and the stations obtain fair throughputs even when some of them have packet error probabilities as high as 0.1 or 0.2. For some restricted settings we are also able to model tail-drop loss at the AP. Although involving many approximations, the model captures the system behavior quite accurately, as compared with simulations.