\section{Proof of Theorem \ref{thm:main}} \label{sec:proof_main}
We first prove \eqref{eqn:reg_exp}. First, since the delays are i.i.d. subexponential random variables, by standard concentration inequality and uniform bound \cite{wainwright2019high}, we have the following lemma:

\begin{lemma}\label{lem:concen_1}
    Let $\left\{\tau_t\right\}_{t=1}^{\infty}$ be i.i.d $(v,b)$  subexponential random variables with expectation $\mathbb{E}[\tau]$. Then we have 
    \begin{equation}
\mathbb{P}\left(\exists t \geq 1: \tau_t \geq \mathbb{E}[\tau]+C_\tau\right) \leq 1-\delta,
\end{equation}
where $C_\tau =\min \left\{\sqrt{2 v^2 \log \left(\frac{3 t}{2 \delta}\right)}, 2 b \log \left(\frac{3 t}{2 \delta}\right)\right\}$
\end{lemma}

Define the good event $G=\{\exists t \geq 1: \tau_t \geq \mathbb{E}[\tau]+C_\tau\}$. By Lemma \ref{lem:concen_1}, the good event happens with probability at least $1-\delta$. Therefore, conditioned on the good event happens, in each batch of the algorithm, we only need to run $\mathbb{E}[\tau]+C_\tau$ episodes and the algorithm can observe enough feedback to finish this batch.

The regret in a batch can be divided into two parts: the first part is the regret caused by running the algorithm in the undelayed environment; the second part is caused by running extra episodes to wait for delayed feedback. The first part can be simply bounded by $\widetilde{\operatorname{Regret}}(K)$. For the second part, since each episode contributes at most $H$ regret, the total regret can be bounded by

\begin{equation}
        \operatorname{Regret}(K)\leq \widetilde{\operatorname{Regret}}(K) +  H N_b \left(\mathbb{E}[\tau]+C_\tau\right).
\end{equation}

For the second inequality, we have the following lemma which reveals the relation between the number of observed feedback and the actual number of episodes using quantile function.

\begin{lemma}\label{lem:concen_2}
At time $t$, Assume that the total number of episodes is $n_t$, and the number of observed feedback is $m_t$, for any quantile $q$ we have
\begin{equation}
\operatorname{Pr}\left[n_{t+d_{\tau}(q)}<\frac{q}{2} m_t\right] \leq \exp \left(-\frac{q}{8} m_t\right) .
\end{equation}
\end{lemma}

\begin{proof}
Define $\mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\}$ to be an indicator that on time $s$ that the delay is smaller than $d_{\tau}(q)$. Note that  $\mathbb{E}\left[\mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\} \right] \geq q$. Thus,
\begin{equation}
\begin{aligned}
\operatorname{Pr}\left[n_{t+d_{\tau}(q)}<\frac{q}{2} m_t\right] & \leq \operatorname{Pr}\left[\sum_{s=1}^{t} \mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\}<\frac{q}{2} m_t\right] \\
& \leq \operatorname{Pr}\left[\sum_{s=1}^{t} \mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\}<\frac{1}{2} \sum_{s=1}^{t} \mathbb{E}\left[\mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\} \right]\right] \\
& \leq \exp \left(-\frac{1}{8} \sum_{s=1}^{t} \mathbb{E}\left[\mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\}\right]\right) \leq \exp \left(-\frac{q}{8} m_t\right),
\end{aligned}
\end{equation}
where the third inequality follows from the relative Chernoff bound, and the last inequality is since
$\sum_{s=1}^{t} \mathbb{E}\left[\mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\} \right] \geq q \cdot m_t$.
\end{proof}

Lemma \ref{lem:concen_2} means, if the length of a batch $m$ is larger than $\frac{\log K}{q}$, then with high probability, if we run the batch for $\frac{m}{q}+d_{\tau}(q)$ episodes, we will observe $m$ feedbacks, which is enough for the algorithm to finish the batch. On the other hand, if the length of a batch is smaller than $\frac{\log K}{q}$, then the regret of this batch can be trivially bounded by $\frac{H\log }{q}$. Hence the total regret can be bounded by
\begin{equation}
        \operatorname{Regret}(K)\leq \frac{1}{q}\widetilde{\operatorname{Regret}}(K) + \frac{2H N_b \log K}{q} +  H N_b d_{\tau}(q) ,
\end{equation}
which finishes the proof.


\input{detail.tex}

\section{Proofs for Tabular Markov Games}\label{sec:proof_tab}
\subsection{Multi-batched Optimistic Nash-VI}
\begin{algorithm}
    \caption{Multi-batched Algorithm for Tabular Markov Game}\label{alg:tab_game}
    \begin{algorithmic}[1]
    \STATE {\bfseries Initialize:} for any $(s, a, b, h), \bar{Q}_h(s, a, b) \leftarrow H$, $\underline{Q}_h(s, a, b) \leftarrow 0, \Delta \leftarrow H, N_h(s, a, b) \leftarrow 0$, trigger set $\mathcal{L} \leftarrow\left\{2^{i-1} \mid 2^i \leq K H, i=1,2, \ldots\right\}$
    \FOR{episode $k = 1, 2, \cdots, K$}
    \IF{there exists $(h,s,a,b)$ such that $N_h^k(s,a,b) \in \mathcal{L}$}
    \FOR{step $h=H,H-1,...,1$}
    \FOR{$(s,a,b)\in \mathcal{S}\times\mathcal{A}\times\mathcal{B}$}
    \STATE $t \leftarrow N_h^k(s,a,b)$
    \IF{$t>0$}
    \STATE $\beta_h^k \leftarrow \operatorname{BONUS}\left(t, \widehat{\mathbb{V}}_h\left[\left(\bar{V}_{h+1}+\underline{V}_{h+1}\right) / 2\right](s, a, b)\right)$
    \STATE $\gamma_h^k \leftarrow(c / H) \widehat{\mathbb{P}}_h\left(\bar{V}_{h+1}-\underline{V}_{h+1}\right)(s, a, b)$
    \STATE $\bar{Q}_h^k(s, a, b) \leftarrow \min \left\{\left(r_h+\widehat{\mathbb{P}}_h \bar{V}_{h+1}\right)(s, a, b)+\gamma_h^k+\beta_h^k, H\right\}$
    \STATE $\underline{Q}_h^k(s, a, b) \leftarrow \max \left\{\left(r_h+\widehat{\mathbb{P}}_h \underline{V}_{h+1}\right)(s, a, b)-\gamma_h^k-\beta_h^k, 0\right\}$
    \ENDIF
    \ENDFOR
    \FOR{$s\in\mathcal{S}$}
    \STATE  $\pi_h^k(\cdot, \cdot \mid s) \leftarrow \operatorname{CCE}\left(\bar{Q}_h(s, \cdot, \cdot), \underline{Q}_h(s, \cdot, \cdot)\right)$
    \STATE $\bar{V}_h(s) \leftarrow\left(\mathbb{E}_{\pi_h} \bar{Q}_h\right)(s) ; \quad \underline{V}_h(s) \leftarrow\left(\mathbb{E}_{\pi_h} \underline{Q}_h\right)(s)$
    \ENDFOR
    \ENDFOR
    \ENDIF
    \FOR{step $h=1,...,H$}
    \STATE take action $\left(a_h, b_h\right) \sim \pi_h^{\Tilde{k}}\left(\cdot, \cdot \mid s_h\right)$, observe reward $r_h$ and next state $s_{h+1}$.
    \STATE add 1 to $N_h^k\left(s_h, a_h, b_h\right) $ and $N_h^k\left(s_h, a_h, b_h, s_{h+1}\right)$.
    \STATE $\widehat{\mathbb{P}}_h\left(\cdot \mid s_h, a_h, b_h\right) \leftarrow N_h^k\left(s_h, a_h, b_h, \cdot\right) / N_h^k\left(s_h, a_h, b_h\right)$
    \ENDFOR
    \ENDFOR
    \end{algorithmic}
\end{algorithm}
In this part, we list some of the important lemmas for the tabular Markov game algorithm, most of which are proven in the previous literature \cite{liu2021sharp}. These lemmas are very useful for proving the regret bound in our main theorem.

We denote $V^k, Q^k, \pi^k, \mu^k$ and $\nu^k{ }^4$ for values and policies at the beginning of the $k$-th episode. In particular, $N_h^k(s, a, b)$ is the number we have visited the state-action tuple $(s, a, b)$ at the $h$-th step before the $k$-th episode. $N_h^k\left(s, a, b, s^{\prime}\right)$ is defined by the same token. Using this notation, we can further define the empirical transition by $\widehat{\mathbb{P}}_h^k\left(s^{\prime} \mid s, a, b\right):=N_h^k\left(s, a, b, s^{\prime}\right) / N_h^k(s, a, b)$. If $N_h^k(s, a, b)=0$, we set $\widehat{\mathbb{P}}_h^k\left(s^{\prime} \mid s, a, b\right)=1 / S$.

We define the empirical variance operator
\begin{equation}
\widehat{\mathbb{V}}_h^k V(s, a, b):=\operatorname{Var}_{s^{\prime} \sim \widehat{\mathbb{P}}_h^k(\cdot \mid s, a, b)} V\left(s^{\prime}\right)
\end{equation}
and true variance operator
\begin{equation}
\mathbb{V}_h^k V(s, a, b):=\operatorname{Var}_{s^{\prime} \sim \mathbb{P}_h^k(\cdot \mid s, a, b)} V\left(s^{\prime}\right).
\end{equation}
The bonus terms can be written as
\begin{equation}
    b_h^k(s,a,b)=\beta_h^k(s, a, b)+\gamma_h^k(s, a, b)
\end{equation}
where
\begin{equation}\label{eqn:bonus1}
\beta_h^k(s, a, b):=C\left(\sqrt{\frac{\widehat{\boldsymbol{V}}_h^k\left[\left(\bar{V}_{h+1}^k+\underline{V}_{h+1}^k\right) / 2\right](s, a, b)}{\max \left\{N_h^k(s, a, b), 1\right\}}}+\frac{H^2 S \iota}{\max \left\{N_h^k(s, a, b), 1\right\}}\right)
\end{equation}
and the lower-order term
\begin{equation}\label{eqn:bonus2}
\gamma_h^k(s, a, b):=\frac{C}{H} \widehat{\mathbb{P}}_h\left(\bar{V}_{h+1}^k-\underline{V}_{h+1}^k\right)(s, a, b)
\end{equation}
for some absolute constant $C > 0$.

