13 ms·

Lines of code that beat A/B testing (2012)

379 points by Kerrick 2y ago

asdasdsddd 2y ago
Multi arm bandits are fine but their limited to tests where its ok to switch users between arms frequently and tests that have more power
- tantalor 2y ago
  > where its ok to switch users between arms frequently It's not hard to keep track of which arm any given user was exposed to in the first run, and then repeat it.
  - asdasdsddd 2y ago
    There are often product limitations
85392_school 2y ago
Previously discussed: https://news.ycombinator.com/item?id=11437114 https://news.ycombinator.com/item?id=11437114 https://news.ycombinator.com/item?id=4040022 https://news.ycombinator.com/item?id=4040022
- dang 2y ago
  Thanks! Macroexpanded: 20 lines of code that beat A/B testing (2012) - https://news.ycombinator.com/item?id=11437114 https://news.ycombinator.com/item?id=11437114 - April 2016 (157 comments) 20 lines of code that beat A/B testing every time - https://news.ycombinator.com/item?id=4040022 https://news.ycombinator.com/item?id=4040022 - May 2012 (147 comments)
nottorp 2y ago
"People distrust things that they do not understand, and they especially distrust machine learning algorithms, even if they are simple." How times have changed :)
- saintfire 2y ago
  Just had to anthropomorphize machine learning.
  - iforgot22 2y ago
    More like, had to make it really good
isoprophlex 2y ago
As one of the comments below the article states, the probabilistic alternative to epsilon-greedy is worth exploring ad well. Take the "bayesian bandit", which is not much more complex but a lot more powerful. If you crave more bandits: https://jamesrledoux.com/algorithms/bandit-algorithms-epsilon-ucb-exp-python/ https://jamesrledoux.com/algorithms/bandit-algorithms-epsilo...
- hruk 2y ago
  We've been happy using Thompson sampling in production with this library https://github.com/bayesianbandits/bayesianbandits https://github.com/bayesianbandits/bayesianbandits
- timr 2y ago
  Just a warning to those people who are potentially implementing it: it doesn't really matter. The blog author addresses this, obliquely (says that the simplest thing is best most of the time), but doesn't make it explicit. In my experience, obsessing on the best decision strategy is the biggest honeypot for engineers implementing MAB. Epsilon-greedy is very easy to implement and you probably don't need anything more. Thompson sampling is a pain in the butt, for not much gain.
  - blagie 2y ago
    "Easy to implement" is a good reason to use bubble sort too. In a normal universe, you just import a different library, so both are the same amount of work to implement. Multiarmed bandit seems theoretically pretty, but it's rarely worth it. The complexity isn't the numerical algorithm but state management. * Most AB tests can be as simple as a client-side random() and a log file. * Multiarmed bandit means you need an immediate feedback loop, which involves things like adding database columns, worrying about performance (since each render requires another database read), etc. Keep in mind the database needs to now store AB test outcomes and use those for decision-making, and computing those is sometimes nontrivial (if it's anything beyond a click-through). * Long-term outcomes matter more than short-term. "Did we retain a customer" is more important than "did we close one sale." In most systems, the benefits aren't worth the complexity. Multiple AB tests also add testing complexity. You want to test three layouts? And three user flows? Now, you have nine cases which need to be tested. Add two color schemes? 18 cases. Add 3 font options? 54 cases. The exponential growth in testing is not fun. Fire-and-forget seems great, but in practice, it's fire-and-maintain-exponential complexity. And those conversion differences are usually small enough that being on the wrong side of a single AB test isn't expensive. Run the test. Analyze the data. Pick the outcome. Kill the other code path. Perhaps re-analyze the data a year later with different, longer-term metrics. Repeat. That's the right level of complexity most of the time. If you step up to multiarm, importing a different library ain't bad.
zahlman 2y ago
Nothing shows on this page without JavaScript except for the header and a grey background. A bit strange for a blog.
- forgetfreeman 2y ago
  Utterly unremarkable for 2012 though.
- lelandfe 2y ago
  Pre-CSS grid masonry layout. Author hides the content with CSS, and JS reveals it, to avoid a flash. CSS to make it noscript friendly: `.main { visibility: visible !important; max-width: 710px; }`
tracerbulletx 2y ago
A lot of sites don't have enough traffic to get statistical significance with this in a reasonable amount of time and it's almost always testing a feature more complicated than button color where you aren't going to have more than the control and variant.
- douglee650 2y ago
  Yes wondering what the confidence intervals are.
- wiml 2y ago
  If the effect size x site traffic is so small it's statistically insignificant, why are you doing all this work in the first place? Just choose the option that makes the PHB happy and move on. (But, it's more likely that you don't know if there's a significant effect size)
  - koliber 2y ago
    The PHB wanted A/B testing! True story. I've spent two months convincing them that it made no sense with the volume of conversion events we had.
    - wussboy 2y ago
      Another option, "I'm already doing A/B testing, trust me."
- deleted 2y ago
  [deleted]
- kridsdale1 2y ago
  I’ve only implemented A/B/C tests at Facebook and Google, with hundreds of millions of DAU on the surfaces in question, and three groups is still often enough to dilute the measurement in question below stat-sig.
- ryan-duve 2y ago
  > A lot of sites don't have enough traffic to get statistical significance with this in a reasonable amount of time What's nice about AB testing is the decision can be made on point estimates, provided the two choices don't have different operational "costs". You don't need to know that A is better than B, you just need to pick one and the point estimate gives the best answer with the available data. I don't know of a way to determine whether A is better than B with statistical significance without letting the experiment run, in practice, for way too long.
usgroup 2y ago
If your aim is to evaluate an effect size of your treatment because you want to know whether it’s significant, you can’t do what the article advises.
HeliumHydride 2y ago
The "20" is missing from the title.
- jerrygenser 2y ago
  I believe hacker news automatically truncates the number at the beginning of titles
