Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper studies linear MDP with possibly adversarial rewards. The authors propose a detection-based algorithm that can simultaneously learn stochastic and adversarial linear MDP. Assuming a known probability transition, it is shown that the proposed algorithm can achieve logarithmic regret in the stochastic case and sublinear regret in the adversarial case.
strength_and_weaknesses: Strength:

- The authors have done a good job reviewing the related literature.
- This paper studies an interesting problem of simultaneously learning stochastic and adversarial linear MDP, and the result presents a best-of-both-worlds guarantee.
- The theoretical analysis provides a high-probability regret guarantee for adversarial linear MDP.

Weaknesses:

- Given the existing literature on RL with function approximation, I believe the setting of linear MDP is already well-motivated. So for the introduction, the authors should discuss more the motivation of best-of-both-world type algorithm and, more importantly, explain the challenges in the algorithm design and theoretical analysis, compared with existing results.
- Following the previous point, please explain the technical challenges induced by the setting of linear MDP and the novelty of the proposed method.
- The description of the proposed algorithm in Section 4 is a bit difficult to follow. I would suggest the authors put more effort into reorganizing this section for readability. More specifically, Algorithm 4 seems to be an important subroutine, but it is not clearly explained what this algorithm is doing and why we need it. The description on page 5 could be more carefully structured using some highlighted words/sentences. Also, please provide references to existing related methods in other settings and compare them.
- It seems crucial to assume a finite policy set. Why is this a reasonable assumption for linear MDP? For example, consider the LSVI-UCB algorithm where the policy is given by the greedy policy w.r.t. the estimated Q-function, and in this case, the policy set is infinite. Even if using a covering argument for the policy set, it would introduce additional dependence on the dimension. Please justify this assumption and discuss its limitation in detail.
clarity,_quality,_novelty_and_reproducibility: This work is original, extending previous works on best-of-both-worlds results for bandits and tabular MDP to the setting of linear MDP. For novelty, the authors should discuss the unique challenges in the setting of linear MDP and the corresponding solutions. For clarity and quality, I suggest revising the algorithm section for better readability. Also, the authors should explicitly and clearly specify the assumptions for each lemma and theorem.
summary_of_the_review: I think this paper studies a meaningful setting and the results are solid. But the overall writing can be further improved, and see detailed comments above. I didn't carefully check the proof in the appendix.

Besides, I have a few more questions as follows:

- In the definition of the Q-function, normally people would include the reward received at the current step, i.e., $r_{k,h}(s,a)$
- The loops in Algorithm 1 and 2 are a bit weird. Should provide a stopping criterion, otherwise it's not clear when the algorithm ends.
- If assuming a known transition, do we still need to require the transition probability to be linear? I think without the linear assumption on the probability transition, the value function can still be written as a summation of inner products between the expected feature vectors and the parameters of the rewards.



---
Other minor problems:

- Near the bottom of page 5, should be 'standard least square estimators'
- Under Algorithm 3, should be 'fool the algorithm'
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The submission studies the BoBW problem under a new setting. The submission proposes and analyzes the first BoBW algorithm for linear MDP with high-probability regret bounds (Algorithm 1). A secondary result is the first algorithm achieving a high-probability regret for the adversarial liner MDP (Algorithm 4).
strength_and_weaknesses: - (a) The submission develops a new component (Algorithm 4 and Theorem 1) for the main algorithm.
- (b) What prevents the authors from directly analyzing the regret under the general function approximation setting?  
- (c) The submission did a great job explaining the roles and jobs of the components of the main algorithm. The proof sketch is also easy to follow. It would be better if there were discussions about why other works fail, and how this work succeeds would better justify the technical contributions of this submission.
- (d) What prevents the authors from removing the known transition assumption? Why can't we leverage existing works on unknown transitions?
- (e) The paragraph above Section 5.1 discusses a way to handle the case when $\Pi$ is infinitely large (which is why function approximation was developed to replace the tabular methods). However, simply combining $Reg(K)$ with (14) and (15), the $|\pi|$ term is still there in the bound. Is there any misunderstanding?

clarity,_quality,_novelty_and_reproducibility: Clarity
- (f) A comprehensive review of BoBW under various settings (bandits versus MDPs and tabular versus function approximation).

Novelty
- (g) A nice observation that leverages the property of linear approximation to convert the problem to an online linear optimization problem.

