Abstract
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.
Introduction
In the standard Multi-Armed Bandit (MAB) problem, an agent seeks to maximize cumulative rewards by balancing exploration and exploitation. However, in many modern platforms (e.g., recommendation systems, review sites), the entity making the decision (the player) is distinct from the entity interested in learning (the principal). Players are typically myopic, choosing only the option with the highest current estimated reward. To facilitate exploration of suboptimal arms, the principal must offer incentives, such as discounts or coupons.
A critical challenge in this setting is Reward Drift. Incentives often bias user feedback; for instance, a discounted meal might receive a higher rating than it would at full price. This paper investigates whether standard MAB algorithms can remain effective when learning from such biased feedback.
Methodology
The authors model the interaction as a principal paying a player compensation $x_t$ to pull a specific arm. This compensation induces a drift $b_t = f_t(x_t)$ in the observed reward. The study focuses on three primary algorithmic adaptations:
- Incentivized UCB: A deterministic approach using upper confidence bounds derived from biased rewards.
- Incentivized $\varepsilon$-Greedy: A randomized approach that explores with a decaying probability $\varepsilon_t$.
- Incentivized Thompson Sampling (TS): A Bayesian approach sampling from Gaussian posteriors.
The theoretical analysis assumes the drift function is non-decreasing and Lipschitz continuous, ensuring that the bias remains manageable relative to the incentive provided.
Key Results and Analysis
The core finding is that all three algorithms maintain optimal performance, achieving $O(\log T)$ total regret and $O(\log T)$ total compensation. This indicates that the cost of incentivizing exploration does not grow prohibitively over time.
Comparative Performance
Numerical simulations with $K=9$ arms and Gaussian noise confirm these theoretical bounds. As shown in the figure below, Thompson Sampling significantly outperforms both UCB and $\varepsilon$-Greedy in minimizing both regret and the total cost of incentives.
Sensitivity to Reward Drift
The impact of the drift coefficient $l$ (where $b_t = l \cdot x_t$) varies across algorithms. UCB is particularly sensitive, with regret scaling quadratically with $(l+1)$, while randomized algorithms like TS and $\varepsilon$-Greedy exhibit more linear sensitivity.
Despite the biased feedback, the algorithms remain remarkably accurate. The relative error in estimating the true mean of the optimal arm typically stays below 2%, even under significant drift. This "self-correcting" behavior occurs because as the principal identifies the best arm, the required compensation (and thus the drift) naturally decays.
Conclusion
This research demonstrates that incentivized exploration is robust to reward drift. While all tested algorithms achieve logarithmic efficiency, Thompson Sampling emerges as the most effective and least sensitive to feedback bias. Future research may explore non-monotonic drift functions or scenarios where strategic players intentionally manipulate feedback to maximize future incentives.
Summary updated