Decentralized Task Offloading in Edge Computing: A Multi-User Multi-Armed Bandit Approach

Mobile edge computing facilitates users to offload computation tasks to edge servers for meeting their stringent delay requirements. Previous works mainly explore task offloading when system-side information is given (e.g., server processing speed, cellular data rate), or centralized offloading under system uncertainty. But both generally fall short of handling task placement involving many coexisting users in a dynamic and uncertain environment. In this paper, we develop a multi-user offloading framework considering unknown yet stochastic system-side information to enable a decentralized user-initiated service placement. Specifically, we formulate the dynamic task placement as an online multi-user multi-armed bandit process, and propose a decentralized epoch based offloading (DEBO) to optimize user rewards which are subject to the network delay. We show that DEBO can deduce the optimal user-server assignment, thereby achieving a close-to-optimal service performance and tight O(log T ) offloading regret. Moreover, we generalize DEBO to various common scenarios such as unknown reward gap, dynamic entering or leaving of clients, and fair reward distribution, while further exploring when users’ offloaded tasks require heterogeneous computing resources. Particularly, we accomplish a sub-linear regret for each of these instances. Real measurements based evaluations corroborate the superiority of our offloading schemes over state-of-the-art approaches in optimizing delay-sensitive rewards.

I. Introduction

The recent proliferation of smart devices has brought enormous popularity of many intelligent mobile applications (e.g., real-time face recognition, interactive gaming) which typically demand low latency and intensive computation [1]. Driven by emerging 5G and IoT, 90% of the data will be generated and stored at the network edge [2], making it difficult for resource-constrained mobile devices to handle such huge amount of data. To address this challenge, mobile edge computing (MEC) has emerged as a new computing paradigm to push cloud frontier near to the network edge for supporting computation-intensive yet delay-sensitive applications [3].