Timezone: »

 
Poster
Real-Time Bidding with Side Information
arthur flajolet · Patrick Jaillet

Wed Dec 06 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #62
in Posters Wed »
We consider the problem of repeated bidding in online advertising auctions when some side information (e.g. browser cookies) is available ahead of submitting a bid in the form of a $d$-dimensional vector. The goal for the advertiser is to maximize the total utility (e.g. the total number of clicks) derived from displaying ads given that a limited budget $B$ is allocated for a given time horizon $T$. Optimizing the bids is modeled as a contextual Multi-Armed Bandit (MAB) problem with a knapsack constraint and a continuum of arms. We develop UCB-type algorithms that combine two streams of literature: the confidence-set approach to linear contextual MABs and the probabilistic bisection search method for stochastic root-finding. Under mild assumptions on the underlying unknown distribution, we establish distribution-independent regret bounds of order $\tilde{O}(d \cdot \sqrt{T})$ when either $B = \infty$ or when $B$ scales linearly with $T$.
Keywords: Bandit Algorithms · Online Learning · Web Applications and Internet Data
[ Paper] 

Author Information

arthur flajolet (MIT)
Patrick Jaillet (MIT)

More from the Same Authors