Data-Dependent Regret Bounds for Constrained MABs

We thank the Reviewer for the positive evaluation of our work.

Remark 2 uses a lower bound from 2016 for unconstrained MABs. I was surprised that the remark writes that, thus, an upper bound for constrained MABs is tight. Would there be a restricted class of constrained MABs that are "far from unconstrained ones", and for which it would be an open question to provide a lower bound?

Our algorithm, COLB, matches the existing regret lower bound for the unconstrained settings. However, we remark that our algorithm also exhibits an upper bound on the cumulative violations. This ''double'' guarantee differentiates the performance analysis of MAB algorithms in the soft constraints setting from the ones in the unconstrained setting. It doesn't matter how much constrained the instance is; the worst-case upper bound on the regret is still in that order of magnitude, as well as the bound on the cumulative violations. This is due to the worst-case nature of the result.

Could a discussion of concrete motivations for studying constrained MABs be added to the paper. Many readers can have practical motivations in mind for unconstrained MABs (say, for online advertisment) but I think many readers would benefit from examples of concrete constraints.

In the final version of the paper, we will add the following discussion about applications to online advertising. In an online advertisement scenario, from the perspective of a publisher, multiple ads (say, $K$ distinct ads) are available to be displayed to incoming users. Every ad is associated with an expected revenue, which may depend on the type of ad or its position. In an unconstrained scenario, the problem would just be to find the most profitable ad strategy. However, displaying an ad is associated with an economic cost (the spend-per-impression), and a marketing campaign has limited funding. In this sense, a publisher trying to maximize its profits in an online manner resorts to the constrained MAB model, with either soft or hard constraints, depending on its own spending policy.

Line 332, is it the fifth term rather than the fourth?

We thank the Reviewer for spotting the typo. We will surely modify it in the final version of the paper.

We thank the Reviewer for the positive evaluation of our work.

While the question of data-dependent guarantees for constrained MABs is novel, both data-dependent regret bounds for unconstrained MABs and algorithmic design for constrained MABs have been extensively studied. This paper appears to combine several previously proposed techniques and results. In particular, the OMD with log-barrier algorithm introduced by [lee et al. 2020] is heavily utilized in the proposed algorithm, especially in the analysis techniques, which are central to the proofs of the main theorems. Additionally, the structure of the feasible sets and the combination factor idea bear strong resemblance to those presented in [Pacchiano et al. 2021] and [Amani et al. 2019] .

We certainly agree with the Reviewer on the fact that our algorithm for the soft constraints setting relies on existing algorithms that attain data-dependent bounds in unconstrained settings.

Nonetheless, we believe that our results contain technical novelty and may be of independent interest. Both the regret upper bound and the regret lower bound require a novel (and challenging) analysis w.r.t. state-of-the-art unconstrained settings. This is a consequence of the fact that the (A) term and the (B) term must be treated separately (in both upper and lower regret bounds), preventing the use of existing techniques.

Moreover, while our techniques to handle the constraints satisfaction may share similarities with [Pacchiano et al. 2021] and [Amani et al. 2019], we underline that their techniques cannot be generalized to our setting, due to the adversariality of the losses. Indeed, their approach is summarized as follows. They play the strictly safe strategy for a certain number of rounds, then they play on a pessimistic safe set. We cannot adopt their approach, since adversarial no-regret algorithms do not work on enlarging decision spaces, such as pessimistic ones. Instead, we optimize on an optimistic decision space (that is, a decreasing one) and then perform a convex combination on the strictly safe strategy.

I have an issue with the paragraph titled Safe Decision Space (Lines 152--160).

We thank the Reviewer for the opportunity to clarify this aspect. We believe that there is a possible misunderstanding. Playing in $S_t$ at each round allows us to obtain sublinear cumulative violation. The safety property is attained by an additional convex combination with the safe known strategy.

From a technical perspective, lower confidence bounds are employed since the safe optimum must be included in $S_t$ at each $t$; thus, it is necessary to be optimistic on the constraints satisfaction, which results in employing the lower confidence bound. Then, it is easy to show that $S_t$ concentrates on the true safe set at a rate of $1/\sqrt{T}$, resulting in a $\widetilde{\mathcal{O}}(\sqrt{T})$ violation bound.

We will better specify it in the final version of the paper.

Since this is a crucial aspect, please let us know if further discussion is necessary.

