PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimized Computation Offloading Performance in Virtual Edge Computing Systems via Deep Reinforcement Learning

Xianfu Chen, Honggang Zhang, Celimuge Wu, Shiwen Mao, Yusheng Ji, Mehdi Bennis

arXiv:1805.06146v1cs.LGcs.AIstat.ML

TL;DR

The paper studies how to optimize stochastic computation offloading in a virtual MEC system with changing network conditions and many possible base stations. It models the problem as an MDP and develops double-DQN-based online learning algorithms, including a Q-function-decomposition variant. Numerical experiments report better long-term performance than three baselines, with Deep-SARL performing best.

  • Problem

    Stochastic offloading in an ultra-dense sliced RAN must adapt to time-varying communication qualities, task and energy states, and multiple base-station choices, creating a high-dimensional decision problem.

  • Method

    The paper formulates offloading as an MDP and proposes double-DQN-based online algorithms, including Deep-SARL, which combines double DQN with Q-function decomposition.

  • Results

    Both proposed algorithms outperform three baseline schemes in numerical experiments, and Deep-SARL achieves the best computation offloading performance.

  • Takeaways & Limitations

    The proposed learning algorithms provide online computation-offloading policies that survive high-dimensional state spaces without a priori network-dynamics statistics.

Abstract

from arXiv · show

To improve the quality of computation experience for mobile devices, mobile-edge computing (MEC) is a promising paradigm by providing computing capabilities in close proximity within a sliced radio access network (RAN), which supports both traditional communication and MEC services. Nevertheless, the design of computation offloading policies for a virtual MEC system remains challenging. Specifically, whether to execute a computation task at the mobile device or to offload it for MEC server execution should adapt to the time-varying network dynamics. In this paper, we consider MEC for a representative mobile user in an ultra-dense sliced RAN, where multiple base stations (BSs) are available to be selected for computation offloading. The problem of solving an optimal computation offloading policy is modelled as a Markov decision process, where our objective is to maximize the long-term utility performance whereby an offloading decision is made based on the task queue state, the energy queue state as well as the channel qualities between MU and BSs. To break the curse of high dimensionality in state space, we first propose a double deep Q-network (DQN) based strategic computation offloading algorithm to learn the optimal policy without knowing a priori knowledge of network dynamics. Then motivated by the additive structure of the utility function, a Q-function decomposition technique is combined with the double DQN, which leads to novel learning algorithm for the solving of stochastic computation offloading. Numerical experiments show that our proposed learning algorithms achieve a significant improvement in computation offloading performance compared with the baseline policies.

I. INTRODUCTION

The paper addresses stochastic computation offloading in a virtual MEC system, where decisions must adapt to changing channels, task arrivals, and energy status. It formulates the problem as an MDP and proposes deep reinforcement-learning algorithms to handle high-dimensional state spaces without prior network dynamics.

  • Motivation: Mobile devices have limited battery capacity, local CPU computation power, and overall computation capabilities.These constraints create tension between resource-demanding applications and device-side execution.
  • Motivation: MEC places computing capabilities close to mobile users within RANs, enabling computation offloading to resource-rich servers.The paper links this proximity to improved computation QoS and QoE and augmented mobile-device capabilities.
  • Problem Setting: Computation offloading must share wireless radio resources between traditional communication and MEC services over a common RAN.The shared infrastructure creates technical challenges for virtualized network resource management.
  • Contributions: The paper formulates stochastic offloading as an MDP and develops DARLING and Deep-SARL using double DQN, Q-function decomposition, and deep reinforcement learning.The algorithms learn policies without a priori knowledge of network dynamics and address high-dimensional state spaces.
  • Research Gap: Previous offloading policies largely use one-shot optimization and fail to characterize long-term performance under time-varying channels, task arrivals, and energy status.Some prior approaches also depend on network statistics or provide only approximately optimal solutions.
  • Research Gap: Multiple base stations with different transmission qualities enlarge the state space, while wireless charging further complicates stochastic offloading-policy design.These conditions make conventional reinforcement-learning algorithms infeasible in the considered ultra-dense sliced RAN.
  • Results: Both proposed online learning algorithms outperform three baseline schemes, with Deep-SARL achieving the best computation offloading performance.The comparison is based on numerical experiments conducted using TensorFlow.

II. SYSTEM DESCRIPTIONS AND ASSUMPTIONS

