Learning to Price Against a Moving Target

Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, Pratik Worah
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:6223-6232, 2021.

Abstract

In the Learning to Price setting, a seller posts prices over time with the goal of maximizing revenue while learning the buyer’s valuation. This problem is very well understood when values are stationary (fixed or iid). Here we study the problem where the buyer’s value is a moving target, i.e., they change over time either by a stochastic process or adversarially with bounded variation. In either case, we provide matching upper and lower bounds on the optimal revenue loss. Since the target is moving, any information learned soon becomes out-dated, which forces the algorithms to keep switching between exploring and exploiting phases.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-leme21a, title = {Learning to Price Against a Moving Target}, author = {Leme, Renato Paes and Sivan, Balasubramanian and Teng, Yifeng and Worah, Pratik}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {6223--6232}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/leme21a/leme21a.pdf}, url = {https://proceedings.mlr.press/v139/leme21a.html}, abstract = {In the Learning to Price setting, a seller posts prices over time with the goal of maximizing revenue while learning the buyer’s valuation. This problem is very well understood when values are stationary (fixed or iid). Here we study the problem where the buyer’s value is a moving target, i.e., they change over time either by a stochastic process or adversarially with bounded variation. In either case, we provide matching upper and lower bounds on the optimal revenue loss. Since the target is moving, any information learned soon becomes out-dated, which forces the algorithms to keep switching between exploring and exploiting phases.} }
Endnote
%0 Conference Paper %T Learning to Price Against a Moving Target %A Renato Paes Leme %A Balasubramanian Sivan %A Yifeng Teng %A Pratik Worah %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-leme21a %I PMLR %P 6223--6232 %U https://proceedings.mlr.press/v139/leme21a.html %V 139 %X In the Learning to Price setting, a seller posts prices over time with the goal of maximizing revenue while learning the buyer’s valuation. This problem is very well understood when values are stationary (fixed or iid). Here we study the problem where the buyer’s value is a moving target, i.e., they change over time either by a stochastic process or adversarially with bounded variation. In either case, we provide matching upper and lower bounds on the optimal revenue loss. Since the target is moving, any information learned soon becomes out-dated, which forces the algorithms to keep switching between exploring and exploiting phases.
APA
Leme, R.P., Sivan, B., Teng, Y. & Worah, P.. (2021). Learning to Price Against a Moving Target. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:6223-6232 Available from https://proceedings.mlr.press/v139/leme21a.html.

Related Material