Multi-armed Bandits with Compensation

Siwei Wang, Longbo Huang

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 {\Delta_i\log T\over KL_i})$, where $\Delta_i$ and $KL_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.

1. Introduction

Standard Multi-armed Bandit (MAB) theory typically assumes a single centralized controller that balances exploration and exploitation to maximize long-term rewards. However, in many modern applications such as e-commerce platforms, crowdsourcing marketplaces, and recommendation systems, decisions are made by short-term players. These players are inherently greedy; they seek to maximize their immediate utility and have no incentive to pull a sub-optimal arm for the sake of future system-wide learning.

To address this, we introduce the Known-Compensation Multi-armed Bandit (KCMAB) framework. In this setting, the controller nudges players toward exploration by offering monetary compensation. The challenge lies in designing a mechanism that minimizes both regret (the difference between the optimal expected reward and the actual reward collected) and compensation (the total cost of incentives paid).

2. Problem Formulation and Theoretical Bounds

In the KCMAB model, a controller manages $K$ arms over $T$ time steps. At each step $t$, a player arrives and chooses an arm $i$ that maximizes their total income:

$$Income = \hat{\mu}_i(t) + c_i(t)$$

where $\hat{\mu}_i(t)$ is the empirical mean reward of arm $i$ and $c_i(t)$ is the compensation offered by the controller. A key contribution of this work is establishing a theoretical compensation lower bound. We prove that any algorithm achieving low regret must necessarily incur a compensation cost that grows logarithmically with time, specifically $\Theta(\sum_i {\Delta_i\log T\over KL_i})$. This demonstrates that regret and compensation are fundamentally linked; learning always comes at a literal price.

3. Proposed Algorithms

We adapt three classic bandit strategies to the KCMAB setting:

  1. UCB with Compensation: The controller calculates the Upper Confidence Bound (UCB) for each arm and provides just enough compensation to make the arm with the highest UCB appear most attractive to the greedy player.
  2. Modified $\epsilon$-greedy: To simplify analysis and bound costs, this version replaces random exploration with a deterministic round-robin approach during exploration phases.
  3. Modified Thompson Sampling (TS): To overcome the analytical difficulties of standard TS, we propose a "round-based" modification. The algorithm alternates between "empirical steps" (pulling the current best arm) and "sample steps" (pulling based on posterior distributions).

4. Experimental Evaluation

We validated our theoretical findings using a synthetic 9-armed Bernoulli bandit environment with a reward vector $\mu = [0.9, 0.8, \dots, 0.1]$. The simulations spanned $T = 10,000$ steps, averaged over 1,000 independent runs.

Algorithm Comparison

Our results confirm that all three algorithms achieve the predicted $O(\log T)$ growth for both regret and compensation. As shown in Figure 2, the Modified Thompson Sampling algorithm significantly outperforms UCB and $\epsilon$-greedy, maintaining the lowest levels of both regret and compensation throughout the horizon.

Comparison of regret and compensation for UCB, Modified Thompson Sampling, and Epsilon-Greedy algorithms.

Exploration Trade-offs

The $\epsilon$-greedy algorithm provides a clear window into the trade-off between exploration and cost. By varying the exploration parameter $\epsilon$, we observe that more aggressive exploration leads to lower cumulative regret but at the cost of significantly higher total compensation (see Figure 4).

Regret and compensation trade-offs for the Epsilon-Greedy algorithm with varying exploration parameters.

5. Conclusion

This paper formalizes the KCMAB problem, proving that logarithmic regret is achievable with logarithmic compensation. While our modified Thompson Sampling algorithm shows superior performance, several avenues for future research remain. These include relaxing the assumption of "Known" player utility, considering myopic players with limited memory, and addressing scenarios with strict total compensation budgets.

Summary updated

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 {\Delta_i\log T\over KL_i})$, where $\Delta_i$ and $KL_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.
BibTeX
@inproceedings{wang2018multi,
  author = {Siwei Wang and Longbo Huang},
  title = {{Multi-armed Bandits with Compensation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=rkZNh8bd-S},
}

Loading related content...

Figure