jbentley1 2y ago
Multi-armed bandits make a big assumption that effectiveness is static over time. What can happen is that if they tip traffic slightly towards option B at a time when effectiveness is higher (maybe a sale just started) B will start to overwhelmingly look like a winner and get locked in that state. You can solve this with propensity scores, but it is more complicated to implement and you need to log every interaction.
- LPisGood 2y ago
  This objection is mentioned specifically in the post. You can add a forgetting factor for older results.
  - randomcatuser 2y ago
    This seems like a fudge factor though. Some things are changed bc you act on them! (e.g. recommendation systems that are biased towards more popular content). So having dynamic groups makes the data harder to analyze
    - LPisGood 2y ago
      A standard formulation of MAB problem assumes that acting will impact the rewards, and this forgetting factor approach is one which allows for that and still attempts to find the currently most exploitable lever.
  - lern_too_spel 2y ago
    That's a different problem. In jbentley1's scenario, A could be better, but this algorithm will choose B.
crazygringo 2y ago
No, multi-armed bandit doesn't "beat" A/B testing, nor does it beat it "every time". Statistical significance is statistical significance, end of story. If you want to show that option B is better than A, then you need to test B enough times. It doesn't matter if you test it half the time (in the simplest A/B) or 10% of the time (as suggested in the article). If you do it 10% of the time, it's just going to take you five times longer. And A/B testing can handle multiple options just fine, contrary to the post. The name "A/B" suggests two, but you're free to use more, and this is extremely common. It's still called "A/B testing". Generally speaking, you want to find the best option and then remove the other ones because they're suboptimal and code cruft. The author suggests always keeping 10% exploring other options. But if you already know they're worse, that's just making your product worse for those 10% of users.
- LPisGood 2y ago
  Multi-arm bandit does beat A/B testing in the sense that standard A/B testing does not seek to maximize reward during the testing period, MAB does. MAB also generalizes better to testing many things than A/B testing.
  - crazygringo 2y ago
    No -- you can't have your cake and eat it too. You get zero benefits from MAB over A/B if you simply end your A/B test once you've achieved statistical significance and pick the best option. Which is what any efficient A/B test does -- there no reason to have any fixed "testing period" beyond what is needed to achieve statistical significance. While, to the contrary, the MAB described in the article does not maximize reward -- as I explained in my previous comment. Because the post's version runs indefinitely, it has worse long-term reward because it continues to test inferior options long after they've been proven worse. If you leave it running, you're harming yourself. And I have no idea what you mean by MAB "generalizing" more. But it doesn't matter if it's worse to begin with. (Also, it's a huge red flag that the post doesn't even mention statistical significance.)
    - LPisGood 2y ago
__MatrixMan__ 2y ago
After this: > hundreds of the brightest minds of modern civilization have been hard at work not curing cancer. Instead, they have been refining techniques for getting you and me to click on banner ads I was really hoping this would slowly develop into a statistical technique couched in terms of ad optimization but actually settling in on something you might call ATCG testing (e.g. the biostatistics methods that one would indeed use to cure cancer).
JensRantil 2y ago
Yep. I implemented this as a Java library a while ago (and other stuff): https://github.com/JensRantil/java-canary-tools https://github.com/JensRantil/java-canary-tools Basically, I think feature flags and A/B tests aren't always needed to roll out experiments.
royal-fig 2y ago
If multi-arm bandits has piqued your curiosity, we recently added support for it to our feature flagging and experimentation platform, GrowthBook. We talk about it here: https://blog.growthbook.io/introducing-multi-armed-bandits-in-growthbook/ https://blog.growthbook.io/introducing-multi-armed-bandits-i...
munro 2y ago
Here's an interesting write up on various algorithms & different epsilon greedy % values. https://github.com/raffg/multi_armed_bandit https://github.com/raffg/multi_armed_bandit It shows 10% exploration performs the best, very great simple algorithm. Also it shows the Thompson Sampling algorithm converges a bit faster-- the best arm chosen by sampling from the beta distribution, and eliminates the explore phase. And you can use the builtin random.betavariate ! https://github.com/raffg/multi_armed_bandit/blob/42b7377541cb5c31356e5386af0cf66b5d3da579/algorithms/thompson_sampling.py#L22 https://github.com/raffg/multi_armed_bandit/blob/42b7377541c...
kazinator 2y ago
> Statistics are hard for most people to understand. True, but that's exactly what statistics helps with, though also hard to understand. :)
- hot_gril 2y ago
  People are hard for statistics to understand.
iforgot22 2y ago
I don't like how this dismisses the old approach as "statistics are hard for most people to understand." This algo beats A/B testing in terms of maximizing how many visitors get the best feature. But is that really a big enough concern IRL that people are interested in optimizing it every time? Every little dynamic lever adds complexity to a system.
- randomcatuser 2y ago
  Yeah basically. The idea is that somehow this is the data-optimal way of determining which one is the best (rather than splitting your data 50/50 and wasting a lot of samples when you already know) The caveats (perhaps not mentioned in the article) are: - Perhaps you have many metrics you need to track/analyze (CTR, conversion, rates on different metrics), so you can't strictly do bandit! - As someone mentioned below, sometimes the situation is dynamic (so having evenly sized groups helps with capturing this effect) - Maybe some other ones I can't think of? But you can imagine this kind of auto-testing being useful... imagine AI continually pushes new variants, and it just continually learns which one is the best
  - cle 2y ago
    It still misses the biggest challenge though--defining "best", and ensuring you're actually measuring it and not something else. It's useful as long as your definition is good enough and your measurements and randomizations aren't biased. Are you monitoring this over time to ensure that it continues to hold? If you don't, you risk your MAB converging on something very different from what you would consider "the best". When it converges on the right thing, it's better. When it converges on the wrong thing, it's worse. Which will it do? What's the magnitude of the upside vs downside?
    - desert_rue 2y ago
      Are you saying that it may do something like improve click-the-button conversion but lead to less sales overall?
  - iforgot22 2y ago
