Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies reward-free learning in linear MDPs. It proposes a computationally efficient algorithm LSVI-RFE and improves the upper bound to O(H^4d^2/eps^2). An Omega(H^3d^2/eps^2) lower bound is also provided.
strength_and_weaknesses: Strengths:

1. The LSVI-RFE algorithm is computationally efficient and improves the current state of the art bound in reward-free linear MDPs.

Weaknesses:

1. Some literature in reward-free learning could be added to the paper.
clarity,_quality,_novelty_and_reproducibility: This paper is clearly a good add to the reinforcement learning theory community. I haven't checked the details and the correctness of the paper due to the short review timeframe.

To summarize the contribution of the paper. On the upper bound side, the d^2 sample complexity in reward-free linear MDPs has just recently been shown in the paper by Wagenmaker et al. (2022). This paper further improves the H dependence from H^5 to H^4. On the lower bound side, this paper also provides a H^3 lower bound. Moreover, this paper discusses the difficulty to further bridge this gap.

For the technical part, this paper mostly builds on Chen et al. (2021) and Hu et al. (2022). More specifically, the paper uses the idea of enlarging the exploration bonus by a H factor in Chen et al. (2021) to improve the H dependency. In addition, the authors use the fine-grained control of the magnitude of w_{k,h} to improve the d dependency. Therefore, the algorithm design and the analysis might not be very novel. With that being said, putting them into a single piece and getting a final result is definitely a valuable contribution.

Regarding this part, I have a question. Hu et al. (2022) uses different Q-functions (Over-optimistic Q function, Optimistic Q function, Pessimistic Q function), but only a single function Q-function seems to be used in this paper. Can you comment on why you do not need them? My guess is that it might be related to a the worse in H factor in the upper bound.

Another question is that I feel usually a larger bonus term (beta) implies a larger regret since its sum will enter into the regret bound. But both this paper and Chen et al. (2021) mention that using the larger bonus instead reduces the regret. Probably this has been answered in the paper by Chen et al. (2021), but I would appreciate that if the authors can comment on that.

The proof of the lower bound part mostly follows Chen et al. (2021), and I can also share its intuition.

Finally, I would like to point out a few related works in the reward-free learning setting. [1] is about reward-free learning setting and similar as Zanette et al. (2020c) requires some additional assumptions. [2] can handle the more general low-rank MDPs (linear MDPs + unknown feature phi), but requires a reachability assumption. [3] can handle the general function assumption setting and subsumes linear or low-rank MDPs. There are also more related works in the more restricted block MDPs, e.g., [4] and the reference therein.

[1]Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimality

[2]Model-free Representation Learning and Exploration in Low-rank MDPs

[3]On the Statistical Efficiency of Reward-Free Exploration in Non-Linear RL

[4]Efficient Reinforcement Learning in Block MDPs: A Model-free Representation Learning Approach

One minor question: This paper assumes the reward function is linear. Can you handle the case that the reward function is non-linear, but given in the planning phase (assuming that you know the reward function class or simply its size in the online phase)?
summary_of_the_review: Please see other blocks.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the reward free exploration problem in the linear MDP setting. It proposes a sample-efficient and computational-efficient algorithm LSVI-RFE, which returns an $\epsilon$-optimal policy given any reward function using $\tilde{O}(d^2H^4/\epsilon^2)$ exploration trajectories, which is tighter than previous works. Moreover, it shows that the lower bound of sample complexity of reward free exploration in linear MDPs is at least $\Omega(d^2H^3/\epsilon^2)$. 

strength_and_weaknesses: In general, this paper is an extension from Hu et al. (2022) who studies the regret minimization problem in linear MDPs to the reward free setting. The key technical novelties include the variance-aware weighting mechanism to estimate the transition dynamics, the over-optimistic bonus term in the exploration phase, and a larger exploration function in terms of $H$. Although these techniques have been proposed by Hu et al. (2022) and Chen et al. (2021), it requires effort to adapted them to the reward free setting. However, the results in this paper is not that surprising, given previous works such as Hu et al. (2022) and Chen et al. (2021).

