  In display advertising, a small group of sellers and bidders face each other
in up to 10 12 auctions a day. In this context, revenue maximisation via
monopoly price learning is a high-value problem for sellers. By nature, these
auctions are online and produce a very high frequency stream of data. This
results in a computational strain that requires algorithms be real-time.
Unfortunately, existing methods inherited from the batch setting suffer
O($\sqrt t$) time/memory complexity at each update, prohibiting their use. In
this paper, we provide the first algorithm for online learning of monopoly
prices in online auctions whose update is constant in time and memory.
