Online learning for network resource allocation

The problem of efficiently allocating limited resources to competing demands manifests as the key problem in various real-world systems, such as road-traffic network, cellular network, content delivery network and so on. These problems have been studied for decades under the umbrella of network resource allocation, often positively impacting the design and operation of today’s network. However, with progress of technology, demand is increasing, the networks are becoming more complex and large, and new applications are emerging, creating a need for update to the existing solutions. In this thesis, we consider such problems in network resource allocation where new techniques are required for providing optimal solutions. Our central theme is to augment online learning techniques within existing solutions to facilitate improved and targeted operations. We study problems in, 1) road-traffic network, 2) content delivery network, 3) wireless networks, and 4) network of classifiers. In our first problem, we study the minimum toll-booth problem: placing minimum number of tollbooths to induce the original social optimal flow as the Nash equilibrium flow in the tolled network. We provide computational hardness results for the general congestion networks and provide polynomial time algorithm for series-parallel congestion networks. In our second problem, we design two adaptive time-to-live (TTL) caches which tunes its parameters automatically to achieve targeted performance. Specifically, we design dynamic TTL cache to provably achieve a feasible desired hit rate, while filtering TTL achieve the same desired hit rate with much less cache size utilization. All our theoretical results hold in the presence of non-stationary traffic. We empirically show the effectiveness of the proposed algorithms through simulations on 9 day web traffic trace from Akamai. In the third problem, we study cost optimization in a wireless network under stability constraints, where both base station (BS) switching and activation incur cost. Additionally, in our system BS activation requires learning the channel statistics as channels are observable only from active BSs. We design two algorithms which are explore-exploit in nature to solve this problem optimally. The key idea is to constraint BS switching and apply max- weight activation on switching instances. We design both static and queue-length dependent switching schemes, and show that the latter outperforms the former. In the fourth problem, we study an online unsupervised ensemble learning problem. In this problem, samples come to the system for classification in an online manner. The decision maker, across multiple rounds, routes the samples through a subset of classifiers from a fixed ensemble and collects labels from them. Finally, it aggregates the collected labels to provide a final label for the samples and complete its service with a guaranteed accuracy. We characterize the capacity region (in terms of accuracy level vs arrival rate) of this system, and provide a unsupervised learning aided algorithm which is throughput optimal in this setting. We validate our theory through experiments with two ensembles of deep neural networks used for image classification in grouped CIFAR-10 dataset. In our fifth problem, we study the expected reward maximization problem in the multi-armed bandit problem when each time an arm is played it gets blocked for a certain duration. In this problem, which we call Blocking Bandits, we show that the expected reward maximization problem with the knowledge of the mean rewards for each arm is computationally hard. The oracle greedy strategy that plays the available arm with the highest mean reward in each time slot provides an (1 − 1/e) fraction of the optimal reward. Furthermore, when the mean rewards are not known, playing the available arm with the highest upper confidence bound (ucb) index incurs a O(log(T)) regret w.r.t. the oracle greedy policy. We show that there are instances of the blocking bandits problem where Ω(log(T)) regret is unavoidable. Finally, we present both synthetic and real-data experiments to validate our theoretical claims.Electrical and Computer Engineerin