Provable Partially Observable Reinforcement Learning with Privileged Information

Have we addressed your concerns?

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!

Have we addressed your concerns?

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!

Thanks for your support!

**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)!**

Thanks for your replies!

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!

Have we addressed your remaining concerns?

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!

Thank you for the response

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?

Response to further questions of Reviewer zFhw

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.**

Response to further questions of Reviewer zFhw (Cont'd)

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.

Response to further questions of Reviewer zFhw (Cont'd)

--- 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.