{
  "abstract": "We study average-reward weakly-coupled Markov decision processes (WCMDPs), where a WCMDP consists of $N$ smaller MDPs, called arms, that share multiple per-step budget constraints. We consider the setting where the arms have identical model parameters, multiple actions, and state- and action-dependent costs. For restless bandits (RBs), a well-studied special case of WCMDPs, prior work has developed policies that achieve an $O(1/\\sqrt{N})$ optimality gap under general conditions, and has further identified conditions under which policies can achieve a better-than-$1/\\sqrt{N}$ optimality gap. However, for general WCMDPs, no prior result achieves an optimality gap better than $1/\\sqrt{N}$. In this paper, we identify conditions analogous to those for RBs under which a better-than-$1/\\sqrt{N}$ optimality gap is achievable, and design a policy that attains an $O(1/N)$ optimality gap. Notably, unlike prior approaches based on generalizing priority orderings, our policy is not priority-based but rather is designed to induce locally linear mean-field dynamics.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2609.38132",
  "author_total": 5,
  "authors": [
    {
      "name": "Yige Hong"
    },
    {
      "name": "Xiangcheng Zhang"
    },
    {
      "name": "Qiaomin Xie"
    },
    {
      "name": "Yudong Chen"
    },
    {
      "name": "Weina Wang"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/eb36p2d7as3re.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2609.38132",
  "fulltext_url": null,
  "id": "eb36p2d7as3re",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2609.38132",
  "language": null,
  "licence": "CC-BY-4.0",
  "licence_label": "CC BY 4.0",
  "licence_source": "article",
  "licence_url": "http://creativecommons.org/licenses/by/4.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.LG"
    ],
    [
      "arxiv",
      "math.OC"
    ],
    [
      "arxiv",
      "math.PR"
    ],
    [
      "openalex",
      "1803|Advanced Bandit Algorithms Research"
    ]
  ],
  "openalex": "W7214926971",
  "pdf_url": "https://arxiv.org/pdf/2609.38132",
  "pmcid": null,
  "pmid": null,
  "published": "2026-09-29",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/eb36p2d7as3re.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:25:36Z",
      "native_id": "2609.38132",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2609.38132"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    },
    {
      "field": "mathematics",
      "origin": "arxiv:math.PR",
      "subfield": "probability"
    }
  ],
  "title": "Achieving an $O(1/N)$ Optimality Gap in Average-Reward Weakly-Coupled MDPs",
  "title_text": "Achieving an O(1/N) Optimality Gap in Average-Reward Weakly-Coupled MDPs",
  "type": "preprint",
  "updated_at": "2026-10-30T12:25:36Z",
  "url": "https://research.draconitic.com/paper/eb36p2d7as3re",
  "venue": "arXiv",
  "versions": []
}