Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studies the following variations of problems of sequential learning in tabular adversarial MDP with bandit feedback: learning in episodic MDP for the setting with known and unknown transitions of MDP, learning with delayed feedback and infinite-horizon setting. The main novelty of this work is that all proposed algorithms are based on the FTPL method, which often allows to develop more computationally efficient algorithms.   
strengths_and_weaknesses: - On my opinion,  the extension of  FTPL method to the AMDP setting (without assumption on the smallest visitation probability) is an important contribution, as the proposed algorithm is much more computationally efficient than running OMD to compute an occupancy measure as it was done in the previous works for the cases of both known and unknown transitions. 
- On the technical side, Lemma 3 is a straightforward but important result as generalises the analysis of FTRL made for bandit problems to bound the regret in all considered settings. In the same time, once Lemma 3 is applied, there is no hope to get a regret bound that would be optimal in H, so in the future studies a refinement of this lemma would be needed.
- In the delayed feedback setting the result does not improve the current state of the art, but technically it is interesting to see that the FTPL can be applied.  Moreover, the obtained regret guarantees for the Algorithm 4 are only slightly worse in a non-leading term.
- I found the result of section 5 exiting, as this is the first result in the setting of infinite AMDP with bandit feedback, even though the obtained regret bound scales as $T^5/6$ (or $T^2/3$ for the computationally inefficient algorithm). While the authors adapt the analysis of Chandrasekaran and Tewari (2021),  they also show that their algorithm is computationally efficient under the assumption of access to the oracle. 
questions: The analysis is clear, so I have only minor comments:

- Line 9 in Algorithm 1: $\hat{l}_{1:k-1}$ is not defined
- Equation after line 215: $p_k(\pi)$ is not defined 
limitations: The Algorithm 6 is only computationally efficient in the presence of the oracle and Algorithm 7 is computationally inefficient.
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 studies the sample complexity of MDPs with adversarial reward functions and fixed transition kernel. This paper considers the settings of bandit reward feedback, known and unknown transition, and episodic and infinite horizon. Moreover, this paper also studies the delayed-reward setting. The algorithm studied in this paper is the well-known Follow the Perturbed Leader (FTPL). This paper proves that FTPL achieves sublinear regret in all these settings. 
strengths_and_weaknesses: Strengths:
FTPL algorithm is a popular algorithm in online learning. It is novel to show that FTPL is able to achieve sublinear regret in various RL settings. The theoretical results seem reliable. The presentation of this paper is quite clear. 

Weaknesses:
It would be nice to motivate the readers better understand why FTPL is interesting, compared to OMD or FTRL. Does it offer better regret bounds or is it easier to implement? Moreover, previous works have studied mirror descent for adversarial MDP and FTPL for online bandit learning. It would be nice to better explain the novelty given these two strands of literature. 

questions: 1. Previous works have studied mirror descent for adversarial MDP and FTPL for online bandit learning. It would be nice to better explain the novelty given these two strands of literature. 

2. Why the setting of adversarial MDP given in this paper makes sense -- why only assume the reward function is adversarial? 

3. Is it possible to modify the proposed algorithm to the setting where transition kernel is also evolving? Is it possible to obtain a dynamic regret? Is It possible to devise an algorithm with low policy switches? 

limitations: The main limitation is that the transition kernel is fixed but only the reward function can change adversarially. I understand that when the transition is also adversarial, there is some negative results. But it is still possible to consider the case where the transition kernel evolves rather slowly. It would be nice to have a discussion.
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: Motivated by the computation advantage of follow-the-perturbed-leader (FTPL) methods against the online-mirror-descent (OMD) methods, the authors consider studying the regret minimization in the adversarial Markov decision process (AMDP) with bandit feedback using FTPL. They prove that FTPL can also achieve the near-optimal regret bounds in the finite-horizon AMDP. Further, using standard loss estimators, they also prove that their algorithm can achieve the order-optimal regret in the finite-horizon Markov decision process (MDP) with delayed bandit feedback under a more simplified analysis than the OMD-based methods. Taking inspirations from previous work studying infinite-horizon communicating AMDP with full-information feedback, the authors also establish the first algorithm with a sub-linear regret guarantee in communicating infinite-horizon AMDP with bandit feedback and known transition using FTPL.
strengths_and_weaknesses: Strengths

Originality: Several original contributions in this work have been made. Different from most works studying regret minimization in AMDP using OMD (or a similar algorithm called follow-the-regularized-leader (FTRL)), this work considers studying the same task but using FTPL to avoid solving the convex optimization problems over the complicated occupancy measure space. Specifically, the authors point out why directly extending the analysis in existing works studying (contextual) semi-bandit fails and give their modification to overcome this problem. Furthermore, the authors also demonstrate that their algorithm can also achieve the order-optimal regret bound in the finite-horizon AMDP with delayed bandit feedback using the standard loss estimator. Besides, the regret bound of their algorithm has better dependences on the state space size S and the action space size A with a more simplified analysis compared with [1]. Using FTPL, the authors also establish the first algorithm with a sub-linear regret guarantee in communicating infinite-horizon AMDP with known transition based on the policy switching procedure in [2].

Quality: The proposed algorithms and analysis are technically sound. 

Clarity: Overall, this paper is well-organized and well-written. The authors also give sufficient comparisons of the algorithms and analysis with previous works. However, I have a question about the presentation. Please see the first question below.

