Bayesian exploration: incentivizing exploration in Bayesian games

DOI10.1287/OPRE.2021.2205MaRDI QIDQ5080666zbMATH OpenOpenAlexFDO

Authors Yishay Mansour, Alex Slivkins, Vasilis Syrgkanis, Zhiwei Steven Wu

Publication date 31 May 2022

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1602.07570

zbMATH Keywords

Bayes-correlated equilibriumBayesian incentive compatibilityBayesian persuasionBayesian regretexploration-exploitation trade-offinformation designmultiarmed banditsrevenue management and market analytics

Mathematics Subject Classification ID

Games with incomplete information, Bayesian games (91A27) Principal-agent models (91B43) Economics of information (91B44)

Abstract: We consider a ubiquitous scenario in the Internet economy when individual decision-makers (henceforth, agents) both produce and consume information as they make strategic choices in an uncertain environment. This creates a three-way tradeoff between exploration (trying out insufficiently explored alternatives to help others in the future), exploitation (making optimal decisions given the information discovered by other agents), and incentives of the agents (who are myopically interested in exploitation, while preferring the others to explore). We posit a principal who controls the flow of information from agents that came before, and strives to coordinate the agents towards a socially optimal balance between exploration and exploitation, not using any monetary transfers. The goal is to design a recommendation policy for the principal which respects agents' incentives and minimizes a suitable notion of regret. We extend prior work in this direction to allow the agents to interact with one another in a shared environment: at each time step, multiple agents arrive to play a Bayesian game, receive recommendations, choose their actions, receive their payoffs, and then leave the game forever. The agents now face two sources of uncertainty: the actions of the other agents and the parameters of the uncertain game environment. Our main contribution is to show that the principal can achieve constant regret when the utilities are deterministic (where the constant depends on the prior distribution, but not on the time horizon), and logarithmic regret when the utilities are stochastic. As a key technical tool, we introduce the concept of explorable actions, the actions which some incentive-compatible policy can recommend with non-zero probability. We show how the principal can identify (and explore) all explorable actions, and use the revealed information to perform optimally.

Recommendations

• Bayesian Incentive-Compatible Bandit Exploration
• Incentivizing exploration with heterogeneous value of money
• Recommender systems as mechanisms for social learning
• Exploration and correlation
• Learning and incentives in user-generated content: multi-armed bandits with endogenous arms

Cites work

• Adaptive contract design for crowdsourcing markets: bandit algorithms for repeated principal-agent problems
• An efficient dynamic mechanism
• Asymptotically efficient adaptive allocation rules
• Bandit algorithms
• Bayesian Incentive-Compatible Bandit Exploration
• Characterizing Truthful Multi-armed Bandit Mechanisms
• Close the gaps: a learning-while-doing algorithm for single-product revenue management problems
• Dynamic pricing without knowing the demand function: risk bounds and near-optimal algorithms
• Experimentation in Markets
• Finite-time analysis of the multiarmed bandit problem
• scientific article; zbMATH DE number 3638998 (Why is no real title available?)
• scientific article; zbMATH DE number 1233801 (Why is no real title available?)
• Introduction to multi-armed bandits
• Learning and incentives in user-generated content: multi-armed bandits with endogenous arms
• Multi-armed bandit allocation indices. With a foreword by Peter Whittle.
• Optimal dynamic mechanism design and the virtual-pivot mechanism
• Recommender systems as mechanisms for social learning
• Regret analysis of stochastic and nonstochastic multi-armed bandit problems
• Robust predictions in games with incomplete information
• Strategic Experimentation
• The dynamic pivot mechanism
• The Nonstochastic Multiarmed Bandit Problem
• The price of mediation
• Truthful mechanisms with implicit payment computation

Cited in

(10)

• A Bayesian approach to relevance in game playing
• Regret-minimizing Bayesian persuasion
• Multi-round cooperative search games with multiple players
• Regret minimization in online Bayesian persuasion: handling adversarial receiver's types under full and partial feedback models
• Bayesian Reinforcement Learning with Exploration
• Bayesian Incentive-Compatible Bandit Exploration
• Incentivizing exploration with heterogeneous value of money
• Public Bayesian persuasion: being almost optimal and almost persuasive
• The Price of Incentivizing Exploration: A Characterization via Thompson Sampling and Sample Complexity
• Exploration and incentives in reinforcement learning

This page was built for publication: Bayesian exploration: incentivizing exploration in Bayesian games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5080666)