Research map / Multi-agent systems and games / Games and equilibria
Impact of Decentralized Learning on Player Utilities in Stackelberg Games
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies decentralized learning in misaligned Stackelberg games, shows Stackelberg benchmarks force linear regret, and proposes gamma-tolerant and self-gamma-tolerant benchmarks with matching-order algorithms (T^{2/3} and sqrt(T) regret).
Problem
Two learning agents (leader and follower) repeatedly interact in a misaligned, sequential, decentralized Stackelberg game where each observes only its own noisy rewards; standard Stackelberg equilibrium benchmarks are not achievable with sublinear regret for both players.
Approach
Shows the Stackelberg equilibrium benchmark is unachievable under misalignment and introduces gamma-tolerant benchmarks (infimum over epsilon-relaxed Stackelberg utility plus epsilon regularizer over epsilon-best-response sets) that tolerate the other player's suboptimality; designs leader algorithms (ExploreThenUCB, PhasedUCB, LipschitzUCB) that wait for the follower to partially converge.
Key results
- Theorem: any algorithm pair incurs Omega(T) regret for at least one player w.r.t. Stackelberg benchmarks under misalignment.
- ExploreThenUCB-based leader achieves O(T^{2/3}) regret for both players w.r.t. gamma-tolerant benchmarks, matched by an Omega(T^{2/3}) lower bound.
- Under self-gamma-tolerant benchmarks, PhasedUCB achieves O(sqrt(T|A||B| log T)) regret for both players, matching an Omega(sqrt(T|A||B|)) lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ExploreThenUCB for the leader after an initial waiting/exploration phase | StrongDSG with a follower meeting the stated instantaneous-regret condition · γ-tolerant benchmarks | maximum regret: O\left(|\mathcal{A}|^{1/3} |\mathcal{B}|^{1/3} (\log T)^{1/3} T^{2/3} \right) | Helped |
| Replace ExploreThenCommit with ExploreThenCommitThrowOut so the leader waits for follower exploration | StrongDSG with a follower using ExploreThenCommit · γ-tolerant benchmarks | maximum regret: O\left(|\mathcal{A}|^{1/3} |\mathcal{B}|^{1/3} (\log T)^{1/3} T^{2/3} \right) | Helped |
| Use ExploreThenCommit for both players, with leader exploration ending before follower exploration | StrongDSG · γ-tolerant benchmarks | minimum player regret: \Omega(T) | Hurt |
| Use PhasedUCB for the leader with per-action ActiveArmElimination for the follower | WeakDSG · self-γ-tolerant benchmarks | maximum regret: O\left(\sqrt{|\mathcal{A}| \cdot |\mathcal{B}| \cdot T \cdot \log T}\right) | Helped |
| Use LipschitzUCB when utilities have bounded Lipschitz constant | StrongDSG with a follower satisfying the stated anytime-regret bound · Original Stackelberg benchmarks | leader regret: O\left(L \sqrt{T |\mathcal{A}| |\mathcal{B}| \log T}\right) | Helped |
| Use LipschitzUCB when utilities have bounded Lipschitz constant | StrongDSG with a follower satisfying the stated anytime-regret bound · Original Stackelberg benchmarks | follower regret: O\left(L^2 \sqrt{T |\mathcal{A}| \cdot |\mathcal{B}| \log T} \right) | Helped |
| Require the follower to be only approximately best-responding, using the γ-tolerant benchmarks instead of Stackelberg payoffs | Decentralized Stackelberg games · γ-tolerant benchmarks | maximum regret: \Omega(T) -> O(T^{2/3}) | Helped |
| Use self-γ-tolerant benchmarks, which also tolerate the player's own suboptimality | Decentralized Stackelberg games · Self-γ-tolerant benchmarks | maximum regret: O(T^{2/3}) -> O\left(\sqrt{|\mathcal{A}| \cdot |\mathcal{B}| \cdot T \cdot \log T}\right) | Helped |
| Require a bounded Lipschitz constant between the players' utilities | Decentralized Stackelberg games using LipschitzUCB · Original Stackelberg benchmarks | regret growth in T: O(T^{2/3}) -> O(\sqrt{T}) | Helped |
| Use Stackelberg equilibrium payoffs as the regret benchmark | Any decentralized Stackelberg learning algorithms · Original Stackelberg benchmarks | maximum regret: \Omega(T) | Hurt |
Surprising findings
- Both players running ExploreThenCommit can incur linear regret even under the relaxed gamma-tolerant benchmark.
- Misalignment alone, through small differences in follower utilities, can force linear regret for the leader under standard Stackelberg benchmarks.
Limitations
- Gap between upper bound |A|^{1/3} and lower bound independent of |A| in the T^{2/3} regime.
- Lipschitz and self-tolerant results require specific follower algorithms or continuity assumptions on utilities.
Experimental setup
Metrics: regret
Baselines: ExploreThenCommit Stackelberg equilibrium benchmark
Builds on: explore-then-commit UCB active arm elimination
Closest papers by meaning
- Is Learning in Games Good for the Learners? (NeurIPS 2023 · similarity 0.92)
- Online Learning in Stackelberg Games with an Omniscient Follower (ICML 2023 · similarity 0.92)
- No-regret Learning in Harmonic Games: Extrapolation in the Face of Conflicting Interests (NeurIPS 2024 · similarity 0.90)
- Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Sequential Games (ICLR 2024 · similarity 0.89)
- Maximizing utility in multi-agent environments by anticipating the behavior of other learners (NeurIPS 2024 · similarity 0.89)
- Learning to Steer Learners in Games (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.