# Cascaded Reinforcement Learning Agents for Large Action Spaces in Autonomous Penetration Testing
## 3 Background  
The problem to be considered in this paper is a discrete-time reinforcement learning task modelled by a Markov decision process or MDP formalised by a tuple \(\langle\mathcal{S},\mathcal{U},\mathcal{P},\mathcal{R},\bigcirc\rangle\). Unlike previous investigations, we do not wish to formulate the penetration testing as a POMDP because we want to clearly demonstrate the effects of the proposed architecture without compounding factors. No previous studies have used any POMDP-specific solutions, and, further, our method can still be applied as a feature to a POMDP solution. At each time step \(t\), the agent receives a state observation \(s_{t}\in\mathcal{S}\) from the environment. In our penetration testing setting, this represents the observable part of the compromised network. To interact with the environment, the agent executes an action \(u_{t}\in\mathcal{U}\), after which it receives another state \(s_{t+1}\) according to the state transition probability function \(\mathcal{P}:\mathcal{S}\times\mathcal{U}\times\mathcal{S}\rightarrow\mathbb{R}\), which returns a probability distribution of the next state \(s_{t+1}\) given the current state \(s_{t}\) and action \(u_{t}\), and a reward signal \(r_{t}\) given by \(\mathcal{R}:\mathcal{S}\times\mathcal{U}\rightarrow\mathbb{R}\). The agent's aim is to maximise its utility, defined as the total sum of all rewards gained in an episode \(R_{t}=\sum_{\tau=t}^{\infty}\gamma^{\tau-t}r_{\tau}\), where \(\gamma\in[0,1]\) is the discount factor used to determine the importance of long-term rewards. In MARL, the action space \(\mathcal{U}\) is constructed from the action space \(\mathcal{A}^{i}\) of each individual agent. Normally \(u\) is a vector comprised of all the individual actions of \(k\) agents \(u=(a^{1},a^{2},a^{3},...,a^{k})\)[17]. In this paper, \(u\) will be used to refer to the final action which will be exercised on the environment and \(a^{i}\) is the action generated by the agent \(i\), which is dubbed as an action component of \(u\). One common approach in deep reinforcement learning is to use a value-based method, such as deep q-learning or its variants, to learn a (near) optimal policy \(\pi:\mathcal{S}\rightarrow\mathcal{A}\) which maps the observed states or observations to actions. The state-action value function, as defined below, tells each agent \(i\) the expected utility or discounted future return of taking the action \(a_{t}^{i}\) in the state \(s_{t}\):  
\[ \begin{split} Q^{\pi,i}(s,a^{i})&=\mathbb{E}[R_{t}| s_{t}=s,a_{t}=a^{i}]\\ &=\mathbb{E}_{s^{\prime}}[r+\gamma\,\mathbb{E}_{a^{\prime}\sim r ^{i}(s^{\prime})}[Q^{\pi,i}(s^{\prime},a^{i^{\prime}})]|s_{t}=s,a_{t}=a^{i}] \end{split}  \tag{1}\]  
By recursively solving Equation (1) for all state action pairs, and taking the action with the highest Q-value in the next state, the optimal action value function, which is defined as \(Q^{*}(s,a)=\max_{\pi}Q_{\pi}(s,a)\), can be derived. This optimal solution is shown in the Equation (2):  
\[Q^{i*}(s,a^{i})=\mathbb{E}_{s^{\prime}}[r+\gamma\max_{a^{i^{\prime}}}Q^{i*}(s ^{\prime},a^{i^{\prime}})|s,a^{i}] \tag{2}\]  
In non-trivial problems where there are large numbers of states and actions, \(Q(s,a)\) is often approximated by parameterised functions, such as neural networks (e.g., \(Q(s,a;\theta)\)), in which similar states are estimated with similar utility. Generally, DQNs or reinforcement learning algorithms are well-known for becoming unstable as the action space becomes larger, for example, of the order of hundreds or thousands of actions [16]. As a result, the performance of these algorithms degrades as the action space increases [10]. With reinforcement learning, the action space will have a different format and representation depending on the type of problem being tackled. Typically, these action spaces can be classified into two main categories: continuous and discrete. In a discrete action problem, the action space is most commonly constructed as a flat action space with each primitive action identified as one integer.