Provably Efficient Algorithm for Nonstationary Low-Rank MDPs

Summary

The paper presents a new way to perform off-policy RL coupled with representation learning over non-stationary low-rank MDPs, both in a parameter-based and a parameter-free fashion. The paper proposes some interesting new algorithmic techniques to tackle this (off-policy exploration, data-transfer model learning, and target policy update with periodic restart).

Strengths

# originality The work seems quite original in both the analysis and the contribution. # quality The quality of this work is satisfactory and the analysis is thoughtful. # clarity The exposition is clear and neat, I would suggest presenting the algorithms differently (See weaknesses) # significance The work seems to provide a significant contribution to the field, due to the several techniques it introduces.

Weaknesses

My only comment is about the exposition of the algorithm. I would suggest not citing equations but reporting them, and providing the output of the subroutines.

Questions

No questions

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I didn't find any section where the limitations of the proposed method were addressed

Summary

This paper present an algorithm for solving non-stationary low-rank MDP. It also provide a theoretical analysis of their algorithm,

Strengths

This is an interesting question. The presentation is clear.

Weaknesses

I sketch through the results and the proof. I doubt that the proof might be wrong. In page 14, the inequality (i) require the author to provide an upper bound of E_{P^*} f_h^k - E_{\hat P}f_h^k. The paper says that inequality (i) holds since Lemma A.13 and Lemma A.15. However, none of the lemma is related with the term I mentioned above. Therefore, I am worried that the proof might be wrong. More over, the writing of the proof can be improve, and the clearity of the paper have room for improvement. For example, it would be helpful to provide the definition of $\lambda$ in the main part. It would also be helpful to mention that $W\leq K$ in the main part.

Questions

See the 'weakness' section.

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

1 poor

Presentation

3 good

Contribution

2 fair

Limitations

See the 'weakness' section.

Summary

This paper investigates nonstationary RL in the context of episodic low-rank MDPs, where both transition kerns and rewards may change from round to round, and where the low-rank model contains unknown representations. The goal of this work is then to develop methods with low average dynamic suboptimality gap, which is a measure of how well the agent performs across all rounds. The authors start by proposing PORTAL, a base algorithm with three main ideas: (a) off-policy exploration for data collection which is particularly useful for non-stationarity; (b) the transfer of recent history data collected under previous different transition kernels for benefiting the estimation of the current model; and (c) updating target policies with periodic restart. PORTAL requires few hyperparameters, which greatly affect performance but may not be easy to set. for this reason, the authors also propose Ada-PORTAL, a second method that uses PORTAL as a subroutine and additionally treats the selection of the hyperparameters as a bandit problem. Under standard assumptions for low-rank MDPs and assuming that non-stationarity is not significant, the authors show that both methods achieve arbitrarily small average dynamic suboptimality gap with polynomial sample complexity.

Strengths

1. The paper extends the literature in low-rank MDPs by incorporating non-stationarity. In particular, the work advances the recent research on nonstationary linear (mixture) MDPs. Overall, the contribution is interesting, given the attention that both low-rank MDPs as well as non-stationarity have recently attracted. 2. The paper makes assumptions that are consistent with both the low-rank MDP literature as well as the non-stationary RL literature. 3. I was only able to check part of the derivations, which looked correct. I liked that the authors clarified how their work is different from recent works on non-stationarity or low-rank MDPs, not just in terms of the problem statement but also in terms of the new technical challenges.

Weaknesses

1. I appreciate the fact that the authors provided insights and clarifications in several parts of the paper. But the paper is still hard to follow. I think what generally helps with such works is to provide an overview of the proof strategy, explain which exactly elements from prior works are used, and what elements are new. I acknowledge that the paper contains some discussions here and there, but I feel that a more structured approach would significantly improve the exposition. 2. In its current form and presentation, I feel that the paper is only relevant to a very small audience of the ML/AI community.

Questions

1. Why periodic restart in this work does not require a smooth visitation frequency assumption (compared to Fei et al., 2020)? 2. The authors use EXP3-P in Ada-PORTAL. Is this choice critical or could other choices be made instead? Are there reasons to prefer one over the others? 3. The authors stress the significance of \tau and W. For the first algorithm W and \tau, how exactly should the be selected? Could the authors provide clear guidelines?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

None.

Summary

This paper studies reinforcement learning (RL) under non-stationary MDPs where the state transition and reward function changes across episodes. The paper focus on the low-rank MDP setting, in which the state transition function admits a low-rank decomposition. The authors propose a novel algorithm, namely PORTAL, along with theoretical results that characterize a bound for the average suboptimality gap of the learned policies over the episodes. Additionally, the paper also introduces an algorithm, namely Ada-PORTAL, for adaptive tuning of the hyperparameters of PORTAL.

Strengths

* The paper is the first to study non-stationarity in low-rank MDPs. * The proposed method is sound and results in a better suboptimality gap than previous related work (Wei & Luo, 2021).

Weaknesses

* A few algorithmic decisions and assumptions require better explanation/justification to improve the clarity of the paper (see below). * The method relies on an assumption that is not very realistic (reachability) and should be better discussed (see Limitations below). * (Minor) The paper does not have an experimental section.

Questions

Below, I have a few questions and constructive feedback for the authors: 1) In Section 3.2, I would suggest making it clearer what a “round” is. For instance, does each round have a fixed number of episodes? 2) The current version of Section 4.1 is a bit hard to follow. For instance, in Step 1, terms such as “bonus term” and “target policy” are used without being previously defined. 3) “However, in low-rank MDPs, the bonus term $b^k_k$ cannot serve as a point-wise uncertainty measure”. I suggest elaborating on why this is true. 4) In Step 1, why the exploration policy takes two uniformly chosen actions? This algorithmic decision is not discussed or explained. 5) I suggest writing comments in Algorithm 1 mentioning which lines correspond to Step 1, 2, and 3 for improving the clarity. 6) In Algorithm 1, why states are indexed two times (subscript and superscript) with the time step $h$, e.g., $s_h^{k, h}$? What the indexes mean was not defined. 7) What is the role of the coefficient $\tilde{\alpha_{k,W}}$? How is this selected? 8) “Compared with the previous work using periodic restart (Fei et al., 2020), whose choice of $\tau$ is based on a certain smooth visitation assumption, we remove such an assumption and hence our choice of $\tau$ is applicable to more general model classes.” Why can you remove this assumption? How is the value of $\tau$ selected? Please elaborate on why it is necessary to reset the target policy every $\tau$ episode.

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.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Assumption 4.3 is not very realistic: in most MDPs, it is not possible to reach any state of the MDP in a single step. For instance, in a maze, the probability of reaching the end of the maze from the initial state in a single step is zero. Is this assumption also made in related works, e.g., Wei & Luo (2021)?

thank you for the response

I thank the authors for their detailed response. I will increase my score from 5 to 6, since all my concerns and questions were addressed. I encourage the authors to incorporate the various clarifications into the final version of this work for improved clarity, presentation and exposition.