Wouldn't a multi-armed bandit help alleviate this issue? (Basically, randomly display a few other links, and use bayesian stats to figure out if the new links are more optimal).

That, or any kind of exploration/optimization algorithm, to be honest.