Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback
Authors: Tiancheng Jin
Tal Lancewicki
Haipeng Luo
Yishay Mansour
Aviv Rosenberg
Venue: NeurIPS 2022 Accept (2022)
Keywords: regret minimization
adversarial mdp
delay
reinforcement learning
online learning

Abstract: The standard assumption in reinforcement learning (RL) is that agents observe feedback for their actions immediately. However, in practice feedback is often observed in delay. This paper studies online learning in episodic Markov decision process (MDP) with unknown transitions, adversarially changing costs, and unrestricted delayed bandit feedback. More precisely, the feedback for the agent in episode $k$ is revealed only in the end of episode $k + d^k$, where the delay $d^k$ can be changing over episodes and chosen by an oblivious adversary. We present the first algorithms that achieve near-optimal $\sqrt{K + D}$ regret, where $K$ is the number of episodes and $D = \sum_{k=1}^K d^k$ is the total delay, significantly improving upon the best known regret bound of $(K + D)^{2/3}$.

Near-Optimal Regret for Adversarial MDP with Delayed Bandit Feedback
Tiancheng Jin
Tal Lancewicki
University of Southern California tiancheng. jin @ usc.edu
Tel Aviv University lancewicki @maii.tau.aa
Haipeng Luo
Yishay Mansour
University of Southern California haipengl @ustenng@uuuceddu
Tel Aviv University and Google Research
missour.yishay @gmail.com
Aviy Rosenberg"
Amazon
avivros @ amazon.com
Abstract
The standard assumption in reinforcement learning (RL) is that agents observe feedback for their actions immediately. However, in practice feedback is often observed in delay. This paper studies online learning episodic Markov decision process (MDP) with unknown transitions, adversarially changing costs, and un- restricted delayed bandit feedback. More precisely, the feedback for the agent episode l: is revealed only in the end of episode k: + dk, where the delay d can changing over episodes and chosen by an oblivious adversary. We present the first algorithms that achieve near-optimal VK D regret, where K is the number of episodes and D Σ d² the total delay, significantly improving upon the best known regret bound of (K + 2)2/33
Introduction
Delayed feedback has become fundamental challenge that sequential decision making algorithms must face in almost every real-works application. Notable examples include communication between agents [9], video streaming [8] and robotics
[32]. Broadly, delays occur either for computational reasons, c.g., in autonomous vehicles and wearable technology, or when they are an inherent part of the environment like healthcare, finance and recommendation systems.
Although a prominent challenge practice, there is only limited theoretical literature on delays in reinforcement learning (RL). Recently, [18] studied regret minimization in episodic Markov decision processes (MDPs) but assume that the delays (and costs) are stochastic, i.e., sampled i.i.d from fixed (unknown) distribution, which is limiting assumption since it does allow dependencies between costs and delays that are very common in practice. The case of adversarial delays and costs was also studied recently [28]. However, they focus on full iiliifforration feedback where the learner observes the entire cost function, which is not realistic in many applications, and obtain only sub-optimal regret bounds for bandit feedback (where the learner observes only the costs on the traversed trajectory).
In this paper we significantly advance our understanding of delayed feedback in adversarial MDPs with bandit feedback. More precisely, consider episodic MDPs with unknown transition function,
Research conducted while the author was a student at Tel Aviv University.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Regret bounds for Adversarial MDPs with unknown transition and unrestricted delayed bandit feedback, K is the number of episodes, the total delay, H the horizon, S is the number of states and A is the number of actions. Algorithms presented in this paper appear in grey.
Algorithm
Regret
Efficient
Regret w.h.p
D-OPPO [28]
O(HSVAK3/3 + 22
Delayed Hedge
O(H'SVAK + H /SD)
X
Delayed UOB-FIRL
Ó(H'SVK + SAVD)
Delayed
O(H'SVAR + (HSA) HVD)
Lower bound [28]
0(1 Q(1I/A/SAK + + +HVD
has an additional additive term in the regret that scales linearly with dmaz. One can avoid the dependency in dmaz but with a slightly weaker bound than the one that appears this table- for more details see Remark D.I in the supplementary material.
UUder unknown dynamies Delayed
adversarially changing costs (bounded in [0, Il) and unrestricted delayed bandit feedback, i.e., the learner observes the costs suffered in episode k only in the end of episode k + d where the sequence of delays {d } _ are chosen by an oblivious adversary. We develop the first algorithms for this setting that achieve near-optimal regret and provide a major improvement over the currently best known regret bound [28]- see Table for more details.
In the following paragraph we provide an overview of our contributions and the structure of the paper. In Section we devise an inefficient Hedge [13] based algorithm that treats every deterministic policy as an arm. This can be seen as a warm-up a relatively simple and elegant solution that shows that order v K + D regret is attainable with delayed bandit feedback. Moreover, our adaptation of Hedge the setting of adversarial MDP with unknown transition and bandit feedback presents highly non-trivial algorithmic and technical features that may be of independent interest. Then, we focus on the pressing question: Can delayed bandit feedback be handled both optimally and efficiently? We answer this aftirmatively by presenting two efficient algorithms with near-optimal regret. Through our unique analysis and algorithmic design, we shed light on the great challenges of handling efficiently delayed bandit feedback. In Section 4 we consider a relatively standard algorithm we call Delayed UOB-FTRL, based on the Follow the Regularized Leader (FTRL) framework, and focus on unique novel analysis that may be of independent interest. As seen in Table 1, our analysis of Delayed UOB-FTRL shows regret similar to the inefficient Delayed Hedge. However, has worse dependence on S andd A, and has regret guarantee on expectation rather than with high probability (w.h.p). In Section 5 we propose our final solution which is mainly algorithmic: we introduce the algorithm Delayed
that has novel importance-samplin estimator which generalizes the standard estimator and accommodates to the delays. This approach allows us to follow the path of more standard analysis, but most importantly, ensures w.h.p the best regret so far (see Table 1). The first term of the regret bound matches the best known regret for adversarial MDP with non-delayed bandit feedback [22], while the second term matches the lower bound of [28] up to a factor of (HSA)" 1/4
1.1 Additional Related Work
Delays in RL. While delays are popular in the practical RL literature [39, 30, 8, 32, 12], there is limited theoretical literature on the subject. Most previous work [26, 45] considered constant delays in observing the current state. However, the challenges in that setting are different than the ones considered in this paper (see [28] for more details). As discussed in the introduction, most related to this paper are the recent works of [28] and [18].
Delays in multi-arm bandit (MAB). Delays were extensively studied in MAB and optimization both in the stochastic setting [1, 43, 44, 34, 6, 49, 14, 29, 10], and the adversarial setting [35, 7, 41, 3, 52, 19, 15, 42]. However, as discussed in [28], delays introduce new challenges in MDPs that do not appear in MAB.
Regret minimization in RL. There is a rich literature on regret minimization in both stochastic [20, 2, 21, 23, 46, 47, 48] and adversarial [51, 36, 37, 38, 22, 25, 5, 40, 31, 24, 17] MDPs. Note that regret minimization where d 0 for every episode k.
standard episodic MDPs is special case of the model considered in this paper

---

2 Preliminaries
We consider the problem of learning adversarial MDPs under delayed feedback. A finite-horizon episodic MDP is defined by tuple M = (S, A. H. p. {e jk= 1). where S and A are finite state and action spaces of sizes |S| = S and |A| = A, respectively, Il the horizon (i.e., episode length) and K' is the number of episodes. p :: S x A x [H] + As is the transition function which defines the transition probabilities. That is, ph [s a)) is the probability to move to state s' when taking action in state s at time h. {c² S x A x [H] + [o, 1])
cost functions which are chosen by an oblivious adversary, such that cx (s, a) is the cost of taking action a in state at time h of episode k.
A policy т. : S x [H] + AA is a function such that TA (als) is the probability to take action when visiting state at time h. The value Vi (s) is the expected cost of π with respect to cost function c and transition function p' starting from state in time h, i.e. V, (s;c) = F
Σ#= O2 (8hr, ax) 8h = s) where ETP' [-] denotes the expectation with respect to policy T and transition function p'. that is, av ~ T- (- (w) and s1'+1 ~ P'x Sw' ay).
cearner-environment interaction. At the beginning of episode k. the learner picks a policy T², and starts in an initial state of = Sinit- In each time / E [M]. it observes the current state sh draws an action from the policy ax ~ (+1=f) and transitions to the next state sh41 ~ (115% a The feedback of episode k contains the cost function over the agent's 's trajectory (sf, a ) i... bandit feedback (as opposed to full-information feedback which contains the whole cost function).
This feedback is observed only at the end of episode k + d', where the delays {d jk= are unknown and chosen by the oblivious adversary together with the costs. If d = 0 for all k, this model scales down to standard online learning in adversarial MDP.
Occupancy measure. Given a policy ι and transition function p', the occupancy measure q qa [0, 1] MS A is vector, where 4%. x (s, as,a,s)) s') is the probability to visit state at time h. take action a and transition to state s'. We also denote of T- (s, a) = E.' 9r (x, a, 8') and qi (s) = E. Un (s, a). By [36], the occupancy measure encodes the policy and the transition function through the relations Tala s) = o,." (s.0) g, s (s): (s a. 9,.²' (s.a.>")/7 // (s.a). The set of all occupancy measures with respect to an MDP M is denoted by A(M). Importantly, the value of policy from the initial state can be written as the dot product between its occupaney measure and the cost function,
i.e. V. (smaic) c) (a c). Whenever p' is omitted from the notations g= and V= this means that they are with respect to the true transition function p.
Regret. The learner's performance is measured by the regret which is the difference between the cumulative expected cost of the learner and the best fixed policy in hindsight:
K RK = Σ kka
K
K
K (g. )
(smmit
min
(sjint)
=
min (EA(M)
1=1
where V/l (5)=
Confidence set. Since the transition function is unknown, we maintain standard crinstein-basse confidence sets pk for each episode k that contain p with high-probability. For the exact definition of pk see Algorithms and 9, and the fact that p e pk for every & w.h.p is proved for example in [22] (for more details see the appendix). Using pk we can define confidence set of occupancy measures by
((M, = ( I (Ax) p' E p*),
which is a polytope with polynomial constraints as shown in [36]. Note that as long as E Pk. (MM) C k)M
Additional notations. In general, episode indices always appear as superscripts and in-episode steps as subscripts. Ff (s'(s,,) a) is the empirical mean estimation of (s('' (s, a) based on the trajectories available to the algorithm at the beginning of the episode k. n (s, s') denotes the total number of visits at state 8 in which the agent took action a at time h and transitioned to by the end of episode k- - 1. and n (s. a) Ex nf a, s'). Similarly, m (s. a, s') denotes the total number of visits from rounds j such that + d < k 1 at state in which the agent took action at time
3

---

Algorithm Delayed Hedge
1: Initialization: Set wt to the uniform distribution over all deterministic policies, and pl to be set of all transitions functions.
2: for k == 1, ...; do
3: Execute policy x" sampled from wh observe trajectory { a h=
4: Update confidence set pk: compute upper occupancy bound u" and exploration bonus 6 by:
(s,
max P'P
Σ (T)) TER
j. (s,0) (*TT)=
max 1 v'
-9T I11
5:
for j:j+ k do
6: Observe costs {c, (8), al H J= compute loss estimator e defined in Eq. (1), and estimated
loss by (T) ( 2
7: end for
8: Update policy distribution tttl by: (T) x (x)
(nb* = (()).
9: end for
= =k} denotes the set of episodes such that their feedback arrives in the end of episode k. The notations Ō(-) and S hide constant and poly-logarithmic factors including log(K/ö) for some confidence parameter 8, the indicator of event E' is denoted by [[E}. and x V = max(xx xz, y).
h and transitioned to s', and m a)) E., (s,,,,, =
Simplifying assumptions. Throughout this paper we assume that and D > d are known and that the maximal delay dmaz max d < VD. Both of these assumptions are made only for simplicity of presentation and can be easily relaxed using standard doubling and skipping procedures focus on the case of non-delayed trajectory
as shown for example by [41, 28, 4]. In addition, feedback, where the learner observes the trajectory immediately at the end the episode and only the feedback regarding the cost is delayed. Delayed trajectory feedback mainly affects approximation errors and the ideas presented in [28] for handling such delay apply to our case as well. Finally, the regret bounds in the main text hide low-order terms that depends polynomially in H, and A but only poly logarithaaht K the full bounds appear in the appendix.
3 Delayed Hedge
In this section, we consider running Hedge-based algorithm over all Ω - [H) deterministic policies. Algorithm 1, which we call Delayed Hedge, inefficient but gives the first order-optimal regret bounds for adversarial MDP with delayed bandit feedback. Although the main issue that Delayed Hedge tackles delayed feedback, we note that there are many additional challenges introduced by the unknown transitions and the bandit feedback when we maintain a distribution over policies instead of single stochastic policy.
Delayed Hedge maintains a distribution w over deterministic policies (starting from a uniform distribution), and in the beginning of episode samples policy n² execute. Thus. the expected loss incurred in episode k is Σnen wx(T) (qT ) The algorithm updates the distribution w based on the exponential weights update, for which we need to compute an estimated loss for every policy π E Ω.
To do so, first we estimate the cost in each state-action pair. Due unknown dynamics, following [22] we use the confidence sets to compute optimistic importance weighted estimator that will induce exploration:
(8, (s =s, s, =a] (t
(x) +7
where u/ (s, max Ereo wh (T)g (s, a) is upper occupancy bound on the probability to visit (s, a) in step /t of episode k. and y is small bias added for high probability regret [33].

---

Algorithm 2 Delayed UOB-FTRL
1: Initialization: Set x² to be uniform policy, and pl to set of all transitions functions..
2: for k= 1,2, 2,..... ..., K do
3: Execute policy π², observe trajectory {sh. a hh= update confidence set P and compute
upper occupancy bound w a) eax 9h (s,a).
4: for j j d k do
5:
Observe costs {c (6 ) and compute the standard loss estimator e by
()),a)= (,,,)))1s)) 5,0% =
(2)
as) +7
6: end for
7:
Compute occupancy measure by: g arg argmin "n Estai v(1),
where v0()) = 7 Emaaas Qh (s, (n,
8: Update policy: Th + (a 8) dh (sa))o)tt))))
9: end for
Then, we the empirical transition function be compute the estimated loss (T)
(q=-0" att for each policy я. To ensure optimism, we introduce the exploration bonus ((T)) = max,e -1g - 1I1. As long as the real transition function p in confidence pk: optimism is indeed ensured in the sense that (axx** ,c) b² is always no more than the true cost (n for any policy и and [0. 1]-valued cost function c.
With the estimated loss and the exploration bonus for each n, the distribution w+1 is now updated in a manner similar to that of [15]: w (r) x w*(r)- exp (1)²(=) - E Žij++di e (z)). Note that all information required for this update has been received by the learner at the end of episode k. With the help of all these definitions, we prove the following regret bound for Delayed Hedge, and defer the details to Appendix A including the complete algorithm and regret analysis.
Theorem 3.1. With appropriate choices of parameters, Delayed Hedge ensures Rx = δ (HSSAK + HSD))D) with high probability (w.h.p.).
4 Delayed UOB-FTRL
In this section, adjust the UOB-REPS algorithm [22] delayed feedback and present the Delayed UOB-FTRL algorithm (Algorithm 2)- the first efficient algorithm to attain order-optimal regret for adversarial MDP with delayed bandit feedback. The proof is based on novel analysis without additional changes to the algorithm. Namely, we use standard loss estimators (defined in Eq. (2)). Our algorithm is based the Halloo-thh-Regulariieede
(FTRL) framework, which is widely used for deriving online learning algorithm in adversarial environments. Notable examples are [51] that applies FTRL over occupancy measure space solve the adversarial MDP problem with known transition, and [52] that uses FTRL to achieve optimal regret for MAB with delayed feedback.
In our context, in the beginning of episode k. FTRL computes,
g arg min (g. [.ght) + +(g), (EM)=)A(M.))
(3)
where Lohs Estalee is the cumulative losses observed prior to episode k. and p(g)
Enea. (s, a.) s') log 9u (s, a, s') is the Shannon entropy regularizer. Note that Eq. (3) is convex optimization problem with linear constraints and thus can be solved efficiently [51, 36). The policy nh to be played in the episode then extracted from g² Thus, our algorithm can be regarded as direct extension to MDP of FTRL for delayed feedback. However, unlike the successes in MAB, is highly unclear whether optimal regret could be obtained in adversarial MDPs with FTRL even the transition function is known.
5

---

In Theorem 4.1, we show that Delayed UOB-FTRL enjoys order-optimal regret. Through the key steps of the analysis, we shall take a closer look at the key reason why traditional analysis fails: in occupancy measure space, the interplay between different entries of loss functions is significantly harder to analyze. Thus, many critical properties used in [52] do not hold anymore. The complete algorithm and proof are deferred to Appendix B.
Theorem 4.1. With appropriate choices of parameters, Delayed (AB---rR 2) ensures E [ = Ö(H'SVAK + HSAVHD).
Proof sketch of Theorem 4.1. Let q= :P be the occupancy measure associated with the optimal policy n², We adopt the regret decomposition of [22]:
K
K
K
k
RR-
-", 2 +
Σ b ch
ct).
EST
BIAS:
REG
BIAS2
EST, BIAST and BIAS₂ are standard and bounded in [22] b. Ö(THSAK +H/7))
Now, we focus on bounding REG. To this end, we denote by L. = Σド 2h the non-delayed cumulative loss, and introduce the convex conjugate functions Fx with respect to the regularizer Φ(-):
F =
min {p(g) - (z, q)
(EA(M,A)
We now use F to decompose REG into the following three terms as
K
K
F [ohs) + (g", (*) + F% Zahs 2te
-
Σ
+ Lb) -0"" (4
km
kmml
K
Fobs Φه) F+ -ybo - (-FX - 2 F - F
(4)
k=
The first term associated with the unseen loss 25. It is relatively standard and bounded by OKK w.h.p. The second term can be regarded as the regret of a "cheating" algorithm which does not suffer delay and sees one step into the future. This term can he bounded by ((H/n) similarly to [15]. The third term which only relates to delayed feedback, is the most critical object in the analysis.
In the previous work of [52] for multi-arm bandit, the authors managed to rewrite and then upper bound the delay-caused term for every episode k by
S. (ct V xτ²) VV x²²1) do Sn Σ x00) (Ia(1)-Lag00))
Lg (i))
SEINI
where [N] is the set of arms and p²)) is the probability that the algorithm chooses arm i in episode k. Here, the first step uses Newton-Leibniz theorem and the differentiability of convex conjugates, and the second step follows directly from [52, Lemma 3]. Importantly, the second step is largely based on the specific structure of the simplex (over which MAB algorithms operate), which yields the simple behavior of FTRL-based algorithms (e.g., EXP3). Specifically, it is based on the following observation. Suppose that we increase the cumulative loss of arm i. Now consider the behavior of p(i"), the probability of taking arm i' where p is computed from the FTRL framework. One can verify that p(i') will increase for o and decrease for i' = i. In other words, the relationship between any pair of arms is competitive, and this property is critical to achieve the optimal regret with delayed feedback in [52].
However, this property does not hold for MDPs because the constraints of the transition function can dictate positive correlation between entries of the occupancy measure. Similarly, consider two state-action pairs (x, a, h) and (s', a', Jt') from different states. It is highly unclear whether increasing the cumulative loss of (8, a, h)) will increase or decrease the probability qn'(s', (s'' a') of reaching s' in time h and taking action a'. In fact, the relation is related to the specific transition function of

---

the MDP. For example, the FTRL algorithm will decrease the probability in the cases where taking action a at state in step is necessary to reach (s', a', h²), and will increase in other cases where not taking action at state s of step h is necessary.
Therefore, alternative analysis is required in case. Specifically, we are able to bound the delayed-caused term by
Lo Ct, VF h 2²t) - VFF( - x²²) dæ s 2 12112=11
[ - Lohu
(-22(E)
Σ
Ech(e,a)
Σ (5, h,
S
j= 2k
A,,,a
where the first step uses the properties of convex conjugates for some valid occupancy measure (See Lemma B.6 for more details) with || Vx Mæ being the matrix norm for any vector x and positive definite matrix M, and the second step follows from the facts that V-²(((E) a diagonal matrix with values (1 (x, a) v(h, 8, a)} on its diagonal and (x, a) < 1.
While we managed to overcome the complex dependencies between different states in the MDP, comes the price of a looser regret bound. The final bound does not have of (s, a) in the summations which leads to an extra factor of SA. This follows from the application Hölder's inequality and also the relaxation of intermediate occupancy measure
Taking the summation over all episodes, we have that the third term in Eq. (4) is bounded by 5 in expectation. Finally, with proper choice of the parameters r), y and 8, combining the bounds for EST, BIAS1, BIAS₁ and the three terms in Eq. (4) finishes the proof.
5 Delayed UOB-REPS with Delay-adapted Estimator
Finally, we present our last algorithm, Delayed UOB-REP? equipped with our novel importance sampling estimator which call delay-adapted importance sampling estimator. The algorithm appears as Algorithm and in its full version together with the analysis for known and unknown dynamics in Appendices C and D.
Much like Delayed UOB-FTRL, the algorithm is efficient; but outperforms Delayed UOB-FTRL in two important aspects: (i) it guarantees -roobbbbbyyylity regret bound (and not only expected regret), and (ii) the delay term its regret bound is tighter. In fact, as long as A S (which happens in most cases), it obtains an improvement even the regret of the inefficient Delayed Hedge algorithm.
To maintain the occupancy measures g² from which the executed policies T² are extracted, Delayed UOB-REPS uses the Online Mirror Decent (OMD) update rule:
arg min (EA(M,++)
Σ s:d+d/=k
2) KL g))),
where 7) is a learning rate and (L || q') is the unnormalized KL-divergence (see the full algorithm in Appendix D for the definition of KL-divergence). We note that OMD is standard in the O-REPS literature, and has similar guarantees to FTRL. In this case, OMD will be much more useful than FTRL because can utilize its update rule to prove certain properties for the relation between consecutive occupancy measures (sec Lemma D.8).
We do not use the standard importance sampling estimator, but the following
estimator:
(s, {) = a = (s, max(u (s, a), u/ k+d" (s. +
(5)
The delae-adapted estimator specifically tackles one of the main technical challenges in analyzing algorithms under delayed feedback (especially in MDPs) bound their stability. It is biased estimator, and in fact has larger bias than the standard importance sampling estimator, but allows us to directly control the stability of the algorithm.
To describe the intuition behind the delay-adapted estimator, let us first consider a fixed delay d² d. The policy x k+d is updated based on the episodes 1,..., k 1. Thus, playing *+d at episode is
7

---

Algorithm 3 Delayed UOB-REPS with Delay-adapted Estimator
1: Initialization: Set n² to be uniform policy.
2: for k= 1,2, 2,..... ...,, K do
1H 3: Execute policy π² observe trajectory {sh, a 1h-1 update confidence set pi and compute
upper occupancy bound w/ a) pap 9h (s.a).
4: for j + d k do
5: Observe costs {c) (5), d)))= h=1 and compute the delay-adapted cost estimator è by Eq. (5).
6: end for
7: Update occupancy measure by: gf arg gemegee 17 (9 Ejer 0i) KL g*).
8: Update policy: Th +++(aa (a 8) " (s,")(///tt
9: end for
equivalent to running OMD on the same loss estimators but a non-delayed environment. Standard analysis for delayed feedback (e.g., [41, 3] for MAB or [28] for MDPs) utilizes this fact to bound the regret with respect the estimated cost by the sum of: (i) the regret of playing k*td (ii) the "drift" between the playing rht and xh:
H 7
Σ l q- ,
Σ
l
q
kdd
dby
+
Σ %n (s. h,8,a,k
(6)
DRIFT
STARIITTY
The term is usually referred the PENALTY, and the bound (i) PENALTY STABILITY is by standard OMD guarantees. The standard importance sampling estimator defined in Eq. (2) is approximately unbiased (ignoring 7 and transition approximation errors), so the left-hand-side of Eq. (6) is approximately the regret expectation. On the other hand, to bound the STABILITY term, one needs to control the ratio % 4. (s.a)/ since ex, (s, a) has di (s, a)) in the denominator and not k+ (s, a) (for simplicity we ignore the bias between g² and w²). In
In MAB, this ratio essentially bounded by constant, but the proof heavily relies on the simple update form of OMD on the simplex (i.e., EXP3), as explained in Section 4. However, it still remains unclear whether this ratio is bounded by constant when running OMD FTRL on a more general convex set such as (MM). While in the proof of Theorems 3.1 and 4.1 we are able to avoid bounding the ratio in the stability term itself by using "cheating" regret approach, a similar issue re-appears in the drift term. In Theorem 3.1 we bound the ratio between distributions by utilizing the simple update form (for the specific argument see Eq. (21) Appendix A), and Theorem 4.1 we solve this issue with the help of convex conjugates (specifically, Hölder's inequality with respect to the Hessian of the regularizer at an intermediate occupancy measure {), but this comes at the cost of expected regret guarantees and looser bound on the delay term of the regret.
The main idea of the delay-adapted estimator q². The first allows us to control the stability and avoids the need to bound the ratio %, 2+4 "s,a(s //) (e.e), while the second keeps the bias sufficiently small. More precisely, we re- se-eighht using their maximum, which remarkably. causes the estimator's bias to scale similarly to the DRIFT term.
re-weight the cost of episode using both ghtd and
(s.a)/
Finally, there a few important points notice with respect the regret of Algorithm in Theorem 5. First, since the estimator 2 is computed only in the end of episode k + d (when the feedback from episode k arrives), we have already computed both ut and kkd at that point and the estimator well-defined. Second, it generalizes the standard importance sampling estimator and adapts it to the delays. That is, whenever there is no delay, our estimator is identical to the standard importance sampling estimator. Third, there no additional computational cost in computing the new estimator since compute u² for every k anyway. Moreover, there is no additional space complexity because every algorithm for adversarial environments with delayed feedback keeps the probabilities to play actions in episode & until its feedback is received in the end of episode + d².
new estimator before we analyze

---

Theorem 5.1. With appropriate choices of parameters, Delayed UOB-REPS with the delay-adapted estimator (Algorithm 3) ensures with high probability that Rg Ö(H'SVAK + (HSA))/ HvD).
The second term in the regret improves the guarantee of Delayed UOB-FTRL with the standard estimator by factor of H ())A(S It also improves Delayed Hedge by (HS) but on the other hand has an extra factor A/44. Generally, this term is tight up to the (HSA) factor [28]. The first term in the regret matches the state-of-the- regret bound for non-delayed adversarial MDPs [22]. In Appendix C we consider the case of known transitions, and present Delayed O-REPS with the aela-add estimator that achieves the following regret bound. It has similar delay term but its first term is optimal up to poly-log factors [51].
Theorem 5.2. Assume that the transition function is known to the learner. With high probability, Delayed O O-REPS with the delay-adapted estimator (Algorithm 7) ensures that Rg ÖHHVSAK- (HS H H)D
We conclude the section with proof sketch of our main theorem (for the unknown transition case).
Proof sketch of Theorem 5.1. We first break the regret as follows:
K
Rg
Σ
(g x"
q.
q c
c
(q ck
Est
BIAS:
BIAS2
k lat
+
q k+
okk
(g b+ th
9" ck).
DRIFT
REG
EST is the standard transition approximation error which is bounded w.h.p by Ö(H*SV [22]. For BTAS² we use the fact that the delay-adapted estimator is always smaller than the standard estimator and bound it by ((H/)) similarly to [22].
The real advantage of the estimator appears in the REG term. Similar to the fixed delay case, bound REG by,
H +
Σ k,,1,,00
k+d t In
(8,0)c
Σ ((s0,)) JE
H + Σ Σ (s,a),, E
k,h,,, J. jE
STARILTT
where the inequality above is exactly where we utilize the delay-adapted estimator, as by its definition & (s) < 1/uktad k+d' as,a) 1/ k+d" (s,a), a), where the last inequality holds w.h.p. Then, using stan- dard concentration of (f, (,, a) around (f,,,, a) I 1 get that STABILITY S <n(SAAK dmaa//r) Importantly, the concentration arguments hold only because the maximum of n² and *+d" appears in the estimator's 's denominator. If it were only k+th we could not have bounded the distance between the estimator & and the real cost ck
For the DRIFT term, let H be the realization of all episodes j such that j + d' < k. Note that w* and k+d are completely determined by the history k and on the other hand, the k-th episode not part of this history. Next, we take the absolute value on each element of 9t g g and apply
a concentration bound to obtain: DRIFT S. Ek E[( gh++*1,1 1h) H +
The specific definition of the history k is crucial because now we have:
K
K
DRIFT
<la* g 1+td 2t 1,
H = +
Σ
(lg*
- 9
k+dd
1, E
ck
H
K d
H
H
x
l
||1
KL
gi+l)
+
7
k=

---

where the third step follows since w.h.p E
( (s, a)
[
(s (s,a)) 1, the
of (m.)) (na)
fourth step uses the triangle inequality, and the last is by Pinsker inequality, Finally, we utilize the OMD update (which uses KL as regularization) to obtain a bound on (L || g²+ and finally bound (nv HA K) H/7) on the DRIFT term. For BIAS1, apply similar concentration on the cost estimators around E. a [ and show that BIAS, mainly bounded by,
Σ [mmax["" ++
u q² HSAK S <2 -f + Eila - -q + HSAK,
where the maximum is taken element-wise. For last, the first sum is bounded similarly to the EST term while the second sum bounded similarly the DRIFT term. Summing the regret from the different terms and optimizing over 17 and completes the proof.
6 Conclusions and Future Work
In this paper we made a substantial contribution to the literature on delayed feedback in RI.. We presented the first algorithms that achieve near-optimal regret bounds for the challenging setting of adversarial MDP with delayed bandit feedback. Our key algorithmic contribution a novel delay-adapted importance sampling estimator, and we develop various new techniques to analyze delayed bandit feedback in adversarial MDPs.
We leave few interesting questions open for future work. First, there still gap of (HSA) in the delay term between our upper bounds and the lower bound of [28]. Second, it remains open question whether our new estimator necessary to obtain optimal regret in the presence of delays, or it possible to achieve optimal regret with standard algorithmms. Finally, the O-REPS framework but it remains important open problem to achieve Ô (VK D) regret with policy optimization (PO) methods that are widely used in practice, and were recently shown to achieve near-optimal regret in adversarial MDP with non-delayed bandit feedback [31].
algorithms
based on
Acknowledgements
TL, YM and AR have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation program (grant agreement No. 882396), by the Israel Science Foundation (grant number 993/17), Tel Aviv University Center for Al and Data Science (TAD), and the Yandex Initiative for Machine Learning at Tel Aviv University. HI is supported by NSF Award 195-1943607 and Google Faculty Research Award.
References
[1] A. Agarwal and J. C. Duchi. Distributed delayed stochastic optimization. In 20/2 IEEE 5/st IEEE Conference on Decision and Control (CDC), pages 5451-5452. IEEE, 2012.
[2] M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages JMLR. org, 2017.
[3] Bistritz, Z. Zhou, Chen, N. Bambos, and J. Blanchet. Online exp3 learning in adversarial bandits with delayed feedback. In Advances in Neural Information Processing Systems, pages 11349-11358, 2019.
[4] I. Bistritz, Z. Zhou, X. Chen, N. Bambos, and J. Blanchet. No discounted-regrel learning in adversarial bandits with delays. arXiv preprint w:Xiv:2103.04550 2021.
[5] Q Cai, Z. Yang, C. Jin, and Z. Wang. Provably efficient exploration in policy optimization. In International Conference Machine Learning, pages 1283-1294 1294. PMLR, 2020.
[6] N. feedback. In Conference On Learning Theory, pages 750-773, 2018.
C. Gentile, and Y. Mansour. Nonstochastic bandits with composite anonymous
10

---

[7] N. Cesa-Bianchi, C. Gentile, Y. Mansour, and A. Minora. Delay and cooperation in nonstochastic bandits. In Conference on Learning Theory, pages 605 622, 2016.
[8] N. Changuel, B. Sayadi, and M. Kieffer. Online learning for qoe-based video streaming to mobile receivers. In 2012 IEEE Globecom Workshops, pages 1319-1322 1324. IEEE, 2012.
[9] B. Chen, M. Xu, Z. Liu, L. Li, and D. Zhao. Delay-aware multi-agent reinforcement learning. arXiv preprini arXiv:2005.0544) 2020.
[10] A. Cohen, A. Daniely, Drori, T. Koren, and M. Schain. Asynchronous stochastic optimization robust arbitrary delays. arXiv preprint arXiv:2106. 11879, 2021.
[11] A. Cohen, Y. Efroni, Y. Mansour, and A. Rosenberg. Minimax regret for stochastic shortest path. Advances in Neural Information Processing Systems, 34, 2021.
[12] E. Derman, G. Dalal, and S. Mannor. Acting in delayed environments with non-stationary markov policies. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
[13] Y. Freund and R. E. Schapire. A -theoretc generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119-133) 1997.
[14] M. A. Gael, C. Vernade, A. Carpentier, and M. Valko. Stochastic bandits with urm-dependent delays. In International Conference on Machine Learning, pages 3348-3343 -3366. PMLR, 2020.
[15] A. Gyorgy and P. Joulani. Adapting to delays and data in adversarial multi-armed bandits. In International Conference on Machine Learning, pages 3988-3997. PMLR, 2021.
[16] E. Hazan. Introduction to online convex optimization. arXiv preprint arXiv: arXiv: h00N:9999.05777 2019.
[17] J. He, D. Zhou, and Q Gu. Near-optimal policy optimization algorithms for learning adversarial linear mixture mdps. In G. Camps-Valee F. J. R. Ruiz, and I. Valera, editors, Proceedings The 25th International Conference Artificial Intelligence and Statisties, volume 151 1 of Proceedings of Machine Learning Research, pages 4259 4280. PMLR, 28-30 Mar 2022.
[18] B. Howson, C. Pike-Burke, and S. Filippi. Delayed feedback in episodic reinforcement learning. arXiv preprint arXiv:2111.076155 2021.
[19] S. Ito, D. Hatano, H. Sumita, K. Takemura, T. Fukunaga, N. Kakimura, and K.-I. Kawarabayashi. Delay and cooperation in nonstochastic linear bandits. Advances Neural Information Pro- cessing Systems, 33:4872-4884 2020.
[20] T. Jakseh, R. Ortner, and Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11(4), 2010.
[21] C. Jin, Allen-Zhu. Bubeck, and M. Jordan. leaannnn provably efficient? In Advances in Neural Information Processing Systems, pages 4863 4473,,473,44 2018.
[22] C. Jin, T. Jin, H. Luo, S. Sra, and T. Yu. Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning, pages 4860-4869. PMLR, 2020.
[23] C. Jin, 2. Yang, Z. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143, 2020.
[24] T. Jin, L. Huang, and H. Luo. The best of both worlds: stochastic and adversarial episodic mdps with unknown transition. Advances in Neural Information Processing Systems, 2021.
[25] T. Jin and H. Luo. Simultancously learning stochastic and adversarial episodic mdps with known transition. Advances in neural information processing systems, 2020.
[26] K. V. Katsikopoulos and F. Engelbrecht. Markov decision processes with delays and asynchronous cost collection. IEEE transactions automatic control, 48(4):568-3))) 2003.
11

---

[27] T. Lancewicki, A. Rosenberg. and Y. Mansour. Cooperative online learning in stochastic and adversarial MDPs. In Proceedings of the 39th International Conference on Machine Learning. volume 162 of Proceedings of Machine Learning Research, pages 11918-11998 PMLR, 17-23 Jul 2022.
[28] Lancewicki, Rosenberg, and Y. Mansour. Learning adversarial markov decision processes with delayed feedback. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7281-7289, 2022.
[29] T. Lancewicki, S. Segal, T. Koren, and Y. Mansour. Stochastic multi-armed bandits with unrestricted delay distributions. In Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, pages 5969-5978, PMLR, 2021.
[30] S. Liu, X. Wang, and P. X. Liu. Impact of communication delays on secondary frequency control an islanded microgrid. IEEE Transactions on Industrial Electronics, 62(4):2021-2031, 2014.
[31] H. Luo, C.-Y. Wei, and C.-W. Lee. Policy optimization in adversarial mdps: Improved explo- ration via dilated bonuses. Advances in Neural Information Processing Systems, 34, 2021.
[32] A. R. Mahmood, D. Korenkevych, J. Komer, and J. Bergstra. Setting up a reinforcement learning task with real-world robot. In 2018 JEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 4635-4640. IEEE, 2018.
[33] G. Neu. Explore no more: Improved high- probbabbbyy regret bounds for non-stochastic bandits. Advances in Neural Information Processing Systems, 28:3168-31777 2015.
[34] C. BikeeBBuke, S. Agrawal, C. Szepesvari, and S. Grunewalder. Bandits with delayed, aggregated anonymous feedback. In International Conference on Machine Learning, pages 4105-4113. PMLR, 2018.
[35] K. Quanrud and D. Khashabi. Online learning with adversarial delays. Advances in neural information processing systems, 18:1270- 2015.
[36] A. Rosenberg and Y. Mansour. Online convex optimization in adversarial markov decision processes. In International Conference on Machine Learning, pages 5478 -486. PMLR, 2019.
[37] A. Rosenberg and Y. Mansour. Online stochastic shortest path with bandit feedback and unknown transition function. Advances in Neural Information Processing Systems, 32:2212- 2221, 2019.
[38] A. Rosenberg and Y. Mansour. Stochastic shortest path with adversarially changing costs. In Z. Zhou, editor, Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 2936- 2942. orcai.org, 2021.
[39] E. Schuitema, Buçoniu, Babuška, and P. Jonker. Control delay in reinforcement learning for real-time dynamic systems: memoryless approach. In 2010 JEEE/RSJ International Conference on Intelligent Robots and Systems, pages 3226-3231 IEEE, 2010.
[40] L. Shani, Y. Efroni, A. Rosenberg, and S. Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, pages 8604-8613. PMLR, 2020.
[41] T. S. Thune, N. Cesa-Bianchi, and Y. Seldin. Nonstochastic multiarmed bandits with unrestricted delays. In Advances in Neural Information Processing Systems, pages 6541-6550 2019.
[42] D. van der Hoeven and N. Cesa-Bianchi Nonstochastic bandits and experts with arm-dependent delays. arXiv preprint arXiv:2111.0158) 2021.
[43] C. Vernade, O. Cappé, and V. Perchet. Stochastic bandit models for delayed conversions. In Conference Uncertainty in Artificial Intelligence, 2017.
[44] C. Vernade, A. Carpentier, T. Lattimore, G. Zappella, B. Ermis, and M. Brueckner. Linear bandits with stochastic delayed feedback. In International Conference on Muchine Learning, pages 9712-9721. PMLR, 2020.
12

---

[45] T. J. Walsh, A. Nouri, L. Li, and M. L. Littman. Learning and planning in environments with delayed feedback. Autonomous Agents and Multi-Agent Systems, 18(1):83, 2009.
[46] L. Yang and M. Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
[47] A. Zanette, D. Brandfonbrener, E. Brunskill, M. Pirotta, and A. Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages
2020.
[48] A. Zanette, A. Lazaric, M. Kochenderfer, and Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978-10989. PMLR, 2020.
[49] Zhou, R. Xu, and J. Blanchet. Learning generalized linear contextual bandits with stochastic delays. In Advances in Neural Information Processing Systems, pages 5197-5208, 2019.
[50] A. Zimin. Online Learning in Markovian Decision Processes. PhD thesis, Central European University, 2013.
[51] A. Zimin and G. Neu. Online learning in episodic markovian decision processes by relative entropy policy search. In Advances in Neural Information Processing Systems 26: 27th Annual Conference Neural Information Processing Systems 2013. Proceedings of meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 1583-1591, 2013.
[52] J. Zimmert and Y. Seldin. An optimal algorithm for adversarial bandits with arbitrary delays. In International Conference on Artificial Intelligence and Statistics, pages 3285-3294. PMLR, 2020.
13


Reviews:
[{"review_id": "qaLtmLchtFz", "reviewer": "Reviewer_nrUe", "summary": "This work focused on the adversarial MDPs with delayed and bandit feedback. Compared with previous results, the author proposes novel algorithms and improves the regret bound of $(K+D)^{2/3}$ to $\\sqrt{K+D}$, which matches the lower bound on the factors K and D. ", "questions": "1. For the previous work Lancewicki et al.[2022] , it can still obtain a $\\sqrt{D+K}$ regret with full feedback. In this work, the author focuses on the bandit feedback and only improves it in this case. However, the distinction is not clear in the introduction or preliminaries.\nTherefore, it is better if the author can also mention the full feedback and have some discussion about the difference between these settings. \n\nLancewicki T, Rosenberg A, Mansour Y. Learning adversarial Markov decision processes with delayed feedback. (AAAI 2022)\n\n2. In the related work part, the author mentions recent advances in regret guarantees for adversarial MDPs. More recent advanced works have focused on using the function approximation techniques in Adversarial MDPs. For instance, He et al. [2022] improve the result in [5]\nwith a factor of $H$. It is better if the author can mention them or have some discussion about them.\n\n He J, Zhou D, Gu Q. Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation. (AISTATS 2022)", "limitations": "This paper provides theoretical guarantees for learning linear bandit and linear mixture MDP. There is no negative societal impact.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. All three novel algorithms obtain a $\\sqrt{K+D}$ regret guarantee, which improved the previous results and matches the theoretical lower bound on the factors K and D.\n\n2. In the Delayed UOB-REPS Algorithm, the author proposes a novel importance-sampling estimator, which can improve the stability with delay-feed back. This estimator may be of independent interest.\n\nWeakness:\n\n1. This work uses the word \"near-optimal regret\" or \"order-optimal regret (Sections 3-4)\" and it may overclaim the contribution. Near-optimal usually means it matches the theoretical lower bound up to logarithmic factors. However, for both three algorithms, gaps between the upper and lower bound on the elements \"H, S, A\" still exist, which is far from optimal.\n\n2. The Delayed UOB-FTRL and UOB-REPS rely on a minimization over the confidence set with the FTRL algorithm. Therefore, these algorithms require the initial state is fixed ($s_{init}$), which is much more restrictive than previous works.\n\n3. It is still unclear whether the Delayed UOB-FTRL and UOB-REPS are computation-efficient. Both of these algorithms rely on a minimization over the confidence set to compute the occupance measure. Though both the policy space and the possible transition function space $\\mathcal{P}$ are continuous and convex, the relation between them and occupance measure $q$ is complicated, and the structure of $q$ may be unregular. Thus, it is still unclear how to perform the minimization over the confidence set efficiently.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "W2Pl6aTlCr", "reviewer": "Reviewer_dP9N", "summary": "This paper considers online learning in the adversarial MDP setting with unknown transitions, adversarially changing costs, and (unbounded) obliviously adversarial delayed bandit feedback (only see costs along the observed trajectory rather than the whole cost function), and proves the first near-optimal regret bounds which scale as $\\sqrt{K + D}$, for $K$ the number of episodes and $D$ the sum of delays over all episodes. This regret bound improves over the previously best known $(K + D)^{2/3}$ regret bound for this setting. Prior work studied the adversarial case under full-information feedback, and in that setting, achieved a $\\sqrt{K + D}$ upper bound. In the prior work, it was proved that if the costs are changed from adversarial to stochastic, under bandit feedback, one can achieve a $\\sqrt{K + D}$ upper bound, but if the costs remain adversarial, the paper only proved an upper bound of $(K + D)^{2/3}$. \n\nThe paper presents three algorithms: First, a Hedge-based algorithm which is adapted to the adversarial MDP which is computationally inefficient but is a simple solution to validate that an improvement in regret is possible; an FTRL-based algorithm which attains the improved regret bound and is computationally efficient, but does not have its regret bound hold with high probability, and finally, a REPS-based algorithm which attains all desired categories -- computational efficiency, (tightest) regret bound of all, and a high probability guarantee. Furthermore, the first term of the regret bound differs from the corresponding term in the lower bound only by order $\\sqrt{HS}$, and the second term differs from the corresponding term in the lower bound only by order $(HSA)^{1/4}$. \n", "questions": "* Could you clarify in the main paper that $P^1$ is taken to be the set of all transition functions? It's currently buried in the more detailed version of Delayed Hedge (Alg 4) in the appendix - at least it should show up in Algorithm 1. I also think it would be helpful to qualify the definition of Bernstein confidence sets just a little more in the main paper to the unfamiliar reader; the intuition was immediately clear upon looking at Algorithm 5 in the appendix -- maybe consider saying that you're applying the Bernstein bound specifically to the empirical transitions on line 98? \n\n* Comparing Theorem B.1 and Theorem 4.1, there is a term with $H^4S^2A$ and polylog dependency on $K$ in Theorem B.1 but not Theorem 4.1 -- shouldn't the worse dependencies be used here for the $\\log(K)$ term (which is hidden via the tilde)?\n\n* In step 2 of line 524 in the proof of Lemma 2, why is the log term log(HSA/delta) instead of log(SA/delta)? e.g. why do you need to union bound over all horizons as well? \n\n* In step 5 of Eq. 13 in Line 552, why does the S show up inside the square root? Could you clarify what properties of $\\eps_k$ you're using?\n\n* Could you comment further on intuition for why OMD is preferable to FTRL (in lines 228-230)?\n\n* Could you define $\\phi$ directly in Algorithm 2?\n\n* Based on the lower bound given in Table 1 and the comment in Line 278, is it the case that one expects the lower bound in Table 1 can be improved? Or is it the case that even in the non-delayed setting, it is believed that better algorithms in terms of first term of the regret bound exist?\n\n* It might make sense to clarify that you are considering costs bounded in the range $[0, 1]$ when you describe the paper's setting.\n\n* Minor things: \n   * Line 15 has a typo \"an inherit\" --> \"an inherent\" \n   * Line 19 has a typo \"but assume\" --> \"but assumes\"\n   * Line 514: maybe use a different variable name for the coefficient?\n   * Line 532: and Holder's inequality\n   * in Line 539, might be helpful to mention that p' is the maximizer rather than just allude to u_k\n   * Line 552: typo \"forth\" --> \"fourth\"\n\n\n\n", "limitations": "Yes, the authors have adequately clarified their contribution, and have not overstated any part of the work. There are no immediate negative societal consequences of this work. ", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* Strengths: The paper is well written and gives solid theoretical results. I found the structure of the paper quite good, the related work well-cited and referenced, and I particularly thought the description of the FTRL analysis in Section 4 and the REPS analysis in Section 5 were well-written and clarified the main contributions in those sections. Several of the technical contributions are novel and appear to be interesting, and possibly more broadly useful beyond the scope of this specific paper. The paper is also useful pedagogically -- this paper appears to be a great introduction to the delayed adversarial online MDP literature, and possibly also to the more general adversarial online MDP literature via its clear breakdown of standard methodology and paper pointers. The delay-adapted estimator of Section 5 is quite elegant.\n\n* Weaknesses: One weakness is that the proofs in the appendix are sometimes difficult to read due to many steps of the proofs citing specific lemmas and proofs in other papers -- this leads to a lot of pointer tracing to get to the desired statements. Additionally, it might be helpful if the reasoning behind each step in the proofs was less terse.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A0VOPAX3TqN", "reviewer": "Reviewer_sRmT", "summary": "This paper studies online learning for adversarial MDP with delayed bandit feedback in the tabular cases. It proposes three algorithms to solve the problem. The first one called Delayed Hedge is adapted from Hedge with optimism, which can provide high probability guarantee but is computationally inefficient. The second one called Delayed UOB-FTRL is adapted from FTRL with optimism, which is more computationally efficient but can only provide expected guarantee. Delayed UOB-REPS with Delayed-adapted Estimator improves the estimators in Delayed UOB-FTRL and is able to provide high probability guarantee. All these algorithms achieve better regrets than existing algorithms.", "questions": "1. The paper claims that Delayed UOB-FTRL and Delayed UOB-REPS with Delayed-adapted Estimator are computationally efficient. However, the updates of $q^{k+1}$ still seems a little difficult since the constraint set is $\\Delta(M,k+1)$, whose geometry is unclear from the paper (the paper just mentions it is a polytope with polynomial constraints). I wonder the authors can elaborate on this.\n2. The paper only studies the tabular cases, and their algorithms seem tailored to the tabular setting. I wonder whether their algorithms can be further extended to function approximation case.\n", "limitations": "See weakness.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: \n1. The paper proposes three algorithms for adversarial MDP with delayed bandit feedback and achieves better regrets than existing algorithms.\n2. The paper is well written, and the proof sketch is convincing.\n\nWeakness:\nThere is still a gap between the regret upper bounds of these new algorithms and the theoretical lower bound. So maybe “near-optimal” seems a little exaggerated. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept