Introduction
In a standard Multi-armed Bandit (MAB) problem, a single agent attempts to maximize rewards by balancing exploration (trying new options) and exploitation (sticking with known winners). However, in many real-world systems—such as e-commerce recommendation engines or crowdsourcing platforms—the "pulling" of the arms is executed by independent, short-term users.
These users are inherently greedy: they seek to maximize their immediate reward and lack the incentive to explore a sub-optimal arm for the system's long-term learning benefit. To address this, the system controller must offer compensation (e.g., discounts, subsidies, or direct payments) to make less-attractive arms appealing enough for users to select them.
This paper introduces the Known-Compensation Multi-armed Bandit (KCMAB) problem. The core challenge is determining how a central controller can simultaneously minimize "regret" (lost potential reward) and "compensation" (the financial cost of incentivizing exploration). The authors prove that the minimum cost to incentivize exploration scales at the same logarithmic rate as standard regret, and they provide modified versions of classic algorithms that achieve these optimal bounds.
Proposed Algorithms
The authors adapt three classic MAB strategies to the KCMAB setting, ensuring that compensation costs remain bounded:
- Modified UCB: The controller calculates the Upper Confidence Bound (UCB) for each arm. It then offers the player just enough compensation so that the arm with the highest UCB becomes the player's greedy choice.
- Modified $\epsilon$-greedy: Instead of choosing an arm to explore at random (which complicates compensation analysis), this version uses a round-robin approach during exploration phases. This guarantees each arm is explored a deterministic number of times, making payment costs predictable.
- Modified Thompson Sampling (TS): Because analyzing compensation for standard TS is mathematically rigorous, the authors propose a "two-step" round structure. In the first step, the player pulls the arm with the highest empirical mean (requiring no payment). In the second step, the player pulls the arm suggested by Thompson Sampling (requiring payment). This structure ensures the system learns quickly enough to keep compensation costs low.
The paper also establishes a theoretical lower bound, proving that any algorithm maintaining low regret must pay at least $\Omega(\log T)$ in total compensation.
Key Insights
- The Compensation Gap: Compensation is dictated not just by the true quality of an arm, but by its perceived quality. If a high-performing arm experiences an "unlucky" streak of low rewards, the controller must pay more to convince a player to try it again.
- Information is Money: The lower bound proof demonstrates that the cost of incentivizing exploration is fundamentally tied to the same information-theoretic limits as regret. Learning the optimal arm requires paying a price that grows over time.
- Algorithmic Modification Matters: Directly applying standard algorithms fails for compensation analysis. The "two-step" modification for Thompson Sampling cleverly bounds the "unluckiness" of the optimal arm, preventing exorbitant compensation fees.
Experimental Results
The algorithms were evaluated using synthetic Bernoulli Bandits (9 arms with expected rewards ranging from 0.9 down to 0.1) over a horizon of $T = 10,000$ time steps, averaged over 1,000 independent runs.
Optimal Scaling and Overall Performance All three proposed algorithms achieve $O(\log T)$ regret and $O(\log T)$ compensation, successfully matching the theoretical lower bounds in terms of growth rate. In experimental simulations, the Modified Thompson Sampling algorithm performed the best, achieving the lowest combined regret and compensation compared to the other two methods.
Trade-offs in $\epsilon$-greedy The experiments with the $\epsilon$-greedy algorithm clearly demonstrated a fundamental trade-off: selecting a parameter that leads to lower compensation often results in higher regret, and vice versa.
Limitations and Future Work
- Player Rationality: The current model assumes players are perfectly rational and act greedily based solely on the empirical means provided by the system. In reality, users might possess private information or exhibit "noise" in their decision-making.
- Known Sensitivity: The "Known-Compensation" framework assumes the controller knows exactly how much a player values money versus the intrinsic reward. Future work could explore "Unknown-Compensation," where the controller must dynamically learn the players' price sensitivity.
- Contextual Factors: The model does not currently account for user context (e.g., demographics or preferences). Expanding this into a Contextual KCMAB would be a valuable next step for practical applications like personalized advertising.
Summary updated