7 papers
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…
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…
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…
Parameter-Free Dynamic Regret for Unconstrained Linear Bandits
Alberto Rumi, Andrew Jacobsen, Nicolò Cesa-Bianchi +1
We study dynamic regret minimization in unconstrained adversarial linear bandit problems. In this setting, a learner must minimize the cumulative loss relative to an arbitrary sequ…
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…
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…