Bayesian Incentive-Compatible Bandit Exploration

Yishay Mansour; Aleksandrs Slivkins; Vasilis Syrgkanis

Source-linked AI summary

Bayesian Incentive-Compatible Bandit Exploration

Yishay Mansour, Aleksandrs Slivkins, Vasilis Syrgkanis

arXiv:1502.04147v7Feb 13, 2015cs.GT

TL;DR

The paper studies how a social planner can induce self-interested agents to explore while preserving incentive compatibility under Bayesian priors. It develops DetailFreeRace and related reductions, with guarantees that remain robust to heterogeneous or incompletely known priors, while identifying prior-dependent costs and restrictions on feasible priors.

Problem
The paper asks how to design incentive-compatible exploration that approaches unconstrained bandit performance, despite agents preferring actions with the highest Bayesian expected reward.
Method
The paper models planner recommendations to Bayesian agents and develops DetailFreeRace, including a detail-free sampling stage that uses a fixed winner arm to support exploitation incentives.
Results
The algorithm is BIC under stated conditions, and the BIC guarantee extends to agents with different priors and incomplete knowledge of those priors when their prior mean rewards share a known ordering.
Takeaways & Limitations
The framework applies to contextual medical-trial settings where patient characteristics can inform personalized treatment recommendations.
Takeaways & Limitations
The guarantees require restrictions on the common prior, and the prior-dependent incentive cost can become arbitrarily large or grow exponentially with the number of arms.

Abstract

from arXiv · show

Individual decision-makers consume information revealed by the previous decision makers, and produce information that may help in future decisions. This phenomenon is common in a wide range of scenarios in the Internet economy, as well as in other domains such as medical decisions. Each decision-maker would individually prefer to "exploit": select an action with the highest expected reward given her current information. At the same time, each decision-maker would prefer previous decision-makers to "explore", producing information about the rewards of various actions. A social planner, by means of carefully designed information disclosure, can incentivize the agents to balance the exploration and exploitation so as to maximize social welfare. We formulate this problem as a multi-armed bandit problem (and various generalizations thereof) under incentive-compatibility constraints induced by the agents' Bayesian priors. We design an incentive-compatible bandit algorithm for the social planner whose regret is asymptotically optimal among all bandit algorithms (incentive-compatible or not). Further, we provide a black-box reduction from an arbitrary multi-arm bandit algorithm to an incentive-compatible one, with only a constant multiplicative increase in regret. This reduction works for very general bandit setting that incorporate contexts and arbitrary auxiliary feedback.

1. Introduction

The paper studies how a communicating social planner can make self-interested decision-makers explore while preserving incentive compatibility and social welfare. It develops an asymptotically optimal BIC bandit algorithm and a black-box reduction that extends incentive compatibility to broader learning settings.

1. Introduction: The planner must reconcile agents’ preference for exploiting currently rewarding actions with society’s need for exploration that generates information.Agents consume information from earlier decisions and produce observations that can guide later decisions.
1. Introduction: The model requires each recommended action to maximize the arriving agent’s Bayesian expected reward while the planner maximizes cumulative social welfare.Agents observe a recommendation, choose an action, receive its reward, and leave; the planner observes the round’s events.
1. Introduction: The proposed BIC bandit algorithm achieves asymptotically optimal ex-post regret among all multi-armed-bandit algorithms, despite the incentive constraint.The optimality applies to the asymptotic regret rate, including each particular realization of the common prior and worst-case realizations.
1. Introduction: The regret guarantee includes a prior-dependent additive term that can become arbitrarily large and may grow exponentially with the number of arms.The paper conjectures that this dependence can be an unavoidable price of incentive compatibility.
1. Introduction: A black-box reduction converts an arbitrary learning algorithm into a BIC algorithm with only a prior-dependent constant-factor loss in Bayesian regret.The reduction records the original algorithm’s outputs without depending on its internal workings, enabling modular reuse.
1. Introduction: The approach is detail-free and supports heterogeneous contexts, arbitrary auxiliary feedback, and settings where the planner’s utility differs from agents’ utilities.The reduction can transform contextual bandit algorithms and incorporate feedback beyond the chosen action’s reward.

2. Related work

