Could you explain the problem a little more? From what you wrote here, it sounds like the problem is that if the world changes, it can mess up your answers, and bandit will take exp(N) time to catch up.
This is a problem for A/B testing also - if the world changes after your test is finished, you just got the wrong answer. Or am I missing something?
This is why you run tests which you expect to be statistically independent of each other and why you stick to results you expect to be durable.
I'd love it if you email me about it (or post publicly on the topic). I'm thinking of writing a "real world bandit benchmarking suite" which will take into account as many such situations as possible.
The problem is that the world changes - constantly. What changes could mess you up? When we apply math to the real world we should assume as little as possible.
A/B testing is robust in the face of absolute changes in conversion rates so long as preferences remain consistent. Of course preferences do not always remain consistent, but that is substantially more likely to happen than that conversion rates do not budge.
Traditional MAB approaches are not robust in the face of absolute changes in conversion rates, even if preferences remain consistent. The problematic change is what happens if conversion rates improve while the worse version is ahead. Then you can come to very solidly to the conclusion that the worse version is better, and be stuck on that for a depressingly long time. The smarter the MAB algorithm, the more solidly you can make that mistake.
Is this likely? Well most businesses have regular fluctuations in conversion rates. Furthermore websites under continuous improvements are constantly introducing changes. It is therefore not uncommon to, while testing one thing, make independent changes that are likely to improve conversion rates.
But as I said, the simple change to throw away data collected during exploitation makes a MAB approach also robust in the face of absolute changes in conversion rates, as long as preferences remain consistent. Doing so increases average regret by a constant factor in the case where conversion rates never change.
(There are complications in the more than 2 arm case. In particular the fact that you're uncertain about A vs C doesn't mean that you should continue exploring version B. So some observations should count as exploration between a strict subset of the versions. But that's a technical detail.)
This is a problem for A/B testing also - if the world changes after your test is finished, you just got the wrong answer. Or am I missing something?
This is why you run tests which you expect to be statistically independent of each other and why you stick to results you expect to be durable.
I'd love it if you email me about it (or post publicly on the topic). I'm thinking of writing a "real world bandit benchmarking suite" which will take into account as many such situations as possible.