The quantity $D_{\psi_t}$ is used extensively throughout the algorithms. However, unless I missed it, it does not appear to be explicitly defined in the main text.

We thank the Reviewer for the comment. We forgot to explicitly state the Bregman divergence definition, since this directly follows from the regularizer $\psi_t$ definition. Nonetheless, we will explicitly specify it in the final version of the paper.

In the proof of Lemma 2, particularly the first inequality following line 546, it is unclear how the bound holds uniformly for all $t$ without any additional assumption on the norm of $\hat g_t-\beta_t$. Could you please elaborate on this step?

We thank the Reviewer for the comment. The Reviewer is correct. In general, in UCB approaches, when the rewards are bounded in $[0,1]$, the quantity (empirical mean of the) rewards plus concentration bound is capped to $1$. Similarly, in our case, we do the same for the constraints, taking $0$, when $\hat g_t -\beta_t$ is negative.

We will better clarify it in the final version of the paper.

In the proof of Lemma 5, you use the inequality $k^{n_a}\leq 5$. Could you please explain how this bound is derived?

$\kappa$ is defined as $e^{1/\ln T}$. We can upper bound $n_a$ with $\ln 5 \ln T$, noticing that $x_t(a)$ is lower bounded by $1/T$ and initialized to $1/K$ and $h_a$ is initialized as $2K$ and updated as $2/x_t(a)$ every time $1/x_t(a)>h_a$.

In the proof of Theorem 2, could you please clarify the inequality that appears after Line 586?

The Reviewer is correct in stating that $\hat{\boldsymbol{\ell}}\_t$ is sparser than $\boldsymbol{\ell}$, even if $\hat{\boldsymbol{\ell}}\_t$ is larger than $\boldsymbol{\ell}$, in terms of $||\cdot\||_{\infty}$ norm. Nonetheless, the bound (at the end of the inequalities) trivially holds by bounding the difference with $\mathbb{E}_t[(\boldsymbol{\ell}_t^\top \boldsymbol{x}_t)^2]$. Thus, in the proof, we focus on the term $\mathbb{E}_t[(\widehat{\boldsymbol{\ell}}_t^\top \boldsymbol{x}_t)^2]$, which needs more explanation. In the final version of the paper, we will better specify this step. We thank the Reviewer for spotting this aspect.

I suggest modifying the definition of $V_T$ by placing the $\max$ operator inside the summation. This adjustment would ensure that there is no compensation between rounds across different arms. Moreover, the theoretical proofs provided in the paper would remain exactly the same under this modification.

We thank the Reviewer for the comment. We employed our definition of $V_T$ since it is standard in the literature. Nonetheless, we do not understand how placing the $\max_{i\in[m]}$ operator inside the summation would prevent compensation between arms. Indeed, the compensation between rounds is prevented by the $[\cdot]^+$ operator, while the definition of violation is with respect to the strategy, and not with respect to a specific action.

Can you please share your opinion on the case where the losses (or rewards) are stochastic while the constraints are adversarial?

The impossibility result on learning with adversarial constraints carries on when the losses are stochastic, too. Technically, it still holds for deterministic fixed losses. We refer to [1] for additional details.

[1] Online learning with sample path constraints. Shie Mannor, John N. Tsitsiklis, and Jia Yuan Yu (2009)

In Line 13 of the SOLB algorithm

We thank the Reviewer for pointing out the typo, we will correct it in the final version of the paper.

In the proof of Lemma 2, the second equality following line 548 appears to reference the set $\tilde S$. However, I believe it should be $S^\circ$ instead, based on the context and the structure of the argument.

We thank again the Reviewer for pointing out the typo. We will correct the typo in the final version of the paper.

We thank the Reviewer for the positive evaluation of our work.

SOLB requires Slater's condition and explicit knowledge of a strictly feasible strategy and its associated costs as input, which seems limiting, especially in practical applications.

