# Dynamic Computation Offloading with Deep Reinforcement Learning in Edge Network
## 4 Algorithm
### DQN-Based Computation Offloading Algorithm  
#### 4.2.1 Reinforcement Learning Settings  
For each time slot \(T_{i}\) in the reinforcement learning algorithm, the agent receives the system state \(s_{i}\) and computes the reward \(r_{i-1}\) for the last time slot. Then, the agent selects the action \(a_{i}\) according to a predefined policy. After implementing this action, the system moves to the new state, \(s_{i+1}\), and into the next time slot. Similarly, the agent computes the reward \(r_{i}\) and selects the new action \(a_{i+1}\) according to \(s_{i+1}\).  
_State_: In our work, the system state is formulated by the edge servers' operation status \(F_{rt}\), edge servers' deployed service list \(F_{hostList}\), the nearest edge server \(F_{near}\) to the current task, and the service type \(H_{service}\) which the current task requires. Therefore, we use the state \(s_{i}\) during \(T_{i}\) as  
\[s_{i}=\{F_{rt},F_{hostList},F_{near},H_{service}\}\in\mathbb{S} \tag{15}\]  
The edge servers' operation status \(F_{rt}\) refers to the time cost \(t\) before the current task, which is processed on edge server \(F_{i}(i\in n)\). Since our strategy is based on computing resources, the time cost \(t\) is related to the decision node. If the decision node is not the nearest edge server \(F_{near}\), then the task needs to be offloaded to the decision node. The related service needs to migrate from a neighboring server if the decision node does not have the corresponding service. It is noteworthy that we use one-hot coding to formulate the \(F_{near}\) and \(H_{service}\). \(\mathbb{S}\) denotes the space of the system states.  
_Action_: The selected action during \(T_{i}\) is \(a_{i}=\{F_{decision}\}\in\mathbb{A}\), where \(F_{decision}\) is the task's execution node, as determined by our algorithm, and \(\mathbb{A}\) is the set of all possible edge servers. In DQN, DNN outputs Q-values of all actions in action space \(\mathbb{A}\) based on the input state \(s_{i}\), and the execution node is the output action. The action selection is based on the \(\epsilon\)-greedy algorithm, a threshold \(\epsilon\) is set in advance, and a random number \(\phi\) is generated each time. If \(\epsilon>\phi\), the output action is the best action corresponding to the optimal Q-value in all outputs. Otherwise, the action is randomly selected to remove local optimization.  
_Reward_: Since our algorithm focuses on minimizing the total cost \(\mathcal{C}\), if the system completes the task and there is a reduction in cost, the reward will be positive. If the cost of the task is greater than the cost of performing the task locally, the action will face a negative reward. Therefore, the reward during \(T_{i}\) can be expressed as:  
\[r_{i}=M-\frac{\mathcal{C}_{local}^{T_{i}}}{\mathcal{C}^{T_{i}}(s_{i},a_{i})} \tag{16}\]  
where \(M\) is a constant value; \(\mathcal{C}_{local}^{T_{i}}\) is the local execution cost at the time \(T_{i}\); \(\mathcal{C}^{T_{i}}(s_{i},a_{i})\) is the total cost, obtained by choosing the action \(a_{i}\) at the state \(s_{i}\).  
In the Q-learning algorithm [27], the large scale of \(\mathbb{S}\) and \(\mathbb{A}\) lead to the large scale of the Q-table. However, because the dimension of the state space \(\mathbb{S}\) is very large, the Q-table cannot efficiently store these states. To tackle this issue, we adopted the DQN algorithm [28] in our work. DQN combines q-learning and deep learning, and uses a Q-network composed of a DNN with weights \(\theta\) instead of Q-table, to effectively store Q-value information. The detailed algorithm steps of DQN are shown in Algorithm 1.  
```
0:\(\theta\)
0:\(a_{i}\)
1:for episode = 1, N do
2: Observe \(s_{0}\)
3:for i = 1, t do
4: /*Action Selection*/
5: Select \(a_{i}\) according pre-defined policy
6: Observe \(s_{i+1}\)
7: Calculate \(r_{i}\) by Equation (16)
8: /*Q-network Update*/
9: Output \(a_{i}\)
10:endfor
11:endfor
```  
**Algorithm 1** Deep Q-Learning