Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers MDPs with linear transition models. Assuming access to a generative model, under certain anchor state assumption, the authors prove the following two results:

1. A model-based approach achieves a sample complexity of $O~(K / ((1 - \gamma)^3 \epsilon^2))$ which matches the minimax optimal lower bound up to logarithm factors; 
2. A model-free approach based on Q-learning achieves a sample complexity of  $O~(K / ((1 - \gamma)^3 \epsilon^2))$.
main_review: Understanding the tight sample complexity of RL with linear function approximation is an important problem in RL. This paper improves the state-of-the-art sample complexity for RL with linear function approximation assuming access to a generative model. The authors show that the sample complexity of a model-based approach matches the minimax optimal lower bound up to logarithm factors when $\epsilon$ is sufficiently small. The authors also improve the sample complexity of vanilla Q-learning in this setting. 

On the technical side, for the model-based result, the authors borrow the “leave-one-out” analysis developed by Agarwal et al. and generalize it to the linear function approximation setting. For the model-free result, the authors use Freeman's inequality to improve the concentration of the error term.

My major concern is Assumption 1 which is very strong. Although it has been adopted in the RL literature (the authors should consider citing [1] and [2] which also used this assumption) and could be crucial for obtaining tight bounds, the authors should at least discuss whether it is possible to weaken such an assumption. What happens if some $\lambda_i(s, a)$ can be negative but still has bounded absolute value? What happens if we instead assume $\sum \lambda_i(s, a) \le T$ for some $T > 0$? How should the sample complexity depend on $T$? Note that there always exists a set of anchor state-action pairs with $|\lambda_i(s, a)| \le 1$ for all $i \in [K]$ and $(s, a)$ which is implied by the existence of barycentric spanners [3]. This paper could be significantly stronger if such a discussion is available. 

Overall, this is an interesting paper, and the writing is easy to follow. However, the main assumption (assumption 1) seems pretty strong, and thus my recommendation is merely a weak acceptance. 


[1] Efficient Planning in Large MDPs with Weak Linear Function Approximation

[2] Limiting Extrapolation in Linear Approximate Value Iteration

[3] Online linear optimization and adaptive routing
limitations_and_societal_impact: See main review.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper considers reinforcement learning problem in infinite-horizon, discounted reward MDPs with a generative model. The authors aim to obtain upper bounds on the number of samples required to efficiently learn the optimal policy or the optimal $Q$-function when number of states and actions are very large. In order to achieve this, the authors impose generalization by considering transition probabilities to be linear in known state-action features (a.k.a. the linear MDP setting). The authors further assume access to a number of anchor state-action pairs, whose features (essentially) form a basis of the feature space. Under these assumptions on the MDP, the authors propose both model-based and model-free algorithm for learning the optimal policy (or $Q$-function), and analyze their sample complexity guarantees. The authors prove that the sample complexities of both the algorithms scale linearly with the dimension of the feature space (which is also equal to the number of anchor state-action pairs). The sample complexity bound of the model-based algorithm is the first of its kind for linear MDPs, and matches the minimax lower bound of Yang and Wang, 2019. The sample complexity bound of the model-free algorithm, though suboptimal, improves over the previously known bound of Yang and Wang, 2019.
main_review: The model based algorithm and its analysis is novel in the context of linear MDPs. The model-free algorithm, though known and analyzed before, obtains an improved sample complexity which is achieved through a novel application of Freedman inequality. However, I have not checked the correctness of the proofs in detail. The results are significant as long as sample complexity bounds in linear MDPS are concerned, but similar results already exist for tabular MDPs. This paper, though provide sample complexity bounds independent of number of state and actions, do not go beyond the tabular setting. The paper is well-written and the flow is clear.

I have one question for the authors. The dimension of the features and the number of anchor state-action pairs are assumed to be equal. What happens and how the results change is these are different?
limitations_and_societal_impact: This is a theoretical work, and hence possible implications on the society are not foreseeable.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper derives sample complexity for both model-based RL algorithms and model-free RL algorithm (i.e. $Q$-learning) in the case where the underlying MDP admits a linear structure. The resulting sample complexity bounds in both cases are shown to be tight. 
main_review: The linear parametrized MDP model, although was studied in related literature, seems to be relatively restrictive. It would be nice if such model is motivated by some real world applications.