We thank the Reviewer for the opportunity to further elaborate on the assumptions. Assumption 1. Assumption 1 (namely $\rho>0$) is provably necessary in the hard constraints setting, as highlighted by Theorem 5. To see this, notice that, when Assumption 1 does not hold, a strategy that is arbitrarily close to the safe one (that is, the strategy with $\rho=0$) could violate the constraints, thus preventing any form of exploration. We underline that Slater's condition is commonly accepted in the constrained online learning literature. Assumption 2. Assumption 2 states that the algorithm is given a strictly feasible solution (and its costs). From a theoretical perspective, this assumption allows the algorithm to simultaneously explore and satisfy the constraints when no information on the environment is available, that is, in the very first rounds. For instance, in the first round, the algorithm has to play randomly; Assumption 2 allows to be safe in the first round while possibly ``exploring" of a $\rho$ factor. From a practical perspective, we believe that this requirement is met in many real-world interesting scenarios, where a void action, that is, an action with zero constraint violation and zero reward, is available to the learner (e.g., online auctions, where the bidder may bid $0$ whenever its budget is depleted).

The initial setting of the learning rate requires knowledge of the optimal cumulative loss. The learning rate for COLB and SOLB requires knowledge of the optimal cumulative loss. While "doubling trick" is mentioned, how would this trick specifically be applied?

The doubling trick we mention is the one developed in [1] (Appendix C.3) and [2] (Remark 1). In [1], the authors introduce such a doubling trick for adapting to the very same quantity. Their setting involves graph-feedback, but one can plug an unconnected graph and resort to a standard bandit feedback, recovering the exact algorithmic steps.

[1] Chung-Wei Lee, Haipeng Luo, and Mengxiao Zhang. A closer look at small-loss bounds for bandits with graph feedback. In Conference on Learning Theory, 2020.

[2] Lee, C. W., Luo, H., Wei, C. Y., Zhang, M. (2020). Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps. Advances in neural information processing systems, 33, 15522-15533.

Can you possibly relax (or maybe adaptively learn) the strictly feasible strategy and its associated costs? It would be nice to discuss this even as a future research direction.

We believe that it is possible to dynamically learn the Slater's parameter and the strictly feasible strategy on the fly, paying an additional constant term (independent of $T$) in both regret and violation, that is, the safety property is not attainable but constant violation is. This probably can be done employing, for a constant number of rounds, a primal-dual Lagrangian approach on the constraints only, so that the optimal solution becomes the safest one corresponding to Slater's parameter. Then, it is sufficient to run our algorithm for the hard constraints with the estimates attained in the previous phase.

We will include this discussion in the final version of the paper.

Can you give a more in-depth explanation for your conjecture that the $1/\rho$ dependence should affect only the Safety Complexity term (A), and not the Bandit Complexity term (B)? What specific challenges exist in your derivations in achieving a tighter bound?

We thank the Reviewer for the interesting question. From a high-level perspective, the (B) term arises from the intrinsic hardness of attaining small loss regret bounds. Differently, the (A) term arises from the safety property, which forces any algorithm to play the strictly feasible solution a number of times that depends on $\rho$. Thus, if we consider unconstrained MABs, which are the trivial case of constrained MABs, the (A) term disappears, and the regret bound consists of the second term only. Thus, since the $\rho$ terms do not appear in unconstrained cases, it is reasonable that it is linked to the (B) term only.

As concerns the technical challenges to achieve a tighter bound, they are summarized in the following. The main idea we had to prove the tight bound was to split the analysis of Lemma 4 in two phases: (i) when the convex combination parameter $\gamma_t$ is large and (ii) when the convex combination parameter is small enough---notice that a similar approach is employed in the current analysis of Lemma 3, to avoid a $1/\rho^2$ dependence---, and proving that $\widetilde R_T$ in the first phase ($\gamma_t$ large) is constant while $\widetilde R_T$ in the second phase is independent on $\rho$. There are two key challenges in doing that. First, it is necessary to show that after a constant number of rounds, $\tilde{\boldsymbol{x}}_t$ is not to far from the uniform strategy (that is, the initialization). This can be done only assuming that $T$ is very large. Second, it is not true that there exists a round $\bar t$ which splits exactly the two phases. Thus, the analysis may result inconsistent in adversarial settings, since the rounds must be consecutive to properly bound the "regret", or, in this case, $\widetilde R_T$.

Please let us know if further discussion is necessary.

What are the hypothetical practical applications where your algorithm and results would be most critical and beneficial?

In the following, we provide a practical application in the context of online advertisement. In an online advertisement scenario, from the perspective of a publisher, multiple ads (say, $K$ distinct ads) are available to be displayed to incoming users. Every ad is associated with an expected revenue, which may depend on the type of ad or its position. In an unconstrained scenario, the problem would just be to find the most profitable ad strategy. However, displaying an ad is associated with an economic cost (the spend-per-impression), and a marketing campaign has limited funding. In this sense, a publisher trying to maximize its profits in an online manner resorts to the constrained MAB model, with either soft or hard constraints, depending on its own spending policy.