Significance: The regret bound of FTPL in this paper matches the state-of-the-art bound obtained by OMD in the finite-horizon AMDP with unknown transition, is easier to analyze in the AMDP with delayed bandit feedback, and is the first sub-linear regret bound in communicating infinite-horizon AMDP with the known transition. These theoretical results in this paper are meaningful to the community in the sense that they can enable us to better understand the performance of learning AMDP using FTPL. 

Weaknesses

Novelty: Though some contributions have been made, considering some key ingredients of the algorithms and analysis are similar to previous works (e.g., introducing the upper occupancy measure to handle the unknown transition as in [3], the policy switching procedure to adjust the state distribution after switching the policy in infinite-horizon AMDP as in [2]), it is currently not very clear whether there are additional technical challenges met and solved by the authors. I would suggest the authors give more explanations about the technical difficulties they met and how they address them. In particular, it would be better if the authors could give more discussions about the difficulty to bound the single-step stability in AMDP (Lemma 3) given the single-step stability in (contextual) semi-bandit [4], the difficulty to bound the EstReg term in AMDP with delayed feedback given the similar “cheating regret” decomposition in [5], and the difficulty to achieve the sub-linear bound of the error-term after adding T perturbations (Lemma 34).

[1] Jin, T., Lancewicki, T., Luo, H., Mansour, Y., & Rosenberg, A. (2022). Near-optimal regret for adversarial mdp with delayed bandit feedback. arXiv preprint arXiv:2201.13172.

[2] Chandrasekaran, G., & Tewari, A. (2021). Online Learning in Adversarial MDPs: Is the Communicating Case Harder than Ergodic?. arXiv preprint arXiv:2111.02024.

[3] Jin, C., Jin, T., Luo, H., Sra, S., & Yu, T. (2020, November). Learning adversarial markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning (pp. 4860-4869). PMLR.

[4] Syrgkanis, V., Krishnamurthy, A., & Schapire, R. (2016, June). Efficient algorithms for adversarial contextual learning. In International Conference on Machine Learning (pp. 2159-2168). PMLR.

[5] Van Der Hoeven, D., & Cesa-Bianchi, N. (2022, May). Nonstochastic bandits and experts with arm-dependent delays. In International Conference on Artificial Intelligence and Statistics. PMLR.

questions: 1.	On page 8 line 296 – line 297, why the regret in infinite-horizon defined in Eq. (1) is “counterfactual”? I do not seem to find it “counterfactual” since the losses in the first term and the second term in Eq. (1) are evaluated on the states generated by following policy \pi_t and some optimal policy \pi^\ast respectively, which are analogous to them in the regret definition of the finite-horizon MDP.

2.	As previous works have done [6, 7], it is natural to divide the whole horizon into different epochs to learn in the infinite-horizon (discounted) MDP. However, the additional policy switching procedure in Algorithm 5 is used to adjust the state distribution and seems only to be an artifact in the analysis based on the occupancy measure. I wonder whether it is possible to learn in infinite-horizon AMDP using non-occupancy-measure-based analysis (say policy optimization [8]) to remove the policy switching procedure.

3.	What is the concrete hardness to equip FTPL with a delay-adapted loss estimator similar to the UOB-REPS algorithm in [1]?

[6] Zhou, D., He, J., & Gu, Q. (2021, July). Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning (pp. 12793-12802). PMLR.

[7] Wei, C. Y., Jahromi, M. J., Luo, H., & Jain, R. (2021, March). Learning infinite-horizon average-reward mdps with linear function approximation. In International Conference on Artificial Intelligence and Statistics (pp. 3007-3015). PMLR.

[8] He, J., Zhou, D., & Gu, Q. (2022, May). Near-optimal Policy Optimization Algorithms for Learning Adversarial Linear Mixture MDPs. In International Conference on Artificial Intelligence and Statistics (pp. 4259-4280). PMLR.

limitations: Not applicable.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper analyzes the Follow-the-perturbed-leader algorithm for the episodic, adversarial MDP problem where the learner only receives bandit feedback.

Several technical challenges are identified and solved; regret bounds for FTPL in this setting are derived and shown to be competitive with other methods (usually within a $\sqrt{H}$).

Generalized to the delayed setting and infinite-horizon setting (the later being a first), under the slightly less general assumption of known transition dynamics but with a mild mixing requirement.

strengths_and_weaknesses: The presentation and results of this paper are both very strong. On the presentation side, I found the discussion and exposition throughout very clear and very well written for an online learning audience familiar with the standard proof techniques in the literature. Focusing on the difference between the  techniques used in this paper and the techniques used in the rest of the literature works out very well and makes all the results very easy to understand. The discussion throughout really has the right balance of technical details and intuition. The organization is logical, and the paper is a pleasure to read.

The results are well positioned in the literature: they tackle a topical problem (adversarial MDP learning) and fill an obvious algorithmic hole (the use of FTPL). Connections to other algorithms, and a comparison of theoretical results via the regret bound rates, is thorough. Even though the rates aren't necessarily state-of-the-art, the extension to FTPL opens up many future directions and is significant. 

questions: Regarding novelty, it seems that, aside from the different stability assumption, the novelty of the paper is in using many tricks already present in the literature instead of a new analysis technique. I don't think that this assessment really detracts from my opinion of the paper, but am I missing something?
limitations: The main technical limitation, the looseness of the stability lemma, is presented with adequate discussion.
review_title: null

Meta-review: metareview: This paper has received uniformly good reviews, and the reviewers were all happy with the author responses as well. Thus, the paper is clearly suitable for being published at NeurIPS 2022. I encourage the authors to execute all the small updates promised in the rebuttal period when preparing the final version of the paper.
confidence: Certain
Decision: Accept