{
  "id": "2406.08847",
  "version": "v1",
  "published": "2024-06-13T06:15:44.000Z",
  "updated": "2024-06-13T06:15:44.000Z",
  "title": "Roping in Uncertainty: Robustness and Regularization in Markov Games",
  "authors": [
    "Jeremy McMahan",
    "Giovanni Artiglio",
    "Qiaomin Xie"
  ],
  "comment": "Accepted to ICML 2024",
  "categories": [
    "cs.GT",
    "cs.DS",
    "cs.LG"
  ],
  "abstract": "We study robust Markov games (RMG) with $s$-rectangular uncertainty. We show a general equivalence between computing a robust Nash equilibrium (RNE) of a $s$-rectangular RMG and computing a Nash equilibrium (NE) of an appropriately constructed regularized MG. The equivalence result yields a planning algorithm for solving $s$-rectangular RMGs, as well as provable robustness guarantees for policies computed using regularized methods. However, we show that even for just reward-uncertain two-player zero-sum matrix games, computing an RNE is PPAD-hard. Consequently, we derive a special uncertainty structure called efficient player-decomposability and show that RNE for two-player zero-sum RMG in this class can be provably solved in polynomial time. This class includes commonly used uncertainty sets such as $L_1$ and $L_\\infty$ ball uncertainty sets.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-06-13T06:15:44.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "reward-uncertain two-player zero-sum matrix games",
      "robustness",
      "uncertainty sets",
      "regularization",
      "study robust markov games"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}