About Me¶
 |
 |
Principal Data Scientist and Director of Monetate Labs¶
@AustinRochford • austinrochford.com • github.com/AustinRochford¶
arochford@monetate.com • austin.rochford@gmail.com¶
About Monetate¶
- Founded 2008, web optimization and personalization SaaS
- Observed 5B impressions and $4.1B in revenue during Cyber Week 2017
Non-technical marketer-focused¶
Outline¶
- Web optimization
- A/B testing
- Multi-armed bandits
- Bayesian bandits
- Thompson sampling
- Bandit bias
- Inverse propensity weighting
A/B testing machinery¶
|
|
Sequential testing¶
|
|
Sequential optimization¶
Multi-armed bandits¶
Multi-armed bandit systems¶
Bayesian Bandits¶
Beta-binomial model¶
xA,xB=number of rewards from users shown variant A,BxA∼Binomial(nA,rA)xB∼Binomial(nB,rB)rA,rB∼Beta(1,1)
rA | nA,xA∼Beta(xA+1,nA−xA+1)rB | nB,xB∼Beta(xB+1,nB−xB+1)
Thompson sampling¶
Thompson sampling randomizes user/variant assignment according to the probabilty that each variant maximizes the posterior expected reward.
The probability that a user is assigned variant A is
P(rA>rB | D)=∫10P(rA>r | D) πB(r | D) dr=∫10(∫1rπA(s | D) ds) πB(r | D) dr∝∫10(∫1rsαA−1(1−s)βA−1 ds)rαB−1(1−r)βB−1 dr
In [7]:
fig
Out[7]:
In [10]:
fig
Out[10]:
In [11]:
(a_samples > b_samples).mean()
Out[11]:
0.247
Thompson sampling, redeemed¶
- Sample ˆrA∼rA | nA,xA and ˆrB∼rB | nB,xB.
- Assign the user variant A if ˆrA>ˆrB, otherwise assign them variant B.
Simulating a bandit¶
In [12]:
class BetaBinomial:
def __init__(self, a0=1., b0=1.):
self.a = a0
self.b = b0
def sample(self):
return sp.stats.beta.rvs(self.a, self.b)
def update(self, n, x):
self.a += x
self.b += n - x
In [13]:
class Bandit:
def __init__(self, a_post, b_post):
self.a_post = a_post
self.b_post = b_post
def assign(self):
return 1 * (self.a_post.sample() < self.b_post.sample())
def update(self, arm, reward):
arm_post = self.a_post if arm == 0 else self.b_post
arm_post.update(1, reward)
In [15]:
A_RATE, B_RATE = 0.05, 0.1
N = 1000
rewards_gen = generate_rewards(A_RATE, B_RATE, N)
In [16]:
bandit = Bandit(BetaBinomial(), BetaBinomial())
arms = np.empty(N, dtype=np.int64)
rewards = np.empty(N)
for t, arm_rewards in tqdm(enumerate(rewards_gen), total=N):
arms[t] = bandit.assign()
rewards[t] = arm_rewards[arms[t]]
bandit.update(arms[t], rewards[t])
100%|██████████| 1000/1000 [00:00<00:00, 5443.70it/s]
In [18]:
fig
Out[18]:
Simulating many bandits¶
In [20]:
N_BANDIT = 100
arms = np.empty((N_BANDIT, N), dtype=np.int64)
rewards = np.empty((N_BANDIT, N))
for i in trange(N_BANDIT):
arms[i], rewards[i] = simulate_bandit(
generate_rewards(A_RATE, B_RATE, N), N
)
100%|██████████| 100/100 [00:11<00:00, 8.98it/s]
In [22]:
fig
Out[22]:
A/A testing¶
A/A bandits¶
In [24]:
N = 2000
arms, rewards = simulate_bandits(
lambda: generate_rewards(A_RATE, A_RATE, N),
N, N_BANDIT
)
100%|██████████| 100/100 [00:22<00:00, 4.57it/s]
In [26]:
fig
Out[26]:
In [28]:
fig
Out[28]:
Why Bayesian?¶
- Thompson sampling is intuitive and simple to implement
- Principled randomization
- Robustness against delayed feedback
- Marketers are natural Bayesians!
Bandit Bias¶
In [31]:
fig
Out[31]:
In [33]:
fig
Out[33]:
In [35]:
fig
Out[35]:
Inverse propensity weighting¶
ˆrIPSA=1nn∑t=1Yi⋅I(At=1)P(At=1 | D1,t−1)
where
At={1session t saw variant A0session t saw variant B.
Calculating P(At=1 | D1,t−1)
In [36]:
ts_fig
Out[36]:
In [38]:
%%time
N_MC = 500
a_samples = sp.stats.beta.rvs(
a_post_alpha[..., np.newaxis],
a_post_beta[..., np.newaxis],
size=(N_BANDIT, N, N_MC)
)
b_samples = sp.stats.beta.rvs(
b_post_alpha[..., np.newaxis],
b_post_beta[..., np.newaxis],
size=(N_BANDIT, N, N_MC)
)
a_prob = np.empty((N_BANDIT, N))
a_prob[:, 0] = 0.5
a_prob[:, 1:] = (a_samples > b_samples).mean(axis=2)[:, :-1]
CPU times: user 15 s, sys: 2.82 s, total: 17.8 s Wall time: 17.9 s
In [40]:
a_ips_est = 1. / plot_t * (rewards * (arms == 0) / a_prob_).cumsum(axis=1)
b_ips_est = 1. / plot_t * (rewards * (arms == 1) / (1 - a_prob_)).cumsum(axis=1)
In [42]:
fig
Out[42]:
Bias-variance tradeoff¶
In [44]:
fig
Out[44]:
Intuition: the variant with the highest reward rate should receive the most traffic.
In [47]:
fig
Out[47]:
Two Years of Bayesian Bandits for E-Commerce¶PyData NYC • October 18, 2018 • @AustinRochford¶