You're basically correct in your assessment. The time to converge to the optimal action is formalised as the accumulated regret. This is the sum of the error ma

You're basically correct in your assessment. The time to converge to the optimal action is formalised as the accumulated regret. This is the sum of the error made over time. If you assume the landscape is static -- called stationary in the literature -- you can achieve within a constant factor of optimal regret. Good algorithms only differ in their constant factors. If the landscape is not static it is called non-stationary. Amazingly you can still be optimal (for a slightly different definition of optimal) in the non-stationary case! This is called the nonstochastic bandit in the literature. Finally, are websites static or not? It depends :) However it seems that most are static. At least the one where we're applying our tech. are. Something like Amazon probably wouldn't be, but the non-stationary bits of their problem are probably best viewed as a product recommendation problem. UI tweaks might still be reasonably modelled as stationary.