On the Role of Information Structure in Reinforcement Learning for Partially-Observable Sequential Teams and Games
Authors: Awni Altabaa
Zhuoran Yang
Venue: NeurIPS 2024 poster (2024)
Keywords: reinforcement learning
partially-observable
information structure
sequential decision-making
causal
causal structure
graphical model
Primary area: reinforcement_learning
TL;DR: This paper studies how the structure of causal dependencies among system variables dictate the statistical complexity of RL.

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.

On the Role of Information Structure in Reinforcement Learning for Partially-Observable Sequential Teams and Games
Awni Altabaa
Zhuoran Yang Department of Statistics & Data Science Yale University zhuoran.. yangraala. edu
Department of Statistics & Data Science
Yale University
awni wwn..aatabba@yall.ccmm edu
Abstract
In sequential decision-makes 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 struc- ture, while more general models like predictive state representations do not explic- itly model the information structure. By contrast, real-world sequential decision- making problems typically involve complex and time-varying interdependence of system variables, requiring a rich and flexible representation of information struc- ture. In this paper, we formalize novel reinforcement learning model which ex- plicitly represents the information structure. We then use this model earry out an information-struutiee structural analysis of the statistical complexity of general sequential decision-making problems, obtaining characterization via graph-theoretic quan- tity of the DAG representation of the information structure. We prove an upper bound the sample complexity of learning general sequential decision decision-making problem in terms of its information structure by exhibiting an algorithm achiev- ing the upper bound. This recovers known tractability results and gives a novel perspective on reinforcement learning general sequential decision-makinn prob- lems, providing systematic way of identifying new tractable classes of problems.
Introduction
The information structure of sequential decision decision-making problem is description of the causal dependencies between system variables. 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 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-14].
In general, sequential decision-makinn problems with arbitrary causal dependencies between system variables can be computationally and statistically intractable in both control and learning settings [3, 15]. 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 sufficient statistic for the system's 's evolution. These structural assumptions enable practical planning and learning algorithms, for example based on dynamic programming [16, 17]. Although such restricted model classes 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.
38th Conference Neural Information Processing Systems (NeurIPS 2024).

---

