The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability
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 $\epsilon$-optimal policy with a tight sample complexity of $O(1/\epsilon^2)$.
Code (0)
등록된 구현이 없습니다.
Tasks
Decision MakingNavigateTransfer LearningSimilar Papers 제목 키워드 기반
Strategic Decisions Survey, Taxonomy, and Future Directions from Artificial Intelligence Perspective
Strategic Decision-Making is always challenging because it is inherently uncertain, ambiguous, risky, and complex. It is the art of possibility. We develop a systematic taxonomy of decision-making frames that consists of…
Decision MakingLearning Losses for Strategic Classification
Strategic classification, i.e. classification under possible strategic manipulations of features, has received a lot of attention from both the machine learning and the game theory community. Most works focus on analysin…
ClassificationLearning TheoryTransfer LearningCapturing the Complexity of Human Strategic Decision-Making with Machine Learning
Understanding how people behave in strategic settings--where they make decisions based on their expectations about the behavior of others--is a long-standing problem in the behavioral sciences. We conduct the largest stu…
Decision MakingSC2Arena and StarEvolve: Benchmark and Self-Improvement Framework for LLMs in Complex Decision-Making Tasks
Evaluating large language models (LLMs) in complex decision-making is essential for advancing AI's ability for strategic planning and real-time adaptation. However, existing benchmarks for tasks like StarCraft II fail to…
Spatial ReasoningStarcraft IIThe Statistical Complexity of Interactive Decision Making
A fundamental challenge in interactive learning and decision making, ranging from bandit problems to reinforcement learning, is to provide sample-efficient, adaptive learning algorithms that achieve near-optimal regret. …
Decision Makingreinforcement-learningReinforcement Learning (RL)