awkward 2y ago
Pure, disinterested A/B testing where the goal is just to find the good way to do it, and there's enough leverage and traffic that funding that A/B testing is worthwhile is rare. More frequently, A/B testing is a political technology that allows teams to move forward with changes to core, vital services of a site or app. By putting a new change behind an A/B test, the team technically derisks the change, by allowing it to be undone rapidly, and politically derisks the change, by tying it's deployment to rigorous testing that proves it at least does no harm to the existing process before applying it to all users. The change was judged to be valuable when development effort went into it, whether for technical, branding or other reasons. In short, not many people want to funnel users through N code paths with slightly different behaviors, because not many people have a ton of users, a ton of engineering capacity, and a ton of potential upside from marginal improvements. Two path tests solve the more common problem of wanting to make major changes to critical workflows without killing the platform.
- ljm 2y ago
  Tracks that I’ve primarily seen A/B tests used as a mechanism for gradual rollout rather than pure data-driven experimentation. Basically expose functionality to internal users by default then slowly expand it outwards to early adopters and then increment it to 100% for GA. It’s helpful in continuous delivery setups since you can test and deploy the functionality and move the bottleneck for releasing beyond that.
  - baxtr 2y ago
    I wouldn’t call that A/B testing but rather a gradual roll-out.
    - alex7o 2y ago
      I think parent is confusing A/B testing with feature flags, which can be used for A/B tests but also for roll-outs.
      - awkward 2y ago
taion 2y ago
The problem with this approach is that it requires the system doing randomization to be aware of the rewards. That doesn't make a lot of sense architecturally – the rewards you care about often relate to how the user engages with your product, and you would generally expect those to be collected via some offline analytics system that is disjoint from your online serving system. Additionally, doing randomization on a per-request basis heavily limits the kinds of user behaviors you can observe. Often you want to consistently assign the same user to the same condition to observe long-term changes in user behavior. This approach is pretty clever on paper but it's a poor fit for how experimentation works in practice and from a system design POV.
- ivalm 2y ago
  You can assign multiarm bandit trials on a lazy per user basis. So first time user touches feature A they are assigned to some trial arm T_A and then all subsequent interactions keep them in that trial arm until the trial finishes.
  - kridsdale1 2y ago
    The systems I’ve use pre-allocate users effectively randomly an arm by hashing their user id or equivalent.
    - s1mplicissimus 2y ago
      careful when doing that though! i've seen some big eyes when people assumed IDs to be uniform randomly distributed and suddenly their "test group" was 15% instead of the intended 1%. better generate a truely random value using your languages favorite crypto functions and be able to work with it without fear of busting production
      - np_tedious 2y ago
        The user ID is non uniform after hash and mod? How?
IshKebab 2y ago
This is fine as long as your users don't mind your site randomly changing all the time.
- data-ottawa 2y ago
  That’s also a problem for AB testing and solvable (to a degree) by caching assignments
- ryan-duve 2y ago
  This can be addressed with some variant of random.seed(hash(user_id)) I think the bigger problem is handling the fact that not all users click through the same number of times.
fitsumbelay 2y ago
I've only read the first paragraph so bear with me but I'm not understanding the reasoning behind "A/B testing drugs is bad because only half of the sample can potentially benefit" when the whole point is to delineate the gots and got-nots ...
- atombender 2y ago
  If the drug is effective and safe, then one half of the patients lost out on the benefit. You are intentionally "sacrificing" the control arm. (Of course, the whole point is that the benefit and safety are not certain, so I think the term "sacrifice" used in the article is misleading.)
  - kridsdale1 2y ago
    And the control group is also sacrificed from potentially deadly side effects.
    - rogerrogerr 2y ago
      My understanding is they usually do small trials early where they figure out if there are deadly side effects, and then do larger effectiveness trials once there’s determined to be minimal danger. So being in the control group is probably a negative thing on average.
m3kw9 2y ago
If you only keep your entire site static while test one variable change at a time, it could be statistically significant, other wise if your flow changes some where while you do this algo, it may be misleading you into a color and then under perform because you've made a change else where before users get to this page.
bartread 2y ago
Interesting post - certainly I can see myself wanting to tinker with Epsilon greedy - but the comments at the bottom are pretty off the chain, and many not in a good way. No auth commenting is certainly a brave decision in 2024.
- codazoda 2y ago
  I wish I could make this work without the mess though. Maybe an AI moderator could throw some of these away. Not that we need AI for everything, but I don’t have time to edit comments on my blog.
sweezyjeezy 2y ago
One of the assumptions of vanilla multi-armed bandits is that the underlying reward rates are fixed. It's not valid to assume that in a lot of cases, including e-commerce. The author is dismissive and hard wavy about this and having worked in in e-commerce SaaS I'd be a bit more cautious. Imagine that you are running MAB on an website with a control/treatment variant. After a bit you end up sampling the treatment a little more, say 60/40. You now start running a sale - and the conversion rate for both sides goes up equally. But since you are now sampling more from the treatment variant, its aggregate conversion rate goes up faster than the control - you start weighting even more towards that variant. Fluctuating reward rates are everywhere in e-commerce, and tend to destabilise MAB proportions, even on two identical variants, they can even cause it to lean towards the wrong one. There are more sophisticated MAB approaches that try to remove the identical reward-rate assumption - they have to model a lot more uncertainty, and so optimise more conservatively.
- ertdfgcvb 2y ago
  I don't follow. In this case would sampling 50/50 always give better/unbiased results on the experiment?
  - lern_too_spel 2y ago
    Yes.
  - sweezyjeezy 2y ago
    Sampling 50/50 will always give you the best chance of picking the best ultimate 'winner' in a fixed time horizon, at the cost of only sampling the winning variant 50% of the time. That's true if the reward rates are fixed or not. But some changes in reward rates will also cause MAB aggregate statistics to skew in a way that they shouldn't for a 50/50 split yeah.
    - zeroCalories 2y ago
      What do you think of using the epsilon-first approach then? We could explore for that fixed time horizon, then start choosing greedy after that. I feel like the only downside is that adding new arms becomes more complicated.
