Efficient Model-Free Exploration in Low-Rank MDPs

Summary

This paper studied model-free exploration in low-rank MDP. The authors proposed an algorithm based on the idea of barycentric spanner, which is provably efficient given a reachability assumption weaker than previous literatures.

Strengths

The paper writing is clear. The comparsion with previous related work and the design idea of the algorithms are clear. The paper provided results with a weaker reachability assumption than previous literatures.

Weaknesses

I have doubt about whether the algorithm can be called "efficient". It still requires to solve a complex optimization problem in Eq.(6), especially the objective function can be non-convex/concave w.r.t. feature class $\Phi$ and function class $\mathcal{F}$, even though many previous literatures claimed that "it can be efficiently solved". The sample complexity should be improved. Although this paper considered the model-free setting and realizability of $\phi^*$ is much milder than the model realizability, it still requires reachability assumption in some sense, while the previous model-based algorithms (like [1]) does not. [1] Uehara et. al., Representation Learning for Online and Offline RL in Low-rank MDPs

Questions

See weakness.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

N.A.

Summary

The paper studies the reward-free exploration problem for low-rank MDPs. The approach is based on the combination of the barycentric spanner and a model-free representation module. The authors provide a theoretical analysis of the algorithm for both the reward-free exploration task and the downstream reward-based task.

Strengths

The writing is clear and easy to follow. Both the representation learning problem and the reward-free exploration problem are important in RL literature. The result is significant, which applies to more general settings compared to existing works, and also has a comparable theoretical guarantee. The idea of combining barycentric spanner with representation learning is novel.

Weaknesses

1. While the paper studies the exploration problem of low-rank MDPs, its contribution mainly lies in the planning phase. The paper has limited contribution on the representation learning part, which simply reuses the algorithm and theoretical guarantee from existing RL papers. 2. The main theorem provides a guarantee on the total number of episodes. It might make the result more clear if the number of samples / trajectories can also be stated, just as the theorems in previous papers. Since the algorithm repeatedly collects samples in each episode, some being hidden in the RobustSpanner module, it is not easy to figure out the sample complexity at first look. 3. The reward-based downstream task is slightly different from existing reward-free framework. A typical reward-free exploration algorithm would only collect data in the exploration phase, and only use these collected data to construct a good policy for an arbitrary reward function. In the setting of this paper, the planning phase relies on the PSPD module, which seems to need additional interaction with the environment because the module itself (Algo 3, line 4-5) needs to sample data and construct a separate dataset. It's not clear whether this additional interaction is avoidable.

Questions

1. Since the representation learning part is used as a plug-in module of the algorithm, one may wonder what the theoretical guarantee will be like when the true state-action feature is given. Furthermore, how does this result compare with the existing literature for known state-action features? 2. The paper proposes a new reachability notion. While sufficient comparison has been given between it and existing notions, will this notion reduce to a more familiar concept when considering simple MDP settings, such as tabular MDP or block MDP?

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

The paper addressed some of its limitations and proposed some open questions for future work.

Summary

This paper studies model-free RL under low-rank MDPs. This paper first generalizes previous fromulation of low-rank MDPs to a uncountable state case. Then this paper proposes a non-optimistic, model-free RL algorithm called SpanRL, which can provide a good policy cover with polynomial sample complexity. With policy cover produced by SpanRL, this paper optimize any downstream reward function with polynomial sample complexity.

Strengths

1. This paper provides a comprehensive summary of prior research on low-rank MDPs and presents a clear table that compares their sample complexity results with previous work. 2. This paper introduces a novel model-free exploration algorithm for general low-rank MDPs, which improves previous work on model-free RL under low-rank MDPs in two aspects: requiring a less stringent reachability assumption and removing the non-negativity requirement for feature embeddings.

Weaknesses

1. One advantage of the algorithm emphasized in this paper is its computational efficiency. However, there is no experiments to validate this claim. 2. Due to the page limitations, several algorithms (subroutines) are deferred to the Appendix, which makes it hard to track the algorithmic steps. Additionally, I find there is no detailed descriptions and discussions of these algorithms. A high-level description of the algorithms will be helpful for reader to understand the novelty these algorithms. For instance, algorithm 2 is an error-tolerant variant of the classical spanner computation algorithm of [1], it would be beneficial if the authors can discuss in high level about the design modification and novelty of algorithm 2. 3. The machinism why SpanRL can improve previous work is not explain well. For example, which design of algorithm helps to remove the non-nagetivity assumption in [2]? In other words, why does [2] need such assumption while SpanRL doesn't need such an assumption? [1] B. Awerbuch and R. Kleinberg. Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97–114, 2008. [2] A. Modi, J. Chen, A. Krishnamurthy, N. Jiang, and A. Agarwal. Model-free representation learning and exploration in low-rank mdps. CoRR, abs/2102.07035, 2021.

Questions

As listed above.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

There is no negative impact in this work.

Summary

The paper proposes a new algorithm for the low-rank MDPs setting. With a new reachability assumption, the paper shows that one can learn a policy cover in a statistically and computationally efficient manner. The proposed algorithm works in a modular manner, using barycentric spanner for exploration and the replearn algorithm for representation learning. The paper proves that the proposed algorithm can indeed learn a policy cover with in poly number of samples.

Strengths

1. The overall intuition of the proposed algorithm is reasonable, the design of the algorithm is well motivated, and the technical parts of the paper seems right. 2. A computationally tractable model-free algorithm is a very good contribution for the low-rank MDPs setting. 3. The reachability assumption is novel and general, but it might require a better explanation for the intuition of the such reachability assumption: while previous visitation density or feature coverage assumptions are more intuitive, using $\mu$ seems less straightforward. 4. The proposed algorithm is modular and utilizes previous algorithms well.

Weaknesses

1. Unlike previous papers such as BRIEE or MUSIK, the proposed computational efficient algorithm is not empirically tested, but this is a rather small shortcoming since the major contribution of the paper is theoretical. 2. The paper requires more polishing. The ending of the paper seems rather sudden and abrupt, although plenty discussions have been given across the paper. There are other minor presentation issues, such as the FLAMBE paper is cited in two different versions.

Questions

One argument that consistently appears across the paper is that the merit for a model-free algorithm is to avoid making assumption on an additional function class $\Upsilon$, could you elaborate what is the practical significance of such condition?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, 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

N/A

Thank you

I thank the authors for carefully responding to all my questions/concerns. Intutively, requiring guarantees for the second moment will require more assumptions, this makes sense to me. But I am curious about deeper connection between these. I also understand this may not be answered in this paper and can be an interesting further question. Hence, I increase my score appropriately.