# Provably Efficient Reinforcement Learning in
Partially Observable Dynamical Systems

Masatoshi Uehara<EMAIL_ADDRESS>Supported by Masason Foundation Cornell
University  Ayush Sekhari<EMAIL_ADDRESS>Cornell University  Jason D. Lee
<EMAIL_ADDRESS>Princeton University  Nathan Kallus<EMAIL_ADDRESS>Cornell University  Wen Sun<EMAIL_ADDRESS>Cornell University

###### Abstract

We study Reinforcement Learning for partially observable dynamical systems
using function approximation. We propose a new Partially Observable Bilinear
Actor-Critic framework, that is general enough to include models such as
observable tabular Partially Observable Markov Decision Processes (POMDPs),
observable Linear-Quadratic-Gaussian (LQG), Predictive State Representations
(PSRs), as well as a newly introduced model Hilbert Space Embeddings of POMDPs
and observable POMDPs with latent low-rank transition. Under this framework,
we propose an actor-critic style algorithm that is capable of performing
agnostic policy learning. Given a policy class that consists of memory based
policies (that look at a fixed-length window of recent observations), and a
value function class that consists of functions taking both memory and future
observations as inputs, our algorithm learns to compete against the best
memory-based policy in the given policy class. For certain examples such as
undercomplete observable tabular POMDPs, observable LQGs and observable POMDPs
with latent low-rank transition, by implicitly leveraging their special
properties, our algorithm is even capable of competing against the globally
optimal policy without paying an exponential dependence on the horizon in its
sample complexity.

##  1 Introduction

Large state space and partial observability are two key challenges of
Reinforcement Learning (RL). While recent advances in RL for fully observable
systems have focused on the challenge of scaling RL to large state space in
both theory and in practice using rich function approximation, the
understanding of large scale RL under partial observability is still limited.
In POMDPs, for example, a core issue is that the optimal policy is not
necessarily Markovian since the observations are not Markovian.

A common heuristic to tackle large scale RL with partial observability in
practice is to simply maintain a time window of the history of observations,
which is treated as a state to feed into the policy and the value function.
Such a window of history can be often maintained explicitly via truncating
away older history (e.g., DQN uses a window with length 4 for playing video
games [mnih2013playing]; Open AI Five uses a window with length 16 for LSTMs
[berner2019dota]). Since even for planning under partial observations and
known dynamics, finding the globally optimal policy conditional on the entire
history is generally NP-hard (due to the curse of the history)
[littman1996algorithms, papadimitriou1987complexity, golowich2022planning],
searching for a short memory-based policy can be understood as a reasonable
middle ground that balances computation and optimality. The impressive
empirical results of these prior works also demonstrate that in practice,
there often exists a high-quality policy (not necessarily the globally
optimal) that is only a function of a short window of recent observations.
However, these prior works that search for the best memory-based policy
unfortunately cannot ensure sample efficient PAC guarantees due to the
difficulty of strategic exploration in POMDPs. The key question that we aim to
answer in this work is:

_Can we design provably efficient RL algorithms that agnostically learn the
best fixed-length memory based policy with function approximation?_

We provide affirmative answers to the above question. More formally, we study
RL for partially observable dynamical systems that include not only the
classic Partially Observable MDPs (POMDPs) [murphy2000survey, porta2006point,
shani2013survey], but also a more general model called Predictive State
Representations (PSRs) [littman2001predictive]. We design a model-free actor-
critic framework, named _PO-Bilinear Actor-Critic Class_ , where we have a
policy class (i.e., actors) that consists of policies that take a fixed-length
window of observations as input (memory-based policy), and a newly introduced
value link function class (i.e., critics) that consists of functions that take
the fixed-length window of history and (possibly multi-step if the system is
overcomplete) _future observations_ as inputs. A value link function class is
an analog of the value function class tailored to partially observable systems
that only relies on observable quantities (i.e., past and future observations
and actions). In our algorithm, we _agnostically_ search for the best memory-
based policy from the given policy class.

Our framework is based on the idea of a newly introduced notion of value link
function equipped with future observations. While the idea of using future
observations has been used in the literature on POMDPs, our work is the first
to use this idea to learn a high-quality policy in a model-free manner.
Existing works discuss how to use future observations only in a model-based
manner [boots2011closing, hefny2015supervised]. By leveraging these model-
based viewpoints, while recent works discuss strategic exploration to learn
near-optimal policies, their results are either limited to the tabular setting
(and are not scalable for large state spaces) [jin2020provably, guo2016pac,
azizzadenesheli2016reinforcement, xiong2021sublinear, liu2022partially] or are
tailored to specific non-tabular models and unclear how to incorporate general
function approximation [simchowitz2020improper, lale2020regret,
cai2022sample]. We break these barriers by devising a new actor-critic-based
model-free view on POMDPs. We demonstrate the _scalability_ and _generality_
of our PO-bilinear actor-critic framework by showing PAC-guarantee on many
models as follows (see Table 1 for a summary).

Observable Tabular POMDPs. In tabular observable POMDPs, i.e., POMDPs where
_multi-step_ future observations retain information about latent states, the
PO-bilinear rank decomposition holds. We can ensure the sample complexity is
$\mathrm{\mathrm{Poly}}(S,A^{M},O^{M},A^{K},O^{K},H,1/\sigma_{1})$ where
$\sigma_{1}=\min_{x}\|\mathbb{O}x\|_{1}/\|x\|_{1}$ ($\mathbb{O}$ is an
emission matrix),and $S,A,O$ are the cardinality of state, action, observation
space, respectively, $H$ is the horizon, and $K$ is the number of future
observations.111In Section 8, we discuss how to get rid of $O^{M},O^{K}$ using
a model-based learning perspective. The intuition is that a tabular POMDP’s
model complexity has nothing to do with $M$ or $K$, i.e., number of parameters
in transition and omission distribution is $S^{2}A+OA$ (even if we consider
the time-inhomogeneous setting, it scales with $H(S^{2}A+OA)$, but no $O^{M}$
and $O^{K}$) and the PO-bilinear rank is still $S$.  In the special
undercomplete ($O\geq S$) case, our framework is also flexible enough to set
the memory length according to the property of the problems in order to search
for the globally optimal policy. More specifically, using the latest result
from [golowich2022planning] about belief contraction, we can set
$M=\tilde{O}((1/\sigma^{4}_{1})\ln(SH/\epsilon))$ with $\epsilon$ being the
optimality threshold. This allows us to compete against the globally optimal
policy without paying an exponential dependence on $H$.

Observable Linear Quadratic Gaussian (LQG).  In observable LQG – a classic
partial observable linear dynamical system, our algorithm can compete against
the _globally optimal policy_ with a sample complexity scaling polynomially
with respect to the horizon, dimensions of the state, observation, and action
spaces (and other system parameters). This is achieved by simply setting the
memory length $M$ to $H$. The special linear structures of the problem allow
us to avoid exponential dependence on $H$ even when using the full history as
a memory. While the global optimality results in tabular POMDPs and LQG exist
by using different algorithms, _to the best of our knowledge, this is the
first unified algorithm that can solve both tabular POMDPs and LQG
simultaneously without paying an exponential dependence on horizon $H$._

Observable Hilbert Space Embedding POMDPs (HSE-POMDPs). Our framework ensures
the agnostic PAC guarantee on HSE-POMDPs where policy induced transitions and
omission distributions have condition mean embeddings [boots2011closing,
boots2013hilbert]. This model naturally generalizes tabular POMDPs and LQG. We
show that the sample complexity scales polynomially with respect to the
dimensions of the embeddings. This is the _first_ PAC guarantee in HSE-POMDPs.

Predictive State Representations (PSRs). We give the _first_ PAC-guarantee on
PSRs. PSRs model partially observable dynamical systems without even using the
concept of latent states and strictly generalize the POMDP model. Our work
significantly generalizes a prior PAC learning result for reactive PSRs (i.e.,
reactive PSRs require a strong condition that the optimal policy only depends
on the latest observation) which is a much more restricted setting
[jiang2017contextual].

$M$-step decodable POMDPs [efroni2022provable]. Our framework can capture
$M$-step decodable POMDPs where there is a (unknown) decoder that can
perfectly decode the latent state by looking at the latest $M$-memory. Our
algorithm can compete against the globally optimal policy with the sample
complexity scaling polynomially with respect to horizon $H$, $S,A^{M}$, and
the statistical complexities of function classes, without any explicit
dependence on $O$. This PAC result is similar with the one from
[efroni2022provable].

Observable POMDPs with low-rank latent transition. Our framework captures
observable POMDPs where the latent transition is low-rank. This is the _first_
PAC guarantee in this model. Under this model, we first show that with
$M=\tilde{O}\left((1/\sigma_{1}^{4})\ln(dH/\epsilon)\right)$ where $d$ is the
rank of the latent transition matrix, there exists an $M$-memory policy that
is $\epsilon$-near optimal with respect to the globally optimal policy. Then,
starting with a general model class that contains the ground truth transition
and omission distribution (i.e., realizability in model class), we first
convert the model class to a policy class and a value link function class, and
we then show that our algorithm competes against the globally optimal policy
with a sample complexity scaling polynomially with respect to
$H,d,|\mathcal{A}|^{(1/\sigma_{1}^{4})\ln(dH/\epsilon)},1/\sigma_{1}$, and the
statistical complexity of the model class. Particularly, the sample complexity
has no explicit dependence on the size of the state and observation space,
instead it just depends on the statistical complexity of the given model
class.

Model |  | Observable
---
tabular POMDPs
| Observable
---
LQG
| Low-rank $M$-step
---
decodable POMDPs
| Observable
---
HSE-POMDPs
| PSRs
---
| Low rank
---
observable POMDPs
PO-Bilinear Rank |  | $(OA)^{M}S(\dagger)$
---
(Can be $S$)
$O(Md^{2}_{a}d^{2}_{s})(\dagger)$ | Rank $(\dagger)$ |  | Feature dimension
---
on $(z,s)$
| $(OA)^{M}\times$
---
# of core tests
Rank ($\dagger$)
PAC Learning | Known | Known | Known | New | New | New

Table 1: Summary of settings that are from PO-Bilinear AC class. The 2nd row
gives the parameters that bound the PO-Bilinear rank. Here $M$ denotes the
length of memory used to define memory-based policies $\pi(\cdot|\bar{z}_{h})$
where $\bar{z}_{h}=(o_{h-M:h},a_{h-M:h-1})$ denotes the $M$-step memory. In
the 3rd row, “known” means that sample-efficient algorithms already exist. “
New” means our result gives the first sample-efficient algorithm. However,
even in “known” case, agnostic guarantees are new; hence, when the policy
class is small, we can gain some benefit. The symbol $\dagger$ means we can
compete with the globally optimal policy without paying an exponential
dependence on horizon $H$. For the tabular case, the PO-bilinear rank can be
improved to $S$ when we use the most general definition (Refer to Section 8.
For LQG, $d_{a}$ and $d_{s}$ are the dimension of action and state spaces. For
PSRs, $O$ and $A$ denote the size of observation and action spaces.

###  1.1 Related Works

##### Generalization and function approximation of RL in MDPs.

In Markovian environments, there is a growing literature that gives PAC bounds
with function approximation under certain models. Some of the representative
models are linear MDPs [jin2020provably, yang2020reinforcement], block MDPs
[du2019provably, misra2020kinematic, zhang2022efficient], and low-rank MDPs
[agarwal2020flambe, uehara2021representation]. Several general frameworks in
[jiang2017contextual, sun2019model, jin2021bellman, foster2021statistical,
du2021bilinear] characterize sufficient conditions for provably efficient RL.
Each above model is captured in these frameworks as a special case. While our
work builds on the bilinear/Bellman rank framework [du2021bilinear,
jiang2017contextual], when we naïvely reduce POMDPs to MDPs, the
bilinear/Bellman rank is $\Theta(A^{H})$. These two frameworks are only shown
applicable to reactive POMDPs where the optimal policy only depends on the
latest observation. However, this assumption makes the POMDP model very
restricted.

##### Online RL for POMDPs.

Prior works [kearns1999approximate, even2005reinforcement] showed $A^{H}$-type
sample complexity bounds for general POMDPs. Exponential dependence can be
circumvented with more structures. First, in the tabular setting, under
observability assumptions, in [azizzadenesheli2016reinforcement, guo2016pac,
jin2020sample, liu2022partially, golowich2022learning], favorable sample
complexities are obtained by leveraging the spectral learning technique
[hsu2012spectral] (see section 1.1 in [jin2020sample] for an excellent
summary). Second, in LQG, which is a partial observable version of LQRs, in
[lale2020regret, simchowitz2020improper], sub-linear regret algorithms are
proposed. These works use random policies for exploration, which is sufficient
for LQG. Since random exploration strategy is not enough for tabular POMDPs,
it is unclear if the existing techniques from LQG can be applied to solve
general POMDPs. Third, the recent work [efroni2022provable] provides a new
model called $M$-step decodable POMDP (when $M=1$, it is Block MDP) with an
efficient algorithm.

Our framework captures _all_ above mentioned POMDP models. In addition, we
propose a new model called HSE-POMDPs which extends prior works on HSE-
HMM[boots2013hilbert] to POMDPs and includes LQG and tabular POMDPs. Our
algorithm delivers the first PAC bound for this model.

Finally, we remark there are several existing POMDP models that it is unclear
whether our framework can capture. The first model is a POMDP [cai2022sample]
where emissions and transitions are modeled by linear mixture models. The
second model is a latent POMDP [kwon2021rl]. We leave it as future works.

##### System identification for uncontrolled partially observable systems.

There is a long line of work on system identification for uncontrolled
partially observable systems, among which the spectral learning based methods
are related to our work [van2012subspace, hsu2012spectral, song2010hilbert,
boots2011closing, hamilton2013modelling, nishiyama2012hilbert,
boots2013hilbert, kulesza2015spectral, hefny2015supervised, sun2016learning].
Informally, these methods leverage the high-level idea that under some
observability conditions, one can use the sufficient statistics of (possibly
multi-step) future observations as a surrogate for the belief states, thus
allowing the learning algorithms to ignore the latent state inference and
completely rely on observable quantities. Our approach shares a similar spirit
in the sense that we use sufficient statistics of future observations to
replace latent states, and our algorithm only relies on observable quantities.
The major difference is that these prior works only focus on passive system
identification for uncontrolled systems, while we need to find a high-
performance policy by actively interacting with the systems for information
acquisition.

##### Reinforcement learning in PSRs.

PSRs [jaeger2000observable, littman2001predictive, singh2004predictive,
boots2011closing, thon2015links] are models that generalize POMDPs. PSRs also
rely on the idea of using the sufficient statistics of multi-step future
observations (i.e., predictive states) to serve as a summary of the history.
Prior works on RL for PSRs [boots2011closing, kulesza2015spectral,
downey2017predictive, li2020efficient, izadi2008point] do not address the
problem of strategic exploration and operate under the assumption that a pre-
collected diverse training dataset is given and the data collection policy is
a blind policy (i.e., it does not depend on history of observations). To our
knowledge, the only existing PAC learning algorithm for PSRs is limited to a
reactive PSR model where the optimal policy depends just on the latest
observation [jiang2017contextual]. Our framework captures standard PSRs models
that are strictly more general than reactive PSRs.

##### Value link functions.

Analogue of value link functions (referred to as bridge functions) are used in
the literature of causal inference (offline contextual bandits)
[miao2018confounding, deaner2018proxy, cui2020semiparametric,
kallus2021causal, mastouri2021proximal, singh2021finite, xu2021deep] and
offline RL with unmeasured confounders [bennett2021, shi2021minimax]. However,
their settings are not standard POMDPs in the sense that their setting is a
POMDP with unmeasured confounders following [tennenholtz2020off]. Our setting
is a standard POMDP without unmeasured confounders. Here, we emphasize that
their setting does _not_ capture our setting. More specifically, by taking
[shi2021minimax] as an example, they require that logged data is generated by
policies that can depend on latent states but cannot depend on observable
states. Thus, their definition of link functions (called as bridge functions)
is not applicable to our setting since the data we use is clearly generated by
policies that depend on observations. Due to this difference, their setting
prohibits us from using future observations, unlike our setting. Finally, we
stress that our work is online, while their setting is offline. Hence, they do
not discuss any methods for exploration.

###  1.2 Organization

In Section 2, we introduce the notation, definition of POMDPs, and our
function-approximation setup such as the policy and value link function class.
In Section 3, we define value link functions and the PO-bilinear actor-citric
class. In Section 4, we give examples that admit PO-bilinear actor-citric
class including observable undercomplete tabular POMDPs, observable
overcomplete tabular POMDPs, observable LQG, and observable HSE-POMDPs. In
Section 5, we give a unified algorithm for the PO-bilinear actor-citric class,
and the sample complexity of the algorithm. We also instantiate this general
result for examples presented in Section 4. In Section 6, we show that PSRs,
which are more general models than POMDPs, also admit PO-bilinear rank
decomposition. In Section 7, we give a more general definition of PO-bilinear
actor-critic class, followed by showing that two additional examples —
$M$-step decodable POMDPs and observable POMDPs with low-rank latent
transition — fall into this general definition (Section 8). Both the examples
use general nonlinear function approximation and their sample complexities do
not explicitly depend on the size of the state and observation spaces, but
only on the statistical complexities of the function classes. As a by-product,
we can refine the sample complexity result in the tabular case in Section 5.
Most of the proofs are deferred to the Appendix.

##  2 Preliminary

$o_{3}$$a_{3}$$o_{4}$$a_{4}$$o_{5}$$a_{5}$$o_{6}$$a_{6}$$\bar{z}_{6}$$z_{5}$
Figure 1: Case with M$=3$. A 3-memory policy determines action $a_{6}$ based
on $\bar{z}_{6}$.

We introduce background for POMDPs here and defer the introduction of PSRs to
Section 6. We consider an episodic POMDP specified by
$\mathcal{M}=\langle{\mathcal{S}},\mathcal{O},\mathcal{A},H,\mathbb{T},\mathbb{O}\rangle$,
where ${\mathcal{S}}$ is the _unobserved_ state space, $\mathcal{O}$ is the
observation space, $\mathcal{A}$ is the action space, $H$ is the horizon,
$\mathbb{T}:{\mathcal{S}}\times\mathcal{A}\to\Delta({\mathcal{S}})$ is the
transition probability, $\mathbb{O}:{\mathcal{S}}\to\Delta(\mathcal{O})$ is
the emission probability, and $r:\mathcal{O}\times\mathcal{A}\to\mathbb{R}$ is
the reward. Here, $\mathbb{T},\mathbb{O}$ are unknown distributions. For
notation simplicity, we consider the time-homogeneous case in this paper;
Extension to the time-inhomogeneous setting is straightforward.

In our work, we consider $M$-memory policies. Let
$\mathcal{Z}_{h}=(\mathcal{O}\times\mathcal{A})^{\min\\{h,M\\}}$ and
$\bar{\mathcal{Z}}_{h}=\mathcal{Z}_{h-1}\times\mathcal{O}$. An element
$z_{h}\in\mathcal{Z}_{h}$ is represented as
$z_{h}=[o_{\max(h-M+1,1):h},a_{\max(h-M+1,1):h}]$, and an element
$\bar{z}_{h}\in\bar{\mathcal{Z}}_{h}$ is represented as
$\bar{z}_{h}=[o_{\max(h-M,1):h},a_{\max(h-M,1):h-1}]$ (thus,
$\bar{z}_{h}=[z_{h-1},o_{h}]$). Figure 1 illustrates this situation. An
$M$-memory policy is defined as $\pi=\\{\pi_{h}\\}_{h=1}^{H}$ where each
$\pi_{h}$ is a mapping from $\bar{\mathcal{Z}}_{h}$ to a distribution over
actions $\Delta(\mathcal{A})$.

In a POMDP, an $M$-memory policy generates the data as follows. Each episode
starts with the initial state $s_{1}$ sampled from some unknown distribution.
At each step $h\in[H]$, from $s_{h}\in{\mathcal{S}}$, the agent observes
$o_{h}\sim\mathbb{O}(\cdot|s_{h})$, executes action
$a_{h}\sim\pi_{h}(\cdot|\bar{z}_{h})$, receives reward $r(s_{h},a_{h})$, and
transits to the next latent state $s_{h+1}\sim\mathbb{T}(\cdot|s_{h},a_{h})$.
Note that the agent does not observe the underlying states but only the
observations $\\{o_{h}\\}_{h\leq H}$. We denote $J(\pi)$ as the value of the
policy $\pi$, i.e., $\mathbb{E}[\sum_{h=1}^{H}r_{h};a_{1:H}\sim\pi]$ where the
expectation is taken w.r.t. the stochasticity of the policy $\pi$, emissions
distribution $\mathbb{O}$ and transition dynamics $\mathbb{T}$.

We define a value function for a policy $\pi$ at step $h$ to be the expected
cumulative reward to go under the policy $\pi$ starting from a
$z\in\mathcal{Z}_{h-1}$ and $s\in{\mathcal{S}}$, i.e.
$V^{\pi}_{h}:\mathcal{Z}_{h-1}\times{\mathcal{S}}\to\mathbb{R}$ where
$V^{\pi}_{h}(z,s)=\mathbb{E}[\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}\mid
z_{h-1}=z,s_{h}=s;a_{h:H}\sim\pi]$. The notation
$\mathbb{E}[\cdot\,;a_{h:H}\sim\pi]$ means the expectation is taken under a
policy $\pi$ from $h$ to $H$. Compared to the standard MDP setting, the
expectation is conditional on not only $s_{h}$ but also $z_{h-1}$ since we
consider $M$-memory policies. The corresponding Bellman equation for
$V^{\pi}_{h}$ is
$V^{\pi}_{h}(z_{h-1},s_{h})=\mathbb{E}\left[r_{h}+V^{\pi}_{h+1}(z_{h},s_{h+1})\mid
z_{h-1},s_{h};a_{h}\sim\pi\right]$.

