Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper investigates bandits and reinforcement learning problems under the conservative setting where it is required that with high probability, the performance of the proposed policy is comparable to that of a baseline policy $\pi_0$. An efficient framework LCBCE together with a lower bound are proposed which are able to be used to tackle the multi-armed bandit, linear bandit, tabular MDP and even low-rank MDP problems. 
main_review: Strengths
* The proposed algorithm LCBCE is a general framework which could be used to tackle many bandit and RL problems
* For some of the problems (multi-armed bandits, linear bandits and tabular MDPs), a nearly optimal upper bound is obtained.
* The paper is written well and the ideas are easy to understand.

Weaknesses
* Although the proposed framework seems very general, the main ideas of the paper come from the existing literatures. In the beginning, the authors propose a simple policy called Budget-Exploration which performs the baseline policy first to ensure that there is enough budget and then conducts the non-conservative policy for the remaining episodes of the game assuming that the gap between the optimal policy and the baseline policy ($\Delta_0$) is known. A similar idea is already proposed in the BudgetFirst policy in Wu et al., 2016. Later, the authors extend the idea to the case when $\Delta_0$ is unknown where they build an online estimate on the lower bound performance of the policy, which also shares a similar idea with Conservative UCB proposed in Wu et al., 2016. I find it difficult to believe the impact is significant except that the authors deploy the idea under a general problem setting.
* No experiments are conducted to illustrate the empirical performance of the proposed algorithm.
summary_of_the_review: Although the authors propose a general framework to deal with multi-armed bandits and RL problems, it seems to me that the work is an extension of the existing work i.e., Wu et al., 2016 to a more general problem setting.  If I read the paper correctly, I did not see any new techniques developed to tackle this more general problem setting. 

Detailed comments:

__Before section 2__, ... All these works focused on provide an upper-bound to the regret of a conservative algorithm...: provide -> providing

__Notations__, ...there exists a constant $c$ such that $A \geq (\leq) cB$... : constant -> positive constant

__After Assumption 1__, ... there exists $\theta^{\pi} \in \mathbb{R}^d$ such that $Q_h^{\pi}(s, a) = \langle \phi(s, a), \theta^{\pi}_h \rangle. $: $\theta^{\pi}$ -> $\theta^{\pi}_h$
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies bandits and RL settings subject to a conservative constraint where the agent has to perform at least as well as a given baseline policy. It improves the existing lower bound for conservative MAB, and as the main contribution, obtains new lower bounds for conservative linear bandits, tabular RL and low-rank MDP. It also provides new upper bounds matching existing ones with different analyses.
main_review: The paper is well-written in general and the contributions and the model are well-motivated. Numerical experiments that corroborate the theoretical guarantees of the paper are missing in the current version and I highly recommend to add some in the revision since the theoretical guarantees and algorithms seem to be incremental compared to the existing works.

Could the authors provide a convincing argument about the non-incremental nature of the novelty.
summary_of_the_review: The problem studied in this paper is interesting and I think it would interest the ICLR community. While the theoretical derivations heavily reliy on Kazerouni et al 2017 and Wu et al. 2016, the theoretical results are interesting. I have not checked all the proofs, but they seem sound and correct.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a reduction-based framework for a large class of reinforcement learning algorithms, including bandits, linear bandits, tabular MDP and linear MDP.
The authors notably propose a generic lower bound that holds for all the studied class of algorithms. The lower bound is built on the regret decomposition between the regret of the conservative baseline during the time when the budget is not reached, and the regret of a non-conservative algorithm that learns on the baseline. While the obtained lower in the bandit setting is not as tight as the one obtained in (Wu et al, 2016), this lower bound holds for a larger class of algorithms.
Then, two generic algorithms are proposed for handling conservative reinforcement learning. Budget-Exploration consists in learning the non-conservative algorithm on the conservative baseline during a fixed period of time and then to play the non-conservative algorithm. The regret upper bound of Budget-Exploration matches the lower bound, but the knowledge of the baseline gap is need.
The second algorithm LCBCE does not necessitate that the baseline gap be known. The idea of the algorithm is to compute an upper bound of the budget thanks to the lower bounds of rewards obtained by the non-conservative algorithm run on the baseline. The regret upper bound of LCBCE still matches the proposed lower bound.

main_review: This paper is well written. The studied problem is significant. The generality of the results are impressive.

While the reviewer tends to accept the paper, the reviewers has some concerns.

