Policy-Regret Minimization in Markov Games with Function Approximation

Thanh Nguyen-Tang, Raman Arora
Proceedings of the 42nd International Conference on Machine Learning, PMLR 267:46242-46264, 2025.

Abstract

We study policy-regret minimization problem in dynamically evolving environments, modeled as Markov games between a learner and a strategic, adaptive opponent. We propose a general algorithmic framework that achieves the optimal $\mathcal{O}(\sqrt{T})$ policy regret for a wide class of large-scale problems characterized by an Eluder-type condition–extending beyond the tabular settings of previous work. Importantly, our framework uncovers a simpler yet powerful algorithmic approach for handling reactive adversaries, demonstrating that leveraging opponent learning in such settings is key to attaining the optimal $\mathcal{O}(\sqrt{T})$ policy regret.

Cite this Paper

BibTeX
@InProceedings{pmlr-v267-nguyen-tang25a, title = {Policy-Regret Minimization in {M}arkov Games with Function Approximation}, author = {Nguyen-Tang, Thanh and Arora, Raman}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, pages = {46242--46264}, year = {2025}, editor = {Singh, Aarti and Fazel, Maryam and Hsu, Daniel and Lacoste-Julien, Simon and Berkenkamp, Felix and Maharaj, Tegan and Wagstaff, Kiri and Zhu, Jerry}, volume = {267}, series = {Proceedings of Machine Learning Research}, month = {13--19 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v267/main/assets/nguyen-tang25a/nguyen-tang25a.pdf}, url = {https://proceedings.mlr.press/v267/nguyen-tang25a.html}, abstract = {We study policy-regret minimization problem in dynamically evolving environments, modeled as Markov games between a learner and a strategic, adaptive opponent. We propose a general algorithmic framework that achieves the optimal $\mathcal{O}(\sqrt{T})$ policy regret for a wide class of large-scale problems characterized by an Eluder-type condition–extending beyond the tabular settings of previous work. Importantly, our framework uncovers a simpler yet powerful algorithmic approach for handling reactive adversaries, demonstrating that leveraging opponent learning in such settings is key to attaining the optimal $\mathcal{O}(\sqrt{T})$ policy regret.} }
Endnote
%0 Conference Paper %T Policy-Regret Minimization in Markov Games with Function Approximation %A Thanh Nguyen-Tang %A Raman Arora %B Proceedings of the 42nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2025 %E Aarti Singh %E Maryam Fazel %E Daniel Hsu %E Simon Lacoste-Julien %E Felix Berkenkamp %E Tegan Maharaj %E Kiri Wagstaff %E Jerry Zhu %F pmlr-v267-nguyen-tang25a %I PMLR %P 46242--46264 %U https://proceedings.mlr.press/v267/nguyen-tang25a.html %V 267 %X We study policy-regret minimization problem in dynamically evolving environments, modeled as Markov games between a learner and a strategic, adaptive opponent. We propose a general algorithmic framework that achieves the optimal $\mathcal{O}(\sqrt{T})$ policy regret for a wide class of large-scale problems characterized by an Eluder-type condition–extending beyond the tabular settings of previous work. Importantly, our framework uncovers a simpler yet powerful algorithmic approach for handling reactive adversaries, demonstrating that leveraging opponent learning in such settings is key to attaining the optimal $\mathcal{O}(\sqrt{T})$ policy regret.
APA
Nguyen-Tang, T. & Arora, R.. (2025). Policy-Regret Minimization in Markov Games with Function Approximation. Proceedings of the 42nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 267:46242-46264 Available from https://proceedings.mlr.press/v267/nguyen-tang25a.html.

Related Material