## 4 SkyDRL for Multi-Cloud Service Composition Problem
### Preliminary
#### 4.1.2 Deep Reinforcement Learning  
Q-learning is a classic value-based algorithm used in reinforcement learning. Its primary objective is to estimate the value of an action via a Q-table. Whenever the estimated value differs from the actual value, the Q-table gets updated based on the difference between the two values. With repeated updates, the Q-table becomes capable of accurately estimating the true value. However, utilizing a Q-table to store Q-values presents difficulties when dealing with large-scale and continuous data. To overcome the limitations of a Q-table, a Q-function is utilized as a replacement.  
Considering the excellent ability of neural networks in modeling complex functions, a neural network can be used to fit this Q-function. The integration of neural networks and Q-learning is known as Deep Q Network (DQN), and it is a DRL-based algorithm. The core concept of DQN involves using deep neural networks and nonlinear transformations to gradually extract abstract features from input data [51]. The algorithm employs reinforcement learning to maximize cumulative rewards, ultimately facilitating optimal decision-making [50]. In DQN, the input is the state, and the output is the value estimation  
Figure 3: Reinforcement learning.  
for each action. DQN has two crucial enhancements. One is to use the experience replay mechanism to break the correlation between samples, and the other is to use two neural networks with the same structure, Q-network and Q-target. The Q-network estimates the predicted Q-value, while the Q-target calculates the target Q-value. During each step, the agent-environment interaction generates a sample that is stored in the replay buffer. During training, the Q-learning update formula is utilized, and a batch of samples is uniformly extracted from the replay buffer to update the parameters of the Q-network using stochastic gradient descent. The update formula is shown below:  
\[Q(s,a)\ \leftarrow\ Q(s,a)+\alpha\big{[}r+\gamma maxQ(s^{\prime},\ a^{ \prime})-Q(s,a)\big{]} \tag{11}\]  
In the update formula, \(Q(s,a)\) is the Q-value when taking action \(a\) under state \(s\). \(\alpha\) denotes the learning rate; \(r\) represents the reward value, and \(\gamma\) represents the discount factor. A higher \(\gamma\) value suggests that the model prioritizes long-term benefits, whereas a lower \(\gamma\) value places more emphasis on short-term gains. The variable \(s^{\prime}\) stands for the next state; \(maxQ(s^{\prime},\ a^{\prime})\) signifies the maximum Q-value under state \(s^{\prime}\), and \(TargetQ=r+\gamma maxQ(s^{\prime},\ a^{\prime})\) represents the target Q-value. We use \(\theta\) to denote the parameters of the Q-network and \(\theta^{\prime}\) to represent those of the Q-target. During training, the parameters \(\theta\) get updated every time, while \(\theta^{\prime}\) remains unchanged. To ensure consistency between \(\theta\) and \(\theta^{\prime}\), we assign the value of \(\theta\) to \(\theta^{\prime}\) only once every \(C\) steps. Specifically, when a loop of state-action-reward is completed, we call it the end of a time step. After every \(C\) time steps are completed, the parameters are updated.