I think the big issue here is that the bandit problem assumes independence between machines, while this is almost certainly an incorrect assumption to make when analyzing user behavior. For example, I might be able to increase convergence by changing the button text to "buy now" and changing the background color to black, but not each one independently. Conversely, changing the button text to "buy now" might hurt convergence if the background color is black, but improve convergence if the background color is white.
Essentially that means that if I make N changes at the same time and convergence changes, it's not possible to tell which combination of the changes affected convergence, and how (at least not without a new series of hypothesis tests to establish controls). Perhaps only one change made the difference and the rest were irrelevant, perhaps multiple changes made the difference, etc.
The bandit problem is much simpler because it guarantees that none of the variables depend on each other. If there is no such guarantee, we're effectively stuck with searching through an exponentially large space of possibilities, and using NHST to tell the difference.
It also assumes that the distribution remains constant over time, an assumption that is, well, wrong.
But that's not very interesting. What's interesting is if it's still useful regardless, or if there is some sort of modification that would improve it taking that into account.
What you say is absolutely true of the basic bandit problem. More complex algorithms can deal with more complex problems, handling the interdependencies you describe. See the "bandit slate" problem, for example.
The slate problem still assumes each machine is independent (i.e. you want to pick k machines, but picking a particular machine does not effect the probability function of other machines). The ordered slate problem adds one more variable and deals with two dimensions, but it doesn't deal with an arbitrary number of dimensions.
Think about it - if you don't know which of the variables aren't independent, you're effectively searching an exponential space. You can prune it a bit but establishing that some variables are in fact independent, but the space of possibilities is still enormous. You can use standard multivariable function optimization techniques and set up correlation tests to guide the pruning, but you still need to use NHST at each one of these steps.
I agree with the general thrust of what you're saying -- it's a hard problem and no amount of algorithmic finesse can get around the basic problem of the exponentially growing space. In the context of this post, however, I think you can still do a lot better than A/B testing or MVT :).
Here's a paper that I think (I haven't read it in detail yet) addresses the problem you're talking about: http://arxiv.org/pdf/1105.4871v1
Another approach would be to model interactions as a (undirected?) Bayesian network and try to learn the structure of the network from data. I've had reasonable success doing this in the past but with a much simpler problem.
This is certainly something we're looking at, but I think there is enough work building a profitable business addressing the basic problem.
Yes, I think it's a huge commercial opportunity. I could use such a product too, and I sincerely wish you luck. However, the bandit approach is almost certainly not the right way to do it, and most of the value will come from the tools and integration, not a magical statistical model.
I do believe Bayesian network construction will work, though I don't know how much better it would do than NHST.
Woah, we've been talking past each other in a big way. Let me try to clarify:
1. The setup in the bandit problem is identical to the setup in standard A/B testing as applied to web content optimisation. The only difference is that in the bandit problem you are allowed make decisions as data arrives; in A/B testing you have to wait till your experiment completes (otherwise, see "early stopping" which in fact is how the bandit problem came to be). Algorithms for the bandit problem are strictly superior to A/B testing in this setup.
2. The case you seem to be interested in is where you have n possible items to display and you display k <= n simultaneously. In A/B testing land this is known as multivariate testing. The problem comes from dependencies between the items, otherwise it just reduces to k bandit problems. Typical MVT setups assume linear relationships between items. You can do the same in a bandit setup, and this what (I think from a quick read) the arxiv paper I linked above does.
3. NHST (null hypothesis statistical testing, right?) is not more powerful than a bandit algorithm. Consider this: in your hypothesis test you have a probability of making a mistake (determined by the p-value and probability of a type II error which you only indirectly control). The expected regret is thus Pr(error) * Cost(error) * forever (once you make your decision you're stuck with it). Thus the expected regret is infinite (due to that "forever" term). If you decide instead to continue making decisions the probability of making an error rises rapidly. If you decide to control for this you're reinventing sequential design of experiments / the bandit problem.
4. I blogged about the bandit problem because it's the direct analogue of A/B testing. That doesn't mean there aren't more powerful algorithms available in the field of decision theory. If you display your k items in sequence you're doing reinforcement learning, for which there are algorithms with optimal regret bounds. I've discussed k items simultaneously above. No doubt this is a hard problem. The key idea to take away is that you have to control for your uncertainty in the correct action, something that hypothesis testing doesn't do.
That was long; I hope it sheds some light. Oh, and drop me an email -- I've love to at least ask you more questions about the kind of product you'd use.
You misunderstand my criticism. The problem isn't that they're proposing an imperfect algorithm to a problem that's too computationally expensive to solve perfectly. The problem is that what they're proposing is strictly worse than NHST (which is the current status quo).
Look at it this way. If you're testing N different pieces of your site, trying Ni changes for each, and some of the variables are dependent on each other (which is almost certainly the case), then doing local improvements to each part is as likely to make the result worse as it is to make it better. NHST does not have that problem because you switch to a new layout only when you have enough evidence that it increases convergence. So the proposed algorithm is strictly worse than NHST. Not all imperfect algorithms are created equal.
Essentially that means that if I make N changes at the same time and convergence changes, it's not possible to tell which combination of the changes affected convergence, and how (at least not without a new series of hypothesis tests to establish controls). Perhaps only one change made the difference and the rest were irrelevant, perhaps multiple changes made the difference, etc.
The bandit problem is much simpler because it guarantees that none of the variables depend on each other. If there is no such guarantee, we're effectively stuck with searching through an exponentially large space of possibilities, and using NHST to tell the difference.