On the Role of Information Structure in Reinforcement Learning for Partially-Observable Sequential Teams and Games

Summary of review. While the reviewer acknowledges the generality of our framework and technical results, they are skeptical about what advantage or insight this analysis grants compared to existing work, and what concrete new tractable model classes it identifies.

Thank you for your review. We hope to address each of your concerns, clarifying the technical contributions of our work and explaining its significance.

---

The goal of our work is to develop an understanding of how "information structure"---the structure of causal dependence between variables in a system---determines the statistical complexity of learning a sequential decision-making problem.

As you mentioned, there has been a series of recent works that studied classes of tractable POMDPs. However, these previous works tackle a different problem than we do. While many of these works indeed provide a general analysis of statistical complexity, for example in terms of eluder dimension-style quantities, this analysis is not directly linked to the underlying information structure of the system. Thus, in a sense, they are orthogonal to our work as they don't say anything about statistical complexity as a function of information structure or the causal structure in the system's variables.

The main technical contribution of our work is to relate statistical complexity to information structure. This is an important perspective with key insights that are missing from existing general analyses like the ones you mentioned. In particular, the conditions provided in these existing general analyses are not directly connected to the underlying structure of system dynamics.

In our work, we carry out an analysis in terms of the graph representation of the causal structure between system variables, both observable and unobservable. In particular, we identify a key quantity, defined in terms of $d$-separation operations on the DAG representation of the information structure, that we prove characterizes the statistical complexity of general sequential decision-making problems. A key insight from this analysis is a systematic way to understand the difficulty of learning and modeling a system's evolution through the underlying causal structure between its variables, whether those variables are observable or not. In particular, the existence of unobservable system variables that dictate the dynamics of the system can imply a bound on the complexity of observable dynamics that need to be modeled. A simple example of this is POMDPs, where the existence of an unobservable Markovian state implies a bound on the complexity of representing the dynamics of the observables. Our analysis generalizes this to arbitrary information structures.

This characterization of statistical complexity in terms of information structure is, in many cases, a more interpretable characterization of statistical complexity than the types of conditions identified in current general analyses in the literature (e.g., in terms of eluder dimension or a SAIL condition, etc.) because it relates directly to the structure of the system dynamics rather than abstract constructs that may not have real-world physical interpretations.

Moreover, the language of information structure is key to understanding the phenomena of partial observability in a much more powerful way. Our analysis enables considering a much more general notion of partial observability. In standard models, partial observability refers to "emissions" from an underlying Markovian state variable which encodes all relevant information about the system. Under our analysis, we consider a more general notion of partial observability in which system variables evolve according to an arbitrary causal structure (not necessarily Markovian), and the set of observables is specified as an arbitrary subset of all system variables.

Thus, the generality of our framework and analysis provides deep insights into the fundamental theoretical underpinnings of reinforcement learning, characterizing the statistical complexity of learning sequential decision-making problems as a function of the causal structure between system variables.

---

We will make an effort to emphasize the points explained above in the revised paper to better situate our work in the context of existing literature.

---

The POSTs and POSGs are special cases of "generalized PSRs",

It's not quite right to say the POSTs and POSGs are special cases of "generalized PSRs". We develop generalized PSRs as a proof device to obtain an efficient representation of POSTs/POSGs which is amenable to learning. In this paper, we prove (by construction) that certain classes of POSTs/POSGs admit a well-conditioned representation as a generalized PSR, with a condition specified in terms of information structure. Not all POSTs/POSGs admit such a well-conditioned PSR representation. This information-structural condition identifies a new expanded class of tractable problems.

Several examples of information structure are provided, but there isn't a definition of a new, meaningful, and tractable problem class.

The concrete tractable class of sequential decision-making problems is identified in terms of its information structure. It is the class of POSTs/POSGs where $|\mathbb{I}_h^\dagger|$ is bounded, defined in terms of the graph representation of information. The corresponding identifiability condition needed is defined in Definition 6, and is analogous to identifiability conditions considered in previous work on partially-observable models like POMDPs.

The insight attained from such a characterization in terms of the causal structure becomes especially clear when considering physical systems, where the set of system variables and their causal dependence may be known, but only a subset of these variables are observable to the learning agent.

---

We hope our responses address your concerns and look forward to further discussion.

Thank you for your detailed response. Indeed, it is better to move part of the discussion in Appendix D to the main text. Moreover, I would also like to know how the revealing condition (Definition 6) becomes in these examples. It will be good to see whether Definition 6 reduces to a more intuitive (or natural) condition, and what concrete insight it may provide into the learnability of partially observable systems.

I will raise my rating as promised.

Layman explanations of technical definitions

It’s hard to understand what different concepts mean, say core tests. Can a “layman” summary be given after these kinds of definitions?

We will expand on the explanations of technical concepts, and aim to provide simple, plain-language explanations. Core test sets are an important concept in reinforcement learning that appears in many settings. In a sequential decision-making problem, a core test set at a time point $h$ is a set of future trajectories starting from time $h$ whose probabilities conditioned on the history encode everything about the history that can affect the future. That is, if we know the vector of these probabilities $(P(q_h^j | \tau_h))_{j \in [d_h]}$, this forms a sufficient statistic of the past, encoding everything we need to know about $\tau_h$ to predict the future. Hence, the size of the core test set (i.e., number of trajectories in the core test set) is a measure of the complexity of the system dynamics.

