# Reinforcement Learning for Mean-Field Game
## 2 Background
### Value Function, \(Q\) Function and Policy  
We now define a value function for an agent \(i\in[n]\) for oblivious policy \(\pi_{i}\) at \(l\)th time step in an episode as:  
\[V_{i,\pi_{i},l}(s|\alpha_{-,i}) =\text{E}_{p_{i},\pi_{i}}\bigg{[}\sum_{j=1}^{\tau-1}\gamma^{j-l}r _{i,t}|s_{i,l}=s\bigg{]} \tag{7}\] \[=\text{E}_{p_{i},\pi_{i}}\bigg{[}\sum_{j=l}^{\tau-1}\gamma^{j-l} \phi(s_{i,j},a_{i,j},s_{i,j+1})|s_{i,l}=s\bigg{]}. \tag{8}\]  
The expectation in Equation (8) is taken over the actions taken from time step \(l\) and the states visited after time step \(l\) in an episode. We will consider the rest of the definitions from some \(i\)th agent's perspective, \(i\in[n]\), so subscripts \(i\) and \(-i\) will be dropped for brevity. We note that the action space and state space are finite and hence the set of strategies available to the players is also finite. The player adopts the lower myopic best response dynamics to choose the policy. A lower myopic policy selects an action with the lowest index among the actions that maximize the value function. As time proceeds, the strategies and the action distribution converge to the asymptotic equilibrium [10]. Let \(\alpha_{j}^{*}\in[0,1]^{|A|}\) be the limiting population action distribution for \(j\)th time index in episode \(k\). We note that due to the episodic framework, the limiting action distribution depends on the index in an episode. Then, from the definition of limit, for every \(\epsilon>0\) there exist a \(K_{\epsilon}<\infty\) such that for all \(k>K_{\epsilon}\), we have  
\[||\alpha_{k+j}-\alpha_{j}^{*}||_{2}<\epsilon \tag{9}\]  
where \(||.||_{2}\) denotes the \(\ell_{2}\) norm. The value function defined in Equation (8) satisfies the Bellman-property for finite horizon MDPs, given by  
\[V_{\pi,l}(s|\alpha_{l}^{*}) =\mathbf{E}_{\bar{\
u}_{l},\pi_{l}}\left[\sum_{j=l}^{\tau-1}\gamma^{ j-l}r_{ij}|s_{i,l}=s\right] \tag{10}\] \[=\sum_{s^{\prime}\in S}P_{i}(s^{\prime}|s,a,\alpha_{l}^{*})r_{i,l }+\mathbf{E}_{\bar{\
u}_{l},\pi_{l}}\left[\sum_{j=l+1}^{\tau-1}\gamma^{j-l}r_{ ij}=s^{\prime}\right]\] (11) \[=\bar{\
u}_{l}+\gamma\sum_{s^{\prime}\in S}P(s^{\prime}|s,a,\alpha _{l}^{*})V_{\pi,l+1}(s^{\prime}|\alpha_{l+1}^{*}) \tag{12}\]  
where \(\bar{\
u}_{l}=\sum_{s^{\prime}\in S}P(s^{\prime}|s,a,\alpha_{l}^{*})r_{l}\), and \(a=\pi(s,l)\). Similarly, we also define the \(Q\)-function as:  
\[Q_{\pi,l}(s,a|\alpha_{l}^{*})=\bar{r}_{l}+\gamma\sum_{s^{\prime}\in S}P(s^{ \prime}|s,a,\alpha_{l}^{*})V_{\pi,l+1}(s^{\prime}|\alpha_{l+1}^{*}) \tag{13}\]  
We further consider the agents are strategic and hence care only about individual rewards. The goal of each agent is to find an optimal oblivious policy \(\pi^{*}\), such that,  
\[V_{\pi^{*},l}(s|\alpha_{l}^{*})\geq V_{\pi,l}(s|\alpha_{l}^{*})\ \ \forall s\in\mathcal{S},\ \forall l\in[\tau]. \tag{14}\]  
Let \(\alpha^{*}=[\alpha_{0}^{*},\cdots,\alpha_{\tau-1}^{*}]\in[0,1]^{\tau\times| \mathcal{A}|}\), then we can define the optimal oblivious strategy:  
**Definition 2**. : _The set \(\mathcal{P}(\alpha)\) is the set of the optimal oblivious strategies which are chosen from the \(Q\)-function generated by \(\alpha\). In other words, for a given \(\alpha\), a policy \(\bar{\pi}\in\mathcal{P}(\alpha)\) if and only if_  
\[\bar{\pi}(s,l)\in\arg\max_{a}Q_{\pi,l}(s,a|a_{l})\forall s\in S\ l\in[\tau] \tag{15}\]  
Here, the policy \(\bar{\pi}(s,l)\) is used at \(l\)th time index in an episode so that the \(Q\)-value \(Q_{\pi,l}(s)\) is maximized for all states \(s\in\mathcal{S}\). _Note that \(\bar{\pi}(s,l)\) does not depend on the distribution \(\alpha^{*}\) explicitly. Hence, it is an oblivious strategy where each agent takes its decision based on its own observed state only._ Since the reward function is bounded and \(\gamma<1\), the set \(\mathcal{P}(\alpha)\) is always non-empty. However, finding the optimal action is challenging for an oblivious strategy profile. We denote the initial population state distribution denoted by \(f_{0}\).