What is the ideal banner rotation algorithm?

Question

contextual advertising

There are conditionally 500 banners. Half of the income from each banner for 1000 impressions is known (constantly recalculated). The second half is new. It needs to be in rotation.
Which banner to show? Read about weighted random sampling. You can assign each banner its own "weight" depending on the CPM. The probability of showing a banner in this case will be directly proportional to the weight of a particular banner, relative to the sum of the weights of all banners to be rotated.
But here comes another problem. A particular user may not be interested in this banner at all, although its weight will be large throughout the system. How to proceed in this case?
I would be grateful for any links on this topic.

Answer 1

It really depends on the tasks of a particular banner spinner: it is a large advertising network, an internal rotator, etc.
The general principle is this:

# берем список баннеров, которые могут таргетироваться на этого пользователя
banners = get_banners(session)

# большую часть показов (например, 90%) нужно откручивать тем пользователям, для которых ожидаемая полезность максимальна
if random.randint(0,100) > 10: 
    # предсказываем потенциальную прибыль
    banners = {x : predict(x) for x in banners}
    # находим баннер с максимальной прогнозной прибылью
    banner = max(banners, key=lambda k: banners[k])  
    show(banner)
# остальные показы случайные, чтобы модель могла обучаться
else:
  show(random.choice(banners))

The most interesting thing is which model to predict profit. And here it all depends on the characteristics of the task. In the simplest case, eCPM is usually considered, but it is rational to use combined models that use machine learning and all sorts of business restrictions, such as the number of impressions per user.

Answer 2

limit the number of impressions per user.

Answer 3

w-shadow.com/blog/2008/12/10/fast-weighted-random-...