Questions & Miscellaneous Comments

Please define dec-POMDP, POMG before using the acronyms. Or at least define them in the Appendix.

We will do this, thank you for pointing this out.

Why in def 5 we need to remove all the arrows pointing to actions? Can actions be dependent on history?

Yes, actions can depend on observation histories in an arbitrary way. This is specified by the information sets of the action variables in our models. For example, in a multi-agent setting, the information sets may specify that each agent can choose an action based on its own history of observations and prior actions (or some limited memory of its history of observations/actions, etc.). However, these information sets do not affect the size of the key quantity $\mathbb{I}_h^\dagger$ that we refer to as the "information structural state space". In fact, this is a crucial aspect of the information-structural causal analysis, as it greatly reduces the implied statistical complexity. The reason for this is that we only need to model the system dynamics (i.e., the dynamics of system variables). In causal language, removing the arrows pointing to actions corresponds to performing a "do" operation on the actions. Under this lens, the core action sequences identified through our information structural analysis are a minimal set of interventions that allow us to learn and model the system.

Line 268. If I understand correctly $G_h$ is possibly a non-square matrix, what’s an eigenvalue in this context? Do the authors mean singular value as they speak about rank?

This is a typo. We mean singular value. $\sigma_k(A)$ refers to the $k$-th singular value of the matrix $A$. Thank you for pointing this out, we will fix it.

---

We hope our responses address your concerns and look forward to further discussion.

Thank you for your review and feedback. We hope to address of each of your concerns in turn.

---

Finite vs Continuous Spaces

... the authors are dealing with finite state and action spaces ... If this is so, I see it as a major weakness

Our results are stated and proved for finite spaces. Finite spaces reveal the interesting aspects of the role of information structure in studying the statistical complexity of sequential decision-making problems. Introducing continuous spaces can introduce certain technical complications that obfuscate the key message of our information structural analysis. We also note that the majority of previous related work considers finite spaces.

Nonetheless, extensions to continuous spaces are possible. We provide some discussion of this below.

• Our formulation of Generalized Predictive State Representations can be extended to capture continuous spaces for system variables. This requires a few technical modifications:
  • In finite spaces, core test sets are a finite set of trajectories $\mathbb{Q}\_{h} = \\{q\_h^{1}, \ldots, q\_h^{d\_h} \\} \subset \mathbb{F}\_h$, where each $q_{h}^j = (x_{h+1}, ..., x_H)$ is a trajectory. In the extension to continuous spaces, the core tests become trajectories of subsets of the underlying continuous space. I.e., $q_h^j = (\mathcal{X}_{h+1}, ..., \mathcal{X}_H)$, where $\mathcal{X}_k \subset \mathbb{X}_k$ is a measurable subset.
  • In finite spaces, the feature vector $\bar{\psi}(\tau\_h) = (\bar{P}(q\_h^j | \tau\_h))\_j$ is the vector probabilities of core tests. While in finite spaces $q_h^j$ is a single trajectory, in continuous spaces $q_h^j$ is a subset of trajectories, and the probabilities become $\bar{P}(x\_{h+1} \in \mathcal{X}\_{h+1}, ..., x\_{H} \in \mathcal{X}\_{H} | \tau\_h)$.
  • In finite spaces, the observable operators M\_h : \mathbb{X}\_h \to \mathbb{R}^{d\_h \times d_\{h-1}} map the variable at time $h$ to a matrix. In continuous spaces, they become linear functionals that map functions over $\mathbb{Q}_{h-1}$ to functions over $\mathbb{Q}_h$.
  • This type of extension to continuous spaces has been considered in standard PSRs and can be extended to our generalized PSR model. From here, the rest of the analysis, including the causal structure analysis using the POST/POSG model and information structure can be appropriately extended.
• Alternatively, our results can also be applied to continuous spaces via appropriate quantization while accounting for the approximation error due to quantization.

We will provide a discussion of extensions to continuous spaces in the updated manuscript.

---

Generality of the POST/POSG Framework and the importance of Information Structure

I am not sure that Figure 1 is fully substantiated. Hopefully, the authors can clarify

In Figure 1, we depict the following relationship between our POST/POSG framework and existing models like POMDPs: MDP $\subset$ POMDP $\subset$ Dec-POMDP $\subset$ POST $\subset$ POSG. That is, via their general specification of information structure and variable structure, POST/POSG capture MDPs, POMDPs, and Dec-POMDPs as special cases.

