Incentivized Exploration for Multi-Armed Bandits under Reward Drift
This addresses the problem of efficient exploration in bandit settings with incentives and feedback drift, but it is incremental as it extends known algorithms to a drifted reward model.
The paper tackles incentivized exploration in multi-armed bandits with reward drift, where players are compensated for exploring non-greedy arms and may give biased feedback, showing that UCB, ε-Greedy, and Thompson Sampling algorithms achieve O(log T) regret and compensation under these conditions.
We study incentivized exploration for the multi-armed bandit (MAB) problem where the players receive compensation for exploring arms other than the greedy choice and may provide biased feedback on reward. We seek to understand the impact of this drifted reward feedback by analyzing the performance of three instantiations of the incentivized MAB algorithm: UCB, $\varepsilon$-Greedy, and Thompson Sampling. Our results show that they all achieve $\mathcal{O}(\log T)$ regret and compensation under the drifted reward, and are therefore effective in incentivizing exploration. Numerical examples are provided to complement the theoretical analysis.