Provable Partially Observable Reinforcement Learning with Privileged Information

Authors: yang  cai
xiangyu  liu
argyris  oikonomou
kaiqing  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 19:49:56

Abstract: Partial observability of the underlying states generally presents significant challenges for reinforcement learning (RL). In practice, certain *privileged information* , e.g., the access to states from simulators, has been exploited in training and achieved prominent empirical successes. To better understand the benefits of privileged information, we revisit and examine several simple and practically used paradigms in this setting, with both computation and sample efficiency analyses. Specifically, we first formalize the empirical paradigm of *expert distillation* (also known as  *teacher-student* learning), demonstrating its pitfall in finding near-optimal policies. We then identify a condition of the partially observable environment, the deterministic filter condition, under which expert distillation achieves sample and computational complexities that are *both* polynomial. Furthermore, we investigate another successful empirical paradigm of *asymmetric actor-critic*, and focus on the more challenging setting of observable partially observable Markov decision processes. We develop a belief-weighted optimistic asymmetric actor-critic algorithm with polynomial sample and quasi-polynomial computational complexities, where one key component is a new provable oracle for learning belief states that preserve *filter stability* under a misspecified model, which may be of independent interest. Finally, we also investigate the provable efficiency of partially observable multi-agent RL (MARL) with privileged information. We develop algorithms with the feature of centralized-training-with-decentralized-execution, a popular framework in empirical MARL, with polynomial sample and (quasi-)polynomial computational complexity in both paradigms above. Compared with a few recent related theoretical studies, our focus is on understanding practically inspired algorithmic paradigms, without computationally intractable oracles.

Main paper: 
 introduction: 
 In most real-world applications of reinforcement learning (RL), e.g., perception-based robot learning [45, 3] , autonomous driving [72, 40] , dialogue systems [87] , and clinical trials [76] , only partial observations of the environment state are available for sequential decision-making. Such partial observability presents significant challenges for efficient decision-making and learning, with known computational [65] and statistical [42, 35] barriers under the general model of partially observable Markov decision processes (POMDPs). The curse of partial observability becomes severer when multiple RL agents interact, where not only the environment state, but also other agents' information, are not fully-observable in decision-making [84, 79] .On the other hand, a flurry of empirical paradigms has made partially observable (multi-agent) RL promising in practice. One notable example is to exploit the privileged information that may be available (only) during training. The privileged information usually includes direct access to the underlying states, as well as access to other agents' observations/actions in multi-agent RL (MARL), due to the use of simulators and/or high-precision sensors for training. The latter is also known as the centralized-training-with-decentralized-execution (CTDE) framework in deep MARL, and has become prevalent in practice [52, 69, 22, 81] . These approaches can be mainly categorized into two types: i) privileged policy learning, where an expert/teacher policy is trained with privileged information, and then distilled into a student partially observable policy. This expert distillation, also known as teacher-student learning, approach has been the key to some empirical successes in robotic locomotion [44, 58] and autonomous driving [14] ; ii) privileged value learning, where a value function is trained conditioned on privileged information, and used to improve a partially observable policy. It is typically instantiated as the asymmetric actor-critic algorithm [67] , and serves as the backbone of some high-profiled successes in robotic manipulation [45, 3] and MARL [52, 81] .Despite the remarkable empirical successes, theoretical understandings of partially observable RL with privileged information have been rather limited, except for a few recent prominent advances in RL with hindsight observability [43, 30] (see Appendix B for a detailed discussion). However, most of these theoretically sound algorithms are different from those used in practice, and require computationally intractable oracles to achieve provable sample efficiency. The soundness and efficiency of the aforementioned paradigms used in practice remain elusive. In this work, we examine both paradigms of expert distillation and asymmetric actor-critic, with foresight privileged information as in these empirical works. In contrast to [43, 30] , which purely focused on sample efficiency, we aim to understand the benefits of privileged information by examining these practically inspired paradigms under several POMDP models, without computationally intractable oracles. We defer a detailed literature review to Appendix B, and summarize our contribution as follows.Contributions. We first formalize the empirical paradigm of expert distillation, and demonstrate its pitfall in distilling near-optimal policies even in observable POMDPs, a model class that was recently shown to allow provable partially observable RL without computationally intractable oracles [25] . We then identify a new condition for POMDPs, the deterministic filter condition, and establish sample and computational complexities that are both polynomial for expert distillation. The new condition is weaker and thus encompasses several known (statistically) tractable POMDP models (see Figure 1 for a summary). Further, we revisit the asymmetric actor-critic paradigm and analyze its efficiency under the more challenging setting of observable POMDPs above (where expert distillation fails). Identifying the inefficiency of vanilla asymmetric actor-critic, and inspired by the empirical success in belief-state-learning, we develop a new belief-weighted version of asymmetric actorcritic, with polynomial-sample and quasi-polynomial-time complexities. Key to the results is a new belief-state learning oracle that preserves filter stability under a misspecified model, which may be of independent interest. Finally, we also investigate the provable efficiency of partially observable multi-agent RL with privileged information, by studying algorithms under the CTDE framework, with polynomial-sample and (quasi-)polynomial-time complexities in both paradigms above. 
preliminaries: 
 2.1 Partially Observable RL (with Privileged Information) Model. Consider a POMDP characterized by a tuple P = (H, S, A, O, T, O, µ 1 , r), where H denotes the length of each episode, S is the state space with |S| = S, A denotes the action space with |A| = A. We use T = {T h } h∈ [H] to denote the collection of transition matrices, so that T h (• | s, a) ∈ ∆(S) gives the probability of the next state if action a is taken at state s and step h. In the following discussions, for any given a, we treat T h (a) ∈ R |S|×|S| as a matrix, where each row gives the probability for reaching each next state from different current states. We use µ 1 to denote the distribution of the initial state s 1 , and O to denote the observation space with |O| = O. We use O = {O h } h∈ [H] to denote the collection of emission matrices, so that O h (• | s) ∈ ∆(O) gives the emission distribution over the observation space O at state s and step h. For notational convenience, we will at times adopt the matrix convention, where O h is a matrix with rows O h (• | s) for each s ∈ S. Finally, r = {r h } h∈[H] is a collection of reward functions, so that r h (s, a) ∈ [0, 1] is the reward given the state s and action a at step h. When privileged information is available, the agent can observe the underlying state s ∈ S directly during training (only). We thus denote the trajectory until step h with states as τ h = (s 1:h , o 1:h , a 1:h-1 ), the one without states as τ h = (o 1:h , a 1:h-1 ), and its space as T h . Finally, we use b h (τ h ) to denote the posterior distribution over the underlying state at step h given history τ h , which is known as the belief state (c.f. Appendix C.1 for more details).Policy and value function. We define a stochastic policy at step h as:EQUATIONwhere the agent bases on the entire (partially observable) history for decision-making. The corresponding policy class is denoted as Π h . We further denote Π = × h∈[H] Π h . We also define Π gen := {π 1:H | π h : S h × O h × A h-1 → ∆(A) for h ∈ [H]} to be the most general policy space in partially observable RL with privileged state information, which can potentially depend on all historical states, observations, and actions. It can be seen that Π⊆Π gen . We may also use policies that only receive a finite memory instead of the whole history as inputs: fix an integer L > 0, we define the policy space Π L to be the space of all possible policies π = π 1:H := (π h ) h∈ [H] such that π h : Z h → ∆(A) with Z h := O min{L,h} × A min{L,h} for each h ∈ [H]. Finally, we define the space of state-based policies as Π S , i.e., for any π = π 1:H ∈ Π S , π h : S → ∆(A) for all h ∈ [H].Given the POMDP model P, we write P P s 1:H+1 ,a 1:H ,o 1:H ∼π (E) to denote the event E when (s 1:H+1 , a 1:H , o 1:H ) is drawn as a trajectory following the policy π in the model P. We will also use the shorthand notation P π,P (•) if (s 1:H+1 , a 1:H , o 1:H ) is evident. We write E P π [•] to denote the expectation similarly. We define the value function at step h as V π,P h (y h ) := E P π [ H t=h r t (s t , a t ) | y h ], denoting the expected accumulated rewards from step h, where y h ⊆ (s 1:h , o 1:h , a 1:h-1 ), and we slightly abuse the notation by treating as a set the sequence of states s 1:h , the sequence of observations o 1:h , and the sequence of actions a 1:h-1 up to time h, which are the available information to the agent at step h. We say y h is reachable if there exists some policy π ∈ Π gen such that P π,P (y h ) > 0. For h = 1, we adopt the simplified notation v P (π) = E P π [ H h=1 r h (s h , a h )]. Meanwhile, we also define Q π,P h (y h , a h ) := E P π [ H t=h r t (s t , a t ) | y h , a h ]. We denote the occupancy measure on the state space as d π,P h (s h ) = P π,P (s h ). The goal of learning in POMDPs is to find the optimal policy that maximizes the expected accumulated reward over the policies that take τ h as input at each step h ∈ [H], i.e., those π ∈ Π. Formally, we define: Definition 2.1 (ϵ-optimal policy). Given ϵ > 0, a policy π ⋆ ∈ Π is ϵ-optimal, if v P (π ⋆ ) ≥ max π∈Π v P (π) -ϵ.Learning with privileged information. Common RL algorithms for POMDPs deal with the scenario where during both the training and test time, the agent can only observe its historical observations and actions τ h at step h, while the states are not accessible. In other words, the agent can only utilize policies from Π to interact with the environment. In contrast, in settings with privileged information, e.g., training in simulators and/or using sensors with higher precision, the underlying state can be used in training. Thus, the agent is allowed to utilize policies from the class Π gen during training. Meanwhile, the objective is still to find the optimal history-dependent policy in the space of Π, since at test time, the agent cannot access the state information anymore, and it is the performance for such policies that matters eventually. For simplicity, we assume the reward function is known since under our privileged information setting, learning the reward function is much easier than learning the transition and emission, and the sample/computational complexity for the former is dominated by that for the latter. This assumption has also been made for learning in POMDPs without privileged information [35, 46, 47] .Partially observable stochastic games (POSGs) are a natural generalization of POMDPs with multiple agents of potentially independent interests. We define a POSG with n agents by a tuple G = (H, S, {A i } n i=1 , {O i } n i=1 , T, O, µ 1 , {r i } n i=1 ), where each agent i has its individual action space A i , observation space O i , and reward function r i = {r i,h } h∈[H] with r i,h (s, a) ∈ [0, 1] denoting the reward given state s and joint action a for agent i at step h. An episode of POSG proceeds as follows: at each step h and state s h , a joint observation is drawn from (o i,h ) i∈[n] ∼ O h (• | s h ), and each agent receives its own observation o i,h , takes the corresponding action a i,h , obtains the reward r i,h (s h , a h ), where a h := (a i,h ) i∈ [n] , and then the system transitions to the next state as s h+1 ∼ T h (• | s h , a h ). Notably, each agent i may not only know its local information (o i,1:h , a i,1:h-1 ), but also information from some other agents. Therefore, we denote the information available to each agent i at step h also as τ i,h ⊆ (o 1:h , a 1:h-1 ) and define the common information as c h = ∩ i∈[n] τ i,h and private information as p i,h = τ i,h \ c h . We denote the space for common information and private information as C h and P i,h for each agent i and step h. The joint private information at step h is denoted as p h = (p i,h ) i∈ [n] , where the collection of the joint private information is given by P h = P 1,h × • • • × P n,h . We refer more examples of this setting of POSG with information-sharing to Appendix C.2 (and also [61, 62, 50] ). Correspondingly, the policy each agent i deploys at test time takes the form of π i,h : Ω h × C h × P i,h → ∆(A i ), where Ω h is the space of random seeds. We denote the policy Table 1 : Comparison of the theoretical guarantees with and without privileged information. PI: privileged information; STD: structural assumptions on transition dynamics, e.g., deterministic transition or reachability of all states; SL: supervised learning; FA: function approximation; WSE: wellseparated emission.Figure 1 : A landscape of POMDP models that partially observable RL with privileged information can/cannot address. The axes denote the "restrictiveness" of the assumptions, on the emission channels and transition dynamics, respectively. space for agent i as Π i . If π i,h takes the state s h instead of (c h , p i,h ) as input, we denote its policy space as Π S,i , e.g., for each agent i, and policy π 1:H ∈ Π S,i , we have π i,h : S → ∆(A i ) for each step h ∈ [H]. Similar to the POMDP setting, we define Π gen to be the most general policy space, i.e., Π gen := {π 1:H | π h : S h × O h × A h-1 → ∆(A) for h ∈ [H]}. Note that this model covers several recent POSG models studied for partially observable MARL, e.g., [48, 27] . For example, at each step h, if there is no shared information, then c h = ∅, and if all history information is shared, then p i,h = ∅ for all i ∈ [n]. In privileged-information-based learning, the training algorithm may exploit not only the underlying state information, but also the observations and actions of other agents.Solution concepts. The solution concepts for POSGs are usually the equilibria, particularly Nash equilibrium (NE) for two-player zero-sum games (i.e., when n = 2 and r 1,h + r 2,h = 1), 1 and correlated equilibrium (CE) or coarse correlated equilibrium (CCE) for general-sum games. We defer the formal definitions of these standard solution concepts to Appendix C.2.A key technical assumption is that the POMDPs/POSGs we consider satisfy an observability assumption, as outlined below. This observability assumption allows us to use short memory policies to approximate the optimal policy, and yields quasi-polynomial-time complexity for both planning and learning in POMDPs/POSGs [26, 25, 50] . Meanwhile, we defer an additional assumption to ensure the traceability for solving POSGs to Appendix C.3. Assumption 2.2 (γ-observability [20, 26, 25] ). Let γ > 0. For h ∈ [H], we say that the matrix O h satisfies the γ-observability assumption if for each h ∈[H], for any b, b ′ ∈ ∆(S), O ⊤ h b -O ⊤ h b ′ 1 ≥ γ ∥b -b ′ ∥ 1 . A POMDP/POSG satisfies γ-observability if all its O h for h ∈ [H] do so. 
revisiting empirical paradigms of rl with privileged information: 
 Most empirical paradigms of RL with privileged information can be categorized into two types: i) privileged policy learning, where the policy in training is conditioned on the privileged information, and the trained policy is then distilled to a policy that does not take the privileged information as input. This is usually referred to as either expert distillation [14, 63, 57] or teacher-student learning [44, 58, 74] in the literature; ii) privileged value learning, where the value function is conditioned on the privileged information, and is then used to directly output a policy that takes partial observation (history) as input. One prominent example of ii) is asymmetric-actor-critic [67, 3] . It is worth noting that asymmetric-actor-critic is also closely related to one of the most successful paradigms for multi-agent RL, centralized-training-with-decentralized-execution [52, 85, 21] , which is usually instantiated under the actor-critic framework, with the critic taking privileged information as input in training. Here we formalize and revisit the potential pitfalls of these two paradigms, and further develop theoretical guarantees under certain additional conditions and/or algorithm variants.The motivation behind expert policy distillation is that learning an optimal fully observable policy in MDPs is a much easier and better-studied problem with many known efficient algorithms. The (expected) distillation objective can be formalized as follows:EQUATIONwhere π ′ ∈ Π gen is some given behavior policy to collect exploratory trajectories, π ⋆ ∈ arg max π∈Π S v P (π) denotes the optimal fully observable policy, and D f denotes the general fdivergence to measure the discrepancy between π ⋆ and π.Such a formulation looks promising since it essentially circumvents the challenging issue of exploration in partially observable environments, by directly mimicking an expert policy that can be obtained from any off-the-shelf MDP learning algorithm. However, we point out in the following proposition that even if the POMDP satisfies Assumption 2.2, the distilled policy can still be strictly suboptimal even with infinite data, i.e., by solving the expected objective Equation (3.1) completely.We postpone the proof of Proposition 3.1 to Appendix E.Proposition 3.1 (Pitfall of expert policy distillation). For any ϵ, γ ∈ (0, 1), there exists a γ-observable POMDP P ϵ with H = 1, S = O = A = 2 such that for any behavior policy π ′ ∈ Π gen and choice ofD f in Equation (3.1), it holds that v P ϵ ( π ⋆ ) ≤ max π∈Π v P ϵ (π) -(1-ϵ)(1-γ) 4 .The key reason Equation (3.1) fails is that in general, the underlying state can remain highly uncertain even given the full history. Thus, the distilled policy may not be able to mimic the state-based expert policy well at different states s h if the associated π ⋆ h (• | s h ) differs significantly across s h . To see how we may rule out such problems, we notice that if γ = 12 , implying that the observation can decode the underlying state, the bound in Proposition 3.1 becomes vacuous. Inspired by this observation, we propose the following condition that can incorporate this case of γ = 1, and will be shown to suffice to make expert distillation effective. Definition 3.2 (Deterministic filter condition). We say a POMDP P satisfies the deterministic filter condition if for each h ≥ 2, the belief update operator under P satisfies that there exists an unknown function ψ h : S × A × O → S such that for any reachables h-1 ∈ S, o h ∈ O, a h-1 ∈ A, U h (b s h-1 ; a h-1 , o h ) = b ψ h (s h-1 ,a h-1 ,o h ), where we define for any s ∈ S, b s ∈ ∆(S) and b s (s) = 1 is a one-hot vector. In addition, for h = 1, there exists a functionψ 1 : O → S such that for any reachable o 1 , B 1 (µ 1 ; o 1 ) = b ψ1(o1) , where B h (b; o h ) := P P s h ∼b (• | o h ) ∈ ∆(S), U h (b; a h-1 , o h ) := P P s h-1 ∼b (• | a h-1 , o h-1 ) ∈ ∆(S)are the belief update operators under the Bayes rule for any b ∈ ∆(S), for which we defer the formal introduction to Appendix C.1.Notably, this condition is weaker than and thus covers several known tractable classes of POMDPs with sample and computation efficiency guarantees including Block MDP, deterministic POMDP, k-decodable POMDP as well as a new setting we have identified and existing literature cannot handle. We refer the formal introduction to Appendix E and Figure 1 for an illustration.In light of the pitfall in Proposition 3.1, we will analyze both the computational and statistical efficiencies of expert distillation in Section 4, under the condition in Definition 3.2.Asymmetric actor-critic [67] iterates between two procedures as in standard actor-critic algorithms [41] : policy improvement and policy evaluation. As the name suggests, its key difference from the standard actor-critic is that the algorithm maintains Q-value functions (the critic) based on the state/privileged information, while the policy receives only the (partially observable) history as input.Policy evaluation. At iteration t -1, given the policy π t-1 , the algorithm estimates Q-functions in the form of{Q t-1 h (τ h , s h , a h )} h∈[H] ,where we adopt the "unbiased" version [6] such that Q-functions are conditioned on both the history and the states. 3 One key to achieving sample efficiency is by adding some bonus terms in policy evaluation to encourage exploration, i.e., obtaining some optimistic Q-function estimates, similarly as in the fully-observable MDP setting, see e.g., [11, 73] , for which we defer the detailed introduction to Section 4. Policy improvement. At each iteration t, given the critic {Q t-1 h (τ h , s h , a h )} h∈[H] for π t-1 , the vanilla asymmetric actor-critic algorithm updates the policy according to the sample-based gradient estimation via K trajectories {s kEQUATIONwhere λ t is the step-size and PROJ Π is the projection operator onto the space of Π, which corresponds to projecting onto the simplex of∆(A) for each h ∈ [H].Here we point out the potential drawback of the vanilla algorithm as in [67, 6] , where the key insight is that for each iteration of policy evaluation and improvement, one roughly only performs the computation of order O(KH), while needing to collect K new episodes of samples. Thus, the sample complexity will scale in the same order as the computational complexity when the algorithm converges after some iterations to an ϵ-optimal solution, which will be super-polynomial even for γ-observable POMDPs [27] . Proof of the result is deferred to Appendix E. Proposition 3.3 (Inefficiency of vanilla asymmetric actor-critic). Under the tabular parameterization for both the policy and the value function, the vanilla asymmetric actor-critic algorithm (Equation (3.2)) suffers from super-polynomial sample complexity for γ-observable POMDPs under standard hardness assumptions.To address such an issue, one may need to perform more computation per iteration, so that although the total computational complexity (iteration number × per-iteration computational complexity) is super-polynomial, the total iteration number can be lower such that the total sample complexity may be lower as well. This desideratum is hard to achieve if one computes policy update only on the sampled trajectories τ h per iteration, i.e., update asynchronously, since this will couple the scales of computational and sample complexities similarly as Equation (3.2). In contrast, we first propose to update all trajectories per iteration in a synchronous way, with the following proximal-policy optimization-type [71] policy improvement update with the state-history-dependent Q-functionsEQUATIONwhere we recall b h (τ h ) ∈ ∆(S) denotes the belief state and η > 0 is the learning rate. This update rule also reduces to the natural policy gradient (NPG) [39] update under the softmax policy parameterization in the fully-observable case [1] , when updated for each state s h separately [73] . We defer the detailed derivation of Equation (3.3) to Appendix E.However, such an update presents two challenges: (1) It requires enumerating all possible τ h , whose number scales exponentially with the horizon, making it still computationally intractable; (2) An explicit belief function b h is needed. Motivated by these two challenges, we propose to consider finitememory-based policy and assume access to an approximate belief function {b apx h : Z h → ∆(S)} h∈[H] (the learning for which will be made clear later). Correspondingly, the policy update is modified as:π t h (• | z h ) ∝ π t-1 h (• | z h ) exp ηE s h ∼b apx h (z h ) Q t-1 h (z h , s h , •) , ∀h ∈ [H], z h ∈ Z h .Then we develop and analyze one possible approach to learning such an approximate belief efficiently (c.f. Section 5). It is worth noting that the policy optimization algorithm we aim to develop and analyze does not depend on the specific algorithm approximate belief learning. Such a decoupling enables a more modular algorithm design framework, and can potentially incorporate the rich literature on learning approximate beliefs in practice, see e.g., [24, 64, 16, 86, 82] , which has mostly not been theoretically analyzed before. We will thus analyze such an oracle in Section 5. 
provably efficient expert policy distillation: 
 We now focus on the provable correctness and efficiency of expert policy distillation, under the deterministic filter condition in Definition 3.2. We will defer all the proofs in this section to Appendix F. Definition 3.2 motivates us to consider only succinct policies that incorporate an auxiliary parameter representing the most recent state, as well as the most recent observations and actions. We consider policies that are the composition of two functions: at step h a function g h : S × A × O → S that decodes the state based on the previous state, the most recent action, and the most recent observation, and a policy π E ∈ Π S that takes as input the current (decoded) underlying state and outputs a distribution over actions. Definition 4.1. We define a policy class Π D as:Π D = π E h (g h (s h-1 , a h-1 , o h )) : g h : S × A × O → S, π E h : S → ∆(A) h∈[H] ,where π E stands for an arbitrary expert policy, and Π D stands for the distilled policy class, and for h = 1, a 0 , s 0 are some fixed dummy action and state. Intuitively, the distilled policy π ∈ Π D executes as follows: it firstly decodes the underlying states by applying {g h } h∈[H] recursively along the history, and then takes actions using π E based on the decoded states.Our goal is to learn the two functions independently, that is, we want to learn an approximately optimal policy π E ∈ Π S with respect to the MDP M derived from POMDP P by omitting the observations and observing the underlying state (see Definition = {π E h (ψ(•)) : S × A × O → ∆(A)} h∈[H] ∈ Π D .We slightly abuse the notation and simply denote by v P (π E ) = v P ( π E ). Lemma 4.4. Let P = (H, S, A, O, T, O, µ 1 , r) be a POMDP that satisfies Definition 3.2, and consider a policy π E ∈ Π S .Consider a set of decoding functions {g h } h∈ [H] such that,P π E ,P [∃h ∈ [H] : g h (s h-1 , a h-1 , o h ) ̸ = s h ] ≤ ϵ. Consider the policy π = π E h (g h (•)) : S × A × O → ∆(A) h∈[H] on the POMDP P, then: v P (π) ≥ v P ( π E ) -Hϵ.We can use any off-the-shelf algorithm to learn an approximate optimal policy π E for the associated MDP M (see Definition 4.2). Thus, in the rest of the section, we focus on learning the decoding function {g h } h∈[H] . To efficiently learn the decoding function, we model the access to the underlying state by keeping track of the most recent pair of the action and the observation, as well as the two most recent states. We summarize the algorithm of decoding-function learning in Algorithm 1. Theorem 4.5. Consider a POMDP P that satisfies Definition 3.2, a policy π E ∈ Π S , and let{g h } h∈[H] be the output of Algorithm 1 with M = AOS+log(H/δ) ϵ 2. Then, with probability at least 1 -δ, for each step h ∈ [H]:P π E ,P [∃h ∈ [H] : g h (s h-1 , a h-1 , o h ) ̸ = s h ] ≤ ϵ, using POLY(H, A, O, S, 1 ϵ , log 1 δ ) episodes in time POLY(H, A, O, S, 1 ϵ , log 1 δ ).The following is an immediate consequence of Lemma 4.4 and Theorem 4.5. Note that both the sample and computation complexities are polynomial, which is in stark contrast to the k-decodable POMDP case [19] (a special one covered by our Definition 3.2), for which the sample complexity is necessarily exponential in k when there is no privileged information [19] . In fact, thanks to privileged information, the complexities are only polynomial in horizon H even when the decodable length is unknown. For the benefits of using privileged information in several other subclasses of problems, we refer to Table 1 (π) ≥ v P (π E ) -ϵ.Extension to the case with general function approximation. Due to the modularity of our algorithmic framework and its compatibility with supervised learning oracles, it can be readily generalized to the function approximation setting to handle large observation spaces. We defer the corresponding results to Appendix G. 
provable asymmetric actor-critic with approximate belief learning: 
 Unlike most existing theoretical studies on provably sample-efficient partially observable RL [35, 25, 46] , which directly learn an approximate POMDP model for planning near-optimal policies, we consider a general framework with two steps: firstly learning an approximate belief function, followed by adopting a fully observable RL subroutine on the belief state space. 5.1 Belief-Weighted Optimistic Asymmetric Actor-Critic We now introduce our main algorithmic contribution to the privileged policy learning setting. Our algorithm is conceptually similar to the natural policy gradient methods [39, 1, 73] in the fullyobservable setting, with additional weighting over the states s h using some learned belief states, to handle the additional state-dependence in the asymmetric critic. The overall algorithm is presented in Algorithm 2. The algorithm requires a belief-learning subroutine that takes the stored memory as input and outputs a belief about the underlying state (c.f. {b apx h } h∈[H] ). Additionally, similar to the fully observable setting, we include a subroutine to estimate the Q-function, which introduces additional challenges due to partial observability (see Appendix H). We establish the performance guarantee of Algorithm 2 in the following theorem. We defer the proof to Appendix H. Theorem 5.1 (Near-optimal policy). Fix ϵ, δ ∈ (0, 1). Given a POMDP P and an approximate belief{b apx h : Z h → ∆(S)} h∈[H], with probability at least 1 -δ, Algorithm 2 can learn an approximate optimal policy π ⋆ of P in the space of Π L such that v P (π ⋆ ) ≥ max π∈Π L v P (π) -O(ϵ + H 2 ϵ belief ), with sample complexity POLY(S, A, O, H, 1 ϵ , log 1 δ ) and time complexity POLY(S, A, O, H, Z, 1 ϵ , log 1 δ ), where ϵ belief is the belief-learning error defined asϵ belief := max h∈[H] max π∈Π L E P π ∥b h (τ h ) - b apx h (z h )∥ 1 and Z := max h∈[H] |Z h |.Furthermore, if P is additionally γ-observable (c.f. Assumption 2.2), then π ⋆ is also an approximate optimal policy in the space of Π such that v P (π ⋆ ) ≥ max π∈Π v P (π) -O(ϵ + H 2 ϵ belief ), as long as L ≥ Ω(γ -4 log(SH/ϵ)).At a high level, our belief-learning algorithm first learns an approximate POMDP model P by explicitly exploring the state space. The main technical challenge here is that there may exist states that are reachable with very low probability, making it infeasible to collect enough samples to sufficiently explore them, thus potentially breaking the γ-observability property of the ground-truth model P. To circumvent this issue, we ignore such hard-to-visit states and redirect probabilities flowing to them to certain other states. Thus, in our truncated POMDP, where each state is sufficiently explored, we can approximate the transition and emission matrices to a desired accuracy uniformly across all the states and preserve the γ-observability property. This ensures that the learned approximate belief function in the truncated POMDP is sufficiently close to the actual belief function of the original POMDP P. Note that the key to achieving belief learning with both polynomial sample and time complexities is our explicit exploration in the state space, which relies on executing fully observable policies from an MDP learning subroutine. We remark that the belief function may also be learned even if the state space is only explored by partially observable policies, thus utilizing only hindsight observability may be sufficient for this purpose [43] . However, for such exploration to be computationally tractable, one requires to avoid using computationally intractable oracles for POMDP learning, which is in fact our final goal. We present the guarantees in the next theorem and postpone the proof to Appendix H. Theorem 5.2. Consider a γ-observable POMDP P (c.f. Assumption 2.2) and assume that L ≥ Ω(γ -4 log(SH/ϵ)) for an ϵ > 0. Then, we can learn an approximate belief{b apx h } h∈[H] from Al- gorithm 4 using O( S 2 AH 2 O+S 3 AH 2 ϵ 2 + S 4 A 2 H 6 O ϵγ 2 ) episodes in time POLY S, H, A, O, 1 γ , 1 ϵ , log 1 δ such that with probability at least 1 -δ, for any π ∈ Π L and h ∈ [H], E P π ∥b h (τ h ) -b apx h (z h )∥ 1 ≤ ϵ. Theorem 5.2shows that an approximate belief can be learned with both polynomial samples and time, which, combined with Theorem 5.1, yields the final polynomial sample and quasi-polynomial time guarantee below. In contrast to the case without privileged information [25, 27] , the sample complexity is reduced from quasi-polynomial to polynomial for γ-observable POMDPs. Note that the computational complexity remains quasi-polynomial, which is known to be unimprovable even for planning [27] . The key to such an improvement, as pointed out in Section 3.2, is the more practical update rule of actor-critic (in conjunction with our belief-weighted idea), which allows more computation at each iteration (instead of only performing computation at the sampled finite-memory). This allows the total computation to remain quasi-polynomial, while the overall sample complexity becomes polynomial. A detailed comparison can be found in Table  
numerical validation: 
 We now provide some numerical results for both of our principled algorithms. Here we mainly compare with two baselines, the vanilla asymmetric actor-critic [67] , and asymmetric Q-learning [7] , on two settings, POMDP under the deterministic filter condition (c.f. Definition 3.2) and general POMDPs. We report the results in Table 2 and Figure 2 , where our algorithms converge faster to higher rewards. We defer the implementation details and discussions to Appendix I. ).Here we have required that each agent can decode the underlying state through their own information individually. Naturally, one may wonder whether one can relax it so that only the joint history information of all the agents can decode the underlying state. However, we point out in the following that it does not circumvent the computational hardness of POSG, the proof of which is deferred to Appendix J. Note that the computational hardness result can not be mitigated even with privileged state information, as the hardness we state here holds even for the planning problem with model knowledge, with which one can simulate the RL problems with privileged information. Proposition 7.3. Computing CCE in POSGs that satisfy that for each step h ∈ [H], there exists a function ϕ h :C h × P h → S such that P G (s h = ϕ h (c h , p h ) | c h , p h ) = 1 for any reachable (c h , p h ) is still PSPACE-hard.Learning multi-agent individual decoding functions with unilateral exploration. Similar to our framework for POMDPs, our framework for POSGs is also decoupled into two steps: i) learning an expert equilibrium policy that is fully observable, ii) learning the decoding function, where the first step can be instantiated by any provable off-the-shelf algorithm of learning in Markov games. The major difference from the framework for POMDPs lies in how to learn the decoding function. In Theorem J.1, we prove that the difference of the NE/CE/CCE-gap between the expert policy and the distilled student policy is bounded by the decoding errors under policies from the unilateral deviation of the expert policy. Hence, given the expert policy π, the key algorithmic principle is to perform unilateral exploration for each agent i to make sure the decoding function is accurate under policies (π ′ i , π -i ) for any π ′ i , keeping π -i fixed. We refer the detailed algorithm to Algorithm 5, and present below the guarantees for learning the decoding functions and the corresponding distilled policy for learning NE/CCE, while we defer the results for learning CE to Theorem J.6. Theorem 7.4 (Equilibria learning; Combining Theorem J.1 and Theorem J.4). Under Assumption C.8 and conditions of Definition 7.2, given a ϵ 2 -NE/CCE π E for the associated Markov game of G, Algorithm 5 can learn decoding function { g i,h } i∈[n],h∈ [H] such that with probability at least 1 -δ, it is guaranteed that max ui∈Πi,j∈[n] P ui×π-i,G (s h ̸ = g j,h (c h , p j,h )) ≤ ϵ 4nH 2 , for any i ∈ [n], h ∈ [H] with both sample and computational complexities POLY(S, A, H, O, 1 ϵ , log 1 δ ). Consequently, policy π distilled from π E (c.f. Theorem J.1 for the formal distillation procedures) is an ϵ-NE/CCE of G. 
