In this paper, we consider a novel variant of the multi-armed bandit (MAB) problem, MAB with cost subsidy, which models many real-life applications where the learning agent has to pay to select an arm and is concerned about optimizing cumulative costs and rewards. We present two applications, intelligent SMS routing problem and ad audience optimization problem faced by several businesses (especially online platforms), and show how our problem uniquely captures key features of these applications. We show that naive generalizations of existing MAB algorithms like Upper Confidence Bound and Thompson Sampling do not perform well for this problem. We then establish a fundamental lower bound on the performance of any online learning algorithm for this problem, highlighting the hardness of our problem in comparison to the classical MAB problem. We also present a simple variant of explore-then-commit and establish near-optimal regret bounds for this algorithm. Lastly, we perform extensive numerical simulations to understand the behavior of a suite of algorithms for various instances and recommend a practical guide to employ different algorithms.

This paper provides the first sample complexity lower bounds for the estimation of simple diffusion models which seek to explain the diffusion of an epidemic in a network. The Susceptible-Infected-Recovered (SIR) model is a classic example, proposed nearly a century ago [2]. The SIR model remains a cornerstone for the forecasting of epidemics. The so-called Bass model [1] remains a basic building block in forecasting consumer adoption of new products and services. The durability of these models arises from the fact that they have shown an excellent fit to data, in numerous studies spanning both the epidemiology and marketing literatures. Somewhat paradoxically, using these same models as reliable forecasting tools presents a challenge.

Personalization and recommendations are now accepted as core competencies in just about every online setting, ranging from media platforms to e-commerce to social networks. While the challenge of estimating user preferences has garnered significant attention, the operational problem of using such preferences to construct personalized offer sets to users is largely still open, particularly in modern settings where a massive number of items and a millisecond response time requirement mean that even enumerating all of the items is impossible. Faced with such settings, existing techniques are either (a) entirely heuristic with no principled justification, or (b) theoretically sound, but simply too slow to work.

The use of small cells has been proposed to increase system capacity by installation of base stations close to user location. Proximity of the base station with the user equipment also implies lesser power requirement for transmitting the same information. Thus one may expect improvement in energy efficiency. But installing a large number of base stations can also lead to an increase in the total energy consumption of the system. To combat this, mechanisms have been proposed to switch OFF these base stations at times of low load. In this paper, we consider the problem of finding the fraction of base stations that can be switched OFF while maintaining quality of service (measured in terms of the average waiting time of users), for given load conditions. We also obtain the optimal switch OFF pattern. We do this in two steps. First, we determine the optimal ON-OFF pattern of base stations and user-base station association policy for a fixed fraction of base stations to be switched OFF. Then, we find the maximum fraction of base stations that can be switched OFF for given load conditions.

The Indian electricity sector, despite having the world's fifth largest installed capacity, suffers from a 12.9% peaking shortage. This shortage could be alleviated, if a large number of deferrable loads, particularly the high powered ones, could be moved from on-peak to off-peak times. However, conventional Demand Side Management (DSM) strategies may not be suitable for India as the local conditions usually favor inexpensive solutions with minimal dependence on the pre-existing infrastructure. In this work, we present a completely autonomous DSM controller called the nPlug. nPlug is positioned between the wall socket and deferrable load(s) such as water heaters, washing machines, and electric vehicles. nPlugs combine local sensing and analytics to infer peak periods as well as supply-demand imbalance conditions. They schedule attached appliances in a decentralized manner to alleviate peaks whenever possible without violating the requirements of consumers. nPlugs do not require any manual intervention by the end consumer nor any communication infrastructure nor any enhancements to the appliances or the power grids. Some of nPlug's capabilities are demonstrated using experiments on a combination of synthetic and real data collected from plug-level energy monitors. Our results indicate that nPlug can be an effective and inexpensive technology to address the peaking shortage. This technology could potentially be integrated into millions of future deferrable loads: appliances, electric vehicle (EV) chargers, heat pumps, water heaters, etc.