Online Markov Decision Processes with Non-oblivious Strategic Adversary

Abstract

We study a novel setting in Online Markov Decision Processes (OMDPs) where the loss function is chosen by a non-oblivious strategic adversary who follows a no-external regret algorithm. In this setting, we first demonstrate that MDP-Expert, an existing algorithm that works well with oblivious adversaries can still apply and achieve a policy regret bound of $\mathcal{O}(\sqrt{T\log (L)}+{\tau }^2\sqrt{T\log (|A|)})$ where $L$ is the size of adversary's pure strategy set and $|A|$ denotes the size of agent's action space. Considering real-world games where the support size of a NE is small, we further propose a new algorithm: MDP-Online Oracle Expert (MDP-OOE), that achieves a policy regret bound of $\mathcal{O}(\sqrt{T\log (L)}+{\tau }^2\sqrt{Tk\log (k)})$ where $k$ depends only on the support size of the NE. MDP-OOE leverages the key benefit of Double Oracle in game theory and thus can solve games with prohibitively large action space. Finally, to better understand the learning dynamics of no-regret methods, under the same setting of no-external regret adversary in OMDPs, we introduce an algorithm that achieves last-round convergence result to a NE. To our best knowledge, this is first work leading to the last iteration result in OMDPs.

arXiv commentAccepted at Autonomous Agents and Multi-Agent Systems (2023)

References in corpus (12)

• Game-Theoretic Multiagent Reinforcement Learning
• Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile
• Online Bandit Learning against an Adaptive Adversary: from Regret to Policy Regret
• On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games
• Last-Iterate Convergence: Zero-Sum Games and Constrained Min-Max Optimization
• Diverse Auto-Curriculum is Critical for Successful Real-World Multiagent Learning Systems
• Real World Games Look Like Spinning Tops
• Online learning in MDPs with linear function approximation and bandit feedback
• Unifying Behavioral and Response Diversity for Open-ended Learning in Zero-sum Games
• Online Reinforcement Learning in Stochastic Games
• Non-Stationary Reinforcement Learning: The Blessing of (More) Optimism
• Online Double Oracle