nx_sketch_epsilon_greedy.nx source
↩ module page · 216 lines · 6762 B
1// sketch_epsilon_greedy.nx -- Epsilon-Greedy bandit (Sutton-Barto, classic).
2//
3// Simpler alternative to UCB1. At each pull:
4// with probability epsilon: pull a UNIFORM-RANDOM arm
5// with probability 1-epsilon: pull arm with highest empirical mean
6//
7// Three modes via the epsilon_mode field:
8// NX_EG_MODE_FIXED -- epsilon constant (param: epsilon_ppm)
9// NX_EG_MODE_DECAY_LINEAR -- epsilon(t) = epsilon_0 / (t+1)
10// NX_EG_MODE_DECAY_LOG -- epsilon(t) = epsilon_0 / log(t+e)
11//
12// COMPLEMENTS UCB1:
13// - UCB1: deterministic confidence-bound; near-optimal regret;
14// requires sqrt + log per arm per pull
15// - epsilon-Greedy: stochastic; simpler; tunable explore rate;
16// preferred when log/sqrt are expensive (embedded) or when
17// bounded exploration budget needed
18// Together they cover the "classic bandit" textbook coverage.
19//
20// LCG-based deterministic RNG so two runs with same seed produce
21// byte-identical action sequences.
22//
23// LOSSLESS-LANGUAGE DISCIPLINE: nx_eg_query reports the running
24// mean of an arm with stderr ~ 1/sqrt(count_i).
25
26// nx_safety_envelope:
27// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
28// sil_target: SIL1
29// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
30// verdict: NOT_YET_EVALUATED
31
32import "nx_syscalls.nx"
33import "nx_sketch_types.nx"
34import "nx_vecmath.nx"
35
36const NX_EG_MIN_ARMS: i64 = 2
37const NX_EG_MAX_ARMS: i64 = 10000
38
39const NX_EG_MODE_FIXED: i64 = 0
40const NX_EG_MODE_DECAY_LINEAR: i64 = 1
41const NX_EG_MODE_DECAY_LOG: i64 = 2
42
43const NX_EG_LCG_A: i64 = 1103515245
44const NX_EG_LCG_C: i64 = 12345
45const NX_EG_LCG_MOD: i64 = 0x7FFFFFFF
46
47const NX_EG_REWARD_MAX: i64 = 1000000
48
49struct EpsilonGreedy {
50 n_arms: i64,
51 counts: *i64,
52 sum_rewards: *i64,
53 total_pulls: i64,
54 epsilon_mode: i64,
55 epsilon_ppm: i64, // initial/fixed epsilon in PPM
56 rng_state: i64,
57}
58
59// === construction =================================================
60
61func nx_eg_alloc(n_arms: i64, mode: i64, epsilon_ppm: i64, seed: i64) -> *EpsilonGreedy {
62 if n_arms < NX_EG_MIN_ARMS { return 0 as *EpsilonGreedy }
63 if n_arms > NX_EG_MAX_ARMS { return 0 as *EpsilonGreedy }
64 if mode < 0 { return 0 as *EpsilonGreedy }
65 if mode > NX_EG_MODE_DECAY_LOG { return 0 as *EpsilonGreedy }
66 if epsilon_ppm < 0 { return 0 as *EpsilonGreedy }
67 if epsilon_ppm > 1000000 { return 0 as *EpsilonGreedy }
68 let raw: *u8 = sys_mmap(56)
69 let eg: *EpsilonGreedy = raw as *EpsilonGreedy
70 eg.counts = sys_mmap(n_arms * 8) as *i64
71 eg.sum_rewards = sys_mmap(n_arms * 8) as *i64
72 var i: i64 = 0
73 while i < n_arms {
74 eg.counts[i] = 0
75 eg.sum_rewards[i] = 0
76 i = i + 1
77 }
78 eg.n_arms = n_arms
79 eg.total_pulls = 0
80 eg.epsilon_mode = mode
81 eg.epsilon_ppm = epsilon_ppm
82 eg.rng_state = seed | 1
83 return eg
84}
85
86func nx_eg_rng_next(eg: *EpsilonGreedy) -> i64 {
87 let next: i64 = ((eg.rng_state * NX_EG_LCG_A) + NX_EG_LCG_C) & NX_EG_LCG_MOD
88 eg.rng_state = next
89 return next
90}
91
92func nx_eg_rng_below(eg: *EpsilonGreedy, n: i64) -> i64 {
93 let r: i64 = nx_eg_rng_next(eg)
94 return r % n
95}
96
97// === bitlen for decay =============================================
98
99func nx_eg_bitlen(x: i64) -> i64 {
100 if x <= 0 { return 0 }
101 var n: i64 = 0
102 var t: i64 = x
103 while t > 0 {
104 t = t >> 1
105 n = n + 1
106 }
107 return n
108}
109
110// === current epsilon =============================================
111
112func nx_eg_current_epsilon_ppm(eg: *EpsilonGreedy) -> i64 {
113 if eg.epsilon_mode == NX_EG_MODE_FIXED {
114 return eg.epsilon_ppm
115 }
116 if eg.epsilon_mode == NX_EG_MODE_DECAY_LINEAR {
117 let t: i64 = eg.total_pulls + 1
118 return eg.epsilon_ppm / t
119 }
120 if eg.epsilon_mode == NX_EG_MODE_DECAY_LOG {
121 let t: i64 = eg.total_pulls + 2 // +2 so log(t) >= 1
122 let lg: i64 = nx_eg_bitlen(t)
123 if lg <= 1 { return eg.epsilon_ppm }
124 return eg.epsilon_ppm / lg
125 }
126 return eg.epsilon_ppm
127}
128
129// === select =======================================================
130//
131// Explore (uniform random arm) with prob epsilon; else exploit
132// (arm with highest empirical mean). Untested arms are picked
133// uniformly at random during the explore phase, eventually all
134// arms get pulled.
135
136func nx_eg_best_arm_by_mean(eg: *EpsilonGreedy) -> i64 {
137 var best: i64 = 0
138 var best_mean: i64 = -1
139 var i: i64 = 0
140 while i < eg.n_arms {
141 if eg.counts[i] > 0 {
142 let m: i64 = eg.sum_rewards[i] / eg.counts[i]
143 if m > best_mean {
144 best = i
145 best_mean = m
146 }
147 }
148 i = i + 1
149 }
150 if best_mean < 0 {
151 // All arms untested: pick random.
152 return nx_eg_rng_below(eg, eg.n_arms)
153 }
154 return best
155}
156
157func nx_eg_select(eg: *EpsilonGreedy) -> i64 {
158 let eps_ppm: i64 = nx_eg_current_epsilon_ppm(eg)
159 let roll: i64 = nx_eg_rng_below(eg, 1000000)
160 if roll < eps_ppm {
161 // Explore.
162 return nx_eg_rng_below(eg, eg.n_arms)
163 }
164 // Exploit.
165 return nx_eg_best_arm_by_mean(eg)
166}
167
168// === update ======================================================
169
170func nx_eg_update(eg: *EpsilonGreedy, arm: i64, reward_ppm: i64) -> i64 {
171 if arm < 0 { return -1 }
172 if arm >= eg.n_arms { return -1 }
173 if reward_ppm < 0 { return -1 }
174 if reward_ppm > NX_EG_REWARD_MAX { return -1 }
175 eg.counts[arm] = eg.counts[arm] + 1
176 eg.sum_rewards[arm] = eg.sum_rewards[arm] + reward_ppm
177 eg.total_pulls = eg.total_pulls + 1
178 return 0
179}
180
181// === queries =====================================================
182
183func nx_eg_mean_ppm(eg: *EpsilonGreedy, arm: i64) -> i64 {
184 if eg.counts[arm] == 0 { return 0 }
185 return eg.sum_rewards[arm] / eg.counts[arm]
186}
187
188func nx_eg_count(eg: *EpsilonGreedy, arm: i64) -> i64 {
189 return eg.counts[arm]
190}
191
192func nx_eg_best_arm(eg: *EpsilonGreedy) -> i64 {
193 return nx_eg_best_arm_by_mean(eg)
194}
195
196// === isqrt for envelope ==========================================
197
198func nx_eg_isqrt(x: i64) -> i64 { return vm_isqrt(x) }
199
200func nx_eg_query(eg: *EpsilonGreedy, arm: i64) -> *ApproxI64 {
201 let m: i64 = nx_eg_mean_ppm(eg, arm)
202 let cnt: i64 = eg.counts[arm]
203 var stderr_ppb: i64 = 1000000000
204 if cnt > 0 {
205 let isq: i64 = nx_eg_isqrt(cnt)
206 if isq > 0 { stderr_ppb = 1000000000 / isq }
207 }
208 return nx_approx_new(m, NX_ENV_REL_STDDEV, stderr_ppb,
209 682700000,
210 NX_MATURITY_REFERENCE_IMPL,
211 NX_ADV_HONEST)
212}
213
214func nx_eg_memory_bytes(eg: *EpsilonGreedy) -> i64 {
215 return 56 + eg.n_arms * 16
216}