\section{Online Learning of T-MFE}
\label{sec:learning-TMFE-online}
\begin{figure*}[hbt!]
\begin{minipage}{.32\linewidth}
\centering
\includegraphics[width=1\linewidth]{figures/CDF_Algos.pdf}
\caption{TMFE with $c_f=0.1$ }
\label{fig:CDF_Algos}
\end{minipage}\hfill
\begin{minipage}{.32\linewidth}
\centering
\includegraphics[width=1\linewidth]{figures/Algo_CDF.pdf}
\caption{CDF of states for different algorithms: $c_f=0.05$ }
\label{fig:Algos_CDF}
\end{minipage}\hfill
\begin{minipage}{.32\linewidth}
\centering
\includegraphics[width=1\linewidth]{figures/Algo_state_population.pdf}
\caption{Mean states for different algorithms: $c_f=0.05$}
\label{fig:Algos_mean_state}
\end{minipage}\hfill
\begin{minipage}{.32\linewidth}
\centering
\includegraphics[width=1\linewidth]{figures/z_converge_Normal.pdf}
\caption{Convergence of O-TMFQ-Learning: $c_f=0.05.$ }

\label{fig:z_converge}
\end{minipage}\hfill
\begin{minipage}{.32\textwidth}
\centering
\includegraphics[width=1\linewidth]{figures/mean_state.pdf}
\caption{Mean state of O-TMFQ-Learning over time}
\label{fig:mean_state}
\end{minipage}\hfill
\begin{minipage}{.32\linewidth}
\centering
\includegraphics[width=1\linewidth]{figures/CDF_if.pdf}
\caption{CDF of O-TMFQ-Learning}
\label{fig:CDF_OL}
\end{minipage}\hfill
\end{figure*}

The availability of a large number of agents that explore via trembling hand strategies suggests that we can do away with a system simulator via an online algorithm that simply aggregates these concurrently generated samples and computes a new strategy that is then pushed to all agents. Typically, the assumption in such large population scenarios is that the system size is fixed, but any player may leave the system at time step $t$ with probability $\zeta \in (0,1),$ and be immediately replaced by a new agent with random state referred to as a \emph{regeneration event.}

A generic RL approach would require that given the current strategy $\mu_k$ and mean field $z_k,$ we would need to compute the stationary distribution of the model $P_{z_k,\mu_k},$ and set it as the next mean field.  This would preclude learning without a simulator, since running one step in the real world would immediately cause a mean field update to $z_{k+1},$ and induce a new model $P_{z_{k+1},.},$ making the system non-stationary.  

Since our RL algorithms only need a one-step McKean-Vlasov update under each strategy, an online learning approach at time $k$ when the underlying state distribution is $z_k,$ would be to apply $\mu_{k-1}$ to the system, with the resultant state distribution being $z_{k+1}.$  However, we face the issue that the samples obtained pertain to $P_{z_k,\mu_{k-1}},$ whereas the system model is now $P_{z_{k+1},.},$  and so an online sample-based trembling-hand strategy $\mu_{k}$ will lag the current system model by one step.  Fortunately, convergence of the TMFQ-learning approach is robust to this lag, and we present its online version in Algorithm~\ref{algo:ol-Q}.


\begin{algorithm} \label{algo:ol-Q}
	\caption{Online TMFQ-learning Algorithm for T-MFE}
	\begin{algorithmic}[1]
		\STATE Initialize mean field ${z}_0$ and strategy $\mu_{0}$ 

		\FOR {$k= 1, 2, \ldots $}
            \STATE Reset \textit{memory buffer}
		    \FOR {agents $i= 1, 2, \ldots, I$}
		        \STATE Given current state $s^{i}_{k},$ take action $a^{i}_{k} \sim \mu_{k-1}(s^{i}_{k}),$ get reward $r^{i}_{k},$ observe the next state
		        $s^{i}_{k+1}$
		        \STATE Add the sample $(s^{i}_{k}, a^{i}_{k}, r^{i}_{k}, s^{i}_{k+1})$ to the \textit{memory buffer}
		    \ENDFOR
            \STATE Perform TQ-learning on the \textit{memory buffer} to obtain $Q_{{z}_k}$ and ${\mu}_{k} = \pi^{\epsilon}_{Q_{z_k}}$
		\ENDFOR
	\end{algorithmic}
\end{algorithm}


Algorithm \ref{algo:ol-Q} aggregates the samples generated by executing strategy $\mu_{k-1}$ to estimate the TQ-value function, and then passes back $\mu_k$ to the agents.  We note that regeneration of a fraction of players and execution of trembling hand strategies ensures that we have sufficient samples of each state-action pair in the large population regime to ensure that off-policy learning such as TQ-learning on the \textit{memory buffer} converges to the optimal TQ-value function.   In order to characterize the sample complexity of Algorithm \ref{algo:ol-Q}, we employ bounds pertaining to synchronous Q-learning~\citep{even2003learning} using this guarantee that all state-action pairs are sampled a desired number of times.  The PAC result is similar to TMFQ-learning, with accuracy increasing in the number of players, rather than with the number of samples as in Theorem~\ref{thm:TQL-SC}.

\begin{theorem}\label{thm:sync-TQL-SC}
Let Assumption \ref{assump:Lips-R-P} hold. For any $0 \leq \bar{\epsilon}, \bar{\delta} < 1,$ let $k_{0} = k_{0}(\bar{\epsilon})$. In Algorithm \ref{algo:ol-Q}, for each $k \leq k_{0}$, assume that there are a total of $I = I_{0}$ number of players where $I_{0}$ is given as
\begin{align*}
\begin{split}
    I_{0} & = O \Bigg( \frac{|S| |A|}{\epsilon \zeta} \Bigg(\frac{B^{2} V^{2}_{\max}}{\beta^{2} \bar{\epsilon}^{2}} \ln \big( \frac{2 B k_{0}|\mathcal{S}||\mathcal{A}|V_{\max}}{\bar{\delta} \beta \bar{\epsilon}} \big)   \Bigg)^{\frac{1}{w}} \\
    & \quad + \Bigg( \frac{1}{\beta} \ln(\frac{B V_{\max}}{\bar{\epsilon}}) \Bigg)^{\frac{1}{1-w}} \Bigg),
\end{split}
\end{align*}
where $B = \frac{((1-\zeta) 2A)^{k_{0}} (C_{3}\epsilon)}{(1-\zeta) (A-1)}$, $A = \max \{ 1+C_{2}, C_{3}D \}$,  $D = (C_{1} + \gamma C_{2})/(1-\gamma)$, $V_{\max} = 1/(1-\gamma), \beta = (1-\gamma)/2$, $w \in (1/2, 1)$, $\zeta$ is a regeneration probability and $\epsilon$ is the trembling-hand strategy randomization.
Then,
\begin{align*}
    \mathbb{P}(\|z_{k_{0}} - z^{*} \| \leq 2 \bar{\epsilon}) \geq (1 - \bar{\delta}). 
\end{align*}
\end{theorem}
Note that a result similar to that of Corollary \ref{cor:cor-1} can easily be shown here as well under the same assumption. We omit details due to page limitations.
{"config": "arxiv", "file": "2006.11683/06-Online-Learning.tex"}