The concept of information structure is also fundamental to studying the phenomenon of partial observability. In general, partial observability refers to situations where system's '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 restrictive form of this phenomenon. For example, in a Partially-Obervve standard model of partial observability it is assumed that Markovian state exists and that each observation is a noisy measurement of the current state. This assumption often unrealistic, as general systems may not have clearly defined "states", and observations may be generated by more complex dependencies. Information structure provides 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.
Markov Decision Process (POMDP) the
The highly-regulas information structures of classical models make analysis more tractable, enabling favorable theoretical results [e.g., 18-22] and driving notable empirical success across a wide range of domains [e.g.. 23-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 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 -raiing problems, where the system evolves according to complex and time-variig 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 rep- resentation of information structure, and study the role of information structure in the statisti- cal complexity of reinforcement learning. Explicitly modeling information structure allows to identify a broader class of tractable decision problems and ultimately develop more tailored reinforcement learning approaches that leverage this structure.
Summary of Contributions
A model for representing information structure. We propose partially-observable sequential teams (POST) and partially- observable sequential games (POSG) as general models that contain an explicit representation of information structure as part of the problem specification. This forms unifying frame- work that enables an analysis of the role of information struc- ture in RL and captures commonly studied RL models as spe- cial cases, including MDPs, Markov teams/games, POMDPs, (Figure 1). The models introduced in this work draw inspiration from Witsenhausen's 's intrinsic model [1] and its variants from the control literature [29, 30), with added elements to model partial observability in the con- text of reinforcement learning.
POSG
POMG
Dec-POMDP
POMDP
and
MDP
POST
A depiction of the generality of our proposed mod- els. POSTs and POSGs capture MDPs. POMDPs, Dec-POMDPs. and POMGs as special cases.
Figure 1:
Theoretical analysis of sequential decision-making through information structure. We characterize the complexity of the observable dynamics of any sequential decision-making prob- lem through graph-theoretic analysis of the information struc- ture. Moreover, we propose a generalization of predictive state representations--hice may be of by exploiting informa-
independent interest-ant construct such a representation for tion structure. This provides robust and efficient parameterization amenable to learning.
Learning theory & information-structue 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 graphical representation that can be thought of as an effective 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 robust representation amenable to learning. In doing so, identify a larger class of statistically tractable reinforcement learning problems.
analysis of statistical complexity. We prove an upper
Related Work.
We provide a detailed discussion of related work in Appendix B.

---

2
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.
2.1 Generie Sequential Decision Making Problems
Consider a controlled stochastic process (X1..... XH). where X, is a random variable corresponding to the variable at time h. At each time & E [f]] the variable XA, 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, {XA hA, A,A,P) P), where H is the time horizon, X,, is the variable space at time h, O C [H] is the index set of observations (i.e., XA, is an observation if h E O), A c [H] is the index set of actions, and PP = (Pahee is a set of probability kernels which describes the probability of any trajectory æ1..... nH given the actions, P Plz, 8 E O} (Ir, E A)] Tn-1]. 1.. A choice of policy æ induces a probability distribution IP" on X x ... x X The objective of the agent(s) is to choose a policy which maximizes their expected reward V²((T) = E= [R(X1,.. XH)].
Ihee Ph [2n Fi,...., Ih-
Let 1 = II x denote the space of histories at time h and F = II X, denote the space futures at time h. Similarly, let H& = obs (HI,) II. X, denote the observation component of histories and let HHIy = act((H,) = IILe x, denote the action component. The observation and action components of the futures, F% and I1, respectively, are defined similarly. Here, obs()) and act(-) extract the observation and action components, respectively, of any trajectory.
We define the system dynamics matrix Dj E R[HA| as the matrix giving the probability of each possible pair of history and future at time given the execution of the actions, [Dn]T,,u
I' [T] IP [T w8. do(TT w.]]], where Th, is the history, Wh the future, and Th Th wh, wh separate the history and future into observation components and action components.
The rank of the dynamics of a sequential pacision-making problem is measure of its complexity. It defined as the maximal rank of its dynamics matrices.
Definition (Rank of dynamics). The rank of the dynamics (Da)net is = max (a))
2.2 Generalized Predictive State Representations
Predictive state representations (PSR) [31, 32] are representation of dynamical systems and sequen- tial decision-making problems based on predicting future observations given the past, without explic- itly modeling 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 neces- sary to capture POSTs/POSGs (introduced in Section 3), but may also be of independent interest.
The "PSR rank" of a sequential decision- Docision-making problem coincides with the rank of its dynamics (Definition 1). Denote r == rank( D,.). At the heart of predictive state representations is the concept of "core test sets." A core test at time h is a 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. dn (gh..... 9h } C F3, such that the submatrix Dj, [Qn]] E R FRll is full-rank.
Definition 2 (Core test sets). A core test set at time h is a subset of d,, 2 Th futures, Q2 =
The dy -d-menssional vector thn (Tr. = (F(T.. I.l................ PlTR, ") serves as a sufficient statistic for computing the probability of any future conditioned The 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 s/n via 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 (i)ne(H) Hi where A, O partition [H] into actions and observations, respectively. Then, generalized predictive state representation for this sequential decision maaisiinnmakingg problem is a tiple (LQn (QQnoohhsH-s QH (Mahgshh-11> 3/)) satisfying
P [1 [Ii,,..,,,4 Hm] (N() M ( Mi (x1)
(1)
(n(11,..., vn) = Ma(Tx) M1 (x) Vo. Vh,
(2)
3

---

where M₁ : Xp + Rdaxdd 1, 0H : XH + Rd 1. and Φo = (0))
An important condition for the learnability of PSR models, which was used in prior work [including 33-35], is the so-called "well-conditioingg assumption". We state the analogous assumption for our generalized PSR model below. For core test set QA. let Q% act(Qu) be the set of core action sequences, let QA max, [QA1 be the number of core action sequences, and let d max, da.
Assumption 1 conditioned for y > 0 if. for any h E [H] and any n, it satisfies
generalized PSR). A generalized PSR model is said to be y-well
Σ T(wn) (WN) 1
Σ
1
max
max =ER
SER"A | WAEF
|| | IA ZAEXA
where (ww))) = (HH)) ( M ... M (1h+1)))))))))))1)))))(()) and V wh: Eug Twh wR) = 1.
To understand this condition, recall that m.,(w) T () = = P (h, Thus, we can interpret z as the error in estimating the prediction features 1/a. This condition ensures that the error in estimating the probability of system trajectories remains controlled when the estimation error of t/i, is small.
Although we focus on finite spaces Xд in this work, we briefly discuss possible extensions to continuous spaces. In finite settings, the core tests q E Qn are represented by future trajectories
= 11 ..... (1) E Fr. In continuous spaces, the core tests become trajectories over subsets of the underlying continuous space: g = 11 ... Xn) ) C Fn. where each X₂ Xg is measureable
subset. We point to [33] for more discussion on how to extend (standard) PSRs to continuous spaces.
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 's dynamics and is crucial for characterizing the statistical complexity of general RL problems.
3.1 Partially-Observabbe Sequential Teams
We propose a model of sequential mraiing problems that includes an explicit representation of information structure, which we call partially- 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 strueture of POST describes the causal dependence between these variables. The information sel 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
sequential team is a controlled stochastic process that specifies the joint distribution of T variables (Xt)tez)) logether with a specification of the observability of each variable. Here each X, is either syslem variable or action variable, and is either observable by the learning agent or not. POST is specified by the following components.
1. Variable Structures. The variables {Xihem are partitioned into two disjoint subsets - sssttm variables and action variables. S C [T' indexes system variables and A C [T] indexes action variables, with S n A= 0. S U A = [
2. Information Structure. For E [T], the "information set" I, C [t 1] of the variable X, is the set of past variables that are coupled to X, in the dynamics. That is, the transition to X. depends on the value of I, == (X, s It). We call 1e the "information variable" time t, and call 1, = II X2 the "information space". ".
3. System Kernels. For any E S, To E P(X.(Tl)) [Tee is kernel from Tr to X, that specifies the conditional distribution of system variable X, given the information variable L.
4. Decision Kernels. Each agent chooses a decision kernel T. 1I, - P(X.), specifying a (potentially randomized) policy for choosing an action time E A.

---

5. Observability. We denote the observable system variables by O C S. We require that the information sets of the action variables are observable to the learning algorithm: O 05 Ute A S). We define U == O U A, and let H == IM be the lime-horizon of the observable variables. 6. Reward Function. At the end of an episode, the leam receives reward determined by the function R: Il x - [0, 1..
With the above components, any set of decision kernels joint policy) (Te : E A) induces a unique probability measure over X, x x Sr. which is given by
T
TTI
II (1te (xs E Ie)) II EES
(x (x. (..:8E
TEA
We will be interested in modeling the observable dynamics of the POST. We index the observable vari- ables by their position among the observables h [H] rather than their position among all variables, as follows: (Xt)reu = (Xt())..... (H))), where :: [7] - l c [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, 1aT (2=(1))...,,
Eseoc Σx,ex, 1PT [X1 21.... XT æT).
The value of a policy is given by its expected reward ((T) := ET [R( XwH) }] where E" is the expectation associated with the probability measure p The objective of a POST is to learn policy = (Te) L which maximizes the expected reward, sup, V V(T).. When the variable spaces X, are finite, this supremum is attained by a deterministic policy, Te lIe - X,, E A.
Representation of the information structure as directed acyelic graph. The information structure of 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+),), its DAG representation is given by G(V, &,C", L). The nodes of the graph are the set of variables. V = [T'] SUA. The edges & C
V of the DAG are given by = {(i, t) t E (T), i E I.). 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 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 distribu- tion on X x... XT factors according to G.
P Xr] = II [X, pa(X))),
IEV
where pa(X) is the set of parents of X, in G (which are Iz). This representation of the information structure DAG will be crucial for our analysis of the dynamics of sequential teams in Section 3.2.
Partially observable sequential games. We define partially-observabyy sequential games (POSGs) in similar manner. The main difference is that, in the game setting, there exists an expanded reward structure with N different reward objectives R! .... RN with different agents pursuing different objectives. The action index set is partitioned into N subsets A = A U... A where A C A denotes the action index set associated with the agent(s) optimizing for objective R'. The extension to the game setting is treated in detail in Appendix F.
3.2 Information Structure Determines the Rank of POSTs/POSGs
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, POMDPS, and POMGs. By introducing a model with an explici representation of information structure, we gain the ability to perform a richer analysis of sequential decision decision-making problems. In particular, 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-strueuun state", hinting at the role will play. The information structural state is defined for each point in time as subset of the past (whether observed or latent) which forms a sufficient statistic for the future. state). Let G be the DAG obtained from G by removing all edges directed towards actions. That is, it consists of the edges El := E {(xx a) : x NN, E A). For each h E [H), let Iİ C [1hh]] be the minimal set of past variables (observed or unob- served) which d-separates the past observations xx, from the future observations ((itt)...... ...,))))) in the DAG gt. Define 1T == Il.ez Xx as the joint space of those variables.
Definition 5
cnormaation-strucuuuee
5

---

and actions The latent state transitions are Markovian and depend on the agents' joint 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 Theorem 1. The rank of the observable system dynamics of a POST or POSG is bounded in terms of its information structure by r S (-
This result shows that the complexity of the observable system dynamies is characterized by the information structure through I In particular, i7, E If, describes set of system variables, either observable or latent, which provide a sufficient statistic of the past at time h for predicting future observations-44, "separates" the past from the future. Hence, the quantity | admits an interpre- tation as the size an effective state space time h. This is generalization of the standard notion of a latent state. For example, in the case of POMDPs or Dec-POMDPs, the information-structume
state indeed coincides with the latent Markovian state (Figure 2a). We emphasize that II 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.
3.3 Examples of Information Structures and their Rank
In this section, to provide some intuition, we present examples of information structures and ap- ply Theorem to obtain 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- theorethrrtcccc 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 ((t)) = {8:-1, [1 } for the information set of the state variable 8,.
Decentralized POMDPs and POMGs. At each time I, the system variables of a decentralized POMDP (or POMG) consists of latent state st. observations for each agent ......, of of each agent a..... af"
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 by
((x)) = ( d- )
I(o)) = {8t) I(at) = 10i--111..-1)
Here, the observable variables are L1 = foi.r. di.r. E [N]]. By Theorem 1, we have (o)) = (at) }. Vt, i, as shown in Figure 2a. Thus, the rank of Dec-POMDP is bounded by [S], where S is the state space. Note that in the case of models with true latent state (e.g., POMDPs, Dec- POMDPs, and POMGs), the information-structurall state coincides with the Markovian latent state.
Point-to-Poine Real-Time Communication with Feedback. Consider the following model of real- time communication with feedback. Let xa be a Markov source. At time f, the encoder receives the source I₁ E X and sends an encoded symbol 2, E E. The symbol is sent through a memoryless noisy channel which outputs y: the receiver. The decoder produces the estimate अ,. 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 {œIrr, shrr) } and the "actions" " are A = {21:7, } Hence, the information structure is given by the following.
[(x1) (x--1}, I(2)) {I1. Mi. 214-13 I(y) (2), I(i.) {vr.).
By Theorem 1, we have that,
(x,) = {xt), I'(x)) = (1r), I'()) (xr, ))) I' I'. = {21).
Hence, the rank is bounded by [ This is depicted in Figure 2c.
Limited-memon information structures. Consider sequential decision making problem with variables o,, a,, t E [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 is
I(ox) = (Or-mat- 0t-mat-1 } I(a;) = {oLe, 01t-1.
The observables consist of all observations and actions, 11 = {01.7, ). By Theorem 1 we have that (o.) = {o--m:t-1. at as shown in Figure 2d. Hence, the rank of this sequential Socision-making problem is bounded by |0] [ m.

---

(a) Decentralized POMDP/POMG information suformation-structure..
(b) "iean-fielld' information structure.
(c) Point-to toint-to-point real-time communica- tion with feedhack information structure.
81
(d) Limited-meen memory (m 2) information structures.
(e) Fully connected information structure.
Figure 2: DAG representation of various information structures. Solid edges indicate the edges in Et 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 Z). To find Z/.- as 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.
The examples above show that the complexity of the dynamics of a sequential decision-making problem depends directly its information structure. An expanded version of this discussion is provided in Appendix D. Next, we use an information-structurall analysis to construct a generalized PSR representation for class of POSTs/POSGs, which we will ultimately bound on the statistical complexity of reinforcement learning as function of information structure.
prove upper
4 Constructing a PSR Parameterization for POSTs and POSGs
A key challenge in reinforcement learning is constructing representations which enable ro- bustly and efficiently modeling probabilities of system trajectories (i.e., probabilities of the form [future history)). this section, we will construct generalized predictive state representa- tion for class of POSTs/OOSGs, ultimately enabling sample-efficient reinforcement learning.
4.1 Core test sets for POSTs/OOSSs
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 simple and
7

---

ststep future
GA E RRF
(c (x 16))
Observables
Pa 10)
(x
Unobservables
(c.)
(zeay der (err)))) (6)))
inormmtiion-structunn
Figure 3: A depiction of the construction of generalized generalized predictive state representation for POST/POSG models.
regular information structure, a core test set may be simple to obtain. For example, undercomplete POMDPs with full-rank emission matrix admit the 1-step observation futures
test sets.
For POSTs/POSGs with arbitrary information structures, obtaining core test is much more challenging without knowing the system dynamics. In this section, we identify condition in terms of the information structure under which m-step futures
core test for POSTs/POSGs, Let us denote the candidate core test set of m-step futures at time h by Q == IL
Xg. We define the matrix Gn, encoding the probability of observing each m-step future conditioned on the iiormation-structuue state 1 E Ii;
iimin +:min m..
G = P
E ER 9.4h
17 IIIIt,,, 9 Q of u..
(5)
The operational meaning of Gr, depicted Figure 3. Next, we formulate a condition terms of information structure that we will show implies that the m-step futures are core test sets.
Definition 6 (m-step -t-weakly revealing). We say that a sequential team is m-step It -eealyy revealing if for all h E [H], rank(G,)) = -11,) Furthermore, we say that the sequential team is a- robustly m-step It -wekkly revealing for all h E [ - m + 1], 11 ( 2 a.
The Zt weakly revealing condition is essentially statistical identifiability condition. If POST/POSG is Zt-weakly revealing, then, for any two mixtures of the information-struete structural state, the distributions of the m-step futures are distinct. Formally, for any Vı, 1/2 E P(L)) with supp(v)) n supp(u2) = 9, we have G * 22 That is, the future observations contain informa- tion that can distinguish between mixtures of the latent inoommationsstuutttuee
state. The a-rouust version of the - revealing condition requires that G, not only full rank, but that its [T,]| I-th singular value is bounded away from zero, so that || - Gruzll 2 oll21 - -22l-
The condition holds whenever there exists sequence of actions within the m-step futures such that executing these actions results a sequence of observations that informative about the information- structural state i E If,- In general, this condition will be harder to satisfy when II, is large since would require the m-step future observations to encode more information. In particular, G₁, cannot be full rank when Q [1 As heuristic, when we don't 't have prior knowledge about the dynamies (e.g., in the learning setting), we can choose m such that [QP] 2 | In general, will be possible to find smaller core test set when the d-separating set Zj. is small. This happens when the system dynamics contain state-like variables that are oiwddimeniional.
The Zl Zl-weakly-reveating condition is a generalization of the "weakly-revealing condition for POMDPs introduced by Liu al. [36]. Liu et al. [37] proposed an algorithm for learning weakly- revealing POMGs. Our analysis here recovers weakly-revealing POMGs as a special case and enables learning much more general class of problems. We note that such an identifiability condition is necessary, and is reflective
the fundamental difficulty of the partially-observabll 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 Zí sets for POSTs/POSGs which can be used to construct generalized PSR representation amenable
condition, m-step futures are core test

---

to learning, Recall that the vector of core test set probabilities for the history Th is given by the mappings 1h,, Sh HA + 1!861
(T.) IP d = do(T)), do(g" "lgeo (Th) [P [4" Thi do(r)), do(a do(d"))l
Define the mapping my A + 12 1 as, my (w/) = (G))
Flwn b/]] E
(6)
The following lemma, whose proof given in Appendix I, shows that the m-step futures Q are core test sets for any m-step I' -weakly revealing POST/POSG. In particular, given any future wa E Fr and history Th HA, the conditional probability P (ay | Tal can be written as linear combination of the core test probabilities 2 (Tk), with weights given by m, (w)), depending only the future wa.
Lemma 1 (Core test set for POSTs). Suppose that the POST m-step I' -weealyy revealing. Then, Q is core test set for all h E [H]. Furthermore, have P [T,, Wh] (wn)w)) (h((T)) and P P(wn mh] (ma 1. (Tx)).
4.2 Generalized PSR parameterization of POST/POSG
Consider a POST/POSG which is m-step Zt -wekkly revealing. Lemma shows that the m-step futures QA" are core test sets. In this section, we will explicitly construct a generalized PSR parameterization for this class of sequential decision-makee making problems. Moreover, we will show that this generalized PSR representation is well-conditioned when the weakly revealing condition is robust.
Let da == IQ% |. The key observation that allows us construct the generalized PSR representation is that the vector mappings m, FF gd and tha HA, gd can be used derive recursive form of the dynamics of the POST/POSG. We define the operator mapping M,. ((()) + Rdd xdh by
(M((aa))) m=-1(Fu0)) o) ,9 Qr.
(7)
That is, My. (Xr(k)) is the matrix whose rows are indexed by the core tests at the h-th observable step, where the row corresponding to each 9 E Qu is the weights returned by the mapping m when applied to the future consisting of Tε(h) followed by core test q. The operator map M,, allows us to update the probabilities of the core test sets after receiving
additional observation Tma)): 4h (II(1)...., .... Iz(n)) I((k)) = M, (Za(k) - 2t(h-1)) 11). The following result, whose proof is given in Appendix I, states that the set of operators {Ma} J forms a generalized PSR.
Theorem 2. Consider an m-step It -t-kkyy revealing POST/POSG. Let (Mr (Ma)ee(H-)) be defined as above, and let th [T [4]] gECr- Φn (*))) Caany Then, (LQM be; dhH (M))ee(H-j)) vo) forms generalized predictive state representation. Moreover, if the weakly-revealing property is a-robust, then this PSR is
with y = a/ maxx |1] 1/2.
Thus, we have constructed robust parameterization of the sequential pocision-making problem. making use of its information structure, that will enable us to design an efficient learning algorithm.
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 rein- forcement learning problems in terms of their information structure. In plain language, this is result that roughly says "any sequential eecision-maaing problem with an information structure I can be learned with sample complexity most f(Z)". This identifies class of sequential decision 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 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 robust representation amenable to learning. We will introduce 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 information- structural characterization of the rank of observable dynamies 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 directly extended to our generalization of PSRs. With such an algorithm, Theorems and 2 then imply a bound on the achievable sample complexity for learning general sequential recision-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 bound on the achievable sample complexity for POSTs/POSGs. We will defer the details 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 cearmatiio--tructuree state, [/ characterizes an upper bound on the statistical complexity of learning a sequential decision decision-making problem.
Theorem 3. Suppose a sequential decision-maker
problem described by a POST is a-robustly m- step It- -t-kkllly revealing. Let Qm. == max (Q be the size of the m-step observable trajeciories, and let A max,e A [%,s be the size of largest action space. Then, there exists an algorithm that can learn an e-optimal policy with a sample complexity (omitting log factors) bounded by
(2.1nxxTTA) ,m, A,
x poly
Under the game setting, the same assumption implies the existence of self-play algorithm that learns an e (Nash coarse-correlated) equilibrium with the same sample complexity.
This result identifies It-weakly revealing POSTs/POSGs as a class of statistically tractable sequential decision-making problems. The sample complexity is polynomial in the size of the information- structural state space max the size of the action space A, and the time horizon H. Further, it depends on Qm, the size of m-step observable trajectories, and the robustness parameter a- which corresponds to the m-step It_ -wewlyyyy revealing identifiability condition. We note that the algorithm constructed to prove Theorem 3 only needs to know the parameters of the I -i-wkllly revealing condition (i.e., m and a)), and does not need to know the full information structure.
This result shows that the size of the information-struutun statistical complexity of reinforcement learning. As a result, learning is tractable when max, [I, is of modest size, and the information structural state is strongly coupled to the observable system variables.
state is a fundamental measure of the
One notable special case of POSTs/POSGH is POMDPs. Learning in POMDPs has been studied extensively in the literature. Theorem 3 implies a poly O, A, 11) -2 bound on the sample complexity learning a-weakly POMDPs and poly(S, (OA)", H, -1) e-
for learning m-
step weakly revealing POMDPs. This recovers similar sample complexity as was shown by more specialized analysis tailored POMDPs [e.g.. 36, 40].
6 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 graphical representation of the information structure, and admits an interpretation as an effective information- structural state, generalizing the typical notion of a Markovian state.
Limitations. The results of this paper are thcoretical in nature, and the algorithm proposed to prove our main result is not computationally practical. Current SOTA algorithms for partially-obsere algorithms are based on recurrent neural networks 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- algorithms. For example, the information structure can be incorporated as an inductive bias of the neural network.
10

---

References
[1] Hans S Witsenhausen. "The Intrinsic Model for Discrete Stochastic Control: Some Open Problems". In: Control Theory, Numerical Methods and Computer Systems Modelling. Ed. by M. Beckmann, H. P. Künzi, A. Bensoussan, and J. L.. Lions. Berlin, Heidelberg: Springer Berlin Heidelberg, 1975 (cited on pages 1, 2, 17).
[2] Hans S Witsenhausen. "On information structures, feedback and causality". In: SIAM Journal Control (1971) (cited on page 1).
[3] Y. Ho and K. Chu. "Team decision theory and information structures in optimal control problems- Part 1 IEEE Transactions on Automatic Control (1972) (cited on pages 1, 17).
[4] Y. Ho and K. Chu, "On the Equivalence of Information Structures in Static and Dynamic Teams". In: IEEE Transactions on Automatic Control (1973) (cited on page 1).
[5] Tsuneo Yoshikawa. "Decomposition of dynamic team decision problems". In: IEEE Transac- tions on Automatic Control (1978) (cited on page 1).
[6] Hans S Witsenhausen. "Equivalent Stochastic Control Problems". In: Mathematics of Control, Signals, and Systems (1988) (cited on page I).
[7] Mark S Andersland and Demosthenis Teneketzis. "Information structures, causality, and nonsequential stochastic control I: Design-indepeenent properties". In: SIAM journal on control and optimization (1992) (cited on page 1).
[8] Demosthenis Teneketzis. "On Information Structures and Nonsequential Stochastic Control".
In: CWI Quarterly (1996) (cited on page 1).
[9] Aditya Mahajan and Sekhar Tatikonda. "A Graphical Modeling Approach to Simplifying Sequential Teams". In: 2009 7th International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks. 2009 (cited on page 1).
[10] Ashutosh Nayyar, Aditya Mahajan, and Demosthenis Teneketzis. "Optimal Control Strategies in Delayed Sharing Information Structures". In: IEEE Transactions on Automatic Control
(2011) (cited on page 1).
[11] Aditya Mahajan, Nuno C. Martins, Michael C. Rotkowitz, and Serdar Yuksel. "Information Structures in Optimal Decentralized Control". In: 2012 IEEE 5 IEEE Conference on Decision and Control (CDC). Maui, HI, USA: IEEE, 2012 (cited on pages 1, 17).
[12] Ashutosh Nayyar, Aditya Mahajan, and Demosthenis Teneketzis. "The Common-Informalt Approach to Decentralized Stochastic Control". In: Information and Control in Networks. Ed. by Giacomo Como, Bo Bernhardsson, and Anders Rantzer. Cham: Springer International Publishing, 2014 (cited pages 1, 18).
[13] Andreas A. Malikopoulos. "On Team Decision Problems with Nonelassical Information Structures". 2022. arXiv: 2101. 10992 [math] (cited on page 1).
[14] Naci Saldi and Serdar Yüksel. "Geometry of Information Structures, Strategic Measures and Associated Stochastic Control Topologies", In: Probability Surveys (2022) (cited on page 1).
[15] Hans S Witsenhausen. "Separation of estimation and control for discrete time systems". In: Proceedings of the IEEE (1971) (cited on pages 17).
[16] Richard Bellman. "Dynamic programming and stochastic control processes". In: Information and control (1958) (cited on page 1).
[17] Christopher John Cornish Hellaby Watkins. "Learning from delayed rewards". In: (1989)
(cited on page 1).
[18] Satinder Singh, Tommi Jaakkola, Michael L Littman, and Csaba Szepesvári. "Convergence wewtrreemmnt---ernnng algorithms". In: Machine learning
results for single-step on-policy (2000) (cited on page 2).
[19] Richard S Sutton, Hamid Maei, and Csaba Szepesvári. "A convergent o(n) temporal-difference algorithm for off- policy learning with linear function approximation" In: Advances in neural information processing systems (2008) (cited on page 2).
[20] Rémi Munos and Csaba Szepesvári. "Finite-Time Bounds for Fitted Value Iteration." In: Journal of Machine Learning Research (2008) (cited on page 2).
[21] Yasin Abbasi- Yadkiii and Csaba Szepesvári. "Regret bounds for the adaptive control of linear quadratic systems". In: Proceedings of the 24th Annual Conference on Learning Theory. JMLR Workshop and Conference Proceedings. 2011 (cited page 2).
[22] Tor Lattimore and Mareus Hutter. "PAC bounds for discounted MDPs". In: Algorithmic Learning Theory: 23rd International Conference, ALT 2012, Lyon, France, October 29-31, 2012. Proceedings 23. Springer. 2012 (cited on page 2).
11

---

[23] Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. "Playing Atari with Deep Reinforcement Learning". 2013..
arxiv: 1312. 5602 [ca] (cited on page 2).
[24] Jens Kober, J. Andrew Bagnell, and Jan Peters. "Reinforcement Learning in Robotics: A Survey". In: The International Journal of Robotics Research (2013) (cited on pages 18).
[25]
Volodymyr Mnih et al. "Human- Control through Deep Reinforcement Learning". In:
Nature (2015) (cited on page 2).
[26] David Silver et al. "Mastering the Game of Go with Deep Neural Networks and Tree Search". In: Nature (2016) (cited on pages 2, 18).
[27] Shai
Shaked Shammah, and Amnon Shashua. "Safe, Multi-Agent, Reinforee- ment Learning for Autonomous Driving". 2016. arXiv: 1610.03295 [cs, stat] (cited on pages 2, 18).
[28] Oriol Vinyals, Igor Babuschkin, Junyoung Chung, Michael Mathieu, Max Jaderberg, Wojeiech M. Czarnecki, Andrew Dudzik, Aja Huang, Petko Georgiev, and Richard Powell. "Alphastar: Mastering the Real-Time Strategy Game Starcraft Ii".. In: DeepMind blog (2019) (cited on pages 2, 18).
[29] Aditya Mahajan and Sekhar Tatikonda. "An Axiomatic Approach for Simplification of Se- quential Teams". In: (2011) (cited on page 2).
[30] Aditya Mahajan and Sekhar Tatikonda. "An Algorithmic Approach to Identify Irrelevant Information in Sequential Teams". In: Automatica (2015) (cited on page 2).
[31] Michael Littman and Richard S Sutton. "Predictive representations of state". In: Advances in neural information processing systems (2001) (cited pages 3, 6, 17, 19, 20).
[32] Herbert Jaeger. "Observable Operator Models for Discrete Stochastic Time Series", In: Neural
Computation (2000) (cited on pages 3, 17, 19).
[33] Qinghua Liu, Praneeth Netrapalli, Csaba Szepesvári, and Chi Jin. "Optimistic MLE A Generic Model-based Algorithm for Partially Observable Sequential Decision Making". 2022. Xiv: 2209. 000.14999 14997 [cs, stat] (cited on pages 4, 10, 17, 18, 21, 25, 30, 39).
[34] Masatoshi Uehara, Ayush Sekhari, Jason D. Lee, Nathan Kallus, and Wen Sun. "Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems". 2022. arXiv: 2206. 12020 [cs, math, stat] (cited on pages 4, 10, 17).
[35] Ruiquan Huang, Yingbin Liang, and Jing Yang. "Provably Efficient UCB-type Algorithms For Learning Predictive State Representations" 2023. arXiv: 03307000400 [cs, stat] (cited on pages 4, 10, 17, 18, 21, 24, 26, 27, 38, 40, 41, 47, 53, 54).
[36] Qinghua Liu, Alan Chung, Csaba Szepesvári, and Chi Jin. "When Is Partially Observable Reinforcement Learning Not Scary?" 2022. arXiv: 2204. 08967 [cs, eess, stat] (cited on pages 8, 10, 17, 18, 25, 27).
[37] Qinghua Liu, Csaba Szepesvári, and Chi Jin. "Sample-Efficien Reinforcement Learning of Partially Observable Markov Games". 2022. arXiv: 2206. 01315 [cs, stat] (cited on pages 8, 18, 27).
[38] Fan Chen, Yu Bai, and Song Mei. "Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Comple-Efficient Algorithms". 2022. arXiv: 2209. 14990 [cs, math, stat] (cited on pages 10, 17, 18, 25,48).
[39] Wenhao Zhan, Masatoshi Uchara, Wen Sun, and Jason D. Lee. "PAC Reinforcement Learning for Predictive State Representations"" 2022. arXiv: 2207. 2207.05738 05738 18).
[cs] (cited on pages 10, 17,
[40] Chi Jin, Sham M. Kakade, Akshay Krishnamurthy, and Qinghua Liu. "Sample-Efficien Re- inforcement Learning of Undercomplete POMDPs". 2020. arXiv: 2006. 12484 [cs, math, stat] (cited on pages 10, 17).
[41] Christos H. Papadimitriou and John N. Tsitsiklis. "The Complexity of Markov Decision Processes".. In: Mathematics of operations research (1987) (cited on page 17).
[42] Ashutosh Nayyar, Aditya Mahajan, and Demosthenis Teneketzis. "Optimal control strategies in delayed sharing information structures". In: IEEE Transactions on Automatic Control (2010)
(cited on page 17).
[43] Ashutosh Nayyar, Abhishek Gupta, Cedric Langbort, and Tamer Başar. "Common information based Markov perfect equilibria for stochastic games with asymmetric information: Finite games". In: IEEE Transactions on Automatic Control (2013) (cited on page 17).
12

---

[44] Ashutosh Nayyar, Aditya Mahajan, and Demosthenis Teneketzis. "Decentralized stochastic control with partial history sharing: A common information approach".. In: IEEE Transactions on Automatic Control (2013) 3) (cited on page 17).
[45] Yi Ouyang, Hamidreza Tavafoghi, and Demosthenis Teneketzis. "Dynamic games with asym- metric information: Common information based perfect bayesian equilibria and sequential decomposition". In: JEEE Transactions on Automatic Control (2016) (cited on page 17).
[46] Aditya Dave. Nishanth Venkatesh, and Andreas A Malikopoulos. "Decentralized Control of Two Agents with Nested Accessible Information". In: 2022 American Control Conference (ACC). IEEE 2022 (cited on page 17).
[47] Yue Guan, Mohammad Afshari, and Panagiotis Tsiotras. "Zero-Sum Games between Mean- Field Teams: A Common Information and Reachability based Analysis". 2023. arXiv: 2303. 12243 [eess.SY] (cited on page 17).
[48] Serdar Yuksel and Tamer Basar. "Stochastic Teams, Games and Control under Information Constraints". Springer, 2023 (cited page 17).
[49] Joseph A Tatman and Ross D Shachter. "Dynamic programming and influence diagrams". In: IEEE transactions on systems, man, and cybernetics (1990) (cited on page 17).
[50] Daphne Koller and Brian Milch. "Multi-agent influence diagrams for representing and solving games". In: Games and economic behavior (2003) (cited on page 17).
[51]
Ian Osband and Benjamin Van Roy. "Near-optimal reinforcement learning in factored mdps". In: Advances in Neural Information Processing Systems (2014) (cited on page 17).
[52] Peter Auer, Thomas Jaksch, and Ronald Ortner. Opttimll Regret Bounds for Reinforce- ment Learning". In: Advances in neural information processing systems (2008) (cited on page 17).
[53] Shipra Agrawal and Randy Jia. "Optimistic Posterior Sampling for Reinforcement Learning: Worst-Case Regret Bounds". In: Advances in Neural Information Processing Systems (2017) (cited on page 17).
[54] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. "Minimax Regret Bounds for Reinforcement Learning". In: International Conference Machine Learning. PMLR, 2017 (cited on page 17).
[55] Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. "Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism". In: Advances in Neural Information Prucessing Systems (2021) (cited on page 17).
[56] Martin Mundhenk, Judy Goldsmith, Christopher Lusena, and Eric Allender. "Complexity of Finite-Horizor Markov Decision Process Problems". In: Journal of the ACM (JACM) (2000) (cited on page 17).
[57] Nikos Vlassis, Michael L. Littman, and David Barber. "On the Computational Complexity of Stochastic Controller Optimization in POMDPs". In: ACM Transactions on Computation Theory (TOCT) (2012) (cited on page 17).
[58] Elchanan Mossel and Sébastien Roch. "Learning Nonsingular Phylogenies and Hidden Markov Models". In: Proceedings of the Thirty-Seventh Anmual ACM Symposium on Theory of Com- puting. 2005 (cited on page 17).
[59] Akshay Krishnamurthy, Alekh Agarwal, and John Langford. "PAC Reinforcement Learning with Rich Observations". In: Advances in Neural Information Processing Systems (2016) (cited
on page 17).
[60] Yonathan Efroni, Chi Jin, Akshay Krishnamurthy, and Sobhan Miryoosefi. "Provable Rein- forcement Learning with a Short-Term Memory". In: International Conference on Machine Learning, PMLR, 2022 (cited on page 17).
[61] Jiacheng Guo, Zihao Li. Huazheng Wang. Mengdi Wang, Zhuoran Yang, and Xuezhou Zhang "Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP"
2023. arXiv: 2306. 12356 [c].LG] (cited on page 17).
[62] Hongming Zhang, Tongzheng Ren, Chenjun Xiao, Dale Schuurmans, and Bo Dai. "Provable Representation with Efficient Planning for Partially Observable Reinforcement Learning". 2023. arXiv: 2311. 12244 [CS.LG] (cited on page 17).
[63] Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. "Learning in observable pomdps, without computationally intractable oracles". In: Advances in Neural Information Processing Systems (2022) (cited on page 17).
13

---

[64] Noah Golowich, Ankur Moitra, and Dhruv Robatgi. "Planning in Observable POMDPs in Quasipolynomial Time". 2022. arXiv: 2201. 04735 [cs. LG] (cited on page 17).
[65] Noah Golowich, Ankur Moitra, and Dhruv Rohatgi. "Planning and Learning in Partially Observable Systems via Filter Stability". In: Proceedings of the 55th Annual ACM Symposium Theory of Computing- 2023 (cited on page 17).
[66] Qi Cai, Zhuoran Yang, and Zhaoran Wang. "Reinforcement learning from partial observation: Linear function approximation with provable sample efficiency". In: International Conference Machine Learning. PMLR. 2022 (cited on page 17).
[67] Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. "Embed to Control Partially Observed Systems: Representation Learning with Provable Sample Efficiency". 2022. arXiv: 2205. 13476 [cs, eess, stat] (cited on page 17).
[68] Satinder P. Singh, Michael L. Littman, Nicholas K. Jong, David Pardoe, and Peter Stone. "Learning Predictive State Representations". In: Proceedings of the 20th International Confer- ence on Machine Learning (ICML-03). 2003 (cited on page 17).
[69] Satinder Singh, Michael R James, and Matthew R Rudary. "Predictvvee State Representations: A New Theory for Modeling Dynamical Systems". In: Proceedings of the Twentieth Conference on Uncertainty in Artificial Intelligence (UAI2004) (2004) (cited on page 17).
[70] Michael R. James, Satinder Singh, and Michael L. Littman. "Planning with Predictive State Representations"" In: 2004 International Conference on Machine Learning and Applications, 2004. Proceedings. IEEE, 2004 (cited on page 17).
[71] Peter McCracken and Michael Bowling. "Online Discovery and Learning of Predictive State Representations". In: Advances in neural information processing systems (2005) (cited on page 17).
[72] Byron Boots. Sajid M. Siddiqi, and Geoffrey Gordon. "Closing the Learning-Plannigg Planning Loop with Predictive State Representations". In: The International Journal of Robotics Research (2011) (cited on page 17).
[73] Nan Jiang, Alex Kulesza, and Satinder Singh. "Completing State Representations Using Spectral Learning". In: Advances in Neural Information Processing Systems (2018) (cited on page 17).
[74] Zhi Zhang, Zhuoran Yang, Han Liu, Pratap Tokekar, and Furong Huang. "Reinforcement Learning under a Multi-agent Predictive State Representation Model: Method and Theory". In: International Conference on Learning Representations. 2021 (cited on page 17).
[75] Ahmed Hefny, Carlton Downey, and Geoffrey J. Gordon. "Supervised Learning for Dynamical System Learning.. In: Advances in neural information processing systems (2015) (cited on page 17).
[76] Han Zhong, Wei Xiong, Sirui Zheng, Liwei Wang, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. "GEC: A Unified Framework for Interactive Decision Making in MDP, POMDP, and Beyondd 2023, arXiv:
[cs, math, stat] (cited on pages 17, 18, 48).
[77] Shuang Qiu, Ziyu Dai, Han Zhong, Zhaoran Wang, Zhuoran Yang, and Tong Zhang. "Posterior Sampling for Competitive RL: Function Approximation and Partial Observation". 2023. arXiv: 2310. 19861 [cs LG] (cited on pages 17, 18, 48).
[78] Zhihan Liu, Miao Lu, Wei Xiong. Han Zhong, Hao Hu, Shenao Zhang, Sirui Zheng. Zhuoran Yang, and Zhaoran Wang. "Maximize to explore: One objective function fusing estimation, planning, and exploration". In: Advances in Neural Information Processing Systems (2024) (cited on pages 17, 18).
[79] Richard S Sutton and Andrew G Barto. "Reinforcement learning: An introduction".. MIT press, 2018 (cited on page 18).
[80] Noam Brown and Tuomas Sandholm. "Superhuman AI for Multiplayer Poker". In: Science (2019) (cited on page 18).
[81] Ronen I. Brafman and Moshe Tennenholtz. "R-Max-a General Polynomial Time Algorithm for near- Optimal Reinforcement Learning". In: Journal of Machine Learning Research (2002) (cited on page 18).
[82] Yu Bai, Chi Jin, and Tiancheng Yu. "Near-Optimal Reinforcement Learning with Self-Play". In: Advances in Neural Information Processing Systems. Ed. by H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin. Curran Associates, Inc., 2020 (cited on page 18).
[83] Ziang Song, Song Mei, and Yu Bai. "When Can We Learn General-Son -um Markov Games with a Large Number of Players Sample-Efficee Efficiently" In: (2021). arXiv: 2110. 04184 (cited on page 18).
14

---

[84] Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione. "Regret Minimization in Games with Incomplete Information". In: Advances in neural information processing systems (2007) (cited on page 18).
[85] Tadashi Kozuno, Pierre Ménard, Rémi Munos, and Michal Valko. "Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recall". In: (2021).
arxiv: 2106. 06279 (cited on page 18).
[86] Gabriele Farina and Tuomas Sandholm. "Model- Freee Online Learning in Unknown Sequential Decision Making Problems and Games". In: Proceedings of the AAAI Conference on Artificial Intelligence. 2021 (cited on page 18).
[87] Xiangyu Liu and Kaiqing Zhang. "Partially Observable Multi-agent RL with (Quasi- ]Efficiency: The Blessing of Information Sharing". 2024. arXiv: 2308. 08705 [cs LG] (cited
on page 18).
[88] Jayakumar Subramanian, Amit Sinha, Raihan Seraj, and Aditya Mahajan. "Approximate information state for approximate planning and reinforcement learning in partially observed systems". In: The Journal of Machine Learning Research (2022) (cited on page 18).
[89] Weichao Mao, Kaiqing Zhang, Erik Michling, and Tamer Başar. "Information state embedding in partially observable cooperative multi- ageet reinforcement learning". In: 2020 59th IEEE Conference on Decision and Control (CDC). IEEE. 2020 (cited on page 18).
[90] Ali Kara and Serdar Yuksel. "Near optimality of finite memory feedback policies in partially observed markov decision processes". In: Journal of Machine Learning Research (2022) (cited on page 18).
[91] Hsu Kao and Vijay Subramanian. "Common information based approximate state representa- tions in multi-agent reinforcement learning". In: International Conference on Artificial Intelli- gence and Statistics. PMLR. 2022 (cited on page 18).
[92] Dengwang Tang. Ashutosh Nayyar, and Rahul Jain. "A novel point- point-based algorithm for multi- agent control using the common information approach". In: 2023 62nd IEEE Conference on Decision and Control (CDC). IEEE. 2023 (cited on page 18).
[93] John Nash. "Non-cooperative games". In: Annals of mathematics (1951) (cited on page 28).
[94] Sara van de Geer. "Rates of Convergence for Maximum Likelihood Estimators". In: Applica- tions of Empirical Process Theory. Reprint. Cambridge Series on Statistical and Probabilistic Mathematics. Cambridge: Cambridge Univ. Pr, 2006 (cited on pages 33, 40).
[95] Thomas Verma and Judea Pearl. "Causal networks: Semantics and expressiveness". In: Machine intelligence and puttern recognition. Elsevier, 1990 (cited on page 35).
[96] Varsha Dani, Thomas P Hayes, and Sham M Kakade. "Stochastic linear optimization under bandit feedback". In: (2008) (cited on pages 53, 54).
[97] Yasin Abbasi Yadkori, Dávid Pál, and Csaba Szepesvári. "Improved algorithms for linear stochastic bandits". In: Advances in neural information processing systems (2011) (cited on pages 53, 54).
[98] Alexandra Carpentier, Claire Vernade, and Yasin Yadkoi. "The elliptical potential lemma revisited". In: (2020). arXiv: 2010. 10182 [stat. .ML] (cited on pages 53, 54).
15

---

A
Summary of Notation
Space that the variable X, lies in within the stochastic process (X,,..., XH). Generic Sequential Decision-Makiin Problems
X
O
O C H denotes the set of observations among the variables (XI,.... X1)).
A
A H denotes the set of actions among the variables (X1,-.., XH).
Hn.
The space of histories at time h. HI, = X. The space of futures at time h. F, = II 1+ X The observation component of trajectory. (bs( = (0, Ozi)).
F
obs(.)
act(-)
The action component of trajectory. act( ....,,.......................... 2j) (I, 8 E Ani)).
HA (a.a)
The space of observation (resp., action) histories. E.g., H = II
X, = obs((Hl)).
ploa)
The space of observation (resp., action) histories. E.g., F = I..EO
X (b
F[rx]
The probability of trajectory given actions are executed.
P P(Tnl
IP [[obs(T.) do(act(T.))..
Da
Dynamics matrix at time h. D₁, BRIIPI [Dilamm = [ wn]. oh = rank For Th = (#1..... RT)) and policy n, ((T)) = ILEAM T I1,..., II,...,-o-1)..
(Tr)
Twnn Th)
For Th = (II,..., Ih), Wh = (Eh+II..., T(wn
Th) =
ILEEA, 14
TT., F1....,, x--11)
POSTs and POSGs
X
Space that the variable X, lies in within the stochastic process (X1...., .............................. Xz).
S [T] denotes the set system variables among the variables (X, 1....... X7).
A
A [T] denotes the set of action variables among the variables
Xy.).
O
O C S denotes the subset of system variables which are observable.
U
The union of observable system variables and action variables. U = OU Let H1 = 12). For h E [H] indexing the order among observables, t(h) li denotes the order among all variables.
((h)
I.
The information set the f-th variable.
L
4 = Ilszz, X, denotes the information space at time t. The minimal d-separating set at the h-th observable. See Definition 5. T/. II.T X denotes the sinformatioon-stuucuuaal state".
I.
Generalized PSRs
QN
Core test set at time h. Let d, == IQul and max,, dn.
QA
Action component of core test set at time h. Q = act (Q+). Maximum size of the action component of core test sets QA == maxi (AA Observable operators of PSR representation mapping Md Xx, - x1 Prediction features.
QA
Mr
th
Vn (TT) = (IP [Th. gl).g..) (x,),) (11))o- Prediction coefficients. my (wn) = (z(CH) MH 1
In PSR, en (I( Rn)
my
dhn
Normalized prediction features. Th (Th) (T) [TN] (F Th m
General Mathematical Notation
Drv (p, ④)
Total variation distance. DTv (p. 9) == -zexlp(1)) - g(x))-
D (p. q)
Hellinger squared distance. DÉ (p.g) = 2 ΣmEz( (oox(V/lee p((r) v
oR(A)
k-th largest singular value of the matrix A.
||
The matrix p-norm. ||-I]pp
- ||
||
The vector norm induced by the positive semi-definite matrix A. || Vxl Ax. Moore-Penrose pseudoinverse.
AI
P(A)
Space of probability distributions over A. P(BIA) the space of kernels from A to B.
Nea
For an index set N Ne = - (j).
16

---

B Related Work
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 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, well as in the design of efficient algorithms, especially in the decentralized setting. See, c.g., Mahajan et al. [1I], Nayyar et al. [42-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 model partial-observabiliy 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. work studies the role of information structure in planning and control,
Whereas the above-mentione, 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-55). However, under partial observability, reinforcement learning can be computationally and statistically intractable in the worst case, even when assuming a Marko- vian 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 uncontrol- lable. Accordingly, sub-classes of POMDPs have been identified in recent work where added struc- tural 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-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 mod- els in the function approximation setting, where the state or observation spaces are large and function approximators (c.g.. linear functions) are used to represent the model. See. c.g., Uchara 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 class of POSTs P 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-71]. PSRs are way to represent the dynamics of sequential decision-malt making problem by modeling the (conditional) probabilities of a small set of future trajectories, typically called "core tests". In 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 PSR. Various reinforcement learning methods for PSRs have been proposed under the assumption that data distribution is explorative, including spectral algorithms [72-74] and supervised learning approaches [75]. In addition, when it comes to the online setting where the algorithm needs to explore, there is 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],
17

---

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 the works that combine the idea of optimism the face of uncertainty [79] and maximum likelihood model estimation [33, 35, 36, 38, 39J. Specifically, our algorithm extends the UCB-type algorithm proposed by Huang et al. [35] for standard PSRs learn 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], well 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 observable by all agents. Another model which has been explored in the literature is (IEFG), which assumes tree-structured transitions and deterministic emission, and can be viewed as subclass of partially-obeervable Markov games (POMGs). Learning under this model has been studied Zinkevich et al. [84]. Kozuno al. [85]. and Farina and Sandholm [86]. More recently, Liu et al. [37] studied reinforcement learning in POMGs using an MLE- E-beedd algorithm building on their previous work in the single-agent setting [36]. To address the computational intractability of 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 polsi-polynomiil 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 information- sharing 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 [9 I1] and Tang et al. [92].
extensive-fome games
In each of the mentionee models (e.g., MDP, POMDP, MG. IEFG, POMG, etc.), particular fixed information structure is assumed. We emphasize that the POST/POSG model proposed in our work allows the information structure 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.
C Preliminaries
C.1 Generic Sequential Decision-Making Problems
Consider controlled stochastic process (X1,..., XH). where X, is random variable corresponding to the variable at time At each time h E [H], J. the variable X₁, may be either an 'observation' (i.c., observable system variable) or an 'action'. The dynamics of this stochastic process are described by a tuple (H, (X,), > O, A, P), where H is the time horizon, X,, is the variable space time h (i.e.. X,, E X,), O C H is the index set of observations (i.e., Xx, is an observation if h E O), A C [H] the index set of actions, and IP keo is set of probability kernels which describes the the probability of any trajectory I EI,... , h given that the actions are executed,
PP [(1.::8E0) (a, E A))
I (mh I1,..., Th-.)
hEO
A choice of policy (TH (TAA induces probability distribution on X, ... x X as follows
p (II, xn) = Pn (#h "h......hh))) II hEA
Th (I
I xh-1)
BEO
We now define some notation. Let H,, = II X, denote the space of histories at time and F2 = II X2 denote the space futures time h. Similarly, let Hy obs (bH,))),) II X, denote the observation component of histories and let HiC = aCt( = IL X. denote the action component. Here, Ony denotes O n (i.....j) and similarly for A..y- The observation and action components of the futures, FY and Fř, respectively, are defined similarly.
18

---

We define the system dynamics matrix DT E [x/// as the matrix giving the probability of each possible pair of history and future at time given the execution of the actions.
D Dilm = P Th, w/. P [T oo (
The E H4, wh E Fh:
(10)
where w = (bs(w), are is the observation component of the future wh, 4 = act((w) (Wa) is the action component, and similarly for T. Th Note that the actions are actively executed via the do-operation. Hence, the system dynamics matrices are independent of any action- selection criteria. Note that
D3 E R |xx/X1 is defined as [DH]=> P [TH], and Do D
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 measure of the complexity of the dynamics.
Definition (Rank of dynamics; Definition 1). The rank of the dynamics (Di)ne(m is T maX rank( Dr).
This defines the dynamics of the system. A sequential decision-making problem is such a controlled stochastic process together with an objective. The objective defined by reward function
X1 x .... x XH + [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 XA, h A may be chosen by either a single agent or one of several agents (e.g., a team). The policy at time E A is mapping ny : H (Xx,)) from previous observations to action (or distribution over actions, if randomized). The collection of policies at all time steps is denoted π = (TT, h E A), and induces probability distribution over trajectories, denoted IPT Then, the value of a policy is the expected value of the reward under the measure 1P"T, V π == ET [R. XH), )]. 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. 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 sequential decision-making problem as per Definition 1.
C.2 (Generalized) Predictive State Representations
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 decision-making and predictive state representations, the sequence of variables is such that observations and actions always occur in alternating manner (i.e., Oh, an Ol++1, ..) The POST/POSG models we will propose are more general, and hence require 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 matrix D, E IR |Bs x|Fal is indexed by all possible observable histories 7h and futures wh. Denote the rank of the system dynamics at time by Th := rank( R.).
Consider sequential decision-making problem defined in Section 2.1 (i.e., with 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 time h. is subset of dy Th futures, Q ( ... Un C Fn, such that the submatrix Dr [Q]] E [xdn is full-rank, rank Da (Qu]) tank(Di) = Th-
di
A core test set implies the existence of matrix Wn, [Fa//xdd such that D₁, = DR(Qn) WT.
19

---

Denote the 7h-th row of Di. [1nn] by,
(T.) PP
[Th 9hl
P
The 9h
E ER.
(11)
The vector (% (Ti) a sufficient statistic for the history Th in predicting the probabilities of all futures conditioned on T/- This is sometimes called the prediction features of a history Th
For any integer d, 2 The there exists core test set of size dn. In particular, for any low-rank sequential decision-making problem, there exists a minimal core test set size rh at each However, the minimal core test set depends on the system dynamics matrix DR. which is unknown in the learning setting. In the literature on reinforcement learning in PSRs, is typically assumed that core test set is known. We address the problem of constructing a PSR representation for POSTs/POSGs in Section 4.
For core test set Qr. let Q {act(g) : q E Qn), where acl(g) denotes the action components of the test q E Q+. Let QA = max, [2% and d = max, du.
With core test sets defined, we are now ready to present the definition of a generalized predictive state representation. The essential element in PSR is a set of operators Mr. Xn + gd xd for Ih-1) E Rd the linear map (2x) computes the prediction features at time h, incorporating the additional observation 2/.- That is, thn (II. below.
each time point [ld]. Given the prediction features at time h 1,
.h-1) The full definition is given
Definition (Generalized Predictive State Representations; Definition 3). Consider a sequential decision-making problem (X,, E Xx) where A, O partition [H] into actions and observations, re- spectively. Then, a predictive state representation of this sequential decision-making problem is tuple ([QnJosnsH-LL9n M, vho) given by
(QuJoshgH-1 are core test sets, including for h = O, where Qo (4hh.... ..... do C Fo are core tests before the system begins.
2. Vu E (Ro the vector (00) = (Fighl..... Fell...,,,[[[o.]]
3. M = =MMinsASH-1 is set of mappings My. Xn + IR d. from an observa- tion/action to a matrix of size d2 x dR-1.
4. 0H X + Rddu- mapping from the final observation to a du ddn---dimensione vector.
This tuple satisfies,
P [II..... .n] = vn(en) Mn-1(zH-1) M1
(12)
vr ( [hh = Ma(xn) ... Mi (x) )oo vh.
(13)
To obtain a probability for a trajectory Th = (21,..., with h < H, note that
EuneB, EB,
Te [T] = Fg P [Tr). Hence
P
[Tm]
(T)
F
II 1:H [x, 1(sEA} Σ
Σ
(T( -.. (eo1
2h-1
Thus, we recursively define ob, h <
via
1
Σ 2h Ma(an) 0h-11
(14)
X
I(MEA)
with ΦH as the terminating condition, then, obtain IP (Tx] for any h H, via an inner product between di and (4 (Tr).
P [Tx]] = oī wh((TT))
(15)
Finally, we define (Th) (T.) (T.) then we obtain the conditional probability of the core tests given the history, 34 (7r) ) = (P9g) m....... Piahh mx) e Rd (Th) is known as the (normalized) prediction feature of the history Th [31].
20

---

Remark 1 (Generality and difference from standard PSRs). In standard PSRs, observations and actions are assumed occur in an alternating manner, and hence observable operators are defined on pairs of observations and actions (i.e., Mr (On, an)). This structure leads to somewhat simpler description compared the above. However, our formulation is more general, 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 (y-well-conditioned generalized PSR; Assumption 1). A PSR model
(Q0JoSASHM-1199 HH M, v/o). as defined in Definition 3, is said to be -y-well conditioned for > 0 it it satisfies
1. For any h E [
max max
Σ WN WAER
((wnlTh) pm (wh) T 2/ s 7
(16)
SER $1
where mm(wu)) (#n+1,..., TH Fn. The maximization is over policies such that for any fixed future observations wh: Eug T(wg. wh) =1
Φu((n) (anrH))Mnniiee M Ma+1 (IN+1) with wh
2. For any h E [H -
|rttal
max
Σ
[[MM(r))21I (xx))= S
SER%
7
[|=|| $1 EXA
where (xx))= when h & A and Ex, (xx))= when h E A.
To understand this condition, recall that m, (wn)) sumption representing the error in estimating 1/a, (T)), the probabilities of core tests at time h given the history The The --weel--onditionee assumption ensures that the error in estimating the over- all PSR (i.e., the probability of a particular trajectory) does not blow up when the estimation error of (h. (Tx) small.
( th (Th) = [T,, w... We may think of z in As-
The following result states that any sequential decision- decision-making problem of the form described in Section 2.1 admits generalized PSR representation. The proof and explicit construction are given Appendix G.
Proposition 1. Let (X1...., ......,..)))... be any sequential decision- problem with observation index set O, action index set A, and variable spaces (%n "Kh)nemny Let тı. rank DR), where Dn, h E [H] are the system dynamics matrices. Then, there exists a PSR representation tha QH Xx + R
MA Xx. Rrs XTb h E [H 1]. satisfying Definition 3.
Proof. The proof given Appendix G.
D Examples of Information Structures and their Rank
The analysis in Section 3 and Theorem 1 characterizes the rank of any sequential decision-making problem as function of its information strueture. In this section, we illustrate this several sequential decision-making problems, characterizing the information-structee dynamics. The procedure is as follows: 1) formulate the sequential decision-making problem POST/POSG: 2) represent the information structure as labeled directed acyelic graph G: 3) remove incoming edges into the action variables to produce Gt; 4) apply Theorem to find the information structural state at each point in time through d-separation analysis.
complexity of their
Illustration: translating to the POST/POSG framework. We begin by illustrating how an arbitrary sequential decision decision-making problem can be formulated in the POST/POSG framework. Consider
21

---

1
Dr
S1
54
%
Decentralized POMDPs and POMGs. At each time the system variables of a decentralized POMDP (or POMG) consist of a latent state St, observations for each agent ..,..., of" and actions of each agent a!..... N The latent state transitions are Markovian and depend on the agents' joint Figure 4: An illustrative example of the information--sruccuraal state for POMDPs. Left. The DAG representation of the information structure G. Right. The DAG G depicted by drawing the edges corresponding the information sets of the action variables with dotted lines. The information- structural state coincides with the Markovian state 8t, and depicted in red. Future observables are drawn in green, and past observables are drawn in blue.
POMDP with variables (5), $2, 02, a2 ..... This can be formulated as a POST/POSG by simple relabelling of variables follows.
$1
01
41
82
02
02
St
00
a2
1
1
4
+
31
32
33
44
25
T3t-2 2
33
1
33t
Here, the system variables 8 are the s-type and o-type variables, with system index set S
{1, 4, 5, 7,8..... and the action variables are the a-type variables with action index set A
6.. 9, }. The observable system variables the o-type variables only, with index set O
82,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,, or, / [ Similarly, we use the notation I(x) to mean the information set corresponding to the variable x. Similarly, It (x) denotes the informmtiion-structte state at the time when x occurs. For example, in a POMDP I(s:) 19--1,4,113 I(o,) {sr}. and I(a,) {or.e d1.e)-
Below, will consider several examples of sequential dacision-making problems, and apply the information-strucct analysis of Theorem to obtain a bound on the rank of the observable dynamics (which in turn implies bound the sample complexity, by Theorem 3).
action. The observations are sampled via kernel conditional on the latent state. Each agent can use their own history observations to choose an action. Thus, the information structure is given by.
((st) (s-11,
1. a a.
I(o)) = {st} I(a)) = (of.-1:af..-1))
Here, the observable variables are U = {oi. di.r. E [N]]] By Theorem 1, we have It (o:) = {st} Vt, i, as shown in Figure 5a. Thus, the rank Dec-POMDP bounded by [S], where is the state space. Note that in the case of models with true latent state (e.g., POMDPs, Dec-POMDPs, and POMGs), the information-strucceee
state coincides with the true latent state.
Limited-memory information structures. Consider a sequential decision making problem with variables or, a,, t E [Z'] and 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 is
I(ot) = (0r-mit mit 1, at-m:t--) I(a.) = (011t (14-1).
The observables are all observations and actions, 24 = foILT (.r). By Theorem I we have that (o,) = (Or-m:t-1,, - as shown in Figure 5d. Hence, the rank of this sequential decision- making process is bounded by |0| |A|".
22

---

(a) Decentralized POMDP/POMG information stformation-structure..
(b) "ieaa-fielld' information structure.
(c) Point-to toint-to-point real-time communica- tion with feedhack information structure.
81
(d) Limited-menn memory (m 2) information structures.
(e) Fully connected information structure.
Figure 5: DAG representation of various information structures. Solid edges indicate the edges in Et 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 Z). To find Z/.- 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/ "MaettrriiMMMM---eeeleee Information Structures. Consider sequential decision makinn problem with N agents. Each agent has their own local state, sj E Stocal. Similarly, at each time point, each agent takes an action af E Ajoc- The global state 8, = (st,.... s E // =: $ is composed by of all agents' local states. Similarly, the joint action space A = A 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 limit). Here, the transition depends only on the distribution of local states and actions, defined as smm dist(8)) == o.. at dist(a:) == S for 8, E S, E A. Different agents can have different transition kernels for their local state. Hence, by introducing dist(s:), dist auxiliary unobserved variables each time t, we obtain the following information structure,
"mean-field" setting (in the
I(st) (ddis(((--),
I(at) {s/}
23

---

and an application of Theorem bounds the rank by
N
[lac| 1-1
N
|
|nt (st) < [ Alyel S - 11
|
This is compared to |Stoe| N is much larger when the number of agents is large. The information structure and d-separation decomposition are depicted in Figure 5b.
|Atoel N (e.g., if we modeled this as an MDP with the state st), which
Shint-to-Point Real-Time Communication with Feedback. Consider the following model of real- time communication with feedback. Let z; be the Markov source. At time t, the encoder receives the source 2₁ E and encodes sending a symbol 2t E Z. The symbol is sent through memoryless noisy channel which outputs y/: to the receiver. The decoder produces the estimate Tt. The output of the noisy channel is also fed back the encoder. The encoder and decoder have full memory of their observations and previous "actions". The observation variables are O = {II:T. F1.T] and the "actions" are A = {ZI:T, Ti.T J. Hence, the information structure is given by the following,
[(x))= = {. I(2+) {aia, 11: 21-11, I(ye) = {ze) I(G:) = {yr:).
By Proposition 1, we have that,
(x,) = {=t) (=,)) (ar), (1)) = (rc, 2²) It (G,) = (mr)
Hence, the rank is bounded by [Z] This is depicted in Figure 5c.
Connected Information Structures. Consider sequential decision making problem with variables Or, a,, E [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 is
I(o,) for--1 1, di:--1) 1): I(ar) = {01 a13-113
The observables are all observations and actions, U = for:r d1.r). By Theorem I we have that (o:) = (1:--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 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 aggregate consecutive observations and actions force them obey the standard formulation of PSRs. This approach results in a loss of "resolution" " in the information structure. That is, when you aggregate consecutive syslem 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. The examples given above elucidate this. Consider for example the "mean-field" information structure. If we aggregated local states and actions into a combined global state and joint action, the PSR rank would indled be [tncl (N | By comparison, by considering each local state separately without aggregation, we are able to obtain a decomposition with a much smaller PSR rank.
E UCB-Type Reinforcement Learning Algorithm for Generalized PSRs
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 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 guarantces to generalized PSRs. The tools developed in doing so can be used to directly extend any other PSR-based algorithm to generalized PSRs.
24

---

When learning generalized PSRs, we suppose that the core test sets (Qn Josh<H-1 are known by the algorithm. For example, if the sequential decision decision-making making problem is a POST, Section 4 provides conditions under which m-step futures form core test sets. Let θ be the set of 7-well-conditioned generalized PSR representations with (Q) JucAsH-1 as core test sets. Denote by +, an optimistic e-cover of (defined formally in Appendix G).
Recall that da. == | and d = maxa dn. Moreover, Q == act (Qt) are the action components of the core test sets and QA == max; [Q% is the maximal size of those action components. We define the exploration action sequences at time to be Q = act (X,, x Qn U 11). Moreover, we define = as the policy, defined from time / - onwards, in which each selection of action sequences in Q are chosen uniformly at random. For model @ and reward function R, we define the value of a policy under this model and reward as (g == E R(TH (
exp
The algorithmic description is given in Algorithm 1. At each iteration k. the learner collects a k.hh trajectory TH for each time index h E [H] by using a particular policy that drives exploration so as better estimate the parameters associated with the h-th time step. To collect the trajectory R.h the learner executes the policy at the previous iteration, x x²-1, until time exp
collecting the trajectory Th-1 then executes 4 which samples action sequences from Q uniformly. The particular choice of the exploratory action sequences Q comes out of the proof (see proof of Lemma 5 in the appendix). Intuitively, act (cQ(-) allows us to estimate the prediction features " (m
TH
J.h
[P(g (k-1))leQ.--> and act x Q.) allows
estimate MM (3%) T (rh-1))
The collected trajectories are added 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 0 by selecting any model in a constrained set B* defined as
{0 O O vh, (Th, RT) E Di, (Th) 2 Pmin }
min
log P (TH) - }.
(17)
1
A E @ min
Σ
log (TH) 2
max
Σ
d'eet into (DD
(TAA)EEDA
The introduction of min ensures that P7- (Th-1) is not too small so that the estimates of the prediction features Tx (1 ) [P(g - 0. 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 Th, whose prediction features have so far been unexplored. To do this, Algorithm constructs an upper confidence bound on the total variation distance between the estimated model and the true model. This is done via bonus function 8* (TH),
H-1
(TH) = min
(TTA)
where,
(00)
h=0
(18)
- = X +
Σ TAED
(T)
(T.)T.
where À and a are pre-specified parameters to the algorithm. Thus, the bonus function captures the degree of uncertainty in the estimated prediction features ((T)). particular, the bonus b(TH) will be large for trajectories whose prediction feature (TT)) lie far away from the empirical distribution of prediction features sampled in the dataset D This is captured by computing the norm with respect to the covariance Ü,-.
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.
25

---

Algorithm 1: Learning Generalized PSRs (e.g., POSTs) via MLE and Exploration with UCB
for k ..... K do for h + L..... H do
Collect TH R.h
(Wh-11 11 h-1)) using v(x -1, k.h
k.h k.h
exp
Di-1 -D U
T u ( 1.
end
H-11 D = (DD) ii=
Compute MLE E B*, where
θ + min
{0 V0: (T) E Dh, PT 2 Pmin
0 E min'
Σ
log Po (TH)
max c
Σ
log P (TH) - B
(TH,T)EDE
(NM TT)
Define the bonus function, (TH) min
{ H-
{ (a1 ا
|
(T(N))
(10g)-11
where
T = En. (n,) (Tx)
Solve the planning problem to maximize the honus function x² = arg max, V 06 (Tr).
if B @k (m²) S c/2 then lr gh. break.
end
end
return π arg m v V (T)
We extend Huang et al.'s 's theoretical guarantees to show that Algorithm enjoys polynomial sample complexity for generalized PSRs (Definition 3).
Theorem 4, Suppose Assumption 1 holds. Suppose the parameters Punins X, a. B are chosen appro- priately. In particular, let
6
7 A max VF, QAVH//>
Pmin 5
KH
11
11
[X
VdH
QAVdHA
max X QAVB
BB O (log (ol)
Pmin KH
a
72
Then, with probability at least 8, Algorithum I returns model 6 and a policy that satisfy
(=²(T)) v (z) < s, and Vū, Dry (Pă. (TH), (P (T)) S
In addition, the algorithm terminates with a sample complexity of.
((+
Q2H 72
rdH3 max,e [X, 2- Q48
2122
Proof. The proof given in Appendix J.
This result shows that the sample complexity of learning generalized PSR depends on the problem size through a few key quantities. In particular, the sample complexity scales polynomially in the underlying rank the dimension of the PSR parameterization d, the size of the action component of the core tests QA. the time horizon H, the conditioning number ? the size of the action spaces max.c.A |, the log covering number log (e), and the desired suboptimality error e. Note that Ò omits logarithmic dependence.
26

---

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 S max [1 If this POST is a- robustly W revealing, then by Theorem 2 it admits a y-well-conditioned generalized PSR parameterization with 7 = a/ max [T [1/2 and the m-step futures core test sets. Moreover, have = max; d, = max, [2% The following corollary states that Algorithm can learn a partially-obeevaale sequential team with sample complexity which is polynomial in the size of the information-strucee
state space max
Corollary 1. Suppose a vartially-observabee sequential team is m-step a-robustly It It-kkakly re- vealing as per Definition 6. Applying Algorithm I to this PSR representation, with parameters Puning b, ar B chosen as in Theorem 4, returns e-optimal policy with a sample complexity of.
δ ((1+ Q2H a²
max 11, 7. mmax, (0%
H m [x1] maxxEu
[Xol Q7
a²e²
We can interpret this result as saying that the information structure of sequential decision-making problem, through the quantity max [. is fundamentally a measure of the complexity of the dynamics which need to be modeled. As result, learning is tractable when max, [T) is of modest size, and intractable otherwise. Recall that max,, [17,1 is small when there exists "state-like" variables, whether they are observable unobservable. In this sense, max [t] is fundamental quantity which generalizes the notion of "state". For example, in the case of an m-step a-weakly revealing POMDP, our algorithm has sample complexity of poly(S, (OA) .HH a a-) e²? where S is the size of the state space, O is the size of the observation space, and is the size of the action space. This is similar to the sample complexity of [36, 37J, which designed an algorithm tailored specifically for weakly- revealing POMDPs. Our algorithms, together with the POST/POSG models, enable sample-efficiem 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 sample- efficient learning of POSTs. We emphasize that other PSR-based algorithms can be extended in similar manner. In the next section, we tackle the problem of learning in the game setting where different agents have different objectives.
F Extension to the game setting
F1 Partially Observable Sequential Games
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 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 admits. There has been a plethora of work in the game theory community studying such problems.
Analogously to purtially-observarr (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 kemels. In contrast to a POST, agents in a POSG may have different objectives. In POSG, there exists N agents, with agent i E [N] deciding the actions at times E A', where A C A. Each agent has its own objective defined by a reward function R'. This is defined formally below.
sequential teams, we define partially sequential games
Definition 7 (Partially- -bbservbbl Sequential Game Model). A partially-observabe 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 C A the index of action variables associated to agent E [N). Each agent has a reward function R IIE X, + [0, 1] which they aim to maximize.
Denote by X' (T. : 1 E A') the collection of decision kernels belonging agent i, one for each action they take. Denote by (xx) ...., x NN) the collection of all agents' policies. Fixing π induces
27

---

a probability distribution over X1 x ... Xr in the same way as in the team setting,
P XX = 21 XT = ø1| II
(z fa, e I+)) II
(a fxr a E IT)).
(19)
rES
YEA
The value of a policy æ for agent i E [M] is defined as the expected value of their reward I² under IP"T,
(i(T) = V'('', () = E (X.)) X,()))
(20)
where π --' (T ().
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 w St which is sampled at the beginning of an episode. Then, the policy at time L E A can be modeled as a deterministic function mapping the seed w and information variable in 4 to an action X,. That is, T. Q x 4 + X To model independently randomized policies with each agent having private randomness,
consider the special case where the seed has the product structure w. = (W1,- (Wi,...,,4 ,,,, E Q x ...... x fi,, and w; is the seed belonging to agent i E [M]. Then, for t E A', ne Q2 x I + x. For each agent E [N], define the three policy spaces,
1. Deterministic policies, 1m = { n² (IT : 11ee + Xee t A
2. Independemtl--randoiizze policies, rind = -- (mx -2 x Dr + %x, E {
3. Correlated randomized policies, NV cor { {T²² : (IT Ω II + X,, A
Define the joint deterministic policy space, as det l'1 independently-randdiize policy space T ind, and the correlated randomized policy space Toor-
x r and similarly for the
When studying games, a common question is to find an equilibrium within particular policy space. At a high-level, an equilibrium 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 best-response. Suppose that agent i's policy space is I (e.g.. Fast det.
I ind: or ) Then, we say that agent i's policy n¹ is a best response to π 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 π,, x² is said be best-response to π. in the policy space I'd (e.g., Fdet ind or coor). if V π 1)- maxxigr Vi π ")
) =: V+t((=
This leads to the definition of two notions of equilibria. A Nash Equiliiriium (NE) is a joint policy policies. A Coarse
where all agents are responnspn in the space of segpeendenll--anddmmiinn Correlated Equilibrium (CCE) is joint policy where all agents are best-responding in the space of correlated randomized policies. The difference between NE and CCE that the randomness in the joint policy must be independent in an NE but can be correlated in a CCE. Since I Find C I coor, coarse correlated equilibria are a generalization of Nash equilibria. We define them formally below.
Definition 9 (Nash Equilibrium). A joint policy π E l Tind is said to be a Nash equilibrium if for all agents i E [N], (TT)= = max V* π 1) =: Va.t ( "). A joint policy π E Tind is said to an e-approximate Nash equilibrium if (TT) 2 Vi-l (m= - for all E [N].
Definition 10 (Coarse Correlated Equilibrium). A joint policy ा E Teor is said to be a coarse
correlated equilibrium for all agents i E [N], V'(rT) max V' -i) =: (7-((Tr"))
joint policy π cor is said an E-approximate Nash equilibrium if V (T) Z Vht(a & for all i E [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 independentt-rrndonnied
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 E Ω can be modeled as an observable variable time = O which is in all agents' information sets. Similarly, independently randomized policies can be represented through different random seed for each agent at time t = 0, and including the appropriate random seed in each action's 's information set. Hence, the information structure itself can decide which equilibrium notion are interested in. Moreover, this allows to consider additional notions of equilibrium
28

---

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 order to model randomized policies does not affect the information -ttautuual state Ij since the seeds don't 't appear G For concreteness, we focus on NE and CCE in our presentation.
F.2 Characterizing the Sample Complexity of Learning an Equilibrium via a Self-Play Algorithm as a function of the Information Structure
We now introduce sample-efficiens 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 information structure admit well-conditioned generalized PSR representation, they can also be learned sample-efficienty by this algorithm.
sequential games with Z1-weally revealing
The algorithm propose is 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 sequential decision-making problem falls within the game setting if each agent has their own objective. Following Section 2.1, we consider a sequential decision- making problem (Xi..... Xb) 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' A, where {A') ]ej]]] partitions A. Each agent has their own reward function R' fall within this framework.
X Note that POSGs as defined in Definition are structured models which
Equilibria and policy classes. Recall that in the game setting, the type of randomization in each agent's s policy affects the set of equilibria in the game. In Appendix F.I, we formalized this randomization by introducing random seed w E Ω and allowing each agent's policy to be function of their information set and this seed. If the seed has a product structure = ( "61,...,W. WN) with each policies, denoted by r Tind-
agent observing their own seed, this results in If all agents use the same seed, this results in correlated randomized policies, which we denote by T cor- An equilibrium among independently randomized policies is called Nash equilibrium and an cquilibrium among correlated randomized policies called coarse correlated equilibrium.
Estimating probabilities in the planner. The probability of any trajectory under a joint policy v is given by 1PTT (TH) = P( क (TH W [w].. where IP [TH] = P [T] [ as before, and (TH (w) = II 1(a = T (T generalized PSR model 0. We assume that the planner has knowledge of the randomization, P [w]. Hence, the planner in the self-play algorithm is able to compute the probability of any trajectory for each choice of policy.
Recall that the probabilities [Tw] are estimated by the
Algorithm. The algorithmic description is presented in Algorithm 2. In the first stage of the algorithm. the centralized learning agent has unified goal: to explore the environment. This is done by executing policies which maximize the bonus function (TTH) 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, computes the equilibrium using the estimated model directly. That is, ComputeEquil 1 hiupuillbbbrr irrium computes either NE or CCE. The only difference in the exploration stage of the algorithm compared to Algorithm is that the termination condition involves E /4 rather than e/2 in order to guarantee an e-approximate equilibrium under the added complications of the game setting.
Theorem 5. Suppose Assumption 1 holds. Suppose the parameters Pmin X, O, 3 are chosen as in Theorem 4. Then, with probability at least - 5, Algorithm 2 returns model Of and a policy π which is an e-approximate equilibrium (either NE or CCE). That is,
VJJ (T) 2 Vg (T -E, Vi E [N].
29

---

Algorithm 2: Self-play UCB Algorithm for Sequential Games
for k ..... K do for h + L..... H do
Collect TH k.
k.h k.h (Wh-11 11 h-1)
using v(xa-11 exp
-.,1))
Dh-1 D U
T u 1
k.h
end
D = (D))
H-11 i
Compute MLE E B*, where
θ min
{0 10, (T) E P7 2 Pmin
0 E O min'+
Σ
log (T
max c
Σ
log P (TH) - B
(TH,T)EDE
(TM TT)
{
Define the bonus function, (TH) min {
(al -
H-
(T(())
((t))=1 J where
T = Er. (Ta)e (Ta)
Solve the planning problem ** = arg max,
V / (T).
if B (T*) S c/4 then
gh. break.
end end
return π Compute@quilibrrimmd ( { ,..., RN})
In addition, the algorithm terminates with a sample complexity of.
o ((
2al1
rdH3 maxxc 1%,' 2 Q2,
7122
Proof. The proof is given in Appendix K.
To apply this algorithm to partially-observall sequential game, we can use the generalized PSR parameterization constructed in Section 4.
Corollary Suppose a partially-observabee sequential game is m-step a-robustly Il -weakly revealing as per Definition 6. Applying Algorithm 2 to this PSR representation, with parameters Pmnin X, at 3 chosen as Theorem 5, returns e-approximate equilibrium N with a sample complexity of.
(1+
H2 a²
max; |1
maxA Q
H max X -max.E Xa| Q1
2²2
G Existence of Generalized PSR representations and their covering number
In this section we show that any rank-r sequential decision-maan making problem (as per Section 2.1) can be represented via rank-r generalized PSR (Definition 3). Next. we bound the covering number of the class of rank PSRs, which will be important for MLE analysis. Similar results have been established in previous work for sequential decision-making problems with alternating observations and actions [c.g., 33]. Recall that formulation of the generic sequential decision 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 similar procedure prove slightly generalized result.
30

---

Proposition (Existence of Generalized PSR representation). Consider sequential decision-making problem with rank( Th, 0: 1. There exists a generalized PSR representation (i.e, observable operator model) bo, [B (26) be(H)) {Un) such that,
1. (2(()) E RT xr and || [B (2x))22 S for any The
2. 16ol I H
3. ||vall2 S v [ A
4. For any h, Kulliaaay th2 E Bn = U/-
5. For any Th HA, P [ "I (an) (1
Proof. We construct the representation via the singular value decomposition of the matrix D Let Un [ En R Kn,, Vi R be the SVD such that D Un V. Define bo, BR, o% as follows,
bu = Doll2 (x(x)) = UR 1Uh-1l (ws. T = U
Here, (1 denotes an F& by Th-1 submatrix of Uh-1 consisting of the rows (Ih, wa); wh E FF, (i.e., the set of futures where the variable time h is a.). Note that | by convention, a product over an empty set. We verify each property turn.
First, [Tx) = | [Un- 1lon I since Un. Un-1 are unitary matrices. Second,
1bl = Dol2
Σ P
[TH]
P
[Hu]
P
T2l
[x,l
+
#EA
where the inequality since P
[TH]
E
[0, 1]. For property 3, we have
|lull22
F% UnI12
1
||1|
FXI/
where the inequality since Un unitary, and the final equality is since [|Fa| [12 [
Next, to prove properties 4 and 5, we first show the following claim.
Claim. For any history = -Z11..., IN) E HA, h E 0: H, we have (x(I)) ... (i = UN [Pll..
Proof of claim. We prove the claim by induction. In the base case, h 0, DJJ a vector in R.. (note that H.). Hence, Un is simply the normalized vector Un D D ll.. and hence Dooll by- Proceeding by induction, suppose the claim holds for
U. Dj D, Then, we have,
/ Dolla
Bn Ba(x)) ... Bi (z1 Bn (Zn)UU [D]
U,TT Un-il(en.a) U [D] [DTT.l...m
U,T [Un-JU; D (2)
U,T [D]
(1 Fa)snn
U,TT [D] T.T
31

---

where the final equality is because [D] [D (an
11 whl
P wl
[D]] wamm""
Using this fact, we can now show property 5 as follows,
1
u/ Ba(xn)
1
URUU
D
T
[D] J.
FX
177h
|
1
P
wh]
Σ
P Ph wh wf]
F
F
Wh A
W EER WHERR
1
TP
[TR
Σ
Plug 7h R
PP
F
1
IP
[
Th
Σ 1
ERR
P [T
Finally, it remains to show property 4. Consider the linear equation x UUU 1 D Note that UN Dj E R is rank The Thus, this equation has a unique solution. Our strategy to show that iy and wht Emar Ba41 (Ir)) are both solutions this linear equation, and hence II 2h U/4t1 Exair Bat1 (xn). That t2 is solution is clear by definition of the 2/ U D FX "UUU DJ | DJ First, recall by the calculation above that FF 1 DJ is vector in ER where the 7h-th entry is IP [TA [7]. We will calculate the -a-th entry of the vector TUJ Dr when x. wh4t1 Emii1
B (Ih+1),
uht E (
[U DADD
Σ 2ht1
UUUTI (Unlen [UR D
Phtz
1 UNUTUUTT [UNUT DJT
(2
Phti
2h+1
[1JD]] DW) (0x (1
Fh
20+1
P [Th, 2441,
Σ
P [Th, wh]
|
F wa E
wh+t
IP
Σ
Σ
P[wh The wh
P
WRER FREER
IP [[T
Ti Σ
F
P
(TR
Fg F
Fa h+1
P [T 77].
[ 1(h+1EA)
where the final inequality is since | = -IIen--Lrr (1xo ((sEA)).
Corollary 3. Consider a sequential decision problem with rank < r. Then, there exists &Rexr, uH E TR" such that,
generalized PSR bo E RR,, (2x())))ee) H...,,,.......
1. [B 1l < wh, xn E Xx. lbbo 12
H and || $ 1.
2. For any TH H., P [H BH ... (x1))
32

---

Proof. In Proposition 2 we constructed such representation with dimensions in terms of ry instead r. Since гy S r, we can pad this representation with dunmy columns and/or rows filled with zeros to obtain a representation with dimensions in terms of
An important part of maximum likelihood analysis the notion of a "bracketing number" which controls the complexity of the model class θ [c.g.. 94]. In analysis, the model class is the set of generalized PSRs 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. Og is said to be an "optimistic s-cover" for θ if for each 0 E O, there exists 0 E G₂ with an associated probability measure p such that,
vh, The (T(Tr) 2 Pa [Tx],
wh, Σ Pa(t.) - Fe [T^]] S.. Th
The first condition ensures optimism and the second condition ensures that 6 E-covers θ in the sense that the probability of any trajectory is approximated within error e. Recall that the parameter Algorithms and 2, which appears in the sample complexity results Theorems and 5, defined in terms of [0&]. The next proposition bounds the size of [6x].
Proposition (Optimistic cover of sequential decision making problems). Let Mi be the set of all runk-r sequential decision-making problems with a horizon of length H, observation index set O C [H). action index set A C [H), and variable spaces Mi...., NH, Then, there exists an optimistic e-cover G5 of θ with cardinality bounded by,
02|50(1
100(22 max XA H2 log max
max [% ))
log +
Proof. Define the set of generalized PSR representations constructed in Corollary 3,
bo E IR", (E",(B((E))),.. .H E R': [Bx(x)) I 1, Vh, The llbol12 S V |H U ll2 S 1,
and МTи E H Fm [TH] = By Bu (x ... Bj (21)bo.
where m is a sequential decision making problem in 21
Let Cs be d-cover of the above with respect the lox -orm. For Ø 0= (bo, (rr)) ,nn) E Cs.
define the e-optimistic probabilities as,
Pō(Tn) = Bn(an) ... Bi (b 8/2
We will show that for an appropriate choice of C3 an optimistic e-cover. In particular, for each E θ there exists 0 e Cs such that,
Yh, The (T 2 P. [Ta]
Vh, The
Σ
( - Fo [TA]] | cc
Th
33

---

To choose the value of 8 for which the above holds, observe that
Σ
Th (HH)) ... Bi - 2 (H -B(
T2
H
BH(H)) ... (ata( Be ..- -I--BBBB (21))66
k=1
Σ
T BH ............... (2( 1 bo)
ΣΣ BL(x)) (a
[ +
Σ
Vr to bu/
max
< H max Xx #+|A1/2 rō + max Xx1'" Vró,
|1u BB (2n L, (xn) (x v where the second inequality uses 1 H I. and ( bolla I vrllby bu lcc S vr8. Hence, r [x By, (xx) max I rō, ||bo l2 S v
choosing ā = e max, | for an absolute constant large enough achieves a e-optimistic covering of O. Hence, let O Cs. with 8 maxa |Xa| -et [6+/-
It remains bound the size of
Recall that ||-1lcc I I1-112 and that an interval 1-x, x in admits 5-cover of size bounded by 2r /8. Now, observe that max.j (2x)lur & BB (2A. ll2 I 1. Hence, for fixed h, (zx)) admits a cover of size bounded by (2/5)* "|xul Considering all h, the cover is bounded by (2/5)* Σx [xal < (2/5)² maxa (3,, IH
For, bn. we have liboll < |1bo|12 s VHH hence the covering number is bounded by /2V/1H9//0 Finally for uæ. we have || ||ull22 I 1, hence the covering number is bounded by (2/8)". Thus, have,
)))
log + S O
max XN H log
Recalling that 5 = e max,
Xx cff we obtain that,
θr < <0 (1 max Xn H log
maxa [X
log
H
Proofs of Section 3.2
Theorem (Restatement of Theorem 1). The rank of the observable system dynamics of a POST or POSG is bounded by
max S
KE[H]
1
Proof. We have
Dilm,, = P (Th w/ do(TT,
P [ do (T+)] P Tw
Thi do (Th,
P [7R do (Th) Σ p
[ax & E It} Thi do (8)
IP [ fox, k. E I , Thi do (Th wf) wg)
zz E
kEZz
66)
P do (7
{ IRi 1I
p Jug { a k E Ih Th: do (T8wwh) Thi do (7:)
24 EX,
KEZ
Σ P do (7)) [{ 0k & I/b
Thi do (78)
p w faxs k E Ih}] do (wx))
EX
KEI!
34

---

where step (a) is simply the law of total probability, step (b) is that fIx. k E I is conditionally independent of do(w)) (future actions) given (T%: do(T)) )) (the past), and step (c) is that wi is conditionally independent of (rf; do(r))) given {.z. k E )- This is due to result by Verma and Pearl [95] which states: for three sets of variables A, B, C. in directed graphical model, if A and B
d-separated by C. then A B C. Recall that I is defined the minimal set which d-separates X((s)) from (X (X((+1)........ Xx(H))-
(X((i).-... ((())))))),()))))
As technical remark, note that 8 = (IR,, k E I2,) may include actions and hence,
P Ha & E I The do (T =P ({ sas, le E I ns) Th: do (TR)
i{ (TA, & E nA) matches Th
since the action components of i/, are contained in the history Th- Now define two matrices
D = P do (TX)] {{ axs k E In} Thi do do
marhh" E lil,, i = (Ik, k E Ih) E uh.
Da.2 = P wh
fars Iks h z do (wo s/
s (ax, k IT)) E the wn E Fh.
We have that Dj, = DA,1 Dn,2, where both D,,1 and Dn,2 have rank upper bounded by [m Is [x)) Hence, rank(Dn)) s [1,,, and the result follows.
I Proofs of Section
Lemma (Restatement of Lemma 1), Suppose that the POST/POSG is m-step I -weakly revealing. Then, QT is a core test set for all h E [H]. Furthermore, we have
P [Th,wal] = (mm vn (Tx)) and [wh TM (ma(wn), (TT)))
(21)
Proof. Let Th E Has Wh. E FF, be any history and future, respectively. By Theorem 1, recall that have
Flwn ml = Σ e
wh
Th
(22)
Recall that of may overlap with The In particular, the action component of of is contained in The Thus, Plc r)] = P|[ IÍ, U1 Th] 1[( k IÍ, n U1.k) matches 7h Note that IJ M C S does not contain any actions. Hence, the summation over I7, is equivalent to summing over its unobservable components with the restriction that its observable components match The
and ph: H, +B by Define the mappings m. FA, + RR 1
IP wn [1]] &l]eter,' PM(TT) = [[P((t) Th t,t,
(m(w))
Then, we have that the conditional probability of the future wn given the past ты given by the inner product of the above mappings, P[w, | ml = (mn((w)) pa (T.)). Recall that the vector of (conditional) core test set probabilities for the history Th is given by (T,) = [IP ia [ do(r)), do(a") do(("))]l M,err E glo.l By the definition of G,, and Equation (22), we have Ph(P)T th (Tr), since, for 9 E Q.
(G. (G.Pa(TT))
= Σ (Gi)gat (Pn(T)))sg
2
Σ P q ohss do(a))] IP lih Th
s)
= =P Th (
=: [<))),))
35

---

Since by assumption rank(Gr,) = [ its pseudo-inverse G is left inverse of G1, (i.e., G I). Hence, multiplying on the left by G/2- we obtain ph = G.,,% (Ta). Hence,
PP [wo Th]
(inn(w)) G G/,n)(T))
G
(w(())) V va(Tm))
(wrh)
That P wp] = (ma(wa)) (h (Th)) follows directly by noting the definition of (Th)
==
4h (
Hence, we have shown that for the test set Q the probability of each future wi given a history The a linear combination of the probabilities of each test in the core test set with weights my (wn) ==
(G+) ( (m((w)) E ( depending only on the future and not the history.
Theorem (Restatement of Theorem 2). Suppose a POST/POSG is a-robustly m-step -wekkly revealing. Then, the corresponding generalized PSR as constructed in Section 4 is --ell--coniiiooed with = a/ maxk 1/2.
We will first show that (1Q) h. ΦH, {Ma Jas v/) indeed forms PSR through a series of simple calculations.
A direct corollary of Lemma 1 is the following.
Lemma 2. For any h E [M], Th-1 E [H4-1, Te(h) E Xe(n)) Wh E Fh. we have
P [Th-11 Ze()), (m--1 (xFe))) wh), on (n(Tn-1))
(23)
Hence, given a history Th-1 = (I+(1)...... 1)). having observed another variable Ze(k)) we can update our predictions of the future and obtain the probability of trajectories of the form (()))))(())))))))) for any future W/. E F,, Note that Tz(h) may 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 in contrast 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 Zz(h). we can use the my : F2 + Rdd mapping constructed in Lemma to update the probability of any candidate future wh. We are particularly interested in updating the probabilities of the futures corresponding to the core test set the next time point, since this provides a sufficient statistic of the past. Thus, we define the matrix mapping MA." X)())) + xd.-1 by,
[Ma(Fi))) = 1 T, q Qn.
(24)
That is, Mn (Ie( is the matrix whose rows are indexed by the core tests at the h-th observable step, where the q Qn row is the weights given by the mA-1 mapping for the future consisting of T((h) followed by q. This mapping enables us to update the probabilities of the core test sets.
Lemma 3. For any [|]- 1], The HA, T((++1) X((++)). we have
(n( x(()) Mr (hn
(25)
Hence, for history The (E(())...,, E HH,,, we have
*T((T)) (o (E M1 (F
(26)
where 1ho = vho (0).
Finally, observe that Qn X((H)) Hence,
W = -PP (h--1 I(H)) ) Excon [
36

---

Thus, letting 0H : X((m) + (H)(( be (H(()) = Ex(() (the canonical basis vector), yields
P [ h e [H] (x(())
MH-1((((1-1)) "M-
M1(2x)))
(27)
Hence. Equation (27) together with Equation (26) imply that (M, @H vo) a valid generalized PSR representation for the POST/POSG (as per Definition 3).
What remains is to show that if the POST/POSG is a-robustly -1-wellly revealing, then the PSR constructed above well-conditioned.
Theorem (Restatement of Theorem 2). Suppose a POST/POSG is a-robustly m-step Il -eekly revealing. Then, the corresponding generalized PSR as constructed in Section 4 is w-eel--coniiiooe with = az/ maxk 11/2.
Proof. We first show condition (1) Assumption 1. Suppose H m and hence the core tests are the full futures, which have length smaller than m. Then for any x: E RR dn =IT Xg). we have
max
(wn) xx| (ww) = max
| ((w)) S ||>|||
where x|wn]] indexes the component of the vector x corresponding to the future wh- Now suppose h < H m (and hence the core tests consist of m-step futures). Then, we have,
max Σ mm (wn) Tol o0| (ww)) max
m(wn) G...lar T(w))
max
(m(wn) Ghe;t e -
v(wn).
Wh del
Now observe that for any policy and any it I/ we have
Σ m((wn) GRen T(w))) = Σ m(wn) G Gnen
x(()))
wh Et| (Wwx)
po
(w
[t]]
1,
where we used the definition of my (w.) my (wx) T and (on((w))) )[pt π (wi) such that for any fixed sequence of observations wp. Eup π (wh 40)) = 1.
P P(wn |d]]. Recall that
Putting this observation together with the preceding inequality yields
mn (w)) Tal x(w))
max
c
tt!
|
<
G
||1/
|ل||
a
where the final inequality is from the relation between the one-norm and two-norm G
G and | s
1 a- by the assumption on its singular values.
37

---

Now we show condition (2) in Assumption 1. For case of notation, we denote 21(2) by 2h. When h > H m, note that (Ww)lal = 14 (o), 9+11)). for all Qh. go+1 E Q++1- Hence, we have
max Σ (|MM( ((x))= = ||
Now, when h I H m, by similar line of reasoning to the proof for condition (I), we have,
max Σ
max
Σ
Σ
c Mp (an)))ane
26
(2h 1),,, x
Qi Ieel
Σ
E
(T) qa+ (
|ei G =(nn|m-))
max
(Rhi0h 11)EXA x Chil
max
Σ
P
[Tns
Th41
| a(tonlooi))
|cTot///
(FN (1)
where step (a) uses the definition of M, and step (b) uses the definition of ma(wn) = and [mn (wh)) == Plwn 1tt]. Now note that,
Σ
P [T 9h+1
(t] (2
E
Σ
P Ih. (bs(q)+1) it, act(gh+1)) 1)] (x*))
(It (1)+1)
2h act (T++1) 1b=())++)
Σ
act( (1)
where the second line is since for any fixed action sequence, the sum the probabilities of all observation sequences is
Thus, putting this together, we obtain the following,
[a T(x)))ll(xx//ann s Q
G/all,
max
@
||
where the last line again follows by the assumption the singular values of G
Proof of Theorem 4: UCB Algorithm for Generalized PSRs (Team Setting)
In this section, we prove Theorem 4 which states that Algorithm returns a near-optimal policy a polynomial number of iterations. The proof adapted from [35] and generalized 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 eтror of the observable operators {Mr h.- In Appendix J.2 we state some general results on maximum likelihood estimation which show that the MI.E model has small error on the collected dataset. In Appendix J.3 we prove that the bonus term is 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(VK)) Finally, in Appendix J.5 we put this all together to prove the theorem.
J.1 Properties of Generalized PSRs
Recall that PSR model 0 (M, vo, ΦR) consists of operators M = [Ma Mr X Id Xdh-1 0H XH pdd -1 (assumed to be the identity mapping), and the (assumed to be known
38

---

for the purposes of presentation). Recall that, for any trajectory 7h-1 = (I1..... Th-11), under model
have
(TA)
Po (Th-1)
1/ (T))
(28)
Po (I 7h-1)
Pe (In Th-1) Po (Th-1)
S (Th Po (I0 T1-
Here, the notation I' (Ia Ta-1) means the probability of 2 conditioned the history 7h-1+ with all actions executed. In particular, if Tn is an action, then Pe (Iy I Th-1) 1 and MA (f (T.).
The following proposition shows that the total variation distance between the distribution of trajecto- ries of two PSR models can be bounded in terms of the difference in their observable operators.
Proposition 4. For any policy and 0,0 O have,
DTV
p 8r
P
Σ
((T))
mr (wn) (Ma(ar)) Ma(un)) wh (h-1((Tn-)) ((Th1))
h=1 TH TH
DTv
p
p
Σ
((Th)
ma(wn))
(M((xn) Ma((a) Tn-1(Tn-1))
h=1 THE
Proof. The probability of any trajectory TF (......, IH) can be written in terms products of the observable operators (2x) of PSR model (Equation (1)). Hence, we have,
Drv
pat 1
1
Σ
pa (TH)
P (TH)
2 TH
H [II
1 Σ (TH))
Ma(an) vu M==
II
Malen)) 20 Am
2
(TH)
Σ (
(M((zw) (M((an)))M((M)) on (n-1(Th-1)
TH
where the second line follows by the triangle inequality after noting that for any trajectory TH = J1.1 Hr the following holds for any h = 1,..., H1
II Ma((aa)
II Ma Mn (2n) to = fan (Zn+H.) "MM( (2 1) mm (xn+11H))
voo
By the same argument, we obtain the second inequality,
Drv (p_ p7
1
Σ
p (TH)
PT (TH)
2
< 2
Σ n (TH))
my mm(#n41HH)
Pn-1(Ta-1)/-
TH
In this result, recall that we assume tho known to the agent, simplify the presentation. th was not known, there would be another term due to the estimation as & [see 33, Lemma C.3]. Note that the sample complexity of estimating the is small compared to learning the other parameters.
39

---

J.2 General Results on MLE
In this section, state some general results on maximum likelihood estimation which ultimately guarantee that the estimated model produced by the procedure in Algorithm has à small estimation error. The results stated without proof. The proofs 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 ongllikelihood of the true model 0* is large compared any other model.
Proposition 5 (Proposition 4 of [35]). Fix
1 KH
With probability least 1 8, for any B Oe
and any k E [K] the following holds:
K
4O E +o
Σ h (Tb,a)EDa
Σ
log (T)) log
log (Tn)
h (Tax))ED
+
AO E Oe,
lo 1 (TH) 3 log
S
log P- (Ti)
(TH,
The second proposition provides upper bound on the total variation distance between the distribu- tions of futures given histories on the empirical history trajectories. This result ensures that the model estimated by Algorithm is accurate on the sampled trajectories.
Proposition 6 (Proposition 5 in [35]). Fix Pmin and S
Pmin. Let
KH
@ = {0: Yh, (Th, πH) E Di, Pg (Ta) 2 Pmnin }- Then, with probability at least 1 - 5, for any
k E [K] A E e S we have,
PT (TH) Σ
K |
Σ
DIv (PT (wxlTT)) <6> (D
log
P (TH) + 31 log
(NA)))DD
The next proposition is standard in the analysis of maximum likelihood estimation. Da denotes the Hellinger distance.
Proposition 7 (Proposition 6 of [35]). Let K Then, with probability at least 1 6, the following holds for all 0 Q and le E [K].
P (TH) log P (TH) + 2 log
K
0 5
Σ (IP) (TH), REDI
(Tn)) S
(TH.T)EDE
The final proposition of this section states that when Pmin is chosen as in Theorem 4, the true model 0 lies in the constraint O t with high probability.
Proposition 8. Fix Punin I KHIT [al'' Then, with probability at least - 6, we have 8* *
min
Vk.
Proof. For each & E [K], we have 0r E min if P (T 2 Pmiin for all h E [M], (r E DD Consider the probability of 0* violating this constraint for some trajectory in the dataset. For each k, h, (Th T x²), we have
1P5" (Th) < Pmin IP
Ex
P
ppp (7h) < Pmii = πT
Ex
Σ po. (T 1x)1 (Tn) Pminn
E
Pmin
Ta EEl
[H Pmin
8
KH
40

---

be the In the above, the first line is by the law of total probability. where the expectation is over the policy x used while collecting the (h, kt trajectory, and the inner probability over trajectories Th- The
second line calculates the probability of the event {IP@- (Th) < Pmin Taking a union bound over k E [K], E [ and (Th, x) E Di, implies that IP (0 E O
min 2 1 6.
In what follows, let Ew: Ex, Emin the events in Propositions to 8, respectively. Let & E O E n Emin be the intersection of all events. Propositions 6 to 8 guarantee the event & occurs with high probability, P [&]
35, by 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 over full trajectories. The result follows from the MLE analysis in Propositions to 8.
5 K and suppose S K" II, 1x,7
Lemma 4. Let B = 31 log in Proposition 3. Then, under event &, the following holds,
where O is the optimistic E-nel
Σ
Σ
Dīv
P
(wn((T)) (T), 19 (WnlTT) (walTn)) S 7,8, and
h
(FRIT)DD
Σ D
(TH): s 78,
TEDI
Proof. The proof follows by Propositions 6 to 8. The argument is direct and identical Lemma of [35].
J.3 UCB for Total Variation Distance
Notation. Let m", [MM be the observable operators of the true PSR 0", and let [M,), Jn algorithm's estimates of the observable operators corresponding to 0%
Recall that Proposition 4 shows that the total variation distance between the distribution over trajecto- ries of two PSRs is bounded by the estimation eтror of the observable operators Mr, The following result constructs a bound on the estimation error of the observable operators Ma (xx). The proof is adapted from [35, Lemma 2] to our setting with generalized PSRs.
Lemma 5. Under event E, for any policy and k E [K]. we have,
Σ Imm(wp (wa)T (M))) Mi(an) 1 )/ x(TH) S E. PPg ah-1
ak Vh
(Th-1)
10
where,
Lk
Ū1-1= -
Σ
(ah=1)² 2 4XQ2d
4 maxxaa 1202 202
Σ
Dāv (P"
% (wh (0-1 P² (wi mh-1,00)
72
Proof. To ease notation, we index the future trajectories wh-1 (sh aH)) E FA-1 by and his-
tory trajectories Th-1 (x) 1h-1) E HA-1 1 by j. We denote mn (wn) (M(()) M (ax))
as T. ck (T) as Zy. and π (wh-1 (1-1) mTy.
41

---

The following bound follows from the Cauchy-Schwarz inequality,
m² (wn)
(1n) MM(wn) (Ta- 1) (TH)
(w/) (M))))) -M(())) on ( 1 (Th-1)
Σ
Kuy Tzy Tals (i)
Σ
E (Tai) sign(w, x, )wi) 2j P (i)
Σ
Σ Tily sign(w, az)ws)
Iy p (i)
= E Σ Tals sign(w) xzy) 2z)mus
Big
(6)
S Ey BynPy
|15)1(0= )
Σ Tay sign(ws x;)) ws
13
Step (a) follows from the fact that / (Th-1) 1/ 10h Ti 1
(mh-1) の (T
Fog [TA-2] and Fog [Th-1] ((TH) = (wh-1 ( P. (Th-)). Step (b) is the Cauchy--uhhhiee Schwarz inequality.
Fix Th-1 = jo. Let 4 = Σ jo sign(w) (w, zj,) wi ب which we bound next. By the
definition of Eh we partition this term into two parts,
1 = A Σ Telso sign(w, xzj)) wi +
Σ
Σ
Tajdo sign(w, xz0) wi
Ttj
JEDT
We bound 12 and la separately. By the triangle inequality, VT2 is bound by sum of two terms,
VT = V
Σ To sign(w: x06)) w.
max
zER -1]===
VA max
Σ
m" (wT)) (M)) (zn) M((())) 2) (wn-11)j)
|| Wh-1
(b)
V max
Σ (wnn) MM (II)) Twnn-190)
||l|| m1
+ max
Im (WT)) ((W)-
|
Wh-1
where step (a) is by the definition of wT Asjio and the triangle inequality, and step (b) is by the triangle inequality.
42

---

Consider the first term. It can be bound via the definition of o-well-condiiinn as follows,
max = =112=1
Σ
(wn)
MM (2x)
क (wnn11)50)
wh-1
Σ
Σ m² (wh) MR (2r) ((uulbb.=))) T 1jo)
max
|=1|==1
max
Σ
/ (sTn) >
T(znl50)
||=||2
3/.
39 1 max
12 ||2||1
7
||
VdQA
72
where step (a) is by the first condition Assumption 1, step (b) is by the second condition of Assump- tion 1, and step (c) is by the fact that max = | = Vd S vd and |Q s QA- In the above, note that we used the 7-well-conditioning of PSR @h in step (a) and the 7-well- conditioning of PSR 0* in step (b). The second term in vT2 admits an identical bound, simply by using the well-conditioning of the PSR 6* in both steps. Hence, we have that
I2 - 4 AdQQ3
(29)
74
Now we upper bound 13.
2
=k m (wa)) (M (xm) - Mi(un) v (Tn (wwn
13
Σ
Σ
IEDA
Wh
Σ
Σ w
m (ww))
MM (5h-1) - -M,1)-M (Tan)) (Tn-1) π T(wn-1150)
Th-1ED
14
m" (wh) (M)(aN) ( (Tn-1) - 25 () ((wn-
Wh-1
16
Σ (1++
Th-1 TR-1ED4
where the second equality follows from the triangle inequality by adding and subtracting (Th-1) inside the absolute value. We now bound each of 1 and 15.
m² (wn))
43

---

(In)) ck (Th-1) (xn) (m-1)) (( n(wn-1ljo)
- 4
m (=(w))
(
m= (wn)) T (Pge (ar Th- (all) (T)) Fog (an T- (T()T) a (wn--1lo)
-
(wn) T (Por (xp TR-1)V((TA) - Po- [aaa Th- wí (Tn)) ग TT loo 2nn) (xxn(o))
(2n Th-11 1n-11(n(TH)) - Fo- Jan 1 U7
2 (Th)
((mn)jo)
(4)
Po
[Th, 4h
[h-1] Pa. [an, gh [T- V (Ir(jo)
where step (a) is by the fact that MA ( (Th- IP [rn Th-1) (Ta)) shown in Equa- tion (28), step (b) uses wh-1 = (n%, wh) and π 150) = π (a (oo) (wn)) Jo. rn). step (c) is by As- sumption 1, and step (d) follows by the definition Vha [T)( Fe [ mA].
Now, we turn to bound the Is term. We have
Mt (oaaa) (0 (Th-1) (Tn-1)) (T(m-1) )
Is = EE (w(wh)
(wnn (a)
Wh
1ab m (wh-1) Φ
(Th-1) - (Tami) ( T(wn-1150)
Wh-1
(a)
(Th-1) - 15 (m6-1)]
1
P 1 1 Th-1]
Po. (ah-1 Th-1l|
Qn-1EQ4
where step (a) is since (w)) Mt (3)) = m (w step (b) is by the first condition of As- sumption 1, and the final equality is again by the definition of tb Combining the above, we have that,
13 S Σ
(44 + 16)
Th IEDA A-1
Σ
Σ
p [nn 2h [--1]] - Pe- [i Ih [h- T ((n
Th
E en E2u
ge (gh-1 Th-1) Po- (gn-1 Ta
-h-1 C
1
Σ
Σ
F [an. Th-1] Fo- [0 ah F--1]| a (xn((T--1)
22
Th-1 ED
(Ka.9h) X
h-1
P (gh-1 Th-1]
Po- (gn-1 Th |||
Now, we decompose the summations above over X, x QA and Q--1 into separate summations over observation futures and action futures. That is, (Ih qh) is decomposed into (i--1.4_11 where w act( qn) and w obs(zn. qn), and the summations over w aXt(XA Q.)
44

---

and - E obs( XA x Q.). Similarly, 94-1 can be decomposed into E (bs((1-1) x act (1) Hence, the bound on 13 can be written as,
13 S 72
Σ
[wh- Th [1-1, - Po.. [wh-] Th Th-1, (
g
Th ED
With 1
wi h-1
Th 2h-1. Pi 111 Th-1. -oo [gh-1
Uk ph-1
-1 48
2
<
1
Σ
go [wr-11 7o-1,4/h11 - Fg. [wh-1 Th Th-1; 1h-1:
72
Th-1ED
Wh-1 E Ch
Wh
1 Ceep
2
Diy
(Pa-1 (wh-1 Th-1, 11- .F P (wh-1 Th Th-1,
72
Tn-IED! R-1
Where the second inequality by the definition of Qx act (XA. x Qn Qh-1). Here, the second summation is over - obs (Xn Q Qa-1). 1). The final equality uses the fact the under the policy exp the probability of each action sequence w is 1/ 2x Note that [2, S Jact (%& x Qx. + lact (Qh-1)l, and hence we have [Q S 2 max.EA [xa Qa for all h. Hence, have,
I3 S 4 max X,
Q222
Σ
DIv
Th- 7h-1,wh-1) . P (wh-1 Th-11 wh) (wh-1
SEA
72
Th-1ED
h-1
(30)
Putting this together with the bounds on Iz and Iz, we get that,
4XQ2d d
1 S
+ 4 max
x.1
Σ Th-1ED
DIv (1" (wh-1 Th-1, wh
,P Py (wh-1 Th Th- wi.
7
SEA
=: 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, 0h and the true model 0r, is bounded by,
H
2
Drv (Pg. (TH), PT- (TH)
(T-(()) S a BTg
Σ
(Ta)
(31)
(0
for any policy where
4xHQad yx
[ Q4 1
+ 28 max
AEA
Proof. Consider _ in the previous lemma. We have that,
Σ (a
4XHQ&d d
+ 4 max
X
22
1 H
Σ
Σ
Dīy pp%=1 (wh Th-1, wf ,P -..-1 (wi To-1,
74
SEA
77
h=1 TR- A
4XHQ3dd
1
max EEA
1 0₂ 73 =
24
45

---

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 emror:
DIv
12 g (TH), (TH(
H
m" (wa))
- -
0h- (Tn-( (T())
TM
-k
k ah-1
-h- (Th-1)
jk
hm1
H 1
k (Th)
E wo
1
(083-1
h==
where step (a) is by Proposition 4, step (b) is by Lemma 5, and step (c) is by the Cauchy-SShwaar inequality and the calculation above bounding Σn (a%
A direct corollary is the following bound the error in the estimated value function, which establishes that the bonus term 8e gives an upper confidence bound. Corollary 4 (Upper confidence bound). Under the event for any & [K], any reward function R: IIeENH Xn - [0, 1]. and any policy π, we have,
V Bc
(T) - VoR(T)) S V
where (TH) min a
Σn
1/
(Th)
((())- 1
Proof. By a direct calculation,
V.ll Vgl((T)
(T)
Σ R(TH Pg. (TH) Σ R(T (TH)
0h
TM
TM
(a)
pot gk
(TH) -P7- (TH)
Drv
[ (TH). PT. (TH)
H
Erw Ni
Σ
(Th)
h=0
(0))-1
(TH))) (TH)
where step (a) is by the triangle inequality and the fact that R(TH) E [0, 1], step (b) is by Lemma 6, and step (c) is by the definition of t.
J.4
K -k-1
is sublinear
The next step is to prove that > V O(VK). To do that, we first prove that the estimated prediction features and the ground-trun -tunt prediction features can be related through the total-variation distance between the estimated model and the true model.
46

---

Lemma 7. Under event for any k E [K]. we have:
m-
B
(0:)-1
h=0
2HQA Drv Vi
P (Th)) + (1+ max
[x,
QavTrB Tr
H-1
Pg- (Tn),
E M.
(Th
V
h=0
Proof. First, we recall the definition of Üj, and we define its ground-truth counterpart replacing estimated features with true features,
Ü AI + Σ
15 (Th)
(TA)
TED
U = AI +
(hh
(Th)
TED
For any trajectory Th E HH, we have,
(a)
H
(T))
2i (Th)
(()))-
(θ
h=0
h=0
Vr
Enedi
(T))))
(5n)))
H
H-1
vT - (
+ Σ
1+
1
11
(T))l(
VX
h=0
where step (a) is simply using ||=]||2 S ||||| and step (b) is by the identity [35, Lemma 13). Note that is the rank of the PSR and r 2 rank (10 (Tr): Ta H4 H), (ank((f (Th) Th H.))) Moreover, we have,
W - (Th)
S
2 (Th) ক. (TN)
oh lgh The Ihl
Po. [4h The 9
4h CCh
2 max [ Q
(n2
(-1ma) 1o (1I7))
where we used the definition of T in (a) and the definition of the - in (b). Now, by Lemma 4, we have,
Vr
En
Σ
H
H-1
ED
(
(Tx)
Σ
1
1
(T)
(0)))
h=0
h=o
VA
(T)) - -
I+
2 max [oo QA 7r
QAVTTB
Σ
(T))laa
where the first line combining the calculations above and the second line is by the estimation guarantee of Lemma 4.
47

---

The first term can be bounded in expectation under Pg- for any π as follows,
H-1
E P..
(T)) - (5h))
1sth (Tt) (TT))
2 (Th) (1T.. (Tr) - p. (Tn) + v (T> (Tx) v0 (Th p (Tx)
h=
2 (Th
(Tm) (Ta)
(Tx))
ক (TA) (Th) ক ( (mh uP (Tx)
H-1
Σ
2 (TH)
[ (g.( - F (Ta) + حه (T)) ----~-10 ((>)\ x(Tr)
4=0
7h
H-1
2QA DTv
Σ
(Ti)
12
2HHQADrV (Pg- (r,), PT.)
where step (a) the triangle inequality, step (b) is the definition of (T()), step (c) is since
(Tr)
Q I QA for any Th and the definition of (TT)), and step (d) is simply (TA)
DTv
(
(TA),
2 DTv
(pz. (Tr) P. (Tn)).
@+
Putting this together concludes the proof,
H-1 Σ
E7 Pn
(Th)
(D)))-
2HQA V1
max [X,l QavTrB
H-1
DTv
(T)),
(Th) + 1+
E Pg.
(TW))
VA
h=0
The following lemma bounds the cumulative estimation error of the probability of trajectories. can be proved via an & 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 for any h {O..... H 1). have
max.EA X QAVB
dQ nl
(TH), p= (TH) Σ Drv (TH), &
THHK log [1
Here, a S b indicates that there is absolute positive constant e. e.S. a S c.
Proof. Recall that, by the first inequality in Proposition 4, we have:
Drv (Pgg (TH), Taat (TH)
mi (wn)) (MW) Ma(a)) 1b (Tn-1) (TH))
1=1
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 PSR, the analysis follows similar series of steps. We will use analogous notation to Lemma 5. We index the future trajectory wh-1 (Ih...... .., by i and history trajectory Th-1 = (I1, Th-1)
by j. We denote n (w))) (M)))) - Mī((n)) as wi, xp (Fh-1) as Ty, and π (w/h-1/7A T/ as Talj
48

---

Define the matrix,
AA = 7o1+
Σ E s [m ]
where λo is constant to be determined later.
For any policy и, using similar calculation in Lemma 5, we have,
Σ m (wn)
(xn) - MM((r)) x0 (Tn-1) x (TH)
Σ Tely lucy 235
piytt
Σ Talysign(uu 23))0;
ztj
Σ m maysign(u) 2z)mss
R
jurrg
|100 llat
where the last line is the Cauchy-Schwarz inequality.
Fix = jo and consider the term: ||> : Te jo sign(w] Tio )u: Aa in the above. This term can be partitioned in the same manner in Lemma by simply using the definition of A and expanding.
Σ Ti (w; Izo Ww
An
2
27
Ao
Σ Tsljo sign(uu (n 2z.) wi
+
E
juzzth
Σ Taboo
sign(w, 2z0) w/ zj
tck
12
We bound each term separately. The process is nearly identical the proof of Lemma 5, but show it for completeness.
TT is bounded by the sum of two terms,
V11
V do
Σ Tijo sign(w, xz50) w.
max #E 1:
11]|=||a=1
max Σ
m (wn)
MA (2x)) ) (wn-1ljo) (xx)
| |=
max Σ |
m M7 (2
m(wp-1ljo)
Ap max
m (
m(un
|| 11
wy
where step (a) is the definition of W4, Tojo and the triangle inequality, and step (b) is the triangle inequality.
49

---

Both terms can be bounded by the y-well-conditionin assumption on H and 6". Consider the first term,
Σ
m (wn)
क (wnnn (xn)2
max
||
6h-1
Σ
Σ Wi
n M (wa)) ) MB (xxA)= m(unlio: mmm) n m ljo)
max
||=||| =1
max
M (2x))
x(Inl50)
||=1|==1 2h
(6)
1
Q ||=11
I
max
7
|=
WV
vaQA
7/2
where step (a) is by the first condition in Assumption 1, step (b) is by the second condition of Assump- tion 1, and step (c) is by the fact that =ax ||=||
= Vdn- S Vd and [Q S QA-
In the above, note that we used the --well-conndrionnig of PSR 6h in both step (a) and step (b). The second term in vI, admits identical bound, simply by using the well-conditioning of the PSR 0 in the first step and 0 in the second step. Hence, we have that
4 Aod
(32)
71
Now, we consider the term T2
27
12 S
E Th-
Σ (wn) (M))())) -M((zN) 86 (mn-1) T (w0)
)
- 60
*k m (wn) Ma((n) ( 16 (m)-i) x(wn-1150)
EE
swprtt
p-
Lwh
27
Σ
m (wn) T
(Mn)e) (Th-1) - MM (In (Ta-i) (T))))
T(wn-
11,0)
-h-1
(I3 (1s+ + 1,)
where the line follows by the fact that x S [o| and the line follows from the triangle inequality by adding and subtracting mn (wn) Mr (D (Th-1) inside the absolute value. We now bound each of 13 and T4
First, we bound Ig as follows,
2k (7n-1) x (wn-11)50 m (wh) (M(()) (w(n-1)) w
(
T3-
Σ
(a)
Σ
π ((Wn-1150) m (wn-1) T 15 (T((m_-)) - (ma-1)
ck
Wh-1
(M) 1
Lk
(Th-1) - $ (m--)) (m(m)))
1
Σ
Po (ph-1 Th-1] Po- (gh-1 Th 1n-1]
γ
@h
50

---

where step (a) is since m(w)) (TA) = m(wn-1)", step (b) is by Assumption 1, and the final equality is by the definition of v..
1
Σ
m (wh)
My De (Th-2) - (M) (Tn-1) x ((wn~1550)
wh
m (ww) T
PPg (anh 1h-1] (n((T) - -Po- [x Th 1--11 1 (T))) H m(wn-1150)
m (wo)
(Pgi [xn Th-1) 1l (T Fo- [a0 Th- Un (Tx)) T(uulio.
J.A.
wh
(6)
P or 1o0
Po- (an Th-1] 2/ (Th) T(znljo) Th- 11 (TT))
ga (ath, 9h.
[h-1] - .P-. [Irny 9n Th- 1]] (Fnlio)
9h EQu
where step (a) is by the fact that (14) tion (28), step (b) is by Assumption I, and step (c) is since (T))), Pe 19 mh] Combining the above, we have that,
Plr Th-1] 1] (TA).. shown in Equa-
12
Σ
E
(Ja + 1a)²
tck
E
jrupee g+
Σ
Ps [9h-1 | Th Th-1] Po. [gn-1 Th Th-1]
t<k
-h- EQu-1
27
ge [Th, Th-1] - Po- [2
Th Th- 1l| T (x loo)
Fh EQu
Σ
E
swuggh
@e 4h-11 1h-1] Po- [ 1 Th T1-1]
7/2
KC
Wh-1EQn-1
Po [hh, Qh Th-1] Po. [In, 9n I Th-1]] π (Ix1jo)
Thh ga EQu.
(a)
E
jmppt
Σ
@e [wx_1 Th Th-1, - IPo- [w Th [
7/2
C<
Wh LEO wi-1
2
(F" (wh-1
Py. (wh-1 TT-1 )
E
Th- Th-1,
7/2
tck
Iax.EA [x,]
? RQ2
Σ DĀ
(TH) p ( (TH)
tsk
where step (a) follows from the definition of 0 (same as Lemma 5), and step (b) is because the Hellinger distance bounds the total variation distance and since Q < 2 maxxEA [xa] QA. Hence, we have,
1a < 4 max
Xx 2 12222 22
1
Σ P
D
(TH) Po
(TH)
SEA
tck
51

---

Now, combining the bound on 11 and Lg allows us to finally bound follows,
[>> m.gsiign( 2, xy)we
lla, as
Σ siggigg
1y)
An
2ad
4max,
[X5 2 Q9
Σ
D
( (Pth
(TH), 1- "n(a"",07 10 (TH)
7/
72
tck
(ati-1)
We choose Ao=
-
and bound a² == =En (ah-1)² as follows,
Σ (āth 1) 2 = H +
4 max.EA 26,2098
Σ
D
p
(TH). F/ (0 (TH)
72
0
EED*
28 max
(x.1209.
I H +
7/2
Xx 1210099
max.EA
722
where the second line is by the estimation guarantee of Lemma 4. Thus, we have,
Drv (pg' (TH), 1P55 (TH))
T (w))
(x)) - -M((an) vs (Tn-1) + (TH)
h=1
H
1
| (Ta A/
Σ
Talssigu( (wr x.y)
15
h=1
Aa
H
E
7b -
(Th 1)
Σ T. Teg (w) x. )w
Aa
2
(0)
2
2 (Th-2)
Σ n. sigsiin [w: x 2,)
1/
h=1
||
|
ā E
v (Ta-
H
To (Th-1) 2
S â
E
part 6+
where step (a) is by the Sauchy-Schwarr inequality and step (b) is by the bound established above. Since the total variation distance is bounded above by 2, we have
DTv (Ppt (ft), Pg ge (TH) S min { ā.
H Σ
||
(T-
//2
2
1/
A=1
52

---

Finally, the proof is completed by summing over & using the elliptical potential lemma as follows,
K
K
T (Th
1 (Ta-
|| 1/
DTv Pg- (TH), PPT (TH)
min
á
wagh Th
.2)
k=1
k
1=1
||
11:11
VK
min
a2. E 1
.47
h=1
VKä
min
E
(
/
.4/02]
6r
A/
2A 2A 1A3
VKHā (1 4/a²)r log K/Ao)
max,EA X QA
/rKH3 log(1 + K/20)
max,EA 11,QA VrKHBlog( dQaK/7).
Here, step (a) is uses the relationship between the & and &g norms |1:111 S Vdl 11-112- Step (b) is by the elliptical potential lemma ([35, Lemma 14]; see also [96-98]). Step (c) uses the bound on ä established above and the fact that / + 4/a² is bounded by an absolute constant. Step (d) uses the definition of λo and the fact that 228(1 + 4/02) is bounded by an absolute constant.
Using the two lemmas above, we are now ready to show that Σ argument is identical to [35, Lemma 6] and does not require modification for generalized PSRs. We recount the argument for completeness.
== v (T* O(VK). The
Lemma 9, Under the event &, with probubility at least 1 - 6, we have:
K
QAVH
max? Q3H
VF+
7
72
1=1
where 3o = max(log(1 + log11 + dQa
K/h)}, and X = max. Xx AQ4 max (F.AA/H/T)
VdH
Proof.
First, we note that,
v8+ (Mtt) = Σ Pe (T) = Σ Po (T) (r)+ (T)
s V
(Pg"" pp."
where we recall that (-) [0, 1]. Hence, we may focus bounding the value 6o under the true model 0* and use the bound on the cumulative total variation estimation error established in Lemma 8. Recall the definition of the bonus term,
(TM)) min
a
(Th)
which defined in terms of the estimated prediction features V. Recall also that in Lemma established bound on the expectation of the prediction features under the true model, which
53

---

corresponds to V. Hence, we proceed to bound Στ k. V/8- (T²²) as follows,
Σ Vith (TT)
Σ k
E
T/ pank
B (TH)
Σ
E
pa
min
Σ
(Th)
,1
Tur
h
(a)
K
min
1+
2 max A
Ky QQ 7rB
H
E
1b (Tx)
aHQA
DTv
VX
VX
(6)
K
min
2 mmax Ct +
[x 1QAV 7r
H
1 (Tn)
+
K
aHQA
DTV
(P PF
VÁ
(1t))
vx
h=0
where step (a) is by Lemma 7 and step (b) is since min(a + b,c) min(a, c) + b when a, b, non-negative.
Next, we bound the term 7. Recall the definition of U = AI + EnEDy v (m.) (T.) Also, note that the process
B Banwegt
|| [Ta)
(mw)
(1z) ]
1 (Th k+ 1,1,+1
))
K
1100) k=1
a martingale. Hence, by the Azuma- huuua--oe inequality, we have that with probability at least 1-5,
1 2K (2/8)
+ min
1
2 max.eeA QAV
7rB
(Th
++111++1
11000)1111
VT
k=1
0
2 Imax.aA Xs QAA 7r3
I / 2K log(2/0) + a
1
wrK log(1 + K/A)
$ aa (1+ max.EA (..
HrrKlogh + K/X)
V
where the second line is by the Elliptical potential lemma ([35, Lemma 14]; see also [96-98]).
We return to bounding Σ D (m+)) For convenience define 30 max(log(1 K/A) log(1 + dQxK/>)) and we choose as follows.
7 max,EA [x, 2 QAB max (Vr, QAVH/)
dH
54

---

We have,
@a (T**)
0- (x* +
Σ
DTv (pa' Pg-)
aHQA
K
x
1 +
DTv
VA
max,c X QAVTTB
all Q7 m 1/8 VrHK3o
a
1
Vİ
HvrK30-
VT
maxsEA X
QAVTRB
max.EA
HV
H HvrK30
V1
7VA
2V3
Hdd
max 1
1
max
X
QAVB max MiNNNVT,QQMM. QAVH/7)
H HvrK3
72
VA
VdHA
max,EA X SA AAV max Vr. QAVH/1
maxSEA [, Q.HHH.VKKK
1
1
A X VBy
2
Q^ max (VF, QAVH//WWHH
max,EA X QAH
QAV max {V..AVHH))
max.EA (x. QAH rK333
Vr+ QAVH
maxsE.
VrdHK 72
where step (a) is by Lemma 8 and the bound on Jn established above, step (b) uses the definition of o
and the fact that a $ 7
QAvHdX m QAvV and step (c) is by plugging in the choice of A.
J.5 Proof of Theorem
Theorem (Restatement of Theorem 4). Suppose Assumption 1 holds. Let pmin 0
5
KH KHI 13
max.eA F., 2 max (=RAAHH)))
o (QavHd V max (QAV and let B
VaH
(log (e where O KH Then, with probability at least 6, Algorithm I returns model Or and policy n that satisfy
(= -V (x) s, and Drv (P (Tn) 17 (Tn)) S
In addition, the algorithm terminates with a sample complexity of.
ò ((1+ QA H 72
rdH max,EA [X,| Q4
r+
7422
the event & occurs with high probability. [[ 2 1- 38. Suppose holds. Then, by the upper confidence bound established in Corollary 4, if Algorithm terminates, then the following must hold,
Proof. By Propositions
Vn, Dry (Pag (TH). P. (TH)) = 2 max (T)(
V (T))))
< ST)
where the maximization is over reward functions termination condition of Algorithm 1.
HH - [0, 1]. The last inequality is simply the
55

---

Now, the difference between the optimal value and the value of π (the policy returned by the algorithm) can be bounded as follows,
Vg (TT V (T) (TT) ( + Vg (T*) Vi
V (T)
2 VoL (T) c,
where the inequality follows from the fact that π = arg m 1 ( and by Corollary 4. Recall that by Lemma 9, we have,
(VF=
QAVH
m [X Q24 QAHVvrdKKBS
V DR 2
72
By the pigeon-hole principle and the termination condition of Algorithm I, the algorithm must terminate within
K-O -(((+++
SAH ?2
rdH2Q) max.eA 1x 3
712
episodes. Since each episode contains H. iterations, this implies a sample complexity of
K K ((+ 234 72
rdH maxsEA |x,|²
7/22
This concludes the proof Theorem 4.
K Proof of Theorem 5: UCB Algorithm for Generalized PSRs (Game Setting)
Theorem (Restatement of Theorem 5). Suppose Assumption I holds. Let Pmain = = KH II 18
m 1x,, 1x,l2AAA A max VF VT.RAVH//)) a - QAyHa Vx+ max.e AAAB and let B
VaH
Olog ( where & = O KH ). Then, with probability at least - 6, Algorithm 2 returns a model or and policy x which is an e-approximate equilibrium (either NE or CCE). That is.
Vz.(T) 2 Vi- (x-) e, Vi E [N].
In addition, the algorithm terminates with a sample complexity of.
ò
(((
2AH 72
rdH max [Xg 0
r
74222
Proof. Recall that the model-cstimation portion of Algorithm 2 is identical to Algorithm Hence, by Theorem 4, the returned estimated model 6 satisfies,
Drv (I (TH) P. (TH)) S s//
for any collection of policies (a' : [N]). This implies that Vg. (T) Vg. (T) (T) i E [N].
e/2 for all
Let D r ind in the case of running the algorithm find Nash equilibrium and 1 2 cor in the case of coarse correlated equilibrium. Recall that the collection of policies π (T1 ..... N) returned by the algorithm are an equilibrium under 6= That is, for all i [N].
Vis (TT)
max Vgc (#', x
Vgl (T "))
ere ind
Moreover, note that,
yhit Me
(n (t) - 1osi (TT (i--)
= max Vii ( -1) - max Vi (T ग -1)
#t
#t
< maxx Vii ( ग. ブラ) - Vgi ( ক -ー)
e/2,
56

---

where the final inequality is since Dιv (P (TH), (TH)) I e/2 for any æ. Thus, Vid (T-)) 2 V0- (x-1) s/2.
Putting this together, we have,
Vil 2 (T) Vilht ( ( Vi- (T - E.
(π) - e/2
Hence, x is e-approximate equilibrium (either NE or CCE).
57

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The abstract and introduction summarize the main message and technical results of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
This is discussed in the conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
58

---

The paper provides complete, self-contained description of all technical assumptions, and full proof (in the appendix) for all theoretical results. Guidelines:
Justification:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: N/A
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
59

---

Answer:
[NA]
Justification:
There is no data or code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (uttps://ning cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed run reproduce the results. See the NeurlPS code and data submission guidelines (https:
www.uummmissooooooooccoooo for more details. / /nips. cc/pc//pp... htt//uulcc/aae heeicc//gui///eeee Sileee//ooSSuubissc
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperpa- rameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
60

---

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 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 range (e.g. negative еттоr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported didn't 't make it into the paper).
paper (e.g., preliminary or failed experiments that
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: //nerrip/////....////
www.e/hhhhiiileelineeneeaaeeeaee inne??
Answer: [Yes]
Justification:
This work conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is theoretical in nature and does not have immediately negative or positive societal impact.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious 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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
61

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology-
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper does not release data or models.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
We do not use any existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's ss creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
62

---

Answer:
[NA]
Justification:
We do not introduce new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to amonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
63


Reviews:
[{"review_id": "ydKEhw3JV5", "reviewer": "Reviewer_a41N", "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.", "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?\n- 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": "The author(s) have adequately addressed the limitations of the work.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-written and well-structured. The proposed framework of partially-observable sequential teams (POST) and partially-observable sequential games (POSG) incorporates more general system dynamics than classical MDP/POMDP models through much more general information structures. The model is also practically relevant for application with complex and time-varying dependence on the past or time-varying observations dynamics. \n- The paper provides a thorough theoretical foundation to understanding the complexity and tractability of POST and POSG problems. This includes characterizing the complexity of the observable system dynamics, as well as upper bound of on the statistical hardness of learning both through the lens of the information structure. Moreover the results recovers known sample complexity results in POMDPs. \n- This paper gives a key insight that the complexity of the dynamics and the statistical hardness of sequential decision-making problems can be characterized in terms of its information structure. The proposed method of observation generalized predictive state representation is also of independent interest for other adjacent problems.", "weaknesses": "- 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. \n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your engagement with our work and your valuable feedback. We are glad our work resonated with you.\n\nWe hope to address your concerns and answer your questions below, in turn.\n\n---\n\n**On the identifiability condition and hardness results**\n\n> 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.\n\n> 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?\n\nOur results are of an \"upper bound\" nature, stating that if the identified condition in terms of information structure holds, then learning is tractable and the statistical complexity scales according to $|\\mathbb{I}_h^\\dagger|$.\n\nWe note that the $\\mathcal{I}^\\dagger$-weakly revealing condition can be thought of as a statistical identifiability condition. Such an identifiability condition is *necessary*, and is reflective of the fundamental difficulty of the partially-observable setting. For example, in the case of POMDPs, there exist hardness results that state that if an analogous condition does not hold, the statistical complexity can scale exponentially with the relevant quantities (i.e., size of observation/action space).\n\nHowever, in a practical context, if such a condition does not hold for the true underlying system, it may still hold \"approximately\". That is, there may exist a statistical model inside the POST/POSG framework that approximates the true system in total variation distance and which is $\\mathcal{I}^\\dagger$-weakly revealing. In such a case, the implications of our analysis still hold, after accounting for approximation error.\n\nWe will add a discussion to the paper on these issues, emphasizing the need for such an identifiability condition, and the practical implications. Thank you for the question.\n\n**Practical implications**\n\nAs you know, the primary contribution and focus of our work lies in the development of a foundational understanding of the statistical complexity of reinforcement learning in terms of information structure. The proposed algorithm is developed as a proof device rather than being intended for practical use. However, **our work has direct implications to *representation learning* in the context learning sequential decision-making problems**. When learning in arbitrary dynamic decision-making environments, our analysis reveals that the fundamental quantity that dictates the statistical complexity of a problem is the size of the information structural state space, $|\\mathbb{I}_h^\\dagger|$. We note that recent work in machine learning has studied the ability of sequence models like Transformers to learn and represent causal structures in sequential data. Our analysis suggests that the right scaling of the statistical complexity of such tasks, when applied to dynamic decision-making settings, depends on the quantity $|\\mathbb{I}_h^\\dagger|$. The analysis in this work can inform the design of architectural inductive biases that can better capture and represent such causal structures in order to achieve improved sample efficiency.\n\nWe will add further discussion on these practical implications.\n\n**Upper bounds implied for well-studied special cases**\n\n> 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?\n\nYes. The information-structural upper bound established in this work identifies the right quantities with which the statistical complexity scales. We briefly mention this for the case of POMDPs and Dec-POMDPs/POMGs in lines 354-358. This also applies for MDPs and MGs, where $\\alpha = 1$ and $\\mathbb{I}_h^\\dagger = \\mathbb{S} \\times \\mathbb{A}$. However, we note that our analysis recovers the right scaling up to polynomial dependence, but a more tailored analysis can identify tighter polynomial dependence.\n\n---\n\nWe hope our responses address your concerns and look forward to further discussion.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "laA9dXvWUr", "reviewer": "Reviewer_w9Kg", "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.", "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. \n1. Is there an example of a system that is POST but not POMG or not dec-POMDP as claimed in Figure 1?\n1. 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\n1. “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. \n1. Please define dec-POMDP, POMG before using the acronyms. Or at least define them in the Appendix.\n1. Why in def 5 we need to remove all the arrows pointing to actions? Can actions be dependent on history?\n1. What’s $\\sigma$ in Def 6?\n1. 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 are discussed", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The authors present a good study on complexity of decision-making problems in finite state and action spaces\n1. They identify scalable decision-making problems for learning applications.\n1. The work appears to be technically sound, but I haven't checked all the proofs", "weaknesses": "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\n1. 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?\n1. 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. \n1. 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", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review and feedback. We hope to address of each of your concerns in turn.\n\n---\n\n**Finite vs Continuous Spaces**\n> ... the authors are dealing with finite state and action spaces ... If this is so, I see it as a major weakness\n\nOur results are stated and proved for finite spaces. Finite spaces reveal the interesting aspects of the role of information structure in studying the statistical complexity of sequential decision-making problems. Introducing continuous spaces can introduce certain technical complications that obfuscate the key message of our information structural analysis. We also note that the majority of previous related work considers finite spaces.\n\nNonetheless, extensions to continuous spaces are possible. We provide some discussion of this below.\n- Our formulation of Generalized Predictive State Representations can be extended to capture continuous spaces for system variables. This requires a few technical modifications:\n    - In finite spaces, core test sets are a finite set of trajectories $\\mathbb{Q}\\_{h} = \\\\{q\\_h^{1}, \\ldots, q\\_h^{d\\_h} \\\\} \\subset \\mathbb{F}\\_h$, where each $q_{h}^j = (x_{h+1}, ..., x_H)$ is a trajectory. In the extension to continuous spaces, the core tests become trajectories of subsets of the underlying continuous space. I.e., $q_h^j = (\\mathcal{X}_{h+1}, ..., \\mathcal{X}_H)$, where $\\mathcal{X}_k \\subset \\mathbb{X}_k$ is a measurable subset.\n    - In finite spaces, the feature vector $\\bar{\\psi}(\\tau\\_h) = (\\bar{P}(q\\_h^j | \\tau\\_h))\\_j$ is the vector probabilities of core tests. While in finite spaces $q_h^j$ is a single trajectory, in continuous spaces $q_h^j$ is a subset of trajectories, and the probabilities become $\\bar{P}(x\\_{h+1} \\in \\mathcal{X}\\_{h+1}, ..., x\\_{H} \\in \\mathcal{X}\\_{H} | \\tau\\_h)$.\n    - In finite spaces, the observable operators $M\\_h : \\mathbb{X}\\_h \\to \\mathbb{R}^{d\\_h \\times d_\\{h-1}}$ map the variable at time $h$ to a matrix. In continuous spaces, they become linear functionals that map functions over $\\mathbb{Q}_{h-1}$ to functions over $\\mathbb{Q}_h$.\n    - This type of extension to continuous spaces has been considered in standard PSRs and can be extended to our generalized PSR model. From here, the rest of the analysis, including the causal structure analysis using the POST/POSG model and information structure can be appropriately extended.\n- Alternatively, our results can also be applied to continuous spaces via appropriate quantization while accounting for the approximation error due to quantization.\n\nWe will provide a discussion of extensions to continuous spaces in the updated manuscript.\n\n---\n\n**Generality of the POST/POSG Framework and the importance of Information Structure**\n\n> I am not sure that Figure 1 is fully substantiated. Hopefully, the authors can clarify\n\nIn Figure 1, we depict the following relationship between our POST/POSG framework and existing models like POMDPs: MDP $\\subset$ POMDP $\\subset$ Dec-POMDP $\\subset$ POST $\\subset$ POSG. That is, via their general specification of information structure and variable structure, POST/POSG capture MDPs, POMDPs, and Dec-POMDPs as special cases.\n\nInformation structure is the specification of how events (variables) in a system affect each other. MDPs, POMDPs, Dec-POMDPs, and POMGs each assume a particular variable structure and information structure. In particular, they also assume the existence of a *Markovian state* that depends *only* on the state at the previous time step. In our model, we make no such assumption and we allow the information structure to vary across different problem instances, representing the variable structure, information structure, and system dynamics as part of the model specification (by contrast MDPs/POMDPs/etc only represent system dynamics in the model specification and the rest are fixed). In our model, we have a sequence of variables $x_1, x_2, ...$, where each variable depends on an arbitrary subset of the past, can be either a system variable or an action variable, and can be either observable or not observable. This greatly expands the types of system dynamics that can be represented compared to models like POMDPs that assume a Markovian state, and also expands the notion of partial-observability as it now is no-longer defined with respect to an assumed idealized Markovian state.\n\nFor further discussion of this, we point to the subsection \"llustration: translating to the POST/POSG framework\" in Appendix D which provides a detailed worked-through example of how models with fixed information structure such as POMDPs can be naturally represented in the POST/POSG framework.\n\n---\n**Practical implications**\n> 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.\n\nThe primary contribution and focus of our work lies in the development of a foundational understanding of the statistical complexity of reinforcement learning in terms of information structure. Our work has direct implications to representation learning in the context learning sequential decision-making problems. We argue that, when learning in arbitrary dynamic decision-making environments, the fundamental quantity that dictates the statistical complexity of a problem is the size of the information structural state space, $|\\mathbb{I}_h^\\dagger|$. We note that recent work in machine learning has studied the ability of sequence models like Transformers to learn and represent causal structures in sequential data. Our analysis suggests that the right scaling of the statistical complexity of such tasks, when applied to dynamic decision-making settings, depends on the quantity $|\\mathbb{I}_h^\\dagger|$. The analysis in this work can inform the design of architectural inductive biases that can better capture and represent such causal structures in order to achieve improved sample efficiency.\n\nWe will add further discussion on these practical implications.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "j1ljdP46jj", "reviewer": "Reviewer_Ugr3", "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.", "questions": "N/A", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The results of this paper are very general, in the sense that they encompass the results of several previous works.", "weaknesses": "(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).\n\n(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.\n\nOverall, 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.\n\n[1] Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making.\n\n[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.\n\n[3] Dylan J Foster, Noah Golowich, and Yanjun Han. Tight guarantees for interactive decision making with the decision-estimation coefficient.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Summary of review.** While the reviewer acknowledges the generality of our framework and technical results, they are skeptical about what advantage or insight this analysis grants compared to existing work, and what concrete new tractable model classes it identifies.\n\nThank you for your review. We hope to address each of your concerns, clarifying the technical contributions of our work and explaining its significance.\n\n---\n\nThe goal of our work is to ***develop an understanding of how \"information structure\"---the structure of causal dependence between variables in a system---determines the statistical complexity of learning a sequential decision-making problem***.\n\nAs you mentioned, there has been a series of recent works that studied classes of tractable POMDPs. However, these previous works tackle a different problem than we do. While many of these works indeed provide a general analysis of statistical complexity, for example in terms of eluder dimension-style quantities, this analysis is not directly linked to the underlying information structure of the system. Thus, in a sense, they are orthogonal to our work as they don't say anything about statistical complexity as a function of information structure or the causal structure in the system's variables.\n\nThe main technical contribution of our work is to **relate statistical complexity to information structure**. This is an important perspective with key insights that are missing from existing general analyses like the ones you mentioned. In particular, the conditions provided in these existing general analyses are not directly connected to the underlying structure of system dynamics.\n\nIn our work, we carry out an **analysis in terms of the graph representation of the causal structure between system variables**, both observable and unobservable. In particular, we identify a key quantity, defined in terms of $d$-separation operations on the DAG representation of the information structure, that we prove characterizes the statistical complexity of general sequential decision-making problems. A key insight from this analysis is **a systematic way to understand the difficulty of learning and modeling a system's evolution through the underlying causal structure between its variables**, whether those variables are observable or not. In particular, the existence of unobservable system variables that dictate the dynamics of the system can imply a bound on the complexity of observable dynamics that need to be modeled. A simple example of this is POMDPs, where the existence of an unobservable Markovian state implies a bound on the complexity of representing the dynamics of the observables. Our analysis generalizes this to arbitrary information structures.\n\nThis characterization of statistical complexity in terms of information structure is, in many cases, a **more interpretable characterization of statistical complexity** than the types of conditions identified in current general analyses in the literature (e.g., in terms of eluder dimension or a SAIL condition, etc.) because it relates directly to the structure of the system dynamics rather than abstract constructs that may not have real-world physical interpretations.\n\nMoreover, the language of information structure is key to **understanding the phenomena of partial observability in a much more powerful way**. Our analysis enables considering a much **more general notion of partial observability**. In standard models, partial observability refers to \"emissions\" from an underlying Markovian state variable which encodes all relevant information about the system. Under our analysis, we consider a more general notion of partial observability in which system variables evolve according to an arbitrary causal structure (not necessarily Markovian), and the set of observables is specified as an arbitrary subset of all system variables.\n\nThus, the generality of our framework and analysis provides deep insights into the fundamental theoretical underpinnings of reinforcement learning, characterizing the statistical complexity of learning sequential decision-making problems as a function of the causal structure between system variables.\n\n---\n\nWe will make an effort to emphasize the points explained above in the revised paper to better situate our work in the context of existing literature.\n\n---\n\n> The POSTs and POSGs are special cases of \"generalized PSRs\",\n\nIt's not quite right to say the POSTs and POSGs are special cases of \"generalized PSRs\". We develop generalized PSRs as a proof device to obtain an efficient *representation* of POSTs/POSGs which is amenable to learning. In this paper, we prove (by construction) that *certain classes* of POSTs/POSGs admit a well-conditioned representation as a generalized PSR, with a condition specified in terms of information structure. Not all POSTs/POSGs admit such a well-conditioned PSR representation. This information-structural condition identifies a new expanded class of tractable problems.\n\n> Several examples of information structure are provided, but there isn't a definition of a new, meaningful, and tractable problem class.\n\nThe concrete tractable class of sequential decision-making problems is identified in terms of its information structure. It is the class of POSTs/POSGs where $|\\mathbb{I}_h^\\dagger|$ is bounded, defined in terms of the graph representation of information. The corresponding identifiability condition needed is defined in Definition 6, and is analogous to identifiability conditions considered in previous work on partially-observable models like POMDPs.\n\nThe insight attained from such a characterization in terms of the causal structure becomes especially clear when considering physical systems, where the set of system variables and their causal dependence may be known, but only a subset of these variables are observable to the learning agent.\n\n---\n\nWe hope our responses address your concerns and look forward to further discussion.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)