Information structure is the specification of how events (variables) in a system affect each other. MDPs, POMDPs, Dec-POMDPs, and POMGs each assume a particular variable structure and information structure. In particular, they also assume the existence of a Markovian state that depends only on the state at the previous time step. In our model, we make no such assumption and we allow the information structure to vary across different problem instances, representing the variable structure, information structure, and system dynamics as part of the model specification (by contrast MDPs/POMDPs/etc only represent system dynamics in the model specification and the rest are fixed). In our model, we have a sequence of variables $x_1, x_2, ...$, where each variable depends on an arbitrary subset of the past, can be either a system variable or an action variable, and can be either observable or not observable. This greatly expands the types of system dynamics that can be represented compared to models like POMDPs that assume a Markovian state, and also expands the notion of partial-observability as it now is no-longer defined with respect to an assumed idealized Markovian state.

For further discussion of this, we point to the subsection "llustration: translating to the POST/POSG framework" in Appendix D which provides a detailed worked-through example of how models with fixed information structure such as POMDPs can be naturally represented in the POST/POSG framework.

---

Practical implications

While I appreciate that the paper is theoretic in nature, it is hard to judge it's practical implications in present or even in future.

The primary contribution and focus of our work lies in the development of a foundational understanding of the statistical complexity of reinforcement learning in terms of information structure. Our work has direct implications to representation learning in the context learning sequential decision-making problems. We argue that, when learning in arbitrary dynamic decision-making environments, the fundamental quantity that dictates the statistical complexity of a problem is the size of the information structural state space, $|\mathbb{I}_h^\dagger|$. We note that recent work in machine learning has studied the ability of sequence models like Transformers to learn and represent causal structures in sequential data. Our analysis suggests that the right scaling of the statistical complexity of such tasks, when applied to dynamic decision-making settings, depends on the quantity $|\mathbb{I}_h^\dagger|$. The analysis in this work can inform the design of architectural inductive biases that can better capture and represent such causal structures in order to achieve improved sample efficiency.

We will add further discussion on these practical implications.

Thank you for your engagement with our work and your valuable feedback. We are glad our work resonated with you.

We hope to address your concerns and answer your questions below, in turn.

---

On the identifiability condition and hardness results

The m-step $\mathcal{I}^\dagger$-weakly revealing condition can be stringent. As the paper points out, the condition will be harder to satisfy when $\mathbb{I}_h^\dagger$ is large. It would be helpful to address the sensitivity of claimed results when this condition is not satisfied.

How realistic are the assumptions required for the theoretical results, e.g. the m-step $\mathcal{I}^\dagger$-weakly revealing condition, the $\alpha$-robust weakly-revealing property etc.? E.g., what are the some of the implications of these assumptions in a practical context?

Our results are of an "upper bound" nature, stating that if the identified condition in terms of information structure holds, then learning is tractable and the statistical complexity scales according to $|\mathbb{I}_h^\dagger|$.

We note that the $\mathcal{I}^\dagger$-weakly revealing condition can be thought of as a statistical identifiability condition. Such an identifiability condition is necessary, and is reflective of the fundamental difficulty of the partially-observable setting. For example, in the case of POMDPs, there exist hardness results that state that if an analogous condition does not hold, the statistical complexity can scale exponentially with the relevant quantities (i.e., size of observation/action space).

However, in a practical context, if such a condition does not hold for the true underlying system, it may still hold "approximately". That is, there may exist a statistical model inside the POST/POSG framework that approximates the true system in total variation distance and which is $\mathcal{I}^\dagger$-weakly revealing. In such a case, the implications of our analysis still hold, after accounting for approximation error.

We will add a discussion to the paper on these issues, emphasizing the need for such an identifiability condition, and the practical implications. Thank you for the question.

Practical implications

As you know, the primary contribution and focus of our work lies in the development of a foundational understanding of the statistical complexity of reinforcement learning in terms of information structure. The proposed algorithm is developed as a proof device rather than being intended for practical use. However, our work has direct implications to representation learning in the context learning sequential decision-making problems. When learning in arbitrary dynamic decision-making environments, our analysis reveals that the fundamental quantity that dictates the statistical complexity of a problem is the size of the information structural state space, $|\mathbb{I}_h^\dagger|$. We note that recent work in machine learning has studied the ability of sequence models like Transformers to learn and represent causal structures in sequential data. Our analysis suggests that the right scaling of the statistical complexity of such tasks, when applied to dynamic decision-making settings, depends on the quantity $|\mathbb{I}_h^\dagger|$. The analysis in this work can inform the design of architectural inductive biases that can better capture and represent such causal structures in order to achieve improved sample efficiency.

We will add further discussion on these practical implications.

Upper bounds implied for well-studied special cases

Does this sample complexity upper bound also give reasonable upper bounds for other well-studies cases incorporated by the POST framework such as MDPs, Markov games, Dec-POMDPs?

Yes. The information-structural upper bound established in this work identifies the right quantities with which the statistical complexity scales. We briefly mention this for the case of POMDPs and Dec-POMDPs/POMGs in lines 354-358. This also applies for MDPs and MGs, where $\alpha = 1$ and $\mathbb{I}_h^\dagger = \mathbb{S} \times \mathbb{A}$. However, we note that our analysis recovers the right scaling up to polynomial dependence, but a more tailored analysis can identify tighter polynomial dependence.

---

We hope our responses address your concerns and look forward to further discussion.