##### The Actor-critic function approximation setup.

Our goal is to find a near optimal policy that maximizes the policy value
$J(\pi)$ in an online manner. Since any POMDPs can be converted into MDPs by
setting the state at level $h$ to the observable history up to $h$, any off-
the-shelf online provably efficient algorithms for MDPs can be applied to
POMDPs. By defining $\mathcal{H}_{h}$ as the whole history up to step
$h\in[H]$ (i.e., a history $\tau_{h}\in\mathcal{H}_{h}$ is in the form of
$o_{1:h},a_{1:h-1}$) , these naïve algorithms ensure that output policies can
compete against the globally optimal policy
$\pi^{\star}_{\mathrm{gl}}=\mathop{\mathrm{argmax}}_{\pi\in\bar{\Pi}}J(\pi)$
where
$\tilde{\Pi}=\\{\bar{\Pi}_{h}\\},\tilde{\Pi}_{h}=[\mathcal{H}_{h}\to\Delta(\mathcal{A})]$.
However, this conversion results in the error with exponential dependence on
the horizon $H$, which is prohibitively large in the long horizon setting.

Instead of directly competing against the globally optimal policy, we aim for
_agnostic policy learning_ , i.e., compete against the best policy in a given
$M$-memory policy class. Our function approximation setup consists of two
function classes, $(a)$ A policy class $\Pi$ consisting of $M$-memory policies
$\Pi:=\\{\Pi_{h}\\}_{h=1}^{H}$ where
$\Pi_{h}\subset[\bar{\mathcal{Z}}_{h}\to\Delta(\mathcal{A})]$ (i.e., actors),
$(b)$ A set of value link functions
$\mathcal{G}=\\{\mathcal{G}_{h}\\}_{h=1}^{H}$ where
$\mathcal{G}_{h}\subset[\bar{\mathcal{Z}}_{h}\to\mathbb{R}]$, whose role is to
approximate $V^{\pi}_{h}$ (i.e., critics). Our goal is to provide an algorithm
that outputs a policy $\hat{\pi}=\\{\hat{\pi}_{h}\\}$ that has a low excess
risk, where excess risk is defined by $R(\pi):=J(\hat{\pi})-J(\pi^{\star})$
where $\pi^{\star}=\mathop{\mathrm{argmax}}_{\pi\in\Pi}J(\pi)$ is the best
policy in class $\Pi$. To motivate this agnostic setting, $M$-memory policies
are also widely used in practice, e.g., DQN [mnih2013playing] sets $M=4$.
Besides, there are natural examples where $M$-memory policies are close to the
globally optimal policy with $M$ being only polynomial with respect to other
problem dependent parameters, e.g., observable POMDPs [golowich2022planning]
and LQG [lale2020regret, simchowitz2020improper, mania2019certainty]. We will
show the global optimality in these two examples later, without any
exponential dependence on $H$ in the sample complexity.

######  Remark 1 (Limits of existing MDP actor-critic framework).

While general actor-critic framework proposed in MDPs [jiang2017contextual] is
applicable to POMDPs via the naïve POMDP to MDP reduction, it is unable to
leverage any benefits from the restricted policy class. This naïve reduction
(from POMDP to MDP) uses full history and will incur sample complexity that
scales exponentially with respect to the horizon.

Additional notation. Let $[H]=\\{1,\cdots,H\\}$ and $[t]=\\{1,\cdots,t\\}$.
Give a matrix $A$, we denote its pseudo inverse by $A^{\dagger}$ and the
operator norm by $\|A\|$. We define the $\ell_{1}$ norm
$\|A\|_{1}=\max_{x:x\neq 0}\|Ax\|_{1}/\|x\|_{1}$. The outer product is denoted
by $\otimes$. Let $d^{\pi}_{h}(\cdot)\in\bar{Z}_{h}\times{\mathcal{S}}$ be the
marginal distribution at $h$ and $\delta(\cdot)$ be the Dirac delta function.
We denote the policy $\delta(a=a^{\prime})$ by $\mathrm{do}(a^{\prime})$. We
denote a uniform action by $\mathcal{U}(\mathcal{A})$. Given a function class
$\mathcal{G}$, we define
$\|\mathcal{G}\|_{\infty}=\sup_{g\in\mathcal{G}}\|g\|_{\infty}$.

##  3 Value Link Functions and the PO-bilinear Framework

Unlike MDPs, we cannot directly work with value functions $V^{\pi}_{h}(s)$ (or
Q functions) in POMDPs, since they depend on the unobserved state $s$. To
handle this issue, below we first introduce new value link functions by using
future observations, and then discuss the PO-bilinear framework.

###  3.1 Value Link Functions

######  Definition 1 (K-step value link functions).

Fix a set of policies $\pi^{out}=\\{\pi^{out}_{i}\\}_{i=1}^{K}$ where
$\pi^{out}_{i}:\mathcal{O}\to\Delta(\mathcal{A})$. Value link functions
$g^{\pi}_{h}:\mathcal{Z}_{h-1}\times\mathcal{O}^{K}\times\mathcal{A}^{K-1}\to\mathbb{R}$
at step $h\in[H]$ for a policy $\pi$ are defined as the solution to the
following integral equation:

$\displaystyle\forall
z_{h-1}\in\mathcal{Z}_{h-1},s_{h}\in{\mathcal{S}},\qquad\mathbb{E}[g^{\pi}_{h}(z_{h-1},o_{h:h+K-1},a_{h:h+K-2})\mid
z_{h-1},s_{h};a_{h:h+K-2}\sim\pi^{out}]=V^{\pi}_{h}(z_{h-1},s_{h}),$

where the expectation is taken under the policy $\pi^{out}$.

Link functions do not necessarily exist, nor are needed to be unique. At an
intuitive level, K-step value link functions are embeddings of the value
functions onto the observation space, and its existence essentially means that
K-step futures have sufficient information to recover the latent state
dependent value function. The proper choice of $\pi^{out}$ would depend on the
underlying models. For example, we use uniform policy in the tabular case, and
$\delta(a=0)$ in LQG. For notational simplicity, we mostly focus on the case
of $K=1$, though we will also discuss the general case of $K\geq 2$. The
simplified definition for 1-step link functions is provided in the following.
Note that this definition is agnostic to $\pi^{out}$.

######  Definition 2 (1-step value link functions).

One-step value link functions
$g^{\pi}_{h}:\mathcal{Z}_{h-1}\times\mathcal{O}\to\mathbb{R}$ at step
$h\in[H]$ for a policy $\pi$ are defined as the solution to the following
integral equation:

$\displaystyle\forall
z_{h-1}\in\mathcal{Z}_{h-1},s_{h}\in{\mathcal{S}}:\qquad\mathbb{E}[g^{\pi}_{h}(z_{h-1},o_{h})\mid
z_{h-1},s_{h}]=V^{\pi}_{h}(z_{h-1},s_{h}).$ (1)

In Section 4, we will demonstrate the form of the value link function for
various examples. The idea of encoding latent state information using the
statistics of (multi-step) futures have been widely used in learning models of
HMMs [song2010hilbert, hsu2012spectral], PSRs [boots2011closing,
boots2013hilbert, hefny2015supervised, sun2016learning], and system
identification for linear systems [van2012subspace]. Existing provably
efficient (online) RL works for POMDPs elaborate on this viewpoint
[jin2020provably, guo2016pac, azizzadenesheli2016reinforcement]. Compared to
them, the novelty of link functions is that it is introduced to recover _value
functions_ but not _models_. This model-free view differs from the existing
dominant model-based view in online RL for POMDPs. In our setup, we can
control systems if we can recover value functions on the underlying states
even if we fail to identify the underlying model.

###  3.2 The PO-Bilinear Actor-critic Framework for POMDPs

With the definition of value link functions, we are now ready to introduce the
PO-bilinear actor-critic (AC) class for POMDPs. We will focus on the case of
$K=1$ here. Let $\mathcal{G}=\\{\mathcal{G}_{h}\\}_{h=1}^{H}$, where
$\mathcal{G}_{h}\subset[\bar{\mathcal{Z}}_{h}\to\mathbb{R}]$, be a class
consisting of functions that satisfy the following realizability assumption
w.r.t. the policy class $\Pi$.

######  Assumption 1 (Realizability).

We assume that $\mathcal{G}$ is realizable w.r.t. the policy class $\Pi$,
i.e., $\forall\pi\in\Pi,h\in[H]$, there exists _at least one_
$g^{\pi}_{h}\in\mathcal{G}_{h}$ such that $g^{\pi}_{h}$ is a value link
function w.r.t. the policy $\pi$. Note that realizability implicitly requires
the existence of link functions.

We next introduce the PO-Bilinear Actor-critic class. For each level
$h\in[H]$, we first define the Bellman loss:

$\displaystyle\mathrm{Br}_{h}(\pi,g;\pi^{in}):=\mathbb{E}[g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1}):a_{1:h-1}\sim\pi^{in},a_{h}\sim\pi]$

given M-memory policies $\pi=\\{\pi_{h}\\},\pi^{in}=\\{\pi^{in}_{h}\\}$ and
$g=\\{g_{h}\\}$. Letting $g^{\pi}=\\{g^{\pi}_{h}\\}_{h=1}^{H}$ be a link
function for $\pi$, our key observation is that value link functions satisfy

$\displaystyle 0=\mathrm{Br}_{h}(\pi,g^{\pi};\pi^{in})$

for any M memory roll-in policy $\pi^{in}=\\{\pi^{in}_{h}\\}_{h=1}^{H}$, and
any evaluation pair $(\pi,g^{\pi})$. This is an analog of Bellman equations on
MDPs. The above equation tells us that $\mathrm{Br}_{h}(\pi,g;\pi^{in})$ is a
right loss to quantify how much the estimator $g$ is different from
$g^{\pi}_{h}$. When $\mathrm{Br}_{h}(\pi,g;\pi^{in})$ has a low-rank structure
in a proper way, we can efficiently learn a near optimal M memory policy. The
following definition precisely quantifies the low-rank structure that we need
for sample efficient learning.

######  Definition 3 (PO-bilinear AC Class, $K=1$).

The model is a PO-bilinear Actor-critic class of rank $d$ if $\mathcal{G}$ is
realizable, and there exist $W_{h}:\Pi\times\mathcal{G}\to\mathbb{R}^{d}$ and
$X_{h}:\Pi\to\mathbb{R}^{d}$ such that for all
$\pi^{\prime},\pi\in\Pi,g\in\mathcal{G}$ and $h\in[H]$,

  1. 1.

$\mathbb{E}[g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]=\langle
W_{h}(\pi,g),X_{h}(\pi^{\prime})\rangle.$

  2. 2.

$W_{h}(\pi,g^{\pi})=0$ for any $\pi\in\Pi$ and the corresponding value link
function $g^{\pi}\in\mathcal{G}$ .

We define $d$ as the PO-bilinear rank.

While the above definition is enough to capture most of the examples we
discuss later in this work, including undercomplete tabular POMDPs, LQG, HSE-
POMDPs, we provide two useful extensions. The first extension incorporates
discriminators into the framework, which can be used to capture the M-step
decodable POMDPs and POMDPs with low-rank latent transition (see Section 7).
The second extension incorporates multi-step futures, which can be used to
capture overcomplete POMDPs and general PSRs. In the next section, we
introduce the multi-step future version.

###  3.3 PO-bilinear Actor-critic Class with Multi Step Future

In this section, we provide an extension to Definition 3 to incorporate
multiple-step futures (i.e., $K>1$). For simplicity, we assume that
$\pi^{out}=\mathcal{U}(\mathcal{A})$.

The definition is then as follows. The main difference is that we roll out a
policy $\mathcal{U}(\mathcal{A})$, $K-1$ times to incorporate multi-step link
functions. We introduce the notation

$\displaystyle(z_{h-1},o_{h:h+K-1},a_{h:h+K-2})=\bar{z}^{K}_{h}\in\bar{\mathcal{Z}}^{K}_{h}=\mathcal{Z}_{h-1}\times\mathcal{O}^{K}\times\mathcal{A}^{K-1}.$

Then, combining the Bellman equation for state-value functions and the
definition of K-step link functions, we have

$\displaystyle 0$
$\displaystyle=\mathbb{E}[V^{\pi}_{h+1}(z_{h},s_{h+1})+r_{h}-V^{\pi}_{h}(z_{h-1},s_{h})\mid
z_{h-1},s_{h};a_{h}\sim\pi]$
$\displaystyle=\mathbb{E}[g^{\pi}_{h+1}(\bar{z}^{K}_{h+1})\mid
z_{h-1},s_{h};a_{h}\sim\pi,a_{h+1:h+K-1}\sim\mathcal{U}(\mathcal{A})]+\mathbb{E}[r_{h}\mid
z_{h-1},s_{h};a_{h}\sim\pi]$
$\displaystyle-\mathbb{E}[g^{\pi}_{h}(\bar{z}^{K}_{h})\mid
z_{h-1},s_{h};a_{h:h+K-2}\sim\mathcal{U}(\mathcal{A})]$

Thus, by taking expectations further with respect to $(z_{h-1},s_{h})$ (i.e.,
$z_{h-1},s_{h}$ can be sampled from some roll-in policy), we have

$\displaystyle 0$
$\displaystyle=\mathbb{E}[g^{\pi}_{h+1}(\bar{z}^{K}_{h+1});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi,a_{h+1:h+K-1}\sim\mathcal{U}(\mathcal{A})]+\mathbb{E}[r_{h};a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]$
$\displaystyle-\mathbb{E}[g^{\pi}_{h}(\bar{z}^{K}_{h});a_{1:h-1}\sim\pi^{\prime},a_{h:h+K-2}\sim\mathcal{U}(\mathcal{A})].$

Hence, the Bellman loss of a pair $(\pi,g)$ under a roll-in $\pi^{\prime}$
denoted by $\mathrm{Br}_{h}(\pi,g;\pi^{\prime})$ at $h\in[H]$ is defined as

$\displaystyle\mathrm{Br}_{h}(\pi,g;\pi^{\prime})$
$\displaystyle=\mathbb{E}[g_{h+1}(\bar{z}^{K}_{h+1});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi,a_{h+1:h+K-1}\sim\mathcal{U}(\mathcal{A})]+\mathbb{E}[r_{h};a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]$
$\displaystyle-\mathbb{E}[g_{h}(\bar{z}^{K}_{h});a_{1:h-1}\sim\pi^{\prime},a_{h:h+K-2}\sim\mathcal{U}(\mathcal{A})].$

The above is a proper loss function when we use multi-step futures. Here is
the structure we need for $\mathrm{Br}_{h}(\pi,g;\pi^{\prime})$.

######  Definition 4 (PO-bilinear AC Class for POMDPs with multi-step future).

The model is a PO-bilinear class of rank $d$ if $\mathcal{G}$ is realizable
(regarding general K-step link functions), and there exists
$W_{h}:\Pi\times\mathcal{G}\to\mathbb{R}^{d}$ and $X_{h}:\Pi\to\mathbb{R}^{d}$
such that for all $\pi^{\prime},\pi\in\Pi,g\in\mathcal{G}$ and $h\in[H]$,

  1. 1.

We have:

$\displaystyle\mathbb{E}[g_{h+1}(\bar{z}^{K}_{h+1});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi,a_{h+1:h+K-1}\sim\mathcal{U}(\mathcal{A})]+\mathbb{E}[r_{h};a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]$
$\displaystyle-\mathbb{E}[g_{h}(\bar{z}^{K}_{h});a_{1:h-1}\sim\pi^{\prime},a_{h:h+K-2}\sim\mathcal{U}(\mathcal{A})]=\langle
W_{h}(\pi,g),X_{h}(\pi^{\prime})\rangle,$

  2. 2.

$W_{h}(\pi,g^{\pi})=0$ for any $\pi\in\Pi$ and the corresponding value link
function $g^{\pi}$ in $\mathcal{G}$ .

We define $d$ as the PO-bilinear rank.

##  4 Examples of PO-Bilinear Actor-critic Classes

We consider three examples (observable tabular POMDPs, LQG, HSE-POMDPs) that
admit PO-bilinear rank decomposition. Our framework can also capture PSRs and
$M$-step decodable POMDPs, of which the discussions are deferred to Section 6
and Section 8, respectively. We mainly focus on one-step future, i.e., $K=1$,
and briefly discuss extension to $K>1$ in the the tabular case. In this
section, except for LQG, we assume $r_{h}\in[0,1]$ for any $h\in[H]$. All the
missing proofs are deferred to Section B.

###  4.1 Observable Undercomplete Tabular POMDPs

######  Example 1 (Observable undercomplete tabular POMDPs).

Let $\mathbb{O}\in\mathbb{R}^{|\mathcal{O}|\times|{\mathcal{S}}|}$ where the
entry indexed by a pair $(o,s)$ is defined as
$\mathbb{O}_{o,s}=\mathbb{O}(o|s)$. Assume that ${\rm
rank}(\mathbb{O})=|{\mathcal{S}}|$, which we call observability. This requires
undercompletenes $|\mathcal{O}|\geq|{\mathcal{S}}|$.

The following lemma shows that $\mathbb{O}$ being full rank implies the
existence of value link functions.

######  Lemma 1.

For Example 1, there exists a one-step value link function $g^{\pi}_{h}$ for
any $\pi\in\Pi$ and $h\in[H]$.

###### Proof.

Consider any function $f:\mathcal{Z}_{h-1}\times{\mathcal{S}}\to\mathbb{R}$
(thus, this captures all possible $V^{\pi}_{h}$). Denote ${\textbf{1}}(z)$ as
the one-hot encoding of $z$ over $\mathcal{Z}_{h-1}$ (similarly for
${\textbf{1}}(s)$). We have $f(z,s)=\langle
f,{\textbf{1}}(z)\otimes{\textbf{1}}(s)\rangle=\langle
f,{\textbf{1}}(z)\otimes(\mathbb{O}^{\dagger}\mathbb{O}{\textbf{1}}(s))\rangle$,
where we use the assumption that ${\rm rank}(\mathbb{O})=|{\mathcal{S}}|$ and
thus $\mathbb{O}^{\dagger}\mathbb{O}=I$. Then,

