PaperlayerView exact revision on arXiv

Source-linked AI summary

Gated Decoupled Compositional Bandits: A Unified Theory of Contextual Bandits with Supervised-Calibrated Action Scaling and Pre-Execution Gating

Oleg Miroshnichenko

arXiv:2608.21993v1cs.LG

TL;DR

The paper addresses the lack of a common framework for systems combining bandit-selected nominal arms, supervised context scaling, and pre-execution gating. It formalises GDCB, proves structural results, and maps six industrial systems into the framework. Its principal supported result is that stationary gates make historical data valid for warm-up without importance-sampling correction, while empirical validation is currently reported only for STR pricing.

  • Problem

    Six high-stakes systems share an architecture but are treated as distinct algorithmic instances without a common theoretical framework in the bandit literature.

  • Method

    GDCB formalises compositional actions with a separately supervised scaler and pre-execution gate, then derives structural theorems and instantiates the framework across six systems.

  • Results

    A stationary gate makes historical data valid warm-up without importance-sampling correction; the companion paper empirically validates STR pricing on real production data.

  • Takeaways & Limitations

    Approval, compliance, safety, and moderation gates can support rapid bandit deployment by enabling off-policy warm-up from existing decision logs.

  • Takeaways & Limitations

    Instances using neural scalers receive theoretical guarantees only under restricted settings, and instances #2–#6 remain proposed future empirical work.

Abstract

from arXiv · show

We introduce Gated Decoupled Compositional Bandits (GDCB), a family of contextual bandit algorithms with three structural innovations that jointly fall outside the taxonomy of LinUCB, LinTS, HierTS, factored bandits, neural contextual bandits, and RLHF. In a GDCB system: (i) the action delivered to the environment is the composition of a nominal arm, drawn by a discrete or hierarchical bandit, with a context-dependent scaler; (ii) the scaler parameter is learned in a separate supervised loop, not jointly with arm selection; and (iii) every action passes through a pre-execution gate that may modify or veto the composed action before it reaches the environment. We formalise this class of algorithms, prove four structural theorems characterising its statistical behaviour, and show that six industrially significant systems -- short-term rental dynamic pricing, clinical drug dosing, credit origination, grid demand response, content moderation, and LLM tool-use agents -- are all instances of GDCB, differing only in the composition operator, scaler family, and gate. The central result is the Decoupling Variance Reduction theorem: a well-calibrated scaler removes context-induced variance from the arm-to-reward mapping, turning a non-stationary bandit problem into an approximately stationary one. The Gate-Induced Equivalence theorem shows that under a stationary gate, historical data collected under any prior policy is a valid warm-up initialiser without importance-sampling correction, generalising the companion P-HITL result (arXiv:2606.02595) from human approval to arbitrary gates. In regulated, high-stakes domains, constraints usually treated as deployment frictions -- approval gates, compliance rules, safety shields -- are the mechanism that makes fast deployment possible, not an obstacle to it. The companion paper validates instance 1 (STR dynamic pricing) on real production data.

1 Introduction

GDCB formalises a shared architecture across six high-stakes applications: a bandit-selected nominal arm is scaled using supervised context calibration, then accepted, modified, or vetoed by a pre-execution gate. The framework distinguishes this structure from existing contextual, factored, hierarchical, safe-RL, and human-feedback approaches.

  • Shared architecture: Six systems share a three-component architecture comprising a nominal arm space, a supervised context scaler, and a pre-execution gate.The systems span STR pricing, clinical dosing, credit origination, grid demand response, content moderation, and LLM tool use.
  • Shared architecture: The nominal arm is sampled by a bandit, while the scaler is calibrated separately from arm selection using supervised methods.The composition operator combines the sampled arm with the scaler output before gating.
  • Shared architecture: The pre-execution gate may accept, modify, or veto the composed action before it reaches the environment.Examples include physician approval, compliance rules, safety shields, and moderator review.
  • Gap in existing taxonomy: Existing contextual and compositional bandit methods do not model the separate supervised scaler and gate together, while safe RL and RLHF capture only parts of the architecture.LinUCB and LinTS learn context and arm preferences jointly; factored and combinatorial bandits choose all factors through the bandit; RLHF evaluates outcomes after execution.
  • Contributions: GDCB formalises four structural theorems and an instantiation theorem covering six industrial systems through distinct choices of composition operator, scaler, and gate.The framework also provides a unified evaluation protocol and treats the companion P-HITL work as its first empirical instantiation.
  • Gate and warm-up: A stationary pre-execution gate makes historical data valid for warm-up without importance-sampling correction, extending the framework beyond human approval.The framework presents hard safety filters as a special case of this gated setting.

