BanditLP pairs neural Thompson Sampling with a billion-variable LP solver to deliver constrained contextual bandits at web scale, improving performance on benchmarks and driving a documented business uplift in LinkedIn's email marketing.

Main Finding

BanditLP is a practical, scalable method that combines neural Thompson sampling (neural TS) with a large-scale linear program (LP) to solve multi-stakeholder contextual bandit problems under per-round, provider-level, and platform-level constraints. It preserves exploration (via neural TS) while enforcing complex, multi-level operational and fairness constraints at serving time (via an LP solver capable of billions of variables). Experiments (public benchmarks, synthetic data) and an online A/B deployment in LinkedIn’s email marketing system show consistent gains over strong baselines and business improvements sufficient for production.

Key Points

• Problem addressed

  • Real-world recommendation systems need to optimize a primary objective (e.g., revenue, conversions) while satisfying multiple, possibly conflicting constraints for users, providers (business lines, sellers), and platform-level safety/volume caps.
  • Constraints must often hold per-round (not only in aggregate), and scale (U users × I items/campaigns) can produce tens of billions of decision variables.

• Method (BanditLP)

  • Two-stage architecture:
  • Estimate rewards and multiple cost signals with Bayesian neural networks and use neural Thompson sampling (Laplace / linearized Laplace approximation) to draw stochastic samples of rewards/costs per (user, item) context.
  • Solve a constrained optimization subroutine (an LP or slightly perturbed QP) each round using the Thompson-sampled values to produce a probability x_{u,i,t} of selecting item i for user u this round; sample actions according to x.
  • Constraints handled include:
    • Platform-level (global caps e.g., total unsubscriptions)
    • Provider-level (minimum/maximum exposure per cohort/business line)
    • User-level (per-user frequency caps)
  • Application-agnostic and modular: prediction model and LP are decoupled; any neural architecture can be used for estimation.

• Scalability & engineering

  • Neural TS uses Laplace (linearized Laplace approximation, LLA) to obtain a Gaussian posterior predictive distribution. Practical posterior approximations use low-dimensional subspace (e.g., last few layers) to make inversion tractable.
  • Large-scale LP solved with DuaLip (LinkedIn’s solver), which:
    • Solves a regularized QP (objective plus ½ γ x^T x) and optimizes the dual via first-order methods and parallel projections.
    • Chooses γ to trade speed vs precision; for small γ solutions match LP.
  • Production considerations: probability calibration, tuning temperature τ controlling exploration, monitoring realized exploration (proposed overlap-at-K metric), and techniques to avoid data leakage/dilution in online experiments.

• Empirical claims

  • BanditLP outperforms strong baselines on public benchmarks and synthetic datasets.
  • Deployed in LinkedIn email marketing: reward modeled as conversion × LTV, cost=unsubscribe; constraints include global unsubscribe cap, minimum sends for B2B/B2C campaigns, per-member weekly caps. Online A/B tests showed significant multi-objective business improvements and led to production rollout.

Data & Methods

• Modeling and uncertainty

  • Bayesian neural networks trained with MAP estimates; uncertainty via linearized Laplace approximation (LLA) yields Gaussian posterior on the network output’s linearization: μ(z) ~ N(f_{θ_MAP}(z), τ V).
  • Posterior covariance uses Gauss–Newton/Hessian approximations. Full Hessian too large; practical approximations:
    • Use top-k eigenpairs, diagonal approximations, or sub-network (common: last layers) approximations to form a tractable Ω and its inverse.
  • For binary outcomes, predictive probability P(r=1|z) = σ(μ(z)). For numeric rewards/costs, Gaussian predictive posterior is used.
  • Thompson sampling: sample of reward and cost signals from the posterior predictive distribution is fed to LP.

• Optimization (per-round LP/QP)

  • Per-round optimization variable x has dimension U×I (probability of selecting each item for each user).
  • LP is: maximize ∑{u,i} x{u,i,t} b_r_{u,i,t} subject to linear constraints D x ≤ b and box constraints 0≤x≤1. b_r and b_c are Thompson samples for reward and cost signals.
  • DuaLip approach: add small quadratic regularization (γ), dualize constraints, and solve the dual with scalable first-order parallel methods to handle billions of variables. For sufficiently small γ, solution approximates LP.
  • After solving for x, sample actual actions per user from these probabilities and collect feedback; update neural models.

