Skip to content

Stackelberg Learning with Outcome-based Payment

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper establishes the computational and statistical complexity of planning and learning in two-player Stackelberg Markov games where a leader agent can use outcome-based payments to incentivize a follower agent. The central finding is that in cooperative games (aligned rewards), payment is unnecessary for planning but necessary for statistically efficient learning, and trajectory payment strictly dominates upfront payment in regret.

Problem

Prior work on Stackelberg Markov games lacks complexity results for the payment setting, leaving open whether outcome-based payments can circumvent known intractability barriers. As businesses deploy agents that must economically align third-party agents (e.g., an AI service provider incentivizing a user), the theoretical foundations for when efficient payment-learning algorithms exist are missing.

Method

The paper models the interaction as a two-player episodic finite-horizon Stackelberg Markov game where the leader commits to a policy and a payment function b(s,a,b) ≥ 0 that additionally rewards the follower for realized state-action tuples. Two payment regimes are studied: trajectory payment (leader pays only on the realized trajectory, ex-post) and upfront payment (leader pays across all state-actions regardless of trajectory, ex-ante). The analysis proceeds by: 1. Reducing optimal planning with payment to the PARTITION problem to prove NP-hardness in general-sum DAG MDPs. 2. Constructing "needle-in-a-haystack" MDP instances to prove exponential sample lower bounds in cooperative games without payment. 3. Showing that in cooperative games with payment, UCB-VI-FP (UCB-VI with the leader setting exploration bonuses as follower payments) achieves sublinear regret by converting optimism bonuses directly into follower payments, enabling coordinated exploration.

Key Contributions

  • General-sum planning is NP-hard with or without payment (reduction from PARTITION) for deterministic DAG MDPs; polynomial-time algorithm exists for tree-structured MDPs (Algorithm 1 via LP).
  • Cooperative learning without payment is statistically hard: exponential sample lower bounds (Ω(2^|S|) for stochastic trees, Ω(2^H) for deterministic DAGs); entropy-regularized best response does not help.
  • Payment enables efficient learning in cooperative games: UCB-VI-FP achieves O(T^{1/2}) regret under trajectory payment (tight) and O(T^{2/3}) under upfront payment.
  • Tight regret separation between payment regimes: trajectory payment achieves O(1) regret for deterministic rewards; upfront payment incurs Ω(T^{1/2}) due to low-visitation-probability states, formally quantifying the value of on-the-fly payment.

Results

  • General-sum DAG planning: NP-hard (both payment settings, Theorem 4.2)
  • General-sum tree planning: polynomial-time (Proposition 4.3)
  • Cooperative learning without payment: Ω(2^|S|) episodes required on stochastic trees (Theorem 5.1); Ω(2^H) on deterministic DAGs (Theorem 5.2)
  • Cooperative learning with trajectory payment: O(T^{1/2}) regret, matching lower bound (Theorem 6.4)
  • Cooperative learning with upfront payment: O(T^{2/3}) regret (Theorem 6.5)
  • Deterministic reward setting: trajectory payment achieves O(|S||A||B|) constant regret; upfront payment incurs Θ(T^{1/2}) regret (Propositions 6.6–6.8)

Limitations

  • Assumes the leader can observe the follower's actions; partial-information settings (unobservable follower actions) are left open.
  • Assumes the leader can observe or elicit truthful follower rewards; reward misreporting in the Markov game case is not fully analyzed (only a bandit-setting bound is given).
  • Results for general-sum games are largely negative; efficient algorithms for other subclasses of general-sum Markov games remain open.
  • Analysis is restricted to two-player games; multi-follower extensions are not addressed.

Relevance to Agentic AI / LLM Agents

As LLM-based agents are deployed in multi-agent pipelines where one agent (e.g., an orchestrator or service provider) must incentivize another (e.g., a user-facing or subcontracted agent), the theoretical question of how to design payment/reward-shaping schemes with provable guarantees is directly actionable. The paper's formalization of outcome-based pricing—already being adopted by SaaS companies (Stripe, Zendesk, Intercom) for AI agent deployments—provides complexity-theoretic grounding for when such economic alignment is tractable. The key insight that payment converts an intractable exploration problem into an efficient one (via UCB-VI-FP) suggests concrete algorithmic designs for orchestrators that need to guide follower agents through unknown state spaces.