The contributions of this paper are purely theoretical. The two major results are the sample complexity bounds for model-based and model-free RL algorithms. It seems that the approach for obtaining the sample complexity bound of model-based algorithm is similar to [2,5], and the approach for obtaining the sample complexity bound of model-free $Q$-learning is similar to [34]. It should be clearly stated what the technical challenges are in extending the results of [2,5,34] to the setting of this paper.

The $Q$-learning algorithm studied in this paper uses synchronous update, while practically $Q$-learning updates $Q_k$ in an asynchronous manner based a trajectory of samples obtained from a behavioral policy. 





limitations_and_societal_impact: No Societal Impact
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers reinforcement learning in infinite horizon discounted Markov decision processes with access to a generative model with linearly parameterized transitions.  At a high level, the authors consider an infinite horizon discounted Markov decision process with discount factor $\gamma$, finite state and action spaces, and known reward functions.  The high level goal is to query the transition kernel at various states in order to learn a policy $\pi$ mapping states $s$ to actions $a$ which maximizes the cumulative reward experienced across the trajectory.

It is widely known that learning in general depends on $|S| \times |A|$ which can be prohibitively large whenever $S$ or $A$ is large.  As such, the authors impose additional assumptions in the paper different from prior work with respect to the transition kernel (the only uncertainty present in the model) in order to avoid this worst-case scaling.  In particular, they assume that the algorithm designer has access to a feature function $\phi : S \times A \rightarrow R^K$ such that there are unknown functions $\psi_1, \ldots, \psi_k$ where $P(s' | s,a) = \sum_k \phi_k(s,a) \psi_k(s').$  This definition is the same structure imposed on the probability transition kernel in the linear MDP model (but doesn't also require that the reward function is a linear mapping of the features $\phi$).  This model encompasses tabular MDPs with no additional assumptions where $K$ can be taken to be $S \times A$.

In addition to the linear assumption, the authors assume access to a set of anchor state action pairs of size $K$.  With this assumption, they assume that the feature vectors can be expressed as a convex combination of the feature vectors of the anchor state action pairs (which additionally imposes that the transition kernel can be written as $P(s' | s,a) = \sum_i \lambda_i(s,a) P(s' | s_i, a_i))$ where $i$ indexes over the anchor state action pairs. The authors assume that the $\lambda$ function and the anchor pairs are known in advance to the algorithm designer.

This assumption differentiates the model from the typical infinite horizon discounted MDP to (hopefully) obtain improved regret guarantees.  In particular, the theoretical contributions for the authors follows via two separate strands.

First, the authors consider a model based reinforcement learning algorithm using the generative model.  In particular, their algorithm queries all of the anchor state-action pairs a given number of times to obtain independent samples from the transition $P( | s_i, a_i)$.  Using this, they can then construct an empirical transition kernel for all state action pairs using the linear combination arising from the anchor state action pair assumption.  With this estimate of the transition kernel, the authors can construct an empirical MDP where the true transition is replaced by its estimate (which can be done as the reward function is known), and use planning to find an optimal policy in this perturbed MDP.

Via this method the authors show that the sample complexity scales via $K / (1 - \gamma)^3 \epsilon^2$, which is minimax optimal up to logarithmic factors.

Second, the authors consider a model free reinforcement learning algorithm using the generative model.  This algorithm proceeds across time steps, where in each time step they sample a transition for each anchor state action pair, and update an estimate for the $Q$ function using the 'anchored' Bellman equations.

Via this method the authors show that the sample complexity scales via $K / (1 - \gamma)^4 \epsilon^2$, which is minimax optimal or 'sharp' under naive $Q$ learning based algorithms.

Lastly, the authors complement the theoretical results by a detailed discussion comparing the theoretical guarantees on the performance of their approaches to that in [61].
main_review: ### Originality:
The authors present an extension of existing model based and $Q$ learning based algorithms to the infinite horizon discounted MDP setting with linearly parameterized transition kernels.  While the algorithms presented are simple extensions of vanilla model based or $Q$ learning based algorithms, the authors express the necessary and straight-forward modifications to better exploit the linearly parameterized transitions in the algorithm design.  The proof techniques employed seemed like simple extensions of existing proof techniques, but see the questions section for more detailed comments.

### Quality:
The submission is technically sound and the theoretical claims are well supported.  The authors are honest and upfront on the new techniques used in both their proof and algorithm development.  However, there were certain additional assumptions required for the algorithm, namely:
- Known reward function
- Known feature representations $\phi$ and anchor states
which are never fully discussed or compared to the previous literature.

### Clarity:
The submission is clearly written and well organized.  However, with this there are a couple of confusing sections and theorem presentations:
- The title of the paper is misleading, as the authors do not consider the true 'linear MDP' model but instead 'linearly parameterized transitions'
- The sample complexity bounds for Theorem 1 are performance guarantees with respect to the $Q$ function of the learned policy.  However, the guarantees in Theorem 2 are just guarantees with respect to the estimated $Q$ function (independent of the performance of the greedy policy with respect to the estimated $Q$ function).  This is later discussed in the comments, but might be easier to understand if the theorems are in the same 'format'.  Also, upon checking the cited result to transform the bound, it does not provide performance guarantee of the greedy w/r/t $Q$ estimates in the true MDP as cited - unless I am misunderstanding the result.
- The key algorithmic differences between this paper and [61] are never fully discussed.
- Line 324 minor typo in 'employing more complicated analysis tool'.
- The relation to the other linear MDP models listed in line 286 is never fully discussed with respect to the different proof techniques and algorithmic tools needed.

### Significance:
The results in this paper improve the best known bounds for sample complexity guarantees with their model. While the novel techniques used are quite limited (just modifying existing generative model RL algorithms to exploit the anchor state representations), the work can be built upon by better understanding the required assumptions (finite state action space and known anchor state representation).

### Strengths:
The main strengths of the paper are as follows:
- The authors present minimax sample complexity bounds for the infinite horizon MDP setting with linear transitions and access to a generative model
- The paper is incredibly well written and easy to follow

### Weaknesses:
The main weaknesses of the paper are as follows:
- The novel contributions seem limited as the algorithms are straightforward extensions of existing generative model algorithms.  While it seems like the theoretical tools required are novel, these contributions were not fully highlighted in the paper.
- There are no concrete or realistic problem set-ups presented which satisfy the authors linearly parametrized MDP assumptions

### Questions and Comments:
- Line 118 - 121 was a nice point and helped highlight the improvements from the additional assumption.
- Line 134 - 137 was a useful discussion on the notion of anchor states.  However, the assumption that these are known as well as $\lambda(s,a)$ was never explicitly stated but required in the algorithms.  While it seems straightforward to learn the anchor state and $\lambda$ function just from the feature mapping $\phi$, this should be explicitly discussed in the paper.  Especially in the algorithm description you state the feature mapping $\phi$ only is needed (as in Algorithm 1).
- In Theorem 1, the notation $\epsilon_{opt}$ was introduced in the result but not in the theorem statement.  While there was a discussion after the theorem statement, this should be included in the formal theorem definition.
- Section on line 175 was a nice point to consider the computational complexity required.
- For the first point in section 5.  It seems a straightforward proof technique would be to show that the constructed estimated transition kernel approximates the true one up to some accuracy, and then use sensitivity of planning in the perturbed MDP with respect to the estimated transition kernel.  Did you try this approach and show that it leads to suboptimal guarantees?


EDIT: I'd like to thank the authors for their detailed comments for each of the concerns that they bring up, and I've updated my score accordingly.  The authors seem to have taken great care to improve the readability and clarity of the paper, especially addressing some of my earlier concerns with respect to constructing the set of anchor states from the feature representation $\phi$, and comparing some aspects of their proof techniques to other more 'naive' approaches to solving the problem.  All in all, my only concerns that remain are with respect to:
1. The usefulness of the model.  Even in responding to my comment the authors are unable to describe a concrete model where Assumption 1 is valid.  While it is still useful as a starting point for other theoretical analysis, having an example would help.
2. The strength of assumption 1.
limitations_and_societal_impact: The paper focuses on the theory of reinforcement learning, and so it is expected that it will not have any potential negative societal impacts.  The authors are also clear on the limitations of their work, including:
- Assumption that $S$ and $A$ are finite
- Accommodating a large range on $\epsilon$ for the sample complexity guarantees

In addition, there are two assumptions which are stated implicitly but the authors never explicitly discussed their importance:
- Known feature representation $\phi$ and anchor states
- Known reward function
review_title: null

Meta-review: The paper has initially received mixed reviews, with several reviewers taking issue with the strength of the assumptions. After reading the very detailed author response and some further discussion, two reviewers have decided to raise their scores, so eventually all scores ended up being positive. The reviewers agreed that the paper offers an interesting technical contribution clearly improving the previous state of the art, and that it is worthy of being published at the conference. Based on my own reading, I concur with this assessment and strongly recommend this paper for acceptance.
Decision: Accept (Poster)