• Tuning, monitoring, and calibration

  • Temperature τ scales posterior covariance and controls exploration; effect interacts nonlinearly with downstream LP constraints.
  • Overlap-at-K metric proposed to measure realized divergence between TS-based recommendations and greedy (exploit-only) recommendations.
  • Probability calibration applied to TS outputs before feeding LP to align estimated probabilities with empirical rates.
  • Practical deployment requires careful monitoring of exploration intensity, solver regularization γ (speed/precision), and experiment design to prevent leakage.

• Application specifics (LinkedIn email marketing)

  • Reward per send estimated as conversion probability × LTV. Unsubscription estimated as a cost signal.
  • Constraints: weekly total unsubscriptions ≤ C_unsub; minimum sends to B2B/B2C campaigns ≥ C_2B/C_2C; per-user max sends ≤ C_fcap.
  • Action space size = #members × #campaigns → tens of billions of LP variables; solved weekly via DuaLip.

Implications for AI Economics

• Multi-stakeholder welfare optimization at scale

  • BanditLP operationalizes a structured way to optimize platform decisions for aggregate economic objectives (revenue, LTV) while enforcing cross-stakeholder protections (fair exposure, minimum campaign quotas, user safety caps). This enables platforms to encode complex policy trade-offs directly into the decision layer rather than relying solely on scalarized objectives.

• Mitigating feedback loops and selection bias

  • Integrating exploration via neural TS helps reduce the “rich-get-richer” feedback loop endemic in purely supervised recommenders by systematically probing uncertain items/users. That can improve long-term welfare, reduce allocation inefficiencies, and reveal latent value (e.g., under-exposed providers).

• Operationalizing constraints as hard policy instruments

  • The LP layer provides a transparent mechanism to impose enforceable constraints (e.g., minimum exposure for small providers, maximum user contact frequency). From an economic governance perspective, this makes it easier to implement fairness, competition, and consumer-protection policies in algorithmic allocation.

• Trade-offs and costs

  • Computation and monitoring overheads are nontrivial: Bayesian uncertainty estimation, calibrations, and solving very large LPs increase engineering cost. There is a policy/design trade-off between strictness of constraints and achievable surplus; solver regularization (γ) and exploration temperature (τ) materially affect realized allocations.
  • Enforced per-round constraints can reduce short-run expected reward relative to unconstrained exploitation; however, BanditLP helps recover long-run gains via exploration.

• Strategic and market effects

  • When providers (sellers, campaign owners) are strategically aware of constraints/exploration, they could change behavior (bidding, campaign creation) in response. Platforms should consider strategic incentives when specifying constraints (e.g., minimum exposure quotas) to avoid gaming or inefficiencies.
  • The modular architecture enables experiments with different resource allocations, enabling empirical evaluation of policy interventions (e.g., increasing minimum exposure for minority providers) and measuring their economic impact.

• Experimental design and causal inference

  • The authors emphasize careful online experiment design to avoid dilution and leakage when comparing explore-enabled policies to exploit-only baselines. Proper causal evaluation is crucial to quantify economic trade-offs and long-term impacts; BanditLP’s framework facilitates controlled tests of allocation policies.

• Broader applicability

  • The approach generalizes to marketplaces, ad allocation, content platforms, and any setting where (i) outcomes are high-dimensional and nonlinear (suitable for neural models), (ii) multiple stakeholders have hard constraints, and (iii) decisions must be made at massive scale. For AI economists, BanditLP offers a toolbox to study allocation rules, dynamic exploration-exploitation trade-offs, and constrained welfare optimization in operational platforms.

Limitations / points for further research - Theoretical regret guarantees in this highly general, constrained, neural-setting are not provided; most claims are empirical and engineering-focused. - The quality of uncertainty estimates from LLA and subspace approximations (last-layer) can affect TS behavior; misspecification risks remain. - Strategic responses by providers and long-run equilibrium effects of enforced constraints merit formal economic analysis.

Overall, BanditLP presents a production-ready, empirically validated approach to reconcile exploration with multi-level constraints at web scale—an important toolkit advance for platforms that must balance competing economic objectives across stakeholders.