Date/Time
Date(s) - 04/12/2025
1:30 pm - 2:30 pm

Speaker: Jeffrey Negrea (University of Waterloo)

Location: Hamilton Hall, Room 102

Title: Follow-the-Perturbed-Leader with Between-Action Dependence

Abstract: We present a framework for analyzing Gaussian follow-the-perturbed-leader (FTPL) algorithms for full-information online learning problems when the perturbation distribution exhibits between-action dependence. Applications include FTPL algorithms for online learning for i) infinite action spaces when the adversary plays bounded Lipschitz reward functions, where the perturbations are random functions sampled from a Gaussian process; and ii) linear polyhedral games, where the perturbation is a random linear function. We demonstrate how to tightly account for dependence between actions in the FTPL analysis and present an ansatz for the selection of the perturbation distribution based on a Bayesian perspective of FTPL as a variant of Thompson sampling.