Learning In Markov Games With Adaptive Adversaries: Policy Regret, Fundamental Barriers, And Efficient Algorithms

Abstract

We study learning in a dynamically evolving environment modeled as a Markov game between a learner and a strategic opponent that can adapt to the learner's strategies. While most existing works in Markov games focus on external regret as the learning objective, external regret becomes inadequate when the adversaries are adaptive. In this work, we focus on *policy regret* -- a counterfactual notion that aims to compete with the return that would have been attained if the learner had followed the best fixed sequence of policy, in hindsight. We show that if the opponent has unbounded memory or if it is non-stationary, then sample-efficient learning is not possible. For memory-bounded and stationary, we show that learning is still statistically hard if the set of feasible strategies for the learner is exponentially large. To guarantee learnability, we introduce a new notion of *consistent* adaptive adversaries, wherein, the adversary responds similarly to similar strategies of the learner.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keynguyentang2024learning

Related papers

• Regret Minimization And Convergence To Equilibria In General-sum Markov Games (2022)0.00
• Online Learning For Uninformed Markov Games: Empirical Nash-value Regret And Non-stationarity Adaptation (2026)0.00
• Online Learning In Unknown Markov Games (2020)0.00
• Dynamic Regret Of Online Markov Decision Processes (2022)0.00
• Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-regret Learning In Markov Games (2022)0.00
• Learning Adversarial Markov Decision Processes With Delayed Feedback (2020)0.00
• Hardness Of Independent Learning And Sparse Equilibrium Computation In Markov Games (2023)0.00
• Adversarially-robust TD Learning With Markovian Data: Finite-time Rates And Fundamental Limits (2025)0.00