mlsanityData to 14 Oct 2026

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

arXiv 2506.09940 ↗First posted 11 Jun 2025cs.LG cs.AI stat.MLcited by 0

Not on the map. Why?

Abstract (arXiv)

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).

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 53 of its 97 references that are in the map. First posted on arXiv 11 Jun 2025.

Builds on

53 of 97 references.

References · 53

  1. 2015Domain-Adversarial Training of Neural Networkscited by 3,044
  2. 2019A Comprehensive Survey on Transfer Learningcited by 1,160
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2016Contextual Decision Processes with Low Bellman Rank are PAC-Learnablecited by 292
  7. 2020Transfer Learning in Deep Reinforcement Learning: A Surveycited by 265
  8. 2020Model-Based Reinforcement Learning with Value-Targeted Regressioncited by 234
  9. 2020FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPscited by 233
  10. 2021Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithmscited by 223
  11. 2021The Statistical Complexity of Interactive Decision Makingcited by 218
  12. 2019Provably Efficient Exploration in Policy Optimizationcited by 205
38 more
  1. 2014Taming the Monster: A Fast and Simple Algorithm for Contextual Banditscited by 201
  2. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  3. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  4. 2019Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Boundscited by 195
  5. 2021Bilinear Classes: A Structural Framework for Provable Generalization in RLcited by 178
  6. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 176
  7. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  8. 2020Reinforcement Learning via Fenchel-Rockafellar Dualitycited by 100
  9. 2022When Is Partially Observable Reinforcement Learning Not Scary?cited by 100
  10. 2020Minimax Estimation of Conditional Moment Modelscited by 83
  11. 2021Model-free Representation Learning and Exploration in Low-rank MDPscited by 82
  12. 2018Policy Certificates: Towards Accountable Reinforcement Learningcited by 81
  13. 2021Offline Reinforcement Learning: Fundamental Barriers for Value Function Approximationcited by 71
  14. 2019Off-Policy Evaluation in Partially Observable Environmentscited by 66
  15. 2020Confounding-Robust Policy Evaluation in Infinite-Horizon Reinforcement Learningcited by 57
  16. 2018Transfer Learning for Related Reinforcement Learning Tasks via Image-to-Image Translationcited by 50
  17. 2021Near-optimal Representation Learning for Linear Bandits and Linear RLcited by 45
  18. 2020Off-policy Evaluation in Infinite-Horizon Reinforcement Learning with Latent Confounderscited by 41
  19. 2021Proximal Reinforcement Learning: Efficient Off-Policy Evaluation in Partially Observed Markov Decision Processescited by 41
  20. 2020Provably Efficient Causal Reinforcement Learning with Confounded Observational Datacited by 40
  21. 2020POPCORN: Partially Observed Prediction COnstrained ReiNforcement Learningcited by 36
  22. 2021Instrumental Variable Value Iteration for Causal Offline Reinforcement Learningcited by 35
  23. 2022Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systemscited by 35
  24. 2022On Well-posedness and Minimax Optimal Rates of Nonparametric Q-function Estimation in Off-policy Evaluationcited by 33
  25. 2021Strategic Instrumental Variable Regression: Recovering Causal Relationships From Strategic Responsescited by 32
  26. 2022A General Framework for Sample-Efficient Function Approximation in Reinforcement Learningcited by 31
  27. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  28. 2022Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processescited by 26
  29. 2021Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers?cited by 24
  30. 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
  31. 2020Contracts under Moral Hazard and Adverse Selectioncited by 21
  32. 2021A Spectral Approach to Off-Policy Evaluation for POMDPscited by 21
  33. 2022Future-Dependent Value-Based Off-Policy Evaluation in POMDPscited by 21
  34. 2022Sequential Information Design: Markov Persuasion Process and Its Efficient Reinforcement Learningcited by 18
  35. 2021Near-Optimal Reward-Free Exploration for Linear Mixture MDPs with Plug-in Solvercited by 14
  36. 2021Estimating and Improving Dynamic Treatment Regimes With a Time-Varying Instrumental Variablecited by 13
  37. 2021Bayesian Persuasion in Sequential Decision-Makingcited by 12
  38. 2020An Efficient Transfer Learning Framework for Multiagent Reinforcement Learningcited by 11

50 most cited of 53 All 53 (JSON)

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Conjectural Online Learning with First-order Beliefs in Asymmetric Information Stochastic Games
  2. 2025Learning Equilibria from Data: Provably Efficient Multi-Agent Imitation Learning
  3. 2026Conservative Equilibrium Discovery in Offline Game-Theoretic Multiagent Reinforcement Learning
  4. 2023Foundations for Transfer in Reinforcement Learning: A Taxonomy of Knowledge Modalities
  5. 2026Information-Directed Offline-to-Online Reinforcement Learning
  6. 2021Importance of Empirical Sample Complexity Analysis for Offline Reinforcement Learning
  7. 2022The Role of Coverage in Online Reinforcement Learning
  8. 2024Understanding Model Selection For Learning In Strategic Environments