Optimal Algorithm for Bayesian Incentive-Compatible Exploration

Lee Cohen, Yishay Mansour

TL;DR

This paper introduces an optimal algorithm for a social planner aiming to maximize social welfare by recommending actions to myopic, selfish agents. The planner lacks monetary incentives and relies solely on information asymmetry. The algorithm efficiently balances exploration and exploitation while ensuring agents are incentivized to follow recommendations, a significant step towards solving the open problem of Bayesian incentive-compatible exploration.

What Problem Does This Paper Address?

Imagine a scenario where a central planner needs to guide a series of agents to perform actions that maximize overall societal benefit. The catch? The planner can't directly pay agents to try out new, potentially better actions (exploration). Instead, the planner can only recommend actions, and these recommendations must be "Bayesian Incentive Compatible" (BIC). This means that, given the planner's recommendation and the agent's own knowledge, the agent must find it in their best interest to follow the recommendation. This is tricky because agents are myopic (only care about their immediate reward) and selfish. The core challenge is to design a recommendation strategy that encourages agents to explore unknown actions, even if they might not offer the highest immediate reward, without resorting to monetary incentives, and to do so optimally. This paper tackles this by developing an optimal algorithm for a specific, yet important, setting: when actions have deterministic outcomes with limited support.

Methods

The paper's core contribution is an optimal algorithm for Bayesian Incentive-Compatible Exploration. The algorithm operates by mapping "information states" (what the planner knows about the realized rewards of actions) to recommended actions. A key innovation is the use of a correlated randomization strategy. Instead of each agent's exploration decision being independent, the planner uses a single random parameter y (drawn uniformly from [0, 1]) to coordinate exploration across agents and actions. This ensures that:

  • Prioritized Exploration: Actions with a higher a priori expected reward are explored before actions with lower expected rewards.
  • Coordinated Exploration: The randomization is structured to ensure that agents are assigned to explore specific actions in a coordinated manner, preventing redundant exploration and ensuring efficient progress.
  • BIC Guarantee: The algorithm is designed such that the BIC constraints are always met, meaning agents are always incentivized to follow the planner's recommendations.

The algorithm is presented for a case with three actions and then generalized to k actions. It leverages information states, which are partitions of possible histories, to make decisions.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Information Asymmetry is Key: The planner's advantage lies in knowing more about the action outcomes than the agents. This asymmetry is crucial for incentivizing exploration without direct payments.
  • Correlated Randomization is Powerful: Unlike independent exploration strategies, using a single random parameter to coordinate exploration across agents and actions is vital for optimality. This ensures that exploration is efficient and prioritized.
  • Exploration Order Matters: The optimal strategy always explores actions with higher prior expected rewards first. This seems intuitive but is non-trivial to achieve while maintaining BIC constraints.
  • BIC as a Constraint, Not Just a Goal: The algorithm is built around satisfying BIC constraints at every step, ensuring agents' cooperation.

Key Results

  • The paper presents an optimal algorithm for Bayesian Incentive-Compatible Exploration in the case of deterministic actions with limited support.
  • The algorithm guarantees Bayesian Incentive Compatibility (BIC) for all recommendations.
  • It minimizes the time until all actions are explored (terminal state).
  • For a large number of agents, the algorithm maximizes expected social welfare.
  • The algorithm prioritizes exploration of actions with higher a priori expected rewards.
  • The randomization is correlated across agents and actions, a novel feature for this problem.

Limitations and Future Work

  • Limited Support: The current optimal algorithm is for actions with limited support (e.g., {-1, 0, +1} for the best action, {-1, +1} for others). The authors suggest extending this to continuous distributions for all actions, which they begin to address in Section 5.
  • Deterministic Actions: The current work assumes deterministic action outcomes. Future work could explore stochastic actions, even simple Bernoulli variables with different probabilities.
  • Limited Agent Information: Agents currently have limited information about past outcomes. Exploring scenarios where agents receive more information about the past could be a fruitful direction, while still allowing the planner to explore all actions.
  • Generalizing to Continuous Distributions: While Section 5 introduces a partition policy for continuous distributions of the best action's reward, further work might be needed to fully generalize the optimal algorithm to continuous distributions for all actions.

Summary updated

Abstract

We consider a social planner faced with a stream of myopic selfish agents. The goal of the social planner is to maximize the social welfare, however, it is limited to using only information asymmetry (regarding previous outcomes) and cannot use any monetary incentives. The planner recommends actions to agents, but her recommendations need to be Bayesian Incentive Compatible to be followed by the agents. Our main result is an optimal algorithm for the planner, in the case that the actions realizations are deterministic and have limited support, making significant important progress on this open problem. Our optimal protocol has two interesting features. First, it always completes the exploration of a priori more beneficial actions before exploring a priori less beneficial actions. Second, the randomization in the protocol is correlated across agents and actions (and not independent at each decision time).
BibTeX
@inproceedings{cohen2019optimal,
  author = {Lee Cohen and Yishay Mansour},
  title = {{Optimal Algorithm for Bayesian Incentive-Compatible Exploration}},
  booktitle = {EC},
  year = {2019},
  url = {https://openreview.net/forum?id=yCpvUDYqR3S},
}
Figure