code wiki / (root) / sketch_thompson_vs_ucb1_bench.nx

sketch_thompson_vs_ucb1_bench.nx

buildroot/runtime/sketch_thompson_vs_ucb1_bench.nx

4152 B118 linesdepth 5pulls 7 transitivereach 0 importersview sourcekind benchtopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_thompson_vs_ucb1_bench.nx -- paired measurement, Thompson vs UCB1. CLAIM TO VALIDATE: Thompson Sampling (sketch_thompson) achieves LOWER regret than UCB1 (sketch_ucb1) on a 2-armed Bernoulli bandit with arms at 80% and 20% over 1000 steps. Modern Bayesian-bandit literature (Chapelle-Li 2011, Russo-Van Roy 2018) reports Thompson winning by ~10-15% empirical regret on this setting. We measure the same on our substrate. SHARED WORKLOAD: - Same simulator LCG state seed (999) for both - 1000 steps each - Arm 0 = 80% (true mean 0.8), Arm 1 = 20% (true mean 0.2) - Optimal cumulative reward = 800 (always pick arm 0) MEASUREMENT: ACCURACY axis: cumulative successes (closer to 800 wins). MEMORY axis: nx_thompson_memory_bytes vs nx_ucb_memory_bytes. TIME axis: INCONCLUSIVE. HARD-WIN GATE: ACCURACY axis must BEAT by at least 1% (10000 ppm).

dependencies 5 imports · 0 importers

syscalls.nx sketch_thompson.nx sketch_ucb1.nx sketch_comparator.nx sketch_types.nx sketch_thompson_vs_ucb1_bench.

imports: syscalls.nxsketch_thompson.nxsketch_ucb1.nxsketch_comparator.nxsketch_types.nx

imported by: nobody (leaf or entry point)

call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown

main nx_ucb_alloc nx_thompson_alloc nx_ucb_select nx_ucb_score nx_ucb_ln_ppm nx_ucb_bitlen nx_ucb_isqrt nx_ucb_update nx_thompson_select nx_thompson_sample_q14 nx_thompson_sample_order_s nx_thompson_uniform_q14 nx_thompson_rng_next nx_thompson_sort_scratch nx_thompson_isqrt nx_thompson_clt_normal_q14 nx_thompson_uniform_q14 ↻ nx_thompson_update nx_cmp_accuracy nx_cmp_iabs nx_thompson_memory_bytes nx_ucb_memory_bytes nx_cmp_memory nx_ucb_best_arm nx_ucb_mean_ppm nx_thompson_best_arm nx_thompson_posterior_mean nx_cmp_composite

structs

none

consts

31const NX_SIM_LCG_A: i64 = 1103515245
32const NX_SIM_LCG_C: i64 = 12345
33const NX_SIM_LCG_MOD: i64 = 0x7FFFFFFF

functions

35func main() -> i64