sketch_thompson.nx

sketch_thompson.nx -- Thompson Sampling (Bernoulli-Beta bandit). Thompson 1933 / Russo-Van Roy 2018 modern treatment. Bayesian alternative to UCB1 (sketch_ucb1.nx): instead of a confidence- bound upper-bonus, sample from each arm's posterior and pick the argmax. Empirically tighter regret on stochastic Bernoulli arms; matches UCB asymptotic bounds. CORE OPERATION: For arm i with s_i successes, f_i failures: posterior ~ Beta(s_i + 1, f_i + 1) (uniform Beta(1,1) prior) Per decision: for each arm i: sample x_i ~ Beta(s_i+1, f_i+1) pull arg max x_i SAMPLING WITHOUT f64 (the technical chokepoint): Beta(α, β) for integer α, β equals the distribution of the α-th smallest of α + β − 1 uniforms in [0, 1]. (David-Nagaraja "Order Statistics", standard textbook result.) Exact, no log or special functions needed. Cost O(α + β) per sample. HYBRID FOR LARGE (s + f): - exact order statistic when s + f + 1 ≤ NX_THOMPSON_EXACT_MAX - Normal approximation when larger (cost O(1) instead of O(n)). Beta(α, β) ≈ N(μ, σ²) with μ = α/(α+β), σ² = μ(1−μ)/(α+β+1). Normal sampled via Irwin-Hall sum of 12 uniforms (CLT). Both paths produce Q14 fixed-point samples in [0, Q14] = [0, 1]. EXTENDS NISHI-SUBSTRATE BEYOND DATASKETCHES (DS is summarization- only; bandits live elsewhere). Composes against sketch_ucb1 + sketch_epsilon_greedy as the bandit-family triple. LOSSLESS-LANGUAGE DISCIPLINE: nx_thompson_query returns ApproxI64 with NX_ENV_REL_STDDEV = 1/sqrt(count_i + 1), matching posterior shrinkage as samples accumulate.