给一组广告分流时，如果好几版广告效果并列第一，系统理应更容易选对。多臂老虎机（multi-armed bandit）研究的正是这种边试边选的问题；“遗憾”（regret）则衡量系统与一开始就知道最佳选项相比，累计少赚了多少。Ji 等人重新分析了“先随机抽取部分选项，再运行标准算法”的已有方案，给出覆盖各种最优选项数量的更紧遗憾上界，并证明其与下界只差对数因子。收益在最优选项占比很高时尤其明显：旧分析低估了“随手就能抽中好选项”带来的便利。
但论文也给出一个不太乐观的结论：算法若不知道有多少个选项并列最优，就不能总自动拿到对应的近最优表现。为证明这一点，作者没有沿用比较两组互不重叠最佳选项的常见办法——最佳选项很多时，两组必然重叠——而是构造一批对称问题，再统一与“所有选项回报相同”的参照问题比较。结果说明，未知的最优选项数量本身就会带来额外学习代价。需要注意，这项改进针对期望遗憾；论文同时证明，同样的保证无法直接提升为高概率保证。