Published as a conference paper at ICLR 2018 LEARNING PARAMETRIC CLOSED-LOOP POLICIES FOR MARKOV POTENTIAL GAMES
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.
Summary:
This paper studies multi-agent sequential decision making problems that belong to the class of games called Markov Potential Games (MPG). It considers finding the optimal policy within a parametric space of policies, which can be represented by a function approximator such as a DNN.
A main contribution of this work is that it shows that for MPG, instead of solving a multi-objective optimization problem (Eq. 8), which is difficult, it is sufficient to solve a scalar-valued optimization problem (Eq. 16).  Theorem 1 shows that under certain conditions on the reward function, the game is MPG. It also shows how one might find the potential function J, which is used in the single objective optimization problem.
Finding J can be computationally expensive in general. So the paper provides some properties that lead to finding J easier. For example, obtaining J is easy if we have a cooperative game (Corollary 1) or the reward can be decomposed/decoupled in a certain way (Theorem 2).
Evaluation:
This is a well-written paper that studies an important problem, but I don’t think ICLR is the right venue for it. There is not much about (representation) learning in this work. The use of TRPO as an RL algorithm in the Experiment does not play a critical role in this work either. Aside this general comment, I have several other more specific comments.
- There is a significant literature on the use of RL for multi-agent systems. The paper does not do a good job comparing and positioning with respect to them. For example, refer to the following recent paper and references therein:
Perolat, Strub, et al., “Learning Nash Equilibrium for General-Sum Markov Games from Batch Data,” AISTATS, 2017.
- If I understand correctly, the policies are considered to be functions from the state of the system to a continuous action. So it is a function, and not a probability distribution. This means that the space of considered policies correspond to the space of pure strategies. We know that for some games, the Nash equilibrium is a mixed strategy. Isn’t this a big limitation of this approach?
- I am unclear how this approach can handle stochastic dynamics. For example, the optimization (P1) depends on the realization of (theta_i)_i. But this is not available. The dependence is not only in the objective, but also in the constraints, which makes things more difficult.
I understand that in the experiments the authors used two models (either the average of random realization, or solving a different optimization for each realization), but none of them is an appropriate solution for a stochastic system.
- How large is the MPG class? Is there any structural result that positions them compared to other Markov Games? For example, is the class of zero-sum games an example of MPG?
- There is a comment close to the end of Section 5 that when there is no prior knowledge of the dynamics and the reward, one can use the proposed approach to learn PCL-NE by using any DRL.
This is questionable because if the reward is not known, the conditions of Theorems 1 or 2 cannot be verifies, so it is not possible to use (P1) instead of (G2).
- What comments can you make about the computational complexity? It seems that depending on the dynamics, the optimization problem P1 can be non-convex, hence computationally difficult to solve.
- How is the work related to the following paper?
Macua, Zazo, Zazo, “Learning in Constrained Stochastic Dynamic Potential Games,” ICASSP, 2016
======
I updated the score based on the authors' rebuttal.