Multiagent systems where the agents interact among themselves and with an stochastic environment can be formalized as stochastic games. We study a subclass of these games, named Markov potential games (MPGs), that appear often in economic and engineering applications when the agents share some common resource. We consider MPGs with continuous state-action variables, coupled constraints and nonconvex rewards. Previous analysis followed a variational approach that is only valid for very simple cases (convex rewards, invertible dynamics, and no coupled constraints); or considered deterministic dynamics and provided open-loop (OL) analysis, studying strategies that consist in predefined action sequences, which are not optimal for stochastic environments. We present a closed-loop (CL) analysis for MPGs and consider parametric policies that depend on the current state and where agents adapt to stochastic transitions. We provide easily verifiable, sufficient and necessary conditions for a stochastic game to be an MPG, even for complex parametric functions (e.g., deep neural networks); and show that a closed-loop Nash equilibrium (NE) can be found (or at least approximated) by solving a related optimal control problem (OCP). This is useful since solving an OCP---which is a single-objective problem---is usually much simpler than solving the original set of coupled OCPs that form the game---which is a multiobjective control problem. This is a considerable improvement over the previously standard approach for the CL analysis of MPGs, which gives no approximate solution if no NE belongs to the chosen parametric family, and which is practical only for simple parametric forms. We illustrate the theoretical contributions with an example by applying our approach to a noncooperative communications engineering game. We then solve the game with a deep reinforcement learning algorithm that learns policies that closely approximates an exact variational NE of the game. In a noncooperative stochastic dynamic game, the agents compete in a time-varying environment, which is characterized by a discrete-time dynamical system equipped with a set of states and a state-transition probability distribution. Each agent has an instantaneous reward function, which can be stochastic and depends on agents' actions and current system state. We consider that both the state and action sets are subsets of real vector spaces and subject to coupled constraints, as usually required by engineering applications.A dynamic game starts at some initial state. Then, the agents take some action and the game moves to another state and gives some reward values to the agents. This process is repeated at every time step over a (possibly) infinite time horizon. The aim of each agent is to find the policy that maximizes its expected long term return given other agents' policies. Thus, a game can be represented as a set of coupled optimal-control-problems (OCPs), which are difficult to solve in general.OCPs are usually analyzed for two cases namely open-loop (OL) or closed-loop (CL), depending on the information that is available to the agents when making their decisions. In the OL analysis, the action is a function of time, so that we find an optimal sequence of actions that will be executed in order, without feedback after any action. In the CL setting, the action is a mapping from the state, usually referred as feedback policy or simply policy, so the agent can adapt its actions based on feedback from the environment (the state transition) at every time step. For deterministic systems, both OL and CL solutions can be optimal and coincide in value. But for stochastic system, an OL strategy consisting in a precomputed sequence of actions cannot adapt to the stochastic dynamics so that it is unlikely to be optimal. Thus, CL are usually preferred over OL solutions.For dynamic games, the situation is more involved than for OCPs, see, e.g., BID1 . In an OL dynamic game, agents' actions are functions of time, so that an OL equilibrium can be visualized as a set of state-action trajectories. In a CL dynamic game, agents' actions depend on the current state variable, so that, at every time step, they have to consider how their opponents would react to deviations from the equilibrium trajectory that they have followed so far, i.e., a CL equilibrium might be visualized as a set of trees of state-action trajectories. The sets of OL and CL equilibria are generally different even for deterministic dynamic games BID10 BID5 .The CL analysis of dynamic games with continuous variables is challenging and has only be addressed for simple cases.The situation is even more complicated when we consider coupled constraints, since each agent's actions must belong to a set that depends on the other agents' actions. These games, where the agents interact strategically not only with their rewards but also at the level of the feasible sets, are known as generalized Nash equilibrium problems BID3 .There is a class of games, named Markov potential games (MPGs), for which the OL analysis shows that NE can be found by solving a single OCP; see BID6 BID25 for recent surveys on MPGs. Thus, the benefit of MPGs is that solving a single OCP is generally simpler than solving a set of coupled OCPs. MPGs appear often in economics and engineering applications, where multiple agents share a common resource (a raw material, a communication link, a transportation link, an electrical transmission line) or limitations (a common limit on the total pollution in some area). Nevertheless , to our knowledge, none previous study has provided a practical method for finding CL Nash equilibrium (CL-NE) for continuous MPGs.Indeed, to our knowledge, no previous work has proposed a practical method for finding or approximating CL-NE for any class of Markov games with continuous variables and coupled constraints. State-of-the-art works on learning CL-NE for general-sum Markov games did not consider coupled constraints and assumed finite state-action sets BID18 BID16 .In this work, we extend previous OL analysis due to BID26 BID23 and tackle the CL analysis of MPGs with coupled constraints. We assume that the agents' policies lie in a parametric set. This assumption makes derivations simpler, allowing us to prove that, under some potentiality conditions on the reward functions, a game is an MPG. We also show that, similar to the OL case, the Nash equilibrium (NE) for the approximate game can be found as an optimal policy of a related OCP. This is a practical approach for finding or at least approximating NE, since if the parametric family is expressive enough to represent the complexities of the problem under study, we can expect that the parametric solution will approximate an equilibrium of the original MPG well (under mild continuity assumptions, small deviations in the parametric policies should translate to small perturbations in the value functions). We remark that this parametric policy assumption has been widely used for learning the solution of single-agent OCPs with continuous state-action sets; see, e.g., BID9 Melo and Lopes, 2008; BID17 BID24 BID20 . Here, we show that the same idea can be extended to MPGs in a principled manner.Moreover, once we have formulated the related OCP, we can apply reinforcement learning techniques to find an optimal solution. Some recent works have applied deep reinforcement learning (DRL) to cooperative Markov games BID4 BID22 , which are a particular case of MPGs. Our results show that similar approaches can be used for more general MPGs. We have extended previous results on MPGs with constrained continuous state-action spaces providing practical conditions and a detailed analysis of Nash equilibrium with parametric policies, showing that a PCL-NE can be found by solving a related OCP. Having established a relationship between a MPG and an OCP is a significant step for finding an NE, since we can apply standard optimal control and reinforcement learning techniques. We illustrated the theoretical results by applying TRPO (a well known DRL method) to an example engineering application, obtaining a PCL-NE that yields near optimal results, very close to an exact variational equilibrium.A EXAMPLE: THE "GREAT FISH WAR" GAME -STANDARD APPROACH Let us illustrate the standard approach described in Section 3 with a well known resource-sharing game named "the great fish war" due to BID11 . We follow (González-Sánchez and Hernández-Lerma, 2013, Sec. 4.2). Example 1. Let x i be the stock of fish at time i, in some fishing area. Suppose there are N countries obtaining reward from fish consumption, so that they aim to solve the following game: DISPLAYFORM0 where x 0 ≥ 0 and 0 < α < 1 are given.In order to solve G fish , let us express each agent's action as: DISPLAYFORM1 so that the rewards can be also expressed in reduced form, as required by the standard-approach: DISPLAYFORM2 Thus, the Euler equations for every agent k ∈ N and all t = 0, . . . , ∞ become: DISPLAYFORM3 Now, the standard method consists in guessing a family of parametric functions that replaces the policy, and checking whether such parametric policy satisfies (32) for some parameter vector. Let us try with policies that are linear mappings of the state: DISPLAYFORM4 By replacing (33) in (32), we obtain the following set of equations: DISPLAYFORM5 Fortunately, it turns out that (34) has solution (which might not be the case for other policy parametrization), with parameters given by: DISPLAYFORM6 Since 0 < α < 1 and 0 ≤ γ < 1, it is apparent that w k > 0 and the constraint π k (x i ) ≥ 0 holds for all x i ≥ 0. Moreover, since k∈N w k < 1, we have that x i+1 ≥ 0 for any x 0 ≥ 0. In addition, since x i is a resource and the actions must be nonnegative, it follows that lim i→∞ x i = 0 (there is no reason to save some resource). Therefore, the transversality condition holds. Since the rewards are concave, the states are non-negative and the linear policies with these coefficients satisfy the Euler and transversality equations, we conclude that they constitute an equilibrium (González-Sánchez and Hernández-Lerma, 2013, Theorem 4.1).B EXAMPLE: "GREAT FISH WAR" GAME -PROPOSED APPROACHIn this section, we illustrate how to apply the proposed approach with the same "the great fish war" example, obtaining the same results as with the standard approach.Example 2. Consider "the great fish war" game described in Example 1. In order to use our approach, we replace the generic policy with the specific policy mapping of our preference. We choose the linear mapping, π k (x i ) = w k x i , to be able to compare the results with those obtained with the standard approach. Thus, we have the following game: DISPLAYFORM7 Let us verify conditions FORMULA9 - FORMULA9 . For all k, j ∈ N we have: DISPLAYFORM8 DISPLAYFORM9 Since conditions FORMULA9 - FORMULA9 hold, we conclude that FORMULA5 is an MPG. By applying the line integral FORMULA2 , we obtain: DISPLAYFORM10 Now, we can solve OCP (16) with potential function (43). For this particular problem, it is easy to solve the KKT system in closed form. Introduce a shorthand : DISPLAYFORM11 The Euler-Lagrange equation (62) for this problem becomes: DISPLAYFORM12 The optimality condition (64) with respect to the policy parameter becomes: DISPLAYFORM13 Let us solve for β i in (46): DISPLAYFORM14 Replacing FORMULA6 and the state-transition dynamics in FORMULA6 , we obtain the following set of equations: DISPLAYFORM15 Hence, the parameters can be obtained as: DISPLAYFORM16 This is exactly the same solution that we obtained in Example 1 with the standard approach. We remark that for the standard approach, we were able to obtain the policy parameters since we put the correct parametric form of the policy in the Euler equation. If we had used another parametric family without a linear term, the Euler equations (32) might have no solution and we would have got stuck. In contrast, with our approach, we could freely choose any other form of the parametric policy, and always solve the KKT system of the approximate game. Broadly speaking, we can say that the more expressive the parametric family, the more likely that the optimal policy of the original game will be accurately approximated by the optimal solution of the approximate game.
We present general closed loop analysis for Markov potential games and show that deep reinforcement learning can be used for learning approximate closed-loop Nash equilibrium.
{"src": "scitldr-AIC_train", "paper_id": "rJm7VfZA-"}