Regret Minimization

This chapter studies online learning through the regret minimization framework, focusing on the multi-armed bandit problem. Fundamental lower bounds are established. Improved algorithms are developed including upper confidence bound, achieving optimal regret through optimism in the face of uncertainty. Extensions to MDP settings are discussed. The best-arm identification problem addresses pure exploration with sequential halving, achieving sample-optimal PAC guarantees.