privileged value learning: asymmetric marl with approximate belief learning: 
 For POMDPs, we have used finite-memory policies for computational efficiency. We generalize to POSGs with information sharing by defining the compression of the common information. Definition 7.5 (Compressed approximate common information [56, 78, 50] ). For each h ∈[H], given a set C h , we say Compress h is a compression function if Compress h ∈ {f : C h → C h }.For each c h ∈ C h , we denote c h := Compress h (c h ). We also require the compression function to satisfy the regularity condition that for each h ∈ [H], there exists a function Λ h+1 such that c h+1 = Λ h+1 ( c h , ϖ h+1 ), for any c h ∈ C h , ϖ h+1 ∈ Υ h+1 , where we recall c h+1 := c h ∪ ϖ h+1 and the definition of Υ h+1 in Assumption C.7.Similar to the framework we developed for POMDPs in Section 5, we firstly develop the multi-agent RL algorithm based on some approximate belief, and then instantiate it with one provable approach for learning such an approximate belief.Optimistic value iteration of POSGs with approximate belief. For POMDPs, the sufficient statistics for optimal decision-making is the posterior distribution over the state given history. However, for POSGs with information-sharing, as shown in [62, 61, 50] , the sufficient statistics become the posterior distribution over the state and the private information given the common information, instead of only the state. Therefore, we consider the approximate belief in the form of P h : C h → ∆(P h × S) for each h ∈ [H], where we define the error compared with the ground-truth belief to beϵ belief := max h∈[H] max π∈Π E G π s h ,p h |P G (s h , p h | c h ) -P h (s h , p h | c h )|, i.e., the expected total variation distance from the true one. Note that both P h and thus ϵ belief have implicit dependencies on Compress h , as c h := Compress h (c h ). We outline our algorithm in Algorithm 7, which is conceptually similar to the algorithm for POMDPs (Algorithm 2), maintaining the asymmetric critic (i.e., value function), and performing the actor update (i.e., policy update) using the belief-weighted value function. Theorem 7.6 (Equilibria learning; Combining Theorem J.15 and Theorem J.16). Fix ϵ, δ ∈ (0, 1). Under Assumption C.8, with probability at least 1 -δ, Algorithm 7 can learn an(ϵ + H 2 ϵ belief )-NE if G is zero-sum and (ϵ + H 2 ϵ belief )-CE/CCE if G is general-sum with sample complexity O( H 4 SAO log(SAHO/δ) ϵ 2) and computational complexityPOLY(S, (AO) O(γ -4 log(SH/ϵ)) , H, 1 ϵ , log 1 δ ).Learning approximate belief with model truncation. The belief learning algorithm we design for POSGs is conceptually similar to that we designed for POMDPs, where the key to achieving both polynomial sample and computational complexity is still to firstly learn approximate models, i.e., transitions and emissions, and then carefully truncate (as in Section 5.2) its transition and emission to build the approximate belief, where we defer the detailed algorithm to Algorithm 8. Next, we provide its provable guarantees, which leads to a final polynomial-sample and quasi-polynomial-time complexity result when combined with Theorem 7.6. Theorem 7.7. For any ϵ > 0, under Assumption 2.2, it holds that one can learn the approximate belief{ P h : C h → ∆(S × P h )} h∈[H] such that ϵ belief ≤ ϵH 2 with both polynomial sample complexity and computational complexity POLY(S, A, O, H, ) and computational complexity POLY(S, (AO) O(γ -4 log(SH/ϵ)) , H, 1 ϵ , log 1 δ ).Learning with Privileged Information" Our work is theoretical by nature, and aimed at better understanding reinforcement learning under partial observability with privileged information. As such, we do not anticipate any direct positive or negative societal impact from this research.Provable partial observable RL. While POMDPs are generally known to be both statistically hard [42] and computationally intractable [65] , a productive line of research has identified several structured subclasses of POMDPs that can be efficiently solved. [42] introduced the class of POMDPs in the rich-observation setting, where the observation space can be large and fully reveal the underlying state, where sample-efficient RL becomes possible [34, 59] . [19] introduced k-step decodable POMDPs, where the last k observation-action pairs can uniquely determine the state, and proposed polynomial-sample complexity algorithms (assuming k is a small constant). Beyond settings where the underlying state can be exactly recovered, [35, 46] proposed weakly revealing POMDPs, where the observations are assumed to be informative enough. Under the weakly revealing condition (and its variant), there has been a fast-growing line of recent works developing sample-efficient RL algorithms for various settings, see e.g., [83, 15, 12, 53, 47, 89] . Notably, these algorithms are typically computationally inefficient, requiring access to an optimistic planning oracle for POMDPs. On a promising note, [26] showed that in observable POMDPs (see Assumption 2.2), one can have quasi-polynomial-time algorithms for planning the near-optimal policy, which further leads to provable RL algorithms [25, 27] with both quasi-polynomial samples and time.RL under hindsight observability. The closest line of research to ours are the recent theoretical studies for Hindsight Observable Markov Decision Processes (HOMDPs) [43] , where the underlying state is revealed at the end of the episode; see also subsequent related works in [30, 75] with different observation feedback models. These works focused purely on sample efficiency, and showed that polynomial sample complexity can be achieved without (or by further relaxing) aforementioned structural assumptions of the model (e.g., observability or decodability), in both tabular and/or function approximation settings. However, the algorithms (also) require an oracle for planning or even optimistic planning in a learned approximate POMDP, which are not computationally tractable in general. Indeed, without any structural assumption, learning the optimal policy in HOMDPs is computationally no easier than the planning problem, which thus remains PSPACE-hard . [65] . Meanwhile, even under the additional assumption of observability on the underlying POMDP model, it is still not clear if these algorithms can avoid computationally intractable oracles, since the approximate POMDP that [43] needs to do planning on at every iteration during learning can be quite different from the underlying model. For example, at the beginning of exploration when not enough samples are collected, or when there exist certain states that remain less explored during the entire learning process, the potentially misspecified emission (and transition) may break the observability (or other structural) assumptions made for the underlying POMDP. This makes that single iteration even computationally intractable. In contrast, our focus is on better understanding practically inspired algorithmic paradigms, without computationally intractable oracles, which in practice often do have and use the privileged state information during each episode (instead of only at the end) [67, 44, 14] .Most related empirical works. Privileged information has been widely used in empirical partially observable RL, with two main types of approaches based on privileged policy and privileged value learning, respectively. For the former, one prominent example is expert distillation [14, 63, 57] , also known as teacher-student learning [44, 58, 74] , as we analyze in Section 4. For the latter, asymmetric actor-critic [67] represents one of the well-known examples, with other studies in [7, 3] . Learning privileged value functions (to improve the policies) has also been widely used in multi-agent RL, featured in centralized-training-decentralized-execution, see e.g., [52, 22, 69, 85, 81] . Intriguingly, it was shown that if the privileged value function depends only on the state, the associated actor will cause bias [6, 54, 55] . This has thus necessitated the use of history/belief in asymmetric actor-critic, as in our Section 5. Notably, the empirical framework in [82] exactly matches ours, where they exploited the privileged state information in training for belief learning, followed by policy optimization over the learned belief states. Indeed, many empirical works explicitly separate the procedures of explicit belief-state learning and planning [24, 64, 33, 16, 86] as we study in Section 5, oftentimes with privileged state information to supervise the belief learning procedure [60, 5] .C. B h (b; o)(x) = O h (o | x)b(x) z∈S O h (o | z)b(z) , for each x ∈ S. For each h ∈ [H + 1], the belief update operator U h : ∆(S) × A × O → ∆(S), is defined by U h (b; a, o) = B h+1 (T h (a) • b; o) ,where T h (a) • b represents the matrix multiplication. We use the notation b h to denote the belief update function, which receives a sequence of actions and observations and outputs a distribution over states at the step h: the belief state at step h = 1 is defined as b 1 (∅) = µ 1 . For any 2 ≤ h ≤ H and any action-observation sequence (a 1:h , o 1:h ), we inductively define the belief state:b h+1 (a 1:h , o 1:h ) = T h (a h ) • b h (a 1:h-1 , o 1:h ), b h (a 1:h-1 , o 1:h ) = B h (b h (a 1:h-1 , o 1:h-1 ); o h ).We also define the approximate belief update using the most recent L-step history. For 1 ≤ h ≤ H, we follow the notation of [26] and defineb apx,P h (∅; D) = µ 1 if h = 1 D otherwise ,where D ∈ ∆(S) is the prior for the approximate belief update. Then for any 1 ≤ h -L < h ≤ H and any action-observation sequence (a h-L:h , o h-L+1:h ), we inductively defineb apx,P h+1 (a h-L:h , o h-L+1:h ; D) = T h (a h ) • b apx,P h (a h-L:h-1 , o h-L+1:h ; D), b apx,P h (a h-L:h-1 , o h-L+1:h ; D) = B h (b apx,P h (a h-L:h-1 , o h-L+1:h-1 ; D); o h ).For the remainder of our paper, we will use an important initialization for the approximate belief, which are defined as b ′ h (•) := b apx,P h (•; Unif(S)).Model. We use a general framework of partially observable stochastic games (POSGs) as the model for partially observable MARL. Formally, we define a POSG with n agents by a tupleG = (H, S, {A i } n i=1 , {O i } n i=1 , T, O, µ 1 , {r i } n i=1 ), where H denotes the length of each episode, S is the state space with |S| = S, A i denotes the action space for agent i with|A i | = A i . We denote by a := (a 1 , • • • , a n ) the jointA = A 1 × • • • × A n the joint action space with |A| = A = n i=1 A i . We use T = {T h } h∈[H] to denote the collection of transition matrices, so that T h (• | s, a) ∈ ∆(S)gives the probability of the next state if joint action a ∈ A is taken at state s ∈ S and step h. In the following discussions, for any given a, we treat T h (a) ∈ R |S|×|S| as a matrix, where each row gives the probability for the next state from different current states. We use µ 1 to denote the distribution of the initial state s 1 , and O i to denote the observation space for agent i with |O i | = O i . We denote by o := (o 1 , . . . , o n ) the joint observation of all n agents, and byO := O 1 × • • • × O n with |O| = O = n i=1 O i . We use O = {O h } h∈[H]to denote the collection of the joint emission matrices, so that O h (• | s) ∈ ∆(O) gives the emission distribution over the joint observation space O at state s and step h. For notational convenience, we will at times adopt the matrix convention, where O h is a matrix with rows O h (• | s h ). We also denoteO i,h (• | s) ∈ ∆(O i )as the marginalized emission for agent i agent. Finally, r i = {r i,h } h∈[H] is a collection of reward functions, so that r i,h (s h , a h ) is the reward of agent i agent given the state s h and joint action a h at step h.Similar to a POMDP, in a POSG, the states are not observable to the agents, and each agent can only access its own individual observations. The game proceeds as follows. At the beginning of each episode, the environment samples s 1 from µ 1 . At each step h, each agent i observes its own observation o i,h , whereo h := (o 1,h , . . . , o n,h ) is sampled jointly from O h (• | s h ).Then each agent i takes the action a i,h and receives the reward r i,h (s h , a h ). After that the environment transitions to the next state s h+1 ∼ T h (• | s h , a h ). The current episode terminates once s H+1 is reached.Information sharing, common and private information. Each agent i in the POSG maintains its own information, τ i,h , a collection of historical observations and actions at step h, namely,τ i,h ⊆ {o 1 , a 1 , o 2 , • • • , a h-1 , o h },and the collection of such history at step h is denoted by T i,h .In many practical examples, agents may share part of the history with each other, which may introduce some information structures of the game that may lead to both sample and computation efficiencies. The information sharing splits the history into common/shared and private information for each agent. The common information at step h is a subset of the joint historyτ h = (τ i,h ) i∈[n] : c h ⊆ {o 1 , a 1 , o 2 , • • • , a h-1 , o h },which is available to all the agents in the system, and the collection of the common information is denoted as C h and we define C h = |C h |. Given the common information c h , each agent also has her private information p i,h = τ i,h \ c h , where the collection of the private information for agent i is denoted as P i,h and its cardinality as P i,h . The cardinality of the joint private information is P h = n i=1 P i,h . We allow c h or p i,h to take the special value ∅ when there is no common or private information. In particular, when C h = {∅}, the problem reduces to the general POSG without any favorable information structure; when P i,h = {∅}, every agent holds the same history, and it reduces to a POMDP when the agents share a common reward function, where the goal is usually to find the team-optimal solution.Policies and value functions. We define a stochastic policy for agent i at step h as:π i,h : Ω h × P i,h × C h → ∆(A i ), (C.1)where Ω h is the random seed space, which is shared among agents and ω i,h ∈ Ω h is the random seed for agent i. The corresponding policy class is denoted as Π i,h . Hereafter, unless otherwise noted, when referring to policies, we mean the policies given in the form of (C.1), which maps the available information of agent i, i.e., the private information together with the common information, to the distribution over her actions.We define π i as a sequence of policies for agent i at all steps h ∈ [H], i.e.,π i = (π i,1 , • • • , π i,H ).We further denote Π i = × h∈[H] Π i,h as the policy space for agent i and Π = i∈[n] Π i as the joint policy space. As a special case, we define the space of deterministic policy as Π i , where π i ∈ Π i maps the private information and common information to a deterministic action for agent i and the joint space asΠ = i∈[n] Π i .A product policy is denoted asπ = π 1 × π 2 • • • × π n ∈ Π if the distributions of drawing each seed ω i,hfor different agents are independent, and a (potentially correlated) joint policy is denoted asπ = π 1 ⊙ π 2 • • • ⊙ π n ∈ Π.We are now ready to define the value function conditioned on the common information under our model of POSG with information sharing: Definition C.2 (Value function with information sharing). For each agent i ∈ [n] and step h ∈ [H],given common information c h and joint policy π = (π i ) n i=1 ∈ Π, the value function conditioned on the common information of agent i is defined as:V π,G i,h (c h ) := E G π H h ′ =h r i,h ′ (s h ′ , a h ′ ) c h, where the expectation is taken over the randomness from the model G, policy π, and the random seeds. For any c H+1 ∈ C H+1 : V π,G i,H+1 (c H+1 ) := 0. From now on, we will refer to it as value function for short.Another key concept in our analysis is the belief about the state and the private information conditioned on the common information among agents. Formally, at step h, given policies from 1 to h -1, we consider the common-information-based conditional belief Pπ 1:h-1 ,G h (s h , p h | c h ).This belief not only infers the current underlying state s h , but also all agents' private information p h . With the common-information-based conditional belief, the value function given in Definition C.2 has the following recursive structure:V π,G i,h (c h ) = E G π [r i,h (s h , a h ) + V π,G i,h+1 (c h+1 ) | c h ], (C.2)where the expectation is taken over the randomness of (s h , p h , a h , o h+1 ). With this relationship, we can define the prescription-value function correspondingly, a generalization of the action-value function in (fully observable) stochastic games and MDPs to POSGs with information sharing, as follows.Definition C.3 (Prescription-value function with information sharing). At step h, given the common information c h , joint policies π = (π i ) n i=1 ∈ Π, and prescriptions (γ i,h ) n i=1 ∈ Γ h , the prescriptionvalue function conditioned on the common information and joint prescription of agent i is defined as:Q π,G i,h (c h , (γ j,h ) j∈[n] ) := E G π r i,h (s h , a h ) + V π,G i,h+1 (c h+1 ) c h , (γ j,h ) j∈[n] ,where prescriptionγ i,h ∈ ∆(A i ) P i,h replaces the partial function π i,h (• | ω i,h , c h , •) in the value function.From now on, we will refer to it as prescription-value function for short. With such a prescription-value function, agents can take actions purely based on their local private information [62, 61, 50] .This prescription-value function indicates the expected return for agent i when all the agents firstly adopt the prescriptions (γ j,h ) j∈[n] and then follow the policy π.Equilibrium notions. With the definition of value functions, we can accordingly define the solution concepts. Here we define the notions of ϵ-NE, ϵ-CCE, ϵ-CE, and ϵ-team optimum under the information-sharing framework as follows. For a joint policy 4 (ϵ-approximate Nash equilibrium with information sharing). For any ϵ ≥ 0, a product policy π ⋆ ∈ Π is an ϵ-approximate Nash equilibrium of the POSG G with information sharing if:(π i ) n i=1 ∈ Π we denote the expected reward of agent i by v G i (π) = E P π [ H h=1 r i,h (s h , a h )]. Definition C.NE-gap(π ⋆ ) := max i max π ′ i ∈Πi v G i (π ′ i × π ⋆ -i ) -v G i (π ⋆ ) ≤ ϵ.Definition C.5 (ϵ-approximate coarse correlated equilibrium with information sharing). For any ϵ ≥ 0, a joint policy π ⋆ ∈ Π is an ϵ-approximate coarse correlated equilibrium of the POSG G with information sharing if:CCE-gap(π ⋆ ) := max i max π ′ i ∈Πi v G i (π ′ i × π ⋆ -i ) -v G i (π ⋆ ) ≤ ϵ.Definition C.6 (ϵ-approximate correlated equilibrium with information sharing). For any ϵ ≥ 0, a joint policy π ⋆ ∈ Π is an ϵ-approximate correlated equilibrium of the POSG G with information sharing if:CE-gap(π ⋆ ) := max i max ϕi v G i ((m i ⋄ π ⋆ i ) ⊙ π ⋆ -i ) -v G i (π ⋆ ) ≤ ϵ,where m i is called strategy modification for agent i, andm i = {m i,h,c h ,p i,h } h,c h ,p i,h, with each m i,h,c h ,p i,h : A i → A i being a mapping from the action set to itself. The space of m i is denoted as M i . The composition m i ⋄ π i is defined as follows: at step h, when agent i is given c h and p i,h , the joint action chosen to be (a1,h , • • • , a i,h , • • • , a n,h ) will be modi- fied to (a 1,h , • • • , m i,h,c h ,p i,h (a i,h ), • • • , a n,h). Note that this definition follows from that in [77, 49, 37, 48, 50] when there exists certain common information, and is a natural generalization of the definition in the normal-form game case [70] . We denote by M gen i the space of all possible strategy modifications m i if it conditions on any history information instead of only (c h , p i,h ). Similarly, we use M S,i to denote the space of all possible strategy modifications m i if it only conditions on the current state e.g., a modification m i,h,s : A i → A i .Assumption C.7 (Evolution of common and private information). We assume that common information and private information evolve over time as follows:• Common information c h is non-decreasing over time, that is, c h ⊆ c h+1 for all h. Let ϖ h+1 = c h+1 \ c h . Thus, c h+1 = {c h , ϖ h+1 }. Further, we haveϖ h+1 = χ h+1 (p h , a h , o h+1 ), (C.3)where χ h+1 is a fixed transformation. We use Υ h+1 to denote the collection of ϖ h+1 at step h.• Private information evolves according to:p i,h+1 = ξ i,h+1 (p i,h , a i,h , o i,h+1 ), (C.4)where ξ i,h+1 is a fixed transformation.Equation (C.3) states that the increment in the common information depends on the "new" information (a h , o h+1 ) generated between steps h and h + 1 and part of the old information p h . The incremental common information can be obtained by certain sharing and communication protocols among the agents. Equation (C.4) implies that the evolution of private information only depends on the newly generated private information a i,h and o i,h+1 . These evolution rules are standard in the literature [61, 62] , specifying the source of common information and private information. Based on such evolution rules, we define{f h } h∈[H] and {g h } h∈[H] , where f h : A h × O h → C h and g h : A h × O h → P h for h ∈ [H],as the mappings that map the joint history to common information and joint private information, respectively.To solve a POSG without computationally intractable oracles, certain information-sharing is needed even under the observability assumption [50] . We thus make the following assumption as in [50] .Assumption C.8 (Strategy independence of beliefs [61, 31, 50] ). Consider any step h ∈ [H], any policy π ∈ Π, and any realization of common information c h that has a non-zero probability under the trajectories generated by π 1:h-1 . Consider any other policies π ′ 1:h-1 , which also give a nonzero probability to c h . Then, we assume that: for any such c h ∈ C h , and any p h ∈ P h , s h ∈ S,P π 1:h-1 ,G h (s h , p h | c h ) = P π ′ 1:h-1 ,G h (s h , p h | c h ) .We provide examples satisfying this assumption in Appendix C.2, which include the fully-sharing structure as in [27, 68] as a special case. Finally, we also assume that common information and private information evolve over time properly in Assumption C.7, as standard in [61, 62, 50] , which covers the models considered in [27, 68, 48] .Here we take the examples from [51, 50] to illustrate the generality of the information-sharing framework.Example C.9 (One-step delayed sharing). At any step h ∈ [H], the common and private information are given as c h = {o 2:h-1 , a 1:h-1 } and p i,h = {o i,h }, respectively. In other words, the players share all the action-observation history until the previous step h -1, with only the new observation being the private information. This model has been shown useful for power control [2] .Example C.10 (State controlled by one controller with asymmetric delay sharing). We assume there are 2 players for convenience. It extends naturally to n-player settings. Consider the case where the state dynamics are controlled by player1, i.e., T h (• | s h , a 1,h , a 2,h ) = T h (• | s h , a 1,h , a ′ 2,h ) for all (s h , a 1,h , a 2,h , a ′ 2,h , h).There are two kinds of delay-sharing structures we could consider: Case A: the information structure is given asc h = {o 1,2:h , o 2,2:h-d , a 1,1:h-1 }, p 1,h = ∅, p 2,h = {o 2,h-d+1:h }, i.e., player 1's observations are available to player 2 instantly, while player 2's observations are available to player 1 with a delay of d ≥ 1 time steps. Case B: similar to Case A but player 1's observation is available to player 2 with a delay of 1 step. The information structure is given asc h = {o 1,2:h-1 , o 2,2:h-d , a 1,1:h-1 }, p 1,h = {o 1,h }, p 2,h = {o 2,h-d+1:h }, where d ≥ 1.This kind of asymmetric sharing is common in network routing [66] , where packages arrive at different hosts with different delays, leading to asymmetric delay sharing among hosts.Example C.11 (Symmetric information game). Consider the case when all observations and actions are available for all the agents, and there is no private information. Essentially, we have c h = {o 2:h , a 1:h-1 } and p i,h = ∅. We will also denote this structure as fully sharing hereafter. Example C.12 (Information sharing with one-directional-one-step delay). Similar to the previous cases, we also assume there are 2 players for ease of exposition, and the case can be generalized to multi-player cases straightforwardly. Similar to the one-step delay case, we consider the situation where all observations of player 1 are available to player 2, while the observations of player 2 are available to player 1 with one-step delay. All the past actions are available to both players. That is, in this case, c h = {o 1,2:h , o 2,2:h-1 , a 1:h-1 }, and player 1 has no private information, i.e., p 1,h = ∅, and player 2 has private information p 2,h = {o 2,h }. Example C.13 (Uncontrolled state process). Consider the case where the state transition does not depend on the actions, that is,T h (• | s h , a h ) = T h (• | s h , a ′ h ) for any s h , a h , a ′ h , h.Note that the agents are still coupled through the joint reward. An example of this case is the information structure where controllers share their observations with a delay of d ≥ 1 time steps. In this case, the common information is c h = {o 2:h-d } and the private information is p i,h = {o i,h-d+1:h }. Such information structures can be used to model repeated games with incomplete information [4] .Require:1:• POMDP P, • Expert policy π E ∈ Π S , • Number of sampled episodes per step M . Ensure: A decoding function for each step {g h } h∈[H] (see Theorem 4.6) 2: For the h = 1 step: Collect M state-observation pairs from the first-step D 1 = s (i) 1 , o (i) 1 i∈[M ]on POMDP P and define the decoding function g 1 for the first step as:EQUATION1:H , a(i) 1:H i∈[M ]on POMDP P using policy π E and let:D h := s (i) h-1 , a (i) h-1 , o (i) h , s (i) h i∈[M ] 5:Define the decoding function g h for step h as:g h (s h-1 , a h-1 , o h ) = s h : (s h-1 , a h-1 , o h , s h ) ∈ D h 6: end for 7: return {g h } h∈[H]Algorithm 2 Belief-Weighted Optimistic Asymmetric Actor-Critic with Privileged InformationRequire:• POMDP P, • Subroutine T Q that given policy π ∈ Π L , outputs { Q π h } h∈[H] that approximates {Q π,P h } h∈[H] , • Subroutine T b that outputs {b apx h } h∈[H] that approximate {b h } h∈[H] ,• Initial finite-memory policy π 0 = {π 0 h } h∈[H] ∈ Π L for the POMDP P, step-size η, and number of iterations T . Ensure: A near-optimal policy{b apx h } h∈[H] ← T b (P). for Iterations t = 1 . . . , T do { Q t h } h∈[H] ← T Q (P, π t-1 ) Update the policy for each a h ∈ A, z h ∈ Z h as π t h (a h | z h ) ∝ π t-1 h (a h | z h ) • exp ηE s h ∼b apx h (z h ) Q t-1 h (z h , s h , a h ) . Denote π t = π t 1:H end for return A policy uniform at random from set {π t } t∈[T ] Algorithm 3 Optimistic Q-function Estimation with Privileged Information Require: • POMDP P, policy π 1:H ∈ Π L such that π h : S → ∆(A), • Number of episodes M per step. Ensure: Approximate Q-functions { Q π h } h∈[H] (see Lemma H.3) Initialize: ∀z H+1 ∈ Z H+1 , s H+1 ∈ S, a H+1 ∈ A Q π H+1 (z H+1 , s H+1 , a H+1 ) ← 0, π H+1 (a H+1 | z H+1 ) ← 1 |A| .for step h = H, . . . , 1 do Collect M trajectories using policy π and let D h = {τ (i) } i∈[M ] be the collected trajectories.Compute empirical counts and define empirical distributions:T h (s h+1 | s h , a h ) = |{τ ∈ D h : (s ′ h , a ′ h , s ′ h+1 ) = (s h , a h , s h+1 )}| |{τ ∈ D h : (s ′ h , a ′ h ) = (s h , a h )}| O h (o h | s h ) = |{τ ∈ D h : (s ′ h , o ′ h ) = (s h , o h )}| |{τ ∈ D h : s ′ h = s h }| for each memory-state pair (z h , s h ) ∈ Z h × S do Q π h (z h , s h , a h ) = min H -h + 1, E s h+1 ∼ T h (• | s h ,a h ), o h+1 ∼ O h+1 (• | s h+1 ) [ V π h+1 (z h+1 , s h+1 )] + r(s h , a h ) + H • min 2, C • |S| log(1/δ 1 ) max(N h (s h , a h ), 1) + E s h+1 ∼ T h (• | s h ,a h ) H • min 2, C • |O| log(1/δ 1 ) max(N h+1 (s h+1 ), 1),where V π h+1 (z h+1 , s h+1 ) = E a h+1 ∼π h+1 (• | z h+1 ) [ Q π h+1 (z h+1 , s h+1 , a h+1 )] end for end for return { Q π h } h∈[H]Algorithm 4 Approximate Belief Learning with Privileged Information via Model TruncationRequire:• POMDP P = (H, S, A, O, {T h } h∈[H] , {O h } h∈[H] , µ 1 , {r h } h∈[H] ),• An MDP learning oracle MDP_Learning that efficiently learns an approximate optimal policy of an MDP,• Number of trajectories N , • ϵ. Ensure: Approximate belief {b apx h } h∈[H] (See Theorem H.5) for h ∈ [H], s h ∈ S do r h ′ (s ′ h , a ′ h ) ← 1[h ′ = h, s ′ h = s h ] for any (h ′ , s ′ h , a ′ h ) ∈ [H] × S × A. M ← (H, S, A, {T h } h∈[H] , µ 1 , { r h } h∈[H]) to be the MDP associated with P Ψ(h, s h ) ← MDP_Learning(M) Collect N trajectories by executing policy Ψ(h, s h ) for the first h -1 steps then take action a h for each a h ∈ A deterministically and denote the dataset{(s i h , o i h , a i h , s i h+1 )} i∈[N A] for (o h , a h , s h+1 ) ∈ O × A × S do N h (s h ) ← i∈[N A] 1[s i h = s h ] N h (s h , a h ) ← i∈[N A] 1[s i h = s h , a i h = a h ] N h (s h , a h , s h+1 ) ← i∈[N A] 1[s i h = s h , a i h = a h , s i h+1 = s h+1 ] N h (s h , o h ) ← i∈[N A] 1[s i h = s h , o i h = o h ] T h (s h+1 | s h , a h ) ← N h (s h ,a h ,s h+1 ) N h (s h ,a h ) O h (o h | s h ) ← N h (s h ,o h ) N h (s h ) end for end for for h ∈ [H] do S low h ← s h ∈ S | N h (s h ) N A ≤ ϵ S high h ← s h ∈ S | N h (s h ) N A > ϵ end for for (h, s h , o h , a h , s h+1 ) ∈ [H] × S high h × O × A × S high h do T trunc h (s h+1 | s h , a h ) ← T h (s h+1 | s h , a h ) + s ′ h+1 ∈S low h+1 T h (s ′ h+1 | s h ,a h ) |S high h+1 | O trunc h (o h | s h ) ← O h (o h | s h ) µ trunc 1 (s 1 ) := µ 1 (s 1 ) + s ′ 1 ∈S low 1 µ1(s ′ 1 ) |S high 1 |, ∀s 1 ∈ S high 1 end for LetP sub := (H, {S high h } h∈[H] , A, O, { T trunc h } h∈[H] , { O trunc h } h∈[H] , µ trunc 1 , {r h } h∈[H] ) Define { b ′,sub h : Z h → ∆(S high h )} h∈[H]to be the approximate belief w.r.t.P sub Define {b apx h : Z h → ∆(S)} h∈[H] such that b apx h (z h )(s h ) = b ′,sub h (z h )(s h ) for s h ∈ S high h and 0 otherwise. return {b apx h } h∈[H]Algorithm 5 Learning Multi-Agent (Individual) Decoding Functions with Privileged Information (NE/CCE Version) Require:• POSG G = (H, S, A, O, {T h } h∈[H] , {O h } h∈[H] , µ 1 , {r i } i∈[n] ) • π ∈ Π S , controller set {I h ⊆ [n]} h∈[H] .• Procedure MDP_Learning(•, •) that takes as input an MDP and a reward function and returns an approximate optimal policy, • Number of trajectories N . Ensure: A decoding function for each agent and step{ g j,h } j∈[n],h∈[H] (see Theorem J.6) for h ∈ [H], s h ∈ S do for i ∈ [n] do r i,h ′ (s ′ h , a ′ h ) ← 1[h ′ = h, s ′ h = s h ] for any h ′ , s ′ h , a ′ h ∈ [H] × S × A. Define M to be the MDP associated with G, M(π -i ) to be the MDP marginalized by π -i Ψ i (h, s h ) ← MDP_Learning(M(π -i ), r i ) end forCollect N trajectories by executing policy Ψ i (h, s h ) × π -i for the first h -1 steps then take action a h deterministically for each a h ∈ A and denote the dataset{(s k,i h , o k,i h , a k,i h , s k,i h+1 )} k∈[N A] for each i ∈ [n] for (o h , a h , s h+1 ) ∈ O × A × S do N h (s h ) ← k∈[N ],i∈[n] 1[s k,i h = s h ] N h (s h , a T h ,h , s h+1 ) ← k∈[N ],i∈[n] 1[s k,i h = s h , a k,i T h ,h = a T h ,h , s k,i h+1 = s h+1 ] N h (s h , o h ) ← k∈[N ],i∈[n] 1[s k,i h = s h , o k,i h = o h ] T h (s h+1 | s h , a T h ,h ) ← N h (s h ,a T h ,h ,s h+1 ) N h (s h ,a T h ,h ) O h (o h | s h ) ← N h (s h ,o h ) N h (s h ) end for end for Define G := (H, S, A, O, { T h } h∈[H] , { O h } h∈[H] , µ 1 , {r i } i∈[n] ) Define g j,h (s h | c h , p j,h ) := P G (s h | c h , p j,h ) for each j ∈ [n], h ∈ [H], c h ∈ C h , p j,h ∈ P j,h return { g j,h } j∈[n],h∈[H]Algorithm 6 Learning Multi-Agent (Individual) Decoding Functions with Privileged Information (CE Version) Require:• POSG G = (H, S, A, O, {T h } h∈[H] , {O h } h∈[H] , µ 1 , {r i } i∈[n] ) • π ∈ Π S , controller set {I h ⊆ [n]},• Procedure MDP_Learning(•, •) that takes as input an MDP and a reward function and returns an approximate optimal policy, • Number of trajectories N .for h ∈ [H], s h ∈ S do for i ∈ [n] do r i,h ′ (s ′ h , a ′ h ) ← 1[h ′ = h, s ′ h = s h ] for any h ′ , s ′ h , a ′ h ∈ [H] × S × A.Define M extended (π) to be the extended MDP, which is defined in Definition J. 5 .Ψ i (h, s h ) ← MDP_Learning(M extended (π), r i ) end forCollect N trajectories by executing policy Ψ i (h, s h ) × π -i for the first h -1 steps then take action a h deterministically for each a h ∈ A and denote the dataset{(s k,i h , o k,i h , a k,i h , s k,i h+1 )} k∈[N A] for each i ∈ [n] for (o h , a h , s h+1 ) ∈ O × A × S do N h (s h ) ← k∈[N ],i∈[n] 1[s k,i h = s h ] N h (s h , a T h ,h , s h+1 ) ← k∈[N ],i∈[n] 1[s k,i h = s h , a k,i T h ,h = a T h ,h , s k,i h+1 = s h+1 ] N h (s h , o h ) ← k∈[N ],i∈[n] 1[s k,i h = s h , o k,i h = o h ] T h (s h+1 | s h , a T h ,h ) ← N h (s h ,a T h ,h ,s h+1 ) N h (s h ,a T h ,h ) O h (o h | s h ) ← N h (s h ,o h ) N h (s h ) end for end for Define G := (H, S, A, O, { T h } h∈[H] , { O h } h∈[H] , µ 1 , {r i } i∈[n] ) Define g j,h (s h | c h , p j,h ) := P G (s h | c h , p j,h ) for each j ∈ [n], h ∈ [H], c h ∈ C h , p j,h ∈ P j,h return { g j,h } j∈[n],h∈[H] Algorithm 7 Optimistic Common-Information-Based Value Iteration with Privileged Information Require: POSG G, ϵ e , { P h : C h → ∆(S × P h )} h∈[H] for k = 1, 2, • • • , K do for h ← H, H -1, • • • , 1 do for c h ∈ C h do Q high,k i,h ( c h , p h , s h , a h ) ← min r i,h (s h , a h ) + b k-1 h (s h , a h ) + E o h+1 ∼ J k-1 h (• | s h ,a h ) V high,k i,h+1 ( c h+1 ) , H -h + 1 for i ∈ [n] Q low,k i,h ( c h , p h , s h , a h ) ← max r i,h (s h , a h ) -b k-1 h (s h , a h ) + E o h+1 ∼ J k-1 h (• | s h ,a h ) V low,k i,h+1 ( c h+1 ) , 0 for i ∈ [n] Define Q high,k i,h ( c h , γ h ) := E s h ,p h ∼ P h (•,• | c h ) E {a j,h ∼γ j,h (• | p j,h )} j∈[n] Q high,k i,h ( c h , p h , s h , a h ) for i ∈ [n] Define Q low,k i,h ( c h , γ h ) := E s h ,p h ∼ P h (•,• | c h ) E {a j,h ∼γ j,h (• | p j,h )} j∈[n] Q low,k i,h ( c h , p h , s h , a h ) for i ∈ [n] {π k j,h (• | •, c h , •)} j∈[n] ← Bayesian-CE/CCE({Q high,k j,h ( c h , •)} j∈[n] ) (c.f. Appendix J.1) V high,k i,h ( c h ) ← E ω h Q high,k i,h ( c h , {π k j,h (• | ω j,h , c h , •)} j∈[n] ) for i ∈ [n] V low,k i,h ( c h ) ← E ω h Q low,k i,h ( c h , {π k j,h (• | ω j,h , c h , •)} j∈[n] ) for i ∈ [n] end for end for Execute π k and get trajectory (s k 1:H , a k 1:H , o k 1:H+1 ) for h ∈ [H], s h ∈ S, a h ∈ A, o h+1 ∈ O do N k h (s h , a h ) ← l∈[k] 1[s l h = s h , a l h = a h ] N k h (s h , a h , o h+1 ) ← l∈[k] 1[s l h = s h , a l h = a h , o l h+1 = o h+1 ] J k h (o h+1 | s h , a h ) ← N k h (s h ,a h ,o h+1 ) N k h (s h ,a h )end for end for Algorithm 8 Approximate Belief Learning for MARL with Privileged InformationRequire: POSG G = (H, S, A, O, {T h } h∈[H] , {O h } h∈[H] , µ 1 , {r i,h } i∈[n],h∈[H] ), controller set {I h ⊆ [n]} h∈[H], procedure MDP_Learning(•, •), number of trajectories N , and accuracy ϵ.for h ∈ [H], s h ∈ S do r h ′ (s ′ h , a ′ h ) ← 1[h ′ = h, s ′ h = s h ] for any (h ′ , s ′ h , a ′ h ) ∈ [H] × S × A. M ← (H, S, A, {T h } h∈[H] , µ 1 , { r h } h∈[H]) to be the MDP associated with P Ψ(h, s h ) ← MDP_Learning(M) Collect N trajectories by executing policy Ψ(h, s h ) for the first h -1 steps then take action a h for each a h ∈ A deterministically and denote the dataset{(s i h , o i h , a i h , s i h+1 )} i∈[N A] for (o h , a h , s h+1 ) ∈ O × A × S do N h (s h ) ← i∈[N A] 1[s i h = s h ] N h (s h , a T h ,h ) ← i∈[N A] 1[s i h = s h , a i T h ,h = a T h ,h ] N h (s h , a T h ,h , s h+1 ) ← i∈[N A] 1[s i h = s h , a i T h ,h = a T h ,h , s i h+1 = s h+1 ] N h (s h , o h ) ← i∈[N A] 1[s i h = s h , o i h = o h ] T h (s h+1 | s h , a T h ,h ) ← N h (s h ,a h ,s h+1 ) N h (s h ,a T h ,h ) O h (o h | s h ) ← N h (s h ,o h ) N h (s h ) end for end for for h ∈ [H] do S low h ← s h ∈ S | N h (s h ) N A ≤ ϵ S high h ← s h ∈ S | N h (s h ) N A > ϵ end for for (h, s h , o h , a h , s h+1 ) ∈ [H] × S high h × O × A × S high h do T trunc h (s h+1 | s h , a h ) ← T h (s h+1 | s h , a h ) + s ′ h+1 ∈S low h+1 T h (s ′ h+1 | s h ,a h ) |S high h+1 | O trunc h (o h | s h ) ← O h (o h | s h ) µ trunc 1 (s 1 ) := µ 1 (s 1 ) + s ′ 1 ∈S low 1 µ1(s ′ 1 ) |S high 1 |, ∀s 1 ∈ S high 1 end for Let G sub := (H, {S high h } h∈[H] , A, O, { T trunc h } h∈[H] , { O trunc h } h∈[H] , µ trunc 1 , {r i,h } i∈[n],h∈[H] ) Define { P h : C h → ∆(P h × S high h )} h∈[H] to be the approximate belief w.r.t. G sub Define { P h : C h → ∆(S × P h )} h∈[H] such that P h (s h , p h | c h ) = P h (s h , p h | s h ) for s h ∈ S highE P τ h ∼π ′ E s h ∼b h (τ h ) [D f (π ⋆ h (• | s h ) | π h (• | τ h ))] .Therefore, for any h ∈ [H] and τ h such that P π ′ ,P (τ h ) > 0, we can optimize π separately for each h ∈ [H] and τ h as:π ⋆ h (• | τ h ) ∈ argmin q∈∆(A) E s h ∼b h (τ h ) [D f (π ⋆ h (• | s h ) | q)] .Now we are ready to construct the counter-example of γ-observable POMDP P ϵ for some ϵ ∈ (0, 1)with H = 1, S = s 1 , s 2 , A = a 1 , a 2 , and O = o 1 , o 2 . We let µ 1 = ( 1-γ 2-γ , 1 2-γ ), O 1 (o 1 | s 1 ) = 1, and O 1 (o 1 | s 2 ) = 1 -γ, O 1 (o 2 | s 2 ) = γ. Therefore, it is direct to see that O 1 is exactly γ-observable. Most importantly, we choose r 1 (s 1 , a 1 ) = 1, r 1 (s 1 , a 2 ) = 0, and r 1 (s 2 , a 1 ) = 0, r 1 (s 2 , a 2 ) = ϵ.Therefore, given such a reward function, the fully observable expert policy is given by π⋆ 1 (a 1 | s 1 ) = 1 and π ⋆ 1 (a 2 | s 2 ) = 1, i.e., choosing a 1 at state s 1 and a 2 at state s 2 deterministically. Meanwhile, by our construction, one can compute that the belief given observation o 1 ensures b 1 (o 1 ) = Unif(S). Hence, the corresponding "distilled" partially observable policy under observation o 1 is given byπ ⋆ 1 (• | o 1 ) = argmin q∈∆(A) E s1∼b1(o 1 ) [D f (π ⋆ 1 (• | s 1 ) | q)] = argmin q∈∆(A) D f (π ⋆ 1 (• | s 1 ) | q) + D f (π ⋆ 1 (• | s 2 ) | q) 2 = argmin q∈∆(A) f (1/q(a 1 ))q(a 1 ) + f (0)q(a 2 ) + f (0)q(a 1 ) + f (1/q(a 2 ))q(a 2 ) 2 = argmin q∈∆(A) f (0) + f (1/q(a 1 ))q(a 1 ) + f (1/q(a 2 ))q(a 2 ) 2 ,where the last step is due to q ∈ ∆(A). Now consider the function g(x) = xf (1/x) for x > 0. It is direct to compute that g ′ (x) = f (1/x) -f ′ (1/x)x , and g ′′ (x) = f ′′ (1/x)x 3≥ 0 due to the convexity of the function f . Thus, we conclude that g is also convex. By Jensen's inequality, we have f (1/q(a 1 ))q(a 1 ) + f (1/q(a 2 ))q(a 2 ) 2 ≥ f (2/(q(a 1 ) + q(a 2 )))(q(a 1 ) + q(a 2 ))/2 = f (2)/2, where the equality holds when q(a 1 ) = q(a 2 ) = 1 2 . This indicates that π ⋆ 1 (• | o 1 ) = Unif(A). On the other hand, combining the fact that b 1 (o 1 ) = Unif(S) with ϵ < 1, it is direct to see that the optimal partially observable policy π ∈ arg max π∈Π v P (π) satisfies π 1 (a 1 | o 1 ) = 1. Now we are ready to evaluate the optimality gap between π and π ⋆ as followsv P ϵ ( π) -v P ϵ ( π ⋆ ) = P P ϵ (o 1 )(V π,P ϵ 1 (o 1 ) -V π ⋆ ,P ϵ 1 (o 1 )) + P P ϵ (o 2 )(V π,P ϵ 1 (o 2 ) -V π ⋆ ,P ϵ 1 (o 2 )) ≥ P P ϵ (o 1 )(V π,P ϵ 1 (o 1 ) -V π ⋆ ,P ϵ 1 (o 1 )),where the last step is due to the fact that π is the optimal policy, leading to the fact that V π,P ϵ 1(o 2 ) - V π ⋆ ,P ϵ 1 (o 2 ) ≥ 0. Now it is not hard to compute that P P ϵ (o 1 ) ≥ 1 -γ.Meanwhile, we can evaluate thatV π,P ϵ 1 (o 1 ) = 1 2 , V π ⋆ ,P ϵ 1 (o 1 ) = 1 + ϵ 4 and correspondingly V π,P ϵ 1 (o 1 )-V π ⋆ ,P ϵ 1 (o 1 ) = 1-ϵ 4 , implying that v P ϵ ( π)-v P ϵ ( π ⋆ ) ≥ (1-γ)(1-ϵ) 4. This concludes our proof.■Example E.1 (Deterministic POMDP [35, 80] ). We say a POMDP P is of deterministic transition if entries of matrices {T h } h∈[H] and the vector µ 1 are either 0 or 1. Note that we do not make any assumptions on the emission matrices.Example E.2 (Block MDP [42, 18] ). We say a POMDP P is a block MDP if for any h ∈ [19] ). We say a POMDP P is a k-step decodable POMDP if there exists an unknown decoder ϕ ⋆ = {ϕ ⋆ h : Z h → S} h∈[H] such that for any h ∈ [H] and reachable trajectory τ h , P P (s[H], s h , s ′ h ∈ S, it holds that supp(O h (• | s h )) ∩ supp(O h (• | s ′ h )) = ∅ when s h ̸ = s ′ h . Example E.3 (k-step decodable POMDPh = ϕ ⋆ h (z h ) | τ h ) = 1, where Z h = (O × A) max{h-1,k-1} × O, z h = ((o, a) k(h):h-1 , o h ), and k(h) = max{h -k + 1, 1}.Finally, to understand how our condition can extend beyond known examples in the literature, we show that one can indeed allow the decoding length of Example E.3 to be unknown and arbitrary (instead of being a small known constant as in [19] to have provably efficient algorithms).Example E.4 (POMDP with arbitrary, unknown decodable length). This example is similar to Example E.3, but the decoding length m is unknown and not necessarily a small constant.In light of the pitfall in Proposition 3.1, we will analyze both the computational and statistical efficiencies of expert distillation in Section 4, under the condition in Definition 3.2. Sample complexity: The algorithm executes the policy π t-1 and collect K episodes, denoted as{s k 1:H+1 , o k 1:H , a k 1:H } k∈[K]. Thus, the sample complexity of each iteration is Θ(K).Computational complexity for policy evaluation: The policy evaluation of the vanilla asymmetric actor-critic is done by minimizing the Bellman error. In the finite-horizon setting with tabular parameterization, it is equivalent to performing the following update for each h ∈ [H] in a backward way and each k ∈ [K]:Q t h (τ k h , s k h , a k h ) ← (1 -α)Q t-1 h (τ k h , s k h , a k h ) + α   r h (s k h , a k h ) + 1 |J (τ k h , s k h , a k h )| j∈J (τ k h ,s k h ,a k h ) Q t h+1 (τ j h+1 , s j h+1 , a j h+1 )   ,for some stepsize α ∈ (0, 1), whereJ (τ k h , s k h , a k h ) := {j ∈ [K] | (τ j h , s j h , a j h ) = (τ k h , s k h , a k h )}.Therefore, the computational complexity for this procedure is of POLY(H, K).Computational complexity for policy improvement: For tabular parameterization, computing∇ log π t-1 h (a k h | τ k h ) takes O(1) computation.Hence the policy update in Equation (3.2) performs POLY(H, K) computation. Meanwhile, under the exponential time hypothesis, there is no polynomial time algorithm for even planning an ϵ-approximate optimal policy in γ-observable POMDPs [26] . This implies that the vanilla asymmetric actor-critic needs to take super-polynomial time to find an approximately optimal policy. This implies the corresponding sample complexity has to be super-polynomial.Finally, we remark that even if we let the policy and the Q-function not depend on the entire history τ h but only the finite-memory z h , the proof still holds. The key is that whenever one only computes at the sampled history/finite-memories, i.e., updates the policy in an asynchronous way (in contrast to the synchronous one where the policies at all histories/finite-memories are updated), the sample and computational complexities will be coupled with the same order per iteration, which implies a super-polynomial sample complexity due to the super-polynomial computational complexity. ■ Derivation for the closed-form update Equation (3.3). Note that the proximal policy optimization [71] update has the policy improvement as followsπ t ← arg max π    L t-1 (π) -η -1 E P π t-1   h∈[H] KL(π h (• | τ h ) | π t-1 h (• | τ h ))      , (E.1)where η is some learning rate and L t-1 (π) is a first-order approximation of the expected accumulated rewards at π t-1 :L t-1 (π) := v P (π t-1 ) + E P π t-1   h∈[H] Q t-1 h (τ h , s h , •), π h (• | τ h ) -π t-1 h (• | τ h )   .By plugging L t-1 (π) into Equation (E.1), with simple algebric manipulations, we prove that:π t h (• | τ h ) ∝ π t-1 h (• | τ h ) exp ηE s h ∼b h (τ h ) Q t-1 h (τ h , s h , •) .Proof of Lemma 4.4: The proof follows by the assumption that the total cumulative reward is at most H,v P (π) ≥E P π     h∈[H] r h   1[∀h :∈ [H] : g h (s h-1 , a h-1 , o h ) = s h ]   =E P π E     h∈[H] r h   1[∀h :∈ [H] : g h (s h-1 , a h-1 , o h ) = s h ]   + E P π E     h∈[H] r h   1[∀h :∈ [H] : g h (s h-1 , a h-1 , o h ) ̸ = s h ]   -E P π E     h∈[H] r h   1[∀h :∈ [H] : g h (s h-1 , a h-1 , o h ) ̸ = s h ]   =E P π E     h∈[H] r h     -E P π E     h∈[H] r h   1[∀h :∈ [H] : g h (s h-1 , a h-1 , o h ) ̸ = s h ]   ≥v P (π E ) -HP π E ,P [∃h :∈ [H] : g h (s h-1 , a h-1 , o h ) ̸ = s h ]≥v P (π E ) -Hϵ, which completes the proof. ■Proof of Theorem 4.5: For each step h ∈ [H] we define D h to be the distribution over the underlying state s h-1 at step h -1, taken action a h-1 ∈ A based on π E , the underlying state transitioned to s h ∈ S, and the observationo h ∼ O h (• | s h ).We remind that we include at step zero, a dummy state-observation pair (s 0 , o 0 ). Formally, D h is defined asD h (s h-1 , a h-1 , o h , s h ) := P π E ,P [s h-1 , a h-1 , o h , s h ] .We first use union bound to decompose the probability that we incorrectly decode,P π E ,P [∃h ∈ [H] : g h (s h-1 , a h-1 , o h ) ̸ = s h ] ≤ h∈[H] P π E ,P [g h (s h-1 , a h-1 , o h ) ̸ = s h ] = h∈[H] P (s h-1 ,a h-1 ,o h ,s h )∼D h [g h (s h-1 , a h-1 , o h ) ̸ = s h ] . (F.1)For each h ∈ [H], we can use M episodes to collect M samples from the distribution D h . In addition, since state s H+1 is dummy, we need not to collect episodes for D H+1 . Denote the set of collected samples by D M h . We define the decoding g h for step h ∈ [H] as follows:g h (s h-1 , a h-1 , o h ) = s h | (s h-1 , a h-1 , o h , s h ) ∈ D M h .Observe that by Definition 3.2,{s h | (s h-1 , a h-1 , o h , s h ) ∈ D M h} is either the empty set or contains only a single elements, in which case, it is true that g for each step h ∈ [H], we obtain the following by the result in [13] :h (s h-1 , a h-1 , o h ) = ψ h (s h-1 , a h-1 , o h ) (ψP π E ,P [g h (s h-1 , a h-1 , o h ) ̸ = s h ] =P π E ,P [g h (s h-1 , a h-1 , o h ) = ∅] =P (s h-1 ,a h-1 ,o h ,s h )∼D h (s h-1 , a h-1 , o h , s h ) / ∈ D M h = u∈supp(D h ) P u ′ ∼D h [u = u ′ ]1[u / ∈ supp( D M h )] ≤d T V (D h , D M h ) ≤ϵ.Thus, by union bound, with probability at least 1 -δ, we have that for each step h ∈ [H],P (s h-1 ,a h-1 ,o h ,s h )∼D h [g h (s h-1 , a h-1 , o h ) ̸ = s h ] ≤ ϵ,which in combination with Equation (F.1) concludes the proof. Finally, we note that we used a total of Θ H• |A|•|O|•|S|+log(H/δ) ϵ 2episodes from the POMDP, and the computational time was POLY(H, A, O, S, 1 ϵ , log 1 δ ). ■We now turn our attention to the rich-observation setting under our deterministic filter condition. Definition 3.2 motivates us to consider only succinct policies that incorporate an auxiliary parameter representing the most recent state, as well as the most recent observations and actions. To handle the large observation space, we further assume that for each step h ∈ [H], the agent selects a decoding function g h from a family of multi-class classifiers F h ⊂ {S × A × O → S}. For the function class F h , we make the standard realizability assumption. We formally summarize our assumptions in Assumption G.1. Assumption G.1. We consider a POMDP that satisfies Definition 3.2. In addition, to derive learning algorithms that do not dependent on |O|, for each step h ∈ [H], we assume that we have access to a class of functions F h : S × A × O → S such that the perfect decoding function ψ h ∈ F h .We aim for our final bounds to depend on a complexity measure of the function classF = {F h } h∈[H]rather than the cardinality of the observation space O. We utilize the Daniely and Shalev-Shwartz-Dimension (DS Dimension) (Theorem G.2), which characterizes the PAC learnability for multi-class classification [8] . Defining the DS dimension is beyond the scope of our paper; we direct interested readers to [8] for further details. For intuition, readers can think of the DS Dimension as a certificate of PAC learnability without loss of intuition. Theorem G.2 (Theorem 1 in [8] ). Consider a family of multi-class classifiers F that map features in space x ∈ X to labels in space y ∈ Y. Moreover, assume there is a joint probability distribution D over features in X and labels in Y, and that there exists g * ∈ F such that for each (x, y) ∈ supp(D), g * (x) = y. Given n samples from D, there exists an algorithm that with probability at least 1 -δ outputs g ∈ F such thatP (x,y)∼D [ g(x) ̸ = y] ≤ O d 3/2 DS (F) + log 1 δ n ,where d DS (F) denotes the Daniely and Shalev-Shwartz-Dimension of the function class F.We are now ready to present the main theorem of this section. Theorem G. P π E ,P [∃h ∈ [H] : g h (s h-1 , a h-1 , o h ) ̸ = s h ] ≤ ϵ, using O H 2 max h∈[H] d 3/2 DS (F h )+log( 1 δ )ϵ episodes, where d DS (F h ) is the Daniely and Shalev-Shwartz-Dimension of F h [8] .Combining Theorem G.3 and Lemma 4.4, we obtain the final polynomial sample complexity in this function approximation setting, using classification (supervised learning) oracles (c.f. Table 1 ).Proof of Theorem G.3:For each step h ∈ [H],we define D h to be the distribution over the underlying state s h-1 at step h-1, taken action a h-1 ∈ A from π E , the underlying state transitioned to s h ∈ S, and the hallucinated observation o h ∼ O h (• | s h ) (we remind readers that for step 0, we use dummy state s 0 and action a 0 ). Formally, the probability that the sequence(s h-1 , a h-1 , o h , s h ) is sampled from D h equals to D h (s h-1 , a h-1 , o h , s h ) := P π E ,P [s h-1 , a h-1 , o h , s h ] .We first use union bound to decompose the misclassification error,P π E ,P [∃h ∈ [H] : g h (s h-1 , a h-1 , o h ) ̸ = s h ] ≤ h∈[H] P π E ,P [ g h (s h-1 , a h-1 , o h ) ̸ = s h ] = h∈[H] P (s h-1 ,a h-1 ,o h ,s h )∼D h [ g h (s h-1 , a h-1 , o h ) ̸ = s h ] . (G.1) For each h ∈ [H], we can use O H ϵ • max h∈[H] d 3/2 DS (F h ) + log 1 δ episodes to collect O H ϵ • max h∈[H] d 3/2 DS (F h ) + log 1 δsamples from distribution D h . Hence, by Theorem G.2, with probability at least 1 -δ H , we have thatP (s h-1 ,a h-1 ,o h ,s h )∼D h [ g h (s h-1 , a h-1 , o h ) ̸ = s h ] ≤ ϵ H .Thus, by union bound, with probability at least 1 -δ, using a total ofO H 2 ϵ • max h∈[H] d 3/2 DS (F h ) + log 1 δ episodes we have that, h∈[H] P (s h-1 ,a h-1 ,o h ,s h )∼D h [ g h (s h-1 , a h-1 , o h ) ̸ = s h ] ≤ ϵ,which in combination with Equation (G.1) concludes the proof. ■Proof of Theorem 5.1:Let π * ∈ argmax π∈Π L E s1∼µ1 [V π 1 (s 1 )],where we defineV π 1 (s 1 ) := E o1∼O1(• | s1),a1∼π1(• | o1) [Q π h (z 1 = (o 1 ), s 1 , a 1 )].We first note the following equation1 T t∈[T ] E s1∼µ1 [V π t 1 (s 1 )] =E s1∼µ1 [V π * 1 (s 1 )] + 1 T t∈[T ] E s1∼µ1 V π t 1 (s 1 ) -V π * 1 (s 1 ) 1 T t∈[T ] E s1∼µ1 V π t 1 (s 1 ) -V π t 1 (s 1 ) . (H.1)We make use of the performance difference lemma [38, 1, 73] on the extended space h∈[H] (Z h ×S).Definition H.1. Consider the class of policies Π P L such that at step h ∈ [H], the policies in Π P L take an action based on finite memory up to this step and the use of the underlying state, e.g., for each policy π 1:H ∈ Π P L , π h : Z h × S → ∆(A).Observation 1. Note that Π L ⊆ Π P L . Lemma H.2 (Performance difference Lemma [38, 1, 73] ; see e.g., Lemma 1 in [73] ). For any pair of policiesπ = {π h } h∈[H] , π ′ = {π ′ h } h∈[H] ∈ Π P L, and approximation of the Q-function of policy π, we have that for each state s 1 ∈ supp(µ 1 ):V π 1 (z 1 , s 1 ) -V π ′ 1 (z 1 , s 1 ) = h∈[H] E τ h ∼π ′ |z1 Q π h (z h , s h , •), π h (• | z h , s h ) -π ′ h (• | z h , s h ) + h∈[H] E τ h ∼π ′ |z1 Q π h (z h , s h , a h ) -E s h+1 ∼T h (• | s h ,a h ), o h+1 ∼O h+1 (• | s h+1 ) r h (s h , a h ) + V π h+1 (z h+1 , s h+1 ) , where V π h (z h , s h ) = E a h ∼π h (• | z h ) [ Q π h (z h , s h , a h )].Setting π = π t ∈ Π L ⊆ Π LP , and π ′ = π * ∈ Π L ⊆ Π LP , where we remind that π * ∈ argmax π∈Π L V π 1 (s 1 ), and for each z h ∈ Z h and h ∈ [H], we abuse the notation by lettingπ t h (• | z h , s h ) = π t h (• | z h ) and π * h (• | z h , s h ) = π * h (• | z h ) for all s h ∈ S.The above formulation is thus simplified toE s1∼µ1 [ V π t 1 (s 1 ) -V π * 1 (s 1 )] = h∈[H] E τ h ∼π * Q π t h (z h , s h , •), π t h (• | z h , s h ) -π * h (• | z h , s h ) + h∈[H] E τ h ∼π * Q π h (z h , s h , a h ) -E s h+1 ∼T h (• | s h ,a h ), o h+1 ∼O h+1 (• | s h+1 ) r h (s h , a h ) + V π h+1 (z h+1 , s h+1 ) ≥ h∈[H] E τ h ∼π * Q π t h (z h , s h , •), π t h (• | z h , s h ) -π * h (• | z h , s h ) ,where in the inequality above we used Lemma H.3. Since our policy does not depend on the realized underlying state s h ,E s1∼µ1 [ V π t 1 (s 1 ) -V π * 1 (s 1 )] ≥ h∈[H] E τ h ∼π * Q π t h (z h , s h , •), π t h (• | z h , s h ) -π * h (• | z h , s h ) = h∈[H] E τ h ∼π * E s h ∼b(τ h ) Q π t h (z h , s h , •) , π t h (• | z h ) -π * h (• | z h ) = h∈[H] E τ h ∼π * E s h ∼b apx (z h ) Q π t h (z h , s h , •) , π t h (• | z h ) -π * h (• | z h ) + h∈[H] E τ h ∼π * E s h ∼b(τ h ) Q π t h (z h , s h , •) -E s h ∼b apx (z h ) Q π t h (z h , s h , •) , π t h (• | z h ) -π * h (• | z h ) ≥ h∈[H] E τ h ∼π * E s h ∼b apx (z h ) Q π t h (z h , s h , •) , π t h (• | z h ) -π * h (• | z h ) - h∈[H] E τ h ∼π * E s h ∼b(τ h ) Q π t h (z h , s h , •) -E s h ∼b apx (z h ) Q π t h (z h , s h , •) 1 ≥ h∈[H] E τ h ∼π * E s h ∼b apx (z h ) Q π t h (z h , s h , •) , π t h (• | z h ) -π * h (• | z h ) -2 • H • h∈[H] E τ h ∼π * d T V (b h (τ h ), b apx h (z h )) .The last inequality follows by Lemma H.3. By averaging we get,1 T t∈[T ] E s1∼µ1 [ V π t 1 (s 1 )] ≥E s1∼µ1 [V π * 1 (s 1 )] + 1 T h∈[H] E τ h ∼π *   t∈[T ] E s h ∼b apx (z h ) Q π t h (z h , s h , •) , π t h (• | z h ) -π * h (• | z h )   -2 • H • h∈[H] E τ h ∼π * d T V (b h (τ h ), b apx h (z h )) ≥E s1∼µ1 [V π * 1 (s 1 )] + H T max h∈[H] E τ h ∼π *   t∈[T ] E s h ∼b apx (z h ) Q π t h (z h , s h , •) , π t h (• | z h ) -π * h (• | z h )   -2 • H 2 • max h∈[H] E τ h ∼π * d T V (b h (τ h ), b apx h (z h )) ≥E s1∼µ1 [V π * 1 (s 1 )] - 2H H log (|A|) √ T -2 • H 2 • max h∈[H] E τ h ∼π * d T V (b h (τ h ), b apx h (z h )) ,where the last inequality follows since for fixed h ∈ [H] and z h ∈ Z h , the agent updates her policy on memory z h according to MWU on feedbackE s h ∼b apx (z h ) Q π t h (z h , s h , a)a∈A , and thus, the accumulate regret is bounded by (Section 4.3 in [10] ):t∈[T ] E s h ∼b apx (z h ) Q π t h (z h , s h , •) , π * h (• | z h ) -π t h (• | z h ) ≤ log (|A|) η + η • T • Q π t h (z h , s h , •) +∞ ≤ log (|A|) η + η • T • H =2 T • H log (|A|).The proof follows by combining Equation (H.1) and the inequality above. Finally, to achieve the near optimality in the class of Π L , we bound the optimistic estimate using Equation (H.2) in Lemma H.3, and its global near-optimality for a large enough L under γ-observability is a direct consequence of Theorem 4.1 in [26] . ■ Lemma H.3 (Optimistic Q-function -adapted from [47] ). Given a policy π ∈ Π L , and a parameterM ∈ N, let { Q π h : Z h × S × A → [0, H]} h∈[H]be the output of Algorithm 3. Then, with probability at least 1 -δ:∀z h ∈ Z h , s h ∈ S, a h ∈ A H -h + 1 ≥ Q π h (z h , s h , a h ) ≥ E s h+1 ∼T h (• | s h ,a h ), o h+1 ∼O h+1 (• | s h+1 ) r h (s h , a h ) + V π h+1 (z h+1 , s h+1 ) , E s1∼µ1 [ V π 1 (s 1 )] -E s1∼µ1 [V π 1 (s 1 )] ≤ (H.2) O H 2 • max(|O|, |S|) • |S| • |A| M • log |S| • |A| δ log M • |S| • |A| • H δ , (H.3) where V π 1 (s 1 ) = E o1∼O1(• | s1),a1∼π1(• | o1) [Q π h (z 1 = (o 1 ), s 1 , a 1 )], V π 1 (s 1 ) = E o1∼O1(• | s1),a1∼π1(• | o1) [ Q π h (z 1 = (o 1 ), s 1 , a 1 )] and V π h (z h , s h ) = E a h ∼π h (• | z h ) [ Q π h (z h , s h , a h )]. Moreover, Algorithm 3 needs a total of H • M episodes from POMDP P and runs in time POLY(H, M, S, A L , O L ).Proof. For each step h ∈ [H], collect M trajectories with states using policy π on POMDP P and let D h = {τ (i) } i∈[M ] be those collected trajectories. Define the empirical transition, observation and reward distribution as follows:N h (s h , a h , s h+1 ) = {τ = (s ′ 1 , o ′ 1 , a ′ 1 , r ′ 1 . . . , s ′ h , o ′ h , a ′ h , r ′ h ) ∈ D h : (s h , a h , s h+1 ) = (s ′ h , a ′ h , s ′ h+1 )} , N h (s h , a h ) = s h+1 ∈S N h (s h , a h , s h+1 ), N h (s h ) = a h ∈A N h (s h , a h ), N h (s h , o h ) = {τ = (s ′ 1 , o ′ 1 , a ′ 1 , r ′ 1 . . . , s ′ h , o ′ h , a ′ h , r ′ h ) ∈ D h : (s h , o h ) = (s ′ h , o ′ h )} , T h (s h+1 | s h , a h ) = N h (s h , a h , s h+1 ) N h (s h , a h ) , O h (o h | s h ) = N h (s h , o h ) N h (s h ) . Set δ 1 = δ 2•|S|•(|A|+1). By [13] , there exists a constant C > 0 such that for each step h ∈ [H], state s ∈ S and action a ∈ A with probability at least 1 -δ 1 :∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 ≤ min 2, C • |S| log(1/δ 1 ) max(N h (s h , a h ), 1),∥O h (• | s h ) -O h (• | s h )∥ 1 ≤ min 2, C • |O| log(1/δ 1 ) max(N h (s h ), 1).For the rest of the proof we condition on this event. By union bound, this happen with probability at least 1 -δ 2 . We define the optimistic Q function recursively as follows for a memory-state pair (z h , s h ) ∈ Z h × S:Q π H+1 (z H+1 , s H+1 , •) =0, ∀z H+1 ∈ Z H+1 , s H+1 ∈ S Q π h (z h , s h , a h ) = min H -h + 1, E s h+1 ∼ T h (• | s h ,a h ), o h+1 ∼ O h+1 (• | s h+1 ) [ V π h+1 (z h+1 , s h+1 )] + r(s h , a h ) + H • min 2, C • |S| log(1/δ 1 ) max(N h (s h , a h ), 1) + E s h+1 ∼ T h (• | s h ,a h ) H • min 2, C • |O| log(1/δ 1 ) max(N h+1 (s h+1 ), 1),where V π h+1 (z h+1 , s h+1 ) = E a h+1 ∼π h+1 (• | z h+1 ) [ Q π h+1 (z h+1 , s h+1 , a h+1 )].Hence the time complexity of our algorithm is POLY(H, M, S, A L , O L ). To prove the first condition we fix step h ∈ [H], z h ∈ Z h , a h ∈ A and state s h ∈ S and take condition whether Q π h (z h , s h , a h ) = H -h+1. In this case, since by assumption on the POMDP P, r h (s h , a h ) ≤ 1, and by definition ofQ π h+1 (•, •, •) ≤ H -h, we have: Q π h (z h , s h , a h ) = 1 + H -h ≥ E s h+1 ∼T h (• | s h ,a h ), o h+1 ∼O h+1 (• | s h+1 ) [r h (s h , a h ) + V π h+1 (z h+1 , s h+1 )]. If Q π h (z h , s h , a h ) ̸ = H -h + 1, observe that: Q π h (z h , s h , a h ) =E s h+1 ∼ T h (• | s h ,a h ), o h+1 ∼ O h+1 (• | s h+1 ) [ V π h+1 (z h+1 , s h+1 )] + r(s h , a h ) + H • min 2, C • |S| log(1/δ 1 ) max(N h (s h , a h ), 1) + E s h+1 ∼ T h (• | s h ,a h ) H • min 2, C • |O| log(1/δ 1 ) max(N h+1 (s h+1 ), 1) ≥E s h+1 ∼T h (• | s h ,a h ), o h+1 ∼O h+1 (• | s h+1 ) [r h (s h , a h ) + V π h+1 (z h+1 , s h+1 )],and hence, { Q π h } h∈[H] satisfies the first condition. Moreover, it is true that:Q π h (z h , s h , a h ) ≤E s h+1 ∼T h (• | s h ,a h ), o h+1 ∼O h+1 (• | s h+1 ) [r h (s h , a h ) + V π h+1 (z h+1 , s h+1 )] + 2H • min 2, C • |S| log(1/δ 1 ) max(N h (s h , a h ), 1) + 2 • E s h+1 ∼ T h (• | s h ,a h ) H • min 2, C • |O| log(1/δ 1 ) max(N h+1 (s h+1 ), 1) ≤E s h+1 ∼T h (• | s h ,a h ), o h+1 ∼O h+1 (• | s h+1 ) [r h (s h , a h ) + V π h+1 (z h+1 , s h+1 )] + 6H • min 2, C • |S| log(1/δ 1 ) max(N h (s h , a h ), 1) + 2 • E s h+1 ∼T h (• | s h ,a h ) H • min 2, C • |O| log(1/δ 1 ) max(N h+1 (s h+1 ), 1).Thus, it holds that:V π h (z h , s h ) -V π h (z h , s h ) ≤E a h ∼π h (• | z h ), s h+1 ∼T h (• | s h ,a h ), o h+1 ∼O h+1 (• | s h+1 ) [ V π h+1 (z h+1 , s h+1 ) -V π h+1 (z h+1 , s h+1 )] + 6 • C • H • E a h ∼π h (• | z h ) |S| log(1/δ 1 ) max(N h (s h , a h ), 1) + 2 • C • H • E a h ∼π h (• | z h ), s h+1 ∼T h (• | s h ,a h ) |O| log(1/δ 1 ) max(N h+1 (s h+1 ), 1).Thus, we conclude thatE s1∼µ1 [ V π 1 (s 1 )] -E s1∼µ1 [V π 1 (s 1 )] ≤ E τ =(s1,a1,...,s H+1 )∼π   h∈[H] 8 • H • C • max(|S|, |O|) log(1/δ 1 ) max(N h (s h , a h ), 1)   = 8 • H max(|O|, |S|) • log(1/δ 1 ) • C • h∈[H]E τ =(s1,a1,...,s H+1 )∼π1 max(N h (s h , a h ), 1).To finish the proof, we make use of the following lemma.Lemma H.4 (Lemma 6 in [47] ). For each step h ∈ [H], and state-action pair (s h , a h ) ∈ S × A, with probability at least 1 -δ 2 :1 max(N h (s h , a h ), 1) = O |S| • |A| log(M/δ 2 ) M .By settingδ 2 = δ 2•|S|•|A|•H, and taking union bound we have that with probability at least 1 -δ:E s1∼µ1 [ V π 1 (s 1 )] -E s1∼µ1 [V π 1 (s 1 )] = 8 max(|O|, |S|) • log(1/δ 1 ) • C • h∈[H] E τ =(s1,a1,...,s H+1 )∼π 1 max(N h (s h , a h ), 1) ≤ O H 2 • max(|O|, |S|) • |S| • |A| M • log |S| • |A| δ log M • |S| • |A| • H δ .Proof of Theorem 5.2: The proof of Theorem 5.2 follows by combining Theorem H.5 and Theorem H.6 below. Theorem H.5 proves that we can approximately learn a POMDP model P computationally and sample efficiently, thanks to the privileged information.Theorem H.5. Fix any ϵ, δ ∈ (0, 1). Algorithm 4 can learn the approximate POMDP model with transition T 1:H and emission O 1:H such that with probability at least 1 -δ, for any policy π ∈ Π gen and h ∈ [H]E P π ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1 ≤ O(ϵ), using POLY(S, A, H, O, 1 ϵ , log( 1 δ )) episodes in time POLY(S, A, H, O, 1 ϵ , log( 1 δ )).Proof. Note that by Lemma H.10, it suffices to consider only π ∈ Π S as the optimal value for policies in Π gen can be achieved by those in Π S (by consideringr h (s h , a h ) := 2H -(∥T h (• | s h , a h ) - T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1 )).For each h ∈ [H] and s h ∈ S, we definep h (s h ) = max π∈Π S d π h (s h ). Fix ϵ 1 > 0, we define U(h, ϵ 1 ) = {s h ∈ S | p h (s h ) ≥ ϵ 1 }.By the guarantee of the EULER algorithm from [88, 36] , one can learn a policy Ψ(h, s h ) with sample complexity O( S2 AH 4) such that dΨ(h,s h ) h (s h ) ≥ p h (s h ) 2for each s h ∈ U(h, ϵ 1 ) with probability 1 -δ 1 . Now we assume this event holds for any h ∈ [H] and s h ∈ U(h, ϵ 1 ). For each s h ∈ S and a h ∈ A, we have executed in Algorithm 4 the policy Ψ(h, s h ) followed by an action a h ∈ A for N episodes, and denote the number of episodes that s h and a h are visited as N h (s h , a h ). Then with probability 1 -e N ϵ1/8 , N h (s h , a h ) ≥ N p h (s h ) the following: for any π ∈ Π S 1 2• E P π ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 = 1 2 s h ,a h d π h (s h )π h (a h | s h )∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 ≤ Sϵ 1 + 1 2 s h ∈U (h,ϵ1),a h d π h (s h )π h (a h | s h ) S log(1/δ 2 ) N p h (s h ) ≤ Sϵ 1 + s h ∈U (h,ϵ1),a h d Ψ(h,s h ) h (s h )π h (a h | s h ) S log(1/δ 2 ) N p h (s h ) ≤ Sϵ 1 + s h d Ψ(h,s h ) h (s h ) S log(1/δ 2 ) N ≤ Sϵ 1 + S log(1/δ 2 ) N ,where the first inequality follows by [13] with probability at least 1 -δ 2 , and the second inequality uses dΨ(h,s h ) h (s h ) ≥ p h (s h ) 2for all s h ∈ U(h, ϵ 1 ). Similarly, for any π ∈ Π S 1 2• E P π ∥O h (• | s h ) -O h (• | s h )∥ 1 ≤ Sϵ 1 + 1 2 s h ∈U (h,ϵ1) d π h (s h ) O log(1/δ 2 ) N p h (s h ) ≤ Sϵ 1 + s h ∈U (h,ϵ1) d Ψ(h,s h ) h (s h ) O log(1/δ 2 ) N p h (s h ) ≤ Sϵ 1 + s h ∈U (h,ϵ1) d Ψ(h,s h ) h (s h ) O log(1/δ 2 ) N ≤ Sϵ 1 + SO log(1/δ 2 ) N ,where similarly the first inequality follows by [13] with probability at least 1 -δ 2 , and the second inequality uses dΨ(h,s h ) h (s h ) ≥ p h (s h ) 2for all s h ∈ U(h, ϵ 1 ). Therefore, by a union bound, all the high probability events above hold with probability1 -SHδ 1 -SHAe N ϵ1/8 -2SAHδ 2 .Therefore, we can choose N = Θ( S 2 +SO ϵ 2) and ϵ 1 = Θ( ϵ S ), leading to the total sample complexitySHA(N + O( S 3 AH 4 ϵ )) = O( S 2 AHO + S 3 AH ϵ 2 + S 4 A 2 H 5 ϵ ), (H.4)which completes the proof.Now with such a learned model in a reward-free way, we are ready to present our main result for approximate belief learning.Theorem H.6. Consider a γ-observable POMDP P (c.f. Assumption 2.2), an ϵ > 0 and let P be the outcome of Algorithm 4 such that for any π ∈ Π gen :E P π ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1 ≤ O ϵ 3 • H .Then we can construct in time POLY(H, A, S, O, 1 ϵ , log 1 δ ) a belief {b apx h : Z h → ∆(S)} h∈[H] with no further samples. In addition, if the parameter in Algorithm 4 satisfies N = Θ( O log(SH/δ)γ 2 ϵ1) and our class of finite memory policies Π L satisfies L ≥ Ω(γ -4 log(S/ϵ), then for any π ∈ Π gen and h ∈ [H]:E P π ∥b h (τ h ) -b apx h (z h )∥ 1 ≤ O(ϵ).Proof. We firstly consider the following simple while important fact: for the estimated emission O h , its observability can be evaluated as∥ O ⊤ h (b -b ′ )∥ 1 ≥ ∥O ⊤ h (b -b ′ )∥ 1 -∥(O ⊤ h -O ⊤ h )(b -b ′ )∥ 1 ≥ (γ -∥ O h -O h ∥ ∞ )∥b -b ′ ∥ 1 , for any b, b ′ ∈ ∆(S) and ∥ O h -O h ∥ ∞ := max s h ∈S ∥O h (• | s h ) -O h (• | s h )∥ 1 .Therefore, if one can ensure that the emission at any state s h is learned accurately in the sense that∥O h (• | s h ) - O h (• | s h )∥ 1 ≤ γ 2 ,we can conclude that O h is also γ/2-observable. However, the key challenge here is that there could exist some states s h at step h that can only be visited with a low probability no matter what exploration policy is used. Therefore, emissions at such states may not be learned accurately. To address this issue, our key technique here is to redirect the transition probability into states that cannot be explored sufficiently to some highly visited states, in a new POMDP that is close to the original one in some sense. Specifically, first, for any ϵ 1 > 0, we defineS low h := s h ∈ S N h (s h ) N < ϵ 1 2 , S high h := S \ S low h .By Chernoff bound, with probability at least 1 -Se -N ϵ1/8 , it holds thatS low h ⊆ {s h ∈ S | p h (s h ) < ϵ 1 }, where p h (s h ) := max π∈Π S d π h (s h ).To see the reason, we notice that for any s h such that p h (s h ) ≥ ϵ 1 , with probability 1 -e -N ϵ1/8 , it holds that N h (s h ) N ≥ ϵ12 . Therefore, the last step is by taking a union bound for all s h . Now with S low h defined, we are ready to construct a truncated POMDP P trunc such that for each h ∈ [H], we define the transition asT trunc h (s h+1 | s h , a h ) := T h (s h+1 | s h , a h ) + s ′ h+1 ∈S low h+1 T h (s ′ h+1 | s h , a h ) |S high h+1 |, ∀s h ∈ S, s h+1 ∈ S high h+1 , a h ∈ A,T trunc h (s h+1 | s h , a h ) := 0, ∀s h ∈ S, s h+1 ∈ S low h+1 , a h ∈ A.Meanwhile, for the initial state distribution, we defineµ trunc 1 (s 1 ) := µ 1 (s 1 ) + s ′ 1 ∈S low 1 µ 1 (s ′ 1 ) |S high 1 | , ∀s 1 ∈ S high 1 , µ trunc 1 (s 1 ) := 0, ∀s 1 ∈ S low 1 .O trunc h (o h | s h ) := O h (o h | s h ), ∀h ∈ [H], s h ∈ S, o h ∈ O h .Finally, we define the rewards for P trunc arbitrarily. Now we examine the total variation distance between the trajectory distributions in P and P trunc . For any policy π ∈ Π gen , it is easy to see that P π,P (τ h ) ≤ P π,P trunc (τ h ),for any τ h ∈ T high h := {(s 1:h , o 1:h , a 1:h-1 ) | s ′ h ∈ S high h ′ , ∀h ′ ∈ [h]}, since some rarely visited states' probability has been redirected to the highly visited ones in P trunc . Meanwhile, it holds by a union bound that for any h ∈ [H]P π,P (τ h ̸ ∈ T high h ) ≤ h ′ ∈[h] P π,P (s h ′ ∈ S low h ′ ) ≤ HSϵ 1 .Therefore, by noticing that P π,P trunc (τ h ) = 0 for any τ h ̸ ∈ T high h and h ∈ [H], the total variation distance between the trajectory distributions in P and P trunc can be bounded byτ h |P π,P (τ h ) -P π,P trunc (τ h )| ≤ 2HSϵ 1 . (H.5)On the other hand, by Equation (H.10) of Lemma H.9, we haveE P π [∥b h (τ h ) -b trunc h (τ h )∥ 1 ] ≤ 2 τ h |P π,P (τ h ) -P π,P trunc (τ h )| ≤ 4HSϵ 1 . (H.6)With such an intermediate quantity P trunc , we define the transition of its approximate version P trunc as follows: we define the transition asT trunc h (s h+1 | s h , a h ) := T h (s h+1 | s h , a h ) + s ′ h+1 ∈S low h+1 T h (s ′ h+1 | s h , a h ) |S high h+1 | , ∀s h ∈ S, s h+1 ∈ S high h+1 , a h ∈ A, T trunc h (s h+1 | s h , a h ) := 0, ∀s h ∈ S, s h+1 ∈ S low h+1 , a h ∈ A.Meanwhile, for the initial state distribution, we define µ trunc 1 (s 1 ) := µ 1 (s 1 ) + s ′ 1 ∈S low 1 µ 1 (s ′ 1 ) |S high 1 | , ∀s 1 ∈ S high 1 , µ trunc 1 (s 1 ) := 0, ∀s 1 ∈ S low 1 .O trunc h (o h | s h ) := O h (o h | s h ), ∀h ∈ [H], s h ∈ S, o h ∈ O h .∥ O sub h -O sub h ∥ ∞ = max s h ∈S high h ∥O h (• | s h ) -O h (• | s h )∥ 1 ≤ max s h ∈S high h O log(SH/δ) N h (s h ) ≤ max s h ∈S high h 2O log(SH/δ) N ϵ 1 ,where the first inequality is by Lemma J.9, and the second inequality is by the definition of S high h . Therefore, if we takeN ≥ 8O log(SH/δ) γ 2 ϵ 1 , it is guaranteed that ∥ O sub h -O sub h ∥ ∞ ≤ γ 2 .Therefore, we conclude that O sub h is also γ/2-observable.Now we are ready to examine b ′,trunc h . We firstly define the following POMDP P sub , which essentially deletes all states in S low h from the state space of P trunc at each step h, which does not affect the trajectory distribution as they were not reachable in P trunc . Notice that the emission of P sub is exactly O sub h , implying that P sub is a γ/2-observable POMDP. Therefore, for policy class with finite memory Π L with L ≥ Ω(γ -4 log(S/ϵ), by Theorem 4.1 in [25] , it is guaranteed that for any π ∈ Π,E P sub π ∥ b sub h (τ h ) -b ′,sub h (z h )∥ 1 ≤ ϵ, where b sub h (τ h ), b ′,sub h (z h ) ∈ ∆(S high h ). Now we claim thatE P trunc π ∥ b trunc h (τ h ) -b apx h (z h )∥ 1 ≤ ϵ, (H.7)where we define b apx h (z h ) ∈ ∆(S) by augmenting b ′,sub h (z h ) with 0 for states from S low h . To see the reason, we notice that simulating P trunc is exactly equivalent to simulating P sub , and thatb trunc h (τ h )(s h ) = 0 for s h ∈ S low h , b trunc h (τ h )(s h ) = b sub h (τ h )(s h ) for s h ∈ S high h .For the total variation distance between the trajectory distributions in P trunc and P trunc , it holds that by Lemma H.9τ H |P π,P trunc (τ H ) -P π, P trunc (τ H )| ≤ E P trunc π h∈[H] ∥T trunc h (• | s h , a h ) -T trunc h (• | s h , a h )∥ 1 + ∥O trunc h (• | s h ) -O trunc h (• | s h )∥ 1 ≤ h∈[H] E P trunc π ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1 ,where the last step is by Lemma H.7.h E P trunc π ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1 = h 4HSϵ 1 + E P π ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1 ≤ ϵ 3 + 4H 2 Sϵ 1 ,where the last step is by Theorem H.5. Hence, by Lemma H.9, it holds thatEQUATIONE P trunc π ∥b trunc h (τ h ) -b trunc h (τ h )∥ 1 ≤ 2ϵ 3 + 8H 2 Sϵ 1 . (H.9)Finally, we are ready to proveE P π ∥b h (τ h ) -b apx h (z h )∥ 1 ≤ E P π ∥b h (τ h ) -b trunc h (τ h )∥ 1 + E P π ∥b trunc h (τ h ) -b trunc h (τ h )∥ 1 + E P π ∥ b trunc h (τ h ) -b apx h (z h )∥ 1 ≤ E P π ∥b h (τ h ) -b trunc h (τ h )∥ 1 + E P trunc π ∥b trunc h (τ h ) -b trunc h (τ h )∥ 1 + E P trunc π ∥ b trunc h (τ h ) -b apx h (z h )∥ 1 + 4∥P π,P -P π,P trunc ∥ 1 + 2∥P π,P trunc -P π, P trunc ∥ 1 ≤ O(H 2 Sϵ 1 ) + O(ϵ).Therefore, by setting ϵ 1 = Θ ϵ H 2 S , we prove our lemma. Observe that our algorithm needed no further samples. The computational complexity follows by computing belief b apx h on POMDP P sub using finite-memory policies of size Θ(γ -4 log(S/ϵ)). For the final sample complexity, we only need to ensure N = Θ( O log(SH/δ)γ 2 ϵ1) in Equation (H.4), thus concluding our proof.We conclude the proof of Theorem 5.2 by combining Theorem H.5 and Theorem H.6. ■In the following, we provide some technical lemmas and their proofs.Lemma H.7. Fix n > 0 and an index set S ⊆ [n]. For two sequences x 1:n and y 1:n such that x i , y i ∈ [0, 1] for i ∈ [n] and i x i = 1, i y i = 1, we definex i = x i + j∈S x j n -|S| , ∀i ̸ ∈ S, x i = 0, ∀i ∈ S.We define y 1:n similarly. Then, it holds thati |x i -y i | ≥ i | x i -y i |. Proof. Note that i | x i -y i | = i̸ ∈S | x i -y i | = i̸ ∈S x i + j∈S x j n -|S| -y i - j∈S y j n -|S| ≤ (n -|S|) j∈S x j n -|S| - j∈S y j n -|S| + i̸ ∈S |x i -y i | ≤ i |x i -y i |,which completes the proof.Lemma H.8. Fix two finite sets X , Y and two joint distributionsP 1 , P 2 ∈ ∆(X × Y). It holds that -E P1(x) y |P 1 (y | x) -P 2 (y | x)| ≤ x,y |P 1 (x, y) -P 2 (x, y)| - x |P 1 (x) -P 2 (x)| ≤ E P1(x) y |P 1 (y | x) -P 2 (y | x)|.Proof. For the second inequality, it holds thatx,y|P 1 (x, y) -P 2 (x, y)| = x,y |P 1 (x, y) -P 1 (x)P 2 (y | x) + P 1 (x)P 2 (y | x) -P 2 (x, y)| ≤ x,y |P 1 (x, y) -P 1 (x)P 2 (y | x)| + |P 1 (x)P 2 (y | x) -P 2 (x, y)| = x,y |P 1 (x)(P 1 (y | x) -P 2 (y | x))| + |P 2 (y | x)(P 1 (x) -P 2 (x))| = E P1(x) y |P 1 (y | x) -P 2 (y | x)| + x |P 1 (x) -P 2 (x)|.Meanwhile, for the first inequality, it holds thatx,y|P 1 (x, y) -P 2 (x, y)| = x,y |P 1 (x, y) -P 1 (x)P 2 (y | x) + P 1 (x)P 2 (y | x) -P 2 (x, y)| ≥ x,y -|P 1 (x, y) -P 1 (x)P 2 (y | x)| + |P 1 (x)P 2 (y | x) -P 2 (x, y)| = x,y -|P 1 (x)(P 1 (y | x) -P 2 (y | x))| + |P 2 (y | x)(P 1 (x) -P 2 (x))| = E P1(x) - y |P 1 (y | x) -P 2 (y | x)| + x |P 1 (x) -P 2 (x)|,concluding our lemma.Lemma H.9. Consider any two POMDP instances P and P and define the belief functions as b 1:H and b 1:H , respectively (see Appendix C for the definition of belief function b 1:H ). It holds that for any π ∈ Π gen P π,P -P π, P 1 =τ H |P π,P (τ H ) -P π, P (τ H )| ≤ E P π h∈[H-1] ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + E P π h∈[H] ∥O h (• | s h ) -O h (• | s h )∥ 1 , E P π ∥b H (τ H ) -b H (τ H )∥ 1 ≤ 2E P π h∈[H-1] ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + 2E P π h∈[H] ∥O h (• | s h ) -O h (• | s h )∥ 1 ,where we remind readers that we denote by τ H = (s 1:H , o 1:H , a 1:H-1 ) the trajectory with states from an episode of the POMDP, and without loss of generality, we assume T H = T H for notational convenience, since one can assume the episode ends deterministically at a state s H+1 .Proof. The first inequality also appears in [43] and we provide a simplified proof here for completeness. By Lemma H.8, it holds thatτ H |P π,P (τ H ) -P π, P (τ H )| ≤ τ H-1 |P π,P (τ H-1 ) -P π, P (τ H-1 )| + E P π a H-1 ,s H ,o H π H-1 (a h-1 | τ H-1 )T H-1 (s H | s H-1 , a H-1 )O H (o H | s H ) -π H-1 (a h-1 | τ H-1 ) T H-1 (s H | s H-1 , a H-1 ) O H (o H | s H ) ≤ τ H-1 |P π,P (τ H-1 ) -P π, P (τ H-1 )| + E P π ∥T H-1 (• | s H-1 , a H-1 ) -T H-1 (• | s H-1 , a H-1 )∥ 1 + ∥O H (• | s H ) -O H (• | s H )∥ 1 ,where the last step is again from Lemma H.8. Therefore, by rolling out the inequality repeatedly, we proved the first result.For the second result, we notice that by Lemma H.8, it holds thatτ h ,s h |P π,P h (τ h , s h ) -P π, P h (τ h , s h )| ≥ - τ h |P π,P h (τ h ) -P π, P h (τ h )| + E P π s h |P π,P h (s h | τ h ) -P π, P h (s h | τ h )|.Notice the fact that P π,P h (s h | τ h ) does not depend on π since it is exactly b h (τ h )(s h ), we conclude thatE P π ∥b h (τ h ) -b h (τ h )∥ 1 ≤ τ h ,s h |P π,P h (τ h , s h ) -P π, P h (τ h , s h )| + τ h |P π,P h (τ h ) -P π, P h (τ h )| ≤2 τ H |P π,P (τ h ) -P π, P (τ h )|, (H.10)where the last step comes from the fact that after marginalization, the total variation distance will not increase. By combining it with the first result, we proved the second result.Lemma H.10. For any reward function r Proof. Denote π ⋆ ∈ Π S to be the optimal policy obtained by running value iteration only on the state space S for P. Now we are ready to prove the following argument for any π ∈ Π gen inductively:Q π ⋆ ,P h (s h , a h ) ≥ Q π,P h (s 1:h , o 1:h , a 1:h ).It is easy to see the argument holds for h = H. Fix state-action pair (s h , a h ) ∈ S × A and trajectory (s 1:h-1 , o 1:h , a 1:h-1 ), we note that:Q π ⋆ ,P h (s h , a h ) = r h (s h , a h ) + E s h+1 ∼T h (• | s h ,a h ) max a h+1 Q π ⋆ ,P h+1 (s h+1 , a h+1 ) ≥ r h (s h , a h ) + E s h+1 ∼T h (• | s h ,a h ), o h+1 ∼O h+1 (•|s h+1 ) max a h+1 Q π,P h+1 (s 1:h+1 , o 1:h+1 , a 1:h+1 ) ≥ r h (s h , a h ) + E s h+1 ∼T h (• | s h ,a h ), o h+1 ∼O h+1 (•|s h+1 ) E a h+1 ∼π h+1 (• | s 1:h+1 ,o 1:h+1 ,a 1:h ) Q π,P h+1 (s 1:h+1 , o 1:h+1 , a 1:h+1 ) = Q π,P h (s 1:h , o 1:h , a 1:h ),where the first inequality comes from the inductive hypothesis.POMDP under deterministic filter condition. We first evaluate our algorithms on POMDPs with certain structures, i.e., the deterministic conditions. In particular, we generate POMDPs, where either the transition dynamics are deterministic or the emission ensures decodability. We test three of our approaches, expert policy distillation, asymmetric optimistic natural policy gradient. We summarize our results in Table 2 , where the four cases corresponds to POMDPs with(S = A = 2, O = 3, H = 5), (S = A = 2, O = 3, H = 10), (S = 3, A = 2, O = 4, H = 5), (S = 3, A = 2, O = 4, H = 5),and we can see that our approach based on expert distillation outperforms all the other methods, which is consistent with the fact that such methods have exploited the special structures of the POMDPs achieving both polynomial sample and computational complexity.General POMDPs. Here we also evaluate our methods for general randomly generated POMDPs without any structures. Hence, we compare the baselines with asymmetric optimistic natural policy gradient and asymmetric optimistic value iteration (i.e., the single-agent version of Algorithm 5). In Figure 2 Implementation details. For each problem setting, we generated 20 POMDPs randomly and report the average performance and its standard deviation for each algorithms. For our algorithms based on privileged value learning methods, we find that using a finite memory of 3 already provides strong performance. For our algorithms based privileged policy learning, we instantiate the MDP learning algorithm with the fully observable optimistic natural policy gradient algorithm [73] . Meanwhile, for both the decoder learning and belief learning, we find that just utilizing all the historic trajectories gives us reasonable performance without additional samples. For baselines, the hyperparameters α for Q-value update and step size for the policy update are tuned by grid search, where α controls the update of temporal difference learning (recall the update rule of temporal difference learning as Q ← (1 -α)Q + αQ target ). For asymmetric Q-learning, we use ϵ-greedy exploration, where we use the seminal decreasing rate ϵ t = H+1 H+t . Finally, all simulations are conducted on a personal laptop with Apple M1 CPU and 16 GB memory.Empirical insights and interpretation of the experimental results. To understand intuitively why our approach outperforms those baseline algorithms, we notice the key difference in the value and policy update style between our approaches and vanilla asymmetric actor critic and asymmetric Q-learning. The baselines often roll-out the polices, collect trajectories, and only update the value and the policies on the states/history the trajectories have visited. Therefore, ideally, to learn a good policy for baselines, the number of trajectories to collect is at least as large as the history size, which is indeed exponential in the horizon H. This is known as curse of history for partially observable RL. In contrast, in our algorithms, we explicitly estimate the empirical transition and emissions, which is indeed of polynomial size. Thus, the sample complexity avoids suffering from the potential exponential dependency of horizon or the length of the finite memory. Finally, we acknowledge that the baselines are developed to handle complex, high-dimensional deep RL problems, while scaling our methods to deep RL benchmarks requires non-trivial engineering efforts.Proof of Proposition 7.1:Given the condition of Definition 3.2, the function ϕ h that satisfies the condition of Proposition 7.1 can be constructed recursively as follows for any reachable τ hϕ h (τ h ) := ψ h (ϕ h-1 (τ h-1 ), a h-1 , o h ), ∀τ h ∈ T h-1 ,and ϕ 1 (o 1 ) := ψ 1 (o 1 ). Therefore, we can prove by induction that by belief update ruleP P (s h | τ h ) = U h (b ϕ h-1 (τ h-1 ) ; a h-1 , o h ) = b ψ h (ϕ h-1 (τ h-1 ),a h-1 ,o h ) ,where the last step is by the definition of our ϕ h . Therefore, we haveP P (s h = ψ h (ϕ h-1 (τ h-1 ), a h-1 , o h ) | τ h ) = 1.For the other direction, it is similar to the proof of Lemma C.1 in [19] for m-step decodable POMDP. Here we prove it for completeness. For any reachable trajectory τ h ∈ T h , it holds by the belief update and induction thatP P (s h | τ h ) = U h (b ϕ h-1 (τ h-1 ) , a h-1 , o h ) = P P (s h | s h-1 = ϕ h-1 (τ h-1 ), a h-1 , o h ).Meanwhile, since we know P P (• | τ h ) is a one-hot vector, we can construct ψ h such thatψ h (s h-1 , a h-1 , o h ) is the unique s h that makes P P (s h | τ h ) > 0 with s h-1 = ϕ h-1 (τ h-1). If this procedure does not complete the definition of ψ for some (s h-1 , a h-1 , o h ), it implies that either s h-1 is not reachable or o h is not reachable given s h-1 , i.e., P P (o h | s h-1 , a ′ h-1 ) = 0 for any a ′ h-1 ∈ A,P (mi⋄πi)⊙π-i,G (s h ̸ = g j,h (c h , p j,h ))where π g is the distilled policy of π through the decoding functions g, where at step h, each agent i firstly individually decodes the state by sampling s h ∼ g i,h (• | c h , p i,h ), and then act according to the expert π i,h . In other words, the decoding process does not need correlations among the agents.Proof. For notational simplicity, we write v i instead of v G i when the underlying model is clear in the context. Firstly, we consider any deterministic decoding functionϕ = { ϕ i,h } i∈[n],h∈[H] with ϕ i,h : C h × P i,h → S for each i ∈ [n], h ∈ [H],and note the following that for any i ∈[n], vi(π) -vi(π ϕ ) = E G π [R] -E G π ϕ [R] = E G π [R1[∀j ∈ [n], h ∈ [H] : s h = ϕ j,h (c h , p j,h )]] -E G π ϕ [R1[∀j ∈ [n], h ∈ [H] : s h = ϕ j,h (c h , p j,h )]] + E G π [R1[∃j ∈ [n], h ∈ [H] : s h ̸ = ϕ j,h (c h , p j,h )]] -E G π ϕ [R1[∃j ∈ [n], h ∈ [H] : s h ̸ = ϕ j,h (c h , p j,h )]] = E G π [R1[∃j ∈ [n], h ∈ [H] : s h ̸ = ϕ j,h (c h , p j,h )]] -E G π ϕ [R1[∃j ∈ [n], h ∈ [H] : s h ̸ = ϕ j,h (c h , p j,h )]],where we define R := h r i,h (s h , a h ) and the last step is by the definition of π ϕ . Therefore, we conclude thatv i (π) -v i (π ϕ ) ≤ HP π,G (∃j ∈ [n], h ∈ [H] : s h ̸ = ϕ j,h (c h , p j,h )).Therefore, by noting the fact that g is equivalent to a mixture of deterministic decoding functions, where at the beginning of each episode, one can firstly independently sample the outcome for each c h , p j,h for j ∈ [n] and h ∈ [H], we conclude thatv i (π) -v i (π g ) = v i (π) -E ϕ∼ g v i (π ϕ ) ≤ HE ϕ∼ g P π,G (∃j ∈ [n], h ∈ [H] : s h ̸ = ϕ j,h (c h , p j,h )) = HP π,G (∃j ∈ [n], h ∈ [H] : s h ̸ = g j,h (c h , p j,h )).Now we prove our result for NE and CCE first. Due to similar arguments for evaluating v i (π)-v i (π ϕ ), for any u i ∈ Π i ∪ Π S,i , it holds thatv i (u i × π ϕ -i ) -v i (u i × π -i ) ≤ E G ui×π ϕ -i [R1[∃j ∈ [n] \ {i}, h ∈ [H] : s h ̸ = ϕ j,h (c h , p j,h )]] ≤ HP ui×π ϕ -i ,G (∃j ∈ [n] \ {i}, h ∈ [H] : s h ̸ = ϕ j,h (c h , p j,h)). We notice the following fact thatP ui×π-i,G (∀j ∈ [n] \ {i}, h ∈ [H] : s h = ϕ j,h (c h , p j,h )) = τH ∈T H ( ϕ) P ui×π-i,G (τ H ),where we define T H ( ϕ):= {τ H ∈ T H | ∀j ∈ [n] \ {i}, h ∈ [H] : s h = ϕ j,h (c h , p j,h )}. By definition of π ϕ , it holds that ∀τ H ∈ T H ( ϕ) : P ui×π-i,G (τ H ) = P ui×π ϕ -i ,G (τ H). Therefore, we haveP ui×π-i,G (∀j ∈ [n] \ {i}, h ∈ [H] : s h = ϕ j,h (c h , p j,h )) = P ui×π ϕ -i ,G (∀j ∈ [n] \ {i}, h ∈ [H] : s h = ϕ j,h (c h , p j,h )). conclude that CE-gap(π g ) -CE-gap(π) ≤ max i∈[n] max mi∈Mi v i ((m i ⋄ π g i ) ⊙ π g -i ) -max mi∈Mi v i ((m i ⋄ π i ) ⊙ π -i ) + HP π,G (∃j ∈ [n], h ∈ [H] : s h ̸ = g j,h (c h , p j,h )) ≤ max i∈[n] max mi∈Mi v i ((m i ⋄ π g i ) ⊙ π g -i ) -v i ((m i ⋄ π i ) ⊙ π -i ) + HP π,G (∃j ∈ [n], h ∈ [H] : s h ̸ = g j,h (c h , p j,h )) ≤ max i∈[n] max mi∈Mi HP (mi⋄πi)⊙π-i,G (∃j ∈ [n] \ {i}, h ∈ [H] : s h ̸ = ϕ j,h (c h , p j,h )) + HP π,G (∃j ∈ [n], h ∈ [H] : s h ̸ = ϕ j,h (c h , p j,h )) ≤ 2H max i∈[n],mi∈Mi j∈[n] h P (mi⋄πi)⊙π-i,G (s h ̸ = ϕ j,h (c h , p j,h )) ≤ 2nH 2 max i∈[n],mi∈Mi,h∈[H],j∈[n] P (mi⋄πi)⊙π-i,G (s h ̸ = ϕ j,h (c h , p j,h ))where the third step is due to the same reason as Equation (J.1).Lemma J.2. For any π ∈ Π S , it holds that for any i ∈ [n] that maxmi∈M gen i v i ((m i ⋄ π i ) ⊙ π -i ) = max mi∈M S,i v i ((m i ⋄ π i ) ⊙ π -i ). Proof. Denote m ⋆ i ∈ argmax mi∈M gen i v i ((m i ⋄ π i ) ⊙ π -i ) and m ⋆ i ∈ argmax mi∈M S,i v i ((m i ⋄ π i ) ⊙ π -i ). Now we shall prove that V (m ⋆ i ⋄πi)⊙π-i,G i,h (s 1:h , o 1:h , a 1:h-1 ) ≤ V ( m ⋆ i ⋄πi)⊙π-i,G i,h (s h ) inductively for each h ∈ [H].Note that it holds for h = H + 1. Now we consider the followingV (m ⋆ i ⋄πi)⊙π-i,G i,h (s 1:h , o 1:h , a 1:h-1 ) = E a h ∼π h (• | s h ) s h+1 ∼T h (• | s h ,m ⋆ i,h (s 1:h ,o 1:h ,a 1:h-1 ,a i,h ),a -i,h ) o h+1 ∼O h+1 (• | s h+1 ) r h (s h , m ⋆ i,h (s 1:h , o 1:h , a 1:h-1 , a i,h ), a -i,h ) + V (m ⋆ i ⋄πi)⊙π-i,G i,h+1 (s 1:h+1 , o 1:h+1 , a 1:h-1 , m ⋆ i,h (s 1:h , o 1:h , a 1:h-1 , a i,h ), a -i,h ) ≤ E a h ∼π h (• | s h ) s h+1 ∼T h (• | s h ,m ⋆ i,h (s 1:h ,o 1:h ,a 1:h-1 ,a i,h ),a -i,h ) o h+1 ∼O h+1 (• | s h+1 ) r h (s h , m ⋆ i,h (s 1:h , o 1:h , a 1:h-1 , a i,h ), a -i,h ) + V ( m ⋆ i ⋄πi)⊙π-i,G i,h+1 (s h+1 ) ≤ E a h ∼π h (• | s h ) s h+1 ∼T h (• | s h , m ⋆ i,h (s h ,a i,h ),a -i,h ) o h+1 ∼O h+1 (• | s h+1 ) r h (s h , m ⋆ i,h (s h , a i,h ), a -i,h ) + V ( m ⋆ i ⋄πi)⊙π-i,G i,h+1 (s h+1 ) = V ( m ⋆ i ⋄πi)⊙π-i,G i,h (s h ),where the second inequality follows from the inductive hypothesis and the third step is by the definition ofm ⋆ i ∈ argmax mi∈M S,i v i ((m i ⋄ π i ) ⊙ π -i ).Lemma J. P ui×π-i,G (s h ̸ = g j,h (c h , p j,h )) ≤ max i∈[n],ui∈Π S,i E G ui×π-i [ h∈[H] ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1 ],andmax i∈[n],mi∈Mi,j∈[n],h∈[H] P (mi⋄πi)⊙π-i,G (s h ̸ = g j,h (c h , p j,h )) ≤ max i∈[n],mi∈M S,i E G (mi⋄πi)⊙π-i [ h∈[H] ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1 ]. Proof. Note for any i ∈ [n], u i ∈ Π i , j ∈ [n], h ∈ [H], it holds P ui×π-i,G (s h ̸ = g j,h (c h , p j,h )) = 1 2 E G ui×π-i s h |P G (s h | c h , p j,h ) -P G (s h | c h , p j,h )|,due to the condition in Definition 7.2. Meanwhile,1 2 E G ui×π-i s h |P G (s h | c h , p j,h ) -P G (s h | c h , p j,h )| ≤ s h ,c h ,p j,h |P ui×π-i,G (s h , c h , p j,h ) -P ui×π-i, G (s h , c h , p j,h )| ≤ τ h |P ui×π-i,G (τ h ) -P ui×π-i, G (τ h )| ≤ τ H |P ui×π-i,G (τ H ) -P ui×π-i, G (τ H )| ≤ E G ui×π-i [ h∈[H] ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1 ],where the first inequality is by Lemma J.7, the second and third inequalities are due to the fact that TV distance does not increase after marginalization, and the last inequality is by Lemma H.9. Since π -i is a fixed and fully-observable Markov policy, by Lemma H.10, we haveE G ui×π-i   h∈[H] ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1   ≤ max ui∈Π S,i E G ui×π-i   h∈[H] ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1   ,thus proving the first result of our lemma.For the second result of our lemma, it can be proved similarly that for any i ∈[n], m i ∈ M i , j ∈ [n], h ∈ [H], P (mi⋄πi)⊙π-i,G (s h ̸ = g j,h (c h , p j,h )) ≤ E G (mi⋄πi)⊙π-i   h∈[H] ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1   .By Lemma J.2, we proved the second result.Theorem J.4. Fix any ϵ, δ ∈ (0, 1 ) and computational complexity POLY(S, A, H, O, 1 ϵ ).Proof. With the help of Lemma J.3, it suffices to provemax i∈[n],ui∈Π S,i E G ui×π-i [ h∈[H] ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1 ] ≤ ϵ.The following proof procedure follows similarly to that of Theorem H.5. For each h ∈ [H] and s h ∈ S, we definep h (s h ) = max i∈[n],ui∈Π S,i d ui×π-i h (s h ).Fix ϵ 1 , δ 1 > 0, we define U(h, ϵ 1 ) = {s h ∈ S | p h (s h ) ≥ ϵ 1 }. By [36] for each s h ∈ U(h, ϵ 1 ) with probability 1 -n • δ 1 . Now we assume this event holds for any h ∈ [H] and s h ∈ U(h, ϵ 1 ). For each s h ∈ S and a h ∈ A, we have executed each policy {Ψ i (h, s h ) × π -i } i∈ [n] for the first h -1 steps followed by an action a h ∈ A for N episodes and denote the total number of episodes that s h and a h are visited as N h (s h , a h ), and N h (s h ) = a∈A N h (s h , a). Then with probability 1 -e -N ϵ1/8 , we have N h (s h , a h ) ≥ N p h (s h ) 2 by Chernoff bound. Now conditioned on this event, we are ready to evaluate the following for any i ∈ [n], and u i = Ψ i (h, s h ) ∈ Π S,i :E G ui×π-i ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 = s h ,a h d ui×π-i h (s h )(u i × π -i ) h (a h | s h )∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 ≤ 2 • Sϵ 1 + s h ∈U (h,ϵ1),a h d ui×π-i h (s h )(u i × π -i ) h (a h | s h ) S log(1/δ 2 ) N h (s h , a h ) ≤ 2 • Sϵ 1 + s h ∈U (h,ϵ1),a h d ui×π-i h (s h )(u i × π -i ) h (a h | s h ) 2S log(1/δ 2 ) N p h (s h ) ≤ 2 • Sϵ 1 + s h d ui×π-i h (s h ) S log(1/δ 2 ) N ≤ 2 • Sϵ 1 + S log(1/δ 2 ) N ,where the second step is by Lemma J.8, and the last step is by Cauchy-Schwarz inequality. Similarly,E P ui×π-i ∥O h (• | s h ) -O h (• | s h )∥ 1 = s h d ui×π-i h (s h )∥O h (• | s h ) -O h (• | s h )∥ 1 ≤ 2 • Sϵ 1 + s h ∈U (h,ϵ1) d ui×π-i h (s h ) O log(1/δ 2 ) N h (s h ) ≤ 2 • Sϵ 1 + s h ∈U (h,ϵ1) d ui×π-i h (s h ) O log(1/δ 2 ) N p h (s h ) ≤ 2 • Sϵ 1 + s h ∈U (h,ϵ1) d ui×π-i h (s h ) O log(1/δ 2 ) N ≤ 2 • Sϵ 1 + SO log(1/δ 2 ) N ,where the second step is by Lemma J.9, and the last step is by Cauchy-Schwarz inequality. Therefore, by a union bound, all high probability events hold with probability1 -SHnδ 1 -SHAe -N ϵ1/8 -SAHδ 2 .Therefore, we can choose N = O( S 2 +SO ϵ 2) and ϵ 1 = O( ϵ , S)leading to the total sample complexitySHA(nN + O( S 3 AH 4 ϵ )) = O( nS 2 AHO + nS 3 AH ϵ 2 + S 4 A 2 H 5 ϵ ).Note that although our Algorithm 5 and Theorem J.4 are stated for NE/CCE, it can also handle CE with simple modifications, where the key observation is that the strategy modification m i ∈ M S,i can also be regarded as a Markov policy in an extended MDP marginalized by π -i defined below. Definition J.5. We define M extended (π) to be an MDP for agent i, where for each h ∈ [H], the state is (s h , a i,h ), the action is some modified action a ′ i,h , the transition is defined asT extended h (s h+1 , a i,h+1 | s h , a i,h , a ′ i,h ) := E a -i,h ∼π h (• | s h ,a i,h ) [T h (s h+1 | s h , a ′ i,h , a -i,h )π h+1 (a i,h+1 | s h+1 )],where we slightly abuse the notation of π h (a -i,h | s h , a i,h ) and π h (a i,h | s h ) by defining them as the posterior and marginal distribution induced by the joint distribution π h (a h | s h ). Similarly, the reward is given by rextended h (s h , a i,h , a ′ i,h ) := E a -i,h ∼π h (• | s h ,a i,h ) [r h (s h , a ′ i,h , a -i,h )].With the help of such an extended MDP, we can develop Algorithm 6, which is a CE version of Algorithm 5 with the following guarantees. Theorem J.6. Fix any ϵ, δ ∈ (0, 1). Algorithm 6 can learn a decoding function g such thatmax i∈[n],mi∈Mi,j∈[n],h∈[H] P (mi⋄πi)⊙π-i,G (s h ̸ = g j,h (c h , p j,h )) ≤ ϵ, with total sample complexity O( nS 2 A 3 HO+nS 3 A 4 H ϵ 2 + S 4 A 6 H 5 ϵ) and computational complexity POLY(S, A, H, O, 1 ϵ ).Proof. Due to the construction of G extended (π -i ), the proof of Theorem J.4 readily applies, where the only difference is that the state space of G extended (π -i ) is SA i , larger than that of G(π -i ) by a factor of A i thus proving our theorem.Lemma J.7. Suppose we can sample from a joint distribution P ∈ ∆(X × Y) for some finite X , Y i.i.d. Then we can learn an approximate distribution Q ∈ ∆(X × Y) with sample complexityΘ |X ||Y|+log 1/δ ϵ 2 such that E x∼P y∈Y |P (y | x) -Q(y | x)| ≤ 2 x∈X ,y∈Y |P (x, y) -Q(x, y)| ≤ ϵ,with probability 1 -δ.Proof. Note the following holdsx∈X ,y∈Y |P (x, y) -Q(x, y)| = x∈X ,y∈Y |P (x, y) -P (x)Q(y | x) + P (x)Q(y | x) -Q(x, y)| ≥ x∈X ,y∈Y |P (x, y) -P (x)Q(y | x)| -|P (x)Q(y | x) -Q(x, y)|.Therefore, we haveE x∼P y∈Y |P (y | x) -Q(y | x)| ≤ x∈X ,y∈Y |P (x, y) -Q(x, y)| + x∈X ,y∈Y |P (x) -Q(x)| ≤ 2 x∈X ,y∈Y |P (x, y) -Q(x, y)|. (J.2)By the sample complexity of learning discrete distributions [13] , we can learn Q such thatx∈X ,y∈Y |P (x, y) -Q(x, y)| ≤ ϵ in sample complexity Θ |X ||Y|+log 1/δ ϵ 2with probability 1 -δ. Thus, we proved our lemma.Lemma J.8 (Concentration on transition). Fix δ > 0 and dataset {τ k H } k∈[N ] sampled from P under policy π ∈ Π gen . We define for each h ∈[H], (s h , a h , s h+1 ) ∈ S × A × S N h (s h , a h ) = k∈[N ] 1[s k h = s h , a k h = a h ] N h (s h , a h , s h+1 ) = k∈[N ] 1[s k h = s h , a k h = a h , s k h+1 = s h ].Then with probability 1 -δ, it holds that for any k ∈EQUATIONfor some absolute constant C 1 > 0, where we define T h (s h+1 | s h , a h ) = N h (s h ,a h ,s h+1 ) max{N h (s h ,a h ),1} .Proof. This is done by firstly bounding ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 for specific k, h, s h , a h according to [13] and then taking union bound for all k ∈ [K], h ∈ [H], s h ∈ S, a h ∈ A.Lemma J.9 (Concentration on emission). Fix δ > 0 and dataset {τ k H } k∈[N ] sampled from P under some policy π ∈ Π gen . We define for each h ∈[H], (s h , o h ) ∈ S × O N h (s h , o h ) = k∈[N ] 1[s k h = s h , o k h = o h ], N h (s h ) = k∈[N ] 1[s k h = s h ].Then, with probability at least 1 -δ, it holds that∥O h (• | s h ) -O h (• | s h )∥ 1 ≤ C 2 O log(SHK/δ) max{N k h (s h ), 1}, for some absolute constant C 2 > 0, where we defineO h (o h | s h ) = N h (s h ,o h ) max{N h (s h ),1} .Proof. This is done by firstly bounding ∥Oh (• | s h ) -O h (• | s h )∥ 1for specific k, h, s h according to [13] and then taking union bound for all k ∈[K], h ∈ [H], s h ∈ S.Lemma J.10. Fix δ > 0. With probability 1 -δ, it holds that for any k ∈[K], h ∈ [H], s h ∈ S: o h+1 P G (o h+1 | s h , a h ) -J k h (o h+1 | s h , a h ) ≤ C 3 O log(SHKA/δ) N k h (s h , a h ), where J k h is defined in Algorithm 7.Proof. This is done by firstly bounding o h+1 P G (o h+1 | s h , a h ) -J k h (o h+1 | s h , a h ) for specific k, h, s h , a h according to [13] and then taking union bound for all k ∈[K], h ∈ [H], s h ∈ S, a h ∈ A.From now on, we shall use the bonus asb k h (s h , a h ) = min C 3 (H -h) O log(SAHK/δ) max{N k h (s h , a h ), 1} , 2(H -h) (J.3)for some absolute constant C 3 > 0.Before presenting our technical analysis, we define the following notation for the ease of intermediate analysis. We define the following approximate value function for any policy π ∈ Π in a backward way for h ∈ [H]:V π,G i,h (c h ) := E s h ,p h ∼ P h (•,• | c h ) E ω h ,{a j,h ∼π j,h (• | ω j,h ,c h ,p j,h )} j∈[n] E s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) r i,h (s h , a h ) + V π,G i,h+1 (c h+1 ) , Q π,G i,h (c h , γ h ) := E s h ,p h ∼ P h (•,• | c h ) E {a j,h ∼γ j,h (• | p j,h )} j∈[n] E s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) r i,h (s h , a h ) + V π,G i,h+1 (c h+1 ) , for each (i, c h ) ∈ [n] × C h , where we define V π,G i,H+1 (c H+1 ) = 0.Intuitively, this definition of V π,G i,h (c h ) mimics the Bellman equation of the ground-truth value function V π,G i,h (c h ) by replacing the ground-truth belief P G (s h , p h | c h ) by P h (s h , p h | c h ). Next, we point out the following quantitative bound when using V π,G i,h (c h ) to approximate V π,G i,h (c h ). Meanwhile, we also define the error for the belief as followsϵ belief := max π∈Π ∥P G (•, • | c h ) -P h (•, • | c h )∥ 1 .Lemma J.11. For any π ′ , π ∈ Π, it holdsE G π ′ |V π,G i,h (c h ) -V π,G i,h (c h )| ≤ (H -h + 1) 2 ϵ belief .Proof. It follows directly by combining Lemma 4 and Lemma 8 of [50] .Meanwhile, note that although in Algorithm 7, the value we maintain has input c h instead of c h for computational efficiency, we extend the definition of those values to also accept c h as inputs as follows (with a slight abuse of notation):Q high,k i,h (c h , γ h ) := Q high,k i,h ( c h , γ h ) Q high,k i,h (c h , p h , s h , a h ) := Q high,k i,h ( c h , p h , s h , a h ) V high,k i,h (c h ) := V high,k i,h ( c h ) Q low,k i,h (c h , γ h ) := Q low,k i,h ( c h , γ h ) Q low,k i,h (c h , p h , s h , a h ) := Q low,k i,h ( c h , p h , s h , a h ) V low,k i,h (c h ) := V low,k i,h ( c h ), where we recall that c h = Compress h (c h ). Lemma J.12 (Optimism 1 for NE/CCE). With probability 1 -δ, for any k ∈ [K], for Algorithm 7, it holds that for any i ∈[n], π ′ i ∈ Π i , h ∈ [H] Q high,k i,h ( c h , γ h ) ≥ Q π ′ i ×π k -i ,G i,h (c h , γ h ) V high,k i,h ( c h ) ≥ V π ′ i ×π k -i ,G i,h (c h ),where we recall that c h = Compress h (c h ).Proof. We will prove by backward induction. Obviously, it holds for h = H + 1. Now we assume the lemma holds for h + 1. Now we notice that by definition,Q high,k i,h (c h , γ h ) = E s h ,p h ∼ P h (•,• | c h ) E {a j,h ∼γ j,h (• | p j,h )} j∈[n] Q high,k i,h (c h , p h , s h , a h ) = E s h ,p h ∼ P h (•,• | c h ) E {a j,h ∼γ j,h (• | p j,h )} j∈[n] min{r i,h (s h , a h ) + b k-1 h (s h , a h ) + E o h+1 ∼ J k-1 h (• | s h ,a h ) V high,k i,h+1 (c h+1 ) , H -h + 1} ≥ E s h ,p h ∼ P h (•,• | c h ) E {a j,h ∼γ j,h (• | p j,h )} j∈[n] min r i,h (s h , a h ) + b k-1 h (s h , a h ) + E o h+1 ∼ J k-1 h (• | s h ,a h ) V π ′ i ×π k -i ,G i,h+1 (c h+1 ) , H -h + 1 ,where the last step is by inductive hypothesis. Now note that for any s h , p h , a h , we haveb k-1 h (s h , a h ) + E o h+1 ∼ J k-1 h (• | s h ,a h ) V π ′ i ×π k -i ,G i,h+1 (c h+1 ) ≥ b k-1 h (s h , a h ) -(H -h)∥ J k-1 h (• | s h , a h ) -P G (• | s h , a h )∥ 1 + E s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) V π ′ i ×π k -i ,G i,h+1 (c h+1 ) ≥ E s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) V π ′ i ×π k -i ,G i,h+1 (c h+1 ) , where we notice P G (o h+1 | s h , a h ) = s h+1 O h+1 (o h+1 | s h+1 )T h (s h+1 | s h , a h )for the first inequality, and the second inequality comes from the construction of our bonus b k-1 h (s h , a h ) in Equation (J.3) and Lemma J.10. Meanwhile, by the definition of value functions, it holds thatE s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) V π ′ i ×π k -i ,G i,h+1 (c h+1 ) ≤ H -h. Therefore, we have min r i,h (s h , a h ) + b k-1 h (s h , a h ) + E s h+1 ,o h+1 ∼ J k-1 h (•,• | s h ,a h ) V π ′ i ×π k -i ,G i,h+1 (c h+1 ) , H -h + 1 ≥ r i,h (s h , a h ) + E s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) V π ′ i ×π k -i ,G i,h+1 (c h+1 ) . Now we conclude Q high,k i,h (c h , γ h ) ≥ E s h ,p h ∼ P h (•,• | c h ) E {a j,h ∼γ j,h (• | p j,h )} j∈[n] E s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) [r i,h (s h , a h ) + V π ′ i ×π k -i ,G i,h+1 (c h+1 )] = Q π ′ i ×π k -i ,G i,h (c h , γ h ).Q high,k i,h (c h , γ h ) = Q high,k i,h ( c h , γ h ), thus proving Q high,k i,h ( c h , γ h ) ≥ Q π ′ i ×π k -i ,G i,h (c h , γ h ). Now for the value function, note that V high,k i,h (c h ) = E ω h Q high,k i,h (c h , {π k j,h (• | ω j,h , c h , •)} j∈[n] ) ≥ E ω ′ h E ω h Q high,k i,h (c h , {π k j,h (• | ω j,h , c h , •)} j∈[n]\{i} , π ′ i,h (• | ω ′ i,h , c h , •)) ≥ E ω ′ h E ω h Q π ′ i ×π k -i ,G i,h (c h , {π k j,h (• | ω j,h , c h , •)} j∈[n]\{i} , π ′ i,h (• | ω ′ i,h , c h , •)) = V π ′ i ×π k -i ,G i,h (c h ),where the first step is by the property of Bayesian CCE, and the second step is byQ high,k i,h (c h , γ h ) ≥ Q π ′ i ×π k -i ,G i,h (c h , γ h ) for any γ h ∈ Γ h . Again by definition, we proved V high,k i,h ( c h ) = V high,k i,h (c h ) ≥ V π ′ i ×π k -i ,G i,h (c h ).Lemma J.13 (Optimism 1 for CE). With probability 1 -δ, for any k ∈ [K], for Algorithm 7, it holds that for any i ∈[n], m i ∈ M i , h ∈ [H] Q high,k i,h ( c h , γ h ) ≥ Q (mi⋄π k i )⊙π k -i ,G i,h (c h , γ h ) V high,k i,h ( c h ) ≥ V (mi⋄π k i )⊙π k -i ,G i,h (c h ).Proof. We will prove by backward induction. Obviously, it holds for h = H + 1. Now we assume the lemma holds for h + 1. Now we notice that by definition,Q high,k i,h (c h , γ h ) = E s h ,p h ∼ P h (•,• | c h ) E {a j,h ∼γ j,h (• | p j,h )} j∈[n] Q high,k i,h (c h , p h , s h , a h ) = E s h ,p h ∼ P h (•,• | c h ) E {a j,h ∼γ j,h (• | p j,h )} j∈[n] min{r i,h (s h , a h ) + b k-1 h (s h , a h ) + E o h+1 ∼ J k-1 h (• | s h ,a h ) V high,k i,h+1 (c h+1 ) , H -h + 1} ≥ E s h ,p h ∼ P h (•,• | c h ) E {a j,h ∼γ j,h (• | p j,h )} j∈[n] min r i,h (s h , a h ) + b k-1 h (s h , a h ) + E o h+1 ∼ J k-1 h (• | s h ,a h ) V (m i ⋄π k i )⊙π k -i ,G i,h+1 (c h+1 ) , H -h + 1 ,where the last step is by inductive hypothesis. Now note that for any s h , p h , a h , we haveb k-1 h (s h , a h ) + E o h+1 ∼ J k-1 h (• | s h ,a h ) V (m i ⋄π k i )⊙π k -i ,G i,h+1 (c h+1 ) ≥ b k-1 h (s h , a h ) -(H -h)∥ J k-1 h (• | s h , a h ) -P G (• | s h , a h )∥1 + E s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) V (m i ⋄π k i )⊙π k -i ,G i,h+1 (c h+1 ) ≥ E s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) V (m i ⋄π k i )⊙π k -i ,G i,h+1 (c h+1 ) ,where we notice PG (o h+1 | s h , a h ) = s h+1 O h+1 (o h+1 | s h+1 )T h (s h+1 | s h , a h )for the first inequality, and the second inequality comes from the construction of our bonus b k-1 h (s h , a h ) in Equation (J.3) and Lemma J.10. Meanwhile, by the definition of value functions, it holds thatE s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) V (mi⋄π k i )⊙π k -i ,G i,h+1 (c h+1 ) ≤ H -h. Therefore, we have min{r i,h (s h , a h ) + b k-1 h (s h , a h ) + E s h+1 ,o h+1 ∼ J k-1 h (•,• | s h ,a h ) V (mi⋄π k i )⊙π k -i ,G i,h+1 (c h+1 ) , H -h + 1} ≥ r i,h (s h , a h ) + E s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) V (mi⋄π k i )⊙π k -i ,G i,h+1 (c h+1 ) . Now we conclude Q high,k i,h (c h , γ h ) ≥ E s h ,p h ∼ P h (•,• | c h ) E {a j,h ∼γ j,h (• | p j,h )} j∈[n] E s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) r i,h (s h , a h ) + V (m i ⋄π k i )⊙π k -i ,G i,h+1 (c h+1 ) = Q (m i ⋄π k i )⊙π k -i ,G i,h (c h , γ h ).Q high,k i,h (c h , γ h ) = Q high,k i,h ( c h , γ h ), thus proving Q high,k i,h ( c h , γ h ) ≥ Q (mi⋄π k i )⊙π k -i ,G i,h (c h , γ h ). Now for the value function, note that V high,k i,h (c h ) = E ω h Q high,k i,h (c h , {π k j,h (• | ω j,h , c h , •)} j∈[n] ) ≥ E ω h Q high,k i,h (c h , {π k j,h (• | ω j,h , c h , •)} j∈[n]\{i} , (m i,h ⋄ π k i,h )(• | ω i,h , c h , •)) ≥ E ω h Q (mi⋄π k i )⊙π k -i ,G i,h (c h , {π k j,h (• | ω j,h , c h , •)} j∈[n]\{i} , (m i,h ⋄ π k i,h )(• | ω i,h , c h , •)) = V (mi⋄π k i )⊙π k -i ,G i,h (c h ),where the first step is by the property of Bayesian CE, and the second step is by Qhigh,k i,h (c h , γ h ) ≥ Q (mi⋄π k i )⊙π k -i ,G i,h (c h , γ h ) for any γ h ∈ Γ h . Again by definition, we proved V high,k i,h ( c h ) = V high,k i,h (c h ) ≥ V (mi⋄π k i )⊙π k -i ,G i,h (c h ).Lemma J.14 (Pessimism). With probability 1 -δ, for any k ∈ [K], for Algorithm 7, it holds that for anyi ∈ [n], h ∈ [H] Q low,k i,h ( c h , γ h ) ≤ Q π k ,G i,h (c h , γ h ) V low,k i,h ( c h ) ≤ V π k ,G i,h (c h ).Proof. We prove by backward induction on h. Obviously, the lemma holds for h = H + 1. Now we assume the lemma holds for h + 1. Similar to the proof of the previous lemma, we note by inductive hypothesisQ low,k i,h (c h , γ h ) ≤ E s h ,p h ∼ P h (•,• | c h ) E {a j,h ∼γ j,h (• | p j,h )} j∈[n] max r i,h (s h , a h ) -b k-1 h (s h , a h ) + E s h+1 ,o h+1 ∼ J k-1 h (•,• | s h ,a h ) V π k ,G i,h+1 (c h+1 ) , 0 ,where for any s h , p h , a h , we have-b k-1 h (s h , a h ) + E o h+1 ∼ J k-1 h (• | s h ,a h ) V low,k i,h+1 (c h+1 ) ≤ -b k-1 h (s h , a h ) + (H -h)∥ J k-1 h (• | s h , a h ) -P G (• | s h , a h )∥ 1 + E s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) V π k ,G i,h+1 (c h+1 ) ≤ E s h+1 ∼T h (• | s h ,a h ),o h+1 ∼O h+1 (• | s h+1 ) V π k ,G i,h+1 (c h+1 ) ,where the last step again comes from the construction of our bonus in Equation (J. max π ′ i ∈Π i V π ′ i ×π k -i ,G i,1 (c k 1 ) -V π k ,G i,1 (c k 1 )≤O(KH ) and computational complexity POLY(S, A, O, H, 1 ϵ , log 1 δ ).Proof. Note for any given i ∈ [n] and π ′ i ∈ Π i , by Lemma J.12 and Lemma J.14, it holds maxπ ′ i ∈Πi V π ′ i ×π k -i ,G i,1 (c k 1 ) -V π k ,G i,1 (c k 1 ) ≤ V high,k i,h (c k h ) -V low,k i,h (c k h ).Therefore, it suffices to bound V high,k i,h (c k h ) -V low,k i,h (c k h ). V high,k i,h (c k h ) -V low,k i,h (c k h ) = E s h ,p h ∼ P h (•,• | c k h ) Eω h Q high,k i,h (c k h , {π k j,h (• | •, c k h , •)} j∈[n] ) -Q low,k i,h (c k h , {π k j,h (• | •, c k h , •)} j∈[n] ) ≤ E s h ,p h ∼P G (•,• | c k h ) Eω h Q high,k i,h (c k h , {π k j,h (• | •, c k h , •)} j∈[n] ) -Q low,k i,+ (H -h + 1)ϵ h (c k h ) ≤ Z 1 k,h + Q high,k i,h (c k h , p k h , s k h , a k h ) -Q low,k i,h (c k h , p k h , s k h , a k h ) + (H -h + 1)ϵ h (c k h ) ≤ Z 1 k,h + E o h+1 ∼ J k-1 h (• | s k h ,a k h ) V high,k i,h+1 (c h+1 ) -V low,k i,h+1 (c h+1 ) + (H -h + 1)ϵ h (c k h ) + 2b k-1 h (s k h , a k h ) ≤ Z 1 k,h + E o h+1 ∼P G (• | s k h ,a k h ) V high,k i,h+1 (c h+1 ) -V low,k i,h+1 (c h+1 ) + (H -h + 1)ϵ h (c k h ) + 3b k-1 h (s k h , a k h ) ≤ Z 1 k,h + Z 2 k,h + V high,k i,h+1 (c k h+1 ) -V low,k i,h+1 (c k h+1 ) + (H -h + 1)ϵ h (c k h ) + 3b k-1 h (s k h , a k h ),where we define the Martingale difference sequence as follows Now by Lemma J.12 and Lemma J.14 and putting everything together, we concludeZ 1 k,h := E s h ,p h ∼P G (•,• | c k h ) E ω h E {a j,h ∼π k j,h (• | ω j,h , c k h ,p j,h )} j∈[n] Q high,k i,h (c k h , p h , s h , a h ) -Q low,k i,h (c k h , p h , s h , a h ) -Q high,k i,h (c k h , p k h , s k h , a k h ) -Q low,k i,h (c k h , p k h , s k h , a k h ) Z 2 k,h := E o h+1 ∼P G (• | s k h ,a k h ) V high,k i,h+1 (c h+1 ) -V low,k i,h+1 (c h+1 ) -V high,k i,h+1 (c k h+1 ) -V low,k i,k∈[K] max i∈[n] max π ′ i ∈Π i V π ′ i ×π -i ,G i,1 (c k 1 ) -V π,G i,1 (c k 1 )≤ KH 2 ϵbelief + O(H 2 SAOK log(SAHK/δ) + H 2 SA O log(SAHK/δ)).Now by Lemma J.11, we proved the regret guarantees as followsk∈[K] max i∈[n] max π ′ i ∈Π i V π ′ i ×π k -i ,G i,1 (c k 1 ) -V π k ,G i,1 (c k 1 )≤ O(KH 2 ϵbelief + H 2 SAOK log(SAHK/δ) + H 2 SA O log(SAHK/δ)).For the PAC guarantees, since we define k ⋆ ∈ arg min k∈[K] V high,k i,1(c k 1 ) -V low,k i,1(c k 1 ), we haveCCE-gap(π k ⋆ ) ≤ O(H 2 ϵ belief ) + V high,k ⋆ i,h (c k ⋆ 1 ) -V low,k ⋆ i,h (c k ⋆ 1 ) ≤ O(H 2 ϵ belief ) + 1 K k∈[K] V high,k i,h (c k 1 ) -V low,k i,h (c k 1 )≤ O(H 2 ϵ belief + H 2 SAO log(SAHK/δ)/K + H 2 SA K O log(SAHK/δ)).Finally, for two-player zero-sum games, we denote π k ⋆ to be the marginalized policy of π k ⋆ . Then we have) ≤ CCE-gap(π k ⋆ ), thus concluding our theorem.Theorem J.16 (CE version). With probability 1 -δ, Algorithm 7 enjoys the regret guarantee ofk∈[K] max i∈[n] max m ′ i ∈M i V m i ⋄π k i ⊙π k -i ,G i,1 (c k 1 ) -V π k ,G i,1 (c k 1 )≤ O(KH ).Proof. Then proof follows as that of Theorem J.15, where we only need to change the first step of the proof asV π ′ i ×π k -i ,G i,h (c k h ) -V π k ,G i,h (c k h ) ≤ V high,k i,h (c k h ) -V low,k i,h (c k h ),by Lemma J.13 and Lemma J.14, and the remaining steps are exactly the same.Lemma J.17 (Adapted from Theorem H.5). Algorithm 8 can learn the approximate POMDP with transition T 1:H and emission O 1:H such that for any policy π ∈ Π gen and h ∈ [H] ) with probability 1 -δ.E G π ∥T h (• | s h , a h ) -T h (• | s h , a h )∥ 1 + ∥O h (• | s h ) -O h (• | s h )∥ 1 ≤ ϵ,Proof. Note that Algorithm 8 is essentially treating the POSG G as a centralized MDP and running Algorithm 4, where the only modifications we make in Algorithm 8 is that we take the controller set into considerations when learning the models. Specifically, for the transition T h , what we estimate is only T h (s h+1 | s h , a I h ,h ) instead of T h (s h+1 | s h , a h ). Therefore, the sample complexity of Algorithm 8 will not be worse than that of Algorithm 4.Proof of Theorem 7.7:Note that the proof idea essentially resembles that of Theorem H.6, where we construct the model G trunc for G as exactly the same way of constructing P trunc for P. Therefore, by Lemma H.9, we haveE G π [∥P G (•, • | c h ) -P G trunc (•, • | c h )∥ 1 ] ≤ 2 τ h |P π,G (τ h ) -P π,G trunc (τ h )| ≤ 4HSϵ 1 .Meanwhile, we can construct G trunc and G sub using the exactly way as for P trunc and P sub , where G sub is an γ-observable POSGs. Now, according to [50] , for all examples in Appendix C.3, there exists a compression function that maps c h to c h such that the size of the compressed common information is quasi-polynomial, i.e., C h ≤ (AO) Cγ -4 log SH ϵ 2 for some absolute constant C, and corresponding approximate belief { P h : C h → ∆(S × P h )} h∈ [H] such thatE G sub π ∥P G sub (•, • | c h ) -P h (•, • | c h )∥ 1 ≤ ϵ 2 .Therefore, we can do the same augmentation for P h on states from S low h to construct the approximate belief P h as in the proof of Theorem H.6, and the remaining steps are exactly the same as the proof of Theorem H.6. This will lead to a total of polynomial-time and polynomial-sample complexities. ■The Bayesian game is a generalization of normal-form games in partially observable settings. Specifically, a bayesian game is specified as (n, {A i } i∈[n] , {Θ i } i∈[n] , {r i } i∈[n] , µ), where n is the number of players, A i is the actor space, Θ i is the type space, r i : Θ × A → [0, 1] is the reward function, and µ is the prior distribution of the joint type. At the beginning of the game, a type θ = (θ i ) i∈[n] is drawn from the prior distribution µ ∈ ∆(Θ). Then each agent i gets its only type θ i and take the action a i . With a slight abuse of the notation, we define a strategy of an agent as γ i ∈ Γ i = {Θ i → ∆(A i )}. We define J i (γ i , γ -i ) to be the expected rewards for agent i, given the joint strategy γ i , γ -i .By definition, J i (γ i , γ -i ) can be evaluated asJ i (γ i , γ -i ) := E θ∼µ E {aj ∼γj (• | θj )} j∈[n] r i (θ, a).Bayesian NE. We define γ ⋆ is an ϵ-NE is it satisfies thatJ i (γ ⋆ ) ≥ J i (γ ′ i , γ ⋆ -i ) -ϵ, ∀i ∈ [n], γ ′ i ∈ Γ i .Bayesian CCE. We say a distribution of joint strategies s ∈ ∆(Γ) to be a ϵ-Bayesian CCE if it satisfiesE γ∼s J i (γ) ≥ E γ∼s J i (γ ′ i , γ -i ) -ϵ, ∀i ∈ [n], γ ′ i ∈ Γ i .(Agent-form) Bayesian CE. We say a distribution of joint strategies s ∈ ∆(Γ) to be an ϵ-agentform Bayesian CE if it satisfies E γ∼s J i (γ) ≥ E γ∼s J i (m i ⋄ γ i , γ -i ) -ϵ, ∀i ∈ [n], m ′ i ∈ M i , where M i = {Θ i × A i → A i } is the space for strategy modification, where m i modifies γ i as follows: given current type θ i and the recommended action a i , the strategy modification changes the action to the another action m i (θ i , a i ).Note that Bayesian NE for zero-sum games, and (agent-form) Bayesian CE/CCE are all tractable solution concepts and can be computed with polynomial computational complexity, e.g., [29, 32, 23] .In this paper, we aim to understand the provable benefits of privileged information for partially observable RL problems under two empirically successful paradigms, expert distillation [14, 63, 57] and asymmetric actor-critic [67, 7, 3] , which represent privileged policy and privileged value learning, respectively, with an emphasis on studying both the computational and sample efficiencies of the algorithms. Our results (as summarized in Table 1 ) showed that privileged information does improve learning efficiency in a series of known POMDP subclasses. One potential limitation of our work is that we only focused on the case with exact state information. It remains to explore whether such an assumption can be further relaxed, e.g., when privileged state information may be biased, partially observable, or delayed, as usually happens in practice, and how our theoretical results may be affected. Meanwhile, as an initial theoretical study, we have been primarily focusing on the tabular settings (except Appendix G), and it would be interesting to extend the results to function-approximation settings to handle massively large state, action, and observation spaces in practice.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to 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 to 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 or unintentional) misuse of the technology. • If 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: 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, or scraped datasets)?Justification: There is no such risk.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA] Justification: No external codes, data, models are used.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 or dataset.• The authors should state which version of the asset is used and, if possible, include a 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. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.Note that we require r 1,h + r2,h to be 1 instead of 0 to be consistent with our assumption that r i,h ∈ [0, 1] for each i ∈ [0, 1], and this requirement does not lose optimality as one can always subtract the constant-sum offset to attain a zero-sum reward structure.Note that γ cannot be larger than 1 since according to Assumption 2.2, γ ≤ ∥O h ∥∞ ≤ 1.Note that as pointed out in[6], the original asymmetric actor-critic[67], which conditioned the Q-function only on the states, yields a biased estimate of the policy gradient. We will thus use the unbiased one throughout.by Chernoff bound. Now conditioned on this event, we are ready to evaluate 
 
 Appendix:  


