Depending samples in ad ranking and click rate prediction

Question

I am struggling with the following problem: Suppose we fit a machine learning model to model advertisers click rates. I used a Logistic Regression approach using a one-hot/dummy encoding.

We have two advertisers A and B with a click rate of 10% and 9% respectively. Hence, we would rank A before B and would show users ads from A more often, say 90% of all times. Hence our overall click rate would be close to 10%.

Now we introduce a new feature which says a user either clicked on the advertiser before or not. For advertiser A, we observe a click rate of 8% for users that have not clicked before and a rate of 30% for users that have at least clicked once on an ad of the advertiser. For advertiser B we see no difference in the click rate for this feature.

So when it now comes to ranking the ads and we get a "fresh" user that has not clicked on both advertisers, we would rank B above A. Since fresh users are obviously more often, we would mostly show users ads from B, say 90%.

As a consequence, our overall click rate would drop from almost 10% to a little over 9%. The machine learning model does everything correct since we did not introduce any information that the two states of this new features are timely dependent.

From an intuitive approach I would still rank advertiser A over B for these fresh users since it's not clear if they're going to click.

Any ideas how to tackle this problem to get a ranking that in the end maximizes the click rate?