groby_b 2y ago
That's a statistically valid approach. Technically correct, the best kind of correct. Meanwhile, if your users get presented a different button whenever they come by, because the MAB is still pursuing its hill climbing, they'll rightfully accuse you of having extremely crappy UX. (And, sure, you can have MAB with user stickiness, but now you do need to talk about sampling bias) And MAB hill climb doesn't work at all if you want to measure the long-term reward of a variation. You have no idea if the orange button has long-term retention impact. There are sure situations where you'd like to know. Yes, it's a neat technique to have in your repertoire, but like any given technique, it's not the answer "every time".
- hot_gril 2y ago
  A/B testing has the same problem unless you figure out how to treat the same user the same way each time. But yeah I generally don't give much credence to an assertion like this that isn't based on a real-world experience. It's not even like "this algo might help," it's "will beat A/B testing every time."
ertdfgcvb 2y ago
I'm a layman. Isn't MAB changing the experiment parameters while the experiment is still running? That sounds like an easy way towards biased experiment results
- tjbai 2y ago
  From a purely technical definition of bias (difference in expected value of the estimator and the true value), MAB is not biased because "changing the experiment parameters" is just dynamically allocating a different sample size to each of the estimators, so the estimator still converges to the correct value. You are correct that this setup can potentially mislead you, but this is because you might end up getting estimators with high variance. So, you might mistakenly see some early promising results for experiment group A and greedily assign all the requests to that group, even though it is not guaranteed that A is actually better than B. This is the famous exploration-exploitation dilemma—should you maximize conversions by diverting everyone to group A or still try to collect more data from group B?
spmartin823 2y ago
Why would I introduce randomness where I don't have to? I'd regret this as soon as I had to debug something related to it.
- hot_gril 2y ago
  Regular A/B testing has the same kind of randomness. But this is more complex for other reasons.
rmacqueen 2y ago
How do you ensure the same user always gets the same treatment, even on subsequent visits to the site? You need the bucket sizes to be consistent for consistent hashing.
MichaelDickens 2y ago
# for each lever, # calculate the expectation of reward. # This is the number of trials of the lever divided by the total reward # given by that lever. # choose the lever with the greatest expectation of reward. If I'm not mistaken, this pseudocode has a bug that will result in choosing the expected worst option rather than the expected best option. I believe it should read "total reward given by the lever divided by the number of trials of that lever".
- reader9274 2y ago
  Correct, that's why I don't trust reading code comments
orasis 2y ago
Check out improve.ai if you want to see this taken to the next level. We combined Thompson Sampling with XGBoost to build a multi-armed bandit that learns to choose the best arm across context. MIT license.
jwr 2y ago
I've been using a Bernoulli bandit for many years now. Like the original author, I am not quite sure why more people don't use it — for all practical purposes, if you have stuff to do, it is superior to simple A/B testing in every way. The "set it and forget it" feature is really nice. Another thing that I noticed while writing the code (and took advantage of) is that it is insanely scalable in a distributed system, using HyperLogLog and Bloom filters. I may or may not have totally over-engineered my code to take advantage of that, even though my site gets ridiculously low click numbers :-)
- orasis 2y ago
  lol. My first MAB implementation also used HyperLogLog for tracking unique conversions. We over engineer alike it seems.
emsign 2y ago
So he compares users to slot machines. OK, I see why the internet sucks now 10 years later.
sarpdag 2y ago
I really like multi armed bandit approach, but struggles with common scenarios involving delayed rewards or multiple success criteria, such as testing ecommerce search with number of orders and GMV guardrails. For simple, immediate-feedback cases like button clicks, the specific implementation becomes less critical.
- orasis 2y ago
  It’s best for immediate rewards. If you have delayed rewards there is a paper on sampling from the “delay distribution” that solves this.
shireboy 2y ago
Are there any component libraries that just do this for you? Like an angular or Blazor component you put your variations in and it handles storing results and handling the logic.
quaxi 2y ago
A/B testing is a learning tool, not an optimization tool.
SideQuark 2y ago
What an odd, self-contradictory post. "In recent years, hundreds of the brightest minds of modern civilization have been hard at work not curing cancer.", along with phrases like "defective by design" and implied loss by not giving all people in a drug trial the new medicine, imply he thinks all of a thing needs allocated to what he perceives (incorrectly, trivially, shown below) as the best use. Then he states in the multiarm bandit to waste (from his multiple other statements) 10% of what is the best use on random other uses for exploration. However all this fails. For optimal output (be it drug research, allocation of brains, how to run a life), putting all resources on the problem/thing that is the "most important" is sub-optimal use of resources. It's always better expected return to allocate resources to where that spent resource has the best return. If that place is apps, not cancer, then wishing for brains to work on cancer because some would view that as a more important problem may simply be a waste of brains. So if cancer is going to be incredibly hard to solve, and mankind empirically gets utility from better apps, then a better use is to put those brains on apps - then they're not wasted on an probably not solvable problem and are put to use making things that do increase value. He also ignores that in real life the cost to have a zillion running experiments constantly flipping alternatives does not scale, so in no way can a company at scale replace A/B with multiarm bandits. One reason is simple: at any time a large company is running 1000s to maybe 100k A/B tests, each running maybe 6 months, at which point code path is selected, dead paths removed, and this repeats continually.If that old code is not killed, and every feature from all time needs to be on/off randomly, then there is no way over time to move much of the app forwards. It's not effective or feasibly to build many new features if you must also allow interacting with those from 5-10 years ago. A simple google shows tons more reasons, form math to practical, that this post is bad advice.

