Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
40,667 characters · 17 sections · 16 citation commands
Auditing Marketing Budget Allocation with Hindsight Regret
\ccsdesc[500]{Computing methodologies Causal reasoning and diagnostics} \ccsdesc[300]{Computing methodologies Machine learning} \ccsdesc[300]{Information systems Online advertising} \ccsdesc[300]{Computing methodologies Uncertainty quantification} \ccsdesc[100]{Computing methodologies Continuous optimization}
Strategic budget allocation is a recurring decision problem in digital advertising. Organizations must distribute finite budget across channels, markets, and campaigns over a planning horizon while respecting operational guardrails such as budget limits, pacing rules, and stability constraints. Because these allocations are high-dimensional, persistent, and costly to revise, poor decisions can carry substantial economic consequences.
A central challenge is retrospective evaluation. Observed outcomes such as revenue or profit reflect not only decision quality, but also market conditions, platform dynamics, and other factors outside the planner's control. As a result, even when historical logs are available, it is difficult to determine whether a realized allocation was close to the best feasible decision that could have been made under the same operational constraints. This raises a natural question: How much value was left on the table due to the allocation decision itself?
Online advertising provides a concrete and economically important instance of this problem. Although auctions operate at the level of individual impressions, many consequential choices occur at a slower timescale through portfolio-style budget commitments across heterogeneous assets such as channels, regions, and campaigns zhao2019unified. These decisions are subject to practical constraints including caps, pacing rules, and limits on reallocation across periods pmlr-v235-balseiro24a, nguyenAdKDD23, holthausen1982advertising, symitsi2022keyword, baardman2019learning. In practice, organizations often have detailed historical allocation logs, but lack principled tools for auditing whether past allocations were near-optimal.
Standard evaluation approaches do not directly address this need. Randomized experiments are costly or infeasible for continuous, high-dimensional allocations and may violate no-interference assumptions due to cross-channel effects kohavi2020trustworthy,eckles2017interference. Pre--post and interrupted time-series analyses are sensitive to non-stationarity and shocks bernal2017its,angrist2009mhe. Synthetic control methods rely on stable donor units and cross-sectional comparability assumptions that are difficult to justify for persistent, multi-asset allocation trajectories abadie2021using,dube2014pooled_techreport. More broadly, while regret is central in online learning, those formulations focus on sequential adaptation under partial feedback rather than post-hoc auditing of a realized strategic allocation.
We therefore study retrospective budget-allocation auditing through hindsight regret: the opportunity cost of the realized allocation relative to the best feasible alternative in hindsight under the same operational guardrails. Our goal is not online control or policy learning, but post-hoc measurement of whether a historical allocation left recoverable value unrealized. To do so, we estimate regime-specific spend--response functions from historical logs, construct constraint-faithful hindsight benchmarks through constrained optimization, and propagate model and outcome uncertainty through Monte Carlo evaluation to obtain regret distributions and probability-of-improvement summaries. This yields an interpretable estimate of “value left on the table” while separating apparent allocation inefficiency from uncertainty in the estimated response surfaces.
\noindentIn summary, our main contributions are:
Overview of Measurement Approaches in Practice: Randomized online experiments remain the standard for causal measurement in digital systems kohavi2020trustworthy. However, strategic budget allocation is continuous, high-dimensional, and persistent, which makes large-scale randomization costly and often operationally infeasible. Advertising systems also exhibit interference across auctions, channels, and users, weakening standard no-interference assumptions eckles2017interference. When experimentation is unavailable, practitioners often fall back on pre--post or interrupted time-series designs bernal2017its,angrist2009mhe, which rely on stable untreated dynamics and can break under demand shocks or non-stationarity. Synthetic control methods similarly require donor stability and cross-sectional comparability abadie2021using,dube2014pooled_techreport,zhang2019inference, assumptions that are difficult to justify for persistent, policy-driven allocation trajectories in mediated ad-delivery systems.
Regret as retrospective decision evaluation: In statistical decision theory, regret formalizes an ex-post opportunity cost: given realized outcomes and a feasible action set, the chosen decision is evaluated against the best feasible alternative that could have been selected in hindsight under the same environment savage1954foundations,loomes1982regret. This produces a static optimality gap that measures decision inefficiency rather than learning dynamics. By contrast, regret in bandit and reinforcement learning settings auer2002using,jaksch2010near,srinivas2010gaussian,abbasi2011regret,dean2018regret is sequential and cumulative, reflecting the loss incurred while adaptively learning under partial feedback. Our formulation adopts the former perspective. It is also distinct from off-policy evaluation, whose objective is to estimate the value of a target policy from logged feedback. Here the object of evaluation is a realized allocation trajectory, and the benchmark is a feasible hindsight reallocation under the same operational regime rather than a new policy to be deployed prospectively.
Structural Causal Modeling Approach: Budget allocation in advertising systems operates through a structural data-generating process: planned budgets affect latent bidding and delivery decisions, which in turn determine realized spend and downstream returns bottou2013counterfactual. We use the Structural Causal Model (SCM) framework pearl2009causality to give semantics to these counterfactual comparisons through interventional response functions, namely expected returns under hypothetical spend allocations. Identifiability of such structural response functions requires assumptions on functional form and noise structure. Prior work on additive and related noise models provides identifiability results for nonlinear cause--effect pairs shimizu2006linear,hoyer2009nonlinear,peters2017elements, immer2023identifiability,yin2024effective.
Need for a Custom Framework: Existing approaches do not directly answer the question central to this paper: whether a realized strategic allocation was close to the best feasible allocation that could have been chosen in hindsight under the same operational guardrails. Our framework addresses this gap by estimating regime-specific response surfaces from historical logs, constructing feasible hindsight reallocations within the same regime, and quantifying the resulting opportunity cost with uncertainty-aware regret summaries. Non-stationarity is handled through epoch-wise re-estimation and support-aware uncertainty inflation rather than by assuming invariant untreated baselines or stationary learning dynamics.
We consider sequential budget allocation over a fixed planning horizon of $T$ operational time steps. Budgets are updated at coarser decision epochs $\tau \in \{1,\dots,T/k\}$ and held fixed for $k$ operational steps. At each epoch, the planner allocates budget across $N$ assets.
Let $\mathbf{b}_\tau=(b_{\tau,1},\dots,b_{\tau,N}) \in \mathcal{B}\subseteq\mathbb{R}_+^N$ denote the epoch-$\tau$ budget vector, where $\mathcal{B}$ encodes feasibility constraints such as total budget, caps, floors, and operational guardrails.
\paragraph{Mediated execution.} Budgets do not directly determine spend or returns. Instead, delivery is mediated by a platform execution mechanism interacting with a stochastic market environment bottou2013counterfactual. Let $x_\tau$ denote observed context, $u_\tau$ unobserved exogenous factors (e.g., competition, inventory), and $z_\tau$ internal system state. The structural relations are
Here $\mathbf{s}_\tau$ denotes realized spend and $\boldsymbol{\rho}_\tau$ realized returns. Latent bidding and serving actions $\boldsymbol{\beta}_\tau$ are not observed. Our retrospective analysis therefore operates at the realized-spend layer, treating the upstream execution mechanism as latent.
\paragraph{Observability and feedback.} At epoch $\tau$ the planner observes $(x_\tau,\mathbf{b}_\tau,\mathbf{s}_\tau,\boldsymbol{\rho}_\tau)$, but not $\boldsymbol{\beta}_\tau$, $z_\tau$, $u_\tau$, or counterfactual outcomes. Feedback is bandit-style, revealing returns only at the executed allocation.
\paragraph{Budget accounting.} The planner is given a fixed total budget $B_{\mathrm{tot}}$ for the horizon, with allocations satisfying
\paragraph{Planning policy.} A policy $\Pi$ maps available information to allocations: $ \mathbf{b}_\tau \leftarrow \Pi(\mathcal{F}_\tau) $, with $ \mathcal{F}_\tau = \{x_{1:\tau}, \mathbf{b}_{1:\tau-1}, \mathbf{s}_{1:\tau-1}, \boldsymbol{\rho}_{1:\tau-1}\}. $ This partially observed sequential formulation defines the historical setting against which hindsight regret is evaluated.
We present a retrospective framework for auditing the quality of a realized budget allocation through hindsight regret, defined as the opportunity cost relative to the best feasible spend trajectory that could have been executed under the same operational constraints and historical regime. The pipeline proceeds in three steps:
In classical decision theory, regret is the loss in utility incurred by a decision that is suboptimal relative to an alternative evaluated in hindsight under the realized state of the world savage1954foundations,loomes1982regret. In our setting, a decision corresponds to a feasible spend trajectory $\mathbf{s}=\{s_{\tau,i}\}_{\tau,i}$ and utility is total realized return $R(\mathbf{s}) := \sum_{\tau,i} \rho_{\tau,i}(s_{\tau,i})$. Given a realized trajectory $\mathbf{s}_{\mathrm{real}}$ and a feasible benchmark $\mathbf{s}^\star$, regret is defined as
Because realized returns are stochastic and response functions are estimated from data, $\mathrm{Reg}$ is a random variable. Individual realizations may be negative, corresponding to favorable stochastic outcomes under the realized trajectory relative to the benchmark. We therefore evaluate expected regret
and report probability statements of the form $\mathbb{P}(\mathrm{Reg} > 0)$, which quantify the likelihood that the benchmark dominates the realized trajectory in hindsight.
\paragraph{Operational regret with stability constraints ($\delta$) and confidence ($\varepsilon$).} The benchmark depends on the operational realism encoded by the feasible set. We index the feasible set by a stability parameter $\delta$ and define
where $\mathcal{B}(\delta)$ denotes the $\delta$-constrained feasible set (defined in Step II). We call regret $\varepsilon$-certified at level $\delta$ if
Let $\Delta$ denote a prespecified set of plausible constraint levels. We select
and report $\mathbb{E}[\mathrm{Reg}(\delta^\star)]$ together with $\mathbb{P}(\mathrm{Reg}(\delta^\star)>0)$.
We model epoch-specific spend--return mappings and evaluate counterfactual spend trajectories under fixed operational guardrails. Upstream budget-to-bid dynamics are abstracted away; analysis is conducted at the realized-spend layer.
We formalize the assumptions used to identify an epoch-specific interventional mean response. The key modeling choice is to treat each epoch as a locally stationary regime: within an epoch, observations are analyzed as conditionally independent replicates given observed covariates, while non-stationarity is handled at epoch boundaries through drift regularization and stability constraints.
\paragraph{A1. Structural Response Model.} For asset $i$ in epoch $e$, realized outcomes satisfy
The function $f_{i,e}$ represents the reduced-form spend--return mechanism induced by the execution regime in epoch $e$.
\paragraph{A2. Within-epoch stationarity and local mean independence (identification).} Within epoch $e$, conditional on $(s_{\tau,i},x_{\tau,i})$, the noise process $\{\varepsilon_{\tau,i}\}_{\tau\in e}$ is treated as mean-zero and approximately independent across $\tau$:
Under A2, the interventional mean response \[ \mu_{i,e}(s) = \mathbb{E}\!\left[f_{i,e}(s, X_{\tau,i}) \mid \tau\in e\right] \] is identified over the realized spend range in epoch $e$, that is, the $s$ values observed under the historical policy within that epoch.
\paragraph{A3. Bounded drift across epochs (regularization only).} Across adjacent epochs $e$ and $e'$, the reduced-form mechanism varies smoothly on the overlap of their realized spend ranges:
This condition enables weak borrowing of strength for estimation stability but does not expand causal identification beyond the epoch's realized spend range. Accordingly, the framework is intended for within-regime retrospective auditing, with conservative uncertainty-aware evaluation when optimization reaches weak-support regions.
The mean response is decomposed as
\paragraph{Nominal saturation.}
\paragraph{Residual mean and variance.} \[ g_{i,e}(\cdot)\sim\mathcal{GP}(0,k_g), \qquad \log\sigma^2_{i,e}(\cdot)\sim\mathcal{GP}(m_\sigma,k_\sigma), \] with Mat\'ern$(2.5)$ kernels.
The two Gaussian processes serve distinct purposes. The mean GP $g_{i,e}$ captures systematic deviations from the nominal saturation curve, allowing flexible local curvature while preserving the interpretable global shape imposed by $\mu_{\mathrm{nom},i,e}$. The variance GP models heteroskedastic outcome dispersion as a function of spend, enabling uncertainty to increase in weak-support regions. Separating mean and variance components yields calibrated counterfactual uncertainty, which is essential for Monte Carlo regret estimation and detectability analysis.
\paragraph{Auxiliary regularization.} Neighboring-epoch samples are incorporated with exponential weights \[ w_t=\alpha_{\mathrm{aux}}\exp(-|d_t|/\tau), \] which is equivalent to treating auxiliary points as noisier observations. Core epoch data determine identification; auxiliary data provide weak curvature regularization under bounded drift.
\paragraph{Support-aware extrapolation.} For $s$ beyond the upper boundary of the core epoch's realized spend range, the fitted mean is projected onto the space of non-decreasing functions via boundary-anchored isotonic regression. For $s$ beyond the weighted realized range (core plus down-weighted auxiliary coverage), epistemic variance is inflated:
These regions are used only for conservative regret evaluation. Within the core realized range, monotonicity is not imposed; in practice, the posterior mean is typically monotone due to the dominance of the nominal saturation component and smooth GP regularization. Example of the constructed oracle functional forms are shown in Figure (ref).
Given the fitted epoch-wise response functions $\{\hat{\mu}_{i,e}(\cdot)\}_{i=1}^{K}$, we define an oracle allocation as the solution to a fixed objective evaluated over alternative feasible sets:
where $s_{e,i}$ denotes the spend assigned to asset $i$ in epoch $e$. The distinction between oracle variants arises solely from differences in the feasible set, which encodes alternative assumptions about operational realism.
The unconstrained oracle evaluates (ref) over the largest feasible set $\mathcal{B}_{\mathrm{unc}}$, defined only by budget accounting and asset-level bounds: \[ \mathcal{B}_{\mathrm{unc}} := \left\{ \mathbf{s} \;\middle|\; \sum_{e,i} s_{e,i} = B_{\mathrm{tot}},\; \underline{s}_i \le s_{e,i} \le \overline{s}_i \right\}. \]
This oracle represents a theoretical upper bound corresponding to perfect hindsight and unrestricted reallocation across epochs.
Unconstrained optimization may produce trajectories that are operationally implausible. To restore realism, we introduce a constrained family $\mathcal{B}_{\mathrm{con}}(\delta)\subset \mathcal{B}_{\mathrm{unc}}$ that limits how allocations may change across decision epochs. We impose epoch-to-epoch stability constraints:
where $\delta\in(0,1)$ encodes allowable relative changes.
The constrained oracle is defined as \[ \mathbf{s}^{\star}_{\mathrm{con}}(\delta) \in \arg\max_{\mathbf{s}\in\mathcal{B}_{\mathrm{con}}(\delta)} \sum_{e=1}^{E}\sum_{i=1}^{K}\hat{\mu}_{i,e}(s_{e,i}). \]
Oracle variants differ only through the feasible set $\mathcal{B}(\delta)$, where larger $\delta$ permits greater epoch-to-epoch reallocation. For the deterministic planning objective $\tilde R(\mathbf{s})$ in Step II, nested feasibility implies \[ \max_{\mathbf{s}\in\mathcal{B}(\delta_2)} \tilde R(\mathbf{s}) \;\ge\; \max_{\mathbf{s}\in\mathcal{B}(\delta_1)} \tilde R(\mathbf{s}), \quad \delta_2>\delta_1. \] Thus monotonicity holds for the deterministic planning objective, but not necessarily for uncertainty-aware empirical regret after posterior evaluation in Step III.
However, we report uncertainty-aware regret from Step III, where the chosen allocation $\mathbf{s}^\star(\delta)$ is evaluated under posterior predictive uncertainty. Larger $\delta$ may shift the optimizer toward weakly supported regions, increasing variance and occasionally reducing both $\mathbb{E}[\mathrm{Reg}(\delta)]$ and the detectability $\mathbb{P}(\mathrm{Reg}(\delta)>0)$. Thus operational lift need not be monotone in $\delta$, and empirical curves may exhibit saturation or dips.
Regret is random due to stochastic outcomes and uncertainty in the Step I response surfaces. For each stability level $\delta\in\Delta$ (and the unconstrained case), we first compute the oracle trajectory $\mathbf{s}^\star(\delta)$ by optimizing the plug-in mean responses from Step I over the feasible set from Step II. We then hold $\mathbf{s}^\star(\delta)$ fixed and propagate uncertainty via Monte Carlo to obtain a distribution over $\mathrm{Reg}(\delta)$. For each scenario we perform the following sampling steps:
We then select $\delta^\star$ via (ref) using these Monte Carlo estimates, including the $\varepsilon$-certificate, and report the regret distribution at $\delta^\star$ together with the summary metrics in Table (ref).
We evaluate the proposed retrospective regret framework using historical strategic allocation logs under operationally realistic feasibility constraints. All outcomes are reported as relative lift with respect to the realized allocation. For confidentiality, we omit portfolio composition, asset identities, absolute magnitudes, and the semantic meaning of evaluation horizons. Our goal is not to recover a ground-truth global optimum, but to assess whether the framework yields stable and decision-relevant retrospective diagnostics under realistic feasibility constraints. We address four questions:
We evaluate \(P=8\) portfolios across \(H=8\) decision horizons. For each portfolio--horizon pair, epoch-specific spend--return functions are estimated using the weighted monotone grey-box model (Section (ref)). Oracle allocations are computed once per feasibility specification and then held fixed. Uncertainty is introduced only at evaluation time via Monte Carlo propagation of outcome noise and model uncertainty. Figure (ref) shows lift distributions for representative portfolios across horizons under multiple feasibility settings. The distributions illustrate that regret is inherently distributional and that its dispersion varies across constraint levels.
RQ1--RQ3 findings. Across all portfolio--horizon pairs we observe:
Aggregate detectability. Table (ref) summarizes certification results across feasibility levels. For each \(\delta\) and confidence threshold \(\epsilon\), we report the fraction of portfolio--horizon pairs satisfying \(P(\mathrm{Reg}>0)\ge\epsilon\) and the mean lift among detectable pairs.
Three consistent patterns emerge. First, moderate thresholds (\(\epsilon\in\{0.5,0.6\}\)) frequently certify improvement. Second, stringent thresholds (\(\epsilon\ge0.8\)) substantially reduce detectability, reflecting broad regret distributions even when mean lift is positive. Third, increasing flexibility generally raises mean lift among detectable cases but does not guarantee monotone gains in detectability, consistent with uncertainty inflation beyond core empirical support. Taken together, these results suggest that the framework is most useful as an auditing tool for detecting recoverable opportunity cost under plausible reallocation limits, rather than for certifying large aggressive reallocations.
RQ4 evaluates the marginal benefit of relaxing the inter-epoch stability constraint $\delta$. For each $\delta$, we recompute the oracle allocation and estimate regret under the same Monte Carlo protocol, isolating the effect of flexibility alone.
Figure (ref) shows two regimes. Allowing moderate flexibility ($\pm20\%$ -- $\pm40\%$) yields large gains by correcting obvious misallocations and shifting spend toward well-supported, high-return regions. Beyond this, lift often saturates: once allocations approach local optima, additional movement mainly explores flatter or weakly supported regions where marginal returns are small and uncertainty is higher.
In some portfolios, lift continues to rise with $\delta$ when profitable regions remain farther from the realized allocation, so larger moves are still beneficial. However, greater flexibility typically increases variance, so detectability improves only selectively and can weaken at stringent confidence thresholds, as reflected in Table (ref). Overall, most gains are captured at moderate $\delta$, while extreme reallocations trade reliability for limited additional return.
We introduced a hindsight-regret framework for retrospective auditing of strategic budget allocation under operational constraints. The framework evaluates realized allocations against constraint-feasible hindsight benchmarks built from regime-specific response surfaces estimated from historical logs. Empirically, most recoverable gains are attained through moderate feasible reallocations, while more aggressive flexibility yields diminishing returns and higher uncertainty.
Future work will develop formal guarantees for response estimation, regret perturbation, and finite-sample Monte Carlo summaries. An important next step is a semi-synthetic benchmark with known response structure and oracle regret, which would enable direct recovery-based validation of the framework. We also plan to extend the same setup to policy-level retrospective scoreboarding of alternative allocation strategies within the same logged regime.