Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper studies the problem of online optimization with long-term constraints, where the goal is to maximize the reward and minimize the violation simultaneously. The authors provide a best-of-both-worlds (BOBW) algorithm to handle stochastic and adversarial constraints. This algorithm uses a general regret optimizer (RM) oracle, which can handle the different reward functions and feedback models. For the analysis, a new notion of $\rho$, which measures the margin of strict feasibility, is used to give BOBW performance guarantee.
strengths_and_weaknesses: Strength
1. The authors propose a general framework that connects several lines of works based on different types of constraints.

2. The algorithm proposed by the authors is very interesting and intuitive. It consists of two phases: the play phase to select aggressive actions to maximize the reward according to a constraint violation threshold and the recovery phase to compensate for the violation by playing safe actions.

3. The authors give a new notion of $\rho$, and based on $\rho$, the authors provide promising results with weaker assumptions for the stochastic constraint case when $\rho$ is constant. The authors also give results when $\rho$ is not constant and can be arbitrarily small, meaning the constraints are quite difficult to satisfy. Under this case, they provide the first result for the stochastic case, though weaker than the constant case.

Weakness
~1. My main concern is about the adversary case. This work gives a $\frac{\rho}{\rho+1}OPT-O(\sqrt{T})$ reward guarantee, but the authors require $\rho \le O(T^{-1/4})$ and could approach 0 (when $T$ is large), which means the reward guarantee is $0-O(\sqrt{T})$ and the result seems meaningless.~

Post-rebuttal: This concern has been satisfactorily addressed.

questions: ~I hope the authors can justify my concern in the weakness part.~

Also, are there any lower bound results based on $rho$, saying that $\frac{\rho}{1+\rho}$ is the best we can do and $O(T^{3/4}$ types of results are the best for the stochastic case? Can the authors explain more about this?
limitations: Yes, the authors adequately addressed the limitations and there is no potential negative societal impact of their work.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper deals with the problem of online learning with long term constraints, where the latter are either stochastic  or adversarial. The main contribution is a meta-algorithm based on no-regret online learning for the primal and dual problems, which are solving the "Lagrangian game" introduced by Immorlica et al. (for different type of constraints): one online learner tries to maximize the Lagrangian while the other to minimize it. A novel idea is that, when the constraint violation exceeds a threshold, the algorithm takes care only of the constraints, disregarding the objective function. 

The authors prove that their proposed algorithm: (i) achieves, in the case of adversarial constraints, an objective at least a constant fraction of the optimal action in hindsight, while having a constraint violation residual sublinear with T in the case of adversarial constraints where (a bound on) the slack from the Slater condition is known (the constant factor depends on this slack) and (ii) in the case of stochastic constraint achieves a sublinear in T regret and constraint residual even if this bound is not known.   

The objective and constraint functions can be non-convex  and the action sets can be non-convex or discrete; this achieved by essentially randomizing the action by finding a probability distribution over the action space (and have the constraints and objectives be the expectation over this probability distribution).   
strengths_and_weaknesses: Strengths: 
1. This is the first paper, to my knowledge, to provide performance guarantees for adversarial long-term constraints when the benchmark action is allowed to satisfy the long term constraint (instead of satisfying the constraint in every round or windows of rounds). These guarantees are a step towards understanding more about online learning problems with long term constraints (the result of Mannor et al. just states that the adversary can force $\Omega(T)$ regret if the constraint residual is to be sublinear).  
2.  The fact that when constraints are stochastic the slack in the constraints needs not to be known is also a nice result and a nice addition to the related literature. 

Weaknesses: 
1. The presentation is quite high level and difficult to follow and understand how exactly it works and how it can be implemented. 
2. The constant factor depends on the slack $\rho$, which can, at least in theory be very small in the adversarial setting (by the adversary choosing, e.g. constraints that are barely satisfied and/or choosing e.g. $\rho$ as a decreasing function of $T$): it is not clear how useful the approximation bound is in this case.
questions: 1. It would be nice to have some examples with some concrete implementations of the Regret Minimizers and their related operations (e.g. in an appendix); this would help towards a better understanding of the algorithms. 

For example, in the case of concave rewards and convex costs (and convex action set $\mathcal{X}$), does the algorithm run on a probability distribution over $\mathcal{X}$ or the actions themselves? 

2. It would also be nice to have some numerical results about the performance and implementation of the algorithm in the repeated auctions setting of Section 7. 

3. In Section 7, why is the auction model restricted to discrete valuations and actions? 
limitations: This is a theoretical work, so I can think of no potential negative social impact.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper proposes a no-regret meta-algorithm that jointly has:
- no constraint regret (i.e. sublinear) if the constraints are stochastic,
- no-$\rho/(1+\rho)$-regret if they are adversarial (i.e. no-regret w.r.t. $\frac{\rho}{1+\rho}\mathrm{OPT}$), where $\rho$ is the strict feasibility margin of the problem.

The main contribution is that the proposed algorithm attains suitable rates across the array of settings considered in past works (hence the title, 'unifying framework'). The paper also studies the application of the algorithm to the repeated auction setting, showing it satisfies "guaranteed budget completion" under certain assumptions (due to guarantees of the algorithm under stochastic constraints *and* rewards). 
strengths_and_weaknesses: Strengths:
- The paper is very well written and provides an elegant general algorithm,
- Having a play phase and a recovery phase is something that I personally haven't seen in the related work (but I have only read a handful of papers in this particular sphere, online optimization with long-term constraints), and it seems to be amendable to downstream analysis of induced properties (e.g. showing the recovery phase is not entered implies the "guaranteed budget completion" property under stochastic constraints and rewards).

Weaknesses:
- there is no *clear* rate improvement with respect to prior work
- the algorithmic approaches and analysis are somewhat standard and expected (given the 'unifying' character of the work this is somewhat natural in my opinion)
questions: - Could your algorithm provide a zero constraint violation guarantee if employed with a safety barrier as in [37] section 3.2? [answered in rebuttal, see below]
- Could you delineate the trade-offs between their algorithm and the main competitors (e.g. does one or the other have better constants? is one or the other easier to implement?)
limitations: - I think authors should prioritize moving more of the related work discussion from Appendix A to the main body, especially given the nature of the work,
- Similarly, the authors should include a conclusion that clearly address any limitations w.r.t. the existing approaches,
- Could Table 1 be exteded to include more related work? even if the comaprator is different, the comparator type could be noted in an additional column.

Minor Comments:
- should it be 'constraint' rather than 'constraint*s*' in line 4?
- equation $\mathrm{LP}_{f,g}$ could work better as one line?
- maybe change ', e.g. RMs in [41]' to 'RMs such as the ones in [41]' on line 214?
- line 256 : 'allow' -> 'allow*s*'
- line 287: 'to capture also' -> 'to also capture'
- line 339: 'incurring in any cost' -> 'incurring any cost'
review_title: null

Meta-review: metareview: This paper studies the problem of online optimization with long-term constraints and proposes an interesting black-box type of algorithm that works well for both the stochastic setting and the adversarial setting. One issue that reviewers brought up for the adversarial case is whether competing with only \rho/(1+\rho) fraction of the optimal utility is indeed meaningful or necessary. In the rebuttal the authors mentioned that this is likely optimal in light of its connection to the literature on the budget-constrained case, but only leave the formal reduction between the two as future directions. We believe that the paper would be much more complete if this reduction is properly spelled out, and thus encourage the authors to do so in the final version.
confidence: Certain
Decision: Accept