The following lemma is standard concentration result.
\begin{lemma}[Lemma 21, \citet{liu2021sharp}]
Let $c_1$ be some large absolute constant. Define event $E_1$ to be: for all $h, s, a, b, s^{\prime}$ and $k \in[K]$,
\begin{equation}
\left\{\begin{array}{l}
\left|\left[\left(\widehat{\mathbb{P}}_h^k-\mathbb{P}_h\right) V_{h+1}^{\star}\right](s, a, b)\right| \leq c_1\left(\sqrt{\frac{\widehat{\mathbb{V}}_h^k V_{h+1}^{\star}(s, a, b) \iota}{\max \left\{N_h^k(s, a, b), 1\right\}}}+\frac{H \iota}{\max \left\{N_h^k(s, a, b), 1\right\}}\right) \\
\left|\left(\widehat{\mathbb{P}}_h^k-\mathbb{P}_h\right)\left(s^{\prime} \mid s, a, b\right)\right| \leq c_1\left(\sqrt{\frac{\min \left\{\mathbb{P}_h\left(s^{\prime} \mid s, a, b\right), \widehat{\mathbb{P}}_h^k\left(s^{\prime} \mid s, a, b\right)\right\} \iota}{\max \left\{N_h^k(s, a, b), 1\right\}}}+\frac{\iota}{\max \left\{N_h^k(s, a, b), 1\right\}}\right) \\
\left\|\left(\widehat{\mathbb{P}}_h^k-\mathbb{P}_h\right)(\cdot \mid s, a, b)\right\|_1 \leq c_1 \sqrt{\frac{S \iota}{\max \left\{N_h^k(s, a, b), 1\right\}}} .
\end{array}\right.
\end{equation}
We have $\mathbb{P}\left(E_1\right) \geq 1-p$.
\end{lemma}

The following lemma shows the upper and lower bounds are indeed upper and lower bounds of the best responses.

\begin{lemma}[Lemma 22, \citet{liu2021sharp}]
    Suppose event $E_1$ holds. Then for all $h, s, a, b$ and $k \in[K]$, we have
    \begin{equation}
\left\{\begin{array}{l}
\bar{Q}_h^k(s, a, b) \geq Q_h^{\dagger, \nu^k}(s, a, b) \geq Q_h^{\mu^k, \dagger}(s, a, b) \geq \underline{Q}_h^k(s, a, b), \\
\bar{V}_h^k(s) \geq V_h^{\dagger, \nu^k}(s) \geq V_h^{\mu^k, \dagger}(s) \geq \underline{V}_h^k(s) .
\end{array}\right.
\end{equation}
\end{lemma}

\begin{lemma}[Lemma 23, \citet{liu2021sharp}]\label{lem:liu23}
Suppose event $E_1$ holds. Then for all $h, s, a, b$ and $k \in[K]$, we have
    \begin{equation}
\begin{aligned}
& \left|\widehat{\mathbb{V}}_h^k\left[\left(\bar{V}_{h+1}^k+\underline{V}_{h+1}^k\right) / 2\right]-\mathbb{V}_h V_{h+1}^{\pi^k}\right|(s, a, b) \\
\leq & 4 H \mathbb{P}_h\left(\bar{V}_{h+1}^k-\underline{V}_{h+1}^k\right)(s, a, b)+O\left(1+\frac{H^4 S \iota}{\max \left\{N_h^k(s, a, b), 1\right\}}\right) .
\end{aligned}
\end{equation}
\end{lemma}

\begin{proof}[Proof of Theorem \ref{thm:tab_game}]
Suppose event $E_1$ happens. We define
\begin{equation}
\left\{\begin{array}{l}
\Delta_h^k:=\left(\bar{V}_h^k-\underline{V}_h^k\right)\left(s_h^k\right) \\
\zeta_h^k:=\Delta_h^k-\left(\bar{Q}_h^k-\underline{Q}_h^k\right)\left(s_h^k, a_h^k, b_h^k\right) \\
\xi_h^k:=\mathbb{P}_h\left(\bar{V}_{h+1}^k-\underline{V}_{h+1}^k\right)\left(s_h^k, a_h^k, b_h^k\right)-\Delta_{h+1}^k .
\end{array}\right.
\end{equation}

Using standard decomposition techniques we have
\begin{equation}
\begin{aligned}
\Delta_h^k & =\zeta_h^k+\left(\bar{Q}_h^k-\underline{Q}_h^k\right)\left(s_h^k, a_h^k, b_h^k\right) \\
& \leq \zeta_h^k+2 \beta_h^k+2 \gamma_h^k+\widehat{\mathbb{P}}_h^k\left(\bar{V}_{h+1}^k-\underline{V}_{h+1}^k\right)\left(s_h^k, a_h^k, b_h^k\right) \\
& {\leq} \zeta_h^k+2 \beta_h^k+2 \gamma_h^k+\mathbb{P}_h\left(\bar{V}_{h+1}^k-\underline{V}_{h+1}^k\right)\left(s_h^k, a_h^k, b_h^k\right)+c_2\left(\frac{\mathbb{P}_h\left(\bar{V}_{h+1}^k-\underline{V}_{h+1}^k\right)\left(s_h^k, a_h^k, b_h^k\right)}{H}+\frac{H^2 S \iota}{\max \left\{N_h^k, 1\right\}}\right) \\
& {\leq} \zeta_h^k+2 \beta_h^k+\mathbb{P}_h\left(\bar{V}_{h+1}^k-\underline{V}_{h+1}^k\right)\left(s_h^k, a_h^k, b_h^k\right)+2 c_2 C\left(\frac{\mathbb{P}_h\left(\bar{V}_{h+1}^k-\underline{V}_{h+1}^k\right)\left(s_h^k, a_h^k, b_h^k\right)}{H}+\frac{H^2 S \iota}{\max \left\{N_h^k, 1\right\}}\right) \\
& \leq \zeta_h^k+\left(1+\frac{c_3}{H}\right) \mathbb{P}_h\left(\bar{V}_{h+1}^k-\underline{V}_{h+1}^k\right)\left(s_h^k, a_h^k, b_h^k\right) \\
& \quad+4 c_2 C\left(\sqrt{\frac{\iota \widehat{\mathbb{V}}_h^k\left[\left(\bar{V}_{h+1}^k+\underline{V}_{h+1}^k\right) / 2\right]\left(s_h^k, a_h^k, b_h^k\right)}{\max \left\{N_h^k\left(s_h^k, a_h^k, b_h^k\right), 1\right\}}}+\frac{H^2 S \iota}{\max \left\{N_h^k\left(s_h^k, a_h^k, b_h^k\right), 1\right\}}\right).
\end{aligned}
\end{equation}

By Lemma \ref{lem:liu23}, 
\begin{equation}
\begin{aligned}
& \sqrt{\frac{\iota \widehat{\mathbb{V}}_h^k\left[\left(\bar{V}_{h+1}^k+\underline{V}_{h+1}^k\right) / 2\right](s, a, b)}{\max \left\{N_h^k(s, a, b), 1\right\}}} \\
\leq & \left(\sqrt{\frac{\iota \mathbb{V}_h V_{h+1}^{\pi^k}(s, a, b)+\iota}{\max \left\{N_h^k(s, a, b), 1\right\}}}+\sqrt{\frac{H \iota \mathbb{P}_h\left(\bar{V}_{h+1}^k-\underline{V}_{h+1}^k\right)(s, a, b)}{\max \left\{N_h^k(s, a, b), 1\right\}}}+\frac{H^2 \sqrt{S} \iota}{\max \left\{N_h^k(s, a, b), 1\right\}}\right) \\
\leq & c_4\left(\sqrt{\frac{\iota \mathbb{V}_h V_{h+1}^{\pi^k}(s, a, b)+\iota}{\max \left\{N_h^k(s, a, b), 1\right\}}}+\frac{\mathbb{P}_h\left(\bar{V}_{h+1}^k-\underline{V}_{h+1}^k\right)(s, a, b)}{H}+\frac{H^2 \sqrt{S} \iota}{\max \left\{N_h^k(s, a, b), 1\right\}}\right),
\end{aligned}
\end{equation}
where $c_4$ is some absolute constant. Define $c_5:=4 c_2 c_4 C+c_3$ and $\kappa:=1+c_5 / H$. Now we have
\begin{equation}
\left.\Delta_h^k \leq \kappa \Delta_{h+1}^k+\kappa \xi_h^k+\zeta_h^k+O\left(\sqrt{\frac{\iota \mathbb{V}_h V_{h+1}^{\pi^k}\left(s_h^k, a_h^k, b_h^k\right)}{N_h^k\left(s_h^k, a_h^k, b_h^k\right)}}+\sqrt{\frac{\iota}{N_h^k\left(s_h^k, a_h^k, b_h^k\right)}}+\frac{H^2 S \iota}{N_h^k\left(s_h^k, a_h^k, b_h^k\right)}\right)\right\}.
\end{equation}
Recursing this argument for $h\in [H]$ and summing over $k$,
\begin{equation}
\sum_{k=1}^K \Delta_1^k \leq \sum_{k=1}^K \sum_{h=1}^H\left[\kappa^{h-1} \zeta_h^k+\kappa^h \xi_h^k+O\left(\sqrt{\frac{\iota \mathbb{V}_h V_{h+1}^{\pi^k}\left(s_h^k, a_h^k, b_h^k\right)}{\max \left\{N_h^k, 1\right\}}}+\sqrt{\frac{\iota}{\max \left\{N_h^k, 1\right\}}}+\frac{H^2 S \iota}{\max \left\{N_h^k, 1\right\}}\right)\right].
\end{equation}
It is easy to check that $\{\zeta_h^k\}$ and $\{\xi_h^k\}$ are martingales. By Azuma-Hoeffding inequality, with probability at least $1-p$,
\begin{equation}
\left\{\begin{array}{l}
\sum_{k=1}^K \sum_{h=1}^H \kappa^{h-1} \zeta_h^k \leq O(H \sqrt{H K \iota}) \\
\sum_{k=1}^K \sum_{h=1}^H \kappa^h \xi_h^k \leq O(H \sqrt{H K \iota}).
\end{array}\right.
\end{equation}

Now we deal with the rest terms. Note that under the doubling epoch update framework, despite those episodes in which an update is triggered, the number of visits of $(s, a)$ between the $i$-th update of $\hat{P}_{s, a}$ and the $i+1$-th update of $\hat{P}_{s, a}$ do not exceeds $2^{i-1}$. 

We define $i_{\max }=\max \left\{i \mid 2^{i-1} \leq K H\right\}=\left\lfloor\log _2(K H)\right\rfloor+1$. To facilitate the analysis, we first derive a general deterministic result. Let $\mathcal{K}$ be the set of indexes of episodes in which no update is triggered. By the update rule we have $\left|\mathcal{K}^C\right| \leq S A\left(\log _2(K H)+1\right)$. Let $h_0(k)$ be the first time an update is triggered in the $k$-th episode if there is an update in this episode and otherwise $H + 1$. Define $\mathcal{X}=\left\{(k, h) \mid k \in \mathcal{K}^C, h_0(k)+1 \leq h \leq H\right\}$.

Let $w=\left\{w_h^k \geq 0 \mid 1 \leq h \leq H, 1 \leq k \leq K\right\}$ be a group of non-negative weights such that $w_h^k \leq 1$ for any $(k, h) \in[H] \times[K]$ and $w_h^k=0$ for any $(k, h) \in \mathcal{X}$. As in \citet{zhang2021reinforcement}, We can calculate

\begin{equation}
\begin{aligned}
&\sum_{k=1}^K \sum_{h=1}^H \sqrt{\frac{w_h^k}{N_h^k\left(s_h^k, a_h^k\right)}} \\
& \leq \sum_{k=1}^K \sum_{h=1}^H \sum_{s, a} \sum_{i=3}^{i_{\max }} \mathbb{I}\left[\left(s_h^k, a_h^k\right)=(s, a), N_h^k(s, a)=2^{i-1}\right] \sqrt{\frac{w_h^k}{2^{i-1}}}+8 S A\left(\log _2(K H)+4\right) \\
& =\sum_{s, a} \sum_{i=3}^{i_{\max }} \frac{1}{\sqrt{2^{i-1}}} \sum_{k=1}^K \sum_{h=1}^H \mathbb{I}\left[\left(s_h^k, a_h^k\right)=(s, a), N_h^k(s, a)=2^{i-1}\right] \sqrt{w_h^k}+8 S A\left(\log _2(K H)+4\right) \\
& \leq \sum_{s, a} \sum_{i=3}^{i_{\max }} \sqrt{\frac{\sum_{k=1}^K \sum_{h=1}^H \mathbb{I}\left[\left(s_h^k, a_h^k\right)=(s, a), N_h^k(s, a)=2^{i-1}\right]}{2^{i-1}}} . \\
& \sqrt{\left(\sum_{k=1}^K \sum_{h=1}^H \mathbb{I}\left[\left(s_h^k, a_h^k\right)=(s, a), N_h^k(s, a)=2^{i-1}\right] w_h^k\right)}+8 S A\left(\log _2(K H)+4\right) \\
& \leq \sqrt{S A i_{\max } \sum_{k=1}^K \sum_{h=1}^H w_h^k}+8 S A\left(\log _2(K H)+4\right) . 
\end{aligned}
\end{equation}
By plugging $w_h^k= \mathbb{V}_h V_{h+1}^{\pi^k}\left(s_h^k, a_h^k, b_h^k\right)\mathbb{I}[(k, h) \notin \mathcal{X}]$ and $w_h^k= \mathbb{I}[(k, h) \notin \mathcal{X}]$ we have
\begin{equation}
\begin{aligned}
&\sum_{k=1}^K \sum_{h=1}^H\left[O\left(\sqrt{\frac{\iota \mathbb{V}_h V_{h+1}^{\pi^k}\left(s_h^k, a_h^k, b_h^k\right)}{\max \left\{N_h^k, 1\right\}}}+\sqrt{\frac{\iota}{\max \left\{N_h^k, 1\right\}}}+\frac{H^2 S \iota}{\max \left\{N_h^k, 1\right\}}\right)\right] \\
& \leq O\left(\sqrt{S A i_{\max } \iota \sum_{k=1}^K \sum_{h=1}^H \mathbb{V}_h V_{h+1}^{\pi^k}\left(s_h^k, a_h^k, b_h^k\right) \mathbb{I}[(k, h) \notin \mathcal{X}]}+\sqrt{S A i_{\max } \sum_{k=1}^K \sum_{h=1}^H  \mathbb{I}[(k, h) \notin \mathcal{X}] \iota}+S^2 A \iota \log _2(K H)\right)+\left|\mathcal{K}^C\right| \\
& \leq O\left(\sqrt{S A i_{\max } \iota \sum_{k=1}^K \sum_{h=1}^H \mathbb{V}_h V_{h+1}^{\pi^k}\left(s_h^k, a_h^k, b_h^k\right) \mathbb{I}[(k, h) \notin \mathcal{X}]}+\sqrt{S A i_{\max } K \iota}+S^2 A \iota \log _2(K H)\right)+\left|\mathcal{K}^C\right|
\end{aligned}
\end{equation}
By the Law of total variation and standard martingale concentration (see Lemma C.5 in \citet{jin2018q} for a formal proof), with probability at least $1-p$, we have
\begin{equation}
\sum_{k=1}^K \sum_{h=1}^H \mathbb{V}_h V_{h+1}^{\pi^k}\left(s_h^k, a_h^k, b_h^k\right) \leq O\left(H^2 K +H^3 \iota\right).
\end{equation}
By Pigeon-hole argument, 
\begin{equation}
\sum_{k=1}^K \sum_{h=1}^H \frac{1}{\sqrt{\max \left\{N_h^k, 1\right\}}} \leq \sum_{s, a, b, h: N_h^K(s, a, b)>0} \sum_{n=1}^{N_h^K(s, a, b)} \frac{1}{\sqrt{n}}+H S A B \leq O(\sqrt{H^2 S A B K}+H S A B)
\end{equation}
\begin{equation}
\sum_{k=1}^K \sum_{h=1}^H \frac{1}{\max \left\{N_h^k, 1\right\}} \leq \sum_{s, a, b, h: N_h^K(s, a, b)>0} \sum_{n=1}^{N_h^K(s, a, b)} \frac{1}{n}+H S A B \leq O(H S A B \iota) .
\end{equation}

Putting all relations together, we obtain that
\begin{equation}
\operatorname{Regret}(K)=\sum_{k=1}^K\left(V_1^{\dagger}, \nu^k-V_1^{\mu^k, \dagger}\right)\left(s_1\right) \leq O\left(\sqrt{H^3 S A B K \iota}+H^3 S^2 A B \iota^2\right)
\end{equation}
which completes the proof.
\end{proof}








\subsection{Multi-batched Algorithms for Linear Markov Games} \label{sec:proof_lin}
\begin{algorithm}[H]
    \caption{Multi-batched Algorithm for Linear Markov Games}\label{alg:lin_game}
    \begin{algorithmic}[1]
    \STATE {\bfseries Require:} regularization parameter $\lambda$
    \STATE {\bfseries Initialize:} $\Lambda_h = \Lambda_h^0 = \lambda I_d$
    \FOR{episode $k = 1, 2, \cdots, K$}
    \STATE $\Lambda_h^k = \sum_{\tau = 1}^{k - 1} \phi(s_h^\tau, a_h^\tau, b_h^\tau) \phi(s_h^\tau, a_h^\tau,b _h^\tau)^\top + \lambda I_d$
    \ENDFOR
    \IF{$\exists  h \in [H]$, $\det(\Lambda_h^k) > \eta \cdot \det(\Lambda_h)$}
    \STATE $\bar{V}_{H+1}^k \leftarrow 0$, $\underline{V}_{H+1}^k \leftarrow 0$
    \FOR{step $h = H, H - 1, \cdots, 1$}
    \STATE $\Lambda_h \leftarrow \Lambda_h^k$
    \STATE $\bar{w}_h^k \leftarrow (\Lambda_h^k)^{-1} \sum_{\tau = 1}^{k - 1} \phi(s_h^\tau, a_h^\tau, b_h^\tau) \cdot [r_h(s_h^\tau, a_h^\tau, b_h^\tau) + \bar{V}_{h+1}^k(s_{h+1}^\tau)]$
    \STATE $\underline{w}_h^k \leftarrow (\Lambda_h^k)^{-1} \sum_{\tau = 1}^{k - 1} \phi(s_h^\tau, a_h^\tau, b_h^\tau) \cdot [r_h(s_h^\tau, a_h^\tau, b_h^\tau) + \underline{V}_{h+1}^k(s_{h+1}^\tau)]$
    \STATE $\Gamma_h^k(\cdot, \cdot, \cdot) \leftarrow \beta \sqrt{\phi(\cdot, \cdot, \cdot)^\top (\Lambda_h^k)^{-1} \phi(\cdot, \cdot, \cdot)}$
    \STATE $\bar{Q}_h^k(\cdot, \cdot, \cdot) \leftarrow \Pi_{H}\{(\bar{w}_h^k)^\top \phi(\cdot, \cdot, \cdot) + \Gamma_h^k(\cdot, \cdot, \cdot)\}$
    \STATE $\underline{Q}_h^k(\cdot, \cdot, \cdot) \leftarrow \Pi_{H}\{(\underline{w}_h^k)^\top \phi(\cdot, \cdot, \cdot) - \Gamma_h^k(\cdot, \cdot, \cdot)\}$
    \STATE For each $s$, let $\pi_h^k(x) \leftarrow \mathrm{FIND\_CCE}(\bar{Q}_h^k, \underline{Q}_h^k, s)$ (cf. Algorithm~2 in \citet{xie2020learning})
    \STATE $\bar{V}_{h}^{k}(s) \leftarrow \mathbb{E}_{(a, b) \sim \pi_{h}^{k}(s)} \bar{Q}_{h}^{k}(s, a, b)$ for each $s$
    \STATE $\underline{V}_{h}^{k}(s) \leftarrow \mathbb{E}_{(a, b) \sim \pi_{h}^{k}(s)} \underline{Q}_{h}^{k}(s, a, b)$ for each $s$
    \ENDFOR
    \ELSE 
    \STATE $\bar{Q}_h^k \leftarrow \bar{Q}_h^{k-1}$,  $\underline{Q}_h^k \leftarrow \underline{Q}_h^{k-1}$, $\pi_h^k \leftarrow \pi_h^{k-1}$, $\forall h \in [H]$  
    \ENDIF
    \end{algorithmic}
\end{algorithm}





\begin{proof}[Proof of Theorem \ref{thm:linear:mg:switching}]
Let $\{k_1, \cdots, k_{N_{\mathrm{batch}}}\}$ be the episodes where the learner updates the policies. Moreover, we define $b_k = \max \{k_i: i \in [N_{\mathrm{batch}}], k_i \le k \}$. Moreover, we denote the marginals of $\pi_h^k$ as $\mu_h^k$ and $\nu_h^k$.

\paragraph{Part 1: Upper bound of the batch number.}
    By the updating rule, we know there exists one $h \in [H]$ such that $\det(\Lambda_h^{k_i}) > \eta \cdot \det(\Lambda_h^{k_{i-1}})$, which further implies that
    \begin{align*}
        \prod_{h = 1}^{H} \det(\Lambda_h^{k_i}) > \eta \cdot \prod_{h = 1}^{H} \det(\Lambda_h^{k_{i-1}}) .
    \end{align*}
    This yields that 
    \begin{align} \label{eq:171}
        \prod_{h = 1}^{H} \det(\Lambda_h^{k_{N_{\mathrm{batch}}}}) > \eta^{{N_{\mathrm{batch}}}} \cdot \prod_{h = 1}^{H} \det(\Lambda_h^{0}) =  \eta^{{N_{\mathrm{batch}}}} \cdot \lambda^{dH}.
    \end{align}
    On the other hand, for any $h \in [H]$, we have
    \begin{align} \label{eq:172}
        \prod_{h = 1}^{H} \det(\Lambda_h^{k_{N_{\mathrm{batch}}}}) \le \prod_{h = 1}^{H} \det(\Lambda_h^{K+1}).
    \end{align}
    Furthermore, by the fact that $\|\phi(\cdot, \cdot)\|_2 \le 1$, we have
    \begin{align*}
        \Lambda_h^{K+1} = \sum_{k = 1}^{K} \phi(s_h^k, a_h^k, b_h^k) \phi(s_h^k, a_h^k, b_h^k)^\top + \lambda I_d \preceq (K + \lambda) \cdot I_d,
    \end{align*}
    which implies that 
    \begin{align} \label{eq:173}
        \prod_{h = 1}^H \det(\Lambda_h^{K+1}) \le (K + \lambda)^{dH} .
    \end{align}
    Combining \eqref{eq:171}, \eqref{eq:172}, and \eqref{eq:173}, we obtain that
    \begin{align*}
        N_{\mathrm{batch}} \le \frac{dH}{\log \eta} \log\Big(1 + \frac{K}{\lambda}\Big) ,
    \end{align*}
    which concludes the first part of the proof.

\paragraph{Part2: Regret.} We need the following two lemmas to bound the regret.

\begin{lemma} \label{lemma:linear:optimism}
    For any $(s, a, b, k, h)$, it holds that
    \begin{align*}
        \underline{Q}_h^k(s, a, b) - 2(H - h + 1)\epsilon \le Q_{h}^{\mu^k, *}(s, a, b) \le Q_{h}^{*, \nu^k}(s, a, b) \le \bar{Q}_h(s, a, b) + 2(H - h +1)\epsilon,
    \end{align*}
    and 
    \begin{align*}
        \underline{V}_h^k(s) - 2(H - h + 2) \epsilon \le V_h^{\mu^k, *}(s) \le V_h^{*, \nu^k}(s) \le \bar{V}_h^k(s) + 2(H - h + 2)\epsilon.
    \end{align*}
\end{lemma}

\begin{proof}
    See Lemma 5 of \citet{xie2020learning} for a detailed proof.
\end{proof}


\begin{lemma} \label{lemma:uniform:concentration}
 For all $(s, a, b, h, k)$ and any fixed policy pair $(\mu, \nu)$, it holds with probability at least $1 - \delta$ that
\begin{align*}
    & \left|\left\langle\phi(s, a, b), \bar{w}_{h}^{b_k}\right\rangle-Q_{h}^{\mu, \nu}(s, a, b)-\mathbb{P}_{h}\left(\bar{V}_{h+1}^{b_k}-V_{h+1}^{\mu, \nu}\right)(s, a, b)\right| \leq \Gamma_{h}^{b_k}(s, a, b), \\
    & \left|\left\langle\phi(s, a, b), \underline{w}_{h}^{b_k}\right\rangle-Q_{h}^{\mu, \nu}(s, a, b)-\mathbb{P}_{h}\left(\underline{V}_{h+1}^{b_k}-V_{h+1}^{\mu, \nu}\right)(s, a, b)\right| \leq \Gamma_{h}^{b_k}(s, a, b) .
\end{align*}
\end{lemma}

\begin{proof}
    See Lemma 3 of \citet{xie2020learning} for a detailed proof.
\end{proof}

     We define
    \begin{align*}
        & \delta_h^k := \bar{V}_h^{b_k}(s_h^k) - \underline{V}_h^{b_k}(s_h^k), \\
        & \zeta_h^k := \mathbb{E} [\delta_{h+1}^k \mid s_h^k, a_h^k, b_h^k ] - \delta_{h+1}^{k}, \\
        & \bar{\gamma}_h^k := \mathbb{E}_{(a, b) \sim \pi_h^k(s_h^k)} [\bar{Q}_h^{b_k}(s_h^k, a, b)] - \bar{Q}_h^{b_k}(s_h^k, a_h^k, b_h^k), \\
        & \underline{\gamma}_h^k := \mathbb{E}_{(a, b) \sim \pi_h^k(s_h^k)} [\bar{Q}_h^{b_k}(s_h^k, a, b)] - \bar{Q}_h^{b_k}(s_h^k, a_h^k, b_h^k).
    \end{align*}
    By Lemma~\ref{lemma:linear:optimism}, we have
    \begin{align} \label{eq:7890}
    V_1^{*, \nu^k}(s_1) - V_1^{\pi^k, *} &\le \bar{V}_1^k(s_1) - \underline{V}_1^k(s_1) + 8K\epsilon \notag \\
    & \le \bar{V}_1^k(s_1) - \underline{V}_1^k(s_1) + \frac{8}{K} \notag \\
    & = \bar{V}_1^{b_k}(s_1) - \underline{V}_1^{b_k}(s_1) + \frac{8}{K} \notag \\
    & = \delta_1^k + \frac{8}{K},
    \end{align}
    where the second inequality uses that $\epsilon = 1/(KH)$.
    By definition, we have
    \begin{align} \label{eq:7891}
        \delta_h^k &= \bar{V}_h^{b_k}(s_h^k) - \overline{V}_h^{b_k}(s_h^k) \notag \\
        & = \mathbb{E}_{(a, b) \sim \pi_h^k(s_h^k)} [\bar{Q}_h^k(s_h^k, a, b)] - \mathbb{E}_{(a, b) \sim \pi_h^k(s_h^k)} [\underline{Q}_h^{b_k}(s_h^k, a, b)]  \notag \\
        & = \bar{Q}_h^k(s_h^k, a_h^k, b_h^k) - \underline{Q}_h^{b_k}(s_h^k, a_h^k, b_h^k) + \bar{\gamma}_h^k - \underline{\gamma}_h^k.
    \end{align}
    Meanwhile, for any $(s, a, b, k, h)$, we have
    \begin{align*}
        \bar{Q}_h^{b_k}(s, a, b) - \underline{Q}_h^{b_k}(s, a, b) & = [(\bar{w}_h^{b_k})^\top \phi(s, a, b) + \Gamma_h^{b_k}(s, a, b) ] - [(\underline{w}_h^{b_k})^\top \phi(s, a, b) - \Gamma_h^{b_k}(s, a, b) ] \\
        & = ( \bar{w}_h^{b_k} - \underline{w}_h^{b_k})^\top \phi(s, a, b) + 2 \Gamma_h^{b_k}(s, a, b).
    \end{align*}
    By Lemma~\ref{lemma:uniform:concentration}, we further have
    \begin{align} \label{eq:7982}
        \bar{Q}_h^{b_k}(s, a, b) - \underline{Q}_h^{b_k}(s, a, b) \le \mathbb{P}_h (\bar{V}_{h+1}^{b_k} - \underline{V}_{h+1}^{b_k} )(s, a, b) + 4 \Gamma_h^{b_k}(s, a, b) .
    \end{align}
    Plugging \eqref{eq:7982} into \eqref{eq:7891} gives that
    \begin{align*}
        \delta_h^k &\le \mathbb{P}_h (\bar{V}_{h+1}^{b_k} - \underline{V}_{h+1}^{b_k} )(s, a, b) + 4 \Gamma_h^{b_k}(s, a, b) + \bar{\gamma}_h^k - \underline{\gamma}_h^k \notag \\
        & = \delta_{h+1}^k + \zeta_h^k + \bar{\gamma}_h^k - \underline{\gamma}_h^k + 4 \Gamma_h^{b_k}(s, a, b) .
    \end{align*}
    Hence, we have
    \begin{align} \label{eq:7983}
        \sum_{k = 1}^K \delta_1^k &\le \sum_{k = 1}^K \sum_{h = 1}^H ( \zeta_h^k + \bar{\gamma}_h^k - \underline{\gamma}_h^k ) + \sum_{k = 1}^K \sum_{h = 1}^H \Gamma_h^{b_k}(s_h^k, a_h^k, b_h^k) \notag \\
        & \le \tilde{O}(H \cdot \sqrt{H K}) +  \sum_{k = 1}^K \sum_{h = 1}^H \Gamma_h^{b_k}(s_h^k, a_h^k, b_h^k),
    \end{align}
    where the last inequality uses the Azuma-Hoeffding inequality.
    Note that 
    \begin{align*}
        \frac{\Gamma_h^{b_k}(s_h^k, a_h^k, b_h^k)}{\Gamma_h^{k}(s_h^k, a_h^k, b_h^k)} \le \sqrt{\frac{\det(\Lambda_h^k)}{ \det(\Lambda_h^{b_k})}} \le \sqrt{\eta},
    \end{align*}
    which implies that
    \begin{align} \label{eq:7984}
         \sum_{k = 1}^K \sum_{h = 1}^H \Gamma_h^{b_k}(s_h^k, a_h^k, b_h^k) \le \sqrt{\eta}  \sum_{k = 1}^K \sum_{h = 1}^H \Gamma_h^{k}(s_h^k, a_h^k, b_h^k) \le \tilde{{O}} ( \sqrt{\eta d^3 H^4 K}),
    \end{align}
    where the last inequality uses the elliptical potential lemma \citep{abbasi2011improved}. Combining \eqref{eq:7890}, \eqref{eq:7983}, and \eqref{eq:7984}, together with the fact that $\eta = 2$, we obtain 
    \begin{align*}
        \mathrm{Regret}(K) \le \tilde{{O}}(\sqrt{ d^3 H^4 K}),
    \end{align*}
    which concludes the proof.
\end{proof}














\subsection{Multi-batched V-learning}
In this section we introduce the multi-batched version of V-learning \citep{jin2021v} for general-sum Markov games. Our goal is to minimize the following notion of regret. Let $V_{i, 1}^\pi\left(s_1\right)$ be the expected cumulative reward that the $i^{\text {th }}$ player will receive if the game starts at initial state $s_1$ at the $1^{\text {st }}$ step and all players follow joint policy $\pi$. Let $\hat{\pi}^k$ be the policy executed at the $k^{\text{th}}$ episode. The regret is defined as 
\begin{equation}
    \operatorname{Regret}(K)=\sum_{k=1}^{K} \max_{j} \left( V_{j, h}^{\dagger, \hat{\pi}_{-j, h}^k}- V_{j, h}^{\hat{\pi}_h^k}\right)(s_1),
\end{equation}
where $V_{j, h}^{\dagger, \hat{\pi}_{-j, h}^k}$ is the best response of the $j^{\text {th }}$ player when other players follow $\hat{\pi}$.

\begin{algorithm}[H]
    \caption{Multi-batched V-learning}\label{alg:vlearning}
    \begin{algorithmic}[1]
    \STATE {\bfseries Initialize:} $V_h(s) \leftarrow H+1-h, N_h(s) \leftarrow 0, \pi_h(a \mid s) \leftarrow 1 / A$, trigger set $\mathcal{L} \leftarrow\left\{2^{i-1} \mid 2^i \leq K H, i=1,2, \ldots\right\}$
    \FOR{episode $k=1,...,K$}
    \STATE Receive $s_1$.
    \FOR{$h=1,...,H$}
    \STATE take action $a_h \sim \pi_h^{\Tilde{k}}\left(\cdot \mid s_h\right)$, observe  $r_h$ and $s_{h+1}$.
    \STATE $t=N_h\left(s_h\right) \leftarrow N_h\left(s_h\right)+1$.
    \STATE $\tilde{V}_h\left(s_h\right) \leftarrow\left(1-\alpha_t\right) \tilde{V}_h\left(s_h\right)+\alpha_t\left(r_h+V_{h+1}\left(s_{h+1}\right)+\beta (t)\right)$
    \STATE $V_h\left(s_h\right) \leftarrow \min \left\{H+1-h, \tilde{V}_h\left(s_h\right)\right\}$
    \STATE $\pi_h^k\left(\cdot \mid s_h\right) \leftarrow \text{ADV\_BANDIT\_UPDATE} \left(a_h, \frac{H-r_h-V_{h+1}\left(s_{h+1}\right)}{H}\right)$ on $\left(s_h, h\right)^{\text {th }}$ adversarial bandit.
    \ENDFOR
    \IF{$\exists s$, $N_h(s) \in \mathcal{L}$}
    \STATE $\Tilde{k}\leftarrow k$
    \ENDIF
    \ENDFOR
    \end{algorithmic}
\end{algorithm}

The multi-batched V-learning algorithm maintains a value estimator $V_h(s)$, a counter $N_h(s)$, and a policy $\pi_h(\cdot \mid s)$ for each $s$ and $h$. We also maintain $S \times H$ different adversarial bandit algorithms. At step $h$ in episode $k$, the algorithm is divided into three steps: policy execution, $V$-value update, and policy update. In policy execution step, the algorithm takes action $a_h$ according to $\pi_h^{\Tilde{k}}$, and observes reward $r_h$ and the next state $s_{h+1}$, and updates the counter $N_h\left(s_h\right)$. Note that $\pi_h^{\Tilde{k}}$ is updated only when the visiting count of some state $N_h(s)$ doubles. Therefore it ensures a low batch number. 

In the $V$-value update step, we update the estimated value function by
\begin{align*}
\tilde{V}_h\left(s_h\right) = \left(1-\alpha_t\right) \tilde{V}_h\left(s_h\right)+\alpha_t\left(r_h+V_{h+1}\left(s_{h+1}\right) + \beta (t)\right),
\end{align*}
where the learning rate is defined as
\begin{align*}
\alpha_t=\frac{H+1}{H+t}, \quad  \alpha_t^0=\prod_{j=1}^t\left(1-\alpha_j\right),  \quad \alpha_t^i=\alpha_i \prod_{j=i+1}^t\left(1-\alpha_j\right).
\end{align*}
and $\beta (t)$ is the bonus to promote optimism.

In the policy update step, the algorithm feeds the action $a_h$ and its "loss" $\frac{H-r_h+V_{h+1}\left(s_{h+1}\right)}{H}$ to the $\left(s_h, h\right)^{\text {th }}$ adversarial bandit algorithm. Then it receives the updated policy $\pi_h\left(\cdot \mid s_h\right)$.

\paragraph{The ADV\_BANDIT\_UPDATE subroutine} Consider a multi-armed bandit problem with adversarial loss, where we denote the action set by $\mathcal{B}$ with $|\mathcal{B}|=B$. At round $t$, the learner determines a policy $\theta_t \in \Delta_{\mathcal{B}}$, and the adversary chooses a loss vector $\ell_t \in[0,1]^B$. Then the learner takes an action $b_t$ according to policy $\theta_t$, and receives a noisy bandit feedback $\tilde{\ell}_t\left(b_t\right) \in[0,1]$, where $\mathbb{E}\left[\tilde{\ell}_t\left(b_t\right) \mid \ell_t, b_t\right]=\ell_t\left(b_t\right)$. Then, the adversarial bandit algorithm performs updates based on $b_t$ and $\tilde{\ell}_t\left(b_t\right)$, and outputs the policy for the next round $\theta_{t+1}$.


We first state our requirement for the adversarial bandit algorithm used in V-learning, which is to have a
high probability weighted external regret guarantee as follows.
\begin{assumption}
For any $t \in \mathbb{N}$ and any $\delta \in(0,1)$, with probability at least $1-\delta$, we have
\begin{equation}
\max _{\theta \in \Delta_{\mathcal{B}}} \sum_{i=1}^t \alpha_t^i\left[\left\langle\theta_i, \ell_i\right\rangle-\left\langle\theta, \ell_i\right\rangle\right] \leq \xi(B, t, \log (1 / \delta)).
\end{equation}
We further assume the existence of an upper bound $\Xi(B, t, \log (1 / \delta)) \geq \sum_{t^{\prime}=1}^t \xi\left(B, t^{\prime}, \log (1 / \delta)\right)$ where (i) $\xi(B, t, \log (1 / \delta))$ is non-decreasing in $B$ for any $t, \delta$; (ii) $\Xi(B, t, \log (1 / \delta))$ is concave in $t$ for any $B, \delta$.
\end{assumption}

As is shown in \citet{jin2021v}, the Follow-the-Regularized-Leader (FTRL) algorithm satisfies the assumption with bounds $\xi(B, t, \log (1 / \delta)) \leq O(\sqrt{H B\log (B / \delta) / t})$ and $\Xi(B, t, \log (1 / \delta)) \leq O(\sqrt{H B t \log (B / \delta)})$. And we will use FTRL as the subroutine in our algorithm.

For two-player general sum Markov game, we let the two players run Algorithm \ref{alg:vlearning} independently. Each player will uses her own set of bonus that depends on the number of her actions. We have the following theorem for the regret of multi-batched V-learning.

\begin{theorem}
Suppose we choose subroutine ADV\_BANDIT\_UPDATE as FTRL. For any $\delta \in(0,1)$ and $K \in \mathbb{N}$, let $\iota=\log (H S A K / \delta)$. Choose learning rate $\alpha_t$ and bonus $\left\{\beta (t)\right\}_{t=1}^K$ as $\beta (t)=c \cdot \sqrt{H^3 A \iota / t}$ so that $\sum_{i=1}^t \alpha_t^i \beta (i)=\Theta\left(\sqrt{H^3 A \iota / t}\right)$ for any $t \in[K]$, where $A=\max_i A_i$ Then, with probability at least $1-\delta$, after running Algorithm  for $K$ episodes, we have
\begin{equation}
    \operatorname{Regret}(K) \leq O\left(\sqrt{H^5SA\iota} \right).
\end{equation}
And the batch number is $O(HS\log K)$.
\end{theorem}
\begin{proof}
The proof mainly follows \citet{jin2021v}.  Below we list some useful lemmas, which have already been proved in \citet{jin2021v}.
\begin{lemma}[Lemma 10, \citet{jin2021v}]
The following properties hold for $\alpha_t^i$ :

    1. $\frac{1}{\sqrt{t}} \leq \sum_{i=1}^t \frac{\alpha_t^i}{\sqrt{i}} \leq \frac{2}{\sqrt{t}}$ and $\frac{1}{t} \leq \sum_{i=1}^t \frac{\alpha_t^i}{i} \leq \frac{2}{t}$ for every $t \geq 1$.
    
2. $\max _{i \in[t]} \alpha_t^i \leq \frac{2 H}{t}$ and $\sum_{i=1}^t\left(\alpha_t^i\right)^2 \leq \frac{2 H}{t}$ for every $t \geq 1$.

3. $\sum_{t=i}^{\infty} \alpha_t^i=1+\frac{1}{H}$ for every $i \geq 1$.
\end{lemma}

The next lemma shows that $V_h^k$ is an optimistic estimation of $V_{j, h}^{\dagger, \hat{\pi}_{-j, h}^k}$
\begin{lemma}[Lemma 13, \citet{jin2021v}]
For any $\delta \in(0,1]$, with probability at least $1-\delta$, for any $(s, h, k, j) \in \mathcal{S} \times[H] \times [K] \times[m],$ 
$V_{j, h}^k(s) \geq V_h^{\dagger, \nu^k}(s)
$
\end{lemma}


And we define the pessimistic pessimistic V-estimations $\underline{V}$ that are defined similarly as $\tilde{V}$ and $V$. Formally, let $t=N_h^k(s)$, and suppose $s$ was previously visited at episodes $k^1, \ldots, k^t<k$ at the $h$-th step. Then
\begin{equation}
\begin{gathered}
\underline{V}_{j,h}^k(s)=\max \left\{0,\sum_{i=1}^t \alpha_t^i\left[r_{j,h}\left(s, \boldsymbol{a}_h^{k^i}\right)+\underline{V}_{j,h+1}^{k^i}\left(s_{h+1}^{k^i}\right)-\beta (i)\right] \right\}.\\
\end{gathered}
\end{equation}
The next lemma shows $\underline{V}_{j, h}^k(s)$ is a lower bound of $V_{j, h}^{\hat{\pi}_h^k}(s)$.
\begin{lemma}[Lemma 14, \citet{jin2021v}]
    For any $\delta \in(0,1]$, with probability at least $1-\delta$, the following holds for any $(s, h, k, j) \in \mathcal{S} \times[H] \times[K] \times[m]$ and any player $j, \underline{V}_{j, h}^k(s) \leq V_{j, h}^{\hat{\pi}_h^k}(s)$.
\end{lemma}

It remains to bound the gap $\sum_{k=1}^K \max _j\left(V_{1, j}^k-\underline{V}_{1, j}^k\right)\left(s_1\right)$. For each player $j$ we define $\delta_{j, h}^k:=V_{j, h}^k\left(s_h^k\right)-\underline{V}_{j, h}^k\left(s_h^k\right) \geq 0$. The non-negativity here is a simple consequence of the update rule and induction. We need to bound $\delta_h^k:=\max _j \delta_{j, h}^k$. Let $n_h^k=N_h^k\left(s_h^k\right)$ and suppose $s_h^k$ was previously visited at episodes $k^1, \ldots, k^{n_h^k}<k$ at the $h$-th step. Now by the update rule,
\begin{equation}
\begin{aligned}
\delta_{j, h}^k & =V_{j, h}^k\left(s_h^k\right)-\underline{V}_{j, h}^k\left(s_h^k\right) \\
& \leq \alpha_{n_h^k}^0 H+\sum_{i=1}^{n_h^k} \alpha_{n_h^k}^i\left[\left(V_{j, h+1}^{k^i}-\underline{V}_{j, h+1}^{k^i}\right)\left(s_{h+1}^{k^i}\right)+2 \beta_{j}^{\Tilde{k}}(i)\right] \\
& \leq \alpha_{n_h^k}^0 H+\sum_{i=1}^{n_h^k} \alpha_{n_h^k}^i\left[\left(V_{j, h+1}^{k^i}-\underline{V}_{j, h+1}^{k^i}\right)\left(s_{h+1}^{k^i}\right)+4 \beta_{j}^{k}(i)\right] \\
& =\alpha_{n_h^k}^0 H+\sum_{i=1}^{n_h^k} \alpha_{n_h^k}^i \delta_{j, h+1}^{k^i}+O\left(H \xi\left(A_j, n_h^k, \iota\right)+\sqrt{H^3 \iota / n_h^k}\right)
\end{aligned}
\end{equation}
The third line holds because we use FTRL as the subroutine, $\beta_{j}(t)=c \cdot \sqrt{H^3 A_j \iota / t}$, and due to our doubling scheme we have $\beta (n_h^{\Tilde{k}})\leq 2\beta (n_h^{k})$. And in the last step we have used $\sum_{i=1}^t \alpha_t^i \beta_{j, i}=\Theta\left(H \xi\left(A_j, t, \iota\right)+\sqrt{H^3 A \iota / t}\right)$.

The remaining step is the same as \citet{jin2021v}. Summing the first two terms w.r.t. $k$,
\begin{equation}
\sum_{k=1}^K \alpha_{n_h^k}^0 H=\sum_{k=1}^K H \mathbb{I}\left\{n_h^k=0\right\} \leq S H,
\end{equation}
\begin{equation}
\sum_{k=1}^K \sum_{i=1}^{n_h^k} \alpha_{n_h^k}^i \delta_{h+1}^{k^i} \leq \sum_{k^{\prime}=1}^K \delta_{h+1}^{k^{\prime}} \sum_{i=n_h^{k^{\prime}}+1}^{\infty} \alpha_i^{n_h^{k^{\prime}}} \leq\left(1+\frac{1}{H}\right) \sum_{k=1}^K \delta_{h+1}^k.
\end{equation}
Putting them together,
\begin{equation}
\begin{aligned}
\sum_{k=1}^K \delta_h^k & =\sum_{k=1}^K \alpha_{n_h^k}^0 H+\sum_{k=1}^K \sum_{i=1}^{n_h^k} \alpha_{n_h^k}^i \delta_{h+1}^{k^i}+\sum_{k=1}^K {O}\left(H \xi\left(A, n_h^k, \iota\right)+\sqrt{\frac{H^3 \iota}{n_h^k}}\right) \\
& \leq H S+\left(1+\frac{1}{H}\right) \sum_{k=1}^K \delta_{h+1}^k+\sum_{k=1}^K {O}\left(H \xi\left(A, n_h^k, \iota\right)+\sqrt{\frac{H^3 \iota}{n_h^k}}\right).
\end{aligned}
\end{equation}
Recursing this argument for $h\in [H]$ gives 
\begin{equation}
\sum_{k=1}^K \delta_1^k \leq e S H^2+e \sum_{h=1}^H \sum_{k=1}^K {O}\left(H \xi\left(A, n_h^k, \iota\right)+\sqrt{\frac{H^3 \iota}{n_h^k}}\right).
\end{equation}
By pigeonhole argument,
\begin{equation}
\begin{aligned}
\sum_{k=1}^K\left(H \xi\left(A, n_h^k, \iota\right)+\sqrt{H^3 \iota / n_h^k}\right) & ={O}(1) \sum_s \sum_{n=1}^{N_h^K(s)}\left(H \xi(A, n, \iota)+\sqrt{\frac{H^3 \iota}{n}}\right) \\
& \leq {O}(1) \sum_s\left(H \Xi\left(A, N_h^K(s), \iota\right)+\sqrt{H^3 N_h^K(s) \iota}\right) \\
& \leq {O}\left(H S \Xi(A, K / S, \iota)+\sqrt{H^3 S K \iota}\right),
\end{aligned}
\end{equation}
where in the last step we have used concavity.
Finally take the sum w.r.t $h\in [H]$, and plugging $\Xi(B, t, \log (1 / \delta)) \leq {O}(\sqrt{H B t \log (B / \delta)})$ we have 
\begin{equation}
    \operatorname{Regret}(K)\leq O\left(\sqrt{H^5SA\iota} \right).
\end{equation}

\end{proof}

\iffalse
Finally, adapting the algorithm to the delayed feedback setting using our framework, we have the following corollary.
\begin{corollary}
For tabular Markov game with delayed feedback, running Algorithm \ref{alg:protocal_delay} with $\mathcal{ALG}$ being Algorithm \ref{alg:vlearning}, we can upper bound the regret by
\begin{equation}
\begin{aligned}
        \operatorname{Regret}(K)\leq & O\big( \frac{1}{q}\sqrt{H^5SA\iota}  + H^2 S d_{\tau}(q)\log K\big) 
        \end{aligned}
    \end{equation}
    for any $q\in (0,1)$. In addition, if the delays satisfy Assumption \ref{ass:subexp}, the regret can be upper bounded by
    \begin{equation}
    \begin{aligned}
        \operatorname{Regret}(K)\leq &O\big(\sqrt{H^5SA\iota} +  H^2S \mathbb{E}[\tau]\log K\big).
        \end{aligned}
    \end{equation}
\end{corollary}
\fi


\section{Conclusion and Future Work}
In this paper we study delayed feedback in general multi-agent sequential decision making. We propose a novel reduction-based framework, which turns any multi-batched algorithm for sequential decision making with instantaneous feedback into a sample-efficient algorithm that can handle stochastic delays in sequential decision making. Based on this framework, we obtain a complete set of results for (multi-agent) sequential decision making with delayed feedback.  Our work has also shed light on future works. First, it remains unclear whether the result is tight for MDP and Markov game with delayed feedback. Second, it is possible that we can derive a multi-batched algorithm for tabular Markov game with a smaller batch number, since in tabular MDP, \citet{zhang2022near} gives an algorithm with $O(H+\log_2\log_2 K)$ batch number which is independent of $S$. It is not clear whether we can  achieve similar result in MDP for Markov games.
\section{Details of Algorithms for Linear Bandits}
The phase elimination algorithm for linear bandits in \cite{lattimore2020bandit} is as follows. This algorithm is naturally a multi-batched algorithm, with each phase as one batch. Since the length of phase $\ell$ is $O(2^{\ell})$, the number of phases is $O(\log K)$. Note that in each phase the policy is pre-calculated at the beginning of the phase, and does not rely on the data of current phase.
\begin{algorithm}[H]
    \caption{Phase Elimination}
    \begin{algorithmic}[1]
    \STATE {\textbf{Input:} $\mathcal{A} \subset \mathbb{R}^d$, $\beta >  1$, $\delta$}
    \STATE Set $\ell=1$ and let $\mathcal{A}_1=\mathcal{A}$
    \STATE Let $t_{\ell}=t$ be the current timestep and find $G$-optimal design $\pi_{\ell} \in \mathcal{P}\left(\mathcal{A}_{\ell}\right)$ with $\operatorname{Supp}\left(\pi_{\ell}\right) \leq d(d+1) / 2$ that maximises $$\log \operatorname{det} V\left(\pi_{\ell}\right) \text{ subject to } \sum_{a \in \mathcal{A}_{\ell}} \pi_{\ell}(a)=1$$
\STATE Let $\varepsilon_{\ell}=2^{-\ell}$ and
$$
T_{\ell}(a)=\left\lceil\frac{2 d \pi_{\ell}(a)}{\varepsilon_{\ell}^2} \log \left(\frac{k \ell(\ell+1)}{\delta}\right)\right] \text { and } T_{\ell}=\sum_{a \in \mathcal{A}_{\ell}} T_{\ell}(a)
$$

\STATE Choose each action $a \in \mathcal{A}_{\ell}$ exactly $T_{\ell}(a)$ times.


\STATE Calculate the empirical estimate:
$$
\hat{\theta}_{\ell}=V_{\ell}^{-1} \sum_{t=t_{\ell}}^{t_{\ell}+T_{\ell}} A_t X_t \quad \text { with } \quad V_{\ell}=\sum_{a \in \mathcal{A}_{\ell}} T_{\ell}(a) a a^{\top}
$$
using observable data in this phase.
\STATE Eliminating low reward arms:
$$\mathcal{A}_{\ell+1}=\left\{a \in \mathcal{A}_{\ell}: \max _{b \in \mathcal{A}_{\ell}}\left\langle\hat{\theta}_{\ell}, b-a\right\rangle \leq 2 \varepsilon_{\ell}\right\} .$$
\STATE $\ell \leftarrow \ell + 1$ and go to Line 2.
    \end{algorithmic}
\end{algorithm}

\begin{theorem}[Theorem 22.1 in \citet{lattimore2020bandit}]
With probability at least $1-\delta$, the regret of Algorithm 5 satisfies
\begin{equation}
\operatorname{Regret}(K) \leq C \sqrt{K d \log \left(\frac{A \log (K)}{\delta}\right)},
\end{equation}
where $C>0$ is a universal constant. If $\delta=O(1 / K)$, then $\mathbb{E}\left[\operatorname{Regret}(K)\right] \leq C \sqrt{K d \log (AK)}$ for an appropriately chosen universal constant $C>0$.
\end{theorem}

For infinite action set $\mathcal{A} = [-1,1]^d$, we use a covering technique: we find a $\epsilon$-covering of the action space, and run Phase Elimination on the covering set. The covering number of the set $[-1,1]^d$ is $O(d\log(1/\epsilon))$. And the error caused by using $\epsilon$-covering will lead to a $O(\epsilon K)$ increase in regret. Therefore, by setting $\epsilon = \frac{1}{K}$, the regret of the whole algorithm is $O(d\sqrt{K}\log K)$.

\section{A Framework for Sequential Decision Making with Delayed Feedback}
In this section we introduce our framework for sequential decision making problem with stochastic delayed feedback. We first describes our framework, which converts any multi-batched algorithm to algorithm for MSDM with delayed feedback. Then we provide theoretical guarantees for the performance of such algorithms. 

For any sequential decision making problem, assume that we have a multi-batched algorithm $\mathcal{ALG}$ for the problem without delay. Then in the existence of delay, we can still run $\mathcal{ALG}$. The difference is, in each batch of the algorithm, we run some extra steps until we observe enough feedback so that the stopping criteria is satisfied. For example, if the delay $\tau$ is a constant and the stopping criteria is that the policy $\pi_k$ is executed for a pre-defined number of times $t_k$, then we only need to run $\pi_k$ for $t_k+\tau$ times. After the extra steps finishes, we can collect $t_k$ delayed observations, which meets the original stopping criteria. Then we can continue to the next batch. Algorithm \ref{alg:protocal_delay} gives a formal description.

\begin{algorithm}
    \caption{Multi-batched Algorithm With Delayed Feedback}\label{alg:protocal_delay}
    \begin{algorithmic}[1]
    \STATE {\bfseries Require:} A multi-batched algorithm for the undelayed environment $\mathcal{ALG}$
    \STATE Initialize dataset $\mathcal{D}^{0} = \emptyset$
    \FOR{batch $m=1,...,M$}
    \STATE $\mathcal{ALG}$ calculates a policy $\pi^m$ (or a policy sequence) and a stopping criteria $SC$
    \STATE $\mathcal{D}=\emptyset$
    \WHILE{$SC(\mathcal{D})=0$}
    \STATE $k\leftarrow k+1$
    \STATE In episode $k$, execute $\pi^m$
    \STATE Collect trajectory feedback in this batch that is observed at the end of the episode: $\{o^t: t+\tau_t=k\}$
    \STATE $\mathcal{D}=\mathcal{D} \cup \{o^t: t+\tau_t=k\} $
    \ENDWHILE
    \STATE Update dataset $\mathcal{D}^{m} = \mathcal{D}^{m-1}\cup \mathcal{D}$
    \ENDFOR
    \end{algorithmic}
\end{algorithm}

For the performance of Algorithm \ref{alg:protocal_delay}, we have the following theorem, which relates the regret of delayed MSDM problems with the regret of multi-batched algorithm in undelayed environment. 

\begin{theorem}\label{thm:main}
    Assume that in the undelayed environment, we have a multi-batched algorithm with batch number $N_b$, and the regret of the algorithm in $K$ episodes is $\widetilde{\operatorname{Regret}}(K)$. Then in the delayed feedback case, the regret can be upper bounded by
    \begin{equation}\label{eqn:reg_quant}
        \operatorname{Regret}(K)\leq \frac{1}{q}\widetilde{\operatorname{Regret}}(K) + \frac{2H N_b \log K}{q} + H N_b d_{\tau}(q)
    \end{equation}
    for any $q\in (0,1)$. In addition, if the delays satisfy Assumption \ref{ass:subexp}, the regret can be upper bounded by
    \begin{equation}\label{eqn:reg_exp}
        \operatorname{Regret}(K)\leq \widetilde{\operatorname{Regret}}(K) +  H N_b \left(\mathbb{E}[\tau]+C_\tau\right),
    \end{equation}
    where $C_\tau =\min \left\{\sqrt{2 v^2 \log \left(\frac{3 t}{2 \delta}\right)}, 2 b \log \left(\frac{3 t}{2 \delta}\right)\right\}$ is a problem-independent constant.
\end{theorem}

The proof is in Appendix \ref{sec:proof_main}. The main idea is simple: in each batch, we can control the number of extra steps when waiting for the original algorithm to collect enough delayed feedback. And the extra regret can be bounded by the product of the number of batches and the number of extra steps per batch.

\iffalse
\subsection{Proof of Theorem \ref{thm:main}} \label{sec:proof_main}
We first prove \eqref{eqn:reg_exp}. First, since the delays are i.i.d. subexponential random variables, by standard concentration inequality and uniform bound \cite{wainwright2019high}, we have the following lemma:

\begin{lemma}\label{lem:concen_1}
    Let $\left\{\tau_t\right\}_{t=1}^{\infty}$ be i.i.d $(v,b)$  subexponential random variables with expectation $\mathbb{E}[\tau]$. Then we have 
    \begin{equation}
\mathbb{P}\left(\exists t \geq 1: \tau_t \geq \mathbb{E}[\tau]+C_\tau\right) \leq 1-\delta
\end{equation}
where $C_\tau =\min \left\{\sqrt{2 v^2 \log \left(\frac{3 t}{2 \delta}\right)}, 2 b \log \left(\frac{3 t}{2 \delta}\right)\right\}$
\end{lemma}

Define the good event $G=\{\exists t \geq 1: \tau_t \geq \mathbb{E}[\tau]+C_\tau\}$. By Lemma \ref{lem:concen_1}, the good event happens with probability at least $1-\delta$. Therefore, conditioned on the good event happens, in each batch of the algorithm, we only need to run $\mathbb{E}[\tau]+C_\tau$ episodes and the algorithm can observe enough feedback to finish this batch.

The regret in a batch can be divided into two parts: the first part is the regret caused by running the algorithm in the undelayed environment; the second part is caused by running extra episodes to wait for delayed feedback. The first part can be simply bounded by $\widetilde{\operatorname{Regret}}(K)$. For the second part, since each episode contributes at most $H$ regret, the total regret can be bounded by

\begin{equation}
        \operatorname{Regret}(K)\leq \widetilde{\operatorname{Regret}}(K) +  H N_b \left(\mathbb{E}[\tau]+C_\tau\right)
\end{equation}

For the second inequality, we have the following lemma which reveals the relation between the number of observed feedback and the actual number of episodes using quantile function.

\begin{lemma}\label{lem:concen_2}
At time $t$, Assume that the total number of episodes is $n_t$, and the number of observed feedback is $m_t$, for any quantile $q$ we have
\begin{equation}
\operatorname{Pr}\left[n_{t+d_{\tau}(q)}<\frac{q}{2} m_t\right] \leq \exp \left(-\frac{q}{8} m_t\right) .
\end{equation}
\end{lemma}

\begin{proof}
Define $\mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\}$ to be an indicator that on time $s$ that the delay is smaller than $d_{\tau}(q)$. Note that  $\mathbb{E}\left[\mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\} \right] \geq q$. Thus,
\begin{equation}
\begin{aligned}
& \operatorname{Pr}\left[n_{t+d_{\tau}(q)}<\frac{q}{2} m_t\right]  \leq \operatorname{Pr}\left[\sum_{s=1}^{t} \mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\}<\frac{q}{2} m_t\right] \\
& \leq \operatorname{Pr}\left[\sum_{s=1}^{t} \mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\}<\frac{1}{2} \sum_{s=1}^{t} \mathbb{E}\left[\mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\} \right]\right] \\
& \leq \exp \left(-\frac{1}{8} \sum_{s=1}^{t} \mathbb{E}\left[\mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\}\right]\right) \leq \exp \left(-\frac{q}{8} m_t\right),
\end{aligned}
\end{equation}
where the third inequality follows from the relative Chernoff bound, and the last inequality is since
$\sum_{s=1}^{t} \mathbb{E}\left[\mathbb{I}\left\{\tau_s \leq d_{\tau}(q)\right\} \right] \geq q \cdot m_t$.
\end{proof}

