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 variance-adaptive linear bandits and linear mixture MDPs. This paper improves significantly upon regret bounds obtained in the previous work by Zhang et al. (2021). To achieve this, they improved the structure of the confidence set in the previous work by removing the $\epsilon$-net construction in the previous work, and they improved the analyses of the previous work by replacing the complicated volumetric-based argument in the previous work by a simple argument based on their novel elliptical potential "count" lemma.
The improvement on the confidence set and the novel elliptical potential "count" lemma are technically solid.
strengths_and_weaknesses: 
Strengths:
1. The regret bound is significantly improved upon the previous work.
2. The analyses is largely simplified upon the previous work, which paves the way for the novel convidence set to be applied to broader theoretical applications. 
3. The novel elliptical potential "count" lemma would be of broarder interest to the bandit learning community. 
3. The bound for linear mixture MDP is near-optimal up to log factors.

Weakness:
1. The bound for linear bandits is $\sqrt d$ away from being tight.
2. The confidence set is still too complicated to be applied in practice, and optimizing in the confidence set cannot be done in polynomial time.

questions: 
1. Why do the main text and the appendix have different bibliography? This looks not common.
2. Line 406-408 looks strange. Did you forget to delete them? 
3. Line 411: there is "KJ" in the text. Will it break double-blind?
limitations: 1. The proof roadmap for both linear bandits and linear mixture MDP largely follows upon the previous work, which might limit the novelty of this paper. However, the confidence set  might not be able to become a standalone paper, so I think it inevitable to have this limitation.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper revisits the problem for linear bandits and linear mixture MDPs from Zhang et al. (2021). The authors follow their notion of variance-adaptive regret bound and provide novel analysis to improve such bound. In particular, for the linear bandits setting, the current work improves Zhang et al.’s result by a factor of $O(d^3)$ in the leading regrets. For the linear mixture MDPs, the improvement is a factor of $O(d^{3.5})$. The key of the analysis is a novel peeling-based regret analysis that leverages the elliptical potential ‘count’ lemma, which could be of independent interest to other related problems.
strengths_and_weaknesses: Strength:
1. The authors made solid theoretical contributions to the literature. The current work significantly improves previous works’ regret bounds, and the techniques are applicable to both linear bandits and linear mixture MDPs. From my perspective, the peeling techniques and the elliptical potential count lemma can be applied to a wider scope beyond the aforementioned linear bandits and linear mixture MDPs.

2. The technical analysis is sound and the writing is easy to follow.

Weakness

1. My main concern is about the practical usage of the current variance-adaptive algorithm. The confidence interval used in Eq. (3) seems quite complicated. I cannot see the clear landscape of this confidence interval. I wonder how to find the action $x_k$ given such a “conceptual” interval. It could be better if the authors could elaborate more on the landscape of the optimization problem using Eq. (3) as the feasible set of $\theta$. For example, the author could explain under what conditions or in what special cases this interval could be efficiently used. Another way is to show some plausible heuristics to calculate line 4 of the VOFUL2, like optimizing $\theta$ and $x_k$ alternately.

2. The current work does not include any empirical evaluations for their algorithm and the contribution is purely theoretical. I guess it is due to the same reason as mentioned above that line 4 of VOFUL2 does not have efficient solutions.

questions: Please justify or comment on the two weaknesses mentioned in the above Strengths And Weaknesses part. I would like to raise up my score if the authors can solve my concerns.

limitations: The authors mentioned the limitations of computational issues but does not provide explicit solutions, see my comments in the Strengths And Weaknesses part. And there is no potential negative societal impact of their work.
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 work focused on the linear bandit and linear mixture MDPs. The author proposes a novel variance-dependent algorithm, VOFUL2, for the linear bandit, which improved the regret with a factor of $d^{3}$. For linear mixture MDP, the author also proposes the VARLin 2 algorithm with a horizon-free regret guarantee, which improved the previous results with a factor of $d^{3.5}$.
strengths_and_weaknesses: Strength:
1. The VOFUL2 Algorithm improved previous results in unknown-variance linear bandit and reduced the gap to only $\sqrt{d}$.
2. The VARLin2 Algorithm obtains a horizon-free regret guarantee for linear mixture MDP, and the result is near-optimal with the dimension d.

