  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.
