Metraipolis › archive › dc_91899fccf772

Adaptive Policy Portfolios for Robust Markov Decision Processes — arXiv:2608.17929

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.17929
License (as archived)
CC0-1.0
Archived
2026-10-18T14:28:52.138Z
SHA-256 of the archived text
585d498d80d9a9e6f356bc7d677fc3381587892291704e3527360f957827322f
Stable URL of this page
https://metraipolis.com/documento/dc_91899fccf772

How to cite

Adaptive Policy Portfolios for Robust Markov Decision Processes — arXiv:2608.17929 — arXiv (en), https://arxiv.org/abs/2608.17929 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_91899fccf772 (Metraipolis archive dc_91899fccf772, sha256 585d498d80d9a9e6f356bc7d677fc3381587892291704e3527360f957827322f)
BibTeX
@misc{dc91899fccf772,
  title = {Adaptive Policy Portfolios for Robust Markov Decision Processes — arXiv:2608.17929},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.17929},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_91899fccf772; sha256 585d498d80d9a9e6f356bc7d677fc3381587892291704e3527360f957827322f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.17929. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Robust Markov decision processes optimize one policy against a set of plausible transition functions. This can be conservative when the unknown dynamics are fixed and become partially identifiable after deployment. We study adaptive policy portfolios: finite sets of memoryless randomized policies synthesized offline and paired with a lightweight online selector. Robust regret is a natural measure of portfolio quality: for each plausible environment, it measures the loss of the best portfolio member relative to the policy that would have been optimal had that environment been known. Related regret objectives were studied by Ghavamzadeh et al. (2016) with an emphasis on approximations and relaxations for safe policy improvement. We give a complexity-theoretic account of portfolio certification and synthesis. Certifying a given portfolio is $\forall\mathbb{R}$-complete already for deterministic portfolios in acyclic (s,a)-rectangular RMDPs. Synthesizing a portfolio of unary-bounded size is $\exists\forall\mathbb{R}$-complete for general rational polytopes, even with fixed discount and acyclic dynamics. The single-policy case is already hard, both combinatorially and algebraically. Finally, we present an offline portfolio construction that is amenable to runtime specialization.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-08-19 in cs.AI).
Categorie arXiv: Artificial Intelligence (cs.AI) ; Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2608.17929 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T14:27:54.313Z dalla pagina https://arxiv.org/catchup/cs.AI/2026-08-19?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).