Summary
This paper studies multi-armed bandits with cumulative cost connstraints, with the focus of designing a 'best of both worlds' algorithm that has small constraint violations in both the stochastic and adverasarial settings (where the constraints as well as rewards can vary with time arbitrarily), and attain either low-regret for the stochastic setting, or low $alpha$-regret for the adversarial setting (i.e., ensure that the reward accrued is at least $\alpha$ times the best-in-hindsight reward accrued by a constant unconstrained assignment probability x, up to $o(T)$ terms). The main desiderata is to design methods that avoid explicit knowledge of a slater parameter, and avoid polynomial dependence on m, the number of unknown constraints, in the regret and violations, both of which are cons of prior work using the Langrangian BwK design.
Throughout, the setup adopted is linearised, i.e., at each time, the authors select a distribution $x_t$ over the actions [1:K], and the action $a_t$ is selected by sampling from $x_t$. A bandit feedback of both the reward, $f_t(a)$, and the constaint violations $g_{t}^i(a), i \in [1:m]$ is assumed, where these functions are stochastic perturbations of an expected function in the stochastic setting, and are selected arbitrarily in the adversarial setting. Throughout, it is assumed that $f_t \in [0,1]$ and $g\_t^i \in [-1,1]$. The constraint is of the form $\forall i, g_t^i \le 0$, Net violations are defined as $V_T = \max_{i} V_T^{i}, $ where $V_T^i = \sum_t g_t^i(a_t).$ Note that this equals $\sum_t \langle x_t, g_t^i\rangle,$ up to a $\sqrt{T}$ concentration term. In the adverarial case, the paper studies the regret $\frac{\rho}{1+\rho} \max_{x} \sum f_t(x) - \sum f_t(a_t),$ where $\rho$ is the minimax Slater parameter $\rho:= \max_a \min_{i,t} (-g_{t}^i(a))$.
The overall strategy adopted by the paper is very natural: for each time, the method constructs a set of "plausibly" feasible distributions as $\widehat{\mathcal{X}}\_t = \{x \in \Delta\_K : \forall i, \langle x, \hat{g}\_t^i - b\_t\rangle \le 0\}$, where $\hat{g}\_t^i$ serve as "estimates" for $g\_t^i,$ and $b$ is a nonnegative 'bonus' that ensures optimism in the stochastic scenario. The method then just selects actions from $\widehat{\mathcal{X}}\_t$, using a (small modification of) the EXP-IX strategy, thus ensuring low regret relative to any constant $x \in \bigcap \widehat{\mathcal{X}}\_t$. The main results then need to select $\hat{g}_t^i$ and $b_t$ in such a way that
1. In the stochastic case, $\mathcal{X}^* = \{x : \forall i, \langle \mathbb{E}[g_t^i], x\rangle \le 0\}$ remains within this intersection of $\widehat{\mathcal{X}}s$, and
2. In the adverasrial case, $\frac{\delta\_{a^{\emptyset}}}{1+\rho} + \frac{\rho}{1+\rho} \mathcal{X}$ remains within the same.
3. The net violation is small.
As is natural, the $b_t(a)$ is set to just $\sqrt{ \log(mT^2/\delta)/n_{t}(a)},$ where $n_t(a)$ is the number of times action $a$ has been played up to time $t$. The $\hat{g}\_t^i$ are estimated using OGD as $$ \hat{g}\_{t+1}^i(a) = \hat{g}\_t^i(a)\mathbf{1}\{a\_t \neq a\} + ( (1-\eta\_{t}^i(a) \hat{g}\_t^i(a) + \eta\_t^i(a) g\_t^i(a))\mathbf{1}\{a\_t = a\}.$$ The chief question becomes how to select the learning rates $\eta\_t^i(a)$. The basic tension is illustrated thus: in the stochastic case, we'd like $\eta\_t^i$ to be roughly $1/n\_{t}(a),$ so that $\hat{g}\_t^i(a)$ is essentially the empirical average of the feedback. However, in the adversarial case, such a rate would be way too slow, and one needs quicker adaptation. The authors elegantly resolve this dilemma by setting $ \eta\_t^{i}(a) =(1+\Gamma\_t^i)/n\_t^i,$ where $$ \Gamma\_t^t = \min( \zeta\_t , \max( 0, V\_t^i - \zeta\_t )), \textrm{ where } \zeta\_t = 21\sqrt{Kt \log(mT^2/\delta) }$$
For the stochastic case, the analysis directly shows that, whp, $V\_t^i$ never crosses the $21\sqrt{Kt}$ threshold, and thus the desired $\eta\_t = 1/n\_t(a)$ is retained. For the adversarial case, the analysis proceeds by first controlling the violation over any interval in terms of the updates to $\hat{g}\_t$ over the same, and then arguing via contradition by showing that that if $V_\tau/\sqrt{K\tau}$ is ever too large, then $\eta_t$ is large over a significantly sized interval before it, which in turn implies strong adaptation and a small $V_\tau$. Finally, the point 1 follows by the choice of $b_t(a) \sim 1/\sqrt{n\_t(a)}$, and 2 follows directly from the boundedness of the $g\_t^i$, by interpreting $\hat{g}_t^i$ as a weighted sum of the observed $g\_t^i(a_t)$s with net weight $1$.
Strengths
The subject of the paper is of course very peritnent to the online learning subcommunity at Neurips. I think the technical contribution of the paper, i.e., the design of a BOBW method for the bandits with cumulative constraints that avoids knowledge of Slater parameters is quite interesting. Furthermore, the removal of the poly(m) factors from the ensuing bounds is an important improvement in the same.
explained
I find the paper to be quite well written. The thought process behind the design of the method is well explained, and the intuition behind the design of the learning rate is clear. Prior work is contextualised well, and the contribution of the paper is clearly outlined. To my understanding, the proofs are correct.
The design of the scheme, and the analysis, are simple, but well motivated and elegant. Altogether, while I don't see this paper as especially groundbreaking, I do find it to be a well executed contribution that develops a simple idea and does interesting things with it to clean up the theory of bandits with cumulative constraints.
Questions
Comment: Comment: the roundiwse violation bound on V_T^+ of theorem 7.3 has previously been observed for the stochastic setup in the "safe bandit" literature, and this point of contact should perhaps be acknoweldged. See, e.g., [1,2]. The method these papers study is Agarwal and Devanur's style of "doubly-optmistic" selection.
[1]: Chen et al., Strategies for Safe Multi-Armed Bandits with Logarithmic Regret and Risk, ICML 22
[2]: Gangrade et al., Safe Linear Bandits over Unknown Polytopes, COLT 24