# Multi-Agent Reinforcement Learning: A Review of Challenges and Applications
## 2 Background  
In the field of machine learning, reinforcement learning stands apart from the classic paradigm based on learning from examples. It adopts a trial and error procedure using a reward provided by an interpreter that observes the interaction of the agent with the environment. It takes inspiration from research into animal learning [9] combined with theoretical concepts of optimal control theory.  
The interaction between the agent and the environment can be described by three fundamental elements: state, actions, and reward. The state represents a particular configuration of the environment, the actions are the options that the agents have to interact with to modify the environment, and the reward is a signal used to define the task of the agent and is what motivates the agent to pick one action with respect to the others.  
The learning process is iterative. The agent senses the environment while collecting its current state. The agent performs an action, thereby reaching the next state, and it receives a reward based on the combination of the state and selected action. This process is then repeated. The agents adopt a policy to determine the best action to select, which is a mapping from all the possible states of the environment to the action that can be selected.  
The reward, however, is not sufficient to determine the optimal policy because an instantaneous reward does not give information about the future rewards that a specific action can lead to--that is, the long-term profit. For this reason, it is useful to introduce a new kind of reward: the return value \(R_{t}\). If we write as \(r_{t}\) the reward received by the agent at the time-step \(t\), the return value over a finite length time horizon T is defined as  
\[R_{t}=r_{t+1}+\gamma r_{t+2}+\gamma^{2}r_{t+3}+\ldots+\gamma^{T-t-1}r_{T}= \sum_{i=0}^{T-t-1}\gamma^{i}r_{t+i+1} \tag{1}\]  
Sometimes, the return value is also considered for non-finite time horizons.  
\[R_{i}=\sum_{i=0}^{\infty}\gamma^{i}r_{i+1} \tag{2}\]  
where \(\gamma\) is a discounted factor such that \(0\leq\gamma<1\). To evaluate the quality of a particular state or state-action pair, it is possible to define two value functions. In particular, under a policy \(\pi\), the value function of the state is calculated as  
\[V_{\pi}(s)=\mathbb{E}[R_{t}|s_{t}=s,\pi] \tag{3}\]  
and the value faction of the state-action pair is calculated as  
\[Q_{\pi}(s,a)=\mathbb{E}[R_{t}|s_{t}=s,a_{t}=a,\pi] \tag{4}\]  
A value function can be expressed as the relation of two consecutive states \(s_{t}\) and \(s_{t}+1\) defining the so called Bellman Equations (5) and (6).  
\[V_{\pi}(s)=\sum_{a}\pi(s_{t},a)\sum_{s_{t+1}}p(s_{t+1}|s_{t},a)(\mathbb{W}_{s _{t}\to s_{t+1}|a}+\gamma V\pi(s_{t+1})) \tag{5}\]  
and  
\[Q_{\pi}(s,a)=\sum_{s_{t+1}}p(s_{t+1}|s_{t},a)\Bigg{(}\mathbb{W}_{s_{t}\to s_{t+ 1}|a}+\gamma\sum_{a^{\prime}}\pi(s_{t+1},a^{\prime})Q_{\pi}(s_{t+1},a^{\prime} )\Bigg{)} \tag{6}\]  
A way to approximate the solutions to these equations is by using dynamic programming. However, this approach requires complete information about the dynamics of the problem. Model-free RL algorithms can be considered as an efficient alternative.