Source-linked AI summary
Reserve-Aware Contrast Certificates for Conservative Bandits with Uncertain Baselines
Qinchuan Cheng
TL;DR
When an incumbent is uncertain, separate reward bounds can charge for shared estimation error and obscure whether an action meets the baseline-relative constraint. Reserve-C4B certifies the contrast and refreshes accumulated decisions using updated confidence sets while preserving certified credit. Its experiments report lower fallback with coupling and further reductions with refresh, alongside an anytime conditional-mean safety guarantee.
Problem
With an uncertain incumbent, separately bounding candidate and baseline rewards can charge for shared estimation error and obscure the comparative safety decision.
Source: §1 · p. 1Method
Reserve-C4B uses a shared confidence set for the candidate–baseline contrast and a reserve ledger with prefix refresh and carry-forward credit.
Source: §1 · p. 1, §3.2 · p. 2Results
With diverse history, Contrast reduced fallback from 88.2% to 19.4% vs Separate, raised reward ratio by 0.0473, and Refresh reduced fallback to 0.5%.
Source: §4.2 · p. 4Takeaways & Limitations
Theorem 1 guarantees both ledgers anytime conditional-mean safety; shared certificates admit every action separate certificates admit at a fixed history and bank.
Source: §3.2 · p. 2, §3.1 · p. 2The study does not establish robustness to nonlinear rewards, drifting parameters, misspecified noise bounds, or live retail traffic, and comparisons use a fixed horizon.
Source: §4.2 · p. 4
Abstract
from arXiv · showhide
Conservative bandits must improve an incumbent policy without exhausting a prescribed performance budget. When the incumbent is uncertain, separately bounding candidate and baseline rewards can charge twice for shared estimation error. We develop Reserve-C4B around the baseline-relative contrast itself. A shared confidence set yields an exact expression for this avoidable penalty and a tighter admissibility test at every fixed history. A reserve ledger separates statistical evidence from permitted performance deficit; a prefix-refresh extension recertifies accumulated decisions under the current confidence set without discarding previously certified credit. For linear rewards, self-normalized confidence sets provide simultaneous validity over time and adaptively generated candidates, and the resulting policy satisfies a conditional-mean performance constraint with high probability. Reproducible experiments isolate certificate coupling, prefix refresh, and historical information, showing large reductions in baseline fallback while exposing the limitations of frozen certificates.
1. INTRODUCTION
With an uncertain incumbent, separately estimating candidate and baseline rewards can obscure shared estimation error and impose an avoidable penalty. Reserve-C4B certifies the baseline-relative contrast and tracks permitted deficit separately from statistical evidence.
1. INTRODUCTION
- For identical actions with reward interval [ℓ, U], separate bounds can yield a negative comparison despite ℓ > 0; the contrast certificate instead gives αℓ.The avoidable penalty is (1−α)(U−ℓ); aligned estimation errors can create the same issue for nonidentical actions.Source: §1 · p. 1
- A larger initial reserve can postpone rejection, but it neither removes the decoupling penalty nor validates an incorrect certificate.Source: §1 · p. 1
- Reserve-C4B uses one confidence set for the candidate–baseline contrast, quantifies the cost of decoupling, and spends only certified credit.Prefix refresh recertifies executed decisions as information improves while a carry-forward bound preserves previously established credit.Source: §1 · p. 1
- Prior work treats unknown baselines and shared-model policy comparisons; this paper adds contrast-first certificates, a carry/refresh ledger with an anytime safety proof, and matched ablations.The target is the realized action sequence’s cumulative conditional means, unlike time-uniform off-policy evaluation for gated deployment.Source: §1 · p. 1
2. DECISION SETTING AND STATISTICAL EVIDENCE
The setting uses sequential linear rewards with an unknown baseline and an externally specified reserve. Self-normalized confidence sets cover the parameter over time, including for adaptively generated candidate actions.
2. DECISION SETTING AND STATISTICAL EVIDENCE
- Before each reward, the learner observes a finite candidate set, a baseline, and predictable feature vectors; only the selected reward is observed.Source: §2 · p. 1
- The linear model assumes a fixed bounded parameter, bounded predictable features, and conditionally zero-mean sub-Gaussian noise; the baseline mean is unknown but nonnegative.Source: §2 · p. 1
- An external reserve R0 permits an additive deficit; R0 = 0 recovers the strict cumulative conservative constraint, and the reserve is not statistical confidence.The constraint concerns cumulative conditional means, not every noisy realized-reward path; historical training observations improve estimation but receive no deployment budget credit.Source: §2 · p. 2
- The self-normalized confidence event holds simultaneously over time and covers every predictable candidate, even with a generator dependent on past observations.No union bound over pool size is required; marginal prediction coverage for future outcomes does not replace this conditional-mean guarantee.Source: §2 · p. 2
3. CONTRAST CERTIFICATES AND RESERVE LEDGERS
The section quantifies the avoidable cost of separately bounding candidate and baseline rewards, then develops reserve ledgers that preserve certified credit and can refresh past decisions as uncertainty changes.
3.1. The cost of independent uncertainty bounds
- At the baseline, separate bounds incur a penalty of c(U_t(b_t)−ℓ_t(b_t)); shared certificates admit every separately admissible action at the same history and bank.This fixed-history admissibility result does not imply reward dominance when policies subsequently collect different data; rejecting the baseline with the separate formula is an avoidable implementation error.Source: §3.1 · p. 2
3.2. Carry-forward and prefix refresh
- Prefix refresh recertifies accumulated decisions with newly available evidence and carries forward the maximum of refreshed and prior credit, since confidence sets need not be nested.Refresh uses evidence, not unearned reward credit, and addresses the cost of freezing early certificates rather than simply increasing the initial reserve.Source: §3.2 · p. 2, §3.3 · p. 3
- Both ledgers satisfy D_t≥B_t≥0 at every deployment round with probability at least 1−δ, including adaptively chosen candidates covered by one parameter-containment event.Without a certified nonnegative fallback, the policy must stop when no action qualifies.Source: §3.2 · p. 2
3.3. How much reserve does decoupling consume?
- Decoupling can consume an entire exploration allowance in certificate-level reserve, which an online policy cannot know in advance; prefix refresh changes the ledger to address frozen-certificate costs.The reserve comparison is certificate-level, not a reserve requirement that an online policy can know in advance.Source: §3.3 · p. 3
4. EXPERIMENTS
The experiments compare contrast certificates and prefix refresh in a controlled linear-bandit study, varying reserve and historical information. Contrast and refresh reduce fallback, while baseline-only histories expose the cost of frozen certificates.
4.1. Reproducible protocol and comparisons
- The study tests 36 settings across three candidate radii, two noise levels, three reserves, and two history types, using 256 paired episodes per setting.Each episode has 20 historical observations and 200 deployment rounds; the study uses a controlled linear model with 32 candidates per round.Source: §4.1 · p. 3
4.2. What coupling and refresh change
- With diverse history, Contrast cuts fallback from 88.2% to 19.4% versus Separate, raises reward ratio by 0.0473, and Refresh reduces fallback to 0.5%.The paired 95% interval for the reward-ratio increase is 0.0456–0.0490; Figure 1 shows the reduction is sustained throughout deployment.Source: Table 1 · p. 3, Figure 1 · p. 3, §4.2 · p. 4
- With baseline-only history, Refresh reduces fallback from Contrast’s 91.8% to 12.1%, with reward ratios of 1.0190 versus 1.0011 for Revalue-F.Refresh’s paired reward gain over Revalue-F is 0.0179 (95% interval: 0.0169–0.0190).Source: §4.2 · p. 4
- Refresh improves on the frozen contrast ledger in every displayed Table 2 setting, while its gap to LinUCB grows with baseline-only history and wider candidate variation.Revalue-F need not outperform Revalue on reward because the expanded admissible choice set can change collected data.Source: §4.2 · p. 4, Table 2 · p. 4
- All five gated variants had zero conditional-mean prefix violations in tested settings, but the study does not establish robustness to nonlinear rewards, drifting parameters, misspecified noise bounds, or live retail traffic.Zero failures in 256 episodes imply a one-sided 95% binomial upper bound of 1.16% for one fixed setting, not a simultaneous guarantee across the grid.Source: §4.2 · p. 4
5. CONCLUSION
The conclusion presents shared contrast certificates and prefix refresh as a reserve-aware filter with an anytime conditional-mean guarantee and reduced fallback.
5. CONCLUSION
- Shared contrast certificates remove a quantifiable uncertainty penalty, while prefix refresh prevents early pessimism from becoming permanent budget debt.Together they yield an anytime conditional-mean guarantee and measurable fallback reductions under a reproducible linear model.Source: §5 · p. 4