Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors study conditions for achieving constant regret in RL with linear function approximation. They show that under a condition called UNISOFT, which says that features of state-actions pairs that can be reached by the optimal policy has the same span as features of state-action pairs that can be reached by any policy, constant regret is achievable if additional representational condition (completeness or linear MDP) holds. The authors also show that LSVI-LEADER (a modified version of LSVI-UCB), when given a set of N different representations, can adapt to the best representation automatically and achieve a regret bound that is upper bound by that of the best representation. Therefore, LSVI-LEADER achieves constant regret if any of the given representation satisfies UNISOFT. 
main_review: This paper studies conditions that permit constant regret in RL with linear function approximation. The UNISOFT condition is intuitive, and the authors prove that such a condition is necessary for achieving constant regret bound. Moreover, if additional representation conditions that permit sample-efficient RL with linear function approximation hold, UNISOFT is also sufficient for achieving constant regret. Therefore, the authors give an almost complete characterization of conditions that permit constant regret in the linear function approximation setting.

The authors then discuss how to select a representation that satisfies UNISOFT in linear MDPs. In particular, they propose an algorithm that receives M different representations as input and show that the regret of the algorithm is upper bounded by that of the best representation. Therefore, if any of the given M representation satisfies UNISOFT, the algorithm achieves constant regret. Algorithmically, the idea is to solve M different linear regression problems that share the same set of targets, and set the estimated Q value to be the smallest one among all the M predictions. The algorithm itself is a generalization of the one in Papini et al. which works in the bandit setting. However, it should be noted that the representation condition used here is rather strong: it requires the transition probabilities to be linear with respect to all the given M representations, which could be restrictive. 

In summer, this paper studies an interesting question. The authors give an almost complete characterization of conditions that permit constant regret in the linear function approximation setting. The authors also discuss how to automatically utilize a set of representation which potentially contains one representation that satisfies UNISOFT. This paper is also well written. Overall, this is a good paper and therefore I recommend acceptance.  
limitations_and_societal_impact: see main review.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper considers problem dependent bounds for finite horizon MDP. The problem dependent regret bound do not have a logarithmic term of time, which is the key innovation as compared to the prior works. 
main_review: The paper gives the first results where log(T) factor could be removed in problem dependent setup of MDPs. Even though the result is new, the usefulness of the result is unclear. Since there is already a \sqrt{T} term for the regret, saving O(\log T) has a negligible performance improvement in realistic setup. The paper also lacks any numerical result to explain the use of this result in practice. The key novelty in the proof also needs better explanation. 


limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper introduces the “UNISOFT” assumption which roughly states that the features for the state-action pairs visited by the optimal policy must span the entire feature space. A lower bound is given which shows that the assumption is necessary to achieve constant regret, and upper bounds are given which establish that the LSVI-UCB and ELEANOR algorithms achieve constant regret when UNISOFT holds (but also with a gap condition as well as their respective linear MDP and low IBE assumptions). The authors also analyze the representation selection problem (where a candidate set of features is given) and propose the LSVI-LEADER algorithm which has regret as small as that of the best feature, and in particular constant regret if any of those features is UNISOFT.
main_review: From a technical standpoint this seems like a strong paper with interesting technical contributions towards the problem of low-regret algorithms for linear function approximation (although under strong assumptions). For this reason I am recommending acceptance (albeit a weak one for now for reasons that I will be discussing shortly). 

The proofs are neat and mostly seem to check out, although I did not check them in great detail. I particularly enjoyed the lower bound (Theorem 5 and Lemma 7). I think the upper bound results would also be strengthened by emphasizing that, with UNISOFT, constant regret is achieved for any algorithm that falls under the very standard form of “optimism + elliptical confidence bounds”. 

There are a number of confusing or potentially concerning points, however. The main claim is that UNISOFT gives constant regret, but it is very unclear from the stated bounds (Theorems 8 and 9) how the regret is independent of K. In particular the bounds scale with \bar{\kappa} (defined in the text as “the last episode where ELEANOR suffers non-zero regret”), which I would be very surprised to learn is independent of K. In particular If ELEANOR suffered non-zero regret for a number of episodes independent of K then surely ELEANOR would also have constant regret? (e.g.  an easy bound would be Regret <= \bar{\kappa} * H). The text states “As expected, \bar{\kappa} is independent of the number of episodes K” as if it were evident, so it is possible that I am missing something obvious here. Either way, I think some clarification on the K-independence of this bound is in order. Examining the proof for this is not illuminating either — the K-independence comes from Eqn (3) of the sketch (or Eqn (28) of the full proof), and it is not clear how the authors arrive at these crucial inequalities (the <= \Delta_min bound). Can the authors elaborate on this? 