The paper extends incentive-compatible exploration beyond earlier two-action settings, introducing adaptive exploration and a black-box reduction while supporting broader bandit generalizations. Its adaptive approach improves regret guarantees over fixed exploration, including polylogarithmic regret for constant-gap instances.

The paper differs from related incentive-exploration models whose agents, observations, or interaction structures prevent direct comparison.The authors explicitly caution that direct comparison with several other scenarios is uninformative.
The paper handles an arbitrary constant number of actions, addressing recommendation and medical settings that are rarely binary.The extension requires new technical ideas, especially for the detail-free version.
Adaptive exploration improves ex-post regret from ˜O(T^2/3) to ˜O(√T) for all MAB instances and to polylog(T) for constant-gap instances.The earlier fixed-exploration approach cannot achieve these rates.
Its detail-free result requires less prior knowledge from the planner and permits agents to have different priors.Earlier work required a common, detailed prior shared by all agents.
The black-box reduction supports contextual bandits, budgeted exploration, partial monitoring, and arbitrary auxiliary feedback settings.Earlier work did not provide an analogous reduction or handle these generalizations.

3. Model and preliminaries

The model describes a planner interacting sequentially with self-interested agents who receive recommended actions and private rewards under a shared Bayesian prior. Performance is evaluated through incentive-compatible learning and standard ex-post and Bayesian regret.

Each arriving agent receives a planner signal containing a recommended action, chooses an action, observes its reward, and then leaves permanently.The interaction is not observed by later agents, while the planner observes each round.
When signals are restricted to recommended actions, the setting becomes a multi-armed bandit problem in which arms and actions are synonymous.For BIC algorithms, social welfare equals the corresponding bandit algorithm’s total expected reward.
Rewards are generated independently conditional on each arm’s unknown mean, whose vector is drawn from a Bayesian prior known to agents and planner.The paper uses single-parameter reward-distribution families and allows the prior to be independent across arms.
Bayesian incentive compatibility requires the recommended action to maximize the agent’s posterior expected reward given the signal and prior compliance.Strong BIC requires this inequality to be strict.
Ex-post regret measures performance for a fixed reward vector, whereas Bayesian regret also averages over the prior.Ex-post regret can reveal performance on favorable large-gap instances and remains valid for every prior realization.

4. Basic technique: sampling the inferior arm

The basic technique incentivizes agents to sample an initially inferior arm by hiding exploration within likely exploitation. Under a prior condition ensuring that evidence can make the inferior arm attractive, the algorithm is BIC and collects samples from both arms in bounded time.

4.1. Restricting the prior: Property (P1), requiring a positive probability that sufficiently many arm-1 samples make arm 2 appear better, is necessary for strong BIC exploration.Without this property, a strongly BIC algorithm never plays arm 2.
4.2. Algorithm and analysis: A BIC recommendation for the inferior arm is sustained because agents cannot distinguish exploration from more-likely exploitation, so posterior expected gains offset exploration losses.The exploitation pool length L must exceed a prior-dependent threshold.
4.2. Algorithm and analysis: The algorithm collects at least k samples from each arm and completes in kL + max(k,L) rounds.It uses an initial block of arm-1 recommendations followed by phases that hide one arm-2 recommendation among L agents.
4.2. Algorithm and analysis: The proof compares positive-part expected posterior advantages under different information levels, using the fact that more samples provide more information.The key inequality is E[X|X > 0] Pr(X > 0) ≥ E[Y|Y > 0] Pr(Y > 0).
4.3. Example: Gaussian priors: For Gaussian priors and Gaussian conditional rewards, Property (P1) holds for every k ≥ 1, and increasing samples raises the variance of the posterior difference toward the prior variance.The example uses this distributional structure to interpret the phase-length condition.

5. Black-box reduction from any algorithm

The black-box reduction converts any bandit algorithm into a BIC algorithm by separating incentive-compatible sampling from simulated execution, while preserving performance up to constant overhead.

