# Reinforcement Learning for Mean-Field Game
## 2 Background  
### Multi-Player Stochastic Game  
An \(n\)-player stochastic game is formalized by the system dynamics tuple \(\mathcal{M}^{*}=\{\mathcal{S},\mathcal{A},P,r,\tau,\rho,\gamma\}\). The agents are indexed by the set \([n]=\{1,2,\cdots,n\}\). The state of the \(i\)th agent at time \(t\) is given by \(s_{i,t}\in\mathcal{S}\), where \(\mathcal{S}\) is the state space set. \(\mathcal{A}(s)\) is defined as the set of the feasible actions any agent can take in state \(s\). \(\mathcal{A}\) is the action space set defined as \(\bigcup_{s\in\mathcal{S}}\mathcal{A}(s)\). We also assume that both \(\mathcal{S}\) and \(\mathcal{A}\) are finite sets. Since finite sets are also compact, the assumption allows us to use results from previous works of [10]. Since we have \(n\) agents in our system, the combined state space of the system becomes \(\mathcal{S}^{\times n}=\mathcal{S}\times\mathcal{S}\times\cdots\times\mathcal{ S}\), and the combined action space of the system becomes \(\mathcal{A}^{\times n}=\mathcal{A}\times\mathcal{A}\times\cdots\times\mathcal{ A}\). Let \(\mathbf{s}_{t}=\mathbf{s}\in\mathcal{S}^{\times n}\) be a vector of length \(n\), and the \(i\)th element of \(\mathbf{s}\) denotes the states of the \(i\)th agent at time \(t\). Similarly, let \(\mathbf{a}_{t}=\mathbf{a}\in\mathcal{A}^{\times n}\) be a vector of length \(n\), and the \(i\)th element of \(\mathbf{s}\) denotes the action taken by the \(i\)th agent at time \(t\).  
If the agents play joint action \(\mathbf{a}_{t}=\mathbf{a}\in\mathcal{A}^{\times n}\) the next state of the system \(\mathbf{s}_{t+1}=\mathbf{s}^{\prime}\in\mathcal{S}^{\times n}\) follows the probability distribution \(P(\mathbf{s}_{t+1}=\mathbf{s}^{\prime}|\mathbf{s}_{t}=\mathbf{s},\mathbf{a}_{t }=\mathbf{a})\). Along with the state updates, \(i\)th agent also receives a reward \(r_{i,t}=R_{i}(\mathbf{s}_{t},\mathbf{a}_{t},\mathbf{s}_{t+1})\in[0,1]\). We further assume that the reward function \(R_{i}(\cdot)\) independent of the agent \(i\), and each player is trying to optimize for the same reward. Hence, we can drop the subscript \(i\) in the reward function \(R_{i}\). However, since each agent can be in different state, or play different action, their individual rewards will be different and we still use the subscript \(i\) to differentiate between the instantaneous reward of the \(i\)th agent. The constant \(\gamma\in[0,1)\) is the discount factor, and \(\rho\) is the initial state distribution such that \(\mathbf{s}_{0}\sim\rho\).  
We consider an episodic framework where the length of the time horizon or the length of episodes is \(\tau\). State space set \(\mathcal{S}\), action space set \(\mathcal{A}\), \(\tau\) are known and need not be learned by the agent. We consider that the game is played in episodes \(k=0,1,2,\cdots\). In each episode, the game is played in discrete steps, \(j\in[\tau]=\{0,1,\cdots,\tau-1\}\). The episodes begin at times \(t_{k}=k\tau,k=0,1,2,\cdots\). At each time \(t\), the state of the agent \(i\) is given by \(s_{i,t}\), the agent selects an action \(a_{i,t}\), agent observes a scalar reward \(r_{i,t}\) and the state transitions to the state \(s_{t+1}\). Let \(H_{i,t}=(s_{i,1},a_{i,1},r_{i,1},\cdots,s_{i,t-1},a_{i,t-1},r_{i,t-1},s_{i,t})\) denote the history available to the agent \(i\) till time \(t\).