Lemma \ref{lem:concen_2} means, if the length of a batch $m$ is larger than $\frac{\log K}{q}$, then with high probability, if we run the batch for $\frac{m}{q}+d_{\tau}(q)$ episodes, we will observe $m$ feedbacks, which is enough for the algorithm to finish the batch. On the other hand, if the length of a batch is smaller than $\frac{\log K}{q}$, then the regret of this batch can be trivially bounded by $\frac{H\log }{q}$. Hence the total regret can be bounded by
\begin{equation}
        \operatorname{Regret}(K)\leq \frac{1}{q}\widetilde{\operatorname{Regret}}(K) + \frac{2H N_b \log K}{q} +  H N_b d_{\tau}(q) 
\end{equation}
which finishes the proof.

\fi

\iffalse

Applying Theorem \ref{thm:main} to different settings, we will get various type of results. 

\paragraph{Results in bandits} For example, in multi-armed bandit setting, using the BaSE algorithm  \cite{gao2019batched}, we can get a $O(\frac{1}{q}A\log(K)+d_{\tau}(q)\log(K)$ upper bound from \eqref{eqn:reg_quant}, which recovers the SOTA result in \citet{lancewicki2021stochastic} up to a $\log K$ factor in the delay-dependent term.

In linear bandit, using the Phase Elimination algorithm \cite{lattimore2020bandit}, we can get a $O(\sqrt{dK\log(A)}+\mathbb{E}[\tau]\log K)$ upper bound in the finite-arm setting, where $d$ is the dimension of the linear feature space. And we can use standard covering technique to deal with infinite action space when $\mathcal{A}=[-1,1]^d$, and the regret bound becomes $\Tilde{O}(d\sqrt{K}+\mathbb{E}[\tau]\log K)$. Compared with the result in \citet{howson2021delayed}, our bound is tighter in the delay-dependent term as we remove the $d^{3/2}$ factor.

\paragraph{Results in RL} In tabular MDP, using the policy elimination algorithm \cite{zhang2022near}, we get an upper bound of $\tilde{O}\left(\sqrt{S A H^3 K }+ H ( 2H+\log_2 \log_2 K)\mathbb{E}[\tau]\right)$. Compared with previous result $\sqrt{H^3 S A K L}+H^2 S A \log K\mathbb{E}[\tau] $ \cite{howson2022delayed}, our bound removes the $SA$ factor in the delay-dependent term, therefore is tighter. 
We can also apply our framework to linear MDP and MDP with general function approximation settings with delay. These settings are not studied before, therefore our result is novel. In linear MDP setting, using the algorithm in \citet{gao2021provably} we get a regret upper bound $\Tilde{O}(\sqrt{d^3 H^4 K}+d H^2 \log K\mathbb{E}[\tau])$. And in MDP with general function approximation, using the algorithm in \citet{kong2021online} we get a  $\Tilde{O}\left(\sqrt{\operatorname{dim}_E^2(\mathcal{F}, 1 / K) \cdot H^3 \cdot T}+H^2\operatorname{dim}_E(\mathcal{F}, 1 / K)\mathbb{E}[\tau]\right)$ where $\operatorname{dim}_E$ is the eluder dimension. Other results are listed in Table \ref{tab:regret.bounds}.

\fi

\section{Results for Bandits and MDPs} 
We now apply Theorem \ref{thm:main} to different bandit and MDP problems.

In multi-armed bandit settings, using the BaSE algorithm  \cite{gao2019batched}, we can get the following bound.
\begin{corollary}
For multi-armed bandit with delayed feedback, running Algorithm \ref{alg:protocal_delay} with $\mathcal{ALG}$ being the BaSE algorithm in \citet{gao2019batched}, we can upper bound the regret by
\begin{align*}
        \operatorname{Regret}(K)\leq O\left(\frac{A \log K}{q\min _{i \neq \star} \Delta_i} + \frac{\log^2 K }{q} +  d_{\tau}(q) \log K \right)
    \end{align*}
    for any $q\in (0,1)$, where $\Delta_i$ is the optimal gap of the $i^{\text{th}}$ arm. In addition, if the delays satisfy Assumption \ref{ass:subexp}, the regret can be upper bounded by
    \begin{align*}
        \operatorname{Regret}(K)\leq O\left(\frac{A \log K}{\min _{i \neq \star} \Delta_i} +  \mathbb{E}[\tau]\log K\right) .
    \end{align*}
\end{corollary}
This result recovers the SOTA result in \citet{lancewicki2021stochastic} up to a $\log K$ factor in the delay-dependent term.

In linear bandit settings, using the Phase Elimination algorithm \citep{lattimore2020bandit}, we can get the following bound.
\begin{corollary}
For linear bandit with delayed feedback, let $d$ be the dimension of the feature space. When the arm set $\mathcal{A}$ is finite, running Algorithm \ref{alg:protocal_delay} with $\mathcal{ALG}$ being the Phase Elimination algorithm in \citet{lattimore2020bandit}, we can upper bound the regret by
\begin{align*}
        \operatorname{Regret}(K)\leq O\left(\frac{1}{q}\sqrt{dK\log A} + \frac{\log^2 K }{q} +  d_{\tau}(q) \log K \right)
    \end{align*}
    for any $q\in (0,1)$. In addition, if the delays satisfy Assumption \ref{ass:subexp}, the regret can be upper bounded by
    \begin{align*}
        \operatorname{Regret}(K)\leq O\left(\sqrt{dK\log A}+\mathbb{E}[\tau]\log K\right) .
    \end{align*}
\end{corollary}
When the action set is infinitely large (for example, $\mathcal{A}=[-1,1]^d$), we can use techniques such as covering to obtain regret bounds whose main term scales as $\Tilde{O}(d\sqrt{K})$. Compared with the result in \citet{howson2021delayed} which scales as $\Tilde{O}(d\sqrt{K}+d^{3/2}\mathbb{E}[\tau]) $, our bound is tighter in the delay-dependent term as we remove the $d^{3/2}$ factor.

In tabular MDP settings, using the policy elimination algorithm \cite{zhang2022near}, we can get the following bound.
\begin{corollary}
For tabular MDP with delayed feedback, running Algorithm \ref{alg:protocal_delay} with $\mathcal{ALG}$ being the policy elimination algorithm in \citet{zhang2022near}, we can upper bound the regret by
\begin{align*}
        \operatorname{Regret}(K)\leq  O\Big(\frac{1}{q}\sqrt{S A H^3 K \iota} + \frac{(H+\log \log K)\log K }{q}   +  (H+\log \log K)d_{\tau}(q)  \Big)
    \end{align*}
    for any $q\in (0,1)$, where $\iota$ is some log factor. In addition, if the delays satisfy Assumption \ref{ass:subexp}, the regret can be upper bounded by
    \begin{align*}
        \operatorname{Regret}(K)\leq O\left(\sqrt{S A H^3 K \iota}+ H (H+\log \log K)\mathbb{E}[\tau]\right).
    \end{align*}
\end{corollary}
Compared with the previous result $\sqrt{H^3 S A K \iota}+H^2 S A \mathbb{E}[\tau]\log K $ in \citet{howson2022delayed}, our bound removes the $SA$ factor in the delay-dependent term, therefore is tighter.

We can also apply our framework to linear MDP and MDP with general function approximation settings with delay. These settings are not studied before, therefore our result is novel. In linear MDP settings, using the algorithm in \citet{gao2021provably} we can get the following bound.
\begin{corollary}
For linear MDP with delayed feedback, let $d$ be the dimension of the feature space. Running Algorithm \ref{alg:protocal_delay} with $\mathcal{ALG}$ being the algorithm in \citet{gao2021provably}, we can upper bound the regret by
\begin{align*}
        \operatorname{Regret}(K)\leq & \Tilde{O}\big(\frac{1}{q}\sqrt{d^3 H^4 K} 
        +  d H^2 d_{\tau}(q)\log K  \big)
    \end{align*}
    for any $q\in (0,1)$. In addition, if the delays satisfy Assumption \ref{ass:subexp}, the regret can be upper bounded by
    \begin{equation*}
        \operatorname{Regret}(K)\leq \Tilde{O}\left(\sqrt{d^3 H^4 K}+d H^2 \mathbb{E}[\tau]\log K\right).
    \end{equation*}
\end{corollary}
And in MDP with general function approximation, using the algorithm in \citet{kong2021online} we get the following bound.
\begin{corollary}
For MDP with general function approximation and delayed feedback, let $\operatorname{dim}_E(\mathcal{F}, \epsilon)$ be the $\epsilon$-eluder dimension of the function class $\mathcal{F}$. Running Algorithm \ref{alg:protocal_delay} with $\mathcal{ALG}$ being the algorithm in \citet{kong2021online}, we can upper bound the regret by
\begin{equation*}
\begin{aligned}
        \operatorname{Regret}(K)\leq \Tilde{O}\left(\frac{1}{q}\sqrt{\operatorname{dim}_E^2(\mathcal{F}, 1 / K) H^4 K} +  
         H^2\operatorname{dim}_E(\mathcal{F}, 1 / K) d_{\tau}(q)  \right)
        \end{aligned}
    \end{equation*}
    for any $q\in (0,1)$. In addition, if the delays satisfy Assumption \ref{ass:subexp}, the regret can be upper bounded by
    \begin{align*}
        \operatorname{Regret}(K)\leq \Tilde{O}\left(\sqrt{\operatorname{dim}_E^2(\mathcal{F}, 1 / K) H^4  K}+ 
         H^2 \operatorname{dim}_E(\mathcal{F}, 1 / K) \mathbb{E}[\tau]\right).
    \end{align*}
\end{corollary}








\section{Results for Markov Games}
As an application, we study Markov games with delayed feedback using our framework. We first develop new multi-batched algorithms for Markov games, then combine them with our framework to obtain regret bounds for the delayed setting.

\subsection{Tabular Zero-Sum Markov Game}
First we study the tabular zero-sum Markov game setting. The algorithm is formally described in Algorithm \ref{alg:tab_game} in Appendix \ref{sec:proof_tab}. 

\iffalse
\begin{algorithm}[ht]
    \caption{Multi-batched Algorithm for Tabular Markov Game}\label{alg:tab_game}
    \begin{algorithmic}[1]
    \STATE {\bfseries Initialize:} for any $(s, a, b, h), \bar{Q}_h(s, a, b) \leftarrow H$, $\underline{Q}_h(s, a, b) \leftarrow 0, \Delta \leftarrow H, N_h(s, a, b) \leftarrow 0$, trigger set $\mathcal{L} \leftarrow\left\{2^{i-1} \mid 2^i \leq K H, i=1,2, \ldots\right\}$
    \FOR{episode $k = 1, 2, \cdots, K$}
    \IF{$\exists (h,s,a,b)$ such that $N_h^k(s,a,b) \in \mathcal{L}$}
    \FOR{step $h=H,H-1,...,1$}
    \FOR{$(s,a,b)\in \mathcal{S}\times\mathcal{A}\times\mathcal{B}$}
    \STATE Calculate bonus $b_h^k$ as in \eqref{eqn:bonus1} and \eqref{eqn:bonus2}.
    \STATE Calculate $\bar{Q}_h^k(s, a, b)$ and $\underline{Q}_h^k(s, a, b)$ by \eqref{eqn:q_est}
    \ENDFOR
    \FOR{$s\in\mathcal{S}$}
    \STATE  $\pi_h^k(\cdot, \cdot \mid s) \leftarrow \operatorname{CCE}\left(\bar{Q}_h(s, \cdot, \cdot), \underline{Q}_h(s, \cdot, \cdot)\right)$
    \STATE $\bar{V}_h(s) \leftarrow\left(\mathbb{E}_{\pi_h} \bar{Q}_h\right)(s) ; \quad \underline{V}_h(s) \leftarrow\left(\mathbb{E}_{\pi_h} \underline{Q}_h\right)(s)$
    \ENDFOR
    \ENDFOR
    \ENDIF
    \FOR{step $h=1,...,H$}
    \STATE take action $\left(a_h, b_h\right) \sim \pi_h^{k}\left(\cdot, \cdot \mid s_h\right)$, observe reward $r_h$ and next state $s_{h+1}$.
    \STATE add 1 to $N_h^k\left(s_h, a_h, b_h\right) $ and $N_h^k\left(s_h, a_h, b_h, s_{h+1}\right)$.
    \STATE Update empirical model $\widehat{\mathbb{P}}_h\left(\cdot \mid s_h, a_h, b_h\right)$
    \ENDFOR
    \ENDFOR
    \end{algorithmic}
\end{algorithm}
\fi

Our algorithm can be decomposed into two parts: an estimation step and a policy update step. The estimation step largely follows the method in \citet{liu2021sharp}. For each $(h,s,a,b)$, we maintain an optimistic estimation $\bar{Q}_h^k(s,a,b)$ and a pessimistic estimation $\underline{Q}_h^k(s,a,b)$ of the underlying $Q^{\star}_h(s,a,b)$, by value iteration with bonus using the empirical estimate of the transition $\hat{\mathbb{P}}$. 
And we compute the Coarse Correlated Equilibrium (CCE) policy $\pi$ of the estimated value functions \cite{xie2020learning}. A CCE always exists, and can be computed efficiently.

In the policy update step, we choose the CCE policy w.r.t. the current estimated value function. Note that we use the doubling trick to control the number of updates: we only update the policy when there exists $(h,s,a,b)$ such that the visiting count $N_h(s,a,b)$ is doubled. This update scheme ensures that the batch number is small.

For the regret bound of Algorithm \ref{alg:tab_game}, we have the following theorem.

\begin{theorem}\label{thm:tab_game} 
For any $p \in(0,1]$, letting $\iota=\log (S A B T / p)$, then with probability at least $1-p$, the regret of Algorithm \ref{alg:tab_game} satisfies
\begin{equation*}
\begin{aligned}
\operatorname{Regret}(K) \leq  O\left(\sqrt{H^3 S A B K \iota}+H^3 S^2 A B \iota^2\right).
\end{aligned}
\end{equation*}
and the batch number is at most $O(HSAB\log K)$.
\end{theorem}
The proof of Theorem \ref{thm:tab_game} is similar to  Theorem 4 in \citet{liu2021sharp}, but the main difference is we have to deal with the sum of the Bernstein-type bonus under the doubling framework. To deal with this we borrow idea from \citet{zhang2021reinforcement}. The whole proof is in Appendix \ref{sec:proof_tab}.


Adapting the algorithm to the delayed feedback setting using our framework, we have the following corollary.
\begin{corollary}
For tabular Markov game with delayed feedback, running Algorithm \ref{alg:protocal_delay} with $\mathcal{ALG}$ being Algorithm \ref{alg:tab_game}, we can upper bound the regret by
\begin{equation*}
\begin{aligned}
        \operatorname{Regret}(K)\leq O\left( \frac{1}{q}\left(\sqrt{H^3 S A B K \iota}+H^3 S^2 A B \iota^2\right) 
        + H^2 SAB d_{\tau}(q)\log K\right) 
        \end{aligned}
    \end{equation*}
    for any $q\in (0,1)$. In addition, if the delays satisfy Assumption \ref{ass:subexp}, the regret can be upper bounded by
    \begin{equation*}
    \begin{aligned}
        \operatorname{Regret}(K)\leq O\big(\sqrt{H^3 S A B K \iota}+H^3 S^2 A B \iota^2 +  H^2SAB \mathbb{E}[\tau]\log K\big).
        \end{aligned}
    \end{equation*}
\end{corollary}



\subsection{Linear Zero-Sum Markov Game}
We consider the linear zero-sum Markov game setting, where the reward and transition have a linear structure.
\begin{assumption}
For each $(x, a, b) \in \mathcal{S} \times \mathcal{A} \times \mathcal{B}$ and $h \in[H]$, we have
\begin{equation*}
\begin{aligned}
r_h(x, a, b)=\phi(x, a, b)^{\top} \theta_h,  \quad \mathbb{P}_h(\cdot \mid x, a, b) =\phi(x, a, b)^{\top} \mu_h(\cdot),
\end{aligned}
\end{equation*}
where $\phi: \mathcal{S} \times \mathcal{A} \times \mathcal{A} \rightarrow \mathbb{R}^d$ is a known feature map, $\theta_h \in \mathbb{R}^d$ is an unknown vector and $\mu_h=\left(\mu_h^{(i)}\right)_{i \in[d]}$ is a vector of d unknown (signed) measures on $\mathcal{S}$. We assume that $\|\phi(\cdot, \cdot, \cdot)\| \leq 1,\left\|\theta_h\right\| \leq \sqrt{d}$ and $\left\|\mu_h(\mathcal{S})\right\| \leq \sqrt{d}$ for all $h \in[H]$, where $\|\cdot\|$ is the vector $\ell_2$ norm.
\end{assumption}

\iffalse
\begin{algorithm}[H]
    \caption{Multi-batched Algorithm for linear MGs}\label{alg:lin_game}
    \begin{algorithmic}[1]
    \STATE {\bfseries Require:} regularization parameter $\lambda$
    \STATE {\bfseries Initialize:} $\Lambda_h = \Lambda_h^0 = \lambda I_d$
    \FOR{episode $k = 1, 2, \cdots, K$}
    \STATE $\Lambda_h^k = \sum_{\tau = 1}^{k - 1} \phi(s_h^\tau, a_h^\tau, b_h^\tau) \phi(s_h^\tau, a_h^\tau,b _h^\tau)^\top + \lambda I_d$
    \ENDFOR
    \IF{$\exists  h \in [H]$, $\det(\Lambda_h^k) > \eta \cdot \det(\Lambda_h)$}
    \STATE $\bar{V}_{H+1}^k \leftarrow 0$, $\underline{V}_{H+1}^k \leftarrow 0$
    \FOR{step $h = H, H - 1, \cdots, 1$}
    \STATE $\Lambda_h \leftarrow \Lambda_h^k$
    \STATE $\bar{w}_h^k \leftarrow (\Lambda_h^k)^{-1} \sum_{\tau = 1}^{k - 1} \phi(s_h^\tau, a_h^\tau, b_h^\tau) \cdot [r_h(s_h^\tau, a_h^\tau, b_h^\tau) + \bar{V}_{h+1}^k(s_{h+1}^\tau)]$
    \STATE $\underline{w}_h^k \leftarrow (\Lambda_h^k)^{-1} \sum_{\tau = 1}^{k - 1} \phi(s_h^\tau, a_h^\tau, b_h^\tau) \cdot [r_h(s_h^\tau, a_h^\tau, b_h^\tau) + \underline{V}_{h+1}^k(s_{h+1}^\tau)]$
    \STATE $\Gamma_h^k(\cdot, \cdot, \cdot) \leftarrow \beta \sqrt{\phi(\cdot, \cdot, \cdot)^\top (\Lambda_h^k)^{-1} \phi(\cdot, \cdot, \cdot)}$
    \STATE $\bar{Q}_h^k(\cdot, \cdot, \cdot) \leftarrow \Pi_{H}\{(\bar{w}_h^k)^\top \phi(\cdot, \cdot, \cdot) + \Gamma_h^k(\cdot, \cdot, \cdot)\}$
    \STATE $\underline{Q}_h^k(\cdot, \cdot, \cdot) \leftarrow \Pi_{H}\{(\underline{w}_h^k)^\top \phi(\cdot, \cdot, \cdot) - \Gamma_h^k(\cdot, \cdot, \cdot)\}$
    \STATE For each $s$, let $\sigma_h^k(x) \leftarrow \mathrm{FIND\_CCE}(\bar{Q}_h^k, \underline{Q}_h^k, s)$
    \STATE $\bar{V}_{h}^{k}(s) \leftarrow \mathbb{E}_{(a, b) \sim \sigma_{h}^{k}(s)} \bar{Q}_{h}^{k}(s, a, b)$ for each $s$
    \STATE $\underline{V}_{h}^{k}(s) \leftarrow \mathbb{E}_{(a, b) \sim \sigma_{h}^{k}(s)} \underline{Q}_{h}^{k}(s, a, b)$ for each $s$
    \ENDFOR
    \ELSE 
    \STATE $\bar{Q}_h^k \leftarrow \bar{Q}_h^{k-1}$,  $\underline{Q}_h^k \leftarrow \underline{Q}_h^{k-1}$, $\sigma_h^k \leftarrow \sigma_h^{k-1}$, $\forall h \in [H]$  
    \ENDIF
    \end{algorithmic}
\end{algorithm}
\fi

The formal algorithm is in Algorithm \ref{alg:lin_game} in Appendix \ref{sec:proof_lin}. It is also divided into two parts. The estimation step is similar to that in \citet{xie2020learning}, where we  calculate an optimistic estimation $\bar{Q}_h^k(s,a,b)$ and a pessimistic estimation $\underline{Q}_h^k(s,a,b)$ of the underlying $Q^{\star}_h(s,a,b)$ by least square value iteration. And we compute the CCE policy $\pi$ of the estimated value functions.

In the policy update step, we update the policy to the CCE policy w.r.t. the current estimated value function. Note that instead of updating the policy in every episode, we only update it when there exists $  h \in [H]$ such that $\det(\Lambda_h^k) > \eta \cdot \det(\Lambda_h)$. This condition implies that we have collected enough information at one direction. This technique is similar to \citet{gao2021provably,wang2021provably}.

For the regret bound of Algorithm \ref{alg:lin_game}, we have the following theorem.

\begin{theorem} \label{thm:linear:mg:switching}
In Algorithm \ref{alg:lin_game}, let $\eta=2$. Then we have 
\begin{align*}
        \operatorname{Regret}(K) \le \tilde{{O}}(\sqrt{ d^3 H^4 K}).
\end{align*}
And the batch number of Algorithm \ref{alg:lin_game} is
$ \frac{dH}{\log 2} \log\left(1 + \frac{K}{\lambda}\right) $.
\end{theorem}

\begin{proof}
     See Appendix~\ref{sec:proof_lin} for a detailed proof.
\end{proof}

Adapting the algorithm to the delayed feedback setting using our framework, we have the following corollary.

\begin{corollary}
For linear Markov game with delayed feedback, running Algorithm \ref{alg:protocal_delay} with $\mathcal{ALG}$ being Algorithm \ref{alg:lin_game}, we can upper bound the regret by
\begin{align*} 
        \operatorname{Regret}(K)\leq \Tilde{O}\left( \frac{1}{q}\sqrt{ d^3 H^4 K}  + dH^2 d_{\tau}(q)\log K\right) 
    \end{align*}
    for any $q\in (0,1)$. In addition, if the delays satisfy Assumption \ref{ass:subexp}, the regret can be upper bounded by
    \begin{align*}
        \operatorname{Regret}(K)\leq \Tilde{O}\left(\sqrt{ d^3 H^4 K} +  dH^2 \mathbb{E}[\tau]\log K\right).
    \end{align*}
\end{corollary}



\subsection{Tabular General-Sum Markov Game}
In this section, we introduce the multi-batched version of V-learning \citep{jin2021v,mao2022provably,song2021can} for general-sum Markov games. Our goal is to minimize the regret \eqref{eqn:regret_gen}. The algorithm is formally described in Algorithm \ref{alg:vlearning} in Appendix \ref{sec:proof_tab}.

The multi-batched V-learning algorithm maintains a value estimator $V_h(s)$, a counter $N_h(s)$, and a policy $\pi_h(\cdot \mid s)$ for each $s$ and $h$. We also maintain $S \times H$ different adversarial bandit algorithms. At step $h$ in episode $k$, the algorithm is divided into three steps: policy execution, $V$-value update, and policy update. In policy execution step, the algorithm takes action $a_h$ according to $\pi_h^{\Tilde{k}}$, and observes reward $r_h$ and the next state $s_{h+1}$, and updates the counter $N_h\left(s_h\right)$. Note that $\pi_h^{\Tilde{k}}$ is updated only when the visiting count of some state $N_h(s)$ doubles. Therefore it ensures a low batch number. 

In the $V$-value update step, we update the estimated value function by
\begin{align*}
\tilde{V}_h\left(s_h\right) = \left(1-\alpha_t\right) \tilde{V}_h\left(s_h\right)+\alpha_t\left(r_h+V_{h+1}\left(s_{h+1}\right) + \beta (t)\right),
\end{align*}
where the learning rate is defined as
\begin{align*}
\alpha_t=\frac{H+1}{H+t}, \quad  \alpha_t^0=\prod_{j=1}^t\left(1-\alpha_j\right),  \quad \alpha_t^i=\alpha_i \prod_{j=i+1}^t\left(1-\alpha_j\right).
\end{align*}
and $\beta (t)$ is the bonus to promote optimism.

In the policy update step, the algorithm feeds the action $a_h$ and its "loss" $\frac{H-r_h+V_{h+1}\left(s_{h+1}\right)}{H}$ to the $\left(s_h, h\right)^{\text {th }}$ adversarial bandit algorithm. Then it receives the updated policy $\pi_h\left(\cdot \mid s_h\right)$.

For two-player general sum Markov game, we let the two players run Algorithm \ref{alg:vlearning} independently. Each player use its own set of bonus that depends on the number of its actions. We have the following theorem for the regret of multi-batched V-learning.

\begin{theorem}
Suppose we choose adversarial bandit algorithm as FTRL. For any $\delta \in(0,1)$ and $K \in \mathbb{N}$, let $\iota=\log (H S A K / \delta)$. Choose learning rate $\alpha_t$ and bonus $\left\{\beta (t)\right\}_{t=1}^K$ as $\beta (t)=c \cdot \sqrt{H^3 A \iota / t}$ so that $\sum_{i=1}^t \alpha_t^i \beta (i)=\Theta\left(\sqrt{H^3 A \iota / t}\right)$ for any $t \in[K]$, where $A=\max_i A_i$ Then, with probability at least $1-\delta$, after running Algorithm \ref{alg:vlearning} for $K$ episodes, we have
\begin{align*}
    \operatorname{Regret}(K)\leq O\left(\sqrt{H^5SA\iota} \right).
\end{align*}
And the batch number is $O(nHS\log K)$, where $n$ is the number of players.
\end{theorem}

Finally, adapting the algorithm to the delayed feedback setting using our framework, we have the following corollary.
\begin{corollary}
For tabular general-sum Markov game with delayed feedback, running Algorithm \ref{alg:protocal_delay} with $\mathcal{ALG}$ being Algorithm \ref{alg:vlearning}, we can upper bound the regret by
\begin{align*}
        \operatorname{Regret}(K)\leq  O\big( \frac{1}{q}\sqrt{H^5SA\iota}  
        + H^2 nS d_{\tau}(q)\log K\big) 
        \end{align*}
    for any $q\in (0,1)$. In addition, if the delays satisfy Assumption \ref{ass:subexp}, the regret can be upper bounded by
    \begin{align*}
        \operatorname{Regret}(K)\leq O\big(\sqrt{H^5SA\iota} 
        +  H^2nS \mathbb{E}[\tau]\log K\big).
        \end{align*}
\end{corollary}

\section{Introduction}

Delayed feedback is a common and fundamental problem in (multi-agent) sequential decision making \citep{sutton2018reinforcement,lattimore2020bandit,zhang2021multi}. Taking the recommendation system as an example, delayed feedback is an inherent part of this problem. Specifically, the learner adjusts her recommendation after receiving users' feedback, which may take a random delay after the recommendation is issued. More examples include but are not limited to robotics \citep{mahmood2018setting} and video steaming \citep{changuel2012online}. Furthermore, the delayed feedback issue is more serious in multi-agent systems \citep{chen2020delay} since observing the actions of other agents' may happen with a varying delay. 


Although handling delayed feedback is a prominent challenge in practice, the theoretical understanding of delays in sequential decision making is limited. Even assuming the delays are stochastic  (delays are sampled from a fixed distribution), the nearly minimax optimal result is only obtained by works on multi-armed bandits and contextual bandits \citep{agarwal2011distributed,dudik2011efficient,joulani2013online,vernade2020linear,vernade2017stochastic,gael2020stochastic}. 
For more complex problems such as linear bandits \citep{lancewicki2021stochastic} and tabular reinforcement learning (RL) \citep{howson2022delayed}, the results are suboptimal. Meanwhile, to the best of our knowledge, there is no theoretical gurantees  in RL with function approximation and multi-agent RL settings. Hence, we focus on stochastic delays and aim to answer the following two questions in this work:
\begin{center}
    1. Can we provide sharper regret bounds for basic models such as linear bandits and tabular RL? \\
    2. Can we handle delays in (multi-agent) sequential decision making in the context of function approximation?
\end{center}

We answer these two questions affirmatively by proposing a reduction-based framework for stochastic delays in (multi-agent) sequential decision making. Our contributions are summarized below.




\begin{table*}[t!]
	\centering

	\footnotesize
		\renewcommand{\arraystretch}{1.5}
		\begin{tabular}[0.6\textwidth]{|c|c|c|}
		\hline
		Setting & Previous Result & \makecell{This Work}\\
		\hline\hline
		\multirow{2}{*}{\makecell{Multi-armed\\ bandit}} &
            \multirow{2}{*}{\makecell{$O(\frac{A\log(K)}{q\min _{i \neq \star} \Delta_i}+d_{\tau}(q)\log K)$\\{\scriptsize \citep{lancewicki2021stochastic}}}}
		&
			
				$O\left(\frac{A \log K}{q\min _{i \neq \star} \Delta_i} + \frac{\log^2 K }{q} +  d_{\tau}(q) \log K \right)$
		\\
		\cline{3-3}
  &
		&\makecell{$O\left(\frac{A \log K}{\min _{i \neq \star} \Delta_i} +  \mathbb{E}[\tau]\log K\right)$}
		\\
		\hline
    \multirow{2}{*}{\makecell{Linear\\ bandit}} &
            \multirow{2}{*}{\makecell{$\Tilde{O}(d\sqrt{K}+d^{3/2} \mathbb{E}[\tau])$\\{\scriptsize \citep{howson2021delayed}}}}
		&
			
				$\Tilde{O}\left(\frac{1}{q}d\sqrt{K} +  d_{\tau}(q) \right)$
		\\
		\cline{3-3}
  &
		&\makecell{$\Tilde{O}(d\sqrt{K}+\mathbb{E}[\tau])$}
		\\
		\hline
  \multirow{2}{*}{\makecell{Tabular\\ MDP}} &
            \multirow{2}{*}{\makecell{$\Tilde{O}(\sqrt{H^3 S A K }+H^2 S A \mathbb{E}[\tau]\log K )$ \\{\scriptsize \citep{howson2022delayed}}}}
		&
			
				$\Tilde{O}\left(\frac{1}{q}\sqrt{S A H^3 K }  +  H(H+\log \log K)d_{\tau}(q)  \right)$
		\\
		\cline{3-3}
  &
		&\makecell{$\Tilde{O}\left(\sqrt{S A H^3 K }+ H (H+\log \log K)\mathbb{E}[\tau]\right)$}
		\\
		\hline
  \multirow{2}{*}{\makecell{Linear\\ MDP}} &
            \multirow{2}{*}{\makecell{---}}
		&
			
				$\Tilde{O}\big(\frac{1}{q}\sqrt{d^3 H^4 K}  
        +  d H^2 d_{\tau}(q)\log K  \big)$
		\\
		\cline{3-3}
  &
		&\makecell{$\Tilde{O}(\sqrt{d^3 H^4 K}+d H^2 \mathbb{E}[\tau])$}
		\\
		\hline
  \multirow{2}{*}{\makecell{RL with general \\ function approximation}} &
            \multirow{2}{*}{\makecell{---}}
		&
			
				$\Tilde{O}\big(\frac{1}{q}\sqrt{\operatorname{dim}_E^2(\mathcal{F}, 1 / K) H^4 K} +  
         H^2\operatorname{dim}_E(\mathcal{F}, 1 / K) d_{\tau}(q)  \big)$
		\\
		\cline{3-3}
  &
		&\makecell{$\Tilde{O}\left(\sqrt{\operatorname{dim}_E^2(\mathcal{F}, 1 / K)  H^4  K}+H^2\operatorname{dim}_E(\mathcal{F}, 1 / K)\mathbb{E}[\tau]\right)$}
		\\
		\hline
\multirow{2}{*}{\makecell{Tabular two-player \\ zero-sum MG}} &
            \multirow{2}{*}{\makecell{---}}
		&
		$\Tilde{O}\big( \frac{1}{q}\left(\sqrt{H^3 S A B K }+H^3 S^2 A B \right) 
        + H^2 SAB d_{\tau}(q)\log K\big) $
		\\
		\cline{3-3}
  &
		&\makecell{$\Tilde{O}\big(\sqrt{H^3 S A B K }+H^3 S^2 A B  
        +  H^2SAB \mathbb{E}[\tau]\log K\big).$}
		\\
		\hline
\multirow{2}{*}{\makecell{Linear two-player\\ zero-sum MG}} &
            \multirow{2}{*}{\makecell{---}}
		&
			
				$\Tilde{O}\left( \frac{1}{q}\sqrt{ d^3 H^4 K}  + dH^2 d_{\tau}(q)\log K\right) $
		\\
		\cline{3-3}
  &
		&\makecell{$\Tilde{O}\left(\sqrt{ d^3 H^4 K} +  dH^2 \mathbb{E}[\tau]\log K\right)$}
		\\
		\hline
\multirow{2}{*}{\makecell{Tabular multi-player \\ general-sum MG}} &
            \multirow{2}{*}{\makecell{$\tilde{O}\left(H^3 \sqrt{S AK} + H^3 \sqrt{S \mathbb{E}[\tau]K}\right)$ \\{\scriptsize \citep{zhang2022multi}}} }
		&
		$\Tilde{O}\big( \frac{1}{q}\sqrt{H^5SAK}  
        + H^2 nS d_{\tau}(q)\log K\big) $
		\\
		\cline{3-3}
  &
		&\makecell{$\Tilde{O}\big(\sqrt{H^5SAK} 
        +  H^2nS \mathbb{E}[\tau]\log K\big)$}
		\\
            \hline

		\end{tabular}

	\vspace{0.04in}
	\caption[]{
		Comparison of bounds for MSDM with delayed feedback. We denote by $K$  the number of rounds the agent plays (episodes in RL), $A$ and $B$ the number of actions (or arms), $S$ the number of states, $H$ the length of an episode, $d$ the linear feature dimension, and $\operatorname{dim}_E(\mathcal{F}, 1 / K)$ the eluder dimension of general function class $\mathcal{F}$, $\mathcal{T}_K$ is the measure of the total delay, $d_{\tau}(q)$ is the quantile function of the random variable $\tau$ and $n$ is the number of players.
	}
\label{tab:regret.bounds}

\end{table*}


\paragraph{Our Contributions.}  Our main contribution is proposing a new reduction-based framework for (multi-agent) sequential decision making with stochastic delayed feedback. The proposed framework can convert any multi-batched algorithm (cf. Section~\ref{sec:multi:batch}) for sequential decision making with instantaneous feedback to a provably efficient algorithm that is capable of handling stochastic delayed feedback in sequential decision making. Unlike previous works that use different algorithms and analyses, we provide a unified framework to solve a wide range of problems all together.

Based on this framework, we obtain a complete set of results for (multi-agent) sequential decision making with delayed feedback. In specific, 
\begin{itemize}
    \item We derive sharper results for linear bandits and tabular RL, which significantly improve existing results \citep{lancewicki2021stochastic,howson2022delayed};
    \item We provide the first result for single-agent RL with delayed feedback in the context of linear or even general function approximation;
    \item We show that delayed feedback in Markov games (MGs) can also be handled by our framework. By plugging several new proposed multi-batched algorithms for MGs into our framework, we not only improve recent results on tabular MGs \citep{zhang2022multi}, but also present a new result for linear MGs. As a byproduct, we provide the first line of study on multi-batched algorithms for MGs, which might be of independent interest.
\end{itemize}
Our results and comparisons with existing works are summarized in Table~\ref{tab:regret.bounds}.


\iffalse
\begin{itemize}
    \item delay common and fundamental problem; applications
    \item Although sequential decision making with immediate feedback is relatively well-understood, there is limited literature on sequential decision making with delayed feedback. bandits and tabular RL not tight, there is no result for delayed RL with function approximation
    \item Question: Can we design a theoretical framework for (multi-agent) sequential decision making with delayed feedback? 
    \item our contribution: (i) framework (ii) improves previous results of linear bandits and tabular RL; (iii) first result for linear RL and general function approximation; (iv) present the first line of results of multi-agent RL with delayed feedback. As a byproduct, we propose the first low-switching cost algorithms for markov games.  
\end{itemize}
\fi 


\section{Multi-batched Algorithm for MSDMs} \label{sec:multi:batch}
In this section we mainly discuss multi-batched algorithms for MSDMs. This section aims to provide a formal definition of multi-batched algorithm, and give some examples of multi-batched algorithm for the ease of understanding.

Formally, a multi-batched algorithm consists of several batches. At the beginning of each batch, the algorithm outputs a policy $\pi$ (or a sequence of policies) for this batch using data collected in previous batches, along with a stopping criteria $SC$, which is a mapping from a dataset to a boolean value. Then the agent executes $\pi$ (or the predefined policy sequence) for several episodes and collect feedback to the current dataset $\mathcal{D}$, until the stopping criteria is satisfied (i.e. $SC(\mathcal{D}) = 1$).  Algorithm \ref{alg:protocal} describes a protocol of multi-batched algorithm.


\begin{algorithm}
    \caption{Protocol of Multi-batched Algorithm}\label{alg:protocal}
    \begin{algorithmic}[1]
    \STATE Initialize dataset $\mathcal{D}^{0} = \emptyset$
    \FOR{batch $m=1,...,M$}
    \STATE $\mathcal{D}=\emptyset$
    \STATE Calculate a policy $\pi^m$ (or a policy sequence) using previous data $\mathcal{D}^{m-1}$, and a stopping criteria $SC$
    \WHILE{$SC(\mathcal{D})=0$}
    \STATE $k\leftarrow k+1$
    \STATE In episode $k$, execute $\pi^m$ and collect trajectory feedback $o^k$
    \STATE $\mathcal{D}=\mathcal{D} \cup \{o^k\} $
    \ENDWHILE
    \STATE Update dataset $\mathcal{D}^{m} = \mathcal{D}^{m-1}\cup \mathcal{D}$
    \ENDFOR
    \end{algorithmic}
\end{algorithm}

Note that the major requirement is that the policy to be executed during the batch should be calculated at the beginning of the batch. Therefore, algorithms that updates the policy at each episode do not satisfy this requirement. For example, UCB algorithms in bandits \cite{lattimore2020bandit} and UCBVI \cite{azar2017minimax} are not multi-batched algorithms.

\paragraph{Relation with low-switching cost algorithm} Our definition of multi-batched algorithm is similar to that of low-switching cost algorithm, but is more general. 

For any algorithm, the switching cost is the number of policy changes in the running of the algorithm in $K$ episodes, namely:
\begin{equation*}
N_{\text {switch }} \triangleq \sum_{k=1}^{K-1} \mathbb{I}\left\{\pi_k \neq \pi_{k+1}\right\}.
\end{equation*}

Most algorithms with $N_{\text {switch }}$ low-switching cost are multi-batched algorithms with $N_{\text {switch }}$ batches. For example, the policy elimination algorithm proposed in \citet{zhang2022near} is a multi-batched algorithm with $2H+\log\log K$ batches. And the algorithm for linear MDP with low global switching cost in \citet{gao2021provably} is a multi-batched algorithm with $O(d H \log K)$ batches. On the other hand, the difference between batches and switching cost is that we do not require the policy to be consistent during a batch. Therefore, a multi-batched algorithm with $N$ batches may not be an algorithm with $N$ switching cost. For example, the Phase Elimination Algorithm in linear bandit with finite arms setting \cite{lattimore2020bandit} is a multi-batched algorithm with $O(\log K)$ batches, but the switching cost is $O(A\log K)$ which is much larger.





\section{Preliminary}
The objective of this section is to provide a unified view of the settings considered in this paper, i.e., bandits, Markov Decision Processes (MDPs) and multi-agent Markov Games. We consider a general framework for interactive decision making, which we refer to as Multi-agent Sequential Decision Making (MSDM). 

\paragraph{Notations}
We begin by introducing some basic notations. We use $\Delta(\cdot)$ to represent the set of all probability distributions on a set. For $n \in \mathbb{N}_{+}$, we denote $[n]=\{1,2, \ldots, n\}$. We use $O(\cdot), \Theta(\cdot), \Omega(\cdot)$ to denote the big-O, big-Theta, big-Omega notations. We use $\widetilde{O}(\cdot)$ to hide logarithmic factors.

\paragraph{Multi-agent Sequential Decision Making} A Multi-agent Sequential Decision Making problem can be represented as a tuple $M=(n, \mathcal{S}, \{\mathcal{A}_{i}\}_{i=1}^{n} , H, \{p_h\}_{h=1}^H, s_1, \{r_h\}_{h=1}^H)$, where $n$ is the number of agents, $\mathcal{S}$ is the state space, $\mathcal{A}_{i}$ is the action space of player $i$, $H$ is the length of each episode and $s_1$ is the initial state. We define $\mathcal{A} = \bigotimes_i \mathcal{A}_i$ as the whole action space.

At each stage $h$, for every player $i$, every state-action pair $(s, a_1, ..., a_n)$ is characterized by a reward distribution with mean $r_{i,h}(s, a_1, ..., a_n)$ and support in $\left[0, 1\right]$, and a transition distribution $p_h(\cdot | s, a)$ over next states. We denote by $S=|\mathcal{S}|$ and $A_i=|\mathcal{A}_i|$.

The protocol proceeds in several episodes. At the beginning of each episode, the environment starts with initial state $s_1$. At each step $h\in [1,H]$, the agents observe the current state $s_h$, and take their actions $(a_1,..., a_n)$ respectively. Then the environment returns a reward signal, and transits to next state $s_{h+1}$.

A (random) policy $\pi_i$ of the $i^{\text {th }}$ player is a set of $H$ maps $\pi_i:=\left\{\pi_{i, h}: \Omega \times \mathcal{S} \rightarrow \mathcal{A}_i\right\}_{h \in[H]}$, where each $\pi_{i, h}$ maps a random sample $\omega$ from a probability space $\Omega$ and state $s$ to an action in $\mathcal{A}_i$. A joint (potentially correlated) policy is a set of policies $\left\{\pi_i\right\}_{i=1}^m$, where the same random sample $\omega$ is shared among all agents, which we denote as $\pi=\pi_1 \odot \pi_2 \odot \ldots \odot \pi_m$. We also denote $\pi_{-i}$ as the joint policy excluding the $i^{\text {th }}$ player. For each stage $h \in [H]$ and any state-action pair $(s,a)\in \mathcal{S}\times\mathcal{A}$, the value function and Q-function of a policy $\pi$ are defined as:
\begin{align*}
    Q^\pi_{i,h}(s,a)=\mathbb{E}\left[\sum_{h'=h}^H r_{i,h'}|s_h=s,a_h=a,\pi \right], \quad 
    V_{i,h}^{\pi}(s)=\mathbb{E}\left[\sum_{h'=h}^H r_{i,h'}|s_h=s,\pi \right].
\end{align*}
For each policy $\pi$, we define $V_{H+1}^{\pi}(s)=0$ and $Q_{H+1}^{\pi}(s,a)=0$ for all $s\in\mathcal{S},a\in\mathcal{A}$. Sometimes we omit the index $i$ when it is clear from the context.

For the single agent case ($n=1$), the goal of the learner is to maximize the total reward it receives. There exists an optimal policy $\pi^\star$ such that $Q^\star_h(s,a)=Q^{\pi^\star}_h(s,a)=\max_\pi Q^\pi_h(s,a)$ satisfies the optimal Bellman equations 
\begin{align*}
    Q^\star_h(s,a) = r_h(s,a) + \mathbb{E}_{s' \sim p_h(s,a)}[V^\star_{h+1}(s')], \quad 
    V^\star_h(s) = \max_{a\in\mathcal{A}} \{Q^\star_h(s,a)\}, \quad \forall (s, a) \in \mathcal{S} \times \mathcal{A} .
