Regret Minimization With a Crowd of Awakening Experts

We study the Awakening Crowd of Experts (ACE) problem, an online learning problem where the set of experts available to the learner grows at each round. ACE is a special case of the well-known sleeping experts problem (Kleinberg et al., 2010), where the number of experts is huge $(K=T)$. Existing results on sleeping experts preclude any learner from achieving a sublinear regret when the number of available experts is linear in $T$. Inspired by real-world applications, such as Q\&A platforms and social proof marketing, we thus focus on the awakening version of the sleeping experts problem, where a new expert arrives at every round and never leaves. We show that in the stochastic version of ACE, it is possible to obtain regret $\tilde{\mathcal{O}}(T^{2/3})$ using an unusual pessimism in the face of the uncertainty principle. Moreover, we characterize the dependence of the regret on the stability of an optimal strategy. For both results, we present matching lower bounds. Surprisingly, the adversarial version of ACE is sensibly harder. In particular, we provide a lower bound precluding sublinear $\alpha$-regret when the competitive ratio is constant. We provide an algorithm to face this crucial trade-off between competitive ratio and regret, and bound its $\alpha$-regret, almost matching the aforementioned lower bound. As a corollary, we get a $\tilde{\mathcal{O}}(\log(\log(T))$ competitive ratio when an optimal strategy enjoys a reward linear in $T$.

Many online systems need to make repeated decisions by choosing whose advice or content to trust. For example, a platform may have to decide which user review, comment, or recommendation to highlight. A key difficulty is that new users or sources of advice keep appearing over time, while older ones remain available. The system must therefore balance two goals: relying on sources that have already proved useful, and giving newer sources enough attention to discover whether they are better. This paper studies this problem through a model where one new “expert” becomes available at each step and then stays available forever. Standard methods for learning from expert advice struggle in this setting because the number of experts grows very large. We show that the special structure of the problem makes learning possible in important cases. When experts behave consistently over time, we design a cautious learning method that avoids switching too quickly to new, uncertain experts and achieves strong performance guarantees. When expert quality can change in a more unpredictable way, we show that the problem is fundamentally harder, and we design an algorithm that carefully balances learning from recent experts with exploiting reliable older ones.