Learning in Online Principal-Agent Interactions: The Power of Menus
This work addresses a fundamental challenge in online learning for principal-agent problems, offering incremental improvements by extending single-strategy interactions to menu-based approaches.
The paper tackles the problem of learning an agent's private information in online principal-agent interactions by extending existing work to allow the principal to offer a menu of strategies, enabling additional learning from the agent's selection. It provides sample complexity characterizations and algorithms for settings like Stackelberg games, contract design, and information design, including a solution that overcomes a hard instance from prior research.
We study a ubiquitous learning challenge in online principal-agent problems during which the principal learns the agent's private information from the agent's revealed preferences in historical interactions. This paradigm includes important special cases such as pricing and contract design, which have been widely studied in recent literature. However, existing work considers the case where the principal can only choose a single strategy at every round to interact with the agent and then observe the agent's revealed preference through their actions. In this paper, we extend this line of study to allow the principal to offer a menu of strategies to the agent and learn additionally from observing the agent's selection from the menu. We provide a thorough investigation of several online principal-agent problem settings and characterize their sample complexities, accompanied by the corresponding algorithms we have developed. We instantiate this paradigm to several important design problems $-$ including Stackelberg (security) games, contract design, and information design. Finally, we also explore the connection between our findings and existing results about online learning in Stackelberg games, and we offer a solution that can overcome a key hard instance of Peng et al. (2019).