mlsanityData to 14 Oct 2026

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

arXiv 2208.11040 ↗First posted 23 Aug 2022stat.ML cs.IT cs.LGcited by 9

On the map: Offline RL and imitation learning from data → Offline RL algorithms

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.

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.

Builds on

73 of 124 references.

Closest ancestors · 18

Same direction, newest first

  1. 2022Provably Efficient Offline Multi-agent Reinforcement Learning via Strategy-wise Bonus1 Jun
  2. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game31 May
  3. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes26 May
  4. 2022Settling the Sample Complexity of Model-Based Offline Reinforcement Learning11 Apr
  5. 2022Pessimistic Q-Learning for Offline Reinforcement Learning: Towards Optimal Sample Complexity28 Feb
  6. 2021Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processes28 Oct
  7. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learning19 Aug
  8. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coverage13 Jul
  9. 2021Bellman-consistent Pessimism for Offline Reinforcement Learning13 Jun
  10. 2021Risk Bounds and Rademacher Complexity in Batch Reinforcement Learning25 Mar
  11. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism22 Mar
  12. 2021Instrumental Variable Value Iteration for Causal Offline Reinforcement Learning19 Feb
6 more
  1. 2021Finite Sample Analysis of Minimax Offline Reinforcement Learning: Completeness, Fast Rates and First-Order Efficiency5 Feb
  2. 2020Is Pessimism Provably Efficient for Offline RL?30 Dec
  3. 2020MOPO: Model-based Offline Policy Optimization27 May
  4. 2020MOReL : Model-Based Offline Reinforcement Learning12 May
  5. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems4 May
  6. 2020Confounding-Robust Policy Evaluation in Infinite-Horizon Reinforcement Learning11 Feb

Other references · 55

  1. 2016Error bounds for approximations with deep ReLU networkscited by 574
  2. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  3. 2020Performative Predictioncited by 327
  4. 2019Information-Theoretic Considerations in Batch Reinforcement Learningcited by 287
  5. 2015Strategic Classificationcited by 257
  6. 2019A Theoretical Analysis of Deep Q-Learningcited by 215
  7. 2017Strategic Classification from Revealed Preferencescited by 128
  8. 2019Model-Based Reinforcement Learning with a Generative Model is Minimax Optimalcited by 127
  9. 2020Minimax-Optimal Off-Policy Evaluation with Linear Function Approximationcited by 120
  10. 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 114
  11. 2018The Social Cost of Strategic Classificationcited by 105
  12. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
38 more
  1. 2021Outside the Echo Chamber: Optimizing the Performative Riskcited by 96
  2. 2020An Introduction to Proximal Causal Learningcited by 95
  3. 2020Stochastic Optimization for Performative Predictioncited by 93
  4. 2019Strategic Classification is Causal Modeling in Disguisecited by 92
  5. 2020Performative Prediction in a Stateful Worldcited by 90
  6. 2020Minimax Estimation of Conditional Moment Modelscited by 83
  7. 2018The Disparate Effects of Strategic Manipulationcited by 75
  8. 2017Online Reinforcement Learning in Stochastic Gamescited by 67
  9. 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 67
  10. 2019Off-Policy Evaluation in Partially Observable Environmentscited by 66
  11. 2021Strategic Classification in the Darkcited by 66
  12. 2020Causal Strategic Linear Regressioncited by 65
  13. 2020Off-policy Policy Evaluation For Sequential Decisions Under Unobserved Confoundingcited by 61
  14. 2021Strategic Classification Made Practicalcited by 59
  15. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 58
  16. 2021Who Leads and Who Follows in Strategic Classification?cited by 53
  17. 2020The Strategic Perceptroncited by 48
  18. 2022Multiplayer Performative Prediction: Learning in Decision-Dependent Gamescited by 44
  19. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 44
  20. 2022The Efficacy of Pessimism in Asynchronous Q-Learningcited by 42
  21. 2020Off-policy Evaluation in Infinite-Horizon Reinforcement Learning with Latent Confounderscited by 41
  22. 2020Provably Efficient Causal Reinforcement Learning with Confounded Observational Datacited by 40
  23. 2022Regret Minimization with Performative Feedbackcited by 40
  24. 2021State Dependent Performative Prediction with Stochastic Approximationcited by 39
  25. 2021On Improving Model-Free Algorithms for Decentralized Multi-Agent Reinforcement Learningcited by 36
  26. 2022On Well-posedness and Minimax Optimal Rates of Nonparametric Q-function Estimation in Off-policy Evaluationcited by 33
  27. 2021Stateful Strategic Regressioncited by 32
  28. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 28
  29. 2021Off-Policy Evaluation in Partially Observed Markov Decision Processes under Sequential Ignorabilitycited by 24
  30. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  31. 2021On Instrumental Variable Regression for Deep Offline Policy Evaluationcited by 22
  32. 2021Strategic Rankingcited by 21
  33. 2016Learning Nash Equilibrium for General-Sum Markov Games from Batch Datacited by 20
  34. 2022Learning Markov Games with Adversarial Opponents: Efficient Algorithms and Fundamental Limitscited by 17
  35. 2020Gaming Helps! Learning from Strategic Interactions in Natural Dynamicscited by 15
  36. 2021Decentralized Cooperative Reinforcement Learning with Hierarchical Information Structurecited by 14
  37. 2021Estimating and Improving Dynamic Treatment Regimes With a Time-Varying Instrumental Variablecited by 13
  38. 2022Decentralized Optimistic Hyperpolicy Mirror Descent: Provably No-Regret Learning in Markov Gamescited by 12

50 most cited of 55 All 55 (JSON)

Built on by

Cited by year

Citing papers per year: 2022: 3; 2023: 1; 2024: 4; 2025: 1.

9 papers.

  1. 2022The Sample Complexity of Online Contract Designcited by 35
  2. 2023Online Learning in a Creator Economycited by 8
  3. 2024Regularized DeepIV with Model Selectioncited by 7
  4. 2024Strategic Linear Contextual Banditscited by 5
  5. 2024Two-way Deconfounder for Off-policy Evaluation in Causal Reinforcement Learningcited by 5
  6. 2022Blessing from Human-AI Interaction: Super Reinforcement Learning in Confounded Environmentscited by 3
  7. 2022A Reinforcement Learning Approach in Multi-Phase Second-Price Auction Designcited by 1
  8. 2024Learning Under Moral Hazard with Instrumental Regression and Generalized Method of Momentscited by 0
  9. 2025The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportabilitycited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2022Pessimism meets VCG: Learning Dynamic Mechanism Design via Offline Reinforcement Learning
  2. 2026Conservative Equilibrium Discovery in Offline Game-Theoretic Multiagent Reinforcement Learning
  3. 2022Model-Based Offline Reinforcement Learning with Pessimism-Modulated Dynamics Belief
  4. 2026Information-Directed Offline-to-Online Reinforcement Learning
  5. 2025Semi-pessimistic Reinforcement Learning
  6. 2024Compositional Conservatism: A Transductive Approach in Offline Reinforcement Learning
  7. 2024Strategically Conservative Q-Learning
  8. 2021Dealing with the Unknown: Pessimistic Offline Reinforcement Learning