sketch_thompson_vs_ucb1_bench.nx source
↩ module page · 118 lines · 4152 B
1// sketch_thompson_vs_ucb1_bench.nx -- paired measurement, Thompson vs UCB1.
2//
3// CLAIM TO VALIDATE:
4// Thompson Sampling (sketch_thompson) achieves LOWER regret than
5// UCB1 (sketch_ucb1) on a 2-armed Bernoulli bandit with arms at
6// 80% and 20% over 1000 steps. Modern Bayesian-bandit literature
7// (Chapelle-Li 2011, Russo-Van Roy 2018) reports Thompson winning
8// by ~10-15% empirical regret on this setting. We measure the
9// same on our substrate.
10//
11// SHARED WORKLOAD:
12// - Same simulator LCG state seed (999) for both
13// - 1000 steps each
14// - Arm 0 = 80% (true mean 0.8), Arm 1 = 20% (true mean 0.2)
15// - Optimal cumulative reward = 800 (always pick arm 0)
16//
17// MEASUREMENT:
18// ACCURACY axis: cumulative successes (closer to 800 wins).
19// MEMORY axis: nx_thompson_memory_bytes vs nx_ucb_memory_bytes.
20// TIME axis: INCONCLUSIVE.
21//
22// HARD-WIN GATE:
23// ACCURACY axis must BEAT by at least 1% (10000 ppm).
24
25import "syscalls.nx"
26import "sketch_thompson.nx"
27import "sketch_ucb1.nx"
28import "sketch_comparator.nx"
29import "sketch_types.nx"
30
31const NX_SIM_LCG_A: i64 = 1103515245
32const NX_SIM_LCG_C: i64 = 12345
33const NX_SIM_LCG_MOD: i64 = 0x7FFFFFFF
34
35func main() -> i64 {
36 let ucb: *Ucb1 = nx_ucb_alloc(2)
37 let thomp: *Thompson = nx_thompson_alloc(2, 7)
38
39 var sim_ucb: i64 = 999
40 var sim_thomp: i64 = 999 // identical seed for fairness
41
42 var ucb_succ: i64 = 0
43 var thomp_succ: i64 = 0
44
45 var step: i64 = 0
46 while step < 1000 {
47 // ---- UCB1 step ----
48 let ucb_arm: i64 = nx_ucb_select(ucb)
49 sim_ucb = ((sim_ucb * NX_SIM_LCG_A) + NX_SIM_LCG_C) & NX_SIM_LCG_MOD
50 let u_u: i64 = sim_ucb & 1023 // 0..1023
51 var ucb_reward: i64 = 0
52 if ucb_arm == 0 {
53 if u_u < 819 { ucb_reward = 1 } // 80% success
54 }
55 if ucb_arm == 1 {
56 if u_u < 205 { ucb_reward = 1 } // 20% success
57 }
58 nx_ucb_update(ucb, ucb_arm, ucb_reward * 1000000)
59 if ucb_reward == 1 { ucb_succ = ucb_succ + 1 }
60
61 // ---- Thompson step ----
62 let t_arm: i64 = nx_thompson_select(thomp)
63 sim_thomp = ((sim_thomp * NX_SIM_LCG_A) + NX_SIM_LCG_C) & NX_SIM_LCG_MOD
64 let u_t: i64 = sim_thomp & 1023
65 var t_reward: i64 = 0
66 if t_arm == 0 {
67 if u_t < 819 { t_reward = 1 }
68 }
69 if t_arm == 1 {
70 if u_t < 205 { t_reward = 1 }
71 }
72 nx_thompson_update(thomp, t_arm, t_reward)
73 if t_reward == 1 { thomp_succ = thomp_succ + 1 }
74
75 step = step + 1
76 }
77
78 // ---- ACCURACY axis: cumulative successes (closer to 800 = optimal) ----
79 let truth: i64 = 800
80 let acc: *ComparisonResult = nx_cmp_accuracy(thomp_succ, ucb_succ, truth, 10000)
81
82 // ---- MEMORY axis ----
83 let thomp_bytes: i64 = nx_thompson_memory_bytes(thomp)
84 let ucb_bytes: i64 = nx_ucb_memory_bytes(ucb)
85 let mem: *ComparisonResult = nx_cmp_memory(thomp_bytes, ucb_bytes, 10000)
86
87 // ---- TIME axis INCONCLUSIVE ----
88 let tim_raw: *u8 = sys_mmap(40)
89 let tim: *ComparisonResult = tim_raw as *ComparisonResult
90 tim.verdict = NX_CMP_VERDICT_INCONCLUSIVE
91 tim.delta_ppm = 0
92 tim.conf_ppb = 500000000
93 tim.axis = NX_CMP_AXIS_TIME
94
95 // ---- HARD-WIN GATE on ACCURACY ----
96 if acc.verdict != NX_CMP_VERDICT_BEATS {
97 return __syscall(93, 10, 0, 0, 0, 0, 0)
98 }
99 if acc.delta_ppm < 10000 {
100 return __syscall(93, 11, 0, 0, 0, 0, 0)
101 }
102
103 // ---- Sanity: both bandits eventually identify arm 0 as best ----
104 if nx_ucb_best_arm(ucb) != 0 { return __syscall(93, 20, 0, 0, 0, 0, 0) }
105 if nx_thompson_best_arm(thomp) != 0 { return __syscall(93, 21, 0, 0, 0, 0, 0) }
106
107 // ---- Sanity: thomp_succ must be in the realistic 700-800 window ----
108 if thomp_succ < 700 { return __syscall(93, 22, 0, 0, 0, 0, 0) }
109 if thomp_succ > 800 { return __syscall(93, 23, 0, 0, 0, 0, 0) }
110
111 // ---- Composite: not INCONCLUSIVE ----
112 let composite: i64 = nx_cmp_composite(acc, mem, tim)
113 if composite == NX_CMP_VERDICT_INCONCLUSIVE {
114 return __syscall(93, 30, 0, 0, 0, 0, 0)
115 }
116
117 return 0
118}