Decision: This paper presents novel analysis of partially observable RL in the case when privileged information is available during training (ability to observe ground truth states during training). In particular, the two most common privileged settings are considered---(fully observable) expert distillation and asymmetric actor-critic. Theoretical analysis of standard methods in these frameworks is conducted and a more efficient novel algorithm is proposed for the later case. Extensions to the MARL case are considered and some experiments are provided. 

While partially observable RL (RL in POMDPs) is popular, there is lack of theoretical analysis of many of the methods. Similarly, many algorithms focus on the privileged setting in an attempt to improve performance by using additional information from a simulator during training. A better understanding of these algorithms as well as improved algorithms would be beneficial to the community. 

The paper makes an important contribution but it is very dense and the significance of the results is somewhat unclear. Because there are multiple different types of privileged information considered as well as the multiagent (POSG) case, there are many topics covered in the paper, making it hard to fit everything in clearly. In terms of significance, there some question about how practical the analysis and algorithms are. The analysis makes some strong assumptions, such as the deterministic filter condition, but these assumptions still fit with a large portion of POMDPs (including several of those used in papers). The proposed algorithms are unlikely to scale well in their current form but they have the potential to inform future algorithms in the field. The author response and discussion was helpful for clarifying some of the confusions so the paper should be updated to include versions of this text. The additional results were also helpful to better understand the benefits of the approach. The paper would be strengthened by including more discussion about how future work could build off of the theory and algorithms in this paper to develop scalable methods that still outperform current approaches.

