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

Authors: awni  altabaa
zhuoran  yang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 05:05:18

Abstract: In sequential decision-making problems, the *information structure* describes the causal dependencies between system variables, encompassing the dynamics of the environment and the agents' actions. Classical models of reinforcement learning (e.g., MDPs, POMDPs) assume a restricted 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 complexity 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.

Main paper: 
 introduction: 
 The information structure of a sequential decision-making problem is a description of the causal dependencies between system variables. In particular, the information structure specifies the subset of past events that causally influence the present state. This includes information affecting system dynamics and information available to each agent when choosing an action. The control community has long recognized the importance of information structure, leading to the development of the celebrated Witsenhausen intrinsic model [1] , and extensive study since the 1970s [e.g., [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] .In general, sequential decision-making problems with arbitrary causal dependencies between system variables can be computationally and statistically intractable in both control and learning settings [3, 15] . In response, early research has identified classes of tractable information structures. For example, Markov Decision Processes (MDP) and Markov teams/games assume an observable Markovian state, which serves as a sufficient statistic for the system's evolution. These structural assumptions enable practical planning and learning algorithms, for example based on dynamic programming [16, 17] . Although such restricted model classes can enable more fruitful analysis, they lack the expressiveness needed to naturally capture the causal structures of complex real-world sequential decision-making problems, where each event in the system may depend arbitrarily on past events. The concept of information structure is also fundamental to studying the phenomenon of partial observability. In general, partial observability refers to situations where a system's evolution depends on a potentially large number of sequential events, but only a subset of these events is observable by the learning agent. However, commonly studied models capture only a restrictive form of this phenomenon. For example, in a Partially-Observable Markov Decision Process (POMDP)-the standard model of partial observability -it is assumed that a Markovian state exists and that each observation is a noisy measurement of the current state. This assumption is often unrealistic, as general systems may not have clearly defined "states", and observations may be generated by more complex dependencies. Information structure provides a more powerful framework for understanding partial observability, capturing a general notion in which system variables evolve with an arbitrary causal structure (not necessarily Markovian), and the set of observables is any subset of all system variables.The highly-regular information structures of classical models make analysis more tractable, enabling favorable theoretical results [e.g., [18] [19] [20] [21] [22] and driving notable empirical success across a wide range of domains [e.g., [23] [24] [25] [26] [27] [28] . Despite this empirical success, a general theory addressing the role of information structure in the statistical aspects of reinforcement learning is missing. We argue for the perspective that information structure is an important component of analyzing and solving reinforcement learning problems. A rich and flexible representation of information structure is essential to faithfully capture real-world sequential decision-making problems, where the system evolves according to a complex and time-varying dependence on the past, and different agents have different information available to them at different points in time.In this work, we formulate a general model of sequential decision-making with an explicit representation of information structure, and study the role of information structure in the statistical complexity of reinforcement learning. Explicitly modeling information structure allows us to identify a broader class of tractable decision-making problems and ultimately develop more tailored reinforcement learning approaches that leverage this structure. A model for representing information structure. We propose partially-observable sequential teams (POST) and partiallyobservable sequential games (POSG) as general models that contain an explicit representation of information structure as part of the problem specification. This forms a unifying framework that enables an analysis of the role of information structure in RL and captures commonly studied RL models as special cases, including MDPs, Markov teams/games, POMDPs, and Dec-POMDPs/POMGs (Figure 1 ). The models introduced in this work draw inspiration from Witsenhausen's intrinsic model [1] and its variants from the control literature [29, 30] , with added elements to model partial observability in the context of reinforcement learning.Theoretical analysis of sequential decision-making through information structure. We characterize the complexity of the observable dynamics of any sequential decision-making problem through a graph-theoretic analysis of the information structure. Moreover, we propose a generalization of predictive state representations-which may be of independent interest-and construct such a representation for POSTs/POSGs by exploiting information structure. This provides a robust and efficient parameterization amenable to learning.Learning theory & information-structural analysis of statistical complexity. We prove an upper bound on the sample complexity of learning general sequential decision-making problems, expressed as a function of information structure. In particular, the dependence is on an interpretable quantity derived from a graphical representation that can be thought of as an effective "information-structural state", generalizing the typical notion of a Markovian state. We prove this result by exhibiting an algorithm achieving this upper bound, making use of the generalized predictive state representation constructed earlier which provides a robust representation amenable to learning. In doing so, we identify a larger class of statistically tractable reinforcement learning problems. Related Work. We provide a detailed discussion of related work in Appendix B. 
background & preliminaries: 
 What follows is an abridged description of the relevant background and preliminaries. We refer the reader to Appendix C for a more detailed treatment, and to Appendix A for a summary of notations.Consider a controlled stochastic process (X 1 , . . . , X H ), where X h is a random variable corresponding to the variable at time h. At each time h ∈ [H], the variable X h may be either an 'observation' (i.e., observable system variable) or an 'action'. The dynamics of this stochastic process are described by a tuple (H, {X h } h , O, A, P), where H is the time horizon, X h is the variable space at time h, O ⊂ [H] is the index set of observations (i.e., X h is an observation if h ∈ O), A ⊂ [H] is the index set of actions, and P = {P h } h∈O is a set of probability kernels which describes the probability of any trajectory x 1 , . . . , x H given the actions, P [{x s : s ∈ O} | {x s : s ∈ A}] = h∈O P h [x h | x 1 , . . . , x h-1 ]. A choice of policy π induces a probability distribution P π on X 1 × • • • × X H . The objective of the agent(s) is to choose a policy which maximizes their expected rewardV R (π) = E π [R(X 1 , . . . , X H )].Let H h = s∈1:h X s denote the space of histories at time h and F h = s∈h+1:H X s denote the space futures at time h. Similarly, let H o h = obs(H h ) = s∈O 1:h X s denote the observation component of histories and let H a h = act(H h ) = s∈A 1:h X s denote the action component. The observation and action components of the futures, F o h and F a h respectively, are defined similarly. Here, obs(•) and act(•) extract the observation and action components, respectively, of any trajectory. We define the system dynamics matrix D h ∈ R |H h |×|F h | as the matrix giving the probability of each possible pair of history and future at time h given the execution of the actions,[D h ] τ h ,ω h := P [τ h , ω h ] ≡ P [τ o h , ω o h | do(τ a h , ω a h )], where τ h is the history, ω h is the future, and τ o h , τ a h , ω o h , ω a h separate the history and future into observation components and action components.The rank of the dynamics of a sequential decision-making problem is a measure of its complexity. It is defined as the maximal rank of its dynamics matrices. Definition 1 (Rank of dynamics). The rank of the dynamics {D h } h∈[H] is r = max h∈[H] rank(D h ).Predictive state representations (PSR) [31, 32] are a representation of dynamical systems and sequential decision-making problems based on predicting future observations given the past, without explicitly modeling a latent state. In this section, we propose and formalize a generalization of standard PSRs which allows for an arbitrary order of observations and actions. This generalization is necessary to capture POSTs/POSGs (introduced in Section 3), but may also be of independent interest.The "PSR rank" of a sequential decision-making problem coincides with the rank of its dynamics (Definition 1). Denote r h := rank(D h ). At the heart of predictive state representations is the concept of "core test sets." A core test set at time h is a set of futures such that the vector of probabilities of those futures conditioned on the past encodes all the information that the past contains about the future. Definition 2 (Core test sets). A core test set at time h is a subset of d h ≥ r h futures,Q h := {q 1 h , . . . , q d h h } ⊂ F h , such that the submatrix D h [Q h ] ∈ R |H h |×d h is full-rank.The d h -dimensional vector ψ h (τ h ) := (P[τ h , q 1 h ], . . . , P[τ h , q d h h ]) serves as a sufficient statistic for computing the probability of any future conditioned on τ h . Intuitively, core test sets relate the rank of the dynamics to a representation based on predicting future outcomes. A PSR parameterization of the system dynamics represents the probability of any trajectory using the sufficient statistics ψ h via a set of operators that iteratively update the predictive representations at each step as new observations come in. We proceed to formally define our generalized predictive state representation. Definition 3 (Generalized Predictive State Representations). Consider a sequential decision-making problem (X h ) h∈ [H] where A, O partition [H] into actions and observations, respectively. Then, a generalized predictive state representation for this sequential decision-making problem is a tupleEQUATIONwhere M h :X h → R d h ×d h-1 , ϕ H : X H → R d H-1, and ψ 0 = ψ(∅).An important condition for the learnability of PSR models, which was used in prior work [including 33 -35] , is the so-called "well-conditioning assumption". We state the analogous assumption for our generalized PSR model below. For a core test set Q h , let Q A h = act(Q h ) be the set of core action sequences, let Q A = max h |Q A h | be the number of core action sequences, and let d = max h d h . Assumption 1 (γ-well-conditioned generalized PSR). A generalized PSR model is said to be γ-well conditioned for γ > 0 if, for any h ∈ [H] and any π, it satisfies maxz∈R d h ∥z∥ 1 ≤1 ω h ∈F h π(ω h ) m h (ω h ) ⊤ z ≤ 1 γ , max z∈R d h ∥z∥ 1 ≤1 x h ∈X h ∥M h (x h )z∥ 1 π(x h ) ≤ Q A h+1 γ ,wherem h (ω h ) ⊤ = ϕ H (x H ) ⊤ M H-1 (x H-1 ) • • • M h+1 (x h+1 ) and ∀ ω a h , ω o h π(ω o h , ω a h ) = 1.To understand this condition, recall that m h (ω h ) ⊤ ψ h (τ h ) = P [τ h , ω h ]. Thus, we can interpret z as the error in estimating the prediction features ψ h . This condition ensures that the error in estimating the probability of system trajectories remains controlled when the estimation error of ψ h is small.Although we focus on finite spaces X h in this work, we briefly discuss possible extensions to continuous spaces. In finite settings, the core tests q ∈ Q h are represented by future trajectories q = (x h+1 , ..., x H ) ∈ F h . In continuous spaces, the core tests become trajectories over subsets of the underlying continuous space: q = (X h+1 , . . . , X H ) ⊂ F h , where each X k ⊂ X k is a measureable subset. We point to [33] for more discussion on how to extend (standard) PSRs to continuous spaces.h ∈ [H -1], max z∈R d h ∥z∥ 1 ≤1 x h ∈X h ∥M h (x h )z∥ 1 π(x h ) ≤ Q A h+1 γ ,where π(x h ) = 1 when h / ∈ A and x h π(x h ) = 1 when h ∈ A.To understand this condition, recall thatm h (ω h ) ⊤ ψ h (τ h ) = P [τ h , ω h ].We may think of z in Assumption 1 as representing the error in estimating ψ h (τ h ), the probabilities of core tests at time h given the history τ h . The γ-well-conditioned assumption ensures that the error in estimating the overall PSR (i.e., the probability of a particular trajectory) does not blow up when the estimation error of ψ h (τ h ) is small.The following result states that any sequential decision-making problem of the form described in Section 2.1 admits a generalized PSR representation. The proof and explicit construction are given in Appendix G. Proposition 1. Let (X 1 , . . . , X H ) be any sequential decision-making problem with observation index set O, action index set A, and variable spaces{X h } h∈[H] . Let r h = rank(D h ), where D h , h ∈ [H]are the system dynamics matrices. Then, there exists a PSR representation ψ 0 , ϕ H :X H → R r H-1 , M h : X h → R r h+1 ×r h , h ∈ [H -1], satisfying Definition 3.Proof. The proof is given in Appendix G.H ∈ H H , P [τ H ] = v ⊤ H B H (x H ) • • • B 1 (x 1 )b 0 .Proof. In Proposition 2 we constructed such a representation with dimensions in terms of r h instead of r. Since r h ≤ r, we can pad this representation with dummy columns and/or rows filled with zeros to obtain a representation with dimensions in terms of r.An important part of maximum likelihood analysis is the notion of a "bracketing number" which controls the complexity of the model class Θ [e.g., 94]. In our analysis, the model class is the set of generalized PSRs of a given rank. As shown in the results above, rank-r generalized PSRs can represent any rank-r sequential decision-making problem, with operators whose norm is bounded. In the next result, we will consider a closely related notion to the bracketing number which crucially incorporates optimism. Θ ε is said to be an "optimistic ε-cover" for Θ if for each θ ∈ Θ, there exists θ ∈ Θ ε with an associated probability measureP ε θ such that, ∀h, τ h , P ε θ (τ h ) ≥ P θ [τ h ] , ∀h, τ h , τ h P ε θ (τ h ) -P θ [τ h ] ≤ ε.The first condition ensures optimism and the second condition ensures that Θ ε ε-covers Θ, in the sense that the probability of any trajectory is approximated within an error ε. Recall that the parameter β in Algorithms 1 and 2, which appears in the sample complexity results in Theorems 4 and 5, is defined in terms of |Θ ε |. The next proposition bounds the size of Θ ε .Proposition 3 (Optimistic cover of sequential decision making problems). Let M be the set of all rank-r sequential decision-making problems with a horizon of length H, observation index set O ⊂ [H], action index set A ⊂ [H], and variable spaces X 1 , . . . , X H . Then, there exists an optimistic ε-cover Θ ε of Θ with cardinality bounded by,log Θ ε ≤ O r 2 max h |X h | H 2 log max h |X h | ϵ .Proof. Define the set of generalized PSR representations constructed in Corollary 3,Θ := b 0 ∈ R r , {B h (x h )} h,x h , v H ∈ R r : ∥B h (x h )∥ 2 ≤ 1, ∀h, x h , ∥b 0 ∥ 2 ≤ |H a H |, ∥v H ∥ 2 ≤ 1,and∀ τ H ∈ H H , P m [τ H ] = v ⊤ H B H (x H ) • • • B 1 (x 1 )b 0 ,where m is a sequential decision making problem in M .Let C δ be a δ-cover of the above set with respect to the ℓ ∞ -norm. For θ = (b 0 , {B h (x h )} , v H ) ∈ C δ , define the ε-optimistic probabilities as,P ε θ (τ H ) := v ⊤ H B H (x h ) • • • B 1 (x 1 )b 0 + ε/2We will show that for an appropriate choice of δ, C δ is an optimistic ε-cover. In particular, for each θ ∈ Θ, there exists θ ∈ C δ such that,∀h, τ h , P ε θ (τ h ) ≥ P θ [τ h ] , ∀h, τ h , τ h P ε θ (τ h ) -P θ [τ h ] ≤ ε.To choose the value of δ for which the above holds, observe thatτ H v ⊤ H B H (x H ) • • • B 1 (x 1 ) b 0 -v ⊤ H B H (x H ) • • • B 1 (x 1 )b 0 ≤ H h=1 τ H v ⊤ H B H (x H ) • • • B h+1 (x h+1 )( B h (x h ) -B h (x h ))B h-1 (x h-1 ) • • • B 1 (x 1 )b 0 + τ H v ⊤ H B H (x H ) • • • B 1 (x 1 )( b 0 -b 0 ) ≤ h τ H r B h (x h ) -B h (x h ) max |H a H | + τ H √ r b 0 -b 0 ∞ ≤ H max h |X h | H+|A|/2 rδ + max h |X h | H √ rδ,where the second inequality uses∥ v H ∥ 2 = ∥v H ∥ 2 = ∥B h (x h )∥ 2 = 1, ∥ B h (x h ) -B h (x h )∥ 2 ≤ r∥ B h (x h ) -B h (x h )∥ max ≤ rδ, ∥b 0 ∥ 2 ≤ |H a H |, and ∥ b 0 -b 0 ∥ 2 ≤ √ r∥ b 0 -b 0 ∥ ∞ ≤ √ rδ. Hence, choosing δ := ε • max h |X h |-cH for c an absolute constant large enough achieves a ε-optimisticcovering of Θ. Hence, we let Θ ε = C δ , with δ = ε • max h • |X h | -cH . It remains to bound the size of |Θ ε |. Recall that ∥•∥ ∞ ≤ ∥•∥ 2 and that an interval [-x, x] in R admits a δ-cover of size bounded by 2x/δ. Now, observe that max ij |[B h (x h )] ij | ≤ ∥B h (x h )∥ 2 ≤ 1. Hence, for a fixed h, {B h (x h )} x h admits a cover of size bounded by (2/δ) r 2 |X h | . Considering all h, the cover is bounded by (2/δ) r 2 h |X h | ≤ (2/δ) r 2 max h |X h |H . For, b 0 , we have ∥b 0 ∥ ∞ ≤ ∥b 0 ∥ 2 ≤ |H a H |, hence the covering number is bounded by (2 |H a H |/δ) r . Finally for v H , we have ∥v H ∥ ∞ ≤ ∥v H ∥ 2 ≤ 1,hence the covering number is bounded by (2/δ) r . Thus, we have,log Θ ε ≤ O r 2 max h |X h | H log 1 δ .Recalling that δ = ε max s |X s | -cH , we obtain that,log Θ ε ≤ O r 2 max h |X h | H 2 log max h |X h | ϵ .H Proofs of Section 3.2Theorem (Restatement of Theorem 1). The rank of the observable system dynamics of a POST or POSG is bounded by r ≤ maxh∈[H] I † h .Proof. We have[D h ] τ h ,ω h = P [τ o h , ω o h | do(τ a h , τ a h )] = P [τ o h | do (τ a h )] P [ω o h | τ o h ; do (τ a h , ω a h )] (a) = P [τ o h | do (τ a h )] x k ∈X k k∈I † h P x k , k ∈ I † h τ o h ; do (τ a h , ω a h ) P ω o h x k , k ∈ I † h , τ o h ; do (τ a h , ω a h ) (b) = x k ∈X k k∈I † h P [τ o h | do (τ a h )] P x k , k ∈ I † h τ o h ; do (τ a h ) P ω o h x k , k ∈ I † h , τ o h ; do (τ a h , ω a h ) (c) = x k ∈X k k∈I † h P [τ o h | do (τ a h )] P x k , k ∈ I † h τ o h ; do (τ a h ) P ω o h x k , k ∈ I † h ; do (ω a h ) ,where step (a) is simply the law of total probability, step (b) is that {x k , k ∈ I † h } is conditionally independent of do(ω a h ) (future actions) given (τ o h ; do(τ a h )) (the past), and step (c) is that ω o h is conditionally independent of (τ o h ; do(τ a h )) given {x k , k ∈ I † h }. This is due to a result by Verma and Pearl [95] which states: for three sets of variables A, B, C in a directed graphical model, if A and B are d-separated by C, then A ⊥ B | C. Recall that I † h is defined as the minimal set which d-separates (X t(1) , . . . , X t(h) ) from (X t(h+1) , . . . , X t(H) ).As a technical remark, note that i † h = (x k , k ∈ I † h ) may include actions and hence,P x k , k ∈ I † h τ o h ; do (τ a h ) = P x k , k ∈ I † h ∩ S τ o h ; do (τ a h ) 1 x k , k ∈ I † h ∩ A matches τ a h ,since the action components of i † h are contained in the history τ h . Now define two matricesD h,1 := P [τ o h | do (τ a h )] P x k , k ∈ I † h τ o h ; do (τ a h ) τ h ,i † h , τ h ∈ H h , i † h ≡ x k , k ∈ I † h ∈ I † h , D h,2 := P ω o h x k , k ∈ I † h ; do (ω a h ) i † h ,ω h , i † h ≡ x k , k ∈ I † h ∈ I † h , ω h ∈ F h .We have thatD h = D h,1 D h,2, where both D h,1 and D h,2 have rank upper bounded by|I † h | = s∈I † h |X s |. Hence, rank(D h ) ≤ |I † h |, and the result follows. 
information structure: 
 The "information structure" of a sequential decision-making problem defines the causal dependencies between events in the system occurring at different points time, whether those events are observable by the learning agent or not. In this section, we will introduce a novel reinforcement learning model that explicitly represents information structure. We demonstrate that this enables a rich analysis of the system's dynamics and is crucial for characterizing the statistical complexity of general RL problems.We propose a model of sequential decision-making problems that includes an explicit representation of information structure, which we call partially-observable sequential teams (POST). A POST is a controlled stochastic process consisting of a sequence of variables, where each variable is either a "system variable" or an "action variable". POSTs also model the observability of each system variable with respect to the learning algorithm (i.e., which system variables are available to the learning algorithm). The information structure of a POST describes the causal dependence between these variables. The information set of each system variable describes the subset of past variables that are coupled to it in the dynamics. The information set of an action variable describes the information available to the agent when choosing an action, hence defining the policy class they optimize over. Definition 4 (POST). A partially-observable sequential team is a controlled stochastic process that specifies the joint distribution of T variables (X t ) t∈[T ] , together with a specification of the observability of each variable. Here each X t is either a system variable or an action variable, and is either observable by the learning agent or not. A POST is specified by the following components. ∩ A = ∅, S ∪ A = [T ]. 2. Information Structure. For t ∈ [T ], the "information set" I t ⊂ [t -1] of the variable X t isthe set of past variables that are coupled to X t in the dynamics. That is, the transition to X t depends on the value of I t := (X s : s ∈ I t ). We call I t the "information variable" at time t, and call I t = s∈It X s the "information space". 3. System Kernels. For any t ∈ S, T t ∈ P(X t |I t ) is kernel from I t to X t that specifies the conditional distribution of a system variable X t given the information variable I t . 4. Decision Kernels. Each agent chooses a decision kernel π t : I t → P(X t ), specifying a (potentially randomized) policy for choosing an action at time t ∈ A.Observability. We denote the observable system variables by O ⊂ S. We require that the information sets of the action variables are observable to the learning algorithm: O ⊃ ∪ t∈A (I t ∩ S). We define U := O ∪ A, and let H := |U| be the time-horizon of the observable variables. 6. Reward Function. At the end of an episode, the team receives a reward determined by the function R : s∈U X s → [0, 1].With the above components, any set of decision kernels (i.e., joint policy) π = (π t : t ∈ A) induces a unique probability measure over X 1 × • • • × X T , which is given byEQUATIONWe will be interested in modeling the observable dynamics of the POST. We index the observable variables by their position among the observables h ∈ [H] rather than their position among all variables, as follows: (X t ) t∈U = (X t(1) , . . . , X t(H) ), where t : [H] → U ⊂ [T ] maps the index over observables to the index over all variables. The distribution of the observables is obtained by marginalizing over the unobservable variables,P π x t(1) , . . . , x t(H) = s∈O ∁ xs∈Xs P π [X 1 = x 1 , . . . X T = x T ].The value of a policy is given by its expected rewardV (π) := E π R(X t(1) , . . . , X t(H) ), where E π is the expectation associated with the probability measure P π . The objective of a POST is to learn a policy π = (π t ) t∈A which maximizes the expected reward, sup π V (π). When the variable spaces X t are finite, this supremum is attained by a deterministic policy, π t :I t → X t , t ∈ A.Representation of the information structure as a directed acyclic graph. The information structure of a POST can be naturally represented as a labeled directed acyclic graph (DAG). Given the variable structure and information structure of a POST, (S, A, {I t } t ), its DAG representation is given by G(V, E, L). The nodes of the graph are the set of variables,V = [T ] = S ∪ A. The edges E ⊂ V × V of the DAG are given by E = {(i, t) : t ∈ [T ], i ∈ I t }.That is, there exists an edge from i to t if i is in the information set of t. Finally, L contains labels for each node as being a system variable (in S) or an action variable (in A). Further, the observability of system variables (in O) is also labeled.This DAG represents a directed graphical model for the POST. In particular, the probability distribution onEQUATIONwhere pa(X t ) is the set of parents of X t in G (which are I t ). This representation of the information structure as a DAG will be crucial for our analysis of the dynamics of sequential teams in Section 3.2.Partially observable sequential games. We define partially-observable sequential games (POSGs) in a similar manner. The main difference is that, in the game setting, there exists an expanded reward structure with N different reward objectives R 1 , ..., R N , with different agents pursuing different objectives. The action index set is partitioned intoN subsets A = A 1 ∪ • • • A N, where A i ⊂ A denotes the action index set associated with the agent(s) optimizing for objective R i . The extension to the game setting is treated in detail in Appendix F.POSTs and POSGs form a highly general framework that captures any sequential decision-making problem that can be described by a controlled stochastic process, subsuming classical models such as MDPs, POMDPs, Dec-POMDPs, and POMGs. By introducing a model with an explicit representation of information structure, we gain the ability to perform a richer analysis of sequential decision-making problems. In particular, we will show that the rank of the dynamics, and ultimately the statistical complexity of reinforcement learning, can be characterized as a function of the information structure.We begin by defining the central quantity in our analysis, which we call the "information-structural state", hinting at the role it will play. The information structural state is defined for each point in time as a subset of the past (whether observed or latent) which forms a sufficient statistic for the future. Definition 5 (Information-structural state). Let G † be the DAG obtained from G by removing all edges directed towards actions. That is, it consists of the edgesE † := E \ {(x, a) : x ∈ N , a ∈ A}. For each h ∈ [H], let I † h ⊂ [t(h)]be the minimal set of past variables (observed or unobserved) which d-separates the past observations (X t(1) , . . . , X t(h) ) from the future observations (X t(h+1) , . . . , X t(H) ) in the DAG G † . Define I † h := s∈I † h X s as the joint space of those variables.The following theorem, whose proof is given in Appendix H, states that the rank of the observable system dynamics of POSTs and POSGs is bounded by the cardinality of I † h . Theorem 1. The rank of the observable system dynamics of a POST or POSG is bounded in terms of its information structure by r ≤ max h∈[H] |I † h |.This result shows that the complexity of the observable system dynamics is characterized by the information structure through I † h . In particular, i † h ∈ I † h describes a set of system variables, either observable or latent, which provide a sufficient statistic of the past at time h for predicting future observations-I † h "separates" the past from the future. Hence, the quantity |I † h | admits an interpretation as the size an effective state space at time h. This is a generalization of the standard notion of a latent state. For example, in the case of POMDPs or Dec-POMDPs, the information-structural state indeed coincides with the latent Markovian state (Figure 2a ). We emphasize that I † h may contain observable variables as well as unobservable system variables. In fact, unobservable system variables can introduce crucial structure that simplifies the observable system dynamics.In this section, to provide some intuition, we present examples of information structures and apply Theorem 1 to obtain a bound the rank of their observable system dynamics. We see that classical models such as MDPs, POMDPs, and POMGs are special cases of the POST/POSG framework, and known results about their rank [31] are recovered by the generalized graph-theoretic analysis of their information structure. For notational convenience, we adopt a modified notation in this section where information sets I are indexed by the symbol of the variable rather than its time-index. For example, in an MDP, we write I(s t ) = {s t-1 , a t-1 } for the information set of the state variable s t .Decentralized POMDPs and POMGs. At each time t, the system variables of a decentralized POMDP (or POMG) consists of a latent state s t , observations for each agent o 1 t , . . . , o N t , and actions of each agent a 1 t , . . . , a N t . The latent state transitions are Markovian and depend on the agents' joint action. The observations are sampled via a kernel conditioned on the latent state. Each agent can use their own history of observations to choose an action. Thus, the information structure is given byI(s t ) = s t-1 , a 1 t-1 , . . . , a N t-1 , I(o i t ) = {s t } , I(a i t ) = o i 1:t-1 , a i 1:t-1 .Here, the observable variables are U = {o i 1:T , a i 1:T , i ∈ [N ]}. By Theorem 1, we have I † (o i t ) = I † (a i t ) = {s t }, ∀t, i, as shown in Figure 2a . Thus, the rank of a Dec-POMDP is bounded by |S|, where S is the state space. Note that in the case of models with a true latent state (e.g., POMDPs, Dec-POMDPs, and POMGs), the information-structural state coincides with the Markovian latent state.Point-to-Point Real-Time Communication with Feedback. Consider the following model of realtime communication with feedback. Let x t be a Markov source. At time t, the encoder receives the source x t ∈ X and sends an encoded symbol z t ∈ Z. The symbol is sent through a memoryless noisy channel which outputs y t to the receiver. The decoder produces the estimate x t . The output of the noisy channel is also fed back to the encoder. The encoder and decoder have full memory of their observations and previous "actions". The observation variables are O = {x 1:T , y 1:T } and the "actions" are A = {z 1:T , x 1:T }. Hence, the information structure is given by the following,I(x t ) = {x t-1 } , I(z t ) = {x 1:t , y 1:t-1 , z 1:t-1 } , I(y t ) = {z t } , I( x t ) = {y 1:t } .By Theorem 1, we have that,I † (x t ) = {x t } , I † (z t ) = {x t } , I † (y t ) = {x t , z t } , I † ( x t ) = {x t } .Hence, the rank is bounded by |X||Z|. This is depicted in Figure 2c .Limited-memory information structures. Consider a sequential decision making problem with variables o t , a t , t ∈ [T ] and an information structure with length-m "memory". That is, observations do not directly depend on variables more than m steps in the past. That is, the information structure isI(o t ) = {o t-m:t-1 , a t-m:t-1 } , I(a t ) = {o 1:t , a 1:t-1 } .The observables consist of all observations and actions, U = {o 1:T , a 1:T }. By Theorem 1 we have that I † (o t ) = {o t-m:t-1 , a t-m:t-1 }, as shown in Figure 2d . Hence, the rank of this sequential decision-making problem is bounded by |O| m |A| m . The examples above show that the complexity of the dynamics of a sequential decision-making problem depends directly on its information structure. An expanded version of this discussion is provided in Appendix D. Next, we use an information-structural analysis to construct a generalized PSR representation for a class of POSTs/POSGs, which we will ultimately use to prove an upper bound on the statistical complexity of reinforcement learning as a function of information structure. 
constructing a psr parameterization for posts and posgs: 
 A key challenge in reinforcement learning is constructing representations which enable robustly and efficiently modeling probabilities of system trajectories (i.e., probabilities of the form P [future | history]). In this section, we will construct a generalized predictive state representation for a class of POSTs/POSGs, ultimately enabling sample-efficient reinforcement learning.Recall that a core test set is a set of futures such that the probabilities of those futures given the past encode all the information that the past contains about the future. For systems with a simple and regular information structure, a core test set may be simple to obtain. For example, undercomplete POMDPs with a full-rank emission matrix admit the 1-step observation futures as core test sets.Observables Unobservables ℎ 𝐺 ℎ ∈ ℝ ℚ ℎ 𝑚 ×𝕀 ℎ † 𝑞 ℎ ∈ ℚ ℎ 𝑚 𝑚-step future 𝑖 ℎ † ∈ 𝕀 ℎ † ഥ ℙ 𝑞 ℎ 𝑖 ℎ † ) Information-structural state 𝑀 ℎ 𝑥 𝑡 ℎ : = 𝐺 ℎ † ⊤ ഥ ℙ 𝑥 𝑡(ℎ) , 𝑞 ℎ+1 1 𝑖 ℎ † 𝑖 ℎ † ∈𝕀 ℎ † ⋮ 𝐺 ℎ † ⊤ ഥ ℙ 𝑥 𝑡(ℎ) , 𝑞 ℎ+1 𝑑 ℎ+1 𝑖 ℎ † 𝑖 ℎ † ∈𝕀 ℎ †For POSTs/POSGs with arbitrary information structures, obtaining a core test set is much more challenging without knowing the system dynamics. In this section, we identify a condition in terms of the information structure under which m-step futures are a core test set for POSTs/POSGs. Let us denote the candidate core test set of m-step futures at time h by Q m h := s∈U h+1:min(h+m,H) X s . We define the matrix G h as encoding the probability of observing each m-step future conditioned on the information-structural state i † h ∈ I † h :EQUATIONThe operational meaning of G h is depicted in Figure 3 . Next, we formulate a condition in terms of information structure that we will show implies that the m-step futures are core test sets. Definition 6 (m-step I † -weakly revealing). We say that a sequential team is m-step I † -weakly revealing if for all h ∈ [H], rank(G h ) = |I † h |. Furthermore, we say that the sequential team is αrobustly m-stepI † -weakly revealing if for all h ∈ [H -m + 1], σ |I † h | (G h ) ≥ α.The I † -weakly revealing condition is essentially a statistical identifiability condition. If a POST/POSG is I † -weakly revealing, then, for any two mixtures of the information-structural state, the distributions of the m-step futures are distinct. Formally, for any ν 1 , ν 2 ∈ P(I † h ) with supp(ν 1 ) ∩ supp(ν 2 ) = ∅, we have G h ν 1 ̸ = G h ν 2 .That is, the future observations contain information that can distinguish between mixtures of the latent information-structural state. The α-robust version of the I † -weakly revealing condition requires that G h is not only full rank, but that its |I † h |-th singular value is bounded away from zero, so that∥G h ν 1 -G h ν 2 ∥ ≥ α∥ν 1 -ν 2 ∥.The condition holds whenever there exists a sequence of actions within the m-step futures such that executing these actions results in a sequence of observations that is informative about the informationstructural state i † h ∈ I † h . In general, this condition will be harder to satisfy when I † h is large since it would require the m-step future observations to encode more information. In particular, G h cannot be full rank when|Q m h | < |I † h |.As a heuristic, when we don't have prior knowledge about the dynamics (e.g., in the learning setting), we can choose m such that|Q m h | ≥ |I † h |.In general, it will be possible to find a smaller core test set when the d-separating set I † h is small. This happens when the system dynamics contain state-like variables that are low-dimensional.The I † -weakly-revealing condition is a generalization of the "weakly-revealing" condition for POMDPs introduced by Liu et al. [36] . Liu et al. [37] proposed an algorithm for learning weaklyrevealing POMGs. Our analysis here recovers weakly-revealing POMGs as a special case and enables learning a much more general class of problems. We note that 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 [36] .We now proceed to show that under the I † -weakly-revealing condition, m-step futures are core test sets for POSTs/POSGs which can be used to construct a generalized PSR representation amenable to learning. Recall that the vector of core test set probabilities for the history τ h is given by the mappings ψ h , ψ h :H h → R |Q m h | , ψ h (τ h ) = [P [q o , τ o h | do(τ a h ), do(q a )]] q∈Q m h , ψ h (τ h ) = [P [q o | τ o h ; do(τ a h ), do(q a )]] q∈Q m h .Define the mapping m h :EQUATIONThe following lemma, whose proof is given in Appendix I, shows that the m-step futures Q m h are core test sets for any m-step I † -weakly revealing POST/POSG. In particular, given any future ω h ∈ F h and history τ h ∈ H h , the conditional probability P [ω h | τ h ] can be written as a linear combination of the core test probabilities ψ h (τ h ), with weights given by m h (ω h ), depending only on the future ω h .Lemma 1 (Core test set for POSTs). Suppose that the POST is m-step I † -weakly revealing. Then,Q m h is a core test set for all h ∈ [H]. Furthermore, we have P [τ h , ω h ] = ⟨m h (ω h ), ψ h (τ h )⟩ and P [ω h | τ h ] = m h (ω h ), ψ h (τ h ) .Consider a POST/POSG which is m-step I † -weakly revealing. Lemma 1 shows that the m-step futures Q m h are core test sets. In this section, we will explicitly construct a generalized PSR parameterization for this class of sequential decision-making problems. Moreover, we will show that this generalized PSR representation is well-conditioned when the weakly revealing condition is robust.Let d h := |Q m h |.The key observation that allows us to construct the generalized PSR representation is that the vector mappings m h : F h → R d h and ψ h : H h → R d h can be used to derive a recursive form of the dynamics of the POST/POSG. We define the operator mapping M h :EQUATIONThat is, M h (x t(h) ) is the matrix whose rows are indexed by the core tests at the h-th observable step, where the row corresponding to each q ∈ Q h is the weights returned by the mapping m h-1 when applied to the future consisting of x t(h) followed by core test q. The operator map M h allows us to update the probabilities of the core test sets after receiving an additional observation x t(h) : ψ h (x t(1) , ..., x t(h) ) = M h (x t(h) )ψ h-1 (x t(= α/ max h |I † h | 1/2 .Thus, we have constructed a robust parameterization of the sequential decision-making problem, making use of its information structure, that will enable us to design an efficient learning algorithm.1|X h | 1{h∈A} v ⊤ h x h ∈X h B h (x h ) = v ⊤ h-1 . 
characterizing the statistical complexity of general reinforcement problems via information structure: 
 In this section, we establish an upper bound on the achievable sample complexity of general reinforcement learning problems in terms of their information structure. In plain language, this is a result that roughly says "any sequential decision-making problem with an information structure I can be learned with a sample complexity at most f (I)". This identifies a class of sequential decision-making problems that are statistically tractable via conditions on the information structure, expanding the set of known-tractable problems while recovering existing tractability results as a special case.We will prove this result by exhibiting an algorithm that achieves this upper bound. Our approach will be to use the generalized predictive state representation constructed for POSTs/POSGs in Section 4, which provides a robust representation amenable to learning. We will introduce an algorithm for learning generalized PSRs and prove a corresponding sample complexity result, which will in turn imply a bound on the sample complexity of learning POST/POSG models via the informationstructural characterization of the rank of observable dynamics established in Section 3.2.There exist several works in the literature which study learning in PSRs [e.g. 33-35, 38, 39] . Using the technical tools developed in this paper, most of these algorithms can be directly extended to our generalization of PSRs. With such an algorithm, Theorems 1 and 2 then imply a bound on the achievable sample complexity for learning general sequential decision-making problems in terms of their information structure. In this work, we will adapt the model-based UCB-type algorithm of Huang et al. [35] , extending it to generalized PSRs to obtain a bound on the achievable sample complexity for POSTs/POSGs. We will defer the details of the algorithm to Appendix E and formally verify the proof in Appendix J. Here, we will focus on discussing the role of information structure in determining the statistical complexity of reinforcement learning.The following result states that the size of the information-structural state, |I † h |, characterizes an upper bound on the statistical complexity of learning a sequential decision-making problem. Theorem 3. Suppose a sequential decision-making problem described by a POST is α-robustly mstep I † -weakly revealing. Let Q m := max h |Q m h | be the size of the m-step observable trajectories, and let A = max s∈A |X s | be the size of largest action space. Then, there exists an algorithm that can learn an ϵ-optimal policy with a sample complexity (omitting log factors) bounded by1 ϵ 2 × poly 1 α , max h I † h , Q m , A, H .Under the game setting, the same assumption implies the existence of a self-play algorithm that learns an ϵ (Nash or coarse-correlated) equilibrium with the same sample complexity.This result identifies I † -weakly revealing POSTs/POSGs as a class of statistically tractable sequential decision-making problems. The sample complexity is polynomial in the size of the informationstructural state space max h |I † h |, the size of the action space A, and the time horizon H. Further, it depends on Q m , the size of m-step observable trajectories, and the robustness parameter α -1 , which corresponds to the m-step I † -weakly revealing identifiability condition. We note that the algorithm constructed to prove Theorem 3 only needs to know the parameters of the I † -weakly revealing condition (i.e., m and α), and does not need to know the full information structure.This result shows that the size of the information-structural state is a fundamental measure of the statistical complexity of reinforcement learning. As a result, learning is tractable when max h |I † h | is of modest size, and the information structural state is strongly coupled to the observable system variables.One notable special case of POSTs/POSGs is POMDPs. Learning in POMDPs has been studied extensively in the literature. Theorem 3 implies a poly(S, O, A, H, α -1 ) • ϵ -2 bound on the sample complexity of learning in α-weakly POMDPs and poly(S, (OA) m , H, α -1 ) • ϵ -2 for learning mstep weakly revealing POMDPs. This recovers a similar sample complexity as was shown by more specialized analysis tailored to POMDPs [e.g., 36, 40] .τ h ∈ H h , P [τ h ] = v ⊤ h B h (x h ) • • • B 1 (x 1 )b 0 .Proof. We construct the representation via the singular value decomposition of the matrixD ⊤ h . Let U h ∈ R |F h |×r h , Σ h ∈ R r h ×r h , V ⊤ h ∈ R r h ×|H h | be the SVD such that D ⊤ h = U h Σ h V ⊤ h . Define b 0 , B h , v ⊤ h as follows, b 0 = ∥D 0 ∥ 2 , B h (x h ) = U ⊤ h [U h-1 ] (x h ,F h ),: , v ⊤ h = 1 |F a h | 1 ⊤ U h .Here,[U h-1 ] (x h ,Ω h ),: denotes an |F h | by r h-1 submatrix of U h-1 consisting of the rows (x h , ω h ), ω h ∈ F h (i.e., the set of futures where the variable at time h is x h ). Note that |F a H | = 1 by convention, a product over an empty set. We verify each property in turn.First, ∥B h (x h )∥ 2 = ∥U ⊤ h [U h-1 ] (x h ,F h ),: ∥ 2 ≤ 1 since U h , U h-1 are unitary matrices. Second, |b 0 | = ∥D 0 ∥ 2 = τ H P [τ H ] 2 ≤ τ H P [τ H ] = τ a H τ o H P [τ o H | τ a H ] = τ a H 1 = s∈A |X s |,where the inequality is since P [τ H ] ∈ [0, 1]. For property 3, we have∥v h ∥ 2 = 1 |F a h | 1 ⊤ U h 2 ≤ 1 |F a h | ∥1∥ 2 = |F h | |F a h | = |F o h | / |F a h |,where the inequality is since U h is unitary, and the final equality is since|F h | = |F o h | |F a h |.Next, to prove properties 4 and 5, we first show the following claim. 
conclusion: 
 Summary. This paper examines the role of information structure in general reinforcement learning problems. We introduced novel models that explicitly represent information structure, and proved an upper bound on the sample complexity of general reinforcement learning problems in terms of information structure. The central quantity in this upper bound is derived from a graphical representation of the information structure, and admits an interpretation as an effective informationstructural state, generalizing the typical notion of a Markovian state.Limitations. The results of this paper are theoretical in nature, and the algorithm proposed to prove our main result is not computationally practical. Current SOTA algorithms for partially-observable algorithms are based on recurrent neural networks or other deep learning models, which create internal representations of latent states based on the history, akin to belief states. Our theory may offer insights into the design of improved architectures in such deep learning-based algorithms. For example, the information structure can be incorporated as an inductive bias of the neural network.  
 
 Appendix: The space of histories at time h.H h := h s=1 X s . F hThe space of futures at time h.F h := H s=h+1 X s . obs(•)The observation component of a trajectory. obs(x i , . . . , x j ) := (x s : s ∈ O i:j ).The action component of a trajectory. act(x i , . . . , x j ) := (x s : s ∈ A i:j ).The space of observation (resp., action) histories. E.g.,H o h := s∈O 1:h X s = obs(H h ). F {o,a} hThe space of observation (resp., action) histories. E.g.,F o h := s∈O h+1:H X s = obs(F h ). P [τ h ]The probability of a trajectory given actions are executed.P [τ h ] := P [obs(τ h ) | do(act(τ h ))]. D h Dynamics matrix at time h. D h ∈ R |H h |×|F h | , [D h ] τ h ,ω h := P [τ h , ω h ]. r h := rank(D h ). π(τ h ) For τ h = (x 1 , . . . , x h ) and policy π, π(τ h ) := s∈A 1:h π(x s | x 1 , . . . , x s-1 ). π(ω h | τ h ) For τ h = (x 1 , . . . , x h ), ω h = (x h+1 , . . . , x h ′ ), π(ω h | τ h ) = s∈A h+1:h ′ π(x s | x 1 , . . . , x s-1 ).Space that the variable X t lies in within the stochastic process (X 1 , . . . , X T ).denotes the set of system variables among the variables (X 1 , . . . , X T ). AA ⊂ [T ] denotes the set of action variables among the variables (X 1 , . . . , X T ). O O ⊂ S denotes the subset of system variables which are observable.The union of observable system variables and action variables.U := O ∪ A. Let H := |U|. t(h)For h ∈ [H] indexing the order among observables, t(h) ∈ U denotes the order among all variables.The information set of the t-th variable. I t I t := s∈It X s denotes the information space at time t.I † hThe minimal d-separating set at the h-th observable. See Definition 5.I † h I † h := s∈I † h X s denotes the "information-structural state". Generalized PSRs Q h Core test set at time h. Let d h := |Q h | and d = max h d h . Q A h Action component of core test set at time h. Q A h = act(Q h ). Q A Maximum size of the action component of core test sets. Q A := max h |Q A h |. M h Observable operators of PSR representation mapping M h : X h → R d h ×d h-1 . ψ h Prediction features. ψ h (τ h ) := P [τ h , q] q∈Q h . In PSR, ψ h (x 1 , . . . , x h ) = M h (x h ) • • • M 1 (x 1 )ψ 0 . m h Prediction coefficients. m h (ω h ) ⊤ := ϕ H (x H ) ⊤ M H-1 (x H-1 ) • • • M h+1 (x h+1 ). ψ h Normalized prediction features. ψ h (τ h ) := ψ h (τ h )/P [τ h ] = P [q | τ h ] q∈Q h . General Mathematical Notation D TV (p, q) Total variation distance. D TV (p, q) := x∈X |p(x) -q(x)|. D 2 H (p, q) Hellinger squared distance. D 2 H (p, q) := 1 2 x∈X ( p(x) -q(x)) 2 . σ k (A)k-th largest singular value of the matrix A.The matrix p-norm. ∥A∥ p := max ∥x∥ p =1 ∥Ax∥ p . ∥x∥ AThe vector norm induced by the positive semi-definite matrix A.∥x∥ A := √ x ⊤ Ax. A †Moore-Penrose pseudoinverse.Space of probability distributions over A. P(B|A) is the space of kernels from A to B. N i:jFor an index set N ⊂ [H], N i:j = N ∩ {i, . . . , j}.The study of information structure in the control literature. In stochastic control, the construct of the "information structure" is used to model the structural properties of a system which may restrict the flow, storage, and processing of information. The role of information structure in decentralized control has been extensively studied since Witsenhausen [15] and Ho and Chu [3] began investigating information structures in the context of team decision theory. For example, early work showed that the information structure can determine the tractability of optimal decentralized control problems [15, 41] . More generally, information structure plays an important role in the analysis of multi-agent team decision problems and games, as well as in the design of efficient algorithms, especially in the decentralized setting. See, e.g., Mahajan et al. [11] , Nayyar et al. [42] [43] [44] , Ouyang et al. [45] , Dave et al. [46] , and Guan et al. [47] and the references therein. We also refer the reader to Yuksel and Basar [48] for a comprehensive overview of the interaction between information and control, including recent progress in the field. The models we propose in this paper are closely related to Witsenhausen's intrinsic model [1] , but with some added elements to model partial-observability in the context of reinforcement learning. Related to this is the framework of multi-agent influence diagrams [e.g., 49, 50] which allow for an explicit representation of dependence relations among variables in games.Whereas the above-mentioned work studies the role of information structure in planning and control, we study the the role of information structure in reinforcement learning (i.e., statistical estimation and sample complexity). We note that specific types of structural assumptions related to information structure have been studied in the learning setting as well. For example, previous work has studied factored MDPs [51] , which assume an information structure where the state transitions and the reward function are factored, enabling improved learning results. In the present work, we study the role of information structure in reinforcement learning in greater generality, focusing particularly on the partially-observable setting.Learning under partial observations. In an MDP, where the system dynamics obey a Markovian property and are fully observable, reinforcement learning has been shown to be both computationally and statistically efficient [e.g., [52] [53] [54] [55] . However, under partial observability, reinforcement learning can be computationally and statistically intractable in the worst case, even when assuming a Markovian latent state. Such worst-case hardness results are well-known. For example, [41, 56, 57] show that planning is computational intractable and [58, 59] show that learning is statistically intractable, in the worst-case. In these worst cases, the hardness comes from instances where the observations reveal little information about the latent state, which causes errors in learned representations to be uncontrollable. Accordingly, sub-classes of POMDPs have been identified in recent work where added structural conditions make efficient learning possible. One such condition is decodability [see e.g., 59 -62], which assumes that the latent state can be decoded from the current observation (i.e., Block MDP), or an m-step history of observations. Another set of conditions is the "observability" condition [63] [64] [65] and its cousin the "weakly revealing" condition [36, 40] which require different belief states to induce distinguishable distributions over observations. These conditions are further extended to POMDP models in the function approximation setting, where the state or observation spaces are large and function approximators (e.g., linear functions) are used to represent the model. See, e.g., Uehara et al. [34] , Guo et al. [61] , Zhang et al. [62] , Cai et al. [66] , and Wang et al. [67] . In our work, we build on the above by identifying a class of POSTs/POSGs which can be learned efficiently. This is significant since POSTs/POSGs are much more general than POMDPs and do not assume the existence of a latent state.Predictive state representations. Predictive state representations were introduced by Littman and Sutton [31] building on prior work on observable operator models by Jaeger [32] which proposed the idea of predictive representations as an alternative to belief states for modeling HMMs and POMDPs [see also [68] [69] [70] [71] . PSRs are a way to represent the dynamics of a sequential decision-making problem by modeling the (conditional) probabilities of a small set of future trajectories, typically called "core tests". In a PSR, the probability of any future trajectory is a deterministic function of the conditional probabilities of the core tests. That is, the probabilities of the core tests encode all the information that the past contains about the future. Littman and Sutton [31] showed that any POMDP can be represented as a PSR. Various reinforcement learning methods for PSRs have been proposed under the assumption that data distribution is explorative, including spectral algorithms [72] [73] [74] and supervised learning approaches [75] . In addition, when it comes to the online setting where the algorithm needs to explore, there is a line of work that extends the theory and algorithms for online POMDP learning to PSRs. Moreover, some of these works propose generic theory and algorithms that can be applied to a large class of models including MDPs, POMDPs, and two-player zero-sum dynamic games with partial observability. See, e.g., Liu et al. [33] , Huang et al. [35] , Liu et al. [36] ,Chen et al. [38] , Zhan et al. [39] , Zhong et al. [76] , Qiu et al. [77] , and Liu et al. [78] . Our work is particularly related to the works that combine the idea of optimism in the face of uncertainty [79] and maximum likelihood model estimation [33, 35, 36, 38, 39] . Specifically, our algorithm extends the UCB-type algorithm proposed by Huang et al. [35] for standard PSRs to learn a generalization of PSRs which captures POSTs/POSGs.Learning in multi-agent systems. Most applications of interest in reinforcement learning involve the participation of multiple agents in the same environment. Empirical research has achieved striking success in several domains, including for example in the games of Go [26] , Starcraft [28] ,and Poker [80] , as well as in robotic control [24] and autonomous driving [27] . There also exists a growing literature of theoretical work. For example, Brafman and Tennenholtz [81] , Bai et al. [82] , and Song et al. [83] tackle learning in Markov games (MGs)-a generalization of single-agent MDPs that assumes the existence of a Markovian state which is observable by all agents. Another model which has been explored in the literature is imperfect-information extensive-form games (IIEFG), which assumes tree-structured transitions and deterministic emission, and can be viewed as a subclass of partially-observable Markov games (POMGs). Learning under this model has been studied in Zinkevich et al. [84] , Kozuno et al. [85] , and Farina and Sandholm [86] . More recently, Liu et al. [37] studied reinforcement learning in POMGs using an MLE-based algorithm building on their previous work in the single-agent setting [36] . To address the computational intractability of the planning step for such model-based algorithms, Liu and Zhang [87] proposed a quasi-efficient algorithm for multi-agent POMGs that runs in quasi-polynomial time with quasi-polynomial sample complexity. Their proposed algorithm leverages the common information approach [see 12] to construct an approximate Markov game where the state space of this new game corresponds to the space of approximate common information among agents. The idea of leveraging an informationsharing structure in multi-agent reinforcement learning has also appeared in Subramanian et al. [88] , Mao et al. [89] , Kara and Yuksel [90] , Kao and Subramanian [91] , and Tang et al. [92] .In each of the above-mentioned models (e.g., MDP, POMDP, MG, IIEFG, POMG, etc.), a particular fixed information structure is assumed. We emphasize that the POST/POSG model proposed in our work allows the information structure to be specified arbitrarily and hence captures these models as special cases within a unifying framework. Moreover, our analysis and proposed algorithm significantly expand the class of multi-agent sequential decision-making problems that can be efficiently learned.Consider a controlled stochastic process (X 1 , . . . , X H ), where X h is a random variable corresponding to the variable at time h. At each time h ∈ [H], the variable X h may be either an 'observation' (i.e., observable system variable) or an 'action'. The dynamics of this stochastic process are described by a tuple (H, {X h } h , O, A, P), where H is the time horizon, X h is the variable space at time h (i.e.,X h ∈ X h ), O ⊂ [H] is the index set of observations (i.e., X h is an observation if h ∈ O), A ⊂ [H]is the index set of actions, and P = {P h } h∈O is a set of probability kernels which describes the the probability of any trajectory x 1 , . . . , x H given that the actions are executed,EQUATIONA choice of policy π = {π h } h∈A induces a probability distribution onEQUATIONWe now define some notation. Let H h = s∈1:h X s denote the space of histories at time h and F h = s∈h+1:H X s denote the space futures at time h. Similarly, let H o h = obs(H h ) = s∈O 1:h X s denote the observation component of histories and let H a h = act(H h ) = s∈A 1:h X s denote the action component. Here, O i:j denotes O ∩ {i, . . . , j}, and similarly for A i:j . The observation and action components of the futures, F o h and F a h respectively, are defined similarly.We define the system dynamics matrix D h ∈ R |H h |×|F h | as the matrix giving the probability of each possible pair of history and future at time h given the execution of the actions,EQUATIONwhere ω o h = obs(ω h ) are is the observation component of the future ω h , ω a h = act(ω h ) is the action component, and similarly for τ o h , τ a h . Note that the actions are actively executed via the do-operation. Hence, the system dynamics matrices are independent of any action-selection criteria. Note thatD H ∈ R |H H |×1 is defined as [D H ] τ H = P [τ H ], and D 0 = D ⊤H . We introduce the notion of the rank of the dynamics. The rank of such a controlled stochastic process is the maximal rank of its dynamics matrices. This is a measure of the complexity of the dynamics. Definition (Rank of dynamics; Definition 1). The rank of the dynamics{D h } h∈[H] is r = max h∈[H] rank(D h ).This defines the dynamics of the system. A sequential decision-making problem is such a controlled stochastic process together with an objective. The objective is defined by a reward function R :X 1 × • • • × X H → [0, 1] mapping a trajectory to a reward in [0, 1]. The agent(s) can affect the dynamics of the system through their choice of actions or policies. Each action X h , h ∈ A may be chosen by either a single agent or one of several agents (e.g., a team). The policy at time h ∈ A is a mapping π h : H h-1 → P(X h ) from previous observations to an action (or a distribution over actions, if randomized). The collection of policies at all time steps is denoted π = (π h : h ∈ A), and induces a probability distribution over trajectories, denoted P π . Then, the value of a policy π is the expected value of the reward under the measureP π , V R (π) := E π [R(X 1 , . . . , X H )], where E π is the expectation associated with P π .The formalism of sequential decision-making problems introduced in this section is highly generic, but does not explicitly model the information structure. In the next section, we introduce the models of partially observable sequential teams/games, which explicitly represent information structures. We then show that the information structure characterizes the rank of a sequential decision-making problem as per Definition 1.Predictive state representations (PSR) [31, 32] are a model of dynamical systems and sequential decision-making problems based on predicting future observations given the past, without explicitly modeling a latent state. In this section, we propose and formalize a generalization of standard PSRs.In the standard formulation of sequential decision-making and predictive state representations, the sequence of variables is such that observations and actions always occur in an alternating manner (i.e., o h , a h , o h+1 , a h+1 , . . .). The POST/POSG models we will propose are more general, and hence require a more flexible formalization of PSRs which allows for arbitrary order of observations and actions as well as arbitrary variable spaces at each time point. This generalization of PSRs will be used in our reinforcement learning algorithms.The "PSR rank" of a sequential decision-making problem coincides with the rank of its dynamics, as defined in Definition 1. Recall that the system dynamics matrixD h ∈ R |H h |×|F h | isindexed by all possible observable histories τ h and futures ω h . Denote the rank of the system dynamics at time h by r h := rank(D h ).Consider a sequential decision-making problem as defined in Section 2.1 (i.e., with an arbitrary order of observations and actions, and arbitrary variable spaces). At the heart of predictive state representations is the concept of "core test sets." A core test set at time h is a set of futures such that the set of probabilities of those futures conditioned on the past encodes all the information that the past contains about the future. This is formalized in the definition below as a set of futures such that the submatrix of the full dynamics matrix restricted to those futures is full rank. Definition (Core test sets). A core test set at time h is a subset ofd h ≥ r h futures, Q h := q 1 h , . . . , q d h h ⊂ F h , such that the submatrix D h [Q h ] ∈ R |H h |×d h is full-rank, rank(D h [Q h ]) = rank(D h ) = r h .A core test set implies the existence of a matrixEQUATIONThe vector ψ h (τ h ) is a sufficient statistic for the history τ h in predicting the probabilities of all futures conditioned on τ h . This is sometimes called the prediction features of a history τ h .For any integer d h ≥ r h , there exists a core test set of size d h . In particular, for any low-rank sequential decision-making problem, there exists a minimal core test set of size r h at each h. However, the minimal core test set depends on the system dynamics matrix D h , which is unknown in the learning setting. In the literature on reinforcement learning in PSRs, it is typically assumed that a core test set is known. We address the problem of constructing a PSR representation for POSTs/POSGs in Section 4.For a core test setQ h , let Q A h = {act(q) : q ∈ Q h }, where act(q) denotes the action components of the test q ∈ Q h . Let Q A = max h Q A h and d = max h d h .With core test sets defined, we are now ready to present the definition of a generalized predictive state representation. The essential element in a PSR is a set of operators M h :X h → R d h ×d h-1 for each time point h ∈ [H]. Given the prediction features at time h -1, ψ h-1 (x 1 , . . . , x h-1 ) ∈ R d h-1 , the linear map M h (x h ) computes the prediction features at time h, incorporating the additional observation x h . That is, ψ h (x 1 , . . . , x h ) = M h (x h )ψ h-1 (x 1 , . . . , x h-1 ). The full definition is given below. Definition (Generalized Predictive State Representations; Definition 3). Consider a sequential decision-making problem (X h ∈ X h ) where A, O partition [H] into actions and observations, respectively. Then, a predictive state representation of this sequential decision-making problem is a tuple θ = ({Q h } 0≤h≤H-1 , ϕ H , M , ψ 0 ) given by 1. {Q h } 0≤h≤H-1 are core test sets, including for h = 0, where Q 0 = {q 1 0 , . . . , q d0 0 } ⊂ F 0 are core tests before the system begins.2. ψ 0 ∈ R d0 is the vector ψ(∅) = (P[q 1 0 ], . . . , P[q d0 0 ]). 3. M = {M h } 1≤h≤H-1 is a set of mappings M h : X h → R d h ×d h-1, from an observation/action to a matrix of sized h × d h-1 . 4. ϕ H : X H → R d H-1is a mapping from the final observation to a d H-1 -dimensional vector.This tuple satisfies,EQUATIONTo obtain a probability for a trajectory τ h = (x 1 , . . . , x h ), with h < H, note thatω h ∈F h P [τ h , ω h ] = |F a h | P [τ h ]. Hence P [τ h ] = 1 |F a h | ω h P [τ h , ω h ] = 1 s∈h+1:H |X s | 1{s∈A} x H • • • x h+1 ϕ ⊤ H M H (x H ) • • • M h+1 (x h+1 )ψ h (τ h ).Thus, if we recursively define ϕ h , h < H via 1EQUATIONwith ϕ H as the terminating condition, then, we can obtain P [τ h ] for any h < H, via an inner product between ϕ h and ψ h (τ h ),P [τ h ] = ϕ ⊤ h ψ h (τ h ). (15) Finally, if we define ψ h (τ h ) = ψ h (τ h )/P[τ h ],then we obtain the conditional probability of the core tests given the history,ψ h (τ h ) = (P[q 1 h | τ h ], . . . , P[q d h h | τ h ]) ∈ R d h . ψ h (τ h) is known as the (normalized) prediction feature of the history τ h [31] .Remark 1 (Generality and difference from standard PSRs). In standard PSRs, observations and actions are assumed to occur in an alternating manner, and hence observable operators are defined on pairs of observations and actions (i.e., M h (o h , a h )). This structure leads to a somewhat simpler description compared to the above. However, our formulation is more general, as it allows each variable to be treated independently, and allows for an arbitrary sequence of variables with arbitrary spaces. This generality will be needed when modeling problems with an explicit representation of information structure.An important condition for the learnability of PSR models, which was used in prior work [including 33, 35] , is the so-called "well-conditioning assumption". We state the analogous assumption for our generalized PSR model below. Assumption (γ-well-conditioned generalized PSR; Assumption 1).EQUATION)wherem h (ω h ) ⊤ = ϕ H (x H ) ⊤ M H-1 (x H-1 ) • • • M h+1 (x h+1 ) with ω h = (x h+1 , . . . , x H ) ∈ F h .The maximization is over policies π such that for any fixed future observationsω o h , ω a h π(ω o h , ω a h ) = 1.The analysis in Section 3 and Theorem 1 characterizes the rank of any sequential decision-making problem as a function of its information structure. In this section, we illustrate this on several sequential decision-making problems, characterizing the information-structural complexity of their dynamics. The procedure is as follows: 1) formulate the sequential decision-making problem as a POST/POSG; 2) represent the information structure as a labeled directed acyclic graph G; 3) remove incoming edges into the action variables to produce G † ; 4) apply Theorem 1 to find the information structural state at each point in time through a d-separation analysis.Illustration: translating to the POST/POSG framework. We begin by illustrating how an arbitrary sequential decision-making problem can be formulated in the POST/POSG framework. Consider s 1 ↓ x 1 o 1 ↓ x 2 a 1 ↓ x 3 s 2 ↓ x 4 o 2 ↓ x 5 a 2 ↓ x 6 • • • s t ↓ x 3t-2 o t ↓ x 3t-1 a t ↓ x 3t • • •Here, the system variables S are the s-type and o-type variables, with system index set S = {1, 2, 4, 5, 7, 8, ...}, and the action variables are the a-type variables with action index set A = {3, 6, 9, ...}. The observable system variables are the o-type variables only, with index set O = {2, 5, 8, ...} ⊂ S. This can be done for any sequential decision-making problem.To ease notation, let us not explicitly write the indices in this section, but rather use the original notation for the variables in the problem formulation. For example, we'll write S = {s t , o t , t ∈ [T ]}. Similarly, we use the notation I(x) to mean the information set corresponding to the variable x. Similarly, I † (x) denotes the information-structural state at the time when x occurs. For example, in a POMDP I(s t ) = {s t-1 , a t-1 }, I(o t ) = {s t }, and I(a t ) = {o 1:t , a 1:t }.Below, we will consider several examples of sequential decision-making problems, and apply the information-structural analysis of Theorem 1 to obtain a bound on the rank of the observable dynamics (which in turn implies a bound on the sample complexity, by Theorem 3).Decentralized POMDPs and POMGs. At each time t, the system variables of a decentralized POMDP (or POMG) consist of a latent state s t , observations for each agent o 1 t , . . . , o N t , and actions of each agent a 1 t , . . . , a N t . The latent state transitions are Markovian and depend on the agents' joint action. The observations are sampled via a kernel conditional on the latent state. Each agent can use their own history of observations to choose an action. Thus, the information structure is given by,I(s t ) = s t-1 , a 1 t-1 , . . . , a N t-1 , I(o i t ) = {s t } , I(a i t ) = o i 1:t-1 , a i 1:t-1 .Here, the observable variables areU = o i 1:T , a i 1:T , i ∈ [N ]. By Theorem 1, we have I † (o i t ) = {s t } , ∀t, i, as shown in Figure 5a . Thus, the rank of a Dec-POMDP is bounded by |S|, where S is the state space. Note that in the case of models with a true latent state (e.g., POMDPs, Dec-POMDPs, and POMGs), the information-structural state coincides with the true latent state.Limited-memory information structures. Consider a sequential decision making problem with variables o t , a t , t ∈ [T ] and an information structure with m-length memory. That is, observations can only depend directly on at most m of the most recent observations and actions. That is, the information structure isI(o t ) = {o t-m:t-1 , a t-m:t-1 } , I(a t ) = {o 1:t , a 1:t-1 } .The observables are all observations and actions, U = {o 1:T , a 1:T }. By Theorem 1 we have that I † (o t ) = {o t-m:t-1 , a t-m:t-1 }, as shown in Figure 5d . Hence, the rank of this sequential decisionmaking process is bounded by |O| m |A| m . (a) Decentralized POMDP/POMG information-structure. and light edges indicate the information sets of action variables. Grey nodes represent unobservable variables, blue nodes represent past observable variables, green nodes represent future observable variables, and red nodes represent the information structural state I † h . To find I † h , as per Theorem 1, we first remove the incoming edges into the action variables, then we find the minimal set among all past variables (both observable and unobservable) which d-separates the past observations from the future observations. Symmetric / "Mean-field" Information Structures. Consider a sequential decision-making problem with N agents. Each agent has their own local state, s i t ∈ S local . Similarly, at each time point, each agent takes an action a t i ∈ A loc . The global state s t = (s 1 t , . . . , s N t ) ∈ S N loc =: S is composed by of all agents' local states. Similarly, the joint action space is A := A N loc . Consider a symmetric information structure where the evolution of each agent's local state depends only on a symmetric aggregation of all agents' states and actions, rather than on the local state/action of any particular agent. That is, the identity of who is in what state or takes which action does not matter-only the distribution of states and actions. This is often referred to as a "mean-field" setting (in the limit). Here, the transition depends only on the distribution of local states and actions, defined ass 1 1 a 1 1 s 2 1 a 2 1 s 3 1 a 3 1 s mf 1 a mf 1 s 1 2 s 2 2 s 3 2 a 1 2 a 2 2 a 3 2 s mfs mf t = dist(s t ) := 1 N δ s i t , a mf t = dist(a t ) := 1 N δ a i t , for s t ∈ S, a t ∈ A.Different agents can have different transition kernels for their local state. Hence, by introducing dist(s t ), dist(a t ) as auxiliary unobserved variables at each time t, we obtain the following information structure,I(s i t ) = {dist(s t-1 ), dist(a t-1 )} , I(a i t ) = s i tand an application of Theorem 1 bounds the rank byI † (s i t ) < |S loc ||A loc | N |S loc | -1 + 1 |S loc |-1 N |A loc | -1 + 1 |A loc |-1 . This is compared to |S loc | N • |A loc | N (e.g., if we modeled this as an MDP with the state s t ), which is much larger when the number of agents is large. The information structure and d-separation decomposition are depicted in Figure 5b .Point-to-Point Real-Time Communication with Feedback. Consider the following model of realtime communication with feedback. Let x t be the Markov source. At time t, the encoder receives the source x t ∈ X and encodes sending a symbol z t ∈ Z. The symbol is sent through a memoryless noisy channel which outputs y t to the receiver. The decoder produces the estimate x t . The output of the noisy channel is also fed back to the encoder. The encoder and decoder have full memory of their observations and previous "actions". The observation variables are O = {x 1:T , y 1:T } and the "actions" are A = {z 1:T , x 1:T }. Hence, the information structure is given by the following,I(x t ) = {x t-1 } , I(z t ) = {x 1:t , y 1:t-1 , z 1:t-1 } , I(y t ) = {z t } , I( x t ) = {y 1:t } .By Proposition 1, we have that,I † (x t ) = {x t } , I † (z t ) = {x t } , I † (y t ) = {x t , z t } , I † ( x t ) = {x t } .Hence, the rank is bounded by |X||Z|. This is depicted in Figure 5c .Fully-Connected Information Structures. Consider a sequential decision making problem with variables o t , a t , t ∈ [T ] and a fully-connected information structure. That is, each observation directly depends on the entire history of observations and actions. Thus, the information structure isI(o t ) = {o 1:t-1 , a 1:t-1 } , I(a t ) = {o 1:t , a 1:t-1 }The observables are all observations and actions, U = {o 1:T , a 1:T }. By Theorem 1 we have that I † (o t ) = {o 1:t-1 , a 1:t-1 }, as shown in Figure 5e . Hence, the rank of this sequential decision-making process can be exponential in the time horizon.The examples above show that the tractability of a sequential decision-making problem in terms of the complexity of its dynamics depends directly on its information structure. This gives an interpretation of why certain models, like POMDPs, are more tractable than those with arbitrary information structures. Previous work primarily considers particular problem classes with fixed and highly regular information structures. In this work we argue for the importance of explicitly modeling the information structure of a sequential decision-making problem.Remark 2 (Necessity of generalized PSRs). The formalization of generalized PSRs in Section 2.2 was necessary to enable the study of information structure through POSTs/POSGs. An alternative (naive) solution to construct PSR representations for models with non-alternating observations and actions is to aggregate consecutive observations and actions to force them to obey the standard formulation of PSRs. This approach results in a loss of "resolution" in the information structure. That is, when you aggregate consecutive system variables, you also aggregate the DAG which represents the information structure, losing potentially important structure. In particular, in the worst case, such aggregation could result in an exponential increase in the rank of the dynamics We will adapt the model-based UCB-type algorithm of Huang et al. [35] , extending it to generalized PSRs, including those representing POSTs. The algorithm involves the estimation of an upper confidence bound which captures the uncertainty in the estimated model and drives exploration so as to minimize this uncertainty. The UCB-based approach has the advantage of providing a last-iterate guarantee and requiring a weaker notion of planning oracle (a standard planning oracle instead of an optimistic planning oracle as required by similar algorithms). The technical contribution of this section is to extend the algorithm and its theoretical guarantees to generalized PSRs. The tools developed in doing so can be used to directly extend any other PSR-based algorithm to generalized PSRs.When learning generalized PSRs, we suppose that the core test sets {Q h } 0≤h≤H-1 are known by the algorithm. For example, if the sequential decision-making problem is a POST, Section 4 provides conditions under which m-step futures form core test sets. Let Θ be the set of γ-well-conditioned generalized PSR representations with {Q h } 0≤h≤H-1 as core test sets. Denote by Θ ϵ an optimistic ϵ-cover of Θ (defined formally in Appendix G).Recall thatd h := |Q h | and d = max h d h . Moreover, Q A h := act(Q h )are the action components of the core test sets and Q A := max h Q A h is the maximal size of those action components. We define the exploration action sequences at time h to beQ exp h-1 = act(X h × Q h ∪ Q h-1). Moreover, we define u exp h-1 as the policy, defined from time h -1 onwards, in which each selection of action sequences in Q exp h-1 are chosen uniformly at random. For a model θ and reward function R, we define the value of a policy under this model and reward as V R θ (π) := τ H R(τ H )P π θ (τ H ). The algorithmic description is given in Algorithm 1. At each iteration k, the learner collects a trajectory τ k,h H for each time index h ∈ [H] by using a particular policy that drives exploration so as to better estimate the parameters associated with the h-th time step. To collect the trajectory τ k,h H , the learner executes the policy at the previous iteration, π k-1 , until time h -1 collecting the trajectory τ k,h h-1 then executes u exp h-1 which samples action sequences from Q exp h-1 uniformly. The particular choice of the exploratory action sequences Q exp h-1 comes out of the proof (see proof of Lemma 5 in the appendix). Intuitively, act(Q h-1 ) allows us to estimate the prediction featuresψ * (τ k,h h-1 ) = [P(q | τ k,h h-1 )] q∈Q h-1 , and act(X h × Q h ) allows us to estimate M * h (x h )ψ * (τ k,h h-1). The collected trajectories are added to the dataset, together with the policies used to collect them. The next step is model estimation via (constrained) maximum likelihood estimation. The algorithm estimates a model θ k by selecting any model in a constrained set B k defined asEQUATIONThe introduction of Θ k min ensures thatP π k-1 θ * (τ k,h h-1) is not too small so that the estimates of the prediction features ψ * (τ k,h h-1 ) = [P(q | τ k,h h-1 )] q∈Q h-1 are accurate. This design differs from other MLE-based estimators [e.g., 33, 36, 38] due to the estimation of parameters capturing conditional probabilities.Next, the algorithm chooses a policy which drives the algorithm to trajectories τ h whose prediction features have so far been unexplored. To do this, Algorithm 1 constructs an upper confidence bound on the total variation distance between the estimated model and the true model. This is done via a bonus function bk (τ H ), b k (τ H ) = min    α H-1 h=0 ψ(τ h ) 2 ( U k h ) -1 , 1   , where,EQUATIONwhere λ and α are pre-specified parameters to the algorithm. Thus, the bonus function captures the degree of uncertainty in the estimated prediction features ψ(τ h ). In particular, the bonus b(τ H ) will be large for trajectories whose prediction feature ψ(τ h ) lie far away from the empirical distribution of prediction features sampled in the dataset D k h . This is captured by computing the norm with respect to the covariance U k h . The algorithm then chooses an exploration policy for the next iteration which maximizes this upper confidence bound, hence collecting trajectories that have high uncertainty in their prediction features. When the estimated model is sufficiently accurate on all trajectories, the algorithm terminates and returns the optimal policy with respect to the reward function R under the estimated model. = (ω k,h h-1 , τ k,h h-1 ) using ν(π k-1 , u exp h-1 ). D k h-1 ← D k-1 h-1 ∪ τ k,h H , ν π k-1 , u exp h-1. endD k = D k h H-1 h=0Compute MLE θ ∈ B k , whereΘ k min = θ : ∀h, (τ h , π) ∈ D k h , P π θ (τ h ) ≥ p min , B k =    θ ∈ Θ k min : (τ H ,π)∈D k log P π θ (τ H ) ≥ max θ ′ ∈Θ k min (τ H ,π)∈D k log P π θ ′ (τ H ) -β    . Define the bonus function, b k (τ H ) = min α H-1 h=0 ψ(τ h ) 2 ( U k h ) -1, 1 , whereU k h = λI + τ h ∈D h k ψ k (τ h ) ψ k (τ h ) ⊤ .Solve the planning problem to maximize the bonus functionπ k = arg max π V b k θ k (π). if V b k θ k (π k ) ≤ ϵ/2 then θ ϵ = θ k . break. end end return π = arg max π V R θ ϵ (π)We extend Huang et al.'s theoretical guarantees to show that Algorithm 1 enjoys polynomial sample complexity for generalized PSRs (Definition 3). Theorem 4. Suppose Assumption 1 holds. Suppose the parameters p min , λ, α, β are chosen appropriately. In particular, letp min ≤ δ KH H h=1 |X h | , λ = γ max s∈A |X s | 2 Q A β max{ √ r, Q A √ H/γ} √ dH , α = O Q A √ dHλ γ 2 + max s∈A |X s | Q A √ β γ , β = O log Θ ε , ε ≤ p min KH .Then, with probability at least 1 -δ, Algorithm 1 returns a model θ ϵ and a policy π that satisfyV R θ ϵ (π * ) -V R θ ϵ (π) ≤ ε, and ∀π, D TV P π θ ϵ (τ H ), P π θ * (τ H ) ≤ ε.In addition, the algorithm terminates with a sample complexity of,Õ r + Q 2 A H γ 2 • rdH 3 • max s∈A |X s | 2 • Q 4 A β γ 4 ϵ 2 .Proof. The proof is given in Appendix J.This result shows that the sample complexity of learning a generalized PSR depends on the problem size through a few key quantities. In particular, the sample complexity scales polynomially in the underlying rank r, the dimension of the PSR parameterization d, the size of the action component of the core tests Q A , the time horizon H, the conditioning number γ -1 , the size of the action spaces max s∈A |X s |, the log covering number log|Θ ϵ |, and the desired suboptimality error ϵ. Note that Õ omits logarithmic dependence.To apply this algorithm to a POST, we can use the generalized PSR parameterization constructed in Section 4. By Theorem 1 the PSR rank is bounded by r ≤ max h |I † h |. If this POST is αrobustly I † -weakly revealing, then by Theorem 2 it admits a γ-well-conditioned generalized PSR parameterization with γ = α/ max h |I † h | 1/2 and the m-step futures as core test sets. Moreover, we haved = max h d h = max h |Q m h |.The following corollary states that Algorithm 1 can learn a partially-observable sequential team with a sample complexity which is polynomial in the size of the information-structural state space max h |I † h |. Corollary 1. Suppose a partially-observable sequential team is m-step α-robustly I † -weakly revealing as per Definition 6. Applying Algorithm 1 to this PSR representation, with parameters p min , λ, α, β chosen as in Theorem 4, returns a ε-optimal policy with a sample complexity of,Õ 1 + Q 2 A H α 2 max h |I † h | 7 • max h |Q m h | • H 5 • max s∈A |X s | 2 • max s∈U |X s | • Q 4 A α 4 ϵ 2 .We can interpret this result as saying that the information structure of a sequential decision-making problem, through the quantity max h |I † h |, is fundamentally a measure of the complexity of the dynamics which need to be modeled. As a result, learning is tractable when max h |I † h | is of modest size, and intractable otherwise. Recall that max h |I † h | is small when there exists "state-like" variables, whether they are observable or unobservable. In this sense, max h |I † h | is a fundamental quantity which generalizes the notion of a "state". For example, in the case of an m-step α-weakly revealing POMDP, our algorithm has a sample complexity of poly(S, (OA) m , H, α -1 ) • ϵ -2 , where S is the size of the state space, O is the size of the observation space, and A is the size of the action space. This is similar to the sample complexity of [36, 37] , which designed an algorithm tailored specifically for weaklyrevealing POMDPs. Our algorithms, together with the POST/POSG models, enable sample-efficient reinforcement learning for a much broader class of models all within a unified framework.In this section, we extended the algorithm in Huang et al. [35] to generalized PSRs, enabling sampleefficient learning of POSTs. We emphasize that other PSR-based algorithms can be extended in a similar manner. In the next section, we tackle the problem of learning in the game setting where different agents have different objectives.In a POST, all agents share the same objective. In the game setting, different agents may have different objectives which compete with each other in interesting ways. Information structures play a crucial role in the study of games. The information available to one agent when making its decisions, compared to the information available to competing agents, determines how well it can achieve its objective. In particular, the information structure of a problem determines the set of equilibria it admits. There has been a plethora of work in the game theory community studying such problems.Analogously to partially-observable sequential teams, we define partially-observable sequential games (POSGs). The dynamics of a POSG are identical to a POST, with the same formalization of variable structure, variable spaces, information structure, system kernels, and decision kernels. In contrast to a POST, agents in a POSG may have different objectives. In a POSG, there exists N agents, with agent i ∈ [N ] deciding the actions at times t ∈ A i , where A i ⊂ A. Each agent has its own objective defined by a reward function R i . This is defined formally below. Definition 7 (Partially-Observable Sequential Game Model). A partially-observable sequential game (POSG) is a controlled stochastic process consisting of the following components: variable structure, variable spaces, information structure, system kernels, decision kernels, and observability. These are defined in an identical manner to Definition 4. Additionally, POSGs define a reward structure as follows. Let N be the number of agents. Each agent may act several times. Denote by A i ⊂ A the index of action variables associated to agent i ∈ [N ]. Each agent has a reward function R i : t∈U X t → [0, 1] which they aim to maximize.Denote by π i = (π t : t ∈ A i ) the collection of decision kernels belonging to agent i, one for each action they take. Denote by π = (π 1 , . . . , π N ) the collection of all agents' policies. Fixing π induces a probability distribution over X 1 × • • • X T in the same way as in the team setting,EQUATIONThe value of a policy π for agent i ∈ [N ] is defined as the expected value of their reward R i under P π ,EQUATIONwhere π -i = (π j : j ̸ = i).The nature of randomization in agents' policies is crucial to the analysis of solution concepts in the game setting. To model randomized policies, which are potentially correlated, we introduce a random seed ω ∈ Ω which is sampled at the beginning of an episode. Then, the policy at time t ∈ A can be modeled as a deterministic function mapping the seed ω and information variable i t ∈ I t to an action X t . That is, π t : Ω × I t → X t . To model independently randomized policies with each agent having private randomness, we consider the special case where the seed has the product structureω = (ω 1 , . . . , ω N ) ∈ Ω 1 × • • • × Ω N , and ω i is the seed belonging to agent i ∈ [N ]. Then, for t ∈ A i , π t : Ω i × I t → X t .For each agent i ∈ [N ], define the three policy spaces,1. Deterministic policies, Γ i det = π i : π i = π t : I t → X t , t ∈ A i , 2. Independently-randomized policies, Γ i ind = π i : π i = π t : Ω i × I t → X t , t ∈ A i , 3. Correlated randomized policies, Γ i cor = π i : π i = π t : Ω × I t → X t , t ∈ A i .Define the joint deterministic policy space, asΓ det = Γ 1 det × • • • × Γ N det ,and similarly for the independently-randomized policy space Γ ind , and the correlated randomized policy space Γ cor .When studying games, a common question is to find an equilibrium within a particular policy space. At a high-level, an equilibrium is a joint policy where no agent can do better by deviating from their policy when the other agents keep their policies fixed. We will consider several notions of equilibrium. We begin by defining the notion of a best-response. Suppose that agent i's policy space is Γ i (e.g., Γ i det , Γ i ind , or Γ i cor ). Then, we say that agent i's policy π i is a best response to π -i if there is no policy in Γ i which achieves a higher value. This is formalized in the definition below. Definition 8 (Best response). For a joint policy π, π i is said to be a best-response to π -i in the policy space Γ i (e.g., Γ i det , Γ i ind , orΓ i cor ), if V i (π i , π -i ) = max πi ∈Γ i V i (π i , π -i ) =: V i, † (π -i ).This leads to the definition of two notions of equilibria. A Nash Equilibrium (NE) is a joint policy where all agents are best-responding in the space of independently-randomized policies. A Coarse Correlated Equilibrium (CCE) is a joint policy where all agents are best-responding in the space of correlated randomized policies. The difference between NE and CCE is that the randomness in the joint policy must be independent in an NE but can be correlated in a CCE. Since Γ ind ⊂ Γ cor , coarse correlated equilibria are a generalization of Nash equilibria. We define them formally below. Definition 9 (Nash Equilibrium). A joint policy π ∈ Γ ind is said to be a Nash equilibrium if for all agentsi ∈ [N ], V i (π) = max πi ∈Γ i ind V i (π i , π -i ) =: V i, † (π -i ). A joint policy π ∈ Γ ind is said to an ε-approximate Nash equilibrium if V i (π) ≥ V i, † (π -i ) -ε for all i ∈ [N ]. Definition 10 (Coarse Correlated Equilibrium). A joint policy π ∈ Γ cor is said to be a coarse correlated equilibrium if for all agents i ∈ [N ], V i (π) = max πi ∈Γ i cor V i (π i , π -i ) =: V i, † (π -i ). A joint policy π ∈ Γ cor is said to an ε-approximate Nash equilibrium if V i (π) ≥ V i, † (π -i ) -ε for all i ∈ [N ].Since we consider finite-space sequential games, an equilibrium is guaranteed to exist [93] . Remark 3 (Notion of equilibrium can be represented through information structure). The policy classes defined above (i.e., deterministic, independently-randomized, correlated randomized) can be directly modeled by the information structure. For example, to represent correlated randomized policies, the random seed ω ∈ Ω can be modeled as an observable variable at time t = 0 which is in all agents' information sets. Similarly, independently randomized policies can be represented through a different random seed for each agent at time t = 0, and including the appropriate random seed in each action's information set. Hence, the information structure itself can decide which equilibrium notion we are interested in. Moreover, this allows us to consider additional notions of equilibrium where, for example, only subsets of agents can be correlated with each other (e.g., this may be useful in modeling multi-team problems). Note that adding random seeds in order to model randomized policies does not affect the information-structural state I † h since the seeds don't appear in G † . For concreteness, we focus on NE and CCE in our presentation.Algorithm as a function of the Information StructureWe now introduce a sample-efficient reinforcement learning algorithm for learning well-conditioned generalized predictive state representations in the game setting with each agent having their own objective. In particular, since partially-observable sequential games with a I † -weakly revealing information structure admit a well-conditioned generalized PSR representation, they can also be learned sample-efficiently by this algorithm.The algorithm we propose is a self-play algorithm for learning an equilibrium of the dynamic game problem. That is, the algorithm specifies the policies of all agents during the learning phase, collecting the trajectory of observables at each episode to improve its estimate of the system dynamics. This can be thought of as a centralized agent playing against itself. We will propose an algorithm which can find a Nash equilibrium or coarse correlated equilibrium in a sample-efficient manner. We begin with some preliminaries.Game setting. Recall that a sequential decision-making problem falls within the game setting if each agent has their own objective. Following Section 2.1, we consider a sequential decisionmaking problem (X 1 , . . . , X H ) where O denotes the index set of (observable) system variables and A denotes the set of action variables. We suppose the game involves N agents, and denote the action index set of each agent by A i ⊂ A, where {A i } i∈[N ] partitions A. Each agent has their own reward function R i (X 1 , . . . , X H ). Note that POSGs as defined in Definition 7 are structured models which fall within this framework.Equilibria and policy classes. Recall that in the game setting, the type of randomization in each agent's policy affects the set of equilibria in the game. In Appendix F.1, we formalized this randomization by introducing a random seed ω ∈ Ω and allowing each agent's policy to be a function of their information set and this seed. If the seed has a product structure ω = (ω 1 , . . . , ω N ) with each agent observing their own seed, this results in independently-randomized policies, denoted by Γ i ind . If all agents use the same seed, this results in correlated randomized policies, which we denote by Γ icor . An equilibrium among independently randomized policies is called a Nash equilibrium and an equilibrium among correlated randomized policies is called a coarse correlated equilibrium.Estimating probabilities in the planner. The probability of any trajectory under a joint policy π is given by Pπ (τ H ) = ω P [τ H ] π(τ H |ω)P [ω], where P [τ H ] = P [τ o H | τ a H ] as before, and π(τ H | ω) = h∈A 1{x h = π h (τ h-1 , ω)}.Recall that the probabilities P [τ H ] are estimated by the generalized PSR model θ. We assume that the planner has knowledge of the randomization, P [ω]. Hence, the planner in the self-play algorithm is able to compute the probability of any trajectory for each choice of policy.Algorithm. The algorithmic description is presented in Algorithm 2. In the first stage of the algorithm, the centralized learning agent has a unified goal: to explore the environment. This is done by executing policies which maximize the bonus function b k (τ H ) by visiting trajectories with imprecise estimates of their probability, as measured by the upper confidence bound on the total variation distance. This part is identical to Algorithm 1. Once the algorithm is sufficiently confident about the estimated probabilities of all trajectories, it computes the equilibrium using the estimated model directly. That is, ComputeEquilibrium computes either NE or CCE. The only difference in the exploration stage of the algorithm compared to Algorithm 1 is that the termination condition involves ε/4 rather than ε/2 in order to guarantee an ε-approximate equilibrium under the added complications of the game setting.Theorem 5. Suppose Assumption 1 holds. Suppose the parameters p min , λ, α, β are chosen as in Theorem 4. Then, with probability at least 1 -δ, Algorithm 2 returns a model θ ϵ and a policy π which is an ε-approximate equilibrium (either NE or CCE). That is,V i θ * (π) ≥ V i, † θ * (π -i ) -ε, ∀i ∈ [N ].Algorithm 2: Self-play UCB Algorithm for Sequential Gamesfor k ← 1, . . . , K do for h ← 1, . . . , H do Collect τ k,h H = (ω k,h h-1 , τ k,h h-1 ) using ν(π k-1 , u exp h-1 ). D k h-1 ← D k-1 h-1 ∪ τ k,h H , ν π k-1 , u exp h-1. endD k = D k h H-1 h=0Compute MLE θ ∈ B k , whereΘ k min = θ : ∀h, (τ h , π) ∈ D k h , P π θ (τ h ) ≥ p min , B k =    θ ∈ Θ k min : (τ H ,π)∈D k log P π θ (τ H ) ≥ max θ ′ ∈Θ k min (τ H ,π)∈D k log P π θ ′ (τ H ) -β    . Define the bonus function, b k (τ H ) = min α H-1 h=0 ψ(τ h ) 2 ( U k h ) -1, 1 , whereU k h = λI + τ h ∈D h k ψ k (τ h ) ψ k (τ h ) ⊤ .Solve the planning problemπ k = arg max π V b k θ k (π). if V b k θ k (π k ) ≤ ϵ/4 then θ ϵ = θ k . break. end end return π = ComputeEquilibrium(θ ϵ , R 1 , . . . , R N )In addition, the algorithm terminates with a sample complexity of,Õ r + Q 2 A H γ 2 • rdH 3 • max s∈A |X s | 2 • Q 4 A β γ 4 ϵ 2 .Proof. The proof is given in Appendix K.To apply this algorithm to a partially-observable sequential game, we can use the generalized PSR parameterization constructed in Section 4. Corollary 2. Suppose a partially-observable sequential game is m-step α-robustly I † -weakly revealing as per Definition 6. Applying Algorithm 2 to this PSR representation, with parameters p min , λ, α, β chosen as in Theorem 5, returns a ε-approximate equilibrium π with a sample complexity of,Õ 1 + Q 2 A H α 2 • max h |I † h | 7 • max h |Q m h | • H 5 • max s∈A |X s | 2 • max s∈U |X s | • Q 4 A α 4 ϵ 2 .In this section we show that any rank-r sequential decision-making problem (as per Section 2.1) can be represented via a rank-r generalized PSR (Definition 3). Next, we bound the covering number of the class of rank r PSRs, which will be important for our MLE analysis. Similar results have been established in previous work for sequential decision-making problems with alternating observations and actions [e.g. , 33] . Recall that our formulation of the generic sequential decision-making problem and generalized PSRs is more general than the standard formulation since it allows for an arbitrary sequence of variables. Here, we follow a similar procedure to prove a slightly generalized result.Proposition 2 (Existence of Generalized PSR representation). Consider a sequential decision-making problem with rank(D h ) = r h , h ∈ 0 : H -1. There exists a generalized PSR representation (i.e, observable operator model) b 0 , {B h (x h )} h∈[H],x h ∈X h , {v h } h∈0:H such that, 1. B h (x h ) ∈ R r h ×r h-1 and ∥B h (x h )∥ 2 ≤ 1 for any x h . 2. |b 0 | ≤ |H a H |. 3. ∥v h ∥ 2 ≤ |F o h | / |F a h |.h = (x 1 , . . . , x h ) ∈ H h , h ∈ 0 : H, we have B h (x h ) • • • B 1 (x 1 )b 0 = U ⊤ h D ⊤ h :,τ h .Proof of claim. We prove the claim by induction. In the base case, h = 0, D ⊤ 0 is a vector in R F0 (note that F 0 = H H ). Hence, U 0 is simply the normalized vector U 0 = D ⊤ 0 /∥D ⊤ 0 ∥ 2 , and henceU ⊤ 0 D ⊤ 0 = D 0 D ⊤ 0 /∥D 0 ∥ 2 = ∥D 0 ∥ 2 = b 0 .Proceeding by induction, suppose the claim holds for h -1. Then, we have,B h (x h ) • • • B 1 (x 1 )b 0 = B h (x h )U ⊤ h-1 D ⊤ h-1 :,τ h-1 = U ⊤ h [U h-1 ] (x h ,F h ),: U ⊤ h-1 D ⊤ h-1 :,τ h-1 = U ⊤ h U h-1 U ⊤ h-1 D ⊤ h-1 (x h ,F h ),τ h-1 = U ⊤ h D ⊤ h-1 (x h ,F h ),τ h-1 = U ⊤ h D ⊤ h :,τ h ,where the final equality is becauseD ⊤ h-1 (x h ,ω h ),τ h-1 = P [τ h-1 , x h , ω h ] = P [τ h , ω h ] = D ⊤ h ω h ,τ h .Using this fact, we can now show property 5 as follows,v ⊤ h B h (x h ) • • • B 1 (x 1 )b 0 = 1 |F a h | 1 ⊤ U h U ⊤ h D ⊤ h :,τ h = 1 |F a h | 1 ⊤ D ⊤ h :,τ h = 1 |F a h | ω h ∈F h P [τ h , ω h ] = 1 |F a h | ω a h ∈F a h ω o h ∈F o h P [τ o h , ω o h | τ a h , ω a h ] = 1 |F a h | P [τ o h | τ a h ] ω a h ∈F a h ω o h ∈F o h P [ω o h | ω a h , τ a h , τ o h ] = 1 |F a h | P [τ o h | τ a h ] ω a h ∈F a h 1 = P [τ o h | τ a h ] .Finally, it remains to show property 4. Consider the linear equation x ⊤ U ⊤ h D ⊤ h = |F a h | -1 1 ⊤ D ⊤ h . Note that U ⊤ h D ⊤ h ∈ R r h ×|H h | is rank r h .⊤ h = v ⊤ h+1 x h+1 B h+1 (x h ). That v ⊤ h is a solution is clear by definition of v h , v ⊤ h U ⊤ h D ⊤ h = |F a h | -1 1 ⊤ U h U ⊤ h D ⊤ h = |F a h | -1 1 ⊤ D ⊤ h . First, recall by the calculation above that |F a h | -1 1 ⊤ D ⊤ h is a vector in R H h where the τ h -th entry is P [τ o h | τ a h ].We will calculate the τ h -th entry of the vectorx ⊤ U ⊤ h D h when x ⊤ = v ⊤ h+1 x h+1 B h+1 (x h+1 ),   v ⊤ h+1 x h+1 B h+1 (x h+1 )   U ⊤ h D ⊤ h :,τ h = 1 F a h+1 x h+1 1 ⊤ U h+1 U ⊤ h+1 [U h ] (x h+1 ,F h+1 ),: U ⊤ h D ⊤ h :,τ h = 1 F a h+1 x h+1 1 ⊤ U h+1 U ⊤ h+1 U h U ⊤ h D ⊤ h (x h+1 ,F h+1 ),τ h = 1 F a h+1 x h+1 1 ⊤ D ⊤ h (x h+1 ,F h+1 ),τ h = 1 F a h+1 x h+1 ω h+1 P [τ h , x h+1 , ω h+1 ] = 1 F a h+1 ω h ∈F h P [τ h , ω h ] = 1 F a h+1 P [τ o h | τ a h ] ω a h ∈F a h τ o h ∈F o h P [ω o h | τ h , ω a h ] = 1 F a h+1 P [τ o h | τ a h ] ω a h ∈F a h 1 = 1 F a h+1 |F a h | P [τ o h | τ a h ] = 1 |X h+1 | 1{h+1∈A} P [τ o h | τ a h ] ,where the final inequality is since|F a h | = s∈h+1:H (|X s | 1{s∈A} ).Corollary 3. Consider a sequential decision-making problem with rank(D h ) ≤ r. Then, there existsa generalized PSR b 0 ∈ R r , {B h (x h )} h∈[H],x h ∈X h ⊂ R r×r , v H ∈ R r such that, 1. ∥B h (x h )∥ 2 ≤ 1, ∀h, x h ∈ X h , ∥b 0 ∥ 2 ≤ |H a H |, and ∥v H ∥ 2 ≤ 1.Lemma (Restatement of Lemma 1). Suppose that the POST/POSG is m-step I † -weakly revealing. Then, Q m h is a core test set for all h ∈ [H]. Furthermore, we haveEQUATIONProof. Let τ h ∈ H h , ω h ∈ F h be any history and future, respectively. By Theorem 1, recall that we haveEQUATIONRecall that i † h may overlap with τ h . In particular, the action component ofi † h is contained in τ h . Thus, P[i † h | τ h ] = P[{x k , k ∈ I † h \ U 1:h } | τ h ] • 1{(x k , k ∈ I † h ∩ U 1:h ) matches τ h }. Note that I † h \ U 1:h ⊂ Sdoes not contain any actions. Hence, the summation over I † h is equivalent to summing over its unobservable components with the restriction that its observable components match τ h .F h → R |I † h | and p h : H h → R |I † h | by mh (ω h ) = P ω h i † h i † h ∈I † h , p h (τ h ) = P i † h τ h i † h ∈I † h .Then, we have that the conditional probability of the future ω h given the past τ h is given by the inner product of the above mappings,P [ω h | τ h ] = ⟨ mh (ω h ), p h (τ h )⟩.Recall that the vector of (conditional) core test set probabilities for the history τ h is given byψ h (τ h ) = [P [q o | τ o h ; do(τ a h ), do(q a )]] q∈Q m h ∈ R |Q m h | .By the definition of G h and Equation ( 22), we haveG h p h (τ h ) = ψ h (τ h ), since, for q ∈ Q m h , (G h p h (τ h )) q = i † h (G h ) q,i † h (p h (τ h )) i † h = i † h P q o i † h ; do(q a ) P i † h τ h = P [q o | τ o h ; do(τ a h ), do(q a )] =: ψ h (τ h ) q Since by assumption rank(G h ) = I † h , its pseudo-inverse G † h is a left inverse of G h (i.e., G † h G h = I). Hence, multiplying on the left by G † h , we obtain p h (τ h ) = G † h ψ h (τ h ). Hence, P [ω h | τ h ] = mh (ω h ), G † h ψ h (τ h ) = G † h ⊤ mh (ω h ) m h (ω h ) , ψ h (τ h ) . That P [τ h , ω h ] = ⟨m h (ω h ), ψ h (τ h )⟩ follows directly by noting the definition of ψ h (τ h ) := ψ h (τ h )/P [τ h ].Hence, we have shown that for the test set Q m h , the probability of each future ω h given a history τ h is a linear combination of the probabilities of each test in the core test set with weightsm h (ω h ) := (G † h ) ⊤ mh (ω h ) ∈ R |Q m h| depending only on the future and not the history.Theorem (Restatement of Theorem 2). Suppose a POST/POSG is α-robustly m-step I † -weakly revealing. Then, the corresponding generalized PSR as constructed in Section 4 is γ-well-conditionedwith γ = α/ max h |I † h | 1/2 .We will first show that ({Q m h } h , ϕ H , {M h } h , ψ 0 ) indeed forms a PSR through a series of simple calculations.A direct corollary of Lemma 1 is the following.EQUATIONHence, given a history τ h-1 = (x t(1) , . . . , x t(h-1) ), having observed another variable x t(h) , we can update our predictions of the future and obtain the probability of trajectories of the form (τ h-1 , x t(h) , ω h ) for any future ω h ∈ F h . Note that x t(h) may be either an observation or an action. Hence, we can update our prediction of the future after deciding an action, and before receiving the next observation. This is in contrast to the standard PSR formulation where predictions of the future can only be updated with a pair of observation and action. Our formulation provides additional flexibility, which is crucial for the general information structures modeled by POSTs and POSGs.This means that, after observing x t(h) , we can use the m h : F h → R d h mapping constructed in Lemma 1 to update the probability of any candidate future ω h . We are particularly interested in updating the probabilities of the futures corresponding to the core test set at the next time point, since this provides a sufficient statistic of the past. Thus, we define the matrix mapping M h :EQUATIONThat is, M h (x t(h) ) is the matrix whose rows are indexed by the core tests at the h-th observable step, where the q ∈ Q h row is the weights given by the m h-1 mapping for the future consisting of x t(h) followed by q. This mapping enables us to update the probabilities of the core test sets.EQUATIONHence, for a history τ h = x t(1) , . . . , x t(h) ∈ H h , we haveEQUATIONwhere ψ 0 = ψ 0 (∅).Finally, observe that Q m H-1 = X t(H) . Hence,ψ H-1 (τ H-1 ) = P τ h-1 , x t(H) x t(H) ∈X t(H) ∈ R |Xt(H)| .Thus, letting ϕ H : X t(H) → R |Xt(H)| be ϕ H (x t(H) ) = e x t(H) (the canonical basis vector), yieldsEQUATIONHence, Equation ( 27) together with Equation (26) imply that (M , ϕ H , ψ 0 ) is a valid generalized PSR representation for the POST/POSG (as per Definition 3).What remains is to show that if the POST/POSG is α-robustly I † -weakly revealing, then the PSR constructed above is well-conditioned. Theorem (Restatement of Theorem 2). Suppose a POST/POSG is α-robustly m-step I † -weakly revealing. Then, the corresponding generalized PSR as constructed in Section 4 is γ-well-conditionedwith γ = α/ max h |I † h | 1/2 .Proof. We first show condition (1) in Assumption 1. Suppose h > H -m and hence the core tests are the full futures, which have length smaller than m. Then for anyx ∈ R d h , d h = H s=h |X s |, we have max π ω h m h (ω h ) ⊤ x • π(ω h ) = max π ω h |x[ω h ]| π(ω h ) ≤ ∥x∥ 1 ,where x[ω h ] indexes the component of the vector x corresponding to the future ω h . Now suppose h ≤ H -m (and hence the core tests consist of m-step futures). Then, we have,max π ω h m h (ω h ) ⊤ x π(ω h ) = max π ω h m(ω h ) ⊤ G h G † h x • π(ω h ) ≤ max π ω h i † ∈I † h m(ω h ) ⊤ G h e i † e ⊤ i † G † h x • π(ω h ).Now observe that for any policy π and any i † ∈ I † h , we haveω h m(ω h ) ⊤ G h e i † • π(ω h ) = ω h m(ω h ) ⊤ G † h G h e i † • π(ω h ) = ω h P ω h i † π(ω h ) = ω h P π ω h i † = 1,where we used the definition ofm h (ω h ) := mh (ω h ) ⊤ G † h , and [ mh (ω h )] i † := P[ω h | i † ]. Recall that π(ω h ) is such that for any fixed sequence of observations ω o h , ω a h π(ω o h , ω a h ) = 1.max π ω h m h (ω h ) ⊤ x π(ω h ) ≤ i † ∈I † h e ⊤ i † G † h x = G † h x 1 ≤ G † h 1 • ∥x∥ 1 ≤ I † h α ∥x∥ 1 ,where the final inequality is from the relation between the one-norm and two-normG † h 1 ≤ I † h G † h 2, and G † h 2 ≤ 1 α , by the assumption on its singular values. Now we show condition (2) in Assumption 1. For ease of notation, we denote x t(h) by x h . When h > H -m, note that [M h (x h )] q h+1 ,q h = 1{q h = (x h , q h+1 )}, for all q h ∈ Q h , q h+1 ∈ Q h+1 . Hence,we have maxπ x h ∥M h (x h )z∥ 1 π(x h ) = ∥z∥ 1 .Now, when h ≤ H -m, by a similar line of reasoning to the proof for condition (1), we have,EQUATION= maxπ i †   (x h ,q h+1 ) P x h , q h+1 i † π(x h |τ h-1 )   e ⊤ i † G † h zwhere step (a) uses the definition of M h and step (b) uses the definition ofm h (ω h ) ⊤ := mh (ω h ) ⊤ G † h and [ mh (ω h )] i † := P[ω h | i † ]. Now note that, (x h ,q h+1 ) P x h , q h+1 i † π(x h |τ h-1 ) = x h act(q h+1 ) obs(q h+1 ) P x h , obs(q h+1 ) i † , act(q h+1 ) π(x h ) = act(q h+1 ) 1 = Q A h+1, where the second line is since for any fixed action sequence, the sum over the probabilities of all observation sequences is 1.Thus, putting this together, we obtain the following,max π x h ∥M h (x h )z∥ 1 π(x h |τ h-1 ) ≤ Q A h+1 • G † h z 1 ≤ I † h Q A h+1 α ∥z∥ 1 ,where the last line again follows by the assumption on the singular values of G h .J Proof of Theorem 4: UCB Algorithm for Generalized PSRs (Team Setting)In this section, we prove Theorem 4 which states that Algorithm 1 returns a near-optimal policy in a polynomial number of iterations. The proof is adapted from [35] and generalized to our setting with generalized PSRs (Definition 3). The proof is organized into several subsections. In Appendix J.1, we show that the total variation distance between trajectories under the true model and the estimated model can be bounded in terms of the estimation error of the observable operators {M h } h . In Appendix J.2 we state some general results on maximum likelihood estimation which show that the MLE model has small error on the collected dataset. In Appendix J.3 we prove that the bonus term is an upper confidence bound for the total variation distance. In Appendix J.4 we show that the estimation error is sublinear in the number of iterations (i.e., O( √ K)). Finally, in Appendix J.5 we put this all together to prove the theorem.Recall that a PSR model θ = (M , ψ 0 , ϕ H ) consists of operatorsM = {M h } H-1 h=1 , M h : X h → R d h ×d h-1 , ϕ H : X H → R d H-1 (assumed to be the identity mapping), and ψ 0 (assumed to be known for the purposes of presentation). Recall that, for any trajectory τ h-1 = (x 1 , . . . , x h-1 ), under model θ, we haveEQUATIONHere, the notation P θ (x h | τ h-1 ) means the probability of x h conditioned on the history τ h-1 , with all actions executed. In particular, if x h is an action, thenP θ (x h | τ h-1 ) = 1 and M h (x h )ψ h-1 (τ h-1 ) = ψ h (τ h ).The following proposition shows that the total variation distance between the distribution of trajectories of two PSR models can be bounded in terms of the difference in their observable operators.Proposition 4. For any policy π and θ, θ ∈ Θ, we have,D TV P π θ , P π θ ≤ H h=1 τ H ∈H H π(τ h ) m h (ω h ) ⊤ M h (x h ) -M h (x h ) ψ h-1 (τ h-1 ) , D TV P π θ , P π θ ≤ H h=1 τ H ∈H H π(τ h ) m h (ω h ) ⊤ M h (x h ) -M h (x h ) ψ h-1 (τ h-1 ) ,Proof. The probability of any trajectory τ H = (x 1 , . . . , x H ) can be written in terms of products of the observable operators M h (x h ) of a PSR model (Equation ( 1)). Hence, we have,D TV P π θ , P π θ = 1 2 τ H P π θ (τ H ) -P π θ (τ H ) = 1 2 τ H π(τ H ) • H h=1 M h (x h ) ψ 0 - H h=1 M h (x h ) ψ 0 ≤ 1 2 τ H π(τ H ) H h=1 m h (x h+1:H ) ⊤ M h (x h ) -M h (x h ) ψ h-1 (τ h-1 ) ,where the second line follows by the triangle inequality after noting that for any trajectory τ H = x 1:H ∈ H H , the following holds for any h = 1, . . . , H,H h=1 M h (x h ) ψ 0 - H h=1 M h (x h ) ψ 0 = m h (x h+1:H ) ⊤ M h (x h ) ψ h-1 (x 1:h-1 )-m h (x h+1:H ) ⊤ M h (x h )ψ h-1 (x 1:h-1 ).By the same argument, we obtain the second inequality,D TV P π θ , P π θ = 1 2 τ H P π θ (τ H ) -P π θ (τ H ) ≤ 1 2 τ H π(τ H ) H h=1 m h (x h+1:H ) ⊤ M h (x h ) -M h (x h ) ψ h-1 (τ h-1 ) .In this result, recall that we assume ψ 0 is known to the agent, to simplify the presentation. If ψ 0 was not known, there would be another term due to the estimation as ψ 0 [see 33, Lemma C.3]. Note that the sample complexity of estimating ψ 0 is small compared to learning the other parameters.In this section, we state some general results on maximum likelihood estimation which ultimately guarantee that the estimated model produced by the procedure in Algorithm 1 has a small estimation error. The results are stated without proof. The proofs are given in [35] and use standard techniques on MLE analysis [94] . This ultimately leads us to a lemma which states that the estimation error of the MLE model is small on the collected data.The first proposition states that the log-likelihood of the true model θ * is large compared to any other model. Proposition 5 (Proposition 4 of [35] ). Fix ε < 1 KH . With probability at least 1 -δ, for any θ ∈ Θ ε and any k ∈ [K], the following holds:∀θ ∈ Θ ε , h (τ h ,π)∈D h log P π θ (τ h ) -3 log K Θ ε δ ≤ h (τ h ,π)∈D k h log P π θ * (τ h ) ∀θ ∈ Θ ε , (τ H ,π)∈D k log P π θ (τ H ) -3 log K Θ ε δ ≤ (τ h ,π)∈D k h log P π θ * (τ h )The second proposition provides an upper bound on the total variation distance between the distributions of futures given histories on the empirical history of trajectories. This result ensures that the model estimated by Algorithm 1 is accurate on the sampled trajectories. Proposition 6 (Proposition 5 in [35] ). Fix p min and ε≤ pmin KH . Let Θ k min = θ : ∀h, (τ h , π) ∈ D k h , P π θ (τ h ) ≥ p min . Then, with probability at least 1 -δ, for any k ∈ [K], θ ∈ Θ k min , we have, h (τ h ,π)∈D k h D 2 TV (P π θ (ω h |τ h ), P π θ * (ω h |τ h )) ≤ 6 h (τ h ,π)∈D k h log P π θ * (τ H ) P π θ (τ H ) + 31 log K Θ ε δ .The next proposition is standard in the analysis of maximum likelihood estimation. D H denotes the Hellinger distance. Proposition 7 (Proposition 6 of [35] ). Let ε < 1 K 2 H 2 . Then, with probability at least 1 -δ, the following holds for all θ ∈ Θ and k ∈ [K],π∈D k D 2 H (P π θ (τ H ), P π θ * (τ H )) ≤ 1 2 (τ H ,π)∈D k log P π θ * (τ H ) P π θ (τ H ) + 2 log K Θ ε δ .The final proposition of this section states that when p min is chosen as in Theorem 4, the true model θ * lies in the constraint Θ k min with high probability.Proposition 8. Fix p min ≤ δ KH H h=1 |X h | . Then, with probability at least 1 -δ, we have θ * ∈ Θ k min ∀k. Proof. For each k ∈ [K], we have θ * ∈ Θ k min if P π k θ * (τ k h ) ≥ p min for all h ∈ [H], (τ k h , π k ) ∈ D k h .Consider the probability of θ * violating this constraint for some trajectory in the dataset. For each k, h, (τ k h , π k ), we haveP P π k θ * (τ k h ) < p min = E π P P π k θ * (τ k h ) < p min π k = π = E π τ h ∈H h P π θ * (τ k h = τ h )1{P π θ * (τ h ) < p min } < τ h ∈H h p min = |H h | p min ≤ δ KH .In the above, the first line is by the law of total probability, where the expectation is over the policy π k used while collecting the (h, k)-th trajectory, and the inner probability is over trajectories τ k h . The second line calculates the probability of the event {P π k θ * (τ k h ) < p min }. Taking a union bound overk ∈ [K], h ∈ [H], and (τ h , π) ∈ D h implies that P θ * ∈ Θ k min ≥ 1 -δ.In what follows, let E ω , E π , E min be the events in Propositions 6 to 8, respectively. Let E = E ω ∩ E π ∩ E min be the intersection of all events. Propositions 6 to 8 guarantee the event E occurs with high probability, P [E] ≥ 1 -3δ, by a union bound.The following result states that the estimated model is accurate on the past exploration policies and dataset of collected trajectories. This holds for both the conditional probabilities of futures given past trajectories in the dataset as well as over full trajectories. The result follows from the MLE analysis in Propositions 6 to 8. , and suppose ε ≤δ K 2 H 2 h |X h |, where Θ ε is the optimistic ε-net in Proposition 3. Then, under event E, the following holds,h (τ h ,π)∈D k h D 2 TV P π θ k (ω h |τ h ), P π θ * (ω h |τ h ) ≤ 7β,andπ∈D k D 2 H P π θ k (τ H ), P π θ * (τ H ) ≤ 7β,Proof. The proof follows by Propositions 6 to 8. The argument is direct and is identical to Lemma 1 of [35] .Notation. Let m * , {M * h } h be the observable operators of the true PSR θ * , and let { M k h } h be the algorithm's estimates of the observable operators corresponding to θ k .Recall that Proposition 4 shows that the total variation distance between the distribution over trajectories of two PSRs is bounded by the estimation error of the observable operators M h . The following result constructs a bound on the estimation error of the observable operators M h (x h ). The proof is adapted from [35, Lemma 2] to our setting with generalized PSRs.Lemma 5. Under event E, for any policy π and k ∈ [K], we have,τ H m ⋆ (ω h ) ⊤ M k h (x h ) -M ⋆ h (x h ) ψ k h-1 (τ h-1 ) π(τ H ) ≤ E π τ h-1 ∼P θ k α k h-1 ψ k h-1 (τ h-1 ) ( U k h-1 ) -1where,U k h-1 = λI + τ h-1 ∈D k h-1 ψ k h (τ h-1 ) ψ k h (τ h-1 ) ⊤ α k h-1 2 = 4λQ 2 A d γ 4 + 4 max s∈A |X s | 2 Q 2 A γ 2 τ h-1 ∈D k h-1 D 2 TV P u exp h-1 θ k ω o h-1 τ h-1 , ω a h-1 , P u exp h-1 θ * ω o h-1 τ h-1 , ω a hProof. To ease notation, we index the future trajectories ω h-1 = (x h , . . . , x H ) ∈ F h-1 by i and his-tory trajectories τ h-1 = (x 1 , . . . , x h-1 ) ∈ H h-1 by j. We denote m ⋆ (ω h ) ⊤ M k h (x h ) -M ⋆ h (x h ) as w ⊤ i , ψ k h (τ h-1) as x j , and π(ω h-1 |τ h-1 ) as π i|j .The following bound follows from the Cauchy-Schwarz inequality,τ H m ⋆ (ω h ) ⊤ M k h (x h ) -M ⋆ h (x h ) ψ k h-1 (τ h-1 ) π(τ H ) (a) = ω h-1 τ h-1 m ⋆ (ω h ) ⊤ M k h (x h ) -M ⋆ h (x h ) ψ k h (τ h-1 ) π(ω h-1 |τ h-1 )P π θ k (τ h-1 ) = i j w ⊤ i x j π i|j P π θ k (j) = i j π i|j • sign(w ⊤ i x j )w i ⊤ x j • P π θ k (j) = j i π i|j • sign(w ⊤ i x j )w i ⊤ x j • P π θ k (j) = E j∼P π θ k   i π i|j • sign(w ⊤ i x j )w i ⊤ x j   (b) ≤ E j∼P π θ k   ∥x j ∥ ( U k h-1 ) -1 i π i|j • sign(w ⊤ i x j ) • w i U k h-1   .Step (a) follows from the fact thatψ k h-1 (τ h-1 ) = ψ k h (τ h-1 ) • ( ϕ k h-1 ) ⊤ ψ k h-1 (τ h-1 ) = ψ k h (τ h-1 ) • P θ k [τ h-1 ] and P θ k [τ h-1 ] • π(τ H ) = π(ω h-1 |τ h-1 ) • P π θ k (τ h-1 ).Step (b) is the Cauchy-Schwarz inequality.h-1 = j 0 . Let I 1 := i π i|j0 • sign(w ⊤ i x j0 ) • w i 2 U k h-1, which we bound next. By the definition of U k h-1 , we partition this term into two parts,I 1 = λ i π i|j0 • sign(w ⊤ i x j0 ) • w i 2 2 I2 + j∈D τ h-1   i π i|j0 • sign(w ⊤ i x j0 ) • w i ⊤ x j   2 I3.We bound I 2 and I 3 separately. By the triangle inequality, √ I 2 is bound by a sum of two terms,I 2 = √ λ max z∈R d h-1 :∥z∥ 2 =1 i π i|j0 • sign(w ⊤ i x j0 ) • w ⊤ i z (a) ≤ √ λ max ∥z∥ 2 =1 ω h-1 m ⋆ (ω ⊤ h ) M k h (x h ) -M ⋆ h (x h ) z π(ω h-1 |j 0 ) (b) ≤ √ λ max ∥z∥ 2 =1 ω h-1 m ⋆ (ω h ) ⊤ M k h (x h )z π(ω h-1 |j 0 ) + √ λ max ∥z∥ 2 =1 ω h-1 m ⋆ (ω h ) ⊤ M ⋆ h (x h )z π(ω h-1 |j 0 ),where step (a) is by the definition of w ⊤ i , π i|j0 and the triangle inequality, and step (b) is by the triangle inequality.Consider the first term. It can be bound via the definition of γ-well-conditioning as follows,max ∥z∥ 2 =1 ω h-1 m ⋆ (ω h ) ⊤ M k h (x h )z π(ω h-1 |j 0 ) = max ∥z∥ 2 =1 x h ω h m ⋆ (ω h ) ⊤ M k h (x h )z π(ω h |j 0 , x h ) π(x h |j 0 ) (a) ≤ 1 γ max ∥z∥ 2 =1 x h M k h (x h )z 1 π(x h |j 0 ) (b) ≤ 1 γ max ∥z∥ 2 =1 Q A h+1 ∥z∥ 1 γ (c) ≤ √ dQ A γ 2where step (a) is by the first condition in Assumption 1, step (b) is by the second condition of Assumption 1, and step (c) is by the fact that maxz∈R d h-1 :∥z∥ 2 =1 ∥z∥ 1 = d h-1 ≤ √ d and Q A h+1 ≤ Q A .In the above, note that we used the γ-well-conditioning of PSR θ k in step (a) and the γ-wellconditioning of PSR θ * in step (b). The second term in √ I 2 admits an identical bound, simply by using the well-conditioning of the PSR θ * in both steps. Hence, we have thatEQUATIONNow we upper bound I 3 ,I 3 ≤ τ h-1 ∈D k h-1   ω h-1 m ⋆ (ω h ) ⊤ M k h (x h ) -M ⋆ h (x h ) ψ k (τ h-1 ) π(ω h-1 |j 0 )   2 ≤ τ h-1 ∈D k h-1 ω h-1 m ⋆ (ω h ) ⊤ M k h (x h ) ψ k (τ h-1 ) -M ⋆ h (x h )ψ ⋆ (τ h-1 ) π(ω h-1 |j 0 ) I4 + ω h-1 m ⋆ (ω h ) ⊤ M ⋆ h (x h ) ψ k (τ h-1 ) -ψ ⋆ (τ h-1 ) π(ω h-1 |j 0 ) I5 2 =: τ h-1 ∈D k h-1 (I 4 + I 5 ) 2where the second equality follows from the triangle inequality by adding and subtracting m * (ω h ) ⊤ M * h (x h )ψ * (τ h-1 ) inside the absolute value. We now bound each of I 4 and I 5 .I 4 := ω h-1 m ⋆ (ω h ) ⊤ M k h (x h ) ψ k (τ h-1 ) -M ⋆ h (x h )ψ ⋆ (τ h-1 ) π(ω h-1 |j 0 ) (a) = ω h-1 m ⋆ (ω h ) ⊤ P θ k [x h | τ h-1 ] ψ h (τ h ) -P θ * [x h | τ h-1 ] ψ * h (τ h ) π(ω h-1 |j 0 ) (b) = x h ω h m ⋆ (ω h ) ⊤ P θ k [x h | τ h-1 ] ψ h (τ h ) -P θ * [x h | τ h-1 ] ψ * h (τ h ) π(ω h |j 0 , x h ) π(x h |j 0 ) (c) ≤ 1 γ x h P θ k [x h | τ h-1 ] ψ h (τ h ) -P θ * [x h | τ h-1 ] ψ * h (τ h ) 1 π(x h |j 0 ) (d) = 1 γ x h q h ∈Q h P θ k [x h , q h | τ h-1 ] -P θ * [x h , q h | τ h-1 ] π(x h |j 0 )where step (a) is by the fact thatEQUATIONc) is by Assumption 1, and step (d) follows by the definition ψ h , ψ h (τ h ) l = P θ q l h τ h . Now, we turn to bound the I 5 term. We haveI 5 = ω h x h m ⋆ h (ω h ) ⊤ M ⋆ h (x h ) ψ k (τ h-1 ) -ψ ⋆ (τ h-1 ) π(ω h |j 0 , x h )π(x h |j 0 ) (a) = ω h-1 m ⋆ h-1 (ω h-1 ) ⊤ ψ k (τ h-1 ) -ψ ⋆ (τ h-1 ) π(ω h-1 |j 0 ) (a) ≤ 1 γ ψ k (τ h-1 ) -ψ ⋆ (τ h-1 ) 1 = 1 γ q h-1 ∈Q h-1 P θ k [q h-1 | τ h-1 ] -P θ * [q h-1 | τ h-1 ] ,where step (a) is sincem * h (ω h ) ⊤ M * h (x h ) = m * h-1 (ω h-1 ) ⊤ , step (b)is by the first condition of Assumption 1, and the final equality is again by the definition of ψ.Combining the above, we have that,EQUATIONNow, we decompose the summations above over X h × Q h and Q h-1 into separate summations over observation futures and action futures. That is, (x h , q h ) is decomposed into (ω a h-1 , ω o h-1 ), where ω a h-1 = act(x h , q h ) and ω o h-1 = obs(x h , q h ), and the summations are overω a h-1 ∈ act(X h × Q h ) and ω o h-1 ∈ obs(X h × Q h ). Similarly, q h-1 can be decomposed into (q o h-1 , q a h-1 ) ∈ obs(Q h-1 ) × act(Q h-1 ). Hence, the bound on I 3 can be written as,I 3 ≤ 1 γ 2 • τ h-1 ∈D k h-1 ω a h-1 ω o h-1 P θ k ω o h-1 τ h-1 , ω a h-1 -P θ * ω o h-1 τ h-1 , ω a h π(x h |τ h-1 ) + q a h-1 q o h-1 P θ k q o h-1 τ h-1 , q a h-1 -P θ * q o h-1 τ h-1 , q a h-1 2 ≤ 1 γ 2 • τ h-1 ∈D k h-1   ω a h-1 ∈Q exp h-1 ω o h-1 P θ k ω o h-1 τ h-1 , ω a h-1 -P θ * ω o h-1 τ h-1 , ω a h-1   2 = 1 γ 2 Q exp h-1 2 • τ h-1 ∈D k h-1 D 2 TV P u exp h-1 θ k ω o h-1 τ h-1 , ω a h-1 , P u exp h-1 θ * ω o h-1 τ h-1 , ω a h-1 .Where the second inequality is by the definition ofQ exp h-1 = act (X h × Q h ∪ Q h-1). Here, the second summation is overω o h-1 ∈ obs (X h × Q h ∪ Q h-1). The final equality uses the fact the under the policy u exp h-1 the probability of each action sequenceω o h-1 is 1/ Q exp h-1 . Note that Q exp h-1 ≤ |act (X h × Q h )| + |act (Q h-1 )|, and hence we have Q exp h-1 ≤ 2 max s∈A |X s | Q A for all h.Hence, we have,EQUATIONPutting this together with the bounds on I 2 and I 3 , we get that,I 1 ≤ 4λQ 2 A d γ 4 + 4 max s∈A |X s | 2 Q 2 A 1 γ 2 τ h-1 ∈D k h-1 D 2 TV P u exp h-1 θ k ω o h-1 τ h-1 , ω a h-1 , P u exp h-1 θ * ω o h-1 τ h-1 , ω a h =: α k h-1 2 ,completing the proof.Using the above bound on the difference between the observable operators of the true model and the estimated model, we now bound the total variation distance between the distributions of trajectories through Proposition 4.Lemma 6. Under even E, the total variation distance between the estimated model at iteration k, θ k , and the true model θ * , is bounded by,EQUATIONfor any policy π, whereα 2 = 4λHQ 2 A d γ 4 + 28 max s∈A |X s | 2 Q 2 A 1 γ 2 βProof. Consider α k h-1 in the previous lemma. We have that,H h=1 α k h-1 2 = 4λHQ 2 A d γ 4 + 4 max s∈A |X s | 2 Q 2 A 1 γ 2 H h=1 τ h-1 ∈D k h-1 D 2 TV P u exp h-1 θ k ω o h-1 τ h-1 , ω a h-1 , P u exp h-1 θ * ω o h-1 τ h-1 , ω a h ≤ 4λHQ 2 A d γ 4 + 4 max s∈A |X s | 2 Q 2 A 1 γ 2 7β =: α 2 ,where the inequality is by the bound on the total variation distance established in Lemma 4. Now, by Proposition 4, the total variation distance is bounded by the estimation error: A direct corollary is the following bound on the error in the estimated value function, which establishes that the bonus term b k gives an upper confidence bound. Corollary 4 (Upper confidence bound). Under the event E, for any k ∈ [K], any reward functionEQUATIONR : h∈[H] X h → [0, 1], and any policy π, we have,V R θ k (π) -V R θ * (π) ≤ V b k θ k , where b k (τ H ) = min α h ψ k (τ h ) 2 ( U k h ) -1 , 1 .Proof. By a direct calculation,V R θ k (π) -V R θ * (π) = τ H R(τ H )P π θ k (τ H ) - τ H R(τ H )P π θ * (τ H ) (a) ≤ τ H P π θ k (τ H ) -P π θ * (τ H ) = D TV P π θ k (τ H ), P π θ * (τ H ) (b) ≤ α • E τ H ∼P π θ k   H-1 h=0 ψ k (τ h ) 2 ( U k h ) -1   (c) ≤ α τ H b k (τ H )P π θ k (τ H ) =: V b k θ kwhere step (a) is by the triangle inequality and the fact that R(τ H ) ∈ [0, 1], step (b) is by Lemma 6, and step (c) is by the definition of b k .J.4 K k=1 V b k θ k is sublinear The next step is to prove that K k=1 V b k θ k = O( √ K).To do that, we first prove that the estimated prediction features and the ground-truth prediction features can be related through the total-variation distance between the estimated model and the true model. Lemma 7. Under event E, for any k ∈ [K], we have:E τ H ∼P π θ *   H-1 h=0 ψ k (τ h ) 2 ( U k h ) -1   ≤ 2HQ A √ λ D TV P π θ * (τ h ), P π θ k (τ h ) + 1 + 2 max s∈A |X s | Q A √ 7rβ √ λ H-1 h=0 E τ h ∼P π θ * ψ * (τ h ) (U k h ) -1Proof. First, we recall the definition of U k h , and we define its ground-truth counterpart replacing estimated features with true features,U k h = λI + τ ∈D k h ψ k (τ h ) ψ k (τ h ) ⊤ , U k h = λI + τ ∈D k h ψ * (τ h )ψ * (τ h ) ⊤ .For any trajectory τ H ∈ H H , we have,H-1 h=0 ψ k (τ h ) 2 ( U k h ) -1 (a) ≤ H-1 h=0 ψ k (τ h ) ( U k h ) -1 ≤ 1 √ λ H-1 h=0 ψ k (τ h ) -ψ * (τ h ) 2 + H-1 h=0       1 + √ r τ h ∈D k h ψ k (τ h ) -ψ * (τ h ) 2 2 √ λ       ψ * (τ h ) (U k h ) -where step (a) is simply using ∥x∥ 2 ≤ ∥x∥ 1 and step (b) is by the identity [35, Lemma 13] . Note that r is the rank of the PSR and r ≥ rank({ ψ k (τ h ) :τ h ∈ H h }), rank({ψ * (τ h ) : τ h ∈ H h }).Moreover, we have,ψ k (τ h ) -ψ * (τ h ) 2 ≤ ψ k (τ h ) -ψ * (τ h ) 1 (a) = q h ∈Q h P θ k [q o h | τ h , q a h ] -P θ * [q o h | τ h , q a h ] (b) ≤ 2 max s∈A |X s | Q A D TV P u exp h-1 θ k (•|τ h ), P u exp h-1 θ * (•|τ h ) ,where we used the definition of ψ in (a) and the definition of the u exp h-1 in (b). Now, by Lemma 4, we have,H-1 h=0 ψ k (τ h ) 2 ( U k h ) -1 ≤ 1 √ λ H-1 h=0 ψ k (τ h ) -ψ * (τ h ) 2 + H-1 h=0       1 + √ r τ h ∈D k h ψ k (τ h ) -ψ * (τ h ) 2 2 √ λ       ψ * (τ h ) (U k h ) - ≤ 1 √ λ H-1 h=0 ψ k (τ h ) -ψ * (τ h ) 2 + 1 + 2 max s∈A |X s | Q A √ 7rβ √ λ H-1 h=0 ψ * (τ h ) (U k h ) -1 ,where the first line is combining the calculations above and the second line is by the estimation guarantee of Lemma 4.The first term can be bounded in expectation under P π θ * for any π as follows,H-1 h=0 E τ h ∼P π θ * ψ k (τ h ) -ψ * (τ h ) 2 ≤ H-1 h=0 E τ h ∼P π θ * ψ k (τ h ) -ψ * (τ h ) 1 ≤ H-1 h=0 τ h ψ k (τ h ) P π θ * (τ h ) -P π θ k (τ h ) + ψ k (τ h )P π θ k (τ h ) -ψ * (τ h )P π θ * (τ h )   ≤ 2HQ A √ λ D TV P π θ * (τ h ), P π θ k (τ h ) + 1 + 2 max s∈A |X s | Q A √ 7rβ √ λ H-1 h=0 E τ h ∼P π θ * ψ * (τ h ) (U k h ) -1 .The following lemma bounds the cumulative estimation error of the probability of trajectories. It can be proved via an ℓ 2 Eluder argument [38, 76, 77] . A significant portion of the proof is very similar to that of Proposition 4, involving an exchange of (•) and (•) * . We include the proof for completeness. Lemma 8. Under event E, for any h ∈ {0, . . . , H -1}, we have kD TV P π k θ ⋆ (τ H ), P π k θ k (τ H ) ≲ max s∈A |X s | Q A √ β γ rHK log 1 + dQ A K γ 4 .Here, a ≲ b indicates that there is an absolute positive constant c s.t. a ≤ c • b.Proof. Recall that, by the first inequality in Proposition 4, we have:D TV P π k θ ⋆ (τ H ), P π k θ k (τ H ) ≤ H h=1 τ H m k (ω h ) ⊤ M k h (x h ) -M ⋆ h (x h ) ψ ⋆ (τ h-1 ) π k (τ H )This is very similar to the inequality in Lemma 5, with the difference being that the quantities associated with the estimated model and the true model are exchanged. Since both correspond to a PSR, the analysis follows a similar series of steps. We will use analogous notation to Lemma 5. We index the future trajectory ω h-1 = (x h , . . . , x H ) by i and history trajectory τ h-1 = (x 1 , . . . , x h-1 ) by j. We denotem k (ω h ) ⊤ M k h (x h ) -M ⋆ h (x h ) as w i , ψ ⋆ (τ h-1) as x j , and π(ω h-1 |τ h-1 ) as π i|j .Define the matrix,Λ k h = λ 0 I + t<k E j∼P π t θ ⋆ x j x ⊤ jwhere λ 0 is a constant to be determined later.For any policy π, using a similar calculation as in Lemma 5, we have,τ H m k (ω h ) ⊤ M k h (x h ) -M ⋆ h (x h ) ψ ⋆ (τ h-1 ) π k (τ H ) = E j∼P π k θ ⋆ i π i|j w ⊤ i x j = E j∼P π k θ ⋆   i π i|j sign(w ⊤ i x j )w i ⊤ x j   ≤ E j∼P π k θ ⋆   ∥x j ∥ Λ † h i π i|j sign(w ⊤ i x j )w i Λ h  where the last line is the Cauchy-Schwarz inequality.Fix j = j 0 and consider the term: i π i|j0 sign(w ⊤ i x j0 )w i Λ h in the above. This term can be partitioned in the same manner as in Lemma 5 by simply using the definition of Λ h and expanding,i π i|j0 sign(w ⊤ i x j0 )w i 2 Λ h = λ 0 i π i|j0 • sign(w ⊤ i x j0 ) • w i 2 2 I1 + t<k E j∼P π k θ ⋆   i π i|j0 • sign(w ⊤ i x j0 ) • w ⊤ i x j 2   I2 .We bound each term separately. The process is nearly identical to the proof of Lemma 5, but we show it for completeness. √ I 1 is bounded by the sum of two terms,I 1 = λ 0 max z∈R d h-1 :∥z∥ 2 =1 i π i|j0 • sign(w ⊤ i x j0 ) • w ⊤ i z (a) ≤ λ 0 max ∥z∥ 2 =1 ω h-1 m k (ω h ) ⊤ M k h (x h ) -M ⋆ h (x h ) z π(ω h-1 |j 0 ) (b) ≤ λ 0 max ∥z∥ 2 =1 ω h-1 m k (ω h ) ⊤ M k h (x h )z π(ω h-1 |j 0 ) + λ 0 max ∥z∥ 2 =1 ω h-1 m k (ω h ) ⊤ M ⋆ h (x h )z π(ω h-1 |j 0 ),where step (a) is the definition of w i , π i|j0 , and the triangle inequality, and step (b) is the triangle inequality.Both terms can be bounded by the γ-well-conditioning assumption on θ k and θ * . Consider the first term,EQUATION≤ max∥z∥ 2 =1 x h 1 γ M k h (x h )z 1 π(x h |j 0 ) (b) ≤ 1 γ max ∥z∥ 2 =1 Q A h+1 ∥z∥ 1 γ (c) ≤ √ dQ A γ 2where step (a) is by the first condition in Assumption 1, step (b) is by the second condition of Assumption 1, and step (c) is by the fact that max z∈Rd h-1 :∥z∥ 2 =1 ∥z∥ 1 = d h-1 ≤ √ d and Q A h+1 ≤ Q A .In the above, note that we used the γ-well-conditioning of PSR θ k in both step (a) and step (b). The second term in √ I 1 admits an identical bound, simply by using the well-conditioning of the PSR θ k in the first step and θ * in the second step. Hence, we have thatEQUATIONNow, we consider the term I 2I 2 ≤ t<k E τ h-1 ∼P π k θ ⋆      ω h-1 m k (ω h ) ⊤ M k h (x h ) -M ⋆ h (x h ) ψ * (τ h-1 ) π(ω h-1 |j 0 )   2    ≤ t<k E j∼P π k θ ⋆ ω h-1 m k (ω h ) ⊤ M h (x h ) ψ ⋆ (τ h-1 ) -ψ k (τ h-1 ) π(ω h-1 |j 0 ) I3 + ω h-1 m k (ω h ) ⊤ M k h (x h ) ψ k (τ h-1 ) -M ⋆ h (x h )ψ ⋆ (τ h-1 ) π(ω h-1 |j 0 ) I4 2 =: t<k E j∼P π k θ ⋆ (I 3 + I 4 ) 2where the line follows by the fact that x ≤ |x| and the line follows from the triangle inequality by adding and subtracting mh (ω h ) M h (x h ) ψ k (τ h-1) inside the absolute value. We now bound each of I 3 and I 4 .First, we bound I 3 as follows,I 3 = ω h-1 m k h (ω h ) ⊤ M h (x h ) ψ ⋆ (τ h-1 ) -ψ k (τ h-1 ) π(ω h-1 |j 0 ) (a) = ω h-1 m k h-1 (ω h-1 ) ⊤ ψ ⋆ (τ h-1 ) -ψ k (τ h-1 ) π(ω h-1 |j 0 ) (b) ≤ 1 γ ψ k (τ h-1 ) -ψ ⋆ (τ h-1 ) 1 = 1 γ q h-1 ∈Q h-1 P θ k [q h-1 | τ h-1 ] -P θ * [q h-1 | τ h-1 ] ,where step (a) is since m(ω h ) ⊤ M h (x h ) = m(ω h-1 ) ⊤ , step (b) is by Assumption 1, and the final equality is by the definition of ψ.I 4 = ω h-1 m k (ω h ) ⊤ M k h (x h ) ψ k (τ h-1 ) -M ⋆ h (x h )ψ ⋆ (τ h-1 ) π(ω h-1 |j 0 ) (a) = ω h-1 m k (ω h ) ⊤ P θ k [x h | τ h-1 ] ψ h (τ h ) -P θ * [x h | τ h-1 ] ψ * h (τ h ) π(ω h-1 |j 0 ) = x h ω h m k (ω h ) ⊤ P θ k [x h | τ h-1 ] ψ h (τ h ) -P θ * [x h | τ h-1 ] ψ * h (τ h ) π(ω h |j 0 , x h ) π(x h |j 0 ) (b) ≤ 1 γ x h P θ k [x h | τ h-1 ] ψ h (τ h ) -P θ * [x h | τ h-1 ] ψ * h (τ h ) 1 π(x h |j 0 ) (c) = 1 γ x h q h ∈Q h P θ k [x h , q h | τ h-1 ] -P θ * [x h , q h | τ h-1 ] π(x h |j 0 )where step (a) is by the fact thatM h (x h )ψ h-1 (τ h-1 ) = P [x h | τ h-1 ] ψ(τ h ),as shown in Equation (28) , step (b) is by Assumption 1, and step (c) is since ψ h (τ h ) l = P θ q l h τ h . Combining the above, we have that,I 2 ≤ t<k E j∼P π k θ ⋆ (I 3 + I 4 ) 2 ≤ t<k E j∼P π k θ ⋆ 1 γ q h-1 ∈Q h-1 P θ k [q h-1 | τ h-1 ] -P θ * [q h-1 | τ h-1 ] + 1 γ x h q h ∈Q h P θ k [x h , q h | τ h-1 ] -P θ * [x h , q h | τ h-1 ] π(x h |j 0 ) 2 = 1 γ 2 • t<k E j∼P π k θ ⋆ q h-1 ∈Q h-1 P θ k [q h-1 | τ h-1 ] -P θ * [q h-1 | τ h-1 ] + 1 γ x h q h ∈Q h P θ k [x h , q h | τ h-1 ] -P θ * [x h , q h | τ h-1 ] π(x h |j 0 ) 2 (a) ≤ 1 γ 2 • t<k E j∼P π k θ ⋆   ω a h-1 ∈Q exp h-1 ω o h-1 P θ k ω o h-1 τ h-1 , ω a h-1 -P θ * ω o h-1 τ h-1 , ω a h   2 = Q exp h-1 2 γ 2 • t<k E j∼P π k θ ⋆ D 2 TV P u exp h-1 θ k ω o h-1 τ h-1 , ω a h-1 , P u exp h-1 θ * ω o h-1 τ h-1 , ω a h (b) ≤ 4 max s∈A |X s | 2 Q 2 A γ 2 • t<k D 2 H P ν h (π t ,u exp h-1 ) θ k (τ H ) , P ν h (π t ,u exp h-1 ) θ * (τ H ) ,where step (a) follows from the definition of Q exp h-1 (same as Lemma 5), and step (b) is because the Hellinger distance bounds the total variation distance and since Q exp h-1 ≤ 2 max s∈A |X s | Q A . Hence,| 2 Q 2 A β γ 2 ≲ max s∈A |X s | 2 Q 2 A β γ 2 ,where the second line is by the estimation guarantee of Lemma 4.Thus, we have,D TV P π k θ ⋆ (τ H ), P π k θ k (τ H ) ≤ H h=1 τ H m k (ω h ) ⊤ M k h (x h ) -M ⋆ h (x h ) ψ ⋆ (τ h-1 ) π k (τ H ) ≤ H h=1 E τ h-1 ∼P π k θ ⋆   ψ * (τ h-1 ) Λ † h i π i|j sign(w ⊤ i x j )w i Λ h   ≤ E τ h-1 ∼P π k θ ⋆   H h=1 ψ * (τ h-1 ) Λ † h i π i|j sign(w ⊤ i x j )w i Λ h   (a) ≤ E τ h-1 ∼P π k θ ⋆   H h=1 ψ * (τ h-1 ) 2 Λ † h H h=1 i π i|j sign(w ⊤ i x j )w i 2 Λ h   (b) ≤ α • E τ h-1 ∼P π k θ ⋆   H h=1 ψ * (τ h-1 ) 2 Λ † h   ≤ α • H h=1 E τ h-1 ∼P π k θ ⋆ ψ * (τ h-1 ) 2 Λ † h ,where step (a) is by the Cauchy-Schwarz inequality and step (b) is by the bound established above. Since the total variation distance is bounded above by 2, we haveEQUATION   .Finally, the proof is completed by summing over k using the elliptical potential lemma as follows, K k=1EQUATION≤ √ K α K k=1 H h=1 min E τ h-1 ∼P π k θ ⋆ ψ * (τ h-1 ) 2 Λ † h , 4/α 2 (b) ≤ √ KH α (1 + 4/α 2 )r log(1 + K/λ 0 ) (c) ≲ max s∈A |X s | Q A γ rKHβ log(1 + K/λ 0 ) (d) ≲ max s∈A |X s | Q A γ rKHβ log(1 + dQ A K/γ).Here, step (a) is uses the relationship between the ℓ 1 and ℓ 2 norms∥•∥ 1 ≤ √ d ∥•∥ 2 .Step (b) is by the elliptical potential lemma ([35, Lemma 14] ; see also [96] [97] [98] ). Step (c) uses the bound on α established above and the fact that 1 + 4/α 2 is bounded by an absolute constant. Step (d) uses the definition of λ 0 and the fact that 28(1 + 4/α 2 ) is bounded by an absolute constant.Using the two lemmas above, we are now ready to show thatK k=1 V b k θ k (π k ) = O( √ K).The argument is identical to [35, Lemma 6] and does not require modification for generalized PSRs. We recount the argument for completeness. Lemma 9. Under the event E, with probability at least 1 -δ, we have:K k=1 V b k θ k (π k ) ≲ √ r + Q A √ H γ max 2 s∈A Q 2 A H √ drHβKβ 0 γ 2where β 0 = max{log(1 + K/λ), log(1 + dQ A K/γ)}, and λ = γ max s∈A |Xs|Q A β max{ √ r,Q A √ H/γ} √ dHProof. First, we note that, where the second line is by the Elliptical potential lemma ([35, Lemma 14] ; see also [96] [97] [98] ).V b k θ k (π k ) = τ P π k θ k (τ ) b k (τ ) = τ P π k θ * (τ ) b k (τ )+ τ (P π k θ k (τ )-P π k θ * (τ )) b k (τ ) ≤ V b k θ * (π k )+D TV P π k θ k , P π k θ * ,We now return to boundingK k=1 V b k θ k (π k ).For convenience we define β 0 := max{log(1 + K/λ), log(1 + dQ A K/γ)} and we choose λ as follows,λ = γ max s∈A |X s | 2 Q A β max{ √ r, Q A √ H/γ} √ dH .We have, In addition, the algorithm terminates with a sample complexity of,K k=1 V b k θ k (π k ) ≤ K k=1 V b k θ * (π k ) + K k=1=   1 + Q A max{ √ r, Q A √ H/γ} √ dH γ   2 max s∈A |X s |Q A H √ rKββ 0 γ ≲   1 + Q A √ dH max √ r, Q A √ H/γ γ   max s∈A |X s |Q A H √ rKββ 0 γ ≤ √ r + Q A √ H γ max s∈A |X s |QÕ r + Q 2 A H γ 2 rdH 3 max s∈A |X s | 2 Q 4 A β γ 4 ϵ 2 .Proof. By Propositions 6 to 8, the event E occurs with high probability, P [E] ≥ 1 -3δ. Suppose E holds. Then, by the upper confidence bound established in Corollary 4, if Algorithm 1 terminates, then the following must hold, ∀π, D TV (P π θ ϵ (τ H ),P π θ * (τ H )) = 2 max R V R θ ϵ (π) -V R θ * (π) ≤ V b ϵ θ ϵ (π) ≤ ϵ,where the maximization is over reward functions R : H H → [0, 1]. The last inequality is simply the termination condition of Algorithm 1.where the inequality follows from the fact that π = arg max π V R θ ϵ (π) and by Corollary 4. Recall that by Lemma 9, we have,K k=1 V π k θ k ,b k ≲ √ r + Q A √ H γ max s∈A |X s | Q 2 A H √ rdHKββ 0 γ 2 .By the pigeon-hole principle and the termination condition of Algorithm 1, the algorithm must terminate withinK = Õ r + Q 2 A H γ 2 rdH 2 Q 4 A max s∈A |X s | 2 β γ 4 ϵ 2episodes. Since each episode contains H iterations, this implies a sample complexity ofK = Õ r + Q 2 A H γ 2 rdH 3 Q 4 A max s∈A |X s | 2 β γ 4 ϵ 2 .This concludes the proof of Theorem 4.K Proof of Theorem 5: UCB Algorithm for Generalized PSRs (Game Setting)Theorem (Restatement of Theorem 5). Suppose Assumption 1 holds. Letp min = O δ KH H h=1 |X h | , λ = γ max s∈A |Xs| 2 Q A β max{ √ r,Q A √ H/γ} √ dH , α = O Q A √ Hd γ 2 √ λ + max s∈A |Xs|Q A √ β γ, and let β = O(log Θ ε ), where ε = O( pmin KH ). Then, with probability at least 1 -δ, Algorithm 2 returns a model θ ϵ and a policy π which is an ε-approximate equilibrium (either NE or CCE). That is,V i θ * (π) ≥ V i, † θ * (π -i ) -ε, ∀i ∈ [N ].In addition, the algorithm terminates with a sample complexity of,Õ r + Q 2 A H γ 2 rdH 3 max s∈A |X s | 2 Q 4 A β γ 4 ϵ 2where the final inequality is since D TV (P π θ ε (τ H ), P π θ * (τ H )) ≤ ε/2 for any π. Thus, V i, † θ ε (π -i ) ≥ V i, † θ * (π -i ) -ε/2. Putting this together, we have,V i θ * (π) ≥ V i θ ε (π) -ε/2 = V i, † θ ε (π -i ) -ε/2 ≥ V i, †θ * (π -i ) -ε. Hence, π is an ε-approximate equilibrium (either NE or CCE).• It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to(a) 


Decision: This paper proposes a fairly general formulation of sequential decision problems that exploits so-called “information structure,” which is essentially a catch-all term to describe conditional dependencies of “state” variables and “agent observation” variables on past variables. The key result is a characterization (upper bound) of the sample complexity of RL in such settings in a way that exploits the properties of the graphical model of this information structure. The reviewers raised a number of questions, but the exchange with the reviewers seems to have resolved most of these issues.

On my reading of the paper, however, there is a significant deficiency that makes the paper fully unacceptable unless it is addressed by the authors. There is a massive body of literature on exploiting the variable independence structure (in action, state-dynamics and observation space) of MDPs, POMDPs, DEC-POMDPs, etc. using factored MDP representations. The authors claim that problems have only been studied that assume uniform/regular independence structure or ignore it altogether. Nothing could be further from the truth. For example, the rich literature on using graphical models to represent MDPs, POMDPs, etc. using dynamic Bayesian networks (DBNs) does exactly what the authors claim does not exist. Moreover, numerous algorithms for solving sequential decision problems in a way that exploits these representations have been proposed for the past 30 years (at least since 1994). In addition, various papers study the RL variants of these problems (sometime focused on regret analysis, sometimes sample complexity).

The literature is too broad to do justice here, but for example, see:

* The extensive survey of very early work in this area: Decision-Theoretic Planning: Structural Assumptions and Computational Leverage, Boutilier, Dean, Hanks, J. of AI Research, 1999.

* The voluminous body of work that followed extending these to richer classes of MDPS, POMDPs, dec-POMDPs, games, etc.

* See also early work on influence diagrams (cited in the work above) that focuses especially on observation structure.

* From an RL perspective, the work on regret analysis and sample complexity of RL in factored domains. Just one example: Osband, van Roy, NeurIPS 2014.

I do believe the contribution of this paper is valuable due to the level of generality in brings to the formulation and analysis. But the lack of awareness of precedent is scientifically unacceptable. Unless this paper explains how it differs from past work (and, ideally, how it generalizes existing models, which I think it does), it cannot be published in a forum like NeurIPS.

I note the reviewers raise a number of other questions that should be addressed in revision as well.

Reviews: review: paper_summary: paper_summary: This paper studies the tractability of modeling and learning general sequential decision-making problems with an explicit representation of information structure. This gives a unifying framework that captures a range of commonly studied RL models. Through a graph-theoretic analysis it characterizes the complexity of observable dynamics in sequential decision-making problems. It then gives an upper bound on the sample complexity of learning these problems characterized by their information structure.
strength_weakness: strength_weakness: - 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. 
- The results of the paper are theoretical in nature, and it could benefit from empirical results to demonstrate the effectiveness of the proposed algorithm and framework on experiments / simulations.
questions: questions: - 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?
- The paper shows that the sample complexity upper bound in Theorem 3 for POST implies a reasonable bound for the case of $\alpha$-weakly POMDPs. 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?
limitations: limitations: The author(s) have adequately addressed the limitations of the work.
paper_summary: paper_summary: The paper presents a new representation of sequential decision making problems with an information structure. They show that the information structure can be used to estimate the complexity of the decision-making problems and can guide learning algorithm development.
strength_weakness: strength_weakness: 1. If I understood correctly, the authors are dealing with finite state and action spaces and the complexity measure is effectively a rank of a certain matrix that they construct. If the state or the action spaces are infinite or continuous then the measure becomes infinite for all systems and we cannot use the measure for judging complexity. If this is so, I see it as a major weakness
1. Presentation can be improved. It’s hard to understand what different concepts mean, say core tests. Can a “layman” summary be given after these kinds of definitions?
1. 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. 
1. Some claims need for further clarification or justification. For example, I am not sure that Figure 1 is fully substantiated. Hopefully, the authors can clarify
questions: questions: 1. The dynamics matrix seems to bear resemblance to the Hankel operator for linear systems theory in control literature. The Hankel operator is mapping past inputs to feature outputs, since the system is linear its information structure is rather simple.  The rank of the Hankel operator is actually a well-established complexity measure for linear systems. It would be good to understand if there’s more than just some general similarity. 
1. Is there an example of a system that is POST but not POMG or not dec-POMDP as claimed in Figure 1?
1. Are the authors deal with finite state and action spaces? It seems that the dynamics matrix with probabilities of potential futures and histories is finite-dimensional, but it’s not clearly stated
1. “This   assumption is often unrealistic, since general systems may not have “states” per se, and observations may be generated with more complex dependencies.” - I am bit confused what does it mean that the system may not have states. Can you add an example here? I think that POMDPs are generally quite realistic when it comes to single agent systems hence this comment is confusing for me. 
1. Please define dec-POMDP, POMG before using the acronyms. Or at least define them in the Appendix.
1. Why in def 5 we need to remove all the arrows pointing to actions? Can actions be dependent on history?
1. What’s $\sigma$ in Def 6?
1. 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?
limitations: limitations: limitations are discussed
paper_summary: paper_summary: This paper proposes an abstract model of RL with information structures. Under this mode, the paper investigates the necessary conditions for sample-efficient learning.
strength_weakness: strength_weakness: (1) It is hard to identify the technical novelty & originality of this paper. The POSTs and POSGs are special cases of "generalized PSRs", but the so-called "generalized PSR" is largely a direct abstraction of the analysis framework of Liu et al. 2022b. The algorithm and the proofs are also largely patching the analysis in the previous papers (in particular, Liu et al. 2022b).

(2) It is not clear what new concrete tractable class does this paper identify. Tractable POMDP classes and POMG classes have already been studied in previous works. Several examples of information structure are provided, but there isn't a definition of a new, meaningful, and tractable problem class.

Overall, this paper indeed provides a general framework, but it seems that generality is the only advantage of this framework. However, "general framework" cannot be an excuse. After all, there have already been several general frameworks for sequential decision making. For example, for model-based learning, the so-called Decision-Estimation Coefficient characterizes the statistical complexity of *any* model class [1,2,3,etc]. The SAIL framework of Liu et al. (2022b) is more concrete and it also applies to a broad class of sequential decision making problems. The authors have to justify what is the significance of this framework other than its (vacuous) generality.

[1] Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making.

[2] Dean Foster, Dylan J Foster, Noah Golowich, and Alexander Rakhlin. On the complexity of multi-agent decision making: From learning in games to partial monitoring.

[3] Dylan J Foster, Noah Golowich, and Yanjun Han. Tight guarantees for interactive decision making with the decision-estimation coefficient.
questions: questions: N/A
limitations: limitations: N/A

Comments: title: Thank you
Questions & more minor comments
comment: We sincerely thank the reviewer for their response. We are delighted that you found most of your questions were well addressed. We also greatly appreciate you being engaged with the discussions with the other reviewers and are glad to hear you found our responses to their comments to be compelling as well.

We would like to thank you again for your feedback and your engagement! If you have any remaining questions before the end of the rebuttal period, please don't hesitate to ask.
Thank you for your continued engagement.

> On the flip side, Theorem 3 seems to indicate that there are non POMDP information structures of similar to POMDP complexity (if I understood correctly). Furthermore, complexity is not directly defined by the cardinality of the state-space, which is an advantage.

Yes, that's correct. We are glad that you appreciate this.

> In summary, I see your point and I agree with your claims in Figure 1. I recommend adding a remark on MDP/POMDP reformulations in the Appendix. I think it's a more complicated question and maybe warrant a further investigation. In any case, seems to be out of scope of this work.

We appreciate this feedback. We agree that this will be interesting, and we will aim to add such a discussion to the appendix.

> I will have to think a bit more about the score, apologies if this will be after the rebuttal deadline.

We understand. If you have any further questions or concerns before the discussion period ends, please don't hesitate to ask! Thank you again for your questions and your feedback.
Dear reviewer,

We appreciate your continued engagement and are glad that we were able to address your concerns.

On your question about the weakly-revealing condition in these cases: the weakly revealing condition is defined with respect to the information structural state $\mathbb{I}_h^\dagger$ at each time step. That is, $m$-step futures must be weakly-revealing for the information structural state. More precisely, for each observable time step $h$, for two different distributions over the information structural state $\nu_1, \nu_2 \in \mathcal{P}(\mathbb{I}_h^\dagger)$ (with disjoint support), the distributions of $m$-step future observations that they observe are different. 

The importance of this condition is its generalization of existing observability conditions, which are defined with respect to an assumed Markovian state. Our analysis extends this to arbitrary information structures and identifies the quantity that the observability condition (which is necessary) must "reveal". That is, it identifies the collection of latent variables in the system that future observations must be sufficiently informative about to enable sample-efficient learning.

For example, in the case of the "point-to-point real-time communication with feedback" information structure, the weakly-revealing condition states that future observations (which include the encodings/symbols and future sources $y_t, x_{t+1}, y_{t+1}, ...$) must be weakly-revealing about the source $x_t$. In the mean-field information structure, future observations (which include the local states of agents $s_{t+1}^1, ..., s_{t+1}^n, ...$) must be weakly revealing about the mean-field state at the previous time point $s_t^{mf} = n^{-1} \cdot \sum_i s_t^i$.

We thank you again for your engagement with our work and for your feedback which has helped us improve the presentation of the paper.
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.
I see your point regarding the formulations and reformulations. I agree that increasing the size of the system (MDP, POMDP) is not a favorable solution.

> However such reformulations result in an explosion in model size, losing the ability to analyze statistical complexity.

This is not a straightforward claim to me. I am not sure that the same size reformulations would not exist for say POMDPs (in the single agent setting). Especially, if we are talking about specific examples. 

On the flip side, Theorem 3 seems to indicate that there are non POMDP information structures of similar to POMDP complexity (if I understood correctly). Furthermore, complexity is not directly defined by the cardinality of the state-space, which is an advantage.  

In summary, I see your point and I agree with your claims in Figure 1. I recommend adding a remark on MDP/POMDP reformulations in the Appendix. I think it's a more complicated question and maybe warrant a further investigation. In any case, seems to be out of scope of this work.

I will have to think a bit more about the score, apologies if this will be after the rebuttal deadline.
Thank you for the prompt response. Apologies for the misunderstanding, as we thought you were looking for a demonstration of how Dec-POMDP can be represented as a POST.

There is essentially no restriction on the type of dynamics that can be represented by the POST/POSG framework since it allows for *arbitrary* information structures, arbitrary variable structures, and arbitrary transition dynamics. Any system that does not have a Markovian state is an example of a system that can be represented as a POST but not a POMDP/Dec-POMDP/POMG. Figure 2 and Appendix D give some examples of this (e.g., two examples we give are a mean-field information structure and an information structure associated with a point-to-point real-time communication with feedback). However, we emphasize that the key is not merely the generality of the model, but its ability to represent structure in a way that enables a richer analysis.

You may be familiar with the Witsenhausen intrinsic model from the control literature: our POST/POSG framework is closely related and builds on it by introducing additional components to better-represent the reinforcement learning setting and notions of partial-observability with respect to the learning algorithm.

Your question about reformulations is important to this discussion. Of course, it will often be possible to re-formulate a problem as POMDP (or even an MDP). For example, a system with arbitrary dependence on the past can be reformulated into an MDP by defining the state as an encoding of the entire past at each point in time. Similarly, a POMDP can be translated to belief-MDP. However such reformulations result in an explosion in model size, losing the ability to analyze statistical complexity. Thus, representing information structure explicitly in a general model is essential to analyzing statistical complexity in terms of the true model structure.

Although POST/POSG can represent arbitrary sequential decision-making problems in environments with arbitrary dynamics and information structures, many instances of POST/POSG will have unfavorable statistical complexity. The primary contribution of our work is to characterize the statistical complexity of arbitrary decision-making problems as a function of the information structure of the underlying system dynamics.
Unfortunately, this does seem to answer my question. If I understood correctly, this shows Dec-POMDP $\subseteq$ POST, but not Dec-POMDP $\subset$ POST. This doesn't show that there's a POST system that's not dec-POMDP. Moreover, there may be a system that you can formulate as POST that doesn't have dec-POMDP form, but a reformulation gives dec-POMDP. Again this may be a naive question, but it is important to answer.
Thank you for the continued discussion and engagement with our work! We are delighted that many of your concerns have been addressed.

We are eager to answer your remaining questions and address any remaining concerns. First, we point to Appendix D which provides detailed discussion on the examples of information structures depicted in Figure 2. In particular, for each example of information structure depicted in Figure 2, we provide
1. a formal description of how it can be represented in the POST/POSG framework (i.e., what is the variable structure, information structure, etc., as per Def 4), and
2. a discussion of what our main results imply about the statistical complexity of each information structure. That is, it identifies information structural state and its size (hence, the statistical complexity, as per Theorem 3).

With the additional content page allowed in the camera-ready version, we will incorporate a revised version of this section into the main body of the paper, which we hope will help to ground our general and abstract results in concrete examples.

> This may be a trivial and a naive question, but it is not clear to me that POST structure is actually more general than dec-POMDP without a proof. In any case, it would be a good illustration if it is a trivial question

The fact that POST/POSG captures special cases like Dec-POMDP is indeed direct, given the definition. We hope that reading through Appendix D will help elucidate how the POST/POSG framework captures arbitrary information structures, including commonly studied ones like Dec-POMDPs. In particular, we point to the subsection titled "Illustration: translating to the POST/POSG framework" in Appendix D which works through how a POMDP can be explicitly represented within the POST framework.

To keep the response self-contained, we also provide a summary of how Dec-POMDP can be represented as an instantiation of a POST here.

---

**Representation of Dec-POMDP in the POST framework.**

Consider a $n$-agent Dec-POMDP given by $(\mathbb{S}, \\{\mathbb{O}^i\\}\_{i \in [n]}, \\{\mathbb{A}^i\\}\_{i \in [n]}, \mathrm{Tr}, \\{\mathrm{Ob}^i\\}\_{i \in [n]})$. The sequence of variables are given by
$$s\_1, o\_1^1, ..., o\_1^n, a\_1^1, ..., a\_1^n, s\_2, o\_2^1, ..., o\_2^n, a\_2^1, ..., a\_2^n, ...$$
Note that the order of observation or action variables for different agents within one time step is arbitrary since they occur simultaneously. In the POST framework, we reindex and denote all variables by "$X_t$". That is, this sequence is denoted by $X\_1, X\_2, ...$, where each $X\_t$ is either a state or an observation/action for some agent. In the POST framework, the variable structure is defined in terms of the variable indices $\mathcal{S, O, A} \subset [T]$, where $T$ is the total time horizon (counting each variable separately). However, we can slightly abuse notation by indexing variables via the notation $s\_t, o\_t^i, a\_t^i$ in order to avoid the messiness of translating each into an integer index.

With this, we can define each component of the POST:
1. Variable structure: the "system variables" are $\mathcal{S} = \\{s\_t, o\_t^i, t \in [T], i \in [n] \\}$ (i.e., all state variables and observation variables for all agents); the "action variables" are $\mathcal{A} = \\{a\_t^i, t \in [T], i \in [n]\\}$.
2. Information structure: the information set of the state variable contains the state variable and joint action at the previous time step, $\mathcal{I}(s\_t) = \\{s\_{t-1}, a\_{t-1}^1, ..., a\_{t-1}^n\\}$; the information set for observation variables of each agent are contains the state variable at that time step, $\mathcal{I}(o\_t^i) = \\{s\_{t}\\}$; the information set for the action variables of each agent contains that agent's history of observations and actions, $\mathcal{I}(a\_t^i) = \\{o\_{1:t}^i, a\_{1:t-1}^i\\}$.
3. System kernels: Each system variable in $\mathcal{S}$ is either a state variable or an observation variable for some agent. If it is a state variable, the system kernel is the state transition kernel $\mathrm{Tr} \in \mathcal{P}(\mathbb{S} | \mathbb{S} \times \mathbb{A})$. If it is an observation variable, then it is the emission kernel corresponding to that agent $\mathrm{Ob}^i$.
4. Decision kernels: These are the policies of each agent. For each action in $\mathcal{A}$ there is a decision kernel. In the case of Dec-POMDPs, each action corresponds to a time point $t$ and an agent $i$. It is defined as a kernel mapping $(o\_{1:t}^i, a\_{1:t-1}^i)$ to an action in $\mathbb{O}^i$.
5. Observability: The observable system variables are $\mathcal{O} = \\{o\_t^i, t \in [T], i \in [n] \\} \subset \mathcal{S}$.
6. Reward function: this is an arbitrary function of the observables and actions (of all agents). In the case of a team, the reward is the same across all agents.

---

We hope this clarifies things. Please let us know whether your concerns are address or if you have any additional questions.
Dear reviewer,

Thank you for your response. We appreciate your constructive engagement with us during the reviewer discussion period. We are glad that our elaboration and explanation makes sense to you. We are eager to address your remaining concern.

> A concern is that the current organization seems to emphasize more on the rather abstract formulation, instead of providing more examples and concrete results. 

This point is well taken. The current version of the paper indeed emphasizes the abstract formulation over concrete examples. We fully agree on the importance of discussing concrete examples to better emphasize the significance of the results and provide a more clear and pedagogical presentation. **We will include a new section in the paper dedicated entirely to doing this**. We appreciate this feedback and we believe it improves the paper.

First, we would like to briefly explain our choice regarding the current organization of the paper. We initially did have a section in the paper dedicated to doing exactly what you describe: a formal description of all the examples of information structures in Fig 2 together with a discussion of how our results can be applied to each information structure. However, we had to move this to the appendix due to space constraints. With the additional content page allowed in the camera-ready version, we will add a revised version of this section back to the main body of the paper, which we hope addresses your concern and grounds the general abstract results of the paper in concrete examples.

We point to Appendix D in the paper, "Examples of Information Structures and their Rank", which perhaps provides exactly the type of discussion you are describing. For each information structure depicted in Fig 2, it provides:
1. a formal description of how it can be represented in the POST/POSG framework (i.e., what is the variable structure, information structure, etc., as per Def 4), and
2. a discussion of what our main results imply about the statistical complexity of each information structure. That is, it identifies information structural state space and its size (hence, by Theorem 3, the statistical complexity).

To give an idea of this discussion (in case you are unable to view the paper in detail at the moment), we briefly summarize the discussion on the "point-to-point real-time communication with feedback" information structure (Fig 2 c) below. Please see the full section in the appendix for details on the other information structures.

---
Let $x\_t$ be a Markov source. At time $t$, the encoder receives the source $x\_t \in \mathbb{X}$ and encodes sending a symbol $z\_t \in \mathbb{Z}$. The symbol is sent through a memoryless noisy channel which outputs $y\_t$ to the receiver. The decoder produces the estimate $\hat{x}\_t$. The output of the noisy channel is also fed back to the encoder. The encoder and decoder have a full memory of their previous actions (i.e., "messages"). 

The sequence of variables is $x\_t, z\_t, y\_t, \hat{x}\_t, x\_{t+1}, z\_t, ...$, and map onto the index sets $\mathcal{S, A, O}$. $x\_t$ and $y\_t$ are (observable) system variables, and hence in $\mathcal{S} = \mathcal{O}$. $z\_t$ and $\hat{x}\_t$ are action variables (for the encoder and decoder, resp.), and hence are in $\mathcal{A}$. The information structure is given by: 
$$\mathcal{I}(x\_t) = \\{x\_{t-1}\\}, \mathcal{I}(z\_t) = \\{x\_{1:t}, y\_{1:t-1}, z\_{1:t-1}\\}, \mathcal{I}(y\_t) = \\{z\_t\\}, \mathcal{I}(\hat{x}\_t)=\\{y\_{1:t}\\}.$$ 

By Theorem 1, the information structural state is given by:
$$\mathcal{I}^\dagger(x\_t) = \\{x\_{t-1}\\}, \mathcal{I}^\dagger(z\_t) = \\{x\_t\\}, \mathcal{I}^\dagger(y\_t) = \\{x\_t, z\_t\\}, \mathcal{I}^\dagger(\hat{x}\_t) = \\{ x\_t \\}.$$

Thus, by Theorem 1, the rank of the observable dynamics of this information structure is bounded by $r \leq |\mathbb{X}| |\mathbb{Z}|$.

(Note, here, that $\mathcal{I}^\dagger(\cdot)$ means $\mathcal{I}\_h^\dagger$ for $h$ corresponding to the variable "$\cdot$"; that is, at the time point $h$ corresponding to "$\cdot$". Similarly for $\mathcal{I}^\dagger(\cdot)$. This is explained in Appdx D.)

---

Please let us know whether this addresses your concern or if you have any remaining questions.

> Examples in Figure 2 need more explanation and discussion, and to me, they are much more interesting than Section 4 (which is analogous to the existing literature in my opinion).

On this, we briefly note that Section 4 is essential for our statistical complexity results, and generalizes existing PSR construction results and learnability conditions in the literature to arbitrary information structures. In particular, the $\mathcal{I}^\dagger$-weakly-revealing condition is crucially with respect to the information structural state---a new quantity we define in this work---rather than some assumed Markovian latent state (e.g., as in the case of existing conditions for learnability of POMDPs).
Thank you for your response. The formulation of a "more general notion of partial observability" does make more sense to me. 

A concern is that the current organization seems to emphasize more on the rather abstract formulation, instead of providing more examples and concrete results. Examples in Figure 2 need more explanation and discussion, and to me, they are much more interesting than Section 4 (which is analogous to the existing literature in my opinion). It will be clearer if you can formally define the classes (a) - (d) in Figure 2, and also write down how Def 6 becomes in these classes. I believe this will address my concern (2). 

If you can provide a more thorough discussion on the examples of specific information structures, I am willing to raise my score to 5 and favor the acceptance of this paper.
I would like to thank the authors for the detailed response. I think most of my questions are well addressed. I don't have any further questions.

I think the author has given a detailed response to Reviewer w9Kg regarding possible extensions to continuous spaces, the importance of information structure and the potential practical relevance of the proposed complexity measure. Reviewer Ugr3 has pointed out a few prior work on general frameworks for statistical complexity of sequential decision making problems. I agree that the paper could benefit from better explanation of its relation to related works in this area. I think the authors have given a reasonable response to situate this work with respect the literature in the rebuttal. 

I still think this is an interesting work and I will keep my score for the moment.
Thank you for a detailed response! Many of the concerns have been addressed, but I haven't found an answer to the following question:

> Is there an example of a system that is POST but not POMG or not dec-POMDP as claimed in Figure 1?

This may be a trivial and a naive question, but it is not clear to me that POST structure is actually more general than dec-POMDP without a proof. In any case, it would be a good illustration if it is a trivial question
**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.