Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: This paper proposes an RL algorithm to learn a policy in a constrained setting without violating the safety constraints.
It relies on an initial baseline policy to collect data for the first episodes.
Eventually, it switches to a policy optimistic with respect to the transition function and reward.
To ensure the new policy is safe the paper proposes to penalize the cost function inversely to the number of times, being pessimistic with respect to the cost function.

The paper provides regret bounds for the main objective tighter than the bounds from previous algorithms that also do not violate the safety constraints (OptPess-LP).
strengths_and_weaknesses: 
### strengths

- The main novelty of the proposed algorithm compared to the previous OptPess-LP is to be optimistic with respect to the transition function in addition to optimism with respect to the reward. To compensate for the double optimism the paper also proposes a new penalty for the cost function, increasing the pessimism with respect to the cost.
- The significance of the paper seems limited to showing that the algorithm proposed has smaller regret compared to the OptPess-LP algorithm.

### weaknesses

- The empirical results could be improved considerably. Although the paper describes the AlwaysSafe-$\pi_\alpha$ algorithm, it tests the AlwaysSafe-$\pi_T$ algorithm. In [34], it is already shown that the $\pi_T$ variant can be overly conservative, it may even fail to converge to the optimal policy. An appropriate comparison should use the $\pi_\alpha$ algorithm, which can converge to the optimal policy.
- The clarity of the paper could be improved, for instance, by clarifying the connections between the different theoretical claims in Section 4.

### minor comments

- line 100: peratins -> pertains
- line 210: something is strange with "less observed less"


### references

[34] Thiago D Simão, Nils Jansen, and Matthijs TJ Spaan. AlwaysSafe: Reinforcement learning without safety constraint violations during training. 2021.
questions: 
1. The current definition of regret is related to a weak measure as described in [17], which allows for "error cancellations". Considering Proposition 5, which states the policy applied in each episode is safe with high-probability, can we conclude the bound on the safety regret of DOPE is a strong measure?

2. How DOPE behaves in the Factored CMDP given a baseline with cost bound $\bar{C}_b = 0$?

3. Empirically, it seems the effect of the baseline policy in the regret seems to be contradictory to what would be expected from the regret bounds. That is, lower values of $\bar{C}_b$ would lead to lower regrets. Could you comment on this phenomenon?

### references

[17] Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitation in constrained MDPs. arXiv preprint arXiv:2003.02189, 2020.
limitations: 
Yes, the paper makes clear statements regarding the assumptions required for the proposed algorithm, namely, access to a safe initial baseline policy.
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 authors propose a safe exploration algorithm that relies on the idea of both optimism and pessimism under uncertainty. The problem is formulated as a constrained MDP that is solved using a Linear Programming approach which iteratively approximates the transition model and the optimal policy, the cost, and constraints for each state-action pair.
In order to ensure that the policy is safe through this approximation, an additional term is added to the constraint objectives (pessimism) and the cost objective is relaxed with additional terms (optimism) which ensures the exploration of under-explored states. These terms are O(1/n(s,a)) and can cause the initial problem to be infeasible. Therefore,
the algorithm relies on an initial safe exploration policy that ensures that constraints are not violated. The authors demonstrate that under certain conditions, constraints are satisfied with high probability in the original problem i.e. under the true transition model. The result is an algorithm that has 0 constraint regret and that, compared to SOTA, reduces the objective regret
by a factor of O^{\tilde}(\sqrt(|S|)) where |S| is the size of the state space.
strengths_and_weaknesses: Strengths:

An algorithm that combines both advantages of pessimism and optimism approaches to safety yielding 0 constraints regret and a reduced objective regret by a factor of O^{\tilde}(\sqrt(|S|))
An analysis of the algorithm which clarifies the motivation behind the algorithm
Empirical results that demonstrate the superiority of the algorithm over SOTA
Weaknesses:

The algorithm relies on the assumption that we have an initial safe exploration policy which ensures that the constraints are always satisfied.
questions: Line 179: Shouldn't there be a summation over the timestep h? or it should be the number of times the pair (s,a) has been observed at timestep h before the beginning of episode k
Line 188: The summation should be until k-1 and r_{h} should be replaced by r_{h, k^{\prime}} I suppose
Line 189: What is r^{\tilde} in terms of (r^{\tilde}_{h})
limitations: The algorithm is limited to tabular settings but this is something that the authors have already pointed out.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: Existing safe reinforcement learning (RL) algorithms are basically optimistic w.r.t. reward (via exploration bonus) and pessimistic w.r.t. constraints. Such algorithms are excessively pessimistic; thus, empirical performance is bad due to a long learning process. The authors present Doubly Optimistic and Pessimistic
Exploration (DOPE) algorithm for safe RL, which is doubly optimistic w.r.t. reward and model while being pessimistic w.r.t safety. The authors theoretically analyze the objective regret and constraint violation, which is better than OptPessLP algorithm. Finally, they empirically show that DOPE performs better than baselines in multiple benchmark tasks.
strengths_and_weaknesses: I think this paper is a solid paper, which will potentially contribute to the future safe RL researches.

[Strength]
- This paper is well-organized and easy to follow.
- Theoretical results are good. Especially, it is an important result that objective regret is less than OptPess-LP while constraint regret is zero.
- Empirical experiments. I deeply appreciate that the authors conducted experiments in three tasks. As the authors argue, many safe RL algorithms do not perform well in empirical experiments in spite of its beautiful theoretical properties. I personally think that DOPE algorithm is impressive in that it is backed by theory and practice.

[Weakness]
- (Note that I think this is a minor weakness) Benchmark tasks are still easy and simple.
- Source code is messy. I would like the authors to refactor it before open-sourcing it. 

questions: [Q1] Can the authors provide me with an intuitive explanation of which of the innovations in this paper led to the reduction of objective regret? I think I understand the DOPE algorithm and followed the proof, but I do not fully understand why the DOPE algorithm can achieve smaller regret.
limitations: Limitations and potential negative societal impact have been fully addressed in lines 351-355 and lines 487-500, respectively.
review_title: null

Meta-review: metareview: I went through the paper, reviews and responses. This is a borderline paper with reasonable theoretical analysis but weak experimental results. Lack of comparisons to practical safe RL algorithms is not an advantage.
I tend to accept. I'm also ok with a borderline reject.
confidence: Less certain
Decision: Accept