Budget-Constrained Causal Bandits: Bridging Uplift Modeling and Sequential Decision-Making

1. Formulazione del Problema

Il documento affronta la sfida dell'allocazione dei trattamenti vincolata dal budget nella pubblicità digitale, specificamente in scenari di cold-start dove i dati storici sono scarsi o inesistenti (ad esempio, nuove campagne, nuovi mercati).

• Obiettivo Principale: Massimizzare le conversioni totali (esiti del trattamento) selezionando un sottoinsieme di utenti a cui mostrare annunci, soggetto a un vincolo di budget totale $B$.
• Vincoli e Sfide Chiave:
  1. Effetti del Trattamento Eterogenei (HTE): Gli utenti rispondono diversamente agli annunci. L'obiettivo è indirizzare gli utenti con alti effetti causali positivi ($\tau(x)$), evitando quelli non influenzati o influenzati negativamente.
  2. Vincoli di Budget: Ogni utente ha un costo specifico $c_t$ (ad esempio, prezzo dell'asta pubblicitaria). Il costo cumulativo non deve superare $B$.
  3. Cold-Start / Scarsità di Dati: I metodi offline tradizionali richiedono grandi dataset storici per addestrare modelli di uplift. In nuovi scenari, questi dati non sono disponibili, portando al problema del "cold-start".
  4. Decisione Sequenziale: Gli utenti arrivano uno alla volta. Il sistema deve apprendere gli effetti del trattamento online, gestendo simultaneamente il ritmo di spesa del budget (evitando l'esaurimento prematuro o la spesa insufficiente e sprecona).

Definizione Formale:
Il problema è modellato come un processo sequenziale su $T$ round. Ad ogni round $t$, l'agente osserva un utente con caratteristiche $x_t$ e costo $c_t$, e sceglie un'azione $a_t \in \{0, 1\}$ (trattare o meno). L'obiettivo è:
$$\max \sum_{t=1}^T a_t \cdot Y_t(1) \quad \text{soggetto a} \quad \sum_{t=1}^T a_t \cdot c_t \le B$$
dove $Y_t(1)$ è l'esito potenziale se trattato.

2. Metodologia: Causal Bandits Vincolati dal Budget (BCCB)

Gli autori propongono BCCB, un framework online unificato che integra tre componenti distinte in un singolo processo decisionale sequenziale. A differenza delle pipeline offline a due stadi (addestra poi ottimizza) o dei bandit standard (che ignorano l'HTE), BCCB impara, esplora e regola il ritmo simultaneamente.

A. Stima Online dell'HTE

• Approccio: Utilizza un approccio a due modelli per stimare gli effetti del trattamento individuali online.
  • Modello 1: Stima $P(Y=1 | x, T=1)$ (Probabilità di conversione se trattato).
  • Modello 2: Stima $P(Y=1 | x, T=0)$ (Probabilità di conversione se controllo).
• Meccanismo: Entrambi i modelli vengono aggiornati incrementalmente utilizzando la Discesa del Gradiente Stocastica (SGD) con perdita logistica dopo ogni osservazione.
• Gestione del Cold-Start: Prima di raccogliere dati sufficienti (meno di 50 osservazioni trattate/di controllo), viene utilizzato un prior ottimistico ($\hat{\tau} = 0.002$) per incoraggiare l'esplorazione iniziale.

B. Esplorazione tramite Campionamento di Thompson

• Obiettivo: Bilanciare l'esplorazione (apprendere utenti incerti) e lo sfruttamento (indirizzare utenti di alto valore noti).
• Meccanismo: Mantiene distribuzioni posteriori Beta per i tassi di successo globali del trattamento e del controllo.
• Bonus di Esplorazione: Ad ogni passo, l'algoritmo campiona dalle posteriori per calcolare un bonus di esplorazione:
  $$\text{exploration\_bonus}_t = (\theta_t^{(1)} - \theta_t^{(0)}) \cdot \eta$$
  Questo bonus viene aggiunto all'HTE stimato, incoraggiando l'algoritmo a trattare utenti con effetti incerti anche se la stima attuale dell'HTE è ambigua.

C. Regolazione Adattiva del Budget (Budget Pacing)

• Obiettivo: Prevenire l'esaurimento prematuro del budget o una spesa inefficiente insufficiente.
• Meccanismo: Calcola un rapporto di pressione del budget ($pace_t$) ad ogni round:
  $$pace_t = \frac{B_t / B_0}{(T - t) / T}$$
  • Se $pace_t > 1$: Il budget è abbondante rispetto al tempo; l'algoritmo spende più liberamente.
  • Se $pace_t < 1$: Il budget si esaurisce troppo velocemente; l'algoritmo diventa più selettivo.
• Modulazione della Soglia: Il rapporto di ritmo adatta dinamicamente la soglia decisionale. Quando il budget è scarso, la soglia per il trattamento aumenta, garantendo che vengano selezionati solo utenti ad alta efficienza di costo.

D. Regola Decisionale Combinata

Per ogni utente $t$, l'algoritmo calcola un punteggio e una metrica valore-per-dollaro:

1. Punteggio: $s_t = \hat{\tau}(x_t) + \text{exploration\_bonus}_t$
2. Valore: $v_t = s_t / c_t$
3. Decisione: Trattare ($a_t=1$) se $v_t > \frac{\lambda}{\max(pace_t, \epsilon)}$, dove $\lambda$ è una soglia di base.

3. Contributi Chiave

1. Framework Unificato: Propone BCCB, il primo framework che unisce l'apprendimento HTE, l'esplorazione tramite Campionamento di Thompson e la regolazione adattiva del budget in un singolo processo online senza richiedere dati storici pre-raccolti.
2. Crossover di Efficienza dei Dati: Identifica empiricamente una soglia critica (~10.000 osservazioni storiche). Al di sotto di questa, i metodi offline falliscono o sono altamente instabili; al di sopra, i metodi offline possono superare quelli online. BCCB opera efficacemente dal primo utente in assoluto.
3. Stabilità delle Prestazioni: Dimostra che BCCB ha una varianza delle prestazioni 3–5 volte inferiore rispetto ai metodi offline su esecuzioni ripetute, rendendolo più affidabile per la pianificazione delle campagne.
4. Prestazioni Online Superiori: Tra i metodi puramente online, BCCB supera costantemente il Campionamento di Thompson Standard, il Campionamento di Thompson con Budget e la stima HTE Greedy a tutti i livelli di budget.

4. Risultati Sperimentali

Lo studio è stato valutato sul dataset Criteo Uplift (1,4 milioni di utenti) con costi sintetici generati tramite una distribuzione log-normale.

• Confronto Online vs Online:
  • Con un budget alto ($8.000), BCCB ha ottenuto 46 conversioni, superando il Campionamento di Thompson Standard (37) e HTE Greedy (29).
  • Con budget ristretti ($1.000), BCCB e Budgeted TS hanno ottenuto i migliori risultati, evidenziando l'importanza della consapevolezza del budget.
• Crossover di Efficienza dei Dati (Offline vs Online):
  • < 2.000 osservazioni: I metodi offline sono falliti completamente (il modello non poteva adattarsi a causa di esempi positivi nulli nel gruppo di controllo). BCCB ha operato con successo.
  • 2.000 – 10.000 osservazioni: I metodi offline hanno mostrato una varianza estrema (Coefficiente di Variazione > 100%). BCCB è rimasto stabile.
  • > 50.000 osservazioni: I metodi offline hanno infine superato BCCB (104 vs 25 conversioni), confermando che i metodi offline sono superiori quando esistono dati abbondanti e rappresentativi.
• Stabilità: BCCB ha mostrato deviazioni standard di 7–13 conversioni, mentre i metodi offline variavano da 35–65. Questa riduzione della varianza di 3–5 volte è cruciale per previsioni di ROI prevedibili.
• Scalabilità: BCCB ha mantenuto prestazioni superiori su diverse scale del dataset (100K, 500K, 1,4M utenti), mentre i metodi HTE Greedy erano altamente incoerenti.

5. Significato e Limiti

Significato:

• Risoluzione del Problema Cold-Start: Fornisce una soluzione praticabile per nuove campagne pubblicitarie dove i dati storici non sono disponibili, uno scenario in cui le pipeline industriali standard falliscono.
• Mitigazione del Rischio: L'alta stabilità di BCCB riduce il rischio di fallimento della campagna dovuto alla varianza del seme casuale, un problema comune con i modelli offline addestrati su piccoli dataset.
• Cambiamento di Paradigma: Sposta il campo da "addestra poi distribuisci" a "impara e alloca simultaneamente" per l'inferenza causale vincolata alle risorse.

Limiti:

• Abbondanza di Dati: Se un'azienda dispone di 50.000+ osservazioni storiche dalla stessa popolazione, i metodi offline rimangono superiori.
• Costi Sintetici: Lo studio ha utilizzato costi sintetici basati su una distribuzione log-normale. Le dinamiche reali delle aste potrebbero essere più complesse.
• Complessità del Modello: L'implementazione attuale utilizza classificatori lineari per l'HTE. Modelli online più espressivi (ad esempio, reti neurali online) potrebbero migliorare l'accuratezza ma sono stati lasciati per lavori futuri.

Conclusione:
BCCB colma il divario tra la modellazione dell'uplift e la decisione sequenziale, offrendo una soluzione robusta ed efficiente dal punto di vista dei dati per l'allocazione dei trattamenti vincolata dal budget nella pubblicità digitale, in particolare in scenari caratterizzati da scarsità di dati e dalla necessità di prestazioni immediate e stabili.