# Multi-UAV Conflict Resolution with Graph Convolutional Reinforcement Learning
## 3 Theoretical Background
### Reinforcement Learning  
Reinforcement Learning (RL) is a paradigm of machine learning which deals with sequential decision making [31]. A given RL problem is formalized by a Markov Decision Process (MDP), which is a discrete time stochastic control process [34] that consists of a 4-tuple \((S,A,T,R)\), where:  
* \(S\) is the state space,
* \(A\) is the action space,
* \(T:S\times A\times S\rightarrow[0,1]\) is the transition function which is a set of conditional probabilities between states,
* \(R:S\times A\times S\rightarrow\mathbb{R}\) is the reward function  
In RL, an agent makes decisions in an environment to maximize a certain notion of cumulative reward G, defined as follows:  
\[G_{t}=R_{t+1}+\gamma R_{t+2}+\gamma^{2}R_{t+3}+...=\sum_{k=0}^{\infty}\gamma^ {k}R_{t+k+1} \tag{1}\]where \(\gamma\) is a discount factor between 0 and 1. Its task is to inform the agent how relevant immediate rewards are in relation to rewards further in the future. The higher \(\gamma\) is the more the agent will care about future consequences. The agent improves incrementally by modifying its behavior according to previous experience. The agent does not strictly require complete information or knowledge of the environment; it only needs to interact with it and gather information [35]. The RL agents starts at an initial state \(s_{0}\in S\) and at each time step \(t\) must take an action \(a_{t}\in T\). Then, the agent gets a reward \(r_{t}\in R\) from the environment. The states then transitions to \(s_{t+1}\in S\), which is dictated by the taken action and the dynamics of the environment. Finally, the agent stops interacting with the environment when it reaches a defined goal state. The agent's behavior is encoded into a policy \(\pi\), which can be deterministic \(\pi:S\to A\), or stochastic \(\pi:S\times A\rightarrow[0,1]\). There are two ways that are used to predict the total future discounted reward: the value function \(V^{\pi}\) and the action-value function \(Q^{\pi}\), defined as follows:  
\[V^{\pi}(s)=\mathbb{E}_{\pi}(R_{t}|s_{t}=s) \tag{2}\]  
\[Q^{\pi}(s,a)=\mathbb{E}_{\pi}(R_{t}|s_{t}=s,a_{t}=a) \tag{3}\]  
The value function represents the future expected reward in the current state if the policy \(\pi\) is followed, while action-value function represents expected rewards for state-action pairs following policy \(\pi\). Ultimately, the goal of all RL algorithms is to solve either of these functions. Q-learning is one most prominent algorithms for solving RL problems. There, an agent must learn to estimate the optimal action-value function in the form of a table with as many state-action pair entries as possible [29]. However, in cases where the state space or action space (or both) are continuous, there are infinitely many state-action pairs, which makes it unfeasible to store the values in table. In those cases, a function is used to approximate the Q function. Such a function with parameters \(\mu\), is optimized through an objective function based on the Bellman equation [34]. In the case of Deep Q-Networks (DQN) [36], the Q function approximators are neural networks. However, several issue arise when applying deep learning directly on a RL problem. First, in RL rewards can be sparse or delayed, which hinders neural networks, as they rely on directly gained feedback. Additionally, the data that are obtained from an RL problem are highly correlated and lastly, the data distribution changes as the policy does, making it nonstationary, which further impairs the learning capabilities of neural networks. To overcome these issues, several modifications must be. Experience replay is used to mitigate the issue of sample autocorrelation [36]. In this technique, the agent's experience is stored at each time step in a replay buffer. the memory is sampled randomly and is used to update the networks. When the replay buffer becomes full, the simplest solution is to discard the oldest samples.