# Strategic Decision-Making in the Presence of Information Asymmetry: Provably Efficient RL with Algorithmic Instruments

arXiv: https://arxiv.org/abs/2208.11040 · HTML: https://mlsanity.com/paper/2208.11040/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data.
- Builds on 73 of its 124 references that are in the map.
- First posted on arXiv 23 Aug 2022.

## Placed in

- Offline RL and imitation learning from data / [Offline RL algorithms](https://mlsanity.com/offlinerl/offline-rl-algorithms/)

## Builds on (most cited first, 30 of 73)

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [MOPO: Model-based Offline Policy Optimization](https://mlsanity.com/paper/2005.13239/) (2020)
- [MOReL : Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2005.05951/) (2020)
- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Pessimism Provably Efficient for Offline RL?](https://mlsanity.com/paper/2012.15085/) (2020)
- [Performative Prediction](https://mlsanity.com/paper/2002.06673/) (2020)
- [Information-Theoretic Considerations in Batch Reinforcement Learning](https://mlsanity.com/paper/1905.00360/) (2019)
- [Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism](https://mlsanity.com/paper/2103.12021/) (2021)
- [Bellman-consistent Pessimism for Offline Reinforcement Learning](https://mlsanity.com/paper/2106.06926/) (2021)
- [Strategic Classification](https://mlsanity.com/paper/1506.06980/) (2015)
- [A Theoretical Analysis of Deep Q-Learning](https://mlsanity.com/paper/1901.00137/) (2019)
- [Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage](https://mlsanity.com/paper/2107.06226/) (2021)
- [Strategic Classification from Revealed Preferences](https://mlsanity.com/paper/1710.07887/) (2017)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Minimax-Optimal Off-Policy Evaluation with Linear Function Approximation](https://mlsanity.com/paper/2002.09516/) (2020)
- [V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RL](https://mlsanity.com/paper/2110.14555/) (2021)
- [Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning](https://mlsanity.com/paper/2108.08812/) (2021)
- [The Social Cost of Strategic Classification](https://mlsanity.com/paper/1808.08460/) (2018)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Outside the Echo Chamber: Optimizing the Performative Risk](https://mlsanity.com/paper/2102.08570/) (2021)
- [An Introduction to Proximal Causal Learning](https://mlsanity.com/paper/2009.10982/) (2020)
- [Stochastic Optimization for Performative Prediction](https://mlsanity.com/paper/2006.06887/) (2020)
- [Strategic Classification is Causal Modeling in Disguise](https://mlsanity.com/paper/1910.10362/) (2019)
- [Performative Prediction in a Stateful World](https://mlsanity.com/paper/2011.03885/) (2020)
- [Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity](https://mlsanity.com/paper/2202.13890/) (2022)
- [Minimax Estimation of Conditional Moment Models](https://mlsanity.com/paper/2006.07201/) (2020)
- [Settling the Sample Complexity of Model-Based Offline Reinforcement Learning](https://mlsanity.com/paper/2204.05275/) (2022)
- [The Disparate Effects of Strategic Manipulation](https://mlsanity.com/paper/1808.08646/) (2018)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)

## Built on by (most cited first, 9 of 9)

- [The Sample Complexity of Online Contract Design](https://mlsanity.com/paper/2211.05732/) (2022)
- [Online Learning in a Creator Economy](https://mlsanity.com/paper/2305.11381/) (2023)
- [Regularized DeepIV with Model Selection](https://mlsanity.com/paper/2403.04236/) (2024)
- [Strategic Linear Contextual Bandits](https://mlsanity.com/paper/2406.00551/) (2024)
- [Two-way Deconfounder for Off-policy Evaluation in Causal Reinforcement Learning](https://mlsanity.com/paper/2412.05783/) (2024)
- [Blessing from Human-AI Interaction: Super Reinforcement Learning in Confounded Environments](https://mlsanity.com/paper/2209.15448/) (2022)
- [A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Design](https://mlsanity.com/paper/2210.10278/) (2022)
- [Learning Under Moral Hazard with Instrumental Regression and Generalized Method of Moments](https://mlsanity.com/paper/2405.20642/) (2024)
- [The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability](https://mlsanity.com/paper/2506.09940/) (2025)

## Abstract (arXiv)

We study offline reinforcement learning under a novel model called strategic MDP, which characterizes the strategic interactions between a principal and a sequence of myopic agents with private types. Due to the bilevel structure and private types, strategic MDP involves information asymmetry between the principal and the agents. We focus on the offline RL problem, where the goal is to learn the optimal policy of the principal concerning a target population of agents based on a pre-collected dataset that consists of historical interactions. The unobserved private types confound such a dataset as they affect both the rewards and observations received by the principal. We propose a novel algorithm, Pessimistic policy Learning with Algorithmic iNstruments (PLAN), which leverages the ideas of instrumental variable regression and the pessimism principle to learn a near-optimal principal's policy in the context of general function approximation. Our algorithm is based on the critical observation that the principal's actions serve as valid instrumental variables. In particular, under a partial coverage assumption on the offline dataset, we prove that PLAN outputs a 1 / √K-optimal policy with K being the number of collected trajectories. We further apply our framework to some special cases of strategic MDP, including strategic regression, strategic bandit, and noncompliance in recommendation systems.