# A Comparison of an Adaptive Self-Guarded Honeypot with Conventional Honeypots
## 2 Background
### Reinforcement Learning
#### 2.1.1 Markov Decision Processes  
The RL problem is modelled by Markov Decision Processes (MDP), as shown in Figure 1. At a time \(t\), facing the environment, which is represented by a _state_\(S_{t}\), the agent selects and executes an _action_\(A_{t}\). In return, it receives a reward \(R_{t+1}\in\mathbb{R}\) that allows it to evaluate its decision making. Subsequently, the agent now receives a new state \(S_{t+1}\), and again, selects a new action \(A_{t+1}\), then receives a new reward \(R_{t+2}\), and continues, again and again, improving its behaviour [7]. The _Markov property_ assumes that the _next action_ only depends on the _current state_ but not any other _previous state_.  
Formally, an MDP is a tuple \(<S,A,P,R>\) where  
* \(S\) is a (finite) set of states \(s\in S\), which represents the environment,
* \(A\) is a (finite) set of actions \(a\in A\) that the agent can perform,
* \(P^{a}_{ss^{\prime}}\) is the probability of reaching state \(s^{\prime}\) from state \(s\) after taking action \(a\) \[P^{a}_{ss^{\prime}}=P(S_{t+1}=s^{\prime}|S_{t}=s,A_{t}=a)\] (1)
* \(R^{a}_{s}\) is a reward function that the agent receives when it is in state \(s\) and is taking an action \(a\).  
Figure 1: Reinforcement Problem–Interaction between agent and its environment.  
Given this MDP, through the interactions between the agent and the environment, it produces a sequence of interactions called a _trajectory_ which consists of a sequence of states, actions and rewards: \(S_{0},A_{0},R_{1},S_{1},A_{1},R_{2},S_{3},\ldots\)[7]. The goal of the agent is to find a policy \(\pi\) to maximise its total reward, called a _return_\(G\). Each received reward is not equally valued because the agent can value the immediate reward more compared to the delayed rewards that the agent receives far in the future. Thus, the return \(G\) is the total discounted rewards from time-step \(t\), which is defined as  
\[G_{t}=R_{t+1}+\gamma R_{t+2}+\ldots=\sum_{k=0}^{\infty}\gamma^{k}R_{t+k+1} \tag{2}\]  
where \(\gamma\in[0,1]\) is a discount factor.  
The experiences can be derived from _episodic_ tasks or _continuous_ tasks. An episodic task has a start state and a terminating state, while a continuous one has no terminating state [7]. The agent uses these experiences to evaluate and improve its current policy.  
In most of the problems of reinforcement learning, an agent learns to estimate the _state-value_\(v(s)\) or a _state-action_ value \(q(s,a)\), also known as the \(q\)-value. These values provide an insight into the future rewards that the agent can receive. These rewards depend on how the agent decides to choose an action in a given state. The value of state and state-action following a policy \(\pi\) are denoted, respectively, as \(v_{\pi}(s)\) and \(q_{\pi}(s,a)\). The policy that allows the agent to maximise their state value is called an _optimal policy_, denoted as \(\pi^{*}\)[7].  
We differentiate two groups of learning methods: _model-based_ and _model-free_ methods. The model-based method requires the model of the environment to be completely defined and available to search for an optimal policy, whereas the model-free method relies only on the experiences through interacting with its environment and collecting rewards to find the optimal policy. Among these algorithms, we also distinguish two types of learning policy: _on-policy_ and _off-policy_. The former describes the group of algorithms that use their current learned policy to improve its own policy; whereas the latter exploits a different policy to improve its current policy [7].