Contextual combinatorial bandits in wireless distributed computing

摘要

With Wireless Distributed Computing (WDC), multiple resource-constrained mobile devices connected wirelessly can collaborate to enable a variety of applications involving complex tasks that one device cannot support individually. It is important to consider the application task graph, the features of the instantaneous data-frame, availability of the computing resources and the link connectivity to these devices, and determine the task assignments to balance the trade-off between energy costs of the devices and overall task execution latency. Considering the time-varying nature of the resource availability and the link conditions, we model the online task assignment problem as a contextual combinatorial bandit. Since each incoming data-frame may have different features and affect the optimal task assignment, the data-frame features act as context at each time-slot. We propose a novel online learning algorithm called PMF Learning algorithm that learns the distributions of the internal random variables of the system over time and uses the empirical distributions to make task allocations at each step. We prove that the regret of PMF Learning algorithm scales logarithmically over time and linearly in the number of connected devices, which is a substantial improvement over the standard combinatorial bandit algorithms.