Computation and Learning of Equilibria in Markov Games
Event details
| Date | 20.08.2025 |
| Hour | 13:00 › 15:00 |
| Speaker | Philip Jordan |
| Location | |
| Category | Conferences - Seminars |
EDIC candidacy exam
Exam president: Prof. Mika Göös
Thesis advisor: Prof. Maryam Kamgarpour
Co-examiner: Prof. Nicolas Flammarion
Abstract
Markov games [1] provide a framework for modelling multi-agent RL problems. While computing Nash equilibria is hard even in the less general case of normal-form games [2], for certain subclasses of Markov games (e.g. zero-sum, and potential games), a variety of learning algorithms have been proposed [3].
A problem I have been studying in my first year is about (Markov) games with coupling constraints. Such games may e.g. model multi-agent RL with joint safety constraints. In particular, I am interested in existence and computation/learning of Nash equilibria in such constrained games. These topics have received significantly less attention than their unconstrained counterparts, and known results for both existence and computation come with strong assumptions -- such as convexity of the joint feasible set -- which we aim to relax.
Selected papers
[1] Shapley, Lloyd S. "Stochastic games." Proceedings of the national academy of sciences 39.10 (1953): 1095-1100. https://www.jstor.org/stable/88799
[2] Daskalakis, Constantinos, Paul W. Goldberg, and Christos H. Papadimitriou. "The complexity of computing a Nash equilibrium." Communications of the ACM 52.2 (2009): 89-97. https://dl.acm.org/doi/abs/10.1145/1461928.1461951 (for extended version, see https://people.csail.mit.edu/costis/journal_ver10.pdf)
[3] Ding, Dongsheng, et al. "Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence." International Conference on Machine Learning. PMLR, 2022. https://proceedings.mlr.press/v162/ding22b/ding22b.pdf
Exam president: Prof. Mika Göös
Thesis advisor: Prof. Maryam Kamgarpour
Co-examiner: Prof. Nicolas Flammarion
Abstract
Markov games [1] provide a framework for modelling multi-agent RL problems. While computing Nash equilibria is hard even in the less general case of normal-form games [2], for certain subclasses of Markov games (e.g. zero-sum, and potential games), a variety of learning algorithms have been proposed [3].
A problem I have been studying in my first year is about (Markov) games with coupling constraints. Such games may e.g. model multi-agent RL with joint safety constraints. In particular, I am interested in existence and computation/learning of Nash equilibria in such constrained games. These topics have received significantly less attention than their unconstrained counterparts, and known results for both existence and computation come with strong assumptions -- such as convexity of the joint feasible set -- which we aim to relax.
Selected papers
[1] Shapley, Lloyd S. "Stochastic games." Proceedings of the national academy of sciences 39.10 (1953): 1095-1100. https://www.jstor.org/stable/88799
[2] Daskalakis, Constantinos, Paul W. Goldberg, and Christos H. Papadimitriou. "The complexity of computing a Nash equilibrium." Communications of the ACM 52.2 (2009): 89-97. https://dl.acm.org/doi/abs/10.1145/1461928.1461951 (for extended version, see https://people.csail.mit.edu/costis/journal_ver10.pdf)
[3] Ding, Dongsheng, et al. "Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence." International Conference on Machine Learning. PMLR, 2022. https://proceedings.mlr.press/v162/ding22b/ding22b.pdf
Practical information
- General public
- Free
Contact
- edic@epfl.ch