nx_sketch_epsilon_greedy.nx source
↩ module page · 230 lines · 7056 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"
34
35const NX_EG_MIN_ARMS: i64 = 2
36const NX_EG_MAX_ARMS: i64 = 10000
37
38const NX_EG_MODE_FIXED: i64 = 0
39const NX_EG_MODE_DECAY_LINEAR: i64 = 1
40const NX_EG_MODE_DECAY_LOG: i64 = 2
41
42const NX_EG_LCG_A: i64 = 1103515245
43const NX_EG_LCG_C: i64 = 12345
44const NX_EG_LCG_MOD: i64 = 0x7FFFFFFF
45
46const NX_EG_REWARD_MAX: i64 = 1000000
47
48struct EpsilonGreedy {
49 n_arms: i64,
50 counts: *i64,
51 sum_rewards: *i64,
52 total_pulls: i64,
53 epsilon_mode: i64,
54 epsilon_ppm: i64, // initial/fixed epsilon in PPM
55 rng_state: i64,
56}
57
58// === construction =================================================
59
60func nx_eg_alloc(n_arms: i64, mode: i64, epsilon_ppm: i64, seed: i64) -> *EpsilonGreedy {
61 if n_arms < NX_EG_MIN_ARMS { return 0 as *EpsilonGreedy }
62 if n_arms > NX_EG_MAX_ARMS { return 0 as *EpsilonGreedy }
63 if mode < 0 { return 0 as *EpsilonGreedy }
64 if mode > NX_EG_MODE_DECAY_LOG { return 0 as *EpsilonGreedy }
65 if epsilon_ppm < 0 { return 0 as *EpsilonGreedy }
66 if epsilon_ppm > 1000000 { return 0 as *EpsilonGreedy }
67 let raw: *u8 = sys_mmap(56)
68 let eg: *EpsilonGreedy = raw as *EpsilonGreedy
69 eg.counts = sys_mmap(n_arms * 8) as *i64
70 eg.sum_rewards = sys_mmap(n_arms * 8) as *i64
71 var i: i64 = 0
72 while i < n_arms {
73 eg.counts[i] = 0
74 eg.sum_rewards[i] = 0
75 i = i + 1
76 }
77 eg.n_arms = n_arms
78 eg.total_pulls = 0
79 eg.epsilon_mode = mode
80 eg.epsilon_ppm = epsilon_ppm
81 eg.rng_state = seed | 1
82 return eg
83}
84
85func nx_eg_rng_next(eg: *EpsilonGreedy) -> i64 {
86 let next: i64 = ((eg.rng_state * NX_EG_LCG_A) + NX_EG_LCG_C) & NX_EG_LCG_MOD
87 eg.rng_state = next
88 return next
89}
90
91func nx_eg_rng_below(eg: *EpsilonGreedy, n: i64) -> i64 {
92 let r: i64 = nx_eg_rng_next(eg)
93 return r % n
94}
95
96// === bitlen for decay =============================================
97
98func nx_eg_bitlen(x: i64) -> i64 {
99 if x <= 0 { return 0 }
100 var n: i64 = 0
101 var t: i64 = x
102 while t > 0 {
103 t = t >> 1
104 n = n + 1
105 }
106 return n
107}
108
109// === current epsilon =============================================
110
111func nx_eg_current_epsilon_ppm(eg: *EpsilonGreedy) -> i64 {
112 if eg.epsilon_mode == NX_EG_MODE_FIXED {
113 return eg.epsilon_ppm
114 }
115 if eg.epsilon_mode == NX_EG_MODE_DECAY_LINEAR {
116 let t: i64 = eg.total_pulls + 1
117 return eg.epsilon_ppm / t
118 }
119 if eg.epsilon_mode == NX_EG_MODE_DECAY_LOG {
120 let t: i64 = eg.total_pulls + 2 // +2 so log(t) >= 1
121 let lg: i64 = nx_eg_bitlen(t)
122 if lg <= 1 { return eg.epsilon_ppm }
123 return eg.epsilon_ppm / lg
124 }
125 return eg.epsilon_ppm
126}
127
128// === select =======================================================
129//
130// Explore (uniform random arm) with prob epsilon; else exploit
131// (arm with highest empirical mean). Untested arms are picked
132// uniformly at random during the explore phase, eventually all
133// arms get pulled.
134
135func nx_eg_best_arm_by_mean(eg: *EpsilonGreedy) -> i64 {
136 var best: i64 = 0
137 var best_mean: i64 = -1
138 var i: i64 = 0
139 while i < eg.n_arms {
140 if eg.counts[i] > 0 {
141 let m: i64 = eg.sum_rewards[i] / eg.counts[i]
142 if m > best_mean {
143 best = i
144 best_mean = m
145 }
146 }
147 i = i + 1
148 }
149 if best_mean < 0 {
150 // All arms untested: pick random.
151 return nx_eg_rng_below(eg, eg.n_arms)
152 }
153 return best
154}
155
156func nx_eg_select(eg: *EpsilonGreedy) -> i64 {
157 let eps_ppm: i64 = nx_eg_current_epsilon_ppm(eg)
158 let roll: i64 = nx_eg_rng_below(eg, 1000000)
159 if roll < eps_ppm {
160 // Explore.
161 return nx_eg_rng_below(eg, eg.n_arms)
162 }
163 // Exploit.
164 return nx_eg_best_arm_by_mean(eg)
165}
166
167// === update ======================================================
168
169func nx_eg_update(eg: *EpsilonGreedy, arm: i64, reward_ppm: i64) -> i64 {
170 if arm < 0 { return -1 }
171 if arm >= eg.n_arms { return -1 }
172 if reward_ppm < 0 { return -1 }
173 if reward_ppm > NX_EG_REWARD_MAX { return -1 }
174 eg.counts[arm] = eg.counts[arm] + 1
175 eg.sum_rewards[arm] = eg.sum_rewards[arm] + reward_ppm
176 eg.total_pulls = eg.total_pulls + 1
177 return 0
178}
179
180// === queries =====================================================
181
182func nx_eg_mean_ppm(eg: *EpsilonGreedy, arm: i64) -> i64 {
183 if eg.counts[arm] == 0 { return 0 }
184 return eg.sum_rewards[arm] / eg.counts[arm]
185}
186
187func nx_eg_count(eg: *EpsilonGreedy, arm: i64) -> i64 {
188 return eg.counts[arm]
189}
190
191func nx_eg_best_arm(eg: *EpsilonGreedy) -> i64 {
192 return nx_eg_best_arm_by_mean(eg)
193}
194
195// === isqrt for envelope ==========================================
196
197func nx_eg_isqrt(x: i64) -> i64 {
198 if x < 0 { return 0 }
199 if x == 0 { return 0 }
200 if x < 4 { return 1 }
201 var g: i64 = (x >> 1) + 1
202 var iter: i64 = 0
203 while iter < 64 {
204 let next_g: i64 = (g + x / g) / 2
205 if next_g >= g { iter = 64 }
206 if next_g < g {
207 g = next_g
208 iter = iter + 1
209 }
210 }
211 return g
212}
213
214func nx_eg_query(eg: *EpsilonGreedy, arm: i64) -> *ApproxI64 {
215 let m: i64 = nx_eg_mean_ppm(eg, arm)
216 let cnt: i64 = eg.counts[arm]
217 var stderr_ppb: i64 = 1000000000
218 if cnt > 0 {
219 let isq: i64 = nx_eg_isqrt(cnt)
220 if isq > 0 { stderr_ppb = 1000000000 / isq }
221 }
222 return nx_approx_new(m, NX_ENV_REL_STDDEV, stderr_ppb,
223 682700000,
224 NX_MATURITY_REFERENCE_IMPL,
225 NX_ADV_HONEST)
226}
227
228func nx_eg_memory_bytes(eg: *EpsilonGreedy) -> i64 {
229 return 56 + eg.n_arms * 16
230}