\end{align*}
Then the optimal policy is the greedy policy $\pi^\star_h(s) = \arg\max_{a\in\mathcal{A}} \{Q_h^\star(s,a)\}$. And we evaluate the performance of the learner through the notion of single-player regret, which is defined as
\begin{equation}\label{eq:regret}
    \operatorname{Regret}(K)=\sum_{k=1}^{K} \left(V^\star_1 -V^{\pi_{k}}_1\right)(s_1).
\end{equation}
In the case of multi-player general-sum MGs, for any policy $\pi_{-i}$, the best response of the $i^{\text {th }}$ player is defined as a policy of the $i^{\text {th }}$ player which is independent of the randomness in $\pi_{-i}$, and achieves the highest value for herself conditioned on all other players deploying $\pi_{-i}$. In symbol, the best response is the maximizer of $\max _{\pi_i^{\prime}} V_{i, 1}^{\pi_i^{\prime} \times \pi_{-i}}\left(s_1\right)$ whose value we also denote as $V_{i, 1}^{\dagger, \pi_{-i}}\left(s_1\right)$ for simplicity. 

For general-sum MGs, we aim at learning the Coarse Correlated Equilibrium (CCE), which is defined as a joint (potentially correlated) policy where no player can increase her value by playing a different independent strategy. In symbol,
\begin{definition}[Coarse Correlated Equilibrium]
A joint policy $\pi$ is a CCE if $\max _{i \in[m]}\left(V_{i, 1}^{\dagger, \pi_{-i}}-V_{i, 1}^\pi\right)\left(s_1\right)=$ 0. A joint policy $\pi$ is a $\epsilon$-approximate CCE if $\max _{i \in[m]}\left(V_{i, 1}^{\dagger, \pi_{-i}}-V_{i, 1}^\pi\right)\left(s_1\right) \leq \epsilon$.
\end{definition}
For any algorithm that outputs policy $\hat{\pi}^{k}$ at episode $k$, we measure the performance of the algorithm using the following notion of regret:
\begin{equation}\label{eqn:regret_gen}
    \operatorname{Regret}(K)=\sum_{k=1}^{K} \max_{j} \Big(V_{j, h}^{\dagger, \hat{\pi}_{-j, h}^k} - V_{j, h}^{\hat{\pi}_h^k} \Big)(s_1).
