A new paper nails down exactly how much performance you give up when a decision problem has more than one right answer.
The paper studies multi-armed bandits, the standard model for repeatedly choosing among options with unknown rewards, for the case where A out of K arms are all tied for optimal. The authors sharpen earlier sub-sampling algorithms, tightening the proven regret bound from order sqrt(KT/A) to order (K-A)/sqrt(KA) times sqrt(T), where T is the number of rounds played. They then prove a matching lower bound, showing the new rate is close to the best any algorithm can achieve across every possible value of A. A final result shows an algorithm must know roughly how many arms are tied for best to actually hit that rate; algorithms tuned for the wrong count pay a real regret penalty.
That last point matters beyond the math: most bandit-based systems, from ad-variant testing to adaptive recommendations, are built around the assumption that exactly one option is best, which understates how much efficiency is available when several options are genuinely tied. But the result also rules out a free lunch, because a system cannot just hedge for "maybe there are ties" and expect the improved rate automatically; it has to estimate the number of optimal arms first.
It is a tight piece of theory, not a shipped algorithm or a test against real traffic, so the real-world payoff rests on someone building an estimator for that arm count outside of a proof.