Minimax Policies for Combinatorial Prediction Games

By Jean-Yves Audibert, Sébastien Bubeck, Gábor Lugosi. 2011

87 citations recorded by the source corpus.

We address the online linear optimization problem when the actions of the forecaster are represented by binary vectors. Our goal is to understand the magnitude of the minimax regret for the worst possible set of actions. We study the problem under three different assumptions for the feedback: full information, and the partial information models of the so-called "semi-bandit", and "bandit" problems. We consider both L -, and L2-type of restrictions for the losses assigned by the adversary. We formulate a general strategy using Bregman projections on top of a potential-based gradient descent, which generalizes the ones studied in the series of papers Gyorgy et al. (2007), Dani et al. (2008), Abernethy et al. (2008), Cesa-Bianchi and Lugosi (2009), Helmbold and Warmuth (2009), Koolen et al. (2010), Uchiya et al. (2010), Kale et al. (2010) and Audibert and Bubeck (2010). We provide simple proofs that recover most of the previous results. We propose new upper bounds for the semi-bandit game. Moreover we derive lower bounds for all three feedback assumptions. With the only exception of the bandit game, the upper and lower bounds are tight, up to a constant factor. Finally, we answer a question asked by Koolen et al. (2010) by showing that the exponentially weighted average forecaster is suboptimal against L adversaries.

Subfields: Artificial Intelligence, Management Science and Operations Research, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Game & Decision Theory

Citations in the corpus

On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization (2012, background): “Keywords: Stochastic Convex Optimization; Derivative-Free Optimization; Bandit Convex Optimization; Regret”
Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “The case of deterministic covariates (fixed design), finitely many arms, and a linear stochastic dependence between covariates and rewards has been studied in Auer [2002], Chu et al.”
Fundamental Limits of Online and Distributed Algorithms for Statistical Learning and Estimation (2013, background): “In partial monitoring ([20]), we get a Ω( d/k ) lower bound where k is the logarithm of the feedback matrix width.”
Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms (2014, background): “In the linear combinatorial bandit setting, i.e., semi-bandit with L ∞ assumption in Audibert et al. (2011), our regret is O ( m 3 n log n ), which is a factor √ m oﬀ the optimal bound in the adversarial setting.”
Towards Minimax Policies for Online Linear Optimization with Bandit Feedback (2012, methodology): “More precisely, following Audibert et al. (2011), (2) can be written (up to a numerical constant) as”
Bandit Theory meets Compressed Sensing for high dimensional Stochastic Linear Bandit (2012, methodology): “One idea would be to use techniques developed for adversarial bandits (see (Abernethy et al., 2008; Bartlett et al., 2008; Cesa-Bianchi and Lugosi, 2009; Koolen et al., 2010; Audibert et al., 2011), but also (Flaxman et al.”
Compiling Combinatorial Prediction Games (2018, methodology): “Conceptually, an online combinatorial optimization problem can be cast as a repeated prediction game between a learning algorithm and its environment (Audibert et al., 2011; 2014).”