\end{equation}
One special case of multi-player general-sum MGs is two-player zero-sum MGs, in which there are only two players and the reward satisfies $r_{2,h}=-r_{1,h}$. In zero-sum MGs, there exist policies 
that are the best response to each other. We call these optimal strategies the Nash equilibrium of the Markov game, which satisfies the following minimax equation:
\begin{equation*}
\sup _\mu \inf _\nu V_h^{\mu, \nu}(s)=V_h^{\mu^{\star}, \nu^{\star}}(s)=\inf _\nu \sup _\mu V_h^{\mu, \nu}(s).
\end{equation*}
We measure the suboptimality of any pair of general policies $(\hat{\mu}, \hat{\nu})$ using the gap
between their performance and the performance of the optimal strategy (i.e., Nash equilibrium) when playing
against the best responses respectively:
\begin{equation*}
\begin{aligned}
V_1^{\dagger, \hat{\nu}}\left(s_1\right)-V_1^{\hat{\mu}, \dagger}\left(s_1\right) 
=\left[V_1^{\dagger, \hat{\nu}}\left(s_1\right)-V_1^{\star}\left(s_1\right)\right]+\left[V_1^{\star}\left(s_1\right)-V_1^{\hat{\mu}, \dagger}\left(s_1\right)\right] .
\end{aligned}
\end{equation*}

