Metraipolis › archive › dc_ea73cf20fdc5

Epsilon-Nash Equilibria in History-Dependent SA-MDPs — arXiv:2609.18829

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.18829
License (as archived): CC0-1.0
Archived: 2026-10-15T14:08:41.710Z
SHA-256 of the archived text: 1337231c74f002d34d1e5af207591bf6f82ae6e1a864fe2f01a6ed14629a91dd
Stable URL of this page: https://metraipolis.com/documento/dc_ea73cf20fdc5

How to cite

Epsilon-Nash Equilibria in History-Dependent SA-MDPs — arXiv:2609.18829 — arXiv (en), https://arxiv.org/abs/2609.18829 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ea73cf20fdc5 (Metraipolis archive dc_ea73cf20fdc5, sha256 1337231c74f002d34d1e5af207591bf6f82ae6e1a864fe2f01a6ed14629a91dd)

BibTeX

@misc{dcea73cf20fdc5,
  title = {Epsilon-Nash Equilibria in History-Dependent SA-MDPs — arXiv:2609.18829},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.18829},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ea73cf20fdc5; sha256 1337231c74f002d34d1e5af207591bf6f82ae6e1a864fe2f01a6ed14629a91dd},
  year = {2026}
}

Archived text

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

We study state-adversarial Markov decision processes (SA-MDPs) as games of observation-space attacks: at each step, an agent selects an action from a received observation while an adversary$\unicode{x2014}$who knows the true state the agent is in$\unicode{x2014}$chooses a perturbed observation within a state-dependent proximity set. While existing work focuses on Markovian policies, we develop a solution concept and computational approach for SA-MDPs under history dependence. History dependence can materially change equilibrium outcomes and can force both the agent and the adversary to adapt their strategies. First, we prove the non-existence of universal (agnostic of the initial state distribution) history-dependent equilibrium policies. Our main result presents the first algorithmic route to computing $\epsilon$-approximations of initial-state dependent equilibria. We do so by reducing SA-MDPs to a strategically equivalent constrained zero-sum one-sided partially observable stochastic game. We test our algorithm on small analytically verifiable games and show that it scales to larger, more realistic benchmarks, including Atari Freeway rollouts with a 12-period ahead horizon.

Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-09-17 in cs.GT).
Categorie arXiv: Computer Science and Game Theory (cs.GT) ; Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2609.18829 — 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-15T13:50:52.126Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-09-17?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).