# Reinforcement Learning for Mean-Field Game
## 4 Convergence Result
### Sampling Does Not Lead to a Gap for Expected Value Function  
In the last subsection, we proved that there exists an optimal oblivious strategy. We will show that the policies generated by Algorithm 2, \(\pi_{k}\), for the sampled system dynamics \(\mathcal{M}_{k}\) in episode \(k\) by Algorithm 1 converges to the optimal oblivious policy \(\tilde{\pi}\). To show the convergence of the policy \(\pi_{k}\) to \(\tilde{\pi}\), we will show that the value function of the optimal oblivious policy \(\pi_{k}\) converges to the optimal value function of the true system dynamics. We will first describe the lemmas that are used to prove the required result. We start by stating the Azuma-Hoeffding Lemma for obtaining confidence intervals. **Lemma 2** (Azuma-Hoeffding Lemma [15]). : _If \(Y_{n}\) is a zero-mean martingale with almost surely bounded increments, \(|Y_{i}-Y_{i-1}|\leq C\), then for any \(\delta\geq 0\) with probability at least \(1-\delta\), \(Y_{n}\leq C\sqrt{2n\log(1/\delta)}\)._  
We also utilize the following result of [15] on any \(\sigma\)-measurable function \(g\). **Lemma 3**. : _If \(f\) is the distribution of \(\mathcal{M}^{*}\) then, for any \(\sigma(H_{t_{k}})\)-measurable function \(g\),_  
\[\mathbf{E}[g(\mathcal{M}^{*})|H_{t_{k}}]=\mathbf{E}[g(\mathcal{M}_{k})|H_{t_{k }}]. \tag{28}\]  
At the start of every episode, each agent samples system dynamics from the posterior distribution given \(H_{t_{k}}\). The following result bounds the difference between the optimal value function learned by the true distribution \(\mathcal{M}^{*}\) function using the optimal policy which is unknown, and the optimal value function achieved by the sampled distribution \(\mathcal{M}_{k}\) from the policy \(\pi_{k}\). Let \(V^{\mathcal{M}_{k}}_{\pi_{k},j}(s|\alpha_{j}))\) be the optimal value function for an oblivious policy \(\pi_{k}(s,j)=\arg\max_{a}Q^{\mathcal{M}_{k}}_{\pi_{k},j}(s,a|\alpha_{l})\) for the sampled system dynamics \(\mathcal{M}_{k}\) chosen form Algorithm 1. Then \(V^{\mathcal{M}_{k}}_{\pi_{k},j}(s|\alpha_{j}))\) converges to the optimal value function, \(V_{\pi^{*},j}(s|\alpha_{j})\), of the true system dynamics \(\mathcal{M}^{*}\) i.e., _for all states \(s\in\mathcal{S}\) as \(k\to\infty\) with probability at least \(1-\delta\),_  
\[V^{\mathcal{M}_{k}}_{\pi_{k},j}(s|\alpha_{j}))-V_{\pi^{*},j}(s|\alpha_{j})\to 0 \tag{29}\]  
Proof. : We note that since the optimal value function is a \(\sigma(H_{k})\)-measurable, we can use Lemma 3 to bound the difference of the optimal value functions of the sampled distribution at episode \(k\) and the true distribution to show that for all states \(s\in\mathcal{S}\),  
\[\mathbb{E}\Big{[}V_{\pi^{*},j}(s|\alpha_{j})-V^{\mathcal{M}_{k}}_{\pi_{k},j}(s |\alpha_{j}))\Big{]}=0 \tag{30}\]  
Note that the length of all episodes is given by \(\tau\) and the support of the reward is \([0,1]\). Therefore for all states \(s\in\mathcal{S}\), we have \(V_{\pi^{*},0}(s|\alpha_{0})-V^{\mathcal{M}_{k}}_{\pi_{k},0}(s|\alpha_{0}))\in[ -\tau,\tau]\). Note that this condition is similar to bounded increments in Azuma-Hoeffding Lemma (Lemma 2). Since \(V_{\pi^{*},0}(s|\alpha_{0})-V^{\mathcal{M}_{k}}_{\pi_{k},0}(s|\alpha_{0})\in [-\tau,\tau]\) is a zero mean martingale with respect to the filtration \(\{H_{k}:k=1,..,m\}\), and satisfies the assumptions of Azuma-Hoeffding Lemma, we obtain the result as in the statement of the Lemma. Also, for all states \(s\in\mathcal{S}\), we have, \(V_{\pi^{*},0}(s|\alpha_{0})-V^{\mathcal{M}_{k}}_{\pi_{k},0}(s|\alpha_{0}))\in [-\tau,\tau]\). So, the difference is a zero-mean martingale and has the bounded increments property. Applying the Azuma-Hoeffding Lemma to the martingale, we have the following result,  
\[\sum_{k=1}^{m}\Big{(}V_{\pi^{*},0}(s|\alpha_{0})-V^{\mathcal{M}_{k}}_{\pi_{k}, 0}(s|\alpha_{0})\Big{)}\leq\tau\sqrt{2m\log(1/\delta)} \tag{31}\]  
For total time \(T\) of the algorithm, we have \(m=T/\tau\).