91黑料网

TITLE / TITRE

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

听

ABSTRACT /听R脡SUM脡听

Online learning is a framework for analysing sequential decision-making problems in adversarial environments. Many important problems in statistics and computer science can be reduced to variants of online learning, including finding equilibrium strategies for multiplayer games, stochastic and online optimization, adaptive density estimation, sequential testing, adaptive experimental design, and online change-point detection. Design of algorithms for online learning can, thus, be used to study the information theoretic and computational limits of sequential decision making under uncertainty in a variety of contexts with numerous applications.

An important class of online learning algorithms are "follow-the-perturbed leader" (FTPL) methods, which make decisions by randomly simulating the future of the online learning game and then playing the best response to the simulation. These methods are typically among those with the most efficient implementation. However, the analysis of FTPL performance in previous work has largely been limited to cases where some strong "between-action" independence assumptions are imposed on the simulation of the future. This limits the broad applicability of these methods when such independence is not appropriate.

We present a framework for analyzing Gaussian 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.

PLACE /LIEU听
Hybride - CRM, Salle / Room 5340, Pavillon Andr茅 Aisenstadt

听