Combinatorial Bandits for Incentivizing Agents with Dynamic Preferences

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.

arXiv commentPublished as a conference paper in Conference on Uncertainty in Artificial Intelligence (UAI) 2018

References in corpus (6)

• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Bandits with Knapsacks
• Combinatorial Multi-Armed Bandit and Its Extension to Probabilistically Triggered Arms
• Matroid Bandits: Fast Combinatorial Optimization with Learning
• Regret Bounds for Reinforcement Learning with Policy Advice
• A Multi-Armed Bandit Approach for Online Expert Selection in Markov Decision Processes