# Deep Reinforcement Learning for Intelligent Penetration Testing Path Design
## 2 Related Work
### Improved Deep Q Network Algorithm  
DQN [30; 31; 32] is the first mature algorithm that combines deep learning and reinforcement learning, and is an extension of the Q-learning algorithm. The Q-learning algorithm initializes the Q-table with a limited number of states and actions and continuously updates them, but it is prone to the problem of state explosion.  
The DQN algorithm adopts the experience replay method and updated method with network delay to solve the problems of learning instability and excessive sample correlation in the Q-learning algorithm.  
The experience replay method stores the past training data. When the parameters are updated, a part of the data is exacted from the memory in order to solve the problem of the high correlation between data.  
The updated method with network delay creates the target Q network. During the update process, only the parameter of the current Q network is updated, and the \(\theta\) parameter of the target Q network remains unchanged. After a certain number of iterations, the updated current Q network is copied to the target Q network.  
The target value is relatively fixed for a period of time when the target Q network does not change. Therefore, the introduction of the target Q network increases the stability of the DQN algorithm learning. In each episode of DQN algorithm training, the network parameters will be updated through gradient descent backpropagation to minimize the loss function.  
The DQN algorithm uses the Q network approximation function to solve the continuous state space problem. However, it still has the problem of overestimating the Q value. To improve the calculation method of the target and deal with this problem, the DDQN is proposed. The DDQN algorithm is an improvement of the DQN algorithm. The structure of the DDQN algorithm is similar to the DQN algorithm, but the target function is improved, as shown in Equations (1) and (2).  
\[Y_{t}^{DQN}=R_{t+1}+\gamma\underset{a}{max}\,Q(S_{t+1},a;\theta_{t}^{-}) \tag{1}\]  
\[Y_{t}^{DDQN}=\ R_{t+1}+\gamma Q(S_{t+1},arg\underset{a}{max}\,Q(S_{t+1},a; \theta_{t}),\theta_{t}^{-}) \tag{2}\]  
where \(R_{t+1}\) denotes the reward for the next state, \(\gamma\) represents the discount factor, \(\theta_{t}^{-}\) denotes the neural network parameters in the target Q network, and \(\theta_{t}\) represents the parameters of the current Q network.  
The optimal action selection of the objective function in the DDQN algorithm is based on the Q network parameters that are currently being updated instead of selecting the maximum value from the target Q network. Therefore, this algorithm solves the overestimation problem of the DQN algorithm to a certain extent, making the Q value closer to the true value.  
In recent years, more and more improved DQN algorithms have been proposed. [PERSON] et al. [33] proposed the soft actor-critic (SAC) algorithm. It handles continuous action spaces and incorporates an entropy regularization term to encourage exploration. [PERSON] et al. [34] proposed the Rainbow algorithm, which combines several DQN extensions into a unified framework. It incorporates improvements such as double Q learning, prioritized experience replay, dueling architectures, distributional reinforcement learning, and noisy networks.