2. Bandit B samples nominal arm anom

GDCB separates nominal-arm selection from supervised scaling and pre-execution gating, then characterizes the resulting system through structural theorems and an STR instantiation. The theory links calibration to reduced context variance, stationary-gate data reuse, additive regret, and compressed cold starts.

  • Architecture: The bandit and supervised module share only outcomes while updating disjoint parameter sets through distinct algorithms.This separation underlies the sample-complexity lifting result.
  • Architecture: GDCB combines a nominal arm, a supervised context-dependent scaler, a composition operator, and a pre-execution gate.The STR instantiation uses a 25-arm factored grid, multiplicative scaling, and revenue-manager approval.
  • Decoupling variance reduction: A perfectly calibrated scaler reduces context-induced arm-value variance, yielding approximately stationary arm rewards and stationary-rate Thompson-sampling regret O(√KT log T).The P-HITL instantiation reports cold-start compression from 150 to 30 episodes.
  • Gate-induced equivalence: Under an idempotent stationary gate, historical executed-action distributions match live distributions, making historical tuples valid on-policy warm-up data without importance sampling.The result specializes to human approval, safety shields, and compliance rules.
  • Regret decomposition: GDCB regret decomposes additively into arm-selection, scaler-calibration, and gate-misalignment components.The gate term is bounded by O(T · P[override] · override-suboptimality), enabling diagnosis by dominant component.
  • Sample-complexity lifting: Simultaneous ε-optimality requires max(Nbandit(ε), Nsup(ε)) episodes, while valid historical data reduces effective cold start for both loops.The STR specialization uses 1,461 historical nightly episodes and compresses cold start from approximately 150 to approximately 30 episodes.

5 Instantiation Theorem

The instantiation theorem maps six industrial systems to GDCB by varying the composition operator, supervised scaler, gate, and reward structure. A separate Kalman-contextual instance extends the framework under additional assumptions and supports triple cold-start reuse, while endogenous-context feedback remains unresolved.

  • 5.1 Statement: Each of the six systems in Table 2 is obtained from GDCB by choosing distinct values of (A, ∆, Φ, δθ, g, R).The theorem states that structural Theorems 1–4 specialise to known or expected empirical results in each domain.
  • 5.1 Statement: The six domains were selected for diversity in composition operators and gate types, exercising the widest range of gate mechanisms.The listed gates include human approval, safety bounds, compliance rules, physics constraints, and policy filters.
  • 5.2 GDCB taxonomy: where existing algorithms live: Figure 5 places GDCB and existing algorithms in a three-dimensional space defined by composition, scaler, and gate complexity.The GDCB region is described as under-explored, with six instances occupying distinct cells.
  • 5.3 Specialisation of Theorems 1–4 across instances: Figure 6 specifies each instance’s nominal arm space, composition operator, supervised scaler, pre-execution gate, and reward signal.Across the six rows, composition includes multiplication, addition, identity, and prompt-composition, while gates include human, safety, compliance, and retrieval mechanisms.
  • 5.4 A structurally distinct instance: adaptive Kalman filtering: The Kalman-contextual instance uses filtered state estimates as contexts and models a mode-conditioned covariance scaler, steady-state Kalman gain, and deployment-specific approval operator.Its scaler range is restricted to a compact positive-definite set, with detectability, stabilisability, and ridge-regularisation assumptions.
  • 5.4 A structurally distinct instance: adaptive Kalman filtering: The Kalman embedding satisfies the GDCB assumptions and therefore falls within Theorems 4.1–4.8, but endogenous-context feedback is not analysed as a closed-loop compounding benefit.The feedback’s empirical effect is reported as non-compounding across four domains and at best additive.
  • 5.4 A structurally distinct instance: adaptive Kalman filtering: One historical dataset can support bandit posterior, covariance-regression, and filter-initialisation warm-up when covariances remain at fixed defaults.The sequential estimator splits the historical innovations to avoid circularity between estimating R and P0; consistency requires stationary ergodic innovations and calibration-window validity.
  • 5.4 A structurally distinct instance: adaptive Kalman filtering: The sequential estimator is consistent, but not unbiased in finite samples; without full column rank of H, only the identifiable restriction of P0 converges.The complement retains the prior, and nonlinear eigenvalue projections explain why consistency does not imply unbiasedness.

