Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of sequential learning in episodic MDP with full and bandit feedback and unknown dynamics of the MDP. The paper provides the first algorithm with provable performance guarantees, that simultaneously ensure polylogarithmic regret in the stochastic setting and the \sqrt(T) order regret bound in the adversarial setting. This is the first result of this kind, previous works only answer this question for a setting when the transitions are known. The paper proposes running the FTRL-type algorithm over the set of all valid occupancy measures from the estimated transition matrix. It ensures the exploration by subtracting the exploration bonus from the loss and it gives the importance weighted loss estimator by dividing the observed loss by the upper bound on the occupancy measure. The algorithm is computationally efficient. The secondary contribution of the paper is a more simple analysis of the variation of the same problem where the transitions are known. 



main_review: The paper is very well-written and studies an interesting problem. It provides new techniques:

- The choice and use of a shifting function. It is a very nice solution. 

- The idea to move the use of exploration bonus from the search of the occupancy measure for the confidence set of transitions
to the alternative solution of substructing the exploration bonus from the loss. This trick looks potentially useful in other applications. 

Remarks:

- The statement of lines 167 - 170 and equation (7), and later reasoning on the same topic at lines 295-300 suffer from lack of clarity. Reference to a more detailed explanation in the appendix is needed and also reformulate a thought more clearly. 

- (1) comes initially from best of both worlds analysis for bandits.

- The message of lines 231-234 is not very clear. The shifting function as well can be computed using \mathcal{P}_i.

- It is not very clear why the best of both world problem in the full information setting requires special attention. The stochastic regime with full information is not very challenging. 
limitations_and_societal_impact: There is no potential negative societal impact.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: This paper presents an algorithm for episodic Markov decision processes with unknown losses and transition kernel. The paper proves that this algorithm achieves order sqrt(T) regret bounds when losses are chosen by an oblivious adversary and order log^2*(T) when losses are stochastic. This is the first algorithm to achieve such best of both works regret guarantees when transitions are unknown. 
The key technical innovations are (1) the use of loss-shifting technique in the MDP setting, (2) running FTRL in phases where the empirical transition model is fixed per phase, (3) new biased loss estimators that combine importance weighting using upper occupancy measures with   additional bonus terms to promote exploration and (4) carefully tuned regularizers for FTRL.
main_review: Significance: Best of both worlds results are desirable and have received a good amount of attention in the RL / bandit theory community. This paper significantly advances the state of the art in this area by showing the first such results in MDPs with unknown transitions. Besides the actual regret bound, I think the proof techniques in this paper will be useful in other settings as well. I particularly liked the simpler analysis using shifted losses compared to prior works.

Clarity: The paper is very well written, illustrating the main technical challenges and clearly explaining how they were overcome. I think the paper does a particularly good job at sketching the intuition in the main paper while providing the verbose arguments with all details in the appendix.

Originality: Many of the technologies used in this paper have been used elsewhere before, including loss shifting, using phases where the empirical model is kept fixed and adding a reward bias to account for uncertainty in transition estimates (e.g. in UCBVI algorithms). I still think that the combination and adaptation of these tools to the setting addressed here is technically highly nontrivial and sufficiently novel.

Quality: I checked several technical lemmas in the proofs and did not find any issues. The main arguments also make sense to me, but I did not go through all lemmas in the appendix carefully.

Minor comments and typos:
- One log(T) factor seems to come from the fact that the algorithm runs log(T) independent instances of FTRL. If one could avoid that, would that allow us to achieve a log(T) instead of log^2(T) bound or are there other places that contribute the additional log-factor?
- I understand that it is not the main focus of the paper to push the best results for either case, adversarial or stochastic, but I wonder whether the techniques developed in this paper can shed light on the additional sqrt(S) / S factor in the presented upper-bounds compared to the lower bounds when transitions are stochastic & unknown?
- Line 342: challenging -> challenges
limitations_and_societal_impact: I am not aware of any potential negative societal impact of this work and the authors have sufficiently discussed the technical limitations of their work.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The authors consider the problem of stochastic and adversarial episodic MDPs with unknown transition, is an extension of the work of Jin and Luo (2020), with unknown transitions rather than known ones. 

They propose an algorithm which is part of the FTRL framework, where they use some existing tools, such as the self-bounding technique as well as new tools such as the Loss-Shifting Technique.

They outperform the previous results from Jin and Luo (2020) for the problem of stochastic and adversarial episodic MDPs with known transition with a simpler analysis, and they derive new bounds in the setting with unknown transitions.

Both Full information and Bandit feedback are coinsidered.