379 points by Kerrick 2y ago

Multi arm bandits are fine but their limited to tests where its ok to switch users between arms frequently and tests that have more power

tantalor 2y ago
> where its ok to switch users between arms frequently It's not hard to keep track of which arm any given user was exposed to in the first run, and then repeat it.
- asdasdsddd 2y ago
  There are often product limitations

85392_school 2y ago

Previously discussed: https://news.ycombinator.com/item?id=11437114 https://news.ycombinator.com/item?id=11437114 https://news.ycombinator.com/item?id=4040022 https://news.ycombinator.com/item?id=4040022

dang 2y ago
Thanks! Macroexpanded: 20 lines of code that beat A/B testing (2012) - https://news.ycombinator.com/item?id=11437114 https://news.ycombinator.com/item?id=11437114 - April 2016 (157 comments) 20 lines of code that beat A/B testing every time - https://news.ycombinator.com/item?id=4040022 https://news.ycombinator.com/item?id=4040022 - May 2012 (147 comments)

nottorp 2y ago

"People distrust things that they do not understand, and they especially distrust machine learning algorithms, even if they are simple." How times have changed :)

saintfire 2y ago
Just had to anthropomorphize machine learning.
- iforgot22 2y ago
  More like, had to make it really good

isoprophlex 2y ago

As one of the comments below the article states, the probabilistic alternative to epsilon-greedy is worth exploring ad well. Take the "bayesian bandit", which is not much more complex but a lot more powerful. If you crave more bandits: https://jamesrledoux.com/algorithms/bandit-algorithms-epsilon-ucb-exp-python/ https://jamesrledoux.com/algorithms/bandit-algorithms-epsilo...

hruk 2y ago
We've been happy using Thompson sampling in production with this library https://github.com/bayesianbandits/bayesianbandits https://github.com/bayesianbandits/bayesianbandits
timr 2y ago
Just a warning to those people who are potentially implementing it: it doesn't really matter. The blog author addresses this, obliquely (says that the simplest thing is best most of the time), but doesn't make it explicit. In my experience, obsessing on the best decision strategy is the biggest honeypot for engineers implementing MAB. Epsilon-greedy is very easy to implement and you probably don't need anything more. Thompson sampling is a pain in the butt, for not much gain.
- blagie 2y ago
  "Easy to implement" is a good reason to use bubble sort too. In a normal universe, you just import a different library, so both are the same amount of work to implement. Multiarmed bandit seems theoretically pretty, but it's rarely worth it. The complexity isn't the numerical algorithm but state management. * Most AB tests can be as simple as a client-side random() and a log file. * Multiarmed bandit means you need an immediate feedback loop, which involves things like adding database columns, worrying about performance (since each render requires another database read), etc. Keep in mind the database needs to now store AB test outcomes and use those for decision-making, and computing those is sometimes nontrivial (if it's anything beyond a click-through). * Long-term outcomes matter more than short-term. "Did we retain a customer" is more important than "did we close one sale." In most systems, the benefits aren't worth the complexity. Multiple AB tests also add testing complexity. You want to test three layouts? And three user flows? Now, you have nine cases which need to be tested. Add two color schemes? 18 cases. Add 3 font options? 54 cases. The exponential growth in testing is not fun. Fire-and-forget seems great, but in practice, it's fire-and-maintain-exponential complexity. And those conversion differences are usually small enough that being on the wrong side of a single AB test isn't expensive. Run the test. Analyze the data. Pick the outcome. Kill the other code path. Perhaps re-analyze the data a year later with different, longer-term metrics. Repeat. That's the right level of complexity most of the time. If you step up to multiarm, importing a different library ain't bad.

zahlman 2y ago

Nothing shows on this page without JavaScript except for the header and a grey background. A bit strange for a blog.

forgetfreeman 2y ago
Utterly unremarkable for 2012 though.
lelandfe 2y ago
Pre-CSS grid masonry layout. Author hides the content with CSS, and JS reveals it, to avoid a flash. CSS to make it noscript friendly: `.main { visibility: visible !important; max-width: 710px; }`

tracerbulletx 2y ago

A lot of sites don't have enough traffic to get statistical significance with this in a reasonable amount of time and it's almost always testing a feature more complicated than button color where you aren't going to have more than the control and variant.

douglee650 2y ago
Yes wondering what the confidence intervals are.
wiml 2y ago
If the effect size x site traffic is so small it's statistically insignificant, why are you doing all this work in the first place? Just choose the option that makes the PHB happy and move on. (But, it's more likely that you don't know if there's a significant effect size)
- koliber 2y ago
  The PHB wanted A/B testing! True story. I've spent two months convincing them that it made no sense with the volume of conversion events we had.
  - wussboy 2y ago
    Another option, "I'm already doing A/B testing, trust me."
deleted 2y ago
[deleted]
kridsdale1 2y ago
I’ve only implemented A/B/C tests at Facebook and Google, with hundreds of millions of DAU on the surfaces in question, and three groups is still often enough to dilute the measurement in question below stat-sig.
ryan-duve 2y ago
> A lot of sites don't have enough traffic to get statistical significance with this in a reasonable amount of time What's nice about AB testing is the decision can be made on point estimates, provided the two choices don't have different operational "costs". You don't need to know that A is better than B, you just need to pick one and the point estimate gives the best answer with the available data. I don't know of a way to determine whether A is better than B with statistical significance without letting the experiment run, in practice, for way too long.

usgroup 2y ago

If your aim is to evaluate an effect size of your treatment because you want to know whether it’s significant, you can’t do what the article advises.

HeliumHydride 2y ago

The "20" is missing from the title.

jerrygenser 2y ago
I believe hacker news automatically truncates the number at the beginning of titles

