  We introduce the $\texttt{$k$-experts}$ problem - a generalization of the
classic Prediction with Expert's Advice framework. Unlike the classic version,
where the learner selects exactly one expert from a pool of $N$ experts at each
round, in this problem, the learner can select a subset of $k$ experts at each
round $(1\leq k\leq N)$. The reward obtained by the learner at each round is
assumed to be a function of the $k$ selected experts. The primary objective is
to design an online learning policy with a small regret. In this pursuit, we
propose $\texttt{SAGE}$ ($\textbf{Sa}$mpled Hed$\textbf{ge}$) - a framework for
designing efficient online learning policies by leveraging statistical sampling
techniques. For a wide class of reward functions, we show that $\texttt{SAGE}$
either achieves the first sublinear regret guarantee or improves upon the
existing ones. Furthermore, going beyond the notion of regret, we fully
characterize the mistake bounds achievable by online learning policies for
stable loss functions. We conclude the paper by establishing a tight regret
lower bound for a variant of the $\texttt{$k$-experts}$ problem and carrying
out experiments with standard datasets.
