Optimal Task Offloading for Edge Computing with Stochastic Task Arrivals

Edge computing enables great computation ability in close proximity to the mobile devices (MDs). The task execution delay and energy consumption of the MDs will be greatly reduced by designing efficient task offloading policies. However, designing efficient task offloading policies is hard due to stochastic task arrivals. We formulate the task offloading problem as a Constrained Markov Decision Process (CMDP). We first propose a deterministic task offloading policy combining the value iteration algorithm and the sub-gradient algorithm. We then prove the existence of optimal randomized task offloading policies. Based on this, we further propose an optimal randomized task offloading policy with a closed-form policy selection probability. Simulation results demonstrate the efficiency of our algorithm in achieving low delay.