Randomized probability matching selects each alternative with probability equal to the estimated probability that it is best. In a production ad selector, a model estimated as best with probability 0.75 serves 75% of decisions, while a 0.25 model still receives 25%. The rule therefore combines exploitation with uncertainty-directed exploration rather than using fixed random traffic or always choosing the current leader. section 3.3.2 section 5.3.2
A practical implementation follows this loop:
- Create one bootstrap sample for each arm, estimate its metric, and select the arm with the highest sampled estimate; repeated sampling produces probability matching. section 3.3.2
- Use an online bootstrap to maintain many sampled estimates efficiently; increasing the number of bootstrap means improves approximation but slows execution. section 3.3.3
- Force sampling of under-observed arms until each has enough measurements to resolve practically significant differences, then apply randomized selection. section 3.3.3
- Stop when an arm's probability of being best exceeds a threshold such as 0.95; uncertainty normally decreases as observations accumulate. section 3.3
Ad selection
Suppose click models A and B have pbest(A) = 0.75 and pbest(B) = 0.25. Randomized probability matching serves A three times as often as B in expectation. In a contextual recommender, randomly selecting one of ten equally credible models can yield the same rule: if seven models choose post 1 and three choose post 2, the policy displays those posts with probabilities 0.7 and 0.3. section 3.3.2 section 5.3.2
