Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: This paper studies the problem of Episodic Linear Mixture MDPs, where the transition model is a linear combination of $d$ valid MDP transition models. The MDP has a countable set of states and a finite set of actions, and the cumulative reward in each episode is not larger than $1$. The agent interacts with the MDP for $K$ epsidoes, and the planning horizon is $H$ for each episode. As a warm-up, this paper gives an algorithm WeightedOFUL$^+$ for heterogeneous linear bandits. It is computationally efficient and achieves a state-of-the-art $\tilde{O}(d \sqrt{\sum_{k=1}^K \sigma_k^2} + d)$ regret, where $\sigma_k$ is the variance of noise in episode $k$ (assumed to be known). The main result is a computationally efficient algorithm, HF-UCRL-VTR$^+$, for Linear Mixture MDPs. It achieves a $\tilde{O}(d \sqrt{K} + d)$ regret, matching the lower-bound given in this paper.
strengths_and_weaknesses: Strengths:
1. This paper improves upon previous results of Linear MABs and Linear Mixture MDPs by giving computational efficient algorithms with matching state-of-the-art regrets. For Linear Mixture MDP, this paper also provides a tight lower-bound.
2. This paper is clearly written. The comparison between different works is straightforward.
3. This work is significant because it nearly closes the problem of Linear Mixture MDP.


Weaknesses:
1. WeightedOFUL$^+$ needs knowledge of $\sigma_k$, which is in general not practical, otherwise, it would degenerate into $d\sqrt{K}$.

questions: None.
limitations: None.
review_title: null

final_score: 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.
review_content: summary: This paper extends the previous work [1], by proposing a novel variance-aware and uncertainty-aware weight in the weighted least square regression to provide an improved analysis on the heterogeneous linear bandits and linear mixture MDPs, that can be computational efficient for linear mixture MDPs and for the case when we have an upper bound of the noise scale in heterogeneous linear bandits. The key observation is that, by introducing the additional uncertainty aware terms in the weight, we can have much tighter confidence set when $\sigma_k$ is small and $K$ is large, as illustrated in Lemma 4.3 and Line 213-216.

[1] Zhou, Dongruo, Quanquan Gu, and Csaba Szepesvari. "Nearly minimax optimal reinforcement learning for linear mixture markov decision processes." Conference on Learning Theory. PMLR, 2021.

strengths_and_weaknesses: ### Strengths:
* Simple but clear theoretical results.
* Well-written in general.

### Weaknesses:
* The authors do not provide so much intuition on the key results (Lemma 4.3). I think it deserves much more discussion.
* A minor concern: the part other than Lemma 4.3 is not technically significant.

questions: * This paper is in general good. Mainly I hope the authors provide more intuition and discussion on Lemma 4.3, especially how it compares with the self-normalized martingale concentration inequality in [1]. It may not be so simple for the potential audience to understand the motivation.

* Additional Minor Issues:
* * Please check the input of the algorithm. Some hyperparameters should appear in the input part (e.g. $\alpha$ and $\gamma$ in Algorithm 1).
* * It would be better if the authors can make some additional discussions on the work without the assumption of known variance. As far as I know, unlike the authors claim in Line 84-87, both Zhang et al. and Kim et al. do not require an upper bound of $\sigma_k^2$. And to deal with this issue, they need to work on the noise concentration and use some peeling techniques to construct the confidence set. I hope the authors make this distinction clear.

[1] Zhou, Dongruo, Quanquan Gu, and Csaba Szepesvari. "Nearly minimax optimal reinforcement learning for linear mixture markov decision processes." Conference on Learning Theory. PMLR, 2021.

limitations: This paper is on the theory side and does not need to address the societal impact.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper gives the first computationally efficient horizon-free algorithm for linear mixture MDPs, which achieves the optimal $O(d\sqrt{K} + d^2)$ regret up to logarithmic factors. Their technique can also be applied to heterogeneous linear bandits and achieve $d\sqrt{\sum_{k=1}^K\sigma_k^2} + d$ regret when the reward variance $\sigma_k^2$ is known.
strengths_and_weaknesses: This paper solves a very important open problem in RL with linear function approximation: getting horizon-free regret bound efficiently. The developed techniques can potentially be applied to many other problems and improved current results. The algorithm also has a simple structure and thus easy to implement and extend. Discussions on related work and implications of results are thorough and well presented. 

Given that the algorithm is simple enough, it would be beneficial to also perform experiments to verify the theoretical gain.
questions: Can this technique be applied to linear MDP and achieve horizon-free regret?
limitations: Nothing necessary stands out.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposed a computationally efficient horizon-free RL algorithm.
strengths_and_weaknesses: The writing needs improvements and the notation is a bit heavy. The contribution is not very significant. UCRL-VTR itself is not computationally-efficient beyond linear case, as pointet out in "Model-Based Reinforcement Learning with Value-Targeted
Regression".

I feel the algorithm used in this paper does not show significant improvement over the one in "Nearly minimax optimal reinforcement learning for linear mixture markov decision processes." The weighted OFUL+UCRL VTR is almost the same. The improvement of regret bound for linear bandit is not huge since dsqrt{sum sigma_i^2} term is the leading term. 

The main trick to obtain horizon-free bound seems to be cumulative rewards bounding by [0, 1] + variance-aware confidence interval. This is known before and this paper seems to offer no new message in my mind. 

I think Algorithm 2 heavily relies on linear mixture MDP assumption. That means you assume the complicated environment enjoys a quite simplified parametric form. If your algorithm is general but you use linear mixture MDP as a sanity check, that's fine. But the algorithm now is designed for linear mixture MDPs.

Since the paper claims the major contribution is computational-wise, I feel some simple experiments are needed. It is unclear what's the empirical performance since it is not built on any algorithm that is widely empirically evaluated. It will be good to observe what's the meaning of horizon free on existing benchmarks. 

questions: 1. If the cumulative reward is bounded by H, will the bound still be independent of H? 
limitations: no
review_title: null

Meta-review: metareview: This work advances the state-of-the-art for horizon-free regret bounds for linear mixture MDP as well as heterogeneous linear bandits. Clear accept.
confidence: Certain
Decision: Accept