The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability

Jiachen Hu, Rui Ai, Han Zhong, Xiaoyu Chen, Liwei Wang, Zhaoran Wang, Zhuoran Yang

TL;DR

This paper tackles the challenge of online reinforcement learning under both information asymmetry (where agents hide private information and act strategically) and knowledge transportability (where data is collected from a source population but applied to a different target population). The authors introduce the Online Strategic Interaction Model and propose a sample-efficient, model-based algorithm (OPME) that uses nonparametric instrumental variables to bypass confounding. The method provably learns an $\epsilon$-optimal policy with a tight sample complexity of $\tilde{O}(1/\epsilon^2)$.

What Problem Does This Paper Address?

Standard reinforcement learning (RL) assumes that the environment is either passive or directly cooperative. However, in many real-world economic and social scenarios—such as contract design between shareholders and a CEO, or university admissions—a "principal" interacts with "agents" who possess private information (their "type") and act to maximize their own short-term rewards. This creates information asymmetry. Because the principal cannot observe the agents' true types or exact motivations, the agents' strategic actions introduce unobserved confounders into the data.

Furthermore, it is often too costly or impossible to run active experiments on the specific group you care about (the target population). Instead, the principal must learn from an alternative group where data is readily available (the source population) and transfer that knowledge—a challenge known as knowledge transportability.

While prior work has addressed these issues in offline settings using independent and identically distributed (i.i.d.) data, this paper addresses a more difficult question: Can a principal efficiently learn an optimal policy online, where data is inherently non-i.i.d., confounded by strategic agent behavior, and subject to a population distribution shift?

Figure 1. Timeline of the interaction. rh and sh+1 (blue) are influenced by observable sh, ah, eh (red) and unobservable th (green). We use numbers to indicate the sequence of events.

Methods

The authors propose a model-based framework called Optimistic Planning with Minimax Estimation (OPME), offering two variants: OPME-D for non-linear dynamical systems with additive noise, and OPME-G for general transition classes.

The core methodology relies on three pillars:

  1. Nonparametric Instrumental Variables (NPIV): To overcome the unobserved confounder (the agent's private type $t_h$), the algorithm treats the principal's own state-action pair $(s_h, a_h)$ as an instrumental variable. As illustrated in the causal graph below, the principal's choices only influence the final rewards and next states through the agent's manipulated feedback ($e_h$), making it a valid instrument for causal identification.
  2. Minimax Value Target Regression: Because online data is non-i.i.d., standard regression fails. The authors use a minimax optimization approach with discriminator function classes ($\mathcal{F}$ and $\mathcal{G}$) to solve conditional moment equations, allowing them to accurately isolate system dynamics from confounding noise.
  3. Target-Driven Optimistic Exploration: The algorithm decouples estimation and exploration. It uses data from the source population to estimate the underlying model, but applies the target population distribution to construct optimistic confidence sets, guiding the principal's next exploratory actions.
Figure 2. The causal graph for the strategic interaction between the principal and the h-th agent. The red line denotes the confounding between (rh, sh+1) and th. ”IV” means instrumental variables.

Datasets

Not discussed in the paper. This work is purely theoretical and focuses on proving mathematical guarantees and sample complexity bounds rather than evaluating on empirical datasets.

Key Insights and Ideas

  • Your Actions are Your Instruments: The most elegant insight is that the principal's own decisions $(s_h, a_h)$ can serve as the mathematical lever (the instrumental variable) needed to untangle the messy, strategic feedback loop engineered by the agents.
  • "Use Source for Estimation, Use Target for Exploration!": The algorithm elegantly splits its operational logic. It corrects for confounding using the source data stream but plans its exploration policy using the target distribution, bypassing the need to ever actively experiment on the target population.
  • Quantifying the Hardness of Transfer: The paper introduces two critical metrics to bound sample complexity:
  • The ill-posedness measure ($\tau_h$), which quantifies how severely the unobserved confounders obscure the true rewards and transitions.
  • The knowledge transfer multiplicative term ($C_h^f$), which acts as a concentrability coefficient measuring the severity of the distribution shift between populations.

Key Results

  • Optimal Sample Complexity: The OPME algorithm provably learns an $\epsilon$-optimal policy for the target population using $\tilde{O}(1/\epsilon^2)$ samples.
  • Tight Bounds: This rate is statistically tight and matches the information-theoretic lower bounds for standard episodic RL, proving that we do not necessarily have to pay a higher rate penalty for managing strategic confounders and distribution shifts.
  • The sample complexity scales linearly with the distributional Eluder dimension ($d_{V,h}$), the ill-posedness measure ($\tau_h$), and the knowledge transfer term ($C_h^f$).

Limitations and Future Work

  • Prior Knowledge Requirements: The model assumes the principal already knows the target population's distribution ($\mathcal{P}^t$) and the feedback manipulation distribution ($\mathcal{F}$). In practice, these would likely need to be estimated beforehand using passive observations.
  • Fully Observable States: The current framework assumes the environment's states are fully observable to the principal, which is rarely true in complex socio-economic systems where market or environmental factors remain hidden.
  • Future Directions: The authors suggest extending this NPIV-based approach to Partially Observable Markov Decision Processes (POMDPs) and exploring its validity when combined with value bridge functions.

Summary updated

Abstract

Information asymmetry is a pervasive feature of multi-agent systems, especially evident in economics and social sciences. In these settings, agents tailor their actions based on private information to maximize their rewards. These strategic behaviors often introduce complexities due to confounding variables. Simultaneously, knowledge transportability poses another significant challenge, arising from the difficulties of conducting experiments in target environments. It requires transferring knowledge from environments where empirical data is more readily available. Against these backdrops, this paper explores a fundamental question in online learning: Can we employ non-i.i.d. actions to learn about confounders even when requiring knowledge transfer? We present a sample-efficient algorithm designed to accurately identify system dynamics under information asymmetry and to navigate the challenges of knowledge transfer effectively in reinforcement learning, framed within an online strategic interaction model. Our method provably achieves learning of an $ε$-optimal policy with a tight sample complexity of $O(1/ε^2)$.
BibTeX
@inproceedings{hu2025sample,
  author = {Jiachen Hu and Rui Ai and Han Zhong and Xiaoyu Chen and Liwei Wang and Zhaoran Wang and Zhuoran Yang},
  title = {{The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability}},
  booktitle = {International Conference on Machine Learning},
  year = {2025},
  url = {https://openreview.net/forum?id=e5yAhjSJ4j},
}
Figure