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: The work consider RLSVI-type algorithms on a bilinear exponential family MDP.
They make several contribution, including achieving tractable exploration.

I believe this work represents a significant improvement over existing art, both in terms of result as well as techniques involved. The work is well explained and it flows easily.
strengths_and_weaknesses: I appreciate the work: I think it is well explained, there is a solid contribution to a well defined problem.
I therefore recommend acceptance. 

However, I have one major complaint / observation.
This work is model based, but the authors claim that it applies to the linear MDP model. Specifically, there is a choice that results in linear MDP. However, as I understand, not all linear MDP as defined in (Jin et al, 20’) can be solved with this algorithm. This is because fixing \phi on a linear MDP still yields many choice for \mu (proportional to the state space). In this case, one would need order S (the state space) parameters to fully describe the transition kernel of the linear MDP. Jin et al, 20’ bypasses this problem as it only needs to compute inner products, but the submission here puts a specific model on P; I would expect this model to be of order S in terms of dimensionality. Rather, the model assumed here seems to be that of Yang et al, “Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound” which is far more restrictive. If that’s the case, the comparison / improvement with Zanette et al “Frequentist Regret Bounds for Randomized Least-Squares Value Iteration” is also not as clear, as the two operates in quite different models. More precisely, this work seems to be model based (as explained above); as such, it requires estimating different quantities that the work by Zanette et al. It follows that the improvement that removes the artificial clipping of the value function (and improves the bound) used in Zanette et al. may be enabled by the setting where the current algorithm operates. I think this aspect should be clarified, both in the rebuttal as well as in the paper (apologies if I missed something).
questions: See above in details
limitations: In the specific linear setting considered by the authors, only a restricted linear MDP model seems to be covered
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 studies episodic reinforcement learning where the reward and transition probability functions belong to parametric bilinear exponential families. A randomized least square value iteration algorithm is proposed to perform tractable exploration and planning for bilinear exponential family of MDPs. Novel analysis techniques are introduced to show that the regret of the proposed algorithm is bounded by $\widetilde{\mathcal{O}}(\sqrt{d^3H^3K})$.
strengths_and_weaknesses: This paper is well-written and easy to follow. The authors have clearly summarized their contributions and discussed the improvement in their method over existing works. The theoretical analysis seems to be novel and non-trivial. However, the bilinear exponential family model defined in this paper seems to be more restrictive than the original definition in [CGM21]. Also, some notations are confusing. See more details below.
questions: Some comments and questions are as follows:

1. The notation for matrix $\mathbb{A}$ in Algorithm 1 is used before its definition. It's better to move earlier the definition of $\mathbb{A}$.
2. Compared with the original definition of the bilinear exponential family model in [CGM21], the factor $h(s',s,a)$ is omitted. Is this critical for the observation of linearity of transitions in Eq.(4)?
3. It is said in line 41-43 that linear MDP is a special case of the bilinear exponential family model. Could the authors elaborate on this?
4. In line 11 of Algorithm 1, solving $\hat\theta^p(k)$ and $\hat\theta^r(k)$ involves integral approximations as remarked in line 176-177. Can this be implemented efficiently? More details on this should be provided.
5. The $({\hat\theta}^p, \tilde\theta^r)$ in line 6 of Algorithm 1 should be indexed with $k$? Similarly, in the regret decomposition in Eq.(9) and the corresponding analysis in Section 5 and Appendix B, what is $\hat \theta^p$? Is it an arbitrary estimator or some estimate constructed during running Algorithm 1?
6. Following the previous question, it is not clear why $\zeta_{hk}$ in line 508 in the appendix is a martingale sequence. Does $V_{\hat\theta^p,\theta^r,h+1}$ depend on previous data? Details about this $\hat\theta^p$ need to be specified.

---
Minor issues:

1. In line 22, '$t = 1, \ldots, H$', missing a comma.
2. It seems that the definition of $\mathbb{E}_{s,a}^{\tilde\theta^r}[r]$ is missing in the main context.
3. In line 40, a few extra '-'.
4. The inner product in Eq.(5) and the equation under line 191 should be $\langle\cdot, \cdot \rangle_{\mathcal{H}}$?
5. In line 140, '$[p, r]$' should be {$p, r$}?
limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
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 studies model-based reinforcement learning for episodic Markov decision processes whose rewards and transitions are parametrized by bilinear exponential families with features of state and action. To balance the exploration-exploitation trade-off, the author suggested a randomized algorithm that injects a calibrated Gaussian noise in the parameter of rewards. The proposed algorithm achieves $\tilde{\mathcal{O}}(\sqrt{d^3 H^3 K})$ regret bound with high probability. 

strengths_and_weaknesses: <Strengths>

1. In this paper, the author not only presented a provable algorithm for a model-based algorithm whose transitions and rewards are parametrized by a bilinear exponential family that extends the linear transition assumption but also improved the regret by $\sqrt{H}$ compared to the upper-confidence based algorithm in a similar setting. 

2. Unlike the other model-based algorithms that assume the reward information is known, this paper solves the problem under the assumption that neither transition model nor reward information is known. In addition, it is interesting that the analysis is carried out by dividing the “Good rounds” and “Bad rounds” according to the weighted norm of the state-action feature without using the handcrafted clipping value function.

3. Based on the concentration results of the upper-confidence based algorithm in a similar problem setting, the author presented a randomized algorithm which is known to be practical but difficult to analyze with a frequentist regret bound guarantee for the first time. 

<Weakness>

1.  Although the author dealt with the setting where the model is parametrized by the bilinear exponential family, but it seems to solve the problem by using linearity in RKHS. This seems to rely on the information on the RKHS (e.g., RBF kernel $k(x,y)$) corresponding to the transition probability that the agent estimates. If not, what is the difference between the problem in this paper and the linear MDP method in ([JYWJ20], [ZBB+20], Yang & Wang;2020)  ?
    
c.f) Yang & Wang, 2020: Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound

