## 4 Problem Definition and Optimization Approaches
### Deep Q-Learning Approach
#### 4.2.3 Deep Q-Learning Algorithm
This means we assume that the task is inserted into both local and transmission queues and we want to remove the task from one of the queues by taking an action. This way of looking at this problem is necessary for the Q-learning algorithm to work properly, as we expect \(\max_{a\in A}Q(s_{t+1},a)\) to have a smaller value compared to \(Q(s_{t},a_{t})\). In other words, when a task arrives, the workload of the task should be reflected in the state of the mobile device, which is satisfied by adding it to both the local and transmission queues. A random value \(x\) is then drawn using uniform distribution \(U(0,1)\). If \(x\) is smaller than \(\epsilon\), we randomly choose an action. Hence, \(\epsilon\) is used to control the rate of exploration/exploitation of our model. If \(x\) is not smaller than \(\epsilon\), then the \(Q\)-value for both local execution \((a=0)\) and transmission \((a=1)\) are calculated using the current parameters \(\theta\) for our ANN, and the value of \(a\) for which the \(Q\)-value is higher is returned. Based on the chosen value for \(a\), task \(t\) is inserted into the local or transmission queues. After the insertion, the state of the mobile device is recorded into \(s^{\prime}\), this time without any modification. Finally, the transition \((t,s,a,s^{\prime})\) is recorded into the partial transition buffer. This transition from \(s\) to \(s^{\prime}\) is considered partial because we still do not know the reward that will be obtained for the action \(a\). This reward will arrive when the task is executed and the task result arrives at the mobile device. As depicted by Algorithm 5, the procedure for when a task is received by an edge device is almost identical to that of a mobile device. The only difference is that when a task is received, first, we examine to determine if the task was received from an edge device, that is, if the task was further offloaded by an edge device. If this is the case, we simply insert the task into the execution queue and no record for this transition is put into the partial transition buffer. Otherwise, an identical procedure to that of the mobile device is employed. As a result, each edge device trains two Q-learning models: one for the connected mobile devices and one for making decisions itself. With regard to connected mobile devices, it receives transitions from all connected mobile devices and uses those transitions to train a Q-learning model. Each edge device also transmits all the transitions that it has received from mobile devices to connected edge devices, so that those edge devices can also use those experiences. Hence, each edge device uses the experiences of the connected mobile devices and the connected edge devices. This process is elaborated in Algorithm 7. With regard to the Q-learning model for edge-level decision-making, experiences from both the edge device and all the connected edge devices are used to train the Q-learning model. To achieve this, whenever a transition is arrived at the transition arrival queue, it is added to the transition buffer of the edge device for the purpose of training the model. The procedure is explained in Algorithm 8. ```
1:\(i\gets 0\)
2:repeat
3: wait until a completed transition arrives
4:\((t,s,a,s^{\prime},r)\)\(\leftarrow\) receive transition
5:if transition was arrived from a mobile device then
6: transmit \((t,s,a,s^{\prime},r)\) to connected edge devices
7:endif
8: store \((t,s,a,s^{\prime},r)\) in transition buffer \(T_{mb}\)
9:if\(size(T_{mb})>N\)then
10: remove oldest item from transition buffer \(T_{mb}\)
11:endif
12:\(i\gets i+1\)
13:if\(i\geq n\)then
14:\(S\leftarrow\) sample \(m\) items from transition buffer \(T_{mb}\)
15:\(train(Q_{\theta}^{m},S)\)
16:\(i\gets 0\)
17:endif
18:until all task results have arrived
```  
**Algorithm 7** Q-training algorithm in edge devices for connected mobile devices  
For both models, after every \(n\) new insertions into the transition buffer \(T_{b}\), a sample \(S\) of size \(m\) is drawn uniformly at random from the transition buffer \(T_{b}\).