main_review: This work is an improvement compared to previous works on several fronts. First, in the setting with fixed transitions, this new algorithm and its analysis are both more efficient and simpler to study. 
In the setting with unknown transition, the results are novel. 

Overall, the framework provided is very complete, as they study episodic MDPs in a Best of Both world setting, both with known and unknown transitions and both with bandit and full information feedback.
 
The algorithm proposed is part of the FTRL framework, where they use some  existing tools, such as the self-bounding technique as well as new tools such as the Loss-Shifting Technique, which is efficient and easier to analyse than the previously existing algorithm from Jin and Luo (2020).

The paper is quite well written, and the proofs are extensively detailled in the appendix. The amount of material presented is important for the length of the paper. 
 A conclusion that discuss possible extensions would be a useful addition.
limitations_and_societal_impact: The limitations are supposedly discussed in section 1, but they could be clearer and extended. In particular, a clearer description of the suboptimality gaps of the provided bounds would be beneficial.

The societal impact is not super relevant for this type of theoretical problems, and in general achieving more robust and polyvalent algorithms has a positive impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the "best of both worlds" algorithm for episodic MDPs with unknown transition with stochastic and adversarial rewards, hence the paper resolves the open question in (Jin and Luo 2020). While the adversarial case alone with unknown transition is closed in (Jin et al. 2020), the paper shows that a simple variation of FTRL with a loss-shifting trick, optimism-based exploration bonus and restarting can also achieve poly-logarithmic regret in stochastic environments assuming the constant minimum-gap $\Delta_{min} = \min_{s, a \neq \pi^*(s)} V^*(s) - Q^*(s,a)$. The proposed algorithm and associated analysis enjoy more simplified analysis compared to the previous work in (Jin and Luo 2020). The simplified analysis is adapted from (Jin and Luo 2020) and (Simchowitz and Jamieson 2019). Main results are the the regret bound of $O(\sqrt{T})$ under adversarial setting, and $O(log^2 (T))$ under stochastic setting.
main_review: In some sense, the contribution may be seen as a minor improvement from (Jin and Luo 2020) for known transition case. In fact, maybe one can first run reward-free exploration schemes to learn transition kernels and then execute any known algorithms for best-of-both-worlds. It would result in O(T^{2/3})-regret nevertheless. Hence getting $O(\sqrt{T})$ and $O(polylog(T))$ regrets in adversarial and stochastic cases respectively does not seem to be so trivial.
 
On the other hand, analysis seems not particularly novel but a variation of FTRL method (e.g., Jin et al. 2020) and logarithmic-regret for MDPs (e.g., Simchowitz and Jamieson 2019). Nevertheless, they are well-adapted to a challenging problem of achieving best of both worlds with unknown transition kernels. 

Overall the paper is well-written and easy to follow. Comparisons to previous work are well discussed whenever needed. Main results and analysis are well-presented, hence I recommend the acceptance for this paper. 



There are some points I want to be clarified.

- In Section 3, the main idea seems to add additional term (loss-shifting?) $g_\tau$. However, I do not see what conceptually plays the role of $g_\tau$ in Algorithm 1. (Eq (11) is, in my interpretation, simply an adjusted loss with standard exploration bonus). Could you be more specific about the connection?

- Line 231-234: I do not understand what it does mean by "This framework, however, does not allow the loss-shifting trick discussed in Section 3" (or why it has to be).

- Line 293-294 "In fact, ... complicated": at least, could you explain which improvement you have or can be made? 



I also raise some other questions on the analysis

- Could you be more specific on your technical novelty? In which part of the analysis is different from (Jin et al. 2020) for adversarial case? 

- How is the regret decomposition for the stochastic case different from (Simchowitz and Jamieson 2019)? (or are they the same?)

- Line 345-346 "In fact, the reason ... terms":  I don't understand what you mean by $Reg_T(\pi^o)$ cannot be directly bounded - isn't your theorem bounds it by $O(\sqrt{T})$? 





Minor Comments

- Line 259: "in the bandit case" -> do you mean in the bandit-feedback case?

- Line 137: $\Delta(s,a)$ is not defined before used here.

- Line 177: "this natural and simple candidate" - do you mean the one used in (Zimmert and Seldin 2019)?
limitations_and_societal_impact: Limitations are not separately addressed in the main paper. Here are a few of my questions:

- Do you think the regret bound can be improved to $O(log T)$ in the stochastic cases in (Simchowitz and Jamieson 2019)?

- Can you improve the regret bound by a factor of $|S|$ in the adversarial case?
review_title: null

Meta-review: This paper has been very well-received by the reviewers, who all appreciated the significance of the contribution and the high quality of both the writing and the technical content. This is an excellent paper that clearly deserves to be published at the conference.
Decision: Accept (Oral)