Reserve-Aware Contrast Certificates for Conservative Bandits with Uncertain Baselines

arXiv:2609.39106v1 Announce Type: new Abstract: 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.

Related

• Learning When to Trust in Contextual Social Bandits
• VStress: Correlation-Aware Auditing and Adaptive Budget Allocation for Repeated Verifiers
• Exploit More, Explore Smarter for Budget-Constrained Agentic Search
• Nice Fold or Hero Call: Learning Budget-Efficient Thinking under Policy-Dependent Solvability

Source: arXiv cs.AI | 2026-10-01