# Multi-Agent Reinforcement Learning: A Review of Challenges and Applications
## 2 Background
### Single-Agent RL Algorithms
#### 2.2.3 A3c  
Recalling the policy update rule of REINFORCE \(\theta\leftarrow\theta+\alpha(R_{t}-b)\
abla_{\theta}\ln\pi_{\theta}\), a frequently used baseline \(b\) is a learned estimate of the state value function \(b(s)=V^{\pi}(s;\theta_{v})\). If this kind of baseline is selected, we can express the term \(R_{t}-b\) as an advantage function \(A(a_{t},s_{t})=Q(s_{t},a_{t})-V(s_{t})\) because \(R_{t}\) is an estimate of the state-action value function. This approach can be viewed as an actor-critic method in which the actor is the policy network \(\pi_{\theta}\) and the critic is represented by the baseline. In [20], A3C (asynchronous advantage actor critic) and its synchronous variant A2C are presented; the algorithm maintains a policy function \(\pi(a_{t}|s_{t};\theta)\) parameterized by \(\theta\) and an estimate of the value function \(V(s_{t};\theta_{v})\) parameterized by \(\theta_{v}\). In the formulation, the weights are considered separately; in the implementation, the same deep convolutional neural network is used to approximate the policy and the state value, with the only difference being in the separated output layers (a soft-max layer for the policy and linear layer for the state value). The algorithm continues for a number of steps \(t_{max}\) or until it reaches a terminal state; the return value is then calculated, and the updating of the parameters is performed following the gradient. In Algorithm 1 the psuedocode of the A3C algorithm can be found.  
\[\begin{split}&\
abla_{\theta^{\prime}}\log\pi(a_{t}|s_{t}; \theta^{\prime})A(s_{t},a_{t};\theta,\theta_{v})\\ &\text{with }A\text{ given by}\\ & A(s_{t},a_{t};\theta,\theta_{v})=\sum_{i=0}^{k-1}\gamma^{i}r_{ t+i}+\gamma^{k}V(s_{t+k};\theta_{v})-V(s_{t};\theta_{v})\end{split} \tag{13}\]  
The algorithm was trained and tested in a variety of domains, such as the Atari 2600 platform, improving upon the results of state-of-the-art RL algorithms such as the Deep Q-network [21].  
```
//Assume global shared parameter vectors \(\theta\) and \(\theta_{v}\) and global shared counter \(T=0\) //Assume thread-specific parameter vectors \(\theta^{\prime}\) and \(\theta^{\prime}_{v}\)  Initialize thread step counter \(t\gets 1\) repeat  Reset gradients \(d\theta\gets 0\) and \(d\theta_{v}\gets 0\).  Syncronize thread-specific parameters \(\theta^{\prime}=\theta\) and \(\theta^{\prime}_{v}=\theta_{v}\) \(t_{start}=t\)  Get s\({}_{t}\) repeat  Perform \(a_{t}\) according to policy \(\pi(a_{t}|s_{t};\theta^{\prime})\)  Recieve reward \(r_{t}\) and new state \(s_{t+1}\) \(t\gets t+1\) \(T\gets T+1\) until terminal \(s_{t}\) or \(t-t_{start}==t_{max}\) \(R=\begin{cases}0\text{ for terminal }s_{t}\\ V(s_{t},\theta^{\prime}_{v})\text{ for non-terminal }s_{t}\ //\text{ Bootstrap from last state}\end{cases}\) for\(i\in t-1,\dots,t_{start}\)do \(R\gets r_{i}+\gamma R\)  Accumulate gradients wrt \(\theta^{\prime}:d\theta\gets d\theta+\
abla_{\theta^{\prime}}\log\pi(a_{ i}|s_{i};\theta^{\prime})(R-V(s_{i};\theta^{\prime}_{v}))\)  Accumulate gradients wrt \(\theta^{\prime}_{v}:d\theta_{v}\gets d\theta_{v}+\partial(R-V(s_{i}; \theta^{\prime}_{v}))^{2}/\partial\theta^{\prime}_{v}\) endfor  Perform asynchronous update of \(\theta\) using \(d\theta\) and of \(\theta_{v}\) using \(d\theta_{v}\) until\(T>T_{max}\)
```  
**Algorithm 1** A3C Pseudocode [20].