Multi-armed Bandits with Compensation

Abstract

We propose and study the known-compensation multi-arm bandit (KCMAB) problem, where a system controller offers a set of arms to many short-term players for $T$ steps. In each step, one short-term player arrives to the system. Upon arrival, the player aims to select an arm with the current best average reward and receives a stochastic reward associated with the arm. In order to incentivize players to explore other arms, the controller provides a proper payment compensation to players. The objective of the controller is to maximize the total reward collected by players while minimizing the compensation. We first provide a compensation lower bound $\Theta ({\sum }_i\frac{{\Delta }_i\log T}{K{L}_i})$, where ${\Delta }_i$ and $K{L}_i$ are the expected reward gap and Kullback-Leibler (KL) divergence between distributions of arm $i$ and the best arm, respectively. We then analyze three algorithms to solve the KCMAB problem, and obtain their regrets and compensations. We show that the algorithms all achieve $O(\log T)$ regret and $O(\log T)$ compensation that match the theoretical lower bound. Finally, we present experimental results to demonstrate the performance of the algorithms.

Cited by in corpus (7)

• The Intrinsic Robustness of Stochastic Bandits to Strategic Manipulation
• Incentivizing Exploration in Linear Bandits under Information Gap
• (Almost) Free Incentivized Exploration from Decentralized Learning Agents
• Incentivized Exploration for Multi-Armed Bandits under Reward Drift
• Multi-armed Bandit Algorithm against Strategic Replication
• Incentivized Bandit Learning with Self-Reinforcing User Preferences
• Learning to Price Vehicle Service with Unknown Demand