Second-order Quantile Methods for Experts and Combinatorial Games

Understand

We aim to design strategies for sequential decision making that adjust to the difficulty of the learning problem.

• We study this question both in the setting of prediction with expert advice, and for more general combinatorial decision tasks.
• We are not satisfied with just guaranteeing minimax regret rates, but we want our algorithms to perform significantly better on easy data.
• Two popular ways to formalize such adaptivity are second-order regret bounds and quantile bounds.