Black-box reduction: The reduction uses a sampling stage to collect k samples per arm, followed by L-round simulation phases that dedicate one randomly chosen round to the original algorithm.All other agents receive the current exploit-arm recommendation, while only the dedicated round executes the original algorithm and returns its reward.
Incentive compatibility: The reduction is BIC for any input bandit algorithm when k and L exceed prior-dependent thresholds under Property (P2).Property (P2) requires that an arm can have a sufficiently high posterior probability of being best after enough samples from earlier arms.
Performance: The reduction achieves the input algorithm’s average-reward, total-reward, and Bayesian-regret guarantees with only sampling-stage and phase-length overhead.The first c rounds receive worst-case treatment in the bounds, while later phases compare the exploit arm with the arm selected by the original algorithm.
Performance: When the original algorithm has asymptotically optimal Bayesian regret for rewards in [0,1], the incentive-compatible reduction is asymptotically optimal as well.The performance theorem states this inheritance explicitly for the reduced algorithm AIC.
Predictions: The algorithm preserves the input method’s prediction distribution after an initial delay, so auxiliary predictions learn at the same rate up to phase rescaling.For t > c + L, AIC’s prediction has the same distribution as A’s prediction in round floor((t-c)/L).

6. Ex-post regret bounds with a detail-free algorithm

DetailFreeRace achieves BIC exploration with limited prior knowledge by combining detail-free sampling and a racing-based elimination stage. Its guarantees cover ex-post regret and heterogeneous or incomplete prior information under stated assumptions.

Results and discussion: DetailFreeRace provides near-optimal ex-post regret for both favorable and worst-case multi-armed-bandit instances while requiring only limited prior knowledge.The algorithm is described as detail-free because it does not require the precise prior and estimates rewards using sample averages.
Results and discussion: The algorithm is BIC under independent-arm priors, bounded rewards, full support, and appropriate parameters based on the prior mean ordering and threshold.The required inputs include an arm ordering, an approximation to the smallest prior mean, and a threshold upper bound.
Results and discussion: The detail-free guarantee permits agents to have different priors and incomplete knowledge of their own priors when they share the prior-mean ordering and satisfy common conditions.Each agent must know that these ordering and prior conditions hold.
Algorithm: DetailFreeRace samples each arm before using a BIC version of Active Arms Elimination, where arms are repeatedly compared and removed when confidently suboptimal.The sampling stage avoids posterior updates, and the racing stage retains only active arms until one remains.
Detail-free sampling stage: The sampling stage uses a safety margin and sequential comparisons to make exploration recommendations credible without relying on exact posterior means.For multiple arms, the construction uses arm 1 as the previous-phase winner and compares sample averages against prior means with a safety margin.

9 For all remaining agents recommend the single arm a∗that remains in B

The detail-free racing stage eliminates arms over successive phases and recommends the single surviving arm thereafter. Its ex-post regret follows from concentration-based elimination and includes the initial sampling cost.

Incentive compatibility: The algorithm’s BIC conditions require sufficiently large sampling and racing parameters, including thresholds tied to the prior and concentration margin.The stated BIC guarantee applies when θ and k satisfy the required threshold inequalities.
Racing stage: Only active arms are selected in each phase, and an arm is permanently deactivated once evidence shows it is suboptimal with high confidence.The active-arm set is recomputed phase by phase until one arm remains for all later recommendations.
Regret analysis: Chernoff-Hoeffding concentration controls the probability of retaining or eliminating arms, yielding logarithmic dependence on the horizon in the favorable-gap regime.The proof separates cases according to the realized gap and bounds elimination errors through concentration events.
Regret guarantees: The racing stage achieves ex-post regret bounds for every round by combining an initial sampling stage with a subsequent elimination process.The total bound accounts for the duration of initial sampling and the gap between the best and worst arms during those rounds.

7. Extensions: contextual bandits and auxiliary feedback

The paper extends its black-box incentive-compatible reduction to contextual bandits with auxiliary feedback, using context-dependent arm ranks to preserve Bayesian incentive compatibility. The reduction retains performance guarantees while requiring only prior-ranking and posterior-optimization oracles.

