# Multi-Agent Reinforcement Learning: A Review of Challenges and Applications
## 2 Background
### Single-Agent RL Algorithms  
The field of RL is extremely broad, and over the last few years, a multitude of algorithms have been presented. To categorize them, the first division can be made between model-free and model-based algorithms. Model-based algorithms require users to have access to a model of the environment, including the transition probability and the associated reward, or to learn the model directly during training. They then use the model to plan the best action to take. An example of this approach is the DYNA algorithm [12]. This approach leads to an optimal solution; however, in most applications, a model of the environment cannot be obtained or would be too complex to implement. Moreover, the quality of the solutions is sensitive to error in the model estimation. Another downside is a loss of computational efficiency in cases in which the model is highly complex but the optimal policy is very simple. An example could be a complex robotic system that has to learn only how to move forward. In recent research, the efficiency of the learned model has been addressed, obtaining state-of-the-art performances with approaches such as MuZero and AlphaZero [13; 14].  
Model-free algorithms do not require any knowledge about the model, and they operate by directly optimizing the policy or other value parameters. This type of approach is goal-oriented and can perform in a variety of environments and adapt to their changes. In this work, we focus exclusively on model-free algorithms. Model-free algorithms can be further divided in two fields: value-based approaches and policy-based approaches.  
The objective of value-based methods is to find good estimates of the state and/or state-action pair value functions \(V(s)\) and \(Q(s,a)\). The optimal policy is selected using a fixed rule to map from the value functions to the actions; for an example, take the \(\epsilon-greedy\) policy, which selects the action associated with the higher Q-value with probability \(1-\epsilon\) and a random action with probability \(\epsilon\). An example of this approach is the famous Q-learning algorithm [15]. Policy-based methods do not require the value function to be estimated but use a parameterized policy that represents a probability distribution of actions over states \(\pi_{\theta}=Pr[a|s]\) as a neural network. The policy is directly optimized by defining an objective function and using gradient ascent to reach an optimal point. If we consider, for example, the reward as the objective function, we can derive the expression  
\[\
abla_{\theta}\mathbb{E}[R(S,A)]=\mathbb{E}[\
abla_{\theta}\log\pi_{\theta}( A|S)R(S,A)] \tag{8}\]  
which is known as the policy gradient theorem. While the expected value of the reward cannot be differentiated, the policy can, making gradient ascent possible. A last category of RL algorithms that originates from the combination of policy-based and value-based methods is the actor-critic approach. As shown in Figure 2, in an actor-critic algorithm, two different learning agents are defined:* The critic, which has the task of estimating the value function, typically using TD methods;
* The actor, which represents the parameterized policy and updates its action distribution in the direction \"suggested\" by the critic using a policy gradient.  
The critic outputs a signal that changes the action selection preferences in order to chose actions related to higher value functions more frequently. This kind of algorithm presents a reduced variance in the gradient estimates due to the use of the value function information to guide the policy evolution. In addition, minimal computation is required to select an action as there is no need to compare different state-action values, and it is possible to learn an explicitly stochastic policy [16].  
All of these methods, as summarized in Figure 3, have been used with success in the solution of RL problems, and their effectiveness is dependent on the type of problem.