So the concern then is the time it takes to converge on an optimal value? Is that even possible?
I'm not a content optimization expert by any means, so I'm just curious if we have any evidence that the landscape is static. It seems entirely possible (maybe even probable) that an optimal option now may grow stale and actually be suboptimal next week/month.
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.
Why wouldn't you use TD-learning? You have what seems like a relatively small state space that conforms well to a table representation. You need to assume it's Markovian, but you can just artificially inflate the state to include 3-4 clicks of history. Seems straight-forward, right?