# MADDPG-Based Offloading Strategy for Timing-Dependent Tasks in Edge Computing
## 4 User-Prediction-Based Timing-Dependent Task Offloading Algorithm
### Timing-Dependent Task Offloading Algorithm  
MADDPG is applicable to a variety of complex environments and systems that require multiple agents to collaborate or compete to accomplish a task. The Markov decision of \(N\) agents is defined by a set of states \(S=[o_{1},\,o_{2},\,\ldots,\,o_{n}]\) that describe the independently observed states of all the agents themselves, and the agents choose an action from action \(A=[a_{1},a_{2},\,\ldots,\,a_{n}]\) as feedback to the current state. Agents interact with the environment, and every agent that makes a corresponding action causes a corresponding change in the state environment. Therefore, the environment is non-stationary from the point of view of any agent. The core idea of the MADDPG algorithm lies in learning a centralized Q-function that is conditional on global information for each agent, aiming to alleviate the non-stationary problem and promote the stability of the training process [40]. In addition, to reduce the variance of the policy gradient, centralized training is adopted in an actor-critic learning framework [41]. The system architecture of centralized training is shown in Figure 3. During the training process, the central controller randomly extracts a batch of records (\(o_{t}\), \(a_{t}\), \(r_{t}\), \(o_{t+1}\)) from the experience playback cache to train the agent's policy network parameters. The value network is used to evaluate the value of the agent taking a specific action \(a\) in a specific state \(s_{t}\). The expected gain gradient for agent \(i\) is [42]:  
\[\
abla_{\theta_{i}}\int(\mu_{i})=E_{x\sim D}[\
abla_{\theta_{i}}\mu_{i}(a_{i}| o_{i})\
abla_{a_{i}}Q_{i}^{ht}(x,a_{1},\ldots,a_{n})|_{a_{i}=\mu_{i}(s_{i})}]\,, \tag{15}\]  
The loss function for training Q is defined as [39]:  
\[L(w_{i})=E_{x,a,\rho,x}[(Q_{i}^{ht}(x,a_{1},\ldots,a_{n})-y)^{2}]\,, \tag{16}\]  
\[y=r_{i}+\gamma Q_{i}^{tr^{\prime}}(x^{\prime},a_{1}^{\prime},\ldots,a_{n}^{ \prime})|_{a_{j}^{\prime}=r_{j}^{\prime}(o_{j})}\,, \tag{17}\]  
After the training is completed, the policy network parameters are deployed to the corresponding agents who can make decisions locally and independently based on the local observation \(o\) and no longer need the participation of the value network. The training flow based on the MADDPG task-offloading algorithm is shown in Figure 3.  
Figure 3: The training process based on the MADDPG task-offloading algorithm. In order to solve the computing resource conflicts in multi-task concurrent scenarios, this paper improves the training process of the MADDPG algorithm to obtain better and faster offloading strategies. It is assumed that at the moment \(t\), GRU-based deep reinforcement learning obtains the state of the server in the MEC network from the existing multi-user concurrent scenario and makes the corresponding offloading action \(a_{t}\) based on the observation value. The offloading action directly affects the current service user state and updates the existing task state, and the user decides whether to offload the task or not based on the action value. When the task enters the offloading state, it will go through different stages of state changes such as data transmission, edge node storage queuing, node processing, and execution completion. During the task execution, the computing resources of the MEC server continuously and dynamically change. After the execution of this round of action, the agent obtains the corresponding feedback \(r_{t}\) from the environment and the state \(S_{t+1}\) of the environment at the next moment. The agent stores the data (\(s_{t}\),\(a_{t}\),\(r_{t}\),\(s_{t+1}\)) recorded in this round of training in the return experience pool and utilizes the data to train its own network data. As can be seen in Figure 4, this paper improves the training process of reinforcement learning, in which the agent cannot obtain the immediate reward \(r_{t}\) from the environment feedback but only the reward \(r_{t-1}\) obtained from the training in the previous moment.