Conservative bandits improve uncertain policies with shared confidence
Reserve-Aware Contrast Certificates for Conservative Bandits with Uncertain Baselines
Artificial IntelligenceMachine Learning
Summary
Sometimes computers try to improve a current strategy without making it worse by too much. But if they aren’t sure how good the old strategy really is, they can make mistakes by being too cautious. The authors figured out a better way to measure the difference between new ideas and the old one, using shared information to avoid paying twice for the same uncertainty. This method helps computers decide when it’s safe to try improvements while keeping risks low.
What this means in practice
- •For online recommendation teams: Manage exploration of new options in recommendations while keeping user experience close to current standards despite uncertain baseline outcomes.
- •For adaptive clinical trial designers: Safely test improved treatment policies without exceeding acceptable risk when historical patient outcomes are uncertain.
Authors
Qinchuan Cheng
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.