The system models MEC in a virtualized, ultra-dense sliced RAN where mobile users share MEC resources and select among base stations for task offloading. Tasks may execute locally or remotely, subject to queue, energy, CPU, channel, and transmission constraints.

  • The considered ultra-dense virtualized RAN provides a set of base stations through which mobile users can access edge computing.
  • MEC and traditional communication services share a common physical network infrastructure with separate radio-resource slices.
  • Task arrivals are modeled as an independent and identically distributed Bernoulli sequence, with each task characterized by input size and required CPU cycles.
  • Queued tasks are processed either locally on the mobile device or remotely at the MEC server through a selected base station.
  • A representative mobile user makes joint offloading and energy-allocation decisions at the beginning of each decision epoch.
  • Local computation frequency is constrained by maximum CPU capacity, while transmission performance depends on channel states modeled by finite-state Markov chains.
  • Increasing allocated energy units decreases the transmission time required for offloaded task input data.

III. PROBLEM FORMULATION

The paper formulates stochastic computation offloading as an optimization problem within a Markov decision process framework. It then considers optimal solutions for this formulation.

  • The stochastic computation offloading problem is first formulated within the Markov decision process framework.
  • The formulation is followed by a discussion of the optimal solutions.

A. Stochastic Computation Task Offloading

The model evaluates computation experience using delay, task drops, queueing, execution failures, and MEC payment, while the user selects stationary joint control actions from observed network states. The objective is to maximize expected long-term discounted utility in an infinite-horizon single-agent MDP.

  • Experienced delay is a key performance indicator, measured from task arrival until successful removal from the computation queue.
  • A failed execution leaves the task in the queue, while a full queue causes task drops.
  • The immediate utility combines weighted satisfaction functions for execution delay, task drops, queueing delay, failure penalties, and MEC access payment.
  • At each epoch, the mobile user observes the network state and selects a joint task-offloading and energy-allocation action under a stationary policy.
  • The optimal stationary policy maximizes expected long-term utility for every initial network state.
  • The resulting optimization is a single-agent infinite-horizon MDP with a discounted utility criterion.

B. Learning Optimal Solution to Problem 1

The section formulates learning the optimal control policy through Q-learning, but highlights scalability limits in large state and action spaces. It motivates deep reinforcement learning as a practically feasible alternative without requiring prior network-transition statistics.

  • Traditional value-iteration and policy-iteration solutions require complete statistics for task arrivals, received energy, and channel-state transitions.Off-policy Q-learning avoids requiring a priori network-state transition statistics.
  • Q-learning learns action values from observed states, actions, utilities, and subsequent network states.The update uses recursive observations at consecutive decision epochs and balances exploration with exploitation through an ε-greedy strategy.
  • Q-learning converges to the optimal control policy under stationary transitions, suitable learning rates, and infinitely frequent visits to all state-action pairs.
  • Standard Q-learning scales poorly because its tabular representation becomes impractical in high-dimensional state or action spaces.The state space grows exponentially with the number of base stations.

IV. APPROACHING THE OPTIMAL POLICY

The paper develops practically feasible algorithms using deep reinforcement learning together with a linear Q-function decomposition technique to approach the optimal control policy.

  • The proposed approach combines recent deep reinforcement-learning methods with a linear Q-function decomposition technique.

A. Deep Reinforcement Learning Algorithm

The deep reinforcement-learning algorithm approximates the state-action Q-function with neural networks and uses double DQN learning to address the massive network state space.

  • A double DQN is adopted to address the massive network state space in stochastic computation offloading.
  • The DQN approximates Q(χ, (c, e)) with a parameterized function Q(χ, (c, e); θ).The parameters are learned iteratively rather than computing the optimal Q-function directly.
  • DARLING stores transition experiences in finite replay memory and trains the DQN using randomly sampled mini-batches.The stored experience includes the current state, joint action, achieved utility, and next state.
  • The training objective is a mean-squared Bellman-equation error based on the DQN prediction and its target value.

B. Linear Q-Function Decomposition based Deep Reinforcement Learning

The paper decomposes the utility into additive satisfaction categories and learns corresponding per-agent Q-functions with virtual agents. The resulting decomposition is stated to achieve the optimal solution while enabling simpler learning components.

  • Linear Q-Function Decomposition: The additive utility structure motivates linearly decomposing the joint state-action Q-function into per-agent Q-functions.Categories include execution delay, task drops, queuing delay, failed processing, and MEC-service payment.
  • Linear Q-Function Decomposition: Virtual agents learn per-category long-term satisfaction, while the mobile user selects actions by aggregating their Q-function values.
  • Linear Q-Function Decomposition: Theorem 1 states that linear Q-function decomposition achieves the optimal solution to the computation-offloading problem.
  • Linear Q-Function Decomposition: Each virtual agent can use a simpler DQN because it learns a respective expected long-term satisfaction using relevant network-state information.
  • Deep SARSA: SARL uses on-policy updates based on the actually performed next action rather than a hypothetical maximizing action.Theorem 2 states that SARL converges to the optimal per-agent state-action Q-functions when state-action pairs are visited infinitely often.