2. As the author said, the most existing works on model-based RL usually assume that information about reward is given. The reason is that it is more difficult to estimate the transition model than the reward, and in the end, the part for reward estimation in regret is not the leading term. This can be seen in the main theorem presented in the paper. Therefore, it is questionable whether learning without information on reward can be said to be a special contribution.


questions: I would appreciate it if the author could tell me their opinion on the aformentioned 'Weakness' part.

Some more questions are as follows:

Line 93: I think $\theta$ denotes $(\theta^p, \theta^r)$. It would be better to mention that before referring to the optimal policy for clarity.

Line 191: For the $Q$ function that the agent calculates using the estimated parameter, if $Q^{\pi}_{\hat{\theta}^p, \tilde{\theta}^r, h}$ in line 191 is the same $Q\_{\tilde{\theta}, h}$ as the calculated in Algorithm 2, shouldn't it be correct that there should be no $\pi$ symbol in $Q$? Also, I think it should be fixed in the regret decomposition (eq. 10).

Line 230 (Stochastic optimism): I am a little confused because of the $\pi$ notation in the value function calculated with the estimated parameter (e.g., $V^{\pi}\_{\hat{\theta}^p, \tilde{\theta}^r, 1})$, but I am curious how the $Q^*_{\hat{\theta}^p, \tilde{\theta}^r, 1}$ appears in the first inequality. Also, I am not sure how the second inequality decomposes? 

Most of explanations were clear and well written, but with appearance of a lot of notations, it would be very helpful to understand this paper if the author mentions why the inequality holds in the appendix. 
limitations: I think there are no issues related to social impact. However, although this paper is highly related to theoretical part, considering that many recently published theoretical papers about model-based RL also present numerical experiments, I think it would be better if there was an experimental result in this paper.
review_title: null

Meta-review: metareview: The paper presents a tractable algorithm for bilinear exponential MDP with regret bound that improves from the best known result and achieves \sqft{d^3 HK} regret. The result appears to be correct with strong technical analysis. Reviewers and ACs appreciate merits of the analysis for this specific problem class.

However, both the reviewer team and the AC found that the authors miss to discuss several important and closely related works, such as Zanette et al, '19; Yang and Wang, '19 and a line of works on kernel RL and model-based RL with Eluder dimension analysis. In particular, Table 1 only compares the new result with several recent results on specific MDP models published after 2021, which is far from comprehensive. During the rebuttal, the authors acknowledged that they were not aware of these related works. However,  they didn’t revise the submission to include the missing discussions pointed by the reviewer. 

It remains unclear how the submission’s analysis relates to the aforementioned results that were not discussed in the paper. The authors provided some high-level discussion after rebuttal, but they would need a lot more technical details to be convincing. For example, regret analysis using Eluder dimension for general function class is often a go-to benchmark for non-linear models. The proposed model appears to be a generalized linear model, which is a standard special case of the Eluder dimension analysis. Then one would expect such analysis to lead to a O(d poly(H)\sqrt{T}) regret, (with \sqrt{d} coming from Eluder dimension and \sqrt{d} coming from metric dimension), better than result of this paper.  Note that this is just a conjecture, and rigorously working out this analysis would likely need extra work (nontrivial, as the authors pointed out). However, it is still not appropriate to overlook the possibility of using a more general analysis and just focus on a specific parametric model. A careful and honest discussion is necessary.

Beyond using Eluder dimension, there are actually a handful of RL theory papers on general function approximation and general model classes. We strongly recommend the authors to redo their paper survey and properly place their contribution in the context of state-of-art RL theory. We have reviewed a very competitive batch of RL papers this year. This submission has strengths but falls on the borderline. After consulting with the senior AC member who is also expert in RL theory, we regretful commend the authors further revise the paper and submit to the next venue. 
confidence: Less certain
Decision: Reject