$\displaystyle f(z,s)=\langle
f,{\textbf{1}}(z)\otimes(\mathbb{O}^{\dagger}\mathbb{E}_{o\sim
O(s)}{\textbf{1}}(o))\rangle=\mathbb{E}_{o\sim O(s)}\langle
f,{\textbf{1}}(z)\otimes\mathbb{O}^{\dagger}{\textbf{1}}(o)\rangle,$ (2)

which means that the value link function corresponding to $f$ is
$g(z,o):=\langle
f,{\textbf{1}}(z)\otimes\mathbb{O}^{\dagger}{\textbf{1}}(o)\rangle$. ∎

We next show that the PO-Bilinear rank (Definition 3) of tabular POMDPs is
bounded by $|{\mathcal{S}}|(|\mathcal{O}||\mathcal{A}|)^{M}$.

######  Lemma 2.

Assume $\mathbb{O}$ is full column rank. Set the value link function class
$\mathcal{G}_{h}=[\mathcal{Z}_{h-1}\times\mathcal{O}\to[0,C_{\mathcal{G}}]]$
for certain $C_{\mathcal{G}}\in\mathbb{R}$, and policy class
$\Pi_{h}=[\bar{\mathcal{Z}}_{h}\to\Delta(\mathcal{A})]$. Then, the model is a
PO-biliner AC class (Definition 3) with PO-bilinear rank at most
$|{\mathcal{S}}|(|\mathcal{O}||\mathcal{A}|)^{M}$.

Later, we will see that the PO-bilinear rank in the more general definition is
just $|{\mathcal{S}}|$ in Section 7. This fact will result a significant
improvement in terms of the sample complexity, and will result in a sample
complexity that does not incur $|\mathcal{O}|^{M}$.

###  4.2 Observable Overcomplete Tabular POMDPs

We consider overcomplete POMDPs with multi-step futures. The proofs are
deferred to Section B.2. We have the following theorem. This is a
generalization of Lemma 1, i.e., when $K=1$, it is Lemma 1.

######  Lemma 3.

Define a $|{\mathcal{T}}^{K}|\times|{\mathcal{S}}|$-dimensional matrix
$\mathbb{O}^{K}$ whose entry indexed by
$(o_{h:h+K-1},a_{h:h+K-2})\in{\mathcal{T}}^{K}$ and $s_{h}\in{\mathcal{S}}$ is
equal to $\mathbb{P}(o_{h:h+K-1},a_{h:h+K-2}\mid
s_{h};a_{h:h+K-2}\sim\mathcal{U}(\mathcal{A}))$. When this matrix is full-
column rank, K-step link functions with respect to $\mathcal{U}(\mathcal{A})$
exist.

Note a sufficient condition to satisfy the above is that a matrix
$\mathbb{O}^{K}(a^{\prime}_{h:h+K-2})\in\mathbb{R}^{|\mathcal{O}|^{K}\times|{\mathcal{S}}|}$
whose entry indexed by $o_{h:h+K-1}\in\mathcal{O}^{K}$ and
$s_{h}\in{\mathcal{S}}$ is equal to $\mathbb{P}(o_{h:h+K-1}\mid
s_{h};a_{h:h+K-2}=a^{\prime}_{h:h+K-2})$ is full-column rank for certain
$a^{\prime}_{h:h+K-2}\in\mathcal{A}^{K-1}$. It says there is (unknown) action
sequence with length $K$ that retains information about latent states.

We next calculate the PO-bilinear rank. Importantly, this does _not_ depend on
$|\mathcal{A}|^{K}$ and $|\mathcal{O}|^{K}$.

######  Lemma 4.

Set a value link function class
$\mathcal{G}_{h}=[\bar{\mathcal{Z}}^{K}\to[0,C_{\mathcal{G}}]]$ for certain
$C_{\mathcal{G}}\in\mathbb{R}^{+}$ and a policy class
$\Pi_{h}=[\bar{\mathcal{Z}}_{h}\to\Delta(\mathcal{A})]$. Then, the model
satisfies PO-bilinear rank condition with PO-bilinear rank (Definition 4) at
most $|{\mathcal{S}}|(|\mathcal{O}||\mathcal{A}|)^{M}$.

Note that the bilinear rank is still
$|{\mathcal{S}}|(|\mathcal{O}||\mathcal{A}|)^{M}$ (just $|{\mathcal{S}}|$ in
the more general definition in Section 7). Crucially, it does not depend on
the length of futures $K$.

###  4.3 Observable Linear Quadratic Gaussian

The next example is Linear Quadratic Gaussian (LQG) with continuous state and
action spaces. The details are deferred to Section J. Here, we set $M=H-1$ so
that the policy class $\Pi$ contains the globally optimal policy.

######  Example 2 (Linear Quadratic Gaussian (LQG)).

Consider LQG:

$\displaystyle
s^{\prime}=As+Ba+\epsilon,~{}o=Cs+\tau,~{}r=-(s^{\top}Qs+a^{\top}Ra)$

where $\epsilon,\tau$ are Gaussian distribution with mean $0$ and variances
$\Sigma_{\epsilon}$ and $\Sigma_{\tau}$, respectively, and
$s\in\mathbb{R}^{d_{s}},o\in\mathbb{R}^{d_{o}}$, and $a\in\mathbb{R}^{d_{a}}$,
and $Q,R$ are positive definite matrices.

We define the policy class as the linear policy class
$\Pi_{h}=\\{\delta(a_{h}=K_{h}\bar{z}_{h})\mid{}K_{h}\in\mathbb{R}^{|\mathcal{A}|\times
d_{\bar{z}_{h}}})$, where $d_{\bar{z}_{h}}$ is a dimension of
$\bar{z}_{h}\in\bar{\mathcal{Z}}_{h}$. This choice is natural since the
globally optimal policy is known to be linear with respect to the entire
history [bertsekas2012dynamic, Chapter 4]. We define two quadratic features,
$\phi_{h}(z_{h-1},s_{h})=(1,[z^{\top}_{h-1},s^{\top}_{h}]\otimes[z^{\top}_{h-1},s^{\top}_{h}])^{\top}$
with $z_{h-1}\in\mathcal{Z}_{h-1},s_{h}\in{\mathcal{S}}$, and
$\psi_{h}(z_{h-1},o_{h})=(1,[z^{\top}_{h-1},o^{\top}_{h}]\otimes[z^{\top}_{h-1},o^{\top}_{h}])^{\top}$
with $z_{h-1}\in\mathcal{Z}_{h-1},o_{h}\in\mathcal{O}$. We have the following
lemma.

######  Lemma 5 (PO-bilinear rank of observable LQG).

Assume ${\rm rank}(C)=d_{s}$. Then, the following holds:

  * •

For any policy $\pi$ linear in $\bar{z}_{h}$, a one-step value link function
$g^{\pi}_{h}(\cdot)$ exists, and is linear in $\psi_{h}(\cdot)$.

  * •

Letting $d_{\psi_{h}}$ be the dimension of $\psi_{h}$, we set
$\mathcal{G}_{h}=\\{\theta^{\top}\psi_{h}(\cdot)|\theta\in\mathbb{R}^{d_{\psi_{h}}}\\}$
and $\Pi$ being linear in $\bar{z}_{h}$. Then LQG satisfies Definition 3 with
PO-bilinear rank at most $O(\\{1+(H-1)(d_{o}+d_{a})+d_{s}\\}^{2})$

We have two remarks. First, when $\pi^{out}_{t}=\delta(a=0)$, K-step link
functions exist when $[C^{\top},(CA)^{\top},\dots,(CA^{K-1})^{\top}]$ is full
raw rank. This assumption is referred to as observability in control theory
[hespanha2018linear]. Secondly, the PO-bilinear rank scales polynomially with
respect to $H,d_{o},d_{a},d_{s}$ even with $M=H-1$. As we show in Section J,
due to this fact, we can compete against the _globally_ optimal policy with
polynomial sample complexity.

###  4.4 Observable Hilbert Space Embedding POMDPs

We consider HSE-POMDPs that generalize tabular POMDPs and LQG. Proofs here are
deferred to Section B.4. Consider any $h\in[H]$. Given a policy
$\pi_{h}:\bar{\mathcal{Z}}_{h}\to\mathcal{A}$, we define the induced
transition operator $\mathbb{T}_{\pi}=\\{\mathbb{T}_{\pi;h}\\}_{h=1}^{H}$ as
$(z_{h},s_{h+1})\sim\mathbb{T}_{\pi;h}(z_{h-1},s_{h})$, where we have
$o_{h}\sim\mathbb{O}(s_{h}),a_{h}\sim\pi_{h}(\bar{z}_{h}),s_{h+1}\sim\mathbb{T}(s_{h},a_{h})$.
Namely, $\mathbb{T}_{\pi}$ is the transition kernel of some Markov chain
induced by the policy $\pi$. The HSE-POMDP assumes two conditional
distributions $\mathbb{O}(\cdot|s)$ and $\mathbb{T}_{\pi}(\cdot,\cdot|z,s)$
have conditional mean embeddings.

######  Example 3 (HSE-POMDPs).

We introduce features
$\phi_{h}:\mathcal{Z}_{h-1}\times{\mathcal{S}}\to\mathbb{R}^{d_{\phi_{h}}},\psi_{h}:\mathcal{Z}_{h-1}\times\mathcal{O}\to\mathbb{R}^{d_{\psi_{h}}}$.
We assume the existence of the conditional mean embedding operators: (1) there
exists a matrix $K_{h}$ such that for all
$z\in\mathcal{Z}_{h-1},s\in{\mathcal{S}}$,
$\mathbb{E}_{o\sim\mathbb{O}(\cdot|s)}\psi_{h}(z,o)=K_{h}\phi_{h}(z,s)$ and
(2) for all $\pi\in\Pi$, there exists a matrix $T_{\pi;h}$, such that
$\mathbb{E}_{z_{h},s_{h+1}\sim\mathbb{T}_{\pi;h}(z_{h-1},s_{h})}\phi_{h+1}(z_{h},s_{h+1})=T_{\pi;h}\phi_{h}(z_{h-1},s_{h})$.

The existence of conditional mean embedding is a common assumption in prior RL
works on learning dynamics of HMMs, PSRs, [song2009hilbert, boots2013hilbert]
and Bellman complete linear MDPs [zanette2020learning, duan2020minimax,
chowdhury2020no, hao2021sparse]. HSE-POMDPs naturally capture tabular POMDPs
and LQG. For tabular POMDPs, $\psi_{h}$ and $\phi_{h}$ are one-hot encoding
features. In LQG, $\phi_{h}$ and $\psi_{h}$ are quadratic features we define
in Section 4.3. Here for simplicity, we focus on finite-dimensional features
$\phi_{h}$ and $\psi_{h}$. Extension to infinite-dimensional Reproducing
kernel Hilbert Space is deferred to Section B.4.

The following shows the existence of value link functions and the PO-bilinear
rank decomposition.

######  Lemma 6 (PO-bilinear rank of observable HSE-POMDPs).

Assume $K_{h}$ is full column rank (observability), and $V_{h}^{\pi}(\cdot)$
is linear in $\phi_{h}$ for any $\pi\in\Pi,h\in[H]$. Then the following holds.

  * •

A one-step value link function $g^{\pi}_{h}(\cdot)$ exists for any
$\pi\in\Pi,h\in[H]$, and is linear in $\psi_{h}$.

  * •

We set a value function class
$\mathcal{G}_{h}=\\{w^{\top}\psi_{h}(\cdot)|w\in\mathbb{R}^{d_{\psi_{h}}}\\}$,
policy class $\Pi_{h}\subset[\bar{\mathcal{Z}}_{h}\to\Delta(\mathcal{A})]$.
Then HSE-POMDP satisfies Definition 3 with PO-bilinear rank at most
$\max_{h\in[H]}d_{\phi_{h}}$.

The first statement can be verified by noting that when
$V^{\pi}_{h}(\cdot)=\langle\theta_{h},\phi_{h}(\cdot)\rangle$, value link
functions take the following form
$g_{h}^{\pi}(\cdot)=\langle(K^{\dagger}_{h})^{\top}\theta_{h}),\psi_{h}(\cdot)\rangle$
where we leverage the existence of the conditional mean embedding operator
$K_{h}$, and that $K_{h}$ is full column rank (thus
$K_{h}^{\dagger}K_{h}=\mathbb{I}_{d_{\phi_{h}}}$). Note that the PO-bilinear
rank depends only on the dimension of the features $\phi_{h}$ without any
explicit dependence on the length of memory.

##  5 Algorithm and Complexity

In this section, we first give our algorithm followed by a general sample
complexity analysis. We then instantiate our analysis to specific models
considered in Section 4.

###  5.1 Algorithm

Algorithm 1 PaRtially ObserVAble BiLinEar (Provable) # multi-step version is
in Algorithm 2

1: Input: Value class
$\mathcal{G}=\\{\mathcal{G}_{h}\\},\mathcal{G}_{h}\subset[\mathcal{Z}_{h-1}\to\mathbb{R}]$,
Policy class
$\Pi=\\{\Pi_{h}\\},\Pi_{h}\subset[\bar{\mathcal{Z}}_{h-1}\to\mathbb{R}]$,
parameters $m\in\mathbf{N},R\in\mathbb{R}$

2: Initialize $\pi^{0}\in\Pi$

3: Form the first step dataset $\mathcal{D}^{0}=\\{o^{i}\\}_{i=1}^{m}$, with
$o^{i}\sim\mathbb{O}(\cdot|s_{1})$

4: for $t=0\to T-1$ do

5: For any $h\in[H]$, collect $m$ i.i.d tuple as follows:
$(\bar{z}_{h},s_{h})\sim
d^{\pi^{t}}_{h},a_{h}\sim\mathcal{U}(\mathcal{A}),r_{h}=r_{h}(o_{h},a_{h}),s_{h+1}\sim\mathbb{T}(s_{h},a_{h}),o_{h+1}\sim\mathbb{O}(\cdot|s_{h+1})$.

6: Define
$\mathcal{D}^{t}_{h}=\\{(\bar{z}^{i}_{h},a^{i}_{h},r^{i}_{h},o^{i}_{h+1})\\}_{i=1}^{m}$
# note latent state $s$ is not in the dataset

7: Define the Bellman error $\forall(\pi,g)\in\Pi\times\mathcal{G}$,
$\textstyle\sigma^{t}_{h}(\pi,g):=\mathbb{E}_{\mathcal{D}^{t}_{h}}\left[\pi_{h}(a_{h}\mid\bar{z}_{h})|\mathcal{A}|\\{g_{h+1}(\bar{z}_{h+1})+r_{h}\\}-g_{h}(\bar{z}_{h})\right].$

8: Select policy optimistically as follows
$\displaystyle\textstyle(\pi^{t+1},g^{t+1}):=\mathop{\mathrm{argmax}}_{\pi\in\Pi,g\in\mathcal{G}}\mathbb{E}_{\mathcal{D}^{0}}[g_{1}(o)]\quad\mathrm{s.t.}\quad\forall
h\in[H],\forall i\in[t],(\sigma^{i}_{h}(\pi,g))^{2}\leq R.$

9: end for

10: Output: Randomly choose $\hat{\pi}$ from $(\pi_{1},\cdots,\pi_{T})$.

We first focus on the cases where models satisfy the PO-bilinear AC model
(i.e., Definition 3) with finite action and with one-step link function. We
discuss the extension to handle continuous action in Remark 2 and multi-step
link functions at the end of this subsection.

We present our algorithm Provable in Algorithm 1. Note Provable is agnostic to
the form of $X_{h}$ and $W_{h}$. Inside iteration $t$, given the latest
learned policy $\pi^{t}$, we define Bellman error for all pairs $(\pi,g)$
where the Bellman error is averaged over the samples from $\pi^{t}$. Here, to
evaluate the Bellman loss for any policy $\pi\in\Pi$, we use importance
sampling by running $\mathcal{U}(\mathcal{A})$ rather than executing a policy
$\pi$ so that we can reuse samples.222This choice might limit the algorithm to
the case where $\mathcal{A}$ is discrete. However, for examples such as LQG,
we show that we can replace $\mathcal{U}(\mathcal{A})$ by a G-optimal design
over the quadratic polynomial feature of the actions. A pair $(\pi,g)$ that
has a small total Bellman error intuitively means that given the data so far,
$g$ could still be a value link function for the policy $\pi$. Then in the
constrained optimization formulation, we only focus on $(\pi,g)$ pairs whose
Bellman errors are small so far. Among these $(\pi,g)$ pairs, we select the
pair using the principle of optimism in the face of uncertainty. We remark the
algorithm leverages some design choices from the Bilinear-UCB algorithm for
MDPs [du2021bilinear]. The key difference between our algorithm and the
Bilinear-UCB is that we leverage the actor-critic framework equipped with
value link functions to handle partially observability and agnostic learning.

##### With multi-step link functions.

Finally, we consider the case with multi-step futures in Algorithm 2 when
$\pi^{out}=\mathcal{U}(\mathcal{A})$. Recall the notation
$\bar{z}^{K}_{h}=(z_{h-1},o_{h:h+K-1},a_{h:h+K-2})$. The only difference is in
the process of data collection. Particularly, at every iteration $t$, we roll-
in using $\pi^{t}$ to (and include) time step $h-1$, we then roll-out by
switching to $\mathcal{U}(\mathcal{A})$ for $K$ steps.

Algorithm 2 PaRtially ObserVAble BiLinEar (Provable) # multi-step version

1: Input: Value link function class
$\mathcal{G}=\\{\mathcal{G}_{h}\\},\mathcal{G}_{h}\subset[\bar{Z}^{K}_{h}\to\mathbb{R}]$,
Policy class
$\Pi=\\{\Pi_{h}\\},\Pi_{h}\subset[\bar{\mathcal{Z}}_{h}\to\Delta(\mathcal{A})]$,
parameters $m\in\mathbb{N},R\in\mathbb{R}$

2: Define  $\displaystyle
l_{h}(\bar{z}^{K}_{h},a_{h+K-1},r_{h},o_{h+K};\pi,g):=|\mathcal{A}|\pi_{h}(a_{h}\mid\bar{z}_{h})\left(g_{h+1}(\bar{z}^{K}_{h+1})+r_{h}\right)-g_{h}(\bar{z}^{K}_{h}).$

3: Initialize $\pi^{0}\in\Pi$

4: Form the first step dataset
$\mathcal{D}^{0}=\\{\bar{z}^{K;i}_{1}\\}_{i=1}^{m}$ where each $\bar{z}^{K}$
is generated by following $a_{1:K-1}\sim U(\mathcal{A})$ in an i.i.d manner.

5: for $t=0\to T-1$ do

6: for any $h\in[H]$, define the Bellman error
$\displaystyle\sigma^{t}_{h}(\pi,g)=\mathbb{E}_{\mathcal{D}^{t}_{h}}[l_{h}(\bar{z}^{K}_{h},a_{h+K-1},r_{h},o_{h+K};\pi,g)]$
where $\mathcal{D}^{t}_{h}$ means empirical approximation by executing
$a_{1:h-1}\sim\pi^{t},a_{h:h+K-1}\sim\mathcal{U}(\mathcal{A})$ and collecting
$m$ i.i.d tuples.

7: Select policy optimistically as follows (here note
$g=\\{g_{h}\\}_{h=1}^{H}$)
$\displaystyle(\pi^{t+1},g^{t+1}):=\mathop{\mathrm{argmax}}_{\pi\in\Pi,g\in\mathcal{G}}\mathbb{E}_{\mathcal{D}^{0}}[g_{1}(\bar{z}^{K}_{1})]\quad\mathrm{s.t.}\quad\forall
h\in[H],\forall i\in[t],\,\sigma^{i}_{h}(\pi,g)^{2}\leq R.$

8: end for

9: Output: Randomly choose $\hat{\pi}$ from $(\pi_{1},\cdots,\pi_{T})$.

######  Remark 2 (Continuous control).

