publication . Preprint . 2015

Online learning in repeated auctions

Perchet, Vianney; Rigollet, Philippe; Weed, John;
Open Access English
  • Published: 18 Nov 2015
  • Country: France
Abstract
Motivated by online advertising auctions, we consider repeated Vickrey auctions where goods of unknown value are sold sequentially and bidders only learn (potentially noisy) information about a good's value once it is purchased. We adopt an online learning approach with bandit feedback to model this problem and derive bidding strategies for two models: stochastic and adversarial. In the stochastic model, the observed values of the goods are random variables centered around the true value of the good. In this case, logarithmic regret is achievable when competing against well behaved adversaries. In the adversarial model, the goods need not be identical and we sim...
Subjects
arXiv: Computer Science::Computer Science and Game Theory
ACM Computing Classification System: TheoryofComputation_GENERAL
free text keywords: Computer Science - Computer Science and Game Theory, Computer Science - Learning, Statistics - Machine Learning, Primary 62L05, secondary 62C20, [INFO.INFO-GT]Computer Science [cs]/Computer Science and Game Theory [cs.GT]
Funded by
NSF| Statistical and Computational Tradeoffs in High Dimensional Learning
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1317308
  • Funding stream: Directorate for Mathematical & Physical Sciences | Division of Mathematical Sciences
,
NSF| CAREER: Large Scale Stochastic Optimization and Statistics
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1053987
  • Funding stream: Directorate for Mathematical & Physical Sciences | Division of Mathematical Sciences
,
NSF| Graduate Research Fellowship Program
Project
  • Funder: National Science Foundation (NSF)
  • Project Code: 1122374
  • Funding stream: Directorate for Education & Human Resources | Division of Graduate Education
42 references, page 1 of 3

[ACBF02] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer, Finite-time analysis of the multiarmed bandit problem, Mach. Learn. 47 (2002), no. 2-3, 235{256.

[ACBFS03] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E. Schapire, The nonstochastic multiarmed bandit problem, SIAM J. Comput. 32 (2002/03), no. 1, 48{77 (electronic). MR1954855 (2003k:91031) [OpenAIRE]

[ACD+15] Kareem Amin, Rachel Cummings, Lili Dworkin, Michael Kearns, and Aaron Roth, Online learning and pro t maximization from revealed preferences, Proceedings of the Twenty-Ninth AAAI Conference on Arti cial Intelligence, January 25-30, 2015, Austin, Texas, USA., 2015, pp. 770{776.

[ARS14] Kareem Amin, Afshin Rostamizadeh, and Umar Syed, Repeated contextual auctions with strategic buyers, Advances in Neural Information Processing Systems 27 (Z. Ghahramani, M. Welling, C. Cortes, N.D. Lawrence, and K.Q. Weinberger, eds.), Curran Associates, Inc., 2014, pp. 622{630.

[BCB12] Sebastien Bubeck and Nicolo Cesa-Bianchi, Regret analysis of stochastic and nonstochastic multi-armed bandit problems, Foundations and Trends in Machine Learning 5 (2012), no. 1, 1{122.

[BKS10] Moshe Babaio , Robert D. Kleinberg, and Aleksandrs Slivkins, Truthful mechanisms with implicit payment computation, Proceedings of the 11th ACM Conference on Electronic Commerce (New York, NY, USA), EC '10, ACM, 2010, pp. 43{52.

[BFP+14] Gabor Bartok, Dean P. Foster, David Pal, Alexander Rakhlin, and Csaba Szepesvari, Partial monitoring|classi cation, regret bounds, and algorithms, Math. Oper. Res. 39 (2014), no. 4, 967{997. MR3279754

[BMM15] Avrim Blum, Yishay Mansour, and Jamie Morgenstern, Learning valuation distributions from partial observation, Proceedings of the Twenty-Ninth AAAI Conference on Arti cial Intelligence, January 25-30, 2015, Austin, Texas, USA., 2015, pp. 798{804.

[BPR13] Sebastien Bubeck, Vianney Perchet, and Philippe Rigollet, Bounded regret in stochastic multi-armed bandits, COLT 2013 - The 26th Conference on Learning Theory, Princeton, NJ, June 12-14, 2013 (Shai Shalev-Shwartz and Ingo Steinwart, eds.), JMLR W&CP, vol. 30, 2013, pp. 122{134.

[BSS09] Moshe Babaio , Yogeshwer Sharma, and Aleksandrs Slivkins, Characterizing truthful multi-armed bandit mechanisms: Extended abstract, Proceedings of the 10th ACM Conference on Electronic Commerce (New York, NY, USA), EC '09, ACM, 2009, pp. 79{88.

[CBGM13] Nicolo Cesa-Bianchi, Claudio Gentile, and Yishay Mansour, Regret minimization for reserve prices in second-price auctions, Proceedings of the Twenty-Fourth Annual ACMSIAM Symposium on Discrete Algorithms, SODA '13, SIAM, 2013, pp. 1190{1204.

[CBL06] Nicolo Cesa-Bianchi and Gabor Lugosi, Prediction, learning, and games, Cambridge University Press, Cambridge, 2006. MR2409394 (2009g:91006)

[CHN14] Shuchi Chawla, Jason Hartline, and Denis Nekipelov, Mechanism design for data science, Proceedings of the Fifteenth ACM Conference on Economics and Computation (New York, NY, USA), EC '14, ACM, 2014, pp. 711{712.

[CM88] Jacques Cremer and Richard P. McLean, Full extraction of the surplus in bayesian and dominant strategy auctions, Econometrica 56 (1988), no. 6, pp. 1247{1257 (English). [OpenAIRE]

[CR14] Richard Cole and Tim Roughgarden, The sample complexity of revenue maximization, Proceedings of the 46th Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC '14, ACM, 2014, pp. 243{252.

42 references, page 1 of 3
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Preprint . 2015

Online learning in repeated auctions

Perchet, Vianney; Rigollet, Philippe; Weed, John;