Importantly, I found it hard to understand a few sentences in the main text, mainly because the authors used involved explanations instead of straight forward sentences. For example, what does it mean by "negligible cost" at the bottom of page 5? How does the mentioned term relate to the total uncertainty in the exploration phase? Another example is the first sentence in Remark 4.2. It is confusing to directly say "auxiliary value functions" and "decouple UCB bonuses" since this function and meaning of decouple are not defined at all. I suggest the authors use more straight forward sentences to express their ideas.

Lastly, I want to mention that the line spacing on page 5 and 6 seems to be abnormal, the lines are too much squeezed. 

Minor comments and typos: 
- Line 9 of Algorithm 1: $\hat{V}_{k,h}$ -- $\hat{V}_{k,h+1}$
- Line 7 of Algorithm 1: it seems that the constant should be 4 according to the proof in Lemma A.15
- Section 4: instatanous -- instantaneous
- Why does the first inequality (the $\sqrt{d}$ term) of Equation (9) hold?
clarity,_quality,_novelty_and_reproducibility: See above
summary_of_the_review: This paper proposes a reward free exploration algorithm in linear MDPs with improved sample complexity. It also provides a lower bound by reducing the reward free problem to the standard linear MDP exploration problem. The paper provides rigorous proofs for all the statements, but some formulas and sentences are a bit confusing. Overall, I vote for acceptance, but I strongly recommend the authors to clarify their expressions and clean the typos in the technical part of the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies the reward-free reinforcement learning in linear MDPs. In particular, by utilizing techniques from the minimax optimal algorithm for ordinary reinforcement learning in linear MDPs, this paper improves the sample complexity to an order of $\widetilde{O}(H^4d^2/\epsilon^2)$. Meanwhile, it also improves the lower bound to an order of $\Omega(H^3d^2/\epsilon^2)$, thus matching the lower bound in terms of dimension $d$.
strength_and_weaknesses: ### Strengths
This paper proves a first sample complexity bound that is optimal in $d$ by improving over the previous lower bound. Meanwhile, the paper is also well-written with a clear logical flow.

### Weaknesses
It seems most of the technical innovations claimed in Algorithm 1 directly come from [Hu et al. (2022)]. Indeed, it is by no means trivial to derive all details step-by-step. However, it will be better if the paper can clarify whether the techniques in Algorithm 1 that are similar to those in [Hu et al. (2022)] actually contain significant difference.

On the other hand, the improvement seems to be marginal since [Wagenmaker et al. (2022)] has already achieved optimal dependence in $d$. It will be more significant if the results in this paper can also be optimal in $H$.

```
[Hu et al. (2022)] Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 8971–9019. PMLR, 2022.
[Wagenmaker et al. (2022)] Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon S Du, and Kevin Jamieson. Rewardfree rl is no harder than reward-aware rl in linear markov decision processes. arXiv preprint arXiv:2201.11206, 2022.
```
clarity,_quality,_novelty_and_reproducibility: The clarity of this paper is good in general. However, its novelty seems to be limited as discussed in the previous section.

#### Questions
- Can you explain how the magnitudes for $w_{k, h}$ are chosen in two different conditions at line 20 and 22 in Algorithm 1?
- Do the techniques and analysis of variance-aware weights and weighted linear regression in this paper have any significant difference from those in [Hu et al. (2022)]?


```
[Hu et al. (2022)] Pihe Hu, Yu Chen, and Longbo Huang. Nearly minimax optimal reinforcement learning with linear function approximation. In International Conference on Machine Learning, pp. 8971–9019. PMLR, 2022.
```
summary_of_the_review: This paper improves the upper bound and lower bound for reward-free reinforcement learning in linear MDPs to achieve a sample complexity that is optimal in $d$. However, the technical novelty and significance semm to be limited.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors study reward-free reinforcement learning in linear MDPs.  In this setting, the agent first interacts with the environment for some fixed number of timesteps without knowledge of the downstream reward function it is trying to optimize.  Based on the estimated transition distribution from samples obtained in this exploration phase, the agent is given a reward function and is tasked with outputting an $\epsilon$-optimal policy.  This paper focuses on the linear MDP setting, where the rewards and transition kernel can be written in terms of a known feature representation of an unknown vector (or distribution).  The authors show a novel algorithm with an $H^4 d^2 / \epsilon^2$ sample complexity bound, where $H$ is the episode length and $d$ is dimension of features.  They also show a lower bound of $H^3 d^2 / \epsilon^2$, essentially showing their result is tight up to a factor of $H$.  The algorithm is based on new concentration based on Bernstein confidence sets to improve upon the sample complexity results of prior literature.

