Contextual Search in Principal-Agent Games: The Curse of Degeneracy
Yiding Feng, Mengfan Ma, Bo Peng, Zongqi Wan · 2025
Read Contextual Search in Principal-Agent Games: The Curse of Degeneracy by Yiding Feng, Mengfan Ma, Bo Peng, Zongqi Wan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-18567.txt.
Introduction
Yiding Feng works with Mengfan Ma, Bo Peng, and Zongqi Wan. They study a repeated deal between a principal and agents. Each round, the principal offers contracts. The offers rest on context and past feedback. The principal does not know the agents' true costs or rewards. The setup extends classic contextual pricing. There, the only real choice is a price. Here, agents can take much richer actions.
The results are sobering. One regret bound grows almost exponentially with context size. A second, classic regret bound is also proved. Even three actions and two context traits make the problem vastly harder. Contextual pricing, by contrast, admits near-optimal learning. The authors blame a structural trap. They call it contextual action degeneracy. Crafted contexts can make some actions strictly worse. The principal then cannot lure agents to try them. Exploration gets blocked at the root.
Catalog record
| CREATOR | Yiding Feng, Mengfan Ma, Bo Peng, Zongqi Wan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 225 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-18567