Skip to main content

qualia_core_db/solvers/learning/experiment/
bandit.rs

1//! Multi-armed bandits (Practical Statistics ch 3) — sequential experimentation
2//! that *adapts*: instead of a fixed-split A/B test, allocate more trials to the
3//! arms that look better, trading exploration against exploitation. Three classic
4//! policies: ε-greedy, UCB1, and Thompson sampling (Beta-Bernoulli). Kernel-class
5//! `Divergent` (the sampling/branch logic).
6
7/// Allocation policy.
8#[derive(Debug, Clone, Copy, PartialEq)]
9pub enum Policy {
10    /// With probability ε pick a random arm, else the empirically best.
11    EpsilonGreedy(f64),
12    /// Upper Confidence Bound (UCB1): optimism under uncertainty.
13    Ucb1,
14    /// Thompson sampling with a Beta-Bernoulli posterior per arm.
15    ThompsonBernoulli,
16}
17
18/// A bandit over `k` arms.
19#[derive(Debug, Clone)]
20pub struct Bandit {
21    policy: Policy,
22    counts: Vec<u64>,
23    values: Vec<f64>, // running mean reward
24    alpha: Vec<f64>,  // Beta posterior (Thompson)
25    beta: Vec<f64>,
26    t: u64,
27    rng: Lcg,
28}
29
30#[derive(Debug, Clone)]
31struct Lcg(u64);
32impl Lcg {
33    fn unit(&mut self) -> f64 {
34        self.0 = self
35            .0
36            .wrapping_mul(6364136223846793005)
37            .wrapping_add(1442695040888963407);
38        ((self.0 >> 11) as f64) / ((1u64 << 53) as f64)
39    }
40    fn below(&mut self, b: usize) -> usize {
41        (self.unit() * b as f64) as usize % b.max(1)
42    }
43    fn gaussian(&mut self) -> f64 {
44        let u1 = self.unit().max(1e-12);
45        let u2 = self.unit();
46        (-2.0 * u1.ln()).sqrt() * (std::f64::consts::TAU * u2).cos()
47    }
48    fn gamma(&mut self, a: f64) -> f64 {
49        if a < 1.0 {
50            return self.gamma(a + 1.0) * self.unit().max(1e-12).powf(1.0 / a);
51        }
52        let d = a - 1.0 / 3.0;
53        let c = 1.0 / (9.0 * d).sqrt();
54        loop {
55            let x = self.gaussian();
56            let v = (1.0 + c * x).powi(3);
57            if v <= 0.0 {
58                continue;
59            }
60            let u = self.unit();
61            if u.ln() < 0.5 * x * x + d - d * v + d * v.ln() {
62                return d * v;
63            }
64        }
65    }
66    fn beta(&mut self, a: f64, b: f64) -> f64 {
67        let x = self.gamma(a);
68        let y = self.gamma(b);
69        if x + y > 0.0 {
70            x / (x + y)
71        } else {
72            0.5
73        }
74    }
75}
76
77impl Bandit {
78    /// Creates a default `Bandit`.
79    pub fn new(k: usize, policy: Policy, seed: u64) -> Self {
80        Self {
81            policy,
82            counts: vec![0; k],
83            values: vec![0.0; k],
84            alpha: vec![1.0; k], // Beta(1,1) uniform prior
85            beta: vec![1.0; k],
86            t: 0,
87            rng: Lcg(seed ^ 0x9E3779B97F4A7C15),
88        }
89    }
90
91    /// Choose the next arm to pull.
92    pub fn select(&mut self) -> usize {
93        let k = self.counts.len();
94        match self.policy {
95            Policy::EpsilonGreedy(eps) => {
96                // Try each untried arm first, then ε-greedy.
97                if let Some(u) = (0..k).find(|&i| self.counts[i] == 0) {
98                    return u;
99                }
100                if self.rng.unit() < eps {
101                    self.rng.below(k)
102                } else {
103                    argmax(&self.values)
104                }
105            }
106            Policy::Ucb1 => {
107                if let Some(u) = (0..k).find(|&i| self.counts[i] == 0) {
108                    return u;
109                }
110                let t = self.t.max(1) as f64;
111                let mut best = 0;
112                let mut best_v = f64::NEG_INFINITY;
113                for i in 0..k {
114                    let bonus = (2.0 * t.ln() / self.counts[i] as f64).sqrt();
115                    let v = self.values[i] + bonus;
116                    if v > best_v {
117                        best_v = v;
118                        best = i;
119                    }
120                }
121                best
122            }
123            Policy::ThompsonBernoulli => {
124                let mut best = 0;
125                let mut best_s = f64::NEG_INFINITY;
126                for i in 0..k {
127                    let s = self.rng.beta(self.alpha[i], self.beta[i]);
128                    if s > best_s {
129                        best_s = s;
130                        best = i;
131                    }
132                }
133                best
134            }
135        }
136    }
137
138    /// Record a `reward ∈ [0,1]` for `arm` (1 = success / 0 = failure for Bernoulli).
139    pub fn update(&mut self, arm: usize, reward: f64) {
140        self.t += 1;
141        self.counts[arm] += 1;
142        let n = self.counts[arm] as f64;
143        self.values[arm] += (reward - self.values[arm]) / n; // running mean
144        self.alpha[arm] += reward.clamp(0.0, 1.0);
145        self.beta[arm] += 1.0 - reward.clamp(0.0, 1.0);
146    }
147
148    /// Arm pull counts.
149    pub fn counts(&self) -> &[u64] {
150        &self.counts
151    }
152    /// All values.
153    pub fn values(&self) -> &[f64] {
154        &self.values
155    }
156    /// The arm with the most pulls — the bandit's current best guess.
157    pub fn best_arm(&self) -> usize {
158        argmax_u64(&self.counts)
159    }
160}
161
162fn argmax(v: &[f64]) -> usize {
163    let mut best = 0;
164    for i in 1..v.len() {
165        if v[i] > v[best] {
166            best = i;
167        }
168    }
169    best
170}
171fn argmax_u64(v: &[u64]) -> usize {
172    let mut best = 0;
173    for i in 1..v.len() {
174        if v[i] > v[best] {
175            best = i;
176        }
177    }
178    best
179}
180
181#[cfg(test)]
182mod tests {
183    use super::*;
184
185    /// Deterministic Bernoulli reward source.
186    struct Arms {
187        p: Vec<f64>,
188        rng: Lcg,
189    }
190    impl Arms {
191        fn pull(&mut self, arm: usize) -> f64 {
192            if self.rng.unit() < self.p[arm] {
193                1.0
194            } else {
195                0.0
196            }
197        }
198    }
199
200    fn run(policy: Policy) -> (Bandit, usize) {
201        let mut bandit = Bandit::new(3, policy, 1);
202        let mut arms = Arms {
203            p: vec![0.2, 0.5, 0.8],
204            rng: Lcg(42),
205        };
206        for _ in 0..3000 {
207            let a = bandit.select();
208            let r = arms.pull(a);
209            bandit.update(a, r);
210        }
211        let best = bandit.best_arm();
212        (bandit, best)
213    }
214
215    #[test]
216    fn thompson_converges_to_the_best_arm() {
217        let (b, best) = run(Policy::ThompsonBernoulli);
218        assert_eq!(
219            best,
220            2,
221            "should mostly pull the 0.8 arm; counts {:?}",
222            b.counts()
223        );
224        assert!(
225            b.counts()[2] > b.counts()[0],
226            "best arm pulled more than the worst"
227        );
228    }
229
230    #[test]
231    fn ucb1_converges_to_the_best_arm() {
232        let (b, best) = run(Policy::Ucb1);
233        assert_eq!(best, 2, "counts {:?}", b.counts());
234    }
235
236    #[test]
237    fn epsilon_greedy_favours_the_best_arm() {
238        let (b, _) = run(Policy::EpsilonGreedy(0.1));
239        // The best arm gets the lion's share of the non-exploration pulls.
240        assert!(
241            b.counts()[2] > b.counts()[0] + b.counts()[1],
242            "counts {:?}",
243            b.counts()
244        );
245        // Its estimated value is near the true 0.8.
246        assert!((b.values()[2] - 0.8).abs() < 0.1, "value {}", b.values()[2]);
247    }
248}