12 papers
m-Set Adversarial Bandits with Winner Feedback
Nicolò Cesa-Bianchi, Matteo Papini
We show upper and lower bounds on the regret of -set adversarial bandits for different utilities (winner reward or sum of rewards) and feedback models (winner index, winner rewa…
Gradient-Variation Regret Bounds for Unconstrained Online Learning
Yuheng Zhao, Andrew Jacobsen, Nicolò Cesa-Bianchi +1
We develop parameter-free algorithms for unconstrained online learning with regret guarantees that scale with the gradient variation $V_T(u) = \sum_{t=2}^T \|\nabla f_t(u)-\nabla f…
Surviving Eratosthenes sieve I: quadratic density and Legendre's conjecture
Fred B. Holt
We have been studying Eratosthenes sieve as a discrete dynamic system, obtaining exact models for the relative populations for small gaps (currently gaps ) in the cycle o…
A Perturbation Approach to Unconstrained Linear Bandits
Andrew Jacobsen, Dorian Baudry, Shinji Ito +1
We revisit the standard perturbation-based approach of Abernethy et al. (2008) in the context of unconstrained Bandit Linear Optimization (uBLO). We show the surprising result that…
Lookahead identification in adversarial bandits: accuracy and memory bounds
Nataly Brukhim, Nicolò Cesa-Bianchi, Carlo Ciliberto
We study an identification problem in multi-armed bandits. In each round a learner selects one of arms and observes its reward, with the goal of eventually identifying an arm t…
Online Linear Regression with Paid Stochastic Features
Nadav Merlis, Kyoungseok Jang, Nicolò Cesa-Bianchi
We study an online linear regression setting in which the observed feature vectors are corrupted by noise and the learner can pay to reduce the noise level. In practice, this may h…
Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring
Federico Di Gennaro, Khaled Eldowa, Nicolò Cesa-Bianchi
In contrast to the classic formulation of partial monitoring, linear partial monitoring can model infinite outcome spaces, while imposing a linear structure on both the losses and…
The Invisible Handshake: Persistent Overpricing by Adaptive Market Agents
Luigi Foscari, Emanuele Guidotti, Nicolò Cesa-Bianchi +2
We study overpricing in a repeated game between two representative agents: a market maker, who controls market liquidity, and a market taker, who chooses trade quantities. Market p…
Improved Regret Bounds for Bandits with Expert Advice
Nicolò Cesa-Bianchi, Khaled Eldowa, Emmanuel Esposito +1
In this research note, we revisit the bandits with expert advice problem. Under a restricted feedback model, we prove a lower bound of order for the worst-cas…
Sparsity-Agnostic Linear Bandits with Adaptive Adversaries
Tianyuan Jin, Kyoungseok Jang, Nicolò Cesa-Bianchi
We study stochastic linear bandits where, in each round, the learner receives a set of actions (i.e., feature vectors), from which it chooses an element and obtains a stochastic re…
Information Capacity Regret Bounds for Bandits with Mediator Feedback
Khaled Eldowa, Nicolò Cesa-Bianchi, Alberto Maria Metelli +1
This work addresses the mediator feedback problem, a bandit game where the decision set consists of a number of policies, each associated with a probability distribution over a com…
Information-Theoretic Regret Bounds for Bandits with Fixed Expert Advice
Khaled Eldowa, Nicolò Cesa-Bianchi, Alberto Maria Metelli +1
We investigate the problem of bandits with expert advice when the experts are fixed and known distributions over the actions. Improving on previous analyses, we show that the regre…