2) Deep SARSA Reinforcement Learning (Deep-SARL):

Deep-SARL combines double-DQN learning with linear Q-function decomposition to solve stochastic computation offloading online. Its agents learn locally and iteratively from replayed state transitions.

  • Q-function decomposition: Deep-SARL reexpresses the global state-action Q-function as a sum of per-agent DQNs.The decomposition exploits the additive structure of the utility function.
  • Algorithm design: The method derives a deep SARSA reinforcement-learning algorithm for stochastic computation offloading.It is presented as an alternative to the DARLING algorithm.
  • Online learning: Deep-SARL learns DQN parameters locally at the agents through online iterative updates.The algorithm is summarized as an online implementation for MEC computation offloading.
  • Online learning: At each decision epoch, experience transitions are stored, mini-batches are sampled, and DQN parameters are updated using gradients.The transition includes the network state, joint action, per-agent utilities, next state, and next action.

V. NUMERICAL EXPERIMENTS

The experiments evaluate DARLING and Deep-SARL in a six-base-station MEC system using replay-based DQNs and three computation-offloading baselines. The setup includes mobile execution, server execution, and greedy execution comparisons.

  • General Setup: The simulated system contains B = 6 BSs connecting the mobile user with the MEC server.Channel gain states between the mobile user and BSs are included in the system setting.
  • General Setup: Each energy unit corresponds to 2 · 10^-3 Joule, and energy arrivals follow a Poisson process with average rate λ(e).The rate is measured in energy units per epoch.
  • General Setup: DARLING uses a single hidden layer with 200 neurons and tanh activation, while Deep-SARL uses 200-neuron single-layer DQNs for its agents.Both algorithms are implemented in TensorFlow, with Adam used as the optimizer.
  • General Setup: The evaluation compares DARLING and Deep-SARL with mobile execution, server execution, and greedy execution baselines.Mobile execution stays at the device, server execution selects a minimum-delay BS under constraints, and greedy execution minimizes immediate delay.

B. Experiment Results

Experiments examine convergence and performance under changing task and energy arrival rates. Both proposed algorithms improve utility over baselines, while Deep-SARL generally achieves the strongest offloading performance.

  • Experiment 1 – Convergence performance: DARLING and Deep-SARL converge at similar, reasonable speeds in the convergence experiment.The plotted Q-values and loss function are evaluated against decision epochs.
  • Experiment 2 – Performance under various λ(t): Both proposed schemes achieve significant gains in average utility compared with the three baseline offloading schemes.The comparison covers average utility and additional delay, drops, queuing, payment, and failure-penalty measures.
  • Experiment 2 – Performance under various λ(t): As task arrival probability increases, average utility decreases alongside increases in delay, drops, queuing delay, payment, and failure penalty.The results are reported across the performance plots in Fig. 5.
  • Experiment 2 – Performance under various λ(t): Deep-SARL achieves higher utility than DARLING, while its average MEC service payment per epoch is slightly higher.The higher payment is associated with more tasks being scheduled for MEC-server execution under the tested settings.
  • Experiment 3 – Performance with changing λ(e): As energy arrival rates increase, overall computation offloading performance improves, while delay, payment, and failure penalty first increase and then decrease.With sufficiently many queued energy units, enough energy can be allocated to tasks, reducing these quantities.

VI. CONCLUSIONS

The paper formulates stochastic computation offloading for a mobile user in an ultra-dense sliced RAN as an MDP and proposes two double-DQN online algorithms. Numerical results report better long-term utility than three baselines, with Deep-SARL outperforming DARLING.

  • VI. CONCLUSIONS: The offloading policy accounts for time-varying channel qualities, energy arrivals, and computation-task arrivals in an ultra-dense sliced RAN.The stochastic offloading problem is formulated as a Markov decision process.
  • VI. CONCLUSIONS: DARLING and Deep-SARL are double-DQN-based online algorithms that require no a priori dynamics statistics and address high-dimensional state spaces.Both algorithms learn computation-offloading policies from the considered system dynamics.
  • VI. CONCLUSIONS: Compared with three baselines, the proposed algorithms achieve much better long-term utility performance.The reported utility reflects tradeoffs among execution delay, task drops, queuing delay, MEC payment, and failure penalty.
  • VI. CONCLUSIONS: Deep-SARL outperforms DARLING by exploiting the additive structure of the utility function.The conclusion identifies this structure as the basis of Deep-SARL’s advantage.
Loading 1805.06146v1…