# Reinforcement Learning for Mean-Field Game
## 3 Proposed Algorithm  
In this section, we propose an algorithm, which will be shown to converge to the mean-field equilibrium (MFE) in the following section. For each agent \(i\), the algorithm begins with a prior distribution \(g\) over the stochastic game with state-space set \(S\) and action space set \(A\) and time horizon \(\tau\). The prior distribution \(g\) for modeling state transition probability distribution is typically taken to be Dirichlet distribution [14; 15]. The game is played episodes \(k=0,1,2,\cdots\). The length of each episode is given by \(\tau\). In each episode, the game is played in discrete steps, \(j=0,1,\cdots,\tau-1\). The episodes begin at times \(t_{k}=k\tau,k=0,1,2,\cdots\). At each time \(t=k\tau+j\), the state of the agent is given by \(s_{t}\), it selects an action \(a_{t}\), and observes a scalar reward \(r_{t}\) then transitions to the state \(s_{t+1}\). Let \(H_{t}=(s_{1},a_{1},r_{1},\ldots,s_{t},a_{t-1},r_{t-1})\) denote the history of the agent till time \(t\). The proposed algorithm is described in Algorithm 1. At the beginning of each episode, the MDP, \(\mathcal{M}_{k}\) is sampled from the posterior distribution conditioned on the history \(H_{t_{k}}\) in Line 4. We note that the sampling of MDP only relates to the sampling of the transition probability \(P\) and the reward distribution since the rest of the parameters are known. We note that the algorithm doesn't perform explicit exploration like an \(\epsilon\)-greedy algorithm. Instead, the algorithm samples a new MDP \(\mathcal{M}_{k}\) for episode \(k\) in Line 4. The Algorithm can generate a new trajectory from the new policy [14; 15] solved for the sampled MDP \(\mathcal{M}_{k}\). We assume that after some samples, \(\alpha_{k}\) has converged. The proposed algorithm converges as the induced transition probability and reward function converge after \(\alpha_{k}\) converge. ```
1:Input: Prior distribution \(g\), time horizon \(\tau\), \(\gamma\)
2:Initialize \(H_{0}=\phi\). 3:for episodes \(k=0,1,2,\cdots\)do
4: Sample \(\mathcal{M}_{k}\sim g(\cdot|H_{k\tau})\). 5: Obtain optimal \(Q\) for \(\mathcal{M}_{k}\) from Algorithm 2
6:for time steps \(j=0,\ldots,\tau-1\)do
7: Play \(a_{j}=\arg\max_{a}Q_{j}(s_{j},a)\). 8: Observe reward \(r_{j}\), action of the agent \(a_{j}\), and next state \(s_{j+1}\). 9: Append action taken \(a_{j}\), reward obtained \(r_{j}\), and state update \(s_{j+1}\) to history \[H_{k\tau+j+1}=H_{k\tau+j}\cup\{a_{j},r_{j},s_{j+1}\}.\]
10:endfor
11:endfor
```  
**Algorithm 1** Proposed Algorithm for Mean-Field Game with Best Response Learning Dynamics. We use Backwards Induction algorithm [25] described in Algorithm 2 to obtain the Q-value function for the current sampled MDP (Line 5, Algorithm 1). Backward induction in Algorithm 2 starts from the end of the episode and calculates the potential maximum rewards for each state and action (Line 5). The algorithm then goes back in the episode (Line 8), to calculate the maximum possible cumulative rewards for each state and action in Line 11. After all the time indices in an episode are covered, the algorithm returns the calculated optimal Q-values. We obtain the policy \(\pi_{k}\) from the calculated Q-values and the policy is not altered in an episode. Recall for a given \(\alpha\), a policy \(\pi\in\mathcal{P}(\alpha)\) if and only if \(\pi_{k}(s,j)\in\arg\max_{a}Q_{\pi_{k,j}}(s,a|\alpha_{j})\) for all \(s\in\mathcal{S}\) and \(j=0,1,\ldots,\tau-1\). Let \(\alpha_{k}\) be the population action distribution in episode \(k\), then the algorithm aims to choose a policy \(\pi_{k}\in\mathcal{P}(\alpha_{k})\). In order to choose the policy \(\pi_{k}\) from the set \(\mathcal{P}(\alpha_{k})\), we use lower myopic learning dynamics, where at each episode we choose the strategy which is the smallest action index in the set \(\mathcal{P}(\alpha_{k})\). ```
1:Input:\(\mathcal{M}=\{\mathcal{S},\mathcal{A},P,\tau,\tau\}\)\(\triangleright\) Sampled MDP from Algorithm 1
2: Initialize \(Q_{l}(s,a)=0\;\forall\;s\in\mathcal{S},a\in\mathcal{A},l\in[\tau]\).