Let $\left(\mu^k, \nu^k\right)$ denote the policies deployed by the algorithm in the $k^{\text {th }}$ episode. The learning goal is to minimize the two-player regret of $K$ episodes, defined as
\begin{equation}\label{eqn:regret_zero}
\operatorname{Regret}(K)=\sum_{k=1}^K\left(V_1^{\dagger, \nu^k}-V_1^{\mu^k, \dagger}\right)\left(s_1\right).
\end{equation}
One can see that \eqref{eqn:regret_zero} is a natural reduction of \eqref{eqn:regret_gen} from general-sum game to zero-sum game.


\paragraph{MSDM with Delayed Feedback} We focus on the case where there is delay between playing an episode and observing the sequence of states, actions and rewards sampled by the agent; we refer to this sequence as feedback throughout this paper.

We assume that the delays are stochastic, i.e. we introduce a random variable for the delay between playing the $k$-th episode and observing the feedback of the $k$-th episode, which we denote by $\tau_k$. We assume the delays are i.i.d:
\begin{assumption}
    The delays $\{\tau_k\}_{k=1}^{k}$ are positive, independent and identically distributed random variables: $\tau_k \stackrel{i.i.d.}{\sim} f_\tau(\cdot)$. We denote the expectation of $\tau$ as $\mathbb{E}[\tau]$ (which may be infinite), and denote the quantile function of $\tau$ as $d_{\tau}(q)$, i.e.
    \begin{equation}
