use std::collections::VecDeque;
use serde::{Deserialize, Serialize};
const LAMBDA_GRID: [f64; 18] = [
0.05, 0.10, 0.15, 0.20, 0.25, 0.30, 0.35, 0.40, 0.45, 0.50, 0.55, 0.60, 0.65, 0.70, 0.75, 0.80,
0.85, 0.90,
];
pub const DEFAULT_MARGIN: f64 = 0.05;
pub const DEFAULT_ALPHA: f64 = 0.05;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum Arm {
Incumbent,
Challenger,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
#[serde(rename_all = "snake_case")]
pub enum Status {
Undecided,
Certified,
Halted,
}
#[derive(Debug, Clone, Serialize, Deserialize)]
struct Mixture {
sign: f64,
lambdas: Vec<f64>,
wealth: Vec<f64>,
}
impl Mixture {
fn new(margin: f64, sign: f64) -> Self {
let worst = if sign > 0.0 {
1.0 + margin
} else {
1.0 - margin
};
Self {
sign,
lambdas: LAMBDA_GRID.iter().map(|g| g / worst).collect(),
wealth: vec![1.0; LAMBDA_GRID.len()],
}
}
fn step(&mut self, d: f64, margin: f64) {
let x = self.sign * (d - margin);
for (w, lambda) in self.wealth.iter_mut().zip(&self.lambdas) {
*w *= 1.0 + lambda * x;
}
}
fn e_value(&self) -> f64 {
#[expect(
clippy::cast_precision_loss,
reason = "the grid has 18 entries; exact in f64"
)]
let n = self.wealth.len() as f64;
self.wealth.iter().sum::<f64>() / n
}
}
#[derive(Debug, Clone, Copy, Default, PartialEq, Serialize, Deserialize)]
pub struct ArmStats {
pub outcomes: u64,
pub outcome_sum: f64,
pub requests: u64,
pub cost_usd: f64,
}
impl ArmStats {
#[must_use]
pub fn success_rate(&self) -> Option<f64> {
#[expect(clippy::cast_precision_loss, reason = "counts far below 2^52")]
(self.outcomes > 0).then(|| self.outcome_sum / self.outcomes as f64)
}
#[must_use]
pub fn cost_per_request(&self) -> Option<f64> {
#[expect(clippy::cast_precision_loss, reason = "counts far below 2^52")]
(self.requests > 0).then(|| self.cost_usd / self.requests as f64)
}
}
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct Report {
pub status: Status,
pub margin: f64,
pub alpha: f64,
pub pairs: u64,
pub decided_at_pair: Option<u64>,
pub e_certify: f64,
pub e_halt: f64,
pub incumbent: ArmStats,
pub challenger: ArmStats,
}
#[derive(Debug, Clone, Serialize, Deserialize)]
pub struct Experiment {
margin: f64,
alpha: f64,
certify: Mixture,
halt: Mixture,
pending_incumbent: VecDeque<f64>,
pending_challenger: VecDeque<f64>,
pairs: u64,
status: Status,
decided_at_pair: Option<u64>,
incumbent: ArmStats,
challenger: ArmStats,
}
impl Experiment {
pub fn new(margin: f64, alpha: f64) -> Result<Self, String> {
if !margin.is_finite() || margin <= 0.0 || margin > 0.5 {
return Err(format!("margin must be in (0, 0.5], got {margin}"));
}
if !alpha.is_finite() || alpha <= 0.0 || alpha >= 0.5 {
return Err(format!("alpha must be in (0, 0.5), got {alpha}"));
}
Ok(Self {
margin,
alpha,
certify: Mixture::new(margin, -1.0),
halt: Mixture::new(margin, 1.0),
pending_incumbent: VecDeque::new(),
pending_challenger: VecDeque::new(),
pairs: 0,
status: Status::Undecided,
decided_at_pair: None,
incumbent: ArmStats::default(),
challenger: ArmStats::default(),
})
}
pub fn observe_outcome(&mut self, arm: Arm, outcome: f64) -> bool {
if !outcome.is_finite() || !(0.0..=1.0).contains(&outcome) {
return false;
}
let stats = self.stats_mut(arm);
stats.outcomes += 1;
stats.outcome_sum += outcome;
match arm {
Arm::Incumbent => self.pending_incumbent.push_back(outcome),
Arm::Challenger => self.pending_challenger.push_back(outcome),
}
while let (Some(&x_inc), Some(&x_ch)) = (
self.pending_incumbent.front(),
self.pending_challenger.front(),
) {
self.pending_incumbent.pop_front();
self.pending_challenger.pop_front();
self.pairs += 1;
if self.status == Status::Undecided {
let d = x_inc - x_ch;
self.certify.step(d, self.margin);
self.halt.step(d, self.margin);
let level = 1.0 / self.alpha;
if self.certify.e_value() >= level {
self.status = Status::Certified;
self.decided_at_pair = Some(self.pairs);
} else if self.halt.e_value() >= level {
self.status = Status::Halted;
self.decided_at_pair = Some(self.pairs);
}
}
}
true
}
pub fn observe_pair(&mut self, x_inc: f64, x_ch: f64) -> bool {
if !x_inc.is_finite()
|| !(0.0..=1.0).contains(&x_inc)
|| !x_ch.is_finite()
|| !(0.0..=1.0).contains(&x_ch)
{
return false;
}
self.incumbent.outcomes += 1;
self.incumbent.outcome_sum += x_inc;
self.challenger.outcomes += 1;
self.challenger.outcome_sum += x_ch;
self.pairs += 1;
if self.status == Status::Undecided {
let d = x_inc - x_ch;
self.certify.step(d, self.margin);
self.halt.step(d, self.margin);
let level = 1.0 / self.alpha;
if self.certify.e_value() >= level {
self.status = Status::Certified;
self.decided_at_pair = Some(self.pairs);
} else if self.halt.e_value() >= level {
self.status = Status::Halted;
self.decided_at_pair = Some(self.pairs);
}
}
true
}
pub fn observe_cost(&mut self, arm: Arm, cost_usd: f64) {
if !cost_usd.is_finite() || cost_usd < 0.0 {
return;
}
let stats = self.stats_mut(arm);
stats.requests += 1;
stats.cost_usd += cost_usd;
}
#[must_use]
pub fn status(&self) -> Status {
self.status
}
#[must_use]
pub fn report(&self) -> Report {
Report {
status: self.status,
margin: self.margin,
alpha: self.alpha,
pairs: self.pairs,
decided_at_pair: self.decided_at_pair,
e_certify: self.certify.e_value(),
e_halt: self.halt.e_value(),
incumbent: self.incumbent,
challenger: self.challenger,
}
}
fn stats_mut(&mut self, arm: Arm) -> &mut ArmStats {
match arm {
Arm::Incumbent => &mut self.incumbent,
Arm::Challenger => &mut self.challenger,
}
}
}
#[cfg(test)]
mod tests {
use super::*;
struct Rng(u64);
impl Rng {
fn next_f64(&mut self) -> f64 {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 7;
self.0 ^= self.0 << 17;
#[expect(clippy::cast_precision_loss, reason = "53-bit mantissa draw")]
let v = (self.0 >> 11) as f64 / (1u64 << 53) as f64;
v
}
fn bern(&mut self, p: f64) -> f64 {
if self.next_f64() < p { 1.0 } else { 0.0 }
}
}
fn run(p_inc: f64, p_ch: f64, seed: u64, cap: u64) -> Status {
let mut rng = Rng(seed);
let mut exp = Experiment::new(DEFAULT_MARGIN, DEFAULT_ALPHA).expect("valid");
for _ in 0..cap {
let a = rng.bern(p_inc);
let b = rng.bern(p_ch);
exp.observe_outcome(Arm::Incumbent, a);
exp.observe_outcome(Arm::Challenger, b);
if exp.status() != Status::Undecided {
break;
}
}
exp.status()
}
fn rate(p_inc: f64, p_ch: f64, want: Status, reps: u64, cap: u64) -> f64 {
let hits = (0..reps)
.filter(|s| run(p_inc, p_ch, 0x9E37_79B9_7F4A_7C15 ^ (s + 1), cap) == want)
.count();
#[expect(clippy::cast_precision_loss, reason = "small counts")]
let r = hits as f64 / reps as f64;
r
}
#[test]
fn rejects_incoherent_parameters() {
assert!(Experiment::new(0.0, 0.05).is_err());
assert!(Experiment::new(0.6, 0.05).is_err());
assert!(Experiment::new(f64::NAN, 0.05).is_err());
assert!(Experiment::new(0.05, 0.0).is_err());
assert!(Experiment::new(0.05, 0.5).is_err());
assert!(Experiment::new(0.05, 0.05).is_ok());
}
#[test]
fn out_of_range_outcomes_are_refused_not_clamped() {
let mut exp = Experiment::new(0.05, 0.05).expect("valid");
assert!(!exp.observe_outcome(Arm::Incumbent, 1.5));
assert!(!exp.observe_outcome(Arm::Incumbent, -0.1));
assert!(!exp.observe_outcome(Arm::Challenger, f64::NAN));
assert_eq!(exp.report().incumbent.outcomes, 0);
assert_eq!(exp.report().challenger.outcomes, 0);
}
#[test]
fn pairs_only_form_across_arms_in_arrival_order() {
let mut exp = Experiment::new(0.05, 0.05).expect("valid");
for _ in 0..5 {
exp.observe_outcome(Arm::Incumbent, 1.0);
}
assert_eq!(exp.report().pairs, 0, "one arm alone is no evidence");
exp.observe_outcome(Arm::Challenger, 1.0);
exp.observe_outcome(Arm::Challenger, 0.0);
assert_eq!(exp.report().pairs, 2);
}
#[test]
fn equal_arms_certify() {
assert!(rate(0.76, 0.76, Status::Certified, 100, 20_000) >= 0.95);
}
#[test]
fn a_clearly_worse_challenger_halts_fast_and_never_certifies() {
let mut halted_quickly = 0;
for s in 0..100u64 {
let mut rng = Rng(0xDEAD_BEEF ^ (s + 1));
let mut exp = Experiment::new(DEFAULT_MARGIN, DEFAULT_ALPHA).expect("valid");
for _ in 0..2_000 {
exp.observe_outcome(Arm::Incumbent, rng.bern(0.77));
exp.observe_outcome(Arm::Challenger, rng.bern(0.56));
if exp.status() != Status::Undecided {
break;
}
}
assert_ne!(exp.status(), Status::Certified, "seed {s}");
if exp.status() == Status::Halted && exp.report().pairs <= 500 {
halted_quickly += 1;
}
}
assert!(
halted_quickly >= 95,
"halted quickly in {halted_quickly}/100"
);
}
#[test]
fn false_certification_at_the_null_boundary_is_at_most_alpha() {
let r = rate(0.76, 0.71, Status::Certified, 400, 10_000);
assert!(r <= DEFAULT_ALPHA + 0.022, "false-certification rate {r}");
}
#[test]
fn false_halt_at_the_null_boundary_is_at_most_alpha() {
let r = rate(0.76, 0.71, Status::Halted, 400, 10_000);
assert!(r <= DEFAULT_ALPHA + 0.022, "false-halt rate {r}");
}
#[test]
fn decisions_are_sticky() {
let mut exp = Experiment::new(0.05, 0.05).expect("valid");
while exp.status() == Status::Undecided {
exp.observe_outcome(Arm::Incumbent, 1.0);
exp.observe_outcome(Arm::Challenger, 0.0);
}
assert_eq!(exp.status(), Status::Halted);
let at = exp.report().decided_at_pair;
for _ in 0..1_000 {
exp.observe_outcome(Arm::Incumbent, 0.0);
exp.observe_outcome(Arm::Challenger, 1.0);
}
assert_eq!(exp.status(), Status::Halted);
assert_eq!(exp.report().decided_at_pair, at);
assert_eq!(exp.report().challenger.outcomes, exp.report().pairs);
}
#[test]
fn cost_is_tallied_per_arm_and_bad_costs_ignored() {
let mut exp = Experiment::new(0.05, 0.05).expect("valid");
exp.observe_cost(Arm::Incumbent, 0.75);
exp.observe_cost(Arm::Incumbent, 0.25);
exp.observe_cost(Arm::Challenger, 0.1);
exp.observe_cost(Arm::Challenger, -1.0);
exp.observe_cost(Arm::Challenger, f64::INFINITY);
let r = exp.report();
assert_eq!(r.incumbent.cost_per_request(), Some(0.5));
assert_eq!(r.challenger.requests, 1);
assert_eq!(r.challenger.cost_per_request(), Some(0.1));
}
#[test]
fn wealth_stays_nonnegative_at_the_extremes() {
for &m in &[0.01, 0.05, 0.5] {
for &sign in &[1.0, -1.0] {
let mut mix = Mixture::new(m, sign);
for &d in &[-1.0, 1.0, -1.0, 1.0] {
mix.step(d, m);
}
assert!(mix.wealth.iter().all(|w| *w >= 0.0), "m={m} sign={sign}");
}
}
}
#[test]
fn observe_pair_out_of_range_is_refused_not_clamped() {
let mut exp = Experiment::new(0.05, 0.05).expect("valid");
assert!(!exp.observe_pair(1.5, 0.5));
assert!(!exp.observe_pair(0.5, -0.1));
assert!(!exp.observe_pair(f64::NAN, 1.0));
assert!(!exp.observe_pair(1.0, f64::INFINITY));
let r = exp.report();
assert_eq!(r.pairs, 0);
assert_eq!(r.incumbent.outcomes, 0);
assert_eq!(r.challenger.outcomes, 0);
}
#[test]
fn observe_pair_bypasses_fifo_queues() {
let mut exp = Experiment::new(0.05, 0.05).expect("valid");
exp.observe_outcome(Arm::Incumbent, 1.0);
exp.observe_outcome(Arm::Incumbent, 1.0);
assert!(exp.observe_pair(1.0, 1.0));
let r = exp.report();
assert_eq!(r.pairs, 1);
assert_eq!(r.incumbent.outcomes, 3); assert_eq!(r.challenger.outcomes, 1); }
#[test]
fn observe_pair_validity_at_null_boundary() {
let mut certify_count = 0u32;
for s in 0..400u64 {
let mut rng = Rng(0xFEED_CAFE ^ (s + 1));
let mut exp = Experiment::new(DEFAULT_MARGIN, DEFAULT_ALPHA).expect("valid");
for _ in 0..10_000 {
let x_ch = rng.bern(1.0 - DEFAULT_MARGIN); exp.observe_pair(1.0, x_ch);
if exp.status() != Status::Undecided {
break;
}
}
if exp.status() == Status::Certified {
certify_count += 1;
}
}
let rate = certify_count as f64 / 400.0;
assert!(
rate <= DEFAULT_ALPHA + 0.022,
"false-certification rate at null boundary: {rate} (limit {})",
DEFAULT_ALPHA + 0.022
);
}
#[test]
fn a_clearly_worse_paired_challenger_halts() {
let mut exp = Experiment::new(DEFAULT_MARGIN, DEFAULT_ALPHA).expect("valid");
for _ in 0..500 {
exp.observe_pair(1.0, 0.0);
if exp.status() != Status::Undecided {
break;
}
}
assert_eq!(exp.status(), Status::Halted);
}
#[test]
fn the_report_round_trips() {
let mut exp = Experiment::new(0.05, 0.05).expect("valid");
exp.observe_outcome(Arm::Incumbent, 1.0);
exp.observe_outcome(Arm::Challenger, 1.0);
let r = exp.report();
let back: Report =
serde_json::from_str(&serde_json::to_string(&r).expect("ser")).expect("de");
assert_eq!(back.status, r.status);
assert_eq!(back.pairs, r.pairs);
assert_eq!(back.incumbent, r.incumbent);
assert!((back.e_certify - r.e_certify).abs() < 1e-12);
assert!((back.e_halt - r.e_halt).abs() < 1e-12);
}
}