Reproduce “Principal-Agent Bandit Games with Self-Interested and Exploratory Learning Agents” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Junyan Liu, Lillian J. Ratliff
The paper introduces principal-agent bandit algorithms designed for more realistic scenarios where agents are self-interested and learn their preferences based on empirical observations, rather than possessing full knowledge of reward means. It achieves improved regret bounds across several settings, including an O("sqrt{KT log(KT)}") bound for self-interested learning agents with I.I.D. rewards and a significant improvement to O("log^2(KT)sqrt{KT}") for exploratory oracle-agents.
Key insights
- Playing "bad" arms for a calculated number of rounds is crucial to ensure sufficient data for accurate incentive estimation, particularly when agents' decisions are based on empirical means.
- An "asymmetric check" within a noisy binary search for incentives efficiently accounts for the agent's continuously updated empirical means, leading to more accurate incentive discovery.
- Techniques like probability amplification (repeating tests logarithmically) and median-based decision-making effectively robustify algorithms against arbitrary agent exploration behaviors.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.