Algorithms so far implicitly assume the action is finite. However, we can
consider LQG, which has continuous action. By employing a G-optimal design
over actions, our algorithm can handle the continuous action. The discussion
is deferred to Section C.

###  5.2 Sample Complexity

We show a sample complexity result by using reduction to supervised learning
analysis. We begin by stating the following assumption which is ensured by
standard uniform convergence results.

######  Assumption 2 (Uniform Convergence).

Fix $h\in[H]$. Let $\mathcal{D}^{\prime}_{h}$ be a set of $m$ i.i.d tuples
following $(z_{h-1},s_{h},o_{h})\sim
d^{\pi^{t}}_{h},a_{h}\sim\mathcal{U}(\mathcal{A}),s_{h+1}\sim\mathbb{T}(s_{h},a_{h}),o_{h+1}\sim\mathbb{O}(s_{h+1})$.
With probability $1-\delta$,

$\displaystyle\textstyle\sup_{\pi\in\Pi,g\in\mathcal{G}}|(\mathbb{E}_{\mathcal{D}^{\prime}_{h}}-\mathbb{E})[\pi_{h}(a_{h}\mid\bar{z}_{h})|\mathcal{A}|\\{g_{h+1}(\bar{z}_{h+1})+r_{h}\\}-g_{h}(\bar{z}_{h})]|\leq\epsilon_{gen,h}(m,\Pi,\mathcal{G},\delta)$

For $h=1$, we also require

$\sup_{g_{1}\in\mathcal{G}_{1}}|\mathbb{E}_{\mathcal{D}^{\prime}_{1}}[g_{1}(o_{1})]-\mathbb{E}[\mathbb{E}_{\mathcal{D}^{\prime}_{1}}[g_{1}(o_{1})]]|\leq\epsilon_{ini,1}(m,\mathcal{G},\delta).$

######  Remark 3 (Finite function classes).

The term $\epsilon_{gen}$ depends on the statistical complexities of the
function classes $\Pi$ and $\mathcal{G}$. As a simple example, we consider the
case where $\Pi$ and $\mathcal{G}$ are discrete. In this case, we have
$\epsilon_{gen,h}(m,\Pi,\mathcal{G},\delta)=O(\sqrt{\ln(|\Pi||\mathcal{G}|/\delta)/m})$,
and
$\epsilon_{ini,1}(m,\mathcal{G},\delta)=O(\sqrt{\ln(|\mathcal{G}|/\delta)/m})$,
which are standard statistical complexities for discrete function classes
$\Pi$ and $\mathcal{G}$. Achieving this result simply requires standard
concentration and a union bound over all functions in $\Pi,\mathcal{G}$.

Under Assumption 2, when the model is PO-bilinear with rank $d$, we get the
following.

######  Theorem 1 (PAC guarantee of Provable).

Suppose we have a PO-bilinear AC class with rank $d$. Suppose Assumption 2,
$\sup_{\pi\in\Pi}\|X_{h}(\pi)\|\leq B_{X}$ and
$\sup_{\pi\in\Pi,g\in\mathcal{G}}\|W_{h}(\pi,g)\|\leq B_{W}$ for any
$h\in[H].$
By setting
$T=2Hd\ln\left(4Hd\left(\frac{B^{2}_{X}B^{2}_{W}}{\tilde{\epsilon}^{2}_{gen}}+1\right)\right),R=\epsilon^{2}_{gen}$
where

$\displaystyle\textstyle\epsilon_{gen}:=\max_{h}\epsilon_{gen,h}(m,\Pi,\mathcal{G},\delta/(TH+1)),\tilde{\epsilon}_{gen}:=\max_{h}\epsilon_{gen,h}(m,\Pi,\mathcal{G},\delta/H).$

With probability at least $1-\delta$, letting
$\pi^{\star}=\mathop{\mathrm{argmax}}_{\pi\in\Pi}J(\pi^{\star})$, we have

$\displaystyle\textstyle J(\pi^{\star})-J(\hat{\pi})\leq
5\epsilon_{gen}\sqrt{dH^{2}\cdot\ln\left(4Hd\left({B^{2}_{X}B^{2}_{W}}/{\tilde{\epsilon}^{2}_{gen}}+1\right)\right)}+2\epsilon_{ini,1}(m,\mathcal{G},\delta/(TH+1)).$

The total number of samples used in the algorithm is $mTH$.

Informally, when $\epsilon_{gen}\approx\tilde{O}(1/\sqrt{m})$, to achieve
$\epsilon$-near optimality, the above theorem indicates that we just need to
set $m\approx\tilde{O}(1/\epsilon^{2})$, which results a sample complexity
scaling $\tilde{O}(1/\epsilon^{2})$ (since $T$ only scales $\tilde{O}(dH)$).
We give detailed derivation and examples in the next section.

###  5.3 Examples

Hereafter, we show the sample complexity result by using Theorem 1. For
complete results, refer to Section F–K. The result of $M$-step decodable
POMDPs and observable low-rank POMDPs are deferred to Section M.

####  5.3.1 Finite Sample Classes

We first consider the case where the hypothesis class is finite when the class
admits PO-bilinear rank decomposition.

######  Example 4 (Finite Sample Classes).

Consider the case when $\Pi$ and $\mathcal{G}$ are finite and the PO-bilinear
rank assumption is satisfied. When $\Pi$ and $\mathcal{G}$ are infinite
hypothesis classes, $|\mathcal{F}|$ and $|\mathcal{G}|$ are replaced with
their $L^{\infty}$-covering numbers, respectively.

######  Theorem 2 (Sample complexity for discrete $\Pi$ and $\mathcal{G}$
(informal)).

Let $\|\mathcal{G}_{h}\|_{\infty}\leq C_{\mathcal{G}},r_{h}\in[0,1]$ for any
$h\in[H]$ and the PO-bilinear rank assumption holds with PO-biliear rank $d$.
By letting
$|\Pi_{\max}|=\max_{h}|\Pi_{h}|,|\mathcal{G}_{\max}|=\max_{h}|\mathcal{G}_{h}|$,
with probability $1-\delta$, we can achieve
$J(\pi^{\star})-J(\hat{\pi})\leq\epsilon$ when we use samples

$\displaystyle\tilde{O}\left(d^{2}H^{4}\max(C_{\mathcal{G}},1)^{2}|\mathcal{A}|^{2}\ln(|\mathcal{G}_{\max}||\Pi_{\max}|/\delta)\ln^{2}(B_{X}B_{W}/\delta)(1/\epsilon)^{2}\right).$

Here,
$\mathrm{Polylog}(d,H,|\mathcal{A}|,\ln(|\mathcal{G}|),\ln(|\Pi|),\ln(1/\delta),\ln(B_{X}),\ln(B_{W}),\ln(1/\delta),1/\epsilon)$
are omitted.

####  5.3.2 Observable Undercomplete Tabular POMDPs

We start with tabular POMDPs. The details here is deferred to Section H.

######  Example 5 (continues=ex:under_tabular).

In tabular models, recall the PO-bilinear rank is at most
$d=|\mathcal{O}|^{M}|\mathcal{A}|^{M}|{\mathcal{S}}|$. We suppose
$r_{h}\in[0,1]$ for any $h\in[H]$. Assuming $\mathbb{O}$ is full-column rank,
to satisfy the realizability, we set
$\mathcal{G}_{h}=\\{\langle\theta,\mathbf{1}(z)\otimes\mathbb{O}^{\dagger}\mathbf{1}(o)\rangle\mid\|\theta\|_{\infty}\leq
H\\}$ where $\|\mathbb{O}^{\dagger}\|_{1}\leq 1/\sigma_{1}$ and
$\mathbf{1}(z),\mathbf{1}(o)$ are one-hot encoding vectors over
$\mathcal{Z}_{h-1}$ and $\mathcal{O}$, respectively. We set
$\Pi_{h}=[\bar{Z}_{h}\to\Delta(\mathcal{A})]$. Then, the following holds.

######  Theorem 3 (Sample complexity for unrercomplete tabular models
(Informal)).

With probability $1-\delta$, we can achieve
$J(\pi^{\star})-J(\hat{\pi})\leq\epsilon$ when we use samples at most
$\tilde{O}\left(|{\mathcal{S}}|^{2}|\mathcal{A}|^{3M+3}|\mathcal{O}|^{3M+1}H^{6}(1/\epsilon)^{2}(1/\sigma_{1})^{2}\ln(1/\delta)\right).$
Here,
$\mathrm{polylog}(|{\mathcal{S}}|,|\mathcal{O}|,|\mathcal{A}|,H,1/\sigma_{1},\ln(1/\delta))$
are omitted.

Firstly, while the above error incurs $|\mathcal{O}|^{M}|\mathcal{A}|^{M}$, we
will later see in Section 8.2.2 when we use the more general definition of PO-
bilinear AC class and combine a model-based perspective, we can remove
$|\mathcal{O}|^{M}$ from the error bound. The intuition here is that the
statistical complexity still scales with
$|{\mathcal{S}}|^{2}|\mathcal{A}|+|\mathcal{O}||\mathcal{A}|$ and does not
incur $|\mathcal{O}|^{M}$. At the same time, although PO-bilinear rank
currently scales with $|\mathcal{O}|^{M}||\mathcal{A}|^{M}|{\mathcal{S}}|$, we
can show that it can be just $|{\mathcal{S}}|$ with a more refined definition.
Secondly, $\|\mathbb{O}^{\dagger}\|_{1}\leq 1/\sigma_{1}$ can be replaced with
other analogous conditions $\|\mathbb{O}^{\dagger}\|_{2}\leq 1/\sigma_{2}$.
Here, note
$\|\mathbb{O}^{\dagger}\|_{1}=1/\\{\min_{x}\|\mathbb{O}x\|_{1}/\|x\|_{1}\\},\|\mathbb{O}^{\dagger}\|_{2}=1/\\{\min_{x}\|\mathbb{O}x\|_{2}/\|x\|_{2}\\}$.
The reason why we use $1$-norm is to invoke the result [golowich2022planning]
to achieve the near global optimality as in the next paragraph.

##### Near global optimality.

Finally, we consider the PAC guarantee against the globally optimal policy. As
shown in [golowich2022planning], it is enough to set
$M=O((1/\sigma^{4}_{1})\ln(SH/\epsilon))$ to compete with the globally optimal
policy $\pi^{\star}_{\mathrm{gl}}$. Thus we achieve a quasipolynomial sample
complexity when competing against $\pi^{\star}_{\mathrm{gl}}$.

######  Theorem 4 (Sample complexity for undercomplete tabular models
(Informal) — competing against $\pi^{\star}_{\mathrm{gl}}$).

With probability $1-\delta$, we can achieve
$J(\pi^{\star}_{\mathrm{gl}})-J(\hat{\pi})\leq\epsilon$ when we use samples at
most

$\displaystyle\textstyle\mathrm{poly}(|{\mathcal{S}}|,|\mathcal{A}|^{\ln(|{\mathcal{S}}|H/\epsilon)/\sigma^{4}_{1}},|\mathcal{O}|^{\ln(|{\mathcal{S}}|H/\epsilon)/\sigma^{4}_{1}},H,1/\sigma_{1},1/\epsilon,\ln(1/\delta)).$

####  5.3.3 Observable Tabular Overcomplete POMDPs

We consider obvercomplete tabular POMDPs. In this case, the PO-bilinear rank
is at most $|\mathcal{O}|^{M}|\mathcal{A}|^{M}|{\mathcal{S}}|$. We suppose
$r_{h}\in[0,1]$ for any $h\in[H]$. Assuming $\mathbb{O}^{K}$ is full-column
rank, to satisfy the realizability, we set
$\mathcal{G}_{h}=\\{\langle\theta,\mathbf{1}(z)\otimes\\{\mathbb{O}^{K}\\}^{\dagger}\mathbf{1}(t^{K})\rangle\mid\|\theta\|_{\infty}\leq
H\\}$ where $\|\mathbb{O}^{K}\|_{1}\leq 1/\sigma_{1}$ and
$\mathbf{1}(z),\mathbf{1}(t^{K})$ are one-hot encoding vectors over
$\mathcal{Z}_{h-1}$ and $\mathcal{O}^{K}\times\mathcal{A}^{K-1}$,
respectively. We set $\Pi_{h}=[\bar{\mathcal{Z}}_{h}\to\Delta(\mathcal{A})]$.
Then, the following holds.

######  Theorem 5 (Sample complexity for overcomplete tabular models).

With probability $1-\delta$, we can achieve
$J(\pi^{\star})-J(\hat{\pi})\leq\epsilon$ when we use samples at most
$\tilde{O}\left(|{\mathcal{S}}|^{2}|\mathcal{A}|^{3M+K+2}|\mathcal{O}|^{3M+K}H^{6}(1/\epsilon)^{2}(1/\sigma_{1})^{2}\ln(1/\delta)\right).$
Here,
$\mathrm{polylog}(|{\mathcal{S}}|,|\mathcal{O}|,|\mathcal{A}|,H,1/\sigma_{1},\ln(1/\delta))$
are omitted.

When we use K-step futures, in the above theorem, we additionally incur
$|\mathcal{A}|^{K}|\mathcal{O}|^{K}$, which is coming from a naive
parameterization of $\mathcal{G}_{h}$. In Section 8.2.3, we will see that
under the model-based learning perspective (i.e., we parameterize
$\mathbb{T},\mathbb{O}$ first and then construct $\Pi$ and $\mathcal{G}$ using
the model class), we will get rid of the dependence $|\mathcal{O}|^{M+K}$ and
$|\mathcal{A}|^{K}$. This is because the complexity of the model class is
independent of $M$ or $K$ (i.e., number of parameters in
$\mathbb{T},\mathbb{O}$ are
$O(|{\mathcal{S}}|^{2}|\mathcal{A}||\mathcal{O}|)$).

####  5.3.4 Observable LQG

Now let us revisit LQG. The detail here is deferred to Section J. We show that
Provable can compete against the globally optimal policy with polynomial
sample complexity.

######  Example 6 (continues=ex:lqqs).

In LQG, by setting $H=M-1$, we achieve a polynomial sample complexity when
competing against the globally optimal policy $\pi^{\star}_{\mathrm{gl}}$.

######  Theorem 6 (Sample complexity for LQG (informal) – competing against
$\pi^{\star}_{\mathrm{gl}}$).

Consider a linear policy class
$\Pi_{h}=\\{\delta(a_{h}=\bar{K}_{h}\bar{z}_{h})\mid\|\bar{K}_{h}\|\leq\Theta\\}$.
and assume $\max(\|A\|,\|B\|,\|C\|,\|Q\|,\|R\|)\leq\Theta$ and all policies
induce a stable system (we formalize in Section J). With probability
$1-\delta$, we can achieve
$J(\pi^{\star}_{\mathrm{gl}})-J(\hat{\pi})\leq\epsilon$ when we use samples at
most

$\displaystyle\textstyle\mathrm{poly}(H,d_{s},d_{o},d_{a},\Theta,\|C^{\dagger}\|,\ln(1/\delta))\times(1/\epsilon)^{2}.$

####  5.3.5 Observable HSE-POMDPs

Next, we study HSE-POMDPs. The details here is deferred to Section G.

######  Example 7 (continues=ex:linear).

In HSE-POMDPs, PO-bilinear rank is at most $\max_{h}d_{\phi_{h}}$. Suppose
$\|\psi_{h}\|\leq 1$ and
$V^{\pi}_{h}(\cdot)=\langle\theta^{\pi}_{h},\phi_{h}(\cdot)\rangle$ such that
$\|\theta^{\pi}_{h}\|\leq\Theta_{V}$ for any $h\in[H]$. Then, to satisfies the
realizability, we set
$\mathcal{G}_{h}=\\{\langle\theta,\psi_{h}(\cdot)\rangle\mid\|\theta\|\leq\Theta_{V}/\sigma_{\min}(K)\\}$
where $\sigma_{\min}(K)=\min_{h\in[H]}1/\|K^{\dagger}_{h}\|$.

######  Theorem 7 (Sample complexity for HSE-POMDPs (Informal)).

Let
$d_{\psi}=\max_{h}\\{d_{\psi_{h}}\\},d_{\phi}=\max_{h}\\{d_{\psi_{h}}\\},|\Pi_{\max}|=\max_{h}(|\Pi_{h}|)$.
Suppose $r_{h}$ lies in $[0,1]$ for any $h\in[H]$. Then, with probability
$1-\delta$, we can achieve $J(\pi^{\star})-J(\hat{\pi})\leq\epsilon$ when we
use samples

$\displaystyle\textstyle\tilde{O}\left(d^{2}_{\phi}H^{4}|\mathcal{A}|^{2}\max(\Theta_{V},1)^{2}\\{d_{\psi}+\ln(|\Pi_{\max}|/\delta)\\}{(1/\sigma_{\min}(K))^{2}}\cdot(1/\epsilon)^{2}\right).$

Here,
$\mathrm{polylog}(d_{\phi},d_{\psi},|\mathcal{A}|,\Theta_{V},\ln(|\Pi_{\max}|),1/\sigma_{\min}(K),1/\epsilon,\ln(1/\delta),\sigma_{\max}(T),\sigma_{\max}(K))$
are omitted and
$\sigma_{\max}(K)=\max_{h\in[H]}\|K_{h}\|,\sigma_{\max}(T)=\max_{\pi\in\Pi,h\in[H]}\|T_{\pi:h}\|$.

Note that the sample complexity above does not explicitly depend on the memory
length $M$, instead it only explicitly depends on the dimension of the
features $\phi,\psi$. In other words, if we have a feature mapping $\psi_{h}$
that can map the entire history (i.e., $M=H$) to a low-dimensional vector
(e.g., LQG), our algorithm can immediately compete against the global
optimality $\pi^{\star}_{\mathrm{gl}}$.

##  6 Predictive State Representations

In this section, we demonstrate that our definition and algorithm applies to
PSRs — models that strictly generalize POMDPs [littman2001predictive,
singh2004predictive]. Below, we first briefly introduce PSRs, followed by
showing that it is a PO-bilinear AC model. Throughout this section, we will
focus on discrete linear PSRs. We also suppose reward at $h$ is deterministic
function of $(o_{h},a_{h})$ conditional on $\tau^{a}_{h+1}$ where
$\tau^{a}_{h}=(o_{1},a_{1},\cdots,o_{h-1},a_{h-1})$. Given $\tau^{a}_{h}$, the
dynamical system generates $o_{h}\sim\mathbb{P}(\cdot|\tau^{a}_{h})$. Here we
use the superscript $a$ on $\tau_{h}^{a}$ to emphasize that the $\tau^{a}_{h}$
ends with the action $a_{h-1}$.

PSRs use the concept of _test_ , which is a sequence of future observations
and actions, i.e., for some test $t=(o_{h:h+W-1},a_{h:h+W-2})$ with length
$W\in\mathbb{N}^{+}$, we define the probability of test $t$ being successful
$\mathbb{P}(t|\tau^{a}_{h})$ as
$\mathbb{P}(t|\tau^{a}_{h}):=\mathbb{P}(o_{h:h+W-1}|\tau^{a}_{h};\text{do}(a_{h:h+W-2}))$
which is the probability of observing $o_{h:h+W-1}$ by actively executing
actions $a_{h:h+W-2}$ conditioned on history $\tau^{a}_{h}$.

We now explain one-step observable PSRs while deferring the general multi-step
observable setting to Section D. A one-step observable PSR uses the
observations in $\mathcal{O}$ as tests, i.e., tests with length 1.

######  Definition 5 (Core test set and linear PSRs).

