Web platforms select among costly interventions for each user to maximize incremental outcomes under a global budget. We formulate this problem as a budget-constrained contextual bandit with heterogeneous treatment effects. Although an action-independent outcome baseline cancels from treatment comparisons, modeling a nonlinear baseline can increase statistical complexity. We propose DR-CATE-CBwK, an action-centered causal bandit that directly learns treatment contrasts. Its online update remains valid under baseline-model misspecification without inverse-propensity weighting. It combines an offline doubly robust learner to warm-start treatment-effect estimates, an online action-centered estimator for sequential contrast learning, and a primal-dual controller with an affordable-action rule to enforce the effective-cost budget pathwise. For linear conditional average treatment effects (CATEs) in a stationary i.i.d. setting, we prove a high-probability (\widetilde{O}(Kd\sqrt{T})) regret bound, where K is the number of priced actions, d the context dimension, and T the horizon. We benchmark against the fluid linear program (LP) under the coverage-guaranteed action rule. We further show that the action-centered estimating moment remains unbiased under any predictable baseline estimate, whereas a specified separate-arm reward regression can exhibit asymptotic contrast bias under action-dependent logging and shared-baseline misspecification. On a semi-synthetic job-marketplace benchmark with real logged features and simulated outcomes, our practical Thompson-restricted variant achieves the lowest regret among evaluated budget-feasible methods in the operating regime. It reduces regret by approximately 20% versus the strongest reward-based baseline, outperforming raw-reward contextual bandits, BwK baselines, and a static offline policy, while never exceeding the effective-cost budget.
Algorithm 3 RandomizedAction : active-set semiparametric selection with a budget offset (Assumption 8 ).
Method
Regret R(T)
Spend ( B=600 )
DR-CATE-CBwK (Thompson, ours)
498±56
600
No CATE prior
592±54
600
Raw-Flex-CBwK
620±38
600
Raw-CBwK
718±54
600
No residualization
836±98
600
SquareCBwK
928±103
600
Table 1: Operating regime (nonlinear baseline, context-dependent logging, offline-to-online shift; T=6000 , ρ=0.10 , 32 seeds, 95% CI). Regret is against the fluid LP (lower is better); ± is the 95% CI half-width over seeds. DR-CATE-CBwK variants use calibrated parameters as described in Section 6.1 . Spend is rounded to whole normalized effective-cost units. Budget-aware methods respect the 600 cap; the No budget ablation spends 2729 .
Figure 1: Finite-horizon scaling for Thompson (deployed; slope 0.56 , CI [0.51,0.61] ) and the coverage mixture ( γ=0.1 , slope 0.72 ), using calibrated confidence and dual scales.
Figure 2: Baseline robustness (Theorem 2 (a,b)). Contrast error versus sample size. Under context-dependent logging the action-centered estimator’s error keeps decreasing while separate-arm OLS plateaus at a bias; under randomized logging both decrease. Means over 32 seeds.
Method
Regret R(T)
Neural DR-CATE-CBwK
906±42
DR-CATE-CBwK (linear)
945±45
Raw-Flex-CBwK
1009±45
Raw-CBwK
1063±46
UCB-ALP
1070±50
SquareCBwK
1078±57
Table 2: Nonlinear CATEs ( ω=5 , T=6000 , ρ=0.10 , 32 seeds; ± denotes 95% CI half-width). The neural improvement over the linear variant is not significant ( p=0.11 ).
Treatment allocation under budget constraints is a central challenge in digital advertising: advertisers must decide which users to show ads to while spending a limited budget wisely. The standard approach follows a two-stage offline pipeline - first collect historical data to estimate heterogeneous treatment effects (HTE), then solve a constrained optimization to allocate the budget. This works well with abundant data, but fails in cold-start settings such as new campaigns, new markets, or new customer segments where little historical data exists. We propose Budget-Constrained Causal Bandits (BCCB), an online framework that learns which users respond to ads while simultaneously spending the budget, making treatment decisions one user at a time. BCCB unifies three components into a single sequential process: learning individual-level ad effectiveness, exploring users whose response is uncertain, and pacing the budget over time. We evaluated on the Criteo Uplift dataset, a large-scale advertising dataset from a real randomized controlled trial. Our key finding is a data-efficiency crossover: offline methods require approximately 10,000 historical observations to produce reliable results, while BCCB operates effectively from the very first user. Furthermore, BCCB exhibits 3-5x lower performance variance between runs, making it more practical for real campaign planning. Among purely online methods, BCCB consistently outperforms standard Thompson Sampling, budgeted Thompson Sampling, and greedy HTE estimation across all budget levels tested.
We study constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. The conditional mean reward and cost belong to known function classes and are learned through online regression oracles. The benchmark is a stationary randomized policy whose expected cost is non-positive at every observed context. We extend the seminal SquareCB algorithm of Foster and Rakhlin (2020), which reduces the contextual bandits to a regression problem, to the constrained setting. A surrogate reward function is constructed which penalizes the positive part of the expected cost of an action distribution, and an auxiliary variable accumulates its predicted value. Then we use an exponential Lyapunov function to control both regret and cumulative constraint violation via a single inequality. If the cumulative squared prediction error is at most UT, our algorithm achieves O(KTUT) regret and O(KTUTlogT) cumulative expected cost, with high probability, improving upon the previous O(T3/4) type bounds obtained in stochastic contextual settings with an unknown context distribution. Our results require neither additional margin conditions nor probabilistic assumptions on the context sequence.
Dhruv Sarkar, Abhishek Sinha
Indian Institute of Technology Kharagpur, India · Tata Institute of Fundamental Research, Mumbai, India
Contextual bandits with stage-wise constraints model decisions that must control risk while learning from their outcomes. We study this problem when only the selected action's reward and cost are observed, with a general reward class and a convex class of nonlinear cost functions. We propose CS-UCCB, which combines offline regression, cost confidence sets, and upper counterfactual confidence bounds. Each regression fit defines a valid cost confidence set, while a geometry derived from covering entropy controls cumulative cost uncertainty along the sampled decisions. Under polylogarithmic covering entropy for both classes and polylogarithmic offline estimation error, the finite-action algorithm guarantees, with high probability, feasibility at every round and O(T) regret without an eluder-dimension term. We also extend the analysis to infinite actions under an explicit reward-design condition and compare our bound with existing eluder-dimension bounds.