d_{\tau}(q)=\min \left\{\gamma \in \mathbb{N} \mid \operatorname{Pr}\left[\tau \leq \gamma\right] \geq q\right\}.
\end{equation}
\end{assumption}
When delay exists, the feedback associated with an episode does not return immediately. Instead, the feedback of the $k$-th episode cannot be observed until the $k+\tau_k$-th episode ends. 

Sometimes in order to control the scale and distribution of the delay, we make the assumption that the delays are $(v,b)$ subexponential random variables. This is a standard assumption used in previous works \cite{howson2021delayed}, though it is not always necessary in our paper.

\begin{assumption}\label{ass:subexp}
     The delays are non-negative, independent and identically distributed $(v, b)$-
subexponential random variables. That is, their moment generating function satisfies the following inequality
\begin{equation}
\mathbb{E}\left[\exp \left(\gamma\left(\tau_t-\mathbb{E}\left[\tau_t\right]\right)\right)\right] \leq \exp \left(\frac{1}{2} v^2 \gamma^2\right)
\end{equation}
for some $v$ and $b$, and all $|\gamma| \leq 1 / b$.
\end{assumption}


\subsection{Related Works}
\paragraph{Bandit/MDP with delayed feedback.}
Stochastically delayed feedback has been studied a lot in the multi-armed bandit and contextual bandit problems \citep{agarwal2011distributed,dudik2011efficient,joulani2013online,vernade2020linear,vernade2017stochastic,gael2020stochastic}. A recent work \citep{lancewicki2021stochastic} shows that under stochastic delay, elimination algorithm performs better than UCB algorithm, and gives tight upper and lower bounds for multi-armed bandit setting. \citet{howson2021delayed} solves the linear bandit setting by adapting LinUCB algorithm.

