  We consider contextual bandit problems with knapsacks [CBwK], a problem where
at each round, a scalar reward is obtained and vector-valued costs are
suffered. The learner aims to maximize the cumulative rewards while ensuring
that the cumulative costs are lower than some predetermined cost constraints.
We assume that contexts come from a continuous set, that costs can be signed,
and that the expected reward and cost functions, while unknown, may be
uniformly estimated -- a typical assumption in the literature. In this setting,
total cost constraints had so far to be at least of order $T^{3/4}$, where $T$
is the number of rounds, and were even typically assumed to depend linearly on
$T$. We are however motivated to use CBwK to impose a fairness constraint of
equalized average costs between groups: the budget associated with the
corresponding cost constraints should be as close as possible to the natural
deviations, of order $\sqrt{T}$. To that end, we introduce a dual strategy
based on projected-gradient-descent updates, that is able to deal with
total-cost constraints of the order of $\sqrt{T}$ up to poly-logarithmic terms.
This strategy is more direct and simpler than existing strategies in the
literature. It relies on a careful, adaptive, tuning of the step size.
