Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: In this paper, the authors study reward-free exploration in linear mixture MDPs where the transition probabilities are linear combinations of d known models. The authors propose UCRL-RFE which solves the problem provably efficiently. The authors further improve the sample complexity by using Bernstein-style exploration bonus. Finally, by constructing a hard instance with constant number of states and exponential number of actions, the authors prove a sample complexity lower bound for the problem under consideration. 
main_review: Recently there has been great in understanding the sample complexity of reward-free exploration in reinforcement learning. In this paper, the authors study reward-free exploration in linear mixture models. The main methodology is to combine the idea of defining exploration-driven reward functions as the uncertainty bonus (such idea was proposed in [17]) and mechanisms for quantifying uncertainty in linear mixture models. Moreover, the authors show how to improve the sample complexity by using a Bernstein-type uncertainty bonus. The authors also prove a lower bound by constructing a hard instance with three states and exponential number of actions. 

My main concern is the lack the novelty. The algorithms presented in this paper follow the same methodology developed in [17], with modifications on the exploration-driven reward function so that it works for linear mixture models (see Remark 1). Is that true that the main algorithm in this paper is a direct combination of the methodology in [17] and uncertainty quantification techniques for linear mixture models? If not, the authors should consider adding a section highlighting the technical challenges they face when adapting the methodology in [17] to linear mixture models. Such a discussion will significantly improve the paper.

Minor comment
Table 1: the algorithm in [25] does not work in linear MDPs. Rather, it requires linear completeness and certain explorability assumption. 
limitations_and_societal_impact: See main review.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider reward-free exploration for episodic MDP under the assumption of linear kernel MDP. Precisely they assume that the transition kernel is a linear function over a certain feature mapping. And the goal is to explore the MDP (without observing the rewards) in order to be able to predict the optimal policy for any reward function with high probability. They propose the model-based UCRL-RFE algorithm which uses exploration-driven reward and estimates the parameter by least-square regression with well-chosen targets. They prove a bound on the sample complexity of  UCRL-RFE of order O(H^5d^2\epsilon^{-2}). They also propose a variant of UCRL-RFE with Bernstein-type bonus that enjoys a sample complexity of order O(H^4d (H+d)epsilon^{-2}). Finally, they provide a lower bound on the sample complexity for reward-free exploration of order \Omega(H^2d\epsilon^-2).
main_review: The paper is well written and the proofs seem correct (see specific comments, I did not check the proofs relative to Algorithm 3). I think that in absolute terms it is interesting to study the optimal problem independent rate for reward-free exploration problem with linear kernel assumption. But on the other hand, the implementation seems limited to the tabular case and no simple examples are provided. Thus the proposed solution seems rather theoretical. 

Main comments:
-Can you provide intuition on the different sources of "optimism" in your algorithm. Because they are: the exploration driven reward function, additional bonuses in PLAN, and pseudo value function which should all help to explore. In particular why we cannot use the value V_h^k for the target and in the exploration-driven rewards instead of the max (this would save computations)?

-Can you elaborate on the implementation of UCRL-RFE when S is large or infinite? In particular, what is the time complexity of the algorithm in this case?  E.g. do we actually need to do a complete pass over all state-action pairs in Planning Module, Algorithm 1?  

-What do you think is the optimal dependence on the horizon H and how to obtain it? More generally would it be possible to match the lower bound? 

-What are the main technical differences/challenges with respect to [17] in linear-kernel MDP?


Specific comments:
-L49: Can you detail why the bound is too conservative?

-53: maybe here you should explain a bit what is the difference between linear MDP and linear kernel MPD.

-L93, Table 1: For the results, you should be precise with the setting otherwise the table is wrong. The papers [9,12,14] consider episodic MDP with bounded rewards in [0,1] and step-dependent transitions. In this setting, the optimal rate is of order O(H^3S^2A/\epsilon^2) and O(H^2S^2A/\epsilon^2) if the transitions are step-independent. [27] consider an additional assumption where the sum of the rewards is equal to 1 (and step-independent transitions) where they obtain a rate of O(S^2A/\epsilon^2) which they prove to be optimal given this extra assumption. Note that in particular, their algorithm has no guarantees in the setting considered by  [9,12,14].

-L20: It is not clear if the expectation or the variance are well defined for any function V no?

-L126: Do you have any example of MDP that satisfies this assumption except the trivial example of tabular MDP? In particular, an MDP where it is easy to compute the summation in L129.

-L138 Maybe you should describe how the agent interacts with the mdp during the exploration phase. 

-L186: Intuitively why do you need to take the maximum over f.  Because the "exploration driven
reward function"  is not enough to explore?

-L206: can you elaborate on this point because the main focus of the paper is to deal with large state space?

-L264: Since \tiled{\theta} and \hat{\theta} estimate both the same parameter \theta^* why you need two separate estimators?

-L315:  Thus do you think that the lower bound is sub-optimal in this case?

