Exploration and Incentives in Reinforcement Learning
Max Simchowitz, Aleksandrs Slivkins
Operations Research · 2024 · Volume 72 · Issue 3
Abstract
How do you incentivize self-interested agents to explore when they prefer to exploit ? We consider complex exploration problems, where each agent faces the same (but unknown) Markov decision process (MDP). In contrast with traditional formulations of reinforcement learning, agents control the choice of policies, whereas an algorithm can only issue recommendations. However, the algorithm controls the flow of information, and can incentivize the agents to explore via information asymmetry. We design an algorithm which explores all reachable states in the MDP. We achieve provable guarantees similar to those for incentivizing exploration in static, stateless exploration problems studied previously. To the best of our knowledge, this is the first work to consider mechanism design in a stateful, reinforcement learning setting. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.0495 .
Keywords
Market Analytics and Revenue Management, incentivized exploration, exploration-exploitation tradeoff, mechanism design, information design, information asymmetry, Bayesian incentive-compatibility, reinforcement learning, Markov decision processes
Enable JavaScript for citation tools and additional paper interactions.