MARL algorithms for soccer game

A soccer game can be simplified and modeled to be a Markov game by making it a discrete space, two player, zero-sum game. There are many algorithms to train an agent to be a strong player in this kind of setting. What if we change the environment to be a continuous field and make it a team playing against each other? In this project, I first work on the simple two player zero-sum soccer game. With this baseline I move on to the more complicated environment to find a optimized algorithm that can produce a meaningful result.

2.1 Markov Decision Process and Markov Game

Reinforcement Learning can be divided into single agent and multi agent. In SARL there is one agent that acts in a fixed environment. In MARL there are several agents, each with its own objectives acting at the same time. The mathematical framework for SARL is Markov Decision Process. It is defined as $(S, A, T, R, \gamma)$ where $S$ is the set of states, $A$ is the set of Actions, $T: S \times A \to \Delta(S)$ is the transition function, $R: S \times A \to \mathbb{R}$ is the reward, $\gamma \in [0,1)$ is the discount factor. The objective is to find a policy $\pi : S \to \Delta(A)$ maximizing expected discounted return, $\displaystyle \max_{\pi} \mathbb{E}\!\left[\sum_{t=0}^{\infty} \gamma^{t} R(s_t, a_t)\right]$

The mathematical framework for MARL is the Markov Game. It is defined as $(S, \{A_i\}_{i=1}^{n}, T, \{R_i\}_{i=1}^{n}, \gamma)$ where $S$ is the set of states, $A_i$ is the set of Actions for agent $i$, $T: S \times A_1 \times \cdots \times A_n \to \Delta(S)$ is the transition function, $R_i: S \times A_1 \times \cdots \times A_n \to \mathbb{R}$ is the reward for agent $i$, $\gamma \in [0,1)$ is the discount factor. Each agent's objective is to find a policy $\pi_i : S \to \Delta(A_i)$ maximizing its own expected discounted return, $\displaystyle \max_{\pi_i} \mathbb{E}\!\left[\sum_{t=0}^{\infty} \gamma^{t} R_i(s_t, a_{1,t}, \ldots, a_{n,t})\right]$. This expectation depends on every other agent's policy, so no agent can solve it alone.

2.2 Best Response and Markov Perfect Equilibrium

Let $\pi = (\pi_1, \ldots, \pi_n)$ be the joint policy, $\pi_{-i}$ be the policies of every agent other than $i$, and $V_i^{\pi}(s)$ be agent $i$'s expected discounted return starting from state $s$ when all agents follow $\pi$. Two terms need to be defined.

Best Response is one agent's optimal policy against a fixed opponent. $\displaystyle \pi_i^{\text{BR}} \in \arg\max_{\pi_i} V_i^{(\pi_i,\, \pi_{-i})}(s)$. If every other agent's policy is held still, agent $i$ no longer faces a moving environment. This problem becomes an ordinary MDP.

Markov Perfect Equilibrium is a joint policy $\pi^{*}$ in which every agent is a best response to the others at the same time, so that $V_i^{\pi^{*}}(s) \geq V_i^{(\pi_i,\, \pi^{*}_{-i})}(s)$ for every agent $i$, every state $s \in S$, and every alternative policy $\pi_i$. No agent can gain by changing their own policy while the rest stay fixed therefore the joint policy is stable.