7. Extensions: contextual bandits and auxiliary feedback: The reduction handles contexts, auxiliary feedback, and predictions while applying to an arbitrary underlying bandit algorithm.Each round exposes a context, recommends an action, observes reward and auxiliary feedback, and may receive a prediction from the original algorithm.
7. Extensions: contextual bandits and auxiliary feedback: The contextual setting compares performance against the best policy in a restricted policy class using Bayesian contextual regret.The policy class controls the comparator because the full context-to-action policy space can be exponentially large.
7. Extensions: contextual bandits and auxiliary feedback: Arm-rank sampling removes direct dependence on contexts by collecting samples according to context-specific prior reward rankings.The exploit arm is the best arm among previously considered ranks, while the current phase samples the next rank.
7. Extensions: contextual bandits and auxiliary feedback: The construction accesses the common prior through context-specific prior rankings and posterior-mean maximization over collected rank-samples.These operations determine the exploit action and support the simulation of the original algorithm.
7. Extensions: contextual bandits and auxiliary feedback: The reduction is BIC when k ≥ kP and L ≥ LP, where LP is a finite prior-dependent constant.The guarantee assumes the common prior satisfies Property (P5).
7. Extensions: contextual bandits and auxiliary feedback: The sampling stage lasts c = mLk + k rounds, and asymptotically optimal Bayesian contextual regret O(tlog|Π|) is preserved when L is constant.After initialization, predictions have the same distribution as those produced by the original algorithm at a rescaled round index.

8. Properties of the common prior

The common-prior analysis identifies conditions ensuring that sampled arm ranks retain a positive posterior advantage with nontrivial probability. A key monotonicity result shows that this property persists when conditioning on additional samples.

8. Properties of the common prior: Property (P6) requires a prior-dependent positive posterior gap with probability at least ρP: Pr(Xi,a ≥ τP) ≥ ρP.Xi,a is the minimum conditional posterior-mean difference between arm i and the other arms after the specified samples.
8. Properties of the common prior: Property (P6) is preserved when the conditioning vector increases coordinatewise, so additional samples cannot invalidate the condition.Lemma 8.1 establishes this by relating the less-conditioned quantity to a conditional expectation of the more-conditioned one.
8. Properties of the common prior: The proof uses nested sample information: the sigma-field generated by fewer samples is contained in that generated by more samples.The argument applies conditional-expectation reasoning to transfer the property from the larger sample set back to the smaller one.
8. Properties of the common prior: For independent arm priors, posterior quantities associated with fixed sample counts are mutually independent across arms.This independence simplifies the incentive condition and the analysis of posterior gaps between ranked arms.
8. Properties of the common prior: The sufficient prior conditions rely on convergence of posterior means, bounded rewards, distinct prior means, and full support assumptions.The convergence argument invokes Doob’s theorem for bounded realized rewards.

9. Conclusions and open questions

The paper resolves asymptotic regret for incentive-compatible exploration with a constant number of actions and gives a general reduction from arbitrary bandit algorithms to BIC algorithms. It also identifies several directions where the prior assumptions, action-space scale, information disclosure, and detail-free guarantees remain open.

9. Conclusions and open questions: For a constant number of actions, the paper gives a BIC bandit algorithm with asymptotically optimal regret.The regret is optimal among the relevant bandit algorithms described in the paper.
9. Conclusions and open questions: A general black-box reduction converts arbitrary bandit algorithms into BIC algorithms with at most a constant multiplicative regret increase.The reduction applies in a broad explore-exploit setting.
9. Conclusions and open questions: Open questions include prior-independent regret constants, polynomial dependence on the number of actions, and larger structured action spaces.Large-action settings may involve complex correlations that need not satisfy the paper’s prior assumptions.
9. Conclusions and open questions: The mechanism-design framework could be extended to constrain how much information about previous rounds is revealed to agents.The paper notes that practical and legal disclosure constraints make the planner’s problem more difficult.

Appendix A: A simpler detail-free algorithm for two arms

For two arms, the detail-free algorithm has a simpler sampling and racing structure than the general multi-arm construction. Its threshold can also be computed using limited prior information.

Appendix A: A simpler detail-free algorithm for two arms: The two-arm detail-free algorithm samples arm 1, chooses arm 2 only after a sufficient estimated advantage, and then races the two arms.The race alternates arms until one satisfies the stopping condition described in the appendix.
Appendix A: A simpler detail-free algorithm for two arms: The appendix separates the sampling and racing analyses, whose lemmas yield the two-arm performance theorem.The derivation follows the same broad structure as the corresponding general analysis.
Appendix A: A simpler detail-free algorithm for two arms: For two arms, computing the threshold exactly requires only both prior mean rewards and CDF evaluations at one point for each relevant distribution.This is an additional provable guarantee relative to the general case with more than two arms.