jbentley1 2y ago

Multi-armed bandits make a big assumption that effectiveness is static over time. What can happen is that if they tip traffic slightly towards option B at a time when effectiveness is higher (maybe a sale just started) B will start to overwhelmingly look like a winner and get locked in that state. You can solve this with propensity scores, but it is more complicated to implement and you need to log every interaction.

LPisGood 2y ago
This objection is mentioned specifically in the post. You can add a forgetting factor for older results.
- randomcatuser 2y ago
  This seems like a fudge factor though. Some things are changed bc you act on them! (e.g. recommendation systems that are biased towards more popular content). So having dynamic groups makes the data harder to analyze
  - LPisGood 2y ago
    A standard formulation of MAB problem assumes that acting will impact the rewards, and this forgetting factor approach is one which allows for that and still attempts to find the currently most exploitable lever.
- lern_too_spel 2y ago
  That's a different problem. In jbentley1's scenario, A could be better, but this algorithm will choose B.

crazygringo 2y ago

No, multi-armed bandit doesn't "beat" A/B testing, nor does it beat it "every time". Statistical significance is statistical significance, end of story. If you want to show that option B is better than A, then you need to test B enough times. It doesn't matter if you test it half the time (in the simplest A/B) or 10% of the time (as suggested in the article). If you do it 10% of the time, it's just going to take you five times longer. And A/B testing can handle multiple options just fine, contrary to the post. The name "A/B" suggests two, but you're free to use more, and this is extremely common. It's still called "A/B testing". Generally speaking, you want to find the best option and then remove the other ones because they're suboptimal and code cruft. The author suggests always keeping 10% exploring other options. But if you already know they're worse, that's just making your product worse for those 10% of users.

LPisGood 2y ago
Multi-arm bandit does beat A/B testing in the sense that standard A/B testing does not seek to maximize reward during the testing period, MAB does. MAB also generalizes better to testing many things than A/B testing.
- crazygringo 2y ago
  No -- you can't have your cake and eat it too. You get zero benefits from MAB over A/B if you simply end your A/B test once you've achieved statistical significance and pick the best option. Which is what any efficient A/B test does -- there no reason to have any fixed "testing period" beyond what is needed to achieve statistical significance. While, to the contrary, the MAB described in the article does not maximize reward -- as I explained in my previous comment. Because the post's version runs indefinitely, it has worse long-term reward because it continues to test inferior options long after they've been proven worse. If you leave it running, you're harming yourself. And I have no idea what you mean by MAB "generalizing" more. But it doesn't matter if it's worse to begin with. (Also, it's a huge red flag that the post doesn't even mention statistical significance.)
  - LPisGood 2y ago

__MatrixMan__ 2y ago

After this: > hundreds of the brightest minds of modern civilization have been hard at work not curing cancer. Instead, they have been refining techniques for getting you and me to click on banner ads I was really hoping this would slowly develop into a statistical technique couched in terms of ad optimization but actually settling in on something you might call ATCG testing (e.g. the biostatistics methods that one would indeed use to cure cancer).

JensRantil 2y ago

Yep. I implemented this as a Java library a while ago (and other stuff): https://github.com/JensRantil/java-canary-tools https://github.com/JensRantil/java-canary-tools Basically, I think feature flags and A/B tests aren't always needed to roll out experiments.

royal-fig 2y ago

If multi-arm bandits has piqued your curiosity, we recently added support for it to our feature flagging and experimentation platform, GrowthBook. We talk about it here: https://blog.growthbook.io/introducing-multi-armed-bandits-in-growthbook/ https://blog.growthbook.io/introducing-multi-armed-bandits-i...

munro 2y ago

Here's an interesting write up on various algorithms & different epsilon greedy % values. https://github.com/raffg/multi_armed_bandit https://github.com/raffg/multi_armed_bandit It shows 10% exploration performs the best, very great simple algorithm. Also it shows the Thompson Sampling algorithm converges a bit faster-- the best arm chosen by sampling from the beta distribution, and eliminates the explore phase. And you can use the builtin random.betavariate ! https://github.com/raffg/multi_armed_bandit/blob/42b7377541cb5c31356e5386af0cf66b5d3da579/algorithms/thompson_sampling.py#L22 https://github.com/raffg/multi_armed_bandit/blob/42b7377541c...

kazinator 2y ago

> Statistics are hard for most people to understand. True, but that's exactly what statistics helps with, though also hard to understand. :)

hot_gril 2y ago
People are hard for statistics to understand.

iforgot22 2y ago

I don't like how this dismisses the old approach as "statistics are hard for most people to understand." This algo beats A/B testing in terms of maximizing how many visitors get the best feature. But is that really a big enough concern IRL that people are interested in optimizing it every time? Every little dynamic lever adds complexity to a system.

randomcatuser 2y ago
Yeah basically. The idea is that somehow this is the data-optimal way of determining which one is the best (rather than splitting your data 50/50 and wasting a lot of samples when you already know) The caveats (perhaps not mentioned in the article) are: - Perhaps you have many metrics you need to track/analyze (CTR, conversion, rates on different metrics), so you can't strictly do bandit! - As someone mentioned below, sometimes the situation is dynamic (so having evenly sized groups helps with capturing this effect) - Maybe some other ones I can't think of? But you can imagine this kind of auto-testing being useful... imagine AI continually pushes new variants, and it just continually learns which one is the best
- cle 2y ago
  It still misses the biggest challenge though--defining "best", and ensuring you're actually measuring it and not something else. It's useful as long as your definition is good enough and your measurements and randomizations aren't biased. Are you monitoring this over time to ensure that it continues to hold? If you don't, you risk your MAB converging on something very different from what you would consider "the best". When it converges on the right thing, it's better. When it converges on the wrong thing, it's worse. Which will it do? What's the magnitude of the upside vs downside?
  - desert_rue 2y ago
    Are you saying that it may do something like improve click-the-button conversion but lead to less sales overall?