1/ No assumption is made on the baseline \pi_0. However, Budget-Exploration plays \pi_0 during a first period of time. What does happen if \pi_0 plays only one sub-optimal arm? How can learn the non-conservative baseline ?

2/ The proposed lower bound is not as tight the one in (Wu et al 2016): the right term is greater in (Wu et al 2016). However, Theorem 3 states that the regret upper bound of LCBCE reaches the proposed lower bound. Hence it violates the lower stated in (Wu et al 2016). Could you comment? (The reviewer does not understand the comment below Corollary 1).

3/ The reviewer thinks that the comment on the comparison with (Wu et al 2016) above section 1.3 is not supported by the facts. In particular the reviewer does not get the sentence “our algorithm calculates how much budget the algorithm needs in advance, and therefore has a tighter regret bound”. First it only concerns Budget-Exploration. Second generally an algorithm that uses the seen data is better than an algorithm that does not use them.


AFTER REBUTTAL
The authors have answered my concerns. I vote for acceptance.
summary_of_the_review: While the reviewer tends to accept the paper, the reviewers has some concerns.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies online sequential decision making under a conservative constraint, i.e., the agent needs to perform at least as well as some baseline policy. The authors present algorithms based on a reduction from non-conservative MAB/linear bandits/tabular MDPs/linear MDPs, and prove minimax optimal (or near-optimal) upper and lower bounds on the regret.
main_review: **strengths:**
1. The paper is clearly written and easy to follow.
2. The budget approach is simple and intuitive.
3. The regret upper bounds are optimal (near-optimal for linear MDPs but this is the best one can hope for).
4. The reduction approach provides lower bounds easily for many settings.

**weaknesses:**
1. The authors give too much credit to their MAB lower bound in my opinion. Notice that this lower bound is less tight than the previous one, and that it can be deduced from the previous lower bound and this paper's new upper bound. I think that the authors need to state this a little more accurately and focus on the lower bounds that they provide for the other settings (for which there were no previous lower bounds).
2. Although there are no previous lower bounds for conservative linear bandits/tabular MDPs/linear MDPs, I think that the authors should discuss standard constructions. That is, if I take the construction of Wu et al. and embed it in linear bandit or MDP what would I get? Embedding MAB in MDP or linear bandit is common in sequential decision making problems and should be addressed in my opinion. Could the authors explain if this is not possible here or if it gives sub-optimal lower bounds? The derivation of lower bounds through the reduction is nice but it should be put in perspective against common approaches.
3. The lower bound proof sketch is not clear at all in my opinion. I read the proof in the appendix and it was very clear so I encourage the authors to rewrite the proof sketch more closely to the way that it is written in the appendix (this is not a long proof).
4. There is no proof sketch for Theorem 3. This is the most important theorem and there is no explanation regarding its proof. The way that the LCB is combined with the budget was very interesting to me, and I was very disappointed that the (short) proof from the appendix was not sketched at all.
5. The authors mention safe RL and constrained MDP but do not explain what is the difference between them and conservative RL. These problems seem very related and I think a comparison or at least an explanation is in order.
6. The authors claim that the concept of budget was already used in Wu et al., but that it is less general because it is for the UCB algorithm. Is it really less general or simply analyzed better in the current paper (since the reduction also uses confidence bounds I am guessing it will only work with optimistic algorithms)? I am wondering whether the budget approach is novel in this paper or does this paper just analyze it better (which is also a good contribution but should be stated accurately).
7. The authors also mention budget in the context of the algorithms by Garcelon et al. and Kazerouni et al.. They say that their approach is different, but then just say that their budget is tighter. So is it really different or is the budget analyzed better in the current paper?
summary_of_the_review: The paper studies an interesting question and presents a natural reduction-based approach that yields optimal upper and lower bounds. However, the relation to previous work is not described clearly, the proof sketches are either unclear or missing and the authors put their focus on a lower bound that is less tight than previous ones. Overall, while this paper has interesting contributions, it requires further revision before being published in my opinion.
review_title: null

Meta-review: Summary: The paper studies RL and bandits in the conservative setting where the performance of the new, learnt policy should never be significantly worse than that of a baseline. 

Discussions: The main concern of the reviewers was about novelty, and specifically what new techniques and ideas were brought in this work compared to (Wu et al. 2016) and (Garcelon et al 2020). The authors have addressed these concerns and updated their draft accordingly. The reviewers have now all reached a consensus and recommend to accept this work. 

Recommendation: Accept
Decision: Accept (Poster)