Combinatorial Bandits for Incentivizing Agents with Dynamic Preferences

Tanner Fiez, Shreyas Sekar, Liyuan Zheng, Lillian Ratliff
Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, PMLR R16:692-702, 2018.

Abstract

The design of personalized incentives or recommendations to improve user engagement is gaining prominence as digital platform providers continually emerge. We propose a multi-armed bandit framework for matching incentives to users, whose preferences are unknown a priori and evolving dynamically in time, in a resource constrained environment. We design an algorithm that combines ideas from three distinct domains: (i) a greedy matching paradigm, (ii) the upper confidence bound algorithm (UCB) for bandits, and (iii) mixing times from the theory of Markov chains. For this algorithm, we provide theoretical bounds on the regret and demonstrate its performance via both synthetic and realistic (matching supply and demand in a bike-sharing platform) examples.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR16-fiez18a, title = {Combinatorial Bandits for Incentivizing Agents with Dynamic Preferences}, author = {Fiez, Tanner and Sekar, Shreyas and Zheng, Liyuan and Ratliff, Lillian}, booktitle = {Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence}, pages = {692--702}, year = {2018}, editor = {Globerson, Amir and Silva, Ricardo}, volume = {R16}, series = {Proceedings of Machine Learning Research}, month = {06--10 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r16/main/assets/fiez18a/fiez18a.pdf}, url = {https://proceedings.mlr.press/r16/fiez18a.html}, abstract = {The design of personalized incentives or recommendations to improve user engagement is gaining prominence as digital platform providers continually emerge. We propose a multi-armed bandit framework for matching incentives to users, whose preferences are unknown a priori and evolving dynamically in time, in a resource constrained environment. We design an algorithm that combines ideas from three distinct domains: (i) a greedy matching paradigm, (ii) the upper confidence bound algorithm (UCB) for bandits, and (iii) mixing times from the theory of Markov chains. For this algorithm, we provide theoretical bounds on the regret and demonstrate its performance via both synthetic and realistic (matching supply and demand in a bike-sharing platform) examples.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Combinatorial Bandits for Incentivizing Agents with Dynamic Preferences %A Tanner Fiez %A Shreyas Sekar %A Liyuan Zheng %A Lillian Ratliff %B Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2018 %E Amir Globerson %E Ricardo Silva %F pmlr-vR16-fiez18a %I PMLR %P 692--702 %U https://proceedings.mlr.press/r16/fiez18a.html %V R16 %X The design of personalized incentives or recommendations to improve user engagement is gaining prominence as digital platform providers continually emerge. We propose a multi-armed bandit framework for matching incentives to users, whose preferences are unknown a priori and evolving dynamically in time, in a resource constrained environment. We design an algorithm that combines ideas from three distinct domains: (i) a greedy matching paradigm, (ii) the upper confidence bound algorithm (UCB) for bandits, and (iii) mixing times from the theory of Markov chains. For this algorithm, we provide theoretical bounds on the regret and demonstrate its performance via both synthetic and realistic (matching supply and demand in a bike-sharing platform) examples. %Z Reissued by PMLR on 04 October 2026.
APA
Fiez, T., Sekar, S., Zheng, L. & Ratliff, L.. (2018). Combinatorial Bandits for Incentivizing Agents with Dynamic Preferences. Proceedings of the 34th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R16:692-702 Available from https://proceedings.mlr.press/r16/fiez18a.html. Reissued by PMLR on 04 October 2026.

Related Material