More concretely, the authors consider an MDP defined as $(S,A,P,r,H)$ where $S$ and $A$ are state-action space, $P$ transitions, $r$ reward, and $H$ horizon.  They assume MDP is linear, i.e. known features $\phi$ of $S \times A$ which map to a $d$ dimensional vector with $r = \theta^\top \phi$ and $P( = \phi^\top \mu$ where $\mu$ is a distribution over the next states.  The goal is to perform reward free exploration, i.e. design policies to explore the space with unknown reward function, and then given a reward function compute a near optimal policy.

At a high level the authors provide two contributions on this setup:
1. The authors improve the best known algorithmic guarantee to be $H^4 d^2 / \epsilon^2$.  The algorithmic framework follows the standard form (use reward as "exploration" bonuses in the data collection phase), and then solve planning problem over estimated transitions once given a reward function.  However, they modify the algorithmic sketch by introducing novel confidence terms with Bernstein concentration to obtain the new results.
2. The authors improve the lower bound result to be $H^3 d^2 / \epsilon^2$ improving on the best known results.  They highlight how the lower bound is novel, and uses existing techniques from the linear MDP lower bound setup.

## Questions
- Based on the discussion on page 9 - do you believe that the gap remains in the achievability portion (i.e. designing an even better algorithm to save the extra $H$ factor) or the impossibility result?

## Minor Comments
- Defining sample complexity on page 4 should highlight that it should hold for all $r$
- vspace issues on page 6 before algorithm 2
strength_and_weaknesses: ## Strengths
1. The authors tighten the lower bound and prove new state-of-the-art sample complexity guarantees for the well-studied reward free learning in linear MDPs.
2. The authors present a simple algorithmic framework using existing techniques (least squares regression of the value function under "bonus"-tuned reward functions) allowing them to improve on the sample complexity required.

## Weaknesses
1. The authors include no discussion on the computational complexity of the algorithm.
2. The authors provide no empirical results of their algorithm's performance
3 The algorithmic design seems like a straightforward extension of prior mechanisms for linear function approximation for the reward-aware setting. The algorithmic contributions could be highlighted more in the writing.

clarity,_quality,_novelty_and_reproducibility: ## Clarity

The paper is extremely well written and easy to follow, although a bit on the technical side. I listed some small comments on writing earlier up in the review. The two most useful clarifications which I think could help:
- Provide an overall algorithm sketch before the discussion in section 4 instead of just directly highlighting the differences of the proposed algorithm to the related literature
However, I appreciated the proof sketch, and table that were included in the introduction to help conceptualize the main contributions in thep aper.

## Quality + Novelty

The paper provides an improved analysis of upper and lower bounds for reward-free exploration in linear MDPs.  The theoretical results both help close the gap between what sample complexity is achievable (improving an $H$ factor in the lower bound) and also designing a novel algorithm with improved sample complexity (improving an $H$ factor again).  This helps to slowly close the gap (now only an $H$ factor missing) between the achievable upper and impossibility results from lower bounds in this problem.  Through developing the algorithm the authors propose a novel Bersnstein bound with elliptical potentials in order to improve and obtain the optimal dependency on $d$ for the algorithmic results.
summary_of_the_review: The paper provides strong theoretical contributions for improving upper and lower bounds for reward-free exploration in linear MDPs, which improves the state-of-the-art bounds in this setting.  The paper is well written, although very technical, but highlights the main differences and contributions between the paper and the related work.  However, the paper offers no empirical results (or discussion on computational tractability of their proposed algorithm), although standard in the RL with linear function approximation literature.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents an algorithm for reward-free exploration in linear MDPs reaching a minimax optimal sample complexity up to an $H$ and logarithm factor. A number of new analysis tools have been introduced and can be of independent interest. All reviewers lean unanimously toward acceptance so I will recommend so as well.
justification_for_why_not_higher_score: The paper is about a minor improvement on a relatively well-studied theoretical problem and is unlikely to be of broad interest to the ICLR community.
justification_for_why_not_lower_score: N/A.
Decision: Accept: poster