qualia_core_db/solvers/learning/experiment/
bandit.rs1#[derive(Debug, Clone, Copy, PartialEq)]
9pub enum Policy {
10 EpsilonGreedy(f64),
12 Ucb1,
14 ThompsonBernoulli,
16}
17
18#[derive(Debug, Clone)]
20pub struct Bandit {
21 policy: Policy,
22 counts: Vec<u64>,
23 values: Vec<f64>, alpha: Vec<f64>, 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 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: vec![1.0; k],
86 t: 0,
87 rng: Lcg(seed ^ 0x9E3779B97F4A7C15),
88 }
89 }
90
91 pub fn select(&mut self) -> usize {
93 let k = self.counts.len();
94 match self.policy {
95 Policy::EpsilonGreedy(eps) => {
96 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 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; self.alpha[arm] += reward.clamp(0.0, 1.0);
145 self.beta[arm] += 1.0 - reward.clamp(0.0, 1.0);
146 }
147
148 pub fn counts(&self) -> &[u64] {
150 &self.counts
151 }
152 pub fn values(&self) -> &[f64] {
154 &self.values
155 }
156 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 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 assert!(
241 b.counts()[2] > b.counts()[0] + b.counts()[1],
242 "counts {:?}",
243 b.counts()
244 );
245 assert!((b.values()[2] - 0.8).abs() < 0.1, "value {}", b.values()[2]);
247 }
248}