We needed a principled approach to help find heterogenous treatment effects and to discover if A/B Tests with more than 2 arms were potentially interacting with one another. Most approaches seem to just use single t-tests with multiple comparison adjustments, but this approach just became too unwieldly at scale.
Anyone else use the F-test with nested regression? Or find some other useful approach beyond collections of individual A/B tests?
A simple Zero analysis Multi-Armed Bandit
Reproposing Pearson-Neyman sample size calculations to create simple bandits with no need for dedicated software. Obviously not optimal but often a very good option.
Are you suggesting that revenues fell after bailing on SMB. That is hard to imagine, but I guess possible. Given that the core of the industry is about asking counterfactual questions, I would think the appropriate question would be 'would they be more valuable now if they had not gone to the enterprise - would they even have the deal they did wind up getting?'rather than are they more valuable now then they were 4 years ago.
Hard to know, but my guess is that they wouldn't. A simple web editor with a random number generator isn't going to be of interest to anyone looking to buy.
The larger problem is that statistical inference is hard - it just is. And, unlike analytics, where you are just placing sensors into an existing system, here you need to also place actuators, so implementation is much more complicated. That means that at any scale, both the marketing team, and the dev/IT teams need to be involved for anyone to get value and not wind up breaking systems all the time.
Software like theirs, and ours, isn't magic, and without good editorial and hard work by the client, the entire exercise is more statistical theater than science. And that material fact was always in conflict with the rhetoric that they make AB Testing easy for everyone. It lends itself to a particular type of solutionism that VCs and the larger industry are prone to be seduced by.
Self service to SMB clients might be a profitable biz, but perhaps not enough to service such a large amount of venture funding.
FWIW VWO also tries compete at the enterprise.
When thinking about what type of approach is best, first think about the nature of the problem. First is it a real optimization problem, IOW are you more concerned with learning an optimal controller for your marketing application? If so then ask:
1) Is the problem/information perishable - for example Perishable: picking headlines for News articles; Not Perishable: Site redesign. If Perishable then Bandit might give you real returns.
2) Complexity: Are you using covariates (contextual bandits, Reinforcement learning with function approximation) or not. If you are, then you might want your targeting model to serve up best the predicted options in subspaces (frequent user types) that it has more experiences in and for it to explore more in less frequently visited areas (less common user types).
3) Scale/Automation: You have tons of transactional decision problems, and it just doesn't scale to have people running many AB Tests.
Often it is a mix - you might use a bandit approach with your predictive targeting, but you also should A/B tests the impact of your targeting model approach vs a current default and/or a random draw. see slides 59-65: http://www.slideshare.net/mgershoff/predictive-analytics-bro...
I read GEB as my subway book, back in 1999 (during a work stint in Paris), during my daily commute to work. Years later, when I was looking for a change, I started thinking about GEB. Even though I had no CS background,I decided to apply to a few AI programs and wound up going to the University of Edinburgh for an Msc. in AI in '05. Now I am a co-founder of software start up that applies reinforcement learning, a method from ai -lower case ;-) to conversion optimization. Obviously, I can't say if you will find it a worthwhile read, but I do look back on it as a significant influence on a major pivot in my life.
I think what makes Hinton surprising is that he has a long established academic lab and so many current top researchers went through that lab. Yann LeCun (ANNs/Deep Learning), Chris Williams, (GPs), Carl Rasmussen (GPs), Peter Dayan (NeuroScince and TD-Learning), Sam Roweis (RIP).
As you note, industrial research labs (with Nobel prize winning researchers) have been around at IBM, NEC, and ATT Bell etc.
One thing that I think about, is what happens to the quality of research as top folks who have an established record of producing new researchers are pulled from that role?
Also not sure about startups having anything to do with with making technology real. Is Google still a startup?
I reached out to Yann LeCun and he emailed me a couple more recent links. I updated the deep learning section of the post to include them. Feel free to check them out.
Thanks! Sure, I didn't mean to imply that once you learn Linear Algebra you are all done - just that it you really need it and will make your life much easier once you do.
Yeah, I didn't include a ton of stuff - nothing on EM, trees, boosting, etc. Prob the biggest thing missing is something explicitly about regularization. Maybe I will add something there.
Please feel free to add stuff you think others might be interested in down in the comments section of the post.
Thanks again for the comments and taking the time to read through it and don't forget to sign up for a free account!
Huh, looks like all of the companies are out of NY and mostly fashion related. Its too bad it was more of a PR piece for these companies, rather than a deeper look at gender and class.
Disclaimer: I also have software for running AB/MVT as well as adaptive control problems (so bandits as well as extended sequential decisions) at www.conductrics.com.
I wouldn't sweat too much UCB methods vs e-greedy or other heuristics for balancing explore/exploit. E-greedy (and e-greedy decreasing) is nice because it is simple. Softmax/Boltzman, is interesting since it is satisfying in that it selects arms weighted by the estimated means, and UCB-Tuned and UCB-Normal are nice because, like AB testing, they take variance measures directly into account when selecting an arm.
Take a look at this paper from Doina Precup (who is super nice BTW) and Volodymyr Kuleshov from 2000 http://www.cs.mcgill.ca/~vkules/bandits.pdf they have comparisons between various methods. Guess what - the simple methods work just fine.
Of course there are various Bayesion versions - esp of UCB. Nando de Freitas over at UBC has a recent ICML paper on using the Gaussian Process for Bandits (based on a form of UCB). See http://www.cs.ubc.ca/~nando/papers/BayesBandits.pdf
I have not given it a tight read, but not sure what the practical return would be. Plus you have to fiddle with picking a Kernel function, and I imagine length scales and the rest of hyper parameters associated with GPs.
I did read a working paper from Nando a few years back that used a random forest as a prior - I can't seem to find it now.
BTW - John Langford is program chair of this year’s ICML over in Edinburgh. If you are in the UK might be worth it to pop up and attend. Plus Chris Williams is there at Edinburgh, so maybe you can corner him about GPs. Although he has moved on from GPs - he still wrote (well, co-wrote) the book and is one of the smartest people I have ever met.
This is a good coversation.
So the Disclaimer, my company Conductrics.com allows you to use algos similar to bandits as well as AB/MVT.
AB can be thought of as more of a form of epoch- greedy - you play uniform random then play greedy. One advantage of e-greedy is that if your environment is not stationary - you are still sampling from the arms - its sort of an insurance premium.
To address the differences in reward signals based on the environment, there is the option to model the environment with features - since it maybe that Fridays require a different selection than Sundays - not sure why you would a priori assume that the relative values, or even just the arm rankings are independent of environmental variables.
One other point- if you just want a super quick hack to pick winners (or at least pick from te set of higher performing arms) you can just optimistically seed your estimates for each arm - then just pick greedy. Not claiming it is optimal or anything but it requires almost no coding overhead. Of course you need the problem to be stationary.
Regardless of which algo approach you use, I do think it is useful to at least think in terms of bandits or reimforcemt learning when tackling these problems.
Is that true in the e-greedy case? Sure, during the exploit call, they are not independent, but during the explore portion I would assume they are, since they have been randomly assigned into the exploration pool (epsilon) and then drawn from a uniform random draw. There is no information that I can see from prior draws being used.
Of course, of the environment is truely stationary, then the easiest simpest hack method for exploration is just seed the initial values for each option (A/B../Z) with a an optimistic guess (so something you know is higher than the true value. Then just make decisions based on the current best estimate. The estimates will be driven down over time to their true values. Not claiming you should do this or that is optimal or anything but keep it in mind as a quick hack to solve the problem.
You might want to look at botlzman/softmax if you want to weight the prob of selection as a function of the current estimated value. One tricky bit is figuring out a good setting for the temperature parameter. Another poster alluded to softmax. In my experience it dosn't really perform better than a simple e-greedy approach, but maybe it has worked well for others?
A GA is a zeroth order optimization method. A Bandit is a type of decision problem. So, bandit is a single state RL problem were one is trying to make decisions in an environment in order to min regret. GA is a general optimization approach when there is no gradient or second order info about the problem to use.
Take a look at XCS classifiers for an approach that can solve bandit type problems, but uses GAs to estimate the mailings between features and rewards.
Well I guess you could be running a MANOVA or something to test over joint outcomes, but the AB test is over some sort of metric. I mean, when you set up an experiment, you need to have defined the dependent variable first.
Now, after you have randomly split your treatment groups you can do post hock analysis, which I think is what you are referring to. But if you are optimizing, here needs to be some metric to optimize over.
Of course at the end of the day the hypothesis test just tells you prob(data or greater| null=true) which I am not sure provides a direct path to decision making.
I think rather than get hung up on e-greedy vs. A/B testing vs UCB (Bayesian vs. non Bayesian), it is helpful to first step back and think about the larger problem of online learning as a form of the prediction/control problem. The joint problem is to 1)LEARN (estimate) the values of possible courses of action in order to predict outcomes.
and 2)CONTROL the application by selecting the best action for a particular situation.
I noted elsewhere that A/B can be though of as an epsilon-first learning approach, Play random 100% till P-value<alpha, then play greedy(play the 'winner'). As an aside, it is unclear to me how using p-values is a clearer, easier, or more efficient, decision rule for these types of problems. It is almost always misinterpreted as the Prob(B>A|Data), choice of alpha determines threshold but is arbitrary, and often a straw-man default - implicitly biasing your confusion matrix. Not saying that you won't get good results, just that it is not clear that is a dominate approach.
But don't take my word for it (disclaimer: I work for www.conductrics.com, which provides decision optimization as a service) take a look at a great intro text on the topic by Sutton & Barto http://webdocs.cs.ualberta.ca/~sutton/book/ebook/the-book.ht...
Actually, you kind of are already in the RL space when using AB testing to make online decisions, you just may not be thinking of it that way.
From Sutton & Barto "Reinforcement learning is learning what to do--how to map situations to actions--so as to maximize a numerical reward signal."
That is exactly what you are doing when applying A/B style hypothesis testing to inform decisions in an online application.
Plus, personally, I think A/B testing is, in a way, much harder to interpret, at least most folks interpret wrong, which isn't a knock, since it is provides a non-intuitive - at least to me ;) - result.
If you are using an epsilon-greedy approach (or something similar), then I believe that the data collected during the exploration portion - (the random calls) are open, albeit with less power due to reduced sample size, to standard hypothesis testing.
Think of it this way, you might normally run your experiment on a subset of your traffic (population) - so only 20%, with the rest (80%) getting the current experience. With the e-greedy type of approach you are just swapping the 'current experience' with the maximum estimated experience, but that other 20% is still a random draw.
This is part of a larger class of problems known as reinforcement learning problems. A/B testing when used for decision optimization can be thought of (sort of) as just a form of bandit using an epsilon-first approach. You play random until some threshold (using some sort of arbitrary hypothesis test), which is the learning period, then you exploit your knowledge and play estimate best option.
Epsilon-greedy is nice because it tends to work well regardless, and isn't completely affected by drift (nonstationarity of the environment).
One heuristic to use for deciding between using a bandity approach is to ask , is the information I will glean perishable or not pershible? For perishable problems the opportunity cost to learn is quite high, since you have less time to recoup your investment in learning (reducing the uncertainty in your estimates).
Also, finding the optimal answer in these situations may be less important than just ensuring that you are playing from the set of high performing actions.
We have a couple of blog posts on related issues
http://www.conductrics.com/blog/