In RL, despite practical importance, there is limited literature on stochastical delay in RL. \citet{lancewicki2022learning} and \citet{jin2022near} considered adversarial delays. Their regret depends on the sum of
the delays, the number of states and the number of steps per episode. However, when reducing their results to stochastic delay, the bounds will be too loose. \citet{howson2022delayed} considered stochastic delay in tabular MDP, but their bound is not tight. As far as we know, there is no work considering linear MDP and general function approximation with delayed feedback.

\paragraph{Low switching cost algorithm.} 
Bandit problem with low switching cost is widely studied in past decades. \citet{cesa2013online} showed an $\tilde{\Theta}\left(K^{\frac{2}{3}}\right)$ regret bound under adaptive adversaries and bounded memories. \citet{perchet2016batched} proved a regret bound of $\tilde{\Theta}\left(K^{\frac{1}{1-2^{1-M}}}\right)$ for the two-armed bandit problem within $M$ batches, and later \citet{gao2019batched} extended their result to the general $A$-armed case.

In RL, by doubling updates, the global switching cost is $O\left(S A H \log _2(K)\right)$ while keeping the regret $\tilde{O}\left(\sqrt{S A K H^3}\right)$ \citep{azar2017minimax}.  Recently \citet{zhang2022near} proposed a policy elimination algorithm that achieves $\tilde{O}\left(\sqrt{S A K H^3}\right)$ regret and $O\left(H+\log _2 \log _2(K)\right)$ switching cost. Besides, \citet{gao2021provably} generalized the problem to Linear RL, and established a regret bound of $\tilde{O}\left(\sqrt{d^3 H^4 K}\right)$ with $O(d H \log (K))$ global switching cost. Recent work \citet{qiao2022sample} achieved $O\left(H S A \log _2 \log _2(K)\right)$ switching cost and $\tilde{O}(\operatorname{poly}(S, A, H) \sqrt{K})$ regret with a computational inefficient algorithm. And \citet{kong2021online} consider MDP with general function approximation setting.

\paragraph{Learning Markov games.} 
A standard framework to capture multi-agent RL is Markov games (also known as stochastic games) \citep{shapley1953stochastic}. For two-player zero-sum Markov games, the goal is to solve for the Nash equilibrium (NE) \citep{nash1951non}. 
Recently, many works study this problem under the generative model \citep{zhang2020model,li2022minimax}, offline setting \citep{cui2022offline,cui2022provably,zhong2022pessimistic,xiong2022nearly,yan2022model}, and online setting \citep{bai2020provable,bai2020near,liu2021sharp,tian2021online,xie2020learning,chen2021almost,jin2022power,xiong22b,huang2021towards}. 
Our work is mostly related to \citet{liu2021sharp} and \citet{xie2020learning}. Specifically, \citet{liu2021sharp} studies online tabular two-player zero-sum MGs and proposed an algorithm with $O(\sqrt{SABH^3K})$ regret. \citet{xie2020learning} focused on online linear MGs provide an algorithm that enjoys $O(\sqrt{d^3H^4K})$ regret. We also remark that  \citet{jin2022power,xiong22b,huang2021towards} establish sharper regret bound for linear MGs but the algorithms therein are computationally inefficient. There is also a line of works \citep{liu2021sharp,jin2021v,song2021can,zhong2021can,mao2022provably,cui2022offline,jin2022complexity,daskalakis2022complexity} studying multi-player general-sum MGs. Among these works, \citet{jin2021v,song2021can,mao2022provably} use V-learning algorithms to solve coarse correlated equilibrium (CCE). 
 But all these algorithms can not handle delayed feedback nor are multi-batched algorithms that can be plugged into our framework. To this end, we present the first line of studies on multi-batched algorithms for MGs and provide a complete set of results for MGs with delayed feedback.

A very recent but independent work \citep{zhang2022multi} also studies multi-agent reinforcement learning with delays. They assume that the reward is delayed, and aim to solve for coarse correlated equilibrium (CCE) in general-sum Markov games. Our work has several differences from \citet{zhang2022multi}.  First, they study the setting where the total delay is upper bounded by a certain threshold, while we focus on the setup with stochastic delay. Besides, their method seems only applicable for reward delay, while we allow the whole trajectory feedback to be delayed. Second, in the stochastic delay setting the delay-dependent term in their bound is worse than ours. Specifically,  their bound scales as $O(H^3\sqrt{S\mathbb{E}[\tau]K})$, while ours is $O(H^2nS\mathbb{E}[\tau])$ where $n$ is the number of players. Finally, it seems that their results cannot be extended to the multi-agent RL with function approximation.
