# ktexttt-experts -- Online Policies and Fundamental Limits

arXiv: https://arxiv.org/abs/2110.07881 · HTML: https://mlsanity.com/paper/2110.07881/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 51 references that are in the map.
- First posted on arXiv 15 Oct 2021.

## Builds on (most cited first, 7 of 7)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Introduction to Online Convex Optimization](https://mlsanity.com/paper/1909.05207/) (2019)
- [Second-order Quantile Methods for Experts and Combinatorial Games](https://mlsanity.com/paper/1502.08009/) (2015)
- [Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications](https://mlsanity.com/paper/1408.2051/) (2014)
- [Tight Lower Bound on the Probability of a Binomial Exceeding its Expectation](https://mlsanity.com/paper/1306.1433/) (2013)
- [A Tutorial on Online Supervised Learning with Applications to Node Classification in Social Networks](https://mlsanity.com/paper/1608.09014/) (2016)
- [On solving the densest k-subgraph problem on large graphs](https://mlsanity.com/paper/1901.06344/) (2019)

## Built on by (most cited first, 8 of 8)

- [Optimistic No-regret Algorithms for Discrete Caching](https://mlsanity.com/paper/2208.06414/) (2022)
- [No-regret Algorithms for Fair Resource Allocation](https://mlsanity.com/paper/2303.06396/) (2023)
- [Online Learning and Bandits with Queried Hints](https://mlsanity.com/paper/2211.02703/) (2022)
- [Consistent algorithms for multi-label classification with macro-at-k metrics](https://mlsanity.com/paper/2401.16594/) (2024)
- [Universal Caching](https://mlsanity.com/paper/2205.04860/) (2022)
- [Online Subset Selection using α-Core with no Augmented Regret](https://mlsanity.com/paper/2209.14222/) (2022)
- [No-Regret Online Prediction with Strategic Experts](https://mlsanity.com/paper/2305.15331/) (2023)
- [Follow The Approximate Sparse Leader for No-Regret Online Sparse Linear Approximation](https://mlsanity.com/paper/2501.00799/) (2025)

## Abstract (arXiv)

We introduce the textttk-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≤ k≤ 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 textttSAGE (Sampled Hedge) - a framework for designing efficient online learning policies by leveraging statistical sampling techniques. For a wide class of reward functions, we show that textttSAGE 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 textttk-experts problem and carrying out experiments with standard datasets.