  How do you incentivize self-interested agents to $\textit{explore}$ when they
prefer to $\textit{exploit}$? We consider complex exploration problems, where
each agent faces the same (but unknown) 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.

Machine Learning;Computer Science and Game Theory