A.1. The sampling stage for two arms

The sampling stage samples both arms, then selects an exploit arm using arm 1’s sample average relative to the prior mean of arm 2. Randomized recommendations and parameter conditions ensure Bayesian incentive compatibility.

A.1. The sampling stage for two arms: The exploit arm is chosen from arm 1’s sample average rather than its posterior mean.Arm 2 is selected only when the sample average of arm 1 is sufficiently below arm 2’s prior mean.
A.1. The sampling stage for two arms: After selection, the exploit arm is recommended except to k uniformly random agents among the next L · k agents, who receive arm 2.This randomized exploration supports incentive compatibility while preserving exploitation for most agents.
A.1. The sampling stage for two arms: The algorithm samples both arms k times before selecting an exploit arm.The sampling stage collects k samples from each arm.
A.1. The sampling stage for two arms: Lemma A.1 gives a completion time of Lk + max(k,k∗) rounds and requires Property (P4) plus parameter conditions for BIC.The proof establishes incentive compatibility by showing the relevant conditional expected advantage is nonnegative.
A.1. The sampling stage for two arms: The analysis lower-bounds the incentive-compatible exploration signal using independence and Chernoff–Hoeffding bounds.The sample average is treated as an average of i.i.d. samples and related back to the prior distribution.

A.2. The racing stage for two arms

The racing stage alternates recommendations of both arms in two-round phases until a sample-average gap exceeds a confidence threshold. The winner is then exploited, while the threshold and sample count ensure BIC and logarithmic ex-post regret.

A.2. The racing stage for two arms: The racing algorithm alternates the two arms in two-round phases until one arm wins by a confidence threshold.After elimination, the higher-confidence arm is recommended thereafter.
A.2. The racing stage for two arms: Racing uses k initial samples per arm, phase-specific sample averages, and a threshold parameter θ to determine elimination.The algorithm takes k samples of each arm before splitting the remaining horizon into phases.
A.2. The racing stage for two arms: Algorithm 8 is BIC when θ ≥ θτ, k ≥ θ^2, Property (P4) holds, and θτ depends on Pr(µ2 − µ1 ≥ τ).The threshold is chosen so that a winning arm is sufficiently appealing under agents’ posteriors.
A.2. The racing stage for two arms: The algorithm achieves ex-post regret bounded by 8 log(Tθ) / ∆.Here ∆ = |µ1 − µ2|, and the bound follows because the main loop ends after logarithmically many phases and no regret accrues after correct elimination.
A.2. The racing stage for two arms: The BIC proof shows that the expected incentive to follow arm 2’s recommendation is nonnegative by separating good and bad concentration events.Chernoff bounds control the bad event, while the good event links the winner to the true arm advantage.

A.3. A Chernoff bound for the proof of Lemma A.1

The appendix develops a Chernoff-based bound relating a latent mean to its empirical sample average. This bound supplies the probability and expectation inequalities used in the sampling-stage BIC proof.

A.3. A Chernoff bound for the proof of Lemma A.1: Lemma A.4 bounds E[X | x̂_k ≥ C] Pr(x̂_k ≥ C) from below using the prior probability that X exceeds (1 + ζ)C.The bound requires sufficiently large k and controls the empirical-threshold event through concentration.
A.3. A Chernoff bound for the proof of Lemma A.1: Lemma A.4 assumes X ≥ 1 and i.i.d. samples x1,...,xk in [0,1] with conditional mean X.These assumptions define the sampling model for the concentration result.
A.3. A Chernoff bound for the proof of Lemma A.1: The proof applies Chernoff bounds to relate deviations of x̂_k from X to events where X lies above or below threshold C.The argument factors the relevant probability and conditions on threshold-separated events.
A.3. A Chernoff bound for the proof of Lemma A.1: The appendix instantiates the bound with δ = ε = ζ · C and a lower bound on k involving log(κ · (1 − ζ) · C · Pr(X ≥ (1 + ζ)C)).The resulting inequality preserves a positive fraction of the prior upper-tail probability.