Weakness:
1. The VOFUL2 and VARLin2 algorithms are not novel; they are part following the VOFUL and VARLin 2 algorithms in Zhang et al. (2021). 

Zhang Z, Yang J, Ji X, et al. Variance-aware confidence set: Variance-dependent bound for linear bandits and horizon-free bound for linear mixture MDP

2. VOFUL2 and VARLin2 also inherited the disadvantages of computing inefficiently. In addition, without the $\epsilon$-net structure, the VOFUL2 algorithm needs to consider the intersection of the infinite confidence set, which is much more complicated than the original VOFUL algorithm.

3. The Lemma 4 (elliptical potential count) is not new. This Lemma and also the corresponding peeling technique in linear mixture MDPs appears in the proof of Lemmas B.3-B.5 (He el. al 2021) previously.

He J, Zhou D, Gu Q. Logarithmic regret for reinforcement learning with linear function approximation.

questions: My main concern is the following:
1. It seems strange that the dependence of dimension d in linear Mixture MDP is better than the linear bandit problem. For both variance-dependent results in Zhang et al. (2021) and Zhou et al. (2021), the dependence on dimension d in MDP is no worse than the linear bandit problem, and the variance-dependent result can only help to reduce the H-factor with the help of total variance. Is there some problem with the result in linear Mixture MDP, or the result in the linear bandit can be improved? It is better if the author could provide more explanation about this difference. I may increase my score if the author can solve this main concern.

Zhang Z, Yang J, Ji X, et al. Variance-aware confidence set: Variance-dependent bound for linear bandits and horizon-free bound for linear mixture MDP

Zhou D, Gu Q, Szepesvari C. Nearly minimax optimal reinforcement learning for linear mixture Markov decision processes.

Other comments:
1. For the Markov decision process, Zhang et al. (2021) first propose the horizon-free result and show learning MDP is not more complicated than the bandits. It is better if the author can comment on it and compare the result of VARLin 2 with it since both achieve a horizon-free regret guarantee.

Zhang Z, Ji X, Du S. Is reinforcement learning more difficult than bandits? a near-optimal algorithm escaping the curse of the horizon

2. For the RL with linear function approximation, He el. Al 2021 also provides a potential elliptical count and uses the peeling technique to analyze linear MDP and Mixture MDP. Therefore, it is better if the author can comment on it before the Lemma 4 (elliptical potential count) and the peeling-based proof.

He J, Zhou D, Gu Q. Logarithmic regret for reinforcement learning with linear function approximation.

3. For the unit cumulative rewards (Line 9), since the reward $r_h^k$ depends on the random variable $s_h^k,a_h^k$, it is better if the author can define it more clear. For example, should the expected cumulative reward be smaller than 1, almost smaller than 1, or always smaller than 1?

4. In Line 77, the reward $|r_k|\leq 1$ can not implies that $|\epsilon_k|\leq 1$ almostly, since the mean of reward $|r_k|$ is not 0.

5. In the attachment, some comments such as "KJ: add the details to the proof" should be removed.
limitations: This paper provides theoretical guarantees for learning linear bandit and linear mixture MDP. There is no negative societal impact.
review_title: null

Meta-review: metareview: This paper gives the first minimax optimal (up to log factors) and horizon-free for linear mixture MDP and improved variance-dependent bound for linear bandits. Furthermore, the paper developed a new peeling-based analysis that can be useful for other problems. These contributions make this paper a strong paper in the theoretical RL community. The AC thus recommends acceptance. 
confidence: Certain
Decision: Accept