We will surely include this discussion in the final version of the paper.

We thank the Reviewer for the positive evaluation of our work.

One natural concern is whether it is reasonable to assume adversarial losses in conjunction with stochastic constraints. While the authors do point to an impossibility result to justify the assumption, it is not clear to me whether the proposed setting captures any application reasonably.

As the Reviewer noticed, the main motivation of our setting with adversarial losses and stochastic constraints is theoretical, as it is provably not possible to attain sublinear regret and violation when the constraints are adversarial as well. Nonetheless, we think that there are several applications where the loss (reward) function exhibits some sort of non-stationarity, and the constraints are instead sampled from fixed distributions. Indeed, losses (rewards) may be determined from events occurring in the external environment and possibly influenced by other learning agents (being thus possibly non-stationary), while in many applications, constraints encode some inherently stationary requirements, e.g., some resource consumption not affected by the external environment.

Moreover, the algorithms are assumed to have bounds on the loss of optimal action in hindsight, plus a strictly feasible strategy (Assumption 2). Again, it is perhaps true that the problem is intractable in the absence of such knowledge, but I wonder if what that really means is that the problem is ill-posed.

We thank the Reviewer for the interesting question. For the bound on the loss of the optimal action, we underline that a standard doubling trick approach can easily remove this assumption, that is, the quantity can be estimated on the fly, paying an additional logarithmic factor in the regret [1,2]. As concerns Assumption 2, this is met in every application where there exists a void action that attains $0$ violation, such as online auctions, where the bidder may decide to bid the $0$ value, not incurring any cost. If knowledge on the strictly feasible strategy is not available, the problem becomes ''unlearnable'' according to the standard bandit definition, i.e., the worst-case regret suffered is linear.

[1] Chung-Wei Lee, Haipeng Luo, and Mengxiao Zhang. A closer look at small-loss bounds for bandits with graph feedback. In Conference on Learning Theory, 2020.

[2] Lee, C. W., Luo, H., Wei, C. Y., Zhang, M. (2020). Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps. Advances in neural information processing systems, 33, 15522-15533.

Can the authors provide an intuitive explanation of why lower confidence bounds (LCBs), rather an UCBs, of the arm constraints are used to define safe decision spaces? I am referring to the display equation after Line 155 on Page 4. Note that with high probability, the actual $g_i$ are higher than their LCB. So the following sentence, that with high probability, the set $S_t$ contains actions that satisfy the constraints also feels suspicious.

We thank the Reviewer for the comment. We believe that there is a possible misunderstanding. Playing in $S_t$ at each round allows us to obtain a sublinear cumulative violation. The safety property is attained by an additional convex combination with the safe known strategy.

From a technical perspective, LCBs are employed since the safe optimum must be included in $S_t$ at each $t$; thus, it is necessary to be optimistic on the constraints satisfaction, which results in employing the lower confidence bound. Then, it is easy to show that $S_t$ concentrates on the true safe set at a rate of $1/\sqrt{T}$, resulting in a $\widetilde{\mathcal{O}}(\sqrt{T})$ violation bound.

Line 11 of Algorithm 1

We thank the Reviewer for pointing out this aspect. We forgot to explicitly state the Bregman divergence definition, since this directly follows from the regularizer $\psi_t$ definition. Nonetheless, we will explicitly specify it in the final version of the paper.

Note that regret calculations here include expectations with respect to algorithm randomisation. However, it feels clumsy to provide a high-probability bound on the average regret. Now, I understand the "high-probability" bit is due to the stochastic constraint modelling, and the "average" bit is over the algorithm randomisation. A brief commentary on this would be useful, IMO.

We thank the Reviewer for the interesting comment. Our regret definition employs strategy mixtures in place of the actual actions played by the algorithm and compares them to the optimal mixed strategy. This is done to be consistent with the constrained online learning literature, where the optimum is not pure, but it is a distribution over the actions. We remark that we do not take the expectation over the algorithm's randomization in the regret definition: indeed, we use OMD with log-barrier to deal with the loss estimation without taking the expectation on the algorithm's randomization. Thus, the ''high probability'' also encompasses the algorithm's randomization.

We will surely include this comment in the final version of the paper. Please let us know if further discussion is necessary.