# Task Scheduling Mechanism Based on Reinforcement Learning in Cloud Computing
## 4 QMTSF Algorithm
### Uqrl Algorithm
#### 4.2.3 Reward  
In Q-learning, after taking an action the agent immediately becomes aware of the new state and can receive or observe signals from the environment. These signals, either reward or punishment values, can help the scheduler to learn the optimal policy over time, gradually improving its performance in future task scheduling. Next, we present the design of the reward function used for the proposed scheduling program. The total time that a task exists in the system includes its queue waiting time and the task processing time on \(VM_{k}\)  
\[Time\_T_{VM_{k}}^{j}=w_{1}*Time\_W_{VM_{k}}^{j}+w_{2}*Time\_E_{VM_{k}}^{j}\]  
where \(Time\_W_{VM_{k}}^{j}=e^{k}+\sum\limits_{l\in VM_{Q_{k}}}len_{l}/P_{k}\) is the waiting time of task \(j\) in \(VM_{k}\), \(e^{k}\) is the remaining processing time of the task currently being executed in \(VM_{k}\), \(len_{l}\) is the data length of the task in \(VMQ_{k}\), and \(P_{k}\) is the processing speed of \(VM_{k}\). Moreover, \(Time\_E_{VM_{k}}^{j}\) is the time required to execute a task after it is assigned to \(VM_{k}\), while \(w_{1}\) and \(w_{2}\) are the weights of two different times. We define the reward value r as follows:  
\[\text{r}=\left\{ \begin{array}{ll}1&(Time\_T_{VM_{k}}^{j}\leq Time\_D_{VM_{k }}^{j})\ \ \&\ (Time\_T_{VM_{k}}^{j}=\min_{l\in VM_{Q_{k}}}(Time\_T_{VM_{k}}^{j}))\\ 0&(Time\_T_{VM_{k}}^{j}\leq Time\_D_{VM_{k}}^{j})\\ -1&(Time\_T_{VM_{k}}^{j}>Time\_D_{VM_{k}}^{j})\end{array} \right.\]  
When taking an action a to assign task \(j\) to \(VM_{x}\), if \(VM_{x}\) can meet the deadline of task \(j\) and the sum of the waiting time and execution time of task \(j\) on \(VM_{x}\) is the lowest among all \(m\) VMs, then a positive reward value is given. If task \(j\) only meets the task deadline, no reward value is given. If the task deadline cannot be met, a penalty is given. We designed a suitable reward function to train the scheduler with the goal of improving task processing speed and minimizing the makespans and processing times of all tasks. To schedule tasks reasonably in the server, we propose a task scheduling algorithm called UQRL. We built an RL model based on UCB Q-Learning [42], with the workflow presented below in Algorithm 2. ```
1 Initialize Parameters:\(\varepsilon,\delta,\gamma\) \(Q_{(s,\mu)},\widehat{Q}_{(s,\mu)}\gets 0,N_{(s,\mu)}\gets 0,\forall s\in S,a\in A\) \(\varepsilon_{1}\leftarrow\frac{\varepsilon}{24 RM_{1}\frac{1}{1-\gamma}},H \leftarrow\frac{lnI/((1-\gamma)\varepsilon_{1})}{lnI/\gamma}\) \(\iota(k)=ln(SA(k+1)(k+2))/\delta,a_{k}=\frac{H+1}{H+k}\) for\(t=0,1,2,...\)do  Given the current state \(s_{t}\)  Take action \(a_{t}\leftarrow\arg\max_{a^{\prime}}\widehat{Q}_{(s_{t},a^{\prime})}\)  Receive reward \(r_{t}\) and transit to \(s_{t+1}\) \(N_{(s_{t},\mu_{t})}\gets N_{(s_{t},\mu_{t})}+1\) \(k\gets N_{(s_{t},\mu_{t})},b_{k}\gets\frac{c}{1-\gamma}\sqrt{\frac{H (k)}{k}}\) \(\widehat{V}_{(s_{t+1})}\leftarrow\max_{a\in A}\widehat{Q}_{(s_{t+1},a)}\) \(Q_{(s_{t},\mu_{t})}\leftarrow(1-\alpha_{k})Q_{(s_{t},\mu_{t})}+\alpha_{k}[r_{ (s_{t},\mu_{t})}+b_{k}+\gamma\widehat{V}_{(s_{t+1})}]\) \(\widehat{Q}_{(s_{t},\mu_{t})}\leftarrow\min(\widehat{Q}_{(s_{t},\mu_{t})},Q_{(s _{t},\mu_{t})})\)
```  
**Algorithm 2** UQRL Task scheduling algorithm  
In the algorithm, \(\varepsilon\) is a relaxation factor that allows the algorithm to deviate from the local optimal solution to an extent in order to obtain a better global solution, \(\delta\) represents the magnitude of change or updating of the value function during each iteration, \(\gamma\) is the discount factor for rewards, and \(H\) is the number of steps per episode. The goals of the UQRL algorithm are to select an action that has achieved higher rewards than other actions in past explorations and to select an action that has been explored less than other actions. In line 7 of the algorithm, the action with the maximum reward is selected and \(\widehat{Q}_{(s,a)}\) is the historical minimum value of the \(Q\) function.