A Reduction-based Framework for Sequential Decision Making with Delayed Feedback
Authors: Yunchang Yang
Han Zhong
Tianhao Wu
Bin Liu
Liwei Wang
Simon Shaolei Du
Venue: NeurIPS 2023 poster (2023)
Keywords: sequential decision making
delay
reinforcement learning
TL;DR: We provide a complete set of sharp results for multi-agent sequential decision making with delayed feedback using a reduction-based framework.

Abstract: We study stochastic delayed feedback in general single-agent and multi-agent sequential decision making, which includes bandits, single-agent Markov decision processes (MDPs), and Markov games (MGs). 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. By plugging different multi-batched algorithms into our framework, we provide several examples demonstrating that our framework not only matches or improves existing results for bandits, tabular MDPs, and tabular MGs, but also provides the first line of studies on delays in sequential decision making with function approximation. In summary, we provide a complete set of sharp results for single-agent and multi-agent sequential decision making with delayed feedback.

A Reduction-based Framework for Sequential Decision Making with Delayed Feedback
Yunchang Yang! Han Zhong' Tianhao 2u Bin Liu Liwei Wang
Simon S. Du
CCenter for Data Science, Peking University University of California, Berkeley 3Zhejiang Lab National Key Laboratory of General Artificial Intelligence, School of Intelligence Science and Technology, Peking University 5 University of Washington
Abstract
We study stochastic delayed feedback in general sequential decision-making prob- lems, which include bandits, single-agent Markov decision processes (MDPs), and Markov games (MGs). We propose a novel reduction-basse based framework. which turns any multi-batched algorithm for sequential decision making with instanta- neous feedback into a sample-efficient algorithm that can handle stochastic delays in sequential decision-making problems. By plugging different multi-batched algo- rithms into our framework, we provide several examples demonstrating that our framework not only matches or improves existing results for bandits, tabular MDPs, and tabular MGs, but also provides the first line studies on delays sequential decision making with function approximation. In summary, we provide a complete set of sharp results for single-agent and multi-agent sequential decision-making problems with delayed feedback.
Introduction
Delayed feedback is a common and fundamental problem in sequential decision making (Sutton and Barto, 2018; Lattimore and Szepesvári, 2020; Zhang et al., 2021a). Taking the recommendation system an example, delayed feedback is an inherent part of this problem. Specifically, the learner adjusts her recommendation after receiving users' feedback, which may take random delay after the recommendation is issued. More examples include but are not limited to robotics (Mahmood et al., 2018) and video steaming (Changuel et al., 2012). Furthermore, the delayed feedback issue is more serious in multi-agent systems (Chen et al., 2020) since observing the actions of other agents' may happen with a varying delay.
Although handling delayed feedback is prominent challenge in practice, the theoretical understand- ing 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 armee bandits and contextual bandits (Agarwal and Duchi, 2011; Dudik al., 2011; Joulani et al., 2013; Vernade et al., 2020, 2017: Gael et al., 2020). For more complex problems such as linear bandits (Lancewicki et al., 2021) and tabular reinforcement learning (RI.) (Howson et al., 2022), the results are suboptimal. Meanwhile, to the best of our knowledge, there are no theoretical guarantees 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:
1. Can we provide sharper regret bounds for basic models such as linear bandits and tabular RL?
'Equal contribution. Correspondence Yunchang Yang (yangyc&pku. edu. en) and Han Zhong "hanzhong@stu. pw..pku..ee edu.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Table 1: 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), Amax = max; A,, S the number of states, H the length of an episode, d the linear feature dimension, and dimg(F, 1/K) the eluder dimension of general function class F, dz (q) is the quantile function of the random variable and is the number of players.
Setting
Previous Result
This Work
Multi-armed bandit
Alox(() 0f, miniy &, + d, (q) log K)
gmilge & + Inx d- d-)
Alog &
(Lancewicki 2021)
A
+ 16/7] loR
mimigt 2n.
Oldy + (r(l))
(Lavk + d do(())
Linear bandit
(Hoown
ÖldyK E(rl)
Ō(dvK + B/rl
(Valili et al. 2023), concumeet work
Tabular
Ö(v OSK H SAE log K) (lowsoa et al. 2022)
(AVSAII + IIIII log log K)d, (4)
MDP
VSAHFR + H(H log log K)E(r]
Linear MDP
01. d(l'd-11) log K)
D(VeHH (
RL with general function approximation
Ö dimg (F. 1/K)H** + 112 dimp 1/K)d-(a)
Ó v diug (F 1/K)H*K H dimg 1/K)
Tabular two-player zero-sum MG
0( v VI>SABK + S AB) + 11 S (g) log K)
O(HHSSAKK + H² H SABE log K).
Ô ( ('VPH'K + (H) log K
Lineur two-player zemo-sum MG
Vi-H-K dH' H[T] Ing K)
Tabular multi playerr general sum MG
Ô (H* (SAmas + H /S
O(.VH-SAmma + SSd. log K)
(7hing at al., 202253
Õlv (MVH5SS SAmak K 1 [
2. Can we handle delays in (multi-agent) sequential decision making in the context of function approximation?
We answer these two questions affirmatively by proposing a reduction-basee framework for stochastic delays in both single-agen and multi-agent sequential decision making. Our contributions are summarized below.
Our Contributions. Our main contribution is proposing new reduction based framework for both single-agent and multi-agent sequential decision making with stochastic delayed feedback. The proposed framework can convert any multi-batched algorithm (cf. Section 3) 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 which require case by case algorithm design and analysis, we provide a unified framework to solve a wide range of problems all together.
Based on this framework, we obtain complete set of results for agggee and multi-agent sequential decision making with delayed feedback. In specific, our contributions can be summarized as follows:
New framework: We propose generic algorithm that can be integrated with any multi-batched algorithm in a black-box fashion. Meanwhile, we provide a unified theoretical analysis for the proposed generic algorithm.
Improved results and new results: By applying our framework to different settings, obtain state-of-thed -het-art regret bounds for multi-armed bandits, and derive sharper results for linear bandits and tabular RL, which significantly improve existing results (I (Lancewicki et al., 2021; Howson et al., 2022). We also provide the first result for single-agent RL with delayed feedback in the context of linear even general function approximation:
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 (Zhang et al., 2022a), but
New algorithms:

---

also present 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.
Our results and comparisons with existing works are summarized in Table 1.
1.1 Related Works
Bandit/MDP with delayed feedback. Stochastically delayed feedback has been studied a lot in the multi-armed bandit and contextual bandit problems (Agarwal and Duchi, 2011; Dudik al., 2011; Joulani al., 2013; Vernade et al., 2020, 2017; Gael et al., 2020; Huang al.. 2023). A recent work (Lancewicki ct al., 2021) shows that under stochastic delay, elimination algorithm performs better than UCB algorithm, and gives tight upper and lower bounds for multi-armed bandit setting. Howson et al. (2021) solves the linear bandit setting by adapting LinUCB algorithm. The concurrent work of Vakili et al. (2023) provides bound for the kernel bandit setting with delayed feedback. Our work does not consider the kernel setting, but we conjecture that our framework can handle this problem by designing
algorithm for kernel bandits.
In RL., despite practical importance, there limited literature on stochastical delay in RL. Lancewicki et al. (2022) and Jin et al. (2022b) 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. Howson et al. (2022) 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.
Another line of work considers adversarially delayed feedback (Lancewicki et al., 2022; Jin et al., 2022b; Quanrud and Khashabi, 2015; Thune et al., 2019; Bistritz et al., 2019; Zimmert and Seldin, 2020; Ito et al., 2020; Gyorgy and Joulani, 2021; Van Der Hoeven and Cesa- Desa-Bianchi, 2022). In the adversarial setting the state-of-theaar result of form VK + D. where K is the number of the episodes and D is the total delay. Note that when adapting their result to the stochastic setting, the bound becomes /K KK- + Kr where T is the expectation of delay, while in stochastic delay setting the upper bound can be vK + r. Therefore, a direct reduction from adversarial delay setting to stochastic delay setting will result in a suboptimal regret bound.
Low switching cost algorithm. Bandit problem with low switching cost has been widely studied in past decades. Desa-Bianchi et al. (2013) showed an θ(K²) regret bound under adaptive adver- saries and bounded memories. Perchet et al. (2016) proved regret bound of 0(KT-2--xr) ) for the two-armed bandit problem within M batches, and later Gao et al. (2019) extended their result the general A-armed case. In RL, by doubling updates, the global switching cost is O(SAH log)(K)) while keeping the regret Ö(VSAK H+) (Azar et al., 2017). Recently Zhang et al. (2022b) proposed a policy elimination algorithm that achieves O(VSAKH', regret and O + log, logg( switch- ing cost. Besides, Gao et al. (2021) generalized the problem to linear MDPs, and established regret bound of Ō(V@HH')) with OdH log(K)) global switching cost. Recent work Qiao et al. (2022) achieved O OHHSA Alg logg (K)) switching cost and Opooy((S, A, H) regret with computational inefficient algorithm. And Kong et al. (2021) consider MDP with general function approximation settings.
Markoy Games. A standard framework to capture multi-agent RI. is Markov games (also known as stochastic games) (Shapley, 1953). For two-player zero-sum Markov games, the goal is to solve for the Nash equilibrium (NE) (Nash, 1951). Recently, many works study this problem under the generative model (Zhang et al., 2020; Li et al., 2022), offline setting (Cui and Du, 2022b,a; Zhong et al., 2022; Xiong et al., 2022a; Yan et al., 2022), and online setting (Bai and Jin, 2020; Bai et al., 2020; Liu et al., 2021; Tian et al., 2021; Xie et al., 2020; Chen et al., 2021; Jin et al., 2022a; Xiong et al., 2022b; Huang et al., 2021). Our work is mostly related to Liu et al. (2021) and Xie et al. (2020). Specifically, Liu et al. (2021) studies online tabular two-player zero-sum MGs and proposes an algorithm with O(VSABI² regret. Xie et al. (2020) focused on online linear MGs provide an algorithm that enjoys O O(V regret. We also remark that Jin et al. (2022a); Xiong et al. (2022b); Huang et al. (2021) establish sharper regret bound for linear MGs but the algorithms therein computationally inefficient. There is also a line of works (Liu et al., 2021; Jin et al., 2021;
3

---

Song et al., 2021; Zhong et al., 2021; Mao and Başar, 2022; Cui and Du, 2022b; Jin et al., 2022c; Daskalakis et al., 2022) studying multi-player general-sum MGs. Among these works, Jin al. (2021); Song et al. (2021); Mao and Başar (2022) 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.
very recent but independent work (Zhang et al., 2022a) also studies multi- 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 Zhang et al. (2022a). First, they study the setting where the total delay is upper bounded by 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(H3 / K), while ours is O OHH2nn.ET where n is the number of players. Finally, it seems that their results cannot be extended to the multi-agent RL with function approximation.
2 Preliminary
The objective of this section 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 general framework for interactive decision making, which we refer to as Multi-agent Sequential Decision Making (MSDM).
Notations
We use A(-) to represent the set of all probability distributions on a set. For N to denote the big-O, big- Te--Teet,, big-Omega
we denote [n]] =
n). We use notations. We use (-) to hide logarithmic factors.
Multi-agent Sequential Decision Making A Multi-ggent Sequential Decision Making problem can be represented as a tuple M = (n, S, {= H, {Pr ! 1. $1, {ra Hi 1) where n is the number of agents, S is the state space, A, is the action space of player i, H is the length of each episode and s is the initial state. We define A = X A, as the whole action space.
At each stage h, for every player i, every state-action pair (s, 01, distribution with mean (s, Q1, .... an) and support in [0, 1], and a transition distribution pn. (-Is, a) over next states. We denote by S = |S] and A; = |Ai.).
an) is characterized by reward
The protocol proceeds in several episodes. At the beginning of each episode, the environment starts with initial state $1. At each step & E H.). the agents observe the current state sh, and take their actions (a), an) respectively. Then the environment returns a reward signal, and transits to next state $/+1-
(random) policy n, of the th player is set of maps N. := {MTSA Ω x S + Ane where each TiA maps random sample w from probability space Q and state to an action in A,, A joint (potentially correlated) policy is set of policies { { where the same random sample w is shared among all agents, which we denote as policy excluding the 7th player. For each stage h E [H] and any state-action pair (s, a) E S A, the value function and Q-function of policy are defined as:
④ T2 ④ @ Tm. We also denote -= as the joint
(8,
E
Σ M==
TiM
8h 8, an a, न
(E)(s) E.
Σ h=
ri
8h 8,
For each policy и,, we define V (s) = 0 and 1 (s, a) 0 for all s E S, E 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 maximize the total reward it receives.
There exists an optimal policy n² such that (s, a) Q (s) max, Q (7, a) satisfies the optimal Bellman equations
Q (s, a) = (s, a) + E.r ( Vitti(s)),
V/ = (+,, aeA
((s,a)ESx

---

Then the optimal policy is the greedy policy (s) arg max ( (s, (s. And we evaluate the performance of the learner through the notion annle-player regret, which is defined
K Σ (vi - (s1).
Regret K)
(I)
the case of mulle--player general-sum MGs, for any policy я- the best response of the jt player is defined as policy of the hth player which is independent of the randomness in π-i, and achieves the highest value for herself conditioned on all other players deploying w-i. In symbol, the best response the maximizer of max,; Vi,l xxxxxxxxxx (
($1) whose value we also denote as V Vi'i"=((ss for simplicity.
For general-sum MGs, we aim to learn the Coarse Correlated Equilibrium (CCE), which is defined as joint (potentially correlated) policy where player can increase her value by playing different independent strategy. In symbol,
Definition 1 (Coarse Correlated Equilibrium). joint policy a is a CCE if maxie(m (V.li
VI51 (s1) 0. A joint policy is a e-approximate CCE if (m) (Vii1-> V(Ti)s1) Se.
For any algorithm that outputs policy #* at episode k, we measure the performance of the algorithm using the following notion of regret:
K
Regret ())
Σ max k=
5 5,h (51).
One special case of multi-plan playerr general-sum MGs is two-player zero-sum MGs, in which there only two players and the reward satisfies 72,4 = -ri,-- In zero-sum MGs, there exist policies that the best responses each other. We call these optimal strategies the Nash equilibrium of the Markov game, which satisfies the following minimax equation:
sup inf V/ (s) = V (s) = inf sup Vi (s).
V
We measure the suboptimality of any pair of general policies (á, 8) using the gap between their performance and the performance of the optimal strategy (i.e., Nash equilibrium) when playing against the best responses respectively:
V/ (s1) vPR. (s1) [yt (s1) - Vi* (o1) [vr (s1) vaatt (01)
Let (1* ) denote the policies deployed by the algorithm in the t episode. The learning goal is to minimize the two-player regret K episodes, defined
K
Regret((K) = E(vr"" vtritt) (s1).
(3)
k=1
One can see that (3) is natural reduction of (2) from general-sum games to zero-sum games.
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 stochastic. i.c. we introduce random variable for the delay between playing the k-th episode and observing the feedback of the k-th episode, which we denote by тk- We assume the delays i.i.d:
Assumption 1. The delays {Te)i=n are positive, independent and identically distributed random
variables: Tk i..dd f.). We denote the expectation of [[T] (which may be infinite), and denote the quantile function of T as d=(q), i.e.
d, (q) min { E Pr 2 2
(4)
5

---

When delay exists, the feedback associated with an episode does not return immediately. Instead, the feedback of the k-thh episode cannot be observed until the k + T 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 standard assumption used in previous works Howson et al. (2021), though it is not always necessary in our paper.
Assumption The delays are non non-negative, independent, and identically distributed (v, b)- subexpo- nential random variables. That is, their moment generating function satisfies the following inequality
E exp (1 (T1111111))
S exp ( (202
(5)
for some and and all by S 1/b.
3 Multi-batched Algorithm for MSDMs
In this section we mainly discuss multi-batched algorithms for MSDMs. This section aims to provide formal definition of multi-batched algorithm, and give some examples of multi-batched algorithm for the case of understanding.
Formally, multi- batched algorithm consists of several batches. At the beginning of the m batch, the algorithm outputs policy sequence T" = (< n² ..... x/ for this batch using data collected in previous batches, along with stopping criteria SC, which is mapping from dataset
boolean value. Then the agent executes the policy sequence xh for several episodes and collects feedback the current dataset D, until the stopping criteria are satisfied (i.e. SC(D) = 1). If the length of the m batch exceeds lm. then we simply run the policy sequence cyclically, which means in the kt episode we run policy T mod pm Algorithm describes a protocol of multi-batched algorithm.
Algorithm 1 Protocol of Multi-batched Algorithm
1: Initialize dataset 7 0
2: for batch m 1, M do
3: D=
4:
k =
5: Calculate policy sequence T" (T 42 T(p.) using previous data Dm-1, and
stopping criteria SC
6:
while SC(D) = 0 do
7:
k +- k +
8: In episode k, execute The mod and collect trajectory feedback of
9:
D {o*}
10: end while
Update dataset Dm Dm-1 UD
12:
end for
13:
Output: A policy sequence {
Note that the major requirement is that the policy to be executed during the batch should be calculated the beginning of the batch. Therefore, algorithms that calculate the policy at the beginning of each episode do not satisfy this requirement. For example, UCB algorithms in bandits (Lattimore and Szepesvári, 2020) and UCBVI (Azar et al., 2017) are not multi-batched algorithms.
Relation with low-switching cost algorithm Our definition of multi- baltii-batchdd algorithm is similar that of low-switching cost algorithm, but is more general.
For any algorithm, the switching cost the number of policy changes the running of the algorithm in K episodes, namely:
N Nwitch
I (TT + mt41).
Most algorithms with Nswich low-switching cost are multi-batched algorithms with Newitch batches. For example, the policy climination algorithm proposed in Zhang et al. (2022b) is multi-batched

---

algorithm with 2H + log log K batches. And the algorithm for linear MDP with low global switching cost in Gao et al. (2021) is multi-batched algorithm with O(dH log K) batches. On the other hand, the difference between batches and switching cost is that we do not require the policy to be the same during batch. Therefore, a multi-batched algorithm with N batches may not be an algorithm with N switching cost. For example, the Phase Elimination A Algorithm in linear bandit with finite arms setting (Lattimore and Szepesvári, 2020) is multi-batched algorithm with Olog K) batches, but the switching cost is O(A log K) which is much larger.
4 A Framework for Sequential Decision Making with Delayed Feedback
In this section, we introduce our framework for sequential decision making problems with stochastic delayed feedback. We first describe our framework, which converts any to an algorithm for MSDM with delayed feedback. Then we provide theoretical guarantees for the performance of such algorithms.
algorithm
Before formally introducing our framework, we first give intuitive explanation of why multi- batched algorithms work for delayed settings. Recall that Lancewicki et al. (2021) gives a lower bound showing that UCB-type algorithms are suboptimal in multi-armed bandits with stochastic delay (see Theorem I in Lancewicki et al. (2021)). The main idea of the lower bound is that UCB algorithm will keep pulling a suboptimal arm until the delayed feedback arrives and the policy is updated. Therefore, if the policy updates too frequently, then the algorithm has to spend more time waiting for the update, and the effect of delay will be greater. This observation motivates us to consider multi- matti-batched algorithms, which have low frequency of policy updating.
For any sequential decision making problem, assume that we have multi-batched algorithm ALG for the problem without delay. Then in the existence of delay, we can still run ALG. The difference is, in each batch of the algorithm, we some extra steps until we observe enough feedback that the stopping criteria are satisfied. For example, if the delay 7 is a constant and the stopping criteria is that the policy TT is executed for pre-defined number of times tg. then we only need run ग for tu + r times. After the extra steps are finished, we can collect ty delayed observations, which meet the original stopping criteria. Then we can continue the next batch. Algorithm 2 gives a formal description.
Algorithm 2 Multi-batched Algorithm With Delayed Feedback
1: Require: A multi-batched algorithm for the undelayed environment ALG
2: Initialize dataset D = 0
3: for batch m 1, ..., M do
4: ACG calculates a policy nh (or a policy sequence) and a stopping criteria SC'
5: D=
6:
while SC(D) = 0 do
7:
1o + h +++1
8:
In episode k. execute Th
9:
Collect trajectory feedback in this batch that is observed by the end of the episode: {o'
+ T, = k}
10:
D D- (ot :1+++ Tr k}
11: end while
Update dataset Dm Dm D
13:
end for
14:
Output: A policy sequence {TT
For the performance of Algorithm 2, have the following theorem, which relates the regret of delayed MSDM problems with the regret of multi-batched algorithms in the undelayed environment. Theorem 1. Assume that in the undelayed environment, have a mudti-batched algorithm with No. batches, and the regret of the algorithm in K episodes can be upper bounded by Regret(K) with probability at least 1 - 8. Then in the delayed feedback case, with probability at least 1 5, the regret can be upper bounded by
+ 2H log (K/)) + H. Hod, (g)
Regret(K) < - -Regre((K)
(6)
7

---

for any q E (0, 1). In addition. if the delays satisfy Assumption 2, then with probability at least 1 6 the regret can be upper bounded by
RK I Regret(K)) + H.N6 [
where C, = min(y y 20 (3 26 log(3K
a problem-independent constant.
The proof is in Appendix A. The main idea is simple: in each batch, we can control the number of extra steps when waiting for the original algorithm 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. Note that in Eq. (6) we do not need Assumption 2. This makes (6) more general.
Applying Theorem to different settings, we will get various types of results. For example, in multi-armed bandit setting, using the Batched Successive Elimination (BaSE) algorithm in Gao et al. (2019), we can get a O 1 log K) + d, (q) log(K) (K) upper bound from (6), which recovers the SOTA result in Lancewicki et al. (2021) up to a log factor in the delay-dependent term. We leave the details to Appendix C, and list the main results in Table 1.
5 Results for Markov Games
As an application, we study Markov games with delayed feedback using our framework. We first develop new nulti-batched algorithms for Markov games, then combine them with our framework to obtain regret bounds for the delayed setting.
5.1 Tabular Zero-Sum Markov Game
First we study the tabular zero-sum Markov game setting. The algorithm is formally described in Algorithm 4 in Appendix D.
Our algorithm can be decomposed into two parts: an estimation step and a policy update step. The estimation step largely follows the method in Liu et al. (2021). For each (h, b). we main- tain optimistic estimation Q (8, a, b) and pessimistic estimation 2t, (s, a, b) of the underlying (%, a, b), by value iteration with bonus using the empirical estimate of the transition P. And we compute the Coarse Correlated Equilibrium (CCE) policy ı of the estimated value functions Xie et al. (2020). 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, 8, a, b) such that the visiting count (s, a, b) is doubled. This update scheme ensures that the batch number is small.
For the regret bound of Algorithm 4, we have the following theorem. Theorem 2. For any p E (0, 1), letting + log(SABT/p) then with probability at least p, the regret of Algorithm 4 satisfies
Regret (K) S O (VHSAABL ( H 5 ABL?.
and the batch number most O(HSAB K).
The proof of Theorem 4 is similar to Theorem in Liu et al. (2021), but the main difference is we have deal with the sum of the Bernstein-type bonus under the doubling framework. To deal with this we borrow ideas from Zhang et al. (2021b). The whole proof is Appendix D.
Adapting the algorithm to the delayed feedback setting using our framework, we have the following corollary.
For tabular Markov game with delayed feedback, running Algorithm 2 with ALG being Algorithm 4. we can upper bound the regret by
Corollary 1.
Regret (K) S0 (VHSSABK. + H²S²AB() (
+ H2SAdd, (4) log K
for any q E (0, 1). In addition, the delays satisfy Assumption 2, the regret can be upper bounded by Regret(K) < OOVHHSBBK.
(A2SABE(]]] K).
8

---

5.2 Linear Zero-Sum Markov Game
We consider the linear zero-sum Markov game setting, where the reward and transition have linear structure.
Assumption 3. For each (z, a, b) E Ax B and h E [H] we have
TA a, = Φ(z, a, (TTTT)O). On, PA(. 2, a.a) = 6(x, ()),,,6)'Hu
where Φ S x A A + I is known feature map, O2 E IRd is an unknown vector and 14h (Ph (6) Jie(4] is vector of d unknown (signed) measures on S. We assume that [| I 1, |1 S dd and (S)]l)) S for all E [H], where || is the vector le norm.
The formal algorithm is in Algorithm 5 in Appendix D.2. It is also divided into two parts. The estimation step is similar to that in Xie et al. (2020), where we calculate an optimistic estimation ( a, b) and a pessimistic estimation O (s, a, 6) of the underlying Q7 (s, a, b) by least square value iteration. And we compute the CCE policy æ 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 E [H] such that (et(AA) 77 det(AA). This condition implies that we have collected enough information at one direction. This technique is similar Gao al. (2021); Wang al. (2021).
For the regret bound of Algorithm 5, we have the following theorem.
Theorem 3. In Algorithm 5, let 1 2. Then we have
Regret (K) S Ö(Vd3H*K)
And the batch number of Algorithm 5 is log2
dH log 1 k
Proof. See Appendix D.2 for a detailed proof.
Adapting the algorithm the delayed feedback setting using our framework, we have the following corollary.
Corollary 2. For linear Markov game with delayed feedback, running Algorithm with ALG being Algorithm 5, we can upper bound the regret by
Regret (oggret(KK= S Ó
(N + dz) log
for any q E (0, 1). In addition, if the delays satisfy Assumption 2, the regret can be upper bounded by Regret S (ViH** + dH K).
5.3 Tabular General-Sum Markov Game
In this section, we introduce the multi-batche version of V-learning (Jin et al., 2021: Mao and Başar, 2022: Song et al., 2021) for general-sune Markov games. Our goal is to minimize the regret (2). The algorithm is formally described in Algorithm 6 in Appendix D.
The multi-batched V-learning algorithm maintains value estimator VA (s), counter (x(s), and policy (- for each and h. We also maintain S x H different adversarial bandit algorithms. At step in episode the algorithm divided into three steps: policy execution, V-value update, and policy update. In policy execution step, the algorithm takes action aj according to T/. and observes reward Ta and the next state 8h+1. and updates the counter No. (sx). Note that т is updated only when the visiting count of some state N,, (s) doubles. Therefore ensures a low batch number.
In the V-value update step, we update the estimated value function by
V. (sh) = (1 - oz) V. (sk) + ar (rn + Va+1 (8h+1) + B(t))

---

where the learning rate is defined as
H+1 a: = +t (1-aa))
=i= a, II (1 (1- az) -=++
i
Ø=1
and (() is the bonus to promote optimism.
In the policy update step, the algorithm feeds the action an and its "loss" H-ra+ -intsann)n)) to the (8h, h) adversarial bandit algorithm. Then receives the updated policy my (- 8h))
For two-player general sum Markov games, we let the two players run Algorithm 6 independently. Each player uses her own set of bonus that depends on the number of her actions. If we choose the adversarial bandit algorithm as Follow The Regularized Leader (FTRL) algorithm (Lattimore and Szepesvári, 2020), we have the following theorem for the regret of malti-batched V-learning.
Theorem 4. Suppose and K E N, let = log (SSAAKK/)) Choose learning rate a, and bonus {3(t) as 3(t) / At/t so that Σ (i) Do(/H3Aut for any t E [K], where A = max; A; Then, with probability at least 1 after running Algorithu for K episodes, we have
choose the adversarial bandit algorithm
FTRL For any 8 E (0,1)
Regret(K) s (VH*SAL).
And the batch number is O(NHS log K). where is the number of players.
Proof. See Appendix D for details.
Finally, adapting the algorithm to the delayed feedback setting using framework, have the following corollary.
Corollary 3. For tabular general-sum Markov game with delayed feedback, running Algorithm with ALG being Algorithm 6, we can upper bound the regret by
Regret (k)gret(K- S V (
H'ndd, log K
for any q E (0, 1), In addition, if the delays satisfy Assumption 2, the regret can be upper bounded by
Regret (Rgget((K=a S (VHSSA H2nSE([] log K)
Proof. This corollary is directly implied by Theorems and 4.
6 Conclusion and Future Work
In this paper we study delayed feedback in general multi-agent sequential decision making. We propose a novel reduction-basee framework, which turns any multi-batched algorithm for sequential decision making with instantaneous feedback into 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-batcher algorithm for tabular Markov game with smaller batch number, since in tabular MDP, Zhang et al. (2022b) gives an algorithm with O(H log, log, K) batch number which is independent of S. It not clear whether can achieve similar results in MDP for Markov games. We believe tighter result is possible in this setting with carefully designed multi-batcher algorithm.
Acknowledgements
Liwei Wang is supported in part by NSF IIS 2110170, NSF DMS 2134106, NSF CCF 2212261, NSF IIS 2143493, NSF CCF 2019844, NSF IIS 2229881.
10

---

References
Abbasi- Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24.
Agarwal, A. and Duchi, J. C. (2011). Distributed delayed stochastic optimization. Advances neural information processing systems, 24.
Azar, M. G., Osband, I., and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272. PMLR.
Bai, Y. and Jin, C. (2020). Provable self-play algorithms for competitive reinforcement learning. In International conference on machine learning, pages 551-560. PMLR.
Bai, Y., Jin, C., and Yu, T. (2020). Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-211 2170.
Bistritz, I., Zhou, Z., Chen, X., Bambos, N., and Blanchet, J. (2019). Online exp3 learning in adversarial bandits with delayed feedback. Advances in neural information processing systems, 32.
Cesa-Bianchi, N., Dekel, O., and Shamir, O. (2013). Online learning with switching costs and other adaptive adversaries. Advances in Neural Information Processing Systems, 26.
Changuel, N., Sayadi, B., and Kieffer, M. (2012). Online learning for qoe-based video streaming to mobile receivers. In 2012 IEEE Globecom Workshops, pages 1319-1324. IEEE.
Chen, B., Xu, M., Liu, Z., Li, L., and Zhao, D. (2020). Delay-aware multi-agent reinforcement learning for cooperative and competitive environments. arXiv preprint arXiv:2005.05441.
Chen, Z., Zhou, D., and Gu, Q. (2021). Almost optimal algorithms for two-player markov games with linear function approximation. arXiv preprint arXiv:2102.07404.
Cui, Q. and Du, S. S. (2022a). Provably efficient offline multi-agent reinforcement learning via strategy-wise bonus. arXiv preprint arXiv:2206.00159.
Cui, Q. and Du, S. S. (2022b). When is offline two-player zero-sum markov game solvable? arXiv preprint arXiv:2201.03552
Daskalakis, C., Golowich, N., and Zhang, K. (2022). The complexity of markov equilibrium in stochastic games. arXiv preprint 223.099204..991...
Dudik, M., Hsu, D., Kale, S., Karampatziakis, N., Langford, J., Reyzin, L., and Zhang, T. (2011). I). Efficient optimal learning for contextual bandits. arXiv preprint arXiv:1106.2369
Gael, M. A., Vernade, C., Carpentier, A., and Valko, M. (2020). Stochastic bandits with arm-depended delays. In International Conference Machine Learning, pages 3348-3356. PMLR.
Gao, M., Xie, T., Du, S., and Yang, L. F. (2021), A provably efficient algorithm for linear markov decision process with low switching cost. arXiv preprint wiXiv:2101.0049:
Gao, Z., Han, Y., Ren, Z., and Zhou, Z. (2019). Batched Neural Information Processing Systems, 32.
bandits problem. Advances in
Gyorgy, A. and Joulani, P. (2021). Adapting to delays and data in adversarial multi-armed bandits. In International Conference on Machine Learning, pages 3988-3997. PMLR.
Howson, B., Pike-Burke, C., and Filippi, S. (2021), Delayed feedback in episodic reinforcement learning, arXiv preprint arXiv:2111.07615.
Howson, B., Pike-Burke, C., and Filippi, S. (2022). Delayed feedback in generalised linear bandits revisited. arXiv preprint 20Xiv:2207.10788.
Huang, B., Lee, J. D., Wang, Z., and Yang, Z. (2021). Towards general function approximation in zero-sum markov games. arXiv preprint 2rXiv:2107.14702.

---

Huang, J., Dai, Y.. and Huang, L. (2023). Banker online mirror descent: A universal approach for delayed online bandit learning. arXiv preprint arXiv:2301.10530
Ito. S., Hatano, D., Sumita, H., Takemura, K., Fukunaga, T., Kakimura, N., and Kawarabayashi, K.-I. (2020). Delay and cooperation in nonstochastic linear bandits. Advances in Neural Information Processing Systems, 33:4872-4888.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is q-learning provably efficient? Advances in neural information processing systems, 31.
Jin, C., Liu, Q. Wang, Y., and Yu, T. (2021), V-learning-a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2110.1455:
Jin, C., Liu, Q., and Yu, T. (2022a). The power of exploiter: Provable multi-agent in large state spaces. In International Conference Machine Learning, pages 10251-10279. PMLR.
Jin, T., Lancewicki, T., Luo, H., Mansour, Y., and Rosenberg, A. (2022b). Near-optimal regret for adversarial mdp with delayed bandit feedback. arXiv preprint arXiv:2201.13172.
Jin, Y., Muthukumar, V., and Sidford, A. (2022c). The complexity of infinite-horizon general-sum stochastic games. arXiv preprint WrXiv:2204.04188
Joulani, P., Gyorgy, A., and Szepesvári, C. (2013). Online learning under delayed feedback. In International Conference on Machine Learning, pages 1453-1461. PMLR.
Kong, D., Salakhutdinov, R., Wang, R., and Yang, L. F. (2021). Online sub-sampling for reinforcement learning with general function approximation. arXiv preprint arXiv:210.007203.
Lancewicki, T., Rosenberg, A., and Mansour, Y. (2022). Learning adversarial markov decision processes with delayed feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7281-7289.
Lancewicki, T., Segal, S., Koren, T., and Mansour, Y. (2021). Stochastic multi-armed bandits with unrestricted delay distributions. In International Conference on Machine Learning, pages 5969-5978. PMLR.
Lattimore, T. and Szepesvári. C. (2020). Bandit algorithms. Cambridge University Press.
Li, G., Chi, Wei, Y., and Chen, Y. (2022). Minimax-optimal multi-agent in markov games with generative model. In Advances in Neural Information Processing Systems.
Liu, Q. Yu, T., Bai, Y., and Jin, C. (2021). A sharp analysis of model-based reinforcement learning with self-play In International Conference on Machine Learning, pages 7001-7010. PMLR.
Mahmood, A. R., Korenkevych, D., Komer, B. J., and Bergstra, J. (2018). Setting up reinforcement learning task with real-world robot. In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4635-4640. IEEE.
Mao, W. and Başar, T. (2022). Provably efficient reinforcement learning in decentralized general-sum markov games. Dynamic Games and Applications, pages 1-22.
Nash, J. (1951). Non-cooperative games. The Annals of Mathematics, 54(2):286-22
Perchet, V., Rigollet, P., Chassang, S., and Snowberg, E. (2016). Batched bandit problems. The Annals of Statistics, pages 660-681.
Qiao, D., Yin, M., Min, M., and Wang, Y.-X. (2022). Sample-effcient reinforcement learning with loglog (t) switching cost. arXiv preprint arXiv:2202.06388.
Quanrud, K. and Khashabi, D. (2015). Online learning with adversarial delays. Advances in neural information processing systems, 28.
Shapley, (1953). Stochastic games. 199501000
Proceedings of the national academy of sciences,
12

---

Song, Z., Mei. S., and Bai, Y. (2021). When can we learn general-sum markov games with large number of players sample-eficientyy arXiv preprint vrXiv:2110.448xx
Sutton, R. S. and Barto, A. G. (2018). Reinforcement learning; An introduction. MIT press.
Thune, T. S., Cesa-Bianchi N., and Seldin, Y. (2019). Nonstochastic multiarmed bandits with unrestricted delays. Advances in Neural Information Processing Systems, 32.
Tian, Y., Wang, Y., Yu, T., and Sra, S. (2021). Online learning in unknown markov games. In International conference on machine learning, pages 10279-10288, PMLR.
Vakili, S., Ahmed, D., Bernacchia, A., and Pike-Burke, C. (2023). Delayed feedback in kernel bandits. arXiv preprint arXiv:2302.00392
Van Der Hoeven, D. and Cesa-Bianchi, N. (2022). Nonstochastic bandits and experts with arm- dependent delays. In International Conference on Artificial Intelligence and Statistics. PMLR.
Vernade, C., Cappé, O., and Perchet, V. (2017). Stochastic bandit models for delayed conversions. arXiv preprint arXiv: /706.09186.
Vernade, C., Carpentier, A., Lattimore, T., Zappella, G., Ermis, B., and Brueckner, M. (2020). Linear bandits with stochastic delayed feedback. In International Conference on Machine Learning, pages 9712-9721. PMLR.
Wainwright, M. J. (2019). High-dimensional statistics: A non-usymptotic viewpoint, volume 48. Cambridge University Press.
Wang, T. Zhou, D., and Gu, Q. (2021). Provably efficient reinforcement learning with linear function approximation under adaptivity constraints. Advances in Neural Information Processing Systems, 34:13524
Xie, Q., Chen, Y., Wang, 7., and Yang. 7. (2020). Learning zero-sum simultaneous-move markov games using function approximation and correlated equilibrium. In Conference on learning theory, pages 3674-3682. PMLR.
Xiong, W., Zhong, H., Shi, C., Shen, C., Wang, I.., and Zhang, T. (2022a). Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game. arXiv preprint arXiv:2205. 15512.
Xiong, W., Zhong. H., Shi, C., Shen, C., and Zhang, T. (2022b). A self-play posterior sampling algorithm for zero-sum Markov games. Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 11496-24522, PMLR.
Yan, Y., Li, G.. Chen, Y., and Fan, J. (2022). Model-based reinforcement learning is minimax-optimal for offline zero-sum markov games. arXiv preprint (.XX::2226004444040
Zhang, K., Kakade, S., Basar, T., and Yang, L. (2020). Model-based multi-agent rl in zero-sum markov games with netrooptimal sample complexity. Advances Neural Information Processing Systems, 33:1 1178.178
Zhang. K., Yang, Z., and Başar, T. (2021a). Multi-agent reinforcement learning: selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384.
Zhang, Y., Zhang, R., Li, G., Gu, Y., and Li, N. (2022a). Multi-agent reinforcement learning with reward delays. arXiv preprint 2rXiv:2212.0142
Zhang, Z., Ji, X., and Du, S. (2021b). Is reinforcement learning more difficult than bandits? near-optimal algorithm escaping the curse of horizon. In Conference on Learning Theory, pages 4528 4531. PMLR.
Zhang, 7.,, Jiang, Y., Zhou, Y., and Ji, (2022b). Near-optimal regret bounds for multi-batch reinforcement learning, arXiv preprint arX1v:2210.08238.
13

---

Zhong, H., Xiong, W., Tan, J.. Wang, L., Zhang, T., Wang, Z., and Yang, Z. (2022). Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. arXiv preprint arXiv:2202.07511
Zhong. H., Yang, Z., Wang, Z. and Jordan, M. 1. (2021). Can reinforcement learning find stackelberg nash equilibria in general-sum markov games with myopic followers? arXiv preprint 1rX15:211..13521.
Zimmert, J. and Seldin, Y. (2020). An optimal algorithm for adversarial bandits with arbitrary delays. In International Conference on Artificial Intelligence and Statistics, pages 3285-3294. PMLR.
14

---

A Proof of Theorem 1
We first prove (7). First, since the delays are i.i.d. subexponential random variables, by standard concentration inequality and uniform bound Wainwright (2019), we have the following lemma: Lemma S. Let {n. be i.i.d (v, b) subexponential random variables with expectation E/r]. Then we have
P 2 C+) -1
(8)
where C, = min { 22202 log
2b log 31 28
24
Define the good event G= Et 2:: 2 C+). By Lemma 5, the good event happens with probability at least - 8. Therefore, conditioned the good event happens, in each batch of the algorithm, we only need to run E[r] + C, episodes and the algorithm can observe enough feedback finish this batch.
The regret in 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 Regret(K), For the second part, since each episode contributes at most H regret, the total regret can be bounded by
Regret(K) I Regret (K) + HN, C+).
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.
Lemma 6.
Denote the number of observed feedbbac at time I as ny For any quantile g and any I, we have
Pr mitd-(s)
< 2 2 S exp (-2
9
(10)
8
Proof. Define (Te S (g))
to be an indicator that on time s that the delay is smaller than d, (g).
Note that E T [( < dr (1))
2 q- Thus,
Pr (etd,(1)
< q
s Pr
Σ 1 (T S dg))
Lt
2
2
==1
S Pr
Σ 1 To S d=(1)
Σ e [ fTx s sd
(11)
2
1 -Ellitrssi00
S exp (-2))
exp
where the third inequality follows from the relative Chernoff bound, and the last inequality is since E
I [T. < d+(()) 2..
Lemma 6 means, if the length of the batch in the undelayed environment m log(K(8) then with probability at least & if the batch for + d, (q) episodes, we will observe at least m feedbacks, which is enough for the algorithm finish this batch. On the other hand, if m < 1/8( then the regret of this batch can be trivially bounded by H log(K/8) Hence the total regret can be bounded by
K Regret(K) < Regret (K
d, (1) s 1
Regret(K) + 2HN, (o/(k + HN,d (12)
q
which finishes the proof.
15

---

B Details of Algorithms for Linear Bandits
The phase elimination algorithm for linear bandits in Lattimore and Szepesvári (2020) is follows. This algorithm is naturally a multi-batched algorithm, with each phase as one batch. Since the length of phase é is O(2*), the number of phases is (log K). Note that each phase the policy is pre-calculated at the beginning of the phase, and does not rely on the data of current phase.
Algorithm 3 Phase Elimination
1: Input: .A C R 3 >
2: Set and let A₁ A
3: Let 1 = t be the current timestep and find G-optimal design We E P (At) with Supp (Tt) -
d(d 1)/2 that maximises
log det V (STe) subject to
Σ TE(a) =
aEAte
4: Let E; = 2- and
(a) Et
ke(l 1 and === Σ Tela)
Te(a)=
log
8
acAL
5: Choose each action E Ar exactly Te(a) times.
6: Calculate the empirical estimate:
f T
8
Σ t=
A,X,
with = Σ Tı(a)aa
acA:
using observable data in this phase.
7: Eliminating low reward arms:
Ae41 a Ae: max (0 - a) s 201 bEdt
8: 6- f++1 and go Line 2.
Theorem 7 (Theorem 22.1 in Lattimore and Szepesvári (2020)). With probability at least 8, the regret of Algorithu satisfies
Alog(())
Regret(K) SC Kd
(13)
where C > O is a universal constant. 1f = (1/KK,, then E Regret K)] s C. Kdlog( (AK)))(K))) for an appropriately chosen universal constant 0.
For infinite action set A 1-, we use a covering technique: we find a c-covering of the action space, and run Phase Elimination on the covering set. The covering number of the set [-1, 1] Oldlee//))) And the error caused by using e-covering will lead O(eK) increase in regret. Therefore, by setting k- the regret of the whole algorithm is O(d (dd// K log K).
C Results for Bandits and MDPs
We now apply Theorem different bandit and MDP problems.
In multi-armed bandit settings, using the BaSE algorithm Gao et (2019), we can get the following bound.
16

---

Corollary 4. For multi-armen bandit with delayed feedback, running Algorithm with ALG being the BaSE algorithm in Gao al. (2019), we can upper bound the regret by
Alog K
log² K
Regret(K) 5O
+ dr (4))ggggg log K
qmini A q
for wny 4 E (0, 1), where A, is the optimal gap of the 8th arm In addition, if the delays satisfy Assumption 2, the regret can be upper bounded by
Alog K minge. A
Regret(K) (K) 00
+ E[T] [og]
This result recovers the SOTA result Lancewicki et al. (2021) up to a log factor the delay- dependent term.
In linear bandit settings, using the Phase Elimination algorithm (Lattimore and Szepesvári, 2020), we can get the following bound.
Corollary 5. For linear bandit with delayed feedback, let d be the dimension of the feature space. When the arm set A is finite, running Algorithm 2 with ALG being the Phase Elimination algorithm in Lattimore and Szepesvári (2020). we can upper bound the regret by
Regret (K) so La
(
log log A log K
+ d+ (4) log
for any q E (0,1), 1). In addition, if the delays satisfy Assumption 2, the regret can be upper bounded by Regret(K) = O (Vad K log A + [[[] K
When the action set is infinitely large (for example, as covering to obtain regret bounds whose main term scales as (dv K). Compared with the result in Howson et al. (2021) which scales as Ó(dvK + d3/2E(r]), our bound is tighter in the delay-dependent term as we remove the d3/2 factor.
[|-,, 1) we can use techniques such
In tabular MDP settings, using the policy elimination algorithm Zhang et al. (2022b), we can get the following bound.
Corollary 6. For tabular MDP with delayed feedback, rumning Algorithm 2 with ALG being the policy elimination algorithm Thang al. (2022b), we can upper bound the regret by
Regret (K) S <o(-VSAH>KL+ (H + log log K) log K
+ (H + log log K d (q)
for any E (0, 1), where u is some log factor. addition, if the delays satisfy Assumption 2, the regret can be upper bounded by
Regret (K) S COVSAAASSK H + log log K) K))(T)
Compared with the previous result / VI*SAK: + SAE(T log K in Howson et al. (2022), bound removes the SA factor the delay-dependent term, therefore tighter.
We can also apply our framework to linear MDP and MDP with general function approximation settings with delay. These settings have not been studied before, therefore our result is novel. In linear MDP settings, using the algorithm in Gao et al. (2021) we can get the following bound.
Corollary 7. For linear MDP with delayed feedback, let be the dimension of the feature space. Running Algorithm 2 with ALG being the algorithm in Gao et al. (2021), we can upper bound the regret by
Regret(K)) (K) =OL-VOH- ddH'd, log K)
for any q E (0. In addition, if the delays satisfy Assumption the regret be upper bounded by
Regret(K) (K) s Ö(VPHHK dH E(T) log K)
17

---

And in MDP with general function approximation, using the algorithm in Kong et al. (2021) we get the following bound.
Corollary 8. For MDP with general function approximation and delayed feedback, let dim e (F ee) the e-eluder dimension of the function class F. Running Algorithm with ALG being the algorithm in Kong et al. (2021). we can upper bound the regret by
e) be
Regret(K) s (F,
H dim=(F.1/K)d((a))
for any q E (0,1). In addition, if the delays satisfy Assumption the regret can be upper bounded by
Regret(K) Ô =VVViimm(..//)) + H12 di
D Proofs for Tabular Markov Games
D.1 Multi-batched Optimistic Nash-VI
Algorithm 4 Multi-batched Algorithm for Tabular Markov Game
1: Initialize: for any (s, a, h), (s,s, a. + H, Q, (s, 0. t H,,,((,,,b)) t O.
trigger set C + 2 2 < KH, i = 1,2....} K do
2: for episode k 1,2,
3: if there exists (h, s, a, b) such that N (s, a, E then
4: for step h = H,
1...., do
5:
for (s, a, b) E S x x do
6:
t - [s, a, b)
7:
ift > 0 then
8 + BONUS v, [Vitt + Vn+1) (s,
8:
9:
nh + (c/H) (V4+1 - Vv+1) (s, a)
10:
(, b) + min
( (FA+PPlD++) (s, + + 1h. H
11:
(s, + max
(rh + PAV 1+41 (s,a,b) - 3/
end if end for
13:
14:
for s E S
15:
* * (8) - CCE (2,(5))),2,(00,))
16:
(8) + (ET, Qn) (s); Ln(s) + (Eng Qn (8)
end for end for
18:
19:
end if
20:
for step h = I,., H do
take action (an, bn) m (.. sn). observe reward ra and next state sh+1. 22: add No (sn, an, bn) and Nž (sh, an, byy 8h+1).
21:
23: PA (-1 sh,
( an bn)) < N (sh, an bn. :) / (shr ane by)
end for
25:
end for
In this part, list some of the important lemmas for the tabular Markov game algorithm, most of which are proven in the previous literature Liu et al. (2021). These lemmas are very useful for proving the regret bound in main theorem.
We denote V Q+ x u and u for values and policies the beginning of the k-th episode. In particular, N (s, is the number have visited the state-action tuple (s, a, b) at the h-th step
18

---

before the k-th episode. N% (s, a, s') ) is defined by the same token. Using this notation, we can further define the empirical transition by Ph (s' s, N (s, b, o0) (N a, b). (s, = 0, set Pk (s' 8, 6) 1/8.
We define the empirical variance operator
V a) = Var Var,, (Pt V (s')
(14)
and true variance operator
as, = Var, (l (8')
(15)
The bonus terms can be written as
(s, a (s, (s,
(16)
where
(V + +hi+a) /2 (8,
H
1 as) =
(17)
max (s,
a, b),1]
max (s,
and the lower-order term
(), =
H P (V/ vhttt) (s,
(18)
for some absolute constant C
The following lemma is the standard concentration result. Lemma 8 (Lemma 21, Liu et al. (2021)). Let C₁ be some large absolute constant. Define event Ei to be: for all h, 8, a, b, s' and k E [K].
P PM)) Vhtt1
(s,
sc
Vit (s.0.h))
max N (3.0,)).1 max (c,,,,))
min ( (s1ss,,,, (T.n)
(P% - PPh) (s' s,a,
(19)
1a
max (s.ob)))
max Nx(o,,,)))11
PPt Ph)) (: 5, a b)
S Selv max (N
We have P (E1)21-2 p.
The following lemma shows the upper and lower bounds indeed the upper and lower bounds of the best responses.
Lemma (Lemma 22, Liu et al. (2021)). Suppose event E, holds. Then for all h, 8, a, and e [K]. we have
(s, ofa² as, 2 Q (s, 2 2, (5)(s) Vi (s) (t("t(s)) 2 v*.
(20)
Lemma 10 (Lemma 23, Liu et al. (2021)). Suppose event E₁ holds. Then for all h, s, o, b and
E [K]. we have
Wh (vi+z + vh+t1) /2
Vnvat (8,
(21)
S max (N) b).
<4HP,, (V -hh+t) (s, (s, b) +
1+
19

---

Proof of Theorem 4. Suppose event Ej happens. We define
A = V/ V2) (sh)
ch = D - (2h - 2x) (sh at 0%)
(22)
<h = Ph [+++ x (s att 68)) - A
Using standard decomposition techniques we have
A = c. + h 2%)) (shs af bk)
$ ch + 2 + 27 + Ph (Vi+z - v (oh ami b%))
PA (vk
V vh+t)) (sh aht b%)
Sch 2 + 27 Pr Vh+t1 kbn11) (sh oh. + 02
h+1
2
H
max N
Ph (vi h+1
V/h+i) (sh af.
<ch
2 Ph (Vi++ vh+t) (sh axi bh) 2020
S max (NZ 13
$ ch
1
C3
Ph (vhin Virti) (sts att bh)
H
T (vie + vh+ti) /2 (sti ans 6%)
2 N (stt at. bb) 1
+ 4o20
max { NN (s ax, 6%) .1]
max
(23)
By Lemma 10,
T7k h
(v h+1 + vh++) /2 b))
max as,
HiPk Vk V vh+11 (8,
V.VE h+i (s, +
H2
+
max (s,
max (s,
max b)),
WV WVaVet (s, PA (vR h+l vhtts) (8,a,b)
H2VS
Sea
+
max (s,
max (s, b).
(24)
where eq is some absolute constant. Define cs == 402cr cs and = 1 cs/ H. Now we have
(V NAVa hit (sf, az b/))
S
A A + ngt + ch +
V NK (s at, 64) + N (3% at 6%)
Nà (st ah, 6%)
(25)
Recursing this argument for h E [H] and summing over
K
H
(1
(V VVnViti VT* (5 at, b%)
H²
x ch + k 2 +0
max (N/, +
max (Nk 1)
max {N%, 1]
k=
(26)
20

---

It is easy to check that } and { are martingales. By Azuma inequality, with probability least 1 p.
C S O(HУHКI k= 2k=1 s S O(HVHK))
(27)
Now 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 Pa.a and the i + 1-th update of Ps.a do not exceed 2
We define mmx = max (i) 2 S derive general deterministic result. Let I. be the set of indexes of episodes in which no update triggered. By the update rule we have |X:0| S SA ( + 1). Let (k(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 X' = { (k, h) k E K.C ha(k) + 11 S h < H}.
}H} ( + 1. To facilitate the analysis, we first
Let w = fw 2 0
E H, K} be a group of non-negative weights such that wh S 1 x K]] and w = for any (ki h) E X. As in Zhang et al. (2021b), We can
for any (k, h) E [H] calculate
K
H
NE
afh
K
(fhi (s) N,,,), (s, = -2-11
V/2
V2-1
wxx
+ 8SA (ogg((H) + +4)
2i-1
3=3
kmax
K H
(ski (h) = (s, o) = 21-1
2
Vuz 8SA (Iog;(KH) + +4)
2
8,0
1=3
1=1 h=1
Imax
E Σm
(sh = (s, N/ =
2
8,0
K H ΣΣ
(st at) = (8, N/ ((,, 2--1 wh
+ 85A (KH) +
1=
K H1
SAimax
w + 8SA (KH) + +4)
k=1 1=
(28)
By plugging w VnVa' (5h a bt) L[(ks, h) X and wî 1[(k, h)) $ X1 we have
VV Vit ( ax b))
H2
1
max (Nz. 1} +
max (N4 1}
max { ( 1}
k= 1==1
K H S. Sii
K H
50 0
Wn V h+1 (5h, (/) T(kks 1) & X1 + S Aimax
Σ k=1
[(kk h) $ 21 + S²A logo (0g +1
==
h=1
K H
0
SAimax
ΣΣ
Wn Viti (sh at, b9)) I[(k,h) h) & X + / SAimax + S²AA log, (KH)
+ +|/00)
A=1 h=1
(29)
21

---

By the Law of total variation and standard martingale concentration (see Lemma C.5 in Jin et al. (2018) for a formal proof). with probability at least p. have
ΣΣ vn Viti (sh ah. so H1 <0 112))
(30)
By Pigeon-hole argument,
K
11
(o.ab)
ΣΣ
1
Σ
Σ
+HSAAB S OWVFFABBK+HSAD
max {NK
k=1/=1
,. (s,a,b)>0
(31)
K
N
ΣΣ
E
Σ
HSAB < O(HSAB.).
(32)
max {N }
k=
s,a, S.a.b. (8,0.))00
Putting all relations together, we obtain that
K
Regret(K) (K)
Σ
Vi -1
(81) (81) (0)) (VHBSABKL++ H AB²)
(33)
1=1
which completes the proof.
D.2 Multi-batched Algorithms for Linear Markov Games
Algorithm 5 Multi-batched Algorithm for Linear Markov Games
1: Require: regularization parameter À
2: Initialize: A₁ = Ag Alg
3: for episode l 2, K do
4: - (5 6,, (5) a7 (7) + Ala
5: end for
6: if 3h E [H) (A 17 det det(An) then
7:
V + 0, V f 0
8:
for step h = H, - 1, do
9:
An f A
10:
w + (At) k-1
15 0% bl. (ra 0h b/) + h+1 (3)+
11:
wh + (MK) -ボ= 618 4h, b7)) (rn ah1 07) + V (
12:
Th(:))) B (N -
13:
01(s)) ( +
()(.)) + ( (T)TT (....))) [(: -T
15:
For each 8, let m)( + FIND LIN__CCE((,, 2 (cf. Algorithm 2 in Xie et al. (2020))
16:
(T) + [a (s, a, b) for each
(x) + E B(a (x) 2* (s, a, b) for each
18:
end for
19: else
Q + Ø k- 2¹ + 2--1 Th + Th k-1 Wh. E [
20:
21:
end if
Proof of Theorem 3. Let (ki.... AN be the episodes where the learner updates the policies. Moreover, define by max(k; : E [Nbacch), k; < k). Moreover, denote the marginals of Th as Uù and vi
22

---

Part 1: Upper bound of the batch number. By the updating rule, we know there exists one
h [H] such that (ct(A
v d (-1)) which further implies that
1),
H
H
II
det (A))
II h=1
det (A -A
h=1
This yields that
H II
H1
det An
"
Naatch
II det() = 17 Noatch 2
(34)
h=1
h=1
On the other hand, for any h E [H.. we have
H II
H K-1)
det A
KNbatch)
s II A=1
det(A))
(35)
h=1
Furthermore, by the fact that | $ 1, we have
K
A
(sh h ah (s oh. 1/) + AIa 3 (K + A) la.
k=1
which implies that
H
II
det(AA
(
s (K + 2)
(36)
1=1
Combining (34), (35), and (36), we obtain that
dH log
[ + K )
Nbath
log
which concludes the first part of the proof.
Part2: Regret. We need the following two lemmas to bound the regret.
Lemma 11. For any (s, b, k. h), it holds that
(,, 2(H - + 1)e s Q as,,a, s Q (8, < (n(s,a,b)) +(H - h 1)c,
and
(1 h h < V/ " (s) V Vi (5) S V/ (s) 2(1 h 2)e.
Proof. See Lemma 5 of Xie et al. (2020) for a detailed proof.
Lemma 12. For all (s, as,a,b b, h, k) and any fixed policy pair (1i, v), it holds with probability at least
1 8 that
(d(s,,,b) b). w Qtii" (s,a, aaab -Ph (v h+1 V/44g)
(s, a,a))) b)
- r (s, a.a))). b),
(((s,,,)), uz)) Q4: (s, a) - Phh (v Vitts)
(s, a, b)
< The (s, a, b).
Proof. See Lemma 3 of Xie al. (2020) for detailed proof.
We define
t = the (s/) - vhe (s/t),
ch Elst..1 Stt at b1] 8k 0h+1:
2h ((a.))un 12 (s/ a.aa,)]] b)] - Q (s), an bl)),
2 Baa (s @h (s a, b)] 2 (shh at b..).
23

---

By Lemma 11, we have
Ve (51) -V- - (s1) (81) + 88
Vi+
S (s1) (+(1)) 8
8
vi L (x1) + K
8 + K
(37)
where the second inequality uses that HK... By definition, we have
o = Via (5h) (x(()) (s/)
((a 12 ( b.b] =(a.))= 14 (0%, a, 6]]
( &
an bn)) - 2¹ (s on b%) + + 2n.
(38)
Meanwhile, for any (s, as,,,,,K k,,,,,)). h), have
2h a)) 2 (s, (s. b) (( ((s, + r (s, a, b)] ) To(s,,,)) 2 (s, a. b)]
(wh wht ) To(s,, 2T (s,
By Lemma 12, we further have
@he s a, b)
-hh (s,,) + +4 (s, 2h (s, & (T
(39)
Plugging (39) into (38) gives that
ot PA ( (V Lhe kht1) (8, b, 2h (s, + + -
5 + ch + th I + 4T (s,
Hence, we have
K
K
H
K
8
(ch + 7h -
+
by
h
(s%
k=1
k= h=1
1=
s Ö(H v VKK)
(sh
(40)
k=1k=1
where the last inequality uses the Azuma-Hoeffding inequality. Note that
r (s ah bl.) ( a by.)
det(AAt)
<
I /n. det(A
which implies that
K H pbe (sf at. b/) S vn ΣΣ Jem
K H
Σ> Arm
( a b/) < HO
(41)
where the last inequality uses the elliptical potential lemma (Abbasi- Yadkori al., 2011). Combining (37), (40), and (41), together with the fact that 2, we obtain
Regret(K) Ō((o>>H<K)
which concludes the proof.
24

---

D.3 Multi-batched V-learning
In this section, introduce the multi-batched version of V-learning (Jin et al., 2021) for general-sum Markov games. Our goal is to minimize the following notion of regret. Let V (s1) be the expected cumulative reward that the Wt player will receive if the game starts initial state 81 at the 1 step and all players follow joint policy æ. Let # be the policy executed at the hthh episode. The regret is defined as
(1li** j.h
Regret K)
Σ
max 3
V
j.b
(81):
(42)
where vl.** 3ih is the best response of the 7th player when other players follow Ā. j.h
Algorithm 6 Multi-batched V-learning
1: Initialize: (s(s)
H + h, (s) 0, 8)
1/A, trigger set L
{2--1 2' < KHH ....
2: for episode h = 1,... K do
3: Receive $1.
4: for h I,.... H do
5: take action on n1 (- sa). observe and 81411
6:
== Nn (8n) t Nn (5%) +
7:
V. ($h) t (1 a ar) Vn (sh) + az (rh + Va+i (8u+1) + B(t))
Vn (sk) min { H +1 - h, Vn (sw)
8:
9:
T (. (.1%)) ADV BANDIT LUDATEE
ahe
H Vn+1 (sh+1)
(sh. h))h adversar-
ial bandit.
10:
end for
11:
if 3s. (s) E C then
12:
k
end if
14:
end for
The multi-batched V-learning algorithm maintains a value estimator (s), counter (s), and policy Tn for each and h. We also maintain S x H different adversarial bandit algorithms. At step in episode k, the algorithm divided into three steps: policy execution, V-value update, and policy update. In policy execution step, the algorithm takes action ag according to T and observes reward Th and the next state + and updates the counter N₁ (s,). Note that क. updated only when the visiting count of some state (s) doubles. Therefore it ensures a low batch number.
In the V-value update step, update the estimated value function by
VA (sn) = (1 - an) Vn. (8k) + ar (rn + Vh+1 (88+1) + B()),
where the learning rate is defined
#+1
-1 az), af= oi II (1-az)- j=it1
0r H+
Ø=1
and B(t) is the bonus to promote optimism.
In the policy update step, the algorithm feeds the action an and its "loss" H-rA Va-r( to the (sh, 11tt adversarial bandit algorithm. Then receives the updated policy my (- sn).
CANDIT_UPDATTE UPDATE subroutine Consider a multi-armed bandit problem with adver- The ADV B__BANDIT
sarial loss, where we denote the action set by B with B3| = B. round f, the learner determines policy 0, e Ag. and the adversary chooses a loss vector & E [0, 1 Then the learner takes
25

---

an action by according to policy 8., and receives a noisy bandit feedback & (b.) [0, 1], where &e (bx) 4, br] = & (bx). Then, the adversarial bandit algorithm performs updates based on b and & (6e). and outputs the policy for the next round 0(+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.
Assumption 4. For any t N and any E (0, 1), with probability at least 1 - ô, we have
max OE
Σ at (,), ()) S (((,,,,oo(11/))
(43)
We further assume the existence of an upper bound {(B, t, log(1/0)) 2 Ev= & (og_(())))1))) where (i) E(B, I, log(1/0)) is non-decreasing in B for any 1, 6; (ii) E(B, I, log((/))) is concave in I for any B, 6.
As is shown in Jin et al. (2021), the Follow-the-Regularizee Regularized-Loader (FTRL) algorithm satisfies the assumption with bounds E(B, t, log(1/5)) s log(///8/ and E(B, t, (og(1/6)) s O(v BI (B/)). And will use FTRL as the subroutine in algorithm.
For two-player general sum Markov games, we let the two players run Algorithm independently. Fach player will use 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.
Theorem 13. Suppose we choose subroutine ADV DDV_BANDIT JUPAATE as FTRL, For any 6 E (0, and K E N, let log( (OS(/A///)) Choose learning rale and bonus {B(1) K
3(1)
c. / H Ac/t so that E.= (13 = = (VH*Ae/t) for any t [K], where A max, A, Then, with probability at least 1 6, after ranning Algorithm for K episodes, we have
Regret K)) S O (VHASAL)
(44)
And the batch number is Ogg K).
Proof. The proof mainly follows Jin et al. (2021). Below we list some useful lemmas, which have already been proved Jin et al. (2021).
Lemma 14 (Lemma 10, Jin et (2021)). The following properties hold for af
1. Vi < Ele of <
2 and 5 Ei= af ; < 2 for every 2 1. Vi VE
2. maxie]| of < 24 and Σ (at) <
24 for every t 1.
3. Eee of = иt for every 2 1.
V2 . j.h
The next lemma shows that V an optimistic estimation
in
Lemma 15 (Lemma 13, Jin al. (2021)). For any 5 (0, with probability at least - 8, for any (s, h, k.j) S x H x [K] x [m], Vih (s) 2 V t
(s)
And we define the pessimistic pessimistic V-estimations V. that are defined similarly as V and V. Formally, let t (s), and suppose was previously visited episodes k- J....,, k² < k at the h-th step. Then
(H)(s) = max
0,
at
Tish
ss
a
+ VA (sh+.)) 3(0)
(45)
The next lemma shows V.e (s) is lower bound of vith (s).
26

---

Lemma 16 (Lemma 14, Jin et al. (2021)), For any ò E (0, 11, with probability at least 1- - 6, the following holds for any (s. h. k. E S x [H] x [ x [m]] and any player j. V,, S V (s).
It remains to bound the gap K max; (vi,, vt.) (81). For each player j we define 57, == Vith (s)) VIJ (sh) 2 The non-negativity here a simple consequence of the update rule and induction. We need to bound of == max, 8i,x- Let n = N (sf) and suppose sft was previously visited at episodes k1 ,.,.... A. < k at the 1-th step. Now by the update rule,
(o%)
jAA Vih (%)
a S
H + Σ
(Vihtz - V shhtt) ) (shin)) + 2537 (1)
n/
i=1
14
(46)
(ihtt - Vikt k/att) ( (shins) + 483 (0)
S a m
+
n
i=1
0 H +
0²
Ske
shht + O
( HE (Ai (Ar, 1) + /133//18
1=1
The third line holds because we use FTRL as the subroutine, (2( = c. VH3A Aut/t, and due to our doubling scheme we have ((n s 2n And in the last step we have used Ei= 0g,3,, = [E (A,, t,t) + /H*At/t).
The remaining step is the same Jin et al. (2021). Summing the first two terms w.r.t. k;
K
K
H
HT
k = 0) SHH,
(47)
k=1
K
n
K
K
h+
<
a n S
1+
H
8
h+1
(48)
Am
2m1
k 1
i=n
+1
km
Putting them together,
K
K
K
n
K
H3L
a
H +
+
Σ
HE
(h + V
nyt
k=1
A=1
k=1
(49)
K
K
11
< HS +
1+
1++1
HE (A.
+ V
n
k=1
Recursing this argument for h E [H] gives
K
8 S eSH² e
Σ
H K
0
HE
(A,nl.t) + +V
H3t
(50)
n
h=1k=1
By pigeonhole argument,
(x)
HE (A, + VHDO./nt /HPO)nn)=001)
0(1) Σ
Σ HC(A, + V
H3,
n
20(1) Σ HE (A). + VIENK(60)
(51)
s OO +VHSSKI
27

---

where in the last step we have used concavity. Finally take the sum w.r.t h E [H], and plugging
EBB, I,,,,,, s O( Bt we have
Regret(K) 50( 20 (VHISAA))
(52)
28


Reviews:
[{"review_id": "zzGyssJYgo", "reviewer": "Reviewer_bZKJ", "summary": "This paper provides a general framework for analysing any ‘mini-batch’ or rarely switching algorithm in the presence of delayed feedback. This approach covers bandits, finite horizon MDPs and finite horizon Markov games. The results provided match or improve on the best-known results for delayed feedback in settings that have been studied before, and provide the first bounds in some settings where delayed feedback has not been studied before. ", "questions": "The two results in e.g. theorem 1 are a bit confusing and the difference between them is not well explained. Is the second one (7) on the expected regret and the first (6) on the high probability regret? For (6), I am assuming that q is a parameter which can be chosen, can any guidance be provided for how to choose it? Does it depend on \\delta?\nI am interested in whether experimentally these rarely switching algorithms actually perform better than algorithms tailored to the specific setting, or just versions of optimistic algorithms that only use available data?\nA couple of times ‘minimax optimal’/’tight’ is stated. Are there lower bounds for all these settings with delayed feedback?\nCan the lower bounds/best results for the non-delayed settings be added to the table of results to enable us to clearly understand what the impact of delayed feedback is? \nIn the general algorithm provided in section 4 and algorithm 2, do we need to know the delay distribution to define the batch lengths? The example in the text would suggest that we do, but the pseudo-code does not mention it.\nIn the introduction it is mentioned that the sub-exponential assumption on the delay distribution is only sometimes needed, yet I cannot find any discussion of when it is used for the main results. Is it needed for all results in Theorem 1?\n", "limitations": "Very brief discussion of limitations in conclusion", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "It is nice to have a comprehensive study of delayed feedback in various settings. It is interesting that phase-based algorithms allow one to deal with delayed feedback effectively in a variety of settings. It is nice that the general framework provided in this paper allows us to recover the same bounds as for algorithms for specific settings and provides new bounds in settings where delayed feedback has not been studied previously. ", "weaknesses": "The writing and clarity could be improved. I also found the structure quite confusing with a couple of pages dedicated to Markov games while a lot of the content needed to understand that section (e.g. related work and algorithms) relegated to the appendix. The amount of space dedicated to Markov games also meant that there was not sufficient room to discuss the results for delayed feedback in bandits/RL, nor for all details of the method/results to be provided (see the many questions below).\nThe idea of using phase-based algorithms which switch arms less frequently for delayed feedback is not new and has been used in e.g. Lancewicki et al (2021), Howson et al (2021), Pike-Burke et al (2018), Vakili et al (2023),… This should be stated in section 4. Additionally, I believe Vakili et al (2023) also provide the same bound for the linear bandit setting with delayed feedback as is established in this paper, so this should also be checked and added. \n\nReferences: Vakili, Sattar, et al. \"Delayed Feedback in Kernel Bandits.\" ICML, 2023.\nPike-Burke, Ciara, et al. \"Bandits with delayed, aggregated anonymous feedback.\" ICML, 2018\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful reading and valuable suggestions!\n\nQ1. Writing and clarity\n\nA1. To comply with the page limit, we have moved the details about Markov Games to the appendix. We will arrange the contents to ensure clarity and coherence for the readers. We appreciate your valuable feedback.\n\nQ2. Novelty of our idea\n\nA2. We point out that unlike previous works that propose different phase-based algorithms and analyze them case by case, our work introduces a generic class of algorithms that can be integrated with any multi-batched algorithm in a black-box manner. We also provide a unified theoretical analysis for the proposed generic algorithm. Moreover, papers such as Howson et al (2021) and Pike-Burke et al (2018) fail to fully exploit the potential of multi-batched algorithms, and their bounds are inferior to ours. (see Table 1 for a comparison of the results) \n\nQ3. Checking Vakili et al (2023)\n\nA3. Our work does not consider the kernel setting, but we conjecture that our framework can handle this problem by designing a multi-batched algorithm for kernel bandits. We appreciate your suggestion of this related work and we will discuss it further in the revision.\n\nQ4.Explanation on results in Theorem 1\n\nA4. Both (6) and (7) are high-probability regret bounds. Here (7) holds with probability $1 - \\delta$. Thank you for pointing this out and we will clarify in the revision. The main difference is the use of concentration inequality for the number of delays. (6) uses concentration for sub-exponential delays, and (7) uses concentration in the quantile form. The parameter $q$ can be any real number in (0,1) and does not rely on other parameters such as $\\delta$. \n\nQ5. Numerical experiments\n\nA5.We will consider adding numerical experiments to compare the performance with algorithms tailored to the specific setting. However, we note that all these algorithms are optimistic algorithms, and the main difference lies in the timing of policy update, which directly affects the regret.\n\nQ6.Lower bounds\n\nA6.Here we can give a simple lower bound. Consider the case when the delay $\\tau$ is a constant. For this case a trivial lower bound is $\\Omega(R\\tau)$ where $R$ is the upper bound of reward in each episode ($R=1$ in bandits, and $R=H$ in episodic MDP), since if we run the algorithm for only $\\tau$ episodes, then the algorithm cannot observe anything, and it cannot do better than tossing a coin. Together with existing lower bound for undelayed problems, we obtain a lower bound $\\Omega(\\text{undelayed lower bound} + R\\tau)$. By this lower bound, we know our results are tight in bandits setting. In MDPs and MGs, we improve existing results or provide the first line of study.\n\nQ7.Do we need to know the delay distribution in advance?\n\nA7.We do not need to know the delay distribution in advance. Moreover, we do not have to predefine the length of each batch beforehand. We simply run the batched policy until we collect enough data for the batch to stop.\n\nQ8.Where is the sub-exponential assumption used?\n\nA8.The sub-exponential assumption on the delay distribution is needed when we derive regret bound (7) in Theorem 1. It is used for concentration of delays.\n"}, {"review_id": "GdEgOk8ced", "reviewer": "Reviewer_nwcC", "summary": "The paper presents a new framework for handling stochastic delayed feedback in general sequential decision-making problems, encompassing bandits, single-agent Markov decision processes (MDPs), and Markov games (MGs). The authors introduce a novel reduction-based framework that converts any multi-batched algorithm for sequential decision-making with instantaneous feedback into a sample-efficient algorithm capable of managing stochastic delays. They provide various examples, demonstrating the efficacy of their framework in different scenarios, and present several new results, improving existing findings for linear bandits, tabular RL, and tabular MGs.\n", "questions": "Can you elaborate more on the specific limitations of the current state-of-the-art methods that your framework is intended to overcome?\nCan your framework be generalized to handle other types of delays, or is it specifically designed for stochastic delays?\n", "limitations": "Can we develop new algorithms that work even better than existing multi-batch algorithms? \nThe paper leaves open the question of whether their results are tight for MDP and MG with delayed feedback. Thus, there is room for future work to tighten these results.\nThe paper suggests that a multi-batched algorithm with a smaller batch number for tabular Markov games could be derived, which may provide more efficiency, but does not provide it in this paper.\nIt remains unclear if their findings and the proposed framework will translate effectively into practical scenarios. The authors have not provided any real-world evaluations or use-cases to support their claims.\n", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The paper addresses a significant and practical issue in sequential decision-making: stochastic delayed feedback. It is well-motivated with practical examples like recommendation systems, robotics, and video streaming.\nThe paper presents a novel, reduction-based framework that shows versatility across multiple domains (bandits, single-agent MDPs, and MGs), exhibiting a comprehensive approach.\nThe proposed solution offers theoretical advancements by improving the regret bounds for linear bandits and tabular RL and provides the first theoretical guarantees in RL with function approximation and multi-agent RL settings.\nThe authors effectively integrate existing multi-batched algorithms into their framework, illustrating the generality of their approach.\n", "weaknesses": "It seems that the contribution is rather incremental. The idea that multi-batched algorithms can be used in delayed setting is not new. What appears to be new is some new theorems bounding the regret when using multi-batched algorithms for delayed settings in a variety of settings. \nThe authors could strengthen their paper with some simple experiments to add to the theory\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful reading and valuable comments!\n\nQ1:Is the contribution rather incremental? Explain specific limitations of the current state-of-the-art methods.\n\nA1:We respectfully disagree with the reviewer’s argument that our contribution is rather incremental. Please see our **common response** for more explanation.\n\nQ2: Can our framework handle other types of delays?\n\nA2: Our framework is specifically designed for stochastic delays. As we mentioned in section 1.1, our framework achieves a better result than directly applying the reduction from adversarial delay setting to stochastic delay setting.\n\nQ3:Other limitations\n\nA3:For other limitations such as designing multi-batched algorithms with smaller batch numbers, we have discussed in our paper and we leave this as future work. One possible direction is to follow the idea of Zhang et al. (2022b) and adapt their algorithm to linear RL/Markov game setting. In terms of numerical results, we will consider adding some experiments in the future version. Thanks for your suggestion. \n"}, {"review_id": "TeRuFZmeIz", "reviewer": "Reviewer_p5oe", "summary": "This submission studies the problem of learning from delayed feedback in various online learning settings including multi-armed bandits, linear bandits, linear MDPs, RL with function approximation, and various markov game settings (among others). Delays are assumed to be i.i.d. random variables. Additionally, they are sometimes assumed to be subexponential random variables. \n\nThe authors main result is a framework for sequential decision making with delayed feedback. Their framework makes use of \"multi-batched\" algorithms, which, as the name suggests, runs in batches. In each batch, a multi-batched algorithm outputs a sequence of policies to be used one-after-one (which are trained using data from previous batches), as well as a stopping criterion which decides when to stop the current batch. After a batch is run, the new data is incorporated with the existing data and is used to produce a new sequence of policies and stopping rule for the next round.\n\nAt a high level, the framework converts a multi-batched algorithm for the setting of interest (e.g. linear bandits) to one which can handle delayed feedback. The key idea is to run the policy given by the multi-batched algorithm for some extra time-steps in order to satisfy the stopping criteria. The authors are then able to bound the additional regret due to the delayed feedback by bounding the number of additional steps needed to satisfy the stopping criteria. \n\nBy instantiating their framework in the various settings listed above, they can obtain provable guarantees on the learner's regret. The rates obtained improve upon existing results in some settings (e.g. linear bandits and tabular MDPs), are slightly worse in others (e.g. multi-armed bandits), and are the first of their kind in other settings (e.g., RL with general function approximation). ", "questions": "I was a bit confused by the notation in line 9 of Algorithm 2. Shouldn't this read (both in words and mathematically) \"Collect trajectory feedback in this batch that is observed **by** the end of the episode\"?\n\nWould your framework be able to obtain stronger results if, instead of Assumption 2, the delays are assumed to be subGaussian random variables?\n\nA reference is missing to \"Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learning\" by Huang et al.", "limitations": "The authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The problem of delayed feedback in online learning settings is a well-motivated problem with many real-world applications. Furthermore, the authors are the first to obtain results for learning with delayed feedback in a variety of (important) settings such as RL with general function approximation, as well as improve upon existing results in others such as linear bandits. \n\nThe two main strengths of this paper are the simplicity/clarity of the proposed framework and the sheer number of results the authors are able to obtain using their framework. It is impressive that results for so many important settings are able to be obtained by applying one simple framework. Moreover, all that is required to use their framework is a multi-batched algorithm, which already exist in the literature for many online learning settings. ", "weaknesses": "At times, the writing feels a bit rushed and as a result the submission may be a hard read for someone who is not an expert in RL theory. Specifically, I felt that the mutli-agent results were somewhat lacking in detail. (For example, why is the CCE the \"right\" solution concept, what happens when all players do/don't play a CCE policy, etc.) This is probably due to the fact that the authors have lots of results, which they wish to highlight in the main body of the paper. One suggestion would be to move either subsection 5.1, 5.2, or 5.3 to the Appendix, and use the extra space to provide more background/detail/hand-holding for the reader.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful reading and valuable comments!\n\nQ1: Writing and readability\n\nA1: To comply with the page limit, we have moved the details about multi-agent Markov Games to the appendix. We will polish the contents to ensure clarity and coherence for the readers in the revision. We appreciate your valuable feedback.\n\nQ2: Why we consider CCE in general-sum Markov Games?\n\nA2: Both NE and CCE are common learning objectives in Markov games. However, finding the Nash equilibrium is computationally hard in general-sum Markov games. In this case, a coarse correlated equilibrium (CCE) is a more tractable notion of equilibrium that strictly generalizes NE. Unlike NE, a CCE can be computed efficiently in polynomial time.\n\nQ3: Notations in line 9 of Algorithm 2\n\nA3: You are right. We will correct this in our final version. We mean that in the $k$th episode, after executing the batch policy we collect all the feedback that has been delayed until the end of the episode.\n\nQ4: Stronger results using subgaussian assumption\n\nA4: You are right. If we use subgaussian assumption instead of the subexponential assumption, we can get a stronger result since we use different concentration inequality. In fact, subgaussian assumption is stronger than subexponential assumption, since any subgaussian random variable is also subexponential.\n\nQ5: Reference to Huang et al.\n\nA5: Thanks for your reminder. We will add reference to this paper in our revision.\n"}, {"review_id": "W3nqr0st1W", "reviewer": "Reviewer_EWXd", "summary": "The paper studies the problem of sequential decision-making problems with delayed feedback. The authors propose a reduction from standard sequential decision-making algorithms to the following problem providing regret guarantees in many settings: linear bandits, tabular RL, linear and general function approximations RL, tabular and linear zero-sum Markov Games, tabular general-sum Markov Games.\n\n", "questions": "See weaknesses. \n\nSome minor questions:\n- In algorithm 2, do we know $\\tau_t$ or are we waiting until we do not receive the feedback, and then we can evaluate $\\tau_t$?\n- From a technical point of view what are the main challenges in converting regret bounds from the \"classic\" setting to the delayed feedback one?", "limitations": "The paper is mainly theoretical and the algorithms presented are not easily usable in practice.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The authors improve previous results in the delayed feedback setting for multi-armed bandit, linear bandit, tabular MDP, tabular multi-player general sum MGs.\n- The authors provide the first regret guarantees (in the delayed feedback setting) for linear MDPs, general-function approximation MDPs, and tabular and linear two-player zero-sum MGs.\n- The strategy is simple: \n   - single-agent: apply multi-batched algorithm for RL to the delayed feedback setting running some extra steps depending on the feedback delay $\\tau_k$.\n  - zero-sum tabular and general-sum tabular: using the doubling trick to update the policy.\n  - zero-sum linear: update the policy when there exists $h \\in [H]$ such that $\\text{det}(\\Lambda^k_h) > \\eta \\cdot \\text{det}(\\Lambda_h)$.", "weaknesses": "### Presentation\n\nThe presentation of the paper can be improved. The paper proposes a general strategy to convert multi-batch algorithms to the delayed feedback setting, changing (if I understood correctly) when the policy is updated. This is a simple and elegant transformation and it is not very clear from the presentation where the authors divide the transformations into three sections without providing this connection between them. I suggest providing an algorithm for the general setting which changes the update depending on the setting. \nMoreover, there are some minor issues in the way the algorithms are presented:\n- provide the input parameters in a clear way (e.g. algorithm 1 what is $l_m$?, algorithm 2 how can we compute $\\tau_t$ since it is a random variable, algorithm 4 what is i?)\n- provide output to the algorithms.\n\n\n### Novelty\n\nThe simplicity of the strategy can be seen as a lack of novelty (due also to the previous point (see Presentation)). I suggest making more clear the challenges. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your careful reading and valuable comments!\n\nQ1: Presentation of the framework\n\nA1: In fact, the framework we propose in Algorithm 2 is already for the general setting, which covers both single-agent and multi-agent, both tabular and linear. This framework can transform any multi-batched algorithm into an algorithm in the delayed setting, regardless of the specific type of batches. The “three sections” you mentioned are a strategy for designing multi-batched algorithms, and are not part of the main framework.\n\nQ2: Parameters in Algorithm 1\n\nA2: $\\ell^m$ is the length of the policy sequence $\\pi^m$ calculated by the algorithm. It is not an input parameter. For example, in the phase elimination algorithm for linear bandits in Lattimore and Szepesvári(2020), $\\ell^m=T_m\\approx 2^m$ (for the definition of $T_m$ see Appendix C).\n\nQ3:$\\tau_t$ in Algorithm 2\n\nA3: In algorithm 2, we do not know $\\tau_t$ in advance. In fact, we do not need to know $\\tau_t$ or evaluate it during the whole algorithm. We only wait until we receive enough feedback so that the stopping condition in this batch is satisfied. In other words, the algorithm does not rely on knowledge of $\\tau_t$. It is just a mathematical symbol for ease of presentation.\n\nQ4: Parameter $i$ in Algorithm 4\n\nA4: In algorithm 4, $i$ is used to state the trigger set $\\mathcal{L}$. $\\mathcal{L}$ contains all powers of 2, as long as they do not exceed $KH$.\n\nQ5: Outputs of the algorithms\n\nA5: We will clarify the output of the algorithms in our revision. Most of them are sequential decision making algorithms that output a sequence of policies. Thanks for your suggestion.\n\nQ6: Novelty and simplicity\n\nA6: Our framework is simple yet effective, as it can handle various settings, and using our framework we obtain many results that match or surpass previous results. We believe that simplicity and effectiveness are also a form of novelty. \nBesides, we also summarize our novel contribution as three points. Please see our **common rebuttal** for more explanation.\n\nQ7: From a technical point of view what are the main challenges in converting regret bounds from the \"classic\" setting to the delayed feedback one?\n\nA7: The key point is to decompose the regret bound into two parts: (i) the regret bound of multi-batched algorithms in the classic setting; and (ii) the additional regret incurred by the waiting time at the end of each batch. The first part follows previous results and the second one uses the property of multi-batched algorithms and stochastic delay. Our proof is simple but effective in the sense that we can obtain a unified result for decision making with delayed feedback. Moreover, when specialized to concrete problems, the obtained results match or even improve existing results. \n"}]

Author rebuttal:
## Common rebuttal for the contributions of our paper:

We respectfully disagree with the reviewers’ argument that our contribution is rather incremental. Here we describe some drawbacks of previous works, and how our work addresses them.

The previous works suffer from several drawbacks: (i) they require case by case algorithm design and analysis; (ii) their regret bound is not tight; (iii) they do not explore some settings (linear MDPs and MGs). 

Our work addresses these challenges, and our contributions are as follows:

(1)new framework: We propose **a generic class of algorithms** that can be integrated with **any** multi-batched algorithm in a black-box fashion. Meanwhile, we provide a **unified** theoretical analysis for the proposed generic algorithm.

(2)improved results and new results: By applying our framework to different settings, we obtain state-of-the-art regret bounds for multi-armed bandits, and derive sharper results for linear bandits and tabular RL, which significantly improve existing results.

(3)new algorithm: we design new multi-batched algorithms for multi-agent Markov games, and handle the delayed feedback in Markov games by combining our framework and the newly designed algorithm.


Meta-review: This paper considers a general setting for sequential decision making, subsuming reinforcement learning with function approximation and multi-agent reinforcement learning, and considers the problem of learning under delayed feedback. The main result is a reduction-based framework which lifts any multi-batched algorithm for sequential decision making into an algorithm capable of handling delayed feedback. Using this reduction, the derive new results for a number of settings including reinforcement learning with linear MDPs or bounded eluder dimension.

Reviewers felt that the paper's approach was novel and potentially impactful. In particular, the authors derive the first and only existing results for learning with delayed feedback in a number of single- and multi-agent RL frameworks. While phased-based algorithms have been used in a number of prior works with delayed feedback, the significance of this paper is to provide a unified, black-box approach, and to derive a bounds for a comprehensive set of settings as a consequence. As such, there was a consensus after the discussion period that the paper should be accepted.

For the final version of the paper, the authors are encouraged to incorporate the clarifications, improvements to writing, and references to related work suggested by the reviewers.
Decision: Accept (poster)