- iforgot22 2y ago

awkward 2y ago

Pure, disinterested A/B testing where the goal is just to find the good way to do it, and there's enough leverage and traffic that funding that A/B testing is worthwhile is rare. More frequently, A/B testing is a political technology that allows teams to move forward with changes to core, vital services of a site or app. By putting a new change behind an A/B test, the team technically derisks the change, by allowing it to be undone rapidly, and politically derisks the change, by tying it's deployment to rigorous testing that proves it at least does no harm to the existing process before applying it to all users. The change was judged to be valuable when development effort went into it, whether for technical, branding or other reasons. In short, not many people want to funnel users through N code paths with slightly different behaviors, because not many people have a ton of users, a ton of engineering capacity, and a ton of potential upside from marginal improvements. Two path tests solve the more common problem of wanting to make major changes to critical workflows without killing the platform.

ljm 2y ago
Tracks that I’ve primarily seen A/B tests used as a mechanism for gradual rollout rather than pure data-driven experimentation. Basically expose functionality to internal users by default then slowly expand it outwards to early adopters and then increment it to 100% for GA. It’s helpful in continuous delivery setups since you can test and deploy the functionality and move the bottleneck for releasing beyond that.
- baxtr 2y ago
  I wouldn’t call that A/B testing but rather a gradual roll-out.
  - alex7o 2y ago
    I think parent is confusing A/B testing with feature flags, which can be used for A/B tests but also for roll-outs.
    - awkward 2y ago

taion 2y ago

The problem with this approach is that it requires the system doing randomization to be aware of the rewards. That doesn't make a lot of sense architecturally – the rewards you care about often relate to how the user engages with your product, and you would generally expect those to be collected via some offline analytics system that is disjoint from your online serving system. Additionally, doing randomization on a per-request basis heavily limits the kinds of user behaviors you can observe. Often you want to consistently assign the same user to the same condition to observe long-term changes in user behavior. This approach is pretty clever on paper but it's a poor fit for how experimentation works in practice and from a system design POV.

ivalm 2y ago
You can assign multiarm bandit trials on a lazy per user basis. So first time user touches feature A they are assigned to some trial arm T_A and then all subsequent interactions keep them in that trial arm until the trial finishes.
- kridsdale1 2y ago
  The systems I’ve use pre-allocate users effectively randomly an arm by hashing their user id or equivalent.
  - s1mplicissimus 2y ago
    careful when doing that though! i've seen some big eyes when people assumed IDs to be uniform randomly distributed and suddenly their "test group" was 15% instead of the intended 1%. better generate a truely random value using your languages favorite crypto functions and be able to work with it without fear of busting production
    - np_tedious 2y ago
      The user ID is non uniform after hash and mod? How?

IshKebab 2y ago

This is fine as long as your users don't mind your site randomly changing all the time.

data-ottawa 2y ago
That’s also a problem for AB testing and solvable (to a degree) by caching assignments
ryan-duve 2y ago
This can be addressed with some variant of random.seed(hash(user_id)) I think the bigger problem is handling the fact that not all users click through the same number of times.

fitsumbelay 2y ago

I've only read the first paragraph so bear with me but I'm not understanding the reasoning behind "A/B testing drugs is bad because only half of the sample can potentially benefit" when the whole point is to delineate the gots and got-nots ...

atombender 2y ago
If the drug is effective and safe, then one half of the patients lost out on the benefit. You are intentionally "sacrificing" the control arm. (Of course, the whole point is that the benefit and safety are not certain, so I think the term "sacrifice" used in the article is misleading.)
- kridsdale1 2y ago
  And the control group is also sacrificed from potentially deadly side effects.
  - rogerrogerr 2y ago
    My understanding is they usually do small trials early where they figure out if there are deadly side effects, and then do larger effectiveness trials once there’s determined to be minimal danger. So being in the control group is probably a negative thing on average.

m3kw9 2y ago

If you only keep your entire site static while test one variable change at a time, it could be statistically significant, other wise if your flow changes some where while you do this algo, it may be misleading you into a color and then under perform because you've made a change else where before users get to this page.

bartread 2y ago

Interesting post - certainly I can see myself wanting to tinker with Epsilon greedy - but the comments at the bottom are pretty off the chain, and many not in a good way. No auth commenting is certainly a brave decision in 2024.

codazoda 2y ago
I wish I could make this work without the mess though. Maybe an AI moderator could throw some of these away. Not that we need AI for everything, but I don’t have time to edit comments on my blog.

sweezyjeezy 2y ago

One of the assumptions of vanilla multi-armed bandits is that the underlying reward rates are fixed. It's not valid to assume that in a lot of cases, including e-commerce. The author is dismissive and hard wavy about this and having worked in in e-commerce SaaS I'd be a bit more cautious. Imagine that you are running MAB on an website with a control/treatment variant. After a bit you end up sampling the treatment a little more, say 60/40. You now start running a sale - and the conversion rate for both sides goes up equally. But since you are now sampling more from the treatment variant, its aggregate conversion rate goes up faster than the control - you start weighting even more towards that variant. Fluctuating reward rates are everywhere in e-commerce, and tend to destabilise MAB proportions, even on two identical variants, they can even cause it to lean towards the wrong one. There are more sophisticated MAB approaches that try to remove the identical reward-rate assumption - they have to model a lot more uncertainty, and so optimise more conservatively.

ertdfgcvb 2y ago
I don't follow. In this case would sampling 50/50 always give better/unbiased results on the experiment?
- lern_too_spel 2y ago
  Yes.
