cs.GTNov 5, 2026

Learning and Steering in Incomplete-Information Games

Authors: Asrın Efe Yorulmaz, Tamer Başar

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 O~(ε−2)\widetilde O(\varepsilon^{-2}) 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 O~(T−1/4)\widetilde O(T^{-1/4}), while time-average payments are of O~(T−1/8)\widetilde O(T^{-1/8}).

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Learning in Structured Stackelberg Games

    Apr 11, 2025Maria-Florina Balcan, Kiriaki Fragkia, Keegan HarrisGame TheoryStackelberg Games

  2. Stackelberg POMDP: Learning to Lead via Reinforcement Learning

    Oct 7, 2022Matthias Gerstgrasser, Gianluca Brero, Alon Eden +6Game-Theoretic RLReinforcement Learning