1use std::collections::VecDeque;
53
54use serde::{Deserialize, Serialize};
55
56const LAMBDA_GRID: [f64; 18] = [
59 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,
60 0.85, 0.90,
61];
62
63pub const DEFAULT_MARGIN: f64 = 0.05;
67
68pub const DEFAULT_ALPHA: f64 = 0.05;
70
71#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
73#[serde(rename_all = "snake_case")]
74pub enum Arm {
75 Incumbent,
77 Challenger,
79}
80
81#[derive(Debug, Clone, Copy, PartialEq, Eq, Serialize, Deserialize)]
83#[serde(rename_all = "snake_case")]
84pub enum Status {
85 Undecided,
87 Certified,
90 Halted,
93}
94
95#[derive(Debug, Clone, Serialize, Deserialize)]
97struct Mixture {
98 sign: f64,
99 lambdas: Vec<f64>,
100 wealth: Vec<f64>,
101}
102
103impl Mixture {
104 fn new(margin: f64, sign: f64) -> Self {
105 let worst = if sign > 0.0 {
108 1.0 + margin
109 } else {
110 1.0 - margin
111 };
112 Self {
113 sign,
114 lambdas: LAMBDA_GRID.iter().map(|g| g / worst).collect(),
115 wealth: vec![1.0; LAMBDA_GRID.len()],
116 }
117 }
118
119 fn step(&mut self, d: f64, margin: f64) {
120 let x = self.sign * (d - margin);
121 for (w, lambda) in self.wealth.iter_mut().zip(&self.lambdas) {
122 *w *= 1.0 + lambda * x;
123 }
124 }
125
126 fn e_value(&self) -> f64 {
127 #[expect(
128 clippy::cast_precision_loss,
129 reason = "the grid has 18 entries; exact in f64"
130 )]
131 let n = self.wealth.len() as f64;
132 self.wealth.iter().sum::<f64>() / n
133 }
134}
135
136#[derive(Debug, Clone, Copy, Default, PartialEq, Serialize, Deserialize)]
138pub struct ArmStats {
139 pub outcomes: u64,
141 pub outcome_sum: f64,
143 pub requests: u64,
145 pub cost_usd: f64,
147}
148
149impl ArmStats {
150 #[must_use]
152 pub fn success_rate(&self) -> Option<f64> {
153 #[expect(clippy::cast_precision_loss, reason = "counts far below 2^52")]
154 (self.outcomes > 0).then(|| self.outcome_sum / self.outcomes as f64)
155 }
156
157 #[must_use]
159 pub fn cost_per_request(&self) -> Option<f64> {
160 #[expect(clippy::cast_precision_loss, reason = "counts far below 2^52")]
161 (self.requests > 0).then(|| self.cost_usd / self.requests as f64)
162 }
163}
164
165#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
167pub struct Report {
168 pub status: Status,
170 pub margin: f64,
172 pub alpha: f64,
174 pub pairs: u64,
176 pub decided_at_pair: Option<u64>,
178 pub e_certify: f64,
180 pub e_halt: f64,
182 pub incumbent: ArmStats,
184 pub challenger: ArmStats,
186}
187
188#[derive(Debug, Clone, Serialize, Deserialize)]
191pub struct Experiment {
192 margin: f64,
193 alpha: f64,
194 certify: Mixture,
195 halt: Mixture,
196 pending_incumbent: VecDeque<f64>,
197 pending_challenger: VecDeque<f64>,
198 pairs: u64,
199 status: Status,
200 decided_at_pair: Option<u64>,
201 incumbent: ArmStats,
202 challenger: ArmStats,
203}
204
205impl Experiment {
206 pub fn new(margin: f64, alpha: f64) -> Result<Self, String> {
212 if !margin.is_finite() || margin <= 0.0 || margin > 0.5 {
213 return Err(format!("margin must be in (0, 0.5], got {margin}"));
214 }
215 if !alpha.is_finite() || alpha <= 0.0 || alpha >= 0.5 {
216 return Err(format!("alpha must be in (0, 0.5), got {alpha}"));
217 }
218 Ok(Self {
219 margin,
220 alpha,
221 certify: Mixture::new(margin, -1.0),
222 halt: Mixture::new(margin, 1.0),
223 pending_incumbent: VecDeque::new(),
224 pending_challenger: VecDeque::new(),
225 pairs: 0,
226 status: Status::Undecided,
227 decided_at_pair: None,
228 incumbent: ArmStats::default(),
229 challenger: ArmStats::default(),
230 })
231 }
232
233 pub fn observe_outcome(&mut self, arm: Arm, outcome: f64) -> bool {
239 if !outcome.is_finite() || !(0.0..=1.0).contains(&outcome) {
240 return false;
241 }
242 let stats = self.stats_mut(arm);
243 stats.outcomes += 1;
244 stats.outcome_sum += outcome;
245 match arm {
246 Arm::Incumbent => self.pending_incumbent.push_back(outcome),
247 Arm::Challenger => self.pending_challenger.push_back(outcome),
248 }
249 while let (Some(&x_inc), Some(&x_ch)) = (
250 self.pending_incumbent.front(),
251 self.pending_challenger.front(),
252 ) {
253 self.pending_incumbent.pop_front();
254 self.pending_challenger.pop_front();
255 self.pairs += 1;
256 if self.status == Status::Undecided {
258 let d = x_inc - x_ch;
259 self.certify.step(d, self.margin);
260 self.halt.step(d, self.margin);
261 let level = 1.0 / self.alpha;
262 if self.certify.e_value() >= level {
263 self.status = Status::Certified;
264 self.decided_at_pair = Some(self.pairs);
265 } else if self.halt.e_value() >= level {
266 self.status = Status::Halted;
267 self.decided_at_pair = Some(self.pairs);
268 }
269 }
270 }
271 true
272 }
273
274 pub fn observe_pair(&mut self, x_inc: f64, x_ch: f64) -> bool {
286 if !x_inc.is_finite()
287 || !(0.0..=1.0).contains(&x_inc)
288 || !x_ch.is_finite()
289 || !(0.0..=1.0).contains(&x_ch)
290 {
291 return false;
292 }
293 self.incumbent.outcomes += 1;
294 self.incumbent.outcome_sum += x_inc;
295 self.challenger.outcomes += 1;
296 self.challenger.outcome_sum += x_ch;
297 self.pairs += 1;
298 if self.status == Status::Undecided {
299 let d = x_inc - x_ch;
300 self.certify.step(d, self.margin);
301 self.halt.step(d, self.margin);
302 let level = 1.0 / self.alpha;
303 if self.certify.e_value() >= level {
304 self.status = Status::Certified;
305 self.decided_at_pair = Some(self.pairs);
306 } else if self.halt.e_value() >= level {
307 self.status = Status::Halted;
308 self.decided_at_pair = Some(self.pairs);
309 }
310 }
311 true
312 }
313
314 pub fn observe_cost(&mut self, arm: Arm, cost_usd: f64) {
316 if !cost_usd.is_finite() || cost_usd < 0.0 {
317 return;
318 }
319 let stats = self.stats_mut(arm);
320 stats.requests += 1;
321 stats.cost_usd += cost_usd;
322 }
323
324 #[must_use]
326 pub fn status(&self) -> Status {
327 self.status
328 }
329
330 #[must_use]
332 pub fn report(&self) -> Report {
333 Report {
334 status: self.status,
335 margin: self.margin,
336 alpha: self.alpha,
337 pairs: self.pairs,
338 decided_at_pair: self.decided_at_pair,
339 e_certify: self.certify.e_value(),
340 e_halt: self.halt.e_value(),
341 incumbent: self.incumbent,
342 challenger: self.challenger,
343 }
344 }
345
346 fn stats_mut(&mut self, arm: Arm) -> &mut ArmStats {
347 match arm {
348 Arm::Incumbent => &mut self.incumbent,
349 Arm::Challenger => &mut self.challenger,
350 }
351 }
352}
353
354#[cfg(test)]
355mod tests {
356 use super::*;
357
358 struct Rng(u64);
360 impl Rng {
361 fn next_f64(&mut self) -> f64 {
362 self.0 ^= self.0 << 13;
363 self.0 ^= self.0 >> 7;
364 self.0 ^= self.0 << 17;
365 #[expect(clippy::cast_precision_loss, reason = "53-bit mantissa draw")]
366 let v = (self.0 >> 11) as f64 / (1u64 << 53) as f64;
367 v
368 }
369 fn bern(&mut self, p: f64) -> f64 {
370 if self.next_f64() < p { 1.0 } else { 0.0 }
371 }
372 }
373
374 fn run(p_inc: f64, p_ch: f64, seed: u64, cap: u64) -> Status {
376 let mut rng = Rng(seed);
377 let mut exp = Experiment::new(DEFAULT_MARGIN, DEFAULT_ALPHA).expect("valid");
378 for _ in 0..cap {
379 let a = rng.bern(p_inc);
380 let b = rng.bern(p_ch);
381 exp.observe_outcome(Arm::Incumbent, a);
382 exp.observe_outcome(Arm::Challenger, b);
383 if exp.status() != Status::Undecided {
384 break;
385 }
386 }
387 exp.status()
388 }
389
390 fn rate(p_inc: f64, p_ch: f64, want: Status, reps: u64, cap: u64) -> f64 {
391 let hits = (0..reps)
392 .filter(|s| run(p_inc, p_ch, 0x9E37_79B9_7F4A_7C15 ^ (s + 1), cap) == want)
393 .count();
394 #[expect(clippy::cast_precision_loss, reason = "small counts")]
395 let r = hits as f64 / reps as f64;
396 r
397 }
398
399 #[test]
400 fn rejects_incoherent_parameters() {
401 assert!(Experiment::new(0.0, 0.05).is_err());
402 assert!(Experiment::new(0.6, 0.05).is_err());
403 assert!(Experiment::new(f64::NAN, 0.05).is_err());
404 assert!(Experiment::new(0.05, 0.0).is_err());
405 assert!(Experiment::new(0.05, 0.5).is_err());
406 assert!(Experiment::new(0.05, 0.05).is_ok());
407 }
408
409 #[test]
410 fn out_of_range_outcomes_are_refused_not_clamped() {
411 let mut exp = Experiment::new(0.05, 0.05).expect("valid");
412 assert!(!exp.observe_outcome(Arm::Incumbent, 1.5));
413 assert!(!exp.observe_outcome(Arm::Incumbent, -0.1));
414 assert!(!exp.observe_outcome(Arm::Challenger, f64::NAN));
415 assert_eq!(exp.report().incumbent.outcomes, 0);
416 assert_eq!(exp.report().challenger.outcomes, 0);
417 }
418
419 #[test]
420 fn pairs_only_form_across_arms_in_arrival_order() {
421 let mut exp = Experiment::new(0.05, 0.05).expect("valid");
422 for _ in 0..5 {
423 exp.observe_outcome(Arm::Incumbent, 1.0);
424 }
425 assert_eq!(exp.report().pairs, 0, "one arm alone is no evidence");
426 exp.observe_outcome(Arm::Challenger, 1.0);
427 exp.observe_outcome(Arm::Challenger, 0.0);
428 assert_eq!(exp.report().pairs, 2);
429 }
430
431 #[test]
432 fn equal_arms_certify() {
433 assert!(rate(0.76, 0.76, Status::Certified, 100, 20_000) >= 0.95);
435 }
436
437 #[test]
438 fn a_clearly_worse_challenger_halts_fast_and_never_certifies() {
439 let mut halted_quickly = 0;
440 for s in 0..100u64 {
441 let mut rng = Rng(0xDEAD_BEEF ^ (s + 1));
442 let mut exp = Experiment::new(DEFAULT_MARGIN, DEFAULT_ALPHA).expect("valid");
443 for _ in 0..2_000 {
444 exp.observe_outcome(Arm::Incumbent, rng.bern(0.77));
445 exp.observe_outcome(Arm::Challenger, rng.bern(0.56));
446 if exp.status() != Status::Undecided {
447 break;
448 }
449 }
450 assert_ne!(exp.status(), Status::Certified, "seed {s}");
451 if exp.status() == Status::Halted && exp.report().pairs <= 500 {
452 halted_quickly += 1;
453 }
454 }
455 assert!(
456 halted_quickly >= 95,
457 "halted quickly in {halted_quickly}/100"
458 );
459 }
460
461 #[test]
462 fn false_certification_at_the_null_boundary_is_at_most_alpha() {
463 let r = rate(0.76, 0.71, Status::Certified, 400, 10_000);
466 assert!(r <= DEFAULT_ALPHA + 0.022, "false-certification rate {r}");
467 }
468
469 #[test]
470 fn false_halt_at_the_null_boundary_is_at_most_alpha() {
471 let r = rate(0.76, 0.71, Status::Halted, 400, 10_000);
472 assert!(r <= DEFAULT_ALPHA + 0.022, "false-halt rate {r}");
473 }
474
475 #[test]
476 fn decisions_are_sticky() {
477 let mut exp = Experiment::new(0.05, 0.05).expect("valid");
478 while exp.status() == Status::Undecided {
479 exp.observe_outcome(Arm::Incumbent, 1.0);
480 exp.observe_outcome(Arm::Challenger, 0.0);
481 }
482 assert_eq!(exp.status(), Status::Halted);
483 let at = exp.report().decided_at_pair;
484 for _ in 0..1_000 {
485 exp.observe_outcome(Arm::Incumbent, 0.0);
486 exp.observe_outcome(Arm::Challenger, 1.0);
487 }
488 assert_eq!(exp.status(), Status::Halted);
489 assert_eq!(exp.report().decided_at_pair, at);
490 assert_eq!(exp.report().challenger.outcomes, exp.report().pairs);
491 }
492
493 #[test]
494 fn cost_is_tallied_per_arm_and_bad_costs_ignored() {
495 let mut exp = Experiment::new(0.05, 0.05).expect("valid");
496 exp.observe_cost(Arm::Incumbent, 0.75);
497 exp.observe_cost(Arm::Incumbent, 0.25);
498 exp.observe_cost(Arm::Challenger, 0.1);
499 exp.observe_cost(Arm::Challenger, -1.0);
500 exp.observe_cost(Arm::Challenger, f64::INFINITY);
501 let r = exp.report();
502 assert_eq!(r.incumbent.cost_per_request(), Some(0.5));
503 assert_eq!(r.challenger.requests, 1);
504 assert_eq!(r.challenger.cost_per_request(), Some(0.1));
505 }
506
507 #[test]
508 fn wealth_stays_nonnegative_at_the_extremes() {
509 for &m in &[0.01, 0.05, 0.5] {
510 for &sign in &[1.0, -1.0] {
511 let mut mix = Mixture::new(m, sign);
512 for &d in &[-1.0, 1.0, -1.0, 1.0] {
513 mix.step(d, m);
514 }
515 assert!(mix.wealth.iter().all(|w| *w >= 0.0), "m={m} sign={sign}");
516 }
517 }
518 }
519
520 #[test]
521 fn observe_pair_out_of_range_is_refused_not_clamped() {
522 let mut exp = Experiment::new(0.05, 0.05).expect("valid");
523 assert!(!exp.observe_pair(1.5, 0.5));
524 assert!(!exp.observe_pair(0.5, -0.1));
525 assert!(!exp.observe_pair(f64::NAN, 1.0));
526 assert!(!exp.observe_pair(1.0, f64::INFINITY));
527 let r = exp.report();
529 assert_eq!(r.pairs, 0);
530 assert_eq!(r.incumbent.outcomes, 0);
531 assert_eq!(r.challenger.outcomes, 0);
532 }
533
534 #[test]
535 fn observe_pair_bypasses_fifo_queues() {
536 let mut exp = Experiment::new(0.05, 0.05).expect("valid");
537 exp.observe_outcome(Arm::Incumbent, 1.0);
539 exp.observe_outcome(Arm::Incumbent, 1.0);
540 assert!(exp.observe_pair(1.0, 1.0));
542 let r = exp.report();
543 assert_eq!(r.pairs, 1);
546 assert_eq!(r.incumbent.outcomes, 3); assert_eq!(r.challenger.outcomes, 1); }
549
550 #[test]
551 fn observe_pair_validity_at_null_boundary() {
552 let mut certify_count = 0u32;
557 for s in 0..400u64 {
558 let mut rng = Rng(0xFEED_CAFE ^ (s + 1));
559 let mut exp = Experiment::new(DEFAULT_MARGIN, DEFAULT_ALPHA).expect("valid");
560 for _ in 0..10_000 {
561 let x_ch = rng.bern(1.0 - DEFAULT_MARGIN); exp.observe_pair(1.0, x_ch);
564 if exp.status() != Status::Undecided {
565 break;
566 }
567 }
568 if exp.status() == Status::Certified {
569 certify_count += 1;
570 }
571 }
572 let rate = certify_count as f64 / 400.0;
574 assert!(
575 rate <= DEFAULT_ALPHA + 0.022,
576 "false-certification rate at null boundary: {rate} (limit {})",
577 DEFAULT_ALPHA + 0.022
578 );
579 }
580
581 #[test]
582 fn a_clearly_worse_paired_challenger_halts() {
583 let mut exp = Experiment::new(DEFAULT_MARGIN, DEFAULT_ALPHA).expect("valid");
586 for _ in 0..500 {
587 exp.observe_pair(1.0, 0.0);
588 if exp.status() != Status::Undecided {
589 break;
590 }
591 }
592 assert_eq!(exp.status(), Status::Halted);
593 }
594
595 #[test]
596 fn the_report_round_trips() {
597 let mut exp = Experiment::new(0.05, 0.05).expect("valid");
598 exp.observe_outcome(Arm::Incumbent, 1.0);
599 exp.observe_outcome(Arm::Challenger, 1.0);
600 let r = exp.report();
601 let back: Report =
602 serde_json::from_str(&serde_json::to_string(&r).expect("ser")).expect("de");
603 assert_eq!(back.status, r.status);
605 assert_eq!(back.pairs, r.pairs);
606 assert_eq!(back.incumbent, r.incumbent);
607 assert!((back.e_certify - r.e_certify).abs() < 1e-12);
608 assert!((back.e_halt - r.e_halt).abs() < 1e-12);
609 }
610}