A core test set ${\mathcal{T}}\subset\mathcal{O}$ contains a finite number of
tests (i.e., observations from $\mathcal{O}$). For any $h$, any history
$\tau^{a}_{h}$, any future test $t_{h}=(o_{h:h+W-1},a_{h:h+W-2})$ for any
$W\in\mathbb{N}^{+}$, there exists a vector
$m_{t_{h}}\in\mathbb{R}^{|{\mathcal{T}}|}$, such that the probability of
$t_{h}$ succeeds conditioned on $\tau^{a}_{h}$ can be expressed as:
$\mathbb{P}(t_{h}|\tau^{a}_{h})=m_{t_{h}}^{\top}[\mathbb{P}(o|\tau^{a}_{h})]_{o\in{\mathcal{T}}},$
where we denote ${\bf
q}_{\tau^{a}_{h}}:=[\mathbb{P}(o|\tau^{a}_{h})]_{o\in{\mathcal{T}}}$ as a
vector in $\mathbb{R}^{|{\mathcal{T}}|}$ with entries equal to
$\mathbb{P}(o|\tau^{a}_{h})$ for $o\in{\mathcal{T}}$. The vector ${\bf
q}_{\tau^{a}_{h}}$ is called predictive state.

A core test set ${\mathcal{T}}$ that has the smallest number of tests is
called a _minimum core test set_ denoted as $\mathcal{Q}$. PSRs are strictly
more expressive than POMDPs in that all POMDPs can be embedded into PSRs whose
size of the minimum core tests is at most $|{\mathcal{S}}|$; however, vice
versa does not hold [littman2001predictive]. For example, in observable
undercomplete POMDPs (i.e., $\mathbb{O}$ full column rank) , the observation
set $\mathcal{O}$ can serve as a core test set, but the minimum core test set
$\mathcal{Q}$ will have size $|{\mathcal{S}}|$. Here, we assume we know a core
test set ${\mathcal{T}}$ that contains $\mathcal{Q}$; however, we are agnostic
to which set is the actual $\mathcal{Q}$. In the literature on PSRs, this
setting is often referred to as transform PSRs [boots2011closing,
rosencrantz2004learning].

Now we define a value link function in PSRs. First, given an $M$-memory
policy, define
$\mathcal{V}^{\pi}_{h}(\tau^{a}_{h})=\mathbb{E}[\sum_{t=h}^{H}r_{t}|\tau^{a}_{h};a_{h:H}\sim\pi]$,
i.e., the expected total reward under $\pi$, conditioned on the history
$\tau^{a}_{h}$. Note that our value function here depends on the entire
history.

######  Definition 6 (General value link functions).

Consider an $M$-memory policy $\pi$. One-step general value link functions
$g^{\pi}_{h}:\mathcal{Z}_{h-1}\times{\mathcal{T}}\to\mathbb{R}$ at step
$h\in[H]$ are defined as solutions to

$\displaystyle\mathcal{V}^{\pi}_{h}(\tau^{a}_{h})=\mathbb{E}[g^{\pi}_{h}(z_{h-1},o_{h})\mid\tau^{a}_{h}].$
(3)

This definition is more general than Definition 3 since (3) implies (1) in
POMDPs by setting $\mathcal{O}={\mathcal{T}}$. In PSRs, we can show the
existence of this general value link function.

######  Lemma 7 (The existence of link functions for PSRs).

Suppose ${\mathcal{T}}$ is a core test set. Then, a one-step value link
function $g^{\pi}_{h}$ always exists.

The high-level derivation is as follows. Using the linear PSR property, one
can first show that $\mathcal{V}^{\pi}_{h}(\tau^{a}_{h})$ has a bilinear form
$\mathcal{V}^{\pi}_{h}(\tau^{a}_{h})={\textbf{1}}(z_{h-1})^{\top}\mathbb{J}_{h}^{\pi}{\bf
q}_{\tau^{a}_{h}}$, where ${\textbf{1}}(z)\in\mathbb{R}^{|\mathcal{Z}_{h-1}|}$
denotes the one-hot encoding vector over $\mathcal{Z}_{h-1}$, and
$\mathbb{J}_{h}^{\pi}$ is a $|\mathcal{Z}_{h-1}|\times|{\mathcal{T}}|$ matrix.
Then, given any $\tau^{a}_{h}$ and $o\sim\mathbb{P}(\cdot|\tau^{a}_{h})$, for
some $|\mathcal{Z}_{h-1}|\times|{\mathcal{T}}|$ matrix $\mathbb{J}$, we can
show
$g_{h}(z_{h-1},o):={\textbf{1}}(z_{h-1})^{\top}\mathbb{J}[{\textbf{1}}(t=o)]_{t\in{\mathcal{T}}}$
satisfies the above, where
$[{\textbf{1}}(t=o)]_{t\in{\mathcal{T}}}\in\mathbb{R}^{|{\mathcal{T}}|}$ is a
one-hot encoding vector over ${\mathcal{T}}$ and serves as an unbiased
estimate of ${\bf q}_{\tau^{a}_{h}}$.

Finally, we show that PSR admits PO-bilinear rank decomposition (Definition
3).

######  Lemma 8.

Suppose a core test set ${\mathcal{T}}$ includes a minimum core test set
$\mathcal{Q}$. Set $\Pi_{h}=[\bar{\mathcal{Z}}_{h}\to\Delta(\mathcal{A})]$ and
$\mathcal{G}_{h}=\\{(z_{h-1},o)\mapsto{\textbf{1}}(z_{h-1})^{\top}\mathbb{J}[{\textbf{1}}(t=o)]_{t\in{\mathcal{T}}}\mid\mathbb{J}\in\mathbb{R}^{|\mathcal{Z}_{h-1}|\times|{\mathcal{T}}|}\\}$,
the PO-bilinear rank is at most
$(|\mathcal{O}||\mathcal{A}|)^{M}|\mathcal{Q}|$.

Then, Algorithm 1 is directly applicable to PSRs. Note that here the PO-
bilinear rank, fortunately, rank scales with $|\mathcal{Q}|$ but not
$|{\mathcal{T}}|$. The dependence $(|\mathcal{O}||\mathcal{A}|)^{M}$ comes
from the dimension of the “feature" of memory ${\textbf{1}}(z_{h-1})$. If one
has a compact feature representation
$\phi:\mathcal{Z}_{h-1}\to\mathbb{R}^{d}$, such that
$\mathcal{V}^{\pi}_{h}(\tau^{a}_{h})=\phi(z_{h-1})^{\top}\mathbb{J}^{\pi}_{h}{\bf
q}_{\tau^{a}_{h}}$ is linear with respect to feature $\phi(z_{h-1})$, then the
PO-bilinear rank is $d|\mathcal{Q}|$. This implies that if one has a compact
featurization of memory a priori, one can avoid exponential dependence on $M$.

##### Sample complexity.

We finally brifely mention the sample complexity result. The detail is
deferred to Section K. The sample complexity to satisfy
$J(\pi^{\star})-J(\hat{\pi})\leq\epsilon$ is given as

$\displaystyle\tilde{O}\left(\frac{|\mathcal{O}|^{M}|\mathcal{A}|^{M-1}|\mathcal{Q}|^{2}\max(\Theta,1)H^{4}|\mathcal{A}|^{2}\ln(|\mathcal{G}_{\max}||\Pi_{\max}|/\delta)\ln(\Theta_{W})^{2}}{\epsilon^{2}}\right)$

where $\Theta_{W}$ and $\Theta$ some parameters associated with PSRs. Here,
there is no explicit dependence on $|{\mathcal{T}}|$. Note that in the worst
case, $\ln|\mathcal{G}_{\max}|$ scales as
$O(|\mathcal{Z}_{h-1}||{\mathcal{T}}|)$, and $\ln|\Pi_{\max}|$ scales as
$O(|\mathcal{Z}_{h-1}||\mathcal{O}||\mathcal{A}|)$.

##  7 Generalization of PO-Bilinear AC Class

We extend our previous definition of PO-Bilinear AC framework. We first
present an even more general framework that captures all the previous examples
that we have discussed so far. We then provide two more examples that can be
covered by this framework: (1) $M$-step decodable POMDPs, and (2) observable
POMDPs with low-rank latent transition. Using the result in (2), we can obtain
refined results in the tabular setting compared to the result from Section
5.3.2.

The following is a general PO-Bilinear AC Class. Recall $M(h):=\max(h-M,1)$.
We consider one-step future, i.e., $K=1$, but the extension to $K>1$ is
straightforward. Comparing to Definition 3, we introduce another class of
functions termed as discriminators $\mathcal{F}$ and the loss function $l$.

######  Definition 7 (General PO-Bilinear AC Class).

Consider a tuple $\langle\Pi,\mathcal{G},l,\Pi^{e},\mathcal{F}\rangle$
consisting of a policy class $\Pi$, a function class $\mathcal{G}$, a loss
function $l=\\{l_{h}\\}_{h=1}^{H}$ where
$l_{h}(\cdot;f,\pi,g):\mathcal{H}_{h-1}\times\mathcal{O}\times\mathcal{A}\times\mathbb{R}\times\mathcal{O}\to\mathbb{R}$,
a set of estimation policies $\Pi^{e}:=\\{\pi^{e}(\pi):\pi\in\Pi\\}$ where
$\pi^{e}_{h}(\pi):\bar{\mathcal{Z}}_{h}\to\Delta(\mathcal{A})$, and a
discriminator class $\mathcal{F}=\\{\mathcal{F}_{h}\\}$ with
$\mathcal{F}_{h}\subset[\mathcal{H}_{h}\to\mathbb{R}]$. Consider a non-
decreasing function $\zeta:\mathbb{R}^{+}\to\mathbb{R}$ with $\zeta(0)=0$.

The model is a PO-bilinear class of rank $d$ if $\mathcal{G}$ is realizable,
and there exist $W_{h}:\Pi\times\mathcal{G}\to\mathbb{R}^{d}$ and
$X_{h}:\Pi\to\mathbb{R}^{d}$ such that for all
$\pi,\pi^{\prime}\in\Pi,g\in\mathcal{G}$ and $h\in[H]$,

  1. (a)

$|\mathbb{E}[g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1});a_{1:h}\sim\pi]|\leq|\langle
W_{h}(\pi,g),X_{h}(\pi)\rangle|$,

  2. (b)

$\displaystyle\zeta(\max_{f\in\mathcal{F}_{h}}|\mathbb{E}[l_{h}(\tau_{h},a_{h},r_{h},o_{h+1};f,\pi,g);a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim\pi^{e}(\pi^{\prime})]|)\geq|\langle
W_{h}(\pi,g),X_{h}(\pi^{\prime})\rangle|.$

(In $M$-step decodable POMDPs and POMDPs with low-rank latent transition, we
set $\pi^{e}(\pi)=\mathcal{U}(\mathcal{A})$ and in the previous sections, we
set $\pi^{e}(\pi^{\prime})=\pi^{\prime}$. )

  3. (c)

$\max_{f\in\mathcal{F}_{h}}|\mathbb{E}[l_{h}(\tau_{h},a_{h},r_{h},o_{h+1};f,\pi,g^{\pi});a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim\pi^{e}(\pi^{\prime})]|=0$

for any $\pi\in\Pi$ and the corresponding value link function $g^{\pi}$ in
$\mathcal{G}$ .

The first condition states the average Bellman error under $\pi$ is upper-
bounded by the quantity in the bilinear form. The second condition states that
we have a known loss function $l$ that can be used to estimate an upper bound
(up to a non-decreasing transformation $\zeta$) of the value of the bilinear
form. Our algorithm will use the surrogate loss $l(\cdot)$. As we will show,
just being able to estimate an upper bound of the value of the bilinear form
suffices for deriving a PAC algorithm. The discriminator $\mathcal{F}$ and the
non-decreasing functions $\zeta$ give us additional freedom to design the loss
function. For simple examples such as tabular POMDPs and LQG, as we already
see, we simply set the discriminator class $\mathcal{F}=\emptyset$ (i.e., we
do not use discriminators) and $\zeta$ being the identity mapping.

With this definition, we slightly modify Provable to incorporate the
discriminator to construct constraints. The algorithm is summarized in
Algorithm 3 that is named as DisProvable. There are two modifications: (1)
when we collect data, we switch from the roll-in policy $\pi^{t}$ to the
policy $\pi^{e}$ at time step $M(h)$; (2) the Bellman error constraint
$\sigma^{t}_{h}$ is defined using the loss $l$ together with the discriminator
class $\mathcal{F}_{h}$.

Algorithm 3 PaRtially ObserVAble BiLinEar with DIScriminators (DisProvable)

1: Input: Value link function class
$\mathcal{G}=\\{\mathcal{G}_{h}\\},\mathcal{G}_{h}\subset[\bar{\mathcal{Z}}_{h}\to\mathbb{R}]$,
discriminator class
$\mathcal{F}=\\{\mathcal{F}_{h}\\},\mathcal{F}_{h}\subset[\mathcal{H}_{h}\to\mathbb{R}]$,
policy class
$\Pi=\\{\Pi_{h}\\},\Pi_{h}\subset[\bar{\mathcal{Z}}_{h}\to\Delta(\mathcal{A})]$,
parameters $m\in\mathbb{N},R\in\mathbb{R}$

2: Initialize $\pi^{0}\in\Pi$

3: Form the first step dataset $\mathcal{D}^{0}=\\{o^{i}\\}_{i=1}^{m}$, with
$o^{i}\sim\mathbb{O}(\cdot|s_{1})$

4: for $t=0\to T-1$ do

5: For any $h\in[H]$, define the Bellman error
$\forall(\pi,g)\in\Pi\times\mathcal{G}:\sigma^{t}_{h}(\pi,g):=\max_{f\in\mathcal{F}_{h}}|\mathbb{E}_{\mathcal{D}^{t}_{h}}\left[l_{h}(\tau_{h},a_{h},r_{h},o_{h+1};f,\pi,g)\right]|$
where $\mathcal{D}^{t}_{h}$ is the empirical approximation by executing
$a_{1:M(h)-1}\sim\pi^{t},a_{M(h):h}\sim\pi^{e}(\pi^{t})$ and collecting $m$
i.i.d tuples.

6: Select policy optimistically as follows
$\displaystyle(\pi^{t+1},g^{t+1}):=\mathop{\mathrm{argmax}}_{\pi\in\Pi,g\in\mathcal{G}}\mathbb{E}_{\mathcal{D}^{0}}[g_{1}(o)]\quad\mathrm{s.t.}\quad\forall
h\in[H],\forall i\in[t],\sigma^{i}_{h}(\pi,g)\leq R.$

7: end for

8: Output: Randomly choose $\hat{\pi}$ from $(\pi_{1},\cdots,\pi_{T})$.

The following theorem shows the sample complexity of Algorithm 3. For
simplicity, we direct consider the case where $\Pi,\mathcal{G},\mathcal{F}$
are all discrete.

######  Assumption 3 (Uniform Convergence).

Fix $h\in[H]$. Let $\mathcal{D}^{\prime}_{h}$ be a set of $m$ i.i.d tuples by
executing $a_{1:M(h)-1}\sim\pi^{t},a_{M(h):h}\sim\pi^{e}$ With probability
$1-\delta$,

$\displaystyle\textstyle\sup_{\pi\in\Pi,g\in\mathcal{G},f\in\mathcal{F}}|(\mathbb{E}_{\mathcal{D}^{\prime}_{h}}-\mathbb{E})[l_{h}(\tau_{h},a_{h},r_{h},o_{h+1};f,\pi,g)]|\leq\epsilon_{gen,h}(m,\Pi,\mathcal{G},\mathcal{F},\delta)$

For $h=1$, we also require

$\sup_{g_{1}\in\mathcal{G}_{1}}|\mathbb{E}_{\mathcal{D}^{\prime}_{1}}[g_{1}(o_{1})]-\mathbb{E}[\mathbb{E}_{\mathcal{D}^{\prime}_{1}}[g_{1}(o_{1})]]|\leq\epsilon_{ini,1}(m,\mathcal{G},\delta).$

######  Theorem 8 (Sample complexity of Algorithm 3).

Suppose we have a PO-bilinear AC class with rank $d$ in Definition 7. Suppose
Assumption 3, $\sup_{\pi\in\Pi}\|X_{h}(\pi)\|\leq B_{X}$ and
$\sup_{\pi\in\Pi,g\in\mathcal{G}}\|W_{h}(\pi,g)\|\leq B_{W}$ for any
$h\in[H].$
By setting
$T=2Hd\ln\left(4Hd\left(\frac{B^{2}_{X}B^{2}_{W}}{\zeta^{2}(\tilde{\epsilon}_{gen})}+1\right)\right),R=\epsilon_{gen}$
where

$\displaystyle\textstyle\epsilon_{gen}:=\max_{h}\epsilon_{gen,h}(m,\Pi,\mathcal{G},\mathcal{F},\delta/(TH+1)),\tilde{\epsilon}_{gen}:=\max_{h}\epsilon_{gen,h}(m,\Pi,\mathcal{G},\mathcal{F},\delta/H).$

With probability at least $1-\delta$, letting
$\pi^{\star}=\mathop{\mathrm{argmax}}_{\pi\in\Pi}J(\pi^{\star})$, we have

$\displaystyle\textstyle J(\pi^{\star})-J(\hat{\pi})\leq
H^{1/2}\left[4\zeta(\epsilon_{gen})^{2}+2T\zeta(2\epsilon_{gen})^{2}Hd\ln(4Hd(B^{2}_{X}B^{2}_{W}/\zeta^{2}(\tilde{\epsilon}_{gen})+1))\right]^{1/2}+2\epsilon_{ini}.$

The total number of samples used in the algorithm is $mTH$.

This reduces to Theorem 1 when we set $\zeta$ as an identify function and
$\pi^{e}(\pi^{\prime})=\pi^{\prime}$. When $\zeta^{-1}(\cdot)$ is a strongly
convex function, we can gain more refined rate results. For example, when
$\zeta(x)=\sqrt{x}$, i.e., $\zeta^{-1}(x)=x^{2}$, with
$\epsilon_{gen}=O(1/\sqrt{m})$, the above theorem implies a slow sample
complexity rate $1/\epsilon^{4}$. However, by leverage the strong convexity of
the square function $\zeta^{-1}(x):=x^{2}$, a refined analysis can give the
fast rate $1/\epsilon^{2}$. We will see such two examples in the next
sections.

##  8 Examples for Generalized PO-Bilinear AC Class

We demonstrate that our generalized framework captures two models: (1)
$M$-step decodable POMDPs, and (2) observable POMDPs with the latent low-rank
transition. In this section, we assume $r_{h}\in[0,1]$ for any $h\in[H]$.

###  8.1 $M$-step decodable POMDPs

The example we include here is a model that involves nonlinear function
approximation but has a unique assumption on the exact identifiability of the
latent states.

######  Example 8 ($M$-step decodable POMDPs [efroni2022provable]).

There exists an unknown decoder
$\iota_{h}:\bar{\mathcal{Z}}_{h}\to{\mathcal{S}}$, such that for every
reachable trajectory $(s_{1:h},a_{1:h-1},o_{1:h})$, we have
$s_{h}=\iota_{h}(\bar{z}_{h})$ for all $h\in[H]$.

Note that when $M=0$, this model is reduced to the well-known Block MDP model
[du2019provably, misra2020kinematic, zhang2022efficient].

##### Existence of value link functions.

From the definition, using a value function $V^{\pi}_{h}(z_{h-1},s_{h})$ over
$z_{h-1}\in\mathcal{Z}_{h-1},s_{h}\in{\mathcal{S}}$, we can define a value
link function $v^{\pi}_{h}:\mathcal{Z}_{h-1}\times\mathcal{O}\to\mathbb{R}$ as

$\displaystyle
v^{\pi}_{h}(z_{h-1},o_{h})=V^{\pi}_{h}(z_{h-1},\iota_{h}(\bar{z}_{h}))$

since it satisfies

$\displaystyle\mathbb{E}_{o_{h}\sim\mathbb{O}(s_{h})}[v^{\pi}_{h}(z_{h-1},o_{h})\mid
z_{h-1},s_{h}]=\mathbb{E}_{o_{h}\sim\mathbb{O}(s_{h})}[V^{\pi}_{h}(z_{h-1},\iota_{h}(\bar{z}_{h}))\mid
z_{h-1},s_{h}]=V^{\pi}_{h}(z_{h-1},s_{h}).$

This is summarized in the following lemma.

######  Lemma 9 (Existence of link functions in $M$-step decodable POMDPs).

