Low-Switching Primal-Dual Algorithms for Safe Reinforcement Learning

To me, this work presents several weaknesses, which are highlighted in the following:

1. First, the paper focuses on a specific setting only, that is, online learning in CMDPs where a strictly feasible solution is known to the learner. In real-world scenarios, it is, in general, not the case that a known safe policy is known, nor the associated cost. Thus, papers in this field usually provide additional (and more general) analysis for the case a strictly safe policy is not known (see [Liu et al., 2021] and [Stradi et al. 2024]).

2. While it is interesting that the algorithm achieves a better dependence on state and horizon in the regret bound, it happens at the cost of paying some violations. Furthermore, notice that the violations definition proposed in the paper is weak, since it allows for cancellations during the episodes. To me, assuming the knowledge of a strictly feasible solution should be enough to guarantee the safety property at each episode.

3. The algorithmic ideas seem not particularly novel. The primal-dual setting employed in the work is well-studied in literature, and the same reasoning holds for the optimistic rewards/costs functions (e.g., [Efroni et al. 2020]). Bernstein-style bonuses are generally used for transitions estimations in online MDPs [Jin et al. 2020].

To summarize, the $\sqrt{SH}$ improvement in the regret bound appears to me not enough given the aforementioned limitations. Overall, since this is mainly a theory paper, I believe the contribution is too poor to reach the acceptance threshold for a top conference such as ICLR.

[Liu et al., 2021] "Learning policies with zero or bounded constraint violation for constrained mdps."

[Stradi et al. 2024] "Learning Adversarial MDPs with Stochastic Hard Constraints"

[Efroni et al. 2020] "Exploration-exploitation in constrained mdps"

[Jin et al. 2020] "Learning Adversarial Markov Decision Processes with Bandit Feedback and Unknown Transition"

1. Even if a detailed comparison of the result is provided, it is unclear in the paper how the author achieves this improvement technically. From my perspective, the improvement arises from the selection of the empirical CMDP. In fact, the definition of the empirical CMDP is different from the previous work, since it uses the optimism principle and compensates the underestimation of the cumulative cost by subtracting the safety threshold $\tau$ by some gap $\Delta_k$. Do I understand correctly? Additional clarification about (a) the motivation for selecting this gap and (b) what's the advantage of this gap technically would enhance the paper.

2. Compared to the previous work with known $\pi^0$ and $c^0$ in Table 1, their algorithms can lead to zero violation with higher regret in theory, so the contribution of this paper mainly focuses on reducing the regret result. Is this true in the experiment? The paper could benefit from containing some empirical results to show the advantage. I understand that for a theory paper, the most important contribution is the theoretical insight, but it is also important to conduct a simple empirical validation of the insight. An empirical simulation and comparison of previous work are enough. I would like to increase my score if the authors provide some empirical results.

3. Many RL problems contain a large or even continuous state space. Can this algorithm be extended to the continuous setting such as linear MDP? If it's not, what are the primary challenges?

-Both approach (i.e., low switching) and analysis are heavily based on the reference Zhang et al. (2024). This casts doubts on how much original novelty comes from this paper.

1. Low-switching appears to be one of the central focuses of the paper; however, I noticed a lack of analysis or formal guarantees supporting the claimed benefits of low-switching. It would be beneficial for the authors to clarify how low-switching is quantified and its impact on the model. For example, could the authors provide a quantitative measure of policy switching frequency in SLIM?

2. The rationale behind how low-switching leads to improved dependency in the regret bound is unclear. A more thorough explanation or intuition on why reduced switching would contribute to lower regret could strengthen the understanding of the proposed approach. For example, could you provide a step-by-step explanation or an illustrative example of how reduced switching translates to improved regret bounds?

3. When comparing the proposed regret results with existing methods, the contribution seems somewhat limited. The differences in assumptions and constraint violation conditions make it challenging to directly assess the relative significance of the improvements, as they may not hold under comparable settings.