Please note: This seminar will take place in MC 2034 and online.
Jeffrey Negrea, Assistant Professor
Department of Statistics and Actuarial Science
Follow-the-Perturbed-Leader (FTPL) algorithms offer a computationally efficient approach to online learning. An FTPL-based learner plays the best response to a randomly perturbed history. However, existing analyses of FTPL rely on strong “between-action” independence assumptions for the perturbation distribution, limiting their applicability when independence is not appropriate.
We introduce a framework for analyzing Gaussian FTPL in the context of full-information online learning when the perturbation distribution exhibits between-action dependence. We apply our framework to two regimes: (i) infinite action spaces under bounded Lipschitz rewards, using Gaussian process perturbations, and (ii) linear polyhedral games. We demonstrate how to tightly account for dependence between actions in FTPL regret bounds, and we present an ansatz for the selection of the perturbation distribution.
To attend this seminar in person, please go to MC 2034. You can also attend virtually on Zoom.