# Strategies for Scaleable Communication and Coordination in Multi-Agent (UAV) Systems
## 2 Reinforcement Learning
### Actions, Policies, and Value Functions  
A policy \(\pi(s)\) defines the actions \(a_{i}\in\mathcal{A}_{i}\) of each agent \(i\in\mathcal{N}\) in the current state \(s\in\mathcal{S}\) where \(\mathcal{N}\) is the set of all agents, \(\mathcal{A}_{i}\) is the set of all possible actions at agent \(i\) and \(\mathcal{S}\) is the set of all possible states (in the multi-agent system). That is, for some joint action \(\mathbf{a}=(a_{1},a_{2},\ldots,a_{|\mathcal{N}|})\):  
\[\pi(s):=\mathbf{a}. \tag{1}\]  
Figure 2: Fundamentals of reinforcement learning. (**a**) The state-action-reward-state-action feedback loop. The state, reward, and action at time \(t\) is given by \(s_{t},r_{t}\), and \(a_{t}\) respectively, where \(a_{t}=\pi(s_{t})\) and \(\pi(\cdot)\) is the control policy. The agent optimizes its policy by observing and reacting to the environment. (**b**) The actor-critic training paradigm. The agent includes the actor and critic. The actor defines the control policy (the family of policies is parameterized by \(\theta\)). The critic evaluates the policy (\(J(\theta)\) is the value of the policy \(\pi_{\theta}(\cdot)\)) based on feedback from the environment, and guides the actor to a better policy (via the gradient \(\
abla\theta\)). Local policies \(\pi_{i}(s)\) define the actions \(a_{i}\) of a particular agent \(i\in\mathcal{N}\), whereas global policies \(\pi(s)=(\pi_{1}(s),\pi_{2}(s),\ldots,\pi_{|\mathcal{N}|}(s))\) define the actions of all \(|\mathcal{N}|\) agents simultaneously (i.e., all the individual local policies). The actions executed by all agents collectively form the \"joint\" action \(\mathbf{a}\). In distributed systems, each agent only has direct access to its local state, so any joint-action requires some form of system-wide inter-agent communication to infer \(s\in\mathcal{S}\). In applications where the system has locally interactive structure, agents can prioritize the local states of other agents in their vicinity over agents further away, to reduce the total information throughput [9; 10]. Each agent then obtains a unique view of the state space, with decreasing resolution in regions of the grid more remote from its current position. Even though each agent has different views, the joint-action is still approximately optimal provided the remote areas have enough resolution to capture \"lower-order\" trends. This trade-off between information throughput and overall tracking performance is further explored in Sections 3 and 4. Every policy \(\pi(s)\) at state \(s\in\mathcal{S}\) has an associated value \(V_{\pi}(s)\), defined as the expected discounted reward received over the operating lifetime. \(V_{\pi}(s)\) is called the value function for the policy \(\pi\). Let \(S_{t}\), \(A_{t}\), and \(R_{t}\) be random variables that denote the system state, action, and reward respectively at time \(t\). Let \(\gamma\) denote the discount factor which, like an interest rate, discounts the rewards expected in the future over rewards in the present. Then \(V_{\pi}(s)\) is defined as:  
\[V_{\pi}(s):=E_{\pi}\Bigg{[}\sum_{k=0}^{\infty}\gamma^{k}R_{t+k}|S_{t}=s\Bigg{]}. \tag{2}\]  
Let \(\pi^{*}(s)\) denote the policy with the highest value \(V^{*}(s)\) (i.e., the optimal policy):  
\[V^{*}(s) :=\max_{\pi}V_{\pi}(s), \tag{3}\] \[\pi^{*}(s) :=\arg\max_{\pi}V_{\pi}(s). \tag{4}\]  
The main objective in RL is to compute the \(\pi^{*}(s)\) defined in (4). The optimizations in (3) and (4) satisfy the following fundamental property:  
\[V^{*}(s):=\max_{\mathbf{a}}E_{\pi}[R_{t}+\gamma V^{*}(S_{t+1})|S_{t}=s,A_{t}= \mathbf{a}] \tag{5}\]  
Equation (5) follows from Bellman's Principle of optimality which says that any segment in the shortest path between two points is the shortest sub-path between the segment endpoints. In this case, the \"shortest\" path is the trajectory of states that achieves the maximum discounted reward in (2). For most applications, it is not practical to compute (3) and (4) directly since there are exponentially many trajectories in the size of the state space \(|\mathcal{S}|\).