Incentivized Exploration for Multi-Armed Bandits under Reward Drift

Zhiyuan Liu, Huazheng Wang, Fan Shen, Kai Liu, Lijun Chen

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, ε-Greedy, and Thompson Sampling. Our results show that they all achieve 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 modern recommendation systems, such as Amazon or Yelp, a platform (the principal) often faces a misalignment of interests with its users (the players). While the platform aims to explore new or uncertain products to optimize long-term system utility, users typically act myopically, choosing products with the highest current ratings. To bridge this gap, platforms can offer incentives, such as discounts or coupons, to encourage exploration.

However, behavioral economics suggests that such incentives can introduce "reward drift"—a phenomenon where receiving a discount biases a user's feedback, often leading to inflated ratings. This paper investigates whether this biased feedback undermines the effectiveness of standard bandit algorithms, potentially causing them to converge on suboptimal choices.

Methodology

The study models a principal-player MAB framework where the principal compensates users for the difference between their preferred greedy choice and the platform's exploratory target. The feedback received is modeled as the true reward plus a drift term $b_t = f_t(x)$, where $x$ is the compensation. This drift function is assumed to be non-decreasing and Lipschitz continuous, bounded by a coefficient $l$.

The authors analyze three primary algorithms under this drifted reward model:

  1. Upper Confidence Bound (UCB): A deterministic algorithm that selects arms based on an optimistic estimate of the biased reward.
  2. ε-Greedy: A randomized approach that explores suboptimal arms with a decaying probability $ε_t$.
  3. Thompson Sampling (TS): A Bayesian approach that samples from a posterior distribution of rewards to guide selection.

Empirical Evaluation

The theoretical findings were validated using synthetic simulations of a 9-arm bandit environment with Gaussian reward distributions. A linear drift function ($b_t = l \cdot x_t$) was employed to simulate biased feedback over 20,000 trials.

Cumulative Regret and Compensation over 20,000 trials with a high drift coefficient (l=1.1).

As shown in the simulation results, even under significant reward drift, all three algorithms maintain sub-linear growth in both regret and compensation. However, Thompson Sampling demonstrates superior robustness and efficiency compared to UCB and ε-Greedy.

Key Insights and Results

Robustness of Sub-linear Regret

A primary finding is that reward drift does not break the fundamental efficiency of these algorithms. Because compensation naturally decreases as the platform identifies the optimal arm, the associated drift also decays. Consequently, the system avoids being permanently misled by early biased feedback, maintaining $\mathcal{O}(\log T)$ expected cumulative regret and compensation.

Sensitivity to Drift Magnitude

While all algorithms are theoretically sound, their sensitivity to the drift coefficient $l$ varies significantly. UCB is particularly sensitive because the drift directly inflates the confidence bounds, creating a feedback loop that requires higher compensation to resolve. In contrast, randomized algorithms like Thompson Sampling are more resilient to the magnitude of the drift.

Comparison of Regret (R) and Compensation (C) across varying drift coefficients (l).

As detailed in the table above, as $l$ increases from 0 to 1.1, UCB's regret more than doubles, whereas Thompson Sampling's regret remains significantly lower and grows at a much slower rate. This highlights the practical advantage of Bayesian exploration in incentivized environments.

Conclusion

This research demonstrates that incentivized exploration is robust to reward drift. By providing $\mathcal{O}(\log T)$ in total incentives, a platform can successfully guide myopic users toward optimal long-term outcomes without being derailed by biased feedback. Future work may explore non-monotonic drift functions, such as "skepticism" effects where high compensation might lead to lower ratings, and the derivation of explicit theoretical lower bounds for regret under drift.

Summary updated

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, ε-Greedy, and Thompson Sampling. Our results show that they all achieve 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.
BibTeX
@inproceedings{liu2020incentivized,
  author = {Zhiyuan Liu and Huazheng Wang and Fan Shen and Kai Liu and Lijun Chen},
  title = {{Incentivized Exploration for Multi-Armed Bandits under Reward Drift}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=96cpk09g1r},
}
Figure