6 Experimental Protocol Template

The protocol template evaluates GDCB against bandit, hierarchical, and RLHF baselines using regret, threshold, gate, decomposition, and cold-start measures. The reported P-HITL instantiation demonstrates cold-start compression and early cumulative-regret advantage, while the replication uses calibrated market contexts.

  • 6 Experimental Protocol Template: The proposed protocol evaluates any GDCB instance against natural baselines and reports algorithm specification, theorem specialisation, empirical results, and ablations.The reporting standard covers baselines B0–B4 and ablations A1–A4.
  • 6.1 Baselines: The baselines include pure-online MAB, LinTS, HierTS, instantiated GDCB, and RLHF-alone.They respectively vary context use, joint versus hierarchical learning, the three-component architecture, and human-feedback dependence.
  • 6.2 Metrics: The primary metrics are cumulative regret, episodes-to-threshold, per-component regret decomposition, gate override rate, and cold-start compression.These metrics quantify learning speed, component contributions, intervention frequency, and warm-start value.
  • 6.3 Ablations: The ablations turn off the gate, warm-up, or arm factoring to measure operator-override, historical-reuse, and decomposition effects.The listed ablations isolate the gate, cold-start, and flat-versus-factored arm-space contributions.
  • 6.4 Reporting standard: The P-HITL instantiation reports cold-start compression from ∼150 to ∼30 booked episodes, cumulative-regret advantage from episode 1, and no importance-sampling correction.These results are reported across all six HF-TS benchmark agents in the companion paper.
  • 6.4 Reporting standard: The synthetic replication calibrates occupancy contexts from 38 648 weekly OTA KPI observations across 1 000 Vail listings, replacing a hand-tuned prior with a real-market distribution.The calibrated distribution has mean = 0.537 rather than mean = 0.42.
  • 6.4 Reporting standard: Under calibrated contexts, HITL < Cold start < Standard OPE across all 200 episodes, with HITL saving 11.7% cumulative regret versus cold start at episode 50.The ordering and episode-50 comparison are reported for the synthetic replication.

7 Open Problems and Future Work

The paper identifies open problems involving gate drift, adaptive neural scalers, multiple gates, online scaler updates, causal interpretation, and spectral preprocessing. These gaps limit direct extension beyond stationary gates, identifiable scalers, and the current batch-calibrated settings.

  • 7 Open Problems and Future Work: Gate drift is outside the current theory because all four theorems assume stationarity; a switching-gate regret bound remains open.Examples include changing operators, updated compliance rules, and tightened safety thresholds.
  • 7 Open Problems and Future Work: Neural scaler families may violate identifiability, and a weaker variance-reduction theorem or PAC-Bayes treatment is conjectured but undeveloped.This issue concerns instances using neural scalers.
  • 7 Open Problems and Future Work: Composed multi-gate systems are admitted as g = g3 ◦ g2 ◦ g1, but the equivalence theorem requires simultaneous stationarity and per-gate decomposition remains open.The motivating sequence is safety shield, compliance rule, then human approval.
  • 7 Open Problems and Future Work: The STR implementation updates its scaler monthly by batch regression, leaving two-timescale analysis for incremental ridge, recursive GP, and other online variants open.Online updates are proposed as a way to potentially improve Rcal.
  • 7 Open Problems and Future Work: The scaler is presented as admitting a causal interpretation, but its connection to causal bandits is identified as promising future work rather than developed theory.The stated interpretation concerns the conditional treatment effect of context on the reward surface absent the bandit.
  • 7 Open Problems and Future Work: Innovation sequences used for covariance fitting can contain periodic structure that should not be absorbed into R, motivating spectral pre-filtering before covariance regression.The companion pipeline targets engine harmonics, sensor rotation rates, and circadian or calendar cycles across six domains.