In $M$-step decodable POMDPs, link functions exist.

$M$-step decodable POMDPs showcase the _generality of value link functions_ ,
which not only capture standard observability conditions where future
observations and actions are used to replace belief states (e.g., observable
tabular POMDPs and observable LQG), but also capture a model where history is
used to replace latent states.

##### PO-Bilinear Rank.

Next, we calculate the PO-bilinear rank based on Definition 7. In the tabular
case, we can naïvely obtain the PO-bilinear decomposition with rank
$|\mathcal{O}|^{M}|\mathcal{A}|^{M}|{\mathcal{S}}|$ following Example 1. Here,
we consider the nontabular case where function approximation is used and
$|\mathcal{O}|$ can be extremely large. We define the following Bellman
operator associated with $\pi$ at step $h$:

$\displaystyle\mathcal{B}^{\pi}_{h}:\mathcal{G}\to[\bar{\mathcal{Z}}_{h}\to\mathbb{R}];$
(4)
$\displaystyle\forall\bar{z}_{h}:\left[\mathcal{B}^{\pi}_{h}g\right](\bar{z}_{h}):=\mathbb{E}_{a_{h}\sim\pi(\bar{z}_{h})}\left[r_{h}(\iota_{h}(\bar{z}_{h}),a_{h})+\mathbb{E}_{o_{h+1}\sim\mathbb{O}\circ\mathbb{T}(\iota_{h}(\bar{z}_{h}),a_{h})}[g_{h+1}(\bar{z}_{h+1})]\right].$

Note that above we use the ground truth decoder $\iota_{h}$ to decode from
$\bar{z}_{h}$ to its associated latent state $s_{h}$. The existence of this
Bellman operator $\mathcal{B}^{\pi}_{h}$ is crucially dependent on the
existence of such decoder $\iota_{h}$.

We show that $M$-step decodable POMDPs satisfy the definition in Definition 7.
We assume that the latent state-wise transition model is low-rank. In MDPs,
this assumption is widely used in [yang2020reinforcement, jin2020provably,
agarwal2020flambe, uehara2021representation]. Here, we do _not_ need to know
$\mu,\phi$ in the algorithm.

######  Assumption 4 (Low-rankness of latent transition).

Suppose $\mathbb{T}$ is low-rank, i.e., $\mathbb{T}(s^{\prime}\mid
s,a)=\langle\phi(s,a),\mu(s^{\prime})\rangle(\forall(s,a,s^{\prime}))$ where
$\phi,\mu$ are (unknown) $d$-dimensional features. As technical conditions, we
suppose $\|\phi(s,a)\|\leq 1$ for any $(s,a)$ and
$|\int\mu(s)v(s)d(s)|\leq\sqrt{d}$ for any $\|v\|_{\infty}\leq 1$.

######  Lemma 10 (Bilinear decomposition of low-rank $M$-step decodable POMDPs
).

Suppose Assumption 4, $\|\mathcal{G}_{h}\|_{\infty}\leq
H,\|\mathcal{F}_{h}\|_{\infty}\leq H$, $r_{h}\in[0,1]$ for any $h\in[H]$.
Assume a discriminator class is Bellman complete, i.e.,

$\forall\pi\in\Pi,\forall
g\in\mathcal{G}:(\mathcal{B}^{\pi}_{h}g)-g_{h}\in\mathcal{F}_{h},$

for any $h\in[H]$. The loss function is designed as

$\displaystyle
l_{h}(\tau_{h},a_{h},r_{h},o_{h+1};f,\pi,g):=\pi_{h}(a_{h}\mid\bar{z}_{h})|\mathcal{A}|f(\bar{z}_{h})(g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1}))-0.5f(\bar{z}_{h})^{2}.$
(5)

Then, there exist $W_{h}(\pi,g),X_{h}(\pi^{\prime})$ so that the PO-bilinear
rank is at most $d$ such that

$\displaystyle|\mathbb{E}[g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1}):a_{1:h}\sim\pi]|=|\langle
W_{h}(\pi,g),X_{h}(\pi)\rangle|,$ (6)
$\displaystyle\left\lvert\max_{f\in\mathcal{F}_{h}}\mathbb{E}[l_{h}(\tau_{h},a_{h},r_{h},o_{h+1};f,\pi,g);a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim\mathcal{U}(\mathcal{A})]\right\rvert\geq\frac{0.5\langle
W_{h}(\pi,g),X_{h}(\pi^{\prime})\rangle^{2}}{|\mathcal{A}|^{M}},$ (7)

and

$\displaystyle\left\lvert\max_{f\in\mathcal{F}_{h}}\mathbb{E}[l_{h}(\tau_{h},a_{h},r_{h},o_{h+1};f,\pi,g^{\pi});a_{1:M(h)-1}\sim\pi^{\prime},a_{M(h):h}\sim\mathcal{U}(\mathcal{A})]\right\rvert=0.$
(8)

###### Proof.

The proof is deferred to Section N.2. Note that (6), (7), (8) correspond to
(a), (b), (c) in Definition 7. ∎

We use the most general bilinear class definition from Definition 7, where
$\zeta(a)=|\mathcal{A}|^{M/2}a^{1/2}$ for scalar $a\in\mathbb{R}^{+}$. Hence
$\zeta$ is a non-decreasing function ($\zeta$ is non-decreasing in
$\mathbb{R}^{+}$). The proof of the above lemma leverages the novel trick of
the so-called moment matching policy introduced by [efroni2022provable]. When
the latent state and action space are discrete, it states that the bilinear
rank is $|{\mathcal{S}}||\mathcal{A}|$, which is much smaller than
$|\mathcal{O}|^{M}|\mathcal{A}|^{M}|{\mathcal{S}}|$. Note we here introduce
$-0.5f(\bar{z}_{h})^{2}$ in the loss function (5) to induce strong convexity
w.r.t $f$ as in [uehara2021finite, DikkalaNishanth2020MEoC,
chen2019information], which is important to obtain the fast rate later.

The concrete sample complexity of Provable (Algorithm 3) for this model is
summarized in the following. Recall that the bilinear rank is $d$ where $d$ is
the rank of the transition matrix. We set
$\mathcal{G}_{h}\subset[\bar{\mathcal{Z}}_{h}\to[0,H]]$. Then, we have the
following result.

######  Theorem 9 (Sample complexity for $M$-step decodable POMDPs
(Informal)).

Suppose Assumption 4, Bellman completeness, $\|\mathcal{G}_{h}\|_{\infty}\leq
H,\|\mathcal{F}_{h}\|_{\infty}\leq H$, $r_{h}\in[0,1]$ for any $h\in[H]$. With
probability $1-\delta$, we can achieve
$J(\pi^{\star})-J(\hat{\pi})\leq\epsilon$ when we use samples at most

$\displaystyle\tilde{O}\left(\frac{d^{2}H^{6}|\mathcal{A}|^{2+M}\ln(|\Pi_{\max}||\mathcal{F}_{\max}||\mathcal{G}_{\max}|/\delta)}{\epsilon^{2}}\right).$

Here,
$\mathrm{polylog}(d,H,|\mathcal{A}|,1/\epsilon,\ln(|\Pi_{\max}|),\ln(|\mathcal{F}_{\max}|),\ln(|\mathcal{G}_{\max}|),\ln(1/\delta))$
are omitted.

The followings are several implications. First, the error rate scales with
$O(1/\epsilon^{2})$. As we promised, by leveraging the strong convexity of
loss functions, we obtain a rate $O(1/\epsilon^{2})$, which is faster than
$O(1/\epsilon^{4})$ that are attained when we naively invoke Theorem 8 with
$\xi(x)\propto\sqrt{x}$. Secondly, the error bound incurs $|\mathcal{A}|^{M}$.
As showed in [efroni2022provable], this is inevitable in $M$-step decodable
POMDPs. Thirdly, in the tabular case, when we use the naïve function classes
for $\mathcal{G},\mathcal{F},\Pi$, i.e.,
$\mathcal{G}_{h}=\\{\bar{\mathcal{Z}}_{h}\to[0,H]\\}$,
$\mathcal{F}_{h}=\\{\bar{\mathcal{Z}}_{h}\to[0,H]\\}$,
$\Pi_{h}=\\{\bar{\mathcal{Z}}_{h}\to\Delta(\mathcal{A})\\}$, the bound could
incur additional $|\mathcal{O}|^{M}$ since the complexity of the function
classes can scale with respect to $(|\mathcal{O}||\mathcal{A}|)^{M}$ (e.g.,
$\log(|\mathcal{G}_{h}|)$ can be in the order of
$O(|\mathcal{O}|^{M}|\mathcal{A}^{M})$, and similarly for
$\log(|\mathcal{F}_{h}|),\ln(\Pi_{h})$). However, when we start form a
realizable model class that captures the ground truth transition and omission
distribution, we can remove $|\mathcal{O}|^{M}$. See Section 8.2.4 for an
example.

Note that [efroni2022provable] uses a different function class setup where
they assume one has an M memory-action dependent $Q$ function class
$\mathcal{Q}_{h}:\bar{\mathcal{Z}}_{h}\times\mathcal{A}\to\mathbb{R}$ which
contains $Q^{\star}_{h}(\bar{z}_{h},a)$ while we use the actor-critic
framework $v^{\pi}_{h},\pi$. The two function class setups are not directly
comparable. Generally, we mention that such optimal $Q^{\star}$ with truncated
history does not exist when the exact decodability does not hold (e.g., such
$Q^{\star}$ with truncated history does not exist in LQG). This displays the
potential generality of the actor-critic framework we propose here.

###  8.2 Observable POMDPs with Latent Low-rank Transition: a model-based
perspective

The final example we include in this work is a POMDP with the latent low-rank
transition. We first introduce the model, and then we introduce our function
approximation setup and show the sample complexity. Finally, we revisit the
sample complexity for observable tabular POMDPs and $M$-step decodable tabular
POMDPs using the improved algorithm that elaborates on the model-based
approach in this section.

######  Example 9 (Observable POMDPs with latent low-rank transition).

The latent transition $\mathbb{T}(s^{\prime}|s,a)$ is factorized as
$\mathbb{T}(s^{\prime}|s,a)=\mu^{\star}(s^{\prime})^{\top}\phi^{\star}(s,a),\forall
s,a,s^{\prime}$ where $\mu^{\star}:{\mathcal{S}}\to\mathbb{R}^{d}$ and
$\phi^{\star}:{\mathcal{S}}\times\mathcal{A}\to\mathbb{R}^{d}$. The
observation $|\mathcal{O}|\times|{\mathcal{S}}|$ matrix $\mathbb{O}$ has full-
column rank.

In the tabular POMDP example, we have $d\leq|{\mathcal{S}}|$. However in
general $d$ can be much smaller than $|{\mathcal{S}}|$. Note that in this
section, we will focus on the setting where ${\mathcal{S}},\mathcal{O}$ are
discrete to avoid using measure theory languages, but their size could be
extremely large. Particularly, our sample complexity will not have explicit
polynomial or logarithmic dependence on $|\mathcal{O}|,|{\mathcal{S}}|$,
instead it will only scale polynomially with respect to the complexity of the
hypothesis class and the rank $d$.

##### Model-based function approximation.

Our function approximation class consists of a set of models
$\mathcal{M}=\\{(\mu,\phi,O)\\}$ where $\mu,\phi$ together models latent
transition as $\mu(\cdot)^{\top}\phi(s,a)\in\Delta({\mathcal{S}})$, and
$O:{\mathcal{S}}\to\Delta(\mathcal{O})$ models $\mathbb{O}$, and $O$ is full
column rank. For notation simplicity, we often use
$\theta:=(\mu,\phi,O)\in\mathcal{M}$ to denote a model $(\mu,\phi,O)$. We
impose the following assumption.

######  Assumption 5 (Realizability).

We assume realizability, i.e.,
$(\mu^{\star},\phi^{\star},\mathbb{O})\in\mathcal{M}$.

We assume $\mathcal{M}$ is discrete, but $|\mathcal{M}|$ can be large such
that a linear dependence on $|\mathcal{M}|$ in the sample complexity is not
acceptable. Our goal is to get a bound that scales polynomially with respect
to $\ln(|\mathcal{M}|)$, which is the standard statistical complexity of the
discrete hypothesis class $\mathcal{M}$.

Next, we construct $\Pi,\mathcal{G},\mathcal{F}$ using the model class
$\mathcal{M}$. Given $\theta:=(\mu,\phi,O)$, we denote $\pi^{\theta}$ as the
optimal $M$-memory policy, i.e., the $M$-memory policy that maximizes the
total expected reward. We set

$\Pi=\\{\pi^{\theta}:\theta\in\mathcal{M}\\}.$

We consider the value function class for $\theta:=(\mu,\phi,O)$ with $O$ being
full column rank. For each $\theta$, we can define the corresponding value
function of the policy $\pi$ at $h\in[H]$:
$V^{\pi}_{\theta;h}(z_{h-1},s_{h}):\mathcal{Z}_{h-1}\times{\mathcal{S}}\to\mathbb{R}$.
Then, since $O$ is full column rank, as we see in the proof of Lemma 1, a
corresponding value link function is

$\displaystyle g^{\pi}_{\theta;h}(z,o)=\langle
f^{\pi}_{\theta,h},\mathbf{1}(z)\otimes\mathbb{O}^{\dagger}\mathbf{1}(o)\rangle$

where $V^{\pi}_{\theta;h}(z_{h-1},s_{h})=\langle
f^{\pi}_{\theta;h},\mathbf{1}(z)\otimes\mathbf{1}(s)\rangle$. Then, we
construct $\mathcal{G}=\\{\mathcal{G}_{h}\\}$ as:

$\displaystyle\forall
h\in[H]:\;\mathcal{G}_{h}=\\{\bar{\mathcal{Z}}_{h}\ni\bar{z}_{h-1}\mapsto
g^{\pi}_{\theta;h}(\bar{z}_{h-1})\in\mathbb{R}:\pi\in\Pi,\theta\in\mathcal{M}\\}.$
(9)

By construction, since
$\theta^{\star}:=(\mu^{\star},\phi^{\star},\mathbb{O})\in\mathcal{M}$, we must
have $g^{\pi}\in\mathcal{G},\forall\pi\in\Pi$, which implies $\mathcal{G}$ is
realizable (note $g^{\pi}_{h}=g^{\pi}_{\theta^{\star};h}$). Here, from the
construction and the assumption $r_{h}\in[0,1]$ for any $h\in[H]$, we have
$|\mathcal{G}_{h}|\leq|\mathcal{M}|^{2}$ and $\|\mathcal{G}_{h}\|_{\infty}\leq
H/\sigma_{1}$, which can be seen from

$\displaystyle\forall(z,o);\langle f^{\pi}_{\theta;h},\mathbf{1}(z)\otimes
O^{\dagger}\mathbf{1}(o)\rangle\leq\|f^{\pi}_{\theta;h}\|_{\infty}\|\mathbf{1}(z)\otimes
O^{\dagger}\mathbf{1}(o)\|_{1}\leq H\times\|O^{\dagger}\mathbf{1}(o)\|_{1}\leq
H/\sigma_{1}$

by assuming $\|O^{\dagger}\|_{1}\leq 1/\sigma_{1}$ and
$\|f^{\pi}_{\theta;h}\|_{\infty}\leq H$.

To construct a discriminator class $\mathcal{F}$, we first define the Bellman
operator $\mathcal{B}^{\pi}_{\theta;h}$ for
$\pi\in\Pi,h\in[H],\theta\in\mathcal{M}$:

$\displaystyle\mathcal{B}^{\pi}_{\theta;h}:\mathcal{G}\to[\mathcal{H}_{h}\to\mathbb{R}];$
$\displaystyle\forall\tau_{h};\left(\mathcal{B}^{\pi}_{\theta;h}g\right)(\tau_{h})=\mathbb{E}_{a_{h}\sim\pi_{h}(\bar{z}_{h})}\left[r_{h}+\mathbb{E}_{o_{h+1}\sim\mathbb{P}_{\theta}(\cdot|\tau_{h},a_{h})}g_{h+1}(\bar{z}_{h+1})\right],$

where $\mathcal{H}_{h}$ is the whole history space up to $h$
($\tau_{h}=(a_{1:h-1},o_{1:h})$, and $\bar{z}_{h}$ is just part of this
history) and $\mathbb{P}_{\theta}(o_{h+1}|\tau_{h},a_{h})$ is the probability
of generating $o_{h+1}$ conditioned on $\tau_{h},a_{h}$ under model $\theta$.
Then, we construct $\mathcal{F}=\\{\mathcal{F}_{h}\\}$ such that

$\displaystyle\forall
h\in[H]:\mathcal{F}_{h}=\\{\mathcal{H}_{h}\ni\tau_{h}\mapsto\\{g_{h}-\mathcal{B}^{\pi}_{\theta;h}g\\}(\tau_{h})\in\mathbb{R}:\pi\in\Pi,g\in\mathcal{G},\theta\in\mathcal{M}\\}.$
(10)

so that we can ensure the Bellman completeness:

$\displaystyle-(\mathcal{B}^{\pi}_{h}\mathcal{G})+\mathcal{G}_{h}\subset\mathcal{F}_{h}.$

noting $\mathcal{B}^{\pi}_{\theta^{\star};h}=\mathcal{B}^{\pi}_{h}$. Here,
from the construction,
$|\mathcal{F}_{h}|\leq|\mathcal{M}|^{2}\times|\mathcal{M}|^{2}\times|\mathcal{M}|^{2}=|\mathcal{M}|^{6}$
and $\|\mathcal{F}_{h}\|_{\infty}\leq 3H/\sigma_{1}$.

We define the loss as the same as the one we used in $M$-step decodable
POMDPs, except that our discriminators now take the entire history as input:

$\displaystyle
l_{h}(\tau_{h},a_{h},r_{h},o_{h+1};f,\pi,g):=\pi_{h}(a_{h}\mid\bar{z}_{h})|\mathcal{A}|f(\tau_{h})(g_{h}(\bar{z}_{h})-r_{h}-g_{h+1}(\bar{z}_{h+1}))-0.5f(\tau_{h})^{2}.$
(11)

Finally, as in the case of $M$-step decodable POMDPs (Lemma 10), we get the
following lemma that states that our model is a PO-bilinear AC class
(Definition 7) under the following model assumption.

######  Assumption 6.

We assume $\|O^{\dagger}\|_{1}\leq 1/\sigma_{1}$ for any $O$ in the model.
Suppose $\mu(\cdot)^{\top}\phi(s,a)\in\Delta({\mathcal{S}})$ for any $(s,a)$,
$\mu(\cdot)$ and $\phi(\cdot)$ in the model. Suppose $\|\phi(s,a)\|\leq 1$ for
any $\phi$ in the model and $(s,a)\in{\mathcal{S}}\times\mathcal{A}$. Suppose
for any $v:{\mathcal{S}}\to[0,1]$ and for any $\mu$ in the model, we have
$\|\int v(s)\mu(s)\mathrm{d}(s)\|_{2}\leq\sqrt{d}$.

######  Lemma 11 (PO-bilinear decomposition for Observable POMDPs with low-
rank transition).

Suppose Assumption 5, 6. Consider observable POMDPs with latent low-rank
transition. Set $\mathcal{G}$ as in (9), $\mathcal{F}$ as in (10) and $l$ as
in (11). Then, there exist $W_{h}(\pi,g),X_{h}(\pi^{\prime})$ that admits the
PO-bilinear rank decomposition in Definition 7 with rank $d$.

The above lemma ensures that the PO-bilinear rank only depends on $d$, and is
independent of the length of the memory. For example, in the tabular case, it
is $|{\mathcal{S}}|$.

Next, we show the output from DisProvablecan search for the best in class
$M$-memory policy as follows.

######  Theorem 10 (Sample complexity of DisProvable for observable POMDPs
with latent low-rank transition).

Consider observable POMDPs with latent low-rank transition. Suppose Assumption
5, 6. With probability $1-\delta$, we can achieve
$J(\pi^{\star})-J(\hat{\pi})\leq\epsilon$ when we use samples at most

