sketch_ucb1.nx

sketch_ucb1.nx -- UCB1 multi-armed bandit (Auer-Cesa-Bianchi-Fischer 2002). Online-learning primitive. Given N "arms" (actions), select the best one over time while balancing EXPLORATION (try arms we haven't pulled) and EXPLOITATION (favor arms with high observed reward). UCB1 selection rule: score_i = mean_i + sqrt(2 * ln(N_total) / count_i) pull arg max score_i Where: mean_i = sum_reward_i / count_i (estimated value) sqrt(...) = exploration bonus (shrinks as count_i grows) Arms with count_i = 0 have score = +inf (must-pull first). PROVEN PROPERTIES (Auer 2002): regret bound: O(sqrt(K * N * ln(N))) where K = #arms, N = total pulls. Near-optimal for adversarial problems; optimal up to log factor for stochastic. USE CASES (extends NishiLang substrate beyond DataSketches scope): - A/B testing with multi-arm allocation (Bayesian alternative) - Recommendation with cold-start exploration - Hyperparameter tuning under budget constraints - Game AI move selection INTEGER-FIXED-POINT IMPLEMENTATION: - rewards scaled to PPM (0..1_000_000 = [0, 1.0]) - mean_i = sum_reward_ppm / count_i - ln(N) ≈ (bitlen(N) - 1) * 693147 / 1000 ppm (factor of ln(2)) - sqrt() via isqrt (Newton) - score_i in PPM LOSSLESS-LANGUAGE DISCIPLINE: nx_ucb_query returns ApproxI64 with NX_ENV_REL_STDDEV = 1/sqrt(count_i). Bandits are stochastic by nature; the envelope honestly declares estimation uncertainty.