Another technical concern is about the lower bound. The text after Theorem 5 states that the class of MDPs given in the Theorem statement (i.e. with linear rewards and arbitrary dynamics) subsumes low-rank MDPs, linear-mixture MDPs, and MDPs with Bellman closure. The last of these claims is untrue — linear rewards alone do not guarantee Bellman closure as far as I can tell (due to the max over actions being inside the expectation, the update T(q) can not be written as a single linear function). If this is indeed not true then the lower bound does not actually show that UNISOFT is necessary for constant regret in Bellman-closed MDP-feature-map pairs, so the results are not as strong as they claim. On a related note: the Bellman optimality equation which is given in the Preliminaries section is incorrectly stated (!)

There are some writing concerns which I also think should be addressed. The intro sets up an unclear dichotomy between “good” representations and “learnable” representations. These terms aren’t defined very well (except circularly), and the rest of the paper uses this language in a technical sense (cf. Assumption 4). If we take the meaning expressed in Assumption 4 as the technical definition then it seems that learnable features are defined exactly as the features of Low-Rank MDPs or features with low Bellman Error, which seems like a restrictive definition for such a general idea. Furthermore, if a “good” representation is one that is realizable and a “learnable” definition is as above then one of these definitions is a strict subset of the other one. In summary I do not think this dichotomy adds anything and just confuses the narrative, and I would advise revising this section of the paper. On a more minor note, there is an inconsistency in the text about whether the term “linear MDP” is used (as in the title) or “low-rank MDP” (as in Assumption 2). I think the UNISOFT condition should also be loosely introduced in the setup of the paper, rather than saying “good” in the abstract.

Lastly, a question for the authors: why does unisoft need to assume a unique optimal action? Does this come into the proof somewhere?

limitations_and_societal_impact: As mentioned above: I think certain technical points should be clarified and/or corrected and the writing should be improved in several places.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies representation learning in reinforcement learning. The authors prove that the proposed UNI-SOFT assumption is sufficient and necessary for achieving the constant regret bound for a single representation. The authors also propose an algorithm to select the representation to achieve the constant regret bound when any single representation cannot achieve this.
main_review: The paper is overall well organized and easy to follow. Despite the aforementioned contributions, there're still several drawbacks in this paper. 

First, given the previous logarithmic regret bound given by [He et. al, 2020] and the constant regret bound for linear contextual bandit given by [Papini et. al, 2021], the constant regret bound for linear MDP is somewhat easy to obtain. In detail, as the authors show in line 153, the UNI-SOFT assumption is similar to the HLS condition in [Papini et. al, 2021]. They both show that the representation from the optimal action can provide rich information on the whole space of representation. Given this similarity, the proof of the constant regret bound is quite similar with [Papini et. al, 2021]

Second, regarding the representation selection part, the authors acknowledge in line 294 that there's a $\sqrt{N}$ inflation in the confidence radius $\beta$. However, this additional $\sqrt{N}$ is crucial for representation learning. According to [He et. al, 2020], this additional $\sqrt{N}$ factor will lead to an additional $N$ dependency on the final regret bound. This additional $N$ dependency will make the result infeasible when the representation candidate set is large.

Therefore, due to the drawbacks mentioned above, especially the crucial additional $N$ factor in regret bound for representation selection, I would like to suggest marginally reject this paper.

[1] Papini, Matteo, et al. "Leveraging good representations in linear contextual bandits." International Conference on Machine Learning. PMLR, 2021.

[2] He, Jiafan, Dongruo Zhou, and Quanquan Gu. "Logarithmic regret for reinforcement learning with linear function approximation." International Conference on Machine Learning. PMLR, 2021.
limitations_and_societal_impact: No negative societal impact of this work found. Here's my suggestions

It is still not clear to me how to verify the UNI-SOFT condition. It would help readers understand the performance of the representation learning algorithm by adding some experiments.
review_title: null

Meta-review: The paper studies "fine-grained" properties of linear representations in reinforcement learning, in particular when such a representation can admit constant regret guarantees, going beyond the worst case bounds of \sqrt{T}-type. The paper also consider a representation selection setting, where one representation among a class admits a constant-regret bound. 

The paper is a natural generalization of recent work on fine-grained representation properties in the linear bandits literature, but we believe it is a noteworthy contribution, so we are recommending that the paper is accepted to the conference. 

A couple of comments that I have for the final version:
- It is worthwhile to clarify the difference between the representation selection setting considered in this paper, and the ones in e.g., FLAMBE, MOFFLE, and the paper of Hao et al., on sparse linear RL. I feel the two settings are quite different, and it is worth clarifying this for readers and potential new contributors to the area. To me, the main differences are: in this paper all representations satisfy realizability/linear-MDP assumptions, so all of them can yield \sqrt{T}-type regret, while one can potentially yield a much better guarantee. In the aforementioned work, only one representation can even yield \sqrt{T}-type regret, while the others are essentially useless. In particular, the assumptions here are quite a bit stronger, but of course the result is also stronger. 
- On a technical level, it would be helpful to explain how the proofs here differ from the analogous results in linear bandits. What technical novelty should a reader expect here? 
- Lastly, please include any details from the discussion with the reviewers into the final manuscript. In particular the empirical evaluation would be nice to add. 
Decision: Accept (Poster)