Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: This paper proposes the first model-free RL algorithm (RestartQ-UCB) for the non-stationary episodic RL problems, where the model parameters are determined by an oblivious adversary and change with time with a certain budget on the total variation. Moreover, the authors provide a rigorous analysis of RestartQ-UCB and establish a near-optimal regret upper bound as well as the first lower bound on the dynamic regret in non-stationary RL.

The paper is a novel and rigorous theoretical contribution to non-stationary RL. Overall the paper is well-written and easy to follow. I have done a careful check of the proof of Theorem 1 (including the technical lemmas) and a high-level check of the rest of the analysis, and they all look sound. Overall I do not find any particular weakness in this paper. My only concern is that RestartQ-UCB requires the knowledge of the variation budget in each epoch. While this assumption has been considered in (Ortner et al., 2020), it would be helpful to provide more justification for this assumption.

Additional comments:

-While I could follow the proofs step by step in a mechanistic way, it would be helpful to first outline the high-level idea of the proofs at the beginning of Section 4.

-It is not totally clear to me why stages are necessary for the analysis. Could the authors provide some intuition behind this design?

-While the proofs of Theorem 1 and 2 are similar, it would be helpful to at least highlight the main differences in the main text.

-In Appendix B.2: In the second sentence of the first paragraph, shall the goal be proving $Q_h^{k,*}(s,a)\leq Q_{h}^{k+1}(s,a)$ instead?

review_title: A rigorous theoretical contribution to non-stationary RL

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper presents an algorithm called RestartedQ-UCB for nonstationary episodic MDP. The setting studied is when the transition kernels and reward functions are both possibly changing with iterations. I think the setting is not quite novel, similar settings have appeared in several earlier papers, including Ortner et al. (2020) and Cheung et al. (2020).

The method proposed uses a simple restarting strategy on top of an existing algorithm with known stationary regret, for example, the Q-learning methods (Jin et al., 2018; Zhang et al., 2020). The idea of restarting strategy for nonstationary stochastic optimization or decision-making (even MDP, see reference below) is not new, which clearly diminishes the novelty of this paper. As far as I know,
1. stochastic optimization or online convex optimization. Omar Besbes, Yonatan Gur, and Assaf Zeevi. Non-stationary stochastic optimization. Operations Research, 2015.
2. multi-armed bandits. Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-bandit problem with nonstationary rewards. In NeurIPS, 2014. Omar Besbes, Yonatan Gur, and Assaf Zeevi. Optimal exploration–exploitation in a multi-armed bandit problem with non-stationary rewards. Stochastic Systems, 9(4):319–337, 2019.
3. stochastic linear bandits. Peng Zhao, Lijun Zhang, Yuan Jiang, and Zhi-Hua Zhou. A simple approach for non-stationary linear bandits. In AISTATS, 2020.
4.contextual bandits. Haipeng Luo, Chen-Yu Wei, Alekh Agarwal, and John Langford. Efficient contextual bandits in non-stationary worlds. In COLT, 2018.
5. MDP. Ronald Ortner, Pratik Gajane, and Peter Auer. Variational Regret Bounds for Reinforcement Learning. In UAI 2019. [NOTICE: this paper is published at UAI 2019 venue, while in the submission authors mistakenly cite as UAI 2020. This should be corrected.] A similar idea also appears for the tracking case (when the nonstationary setting reduces to the piecewise stationary) in UCRL2 paper (Jaksch et al. 2010, Section 7 Regret Bounds for Changing MDPs)

Some of the references are not well placed: "We measure the optimality of the policy π in terms of its dynamic regret (Cheung et al., 2020; Domingues et al., 2020)" I do not think the originality of dynamic regret (even for nonstationary MDPs) should be credited to these two papers.

As far as the extra optimism, this has also appeared in the recent work for studying nonstationary MDP (Cheung et al. 2020). 

The main results (Theorem 1 and Theorem 2) are interesting, didn't the algorithm require the variation quantities Delta_r and Delate_p as input? I think this is not fully overcome in previous studies, even the most recent papers (Cheung et al., 2020; Domingues et al., 2020; Fei et al. 2020). The issue should be highlighted in the theorem and the setting of input parameters in the statement of algorithms, explicitly.

