Offline Reinforcement Learning (RL) aims to learn a near-optimal policy from a fixed dataset of transitions collected by another policy. This problem has attracted a lot of attention recently, but most existing methods with strong theoretical guarantees are restricted to finite-horizon or tabular settings. In constrast, few algorithms for infinite-horizon settings with function approximation and minimal assumptions on the dataset are both sample and computationally efficient. Another gap in the current literature is the lack of theoretical analysis for the average-reward setting, which is more challenging than the discounted setting. In this paper, we address both of these issues by proposing a primal-dual optimization method based on the linear programming formulation of RL. Our key contribution is a new reparametrization that allows us to derive low-variance gradient estimators that can be used in a stochastic optimization scheme using only samples from the behavior policy. Our method finds an $\varepsilon$-optimal policy with $O(\varepsilon^{-4})$ samples, improving on the previous $O(\varepsilon^{-5})$, while being computationally efficient for infinite-horizon discounted and average-reward MDPs with realizable linear function approximation and partial coverage. Moreover, to the best of our knowledge, this is the first theoretical result for average-reward offline RL.
Paper
Similar papers
Peer review
Summary
This paper studied offline RL in linear MDP setting, where the transition and reward have low-rank structures and the feature $\phi$ is known. The authors formulated the problem in a primal-dual way and proposed a gradient-based algorithm. They provided convergence guarantees, which only requires coverage over optimal policy.
Strengths
The paper writing is clear and easy to follow. The discussion and comparison with previous works is very detailed. The algorithm is computationally efficient. The algorithm design has some interesting points, especially the reparameterization design to avoid knowlegde of $\Lambda^{-1}$ and updates for variables $v$ and $u$. The coverage assumption seems weaker than previous literatures.
Weaknesses
I didn't see too much technical novelty in the method and proof. The setting is linear MDP, which is kind of restrictive. Convergance rate is kind of far away from optimal.
Questions
Given the knowledge of $\Lambda$, why not consider the reparameterization $\beta = \lambda$, i.e., set $c=0$, but consider $c=1/2$? It seems to me the RHS of Eq. in Line 141 can be estimated unbiasedly? Line 154 claimed that $c = 1/2$ results in a tighter bound, however, according to Theorem 3.2, and Corollary 3.3, the larger $c$ is, the lower dependence on $d$ the sample complexity will have. So how the "tighter bound" is reflected? It seems contradictory.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
N.A.
Summary
This paper proposed an primal-dual framework for offline reinforcement learning in linear MDP Contrary to the more common case of finite horizon, they considered the case of infinite horizon with discounted reward. They reduced the problem of offline reinforcement learning to a problem about solving the saddle-point of a Lagrange form. They designed an algorithm which uses stochastic gradient-based optimization to solve the saddle point. They provide a sample complexity of O(\eps^-4) for both cases of discounted MDP and averaged-reward MDP, and their algorithm is also computational efficient. To summarize, the formulation of offline RL into a linear programming problem is very interesting. The proof seems very solid, and I like the comparison for the concentrability constant in the last discussion section. The comparison for the constant C is thorough and very good. However, I still have some questions about some details in the main text.
Strengths
1. The formulation of offline reinforcement learning to a linear programming problem is very good. 2. The algorithm is clearly motivated by solving the saddle points of a Lagrange form. The algorithm itself is simple and computationally efficient, with a guaranteed sample complexity for both discounted MDP and averaged-reward MDP. 3. They proposed a new concentrability constant C and compare it to other constants appearing in other literatures about offline RL. I think the understanding of the relationship of these concentrability constant is basically correct and very clearly expressed. 4. The proof seems very solid and the result in averaged-reward case is new.
Weaknesses
1. I have some question about your comparison to previous results. Your main references are Cheng et al and Xie et al. 1.1 For Xie et al, the Theorem 3.2 in https://proceedings.neurips.cc/paper_files/paper/2021/file/34f98c7c5d7063181da890ea8d25265a-Paper.pdf implies that their sample complexity is O(1/\eps^2) when applied in linear function approximation. This result is based on assumption3 in their paper. This assumption naturally holds in your paper since you consider linear MDP and they consider the case of 'linear function approximation' (for their difference, see point 2). So it is natural for you to compare your sample complexity to this result, not the O(1/\eps^5) one. [notice that, their algorithm in section 3 is computationally inefficient] 1.2 In Theorem 4.1 in Xie's paper, their sample complexity is O(1/\eps^5) when applied on general function approximation, and O(1/\eps^3) when reduced to linear function approximation case (see paragraph 'Dependence oon T'). Again, their assumption for linear function approximation holds in your case. **This algorithm, however, is computationally efficient.** So you should also compare with this alg with O(1/\eps^3) sample complexity. 1.3 In Cheng's paper, in theorem 5, their sample complexity seems to be O(1/\eps^3), not O(1/\eps^5). I wonder how you derive their sample complexity in Table one. 1.4 I am not sure how you get the O(n^{7/5}) computational complexity for Xie's paper. Could you derive it in more detail? 2. I think in many places in your paper, you confuse the two terms: linear MDP and linear function approximation. Your case is called linear MDP instead of linear function approximation, so I suggest you changing the wrong terms. For reference, both Xie's paper and Cheng's paper consider the 'linear function approximation' case.
Questions
1. In Line 82 and 87, there are typos in the definition of rho and state occupancy measure? There should be a power of gamma in the sum? 2. In line 174-176, you calculate the computational complexity of your algorithm. Can you show this in more detail? I am not sure why each gradient update needs a constant number of elementary vector operation. What is your definition for elementary vector operation? 3. In section 3 and 4, you use c \in {1/2, 1} to state all your results. I wonder whether c can only take these two values? If so, then why cannot c take other values (for example, 2 or 3 or 1/4)? If not, then how will the algorithm behave and how will the sample complexity be when we take c to be other values? If c can take multiple values besides 1/2 and 1, how can you tune c to get the best performance? 4. In theorem 3.2, the sample complexity depend on constant c by D_\phi^{8c} * d^{-2c}, right? Does the constant hidden by the big O depend on c or nor? If not, then suppose D_\phi^{8} / d^2 < 1, if we take c to be large or even converge to the infinify, then the term inside the big O will approach zero. How can that happen? (Let's suppose D)\beta is a constant and does not depend on c). For example, in the most common setting, c = 1 and d > 1, then when we take c \to \infty, the term in the bracket wiil be zero. If the term hidden by the big O depends on constant c, then you should point it out in the paper. 5. In Line 198, you say D_\beta = c * C for some positive universal constant c. Is this c multiplied before the concentrabilty coefficient the same as that c in definition 3.1? If not, then you should use another notation. 6. In line 315, you claim C_{\phi,1} = 1 + chi-square divergence. However, C_{\phi,1} is \sum (\mu^*)^2 / (\mu_B)^2 and the chi-square divergence should be \sum (\mu^*)^2 / (\mu_B), right? So they should not be equal. For the definition of chi-square divergence, see https://en.wikipedia.org/wiki/F-divergence. 7. In line 77, you claim the state space is finite but potentially very large; but in Line 338, you claim that 'not to assume the state space to be finite'. From the proof, I think the latter one is correct, and the first one is just for deriving some equations like equation 1 and 2. So I think you should write somewhere in section 3 that you relax this setting of finite state space and the derivation there also holds for infinite state space but finite action space.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
3 good
Contribution
3 good
Limitations
/
Summary
This paper studies offline reinforcement learning (RL) with linear function approximation and partial data coverage. The authors propose a primal-dual optimization method based on the linear programming (LP) formulation of RL. They prove a $O(\epsilon^{-4})$ sample complexity in both discounted setting and average-reward setting.
Strengths
1. The algorithm proposed in this paper only requires near-minimal dataset coverage assumption, which is important in offline RL. 2. The paper also considers average-reward offline RL, which is often neglected by literature. 3. I like the table for comparison to previous work, which makes the presentation more clear (although I think there is some missing important literature, which I will mention in the weakness section). 4. The proposed algorithm is both computationally and sample efficient.
Weaknesses
1. The first concern is the ‘linear function approximation’ setting, which is restricted. Actually, the main motivation that this paper studies function approximation beyond tabular settings is large state (or action) spaces in practice. However, in real settings, the linear function approximation assumption hardly ever holds. Even in Table 1, many algorithms in previous work apply to general function approximation, which further makes the setting studied in this paper restricted. 2. Algorithm 1 in this paper achieves a $O(\epsilon^{-4})$ sample complexity. This is in terms of expectation (as shown in Theorem 3.2) instead of high probability. The previous results that the authors are comparing to are high probability bound (e.g., [1,2]), so it would be more comparable if the authors could also show a $O(\epsilon^{-4})$ sample complexity bound under high probability. Also, since the previous work studies general function approximation while this paper studies only linear function approximation, it is hard to say that a $O(\epsilon^{-4})$ sample complexity bound in linear function approximation setting is better than a $O(\epsilon^{-5})$ bound in general function approximation setting. Moreover, [3] achieves the near-optimal sample complexity $O(\epsilon^{-2})$ with near-identical settings of [1,2]. (So I disagree with the statement that ‘It is very important to notice that no practical algorithm for this setting so far, including ours, can match the minimax optimal sample complexity rate of $O(\epsilon^{-2})$’. Therefore, a $O(\epsilon^{-4})$ in linear function approximation is not that attractive compared to previous work. 3. The authors use an LP formulation of offline RL. I think it would be better to compare to other work using LP formulation, e.g. [4,5], where [4] is computational and sample efficient under partial data coverage and general function approximation, and [5] achieves near-optimal sample complexity under similar settings. 4. The authors compare the computational complexity. However, it is not that direct to compare an $O(n)$ complexity in linear settings to a $O(n^{7/5})$ complexity in general settings. If the authors really want to demonstrate that their algorithm has better computational complexity, it would be better to do some simulations in the same environment (even in some toy examples). 5. Another advantage that the authors claim is that their algorithm could be adapted to average-reward setting. However, neither did the authors emphasize and explain the importance and challenges of average-reward settings, nor discuss why (or whether) previous work could not be adapted to average-reward settings. I suggest the authors discuss this a bit more. **References** [1] Xie, T., Cheng, C. A., Jiang, N., Mineiro, P., & Agarwal, A. (2021). Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34, 6683-6694. [2] Cheng, C. A., Xie, T., Jiang, N., & Agarwal, A. (2022, June). Adversarially trained actor critic for offline reinforcement learning. In International Conference on Machine Learning (pp. 3852-3878). PMLR. [3] Zhu, H., Rashidinejad, P., & Jiao, J. (2023). Importance Weighted Actor-Critic for Optimal Conservative Offline Reinforcement Learning. arXiv preprint arXiv:2301.12714. [4] Zhan, W., Huang, B., Huang, A., Jiang, N., & Lee, J. (2022, June). Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory (pp. 2730-2775). PMLR. [5] Rashidinejad, P., Zhu, H., Yang, K., Russell, S., & Jiao, J. (2022). Optimal conservative offline rl with general function approximation via augmented lagrangian. arXiv preprint arXiv:2211.00716.
Questions
1. Would it be easy to convert the result from the expectation form to the high-probability version? 2. Is it easy to modify previous algorithms for the average-reward settings? If not, what is the difficulty?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
N/A
Summary
This paper studies offline reinforcement learning with linear function approximation. They propose a primal-dual algorithm, formulating linear RL into a minimax problem and solving it with gradient descent-ascent. Sample complexity analysis is provided for infinite-horizon discounted and average-reward MDPs, where the rate is $O(\frac{1}{\epsilon^4})$ for both settings.
Strengths
1. The algorithm is primal-dual and thus easy to implement in practice. 2. The paper provides rigid theoretical analysis.
Weaknesses
1. The newly defined coverage ratio $C_{\phi,c}$ is a little strange when $c\neq \frac{1}{2}$. For example, when we choose $c=1$ and thus we don't need the knowledge of $\Lambda$, the coverage ratio $C_{\phi,1}=\sum_{x,a}(\frac{\mu^*(x,a)}{\mu_B(x,a)})^2$. Then when $\mu^*=\mu_B$, $C_{\phi,1}$ will become $|X||A|$. However, in the literature, when the behavior policy is the same as the optimal policy, the coverage is typically 1. The authors claim that we can estimate the $\Lambda$ via the offline dataset so that we can choose $c=\frac{1}{2}$, but do not provide any theoretical analysis about this point. I will be more convinced if the authors can give more rigid proofs for this method. 2. The sample complexity is worse than the typical rate $\frac{1}{\epsilon^2}$.
Questions
None.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
None.
Summary
This paper considers the problem of offline reinforcement learning (RL) for linear Markov Decision Processes (MDPs) under the infinite-horizon discounted and average-reward settings. The authors propose a primal-dual optimization method based on the linear programming formulation of RL, which allows for efficient learning of near-optimal policies from a fixed dataset of transitions under partial coverage. The proposed algorithms improve the sample complexity compared to previous methods from $O(\epsilon^{-5})$ to $O(\epsilon^{-4})$ under the discounted setting and provide the first line of result in the average-reward setting with realizable linear function approximation and partial coverage.
Strengths
1 The proposed algorithm improves existing algorithms in both statistical efficiency and computational efficiency under the discounted reward setting with the linear function approximation (we note the baseline may handle problems beyond the linear MDPs). 2 The algorithms presented in this paper do not explicitly leverage the principle of pessimism, but focus on the linear programming formulation of MDP, and rely on a new reparametrization trick extended from the tabular case. The technique itself seems to be novel to me. 3 The algorithms present the first line of work for the offline average-reward MDP. 4 The paper is easy to follow, with a thorough comparison with existing work that clearly positions the results in the literature.
Weaknesses
1 I am confused about the requirement of $\Lambda$ to be invertible (line 140) as this seems to be very closely related to the uniform coverage condition where we assume that the smallest eigenvalue of $\Lambda$ is lower bounded from zero. I am wondering what is the key difference between them. Can you elaborate on this with some intuitions or examples? 2 The authors discuss the relationship between the coverage condition considered in this paper and that of [1] and show that the coverage condition is a low-variance version of the standard feature coverage ratio if $c=1/2$. However, in this case, the algorithm explicitly uses $\Lambda$, while the PEVI proposed in [1] does not. In contrast, $c=1$ leads to a worse bound but we do not need the knowledge of $\Lambda$. Could you provide a more detailed characterization or example to illustrate the difference between these two cases? typo: line 328, $\epsilon^2 \to \epsilon^{-2}$ [1] is pessimism provably efficient for offline rl
Questions
see weakness
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
4 excellent
Contribution
3 good
Limitations
yes
Summary
The authors investigate offline RL in linear MDPs and introduce a novel LP-based method. They assert that their proposed approach achieves the lowest sample complexity of $O(1/\epsilon^4)$ among computationally efficient algorithms. In comparison, existing computationally efficient algorithms can achieve $O(1/\epsilon^5)$. Additionally, the author's theory can be extended to the average reward setting.
Strengths
* To the best of the author’s knowledge, in offline linear MDPs, the result in the average-reward setting is novel. * The LP formulation in linear MDPs is worthwhile to investigate
Weaknesses
* I am uncertain about whether it is appropriate to claim that existing offline RL algorithms in linear MDPs achieve $O(1/\epsilon^5)$. It appears that [38] may have better sample complexity. In Table 1 of the manuscript, the author mentions that [38] cannot handle the discounted setting. However, extending from the finite-horizon to the discounted infinite-horizon setting is relatively straightforward. Hence, this comparison may not be entirely fair. If [38] indeed has better sample complexity, it significantly impacts the author's contribution. Thus, I currently rate the paper with a score of 4. * I am not entirely certain about the significance of the extension to the average reward case. * Presently, I cannot determine whether the reason [9] and [36] cannot handle the average reward case is due to the algorithms or their analysis. If this limitation arises from their analysis, their algorithm has the potential to be superior as it can handle more general MDPs.
Questions
Could you provide further elaboration on my concerns regarding (1) the comparison between the author's work and [38], and (2) the third point in the weakness section?
Rating
4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
2 fair
Limitations
They discussed.
Acknowledged
Thanks for the response. I think my questions are addressed and I will take the response into consideration in the final decision period.
Thank you for your comprehensive responses. I still have some uncertainty regarding the statement regarding [38], "which is only feasible in the finite horizon setting." It appears to me that an analogous approach could be applicable to the infinite horizon discounted setting as well. I will maintain my current evaluation score and ask Area Chair to check this point. While I am retaining my score presently, I am open to raising the score later if I am incorrect.
Thank you for the response, and for being open to raise your score. Your initial question prompted us to reason on how to extend the cited work to our setting. However, we were not able to prove a *straightforward* reduction (see below for details). For this reason, we suspect that if such a trivial reduction were possible, it would have been mentioned directly by the authors. The central part of the algorithm of Zanette et al (Algorithm 1) is the critic procedure `PLSPE` (shown in Algorithm 2), which is invoked at each iteration $t$ of the main loop. This procedure aims to solve a convex problem (Eq. 10a to 10c) which requires optimizing variables of size $dH$ and has a number of constraints proportional to $H$. Thus, it is impossible to run this procedure "as is" in the setting we consider, because in our case $H=\infty$. One idea could be to try to replace $H$ with the effective-horizon $1/(1-\gamma)$. This might be a good approach, but it is not immediately clear if it would work, and it also presents some downsides. For example, it would result in a non-stationary policy, which in practice is something very unappealing (i.e., imagine having to store 99 neural networks as opposed to 1). Moreover, the effective-horizon is just the average length of an "episode", and it would be unclear which policy to use when the interaction lasts longer than $1/(1-\gamma)$. Even addressing all of these concerns, it remains questionable if their algorithm would give us any advantage in terms of computational efficiency, since it requires computing a quantity proportional to $(d|A|n)$ at each iteration, where $n$ is the size of the dataset (see Eq. 10b). Obviously, this does not imply that extending the work of Zanette et al to the infinite-horizon setting is impossible. In fact we are confident that by substantially changing their method it must be possible. For this reason, if you have some specific approach in mind, we encourage you to share it with us, so that we can discuss it together. As an alternative approach, one could also try to completely replace the critic procedure of Zanette et al with something specifically designed for the infinite-horizon setting. In our opinion, this could result in something similar to PSPI (see Algorithm 1 of [Xie et al][1]), which uses a pessimistic policy evaluation procedure, which can be efficiently implemented with a least-squares based approach. However, the resulting method does not attain the optimal sample complexity either. Please refer to our answer to reviewer 7fb2 for a more detailed comparison of our method and PSPI. We hope to have helped addressing your uncertainty, and remain available for further questions. [1]: https://arxiv.org/pdf/2106.06926.pdf
Comparison to related work
Dear authors, I see several reviewers point out concerns related to comparison to related works and also see your responses. We will have to gather everyone's opinion later after they have a chance of reading your rebuttal and each other's review, but just a very quick point regarding your comment: > the concrete implementation of their algorithm in Appendix D does not match the specifications needed in the analysis (e.g., it uses an unbounded function class which prevents using a covering-number argument in the general analysis) You are right the analysis is incomplete, but I think the computational efficiency is still quite obvious? The objective is just maximizing quadratic function with PSD Hessian (_edit:_ up to a minus sign) thus minimizing a convex function. You are totally right that they use an unbounded function class in the computational argument --- but adding (say) a norm constraint on the parameter is quite straightforward? Detailed computational complexity may be difficult to obtain, but broadly speaking I believe polynomial complexity will hold without issues. So at least it should be an entry in your table with very strong sample complexity whereas the detailed computational complexity is less clear (but polynomial).
Thank you for the comment. We find your observation totally reasonable. We will make it more clear in the text and the table, that PSPI, when reduced to the linear MDP setting, achieves $O(\varepsilon^{-3})$ and has polynomial computational complexity.
Thanks. Just saw your updated table. Related to the above discussion, I'd suggest maybe put "oracle/convex opt" for PSPI in the computational column.
Thank you for the suggestion. We will incorporate it into the final draft.
Thanks for the response! I don't think sacrificing the coverage ratio for avoiding estimating $\Lambda$ is a good idea since the authors have proposed a feasible method to estimate $\Lambda$, especially when the coverage ratio could be inflated many times potentially. I still recommend the authors to conduct a thorough analysis for the estimation process since the setting is different from the previous works after all and I will maintain my scores for now.
Thank you for the feedback! We remain at disposal for further questions, and are hopeful you will take into consideration our general rebuttal as well, in your final evaluation.
Quick comment on your last point about coverage ratio: I think more and more people in the community are realizing that this is indeed the right def for linear MDPs, that you only need to cover one direction. See page 10 of https://arxiv.org/pdf/2203.05804.pdf, which has a closely related discussion, and a twitter thread https://twitter.com/nanjiang_cs/status/1666994607073230848.
Thank you for the pointers!
thanks for the response
Thanks for the clarification. I would keep my score toward acceptance.
Thank the authors for the response as well as the attached table. However, I still have some concerns regarding the contribution of this work. For the attached table, the sample complexity of ALMIS should be $O(1/\epsilon^2)$ instead of $O(1/\epsilon^3)$. Is this a typo or am I missing something? Also, the authors added a column denoting whether the algorithm is oracle-based. However, all algorithms dealing with general function approximation need an optimization oracle (otherwise, all they can do is enumerate all functions in the function class since it is a general function class without any additional assumptions). Therefore, it is unfair (or unnecessary) to discuss whether it is oracle-based when comparing linear function approximation to general function approximation. I agree with the author that the sample complexity should not be the only dimension to compare different algorithms. However, according to the table, it seems the only dimension among multiple ones that the proposed algorithm beats other ones is whether it can be extended to the average reward case. However, considering restrictions in other dimensions (linear MDP, suboptimal sample complexity, no empirical evaluation), it remains unclear whether the current algorithm contributes enough to the community. The authors also mentioned that their bound reflects the correct comparator-dependent quantity, which I agree with. From my understanding, this quantity corresponds to the partial data coverage assumption, which only requires that the offline dataset covers the optimal policy (or the target policy). However, many recent works also assume partial data coverage, so they all use the correct notion. Given that, the coverage notion does not seem to be a significant advantage over previous works. Overall, I appreciate the point of average reward setting and the new method to formulate linear MDP. However, it still has many restrictions. I believe it would be great work if (some of) these restrictions could be addressed. For the current state of the paper, I slightly lean towards rejection and would keep my score.
> many recent works also assume partial data coverage, so they all use the correct notion Well not quite. If you read the discussion in Section 6, there are multiple notions of partial coverage (in the sense that we only need to cover the optimal policy or whichever policy we want to compare to) in linear MDPs that are different from each other (in the sense that what counts as "covering a policy" has multiple definitions), and the one in this paper (for the $c=1/2$ result) is arguably the "most correct" one. Not many papers in the literature use this one. This is also discussed in https://arxiv.org/pdf/2203.05804.pdf and a twitter discussion (https://twitter.com/nanjiang_cs/status/1666994607073230848) which I mentioned in another thread. That said, the reason that some prior works didn't use this "most correct" notion is sometimes because people didn't realize these different versions and simply went with what previous people did, and in some cases it is relatively easy to adapt the analysis to obtain the better notion of coverage, so the overall situation is a bit chaotic...
Thanks for your clarification. Now I understand the meaning of the 'correct' notion. In that case, I would be happy to raise my score to 5. I want to clarify that the reason I raised my score is not that I think the proposed algorithm is comparable (in sample complexity or empirical performance) to some previous algorithms, especially in general value function approximation; the reason I think this work is valuable is due to the new method formulating linear MDP and this tight coverage notion appears in the sample complexity bound, which could inspire other works in both linear and general function approximation to rethink about the choice of coverage notion and thus design more practical algorithms.
Thank you for the feedback, and for raising your evaluation of our work. Please see further clarification on your comments below. Yes, the sample complexity of ALMIS is $O(\epsilon^{-2})$ not $O(\epsilon^{-3})$. Thank you for bringing this to our attention. We will update our table accordingly. Regarding your comment on our table, you do make a fair point. However, our focus in the paper is on linear function approximation; a special case of general function approximation. For this reason, we believe that excluding algorithms that were developed for general function approximation would unfair. That said, we would like to emphasize that, the fact that oracle access is common in works focused on general function approximation is of little interest for our comparison. Rather, what we care about is whether these methods are efficient once they are applied to the linear case. When this is not the case, or is not clear from the papers, such methods were categorized as "oracle-based". This does not imply that these methods cannot be made efficient with some work, but that's beyond our scope. We are happy that you agree that sample complexity should not be the only dimension to compare different algorithms. We also appreciate your acknowledgement of our achievement in offline learning in the average reward setting. However, we think our contribution goes beyond tackling the average reward setting. To this end, and, with regards to our concrete contributions to the RL community, please refer to our response to your previous comments as well as paragraph 4 of our general response. Once again, thank you for acknowledging our efforts and reconsidering your evaluation of our work. We also appreciate you drawing our attention to the limitations, because, like with every research area, these will make a great foundation for future work.
Thank the authors for further clarification. Given your explanation of "oracle-based", I think this makes sense to me now. I would recommend authors make it more clear in the revision. Also, I think it would be better to add a column indicating whether the algorithms use the correct (or tight) choice of coverage notion when specializing in linear settings since it is one of the main contributions of this paper. When an algorithm uses a better notion of coverage, even though the sample complexity in terms of $n$ is slightly worse, it would still be valuable and could inspire future work to design algorithms with better coverage notion and better dependence in $n$.
Thank you for the discussion, and recommendations! We are glad that we could help provide some clarity. Please let us know if you have further questions.
Thanks the authors for your reply! Given your clarification on the related work, I will raise my score to six.
Decision
Reject