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 rec- ommendations to improve user engagement is gaining prominence as digital platform providers continually emerge. We propose a multi-armed bandit framework for match- ing incentives to users, whose preferences are unknown a priori and evolving dynamically in time, in a resource constrained environ- ment. We design an algorithm that com- bines ideas from three distinct domains: (i) a greedy matching paradigm, (ii) the upper confidence bound algorithm (UCB) for ban- dits, and (iii) mixing times from the theory of Markov chains. For this algorithm, we provide theoretical bounds on the regret and demon- strate 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 rec- ommendations to improve user engagement is gaining prominence as digital platform providers continually emerge. We propose a multi-armed bandit framework for match- ing incentives to users, whose preferences are unknown a priori and evolving dynamically in time, in a resource constrained environ- ment. We design an algorithm that com- bines ideas from three distinct domains: (i) a greedy matching paradigm, (ii) the upper confidence bound algorithm (UCB) for ban- dits, and (iii) mixing times from the theory of Markov chains. For this algorithm, we provide theoretical bounds on the regret and demon- strate 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 rec- ommendations to improve user engagement is gaining prominence as digital platform providers continually emerge. We propose a multi-armed bandit framework for match- ing incentives to users, whose preferences are unknown a priori and evolving dynamically in time, in a resource constrained environ- ment. We design an algorithm that com- bines ideas from three distinct domains: (i) a greedy matching paradigm, (ii) the upper confidence bound algorithm (UCB) for ban- dits, and (iii) mixing times from the theory of Markov chains. For this algorithm, we provide theoretical bounds on the regret and demon- strate 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