Skip to Main content Skip to Navigation
Conference papers

A bandit learning algorithm and applications to auction design

Abstract : We consider online bandit learning in which at every time step, an algorithm has to make a decision and then observe only its reward. The goal is to design efficient (polynomial-time) algorithms that achieve a total reward approximately close to that of the best fixed decision in hindsight. In this paper, we introduce a new notion of (?, µ)-concave functions and present a bandit learning algorithm that achieves a performance guarantee which is characterized as a function of the concavity parameters ? and µ. The algorithm is based on the mirror descent algorithm in which the update directions follow the gradient of the multilinear extensions of the reward functions. The regret bound induced by our algorithm is Oe(vT) which is nearly optimal. We apply our algorithm to auction design, specifically to welfare maximization, revenue maximization, and no-envy learning in auctions. In welfare maximization, we show that a version of fictitious play in smooth auctions guarantees a competitive regret bound which is determined by the smooth parameters. In revenue maximization, we consider the simultaneous second-price auctions with reserve prices in multi-parameter environments. We give a bandit algorithm which achieves the total revenue at least 1/2 times that of the best fixed reserve prices in hindsight. In no-envy learning, we study the bandit item selection problem where the player valuation is submodular and provide an efficient 1/2-approximation no-envy algorithm.
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03277640
Contributor : Frédéric Davesne <>
Submitted on : Sunday, July 4, 2021 - 3:51:09 PM
Last modification on : Tuesday, July 6, 2021 - 3:41:18 AM

Identifiers

  • HAL Id : hal-03277640, version 1

Citation

Kim Thang Nguyen. A bandit learning algorithm and applications to auction design. 34th Conference on Neural Information Processing Systems (NeurIPS 2020), Dec 2020, Virtual Conference, Canada. ⟨hal-03277640⟩

Share

Metrics

Record views

58