Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: 

The paper studies RL in linear mixture MDP with unknown transition, adversarial loss, and bandit feedback. This paper gives the first algorithm in this setting whose regret scales with sqrt(#episode) and supplements a lower bound, which matches the upper bound for the $d$ and $K$ dependency, where $K$ is #epsiode and $d$ is the ambient dimension of the linear mixture MDP. 
strength_and_weaknesses: 
### Strength

1. This paper studies a reasonable setting of "adversarial" RL with linear function approximation, and designs and proves the first algorithm with sqrt(K) regret. 
2. This paper goes beyond the classical VTR (value-targeted regression) framework of analysis for linear mixture MDP, coming up with a novel technique (imaginary roll out of state) to cope the challenge arouse in adversarial setting.

### Weakness

1. There are many settings of linear RL theory besides linear mixture MDP, such as linear MDP. Also, recently, there are unified framework such as Bellman-rank and bilinear classes for RL with general function approximation. In particular, these frameworks include linear mixture MDP as their special cases. While the theory of RL with function approximation is certainly an important topic, it could become much less important when the scope is restricted to linear mixture MDP.
2. This paper does not prove tight lower bound to complete the theoretical research in their setting.

clarity,_quality,_novelty_and_reproducibility: 
The writing is clear and of good quality. No apparent typos are noticed.
summary_of_the_review: 
This paper contains some novel results and techniques, but it could be made better if the authors could come up with more complete results.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper considers the adversarial linear adversarial MDP and proposes the first efficient algorithm that achieves $\sqrt{K}$ bound. Moreover, they also give a lower bound. Their techniques are based on the occupancy measurements which is initially proposed by Jin et al. (2020b). Compared to previous techniques, this paper adopts some nontrivial extensions, the main one, as stated in the paper, is the use of a carefully chosen " imaginary next state", which solves the dependence between the actual next states and thus allows the usage of regular linear regression to estimate the $\theta$
strength_and_weaknesses: Strength: The results are significant. The techniques seem novel to me -- (1) the use of " imaginary next state" is novel (2) the further improvement on H, S compared to Jin et al. (2020b) seems also interesting (but it is not very clearly stated)

Weakness: Some of the technique contributions are not clearly stated in the paper.
clarity,_quality,_novelty_and_reproducibility: The paper is overall well-written and easy to read. But as I mentioned above, I feel there are some technical novelties that are not clearly explained in the main paper. Specifically,

1\ When talking about how to choose the next state in Eqn.(2), the author also mentioned: " for some technical reasons". But from my perspective it is not that trivial, my understanding is that it is like some "implicit exploration", choosing to maximize the most uncertain states? I would like to see a little more discussion on that.

2\ In remark 2, you said that "it is not a straightforward extension, even given the transition estimator obtained using the imaginary next-states." So my understanding is that, besides the imaginary next-states techniques, there are some other techniques that help you to further shave the dependency. I would like to see some discussion in the main paper.

3\ I personally think section 4.2 can be more concise since it basically gives a summary of the existing standard techniques.



summary_of_the_review: Overall I think it has good results and relatively novel techniques. But the explanation of some techniques seems not very clear to me. So I give 6 and would like to raise my score if I can better understand the novelty of the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies adversarial linear mixture MDPs with unknown transition and bandit feedback. The authors propose an algorithm with an upper bound $\tilde{O}(dS^2 \sqrt{K} + \sqrt{HSAK})$, and prove an almost near-matching lower bound (in $d, K, A$). The authors highlight the use of a novel occupancy measure difference lemma for linear mixture MDPs, which might be of independent interest.
strength_and_weaknesses: Strengths:

(+) The upper bound is accompanied by a near-matching lower bound. The authors also justify the dependence on $S$ and $A$ via the lower bound.

(+) The use of a novel occupancy measure difference lemma (Appendix B.1).

Weaknesses:

(-) The bound depends on $S$, which is unusual and undesirable given the linear mixture MDPs assumption.

(-) The writing can be improved, especially the main results.

Detailed comments:

- I am familiar with statistical RL theory, but not so much in the adversarial setting. Hence, I will comment more on the writing/correctness aspects of the paper rather than the novelty/contribution.

- (main concern) Since the upper bound in Theorem 1 has a dependence on both $S$ and $A$, would this be just the tabular setting? I don’t quite understand where the linear approximation comes in when we still have the dependence on $S$.

- I encourage the authors to make it more explicit which elements are novel, particularly in your algorithm design. For example, how does your proposed algorithm differ from Jin et al. (2020b)?

- The main results (Theorem 1 and 2) should be made more detailed and self-contained. I encourage the authors to at least briefly introduce the settings and various relevant notations in the Theorems.

- The lower bound contains a term $dH\sqrt{K}$, which is linear in the horizon $H$. However, the upper bound only has a $\sqrt{H}$ dependence. Would this lead to a contradiction, or am I missing something here?
clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is generally well-written and easy to follow. The literature review and comparison with existing works are sufficient.

Novelty: The analysis in the paper is sufficiently novel. The analysis utilizes a novel occupancy measure difference (Lemma 2), which is a non-trivial extension from Jin et al. (2020b). Although the tightness of Lemma 2 is unknown, it may be of independent interest and useful for the community.  

Summary Of The Review: The paper studies adversarially linear mixture MDPs. The main results are interesting with a relatively novel analysis. However, the implications of the main results are unclear: what did we gain from the linear MDPs assumptions if the upper bound still depends on $S$?

summary_of_the_review: The paper studies adversarially linear mixture MDPs. The main results are interesting with a relatively novel analysis. However, there is little innovation in the algorithm design, and the implications of the main results are unclear: what did we gain from the linear MDPs assumptions if the upper bound still depends on $S$?
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies inhomogeneous adversarial linear mixture MDPs. It presents an efficient algorithm called LSUOB-REPS which provably achieves $\tilde{\mathcal{O}}(d S^2 \sqrt{K} + \sqrt{HSAK})$. The algorithm relies on occupancy measure based techniques, which maintains a confidence set of the unknown transition function and runs online mirror descent over the space of occupancy measures. One novelty is the construction of a specific linear regression objective function to solve for the transition parameter. To this end, this paper proposes to use an imaginary next state to construct the regression target. Furthermore, a lower bound of order $\Omega(dH\sqrt{K} + \sqrt{HSAK})$ is proven, which shows that the algorithm has close-to-optimal performance. 
strength_and_weaknesses: Strength:

1. This paper gives the first answer to a quite challenging problem, i.e., the adversarial linear MDPs. Both an upper bound and a lower bound (under certain assumptions) are given.

2. The paper is very well-written. This is a very technical paper. Techniques are presented with rather detailed explanations, making it easier for the readers to follow.

3. The paper has some novelty. The technical challenges are also discussed quite thoroughly, showing the technical contributions of the paper clear. For example, the imaginary next-state seems like a quite interesting idea to deal with the challenge of constructing a confidence ellipsoid when the classical self-normalized concentration technique cannot be directly applied. 

---
Weakness: 

There is no major weakness as far as I can tell. There are some comments though. 
1. The dependence of the upper bound on $|S|$ is unpleasant under the linear mixture MDP setting. 

2. The paper lacks a very detailed comparison with [1]. Although it seems that [1] studies tabular MDPs which is different from linear mixture MDP, the major idea of algorithmic design is very similar. Furthermore, in the case of representing a tabular MDP by a linear mixture MDP, we would have a relation $d = |S|^2 |A|$. In this case the bound in this paper would actually be worse than that of $1$ (but I can understand this since representing a tabular MDP by a linear mixture is inefficient. Still a more detailed comparison would be good to have).

3. There is no discussion on computational efficiency of the algorithm, so it might be inappropriate to call the algorithm ‘efficient’.    

[1] Jin, Chi, et al. "Learning adversarial markov decision processes with bandit feedback and unknown transition." International Conference on Machine Learning. PMLR, 2020.
clarity,_quality,_novelty_and_reproducibility: Clarity: This paper is clear in general.Theorems have no ambiguity to me. Technical challenges and the corresponding solutions are described clearly. Related work is also discussed properly with now ambiguity. 


Quality: The quality is good. This is a purely theoretical paper and the theorems are solid. The proof feels correct to me, though I did not check all the details. 

Novelty: The paper is novel. The technical contributions, e.g. how to construct the confidence set of the transition parameter in the adversarial setting; how to choose the imaginary next state; are all good ideas in my opinion.


Reproducibility: This is purely theoretical work with no empirical result. The proof looks reproducible to me as it is written clearly and not very hard to read.  

summary_of_the_review: My current recommendation is accept. 

The reasons are the following:

1. Solid contribution: this paper gives the answer to a quite challenging and important field of reinforcement learning theory. 

2. Some novelty: to solve certain technical challenges, some novel ideas have been proposed.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper studies adversarial linear mixture MDPs with unknown transition and bandit feedback. The authors propose an algorithm with an upper bound of \tilde{O}(dS^s \sqrt{K} + \sqrt{HSAK}) where S is the size of the statespace, A the size of the action space, H the episode length and K the number of epsisodes. The algorithm is efficient (though a slightly restricted setting is considered by necessity) and there is a lower bound that matches in some factors. Some techniques in the paper might be of independent interest and although there are a lot of open problems remaining, the papers makes sufficient contributions to merit acceptance.
justification_for_why_not_higher_score: Borderline, but reasonably good.
justification_for_why_not_lower_score: Paper makes positive contribution.
Decision: Accept: poster