# Scheduling for Mobile Edge Computing with Random User Arrivals: An Approximate MDP and Reinforcement Learning Approach

arXiv: https://arxiv.org/abs/2004.07553 · HTML: https://mlsanity.com/paper/2004.07553/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Apr 2020.

## Built on by (most cited first, 4 of 4)

- [Accelerating Federated Edge Learning via Topology Optimization](https://mlsanity.com/paper/2204.00489/) (2022)
- [Reinforcement Learning-Empowered Mobile Edge Computing for 6G Edge Intelligence](https://mlsanity.com/paper/2201.11410/) (2022)
- [Deep Index Policy for Multi-Resource Restless Matching Bandit and Its Application in Multi-Channel Scheduling](https://mlsanity.com/paper/2408.07205/) (2024)
- [Adaptive Approach to Enhance Machine Learning Scheduling Algorithms During Runtime Using Reinforcement Learning in Metascheduling Applications](https://mlsanity.com/paper/2509.20520/) (2025)

## Abstract (arXiv)

In this paper, we investigate the scheduling design of a mobile edge computing (MEC) system, where active mobile devices with computation tasks randomly appear in a cell. Every task can be computed at either the mobile device or the MEC server. We jointly optimize the task offloading decision, uplink transmission device selection and power allocation by formulating the problem as an infinite-horizon Markov decision process (MDP). Compared with most of the existing literature, this is the first attempt to address the transmission and computation optimization with the random device arrivals in an infinite time horizon to our best knowledge. Due to the uncertainty in the device number and location, the conventional approximate MDP approaches addressing the curse of dimensionality cannot be applied. An alternative and suitable low-complexity solution framework is proposed in this work. We first introduce a baseline scheduling policy, whose value function can be derived analytically with the statistics of random mobile device arrivals. Then, one-step policy iteration is adopted to obtain a sub-optimal scheduling policy whose performance can be bounded analytically. The complexity of deriving the sub-optimal policy is reduced dramatically compared with conventional solutions of MDP by eliminating the complicated value iteration. To address a more general scenario where the statistics of random mobile device arrivals are unknown, a novel and efficient algorithm integrating reinforcement learning and stochastic gradient descent (SGD) is proposed to improve the system performance in an online manner. Simulation results show that the gain of the sub-optimal policy over various benchmarks is significant.