Online bootstrap sampling incrementally maintains bootstrap estimates as observations arrive. For each new measurement, include it in each running bootstrap sample with probability 1/2, updating that sample’s sum and count. Divide the sum by the count when an estimate is needed. section 3.3.2
The technique avoids rescanning the complete dataset during every decision. Full bootstrap sampling makes repeated decisions grow toward O(T²); tracking B incremental bootstrap means reduces the total work to O(TB), so decision time does not grow with experiment duration. section 3.3.2
A practical implementation maintains:
- A running sum and observation count for each of B bootstrap means. section 3.3.2
- An append operation that independently includes each new measurement with probability 1/2. section 3.3.2
- A sampling operation that selects one maintained mean; an empty sample returns infinity to encourage initial observation. section 3.3.2
Using online bootstrap for ad selection
Maintain one OnlineBootstrap instance per ad or click model. After measuring a click, append the binary result to the selected instance. Randomized probability matching samples a CTR estimate from every instance and selects the highest, using repeated samples to estimate each arm’s probability of being best. A production loop can maintain 100 bootstrap means per arm; because estimating pbest remains relatively expensive, call it once every 100 iterations rather than on every decision. section 3.3.2 section 3.3.3
Listing 3.14 Online Bootstrap
class OnlineBootstrap:
def __init__(self, num_bs_means): #1
self._sums = np.zeros(shape=(num_bs_means,)) #2
self._n = np.zeros(shape=(num_bs_means,)) #2
self._count = 0 #3
def append(self, clicked):
i = np.where(np.random.randint(2, size=(len(self._n,))) == 0)[0]
self._sums[i] += clicked
self._n[i] += 1
self._count += 1
def CTR_estimate(self):
i = np.random.randint(len(self._n)) #4
if self._n[i] == 0:
return np.inf #5
return self._sums[i] / self._n[i] #6
def count(self):
return self._count
Inspect the compact OnlineBootstrap implementation, including state initialization, incremental updates, random estimate selection, and the empty-sample safeguard. section 3.3.2