Reviews: review: paper_summary: paper_summary: The submission addresses both statistically and computationally efficient reinforcement learning (RL) in Partially Observable Markov Decision Processes (POMDPs). The training phase has access to hidden states, while the goal is to learn the optimal policy at test time without such access. The authors propose a sample and computation-efficient algorithm under a deterministic filter stability condition.
strength_weakness: strength_weakness: **High-Level Critic**

- More space should have been dedicated to elaborating on the real technical question that the paper aims to resolve. With access to hidden states, the statistical hardness is virtually eliminated, so the focus could have been purely on the computational aspect. The poly-sample result is not surprising, and with the $\gamma$-observable assumption of (Golowich et al., 2022), quasi-polynomial complexity does not seem surprising either.

- The privileged information combined with the deterministic filter condition is very strong. It is unclear why Definition 3.2 was needed given the strong assumption of privileged information.

- The proposed algorithm does not seem as practical as advertised. Beyond the tabular setting, it is unclear how to implement it with general function classes, which are common in deep RL.


The current manuscript needs significant improvement in terms of writing, as detailed below.

- At the beginning of the introduction, it is confusing whether the paper is about RL in POMDPs with more information or about multi-agent RL in POMDPs. The two components investigated in this paper are orthogonal to each other, and the main result seems to be more about the former.

