Small Total-Cost Constraints in Contextual Bandits with Knapsacks, with Application to Fairness

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 estimateda 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 √ 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 √ 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. 1 Setting, literature review, and main contributions We consider contextual bandits with knapsacks [CBwK], a setting where at each round t ⩾ 1, the learner, after observing some context x t ∈ X , where X ⊆ R n , picks an action a t ∈ A in a finite set A. We do not impose the existence of a null-cost action. Contexts are independently drawn according to a distribution ν. The learner may pick a t at random according to a probability distribution, denoted by π t (x t ) = π t,a (x t ) a∈A for consistency with the notion of policy defined later in Section 2. The action a t played leads to some scalar reward r t ∈ [0, 1] and some signed vector-valued cost c t ∈ [-1, 1] d . Actually, r t and c t are generated independently at random in a way such that the conditional expectations of r t and c t given the past, x t , and a t , equal r(x t , a t ) and c(x t , a t ), respectively. We denoted here by r : X × A → [0, 1] and c = (c 1 , . . . , c d ) : X × A → [-1, 1] d the unknown expected-reward and expected-cost functions. The modeling and the estimation of r 37th Conference on Neural Information Processing Systems (NeurIPS 2023).