Zero-sum Markov games arise in a wide variety of sequential decision-making problems such as adversarial learning and planning against modeled uncertainties. However, prior work on finite-sample guarantees on the learned state-action value function (Q-function) for zero-sum Markov games is largely restricted to finite-action settings, or to continuous-action games in which agents have linear dynamics and quadratic rewards (i.e. linear-quadratic, or LQ, games). A central challenge in extending such guarantees to more general continuous-action zero-sum Markov games is that the associated Bellman operator involves a minimax problem that need not admit a tractable saddle-point solution. To this end, we first introduce a class of neural network function approximators for the Q-function that is convex-concave in the players' actions, which guarantees that this minimax problem admits a pure-strategy saddle point. We then study an online variant of fitted Q-iteration employing this function class and establish, to the best of our knowledge, the first finite-sample guarantees for non-LQ zero-sum Markov games with continuous states and actions. Our code can be found at https://github.com/CLeARoboticsLab/QCanPlayThatGame.
Figures & tables
(u~i,v~i)=Oϵ(Qk(si′,⋅,⋅))
yi=r(si,ui,vi)+γQk(si′,u~i,v~i)
Algorithm 1 Online Minimax Fitted Q -Iteration
Figure 1: The TD-style modification of Algorithm 1 trains stably with the partially input convex-concave Q -function architecture. Each curve shows the normalized mean absolute training error δNMAE against iteration k , for n samples per iteration. Solid lines are the mean over 20 random seeds and shaded bands show the min–max spread across seeds. An increase in n yields both lower steady-state error and lower variance.