The lower bound for nonstationary MDP is not surprising by constructing a piecewise stationary hard instance and further taking a reduction to the lower bound for stationary MDP (Jin et al., 2018). Similar constructions have appeared in earlier studies of dynamic regret, to name a few, online convex optimization (https://arxiv.org/pdf/1810.10815.pdf), linear bandits (https://arxiv.org/pdf/1810.03024.pdf), etc.

Overall, the paper fails to provide much technical contribution and novelty to the community since most techniques and ideas were published previously, and unfortunately falls below the bar of ICLR. Please correct me if I missed non-trivial technical contributions.

The final issue is that in the introduction section the authors provide several practical intriguing applications with modeling by nonstationary RL/MDP, and also claim that "our model-free algorithm is more time- and space-efficient, flexible to use, and more compatible with the design of modern deep RL architectures" but no experiments are offered especially in a conference like ICLR, while the theoretical contributions seem to be unable to stand it alone. The authors should implement the algorithm in practical nonstationary RL tasks to show its strength, a number of references can be found at the survey https://arxiv.org/abs/1905.03970
review_title: nonstationary episodic MDP

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper derives a low-regret algorithm to control non-stationary MDPs. By non-stationary, the authors mean that the transition matrix and reward function can vary over time. The sum of all changes is bounded by a variation budget \Delta (known by the controller). This algorithm combines two ingredients:
1. The learning horizon is decomposed into epochs whose lengths depends on \Delta.
2. Within an epoch, the algorithm uses an unmodified Q-learning UCB.

The authors derive an upper bound on the regret of the algorithm that is obtained by carefully choosing the epoch lengths.

I found the paper reasonably well written (although the technical part are not easy to understand, see below). The algorithm is clearly defined and the results are easy to understand.  The problem of learning in non-stationary environment is quite challenging and hence the result is appealing. The proof approach is quite classical for this kind of problems and looks reasonable (apart from a term of Proposition 1, see below).

That being said, I found that the paper has a number of shortcomings that prevent me from seeing its contributions as remarkable. In particular:

1. What is the main originality of the paper? The idea of restarting for non-stationary environment is not new (Jaksch et al. 2010). The use of Q-learning UCB is not new (Jin et al. 2018). The combination of the two and its analysis is probably new.  Yet, I fail to see it as a real contributions. In particular, I have the impression that the approach taken by the authors could be easily adapted by replacing Q-learning UCB by any other algorithm (UCRL2, PSRL,...).  The usual approach to obtain a regret bound is to view the regret as a term of opportunism + a term of concentration. Here, the only addition is to add a term of "error" due to \Delta and then to tune the epoch lengths. This approach seems algorithm-independent.

2. I do not understand why *model-free* is so important here. The fact that there is no analysis of model-free non-stationary algorithms in the literature might just be because model model-based algorithms perform better? The authors do not compare their algorithms to existing solutions. Some numerical experiments could be useful.

3. On page 8: where did the SAH^3 go? Naively replacing D by its value and T by SA\Delta H^2 leads to a term TH which grows in T. Where is the catch?

4. The heavy notations make the technical parts hard to follow. Also, on the beginning of page 6, the notations \v{n}^k_h are then transformed in \v{n} while being similar to N and \v{N}. I would hope that some simplification are doable.

review_title: Interesting model but the contribution is unclear to me 

final_score: rating: 7: Good paper, accept
review_content: The paper studies efficient model-free reinforcement learning in non-stationary Markov Decision process. They propose an algorithm with efficient dynamic regret bounds. Besides, they also propose matching lower bounds. 

pros:
- The theoretical results are solid since they achieve minimax regret bounds.

cons:
- The algorithm follows the similar algorithmic framework of [1], which studies provably efficient reinforcement learning with low switching condition. The algorithm of [1] suits non-stationary setting well since it periodically forgets the previous experience and only uses data collected recently. I guess this is the reason why this idea works for non-stationary environment. Maybe more discussion is needed in the paper.

- The assumption about prior knowledge of the variation budget in each epoch is a bit strong. Restart-UCB algorithm require this knowledge to construct the confidence bonus $b_{\Delta}$. However, in real applications, it is almost impossible to know the variation budget beforehand (If we know this, we can almost directly know the reward and transition in each step.) For theoretical analysis, I remember that many previous results don't need this assumptions, including papers about non-stationary MDP and non-stationary bandit. Since the reasonability of this assumption is important to quantify the contribution of the paper, I suggest that the authors should discuss in detail about this issue during the rebuttal period, including whether this assumption is common in the previous literature, and whether it is possible to remove the assumption.  

[1] Provably Efficient Q-Learning with Low Switching Cost


-------Post Rebuttal-------

Thanks for the feedback from the authors. I am glad to see that the new theorem (Theorem 2) has successfully tackle the problem about the prior knowledge of the variation budget. I have updated the score accordingly.
review_title: An interesting paper, though the assumption is slightly strong

Meta-review: The paper shows (nearly) matching upper and lower bounds on dynamic regret for non-stationary finite-horizon reinforcement learning problems. The paper studies an important problem and the results are interesting. Some reviewers are concerned that there is not enough algorithmic and theoretical innovations in light of prior results. Authors need to improve the presentation and add a more detailed discussion on related works, the novelty and the originality of the paper, and the new algorithmic and theoretical contributions. Finally, authors can improve the submission by implementing the proposed method and adding experiments.
Decision: Reject