Research map / Multi-agent systems and games / Games and equilibria
The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
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.
Proposes an online strategic interaction model (generalized principal-agent MDP) and a model-based NPIV-based optimistic planning algorithm (OPME) that learns an epsilon-optimal policy under confounding and source-to-target knowledge transfer with Õ(1/ε²) sample complexity.
Problem
Learning an optimal principal policy in sequential principal-agent interactions where agents' private types confound rewards and transitions (information asymmetry), with online non-i.i.d. data collected from a source agent population and deployment on a different target population (knowledge transp
Approach
Use the principal's state-action pairs as instrumental variables in a nonparametric IV (NPIV) minimax estimation to identify reward and transition models despite confounding, with martingale (Freedman) concentration for non-i.i.d. online data; estimate on the source population and explore/plan under the target population via optimistic planning, with a concentrability-style knowledge-transfer term
Key results
- Algorithm OPME learns an epsilon-optimal policy with Õ(1/ε²) samples under realizability, bounded ill-posedness τ_h and knowledge-transfer term C^f_h.
- Sample complexity scales linearly in B^2, distributional Eluder dimension d_V,h, τ_h and C^f_h, with a linear-MDP example giving Õ(d) dependence.
- Authors argue the 1/ε² rate matches the lower bound up to logarithmic factors.
Limitations
- Requires target population distribution and feedback manipulation distribution F to be known to the principal.
- Lower bound dependence on problem-dependent parameters is not established.
- Theoretical only; no experiments reported.
Experimental setup
Metrics: sample complexity
Baselines: PLAN (offline strategic MDP)
Builds on: strategic MDP (PLAN) NPIV minimax estimation distributional Eluder dimension
Closest papers by meaning
- Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactions (NeurIPS 2024 · similarity 0.90)
- Multi-Agent Learning under Uncertainty: Recurrence vs. Concentration (NeurIPS 2025 · similarity 0.87)
- Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning (NeurIPS 2025 · similarity 0.87)
- Evolution of Information in Interactive Decision Making: A Case Study for Multi-Armed Bandits (NeurIPS 2025 · similarity 0.87)
- Information-Directed Offline-to-Online Reinforcement Learning (NeurIPS 2026 · similarity 0.86)
- Understanding Model Selection for Learning in Strategic Environments (NeurIPS 2024 · similarity 0.86)
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.