- The contribution of the paper needs to be more clearly articulated in the introduction. My understanding is that the paper is about (1) an algorithm that achieves both sample and computational efficiency with some new technical conditions, and (2) an extension of the proposed condition and algorithm to the multi-agent setting.

- The sentence in Lines 64-65 is confusing. What do we aim to achieve with actor-critic?

- Proposition 3.1 pertains to a specific algorithm, not to the general hardness of the problem.

- Jargon such as privileged, expert distillation, or teacher-student teaching may not help much in motivating the setting of this paper, as these are not the applications the paper pursued. It would be simpler if the problem were motivated from a theoretical perspective, focusing on technical challenges in existing works and some relevance to practice in the context of actor-critic implementation.
The decoding function $g$ in Lemma 4.3 is unclear. Definition 3.2 defines a posterior probability given $(s_{h-1}, a_{h-1}, o_h)$, but Lemma 4.3 assumes the posterior is almost deterministic. This could have been clearly stated during the problem setup. This assumption is essentially similar to the block MDP.
questions: questions: - Definition 3.2: Does $\gamma$-observability or $\gamma$-separated PSR imply Definition 3.2?

- When (Golowich et al., 2022) already achieved quasi-computational complexity for planning, what does Theorem 5.3 improve upon it? How are the previous results in Section 4 related to this result?
limitations: limitations: There are no experiments on practical benchmarks other than synthetic small tabular POMDPs.
paper_summary: paper_summary: This paper presents a novel theoretical characterization of certain kinds of
POMDP's which admit efficient learning. First, related characterizations are
explored and theoretical results show that these classes of POMDP's suffer from
certain drawbacks when trying to learn policies. Based on this analysis, a new
class of POMDP's is defined using the "deterministic filter condition".
This characterization of POMDP's is used to develop a novel learning algorithm
based on a decomposition of POMDP policy learning into belief learning and a
fully-observable policy learning step. Theoretical results show that policy
learning in POMDP's satisfying the deterministic filter condition condition is
tractable given access to privileged information at training time. The paper
also presents an extension of the proposed algorithm to handle partially
observable multi-agent RL.
strength_weakness: strength_weakness: - Some important sections are deferred to the appendix (related work,
  conclusion, and the discussion of experiments). I understand that space in the
  main paper is quite limited but I think it's important to include these
  sections. Maybe instead some theoretical results could be deferred to the
  appendix, especially those in section 3 concerning the shortcomings of
  existing approaches.