$\displaystyle\tilde{O}\left(\frac{d^{2}H^{6}|\mathcal{A}|^{2+M}\ln(|\mathcal{M}|/\delta)}{\epsilon^{2}\sigma^{2}_{1}}\right).$

Here, we omit
$\mathrm{polylog}(d,H,|\mathcal{A}|,\ln(1/\delta),\ln(|\mathcal{M}|),1/\sigma_{1},1/\epsilon)$.

Here, we emphasize that there is no explicit polynomial or logarithmic
dependence on $|{\mathcal{S}}|$ and $|\mathcal{O}|$, which permits learning
for large state and observation spaces. We also do not have any explicit
polynomial dependence on $|\mathcal{O}|^{M}$, as we construct $\Pi$ and
$\mathcal{G}$ from the model class $\mathcal{M}$ which ensures the
complexities of $\pi$ and $\mathcal{G}$ are in the same order as that of
$\mathcal{M}$.

####  8.2.1 Global Optimality

We show a quasi-polynomial sample complexity bound for competing against the
globally optimal policy $\pi^{\star}_{\text{gl}}$. To compete against the
globally optimal policy $\pi^{\star}_{\mathrm{gl}}$, we need to set $M$
properly. We use the following lemma. The proof is given in Section O.

######  Lemma 12 (Near global optimaltiy of $M$-memoruy policy).

Consider $\epsilon\in(0,H]$, and a POMDP with low-rank latent transition and
$\mathbb{O}$ being full column rank with $\|\mathbb{O}^{\dagger}\|_{1}\leq
1/\sigma_{1}$. When $M=\Theta(C(1/\sigma_{1})^{-4}\ln(dH/\epsilon))$ (with $C$
being some absolute constant), there must exists an $M$-memory policy
$\pi^{\star}$, such that
$J(\pi^{\star}_{\mathrm{gl}})-J({\pi^{\star}})\leq\epsilon$

Note that the memory $M$ above is independent of $|{\mathcal{S}}|$ instead it
only depends on the rank $d$. To prove the above lemma, we first show a new
result on belief contraction for low-rank POMDPs under the $\ell_{1}$-based
observability. The proof of the belief contraction borrows some key lemma from
[golowich2022planning] but extends the original result for small-size tabular
POMDPs to low-rank POMDPs. We leverage the linear structure of the problem and
the G-optimal design to construct an initial distribution over ${\mathcal{S}}$
that can be used as a starting point for belief propagation along the memory.

We conclude the study on the POMDPs with low-rank latent transition by the
following theorem, which demonstrates a quasi-polynomial sample complexity for
learning the globally optimal policy.

######  Theorem 11 (Sample complexity of DisProvable for POMDPs with low-rank
latent transition — competing against $\pi^{\star}_{\mathrm{gl}}$).

Consider observable POMDPs with latent low-rank transition. Fix some
$\epsilon\in(0,H),\delta\in(0,1)$. Suppose Assumption 5, 6. We construct
$\Pi,\mathcal{G},\mathcal{F}$, and the loss $l$ as we described above. With
probability at least $1-\delta$, when
$M=\Theta(C\sigma_{1}^{-4}\ln(dH/\epsilon))$, DisProvable outputs a
$\hat{\pi}$ such that $J(\pi^{\star}_{\mathrm{gl}})-J(\hat{\pi})\leq\epsilon$,
with number of samples scaling

$\tilde{O}\left(\frac{d^{2}H^{6}|\mathcal{A}|^{2}\ln(|\mathcal{M}/\delta|)}{\epsilon^{2}\sigma_{1}^{2}}\cdot|\mathcal{A}|^{\ln(dH/\epsilon)/\sigma_{1}^{4}}\right).$

######  Remark 4 (Comparison to [wang2022embed]).

We compare our results to the very recent work [wang2022embed] that studies
POMDPs with the low-rank latent transition. The results are in general not
directly comparable, but we state several key differences here. First,
[wang2022embed] considers a special instance of low-rank transition, i.e.,
[wang2022embed] assumes $\mathbb{T}$ has low non-negative rank, which could be
exponentially larger than the usual rank [agarwal2020flambe]. Second,
[wang2022embed] additionally assumes _short past sufficiency_ , a condition
which intuitively says that for any roll-in policy, the sufficient statistics
of a short memory is enough to recover the belief over the latent states, and
their sample complexity has an exponential dependence on the length of the
memory. While our result also relies on the fact that the globally optimal
policy can be approximated by an $M$-memory policy with small $M$, this fact
is derived directly from the standard observability condition.

####  8.2.2 Revisiting Observable Undercomplete Tabular POMDPs

We reconsider the sample complexity of undercomplete tabular POMDPs using
Theorem 10. In this case, we will start from a model class that captures the
ground truth latent transition $\mathbb{T}$ and omission distribution
$\mathbb{O}$. By constructing $\epsilon$-nets over the model class,we can set
$\ln(|\mathcal{M}|)=\tilde{O}(|{\mathcal{S}}|^{3}|\mathcal{O}||\mathcal{A}|)$
since $\mathbb{T},\mathbb{O}$ have $|{\mathcal{S}}|^{2}|\mathcal{A}|$ and
$|\mathcal{O}||{\mathcal{S}}|$ many parameters, respectively. Besides, the PO-
bilinear rank is $d=|{\mathcal{S}}|$. Therefore, the sample complexity is

$\displaystyle\tilde{O}\left(\frac{|{\mathcal{S}}|^{5}|\mathcal{O}|H^{6}|\mathcal{A}|^{2+M}\ln(1/\delta)}{\epsilon^{2}\sigma^{2}_{1}}\right).$

We leave the formal analysis to future works.

Compared to results in Section 5.3.2, there is no $|\mathcal{O}|^{M}$ term.
This is due to two improvements. The first improvement is that we refine the
rank from $|\mathcal{O}|^{M}|\mathcal{A}|^{M}|{\mathcal{S}}|$ to
$|{\mathcal{S}}|$. The second improvement is we model the value link function
class and policy class starting from the model class whose complexity has
nothing to do with the length of memory $M$ (note that previously, from a pure
model-free perspective, the statistical complexity of $\mathcal{G}$ can scale
as $|\mathcal{O}|^{M}|\mathcal{A}|^{M}|{\mathcal{S}}|$ in the worst case).

####  8.2.3 Revisiting Observable Overcomplete POMDPs

We reconsider the sample complexity of overcomplete tabular POMDPs using
Theorem 10 with slight modification to incorporate multi-step future. Suppose
$\|\\{\mathbb{O}^{K}\\}^{\dagger}\|_{1}\leq 1/\sigma_{1}$ (recall
$\mathbb{O}^{K}$ is defined in Lemma 3 in Section 4.2). Then, we can achieve a
sample complexity

$\displaystyle\tilde{O}\left(\frac{|{\mathcal{S}}|^{5}|\mathcal{O}|H^{6}|\mathcal{A}|^{2+M}\ln(1/\delta)}{\epsilon^{2}\sigma^{2}_{1}}\right)$

since the PO-bilinear rank is $|{\mathcal{S}}|$. Note that there is no
$|\mathcal{O}|^{M+K}$ dependence, since both the policy class and the value
link function class are built from the model class whose complexity has
nothing to do with $M,K$.

Note that due to our definition of $\mathbb{O}^{K}$, there is no
$|\mathcal{A}|^{K}$ term. However, when we use a different definition, for
instance,
$\min_{a^{\prime}_{h:h+K-2}\in\mathcal{A}^{K-1}}\|\\{\mathbb{O}^{K}(a^{\prime}_{h:h+K-2})\\}^{\dagger}\|_{1}\leq
1/\alpha_{1}$ (recall $\mathbb{O}^{K}(a^{\prime}_{h:h+K-2})$ is defined in
Section 4.2), we would incur $|\mathcal{A}|^{K}$. This is because if we only
know that there is an unknown sequence of actions $a^{\prime}_{h:h+K-2}$ such
that $\mathbb{O}^{K}(a^{\prime}_{h:h+K-2})$ is full column rank, we need to
use uniform samples $|\mathcal{A}|^{K}$ in the importance sampling step to
identify such a sequence. More formally, we can see that

$\displaystyle|\mathcal{A}|^{K}\min_{a^{\prime}_{h:h+K-2}\in\mathcal{A}^{K-1}}\|\\{\mathbb{O}^{K}(a^{\prime}_{h:h+K-2})\\}^{\dagger}\|_{1}\geq\|\\{\mathbb{O}^{K}\\}^{\dagger}\|_{1}.$
(12)

####  8.2.4 Revisiting $M$-step Decodable Tabular POMDPs

We reconsider the sample complexity of tabular $M$-step decodable POMDPs by
constructing $\mathcal{F},\mathcal{G},\Pi$ from the model class $\mathcal{M}$
as we did for the low-rank POMDP. In this case, by constructing
$\epsilon$-nets, we can set
$\ln(|\mathcal{M}|)=\tilde{O}(|{\mathcal{S}}|^{3}|\mathcal{O}||\mathcal{A}|)$
since $\mathbb{T},\mathbb{O}$ have $|{\mathcal{S}}|^{2}|\mathcal{A}|$ and
$|\mathcal{O}||{\mathcal{S}}|$ parameters, respectively. Therefore, the sample
complexity is

$\displaystyle\tilde{O}\left(\frac{H^{6}|{\mathcal{S}}|^{5}|\mathcal{O}||\mathcal{A}|^{2+M}\ln(1/\delta)}{\epsilon^{2}}\right).$

Again, we leave the formal analysis to future works. Compared to the naive
result mentioned after Theorem 9 where $\ln(\mathcal{G}),\ln(\Pi)$ could scale
in the order of $|\mathcal{O}|^{M}$ in the tabular case, we do not have
$|\mathcal{O}|^{M}$ dependence here.

##  9 Summary

We propose a PO-bilinear actor-critic framework that is the first unified
framework for provably efficient RL on large-scale partially observable
dynamical systems. Our framework can capture not only many models where
provably efficient learning has been known such as tabular POMDPs, LQG and
M-step decodable POMDPs, but also models where provably efficient RL is not
known such as HSE-POMDPs, general PSRs and observable POMDPs with low-rank
latent transition. Our unified actor-critic based algorithm—Provable provably
performs agnostic learning by searching for the best memory-based policy. For
special models such as observable tabular MDPs, LQG, and POMDPs with low-rank
latent transition, by leveraging their special properties, i.e., the
exponential stability of Bayesian filters in tabular and low-rank POMDPs, and
existence of a compact featurization of histories in LQG, we are able to
directly compete against the global optimality without paying an exponential
dependence on horizon.

## Acknowledgement

We thank Nan Jiang for valuable discussions on PSRs.

###### Contents

  1. 1 Introduction
    1. 1.1 Related Works
    2. 1.2 Organization
  2. 2 Preliminary
  3. 3 Value Link Functions and the PO-bilinear Framework
    1. 3.1 Value Link Functions
    2. 3.2 The PO-Bilinear Actor-critic Framework for POMDPs
    3. 3.3 PO-bilinear Actor-critic Class with Multi Step Future
  4. 4 Examples of PO-Bilinear Actor-critic Classes
    1. 4.1 Observable Undercomplete Tabular POMDPs
    2. 4.2 Observable Overcomplete Tabular POMDPs
    3. 4.3 Observable Linear Quadratic Gaussian
    4. 4.4 Observable Hilbert Space Embedding POMDPs
  5. 5 Algorithm and Complexity
    1. 5.1 Algorithm
    2. 5.2 Sample Complexity
    3. 5.3 Examples
      1. 5.3.1 Finite Sample Classes
      2. 5.3.2 Observable Undercomplete Tabular POMDPs
      3. 5.3.3 Observable Tabular Overcomplete POMDPs
      4. 5.3.4 Observable LQG
      5. 5.3.5 Observable HSE-POMDPs
  6. 6 Predictive State Representations
  7. 7 Generalization of PO-Bilinear AC Class
  8. 8 Examples for Generalized PO-Bilinear AC Class
    1. 8.1 $M$-step decodable POMDPs
    2. 8.2 Observable POMDPs with Latent Low-rank Transition: a model-based perspective
      1. 8.2.1 Global Optimality
      2. 8.2.2 Revisiting Observable Undercomplete Tabular POMDPs
      3. 8.2.3 Revisiting Observable Overcomplete POMDPs
      4. 8.2.4 Revisiting $M$-step Decodable Tabular POMDPs
  9. 9 Summary
  10. A Supplement for Section 3
  11. B Supplement for Section 4
    1. B.1 Observable Undercomplete Tabular POMDPs
    2. B.2 Observable Overcomplete POMDPs
    3. B.3 Observable Linear Quadratic Gaussian
    4. B.4 Observable HSE-POMDPs
  12. C Supplement for Section 5 (Algorithm for LQG with Continuous Action)
  13. D Supplement for Section 6
    1. D.1 Definition of PSRs
    2. D.2 Existence of link functions
    3. D.3 PO-Bilinear Rank Decomoposition
  14. E Proof of Theorem 1
  15. F Sample Complexity for Finite Function Classes
  16. G Sample Complexity in Observable HSE POMDPs
  17. H Sample Complexity in Observable Undercomplete Tabular POMDPs
  18. I Sample Complexity in Observable Overcomplete Tabular POMDPs
  19. J Sample Complexity in LQG
    1. J.1 Existence of Link Functions
    2. J.2 PO-bilinear Rank Decomposition
    3. J.3 Uniform Convergence
    4. J.4 Sample Complexity
  20. K Sample Complexity in PSRs
    1. K.1 Existence of Link Functions
    2. K.2 PO-bilinear Rank Decomposition
    3. K.3 Sample Complexity
    4. K.4 Most General Case
  21. L Proof of Theorem 8
  22. M Sample Complexity in $M$-step Decodable POMDPs
    1. M.1 PO-bilinear Rank Decomposition (Proof of Lemma 10)
    2. M.2 Uniform Convergence
    3. M.3 Proof of Main Statement
  23. N Sample Complexity in Observable POMDPs with Latent Low-rank Transition
    1. N.1 Existence of Value Link Functions
    2. N.2 PO-bilinear Rank Decomposition (Proof of Lemma 11)
  24. O Exponential Stability for POMDPs with Low-rank Transition
  25. P Auxiliary Lemmas

##  Appendix A Supplement for Section 3

We generalize Definition 3 to capture more models. The first extension is to
use multi-step link functions. This extension is essential to capture
overcomplete POMDPs and multi-step PSRs. The second extension is to use
minimax loss functions with discriminators so that we can use not only
absolute value loss functions but also squared loss functions. This extension
is important to capture M-step decodable POMDPs.

##  Appendix B Supplement for Section 4

###  B.1 Observable Undercomplete Tabular POMDPs

We need to prove Lemma 2. In the tabular case, by setting

$\displaystyle\psi_{h}(z,o)=\mathbf{1}(z)\otimes\mathbf{1}(o),\phi_{h}(z,s)=\mathbf{1}(z)\otimes\mathbf{1}(s),K_{h}=I_{|\mathcal{Z}_{h-1}|}\otimes\mathbb{O}$

where $\mathbf{1}(z),\mathbf{1}(o),\mathbf{1}(s)$ are one-hot encoding vectors
over $\mathcal{Z}_{h-1},\mathcal{O},{\mathcal{S}}$, respectively. Then, we can
regard the tabular model as an HSE-POMDP. We can just invoke Lemma 6.

###  B.2 Observable Overcomplete POMDPs

We consider overcomplete POMDPs with multi-step futures. We have the following
theorem. This is a generalization of Lemma 1.

##### Proof of Lemma 3

Consider any function $f:\mathcal{Z}_{h-1}\times{\mathcal{S}}\to\mathbb{R}$
(thus, this captures all possible $V^{\pi}_{h}$). Denote ${\textbf{1}}(z)$ as
the one-hot encoding of $Z_{h-1}$ (similarly for ${\textbf{1}}(s)$ over
${\mathcal{S}}$ and ${\textbf{1}}(t)$ over ${\mathcal{T}}^{K}$). We have
$f(z,s)=\langle f,{\textbf{1}}(z)\otimes{\textbf{1}}(s)\rangle=\langle
f,{\textbf{1}}(z)\otimes((\mathbb{O}^{K})^{\dagger}\mathbb{O}^{K}{\textbf{1}}(s))\rangle$,
where we use the assumption that ${\rm rank}(\mathbb{O}^{K})=|{\mathcal{S}}|$
and thus $(\mathbb{O}^{K})^{\dagger}\mathbb{O}^{K}=I$. Then,

$\displaystyle f(z_{h-1},s_{h})$ $\displaystyle=\langle
f,{\textbf{1}}(z_{h-1})\otimes(\mathbb{O}^{K})^{\dagger}\mathbb{E}[{\textbf{1}}(o_{h:h+K-1},a_{h:h+K-2})\mid
s_{h};a_{h:h+K-2}\sim\pi^{out}]\rangle$ $\displaystyle=\mathbb{E}[\langle
f,{\textbf{1}}(z_{h-1})\otimes(\mathbb{O}^{K})^{\dagger}{\textbf{1}}(o_{h:h+K-1},a_{h:h+K-2})\rangle\mid
z_{h-1},s_{h};a_{h:h+K-2}\sim\pi^{out}].$

which means that the value bridge function corresponding to $f(\cdot)$ is

$g(z,t):=\langle
f,{\textbf{1}}(z)\otimes(\mathbb{O}^{K})^{\dagger}{\textbf{1}}(t)\rangle.$

$\quad\blacksquare$

##### Proof of Lemma 4

Recall we want to show the low-rank property of the following loss function:

$\displaystyle\mathbb{E}[g_{h+1}(\bar{z}^{K}_{h+1});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi,a_{h+1:h+K-1}\sim\pi^{out}]+\mathbb{E}[r_{h};a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi]$
$\displaystyle-\mathbb{E}[g_{h}(\bar{z}^{K}_{h});a_{1:h-1}\sim\pi^{\prime},a_{h:h+K-1}\sim\pi^{out}].$

We consider an expectation conditioning on $z_{h-1}$ and $s_{h}$. For some
vector
$\theta_{\pi,g}\in\mathbb{R}^{|\mathcal{Z}_{h-1}|\times|{\mathcal{S}}|}$,
which depends on $\pi$, we write it in the form of
$\langle\theta_{\pi,g},{\textbf{1}}(z_{h-1},s_{h})\rangle$ where
${\textbf{1}}(z_{h-1},s_{h})$ is the one-hot encoding vector over
$\mathcal{Z}_{h-1}\times{\mathcal{S}}$. Then, the loss for $(\pi,g)$ is equal
to

$\displaystyle\langle\theta_{\pi,g},\mathbb{E}[{\textbf{1}}(z_{h-1},s_{h});a_{1:h-1}\sim\pi^{\prime}]\rangle.$

Hence, we can take
$X(\pi^{\prime})=\mathbb{E}[{\textbf{1}}(z_{h-1},s_{h});a_{1:h-1}\sim\pi^{\prime}]$
and $W(\pi)=\theta_{\pi,g}$. $\quad\blacksquare$

###  B.3 Observable Linear Quadratic Gaussian

We need to prove Lemma 5. The proof is further deferred to Section J.

###  B.4 Observable HSE-POMDPs

We first provide the proof of Lemma 6. Then, we briefly mention how we extend
to the infinite-dimensional setting.

##### Proof of the first statement in Lemma 6

First, we need to show value bridge functions exist. This is proved noting

$\displaystyle\mathbb{E}_{o\sim\mathbb{O}(s)}[\langle(K^{\dagger}_{h})^{\top}\theta^{\pi}_{h},\psi_{h}(\bar{z}_{h})\rangle]=\langle(K^{\dagger}_{h})^{\top}\theta^{\pi}_{h},K_{h}\phi_{h}(z_{h-1},s_{h})\rangle=\langle\theta^{\pi}_{h},\phi_{h}(z_{h-1},s_{h})\rangle=V^{\pi}_{h}(z_{h-1},s_{h}).$

