# Autonomous Penetration Testing Based on Improved Deep Q-Network
## 2 Background
### Markov Decision Process and Reinforcement Learning  
Markov decision process means to be a mathematical framework for describing multistage decision making (or sequential decision) problems [20], and reinforcement learning is a technique for solving MDPs problems. An MDP problem can be formally defined by the tuple: \(<\mathcal{S},\mathcal{A},\mathcal{R},\mathcal{T}>\), where \(\mathcal{S}\) is the state space representing all the possible state of the environment, \(\mathcal{A}\) is the action space representing all the possible actions of the agent, \(\mathcal{R}\) is reward function representing the immediate reward after performing an action, \(\mathcal{T}\) is the transition function \(\mathcal{T}(s,a,s^{\prime})=P(s^{\prime}|s,a)\) representing the probability of environmental state transition after taking an action. Different from supervised learning and unsupervised learning, reinforcement learning learns the mapping from state to action through continuous interaction with the uncertain environment [21]. More specifically, the agent observes the environment and receives the state \(s_{t}\in\mathcal{S}\) at time \(t\); then, the action \(a_{t}\in\mathcal{A}(s_{t})\) is selected based on the policy \(\pi\). As the result of conducting the selected action, the agent can obtain the reward \(r_{t}\in\mathcal{R}\) from the environment; meanwhile, the environment state transitions to \(s_{t+1}\). The process of the agent interacting with the environment from \(s_{t}\) to \(s_{t+1}\) is called a step, and the collection of steps from the initial step to the end is called an episode. The goal of the agent is to learn the optimal policy \(\pi^{*}\) that maximizes the cumulative rewards or average rewards per episode. The policy is the mapping from state to action, and the optimal policy \(\pi^{*}\) can be expressed as the formula:  
\[\pi^{*}=argmax_{\pi}\sum_{t=0}^{T}\gamma^{t}\mathbb{E}_{\pi}[r_{t}], \tag{1}\]  
where \(\gamma\in(0,1)\) is a parameter named discount factor measuring the importance of present rewards to future rewards. The smaller the value, the more shortsighted the agent will be, and on the contrary, it will pay more attention to future long-term rewards. There are many reinforcement learning algorithms available for solving MDP problems. Q-learning is a model-free and value-based algorithm that is widely used. Model-free means it attempts to learn the optimal policy by trial-and-error experience without the need of modeling the environment. Value-based means the policy is derived directly from the value function. For the Q-learning algorithm, the policy can be extracted by the Q-function \(Q(s_{t},a_{t})\) that represents the expected reward if the agent conducts the action \(a_{t}\) from the state \(s_{t}\). The Q-function will converge with the exploration and exploitation of the environment, and then the agent can use it to choose the greedy action for a state. The update equation of the Q-function is:  
\[Q^{NEW}(s_{t},a_{t})\gets Q(s_{t},a_{t})+\alpha(r_{t}+\gamma max_{a}(s_{t +1},a_{t})-Q(s_{t},a_{t})), \tag{2}\]  
where \(\alpha\in(0,1]\) is the learning rate and \(\gamma\) is the discount factor. The traditional tabular Q-learning algorithm uses a table to store the state-action pair values during the training process. This method is simple to implement, though it cannot be applied to solve the problem with large state space as the table size is limited. Deep reinforcement learning (DRL) is the combination of deep learning and reinforcement learning, which makes it possible to cope with the curse of dimensionality. [PERSON] et al. [22, 23] proposed the DQN algorithm that uses the deep neural network as the function approximator to generate the state-action value. In order to ensure the algorithm can converge, DQN uses the experience replay mechanism to improve the efficiency of the use of previous experience and remove the correlation between data by taking random samples from the memory.