- More generally, so much of the discussion in the paper is in the appendix that
  the main body of the paper is quite hard to read.
- The central definition 3.2 could be explained a bit more (see questions).
- The legends on the graphs in the experimental section cover a lot of the
  relevant information in the graph.
questions: questions: I'm not sure that my understanding of 3.2 is correct. The intuition given in the
paper is that it corresponds to allowing $\gamma$ to go to 1 in assumption C.8.
But to my understanding C.8 encodes a certain kind of approximate observability
and letting $\gamma$ go to one recovers a fully-observable environment. (I
believe this is related to the restriction that $b^s$ is a one-hot vector in
definition 3.2). But if the environment is observable then there's no need to
consider POMDP's anymore, regular MDP's should be sufficient. Could you clarify
this definition a bit more, and especially how it is distinct from assuming that
the emission function can be inverted?
limitations: limitations: Limitations of the proposed approach are discussed, although this discussion is left to the appendix.
paper_summary: paper_summary: This paper has several contributions. The authors examine using privileged information for partial observability in RL. The paper looks at two empirical paradigms, expert distillation and asymmetric actor-critic, analyzing their computational and sample efficiency under specific conditions.

In addition, the authors introduce a belief-weighted optimistic asymmetric actor-critic algorithm, providing insights into MARL with CTDE.
strength_weakness: strength_weakness: - Like most theoretical papers, examination of existing empirical paradigms  and evaluation of proposed method is rather lacking, while understandable, is still a weakness.
- The deterministic filter condition, if I understand correctly, is weaker than previous conditions but still rather restrictive compared to real-world tasks.
- More toy examples could be helpful along side theory work.
questions: questions: - What is the purpose of developing the deterministic filter condition? Can you give a motivating example?
limitations: limitations: The authors are upfront about their assumptions; however, I would like to mention that reliance on specific assumptions for computational tractability might limit the generalizability of the results.
paper_summary: paper_summary: This paper offers valuable insights into the use of privileged information in partially observable reinforcement learning (POMDP), presenting theoretical advancements and practical algorithms. However, challenges remain in ensuring the effectiveness of expert distillation, applicability to real-world problems, and bridging the gap between training and test environments. Addressing these limitations is essential for advancing the practical implementation of Privileged Policy Learning.
strength_weakness: strength_weakness: 1.	Expert policies in pratical problems may not be optimal [1-3]. This raises concerns about the effectiveness of Privileged Policy Learning. If the expert policies are suboptimal, the student policies distilled from them may inherit these inefficiencies, potentially leading to suboptimal performance in practical applications. 