8 Limitations •

The framework’s scope is constrained by assumptions on action spaces, reward structure, gate behavior, and scaler models, while its practical motivation is strongest in high-context-variance settings. Its contribution is a unified GDCB framework with structural theorems and one reported empirical validation.

  • GDCB restricts nominal arms to finite or parameterised spaces; continuous-arm variants require GP bandits.
  • The theory assumes scalar rewards, while multi-objective GDCB requires a vector-valued regret decomposition.
  • The Gate-Induced Equivalence equality requires idempotent gates; non-idempotent gates satisfy the theorem only up to a mixing factor.
  • Neural scalers used in instances #4–#6 receive theoretical guarantees only in restricted settings under Assumption 3.
  • Decoupled calibration offers little gain when context distributions are narrow or arm-to-reward mappings are nearly context-independent, whereas high context variance favors decoupling.The framework identifies STR pricing, clinical dosing, and credit origination as examples where scalers absorb substantial context-induced variation.
  • A historical-data diagnostic recommends GDCB strongly when the context-induced-to-intrinsic variance ratio exceeds approximately 1.0; below approximately 0.1, benefits are marginal.
  • The paper introduces GDCB’s compositional actions, decoupled supervised calibration, and pre-execution gating, formalised through four structural theorems.
  • The companion paper empirically validates instance #1 on 1 461 real short-term rental pricing episodes, while instances #2–#6 remain proposed future empirical work.

A Formal Proofs

The proofs establish variance reduction through supervised calibration and policy-independent warm-up through stationary gating. The latter relies on executed-action equivalence, with idempotency and proposal-class conditions determining its scope.

  • A.1 Proof of Theorem 4.1 (Decoupling Variance Reduction): Theorem 4.1 begins by decomposing the calibrated composed signal into an oracle term and a scaler-estimation perturbation.
  • A.1 Proof of Theorem 4.1 (Decoupling Variance Reduction): Lipschitz assumptions bound the perturbation, after which variance expansion and Cauchy–Schwarz control its contribution.
  • A.1 Proof of Theorem 4.1 (Decoupling Variance Reduction): Under scaler realisability, calibration absorbs context variation and leaves only residual reward noise in the per-arm empirical mean.
  • A.2 Proof of Theorem 4.3 (Gate-Induced Equivalence): The Gate-Induced Equivalence proof models actions as proposals passed through a gate and uses idempotency to ensure feasible actions remain unchanged.
  • A.2 Proof of Theorem 4.3 (Gate-Induced Equivalence): For deterministic idempotent gates, proposals collapse into equivalence classes, so executed actions depend on class-aggregated proposal mass rather than within-class details.
  • A.2 Proof of Theorem 4.3 (Gate-Induced Equivalence): Stochastic gates require stationarity plus proposal-class invariance between historical and live policies.
  • A.2 Proof of Theorem 4.3 (Gate-Induced Equivalence): Under these conditions, historical and live policies induce the same executed-action marginal for every context and feasible-action set.
  • A.2 Proof of Theorem 4.3 (Gate-Induced Equivalence): Because posterior updates depend on executed-action marginals, historical posteriors provide valid warm-up without importance-sampling correction.

A.3 Proof of Theorem 4.7 (Regret Decomposition)

The regret proof constructs intermediate executable benchmarks that isolate arm selection, scaler estimation, and gate override. It then bounds these components separately, making each design lever interpretable.

  • The proof defines intermediate benchmarks that successively introduce arm sub-optimality, scaler estimation error, and gate override.
  • The gate term captures conditional override sub-optimality between the no-gate executable and the actually executed action.
  • Regret telescopes additively across the benchmark sequence, separating the contributions of the three imperfections.
  • The bandit term fixes the scaler at its oracle value and removes the gate, reducing the arm-selection problem to a K-armed Thompson-sampling instance with sub-Gaussian rewards.
  • The calibration term measures the discrepancy between oracle and fitted scalers under a Lipschitz reward map.
  • The resulting regret components are controlled independently by exploration breadth, supervised-data quantity, and gate-policy quality.

A.4 Proof of Theorem 4.8 (Sample-Complexity Lifting)

