Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper deals with providing an algorithmic scheme which is provable efficient for Model-free RL in a setting where there are additional constraints on the learned policy in the sense that it also needs to ensure that the expected utility is above a given threshold. The paper also claims that their algorithm does not require an explicit simulator or oracle to run trajectories for a given policy for some number of rounds (as is usually the case with many existing RL methods). They further provide, regret guarantees for their algorithm and compare it with the existing approaches to show their usefulness and superiority.
strengths_and_weaknesses: + Paper is technically solid.
+ The theoretical results appear to be sound and useful
+ The problem attacked is well-motivated

The main weakness of the paper according to me is readability.
- It might help to organize the outline of the proof in a more structured way by giving (sub-)headings for each the various parts, for easy parsing.

questions: 1) Each episode starts with a state drawn from a fixed distribution -- Seems to require a reset at the start of every episode? This seems to contradict the claim that their scheme is simulator-free. Am I missing something?
2) Since I am not very well versed with this topic, can the authors provide some insight on Assumption 2? 
limitations: The authors have clearly stated the limitations of their work and the areas of future directions.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: The paper studies episodic constrained MDP problems. The authors propose a model-free value-based RL algorithm with linear function approximation and establish sublinear regret and violation. 
strengths_and_weaknesses: ## Originality

- The proposed primal-dual algorithm is new and it works for constrained MDPs with linear function approximation, which is an important constrained RL setting. 

- The proof has some novel ingredients, e.g., uniform concentration of value functions.

## Quality & Clarity

- The paper is well written and all claims are justified via proofs. The authors also discussed improvements and limitations in the end of the paper. 

## Significance

- The proposed primal-dual algorithm is based LSVI-UCB while taking account for constraints in the linear function approximation setting. This is a new advance in learning constrained MDPs with large state spaces.

- The analysis generalizes the uniform concentration bound in LSVI-UCB to the constrained case using an intermediate softmax policy update.

- This regret and violation bounds are near-optimal. They improve the dependence on $H$ compared with the existing methods, while $d$-dependence is slightly worse.
questions: - What is $\xi$ in your analysis? Any dependence on $H$?

- It is useful to discuss some work in linear setting: A Simple Reward-free Approach to Constrained Reinforcement Learning

- The proof outline is helpful, but it is useful to highlight the new key techniques. If I set $Y=0$, would this become the standard LSVI-UCB and analysis carries over? 

limitations: Yes.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper studied the episodic CMDPs with linear function approximation and proposed the LSVI-UCB based algorithm which can achieve $O(\sqrt{T})$ regret and $O(\sqrt{T})$ constraint violation bounds.  The author also showed that zero constraint violation is achievable for a large $T.$
strengths_and_weaknesses: **Strengths**
1. The paper is well-written and well-organized.
2. The paper proposes a model-free, simulator-free reinforcement learning algorithm for CMDPs with linear function approximation that can achieve $\sqrt{T}$ regret and zero constraint violation.
3. The paper proves that zero constraint violation is possible when $T$ is sufficiently large.

**Weaknesses**
1. The memory complexity is high, since the algorithm needs to store all the historical states and actions.
questions: 1. This paper indicates that their algorithm is model-free in the sense that the algorithm does not need to estimate the transition kernels. My concerns come from the comparison between this paper and [7]. Although Linear MDP and linear kernel MDP have different assumptions on the model, your algorithms both need to solve a LSTD problem at each episode. [7] needs to estimate the transition kernel in the tabular setting because of the assumption from the linear kernel assumption. I am wondering if your algorithm needs to estimate the transition kernels in the tabular setting?
2. The LSTD-based algorithms are well studied in both bandit and RL settings. Can the authors clarify what the novel technical contributions of this paper are?
limitations: I don't think this paper has any potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers the episodic, model-free, simulator-free, constrained Markov Decision Process (CMDP) framework with a linear function approximator. 
The main contribution is the primal-dual algorithm that is based on the LSVI-UCB algorithm. The paper also provides the regret and constraint violations' bounds that do not depend on the state space cardinality. Instead, the bounds depend on on the dimension of feature mapping $d$. In addition, the presented algorithm can achieve a zero constraints' violation given a sufficiently large number of episodes $K$ as proven in theorem 3.
The paper also compares the presented algorithm with other algorithms that consider the model-free CMDP case, and mentions the shortcomings of them (e.g. their need for a simulator, being model-based).
strengths_and_weaknesses: **Strengths:**

The primal-dual extension to the LSVI-UCB algorithm is non-trivial and is a good contribution to the CMDP literature. The author(s) also clearly presented how their algorithm differentiates from other model-free or tabular algorithms as shown in table 1. The constraints' violations was also shown to go to zero asymptotically w.r.t. the number of episodes. 

In addition, theorem 3 (and its proof in the appendix) is a nice addition to the finite-time regret\constraint violation analysis. I read the proofs provided in the appendix, and to the best of my knowledge they appear to be correct in their analysis. 


**Weaknesses:**
The paper's biggest weakness is its lack of experimental evaluation of the proposed algorithm to support the theoretical bounds. Some of the cited work (Triple-Q algorithm) do present results for the tabular and function approximation cases. 

In addition, the Triple-Q algorithm (cited as [13] inn the paper) was also extended to the neural networks' function approximation case. This raises the point if the proposed primal-dual algorithm should be extended to other function approximators (possibly radial-basis function and not neural networks). The claim on lines 86 and 87 is hence inaccurate since other work can already handle continuous state spaces. 

Minor comments I have:

Line 45 *value function or a policy*: value function of a policy.

Line 87 *regret bound shown in the above paper*: it's better if the author(s) cites the paper again to avoid confusion. 

The Gram matrix $\Lambda_h^k$ is first mentioned on line 196 but it's referenced earlier in Algorithm 1 and its description. The symbol definition should be introduced earlier in the paper.

Line 354: *Whether we can the tighten the*: Whether we can tighten the.

Line 514 *we, now, recursively*: we now, recursively. 


--------------------------------------
### After rebuttal:

I read the responses by the author(s) and also the revised manuscript. I am pleased to see that the author(s) implemented an experiment in less than a week. I also find their response regarding picking a good feature set $\phi(s,a)$ sufficient.

I increased my score from 6 to 7.


questions: **Question 1:** With linear function approximators, finding a good performing set of features significantly affects the approximations' accuracy. Can the author(s) discuss how a set of features $\phi(s,a)$ can be chosen for a linear approximator?

I am willing to increase my score if the author(s) address the weaknesses I mentioned as well as the question I have here.
limitations: **Limitations:** work only considers a linear function approximator. It would be nice to expand this approach to a quadratic function approximator or a kernel-basis functions. The author(s) also mention the possibility of finding tighter bounds given *d* and *H*, and I am pleased that they addressed this bound gap.


**Societal impact:** Not applicable to this work.
review_title: null

Meta-review: metareview: This paper considers minimizing the regret while learning a near-optimal policy in an episodic constrained MDP with linear function approximation. It proposes and analyzes a UCB-based algorithm proving sublinear regret. 

The reviewers found the paper well-motivated and technically sound, and unanimously recommend acceptance. Please incorporate the reviewers' feedback in the final version of the paper. In order to strengthen the final paper, it would be helpful to:
- Incorporate toy experiments and empirically validate some of the paper's claims
- Include a discussion about the tightness of the upper bound
confidence: Certain
Decision: Accept