Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: 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. 
strengths_and_weaknesses: Strength:

1. 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.

2. 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.

Weakness:

1. 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.

2. 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.

3. 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.
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.
Therefore, it is better if the author can also mention the full feedback and have some discussion about the difference between these settings. 

Lancewicki T, Rosenberg A, Mansour Y. Learning adversarial Markov decision processes with delayed feedback. (AAAI 2022)

2. 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]
with a factor of $H$. It is better if the author can mention them or have some discussion about them.

 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.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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}$. 

The 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}$. 

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.

* 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.
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? 

* 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)?

* 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? 

* 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?

* Could you comment further on intuition for why OMD is preferable to FTRL (in lines 228-230)?

* Could you define $\phi$ directly in Algorithm 2?

* 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?

* It might make sense to clarify that you are considering costs bounded in the range $[0, 1]$ when you describe the paper's setting.

* Minor things: 
   * Line 15 has a typo "an inherit" --> "an inherent" 
   * Line 19 has a typo "but assume" --> "but assumes"
   * Line 514: maybe use a different variable name for the coefficient?
   * Line 532: and Holder's inequality
   * in Line 539, might be helpful to mention that p' is the maximizer rather than just allude to u_k
   * Line 552: typo "forth" --> "fourth"




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.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strength: 
1. The paper proposes three algorithms for adversarial MDP with delayed bandit feedback and achieves better regrets than existing algorithms.
2. The paper is well written, and the proof sketch is convincing.

Weakness:
There 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. 

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.
2. 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.

limitations: See weakness.
review_title: null

Meta-review: metareview: This paper has initially received mixed reviews, but the author response has successfully addressed the concerns of the less enthusiastic reviewers, thus we have eventually reached consensus that the paper is suitable for publication at NeurIPS 2022. That said, I encourage the authors to take all the reviewers' comments into account when preparing the final version, especially when it comes to improving the readability and self-containedness of the proofs in the appendix. As for the usage of the term "near-optimal" in the title, I concur with the reviewers who pointed out that this may not be the perfect choice of words. This is not to say that it is necessary to change the title of the paper, but perhaps a better choice of wording may give a better overall impression to future readers of the paper.
confidence: Certain
Decision: Accept