2.	A significant limitation highlighted is the dependency on access to the state of the POMDP environment. In most practical scenarios, the internal states are not observable, restricting the application of the proposed methods. The deterministic filter condition, while theoretically valuable, may not always be applicable in real-world problems where state observability is a significant challenge.

3.	The paper discusses the difficulty of obtaining the internal state in actual problems, creating a gap between the training environment (where privileged information is available) and the test environment (where it is not). This discrepancy can lead to performance degradation when the policies trained with privileged information are deployed in real-world scenarios where such information is unavailable. 

[1] Wu, Yueh-Hua, et al. "Imitation learning from imperfect demonstration." International Conference on Machine Learning. PMLR, 2019.

[2] Tian, Yuandong, Qucheng Gong, and Yu Jiang. "Joint policy search for multi-agent collaboration with imperfect information." Advances in neural information processing systems 33 (2020): 19931-19942.

[3] Tang, Yu, et al. "Hierarchical reinforcement learning from imperfect demonstrations through reachable coverage-based subgoal filtering." Knowledge-Based Systems 294 (2024): 111736.
questions: questions: The paper does not discuss the tightness of the derived bounds or whether they meet the needs of practical problems.
limitations: limitations: Lack of sufficient experimental verification

Comments: title: Response
Thanks for your support!
Have we addressed your concerns?
Have we addressed your concerns?
Have we addressed your remaining concerns?
Thanks for your dedicated efforts!
Thanks!
Response to further questions of Reviewer zFhw (Cont'd)
Response to further questions of Reviewer zFhw (Cont'd)
Response to further questions of Reviewer zFhw
Thank you for the response
References
Thanks for your replies!
comment: Thank for the detailed responses that address my concerns. I thus raise the score.
**We greatly thank the reviewer for appreciating our potential theoretical insights for future research and being NOT concerned with the value of theoretical works!** Meanwhile, we also thank the reviewer for bringing up the **value of the theoretical work** and would like also to clarify for you and (potentially) other reviewers to help further understand our paper in a high-level way.

In terms of **theoretical value**, we believe it has been emphasized and summarized in our Table 1 and Figure 1, which gives a complete landscape for how our approach with privileged information has offered **strict and significant** theoretical benefits in a wide variety of POMDPs. Therefore, we believe our theoretical results are sufficient enough.

In terms of **empirical value**, we also provide some potential points here

1. **We gave a rigorous criteria for using privileged policy learning/expert distillation in specific problems**. This will remind the practitioners to examine how well their applications satisfy our criteria (exactly or approximately) first before really applying such a method to certain problems. Therefore, it can not only serve as a theoretical condition but also as an empirical guidance, particularly considering that the limitations of privileged policy learning/expert distillation have not been not very well understood.

2. **We revealed the potential inefficiency of vanilla asymmetric-actor critic, and highlighted the importance of the advanced decoupled belief learning + policy optimization pipeline.** Notably, this rigorously answered why it is meaningful to pursue different and advanced variants for vanilla asymmetric-actor-critic algorithms to get better efficiency.

In summary, our Sec. 3, explicitly named as ***revisiting empirical paradigms*** is exactly trying to highlight/justify the value of our later theoretical results for practice. We believe different empirical practitioners can find different values from it according to what empirical paradigm they are adopting and what problem they are trying to solve.

**Finally, we want to sincerely thank you again for being optimistic of the theoretical results providing insight for future research! As theoreticians, we are also making efforts for developing empirically-relevant theory (like what we are trying to do in the current submission)!**
I thank the authors for their clarification.  It seems that other reviewers and I are uncertain of how much value this theoretical work would bring. I agree that as far as I can see, there is no straightforward significance. My score remains the same since I'm optimistic of the theoretical results providing insight for future research.
Dear Reviewer 9C6t,
We hope that you are doing well recently! Since the discussion period is ending very soon, we would like to kindly ask whether our responses have adequately addressed your concerns?

We understand that your main concerns are also on our Def 3.2 (deterministic filter condition). We would like to summarize again for our responses.

- On the one hand, Def 3.2 (deterministic filter condition) is already our best efforts at trying to unify existing problems. It also further extends the boundary of our current knowledge for tractable POMDP problems.

- More importantly, we also admit the potential limitations of such a condition. Therefore, in Sec.5, we do not assume this condition anymore but rather only require that observations are not totally uninformative (i.e., ruling out the $\gamma=0$ case in Assumption C.8, which is a quite weak assumption in our opinion). The only sacrifice is that the computation complexity becomes quasi-polynomial instead of polynomial. However, such quasi-polynomial dependency shown to be unimprovable either [22]

Finally, we would like thanks again for the reviewer's patience and efforts dedicated to reviewing our paper and looking forward to your replies!
Dear Reviewer tn5m,

We hope the reviewer is doing well! Since the discussion period is ending very soon, we would like to kindly ask whether our further responses have adequately addressed your remaining concerns?

We understand that the reviewer has the very valid concern of whether RL in POMDP with privileged information is a meaningful setting. We admit there might be other paradigms that will complement this privileged information setting like the wonderful literature shared by the reviewer (we will make sure to include those references in our revision!). Meanwhile, we also would like to point out that our focus is a **theoretical understanding** of such a valid and popular empirical paradigm that is already extensively employed in empirical applications. Therefore, discussion whether the POMDP with privileged information setting is valid is still a quite important question, but beyond the focus of our paper.

Finally, we would like thanks again for the reviewer's patience and efforts dedicated to reviewing our paper and looking forward to your replies!
We hope the reviewer is doing well! Since the discussion period is ending very soon, we would like to kindly ask whether our further responses have adequately addressed your remaining concerns? To briefly summarize and complement our further response above
- For the restrictiveness: we believe reviewer zFhw have shared similar concerns and confusions as you before. After understanding how our condition has been used to generalize existing, extensively-studied problems and obtain stronger theoretical guarantees, reviewer zFhw has revised the evaluation from 3 to 5. Therefore, we believe the discussions there can be very informative, and if the reviewer is also interested in some more detailed technical discussions, we also kindly refer to our further response to reviewer zFhw (Response to Q.2 there).
- For the problem size, we would like to complement that there is a large body of traditional literature on studying planning in POMDP, which also focuses on tabular POMDPs that could have the same order of size as us (as we mentioned in the response above). To connect to the modern deep RL literature, we have also made significant theoretical efforts. **In particular, we have shown that when the observation space is continuous/infinite, our algorithm just needs a simple classification oracle** (the entire Sec G discusses this setting). Therefore, we believe our algorithm can also scale to more complex applications, which can be a good future direction.

Finally, we would like thanks again for the reviewer's patience and efforts dedicated to reviewing our paper! We do apologize if we have caused some confusion for the reviewer in the original submission and promise to revise it accordingly!
We are excited to hear that our responses help address your concerns and will make sure the discussions with you (that are quite effective in our opinion) are included in the later revised version!
I appreciate the detailed responses. Now the picture is more clear to me, and I am now slightly more on the positive side.

However, I still think the submission in the current form needs improvement in terms of writing to clearly convey key challenges and intuition. In the revised version, it would be nicer if a bit more concise and crisp version of the responses to be included accordingly.
---

We are grateful to the reviewer for their dedicated efforts in reviewing our paper and for engaging in the discussion period, which has undoubtedly helped improve our work. We are looking forward to your further feedback. Thank you again.

---

[A] Efroni, Yonathan, et al. "Provable reinforcement learning with a short-term memory." International Conference on Machine Learning. PMLR, 2022.

[B] Guo, Jiacheng, et al. "Provably efficient representation learning with tractable planning in low-rank pomdp." International Conference on Machine Learning. PMLR, 2023.
4. **More importantly, we would like to emphasize again that our motivation is to understand existing practice and develop corresponding provable algorithms based on it, while the reward-free exploration + planning framework (using the algorithm from (Golowich et al., '23)) is certainly disconnected from this goal.** Specifically, our starting point was to analyze the popular pipeline of belief learning + policy optimization (**asymmetric actor-critic**). Note that **our novel techniques in Point 3 are just for one instantiation of the first step of belief learning under the specific $\gamma$-observability assumption and online exploration setting.** In practice, even if observability is not satisfied, there are many effective, empirical methods for the belief learning oracle that can be used, our policy optimization algorithm **decoupled from** the belief learning step are **still effective**. In contrast, such reward-free exploration + planning framework is restricted to the $\gamma$-observable POMDP setting only, and are different from emirical practice.

5. Finally, we would like to remind the reviewer that what the reviewer focuses on is just half of our results (Sec. 5), while in **Sec. 4, we do not need any reward-free techniques or observability assumption**, and the corresponding algorithms are also much more natural. Even in the half of the results that the reviewer focused on, our goal is not just developing **an** algorithm to achieve poly sample and quasi-poly computation complexity for the specific observable POMDP with online exploration setting at the same time, but analyzing (the flaws and enhancements of) **the** algorithmic paradigms used in practice. 

---

### Response to Q.2

1. **Key intuitive explanations of Def 3.2.** Firstly, the terminology of a filter refers to the process of estimating the underlying unknown state using a sequence of actions and observation (recursively). Therefore, our condition states that if at step $h$, the estimation of the current states $s_h$ is not random, then the state estimation for the next step $h+1$ after taking the new action $a_h$ and receiving the new observation $o_{h+1}$ is also non-random.

2. **Example of $\gamma$-observable POMDP.** We apologize for not further explaining observability. This was because we thought it is one of the standard assumptions in RL theory for addressing POMDPs. Notably, another useful/related assumption is weakly-revealing assumption [39], which is indeed also equivalent to $\gamma$-observability (up to some problem-dependent factors). For specific examples, we point out that a sufficient condition is that the emission matrix has **full row-rank**, and some simple/natural examples can be found in Example B.1 of [22].

3. **Why is this case addressed separately in Section 5?**

- Firstly, Sec.4 is to analyze the empirical paradigm of privileged **policy** learning/**expert policy distillation**, while Sec.5 is to analyze the empirical paradigm of privileged **value** learning/**asymmetric actor-critic**. **We have shown that the empirical paradigms in Sec.4 applied to observable POMDPs suffer from sub-optimality (Prop 3.1).** Therefore, we cannot handle this case in Sec. 4. Meanwhile, this sub-optimality further motivates us to propose our Def 3.2 (that is neither stronger or weaker than $\gamma$-observability).

- A more fundamental reason is that for those problems under Def 3.2, the paradigm of Sec. 4 can actually achieve poly sample + poly computation, while it is known that the quasi-poly computation complexity for $\gamma$-observable POMDP is **unimprovable** (Golowich et al., '23). Therefore, we analyzed **another** empirical paradigm in Sec.5 and show it can be used to handle the this $\gamma$-observable POMDP case we cannot handle before.

4. **Furthermore, what are the specific differences in the final guarantees (Theorem 4.5) between Examples E.3 and E.4?**

    We thank the reviewer for bringing this question that can indeed help us **further justify the provable benefits** of privileged information.

-  Firstly, there are **no** specific differences in the final guarantees between Examples E.3 and E.4. In other words, Theorem 4.5 holds as long as the POMDP satisfies Def 3.2. 

- Secondly, **the reason why there are no differences is that our guarantees do not suffer from the exponential dependency on decoding length anymore!** Note that references [A, B] that studied Example E.3 ($k$-decodable POMDP) **has to suffer from the exponential dependency on $k$ both statistically and computationally**, which explains why they have to assume $k$ to be a small constant. In contrast, under privileged information, we show that such exponential dependency on $k$ **can be removed** (with natural and **practical-relevant**  algorithms), which further explains why we can handle the new case Example E.4 that can not be handled by existing literature.
We thank the reviewer for the further questions and respond as follows.

---

### Response to Q.1

1. Firstly, the **computational hardness** for learning (statistically known to be tractable) POMDPs even with access to hidden states we have stated before is for the setting with **only privileged information** and **without any structural assumptions on the POMDP model.** We use it to reply to your high-level critic as follows
    > The privileged information combined with the deterministic filter condition is very strong. It is unclear why Definition 3.2 was needed given the strong assumption of privileged information.
 
2.  Secondly, we only claimed that such hardness of learning problems can potentially exist in the **standard learning setting without privileged information**. **Therefore, we use it to justify why privileged information, a well-motivated empirical paradigm, also offers strict theoretical benefits in terms of computation complexity.**

3. Thirdly, we **really appreciate the reviewer's great question regarding whether reward-free suffices**. In fact, **it was our initial thought as well**. However, we note that **naively extending** the reward-free techniques from MDP to the POMDP by also learning the emission fails, as detailed below. 

    To briefly review, the key idea for standard reward-free exploration in MDP is to estimate the transition given some reward-free dataset $D$ at step $h\in[H]$
$$
\hat{\mathbb{T}}\_h(s^\prime\mid s, a)=\frac{N\_h(s, a, s^\prime)}{N\_h(s, a)},
$$
where $N_h(s, a, s^\prime)$ and $N_h(s, a)$ denote the count of such state-action triplets/tuples in the reward-free dataset $D$. Correspondingly, we can get the guarantee of 
$$
V_1^{\pi, (\mathbb{T}, r)}(s_1)-V_1^{\pi, (\hat{\mathbb{T}}, r)}(s_1)\le \epsilon,
$$
for any reward function $r$ and policy $\pi$, where $V_1^{\pi, (\mathbb{T}, r)}(s_1)$ denotes the value of policy $\pi$ in the MDP specified by $(\mathbb{T}, r)$, and similarly, the definition extends to $V_1^{\pi, (\hat{\mathbb{T}}, r)}(s_1)$. Therefore, if we can find an optimal solution for the estimated model $(\hat{\mathbb{T}}, r)$, it is also an approximately optimal solution for the true MDP $(\mathbb{T}, r)$.

Back to POMDP, we can indeed estimate the model by
$$
\hat{\mathbb{T}}_h(s^\prime\mid s, a)=\frac{N_h(s, a, s^\prime)}{N_h(s, a)},
$$
$$
\hat{\mathbb{O}}_h(o\mid s)=\frac{N_h(s, o)}{N_h(s)},
$$
where again those $N_h$ denote the counts of appearance of the corresponding quantities in the reward-free dataset $D$. By a similar analysis, we can get a similar reward-free POMDP guarantees of 
$$
V_1^{\pi, (\mathbb{T}, \mathbb{O}, r)}(s_1)-V_1^{\pi, (\hat{\mathbb{T}}, \hat{\mathbb{O}}, r)}(s_1)\le \epsilon,
$$
for any reward function $r$ and policy $\pi$, where $V_1^{\pi, (\mathbb{T}, \mathbb{O}, r)}(s_1)$ denotes the value of policy $\pi$ in the POMDP specified by $(\mathbb{T}, \mathbb{O}, r)$, and similarly the definition extends to $V_1^{\pi, (\hat{\mathbb{T}}, \hat{\mathbb{O}}, r)}(s_1)$. Therefore, if we can find an optimal solution for the approximate POMDP $(\hat{\mathbb{T}},\hat{\mathbb{O}}, r)$, it is also an approximately optimal solution for the true POMDP. Up to now, the analysis could be similar to that of reward-free exploration in MDP.

However, even if the original POMDP satisfies $\gamma$-observability, $(\hat{\mathbb{T}},\hat{\mathbb{O}}, r)$ **is not necessarily a $\gamma$-observable POMDP. This is true even if we run the reward-free process for (polynomial) long enough episodes**, since the maximum visitation probability for certain states can be exponentially small. This will affect the estimation accuracy for corresponding rows of the emission $\hat{\mathbb{O}}$, potentially breaking its $\gamma$-observability (to **rigorously see why and how, we kindly refer to the proof of our Theorem H.5**). In other words, although such states that are inherently hard to visit do not affect the **value performance bounds**, or planning in the approximate **MDP** (since any MDP is computationally tractable), they do affect the tractability of planning in the approximate POMDP.

To briefly introduce the key idea to circumvent such an issue, **we introduce a new terminal state  $s^{\text{exit}}$ and try to redirect the probabilities transitioning to those hard-to-explore states to this terminal state** and **carefully re-define the transition/emission correspondingly to ensure the *misspecified* model is $\gamma^\prime$-observable**, while making sure $\frac{\gamma^\prime}{\gamma}\ge \mathcal{O}(1)$. **Note that none of such construction or analysis along the way is proposed/needed in the standard MDP reward-free exploration framework** since it only needs to care about the **value performance bound**, rather than the **computation tractability in the approximate model.**
I thank the authors for clarifying some of my concerns. However, there are several points that still not very convincing to me:


1. You mention the computational hardness for learning (statistically known to be tractable) POMDPs even with access to hidden states (privileged information). It would be very helpful for me to understand this challenge by answering the following question:

*Why cannot we simply learn the model through sufficiently long (but polynomial) reward-free exploration episodes (but also learn the reward and emission models), and output the result of quasi-poly planning on the estimated model?*


2. It seems that Definition 3.2 lacks some key intuitive explanations. Why are there no examples of $\gamma$-observability provided in Appendix E, and why is this case addressed separately in Section 5? Furthermore, what are the specific differences in the final guarantees (Theorem 4.5) between Examples E.3 and E.4?
[1] Jin, Chi, et al. "Sample-efficient reinforcement learning of undercomplete pomdps." Advances in Neural Information Processing Systems 33 (2020): 18530-18539.

[2] Uehara, Masatoshi, et al. "Provably efficient reinforcement learning in partially observable dynamical systems." Advances in Neural Information Processing Systems 35 (2022): 578-592.

[3] Uehara, Masatoshi, et al. "Computationally efficient pac rl in pomdps with latent determinism and conditional embeddings." International Conference on Machine Learning. PMLR, 2023.

[4] Krishnamurthy, Akshay, Alekh Agarwal, and John Langford. "Pac reinforcement learning with rich observations." Advances in Neural Information Processing Systems 29 (2016).

[5] Jiang, Nan, et al. "Contextual decision processes with low bellman rank are pac-learnable." International Conference on Machine Learning. PMLR, 2017.

[6] Efroni, Yonathan, et al. "Provable reinforcement learning with a short-term memory." International Conference on Machine Learning. PMLR, 2022.

[7] Guo, Jiacheng, et al. "Provably efficient representation learning with tractable planning in low-rank pomdp." International Conference on Machine Learning. PMLR, 2023.

[8] Golowich, Noah, Ankur Moitra, and Dhruv Rohatgi. "Planning in observable pomdps in quasipolynomial time." arXiv preprint arXiv:2201.04735 (2022).
We appreciate the reviewer's feedback and are glad to hear that the previous concern regarding whether Definition 3.2 implies decodability has been resolved. Regarding the remaining concerns, we believe they can be addressed with a few additional clarifications, which we apologize to be unable to detail fully in our previous rebuttal.

---

### Concerning the Restrictiveness of Definition 3.2

1. **Firstly, Definition 3.2 is not an artificial condition disconnected from existing literature, but rather an effort to unify and further relax existing classes of POMDPs that have been extensively studied.** Specifically, this condition is broader and encompasses the following well-known classes of POMDPs:

   - **Deterministic POMDP:** This is discussed in our Example E.1 and has been studied in a line of research [1, 2, 3].
   - **Block MDP:** This is addressed in our Example E.2 and has been studied in a separate line of research [4, 5].
   - $k$**-decodable POMDP:** This is covered in our Example E.3 and has been the focus of yet another research thread [6, 7].

   These examples have already been extensively studied, and the structural assumptions they entail are considered reasonable and valuable rather than restrictive. **Thus, we believe that our condition, which unifies these seemingly unrelated assumptions and further relaxes them, should not be regarded as restrictive, especially since these stronger assumptions have been thoroughly examined.**

2. **Secondly, Definition 3.2 pertains only to the first half of our results in Section 4, while the second half of our results in Section 5 does not rely on it anymore.** Specifically, we acknowledge that Definition 3.2 may not always be satisfied in real-world applications. **Therefore, in Section 5, we assume only that the observation is not entirely uninformative, meaning we rule out the** $\gamma = 0$ **case in Assumption C.8 without making any other assumptions.** The trade-off is that the computational complexity increases from polynomial to quasi-polynomial, but this is shown to be unimprovable even in the easier problem of planning [8].


---

### Regarding the Experiments

- Firstly, we emphasize that our primary goal is to develop solid theory rather than specific empirical algorithms. **In fact, none of the theoretical studies we previously cited [1-7] that focus on POMDPs include any experiments (except for [7] on simple environment)**. **Nonetheless, we acknowledge the importance of proof-of-concept experiments and have conducted corresponding validations**. Therefore, we think this should be viewed as a strength rather than a weakness.
- **Regarding the problem size, our problems are not significantly smaller even compared with those examined in the empirical literature on POMDP planning.** For example, the Tiger-grid problem, one of the most famous examples in the POMDP planning literature, has 36 states, 5 actions, 17 observations, and a shorter horizon than ours (a discount factor of 0.95 implies an effective horizon of 20). Notably, experiments of this scale are conducted for the relatively easier problem of planning. Thus, we believe our experiments on the much more challenging learning problems are sufficient for a theory-oriented paper.


---

### Regarding the Deferred Results in the Appendix

We do admit that a long appendix is necessary to present our results sufficiently and accurately. However, we believe that with one additional page in the final revision, along with the reviewer's wonderful suggestions, we can address all remaining concerns. Specifically:

- We will move the results related to revisiting empirical paradigms to the appendix. Based on the reviewer's feedback, we believe that maintaining the core messages of these results in the main text is sufficient.
- We will restore the motivating examples and explanations for Definition 3.2 to the main paper. We believe this will address most of the confusion expressed by all reviewers.

Therefore, we believe these straightforward adjustments will make our presentation much clearer and avoid further confusion. Finally, we hope that our paper will be evaluated primarily on its contributions rather than on these easily fixable presentation issues.

---

We are grateful to the reviewer for their dedicated efforts in reviewing our paper and for engaging in the discussion period, which has undoubtedly helped improve our work! We are looking forward to your further feedbacks!
Thank you for the explanation. I am less concerned about definition 3.2 now, although it still seems quite restrictive to me. I have raised my score slightly (3 -> 4). I am still concerned about the restrictiveness of 3.2, combined with the relatively small experiments (even the new experiments) and the amount of work which is deferred to the appendix.