summary_of_the_review: The submission has substantial contributions to the BoBW problem. However, if allowing $|\Pi|$ to be infinity is the distinctive advantage of function approximation, the concern (e) raised above should be resolved. Therefore, I would like to recommend weak acceptance in the current stage.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: The authors tackle the setting of linear MDPs with known transition but unknown reward that achieves $\text{polylog}(K)$ regret over $K$ episodes when the rewards are stochastic, and $\tilde O(\sqrt{K})$ regret when the rewards are adversarial. 
strength_and_weaknesses: The authors tackle an interesting problem and derive a new algorithm that achieves a "best-of-both-worlds" guarantee. The paper is clearly written, and the problem tackled is interesting. However, I do have some technical concerns.

1. I would like some elaboration on the covering approach used to move from finite hypothesis class $\Pi$ to infinite hypothesis class. Let's say, for example, that I want my hypothesis class to be the set of policies $\pi_h(s) = \text{argmax}_a \langle \phi(s, a), w_h) \rangle$ for some weights $w_h$---that is, $W = (w_1, \dots, w_H) \in \mathbb{R}^{d \times H}$ parameterizes my Q estimates. Naively, I would try to $\epsilon$-cover the space of all such $W$ by considering discretizations of (say) $[0, 1]^{d\times H}$ to precision $\epsilon$. We would thus have $|\Pi| = (1/\epsilon)^{dH}$. 

    **a)** This would lose factors of $\sqrt{dH}$ and $dH$ in the adversarial and stochastic regret bounds respectively. I feel like that means it is worth making explicit in the paper--it *does* "influence the main order of the regret".

    **b)** If we use such a cover by exponentially many functions, is the algorithm stated in the paper efficient? Many steps in the algorithm seem to involve enumerating policies $\pi\in\Pi$, which would take exponential time.

1. The factor $\Delta_\min$ used in this paper seems quite unusually small. For example, Jin & Luo (2020) are able to achieve a bound in the tabular setting with $\Delta_\min := \min_{h, (s, a):a \ne \pi^*(s)} V^*_h(s) -  Q_h^*(s, a)$ (which is larger, at least if the hypothesis class $\Pi$ consists of all deterministic policies). Is it possible for this paper to match that $\Delta_\min$?

1. The algorithm seems broadly extremely similar to Lee et al (2021)'s algorithm for the (non-MDP) bandit setting, applied to the set of arms $\mathcal{X} = \\{ \phi_{\pi, \cdot} : \pi \in \Pi \\}$. What, if any, is the difference here? 

More generally, it does not seem as though this paper is really using any feature of MDPs--instead, it seems that it is directly applying a non-MDP result to the MDP setting and simply ignoring most of the structure of the MDP. As a result, the main theorems of this paper do not look like what I would typically expect MDP results to look like--for example, I would expect MDP results to have dependencies on "local" properties such as the larger $\Delta_\min$ (see point 2 above) and "local" hypothesis classes, rather than the "global" $\Delta_\min$ and "global" policies $\pi \in \Pi$. 

Minor detail: at various points throughout the paper, $O(\sqrt{K})$ should be $\widetilde O(\sqrt{K})$ since the adversarial regret has $\log K$ dependencies.
clarity,_quality,_novelty_and_reproducibility: I am not particularly well-read on this particular line of work, and am taking the authors at their word that this problem has not been tackled in the past. The problem tackled in the paper is quite natural to state, and seems to be of obvious interest in this area. However, as discussed above, I am concerned that the results of the paper seem to **a)** follow pretty immediately from previous results in the non-MDP bandit setting, namely those of Lee et al (2021) and **b)** not really use anything particular about MDPs. As such, I am not sold on the novelty of this paper's approach, or results, compared to Lee et al (2021).

The paper is clearly written, and there are no reproducibility concerns--there are no experiments (the paper is completely theoretical), and all proofs are in the appendix.
summary_of_the_review: A theoretical paper that tackles an interesting and clearly important problem. However, I am not convinced that it tackles the problem sufficiently to distinguish itself from past works. I am willing to consider raising my score if the reviewers provide a response that alleviates my concerns.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes an algorithm for linear MDP with the known transition, which can simultaneously achieve O(polylog⁡K) regret in the stochastic reward setting and O(\sqrt{K}) regret in the adversarial reward setting.

Strengths:

+ The first RL algorithm with linear function approximation that works for both stochastic reward and adversarial reward under known transition.

Weaknesses:

- The finite policy set assumption is very strong.

- Under the known transition assumption, the contributions of this work given prior work in BoBW linear bandits seems incremental.

Even after author response, this paper does not gather sufficient support from the reviewers. Thus I recommend rejection. 
justification_for_why_not_higher_score: The reviewers found that the finite policy set assumption is too strong.
Decision: Reject