Suppose we have a two player, finite horizon, zero sum stochastic game (a.k.a. "competitive MDP"). The game is defined over a finite set of state $S$. At each decision epoch $t\in\{1,\dots,T\}$ (for finite $T$), each player $i\in\{1,2\}$ simultaneously chooses an action $a^i\in{A^i(s)}$, where $s$ is the current state of the game. Player $i$ receives a reward $r^i(s,a^1,a^2)$, and the game then transitions to a new state $s'$ with probability $p(s'\mid s,a^1,a^2)$. Because the game is zero sum, we assume $r^1(s,a^1,a^2)=-r^2(s,a^1,a^2)$ for all $s, a^1,s^2$.

I am much more familiar with standard, single-agent MDPs. Coming from that context, my intuition is to try to write down an extension of Bellman's optimality equations. Something like:

$$ v_t^1(s)=\max_{a^1\in{A^1(s)}}\min_{a^2\in{A^2(s)}}r^1(s,a^1,a^2)+\sum_{s'\in{S}}p(s'\mid s,a^1,a^2)v_{t+1}^1(s) $$

$$ v_t^2(s)=\max_{a^2\in{A^2(s)}}\min_{a^1\in{A^1(s)}}r^2(s,a^1,a^2)+\sum_{s'\in{S}}p(s'\mid s,a^1,a^2)v_{t+1}^2(s) $$ In principle, given boundary conditions $v_T^i(s)$ for $i\in\{1,2\}$ and $s\in{S}$, one could compute $v_t^i(s)$ for all $i$, $s$ and $t$ which would satisfy the two equations above.

My question is: what do the resulting vectors correspond to? Are they value vectors at some kind of equilibrium? Do they in any sense "solve" the game? Or is there something more complicated going on? I hazily think that $v_t^1(s)=-v_t^2(s)$ because the game is zero sum. Is this correct?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.