# Network Defense Strategy Selection with Reinforcement Learning and Pareto Optimization
## 2 Game Theory on Pareto Optima and Q-learning  
### Simple Single Objective Q-Learning  
Q-learning is a model-free approach to find an optimal state-action policy for a given Markov process, meaning that if the system finds itself in a specific state, the conditional probability distribution of future states is independent of the sequence of events or states that preceded it. Q-learning uses dynamic programming to allow a software agent to repeatedly examine specific sate-action pairs and determine if they are beneficial, and thus worth repeating, or harmful, and thus should be avoided [43]. Specifically, we assume that a software agent is moving through a finite state space that can, in a specific state, perform one of a finite set of associated actions, the result of which may or may not be state change. We also assume that each state-action pair, i.e., the action performed by the agent while in the specific state, has an associated reward. Finally, we assume that the probability that a specific state-action pair results in a given state change is independent of the agent's previous actions or states, i.e., the agent's movement is a Markov process. Given these assumptions, it is possible to use Q-learning to determine a movement policy that maximizes the software agent's cumulative reward. Defining the environment described in the previous paragraph means that at a given time \(t\), our agent will be in state \(x_{t}\) (\(\epsilon\)\(S\)), and be able to perform action \(a_{t}\)(\(\epsilon\)\(A\)),which should result in a reward \(r_{t}\) and a probability of moving to state \(y\)(\(\epsilon\)\(S\)). The probability that the environment at time \(t+1\) will have changed to state \(y\) is defined as:  
\[Prob\big{(}x_{t+1}=y\bigm{|}x_{t},a_{t}\big{)}=P_{x_{t},y}(a_{t})=\ P_{x,y}(a) \tag{1}\]  
Note that because this is a Markov process, the probabilities are time independent. The probability that action \(a\) at state \(x\) will result in state \(y\), is the same at \(t\ =\ 0\) and \(t\ =\ 1000\). The action that the agent will take is determined by its policy \(\pi\), such that:  
\[\pi(x)=a \tag{2}\]  
Note that just like the probabilities in Equation (1), the policy is also time independent. Rewards are equally time independent, meaning we can rewrite the reward at time t as a function of the state and policy dictated action:  
\[r_{t}=R_{x}(\pi(x)) \tag{3}\]  
The goal of the Q-learning algorithm is to determine an optimal policy \(\pi^{*}\) that will result in a maximum value for \(\sum_{t}r_{t}\). For this we need to determine both the value of the current reward and the potential future rewards. We define the combination of those two as the value of a state:  
\[V^{\pi}(x)=R_{x}(\pi(x))+\ \gamma\sum_{y}P_{x,y}(\pi(x))V^{\pi}(y) \tag{4}\]  
Here, \(V^{\pi}(x)\) is the value of state \(x\) when using policy \(\pi\) and \(\gamma\) is a discount factor, used to exponentially discount the value of future states. We can now use dynamic programming to determine the optimal policy by finding the action maximizes the state value at each step:  
\[V^{*}(x)=\ V^{\pi^{*}}(x)=\max_{a}\{R_{x}(a)+\ \gamma\sum_{y}P_{x,y}(a)V^{\pi^{*}}( y)\} \tag{5}\]  
The optimal policy \(\pi^{*}\) says that at state x, the agent should perform the action a, that results in the maximum possible state value \(V^{*}(x)\), assuming that the agent continues with policy \(\pi^{*}\). An example of a Markov process with policy-specific state values is given in Figure 1. If the values for \(\gamma\), \(R_{x}(a)\), and \(P_{x,y}(a)\) are known, this can easily be implemented as simple iterative function. This iterative approach requires a Q-value to compare single action changes to the policy.