- sweezyjeezy 2y ago
  Sampling 50/50 will always give you the best chance of picking the best ultimate 'winner' in a fixed time horizon, at the cost of only sampling the winning variant 50% of the time. That's true if the reward rates are fixed or not. But some changes in reward rates will also cause MAB aggregate statistics to skew in a way that they shouldn't for a 50/50 split yeah.
  - zeroCalories 2y ago
    What do you think of using the epsilon-first approach then? We could explore for that fixed time horizon, then start choosing greedy after that. I feel like the only downside is that adding new arms becomes more complicated.

groby_b 2y ago

That's a statistically valid approach. Technically correct, the best kind of correct. Meanwhile, if your users get presented a different button whenever they come by, because the MAB is still pursuing its hill climbing, they'll rightfully accuse you of having extremely crappy UX. (And, sure, you can have MAB with user stickiness, but now you do need to talk about sampling bias) And MAB hill climb doesn't work at all if you want to measure the long-term reward of a variation. You have no idea if the orange button has long-term retention impact. There are sure situations where you'd like to know. Yes, it's a neat technique to have in your repertoire, but like any given technique, it's not the answer "every time".

hot_gril 2y ago
A/B testing has the same problem unless you figure out how to treat the same user the same way each time. But yeah I generally don't give much credence to an assertion like this that isn't based on a real-world experience. It's not even like "this algo might help," it's "will beat A/B testing every time."

ertdfgcvb 2y ago

I'm a layman. Isn't MAB changing the experiment parameters while the experiment is still running? That sounds like an easy way towards biased experiment results

tjbai 2y ago
From a purely technical definition of bias (difference in expected value of the estimator and the true value), MAB is not biased because "changing the experiment parameters" is just dynamically allocating a different sample size to each of the estimators, so the estimator still converges to the correct value. You are correct that this setup can potentially mislead you, but this is because you might end up getting estimators with high variance. So, you might mistakenly see some early promising results for experiment group A and greedily assign all the requests to that group, even though it is not guaranteed that A is actually better than B. This is the famous exploration-exploitation dilemma—should you maximize conversions by diverting everyone to group A or still try to collect more data from group B?

spmartin823 2y ago

Why would I introduce randomness where I don't have to? I'd regret this as soon as I had to debug something related to it.

hot_gril 2y ago
Regular A/B testing has the same kind of randomness. But this is more complex for other reasons.

rmacqueen 2y ago

How do you ensure the same user always gets the same treatment, even on subsequent visits to the site? You need the bucket sizes to be consistent for consistent hashing.

MichaelDickens 2y ago

# for each lever, # calculate the expectation of reward. # This is the number of trials of the lever divided by the total reward # given by that lever. # choose the lever with the greatest expectation of reward. If I'm not mistaken, this pseudocode has a bug that will result in choosing the expected worst option rather than the expected best option. I believe it should read "total reward given by the lever divided by the number of trials of that lever".

reader9274 2y ago
Correct, that's why I don't trust reading code comments

orasis 2y ago

Check out improve.ai if you want to see this taken to the next level. We combined Thompson Sampling with XGBoost to build a multi-armed bandit that learns to choose the best arm across context. MIT license.

jwr 2y ago

I've been using a Bernoulli bandit for many years now. Like the original author, I am not quite sure why more people don't use it — for all practical purposes, if you have stuff to do, it is superior to simple A/B testing in every way. The "set it and forget it" feature is really nice. Another thing that I noticed while writing the code (and took advantage of) is that it is insanely scalable in a distributed system, using HyperLogLog and Bloom filters. I may or may not have totally over-engineered my code to take advantage of that, even though my site gets ridiculously low click numbers :-)

orasis 2y ago
lol. My first MAB implementation also used HyperLogLog for tracking unique conversions. We over engineer alike it seems.

emsign 2y ago

So he compares users to slot machines. OK, I see why the internet sucks now 10 years later.

sarpdag 2y ago

I really like multi armed bandit approach, but struggles with common scenarios involving delayed rewards or multiple success criteria, such as testing ecommerce search with number of orders and GMV guardrails. For simple, immediate-feedback cases like button clicks, the specific implementation becomes less critical.

orasis 2y ago
It’s best for immediate rewards. If you have delayed rewards there is a paper on sampling from the “delay distribution” that solves this.

shireboy 2y ago

Are there any component libraries that just do this for you? Like an angular or Blazor component you put your variations in and it handles storing results and handling the logic.

quaxi 2y ago

A/B testing is a learning tool, not an optimization tool.

SideQuark 2y ago

What an odd, self-contradictory post. "In recent years, hundreds of the brightest minds of modern civilization have been hard at work not curing cancer.", along with phrases like "defective by design" and implied loss by not giving all people in a drug trial the new medicine, imply he thinks all of a thing needs allocated to what he perceives (incorrectly, trivially, shown below) as the best use. Then he states in the multiarm bandit to waste (from his multiple other statements) 10% of what is the best use on random other uses for exploration. However all this fails. For optimal output (be it drug research, allocation of brains, how to run a life), putting all resources on the problem/thing that is the "most important" is sub-optimal use of resources. It's always better expected return to allocate resources to where that spent resource has the best return. If that place is apps, not cancer, then wishing for brains to work on cancer because some would view that as a more important problem may simply be a waste of brains. So if cancer is going to be incredibly hard to solve, and mankind empirically gets utility from better apps, then a better use is to put those brains on apps - then they're not wasted on an probably not solvable problem and are put to use making things that do increase value. He also ignores that in real life the cost to have a zillion running experiments constantly flipping alternatives does not scale, so in no way can a company at scale replace A/B with multiarm bandits. One reason is simple: at any time a large company is running 1000s to maybe 100k A/B tests, each running maybe 6 months, at which point code path is selected, dead paths removed, and this repeats continually.If that old code is not killed, and every feature from all time needs to be on/off randomly, then there is no way over time to move much of the app forwards. It's not effective or feasibly to build many new features if you must also allow interacting with those from 5-10 years ago. A simple google shows tons more reasons, form math to practical, that this post is bad advice.