-L445: For all s?

-L477: Conditioned on the events of lemma A.2 and A.3  do we still have that conditionally the expectation of the random variable in the sum is zero in order to apply Hoeffding inequality?

-L538: there are extra }

-L578: the first equality is inequality.

-L584: can you detail this part, what is E_{s_h}? 

-L688: K should be in the sum and you should keep the sum in the middle inequality.

-L740: you also need to choose \alpha such that the probabilities are in (0,1).

-L745: bound on the cardinal is missing in the statement since taking for \cM a singleton is sufficient. You mean for all M\leq ... there exits ...

-L774: x and x' independent.

-L788: Ok you can in fact invoke the chain rule here and you do not have to consider a deterministic algorithm. P_\theta(Y_k) and E_{Y_k} are not defined.

-L811: could you define clearly \hat{\theta}
limitations_and_societal_impact: It is a theoretical paper without direct societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper studies reward-free model-based reinforcement learning for linear mixture MDPs. This paper devises a new algorithm to calculate a near-optimal policy and proves a lower bound on sample complexity. 
main_review: This papers develops a lower bound specifically for linear MDPs, which matches the upper bound in terms of $\epsilon$.

The major concern is that the MDP studied in this paper is time homogeneous, which may be restrictive in many practical cases. Is this homogeneity assumption fundamental to the proposed algorithm? In other words, is it possible to extend the analysis to the case where transition probabilities are different from step to step?

There are a few typos, such as Page 1 "the algorithm is given a specific reward function and use the collected data" where "use" should be replaced by "uses". 

limitations_and_societal_impact: This paper focuses on theoretical analysis. It's expected that the paper does not have direct negative societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The submission considers reward-free exploration scheme for linear mixture MDPs. Similar studies have been done in [17, 26] for a very similar setting of linear MDPs. In both models, the key property is the linear representability of value functions. The proposed algorithm is an optimism-based exploration scheme for linear mixture MDPs with Hoeffding's (or Bernstein's [28]) exploration bonus for linear models. In spirit, this is similar to Kaufmann et al. [12] which studied a similar reward-free approach in tabular MDP settings. If the computational aspect is not concerned for finding a optimistic value-function, then the sample complexity is upper bounded by $O(d^2)$. For computationally efficient implementation, sample complexity is increased by a factor of $O(d)$. The authors also provide a lower bound $\Omega(H^2 d / \epsilon^2)$ for reward-free exploration.
main_review: The paper is incremental in terms of the originality and significance: (1) the importance of the study on the proposed model should have been more discussed, since a very similar model (linear MDP) has already been studied quite a bit as a benchmark for theoretical studies on function approximation, and (2) techniques (optimistic value-iteration, Bernstein-type bonus) are not particularly new. Pseudo value function seems not much more than some optimistic value function for linear mixture MDP, which is new only because the considered model is different from linear MDP which have slightly different representation for transition and reward models. Main results are also somewhat predictable given many previous works on linear function approximation [3, 7, 10, 12, 17, 26, 28]. Overall, I recommend rejection for this paper. 



Comments

1. The claim for matching upper and lower bounds sounds misleading since it only holds for H \ge d (and in this case, dependence on H is sub-optimal anyway) and computationally inefficient algorithm. 

2. Line 43-44 (They also proved ...): In which setting [17] proved exponential lower bound?

3. Line 46-50 (However, both works ...): I do not understand why the model considered in previous work is a very larger class than linear mixture MDP. 

4. Eq (4.4): Why do you need regularizer on $\theta$? On which line in Algorithm 2 uses $\lambda$? 

5. Theorem 4.2: What is B? Any value range for B?

See also the limitations.



limitations_and_societal_impact: Limitations of the approach does not seem to be so well discussed in this work. In particular, more discussion on differences/novelties of the approach in comparison to previous work [7, 12, 17, 28] would have helped a lot to appreciate contribution of the paper. I also wonder if the sample complexity could have been better by O(d) in [17, 28] if a NP-hard optimization solver is allowed (as the authors assume for solving (4.3)). If that's the case, then I think even the result is not particularly novel since the improvement on the sample complexity on O(d) is mostly due to ignoring this computational issue.
review_title: null

Meta-review: The paper provides the first analysis of reward free in linear mixture MDPs. I think this is a quite natural complement to the literature of RFE. While the paper is well-executed, I find it hard to identify the technical challenges and why certain technical tools are necessary. This concern was also raised by several reviewers. The authors should explain the challenges specific to this setting and why the paper is not a "simple" combination of techniques available in the literature. Due to the theoretical nature of the paper, I think these are quite important points. In addition, during the discussion, no reviewer was willing to champion the paper, which currently stands in a very borderline position. I decided to vote for rejection due to the lack of clarity on the algorithmic choices and novelty to a field that has seen numerous advances in the last couple of years. 
Decision: Accept (Poster)