# Environmental-Impact-Based Multi-Agent Reinforcement Learning
## 1 Introduction  
Many real-world problems are selfish multi-agent systems with shared facilities, referred to as the _common pool resource problems_[1]. The agents choose from a number of available actions to use the shared facility and accordingly earn \"rewards\" from the environment. Using the common resource to maximize its own reward, each agent's goal will be in potential conflict with that of its fellows. Examples include water resource management [2], real-time traffic flow control [3], coordination of autonomous vehicles [4], and multi-player video games [5]. In the autonomous vehicle problem, streets, intersections, and highways are shared common resources. Each vehicle plans a path to reach its given destination and is rewarded based on how fast it gets there. Ideally, each vehicle should choose the shortest path, but this may lead to congestion. So, to maximize their individual rewards, they need to cooperate. Such situations raise a type of Sequential Social Dilemma (SSD) [6] where the most rewarding strategy for each agent (in the short-term) is to \"defect\" and exploit the common resource as much as possible, resulting in mutual defection among all agents; however, this results in the depletion of the common resource, and each agent earns (in the long-term) much less than if they would have all \"cooperated\" and used the common resource up to a certain limit. In SSDs, cooperative or defective behaviors exist not only as atomic actions but also as being temporally extended over each agent's decision-making \"policy\", that is, a strategy that determines what action to choose at each environment state. The question, then, is how to design the agents' policies to have cooperative agents that maximize the collective reward, i.e., to maximize total reward whileminimizing unfairly low rewards earned by cooperators who facilitate the high rewards earned by the \"free-riders\" who defect. The many often stochastic factors impacting the environment and their unknown underlying mechanisms challenge the use of traditional modeling techniques in solving SSDs. For example, in the autonomous vehicle problem, the number of vehicles in each lane is variable, and great uncertainty is involved in the drivers' behavior. Moreover, the observation and action spaces of each agent are too large to search through exhaustively or near exhaustively to find the optimal policies. Even if the optimal policies are found, they are not generalizable--a new environment would need new policies. To tackle these modeling complexities, in addition to model-based structures, Multi-Agent Reinforcement Learning (MARL) proposes a model-free structure where intelligent agents require no prior knowledge about the environment and \"learn\" the optimal policies directly from interacting with the environment. During the interactions, each agent observes the environment state and executes one of the available actions based on its policy. Consequently, the environment transfers to a new state and provides the agent an _extrinsic reward_ indicating the immediate desirability of the environment state. The agent utilizes these interactions to estimate a _state value function_ that assigns to each state the long-term expected reward that the agent obtains when starting from that state and following its policy. According to this value function, the agent improves its policy to choose those actions that result in the highest-value states [7]. The learned policies may be generalized to or sometimes readily used in unseen environments of the problem. However, learning policies in SSDs by using only extrinsic rewards has limited performance because each extrinsic reward is agent (rather than collective)-specific and typically selfishly maximized by exploiting other agents, which can lead to mutual defection. This is because a cooperative equilibrium either does not exist or is difficult to find [8; 9]. One way to mitigate social dilemmas is to reshape the rewards so that defecting behaviors are no longer an equilibrium.