## 4 SkyDRL for Multi-Cloud Service Composition Problem
### SkyDRL  
Figure 6 depicts the overall architecture of our proposed SkyDRL method, which leverages the branch and bound skyline algorithm and deep reinforcement learning techniques. The DRL algorithm is based on the deep Q-network (DQN) algorithm and integrates three enhancements: double DQN (DDQN), Dueling Network, and Prioritized Experience Replay. In the neural network architecture, we modify the original DQN network to a Dueling Network, which divides the single-path output of \(Q(s,a)\) in the original DQN into two separate outputs. The first output is the state's value \(V(s)\), which represents the state's intrinsic value, while the second output is the advantage \(A(s,a)\) of each action in the state relative to others. These outputs are then combined to obtain the total Q value, i.e.,  
\[Q(s,a)=V(s)+A(s,a) \tag{16}\]  
Figure 6: Skyline-enhanced deep reinforcement learning approach. By separating the state value and action advantage, the network structure enhances training speed and stability, making it more effective than the traditional DQN network. When calculating the loss function, due to the overestimation problem of DQN, the estimation error increases as the number of actions increases, which leads to local optima. Therefore, we change the calculation method of the Q-target value to that of DDQN to address this issue. \[TargetQ=r+\gamma Q\big{(}s^{\prime},argmaxQ\big{(}s^{\prime},a;\theta\big{)}; \theta^{\prime}\big{)} \tag{17}\]  
Differing from the calculation method of the Q-target value in Equation (11), Equation (17) first calculates all Q values by inputting the following state \(s^{\prime}\) to the Q-network, selects the action with the highest Q value, and then inputs this action and the next state \(s^{\prime}\) to the Q-target network to calculate the Q value. This is an easy-to-understand approach but has a significant effect on solving the overestimation problem. Regarding the experience replay method, we adopt the Prioritized Experience Replay instead of randomly and uniformly selecting data from the replay buffer, as in traditional DQN methods. This is because the traditional approach overlooks the varying importance levels of samples for the agents. If we select samples based on their importance, the training speed can be greatly enhanced. The Prioritized Experience Replay selects samples with priority based on their importance, leading to more efficient learning. Typically, to evaluate the value of the experience, TD-Error is used, as our goal is to minimize it. If TD-Error is large, it indicates that the current Q function is far from the target Q function and more updates are required. Therefore, we utilize TD-Error to measure the value of experience. The calculation formula for TD-Error is  
\[\delta=r+\gamma Q\big{(}s^{\prime},\text{argmax}Q\big{(}s^{\prime},a;\theta \big{)};\theta^{\prime}\big{)}-Q(s,a) \tag{18}\]  
As indicated by Equation (18), the actual calculation method of TD-Error is the same as that of the loss function. In order to prevent overfitting of the network, we use a probability-based approach to sample experiences and set the priority value of each experience to  
\[P(i)=\frac{p_{i}^{\,\alpha}}{\sum_{k}p_{k}^{\,\alpha}} \tag{19}\]  
where \(p_{i}\) is the priority of the \(i\)-th sample; \(\alpha\) is used to adjust the priority level, and the calculation method of \(p_{i}\) is as follows:  
\[p_{i}=|\delta+\epsilon| \tag{20}\]  
\(\epsilon\) is a very small value to ensure that the probability of extracting experiences with TD-Error equaling zero is not zero. To facilitate the storage and sampling of Prioritized Experience, a SumTree structure is used to store the priority of samples. SumTree is a binary tree structure. The priority we need to store is in the leaf nodes of the tree. The parent node of the leaf node stores the sum of the priority of its child nodes. After updating the parameters of the neural network, the priority of the samples needs to be recalculated.