On the Role of Information Structure in Reinforcement Learning for Partially-Observable Sequential Teams and Games
This work addresses the challenge of handling complex, time-varying interdependencies in sequential decision-making for AI and ML researchers, offering a systematic approach to analyze and improve tractability, though it appears incremental in extending existing frameworks.
The authors tackled the problem of reinforcement learning in complex sequential decision-making by formalizing a model that explicitly represents the information structure, and they proved an upper bound on sample complexity in terms of a graph-theoretic quantity, recovering known tractability results and identifying new tractable classes.
In a sequential decision-making problem, the information structure is the description of how events in the system occurring at different points in time affect each other. Classical models of reinforcement learning (e.g., MDPs, POMDPs) assume a simple and highly regular information structure, while more general models like predictive state representations do not explicitly model the information structure. By contrast, real-world sequential decision-making problems typically involve a complex and time-varying interdependence of system variables, requiring a rich and flexible representation of information structure. In this paper, we formalize a novel reinforcement learning model which explicitly represents the information structure. We then use this model to carry out an information-structural analysis of the statistical hardness of general sequential decision-making problems, obtaining a characterization via a graph-theoretic quantity of the DAG representation of the information structure. We prove an upper bound on the sample complexity of learning a general sequential decision-making problem in terms of its information structure by exhibiting an algorithm achieving the upper bound. This recovers known tractability results and gives a novel perspective on reinforcement learning in general sequential decision-making problems, providing a systematic way of identifying new tractable classes of problems.