Contextual Bandits with Knapsacks for a Conversion Model - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

Contextual Bandits with Knapsacks for a Conversion Model

Résumé

We consider contextual bandits with knapsacks, with an underlying structure between rewards generated and cost vectors suffered. We do so motivated by sales with commercial discounts. At each round, given the stochastic i.i.d.\ context $\mathbf{x}_t$ and the arm picked $a_t$ (corresponding, e.g., to a discount level), a customer conversion may be obtained, in which case a reward $r(a,\mathbf{x}_t)$ is gained and vector costs $c(a_t,\mathbf{x}_t)$ are suffered (corresponding, e.g., to losses of earnings). Otherwise, in the absence of a conversion, the reward and costs are null. The reward and costs achieved are thus coupled through the binary variable measuring conversion or the absence thereof. This underlying structure between rewards and costs is different from the linear structures considered by Agrawal and Devanur [2016] (but we show that the techniques introduced in the present article may also be applied to the case of these linear structures). The adaptive policies exhibited solve at each round a linear program based on upper-confidence estimates of the probabilities of conversion given $a$ and $\mathbf{x}$. This kind of policy is most natural and achieves a regret bound of the typical order (OPT/$B$) $\sqrt{T}$, where $B$ is the total budget allowed, OPT is the optimal expected reward achievable by a static policy, and $T$ is the number of rounds.
Fichier principal
Vignette du fichier
CBwK-conversion--Li-Stoltz-v2.pdf (2.98 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03683289 , version 1 (31-05-2022)
hal-03683289 , version 2 (29-09-2022)

Identifiants

Citer

Zhen Li, Gilles Stoltz. Contextual Bandits with Knapsacks for a Conversion Model. Thirty-sixth Conference on Neural Information Processing Systems, 2022, New Orleans, United States. ⟨hal-03683289v2⟩
111 Consultations
45 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More