Thus,
$\langle(K^{\dagger}_{h})^{\top}\theta^{\pi}_{h},\psi_{h}(\bar{z}_{h})\rangle$
is a value bridge function. $\quad\blacksquare$

##### Proof of the second statement in Lemma 6

Consider a triple $(\pi^{\prime},\pi,g)\in\Pi\times\Pi\times\mathcal{G}$, with
$g_{h}(\cdot)=\theta_{h}^{\top}\psi_{h}(\cdot)$ and
$g^{\pi}_{h}=\langle\theta^{\star}_{h},\psi_{h}(\cdot)\rangle$, we have:

$\displaystyle\mathrm{Br}_{h}(\pi,g;\pi^{\prime})$
$\displaystyle=\mathbb{E}\left[\theta_{h}^{\top}\psi(\bar{z}_{h})-r_{h}-\theta_{h+1}^{\top}\psi(\bar{z}_{h+1});a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi\right]$
$\displaystyle=\mathbb{E}\left[\theta_{h}^{\top}K_{h}\phi_{h}(z_{h-1},s_{h})-r_{h}-\theta_{h+1}^{\top}K_{h+1}(\phi_{h+1}(z_{h},s_{h+1}));a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi\right]$
$\displaystyle=\mathbb{E}\left[(\theta_{h}-\theta^{\star}_{h})^{\top}K_{h}\phi_{h}(z_{h-1},s_{h})-(\theta_{h+1}-\theta^{\star}_{h+1})^{\top}K_{h+1}(T_{\pi;h}\phi_{h}(z_{h-1},s_{h}));a_{1:h-1}\sim\pi^{\prime}\right]$
$\displaystyle=\left\langle\mathbb{E}[\phi_{h}(z_{h-1},s_{h});a_{1:h-1}\sim\pi^{\prime}],\quad
K_{h}^{\top}(\theta_{h}-\theta^{\star}_{h})-T_{\pi;h}^{\top}K_{h+1}^{\top}(\theta_{h+1}-\theta^{\star}_{h+1})\right\rangle,$

which verifies the bilinear structure, i.e.,
$X_{h}(\pi^{\prime})=\mathbb{E}[\phi_{h}(z_{h-1},s_{h});a_{1:h-1}\sim\pi^{\prime}]$,
and
$W_{h}(\pi,g)=K_{h}^{\top}(\theta_{h}-\theta^{\star}_{h})-T_{\pi;h}^{\top}K_{h+1}^{\top}(\theta_{h+1}-\theta^{\star}_{h+1})$,
and shows that the bilinear rank is at most
$\max_{h}d_{\psi_{h}}$.$\quad\blacksquare$

##### Infinite dimensional HSE-POMDPs

Consider the case $\phi_{h}$ and $\psi_{h}$ are features in infinite
dimensional RKHS. By assuming that the spectrum of the operator $K_{h}$ is
decaying with a certain order, we can still ensure the existence of value
bridge functions even if $d_{\phi_{h}}$ and $d^{\prime}_{\psi_{h}}$ are
infinite dimensional.

Next, we consider the PO-bilinear rank. We can still use the decomposition in
the proof above. While the PO-bilinear rank itself in the current definition
is infinite-dimensional, when we get the PAC result later, the dependence on
the PO-bilinear rank comes from the information gain based on $X_{h}(\pi)$,
which is the intrinsic dimension of $X_{h}(\pi)$. Thus, we can easily get the
sample complexity result by replacing $d_{\psi_{h}}$ with the information gain
over $\psi_{h}(\cdot)$ [srinivas2009gaussian]. Generally, to take infinite
dimensional models into account, the PO-bilinear rank in Definition 3 can be
generalized using the critical information gain [du2021bilinear].

##  Appendix C Supplement for Section 5 (Algorithm for LQG with Continuous
Action)

In this section, we present a modification to handle LQG with continuous
action in Definition 3.

Our algorithm so far samples $a_{h}$ from $\mathcal{U}(\mathcal{A})$ and
performs importance weighting in designing the loss $\sigma^{t}_{h}$, which
will incur a polynomial dependence on $|\mathcal{A}|$ as we will see in the
next section. However, among the examples that we consider in Section 4, LQG
has continuous action. If we naïvely sample $a_{h}$ from a ball in
$\mathbb{R}^{d_{a}}$ and perform (nonparametric) importance weighting, we will
pay $\exp(d_{a})$ in our sample complexity bound, which is not ideal for high-
dimension control problems. To avoid exponential dependence on $d_{a}$, here
we replace $\mathcal{U}(\mathcal{A})$ with a $d$-optimal design over the
action’s quadratic feature space.

Here, we want to evaluate the Bellman error of $(\pi,g)$ pair under a roll-in
policy $\pi^{\prime}$:

$\displaystyle\mathrm{Br}_{h}(\pi,g;\pi^{\prime}):=\mathbb{E}[u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi(\bar{z}_{h})]$

where
$u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta)=\theta^{\top}_{h}\psi(\bar{z}_{h})-r_{h}(s_{h},a_{h})-\theta^{\top}_{h+1}\psi_{h+1}(\bar{z}_{h+1})$
for any linear deterministic policy $\pi\in\Pi$ (here
$g_{h}(\cdot):=\theta_{h}^{\top}\psi(\cdot)$) using a _single_ policy. In
other words, we would like to get a good loss $l_{h}$ such that

$\displaystyle\mathrm{Br}_{h}(\pi,g;\pi^{\prime})=\mathbb{E}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta,\pi);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi^{e}]$

for some policy $\pi^{e}$ without incuring exponential dependence on $d_{a}$.
We explain how to design such a loss function $l_{h}(\cdot;\pi,g)$ step by
step.

##### First Step

The first step is to consider the conditional expectation on
$(\bar{z}_{h},s_{h},a_{h})$. Here, using the quadratic form of $\psi$, we can
show that there are some
$c_{0}:\bar{Z}_{h}\times{\mathcal{S}}\to\mathbb{R},c_{1}:\bar{Z}_{h}\times{\mathcal{S}}\to\mathbb{R}^{(d_{a}+d_{s}+d_{\bar{z}_{h}})^{2}},c_{2}\in\mathbb{R}$:

$\displaystyle\mathrm{Br}_{h}(\pi,g;\pi^{\prime})$
$\displaystyle=\mathbb{E}[u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta)\mid\bar{z}_{h},s_{h},a_{h};a_{1:h-1}\sim\pi,a_{h}\sim\pi(\bar{z}_{h})]$
$\displaystyle=\langle
c_{2}(\theta),[1,[\bar{z}^{\top}_{h},s^{\top}_{h},a^{\top}_{h}]\otimes[\bar{z}^{\top}_{h},s^{\top}_{h},a^{\top}_{h}]]^{\top}\rangle$
$\displaystyle=c_{0}(\bar{z}_{h},s_{h};\theta)+c^{\top}_{1}(\bar{z}_{h},s_{h};\theta)\kappa(a_{h})$

where $\kappa(a)=[a^{\top},(a\otimes a)^{\top}]^{\top}$. Then, the Bellman
loss we want to evaluate can be written in the form of

$\displaystyle\mathbb{E}[u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi(\bar{z}_{h})]$
$\displaystyle=\mathbb{E}[c_{0}(\bar{z}_{h},s_{h};\theta)+c^{\top}_{1}(\bar{z}_{h},s_{h};\theta)\kappa(\pi(\bar{z}_{h}));a_{1:h-1}\sim\pi^{\prime}].$

##### Second step

The second step is to compute a d-optimal design for the set
$\\{\kappa(a):a\in\mathbb{R}^{d_{a}},\|a\|_{2}\leq Z\\}$ for certain enough
large $Z\in\mathbb{R}$, and denote $a^{1},\dots,a^{d^{\diamond}}$ as the
supports on the d-optimal design. Note in LQG, though we cannot ensure the
action lives in the compact set, we can still ensure that in high probability
and it suffices in our setting as we will see. Since the dimension of $k(a)$
is $d_{a}+d^{2}_{a}$, we can ensure
$d^{\diamond}\leq(d_{a}+d_{a}^{2})(d_{a}+d_{a}^{2}+1)/2$ [lattimore2020bandit,
kiefer1960equivalence]. Here is a concrete theorem we invoke.

######  Theorem 12 (Property of G-optimal design).

Suppose $\mathcal{X}\in\mathbb{R}^{d}$ is a compact set. There exists a
distribution $\rho$ over $\mathcal{X}$ such that:

  * •

$\rho$ is supported on at most $d(d+1)/2$ points.

  * •

For any $x^{\prime}\in\mathcal{X}$, we have
$x^{\prime\top}\mathbb{E}_{x\sim\rho}[xx^{\top}]^{-1}x^{\prime}\leq d$.

We have the following handy lemma stating any $\kappa(a)$ is spanned by
$\\{\kappa(a^{i})\\}_{i=1}^{d^{\diamond}}$.

######  Lemma 13.

Let
$K=[\rho^{1/2}(a^{1})\kappa(a^{1}),\rho^{1/2}(a^{2})\kappa(a^{2}),\cdots,\rho^{1/2}(a^{d^{\diamond}})\kappa(a^{d^{\diamond}})]$
and $\alpha(a)=K^{\top}(KK^{\top})^{-1}k(a)$.  Then, it satisfies

$\kappa(a)=K\alpha(a),\quad\|\alpha(a)\|\leq(d_{a}+d_{a}^{2})^{1/2},\quad\alpha_{i}(a)/\rho^{1/2}(a^{i})\leq(d_{a}+d_{a}^{2})$

###### Proof.

Since $K$ is full-raw rank from the construction of G-optimal design,
$KK^{\top}$ is invertible. Then, we have

$\displaystyle\sum_{i=1}^{d^{\diamond}}\alpha_{i}(a)\rho^{1/2}(a^{i})\kappa(a^{i})=KK^{\top}(KK^{\top})^{-1}\kappa(a)=\kappa(a)$

For the latter statement, we have

$\displaystyle\langle
K^{\top}(KK^{\top})^{-1}k(a),K^{\top}(KK^{\top})^{-1}k(a)\rangle$
$\displaystyle=k(a)^{\top}(KK^{\top})^{-1}k(a)\leq(d_{a}+d_{a}^{2}).$

We use a property of G-optimal design in Theorem 12.

For the last statement, we have

$\displaystyle\kappa^{\top}(a^{i})(KK^{\top})^{-1}\kappa(a)\leq\|\kappa^{\top}(a^{i})\|_{(KK^{\top})^{-1}}\|\kappa^{\top}(a)\|_{(KK^{\top})^{-1}}\leq(d_{a}+d_{a}^{2}).$

from CS inequality. ∎

##### Third Step

The third step is combining current facts. Recall we want to evaluate

$\displaystyle\mathbb{E}[u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi(\bar{z}_{j})]=\mathbb{E}[c_{0}(\bar{z}_{h},s_{h};\theta)+c^{\top}_{1}(\bar{z}_{h},s_{h};\theta)\kappa(\pi(\bar{z}_{h}));a_{1:h-1}\sim\pi^{\prime}].$

In addition, the following also holds:

$\displaystyle\mathbb{E}[u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim
do(a^{i})]$
$\displaystyle=\mathbb{E}[c_{0}(\bar{z}_{h},s_{h};\theta)+c^{\top}_{1}(\bar{z}_{h},s_{h};\theta)\kappa(a^{i});a_{1:h-1}\sim\pi^{\prime}]$
$\displaystyle\mathbb{E}[u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim
do(0)]$
$\displaystyle=\mathbb{E}[c_{0}(\bar{z}_{h},s_{h};\theta);a_{1:h-1}\sim\pi^{\prime}]$

Here, we use $\kappa(0)=0$. This concludes that

$\displaystyle\mathbb{E}[u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim\pi(\bar{z}_{j})]$
$\displaystyle=\mathbb{E}[c_{0}(\bar{z}_{h},s_{h};\theta)+c^{\top}_{1}(\bar{z}_{h},s_{h};\theta)\kappa(\pi(\bar{z}_{h}));a_{1:h-1}\sim\pi^{\prime}]$
$\displaystyle=\mathbb{E}[c_{0}(\bar{z}_{h},s_{h};\theta)+c^{\top}_{1}(\bar{z}_{h},s_{h};\theta)\\{\sum_{i=1}^{d^{\diamond}}\alpha_{i}(\pi(\bar{z}_{h}))\kappa(a^{i})\\};a_{1:h-1}\sim\pi^{\prime}]$
$\displaystyle=\mathbb{E}\left[c_{0}(\bar{z}_{h},s_{h};\theta)\left(1-\sum_{i=1}^{d^{\diamond}}\alpha_{i}(\pi(\bar{z}_{h}))\right)+\sum_{i=1}^{d^{\diamond}}\alpha_{i}(\pi(\bar{z}_{h}))\left(c^{\top}_{1}(\bar{z}_{h},s_{h};\theta)\kappa(a^{i})+c_{0}(\bar{z}_{h},s_{h};\theta)\right);a_{1:h-1}\sim\pi^{\prime}\right]$
$\displaystyle=\mathbb{E}\left[\left(1-\sum_{i=1}^{d^{\diamond}}\alpha_{i}(\pi(\bar{z}_{h}))\right)u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim
do(0)\right]$
$\displaystyle+\sum_{i=1}^{d^{\diamond}}\mathbb{E}\left[\alpha_{i}(\pi(\bar{z}_{h}))u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim
do(a^{i})\right].$

Thus, we can perform policy evaluation for a policy $\pi$ if we can do
intervention from $do(0),do(a^{1}),\cdots,do(a^{d^{\diamond}})$.

##### Fourth Step

The fourth step is replacing $do(0),do(a^{1}),\cdots,do(a^{d^{\diamond}})$
with a single policy that uniformly randomly select actions from the set
$\\{0,a^{1},\dots,a^{d^{\diamond}}\\}$, which we denote as $a\sim
U(1+d^{\diamond})$. Using importance weighting, we define the loss function
for $\pi,\theta$ as follows:

$\displaystyle\mathbb{E}[f_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta,\pi);a_{1:h-1}\sim\pi^{\prime},a_{h}\sim
U(1+d^{\diamond})]$ (13)

where $U(1+d^{\diamond})$ is a uniform action over
$0,a^{1},\cdots,a^{d^{\diamond}}$ and

$\displaystyle f_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta,\pi)$
$\displaystyle=|1+d^{\diamond}|\left(\mathbb{I}(a_{h}=0)\left(1-\sum_{i=1}^{d^{\diamond}}\alpha_{i}(\pi(\bar{z}_{h}))\right)+\sum_{i=1}^{d^{\diamond}}\mathbb{I}(a_{h}=a^{i})\alpha_{i}(\pi(\bar{z}_{h}))\right)u_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta).$

The term 13is equal to $\mathrm{Br}_{h}(\pi,g;\pi^{\prime})$ we want to
evaluate.

##### Summary

To summarize, we just need to use the following loss function in line 7 in
Algorithm 1:

$\displaystyle\mathbb{E}_{\mathcal{D}^{t}_{h}}[l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta,\pi)]$

where $l_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta,\pi)$ is

$\displaystyle\mathbb{I}(\|\bar{z}_{h}\|\leq Z_{1})\mathbb{I}(\|r_{h}\|\leq
Z_{2})\mathbb{I}(\|o_{h+1}\|\leq
Z_{3})f_{h}(\bar{z}_{h},a_{h},r_{h},o_{h+1};\theta,\pi)$

and $\mathcal{D}^{t}_{h}$ is a set of $m$ i.i.d samples following the
distribution induced by executing $a_{1:h-1}\sim\pi^{\prime},a_{h}\sim
U(1+d^{\diamond})$. Values $Z_{1},Z_{2},Z_{3}$ in indicators functions are
some large values selected properly later. Due to unbounded Gaussian noises in
LQG, indicators functions for truncation is introduced here for technical
reason to get valid concentration in Assumption 2.

##  Appendix D Supplement for Section 6

We first add several discussions to explain core tests in detail. Next, we
show the existence and form of link functions. Finally, we calculate the PO-
bilinear rank. In this section, we will focus on the general case where tests
could be multiple steps.

###  D.1 Definition of PSRs

We first define core tests and predictive states [littman2001predictive,
singh2004predictive]. This definition is a generalization of Definition 5 with
multi-step futures.

We slighly abuse notation and denote
$\tau^{a}_{h}:=(o_{1},a_{1},\dots,o_{h-1},a_{h-1})$ throughout this whole
section — note that $\tau^{a}_{h}$ here does not include $o_{h}$.

######  Definition 8 (Core test sets and PSRs).

A set
${\mathcal{T}}\subset\cup_{C\in\mathbf{N}^{+}}\mathcal{O}^{C}\times\mathcal{A}^{C-1}$
is called a core test set if for any $h\in[H]$, $W\in\mathbf{N}^{+}$, any
possible future (i.e., test)
$t_{h}=(o_{h:h+W-1},a_{h:h+W-2})\in\mathcal{O}^{W}\times\mathcal{A}^{W-1}$ and
any history $\tau^{a}_{h}$, there exists
$m_{t_{h}}\in\mathbb{R}^{|{\mathcal{T}}|}$ such that

$\displaystyle\mathbb{P}(o_{h:W+h-1}\mid\tau^{a}_{h};do(a_{h:W+h-2}))=\langle
m_{t_{h}},[\mathbb{P}(t\mid\tau^{a}_{h})]_{t\in{\mathcal{T}}}\rangle.$

The vector
$[\mathbb{P}(t\mid\tau^{a}_{h})]_{t\in{\mathcal{T}}}\in\mathbb{R}^{|{\mathcal{T}}|}$
is referred to as the predictive state.

We often denote
$\mathbf{q}_{\tau^{a}_{h}}=[\mathbb{P}(t\mid\tau^{a}_{h})]_{t\in{\mathcal{T}}_{h}}$.
To understand the above definition, we revisit observable undercomplete POMDPs
and overcomplete POMDPs.

######  Example 1 (Observable undercomplete POMDPs).

In undercomplete POMDPs, when $\mathbb{O}$ is full-column rank, $\mathcal{O}$
is a core test. Recall $\mathbb{O}$ is a matrix in
$\mathbb{R}^{|\mathcal{O}|\times|{\mathcal{S}}|}$ whose entry indexed by
$o_{i}\in\mathcal{O},s_{j}\in{\mathcal{S}}$ is equal to $\mathbb{O}(o_{i}\mid
s_{j})$.

######  Lemma 14 (Core tests in undercomplete POMDPs).

When $\mathbb{O}$ is full-column rank, $\mathcal{O}$ is a core test set.

###### Proof.

Consider any $h\in[H]$. Given a $|{\mathcal{S}}|$-dimensional belief state
$\mathbf{s}_{\tau^{a}_{h}}=[\mathbb{P}(\cdot\mid\tau^{a}_{h})]_{|{\mathcal{S}}|}$
with each entry $\mathbb{P}(s_{h}\mid\tau^{a}_{h})$, for any future
$t=(o_{h:h+W},a_{h:h+W-1})$, there exists a $|{\mathcal{S}}|$-dimensional
vector $\mathbf{m^{\prime}}_{t}$ such that
$\mathbb{P}(o_{h:h+W}\mid\tau^{a}_{h};do(a_{h:h+W-1}))=\langle\mathbf{m^{\prime}}_{t},\mathbf{s}_{\tau^{a}_{h}}\rangle$.
More specifically, ${\bf m^{\prime}}_{t}$ can be written as:

$\displaystyle({\bf
m^{\prime}}_{t})^{\top}=\mathbb{O}(o_{h+W}\mid{}\cdot)^{\top}\prod_{\tau=h}^{h+W-1}\mathbb{T}_{a_{h}}{\rm
diag}(\mathbb{O}(o_{h}\mid{}\cdot))$

where $\mathbb{O}(o|\cdot)\in\mathbb{R}^{|{\mathcal{S}}|}$ is a vector with
the entry indexed by $s$ equal to $\mathbb{O}(o|s)$,