Bandits and Agents: How to Incentivize Exploration?
Talkat Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016) · 2016-09-19..09-23·
summary
Claims a black-box reduction that converts any bandit algorithm into a Bayes incentive-compatible procedure by simulating the original algorithm rarely and hiding exploration inside long exploitation stretches, so Bayesian regret increases only by a constant-factor blowup (constant depends on the prior, not T). Requires a K initial samples assumption so any arm can become the posterior-best with nonzero probability; extends to contextual feedback and batch games but currently shows exponential dependence on number of actions.
AI-written summary · about
chapters (17)
- 0:00Intro
- 1:42Motivation: recommender systems
- 3:23Exploration and incentives
- 8:03Basic model: BIC bandit exploration
- 10:13Information asymmetry
- 12:21Related work: multi-armed bandits
- 12:51Related work: BIC exploration in Econ
- 14:34How to measure performance?
- 15:14Main result: black-box reduction
- 17:42How to sample the other arm?
- 19:53Black-box reduction from algorithm A
- 23:46Assumptions on the prior
- 25:35Outline
- 27:06Black-box reduction with contexts
- 28:38BIC bandit games
- 31:33Connection to medical trials
- 34:37Open questions
related talks
49mIncentivized Exploration
01h 21mAdversarial Bandits: Theory and Algorithms
22mOnline Learning and Bandits with Queried Hints
01h 01mStochastic Bandits: Foundations and Current Perspectives
32mMulti-Player Multi-Armed Bandit: Can We Still Collaborate at Homes Without "Zoom"?
30mPractical Multi Armed Bandits
01h 15mBridging Stochastic and Adversarial Bandits
21mLeveraging Multi-Armed Bandit Algorithms for Dynamic Decision Making