The sample-complexity proof treats arm values and scaler parameters as separate estimation blocks in the GDCB data-generating process. Conditional independence yields block-diagonal information and decoupled covariance bounds.

  • The proof combines the blockwise information argument with Theorem 4.3 to obtain dual cold-start compression.
  • The proof formulates joint estimation over nominal-arm values and scaler parameters using context, proposal, gate, executable, and reward observations.
  • Conjugate-exponential-family arguments identify sufficient statistics separately for bandit arm values and supervised scaler parameters.
  • The bandit posterior and scaler estimator are conditionally independent given observed rewards and inputs because their update kernels use separate information channels.
  • The GDCB graph has no active path between the two estimators after conditioning on rewards and observed inputs, establishing the required separation.
  • The Fisher information matrix has an additive block structure, with the off-diagonal block vanishing under conditional independence.
  • The Cramér–Rao lower bound therefore decomposes the covariance bound into separate arm-value and scaler-parameter blocks.

Step 5: Cramér–Rao and decoupled

The shared data stream lets the bandit and supervised scaler loops reach their targets in parallel, while GDCB’s structural separation yields decoupled information and rates. Historical data can warm-start both loops without importance-sampling correction.

  • Decoupled rates: The bandit and scaler estimators have no cross-contamination term, so uncertainty in one block does not inflate the other block’s asymptotic variance.Each estimator achieves its own rate under the decoupled structure.
  • Decoupled rates: Each estimator receives every live observation, so the joint ε-optimality sample requirement is max(Nbandit(ε), Nsup(ε)), not their sum.Summing the two requirements double-counts shared observations.
  • Cold-start compression: Historical tuples have the same conditional distribution as live tuples, allowing both loops to consume them without importance-sampling correction.The construction reduces required live observations by Nhist for each loop simultaneously.
  • Architectural dependence: GDCB’s conditional independence creates a block-diagonal Fisher information matrix and produces the decoupled rates.This separation is specific to the architecture rather than a generic property of two-loop estimation.

A.5 Proof of Lemma 5.3 (Kalman embedding)

The Kalman embedding establishes the required regularity by controlling the Riccati map, its gain, and the supervised scaler objective. Contraction prevents error bounds from deteriorating with the time horizon.

  • Kalman regularity: The one-step Riccati recursion and gain use matrix products plus one inversion of S(P, R) = HPH⊤+R.The gain is K(P, R) := PH⊤(HPH⊤+R)−1.
  • Kalman regularity: Uniform detectability and stabilisability make the Riccati map a strict contraction with horizon-independent modulus, avoiding bounds that grow exponentially with time.The contraction yields a bound uniform in the horizon.
  • Kalman regularity: The gain K(P, R) is Lipschitz in covariance parameters because its matrix factors and inverse are uniformly bounded and Lipschitz.Composing gain continuity with Riccati contraction establishes the required composition regularity.
  • Scaler identifiability: Ridge regularization makes the supervised loss strictly convex, so the scaler minimizer is unique without requiring X to have full rank.The Hessian is bounded below by 2λI for λ > 0.

A.6 Proof of Corollary 5.5 and Proposition 5.6

The proofs show that historical and live regimes match under fixed filter parameters, while split-sample covariance estimation removes circular dependence. Recovery is exact only in observable state directions.

  • Corollary 5.5: Historical and live contexts, executed actions, and innovations have matching conditional laws under fixed (Q0, R0), so historical data support live-distribution fitting.The ridge scaler fit is therefore based on a sample from the live distribution.
  • Proposition 5.6: The calibration segment consistently identifies R, with the eigenvalue floor becoming asymptotically inactive under the positive-definiteness assumption.The estimator satisfies R̂ → R almost surely.
  • Proposition 5.6: Disjoint calibration and fitting segments make Cov( R̂, bS) approach zero, preventing shared-sample errors from compressing the covariance difference.Under correct specification the covariance is exactly zero for any split; under misspecification it is asymptotically zero.
  • Scope of recovery: Full column rank of H yields exact recovery of P0; otherwise the estimator recovers only the row-space component and retains the prior on ker(H).Innovations contain no information about state-error components unobserved through H.
Loading 2608.21993v1…