Stochastic/Markov Game

Stochastic Games generalize MDPs to multiple interacting decision-makers.

Mentioned in F1TENTH Research Proposal.

Formalization

A Markov Game is a tuple $⟨\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma ⟩$

• $\mathcal{S}=S_1\times \cdots \times S_N$ where $S_i$ is a finite set of states for player $i$
• $\mathcal{A}=A_1\times \cdots \times A_N$ where $A_i$ is a finite set of actions for player $i$
• $\mathcal{P}:\mathcal{S}\times \mathcal{A}\to S$ is a state transition probability matrix
• $\mathcal{R}=R_1\times \cdots \times R_N$ is a reward function, where $R_i:\mathcal{S}\times \mathcal{A}\times \mathcal{S}\to \mathbb{R}$
• $\gamma$ is a discount factor, $\gamma \in [0,1]$

Value Function $V_{{\pi }^i,{\pi }^{-i}}^i(s):=\mathbb{E}\left[{\sum }_{t\ge 0}{\gamma }^t{R}^i(s_t,a_t,s_{t+1})\mid a_t^i\sim {\pi }_i(\cdot |s_t),s_0=s\right]$

Nash Equilibrium A Nash Equilibrium of the Markov game $(N,S,\{A^i{\}}_{i\in N},P,\{R^i{\}}_{i\in N},\gamma )$ is a joint policy ${\pi }^{\ast }=({\pi }^{1,\ast },\dots ,{\pi }^{N,\ast })$, such that for any $s\in S$ and $i\in N$ $V_{{\pi }^{i,\ast },{\pi }^{-i,\ast }}^i(s)\ge V_{{\pi }^i,{\pi }^{-i,\ast }}^i(s),\text{ for any }{\pi }_i$

• where $-i$ represents the indices of all agents in N except agent $i$.

Resources

• Turn-based markov game formalization: https://arxiv.org/pdf/2002.10620.pdf