Learning and Steering in Incomplete-Information Games
Organizations: University of Illinois Urbana–Champaign
Abstract
In many modern multi-agent systems, a mediator seeks to influence strategic decision dynamics using only outcome-level feedback and without knowing agents' utilities. In this work, we study how a mediator can learn an unknown game and steer adaptive agents toward outcomes that maximize her utility using only trajectory feedback. The mediator knows the game form and her own objective, but not the agents' utilities. Moreover, she commits to nonnegative payments and provides recommendations and contexts, but receives only a single realized terminal outcome rather than full-information feedback. We develop halving-type algorithms that learn utility differences in normal-form games and conditional continuation-value differences in extensive-form games, achieving a sample complexity of that matches worst-case lower bounds up to logarithmic factors. We then combine these learning procedures with a Lagrangian formulation in an online Learn-Compute-Steer algorithm that interleaves learning, equilibrium computation, and steering toward mediator-optimal extensive-form correlated equilibria (EFCE). With high probability, the Learn-Compute-Steer algorithm achieves a directness gap and an optimality gap of , while time-average payments are of .
Figures & tables
| Problem Type | Zhang et al. (2025a) | Our Results | Worst-case Lower Bounds |
|---|---|---|---|
| Single-Agent NFGs | Thm. 3.5 | Zhang et al. (2025a) | |
| Multi-Agent NFGs | | Thm. 3.10 | Zhang et al. (2025a) |
| EFGs | Thm. 3.15 | Prop. 3.16 |
| Reference | Feedback | Equilibrium | Offline steering | Online steering |
|---|---|---|---|---|
| Zhang et al. (2024) | Full feedback | BCE | ||
| Zhang et al. (2024) | Trajectory feedback | BCE | — | |
| Theorem 4.5 | Trajectory feedback | EFCE | — |
| Stag | Hare | |
|---|---|---|
| Stag | ||
| Hare |
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
Imperfect-Information Games
Imperfect-information games study strategic decisions when players have private information or cannot fully observe the state or actions.
See all 95 papers