Regret measures the outcome lost by experimenting instead of consistently choosing the alternative that ultimately proves best. In an ad-serving system, if model A has CTR 0.0050 and model B has CTR 0.0070, randomizing equally produces CTR 0.0060 and regret 0.0010. section 3.1.1
The metric makes exploration cost visible during optimization: every impression sent to an inferior version contributes to the gap between achieved performance and the best available performance. Adaptive selection can reduce that gap by exploiting the version with higher measured CTR while retaining some exploration. section 3.1.2 section 3.4
A/B testing versus epsilon-greedy
A simulated A/B test reaches about 0.0058–0.0060 CTR, compared with the best model's 0.0070, yielding roughly 0.0010 regret. With epsilon = 0.10, epsilon-greedy achieves about 0.0067–0.0068 CTR, leaving about 0.0003 regret. It begins by selecting A and B equally, then chooses the version with higher observed CTR 90% of the time and randomizes otherwise. section 3.1.1 section 3.1.2
Use regret to compare experimental policies operationally:
- Compare achieved business metrics with the counterfactual outcome from always selecting the best alternative. section 3.1.1
- Prefer adaptive exploration when ongoing operation matters; fixed A/B randomization retains linear-like regret, while decaying epsilon has asymptotically logarithmic regret. section 3.1.3 section 3.4
- Tune decaying epsilon carefully, because its regret advantage depends on the system-specific parameter c. section 3.1.3
- Validate complex contextual-bandit changes with an A/B test before relying on their operational performance. section 5.5
Listing 3.6 The epsilon-greedy algorithm
def epsilon_greedy(num_ind, epsilon):
sum_clicks = 0.0
num_ads = 0.0
sum_a = 0.0
num_a = 0
sum_b = 0.0
num_b = 0
ctr_vs_n = []
used_b = []
for _ in range(num_ind): #1
select = "Randomize"
if np.random.uniform(0,1) < 1-epsilon: #2
ctr_a = sum_a/num_a if num_a>0 else 0
ctr_b = sum_b/num_b if num_b>0 else 0
if ctr_a > ctr_b: #3
select = "A"
elif ctr_b > ctr_a: #3
select = "B"
# else, if they're equal, randomize
if select == "Randomize": #4
if np.random.uniform(0,1) < 0.5:
select = "A"
else:
select = "B"
if select == "A":
clicked = measure_a()
sum_a += clicked
num_a += 1
used_b.append(False)
else:
clicked = measure_b()
sum_b += clicked
num_b += 1
used_b.append(True)
sum_clicks += clicked
num_ads += 1
ctr_vs_n.append(sum_clicks / num_ads)
return ctr_vs_n, used_b
The implementation shows how epsilon-greedy alternates exploitation of the higher observed CTR with randomized exploration, making the source of reduced regret concrete. section 3.1.2
