---
abstract: 'We consider revenue maximization in online auction/pricing problems. A seller sells an identical item in each period to a new buyer, or a new set of buyers. For the online pricing problem, we show regret bounds that scale with the *best fixed price*, rather than the range of the values. We also show regret bounds that are *almost scale free*, and match the offline sample complexity, when comparing to a benchmark that requires a *lower bound on the market share*. These results are obtained by generalizing the classical learning from experts and multi-armed bandit problems to their *multi-scale* versions. In this version, the reward of each action is in a *different range*, and the regret with respect to a given action scales with its *own range*, rather than the maximum range.'
author:
- |
    Sébastien Bubeck sebubeck@microsoft.com\
    Microsoft Research,\
    1 Microsoft Way,\
    Redmond, WA 98052, USA. Nikhil Devanur nikdev@microsoft.com\
    Microsoft Research,\
    1 Microsoft Way,\
    Redmond, WA 98052, USA. Zhiyi Huang zhiyi@cs.hku.hk\
    Department of Computer Science,\
    The University of Hong Kong,\
    Pokfulam, Hong Kong. Rad Niazadeh rad@cs.stanford.edu\
    Department of Computer Science,\
    Stanford University,\
    Stanford, CA 94305, USA.
bibliography:
- 'bibliography.bib'
title: 'Multi-scale Online Learning and its Applications to Online Auctions'
---

online learning, multi-scale learning, auction theory, bandit information, sample complexity
